This is an archive of the discontinued LLVM Phabricator instance.

Distribute the weight on the edge from switch to default statement to edges generated in lowering switch.
ClosedPublic

Authored by congh on Aug 27 2015, 4:50 PM.

Details

Summary

Currently, when edge weights are assigned to edges that are created when lowering switch statement, the weight on the edge to default statement (let's call it "default weight" here) is not considered. We need to distribute this weight properly. However, without value profiling, we have no idea how to distribute it. In this patch, I applied the heuristic that this weight is evenly distributed to successors.

For example, given a switch statement with cases 1,2,3,5,10,11,20, and every edge from switch to each successor has weight 10. If there is a binary search tree built to test if n < 10, then its two out-edges will have weight 4x10+10/2 = 45 and 3x10 + 10/2 = 35 respectively (currently they are 40 and 30 without considering the default weight). Each distribution (which is 5 here) will be stored in each SwitchWorkListItem for further distribution.

There are some exceptions:

  1. For a jump table header which doesn't have any edge to default statement, we don't distribute the default weight to it.
  2. For a bit test header which covers a contiguous range and hence has no edges to default statement, we don't distribute the default weight to it.
  3. When the branch checks a single value or a contiguous range with no edge to default statement, we don't distribute the default weight to it.

In other cases, the default weight is evenly distributed to successors.

Diff Detail

Event Timeline

congh updated this revision to Diff 33377.Aug 27 2015, 4:50 PM
congh retitled this revision from to Distribute the weight on the edge from switch to default statement to edges generated in lowering switch..
congh updated this object.
congh added reviewers: hans, spatel, davidxl.
congh added a subscriber: llvm-commits.
hans edited edge metadata.Aug 28 2015, 10:58 AM

Thanks for digging into this!

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
8049

I think we spell it Fallthrough elsewhere, so maybe rename to FallthroughWeight?

8051

s/distributed/distribute/ ?

8056

Could probably just do "for (MachineBasicBlock *Succ : JumpMBB->successors())" here.

8094

s/distributed/distribute/

8098

shouldn't it be -= on the DefaultWeight?

8100

why do we need this else case?

test/CodeGen/X86/switch-edge-weight.ll
41

It would be super nice if these tests could have comments explaining why these weights are in fact the correct ones.

I don't know if this is a reasonable expectation or not, just throwing it out there - it would make it easier for someone reading the test to verify what's going on.

In this test it seems we'll have four ranges, {1}, {155-159}, {1134} and {1140}. I think the pivot here will be 1134, so the weight on the left is 10+50+10/2=65 and on the right is 10+10+10/5=25, so that matches my expectations. But why are the weights so low below? Shouldn't the edge from the 155-159 range to sw.bb have more weight?

davidxl added inline comments.Aug 28 2015, 12:32 PM
test/CodeGen/X86/switch-edge-weight.ll
41

The weight distribution makes sense to me.

BB#5 has as test ' %x == 1140'. Since BB#5's weight is 25 and 1140's weight is 10, so this leaves BB#6 15.

BB#6 has check %x == 1134. One successor is 10, and the remaining (part of the default) is 5.

congh marked 3 inline comments as done.Aug 28 2015, 2:31 PM
congh added inline comments.
lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
8049

OK.

8056

setSuccWeight() needs an iterator as input and that is why I use iterators in this loop.

8098

Here BTB->DefaultWeight hasn't been updated by adding DefaultWeight to it (it is initialized with UnhandledWeights which doesn't include DefaultWeight) . So it will share a half of it now.

8100

This is because UnhandledWeights doesn't include DefaultWeight. Or I can do this before this branch and use -= in the true body.

test/CodeGen/X86/switch-edge-weight.ll
41

I missed one more check that includes the edge weight from switch to 155-159 range. I will add it here and also add comments explaining why we check those numbers.

congh updated this revision to Diff 33484.Aug 28 2015, 3:37 PM
congh edited edge metadata.
congh marked an inline comment as done.

Update the patch according to Hans's comments. Also add descriptions to the test file explaining what to test.

hans accepted this revision.Aug 31 2015, 11:46 AM
hans edited edge metadata.
hans added a subscriber: test.

LGTM!

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
8100

I see. I think your update made it easier to follow though, and it's nice that it matches the similar code further up.

test/CodeGen/X86/switch-edge-weight.ll
41

Very nice, thanks!

60

The switch has four clusters though, so it becomes a binary tree with range checks in the leafs, just like @test above. Is this one testing something that @test doesn't?

115

s/statement/basic block/

This revision is now accepted and ready to land.Aug 31 2015, 11:46 AM
congh marked an inline comment as done.Aug 31 2015, 6:24 PM

Thanks for the review, Hans!

test/CodeGen/X86/switch-edge-weight.ll
60

In this switch statement there are two jump targets instead of 1 in @test. However, I found they are still testing the same thing so I will go ahead and delete this test. Thanks for pointing it out!

115

OK.

This revision was automatically updated to reflect the committed changes.