diff --git a/llvm/lib/Analysis/BranchProbabilityInfo.cpp b/llvm/lib/Analysis/BranchProbabilityInfo.cpp --- a/llvm/lib/Analysis/BranchProbabilityInfo.cpp +++ b/llvm/lib/Analysis/BranchProbabilityInfo.cpp @@ -104,12 +104,67 @@ /// All reachable probability will proportionally share the remaining part. static const BranchProbability UR_TAKEN_PROB = BranchProbability::getRaw(1); +/// Heuristics and lookup tables for non-loop branches: +/// Pointer Heuristics (PH) static const uint32_t PH_TAKEN_WEIGHT = 20; static const uint32_t PH_NONTAKEN_WEIGHT = 12; +static const BranchProbability + PtrTakenProb(PH_TAKEN_WEIGHT, PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT); +static const BranchProbability + PtrUntakenProb(PH_NONTAKEN_WEIGHT, PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT); + +using ProbabilityList = SmallVector; +using ProbabilityTable = std::map; + +/// Pointer comparisons: +static const ProbabilityTable PointerTable{ + {ICmpInst::ICMP_NE, {PtrTakenProb, PtrUntakenProb}}, /// p != q -> Likely + {ICmpInst::ICMP_EQ, {PtrUntakenProb, PtrTakenProb}}, /// p == q -> Unlikely +}; +/// Zero Heuristics (ZH) static const uint32_t ZH_TAKEN_WEIGHT = 20; static const uint32_t ZH_NONTAKEN_WEIGHT = 12; +static const BranchProbability + ZeroTakenProb(ZH_TAKEN_WEIGHT, ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT); +static const BranchProbability + ZeroUntakenProb(ZH_NONTAKEN_WEIGHT, ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT); + +/// Integer compares with 0: +static const ProbabilityTable ICmpWithZeroTable{ + {CmpInst::ICMP_EQ, {ZeroUntakenProb, ZeroTakenProb}}, /// X == 0 -> Unlikely + {CmpInst::ICMP_NE, {ZeroTakenProb, ZeroUntakenProb}}, /// X != 0 -> Likely + {CmpInst::ICMP_SLT, {ZeroUntakenProb, ZeroTakenProb}}, /// X < 0 -> Unlikely + {CmpInst::ICMP_SGT, {ZeroTakenProb, ZeroUntakenProb}}, /// X > 0 -> Likely +}; + +/// Integer compares with -1: +static const ProbabilityTable ICmpWithMinusOneTable{ + {CmpInst::ICMP_EQ, {ZeroUntakenProb, ZeroTakenProb}}, /// X == -1 -> Unlikely + {CmpInst::ICMP_NE, {ZeroTakenProb, ZeroUntakenProb}}, /// X != -1 -> Likely + // InstCombine canonicalizes X >= 0 into X > -1 + {CmpInst::ICMP_SGT, {ZeroTakenProb, ZeroUntakenProb}}, /// X >= 0 -> Likely +}; + +/// Integer compares with 1: +static const ProbabilityTable ICmpWithOneTable{ + // InstCombine canonicalizes X <= 0 into X < 1 + {CmpInst::ICMP_SLT, {ZeroUntakenProb, ZeroTakenProb}}, /// X <= 0 -> Unlikely +}; + +/// 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. +static const ProbabilityTable ICmpWithLibCallTable{ + {CmpInst::ICMP_EQ, {ZeroUntakenProb, ZeroTakenProb}}, + {CmpInst::ICMP_NE, {ZeroTakenProb, ZeroUntakenProb}}, +}; +// Floating-Point Heuristics (FPH) static const uint32_t FPH_TAKEN_WEIGHT = 20; static const uint32_t FPH_NONTAKEN_WEIGHT = 12; @@ -120,6 +175,21 @@ /// exceptional case, so the result is unlikely. static const uint32_t FPH_UNO_WEIGHT = 1; +static const BranchProbability FPOrdTakenProb(FPH_ORD_WEIGHT, + FPH_ORD_WEIGHT + FPH_UNO_WEIGHT); +static const BranchProbability + FPOrdUntakenProb(FPH_UNO_WEIGHT, FPH_ORD_WEIGHT + FPH_UNO_WEIGHT); +static const BranchProbability + FPTakenProb(FPH_TAKEN_WEIGHT, FPH_TAKEN_WEIGHT + FPH_NONTAKEN_WEIGHT); +static const BranchProbability + FPUntakenProb(FPH_NONTAKEN_WEIGHT, FPH_TAKEN_WEIGHT + FPH_NONTAKEN_WEIGHT); + +/// Floating-Point compares: +static const ProbabilityTable FCmpTable{ + {FCmpInst::FCMP_ORD, {FPOrdTakenProb, FPOrdUntakenProb}}, /// !isnan -> Likely + {FCmpInst::FCMP_UNO, {FPOrdUntakenProb, FPOrdTakenProb}}, /// isnan -> Unlikely +}; + /// Set of dedicated "absolute" execution weights for a block. These weights are /// meaningful relative to each other and their derivatives only. enum class BlockExecWeight : std::uint32_t { @@ -468,21 +538,10 @@ assert(CI->getOperand(1)->getType()->isPointerTy()); - BranchProbability TakenProb(PH_TAKEN_WEIGHT, - PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT); - BranchProbability UntakenProb(PH_NONTAKEN_WEIGHT, - PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT); - - // p != 0 -> isProb = true - // p == 0 -> isProb = false - // p != q -> isProb = true - // p == q -> isProb = false; - bool isProb = CI->getPredicate() == ICmpInst::ICMP_NE; - if (!isProb) - std::swap(TakenProb, UntakenProb); - - setEdgeProbability( - BB, SmallVector({TakenProb, UntakenProb})); + auto Search = PointerTable.find(CI->getPredicate()); + if (Search == PointerTable.end()) + return false; + setEdgeProbability(BB, Search->second); return true; } @@ -949,86 +1008,33 @@ if (Function *CalledFn = Call->getCalledFunction()) TLI->getLibFunc(*CalledFn, Func); - bool isProb; + ProbabilityTable::const_iterator Search; if (Func == LibFunc_strcasecmp || Func == LibFunc_strcmp || Func == LibFunc_strncasecmp || Func == LibFunc_strncmp || Func == LibFunc_memcmp || Func == LibFunc_bcmp) { - // 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: + Search = ICmpWithLibCallTable.find(CI->getPredicate()); + if (Search == ICmpWithLibCallTable.end()) 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; - break; - case CmpInst::ICMP_SLT: - // X < 0 -> Unlikely - isProb = false; - break; - case CmpInst::ICMP_SGT: - // X > 0 -> Likely - isProb = true; - break; - default: + Search = ICmpWithZeroTable.find(CI->getPredicate()); + if (Search == ICmpWithZeroTable.end()) + return false; + } else if (CV->isOne()) { + Search = ICmpWithOneTable.find(CI->getPredicate()); + if (Search == ICmpWithOneTable.end()) return false; - } - } else if (CV->isOne() && CI->getPredicate() == CmpInst::ICMP_SLT) { - // InstCombine canonicalizes X <= 0 into X < 1. - // X <= 0 -> Unlikely - isProb = false; } else if (CV->isMinusOne()) { - 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: + Search = ICmpWithMinusOneTable.find(CI->getPredicate()); + if (Search == ICmpWithMinusOneTable.end()) return false; - } } else { return false; } - BranchProbability TakenProb(ZH_TAKEN_WEIGHT, - ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT); - BranchProbability UntakenProb(ZH_NONTAKEN_WEIGHT, - ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT); - if (!isProb) - std::swap(TakenProb, UntakenProb); - - setEdgeProbability( - BB, SmallVector({TakenProb, UntakenProb})); + setEdgeProbability(BB, Search->second); return true; } @@ -1042,34 +1048,21 @@ if (!FCmp) return false; - uint32_t TakenWeight = FPH_TAKEN_WEIGHT; - uint32_t NontakenWeight = FPH_NONTAKEN_WEIGHT; - bool isProb; + ProbabilityList ProbList; if (FCmp->isEquality()) { - // f1 == f2 -> Unlikely - // f1 != f2 -> Likely - isProb = !FCmp->isTrueWhenEqual(); - } else if (FCmp->getPredicate() == FCmpInst::FCMP_ORD) { - // !isnan -> Likely - isProb = true; - TakenWeight = FPH_ORD_WEIGHT; - NontakenWeight = FPH_UNO_WEIGHT; - } else if (FCmp->getPredicate() == FCmpInst::FCMP_UNO) { - // isnan -> Unlikely - isProb = false; - TakenWeight = FPH_ORD_WEIGHT; - NontakenWeight = FPH_UNO_WEIGHT; + ProbList = !FCmp->isTrueWhenEqual() ? + // f1 == f2 -> Unlikely + ProbabilityList({FPTakenProb, FPUntakenProb}) : + // f1 != f2 -> Likely + ProbabilityList({FPUntakenProb, FPTakenProb}); } else { - return false; + auto Search = FCmpTable.find(FCmp->getPredicate()); + if (Search == FCmpTable.end()) + return false; + ProbList = Search->second; } - BranchProbability TakenProb(TakenWeight, TakenWeight + NontakenWeight); - BranchProbability UntakenProb(NontakenWeight, TakenWeight + NontakenWeight); - if (!isProb) - std::swap(TakenProb, UntakenProb); - - setEdgeProbability( - BB, SmallVector({TakenProb, UntakenProb})); + setEdgeProbability(BB, ProbList); return true; } diff --git a/llvm/test/Analysis/BranchProbabilityInfo/pointer_heuristics.ll b/llvm/test/Analysis/BranchProbabilityInfo/pointer_heuristics.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Analysis/BranchProbabilityInfo/pointer_heuristics.ll @@ -0,0 +1,70 @@ +; RUN: opt < %s -passes='print' -disable-output 2>&1 | FileCheck %s + +define i32 @cmp1(i32* readnone %0, i32* readnone %1) { +; CHECK: Printing analysis results of BPI for function 'cmp1': + %3 = icmp eq i32* %0, %1 + br i1 %3, label %4, label %6 +; CHECK: edge -> probability is 0x30000000 / 0x80000000 = 37.50% +; CHECK: edge -> probability is 0x50000000 / 0x80000000 = 62.50% + +4: ; preds = %2 + %5 = tail call i32 bitcast (i32 (...)* @f to i32 ()*)() #2 + br label %8 +; CHECK: edge -> probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +6: ; preds = %2 + %7 = tail call i32 bitcast (i32 (...)* @g to i32 ()*)() #2 + br label %8 +; CHECK: edge -> probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +8: ; preds = %6, %4 + %9 = phi i32 [ %5, %4 ], [ %7, %6 ] + ret i32 %9 +} + +define i32 @cmp2(i32* readnone %0, i32* readnone %1) { +; CHECK: Printing analysis results of BPI for function 'cmp2': + %3 = icmp eq i32* %0, %1 + br i1 %3, label %6, label %4 +; CHECK: edge -> probability is 0x30000000 / 0x80000000 = 37.50% +; CHECK: edge -> probability is 0x50000000 / 0x80000000 = 62.50% + +4: ; preds = %2 + %5 = tail call i32 bitcast (i32 (...)* @f to i32 ()*)() #2 + br label %8 +; CHECK: edge -> probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +6: ; preds = %2 + %7 = tail call i32 bitcast (i32 (...)* @g to i32 ()*)() #2 + br label %8 +; CHECK: edge -> probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +8: ; preds = %6, %4 + %9 = phi i32 [ %5, %4 ], [ %7, %6 ] + ret i32 %9 +} + +; CHECK: Printing analysis results of BPI for function 'cmp3': +define i32 @cmp3(i32* readnone %0) { + %2 = icmp eq i32* %0, null + br i1 %2, label %3, label %5 +; CHECK: edge -> probability is 0x30000000 / 0x80000000 = 37.50% +; CHECK: edge -> probability is 0x50000000 / 0x80000000 = 62.50% + +3: ; preds = %1 + %4 = tail call i32 bitcast (i32 (...)* @f to i32 ()*)() #2 + br label %7 +; CHECK: edge -> probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +5: ; preds = %1 + %6 = tail call i32 bitcast (i32 (...)* @g to i32 ()*)() #2 + br label %7 +; CHECK: edge -> probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] + +7: ; preds = %5, %3 + %8 = phi i32 [ %6, %5 ], [ %4, %3 ] + ret i32 %8 +} + +declare dso_local i32 @f(...) local_unnamed_addr #1 +declare dso_local i32 @g(...) local_unnamed_addr #1