[BPI] Reduce the probability of unreachable edge to minimal value greater than 0

[skatkov]

Summary

The probability of edge coming to unreachable block should be as low as possible.
The change reduces the probability to minimal value greater than zero.

The bug https://bugs.llvm.org/show_bug.cgi?id=32214 show the example when
the probability of edge coming to unreachable block is greater than for edge
coming to out of the loop and it causes incorrect loop rotation.

Please note that with this change the behavior of unreachable heuristic is a bit different
than others. Specifically, before this change the sum of probabilities
coming to unreachable blocks have the same weight for all branches
(it was just split over all edges of this block coming to unreachable blocks).
With this change it might be slightly different but not to much due to probability of
taken branch to unreachable block is really small.

[chandlerc]

We intentionally didn't use zero because that seems more of a degenerate test case. What problem are you actually trying to solve here?

[skatkov]

Hi Chandler,

Let's consider the following example: you have a loop with say throwing instruction (or @llvm.experimental.deoptimize) inside which is representable by unreachable basic block.
If we use any value greater than zero as probability of the branch coming to unreachable block it is possible that profiling will detect that normal exit from the loop has lower probability than unreachable block and this is incorrect.
So now we say that unreachable edge probability is (1, 2^20). If loop is executed > 2^20 iterations than edge coming to "normal" out of the loop basic block will have a probability (1, >2^20) and LLVM will consider unreachable edge be hotter than mormal exit.

This is unexpected behavior. And it is evident if we choose any constant greater than 0 we are able to find a loop iteration count breaking the expected behavior.
In reality as I understand, we expect that unreachable is actually never executed and this corresponds to 0 probability for corresponding edge.

Hope that it helps. If you'd like I could add this example to the summary section. I tried to put more general words in summary section.

[skatkov]

Please take a look, any comments are appreciated.

Please also note that I still think that zero probability for edge coming to unreachable edge still makes sense to me because unreachable edge is something we do not expect or do not want to point our attention to. If there are some pros to avoid zero probability, please let me know for my knowledge.

[chandlerc]

This at least seems like a very reasonable patch to me. I'd like to double check with David and Duncan as well (I've added them as reviewers). My only lingering concern would be if this will run the risk of underflow coming up more often, but that is probably not too much of an issue now that BFI does a better job of things.

Regarding using 'zero' as a viable probability: I'm mostly worried what other assumptions have crept into the codebase as a consequence of these being non-zero. But this is definitely something we can overcome if zero is a substantially better way to model this. The things I think would be needed:

1. Some thorough testing of using zero in this way, both with and without an additional profile.
2. Start a brief llvm-dev thread just to make sure others who may not be watching the reviews are paying attention.
3. In #2, somewhat clearly spell out the reason why the approach in this patch is significantly improved by using 'zero'.

None of this is insurmountable, but it is somewhat expensive, so I only wanted us to go down this path if necessary.

[davidxl]

It is known that BFI can not handle zero weight and it will add 1 to zero weight when it sees it.

Here the unreachable Branch prob is not zero (without the change). Where does it get changed to zero?

[chandlerc]

In D30633#756192, @davidxl wrote:

It is known that BFI can not handle zero weight and it will add 1 to zero weight when it sees it.

Here the unreachable Branch prob is not zero (without the change). Where does it get changed to zero?

This patch doesn't.

In my response I suggested that *if* the author wants to go beyond the current patch (which keeps unreachable at >0) they should discuss it more broadly. I don't think you need to worry about that today, they'll send email if they want to go there.

I added you to this patch to make sure the technique of dropping to 1 and maxing out the other side makes sense (now that we factor in when metadata has more precise information).

[davidxl]

That is not my question :)

My question is that without the patch, the probability of UR branch is actually lower (1, 0x8000....). Looks like it gets truncated somewhere? In other words, the fix can be put to where the truncation happens.

[chandlerc]

In D30633#756248, @davidxl wrote:

That is not my question :)

My question is that without the patch, the probability of UR branch is actually lower (1, 0x8000....). Looks like it gets truncated somewhere? In other words, the fix can be put to where the truncation happens.

I think I must be missing something ... Where is the probability of the UR branch lower before this patch? At least, the test cases updated, the probability of the UR branch is *higher* before this patch.

From the comments in the review thread, the goal here is to avoid the case where the UR branch probability ends up *higher* than the loop exit branch probability.

[skatkov]

Chandler is right in all comments :)

1. The main motivation of the patch is to avoid "the case where the UR branch probability ends up *higher* than the loop exit branch probability". In this terms I'm completely ok with this patch and there is not need to go with zero. The question about zero from my side was mostly about understanding why zero is not good.
2. Th UR branch probability without patch is equal to 1/(2^20) while with this change it will be 1/(2^31), so with the patch it becomes lower.

