Index: llvm/trunk/include/llvm/Analysis/BranchProbabilityInfo.h =================================================================== --- llvm/trunk/include/llvm/Analysis/BranchProbabilityInfo.h +++ llvm/trunk/include/llvm/Analysis/BranchProbabilityInfo.h @@ -26,6 +26,7 @@ namespace llvm { class LoopInfo; +class TargetLibraryInfo; class raw_ostream; /// \brief Analysis providing branch probability information. @@ -43,8 +44,9 @@ class BranchProbabilityInfo { public: BranchProbabilityInfo() {} - BranchProbabilityInfo(const Function &F, const LoopInfo &LI) { - calculate(F, LI); + BranchProbabilityInfo(const Function &F, const LoopInfo &LI, + const TargetLibraryInfo *TLI = nullptr) { + calculate(F, LI, TLI); } BranchProbabilityInfo(BranchProbabilityInfo &&Arg) @@ -116,7 +118,8 @@ return IsLikely ? LikelyProb : LikelyProb.getCompl(); } - void calculate(const Function &F, const LoopInfo &LI); + void calculate(const Function &F, const LoopInfo &LI, + const TargetLibraryInfo *TLI = nullptr); /// Forget analysis results for the given basic block. void eraseBlock(const BasicBlock *BB); @@ -171,7 +174,7 @@ bool calcColdCallHeuristics(const BasicBlock *BB); bool calcPointerHeuristics(const BasicBlock *BB); bool calcLoopBranchHeuristics(const BasicBlock *BB, const LoopInfo &LI); - bool calcZeroHeuristics(const BasicBlock *BB); + bool calcZeroHeuristics(const BasicBlock *BB, const TargetLibraryInfo *TLI); bool calcFloatingPointHeuristics(const BasicBlock *BB); bool calcInvokeHeuristics(const BasicBlock *BB); }; Index: llvm/trunk/include/llvm/Analysis/LazyBranchProbabilityInfo.h =================================================================== --- llvm/trunk/include/llvm/Analysis/LazyBranchProbabilityInfo.h +++ llvm/trunk/include/llvm/Analysis/LazyBranchProbabilityInfo.h @@ -24,6 +24,7 @@ class AnalysisUsage; class Function; class LoopInfo; +class TargetLibraryInfo; /// \brief This is an alternative analysis pass to /// BranchProbabilityInfoWrapperPass. The difference is that with this pass the @@ -55,14 +56,15 @@ /// analysis without paying for the overhead if BPI doesn't end up being used. class LazyBranchProbabilityInfo { public: - LazyBranchProbabilityInfo(const Function *F, const LoopInfo *LI) - : Calculated(false), F(F), LI(LI) {} + LazyBranchProbabilityInfo(const Function *F, const LoopInfo *LI, + const TargetLibraryInfo *TLI) + : Calculated(false), F(F), LI(LI), TLI(TLI) {} /// Retrieve the BPI with the branch probabilities computed. BranchProbabilityInfo &getCalculated() { if (!Calculated) { assert(F && LI && "call setAnalysis"); - BPI.calculate(*F, *LI); + BPI.calculate(*F, *LI, TLI); Calculated = true; } return BPI; @@ -77,6 +79,7 @@ bool Calculated; const Function *F; const LoopInfo *LI; + const TargetLibraryInfo *TLI; }; std::unique_ptr LBPI; Index: llvm/trunk/lib/Analysis/BranchProbabilityInfo.cpp =================================================================== --- llvm/trunk/lib/Analysis/BranchProbabilityInfo.cpp +++ llvm/trunk/lib/Analysis/BranchProbabilityInfo.cpp @@ -14,6 +14,7 @@ #include "llvm/Analysis/BranchProbabilityInfo.h" #include "llvm/ADT/PostOrderIterator.h" #include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/IR/CFG.h" #include "llvm/IR/Constants.h" #include "llvm/IR/Function.h" @@ -30,6 +31,7 @@ INITIALIZE_PASS_BEGIN(BranchProbabilityInfoWrapperPass, "branch-prob", "Branch Probability Analysis", false, true) INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) INITIALIZE_PASS_END(BranchProbabilityInfoWrapperPass, "branch-prob", "Branch Probability Analysis", false, true) @@ -457,7 +459,8 @@ return true; } -bool BranchProbabilityInfo::calcZeroHeuristics(const BasicBlock *BB) { +bool BranchProbabilityInfo::calcZeroHeuristics(const BasicBlock *BB, + const TargetLibraryInfo *TLI) { const BranchInst *BI = dyn_cast(BB->getTerminator()); if (!BI || !BI->isConditional()) return false; @@ -480,8 +483,37 @@ if (AndRHS->getUniqueInteger().isPowerOf2()) return false; + // Check if the LHS is the return value of a library function + LibFunc Func = NumLibFuncs; + if (TLI) + if (CallInst *Call = dyn_cast(CI->getOperand(0))) + if (Function *CalledFn = Call->getCalledFunction()) + TLI->getLibFunc(*CalledFn, Func); + bool isProb; - if (CV->isZero()) { + if (Func == LibFunc_strcasecmp || + Func == LibFunc_strcmp || + Func == LibFunc_strncasecmp || + Func == LibFunc_strncmp || + Func == LibFunc_memcmp) { + // strcmp and similar functions return zero, negative, or positive, if the + // first string is equal, less, or greater than the second. We consider it + // likely that the strings are not equal, so a comparison with zero is + // probably false, but also a comparison with any other number is also + // probably false given that what exactly is returned for nonzero values is + // not specified. Any kind of comparison other than equality we know + // nothing about. + switch (CI->getPredicate()) { + case CmpInst::ICMP_EQ: + isProb = false; + break; + case CmpInst::ICMP_NE: + isProb = true; + break; + default: + return false; + } + } else if (CV->isZero()) { switch (CI->getPredicate()) { case CmpInst::ICMP_EQ: // X == 0 -> Unlikely @@ -707,7 +739,8 @@ } } -void BranchProbabilityInfo::calculate(const Function &F, const LoopInfo &LI) { +void BranchProbabilityInfo::calculate(const Function &F, const LoopInfo &LI, + const TargetLibraryInfo *TLI) { DEBUG(dbgs() << "---- Branch Probability Info : " << F.getName() << " ----\n\n"); LastF = &F; // Store the last function we ran on for printing. @@ -733,7 +766,7 @@ continue; if (calcPointerHeuristics(BB)) continue; - if (calcZeroHeuristics(BB)) + if (calcZeroHeuristics(BB, TLI)) continue; if (calcFloatingPointHeuristics(BB)) continue; @@ -747,12 +780,14 @@ void BranchProbabilityInfoWrapperPass::getAnalysisUsage( AnalysisUsage &AU) const { AU.addRequired(); + AU.addRequired(); AU.setPreservesAll(); } bool BranchProbabilityInfoWrapperPass::runOnFunction(Function &F) { const LoopInfo &LI = getAnalysis().getLoopInfo(); - BPI.calculate(F, LI); + const TargetLibraryInfo &TLI = getAnalysis().getTLI(); + BPI.calculate(F, LI, &TLI); return false; } @@ -767,7 +802,7 @@ BranchProbabilityInfo BranchProbabilityAnalysis::run(Function &F, FunctionAnalysisManager &AM) { BranchProbabilityInfo BPI; - BPI.calculate(F, AM.getResult(F)); + BPI.calculate(F, AM.getResult(F), &AM.getResult(F)); return BPI; } Index: llvm/trunk/lib/Analysis/LazyBranchProbabilityInfo.cpp =================================================================== --- llvm/trunk/lib/Analysis/LazyBranchProbabilityInfo.cpp +++ llvm/trunk/lib/Analysis/LazyBranchProbabilityInfo.cpp @@ -16,6 +16,7 @@ #include "llvm/Analysis/LazyBranchProbabilityInfo.h" #include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/TargetLibraryInfo.h" using namespace llvm; @@ -24,6 +25,7 @@ INITIALIZE_PASS_BEGIN(LazyBranchProbabilityInfoPass, DEBUG_TYPE, "Lazy Branch Probability Analysis", true, true) INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) INITIALIZE_PASS_END(LazyBranchProbabilityInfoPass, DEBUG_TYPE, "Lazy Branch Probability Analysis", true, true) @@ -41,6 +43,7 @@ void LazyBranchProbabilityInfoPass::getAnalysisUsage(AnalysisUsage &AU) const { AU.addRequired(); + AU.addRequired(); AU.setPreservesAll(); } @@ -48,16 +51,19 @@ bool LazyBranchProbabilityInfoPass::runOnFunction(Function &F) { LoopInfo &LI = getAnalysis().getLoopInfo(); - LBPI = llvm::make_unique(&F, &LI); + TargetLibraryInfo &TLI = getAnalysis().getTLI(); + LBPI = llvm::make_unique(&F, &LI, &TLI); return false; } void LazyBranchProbabilityInfoPass::getLazyBPIAnalysisUsage(AnalysisUsage &AU) { AU.addRequired(); AU.addRequired(); + AU.addRequired(); } void llvm::initializeLazyBPIPassPass(PassRegistry &Registry) { INITIALIZE_PASS_DEPENDENCY(LazyBranchProbabilityInfoPass); INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass); + INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass); } Index: llvm/trunk/lib/Transforms/Scalar/JumpThreading.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/JumpThreading.cpp +++ llvm/trunk/lib/Transforms/Scalar/JumpThreading.cpp @@ -132,7 +132,7 @@ bool HasProfileData = F.getEntryCount().hasValue(); if (HasProfileData) { LoopInfo LI{DominatorTree(F)}; - BPI.reset(new BranchProbabilityInfo(F, LI)); + BPI.reset(new BranchProbabilityInfo(F, LI, TLI)); BFI.reset(new BlockFrequencyInfo(F, *BPI, LI)); } @@ -152,7 +152,7 @@ bool HasProfileData = F.getEntryCount().hasValue(); if (HasProfileData) { LoopInfo LI{DominatorTree(F)}; - BPI.reset(new BranchProbabilityInfo(F, LI)); + BPI.reset(new BranchProbabilityInfo(F, LI, &TLI)); BFI.reset(new BlockFrequencyInfo(F, *BPI, LI)); } Index: llvm/trunk/test/Analysis/BranchProbabilityInfo/libfunc_call.ll =================================================================== --- llvm/trunk/test/Analysis/BranchProbabilityInfo/libfunc_call.ll +++ llvm/trunk/test/Analysis/BranchProbabilityInfo/libfunc_call.ll @@ -0,0 +1,264 @@ +; RUN: opt < %s -analyze -branch-prob | FileCheck %s +; RUN: opt < %s -analyze -lazy-branch-prob | FileCheck %s +; RUN: opt < %s -passes='print' -disable-output 2>&1 | FileCheck %s + +declare i32 @strcmp(i8*, i8*) +declare i32 @strncmp(i8*, i8*, i32) +declare i32 @strcasecmp(i8*, i8*) +declare i32 @strncasecmp(i8*, i8*, i32) +declare i32 @memcmp(i8*, i8*) +declare i32 @nonstrcmp(i8*, i8*) + + +; Check that the result of strcmp is considered more likely to be nonzero than +; zero, and equally likely to be (nonzero) positive or negative. + +define i32 @test_strcmp_eq(i8* %p, i8* %q) { +; CHECK: Printing analysis {{.*}} for function 'test_strcmp_eq' +entry: + %val = call i32 @strcmp(i8* %p, i8* %q) + %cond = icmp eq i32 %val, 0 + br i1 %cond, label %then, label %else +; CHECK: edge entry -> then probability is 0x30000000 / 0x80000000 = 37.50% +; CHECK: edge entry -> else probability is 0x50000000 / 0x80000000 = 62.50% + +then: + br label %exit +; CHECK: edge then -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +else: + br label %exit +; CHECK: edge else -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +exit: + %result = phi i32 [ 0, %then ], [ 1, %else ] + ret i32 %result +} + +define i32 @test_strcmp_ne(i8* %p, i8* %q) { +; CHECK: Printing analysis {{.*}} for function 'test_strcmp_ne' +entry: + %val = call i32 @strcmp(i8* %p, i8* %q) + %cond = icmp ne i32 %val, 0 + br i1 %cond, label %then, label %else +; CHECK: edge entry -> then probability is 0x50000000 / 0x80000000 = 62.50% +; CHECK: edge entry -> else probability is 0x30000000 / 0x80000000 = 37.50% + +then: + br label %exit +; CHECK: edge then -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +else: + br label %exit +; CHECK: edge else -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +exit: + %result = phi i32 [ 0, %then ], [ 1, %else ] + ret i32 %result +} + +define i32 @test_strcmp_sgt(i8* %p, i8* %q) { +; CHECK: Printing analysis {{.*}} for function 'test_strcmp_sgt' +entry: + %val = call i32 @strcmp(i8* %p, i8* %q) + %cond = icmp sgt i32 %val, 0 + br i1 %cond, label %then, label %else +; CHECK: edge entry -> then probability is 0x40000000 / 0x80000000 = 50.00% +; CHECK: edge entry -> else probability is 0x40000000 / 0x80000000 = 50.00% + +then: + br label %exit +; CHECK: edge then -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +else: + br label %exit +; CHECK: edge else -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +exit: + %result = phi i32 [ 0, %then ], [ 1, %else ] + ret i32 %result +} + +define i32 @test_strcmp_slt(i8* %p, i8* %q) { +; CHECK: Printing analysis {{.*}} for function 'test_strcmp_slt' +entry: + %val = call i32 @strcmp(i8* %p, i8* %q) + %cond = icmp slt i32 %val, 0 + br i1 %cond, label %then, label %else +; CHECK: edge entry -> then probability is 0x40000000 / 0x80000000 = 50.00% +; CHECK: edge entry -> else probability is 0x40000000 / 0x80000000 = 50.00% + +then: + br label %exit +; CHECK: edge then -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +else: + br label %exit +; CHECK: edge else -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +exit: + %result = phi i32 [ 0, %then ], [ 1, %else ] + ret i32 %result +} + + +; Similarly check other library functions that have the same behaviour + +define i32 @test_strncmp_sgt(i8* %p, i8* %q) { +; CHECK: Printing analysis {{.*}} for function 'test_strncmp_sgt' +entry: + %val = call i32 @strncmp(i8* %p, i8* %q, i32 4) + %cond = icmp sgt i32 %val, 0 + br i1 %cond, label %then, label %else +; CHECK: edge entry -> then probability is 0x40000000 / 0x80000000 = 50.00% +; CHECK: edge entry -> else probability is 0x40000000 / 0x80000000 = 50.00% + +then: + br label %exit +; CHECK: edge then -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +else: + br label %exit +; CHECK: edge else -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +exit: + %result = phi i32 [ 0, %then ], [ 1, %else ] + ret i32 %result +} + +define i32 @test_strcasecmp_sgt(i8* %p, i8* %q) { +; CHECK: Printing analysis {{.*}} for function 'test_strcasecmp_sgt' +entry: + %val = call i32 @strcasecmp(i8* %p, i8* %q) + %cond = icmp sgt i32 %val, 0 + br i1 %cond, label %then, label %else +; CHECK: edge entry -> then probability is 0x40000000 / 0x80000000 = 50.00% +; CHECK: edge entry -> else probability is 0x40000000 / 0x80000000 = 50.00% + +then: + br label %exit +; CHECK: edge then -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +else: + br label %exit +; CHECK: edge else -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +exit: + %result = phi i32 [ 0, %then ], [ 1, %else ] + ret i32 %result +} + +define i32 @test_strncasecmp_sgt(i8* %p, i8* %q) { +; CHECK: Printing analysis {{.*}} for function 'test_strncasecmp_sgt' +entry: + %val = call i32 @strncasecmp(i8* %p, i8* %q, i32 4) + %cond = icmp sgt i32 %val, 0 + br i1 %cond, label %then, label %else +; CHECK: edge entry -> then probability is 0x40000000 / 0x80000000 = 50.00% +; CHECK: edge entry -> else probability is 0x40000000 / 0x80000000 = 50.00% + +then: + br label %exit +; CHECK: edge then -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +else: + br label %exit +; CHECK: edge else -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +exit: + %result = phi i32 [ 0, %then ], [ 1, %else ] + ret i32 %result +} + +define i32 @test_memcmp_sgt(i8* %p, i8* %q) { +; CHECK: Printing analysis {{.*}} for function 'test_memcmp_sgt' +entry: + %val = call i32 @memcmp(i8* %p, i8* %q) + %cond = icmp sgt i32 %val, 0 + br i1 %cond, label %then, label %else +; CHECK: edge entry -> then probability is 0x40000000 / 0x80000000 = 50.00% +; CHECK: edge entry -> else probability is 0x40000000 / 0x80000000 = 50.00% + +then: + br label %exit +; CHECK: edge then -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +else: + br label %exit +; CHECK: edge else -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +exit: + %result = phi i32 [ 0, %then ], [ 1, %else ] + ret i32 %result +} + + +; Check that for the result of a call to a non-library function the default +; heuristic is applied, i.e. positive more likely than negative, nonzero more +; likely than zero. + +define i32 @test_nonstrcmp_eq(i8* %p, i8* %q) { +; CHECK: Printing analysis {{.*}} for function 'test_nonstrcmp_eq' +entry: + %val = call i32 @nonstrcmp(i8* %p, i8* %q) + %cond = icmp eq i32 %val, 0 + br i1 %cond, label %then, label %else +; CHECK: edge entry -> then probability is 0x30000000 / 0x80000000 = 37.50% +; CHECK: edge entry -> else probability is 0x50000000 / 0x80000000 = 62.50% + +then: + br label %exit +; CHECK: edge then -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +else: + br label %exit +; CHECK: edge else -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +exit: + %result = phi i32 [ 0, %then ], [ 1, %else ] + ret i32 %result +} + +define i32 @test_nonstrcmp_ne(i8* %p, i8* %q) { +; CHECK: Printing analysis {{.*}} for function 'test_nonstrcmp_ne' +entry: + %val = call i32 @nonstrcmp(i8* %p, i8* %q) + %cond = icmp ne i32 %val, 0 + br i1 %cond, label %then, label %else +; CHECK: edge entry -> then probability is 0x50000000 / 0x80000000 = 62.50% +; CHECK: edge entry -> else probability is 0x30000000 / 0x80000000 = 37.50% + +then: + br label %exit +; CHECK: edge then -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +else: + br label %exit +; CHECK: edge else -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +exit: + %result = phi i32 [ 0, %then ], [ 1, %else ] + ret i32 %result +} + +define i32 @test_nonstrcmp_sgt(i8* %p, i8* %q) { +; CHECK: Printing analysis {{.*}} for function 'test_nonstrcmp_sgt' +entry: + %val = call i32 @nonstrcmp(i8* %p, i8* %q) + %cond = icmp sgt i32 %val, 0 + br i1 %cond, label %then, label %else +; CHECK: edge entry -> then probability is 0x50000000 / 0x80000000 = 62.50% +; CHECK: edge entry -> else probability is 0x30000000 / 0x80000000 = 37.50% + +then: + br label %exit +; CHECK: edge then -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +else: + br label %exit +; CHECK: edge else -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +exit: + %result = phi i32 [ 0, %then ], [ 1, %else ] + ret i32 %result +}