Page MenuHomePhabricator

[InstCombine] Allow InstCombine to merge adjacent guards
ClosedPublic

Authored by mkazantsev on Feb 1 2017, 12:20 AM.

Details

Summary

If there are two adjacent guards with different conditions, we can
remove one of them and include its condition into the condition of
another one. This patch allows InstCombine to merge them by the
following pattern:

guard(a); guard(b) -> guard(a & b).

Diff Detail

Repository
rL LLVM

Event Timeline

mkazantsev updated this revision to Diff 86584.Feb 1 2017, 12:23 AM
sanjoy requested changes to this revision.Feb 1 2017, 12:47 AM
sanjoy added inline comments.
lib/Transforms/InstCombine/InstCombineCalls.cpp
3269 ↗(On Diff #86584)

There's a subtle problem here -- we can transform

guard(a) [ "deopt"(X) ]
guard(b) [ "deopt"(Y) ]

to

;; Widen the first guard
guard(a & b) [ "deopt"(X) ]

but not to

;; Widen the second guard
guard(a & b) [ "deopt"(Y) ]

since the deopt state of the second guard (represented as "Y" here
for simplicity) may have been optimized under the assumption that a
is true.

For instance, say we started with

guard(a) [ "deopt"(a) ]
guard(b) [ "deopt"(a) ]

which first got optimized to

guard(a) [ "deopt"(a) ]
guard(b) [ "deopt"(true) ]

and then due to this change is optimized to

;; guard(a) [ "deopt"(a) ]
guard(a && b) [ "deopt"(true) ]

Now if a is false at runtime then the expected behavior was to
deoptimize with the deopt state (a) == (false), but in the
optimized program we will deoptimize with the deopt state (true).

The right transform here is to widen the first guard, not the second
one.

3273 ↗(On Diff #86584)

I'd not bother with the !a && !b => !(a && b). I think it is better to leave it as !a && !b (i.e. not special case m_Not at all), and have InstCombine re-canonicalize it (in a later iteration) to !(a || b) if that's more canonical.

This revision now requires changes to proceed.Feb 1 2017, 12:47 AM
mkazantsev updated this revision to Diff 86602.Feb 1 2017, 2:54 AM
mkazantsev edited edge metadata.
mkazantsev marked 2 inline comments as done.
mkazantsev edited the summary of this revision. (Show Details)

Fixed

sanjoy accepted this revision.Feb 1 2017, 8:06 AM

lgtm! Checking in on your behalf.

This revision is now accepted and ready to land.Feb 1 2017, 8:06 AM
mkazantsev added inline comments.Feb 1 2017, 8:09 AM
lib/Transforms/InstCombine/InstCombineCalls.cpp
3269 ↗(On Diff #86584)

Thanks for pointing that out: wasn't obvious indeed.

3273 ↗(On Diff #86584)

Yeah, it is actually done by DeMorgan's Law transformation. :)

This revision was automatically updated to reflect the committed changes.