On Wed, Jan 19, 2022 at 2:37 AM Andrew MacLeod via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> This patch happens to fix the PR, but I believe it only papers over a
> deeper issue that is uncovered in PR104067.
>
> That said, examination of the issue uncovered an oversight in the way
> equivalence sets are merged by the equivalence oracle. I have not seen
> an instance via the ranger, but I suspect its just a matter of time.
>
> Equivalences sets are added to the basic block in which they occur. By
> default, the definition of an SSA_NAME create an equivalence in the DEF
> block containing just the name itself. Other equivalences are added as
> they are encountered in their respective basic blocks, and are created
> by combining whatever equivalence is active (via query) in that block
> with the new equivalence. An equivalence introduced by an edge is
> currently only added the edge destination is a block with a single
> predecessor. It is then added to that block.
>
> When a query is made for the equivalence set for b_2 at BBx, a walk up
> the dominance tree is made looking for the first block which has an
> equivalence containing b_2. This then becomes the equivalence set for
> B2 at BBx.
>
> If this set contains f_8, before we know that f_8 and b_2 actually
> equivalent, we query the equivalence set of f_8 at BBx. If it comes back
> with the same set, then the 2 names are equivalent. if the set is
> different, then they are not.
>
> This allows us to register equivalences as we see them without worrying
> about invalidating other equivalences. Rather, we defer validation
> until we actually care, and pay the cost at the query point.
>
> This PR has exposed a flaw in how we register equivalence sets around
> back edges which could potentially show up somewhere.
>
> searchvolume_5 was use in previous blocks along the back edge and has an
> equivalence set of {_5, world_7} in 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)>
>
> When an equivalence is added for currentVolume_6, a query is made for
> the equivalence set for currentVolume_8, which returns the set {_5, _8,
> world_7 }. Currently, this is simply combined with {_6} via a bitwise
> OR to produce {_5, _6, _8, world_7 }. This is incorrect as _5's
> equivalence set is now {_5, _11}.
>
> _6 and _8 dont appear to be directly related to _5, so we were missing
> it. What should be happening is when we merge the equivalence set for
> currentVolume_6 and currentVolume_8, each member of the set should be
> verified by the same criteria the query uses... ie, ask for the equiv
> set for _5, _8, and world_7 at BB9, and if it is different than this
> set, it isn't added.
>
> This would then create the correct equivalence set { _6, _8, world_7 },
> as the query for _5 would come back with {_5, _11} and not evaluate as
> equivalent.
>
> And yes, PHIS all happen in parallel... We don't need to worry about
> ordering because even if the PHI hadn't been processed in this order,
> the definition would have provided a default of { _5 }, and thus still
> not been equivalent and still won't be added to the set.
>
> Anyway, even tho I think there is an additional problem in this PR, I
> wanted to get approval and check this code in under this PR since it
> does need to be fixed, and was uncovered here. We wont close the PR
> until we are sure the underlying issue is resolved.
>
> I will also see if I can come up with some kind of test case in the
> meantime as well.
>
> Bootstraps on x86_64-pc-linux-gnu with no regressions. Overall compile
> time is very nominal.. less than a 0.1% impact on the EVRP/VRP passes,
> so the cost is miniscule.
>
> OK for trunk?
OK. I don't quite understand how what you describe above works, it sounds
a bit odd with respect to the idea that equivalences should be transitive but
I should note that forming equivalences from PHI nodes with backedges
is not possible without being very careful since you will easily end up
equating _1 and _1 from different iterations (and thus with different value).
Thanks,
Richard.
>
> Andrew
