[Bug middle-end/107709] New: IVOPTs is introducing a non-zero assumption

[Bug middle-end/107709] New: IVOPTs is introducing a non-zero assumption

[amacleod at redhat dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=107709

            Bug ID: 107709
           Summary: IVOPTs is introducing a non-zero assumption
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: middle-end
          Assignee: unassigned at gcc dot gnu.org
          Reporter: amacleod at redhat dot com
  Target Milestone: ---

Ive been working on fixing https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78655 ,
which basically adds an inferred range to

  ptr1 = ptr2 + non-zero-const

such that ptr2 will be non-zero after this statement.  Ive spent the last
couple of days trying to figure out why fortran is failing in a bootstrap, and
I think I finally have it figured out.  fortran/scanner.c is being miscompiled
at -O2, and it boils down to the following testcase:

char *nextc;

void huh ()
{
  int i;
  char c;

  for (i = 0; i < 5; i++)
    {
      c = (nextc == 0) ? '\n' : *nextc++;
      if (c != ' ')
        break;
    }
}

The very beginning of this function, just before going into ivopts, looks like:

  char * prephitmp_3;
  char * pretmp_4;
  unsigned int ivtmp_14;
  unsigned int ivtmp_15;

  <bb 2> [local count: 243289824]:
  pretmp_4 = nextc;

  <bb 3> [local count: 894749065]:
  # prephitmp_3 = PHI <_2(7), pretmp_4(2)>
  # ivtmp_14 = PHI <ivtmp_15(7), 5(2)>
  if (prephitmp_3 != 0B)
    goto <bb 5>; [96.34%]
  else
    goto <bb 8>; [3.66%]

  <bb 8> [local count: 32747817]:

  <bb 4> [local count: 243289824]:
  return;

note that prephitmp_3 will be pretmp4 to start the loop (edge 2->3), and then
it is checked against 0 (NULL) and processing only continues to BB5 if it isnt
NULL.

After IVOPTS runs, this is transformed into:

 <bb 2> [local count: 243289824]:
  pretmp_4 = nextc;
  _12 = pretmp_4 + 5;              <-- New introduction

  <bb 3> [local count: 894749065]:
  # prephitmp_3 = PHI <_2(7), pretmp_4(2)>
  if (prephitmp_3 != 0B)
    goto <bb 5>; [96.34%]
  else
    goto <bb 8>; [3.66%]

  <bb 8> [local count: 32747817]:

  <bb 4> [local count: 243289824]:
  return;

Note it has added
   _12 = pretmp_4 + 5
to basic block 2.

With the new code to instruct VRP that ptr1 = ptr2 + const  means ptr2 is
non-null,  it now propagates a range of [+1, +INF] for pretmp_4 on the edge
2->3, and that allows the condition which checks prephitmp_3 != 0 to be folded,
as _2 is always non-zero as well.

It seems that IVOPTS should not be adding that statement into BB2? It is
introducing a non-zero assumption that is not there before.

[Bug middle-end/107709] IVOPTs is introducing a non-zero assumption

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=107709

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
IVOPTs is usually quite careful with this and the infer of non-NULL from
ptr + CST is new - that introduced a new undefinedness in GIMPLE.  The
workaround would be to avoid the POINTER_PLUS_EXPR here and perform the
increment in an unsigned type.

You can see it creates

<Invariant Expressions>:
inv_expr 1:     (signed int) (unsigned long) (pretmp_4 + 1) + 5
inv_expr 2:     (signed int) (unsigned long) pretmp_4 + 5
inv_expr 3:     (signed int) pretmp_4 + 5
inv_expr 4:     (signed long) pretmp_4 + 1

and only the pretmp_4 + 1 somehow slips through here.

This is built in aff_combination_to_tree via
may_eliminate_iv and there cand_value_at which adds
iv->base as pointer.  IIRC that was done on purpose to help
association and optimization.  So this new undefined behavior hurts here.

The following fixes this

diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc
index a6f926a68ef..0f180f70ff6 100644
--- a/gcc/tree-ssa-loop-ivopts.cc
+++ b/gcc/tree-ssa-loop-ivopts.cc
@@ -5233,7 +5233,7 @@ cand_value_at (class loop *loop, struct iv_cand *cand,
gimple *at,
     aff_combination_add (&delta, &step);

   tree_to_aff_combination (iv->base, type, val);
-  if (!POINTER_TYPE_P (type))
+  //if (!POINTER_TYPE_P (type))
     aff_combination_convert (val, steptype);
   aff_combination_add (val, &delta);
 }

but we for example still see pretmp_4 + 1 in the SCEV analysis result:

(get_scalar_evolution
  (scalar = _2)
  (scalar_evolution = {pretmp_4 + 1, +, 1}_1))

it basically means the compiler can nowhere build a POINTER_PLUS_EXPR
without being sure the pointer is not NULL.  There same issue is already
existing for building signed arithmetic (that may not overflow).

I was last changing the above code to fix the signed arithmetic issue with
r0-129164-gd6adff07f12460 but exempted pointer types there.

Now, do we really want to introduce this new undefined behavior without
seriously auditing the code base?

[Bug middle-end/107709] IVOPTs is introducing a non-zero assumption

[amacleod at redhat dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=107709

--- Comment #2 from Andrew Macleod <amacleod at redhat dot com> ---
(In reply to Richard Biener from comment #1)
> IVOPTs is usually quite careful with this and the infer of non-NULL from
> ptr + CST is new - that introduced a new undefinedness in GIMPLE.  The
> workaround would be to avoid the POINTER_PLUS_EXPR here and perform the
> increment in an unsigned type.
> 
> 
> Now, do we really want to introduce this new undefined behavior without
> seriously auditing the code base?

I think not. I will defer the inferred range code until next release to give us
a chance to sort this kind of thing out. I will attach the patch to PR 78655,
which when it is applied triggers the bug.  That way it is easy to at least
find this one..  I can probably even attach an executable test to this PR that,
when combined with that patch, will fail.  I think :-)

[Bug middle-end/107709] IVOPTs is introducing a non-zero assumption

[amacleod at redhat dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=107709

--- Comment #3 from Andrew Macleod <amacleod at redhat dot com> ---
we might be able to provide a lightweight ranger based query to determine if an
ssa_name is  non-null in a block.. in fact..  we may not need anything special.

/* Create a new ranger instance and associate it with a function.
   Each call must be paired with a call to disable_ranger to release
   resources.  If USE_IMM_USES is true, pre-calculate sideffects like
   non-null uses as required using the immediate use chains.  */
extern gimple_ranger *enable_ranger (struct function *m,
                                     bool use_imm_uses = true);

simply using the on-demand default which sets use_imm_uses to true is probably
enough,  When a pointer is queried, if it hasn't been done yet, all immediate
uses are scanned and if there is an inferred range, those blocks are tagged
with an on-exit range on non-zero.

simply querying get_range_query->range_of_expr (r, name, stmt)  will then walk
the dom tree and tell you through r if name is non-zero or not.

If we end up needing something more efficient for this purpose, we could
harvest that code and produce a module which much more efficiently processes
inferred ranges simply looking for whether a specific property is true or not