[skatkov]

However I need to check what happens if metadata provides a weight greater than 2^31. Will do it tomorrow.

[dexonsmith]

The testcase updates look good to me, and demonstrate the patch is doing what's intended. It might be worth adding a couple of tests for multiple branch targets (switch statements), since I'm not convinced everything adds up to 1 right now.

As an aside, it seems the logic around unreachable (with and without the patch) might pessimize code paths that lead to noreturn functions, such as posix_spawn(). Is that really what we want? Why?

lib/Analysis/BranchProbabilityInfo.cpp

165–171

This doesn't look to me like it will add up to BranchProbability::getOne() in the end. Is that a problem?

[chandlerc]

In D30633#756320, @dexonsmith wrote:

As an aside, it seems the logic around unreachable (with and without the patch) might pessimize code paths that lead to noreturn functions, such as posix_spawn(). Is that really what we want? Why?

Heh, I thought about bringing this up, but it really seems orthogonal and something I wanted to look at.

Yeah, generally, the unreachable logic I wrote eons ago was dead wrong and this is still wrong in the case of nice "run forever" functions. I'll either send a patch or file a bug about this.

[dexonsmith]

In D30633#756347, @chandlerc wrote:

In D30633#756320, @dexonsmith wrote:

As an aside, it seems the logic around unreachable (with and without the patch) might pessimize code paths that lead to noreturn functions, such as posix_spawn(). Is that really what we want? Why?

Heh, I thought about bringing this up, but it really seems orthogonal and something I wanted to look at.

Yeah, generally, the unreachable logic I wrote eons ago was dead wrong and this is still wrong in the case of nice "run forever" functions. I'll either send a patch or file a bug about this.

I agree, no reason to hold the patch up.

[skatkov]

In D30633#756320, @dexonsmith wrote:

The testcase updates look good to me, and demonstrate the patch is doing what's intended. It might be worth adding a couple of tests for multiple branch targets (switch statements), since I'm not convinced everything adds up to 1 right now.

The test @test2 represents the case with switch or you are talking about case when sum of probabilities is not equal to 1?

lib/Analysis/BranchProbabilityInfo.cpp

165–171

The sum of probabilities might be different than 1 and this consistent with all other heuristics in this file.
It seems that it was not considered as problem before.

If you think it should be fixed I can come up with a follow-up patch fixing all cases. The question is actually where to add the remainder.

[davidxl]

lib/Analysis/BranchProbabilityInfo.cpp

231–232

Not sure if we want to add a case to cover the meta data is smaller and is kept.

The only possible way is to use 0 weight, which actually may end up creating a a larger BP (after BFI bumping it up). So we should probably add a comment here and unconditionally update the Unreachable branch (i.e. ignoring 0 weight metadata).

[skatkov]

lib/Analysis/BranchProbabilityInfo.cpp

231–232

I prefer to keep it as is due to current logic is correct semantically independent on what UR_TAKEN_PROB is. If someone in the future increases the UR_TAKEN_PROB the code will work correctly anyway.

[skatkov]

Hello guys,

you are saying that BFI bumps the zero probability but I still see in MachineBlockPlacement pass that it actively uses branch probabilities and it seems that they are original ones. At least I see the zero probability if I set it in metadata.

Could you please point me to the place where it is bumped?

Thank you,
Serguei.

[skatkov]

David, thank you very much for pointing me to place where the weight is bumped in BFI. Yes, it is really bumped for branch frequency computation but branch probability is not updated that is why weight 0 helps me for block placement but 1 is not (1 - helps to reduce the probability but does not help in common case).

Let me just explain one more time where the problem is.
Consider the test basing on https://bugs.llvm.org/show_bug.cgi?id=32214.
We have a loop
LoopHeader -> (UnreachableExit, Middleblock)
Middleblock -> (ColdPath, Backedge)
ColdPath ->Backedge
Backedge -> (NormalExit, LoopHeader)

MiddleBlock and ColdPath are only needed for triggering loop rotation.
The probability of the edge LoopHeader -> UnreachableExit is set to 1/2^20 without this patch and 1/2^31 within this patch.
Let's probability of edge Backedge -> NormalExit is obtained by real profile date and equal to 1/2^31.

