[Bug tree-optimization/103721] New: [12 regression] wrong code generated for loop with conditional (jump threading?)

[Bug tree-optimization/103721] New: [12 regression] wrong code generated for loop with conditional (jump threading?)

[sss@li-snyder.org]

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

            Bug ID: 103721
           Summary: [12 regression] wrong code generated for loop with
                    conditional (jump threading?)
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: sss@li-snyder.org
  Target Milestone: ---

hi -

With a recent checkout of gcc12 (20211214), on a x86_64-pc-linux-gnu host,
the following source is miscompiled with -O2:

-- x.cc --------------------------------------------------
bool flag();
const int* bar();

const int* f (const int* world)
{
  const int* searchVolume = world;
  const int* currentVolume = nullptr;
  while (currentVolume != searchVolume && searchVolume) {
    currentVolume = searchVolume;
    if (flag())
      searchVolume = bar();
  }
  return (currentVolume);
}
----------------------------------------------------------


This can be demonstrated with this test harness:


-- test.cc -------------------------------------------------
#include <stdio.h>

const int* f (const int* world);
bool flag() { return true; }

int ii[3] = {0};
int ipos = 0;

const int *bar() {
  if (ipos == 2)
    return nullptr;
  return &ii[++ipos];
}

int main()
{
  const int* i = f (&ii[0]);
  printf ("%d\n", i - &ii[0]);
  return 0;
}
------------------------------------------------------------

I expect this to print 2, which it does when compiled with -O0 or O1.
But with -O2:

$ g++ -c -O2 x.cc -o x.o
$ g++ -o test  test.cc x.o
$ ./test
0


Here is the generated code for the function f (directives removed
for readability):

_Z1fPKi:
.LFB0:
        pushq   %rbx
        movq    %rdi, %rbx
        testq   %rdi, %rdi
        je      .L2
        call    _Z4flagv
        testb   %al, %al
        jne     .L10
.L2:
        movq    %rbx, %rax
        popq    %rbx
        ret
.L10:
        call    _Z3barv
        movq    %rbx, %rax
        popq    %rbx
        ret


As one can see, in the generated code, the loop is not executed more
than once.  It appears as if the fact that searchVolume can be changed
within the if statement is being lost --- if the conditional is commented
out, then things work as expected.

Things seem to go bad by at least the threadfull1 pass.
In the previous pass, 110t.mergephi2, we have:

-----------------------------------------------------------------

;; Function f (_Z1fPKi, funcdef_no=0, decl_uid=2370, cgraph_uid=1,
symbol_order=0)

Removing basic block 6
const int * f (const int * world)
{
  const int * currentVolume;
  const int * searchVolume;
  bool _1;
  bool _2;
  bool _3;
  bool _14;
  const int * _16;

  <bb 2> [local count: 118111600]:
  goto <bb 8>; [100.00%]

  <bb 3> [local count: 955630225]:
  _14 = flag ();
  if (_14 != 0)
    goto <bb 4>; [33.00%]
  else
    goto <bb 8>; [67.00%]

  <bb 4> [local count: 315357972]:
  _16 = bar ();

  <bb 8> [local count: 1073741824]:
  # searchVolume_4 = PHI <_16(4), world_7(D)(2), searchVolume_4(3)>
  # currentVolume_5 = PHI <searchVolume_4(4), 0B(2), searchVolume_4(3)>
  _1 = searchVolume_4 != currentVolume_5;
  _2 = searchVolume_4 != 0B;
  _3 = _1 & _2;
  if (_3 != 0)
    goto <bb 3>; [89.00%]
  else
    goto <bb 7>; [11.00%]

  <bb 7> [local count: 118111600]:
  return currentVolume_5;

}



-----------------------------------------------------------------

which does seem to represent the loop correctly.
But in 111t.threadfull1, this has been changed to:

------------------------------------------------------------------


;; Function f (_Z1fPKi, funcdef_no=0, decl_uid=2370, cgraph_uid=1,
symbol_order=0)

