This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] if the condition of a select is known, eliminate the select
ClosedPublic

Authored by spatel on Jan 4 2017, 5:21 PM.

Details

Summary

This is a limited solution for PR31512:
https://llvm.org/bugs/show_bug.cgi?id=31512

The motivation is that we will need to increase usage of llvm.assume and/or metadata to solve PR28430:
https://llvm.org/bugs/show_bug.cgi?id=28430

...and this kind of simplification is needed to take advantage of that extra information.

Diff Detail

Event Timeline

spatel updated this revision to Diff 83169.Jan 4 2017, 5:21 PM
spatel retitled this revision from to [InstSimplify] if the condition of a select is known, eliminate the select.
spatel updated this object.
spatel added reviewers: efriedma, hfinkel, majnemer.
spatel added a subscriber: llvm-commits.
efriedma edited edge metadata.Jan 9 2017, 12:27 PM

This seems like a dangerous direction, in the sense that it could make instsimplify very expensive... I mean, if we didn't care about compile-time cost, we could call computeKnownBits on all the operands for every call into instsimplify, and hope something simplifies. Could we put this sort of transform somewhere it isn't called so frequently?

lib/Analysis/InstructionSimplify.cpp
3712 ↗(On Diff #83169)

There's probably a more straightforward way to check whether the condition is a vector type.

majnemer edited edge metadata.Jan 9 2017, 12:31 PM

This seems like a dangerous direction, in the sense that it could make instsimplify very expensive... I mean, if we didn't care about compile-time cost, we could call computeKnownBits on all the operands for every call into instsimplify, and hope something simplifies. Could we put this sort of transform somewhere it isn't called so frequently?

I agree, I'm not sure this is the right place for this.

spatel added a comment.Jan 9 2017, 1:38 PM

This seems like a dangerous direction, in the sense that it could make instsimplify very expensive... I mean, if we didn't care about compile-time cost, we could call computeKnownBits on all the operands for every call into instsimplify, and hope something simplifies. Could we put this sort of transform somewhere it isn't called so frequently?

I agree, I'm not sure this is the right place for this.

Ok, thanks for the guidance. I see a couple of ways to limit the cost and still get the motivating case that has an 'llvm.assume':

  1. Guard this call to computeKnownBits with a check of the select condition's users (make sure there's an assume in the list).
  2. Trigger the fold from an earlier instruction via isKnownNonNullAt(). I think this would involve adding an llvm.assume check that's similar to the change in D20044. This probably also needs the extra isKnownNonNullAt() call from D28204.

Any others? Is one of the above preferable to the other?
Any

spatel added a comment.Jan 9 2017, 3:41 PM

I hope I'm not burning everyone out with 'assume' questions, but I should mention that the test in D28485 works because we have a naked call to computeKnownBits() in InstCombiner::visitReturn(). I'm guessing that there are usually less 'ret' insts than 'select' insts, but should that fold be guarded in the same way as we decide here?

// There might be assume intrinsics dominating this return that completely
// determine the value. If so, constant fold it.

Another option is to handle this in EarlyCSE; we already do a very similar optimization there for branches.

Another option is to do this in instcombine.

spatel retitled this revision from [InstSimplify] if the condition of a select is known, eliminate the select to [InstCombine] if the condition of a select is known, eliminate the select.Jan 9 2017, 5:38 PM
spatel updated this object.
spatel edited edge metadata.
spatel updated this revision to Diff 83757.Jan 9 2017, 5:41 PM

Patch updated to limit compile-time cost:

  1. Move the fold to InstCombine
  2. Guard the fold with a check of the assumption cache

Note that this patch now depends on D28485 to work correctly.

efriedma accepted this revision.Jan 11 2017, 11:48 AM
efriedma edited edge metadata.

I think we need a more comprehensive approach to analyzing value ranges/known bits/etc., but this is fine for now, I think.

This revision is now accepted and ready to land.Jan 11 2017, 11:48 AM

I think we need a more comprehensive approach to analyzing value ranges/known bits/etc., but this is fine for now, I think.

Thanks! And agreed - if there's consensus about how to fix this (nonnull and llvm.assume are my motivations in this series of patches), I'll try to improve it.

This revision was automatically updated to reflect the committed changes.

I made the 2nd test a FIXME (removing the dependency on D28485) and committed this at r291915 so we could see if there is any compile-time impact from this on the bots or other testers.