[COMMITTED] path oracle: Do not look at root oracle for killed defs.

Andrew MacLeod amacleod@redhat.com
Mon Nov 8 17:23:57 GMT 2021


On 11/8/21 3:44 AM, Richard Biener via Gcc-patches wrote:
> On Sat, Nov 6, 2021 at 4:38 PM Aldy Hernandez via Gcc-patches
> <gcc-patches@gcc.gnu.org> wrote:
>> [This is more Andrew's domain, but this is a P1 PR and I'd like to
>> unbreak the SPEC run, since this is a straigthforward fix.  When he
>> returns he can double check my work and give additional suggestions.]
>>
>> The problem here is that we are incorrectly threading 41->20->21 here:
>>
>>    <bb 35> [local count: 56063504182]:
>>    _134 = M.10_120 + 1;
>>    if (_71 <= _134)
>>      goto <bb 19>; [11.00%]
>>    else
>>      goto <bb 41>; [89.00%]
>> ...
>> ...
>> ...
>>    <bb 41> [local count: 49896518755]:
>>
>>    <bb 20> [local count: 56063503181]:
>>    # lb_75 = PHI <_134(41), 1(18)>
>>    _117 = mstep_49 + lb_75;
>>    _118 = _117 + -1;
>>    _119 = mstep_49 + _118;
>>    M.10_120 = MIN_EXPR <_119, _71>;
>>    if (lb_75 > M.10_120)
>>      goto <bb 21>; [11.00%]
>>    else
>>      goto <bb 22>; [89.00%]
>>
>> First, lb_17 == _134 because of the PHI.
>> Second, _134 > M.10_120 because of _134 = M.10_120 + 1.
>>
>> We then assume that lb_75 > M.10_120, but this is incorrect because
>> M.10_120 was killed along the path.
> Huh, since SSA has only a single definition it cannot be "killed".
> What can happen is that if you look across backedges that the same
> reg can have two different values.  Basically when you look across
> backedges you have to discard all knowledge you derived from
> stuff that's dominated by the backedge destination.
>
Yeah, its just terminology... the path oracle follows a linear set of 
edges, so when we see the DEF of an ssa-name, any existing relations 
that have been seen have, by definition, come from a back edge at some 
point.  If the root oracle has that relation, as in this case, it came 
from a back edge.

"Killing" is referring to killing any relations in the path up to this 
point when we see the definition of the SSA_NAME. This includes anything 
in, or preceding, the path to this point.. We were removing any 
relations found in the path, but  were missing the "preceding" part.

Andrew




More information about the Gcc-patches mailing list