This is an archive of the discontinued LLVM Phabricator instance.

[GuardWidening] Widen guards with conditions of frequently taken dominated branches
ClosedPublic

Authored by mkazantsev on Jul 30 2018, 12:37 AM.

Details

Summary

If there is a frequently taken branch dominated by a guard, and its condition is available
at the point of the guard, we can widen guard with condition of this branch and convert
the branch into unconditional:

guard(cond1)
if (cond2) {
  // taken in 99.9% cases
  // do something
} else {
  // do something else    
}

Converts to

guard(cond1 && cond2)
// do something

Diff Detail

Event Timeline

mkazantsev created this revision.Jul 30 2018, 12:37 AM

Fixed indents.

fedor.sergeev added inline comments.Jul 30 2018, 1:32 AM
lib/Transforms/Scalar/GuardWidening.cpp
291

What about adding some STATISTICS here?
Would be useful for experiments with this new mode...

mkazantsev added inline comments.Jul 30 2018, 9:06 PM
lib/Transforms/Scalar/GuardWidening.cpp
291

Will do.

reames requested changes to this revision.Aug 1 2018, 3:16 PM
reames added inline comments.
lib/Transforms/Scalar/GuardWidening.cpp
71

This definitely needs to default to false initially. :)

78

Er, how is a frequency 1000? I would expect a percentage here. Are you using N-to-1 or (N-1)/N instead? If so, the comment on the flag needs updated.

274

Separate whitespace change please.

384

Just use conditional early return followed by unchecked cast<BranchInst>

393

Same as above.

408

Better to move this check into the caller.

test/Transforms/GuardWidening/widen-frequent-branches.ll
11

Please add at least some tests for CFGs other than diamonds. Triangles and simple early returns are also good.

This revision now requires changes to proceed.Aug 1 2018, 3:16 PM
mkazantsev added inline comments.Aug 1 2018, 10:07 PM
lib/Transforms/Scalar/GuardWidening.cpp
71

Agreed. :)

78

I'm using (N-1)/N. Will update the comment to make it clear.

408

No, it is here because we should not remove br instructions. We don't want the caller to know about possible types of guards.

reames added inline comments.Aug 2 2018, 3:47 PM
lib/Transforms/Scalar/GuardWidening.cpp
408

I was suggesting that we only call this function for guards, not for branches. Calling a function called "eliminateGuard" on a branch seems a bit odd.

mkazantsev added inline comments.Aug 2 2018, 10:39 PM
lib/Transforms/Scalar/GuardWidening.cpp
408

Here (and in other places like "getGuardCondition") we assume that the word "guard" has a wider definition than llvm.experimental.guard intrinsic. A branch can be a guard as well in some circumstances.

fedor.sergeev added inline comments.Aug 2 2018, 11:16 PM
lib/Transforms/Scalar/GuardWidening.cpp
408

Technically this is widening of a guard with a branch/guard condition.
And in this patch we are not treating dominated condition exactly as a guard.
And elimination happens for branches and guards differently.
So I definitely see a merit in what Philip suggests.

Alternatively you might call it eliminateBranchConditionOrGuard ;)

mkazantsev marked 5 inline comments as done.
mkazantsev planned changes to this revision.Aug 3 2018, 2:56 AM

Yeah, I see now why this naming confused you... I will try to find the better naming for that.

mkazantsev updated this revision to Diff 158973.Aug 3 2018, 4:19 AM
mkazantsev marked 2 inline comments as done.
reames accepted this revision.Aug 3 2018, 9:55 AM

LGTM

lib/Transforms/Scalar/GuardWidening.cpp
305

Add assert that the branch condition is a constant.

This revision is now accepted and ready to land.Aug 3 2018, 9:55 AM
This revision was automatically updated to reflect the committed changes.