Disambiguating loop 1 with multiple latches
Merged latch edges of loop 1
;; 2 loops found
;;
;; Loop 0
;;  header 0, latch 1
;;  depth 0, outer -1
;;  nodes: 0 1 2 3 4 8 9 7
;;
;; Loop 1
;;  header 9, latch 8
;;  depth 1, outer 0
;;  nodes: 9 8 4 3
;; 2 succs { 9 }
;; 3 succs { 4 8 }
;; 4 succs { 8 }
;; 8 succs { 9 }
;; 9 succs { 3 7 }
;; 7 succs { 1 }
Jump threading proved probability of edge 9->7 too small (it is 11.0% (guessed)
should be always (guessed))

SSA replacement table
N_i -> { O_1 ... O_j } means that N_i replaces O_1, ..., O_j

searchVolume_12 -> { searchVolume_4 }
currentVolume_17 -> { currentVolume_5 }
.MEM_18 -> { .MEM_6 }
_19 -> { _1 }
_20 -> { _2 }
_21 -> { _3 }
currentVolume_22 -> { currentVolume_5 }
.MEM_23 -> { .MEM_6 }
Incremental SSA update started at block: 9
Number of blocks in CFG: 11
Number of blocks to update: 6 ( 55%)


Merging blocks 2 and 9
Merging blocks 8 and 10
const int * f (const int * world)
{
  const int * currentVolume;
  const int * searchVolume;
  bool _1;
  bool _2;
  bool _3;
  bool _14;
  const int * _16;
  bool _19;
  bool _20;
  bool _21;

  <bb 2> [local count: 118111600]:
  _1 = world_7(D) != 0B;
  _2 = world_7(D) != 0B;
  _3 = _1 & _2;
  if (_3 != 0)
    goto <bb 3>; [97.00%]
  else
    goto <bb 6>; [3.00%]

  <bb 3> [local count: 955630225]:
  _14 = flag ();
  if (_14 != 0)
    goto <bb 4>; [33.00%]
  else
    goto <bb 5>; [67.00%]

  <bb 4> [local count: 315357972]:
  _16 = bar ();

  <bb 5> [local count: 955630224]:
  # searchVolume_11 = PHI <_16(4), world_7(D)(3)>
  # currentVolume_8 = PHI <world_7(D)(4), world_7(D)(3)>
  _19 = currentVolume_8 != searchVolume_11;
  _20 = searchVolume_11 != 0B;
  _21 = _19 & _20;

  <bb 6> [local count: 118111600]:
  # currentVolume_22 = PHI <0B(2), currentVolume_8(5)>
  return currentVolume_22;

}

------------------------------------------------------------------

which has no backwards branch.

[Bug tree-optimization/103721] [12 regression] wrong code generated for loop with conditional (jump threading?)

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |wrong-code
   Target Milestone|---                         |12.0

[Bug tree-optimization/103721] [12 regression] wrong code generated for loop with conditional (jump threading?)

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2021-12-14
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Confirmed.
Here is one which does not use pointers and inlining does not matter:
int ipos = 0;
int f (int world)
{
  int searchVolume = world;
  int currentVolume = 0;
  while (currentVolume != searchVolume && searchVolume) {
    currentVolume = searchVolume;
    if (ipos != 0)
      searchVolume = 0;
    else
      searchVolume = 1;
  }
  return (currentVolume);
}
int main()
{
  const int i = f (1111);
  __builtin_printf ("%d\n", (int)(i));
  if (i != 1)
   __builtin_abort ();
  return 0;
}

[Bug tree-optimization/103721] [12 regression] wrong code generated for loop with conditional since r12-4790-g4b3a325f07acebf4

[marxin at gcc dot gnu.org]

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

Martin Liška <marxin at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[12 regression] wrong code  |[12 regression] wrong code
                   |generated for loop with     |generated for loop with
                   |conditional (jump           |conditional since
                   |threading?)                 |r12-4790-g4b3a325f07acebf4
                 CC|                            |aldyh at gcc dot gnu.org,
                   |                            |amacleod at redhat dot com,
                   |                            |marxin at gcc dot gnu.org

--- Comment #2 from Martin Liška <marxin at gcc dot gnu.org> ---
Started with r12-4790-g4b3a325f07acebf4.

[Bug tree-optimization/103721] [12 regression] wrong code generated for loop with conditional since r12-4790-g4b3a325f07acebf4

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P1

[Bug tree-optimization/103721] [12 regression] wrong code generated for loop with conditional since r12-4790-g4b3a325f07acebf4

[amacleod at redhat dot com]

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

