[BPI] Don't assume that strcmp returning >0 is more likely than <0

[john.brawn]

Summary

The zero heuristic assumes that integers are more likely positive than negative, but this also has the effect of assuming that strcmp return values are more likely positive than negative. Given that for nonzero strcmp return values it's the ordering of arguments that determines the sign of the result there's no reason to assume that's true.

Fix this by inspecting the LHS of the compare and using TargetLibraryInfo to decide if it's strcmp-like, and if so only assume that nonzero is more likely than zero i.e. strings are more often different than the same. This causes a slight code generation change in the spec2006 benchmark 403.gcc, but with no noticeable performance impact. The intent of this patch is to allow better optimisation of dhrystone on Cortex-M cpus, but currently it won't as there are also some changes that need to be made to if-conversion.

[chandlerc]

Generally makes sense, but maybe check the intuition of some other folks who've been hacking on static heuristics recently... Also, a small simplifying (I hope) comment inline.

include/llvm/Analysis/BranchProbabilityInfo.h

48 ↗

(On Diff #101542)

Is all of the support for null TLI necessary? It seems like we should always be able to provide it..

[john.brawn]

include/llvm/Analysis/BranchProbabilityInfo.h

48 ↗

(On Diff #101542)

BranchProbabilityInfo is created directly (without using the pass manager) in ModuleSummaryAnalysis, OptimizationDiagnosticInfo, PartialInlining, and PGOInstrumentation, and would require some extra plumbing to have a TargetLibraryInfo available at the point it is created. Or alternatively I could create TargetLibraryInfo directly, except that's messy as there's no simple way to do that.

[skatkov]

Looks reasonable to me.
I would rename the name of the test to something related to string compare instead of just call.

[davidxl]

lib/Analysis/BranchProbabilityInfo.cpp

494 ↗

(On Diff #101542)

memcmp should be handled similarly here.

[john.brawn]

Handle memcmp in the same way, and adjust the name of the test.

[davidxl]

lgtm

llvm/trunk/include/llvm/Analysis/BranchProbabilityInfo.h

 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/BranchProbability.h"
 
 namespace llvm {
 class LoopInfo;
+class TargetLibraryInfo;
 class raw_ostream;
 
 /// \brief Analysis providing branch probability information.
 ///
 /// This is a function analysis which provides information on the relative
 /// probabilities of each "edge" in the function's CFG where such an edge is
 /// defined by a pair (PredBlock and an index in the successors). The
 /// probability of an edge from one block is always relative to the
 /// probabilities of other edges from the block. The probabilites of all edges
 /// from a block sum to exactly one (100%).
 /// We use a pair (PredBlock and an index in the successors) to uniquely
 /// identify an edge, since we can have multiple edges from Src to Dst.
 /// As an example, we can have a switch which jumps to Dst with value 0 and
 /// value 10.
 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)
       : Probs(std::move(Arg.Probs)), LastF(Arg.LastF),
         PostDominatedByUnreachable(std::move(Arg.PostDominatedByUnreachable)),
         PostDominatedByColdCall(std::move(Arg.PostDominatedByColdCall)) {}
 
   BranchProbabilityInfo &operator=(BranchProbabilityInfo &&RHS) {
public:
   void setEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors,
                           BranchProbability Prob);
 
   static BranchProbability getBranchProbStackProtector(bool IsLikely) {
     static const BranchProbability LikelyProb((1u << 20) - 1, 1u << 20);
     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);
 
 private:
   void operator=(const BranchProbabilityInfo &) = delete;
   BranchProbabilityInfo(const BranchProbabilityInfo &) = delete;
 
private:
 
   void updatePostDominatedByUnreachable(const BasicBlock *BB);
   void updatePostDominatedByColdCall(const BasicBlock *BB);
   bool calcUnreachableHeuristics(const BasicBlock *BB);
   bool calcMetadataWeights(const BasicBlock *BB);
   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);
 };
 
 /// \brief Analysis pass which computes \c BranchProbabilityInfo.
 class BranchProbabilityAnalysis
     : public AnalysisInfoMixin<BranchProbabilityAnalysis> {
   friend AnalysisInfoMixin<BranchProbabilityAnalysis>;

llvm/trunk/include/llvm/Analysis/LazyBranchProbabilityInfo.h

 
 #include "llvm/Analysis/BranchProbabilityInfo.h"
 #include "llvm/Pass.h"
 
 namespace llvm {
 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
 /// branch probabilities are not computed when the analysis pass is executed but
 /// rather when the BPI results is explicitly requested by the analysis client.
 ///
 /// There are some additional requirements for any client pass that wants to use
 /// the analysis:

 class LazyBranchProbabilityInfoPass : public FunctionPass {
 
   /// Wraps a BPI to allow lazy computation of the branch probabilities.
   ///
   /// A pass that only conditionally uses BPI can uncondtionally require the
   /// 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;
     }
 
     const BranchProbabilityInfo &getCalculated() const {
       return const_cast<LazyBranchProbabilityInfo *>(this)->getCalculated();
     }
 
   private:
     BranchProbabilityInfo BPI;
     bool Calculated;
     const Function *F;
     const LoopInfo *LI;
+    const TargetLibraryInfo *TLI;
   };
 
   std::unique_ptr<LazyBranchProbabilityInfo> LBPI;
 
 public:
   static char ID;
 
   LazyBranchProbabilityInfoPass();

llvm/trunk/lib/Analysis/BranchProbabilityInfo.cpp

 //===-- BranchProbabilityInfo.cpp - Branch Probability Analysis -----------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // Loops should be simplified before this analysis.
 //
 //===----------------------------------------------------------------------===//
 
 #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"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "branch-prob"
 
 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)
 
 char BranchProbabilityInfoWrapperPass::ID = 0;
 
 // Weights are for internal use only. They are used by heuristics to help to
 // estimate edges' probability. Example:
 //
if (uint32_t numExitingEdges = ExitingEdges.size()) {
     auto Prob = Probs[2] / numExitingEdges;
     for (unsigned SuccIdx : ExitingEdges)
       setEdgeProbability(BB, SuccIdx, Prob);
   }
 
   return true;
 }
 
