This is an archive of the discontinued LLVM Phabricator instance.

[BPI] Detect branches in loops that make themselves not taken
ClosedPublic

Authored by john.brawn on Jul 24 2017, 9:23 AM.

Details

Summary

If we have a loop like this:

int n = 0;
while (...) {
 if (++n >= MAX) {
   n = 0;
 }
}

then the body of the 'if' statement will only be executed once every MAX iterations. Detect this by looking for branches in loops where taking the branch makes the branch condition evaluate to 'not taken' in the next iteration of the loop, and reduce the probability of such branches.

This slightly improves EEMBC benchmarks on cortex-m4/cortex-m33 due to making better choices in if-conversion, but has no effect on any other cpu/benchmark that I could detect.

Diff Detail

Repository
rL LLVM

Event Timeline

john.brawn created this revision.Jul 24 2017, 9:23 AM
davidxl edited edge metadata.Jul 24 2017, 9:34 AM

Why not putting this change into BranchProbablityInfo.cpp, so that other components can benefit from the more precise BP info?

Why not putting this change into BranchProbablityInfo.cpp, so that other components can benefit from the more precise BP info?

I'm not sure what you mean here, this change is in BranchProbabilityInfo.cpp?

Sorry about the noise -- I was juggling around several different issues :)

davidxl added inline comments.Jul 25 2017, 11:12 AM
lib/Analysis/BranchProbabilityInfo.cpp
577

Can you extract the new logic into a separate function : computeUnlikelySuccs Or some other name?

594

If the logic is extracted to a helper function, do a early return here to make it clearer.

597

Early return if condition is not met.

607

limit the walk within the enclosing loop?

614

early return if there is no phi found?

632

continue if not const

637

move this down. The first one should always be non-null.

651

It is probably not too interesting to handle the opposite scenario -- the successor sets some value which makes the branch to it more likely .

test/Analysis/BranchProbabilityInfo/loop.ll
401

no need to check unconditional branch.

Updated patch according to review comments.

john.brawn added inline comments.Jul 26 2017, 9:15 AM
test/Analysis/BranchProbabilityInfo/loop.ll
401

The other tests in this file check the probabilities of all of the branches, not just the unconditional ones, so I'd rather do the same here for the sake of consistency.

This code looks fine to me. My next question is, is the pattern common? The amount of code and possible compile increase added is non trivial.

This code looks fine to me. My next question is, is the pattern common? The amount of code and possible compile increase added is non trivial.

I've finally gotten around to gathering some data on this. Over the entire LLVM test suite (which may or may not be a useful data set, I don't know), for each call to computeUnlikelySuccessors:

  • 56% execute the first loop (i.e. the block does a conditional branch based on a compare with a constant)
  • 19% execute the second loop (i.e. we found a suitable phi node)
  • 0.11% insert at least one element into UnlikelyBlocks

I measured the increase to the overall buildtime of the LLVM test suite as 2%.

This code looks fine to me. My next question is, is the pattern common? The amount of code and possible compile increase added is non trivial.

I've finally gotten around to gathering some data on this. Over the entire LLVM test suite (which may or may not be a useful data set, I don't know), for each call to computeUnlikelySuccessors:

  • 56% execute the first loop (i.e. the block does a conditional branch based on a compare with a constant)
  • 19% execute the second loop (i.e. we found a suitable phi node)
  • 0.11% insert at least one element into UnlikelyBlocks

I measured the increase to the overall buildtime of the LLVM test suite as 2%.

How confident are you in this increase? Is this noise? An actual 2% increase in compile time seems expensive for what this is doing.

How confident are you in this increase? Is this noise? An actual 2% increase in compile time seems expensive for what this is doing.

Not very. I've finally gotten around to getting more measurements, and the result from building the LLVM test suite 10 times (average combined build time of all objects on my machine, 95% confidence intervals) is: before 741s +/- 6s, after 746s +/- 9s. So I would guess this means there's no overall difference, given that each amount lies within the confidence interval of the other plus looking at the individual objects there's none where the confidence intervals don't overlap, but I have little experience in interpreting these kinds of statistics.

john.brawn updated this revision to Diff 128943.Jan 8 2018, 8:53 AM

Rebase and ping.

junbuml added a subscriber: junbuml.Jan 8 2018, 9:45 AM

The branch probability depends on other factors which is not considered here.

For instance

  1. the value of MAX. In the example, if MAX is 1, then the branch probablity should be 50%
  2. the step /increment of n

More generally, the predicted probability should depend on MAX/step. The larger the value, the less likely the branch is taken.

lib/Analysis/BranchProbabilityInfo.cpp
463

Add some documentation on the function documenting the parameters.

Add a comment to computeUnlikelySuccessors.

The branch probability depends on other factors which is not considered here.

For instance

  1. the value of MAX. In the example, if MAX is 1, then the branch probablity should be 50%
  2. the step /increment of n

More generally, the predicted probability should depend on MAX/step. The larger the value, the less likely the branch is taken.

That's true, but making the probability more precise would make the analysis here more complicated and I don't think it's worth it. 50% is a safe lower bound: we know the branch will be not taken at least 50% of the time and never less than that, assuming a large enough number of iterations (for small numbers of iterations whether the iteration count is even/odd will have an effect, e.g. for 1 iteration the branch may be always taken, but when the loop has a small number of iterations it won't be hot so it doesn't matter what we think the probability is).

Add a FIXME comment for possible improvement to unlikelyhood measure.

davidxl accepted this revision.Feb 23 2018, 9:07 AM

LGTM

This revision is now accepted and ready to land.Feb 23 2018, 9:07 AM
This revision was automatically updated to reflect the committed changes.