Andrew Macleod <amacleod at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jeffreyalaw at gmail dot com

--- Comment #3 from Andrew Macleod <amacleod at redhat dot com> ---
After the initial loop tweaking, the IL that the threader sees in 
v.c.111t.threadfull1 is:

;;   basic block 2, loop depth 0
  goto <bb 10>; [100.00%]

;;   basic block 3, loop depth 1
  ipos.0_2 = ipos;
  if (ipos.0_2 != 0)
    goto <bb 6>; [50.00%]
  else
    goto <bb 4>; [50.00%]

;;   basic block 4, loop depth 1

;;   basic block 6, loop depth 1
  # searchVolume_11 = PHI <1(4), 0(3)>
  # currentVolume_10 = PHI <searchVolume_5(4), searchVolume_5(3)>

;;   basic block 10, loop depth 1
  # searchVolume_5 = PHI <searchVolume_11(6), 1111(2)>
  # currentVolume_6 = PHI <currentVolume_10(6), 0(2)>
  _7 = searchVolume_5 != currentVolume_6;
  _8 = searchVolume_5 != 0;
  _9 = _7 & _8;
  if (_9 != 0)
    goto <bb 3>; [89.00%]
  else
    goto <bb 7>; [11.00%]


It looks to me like it decides to thread 2->10, which means it turns bb2 into
something like:


 # searchVolume_5 = 1111
  # currentVolume_6 = 0
  _7 = searchVolume_5 != currentVolume_6;    // folds to 1
  _8 = searchVolume_5 != 0;                  // folds to 1
  _9 = _7 & _8;                              //folds to 1
  if (_9 != 0)                               // folds to goto bb3 
    goto <bb 3>; [89.00%]
  else
    goto <bb 7>; [11.00%]

And then it updates the PHIS in BB10 to not have an edge from bb2:    (note I
am doing this by hand, not actually renaming any ssa_names.)

;;   basic block 10, loop depth 1
  # searchVolume_5 = PHI <searchVolume_11(6)>
  # currentVolume_6 = PHI <currentVolume_10(6)>
  _7 = searchVolume_5 != currentVolume_6;
  _8 = searchVolume_5 != 0;
  _9 = _7 & _8;
  if (_9 != 0)
    goto <bb 3>; [89.00%]
  else
    goto <bb 7>; [11.00%]

The problem would seem to be that when we thread 2->10, we are actually peeling
off an iteration of the loop. the PHIs in BB6:
;;   basic block 6, loop depth 1
  # searchVolume_11 = PHI <1(4), 0(3)>
  # currentVolume_10 = PHI <searchVolume_5(4), searchVolume_5(3)>

I think currentVolume_10 is picking up searchVolume_5 calulated from the
threaded entry point, which is the constant 1111... and we are "losing" the
information that it could also be the value of searchVolume_11 from the
previous iteration. 

Threading is out of my wheel house, but Its not clear to me how you could even
update the PHI nodes properly if you try to thread that path... 
And its starting to give me a headache thinking about it :-)  

It seem that needs to be a new phi inserted in BB3 which sets searchvolume_5 =
PHI <1111(2), searchVolume_11(10)>  Or something to that efffect.
something is missing anyway.

[Bug tree-optimization/103721] [12 regression] wrong code generated for loop with conditional since r12-4790-g4b3a325f07acebf4

[law at gcc dot gnu.org]

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

Jeffrey A. Law <law at gcc dot gnu.org> changed:

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

--- Comment #4 from Jeffrey A. Law <law at gcc dot gnu.org> ---
But what doesn't make any sense here is the folding in this block:

<bb 9> [local count: 1073741824]:
# searchVolume_5 = PHI <searchVolume_11(8), world_7(D)(2)>
# currentVolume_6 = PHI <currentVolume_8(8), 0(2)>
_2 = searchVolume_5 != currentVolume_6;
_3 = searchVolume_5 != 0;
_4 = _2 & _3;
if (_4 != 0)
  goto <bb 3>; [89.00%]
else
  goto <bb 7>; [11.00%]


In fold_using_range::range_of_range_op we have:

(gdb) p debug_tree (op1)
 <ssa_name 0x7ffff77fef30
    type <integer_type 0x7ffff780e5e8 int sizes-gimplified public SI
        size <integer_cst 0x7ffff77f3f90 constant 32>
        unit-size <integer_cst 0x7ffff77f3fa8 constant 4>
        align:32 warn_if_not_align:0 symtab:0 alias-set 1 canonical-type