-bool BranchProbabilityInfo::calcZeroHeuristics(const BasicBlock *BB) {
+bool BranchProbabilityInfo::calcZeroHeuristics(const BasicBlock *BB,
+                                               const TargetLibraryInfo *TLI) {
   const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
   if (!BI || !BI->isConditional())
     return false;
 
   Value *Cond = BI->getCondition();
   ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
   if (!CI)
     return false;
 
   Value *RHS = CI->getOperand(1);
   ConstantInt *CV = dyn_cast<ConstantInt>(RHS);
   if (!CV)
     return false;
 
   // If the LHS is the result of AND'ing a value with a single bit bitmask,
   // we don't have information about probabilities.
   if (Instruction *LHS = dyn_cast<Instruction>(CI->getOperand(0)))
     if (LHS->getOpcode() == Instruction::And)
       if (ConstantInt *AndRHS = dyn_cast<ConstantInt>(LHS->getOperand(1)))
         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<CallInst>(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
       isProb = false;
       break;
     case CmpInst::ICMP_NE:
       // X != 0   ->  Likely
       isProb = true;

 void BranchProbabilityInfo::eraseBlock(const BasicBlock *BB) {
   for (auto I = Probs.begin(), E = Probs.end(); I != E; ++I) {
     auto Key = I->first;
     if (Key.first == BB)
       Probs.erase(Key);
   }
 }
 
-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.
   assert(PostDominatedByUnreachable.empty());
   assert(PostDominatedByColdCall.empty());
 
   // Walk the basic blocks in post-order so that we can build up state about
   // the successors of a block iteratively.
for (auto BB : post_order(&F.getEntryBlock())) {
     if (calcUnreachableHeuristics(BB))
       continue;
     if (calcColdCallHeuristics(BB))
       continue;
     if (calcLoopBranchHeuristics(BB, LI))
       continue;
     if (calcPointerHeuristics(BB))
       continue;
-    if (calcZeroHeuristics(BB))
+    if (calcZeroHeuristics(BB, TLI))
       continue;
     if (calcFloatingPointHeuristics(BB))
       continue;
     calcInvokeHeuristics(BB);
   }
 
   PostDominatedByUnreachable.clear();
   PostDominatedByColdCall.clear();
 }
 
 void BranchProbabilityInfoWrapperPass::getAnalysisUsage(
     AnalysisUsage &AU) const {
   AU.addRequired<LoopInfoWrapperPass>();
+  AU.addRequired<TargetLibraryInfoWrapperPass>();
   AU.setPreservesAll();
 }
 
 bool BranchProbabilityInfoWrapperPass::runOnFunction(Function &F) {
   const LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
-  BPI.calculate(F, LI);
+  const TargetLibraryInfo &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
+  BPI.calculate(F, LI, &TLI);
   return false;
 }
 
 void BranchProbabilityInfoWrapperPass::releaseMemory() { BPI.releaseMemory(); }
 
 void BranchProbabilityInfoWrapperPass::print(raw_ostream &OS,
                                              const Module *) const {
   BPI.print(OS);
 }
 
 AnalysisKey BranchProbabilityAnalysis::Key;
 BranchProbabilityInfo
 BranchProbabilityAnalysis::run(Function &F, FunctionAnalysisManager &AM) {
   BranchProbabilityInfo BPI;
-  BPI.calculate(F, AM.getResult<LoopAnalysis>(F));
+  BPI.calculate(F, AM.getResult<LoopAnalysis>(F), &AM.getResult<TargetLibraryAnalysis>(F));
   return BPI;
 }
 
 PreservedAnalyses
 BranchProbabilityPrinterPass::run(Function &F, FunctionAnalysisManager &AM) {
   OS << "Printing analysis results of BPI for function "
      << "'" << F.getName() << "':"
      << "\n";
   AM.getResult<BranchProbabilityAnalysis>(F).print(OS);
   return PreservedAnalyses::all();
 }

llvm/trunk/lib/Analysis/LazyBranchProbabilityInfo.cpp

 // The difference is that with this pass the branch probabilities are not
 // computed when the analysis pass is executed but rather when the BPI results
 // is explicitly requested by the analysis client.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/LazyBranchProbabilityInfo.h"
 #include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "lazy-branch-prob"
 
 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)
 
 char LazyBranchProbabilityInfoPass::ID = 0;
 
 LazyBranchProbabilityInfoPass::LazyBranchProbabilityInfoPass()
     : FunctionPass(ID) {
   initializeLazyBranchProbabilityInfoPassPass(*PassRegistry::getPassRegistry());
 }
 
 void LazyBranchProbabilityInfoPass::print(raw_ostream &OS,
                                           const Module *) const {
   LBPI->getCalculated().print(OS);
 }
 
 void LazyBranchProbabilityInfoPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<LoopInfoWrapperPass>();
+  AU.addRequired<TargetLibraryInfoWrapperPass>();
   AU.setPreservesAll();
 }
 
 void LazyBranchProbabilityInfoPass::releaseMemory() { LBPI.reset(); }
 
 bool LazyBranchProbabilityInfoPass::runOnFunction(Function &F) {
   LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
-  LBPI = llvm::make_unique<LazyBranchProbabilityInfo>(&F, &LI);
+  TargetLibraryInfo &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
+  LBPI = llvm::make_unique<LazyBranchProbabilityInfo>(&F, &LI, &TLI);
   return false;
 }
 
 void LazyBranchProbabilityInfoPass::getLazyBPIAnalysisUsage(AnalysisUsage &AU) {
   AU.addRequired<LazyBranchProbabilityInfoPass>();
   AU.addRequired<LoopInfoWrapperPass>();
+  AU.addRequired<TargetLibraryInfoWrapperPass>();
 }
 
 void llvm::initializeLazyBPIPassPass(PassRegistry &Registry) {
   INITIALIZE_PASS_DEPENDENCY(LazyBranchProbabilityInfoPass);
   INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
+  INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass);
 }

