Page MenuHomePhabricator

[GVN] If zext X == N or sext X == N, then X == trunc N.
Needs ReviewPublic

Authored by wecing on Dec 28 2020, 11:26 PM.

Details

Summary

As discussed in https://reviews.llvm.org/D93850, this seems to be a bug
of GVN.

Diff Detail

Event Timeline

wecing created this revision.Dec 28 2020, 11:26 PM
wecing requested review of this revision.Dec 28 2020, 11:26 PM
Herald added a project: Restricted Project. · View Herald TranscriptDec 28 2020, 11:26 PM

I am very confused why NewGVN doesn't seem to propagate switch condition values: https://godbolt.org/z/9a9P51. Some guidance on porting this to NewGVN would be appreciated!

spatel added a subscriber: spatel.Dec 29 2020, 6:03 AM
nikic added a reviewer: nikic.Dec 29 2020, 9:49 AM
nikic added a subscriber: nikic.

I'm not convinced that GVN is really the right place to address this, because it is not the only place that would have to understand this pattern. For example LVI does the inverse reasoning (X == C to zext X == zext C), but not this one. For NewGVN and IPSCCP PredicateInfo would have to handle it, and I'm pretty sure we want to avoid that.

The InstCombine patch that moves the zext into the switch seems like the more promising direction to me. Generally, if we have switch (f(x)) case C it makes sense to convert it to switch (x) case f^{-1}(C) for invertible f.

wecing added a comment.Jan 6 2021, 4:30 PM

For NewGVN and IPSCCP PredicateInfo would have to handle it, and I'm pretty sure we want to avoid that.

@nikic Would you mind explaining why? If there is a good reason we cannot do this in NewGVN then D93850 might be the best we could do.

For NewGVN and IPSCCP PredicateInfo would have to handle it, and I'm pretty sure we want to avoid that.

@nikic Would you mind explaining why? If there is a good reason we cannot do this in NewGVN then D93850 might be the best we could do.

I'm not yet convinced we can do this in instcombine,
because why can we do this without a profitability check,
like the fold just below that one does?

nikic added a comment.Jan 7 2021, 9:59 AM

@nikic Would you mind explaining why? If there is a good reason we cannot do this in NewGVN then D93850 might be the best we could do.

Handling it in NewGVN and IPSCCP requires handling it in PredicateInfo, by introducing new SSA variables and performing SSA renaming in relevant branches not just for comparison operands, but also for operands-of-operands. That is, for br icmp (zext X), C we currently introduce up to two new variables for (zext X) and rename to them in the relevant branch. Handling the pattern here would require introducing a new variable for X as well. Of course it's possible to do this, but, but it leads to a collection of special cases rather than a principled approach. Especially as we have to deal with this in multiple passes, it's better to avoid it if we can.

I'm not yet convinced we can do this in instcombine,
because why can we do this without a profitability check,
like the fold just below that one does?

The profitability check is there to avoid creating illegal types that did not exist in the original IR. If we are simply dropping a zext, we're using a type that already existed in the IR, and would generally consider that to be fine. We could be even more conservative and require the zext-ed from type to be legal (doesn't make much diff in practice). Dropping a zext i32 to i64 to switch over an i32 is quite different from inserting a trunc to i3 and switching over i3. The former seems like an unambiguous improvement, while the latter will regress more likely than not.

wecing added a comment.Feb 5 2021, 3:18 PM

@lebedev.ri do you think we could go with D93850?