0x7ffff780e5e8 precision:32 min <integer_cst 0x7ffff77f3f48 -2147483648> max
<integer_cst 0x7ffff77f3f60 2147483647>
        pointer_to_this <pointer_type 0x7ffff7816a80>>
    visited var <var_decl 0x7ffff7a12cf0 searchVolume>
    def_stmt searchVolume_5 = PHI <searchVolume_11(8), world_7(D)(2)>
    version:5>
$113 = void
(gdb) p debug_tree (op2)
 <ssa_name 0x7ffff77fef78
    type <integer_type 0x7ffff780e5e8 int sizes-gimplified public SI
        size <integer_cst 0x7ffff77f3f90 constant 32>
        unit-size <integer_cst 0x7ffff77f3fa8 constant 4>
        align:32 warn_if_not_align:0 symtab:0 alias-set 1 canonical-type
0x7ffff780e5e8 precision:32 min <integer_cst 0x7ffff77f3f48 -2147483648> max
<integer_cst 0x7ffff77f3f60 2147483647>
        pointer_to_this <pointer_type 0x7ffff7816a80>>
    visited var <var_decl 0x7ffff7a12d80 currentVolume>
    def_stmt currentVolume_6 = PHI <currentVolume_8(8), 0(2)>
    version:6>
$114 = void
(gdb) p rel
$115 = EQ_EXPR

If I'm reading the code correctly I think that means that the ranger has
determined that _5 and _6 are equal.  But I don't see how it can possibly make
that determination with this CFG:

int f (int world)
{
  int currentVolume;
  int searchVolume;
  int ipos.0_1;
  _Bool _2;
  _Bool _3;
  _Bool _4;

;;   basic block 2, loop depth 0
;;    pred:       ENTRY
  goto <bb 9>; [100.00%]
;;    succ:       9

;;   basic block 3, loop depth 1
;;    pred:       9
  ipos.0_1 = ipos;
  if (ipos.0_1 != 0)
    goto <bb 8>; [50.00%]
  else
    goto <bb 4>; [50.00%]
;;    succ:       8
;;                4

;;   basic block 4, loop depth 1
;;    pred:       3
;;    succ:       8

;;   basic block 8, loop depth 1
;;    pred:       4
;;                3
  # searchVolume_11 = PHI <1(4), 0(3)>
  # currentVolume_8 = PHI <searchVolume_5(4), searchVolume_5(3)>
;;    succ:       9

;;   basic block 9, loop depth 1
;;    pred:       8
;;                2
  # searchVolume_5 = PHI <searchVolume_11(8), world_7(D)(2)>
  # currentVolume_6 = PHI <currentVolume_8(8), 0(2)>
  _2 = searchVolume_5 != currentVolume_6;
  _3 = searchVolume_5 != 0;
  _4 = _2 & _3;
  if (_4 != 0)
    goto <bb 3>; [89.00%]
  else
    goto <bb 7>; [11.00%]
;;    succ:       3
;;                7

;;   basic block 7, loop depth 0
;;    pred:       9
  return currentVolume_6;
;;    succ:       EXIT

}

This feels like it's got to be a problem in the equivalence handling -- it's
largely outside the threader.

My recollection of equivalences in loops is that they're exceedingly hard to
get correct once you follow the backedge -- particularly since you have to
invalidate some equivalences once you traverse that backedge.  Finding the set
that needed to be invalidated was expensive and the book keeping turned out to
be too hard to do reliably so I ripped it all out.

How does equivalence handling in the Ranger world work once you traverse the
backedge of a loop?

[Bug tree-optimization/103721] [12 regression] wrong code generated for loop with conditional since r12-4790-g4b3a325f07acebf4

[amacleod at redhat dot com]

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

--- Comment #5 from Andrew Macleod <amacleod at redhat dot com> ---


> How does equivalence handling in the Ranger world work once you traverse the
> backedge of a loop?


There are 2 aspects. Ranger itself registers equivalence sets by basic block,
not by name.  All lookups are done via the dominator tree.