llvm/trunk/lib/Transforms/Scalar/JumpThreading.cpp

bool JumpThreading::runOnFunction(Function &F) {
   auto TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
   auto LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI();
   auto AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
   std::unique_ptr<BlockFrequencyInfo> BFI;
   std::unique_ptr<BranchProbabilityInfo> BPI;
   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));
   }
 
   return Impl.runImpl(F, TLI, LVI, AA, HasProfileData, std::move(BFI),
                       std::move(BPI));
 }
 
 PreservedAnalyses JumpThreadingPass::run(Function &F,
                                          FunctionAnalysisManager &AM) {
 
   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
   auto &LVI = AM.getResult<LazyValueAnalysis>(F);
   auto &AA = AM.getResult<AAManager>(F);
 
   std::unique_ptr<BlockFrequencyInfo> BFI;
   std::unique_ptr<BranchProbabilityInfo> BPI;
   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));
   }
 
   bool Changed = runImpl(F, &TLI, &LVI, &AA, HasProfileData, std::move(BFI),
                          std::move(BPI));
 
   if (!Changed)
     return PreservedAnalyses::all();

llvm/trunk/test/Analysis/BranchProbabilityInfo/libfunc_call.ll

+; RUN: opt < %s -analyze -branch-prob | FileCheck %s
+; RUN: opt < %s -analyze -lazy-branch-prob | FileCheck %s
+; RUN: opt < %s -passes='print<branch-prob>' -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
+}