Author: Mark de Wever Date: 2020-10-04T14:24:27+02:00 New Revision: 1113fbf44c2250621548e278d2a1e11ab2b2d63d
URL: https://github.com/llvm/llvm-project/commit/1113fbf44c2250621548e278d2a1e11ab2b2d63d DIFF: https://github.com/llvm/llvm-project/commit/1113fbf44c2250621548e278d2a1e11ab2b2d63d.diff LOG: [CodeGen] Improve likelihood branch weights Bruno De Fraine discovered some issues with D85091. The branch weights generated for `logical not` and `ternary conditional` were wrong. The `logical and` and `logical or` differed from the code generated of `__builtin_predict`. Adjusted the generated code for the likelihood to match `__builtin_predict`. The patch is based on Bruno's suggestions. Differential Revision: https://reviews.llvm.org/D88363 Added: clang/test/CodeGenCXX/attr-likelihood-if-vs-builtin-expect.cpp Modified: clang/lib/CodeGen/CGStmt.cpp clang/lib/CodeGen/CodeGenFunction.cpp clang/lib/CodeGen/CodeGenFunction.h Removed: ################################################################################ diff --git a/clang/lib/CodeGen/CGStmt.cpp b/clang/lib/CodeGen/CGStmt.cpp index 83dd1be31633..c9e6ce2df2c0 100644 --- a/clang/lib/CodeGen/CGStmt.cpp +++ b/clang/lib/CodeGen/CGStmt.cpp @@ -27,7 +27,6 @@ #include "llvm/IR/Intrinsics.h" #include "llvm/IR/MDBuilder.h" #include "llvm/Support/SaveAndRestore.h" -#include "llvm/Transforms/Scalar/LowerExpectIntrinsic.h" using namespace clang; using namespace CodeGen; @@ -652,20 +651,6 @@ void CodeGenFunction::EmitIndirectGotoStmt(const IndirectGotoStmt &S) { EmitBranch(IndGotoBB); } -static Optional<std::pair<uint32_t, uint32_t>> -getLikelihoodWeights(const IfStmt &If) { - switch (Stmt::getLikelihood(If.getThen(), If.getElse())) { - case Stmt::LH_Unlikely: - return std::pair<uint32_t, uint32_t>(llvm::UnlikelyBranchWeight, - llvm::LikelyBranchWeight); - case Stmt::LH_None: - return None; - case Stmt::LH_Likely: - return std::pair<uint32_t, uint32_t>(llvm::LikelyBranchWeight, - llvm::UnlikelyBranchWeight); - } - llvm_unreachable("Unknown Likelihood"); -} void CodeGenFunction::EmitIfStmt(const IfStmt &S) { // C99 6.8.4.1: The first substatement is executed if the expression compares @@ -713,17 +698,11 @@ void CodeGenFunction::EmitIfStmt(const IfStmt &S) { // Prefer the PGO based weights over the likelihood attribute. // When the build isn't optimized the metadata isn't used, so don't generate // it. - llvm::MDNode *Weights = nullptr; + Stmt::Likelihood LH = Stmt::LH_None; uint64_t Count = getProfileCount(S.getThen()); - if (!Count && CGM.getCodeGenOpts().OptimizationLevel) { - Optional<std::pair<uint32_t, uint32_t>> LHW = getLikelihoodWeights(S); - if (LHW) { - llvm::MDBuilder MDHelper(CGM.getLLVMContext()); - Weights = MDHelper.createBranchWeights(LHW->first, LHW->second); - } - } - - EmitBranchOnBoolExpr(S.getCond(), ThenBlock, ElseBlock, Count, Weights); + if (!Count && CGM.getCodeGenOpts().OptimizationLevel) + LH = Stmt::getLikelihood(S.getThen(), S.getElse()); + EmitBranchOnBoolExpr(S.getCond(), ThenBlock, ElseBlock, Count, LH); // Emit the 'then' code. EmitBlock(ThenBlock); diff --git a/clang/lib/CodeGen/CodeGenFunction.cpp b/clang/lib/CodeGen/CodeGenFunction.cpp index 47ef5c830723..363b418dc198 100644 --- a/clang/lib/CodeGen/CodeGenFunction.cpp +++ b/clang/lib/CodeGen/CodeGenFunction.cpp @@ -42,6 +42,7 @@ #include "llvm/IR/MDBuilder.h" #include "llvm/IR/Operator.h" #include "llvm/Support/CRC.h" +#include "llvm/Transforms/Scalar/LowerExpectIntrinsic.h" #include "llvm/Transforms/Utils/PromoteMemToReg.h" using namespace clang; using namespace CodeGen; @@ -1477,15 +1478,30 @@ bool CodeGenFunction::ConstantFoldsToSimpleInteger(const Expr *Cond, return true; } +static Optional<std::pair<uint32_t, uint32_t>> +getLikelihoodWeights(Stmt::Likelihood LH) { + switch (LH) { + case Stmt::LH_Unlikely: + return std::pair<uint32_t, uint32_t>(llvm::UnlikelyBranchWeight, + llvm::LikelyBranchWeight); + case Stmt::LH_None: + return None; + case Stmt::LH_Likely: + return std::pair<uint32_t, uint32_t>(llvm::LikelyBranchWeight, + llvm::UnlikelyBranchWeight); + } + llvm_unreachable("Unknown Likelihood"); +} + /// EmitBranchOnBoolExpr - Emit a branch on a boolean condition (e.g. for an if /// statement) to the specified blocks. Based on the condition, this might try /// to simplify the codegen of the conditional based on the branch. -/// \param Weights The weights determined by the likelihood attributes. +/// \param LH The value of the likelihood attribute on the True branch. void CodeGenFunction::EmitBranchOnBoolExpr(const Expr *Cond, llvm::BasicBlock *TrueBlock, llvm::BasicBlock *FalseBlock, uint64_t TrueCount, - llvm::MDNode *Weights) { + Stmt::Likelihood LH) { Cond = Cond->IgnoreParens(); if (const BinaryOperator *CondBOp = dyn_cast<BinaryOperator>(Cond)) { @@ -1500,7 +1516,7 @@ void CodeGenFunction::EmitBranchOnBoolExpr(const Expr *Cond, // br(1 && X) -> br(X). incrementProfileCounter(CondBOp); return EmitBranchOnBoolExpr(CondBOp->getRHS(), TrueBlock, FalseBlock, - TrueCount, Weights); + TrueCount, LH); } // If we have "X && 1", simplify the code to use an uncond branch. @@ -1509,7 +1525,7 @@ void CodeGenFunction::EmitBranchOnBoolExpr(const Expr *Cond, ConstantBool) { // br(X && 1) -> br(X). return EmitBranchOnBoolExpr(CondBOp->getLHS(), TrueBlock, FalseBlock, - TrueCount, Weights); + TrueCount, LH); } // Emit the LHS as a conditional. If the LHS conditional is false, we @@ -1522,8 +1538,11 @@ void CodeGenFunction::EmitBranchOnBoolExpr(const Expr *Cond, ConditionalEvaluation eval(*this); { ApplyDebugLocation DL(*this, Cond); + // Propagate the likelihood attribute like __builtin_expect + // __builtin_expect(X && Y, 1) -> X and Y are likely + // __builtin_expect(X && Y, 0) -> only Y is unlikely EmitBranchOnBoolExpr(CondBOp->getLHS(), LHSTrue, FalseBlock, RHSCount, - Weights); + LH == Stmt::LH_Unlikely ? Stmt::LH_None : LH); EmitBlock(LHSTrue); } @@ -1533,7 +1552,7 @@ void CodeGenFunction::EmitBranchOnBoolExpr(const Expr *Cond, // Any temporaries created here are conditional. eval.begin(*this); EmitBranchOnBoolExpr(CondBOp->getRHS(), TrueBlock, FalseBlock, TrueCount, - Weights); + LH); eval.end(*this); return; @@ -1548,7 +1567,7 @@ void CodeGenFunction::EmitBranchOnBoolExpr(const Expr *Cond, // br(0 || X) -> br(X). incrementProfileCounter(CondBOp); return EmitBranchOnBoolExpr(CondBOp->getRHS(), TrueBlock, FalseBlock, - TrueCount, Weights); + TrueCount, LH); } // If we have "X || 0", simplify the code to use an uncond branch. @@ -1557,7 +1576,7 @@ void CodeGenFunction::EmitBranchOnBoolExpr(const Expr *Cond, !ConstantBool) { // br(X || 0) -> br(X). return EmitBranchOnBoolExpr(CondBOp->getLHS(), TrueBlock, FalseBlock, - TrueCount, Weights); + TrueCount, LH); } // Emit the LHS as a conditional. If the LHS conditional is true, we @@ -1572,9 +1591,12 @@ void CodeGenFunction::EmitBranchOnBoolExpr(const Expr *Cond, ConditionalEvaluation eval(*this); { + // Propagate the likelihood attribute like __builtin_expect + // __builtin_expect(X || Y, 1) -> only Y is likely + // __builtin_expect(X || Y, 0) -> both X and Y are unlikely ApplyDebugLocation DL(*this, Cond); EmitBranchOnBoolExpr(CondBOp->getLHS(), TrueBlock, LHSFalse, LHSCount, - Weights); + LH == Stmt::LH_Likely ? Stmt::LH_None : LH); EmitBlock(LHSFalse); } @@ -1584,7 +1606,7 @@ void CodeGenFunction::EmitBranchOnBoolExpr(const Expr *Cond, // Any temporaries created here are conditional. eval.begin(*this); EmitBranchOnBoolExpr(CondBOp->getRHS(), TrueBlock, FalseBlock, RHSCount, - Weights); + LH); eval.end(*this); @@ -1597,9 +1619,11 @@ void CodeGenFunction::EmitBranchOnBoolExpr(const Expr *Cond, if (CondUOp->getOpcode() == UO_LNot) { // Negate the count. uint64_t FalseCount = getCurrentProfileCount() - TrueCount; + // The values of the enum are chosen to make this negation possible. + LH = static_cast<Stmt::Likelihood>(-LH); // Negate the condition and swap the destination blocks. return EmitBranchOnBoolExpr(CondUOp->getSubExpr(), FalseBlock, TrueBlock, - FalseCount, Weights); + FalseCount, LH); } } @@ -1608,9 +1632,11 @@ void CodeGenFunction::EmitBranchOnBoolExpr(const Expr *Cond, llvm::BasicBlock *LHSBlock = createBasicBlock("cond.true"); llvm::BasicBlock *RHSBlock = createBasicBlock("cond.false"); + // The ConditionalOperator itself has no likelihood information for its + // true and false branches. This matches the behavior of __builtin_expect. ConditionalEvaluation cond(*this); EmitBranchOnBoolExpr(CondOp->getCond(), LHSBlock, RHSBlock, - getProfileCount(CondOp), Weights); + getProfileCount(CondOp), Stmt::LH_None); // When computing PGO branch weights, we only know the overall count for // the true block. This code is essentially doing tail duplication of the @@ -1630,14 +1656,14 @@ void CodeGenFunction::EmitBranchOnBoolExpr(const Expr *Cond, { ApplyDebugLocation DL(*this, Cond); EmitBranchOnBoolExpr(CondOp->getLHS(), TrueBlock, FalseBlock, - LHSScaledTrueCount, Weights); + LHSScaledTrueCount, LH); } cond.end(*this); cond.begin(*this); EmitBlock(RHSBlock); EmitBranchOnBoolExpr(CondOp->getRHS(), TrueBlock, FalseBlock, - TrueCount - LHSScaledTrueCount, Weights); + TrueCount - LHSScaledTrueCount, LH); cond.end(*this); return; @@ -1666,8 +1692,12 @@ void CodeGenFunction::EmitBranchOnBoolExpr(const Expr *Cond, } } - // Create branch weights based on the number of times we get here and the - // number of times the condition should be true. + llvm::MDNode *Weights = nullptr; + Optional<std::pair<uint32_t, uint32_t>> LHW = getLikelihoodWeights(LH); + if (LHW) { + llvm::MDBuilder MDHelper(CGM.getLLVMContext()); + Weights = MDHelper.createBranchWeights(LHW->first, LHW->second); + } if (!Weights) { uint64_t CurrentCount = std::max(getCurrentProfileCount(), TrueCount); Weights = createProfileWeights(TrueCount, CurrentCount - TrueCount); diff --git a/clang/lib/CodeGen/CodeGenFunction.h b/clang/lib/CodeGen/CodeGenFunction.h index 16656de4e8f7..a9fb47864700 100644 --- a/clang/lib/CodeGen/CodeGenFunction.h +++ b/clang/lib/CodeGen/CodeGenFunction.h @@ -4365,7 +4365,7 @@ class CodeGenFunction : public CodeGenTypeCache { /// evaluate to true based on PGO data. void EmitBranchOnBoolExpr(const Expr *Cond, llvm::BasicBlock *TrueBlock, llvm::BasicBlock *FalseBlock, uint64_t TrueCount, - llvm::MDNode *Weights = nullptr); + Stmt::Likelihood LH = Stmt::LH_None); /// Given an assignment `*LHS = RHS`, emit a test that checks if \p RHS is /// nonnull, if \p LHS is marked _Nonnull. diff --git a/clang/test/CodeGenCXX/attr-likelihood-if-vs-builtin-expect.cpp b/clang/test/CodeGenCXX/attr-likelihood-if-vs-builtin-expect.cpp new file mode 100644 index 000000000000..5e73cd096742 --- /dev/null +++ b/clang/test/CodeGenCXX/attr-likelihood-if-vs-builtin-expect.cpp @@ -0,0 +1,223 @@ +// RUN: %clang_cc1 -O1 -emit-llvm %s -o - -triple=x86_64-linux-gnu | FileCheck %s + +// Verifies the output of __builtin_expect versus the output of the likelihood +// attributes. They should generate the same probabilities for the branches. + +extern bool a(); +extern bool b(); +extern bool c(); + +void ab1(int &i) { + // CHECK-LABEL: define{{.*}}ab1 + // CHECK: br {{.*}} !prof !2 + // CHECK: br {{.*}} !prof !2 + // CHECK: br {{.*}} !prof !2 + if (__builtin_expect(a() && b() && a(), 1)) { + ++i; + } else { + --i; + } +} + +void al(int &i) { + // CHECK-LABEL: define{{.*}}al + // CHECK: br {{.*}} !prof !2 + // CHECK: br {{.*}} !prof !2 + // CHECK: br {{.*}} !prof !2 + if (a() && b() && c()) [[likely]] { + ++i; + } else { + --i; + } +} + +void ab0(int &i) { + // CHECK-LABEL: define{{.*}}ab0 + // CHECK: br {{.*}}else{{$}} + // CHECK: br {{.*}}else{{$}} + // CHECK: br {{.*}} !prof !8 + if (__builtin_expect(a() && b() && c(), 0)) { + ++i; + } else { + --i; + } +} + +void au(int &i) { + // CHECK-LABEL: define{{.*}}au + // CHECK: br {{.*}}else{{$}} + // CHECK: br {{.*}}else{{$}} + // CHECK: br {{.*}} !prof !8 + if (a() && b() && c()) [[unlikely]] { + ++i; + } else { + --i; + } +} + +void ob1(int &i) { + // CHECK-LABEL: define{{.*}}ob1 + // CHECK: br {{.*}}false{{$}} + // CHECK: br {{.*}}rhs{{$}} + // CHECK: br {{.*}} !prof !2 + if (__builtin_expect(a() || b() || a(), 1)) { + i = 0; + } else { + --i; + } +} + +void ol(int &i) { + // CHECK-LABEL: define{{.*}}ol + // CHECK: br {{.*}}false{{$}} + // CHECK: br {{.*}}false2{{$}} + // CHECK: br {{.*}} !prof !2 + if (a() || b() || c()) [[likely]] { + i = 0; + } else { + --i; + } +} + +void ob0(int &i) { + // CHECK-LABEL: define{{.*}}ob0 + // CHECK: br {{.*}} !prof !8 + // CHECK: br {{.*}} !prof !8 + // CHECK: br {{.*}} !prof !8 + if (__builtin_expect(a() || b() || c(), 0)) { + i = 0; + } else { + --i; + } +} + +void ou(int &i) { + // CHECK-LABEL: define{{.*}}ou + // CHECK: br {{.*}} !prof !8 + // CHECK: br {{.*}} !prof !8 + // CHECK: br {{.*}} !prof !8 + if (a() || b() || c()) [[unlikely]] { + i = 0; + } else { + --i; + } +} + +void nb1(int &i) { + // CHECK-LABEL: define{{.*}}nb1 + // CHECK: storemerge{{.*}} !prof !8 + if (__builtin_expect(!a(), 1)) { + ++i; + } else { + --i; + } +} + +void nl(int &i) { + // CHECK-LABEL: define{{.*}}nl + // CHECK: storemerge{{.*}} !prof !8 + if (!a()) [[likely]] { + ++i; + } else { + --i; + } +} + +void nb0(int &i) { + // CHECK-LABEL: define{{.*}}nb0 + // CHECK: storemerge{{.*}} !prof !2 + if (__builtin_expect(!a(), 0)) { + ++i; + } else { + --i; + } +} + +void nu(int &i) { + // CHECK-LABEL: define{{.*}}nu + // CHECK: storemerge{{.*}} !prof !2 + if (!a()) [[unlikely]] { + ++i; + } else { + --i; + } +} + +void tb1(int &i) { + // CHECK-LABEL: define{{.*}}tb1 + // CHECK: br {{.*}}false{{$}} + // CHECK: br {{.*}}end{{$}} + // CHECK: br {{.*}}end{{$}} + // CHECK: storemerge{{.*}} !prof !2 + if (__builtin_expect(a() ? b() : c(), 1)) { + ++i; + } else { + --i; + } +} + +void tl(int &i) { + // CHECK-LABEL: define{{.*}}tl + // CHECK: br {{.*}}false{{$}} + // CHECK: br {{.*}}end{{$}} + // CHECK: br {{.*}}end{{$}} + // CHECK: storemerge{{.*}} !prof !2 + if (bool d = a() ? b() : c()) [[likely]] { + ++i; + } else { + --i; + } +} + +void tl2(int &i) { + // CHECK-LABEL: define{{.*}}tl + // CHECK: br {{.*}}false{{$}} + // CHECK: br {{.*}} !prof !2 + // CHECK: br {{.*}} !prof !2 + if (a() ? b() : c()) [[likely]] { + ++i; + } else { + --i; + } +} + +void tb0(int &i) { + // CHECK-LABEL: define{{.*}}tb0 + // CHECK: br {{.*}}false{{$}} + // CHECK: br {{.*}}end{{$}} + // CHECK: br {{.*}}end{{$}} + // CHECK: storemerge{{.*}} !prof !8 + if (__builtin_expect(a() ? b() : c(), 0)) { + ++i; + } else { + --i; + } +} + +void tu(int &i) { + // CHECK-LABEL: define{{.*}}tu + // CHECK: br {{.*}}false{{$}} + // CHECK: br {{.*}}end{{$}} + // CHECK: br {{.*}}end{{$}} + // CHECK: storemerge{{.*}} !prof !8 + if (bool d = a() ? b() : c()) [[unlikely]] { + ++i; + } else { + --i; + } +} + +void tu2(int &i) { + // CHECK-LABEL: define{{.*}}tu + // CHECK: br {{.*}}false{{$}} + // CHECK: br {{.*}} !prof !8 + // CHECK: br {{.*}} !prof !8 + if (a() ? b() : c()) [[unlikely]] { + ++i; + } else { + --i; + } +} + +// CHECK: !2 = !{!"branch_weights", i32 2000, i32 1} +// CHECK: !8 = !{!"branch_weights", i32 1, i32 2000} _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
