Page MenuHomePhabricator

Broaden the definition of a "widenable branch"
ClosedPublic

Authored by reames on Wed, Nov 20, 12:08 PM.

Details

Summary

As a reminder, a "widenable branch" is the pattern "br i1 (and i1 X, WC()), label %taken, label %untaken" where "WC" is the widenable condition intrinsics. The semantics of such a branch (derived from the semantics of WC) is that a new condition can be added into the condition arbitrarily without violating legality.

Broaden the definition in two ways:

  1. Allow swapped operands to the br (and X, WC()) form
  2. Allow widenable branch w/trivial condition (i.e. true) which takes form of br i1 WC()

The former is just general robustness. The later is specifically important as partial unswitching of a widenable range check produces exactly this form above the loop.

Diff Detail

Event Timeline

reames created this revision.Wed, Nov 20, 12:08 PM
Herald added a project: Restricted Project. · View Herald TranscriptWed, Nov 20, 12:08 PM
ebrevnov added inline comments.Thu, Nov 21, 1:45 AM
llvm/lib/Analysis/GuardUtils.cpp
47–59

Looks not finished...

llvm/lib/Transforms/Utils/GuardUtils.cpp
89–107

Would it be better to use parseWidenableBranch instead of repeating its logic here.

114–128

Same as above.

reames marked 2 inline comments as done.Thu, Nov 21, 9:48 AM
reames added inline comments.
llvm/lib/Analysis/GuardUtils.cpp
47–59

Why? It's the trivial case of a widenable branch?

I can simply remove the comment if it's unhelpful?

llvm/lib/Transforms/Utils/GuardUtils.cpp
89–107

Can't. I wish we could and tried to find a way, but we need to modify the existing instructions to preserve the "one use" requirement on the widenable condition to be able to determine it's a trivially widenable branch.

apilipenko accepted this revision.Thu, Nov 21, 10:20 AM
apilipenko added inline comments.
llvm/lib/Transforms/Utils/GuardUtils.cpp
89–107

Yeah, a naive approach here would be to replace wc with (newc && wc). It handles both trivial and non-trivial widenable branches. The only problem is it makes a pattern which is not recognized by parseWidenableBranch.

br (c && wc), ... - widenable branch
=>
br (c && (newc && wc)), ... - not (obviously) widenable anymore

Can you add a comment that we do it this way because we need to preserve the structure (c && wc) which is recognized by parseWidenableBranch?

This revision is now accepted and ready to land.Thu, Nov 21, 10:20 AM
This revision was automatically updated to reflect the committed changes.
reames marked an inline comment as done.Thu, Nov 21, 3:46 PM
reames added inline comments.
llvm/lib/Transforms/Utils/GuardUtils.cpp
89–107

Just to close loop, Artur and I latter released we could rephrase parseWidenableBranch in terms of Uses and simplify a lot of this code. I landed the rewrite as rG8293f7434577

ebrevnov added inline comments.Thu, Nov 21, 8:11 PM
llvm/lib/Transforms/Utils/GuardUtils.cpp
89–107

Cool. That's what I assumed by asking to reuse parseWidenableBranch :-)