The definition of a name creates an equivalence record containing just that
name in it def block. When that name is registered in an equivalence,  there
will be an equivalence record in that block created combining the equivalence
set of each name in the block.

When we check for equivalence, we look up the "current" equivalence set for
BOTH names in the dominator tree. They are only considered equivalent if both
queries come up with the same set. Anything else means the equivalence set for
one of the names has changed, so they are no longer equivalent. 

So far I have not found this to be an issue with back edges. We basically defer
validation of equivalences until we go to look it up, and then require the 2
searches to come back with the same result. With the Definitions acting as
"equivalency" killers, we don't pick up old equivalencies from back edges. 

Assuming I set everything up right :-) 

The threader adds a path_oracle on top of that which proceeds to manage its own
relations and equivalences along the path.  It first tries to resolve
equivalences from within the path, and if it doesn't find anything, reverts to
a ranger query at the top of the path. Thus is can inherit anything ranger
knows coming into the path but it is subject to getting things right within the
path. There have been a few issues along the way getting this right.

I think I may have found the issue with this particular case:

When I try to thread the path by hand, it boils down to the following
(equivalence set created in { }:

  <bb2>
  <bb9>
  # searchVolume_5 = PHI <world_7(D)(2)>     { _5, world_7 }
  # currentVolume_6 = PHI <0(2)>             { _6 }
  [1,1] = searchVolume_5 != currentVolume_6;
  [1,1] = searchVolume_5 != 0;
  [1,1] = _2 & _3;
    goto <bb 3>; [89.00%]

  <bb3>
  <bb4>
  <bb8>
  # searchVolume_11 = PHI <1(4), 0(3)>      { _11 }
  # currentVolume_8 = searchVolume_5        { _5, _8 , world_7 }

  <bb9>
  # searchVolume_5 = PHI <searchVolume_11(8)>    { _5, _11 }
  # currentVolume_6 = PHI <currentVolume_8(8)>      { whoops }
  _2 = searchVolume_5 != currentVolume_6
  _3 = searchVolume_5 != 0;
  _4 = _2 & _3;

When it creates the equivalency set for _6, it queries the equivalence set of
_8, and comes up with { _5, _8, world_7 }..  which is wrong because _5 is in a 
set with {_5, _11} now.  

In fact, the code wont come out exactly like this in the end because its SSA.
so the  _5 and _6 will be renamed to something new, but I think we are doing
the analysis using the original names until wehave done all the threading.. 
Which is why we are folding the _5 != _6 comparison "thinking" they are
equivalent.

First, When we combine the equivalence sets for _6 and _8, we should be
confirming the equivalence set matches for each element.. 
so a check for _5, _8 and world_7 would eliminate _5 from the equivalency set
for _8.... and we would then generate an equivalency set of
 {_6, _8, world_7 }...   which would then be correct.

What its missing is we aren't suppose to register the equivalency set without
confirming each member at that location.

Even fixing this, I think there is still an issue as this does not fix
pr104067..  so I think there is still an underlying issue within the path
oracle.  

I dont know precisely how it all works together but I believe the threader
queues up all its changes, and then does all the work at the end?  I think
there is something going on with different generations of name from one thread
to another.  I'll try to work thru it and discuss it with aldy tomorrow when he
returns.

[Bug tree-optimization/103721] [12 regression] wrong code generated for loop with conditional since r12-4790-g4b3a325f07acebf4

[aldyh at gcc dot gnu.org]

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

--- Comment #6 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
Please bear with me, as I'm coming up to speed, and my head hurts from all
these equivalences.

The problem seems to be what Jeff mentioned in comment #4.

We think _5 == _6, which makes the conditional in BB9 always false.  This
allows us to thread 8->9->7:

  <bb 9> [local count: 1073741824]:
  # searchVolume_5 = PHI <searchVolume_11(8), world_7(D)(2)>
  # currentVolume_6 = PHI <currentVolume_8(8), 0(2)>
  _2 = searchVolume_5 != currentVolume_6;
  _3 = searchVolume_5 != 0;
  _4 = _2 & _3;
  if (_4 != 0)
    goto <bb 3>; [89.00%]
  else
    goto <bb 7>; [11.00%]

With --param=threader-debug=all we can see the threader registering the path:

  [1] Registering jump thread: (8, 9) incoming edge;  (9, 7) nocopy; 

The bits immediately preceding it are the solver in action for the proposed
path.  Of particular interest is:

path_range_query: compute_ranges for path: 8->9
 Registering value_relation (currentVolume_8 == searchVolume_5) (bb8) at
currentVolume_8 = PHI <searchVolume_5(4), searchVolume_5(3)>
range_defined_in_block (BB8) for currentVolume_8 is int [-INF, -1][1, +INF]
  from bb9: Registering killing_def (path_oracle) searchVolume_5
 Registering value_relation (path_oracle) (searchVolume_11 == searchVolume_5)
(bb8)
  from bb9: Registering killing_def (path_oracle) currentVolume_6
 Registering value_relation (path_oracle) (currentVolume_8 == currentVolume_6)
(bb8)
range_defined_in_block (BB9) for searchVolume_5 is int [0, 1]
range_defined_in_block (BB9) for currentVolume_6 is int [-INF, -1][1, +INF]

path_oracle:
Equivalence set : [searchVolume_5, currentVolume_6, currentVolume_8]
Equivalence set : [currentVolume_6]
Equivalence set : [searchVolume_5, searchVolume_11]
Equivalence set : [searchVolume_5]

Notice the entry at the top of the path_oracle equivalence queue:

Equivalence set : [searchVolume_5, currentVolume_6, currentVolume_8]

The sequence of events that got us here is the following:

1. When calculating the PHIs for the path, we start at BB8, which triggers a
global ranger's range_of_expr.  We do this, to see if there's anything the
global ranger knows on entry to the path.  This in turn registers an equiv for
_8 == _5 in the *root* oracle (not the path specific one):

 Registering value_relation (currentVolume_8 == searchVolume_5) (bb8) at
currentVolume_8 = PHI <searchVolume_5(4), searchVolume_5(3)>

2. Then in BB9 we set up the following path specific equiv:

 Registering value_relation (path_oracle) (currentVolume_8 == currentVolume_6)
(bb8)

Since the root oracle has _8 == _5, this means we "know" that _8 == _6 == _5 in
the path.

Shit rolls downhill from here.

[Bug tree-optimization/103721] [12 regression] wrong code generated for loop with conditional since r12-4790-g4b3a325f07acebf4

[aldyh at gcc dot gnu.org]

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

--- Comment #7 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
After chatting with Andrew about this, it seems the problem is we are starting
a path mid-loop and crossing a backedge.  This causes us to use relations we
had on one iteration in another iteration.

  <bb 8> [local count: 955630225]:
  # searchVolume_11 = PHI <1(4), 0(3)>
  # currentVolume_8 = PHI <searchVolume_5(4), searchVolume_5(3)>
  # **BACKEDGE**

  <bb 9> [local count: 1073741824]:
  # searchVolume_5 = PHI <searchVolume_11(8), world_7(D)(2)>
  # currentVolume_6 = PHI <currentVolume_8(8), 0(2)>
  _2 = searchVolume_5 != currentVolume_6;
  _3 = searchVolume_5 != 0;
  _4 = _2 & _3;
  if (_4 != 0)
    goto <bb 3>; [89.00%]
  else
    goto <bb 7>; [11.00%]
...
...
 <bb3>
 <bb4>
 <bb8>

The _8 == _5 relation in BB8 is using _5 from a previous iteration (that came
through BB9).  Basically 8->9 has a use before def of _5.

Once we hit a back edge, we should probably kill all current relations and
disable looking outside the path altogether for relations.

I will experiment.

[Bug tree-optimization/103721] [12 regression] wrong code generated for loop with conditional since r12-4790-g4b3a325f07acebf4

[amacleod at redhat dot com]

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

--- Comment #8 from Andrew Macleod <amacleod at redhat dot com> ---
No probably about it :-) 

