diff options
author | Hal Finkel <hfinkel@anl.gov> | 2013-11-01 10:58:22 +0000 |
---|---|---|
committer | Hal Finkel <hfinkel@anl.gov> | 2013-11-01 10:58:22 +0000 |
commit | e14fb073574dcb74de05bdeedbfb3fcffbfa1bf6 (patch) | |
tree | 10a5655b64112d33790b371fde46bb0be6693316 | |
parent | 0097e155025767c11790912dcf780f82dffaffb1 (diff) | |
download | llvm-e14fb073574dcb74de05bdeedbfb3fcffbfa1bf6.tar.gz llvm-e14fb073574dcb74de05bdeedbfb3fcffbfa1bf6.tar.bz2 llvm-e14fb073574dcb74de05bdeedbfb3fcffbfa1bf6.tar.xz |
Consider (x == -1) unlikely in BranchProbabilityInfo
This adds another heuristic to BPI, similar to the existing heuristic that
considers (x == 0) unlikely to be true. As suggested in the PACT'98 paper by
Deitrich, Cheng, and Hwu, -1 is often used to indicate an invalid index, and
equality comparisons with -1 are also unlikely to succeed. Local
experimentation supports this hypothesis: This yields a 1-2% speedup in the
test-suite sqlite benchmark on the PPC A2 core, with no significant
regressions.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@193855 91177308-0d34-0410-b5e6-96231b3b80d8
-rw-r--r-- | lib/Analysis/BranchProbabilityInfo.cpp | 22 | ||||
-rw-r--r-- | test/Analysis/BranchProbabilityInfo/basic.ll | 39 |
2 files changed, 57 insertions, 4 deletions
diff --git a/lib/Analysis/BranchProbabilityInfo.cpp b/lib/Analysis/BranchProbabilityInfo.cpp index 7cdf828c2f..86560ca33d 100644 --- a/lib/Analysis/BranchProbabilityInfo.cpp +++ b/lib/Analysis/BranchProbabilityInfo.cpp @@ -398,10 +398,24 @@ bool BranchProbabilityInfo::calcZeroHeuristics(BasicBlock *BB) { // InstCombine canonicalizes X <= 0 into X < 1. // X <= 0 -> Unlikely isProb = false; - } else if (CV->isAllOnesValue() && CI->getPredicate() == CmpInst::ICMP_SGT) { - // InstCombine canonicalizes X >= 0 into X > -1. - // X >= 0 -> Likely - isProb = true; + } else if (CV->isAllOnesValue()) { + switch (CI->getPredicate()) { + case CmpInst::ICMP_EQ: + // X == -1 -> Unlikely + isProb = false; + break; + case CmpInst::ICMP_NE: + // X != -1 -> Likely + isProb = true; + break; + case CmpInst::ICMP_SGT: + // InstCombine canonicalizes X >= 0 into X > -1. + // X >= 0 -> Likely + isProb = true; + break; + default: + return false; + } } else { return false; } diff --git a/test/Analysis/BranchProbabilityInfo/basic.ll b/test/Analysis/BranchProbabilityInfo/basic.ll index c6e1bde81d..05cb31dca0 100644 --- a/test/Analysis/BranchProbabilityInfo/basic.ll +++ b/test/Analysis/BranchProbabilityInfo/basic.ll @@ -173,3 +173,42 @@ exit: %ret = phi i32 [ %val4, %then ], [ %val3, %else ] ret i32 %ret } + +define i32 @zero1(i32 %i, i32 %a, i32 %b) { +; CHECK: Printing analysis {{.*}} for function 'zero1' +entry: + %cond = icmp eq i32 %i, 0 + br i1 %cond, label %then, label %else +; CHECK: edge entry -> then probability is 12 / 32 +; CHECK: edge entry -> else probability is 20 / 32 + +then: + br label %exit + +else: + br label %exit + +exit: + %result = phi i32 [ %a, %then ], [ %b, %else ] + ret i32 %result +} + +define i32 @zero2(i32 %i, i32 %a, i32 %b) { +; CHECK: Printing analysis {{.*}} for function 'zero2' +entry: + %cond = icmp ne i32 %i, -1 + br i1 %cond, label %then, label %else +; CHECK: edge entry -> then probability is 20 / 32 +; CHECK: edge entry -> else probability is 12 / 32 + +then: + br label %exit + +else: + br label %exit + +exit: + %result = phi i32 [ %a, %then ], [ %b, %else ] + ret i32 %result +} + |