This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Fold freeze(undef) into a proper constant
ClosedPublic

Authored by aqjune on Jul 30 2020, 7:17 AM.

Details

Summary

This is a simple patch that folds freeze(undef) into a proper constant after inspecting its uses.

Diff Detail

Event Timeline

aqjune created this revision.Jul 30 2020, 7:17 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 30 2020, 7:17 AM
aqjune requested review of this revision.Jul 30 2020, 7:17 AM

Do these show up in practice?

nikic added inline comments.Jul 31 2020, 12:35 AM
llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
1803

So, these changes duplicate some undef folds from InstSimplify (here: https://github.com/llvm/llvm-project/blob/9b04fec0021112d913058e81bf864e4f33c33dcc/llvm/lib/Analysis/InstructionSimplify.cpp#L2004-L2006) into InstCombine.

I think it would be legal to instead make the fold in InstSimplify also work for one-use freeze of undef. Per the rules, the InstSimplify result needs to be used for a replacement, which will also remove the freeze. Of course, this will only really be safe in conjunction with D84792 for consumers that don't perform replacements.

Though maybe, if we consider the long-term direction (undef replaced by freeze poison), having it in InstCombine and dropping the InstSimplify folds may make more sense -- because we could also fold the multi-use case here, if we replace the whole freeze instruction.

Hi, sorry for delay.

Do these show up in practice?

No, the motivation was from example test1_undef of D84818: if A.fr (which is optimized to freeze(undef)) was combined with or/and & used by a conditional branch, opt was still generating a sub-optimal code.
I thought it must appear at least once in real-world code, but my experiments say that it did not fire when compiling SPEC/testsuite with -O3 + LTO, interestingly. :/
However, wouldn't these folds be pretty low-cost? I think this can happen in a larger codebase as well.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
1803

I think it depends on whether it is valid to replace a portion of uses with InstSimplify-ed value.
For example, even freeze has only one use, if and/or has multiple uses, this can still be problematic:

y = and (freeze undef), x
use(y)
use(y)

If (for some reason) the first use(y) is simplified to 0 but not the second use(y), the two uses will see different values, which is not valid.

If InstCombine isn't enough, we can properly fix each optimization to deal with it, IMO (e.g. JumpThreading). This seems to be a safer way to fix, albeit it may need more engineering.

nikic added a comment.Aug 5 2020, 1:20 PM

Just as another possibility, we could simply always fold freeze undef to zeroinitializer in InstCombine (regardless of number of uses). This is not always the optimal fold, but usually a good one. At least at this point, I don't think freeze undef is expected to be common and it's more important to get rid of the freeze than find the best replacement.

nikic added a comment.Aug 5 2020, 2:44 PM

Just as another possibility, we could simply always fold freeze undef to zeroinitializer in InstCombine (regardless of number of uses). This is not always the optimal fold, but usually a good one. At least at this point, I don't think freeze undef is expected to be common and it's more important to get rid of the freeze than find the best replacement.

To expand on this, if we want to handle multi-use freeze undef in the future, there's generally two ways that can work:

  1. Individual folds for certain operators (as done here), but replacing the freeze itself with an advantageous value rather than just the operator.
  2. Walking the uses of the freeze to find the best replacement value and replace all uses. (E.g. by counting for how many uses a certain value is favorable.)

The current patch would be the starting point for 1, my suggestion would be the starting point for 2.

I should say though that I'm also ok with your current patch.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
1803

I don't think the InstSimplify contract allows replacing only some uses. If you replace your example with

y = and undef, x
use(y)
use(y)

and you replace only the first use with 0, then the second one could later get folded to x still, observing two different values of undef. I don't think the freeze makes a difference here.

Of course, not doing it in InstSimplify is still safer :)

aqjune added a comment.Aug 5 2020, 6:24 PM

To expand on this, if we want to handle multi-use freeze undef in the future, there's generally two ways that can work:

  1. Individual folds for certain operators (as done here), but replacing the freeze itself with an advantageous value rather than just the operator.
  2. Walking the uses of the freeze to find the best replacement value and replace all uses. (E.g. by counting for how many uses a certain value is favorable.)

The current patch would be the starting point for 1, my suggestion would be the starting point for 2.

I should say though that I'm also ok with your current patch.

I think the second option really makes sense, I'll update this patch.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
1803

In this case, it is fine because seeing different values of an undef is allowed to the users of users transitively.
Since undef represents a set of any value conceptually, and undef, x is a set of value that is a subset of bits of x, and each use can pick a value which one to see.
This allows, e.g. folding y = add undef, 1; use(y); use(y) into use(undef); use(undef).
Anyway, it is true that the behavior of undef is mysterious and hard to reason about..

aqjune updated this revision to Diff 283487.Aug 5 2020, 10:40 PM

Iterate over uses of freeze(undef) and choose the best value

aqjune retitled this revision from [InstCombine] Fold select/and/or with freeze(undef) that is used in the op only to [InstCombine] Fold freeze(undef) into a proper constant.Aug 6 2020, 12:32 AM
aqjune edited the summary of this revision. (Show Details)
nikic accepted this revision.Aug 6 2020, 12:55 AM

LGTM. There are various ways in which the value choice can be improved, but this looks like a good starting point.

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp
3415 ↗(On Diff #283487)

I would assert(BestValue && "Must have at least one use") here. Dead freeze should be cleaned by the main InstCombine loop already, so there must be at least one use here.

This revision is now accepted and ready to land.Aug 6 2020, 12:55 AM
This revision was landed with ongoing or failed builds.Aug 6 2020, 2:40 AM
This revision was automatically updated to reflect the committed changes.