This is an archive of the discontinued LLVM Phabricator instance.

Assign weights to edges to jump table when lowering switch statement.
ClosedPublic

Authored by congh on Aug 19 2015, 12:57 PM.

Details

Summary

Currently, when lowering switch statement and a new basic block is built for jump table, the edge to this new block is not assigned with a correct weight. This patch collects the edge weight from all its successors and assign this sum of weights to the edge (and also the other fall-through edge). Test cases are adjusted accordingly.

Diff Detail

Event Timeline

congh updated this revision to Diff 32598.Aug 19 2015, 12:57 PM
congh retitled this revision from to Assign weights to edges to jump table when lowering switch statement..
congh updated this object.
congh added reviewers: hfinkel, spatel, davidxl.
congh added a subscriber: llvm-commits.
davidxl edited edge metadata.Aug 20 2015, 10:54 AM

Can we add more unit test cases (with annotated profile data) to cover profile update for various switch lowering strategies?

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
1901

Same bug occurs here too. The weight to MBB should be the sum of the ExtraWeight of all cases of 'B'. See visitBitTestCase.

congh added a comment.Aug 20 2015, 3:25 PM

Can we add more unit test cases (with annotated profile data) to cover profile update for various switch lowering strategies?

OK. I will investigate on switch lowering and try to make a test case covering all cases with profile data check.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
1901

You are right. I will also fix this issue in this patch.

congh updated this revision to Diff 32778.Aug 20 2015, 5:48 PM
congh edited edge metadata.

Update the patch by also adding forgotten edge weight when adding bit test header for lowering switch statement.

This looks fine to me in general, but other reviewers or Hans may need to take a look.

(The additional test cases can be added as a follow up).

congh added a reviewer: hans.Aug 21 2015, 3:30 PM

This looks fine to me in general, but other reviewers or Hans may need to take a look.

(The additional test cases can be added as a follow up).

OK, thanks! I have added Hans as a reviewer.

hans edited edge metadata.Aug 21 2015, 4:47 PM

This looks fine to me, but it would be really nice to get tests here.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
1901

Does it get the DefaultWeight right here? (Not a criticism, just wondering if this ever worked.)

8018

I think the sum of all the branch weights on a branch (in this case a SwitchInst) will not overflow an uint32_t. Since we're adding up weights from the same switch it should be safe to use uint32_t for JumpWeight and skip the ScaleWeights below.

congh added inline comments.Aug 21 2015, 5:08 PM
lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
1901

Yes. getEdgeWeight() will retrieve edge weight through BPI from BB instead of MBB.

8018

You are right. I will replace uint64_t with uint32_t and remove ScaleWeights() here. Thanks for pointing it out!

congh updated this revision to Diff 33136.Aug 25 2015, 3:36 PM
congh edited edge metadata.

Change the type of weight from uint64_t to uint32_t as there won't be overflow in calculation.

Add a test case that checks if the edge weight to the jump table is correct.

congh updated this revision to Diff 33137.Aug 25 2015, 3:42 PM

Fixed a small issue in the newly added test case.

Hi Hans

Could you please take a look at this patch and see if it is ok to be
checked in? Thank you!

Cong

thanks,
Cong

hans accepted this revision.Aug 26 2015, 1:27 PM
hans edited edge metadata.

Yes, lgtm. Sorry for the delay.

test/CodeGen/X86/switch-jump-table.ll
58

This isn't really checking the probabilities though, but the block placement. Maybe that's the best we can do? :-/

Maybe use a more descriptive prefix than CHECK2? CHECK-PLACEMENT?

This revision is now accepted and ready to land.Aug 26 2015, 1:27 PM
congh added inline comments.Aug 26 2015, 1:48 PM
test/CodeGen/X86/switch-jump-table.ll
58

As this fix is for lowering IR to MC so I think the best pass that we should indicate here is expand-isel-pseudos. I have updated it. I also changed CHECK2 into CHECK-JT-WEIGHT to make it more descriptive. Thanks!

This revision was automatically updated to reflect the committed changes.