MachineBlockPlacement pass tries to do a loop rotation. It will build a loop chain: LoopHeader->MiddleBlock->BackEdge->ColdPath.
To do a loop rotation it needs to find the best exit. It does it using the following (it reality it is a bit more complex but for explanation it is enough):
BlockFrequency ExitEdgeFreq = MBFI->getBlockFreq(MBB) * SuccProb;
There are two exits:
LoopHeader -> UnreachableExit
Backedge -> NormalExit

The frequency of LoopHeader is greater than frequency of Backedge due to mass comes out to UnreachableBlock (even f it's probability is zero due to bump of the weight in BFI).
So without this patch SuccProb for UnreachableExit is equal to 1/2^20 and chances the ExitEdgeFreq will be greater for UnreachableExit than for NormalExit more.
Within this patch the worst case is when probability of edge Backedge -> NormalExit is the lowest one (1/2^31).
In this case SuccProb will be the same for both exits. But taking into account that frequency of LoopHeader is greater than for Backedge the ExitEdgeFreq will be greater for UnreachableExit anyway.
However when SuccProb for UnreachableExit is equal to zero the NormalExit becomes the best exit.
That is why for corner case the zero unreachable probability helps to fix the loop rotation issue.

So, this patch makes sense anyway is due to it reduces the number of cases where loop rotation works incorrectly while for the corner cases Zero probability is required.

Any opinions? May be I missed anything?

[skatkov]

BTW, one of the possible another solution might be to change MachineBlockPlacement pass to use frequency of exit block:
change
BlockFrequency ExitEdgeFreq = MBFI->getBlockFreq(MBB) * SuccProb;
to
BlockFrequency ExitEdgeFreq = MBFI->getBlockFreq(Succ);
In this case the hottest exit will be chosen basing on frequency of exit block...

[skatkov]

Actually I tend to think that we do not need zero probability. Instead I will update loop rotation to prohibit the case when rotation breaks the hot path. In this case for corner case we just will not take the best case but still will not do worse.

[skatkov]

Hello Guys,

To make a progress with landing this patch I need a feedback from you. As I see:

1. Chandler had no issues with this patch
2. David in his e-mail wrote that he is ok with this patch
3. Duncan made a proposal to dd some tests with switch.

There are several tests currently with switch statement with unreachable involved:
basic.ll:@test_unreachable_with_switch_prof1
basic.ll:@test_unreachable_with_switch_prof2
basic.ll:@test_unreachable_with_switch_prof3
basic.ll:@test_unreachable_with_switch_prof4
noreturn.ll:@test2
some of them shows that sum of probabilities are not equal to one:
basic.ll:@test_unreachable_with_switch_prof4

Do you want to see some specific tests to be added?

Is there any thing else what prevent you from accepting this change? Please let me know and I'll fix it.

[chandlerc]

In D30633#758152, @skatkov wrote:

Hello Guys,

To make a progress with landing this patch I need a feedback from you. As I see:

1. Chandler had no issues with this patch
2. David in his e-mail wrote that he is ok with this patch
3. Duncan made a proposal to dd some tests with switch.

I'm just waiting for Duncan to confirm he's happy with the tests. I was planning to give him at least another day as he may have just been busy today.

[skatkov]

sure, thank you Chandler for your time!

[dexonsmith]

Tests LGTM.

lib/Analysis/BranchProbabilityInfo.cpp

165–171

A follow-up patch seems fine. I suggest spreading the remainder among the branches, 1 each until you run out, skipping the unreachable branch.

[skatkov]

lib/Analysis/BranchProbabilityInfo.cpp

165–171

Yest It is clear, the question is the following:
we have 3 branches, 1 unreachable and 2 reachable. The probability of unreachable is 1/0x80000000. Each reachable branch has 0x3fffffff/0x80000000. The remainder is 1. (Please note that with the current patch this remainder will always less then number of reachable branches). So we have two reachable branches and remainder is 1. Where to put it into the first reachable branch or second?

In reality it might be more useful information that two reachable branches has the equal probability then sum of probabilities is equal to one.
Please also note that all other heuristics in these file do not add this remainder. Also please not that before this patch remainder for unreachable heuristic was not ignored as well.

So if I do follow-up patch, it makes sense to fix all other cases as well. However I do not know the clear answer at this moment where to add this remainder. That is the problem.

[skatkov]

Duncan and Chandler, thank you for approval.

lib/Analysis/BranchProbabilityInfo.cpp

 // Probability of the edge BB2->BB3 = 4 / (124 + 4) = 0.03125
 static const uint32_t LBH_TAKEN_WEIGHT = 124;
 static const uint32_t LBH_NONTAKEN_WEIGHT = 4;
 
 /// \brief Unreachable-terminating branch taken weight.
 ///
 /// This is the weight for a branch being taken to a block that terminates
 /// (eventually) in unreachable. These are predicted as unlikely as possible.
-static const uint32_t UR_TAKEN_WEIGHT = 1;
+static const uint32_t UR_TAKEN_WEIGHT = 0;
 
 /// \brief Unreachable-terminating branch not-taken weight.
 ///
 /// This is the weight for a branch not being taken toward a block that
 /// terminates (eventually) in unreachable. Such a branch is essentially never
 /// taken. Set the weight to an absurdly high value so that nested loops don't
 /// easily subsume it.
 static const uint32_t UR_NONTAKEN_WEIGHT = 1024*1024 - 1;
bool BranchProbabilityInfo::calcUnreachableHeuristics(const BasicBlock *BB) {
 
   if (ReachableEdges.empty()) {
     BranchProbability Prob(1, UnreachableEdges.size());
     for (unsigned SuccIdx : UnreachableEdges)
       setEdgeProbability(BB, SuccIdx, Prob);
     return true;
   }
 
   auto UnreachableProb = BranchProbability::getBranchProbability(
       UR_TAKEN_WEIGHT, (UR_TAKEN_WEIGHT + UR_NONTAKEN_WEIGHT) *
                            uint64_t(UnreachableEdges.size()));
   auto ReachableProb = BranchProbability::getBranchProbability(
       UR_NONTAKEN_WEIGHT,
       (UR_TAKEN_WEIGHT + UR_NONTAKEN_WEIGHT) * uint64_t(ReachableEdges.size()));
 
   for (unsigned SuccIdx : UnreachableEdges)
     setEdgeProbability(BB, SuccIdx, UnreachableProb);
   for (unsigned SuccIdx : ReachableEdges)
     setEdgeProbability(BB, SuccIdx, ReachableProb);
 
   return true;
 }
 
bool BranchProbabilityInfo::calcMetadataWeights(const BasicBlock *BB) {
 
   WeightSum = 0;
   for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
     Weights[i] /= ScalingFactor;
     WeightSum += Weights[i];
   }
 
   if (WeightSum == 0) {
     for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
       setEdgeProbability(BB, i, {1, e});
   } else {
     for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
       setEdgeProbability(BB, i, {Weights[i], static_cast<uint32_t>(WeightSum)});
   }
 
   assert(WeightSum <= UINT32_MAX &&
          "Expected weights to scale down to 32 bits");
 

test/Analysis/BranchProbabilityInfo/deopt-intrinsic.ll

 ; RUN: opt -analyze -branch-prob < %s | FileCheck %s
 ; RUN: opt < %s -passes='print<branch-prob>' -disable-output 2>&1 | FileCheck %s
 
 declare i32 @llvm.experimental.deoptimize.i32(...)
 
 define i32 @test1(i32 %a, i32 %b) {
 ; CHECK-LABEL: Printing analysis {{.*}} for function 'test1':
 entry:
   %cond = icmp eq i32 %a, 42
   br i1 %cond, label %exit, label %deopt
 
-; CHECK:  edge entry -> exit probability is 0x7ffff800 / 0x80000000 = 100.00% [HOT edge]
-; CHECK:  edge entry -> deopt probability is 0x00000800 / 0x80000000 = 0.00%
+; CHECK:  edge entry -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
+; CHECK:  edge entry -> deopt probability is 0x00000000 / 0x80000000 = 0.00%
 
 deopt:
   %rval = call i32(...) @llvm.experimental.deoptimize.i32() [ "deopt"() ]
   ret i32 %rval
 
 exit:
   ret i32 %b
 }

test/Analysis/BranchProbabilityInfo/noreturn.ll

 ; Test the static branch probability heuristics for no-return functions.
 ; RUN: opt < %s -analyze -branch-prob | FileCheck %s
 ; RUN: opt < %s -passes='print<branch-prob>' -disable-output 2>&1 | FileCheck %s
 
 declare void @abort() noreturn
 
 define i32 @test1(i32 %a, i32 %b) {
 ; CHECK: Printing analysis {{.*}} for function 'test1'
 entry:
   %cond = icmp eq i32 %a, 42
   br i1 %cond, label %exit, label %abort
-; CHECK: edge entry -> exit probability is 0x7ffff800 / 0x80000000 = 100.00% [HOT edge]
-; CHECK: edge entry -> abort probability is 0x00000800 / 0x80000000 = 0.00%
+; CHECK: edge entry -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
+; CHECK: edge entry -> abort probability is 0x00000000 / 0x80000000 = 0.00%
 
 abort:
   call void @abort() noreturn
   unreachable
 
 exit:
   ret i32 %b
 }
 
 define i32 @test2(i32 %a, i32 %b) {
 ; CHECK: Printing analysis {{.*}} for function 'test2'
 entry:
   switch i32 %a, label %exit [i32 1, label %case_a
                               i32 2, label %case_b
                               i32 3, label %case_c
                               i32 4, label %case_d]
-; CHECK: edge entry -> exit probability is 0x7ffff800 / 0x80000000 = 100.00% [HOT edge]
-; CHECK: edge entry -> case_a probability is 0x00000200 / 0x80000000 = 0.00%
-; CHECK: edge entry -> case_b probability is 0x00000200 / 0x80000000 = 0.00%
-; CHECK: edge entry -> case_c probability is 0x00000200 / 0x80000000 = 0.00%
-; CHECK: edge entry -> case_d probability is 0x00000200 / 0x80000000 = 0.00%
+; CHECK: edge entry -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
+; CHECK: edge entry -> case_a probability is 0x00000000 / 0x80000000 = 0.00%
+; CHECK: edge entry -> case_b probability is 0x00000000 / 0x80000000 = 0.00%
+; CHECK: edge entry -> case_c probability is 0x00000000 / 0x80000000 = 0.00%
+; CHECK: edge entry -> case_d probability is 0x00000000 / 0x80000000 = 0.00%
 
 case_a:
   br label %case_b
 
 case_b:
   br label %case_c
 
 case_c:
   br label %case_d
 
 case_d:
   call void @abort() noreturn
   unreachable
 
 exit:
   ret i32 %b
 }
 
 define i32 @test3(i32 %a, i32 %b) {
 ; CHECK: Printing analysis {{.*}} for function 'test3'
 ; Make sure we unify across multiple conditional branches.
 entry:
   %cond1 = icmp eq i32 %a, 42
   br i1 %cond1, label %exit, label %dom
-; CHECK: edge entry -> exit probability is 0x7ffff800 / 0x80000000 = 100.00% [HOT edge]
-; CHECK: edge entry -> dom probability is 0x00000800 / 0x80000000 = 0.00%
+; CHECK: edge entry -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
+; CHECK: edge entry -> dom probability is 0x00000000 / 0x80000000 = 0.00%
 
 dom:
   %cond2 = icmp ult i32 %a, 42
   br i1 %cond2, label %idom1, label %idom2
 ; CHECK: edge dom -> idom1 probability is 0x40000000 / 0x80000000 = 50.00%
 ; CHECK: edge dom -> idom2 probability is 0x40000000 / 0x80000000 = 50.00%
 
 idom1:

 @_ZTIi = external global i8*
 
 ; CHECK-LABEL: throwSmallException
 ; CHECK-NOT: invoke i32 @smallFunction
 define i32 @throwSmallException(i32 %idx, i32 %limit) #0 personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {
 entry:
   %cmp = icmp sge i32 %idx, %limit
   br i1 %cmp, label %if.then, label %if.end
-; CHECK: edge entry -> if.then probability is 0x00000800 / 0x80000000 = 0.00%
-; CHECK: edge entry -> if.end probability is 0x7ffff800 / 0x80000000 = 100.00% [HOT edge]
+; CHECK: edge entry -> if.then probability is 0x00000000 / 0x80000000 = 0.00%
+; CHECK: edge entry -> if.end probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 if.then:                                          ; preds = %entry
   %exception = call i8* @__cxa_allocate_exception(i64 1) #0
   invoke i32 @smallFunction(i32 %idx)
           to label %invoke.cont unwind label %lpad
 ; CHECK: edge if.then -> invoke.cont probability is 0x7ffff800 / 0x80000000 = 100.00% [HOT edge]
 ; CHECK: edge if.then -> lpad probability is 0x00000800 / 0x80000000 = 0.00%
 

test/CodeGen/X86/switch-order-weight.ll

 ; RUN: llc -mtriple=x86_64-apple-darwin11 < %s | FileCheck %s
 
 ; Check that the cases which lead to unreachable are checked after "10"
 
 define void @test1(i32 %x) nounwind uwtable ssp {
 entry:
   switch i32 %x, label %if.end7 [
     i32 0, label %if.then
     i32 10, label %if.then2
     i32 20, label %if.then5
   ]
 
 ; CHECK-LABEL: test1:
 ; CHECK-NOT: unr
 ; CHECK: cmpl $10
-; CHECK: cmpl $20
 ; CHECK: bar
+; CHECK: cmpl $20
 
 if.then:
   tail call void @unr(i32 23) noreturn nounwind
   unreachable
 
 if.then2:
   tail call void @bar(i32 42) nounwind
   br label %if.end7