As soon as the path crosses a back edge, we can encounter definitions of
SSA_NAMEs that may have had a use in the path already, so this will then be a
new definition.   The relation code is all designed around seeing things in
dominator order, and crossing a back edge in the path violates this assumption.

I thunk purging all relations from the current path list is safe/necessary when
we traverse a back edge, and then I think you can start registering new ones.

Its unclear to me whether its safe to query the root oracle again from the loop
top rather than path start at this point.  It would depend on whether we can be
assured it dominates every other node in the path already.

[Bug tree-optimization/103721] [12 regression] wrong code generated for loop with conditional since r12-4790-g4b3a325f07acebf4

[law at gcc dot gnu.org]

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

--- Comment #9 from Jeffrey A. Law <law at gcc dot gnu.org> ---
I think Andrew has raised a really interesting issue.  If the relation code is
designed around seeing things in dominator order, then don't we have to stop
using it once we traverse any edge where the edge source does not dominate the
edge destination (assume this is a partial graph rather than a multi-entry
function ;-)



   1  2   3
   |   \ /
   |    4
   |   / \
   +->5   6
     / \
    7   8


Note how BB4 does not dominate BB5.  If we try to thread something like
2->4->5->?, then can't we run into problems with the equivalence handling as
well, even though we're not dealing with a loop?

