This is an archive of the discontinued LLVM Phabricator instance.

[JumpThreading] Preserve profile metadata during select unfolding
ClosedPublic

Authored by rp on Nov 16 2022, 6:49 AM.

Details

Summary

Jump threading can replace select and unconditional branch with
conditional branch, but when doing so loses profile information.

This destructive transform can eventually lead to a performance
degradation due to folding of branches in
shouldFoldCondBranchesToCommonDestination as branch probabilities
are no longer known.

Diff Detail

Event Timeline

rp created this revision.Nov 16 2022, 6:49 AM
Herald added a project: Restricted Project. · View Herald TranscriptNov 16 2022, 6:49 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
rp requested review of this revision.Nov 16 2022, 6:49 AM
Herald added a project: Restricted Project. · View Herald TranscriptNov 16 2022, 6:49 AM
rp added subscribers: ebrevnov, mkazantsev.
rp updated this revision to Diff 476840.Nov 21 2022, 3:15 AM

rebase

mnadeem resigned from this revision.Nov 29 2022, 3:42 PM
mnadeem added reviewers: mkazantsev, nikic.
mkazantsev added inline comments.Dec 5 2022, 12:40 AM
llvm/test/Transforms/JumpThreading/select-unfold-prof.ll
2 ↗(On Diff #476840)
  1. Please use -passes=jump-threading, old PM is being deprecated
  2. Please precommit the test and rebase on top of it
rp updated this revision to Diff 480473.Dec 6 2022, 6:55 AM

Removed the test that was copied from select.ll

The checks were added into existing tests in select.ll instead
as other transformations there also throw away the prof attribute
and will need fixes.

mkazantsev added inline comments.Dec 6 2022, 11:58 PM
llvm/lib/Transforms/Scalar/JumpThreading.cpp
2788

Should this also be under HasProfileData?

rp added inline comments.Dec 7 2022, 3:12 AM
llvm/lib/Transforms/Scalar/JumpThreading.cpp
2788

The code is not very consistent, for example updatePredecessorProfileMetadata updates MD_prof without checking for HasProfile.

As IR with MD_prof attached to instruction yet without MD_prof attached to function will pass validation, I've concluded that it would not be polite to just ignore the attribute.

mkazantsev accepted this revision.Dec 8 2022, 5:20 AM

Ok, looks pretty straightforward. LG.

This revision is now accepted and ready to land.Dec 8 2022, 5:20 AM
rp updated this revision to Diff 481315.Dec 8 2022, 9:00 AM

Rebased

rp added a comment.Dec 8 2022, 9:02 AM

Ok, looks pretty straightforward. LG.

Thanks for review. I've rebased the changes, but I need someone to land them for me as this is my first time. Could you perhaps be the one to merge this?

Yup, I'll do it.

This comment was removed by mkazantsev.
chapuni added a subscriber: chapuni.Jan 9 2023, 1:24 PM
chapuni added inline comments.
llvm/test/Transforms/JumpThreading/select.ll
1–10

Does it require asserts?

lebedev.ri added inline comments.
llvm/test/Transforms/JumpThreading/select.ll
3–8

You should just check the metadata (--check-globals)

cmtice added a subscriber: cmtice.Jan 9 2023, 9:20 PM

This commit breaks the test llvm/test/Transforms/JumpThreading/select.ll if you build the compiler optimized I.e. with '-DCMAKE_BUILD_TYPE=Release'. I tested this by building both the version just before this commit and just after this commit with -DCMAKE_BUILD_TYPE=Release, then running the test:

$ ./bin/llvm-lit -s -v ../llvm/test/Transforms/JumpThreading/select.ll

The version built just before this commit passed.:

$ ./bin/llvm-lit -s -v ../llvm/test/Transforms/JumpThreading/select.ll

Testing Time: 0.10s

Passed: 1

The one built just after this commit failed:

$ ./bin/llvm-lit -s -v ../llvm/test/Transforms/JumpThreading/select.ll
FAIL: LLVM :: Transforms/JumpThreading/select.ll (1 of 1)

  • TEST 'LLVM :: Transforms/JumpThreading/select.ll' FAILED ****

Script:

: 'RUN: at line 2'; /usr/local/google3/cmtice/new-llvm-project/build-opt/bin/opt -S -passes=jump-threading -debug-only=branch-prob < /usr/local/google3/cmtice/new-llvm-project/llvm/test/Transforms/JumpThreading/select.ll 2>&1 | /usr/local/google3/cmtice/new-llvm-project/build-opt/bin/FileCheck /usr/local/google3/cmtice/new-llvm-project/llvm/test/Transforms/JumpThreading/select.ll

Exit Code: 1

Command Output (stderr):

/usr/local/google3/cmtice/new-llvm-project/llvm/test/Transforms/JumpThreading/select.ll:4:16: error: CHECK-LABEL: expected string not found in input
; CHECK-LABEL: ---- Branch Probability Info : unfold1 ----

^

<stdin>:1:1: note: scanning from here
opt: Unknown command line argument '-debug-only=branch-prob'. Try: '/usr/local/google3/cmtice/new-llvm-project/build-opt/bin/opt --help'
^
<stdin>:1:43: note: possible intended match here
opt: Unknown command line argument '-debug-only=branch-prob'. Try: '/usr/local/google3/cmtice/new-llvm-project/build-opt/bin/opt --help'

^

Input file: <stdin>
Check file: /usr/local/google3/cmtice/new-llvm-project/llvm/test/Transforms/JumpThreading/select.ll

-dump-input=help explains the following input dump.

Input was:
<<<<<<

1: opt: Unknown command line argument '-debug-only=branch-prob'. Try: '/usr/local/google3/cmtice/new-llvm-project/build-opt/bin/opt --help'

label:4'0 X~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ error: no match found
label:4'1 ? possible intended match

2: opt: Did you mean '--debug-pass=branch-prob'?

label:4'0 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~



Failed Tests (1):

LLVM :: Transforms/JumpThreading/select.ll

Testing Time: 0.52s

Failed: 1

$

Unfortunately, this change causes assertion failures and I'm going to revert it.

Addition in this line can overflow: BP.emplace_back(BranchProbability(TrueWeight, TrueWeight + FalseWeight));. As a result, the constructor of BranchProbability() can trigger an assertion.

Here's an example in a debugger:

frame #9: 0x000055556f3d47ea clang`llvm::JumpThreadingPass::unfoldSelectInstr(this=0x0000068f36045618, Pred=0x0000068f360e55a0, BB=0x0000068f3613d1a0, SI=0x0000068f36b8a6a0, SIUse=0x0000068f397a53d0, Idx=1) at JumpThreading.cpp:2797:23
   2794     if (extractBranchWeights(*SI, TrueWeight, FalseWeight) &&
   2795         (TrueWeight + FalseWeight) != 0) {
   2796       SmallVector<BranchProbability, 2> BP;
-> 2797       BP.emplace_back(BranchProbability(TrueWeight, TrueWeight + FalseWeight));
   2798       BP.emplace_back(BranchProbability(FalseWeight, TrueWeight + FalseWeight));
   2799       BPI->setEdgeProbability(Pred, BP);
   2800     }
(lldb) p TrueWeight
(uint64_t) $0 = 2147483648
(lldb) p FalseWeight
(uint64_t) $1 = 2147483648
(lldb) down
frame #8: 0x0000555571acc3a6 clang`llvm::BranchProbability::BranchProbability(this=0x00007fffffff0d80, Numerator=2147483648, Denominator=0) at BranchProbability.cpp:41:3
   38   #endif
   39
   40   BranchProbability::BranchProbability(uint32_t Numerator, uint32_t Denominator) {
-> 41     assert(Denominator > 0 && "Denominator cannot be 0!");
   42     assert(Numerator <= Denominator && "Probability cannot be bigger than 1!");
   43     if (Denominator == D)
   44       N = Numerator;
(lldb) p Denominator
(uint32_t) $2 = 0

Unfortunately, I don't have a reduced IR example, but hopefully this should be enough to debug and fix.

Actually I do have a reduced example. Apply this change to the test that you added in this patch to reproduce the assertion failure:

diff --git a/llvm/test/Transforms/JumpThreading/select.ll b/llvm/test/Transforms/JumpThreading/select.ll
index 4c7f3ea7d277..cdaae23694c4 100644
--- a/llvm/test/Transforms/JumpThreading/select.ll
+++ b/llvm/test/Transforms/JumpThreading/select.ll
@@ -660,5 +660,5 @@ if.end:
   ret i32 %v1
 }

-!0 = !{!"branch_weights", i32 1, i32 9}
+!0 = !{!"branch_weights", i32 2147483648, i32 2147483648}
 !1 = !{!"function_entry_count", i64 1984}
rp reopened this revision.Jan 10 2023, 5:27 AM
This revision is now accepted and ready to land.Jan 10 2023, 5:27 AM
rp updated this revision to Diff 487763.Jan 10 2023, 5:27 AM
  1. using getBranchProbability instead of BranchProbability ctor to avoid overflow
  2. branch_weights changed to i64, values are UINT_MAX/4 and 3*UINT_MAX/4
  3. added REQUIRES: asserts
  4. regenerated checks with --check-globals
rp marked 2 inline comments as done.Jan 10 2023, 5:31 AM

Actually I do have a reduced example. Apply this change to the test that you added in this patch to reproduce the assertion failure

Thank you very much, I've updated branch weights to be overflowing and 25/75% instead of 50/50%. If I may ask, how did you get the overflows, is there some automation that triggers it?

rp marked 2 inline comments as not done.Jan 10 2023, 6:19 AM
rp added inline comments.
llvm/test/Transforms/JumpThreading/select.ll
3–8

Is it possible to check edge probabilities with metadata? As when I hard-code this code into probability calculation:

BP.emplace_back(BranchProbability::getBranchProbability(1, 10));
      BP.emplace_back(BranchProbability::getBranchProbability(9, 10));

The probabilities in those checks will be reported as 10/90%, yet the prof metadata will stay as it was - 25/75%.

rp requested review of this revision.Jan 10 2023, 6:45 AM
rp marked an inline comment as not done.
In D138132#4039546, @rp wrote:

If I may ask, how did you get the overflows, is there some automation that triggers it?

I got this crash while running Clang on a real-world project internally at Google.

nikic resigned from this revision.Jan 10 2023, 8:32 AM
rp updated this revision to Diff 488125.Jan 11 2023, 2:35 AM

run clang-format

mkazantsev accepted this revision.Jan 16 2023, 3:27 AM

LG since the overflow is now fixed.

This revision is now accepted and ready to land.Jan 16 2023, 3:27 AM
mkazantsev added inline comments.Jan 16 2023, 3:31 AM
llvm/test/Transforms/JumpThreading/select.ll
22

Please regenerate test.