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

["amacleod at redhat dot com" <gcc-bugzilla@gcc.gnu.org>]

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.