[Bug tree-optimization/103721] [12 regression] wrong code generated for loop with conditional since r12-4790-g4b3a325f07acebf4

[amacleod at redhat dot com]

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

--- Comment #10 from Andrew Macleod <amacleod at redhat dot com> ---
(In reply to Jeffrey A. Law from comment #9)

> 
> 
> 
>    1  2   3
>    |   \ /
>    |    4
>    |   / \
>    +->5   6
>      / \
>     7   8
> 
> 
> Note how BB4 does not dominate BB5.  If we try to thread something like
> 2->4->5->?, then can't we run into problems with the equivalence handling as
> well, even though we're not dealing with a loop?

Well, if the top of the path does not dominate an element of the path.. then
maybe yes.

The way it currently works, the assumption is that each node of the path
dominates the previous node. and for processing the path itself, this should be
fine since we add relations as we walk the path and its a linear path.

The problem with back edges was we start to see the same SSA name a second
time...  which is really bad karma and we really need to reset the path
relations immediately.

The next problem which you point out is when a relation does not occur in the
path.  Then we query from the top of the path using ranger.

So if the top of the path does not dominate some element of the path, and we
make a query from there, then yes, we are open to an possible issue if we make
a ranger query.  Otherwise I think we are OK because we are simply walking the
path and by definition the earlier elements of the path dominate the next one.
.

Perhaps the rule should be...  if the next block is not dominated by the path
root, reset all relations, and reset the root to the common dominator of the
original root and the new node?   

OR perhaps thats too aggressive and we reset path relations only on back edges,
and reset the root to the common dominator whenever we encounter a node not
dominated by the path start?

[Bug tree-optimization/103721] [12 regression] wrong code generated for loop with conditional since r12-4790-g4b3a325f07acebf4

[aldyh at gcc dot gnu.org]

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

--- Comment #11 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
The testcase for PR104067 shows an example where the dominance matters,
irregardless of if we reset relations at the backedge point.  There we have a
path that looks like 9->3->5->...:

 <bb 3> [local count: 1063004409]:
  # j_17 = PHI <j_2(9), 0(2)>
  # q_18 = PHI <prephitmp_16(9), &a(2)>
  # ivtmp_4 = PHI <ivtmp_3(9), 99(2)>
  j_8 = j_17 + 1;
  if (j_8 == 10)
    goto <bb 5>; [34.00%]
  else
    goto <bb 4>; [66.00%]

  <bb 4> [local count: 701582906]:
  _1 = (sizetype) j_8;
  _15 = _1 * 4;
  _14 = &a + _15;

  <bb 5> [local count: 1063004409]:
  # j_2 = PHI <j_8(4), 0(3)>
  # prephitmp_16 = PHI <_14(4), &a(3)>
  if (prephitmp_16 == q_18)
    goto <bb 6>; [0.00%]
  else
    goto <bb 7>; [100.00%]

  <bb 9> [local count: 1052374367]:
  goto <bb 3>; [100.00%]

Even if we reset relations and clear the root oracle at the backedge (9->3), we
still get the _16 == _18 in BB3, followed by the DEF of _16 in BB5.

[Bug tree-optimization/103721] [12 regression] wrong code generated for loop with conditional since r12-4790-g4b3a325f07acebf4

[aldyh at gcc dot gnu.org]

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

--- Comment #12 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
Created attachment 52240
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=52240&action=edit
proposed untested patch

This is a proposed patch that fixes both PRs.  Perhaps we can tweak the
dominance check in relations_may_be_invalidated to be less aggressive.

[Bug tree-optimization/103721] [12 regression] wrong code generated for loop with conditional since r12-4790-g4b3a325f07acebf4

[aldyh at gcc dot gnu.org]

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

Aldy Hernandez <aldyh at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bonzini at gnu dot org

--- Comment #13 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
*** Bug 104067 has been marked as a duplicate of this bug. ***

[Bug tree-optimization/103721] [12 regression] wrong code generated for loop with conditional since r12-4790-g4b3a325f07acebf4

[amacleod at redhat dot com]

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

--- Comment #14 from Andrew Macleod <amacleod at redhat dot com> ---
(In reply to Aldy Hernandez from comment #11)
> <bb 3> [local count: 1063004409]:
>  # j_17 = PHI <j_2(9), 0(2)>
>  # q_18 = PHI <prephitmp_16(9), &a(2)>
>

>   <bb 5> [local count: 1063004409]:
>   # j_2 = PHI <j_8(4), 0(3)>
>   # prephitmp_16 = PHI <_14(4), &a(3)>
>   if (prephitmp_16 == q_18)
>     goto <bb 6>; [0.00%]
>   else
>     goto <bb 7>; [100.00%]
> 
>   <bb 9> [local count: 1052374367]:
>   goto <bb 3>; [100.00%]
> 
> Even if we reset relations and clear the root oracle at the backedge (9->3),
> we still get the _16 == _18 in BB3, followed by the DEF of _16 in BB5.

Well, you cant add that relation either..    although you have cleared the
existing relations when you traverse the back edge, you are then immediately
adding another one FROM the backedge (9->3) which is a value from the previous
iteration... so it cant be used. 

You need to also stipulate that if you are adding an equivalence from a PHI
like that, it is not a back edge you are adding from.


And I think it is probably safe to "reset" the root oracle to search for
relations from top of the loop, assuming it dominates the latch it came from. 
Any new relations are going to now be dominated by this block.

[Bug tree-optimization/103721] [12 regression] wrong code generated for loop with conditional since r12-4790-g4b3a325f07acebf4

[cvs-commit at gcc dot gnu.org]

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

--- Comment #15 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Aldy Hernandez <aldyh@gcc.gnu.org>:

https://gcc.gnu.org/g:eb5ee6464809e051e0292471597931a660485658

commit r12-6787-geb5ee6464809e051e0292471597931a660485658
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Thu Jan 20 10:28:26 2022 +0100

    Reset relations when crossing backedges.

    As discussed in PR103721, the problem here is that we are crossing a
    backedge and causing us to use relations from a previous iteration of a
    loop.

    This handles the testcases in both PR103721 and PR104067 which are variants
    of the same thing.

    Tested on x86-64 Linux with the usual regstrap as well as verifying the
    thread count before and after the patch.  The number of threads is
    reduced by a miniscule amount.

    gcc/ChangeLog:

            PR tree-optimization/103721
            * gimple-range-path.cc
            (path_range_query::relations_may_be_invalidated): New.
            (path_range_query::compute_ranges_in_block): Reset relations if
            they may be invalidated.
            (path_range_query::maybe_register_phi_relation): Exit if relations
            may be invalidated on incoming edge.
            (path_range_query::compute_phi_relations): Pass incoming PHI edge
            to maybe_register_phi_relation.
            * gimple-range-path.h (relations_may_be_invalidated): New.
            (maybe_register_phi_relation): Pass edge instead of tree.
            * tree-ssa-threadbackward.cc (back_threader::back_threader):
            Mark DFS edges.
            * value-relation.cc (path_oracle::path_oracle): Call
            mark_dfs_back_edges.
            (path_oracle::register_relation): Add SSA names to m_registered
            bitmap.
            (path_oracle::reset_path): Clear m_registered bitmap.
            * value-relation.h (path_oracle::set_root_oracle): New.

    gcc/testsuite/ChangeLog:

            * gcc.dg/pr103721-2.c: New test.
            * gcc.dg/pr103721.c: New test.

[Bug tree-optimization/103721] [12 regression] wrong code generated for loop with conditional since r12-4790-g4b3a325f07acebf4

[aldyh at gcc dot gnu.org]

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

Aldy Hernandez <aldyh at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
             Status|NEW                         |RESOLVED

--- Comment #16 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
fixed