Index: clang/include/clang/AST/Stmt.h =================================================================== --- clang/include/clang/AST/Stmt.h +++ clang/include/clang/AST/Stmt.h @@ -1177,6 +1177,9 @@ static void EnableStatistics(); static void PrintStats(); + /// \returns the likelihood of a set of attributes. + static Likelihood getLikelihood(ArrayRef Attrs); + /// \returns the likelihood of a statement. static Likelihood getLikelihood(const Stmt *S); Index: clang/include/clang/Basic/Attr.td =================================================================== --- clang/include/clang/Basic/Attr.td +++ clang/include/clang/Basic/Attr.td @@ -1290,14 +1290,12 @@ } def Likely : StmtAttr { - // FIXME: Change the date to 201803 once the implementation is finished. - let Spellings = [CXX11<"", "likely", 2>, C2x<"clang", "likely">]; + let Spellings = [CXX11<"", "likely", 201803>, C2x<"clang", "likely">]; let Documentation = [LikelihoodDocs]; } def Unlikely : StmtAttr { - // FIXME: Change the date to 201803 once the implementation is finished. - let Spellings = [CXX11<"", "unlikely", 2>, C2x<"clang", "unlikely">]; + let Spellings = [CXX11<"", "unlikely", 201803>, C2x<"clang", "unlikely">]; let Documentation = [LikelihoodDocs]; } Index: clang/include/clang/Basic/AttrDocs.td =================================================================== --- clang/include/clang/Basic/AttrDocs.td +++ clang/include/clang/Basic/AttrDocs.td @@ -1724,13 +1724,23 @@ statement with the same likelihood attribute will result in a diagnostic and the attributes are ignored on both branches. +In a ``switch`` statement it's allowed to annotate multiple ``case`` labels +with the same likelihood attribute. This makes +* all values with the ``likely`` attribute equally likely, +* all values with the ``unlikely`` attribute equally unlikely, +* all values without an attribute equally likely. +When a ``case`` has no likelihood attribute it is more likely to be the path of +execution than a ``case`` with the ``unlikely`` attribute and it is less likely +to be the path of execution than a ``case`` with the ``likely`` attribute. + These attributes have no effect on the generated code when using PGO (Profile-Guided Optimization) or at optimization level 0. -In Clang, the attributes will be ignored if they're not placed on the -substatement of an ``if`` or ``else`` statement. The C++ Standard recommends -to honor them on every statement in the path of execution, but that can be -confusing: +In Clang, the attributes will be ignored if they're not placed on +* the case labels of a switch statement, +* or on the substatement of an ``if`` or ``else`` statement. +The C++ Standard recommends to honor them on every statement in the +path of execution, but that can be confusing: .. code-block:: c++ @@ -1759,8 +1769,8 @@ } -At the moment the attribute only has effect when used in an ``if`` or ``else`` -statement. +At the moment the attributes only have effect when used in an ``if``, ``else``, +or ``switch`` statement. .. code-block:: c++ @@ -1802,6 +1812,29 @@ [[likely]] int i = 5; // Issues a diagnostic since the attribute // isn't allowed on a declaration. + switch(i) { + [[likely]] case 1: // This value is likely + ... + break; + + [[unlikely]] case 2: // This value is unlikely + ... + [[fallthrough]]; + + case 3: // No likelihood attribute + ... + [[likely]] break; // No effect + + case 4: [[likely]] { // attribute on substatement has no effect + ... + break; + } + + [[unlikely]] default: // All other values are unlikely + ... + break; + } + }]; } Index: clang/lib/AST/Stmt.cpp =================================================================== --- clang/lib/AST/Stmt.cpp +++ clang/lib/AST/Stmt.cpp @@ -130,19 +130,30 @@ StatisticsEnabled = true; } +static std::pair +getLikelihood(ArrayRef Attrs) { + for (const auto *A : Attrs) { + if (isa(A)) + return std::make_pair(Stmt::LH_Likely, A); + + if (isa(A)) + return std::make_pair(Stmt::LH_Unlikely, A); + } + + return std::make_pair(Stmt::LH_None, nullptr); +} + static std::pair getLikelihood(const Stmt *S) { if (const auto *AS = dyn_cast_or_null(S)) - for (const auto *A : AS->getAttrs()) { - if (isa(A)) - return std::make_pair(Stmt::LH_Likely, A); - - if (isa(A)) - return std::make_pair(Stmt::LH_Unlikely, A); - } + return getLikelihood(AS->getAttrs()); return std::make_pair(Stmt::LH_None, nullptr); } +Stmt::Likelihood Stmt::getLikelihood(ArrayRef Attrs) { + return ::getLikelihood(Attrs).first; +} + Stmt::Likelihood Stmt::getLikelihood(const Stmt *S) { return ::getLikelihood(S).first; } Index: clang/lib/CodeGen/CGStmt.cpp =================================================================== --- clang/lib/CodeGen/CGStmt.cpp +++ clang/lib/CodeGen/CGStmt.cpp @@ -50,7 +50,7 @@ PGO.setCurrentStmt(S); // These statements have their own debug info handling. - if (EmitSimpleStmt(S)) + if (EmitSimpleStmt(S, Attrs)) return; // Check if we are generating unreachable code. @@ -370,7 +370,9 @@ } } -bool CodeGenFunction::EmitSimpleStmt(const Stmt *S) { +bool CodeGenFunction::EmitSimpleStmt(const Stmt *S, + ArrayRef Attrs) { + // clang-format off switch (S->getStmtClass()) { default: return false; case Stmt::NullStmtClass: break; @@ -382,11 +384,12 @@ case Stmt::GotoStmtClass: EmitGotoStmt(cast(*S)); break; case Stmt::BreakStmtClass: EmitBreakStmt(cast(*S)); break; case Stmt::ContinueStmtClass: EmitContinueStmt(cast(*S)); break; - case Stmt::DefaultStmtClass: EmitDefaultStmt(cast(*S)); break; - case Stmt::CaseStmtClass: EmitCaseStmt(cast(*S)); break; + case Stmt::DefaultStmtClass: + EmitDefaultStmt(cast(*S), Attrs); break; + case Stmt::CaseStmtClass: EmitCaseStmt(cast(*S), Attrs); break; case Stmt::SEHLeaveStmtClass: EmitSEHLeaveStmt(cast(*S)); break; } - + // clang-format on return true; } @@ -1221,7 +1224,8 @@ /// EmitCaseStmtRange - If case statement range is not too big then /// add multiple cases to switch instruction, one for each value within /// the range. If range is too big then emit "if" condition check. -void CodeGenFunction::EmitCaseStmtRange(const CaseStmt &S) { +void CodeGenFunction::EmitCaseStmtRange(const CaseStmt &S, + ArrayRef Attrs) { assert(S.getRHS() && "Expected RHS value in CaseStmt"); llvm::APSInt LHS = S.getLHS()->EvaluateKnownConstInt(getContext()); @@ -1238,6 +1242,7 @@ if (LHS.isSigned() ? RHS.slt(LHS) : RHS.ult(LHS)) return; + Stmt::Likelihood LH = Stmt::getLikelihood(Attrs); llvm::APInt Range = RHS - LHS; // FIXME: parameters such as this should not be hardcoded. if (Range.ult(llvm::APInt(Range.getBitWidth(), 64))) { @@ -1252,6 +1257,9 @@ for (unsigned I = 0; I != NCases; ++I) { if (SwitchWeights) SwitchWeights->push_back(Weight + (Rem ? 1 : 0)); + else if (SwitchLikelihood) + SwitchLikelihood->push_back(LH); + if (Rem) Rem--; SwitchInsn->addCase(Builder.getInt(LHS), CaseDest); @@ -1289,7 +1297,9 @@ // need to update the weight for the default, ie, the first case, to include // this case. (*SwitchWeights)[0] += ThisCount; - } + } else if (SwitchLikelihood) + Weights = createBranchWeights(LH); + Builder.CreateCondBr(Cond, CaseDest, FalseDest, Weights); // Restore the appropriate insertion point. @@ -1299,7 +1309,8 @@ Builder.ClearInsertionPoint(); } -void CodeGenFunction::EmitCaseStmt(const CaseStmt &S) { +void CodeGenFunction::EmitCaseStmt(const CaseStmt &S, + ArrayRef Attrs) { // If there is no enclosing switch instance that we're aware of, then this // case statement and its block can be elided. This situation only happens // when we've constant-folded the switch, are emitting the constant case, @@ -1312,12 +1323,14 @@ // Handle case ranges. if (S.getRHS()) { - EmitCaseStmtRange(S); + EmitCaseStmtRange(S, Attrs); return; } llvm::ConstantInt *CaseVal = Builder.getInt(S.getLHS()->EvaluateKnownConstInt(getContext())); + if (SwitchLikelihood) + SwitchLikelihood->push_back(Stmt::getLikelihood(Attrs)); // If the body of the case is just a 'break', try to not emit an empty block. // If we're profiling or we're not optimizing, leave the block in for better @@ -1358,6 +1371,10 @@ // that falls through to the next case which is IR intensive. It also causes // deep recursion which can run into stack depth limitations. Handle // sequential non-range case statements specially. + // + // TODO When the next case has a likelihood attribute the code returns to the + // recursive algorithm. Maybe improve this case if it becomes common practice + // to use a lot of attributes. const CaseStmt *CurCase = &S; const CaseStmt *NextCase = dyn_cast(S.getSubStmt()); @@ -1373,6 +1390,10 @@ CaseDest = createBasicBlock("sw.bb"); EmitBlockWithFallThrough(CaseDest, &S); } + // Since this loop is only executed when the CaseStmt has no attributes + // use a hard-coded value. + if (SwitchLikelihood) + SwitchLikelihood->push_back(Stmt::LH_None); SwitchInsn->addCase(CaseVal, CaseDest); NextCase = dyn_cast(CurCase->getSubStmt()); @@ -1382,7 +1403,8 @@ EmitStmt(CurCase->getSubStmt()); } -void CodeGenFunction::EmitDefaultStmt(const DefaultStmt &S) { +void CodeGenFunction::EmitDefaultStmt(const DefaultStmt &S, + ArrayRef Attrs) { // If there is no enclosing switch instance that we're aware of, then this // default statement can be elided. This situation only happens when we've // constant-folded the switch. @@ -1395,6 +1417,9 @@ assert(DefaultBlock->empty() && "EmitDefaultStmt: Default block already defined?"); + if (SwitchLikelihood) + SwitchLikelihood->front() = Stmt::getLikelihood(Attrs); + EmitBlockWithFallThrough(DefaultBlock, &S); EmitStmt(S.getSubStmt()); @@ -1632,10 +1657,59 @@ FoundCase; } +static Optional> +getLikelihoodWeights(ArrayRef Likelihoods) { + // Are there enough branches to weight them? + if (Likelihoods.size() <= 1) + return None; + + uint64_t NumUnlikely = 0; + uint64_t NumNone = 0; + uint64_t NumLikely = 0; + for (const auto LH : Likelihoods) { + switch (LH) { + // clang-format off + case Stmt::LH_Unlikely: ++NumUnlikely; break; + case Stmt::LH_None: ++NumNone; break; + case Stmt::LH_Likely: ++NumLikely; break; + // clang-format on + } + } + + // Is there a likelihood attribute used? + if (NumUnlikely == 0 && NumLikely == 0) + return None; + + // When multiple cases share the same code they can be combined during + // optimization. In that case the weights of the branch will be the sum of + // the individual weights. Make sure the combined sum of all neutral cases + // doesn't exceed the value of a single likely attribute. + // The additions both avoid divisions by 0 and make sure the weights of None + // don't exceed the weight of Likely. + const uint64_t Likely = INT32_MAX / (NumLikely + 2); + const uint64_t None = Likely / (NumNone + 1); + const uint64_t Unlikely = 0; + + SmallVector Result; + Result.reserve(Likelihoods.size()); + for (const auto LH : Likelihoods) { + switch (LH) { + // clang-format off + case Stmt::LH_Unlikely: Result.push_back(Unlikely); break; + case Stmt::LH_None: Result.push_back(None); break; + case Stmt::LH_Likely: Result.push_back(Likely); break; + // clang-format on + } + } + + return Result; +} + void CodeGenFunction::EmitSwitchStmt(const SwitchStmt &S) { // Handle nested switch statements. llvm::SwitchInst *SavedSwitchInsn = SwitchInsn; SmallVector *SavedSwitchWeights = SwitchWeights; + SmallVector *SavedSwitchLikelihood = SwitchLikelihood; llvm::BasicBlock *SavedCRBlock = CaseRangeBlock; // See if we can constant fold the condition of the switch and therefore only @@ -1710,7 +1784,12 @@ // The default needs to be first. We store the edge count, so we already // know the right weight. SwitchWeights->push_back(DefaultCount); + } else if (CGM.getCodeGenOpts().OptimizationLevel) { + SwitchLikelihood = new SmallVector(); + // Initialize the default case. + SwitchLikelihood->push_back(Stmt::LH_None); } + CaseRangeBlock = DefaultBlock; // Clear the insertion point to indicate we are in unreachable code. @@ -1774,9 +1853,21 @@ SwitchInsn->setMetadata(llvm::LLVMContext::MD_prof, createProfileWeights(*SwitchWeights)); delete SwitchWeights; + } else if (SwitchLikelihood) { + assert(SwitchLikelihood->size() == 1 + SwitchInsn->getNumCases() && + "switch likelihoods do not match switch cases"); + Optional> LHW = + getLikelihoodWeights(*SwitchLikelihood); + if (LHW) { + llvm::MDBuilder MDHelper(CGM.getLLVMContext()); + SwitchInsn->setMetadata(llvm::LLVMContext::MD_prof, + createProfileWeights(*LHW)); + } + delete SwitchLikelihood; } SwitchInsn = SavedSwitchInsn; SwitchWeights = SavedSwitchWeights; + SwitchLikelihood = SavedSwitchLikelihood; CaseRangeBlock = SavedCRBlock; } Index: clang/lib/CodeGen/CodeGenFunction.h =================================================================== --- clang/lib/CodeGen/CodeGenFunction.h +++ clang/lib/CodeGen/CodeGenFunction.h @@ -1395,6 +1395,9 @@ }; OpenMPCancelExitStack OMPCancelStack; + /// Calculate branch weights for the likelihood attribute + llvm::MDNode *createBranchWeights(Stmt::Likelihood LH) const; + CodeGenPGO PGO; /// Calculate branch weights appropriate for PGO data @@ -1439,6 +1442,9 @@ /// The branch weights of SwitchInsn when doing instrumentation based PGO. SmallVector *SwitchWeights = nullptr; + /// The likelihood attributes of the SwitchCase. + SmallVector *SwitchLikelihood = nullptr; + /// CaseRangeBlock - This block holds if condition check for last case /// statement range in current switch instruction. llvm::BasicBlock *CaseRangeBlock = nullptr; @@ -3075,7 +3081,7 @@ /// statements. /// /// \return True if the statement was handled. - bool EmitSimpleStmt(const Stmt *S); + bool EmitSimpleStmt(const Stmt *S, ArrayRef Attrs); Address EmitCompoundStmt(const CompoundStmt &S, bool GetLast = false, AggValueSlot AVS = AggValueSlot::ignored()); @@ -3104,9 +3110,9 @@ void EmitBreakStmt(const BreakStmt &S); void EmitContinueStmt(const ContinueStmt &S); void EmitSwitchStmt(const SwitchStmt &S); - void EmitDefaultStmt(const DefaultStmt &S); - void EmitCaseStmt(const CaseStmt &S); - void EmitCaseStmtRange(const CaseStmt &S); + void EmitDefaultStmt(const DefaultStmt &S, ArrayRef Attrs); + void EmitCaseStmt(const CaseStmt &S, ArrayRef Attrs); + void EmitCaseStmtRange(const CaseStmt &S, ArrayRef Attrs); void EmitAsmStmt(const AsmStmt &S); void EmitObjCForCollectionStmt(const ObjCForCollectionStmt &S); Index: clang/lib/CodeGen/CodeGenFunction.cpp =================================================================== --- clang/lib/CodeGen/CodeGenFunction.cpp +++ clang/lib/CodeGen/CodeGenFunction.cpp @@ -1478,21 +1478,6 @@ return true; } -static Optional> -getLikelihoodWeights(Stmt::Likelihood LH) { - switch (LH) { - case Stmt::LH_Unlikely: - return std::pair(llvm::UnlikelyBranchWeight, - llvm::LikelyBranchWeight); - case Stmt::LH_None: - return None; - case Stmt::LH_Likely: - return std::pair(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. @@ -1692,12 +1677,7 @@ } } - llvm::MDNode *Weights = nullptr; - Optional> LHW = getLikelihoodWeights(LH); - if (LHW) { - llvm::MDBuilder MDHelper(CGM.getLLVMContext()); - Weights = MDHelper.createBranchWeights(LHW->first, LHW->second); - } + llvm::MDNode *Weights = createBranchWeights(LH); if (!Weights) { uint64_t CurrentCount = std::max(getCurrentProfileCount(), TrueCount); Weights = createProfileWeights(TrueCount, CurrentCount - TrueCount); @@ -2569,3 +2549,27 @@ return llvm::DebugLoc(); } + +static Optional> +getLikelihoodWeights(Stmt::Likelihood LH) { + switch (LH) { + case Stmt::LH_Unlikely: + return std::pair(llvm::UnlikelyBranchWeight, + llvm::LikelyBranchWeight); + case Stmt::LH_None: + return None; + case Stmt::LH_Likely: + return std::pair(llvm::LikelyBranchWeight, + llvm::UnlikelyBranchWeight); + } + llvm_unreachable("Unknown Likelihood"); +} + +llvm::MDNode *CodeGenFunction::createBranchWeights(Stmt::Likelihood LH) const { + Optional> LHW = getLikelihoodWeights(LH); + if (!LHW) + return nullptr; + + llvm::MDBuilder MDHelper(CGM.getLLVMContext()); + return MDHelper.createBranchWeights(LHW->first, LHW->second); +} Index: clang/test/CodeGenCXX/attr-likelihood-switch-branch-weights.cpp =================================================================== --- /dev/null +++ clang/test/CodeGenCXX/attr-likelihood-switch-branch-weights.cpp @@ -0,0 +1,173 @@ +// RUN: %clang_cc1 -O1 -disable-llvm-passes -emit-llvm %s -o - -triple=x86_64-linux-gnu | FileCheck %s + +extern volatile int i; + +void OneCaseL() { + // CHECK-LABEL: define{{.*}}OneCaseL + // CHECK: switch + // CHECK: {{.*}} !prof !6 + switch (i) { + [[likely]] case 1: + ++i; + break; + } +} + +void OneCaseU() { + // CHECK-LABEL: define{{.*}}OneCaseU + // CHECK: switch + // CHECK: {{.*}} !prof !7 + switch (i) { + [[unlikely]] case 1 : ++i; + break; + } +} + +void TwoCasesLN() { + // CHECK-LABEL: define{{.*}}TwoCasesLN + // CHECK: switch + // CHECK: {{.*}} !prof !8 + switch (i) { + [[likely]] case 1: + i += 2; + break; + + case 2: + i += 3; + break; + } +} + +void TwoCasesUN() { + // CHECK-LABEL: define{{.*}}TwoCasesUN + // CHECK: switch + // CHECK: {{.*}} !prof !9 + switch (i) { + [[unlikely]] case 1: + i += 2; + break; + + case 2: + i += 3; + break; + } +} + +void TwoCasesLU() { + // CHECK-LABEL: define{{.*}}TwoCasesLU + // CHECK: switch + // CHECK: {{.*}} !prof !10 + switch (i) { + [[likely]] case 1: + i += 2; + break; + + [[unlikely]] case 2: + i += 3; + break; + } +} + +void CasesFallthroughNNLN() { + // CHECK-LABEL: define{{.*}}CasesFallthroughNNLN + // CHECK: switch + // CHECK: {{.*}} !prof !11 + switch (i) { + case 1: + ++i; + case 2: + [[likely]] case 3: + case 4: + i += 3; + break; + } +} + +void CasesFallthroughNNUN() { + // CHECK-LABEL: define{{.*}}CasesFallthroughNNUN + // CHECK: switch + // CHECK: {{.*}} !prof !12 + switch (i) { + case 1: + ++i; + case 2: + [[unlikely]] case 3: + case 4: + i += 3; + break; + } +} + +void CasesFallthroughRangeSmallLN() { + // CHECK-LABEL: define{{.*}}CasesFallthroughRangeSmallLN + // CHECK: switch + // CHECK: {{.*}} !prof !13 + switch (i) { + case 1 ... 5: + ++i; + case 102: + [[likely]] case 103: + case 104: + i += 103; + break; + } +} + +void CasesFallthroughRangeSmallUN() { + // CHECK-LABEL: define{{.*}}CasesFallthroughRangeSmallUN + // CHECK: switch + // CHECK: {{.*}} !prof !14 + switch (i) { + case 1 ... 5: + ++i; + case 102: + [[unlikely]] case 103: + case 104: + i += 103; + break; + } +} + +void CasesFallthroughRangeLargeLLN() { + // CHECK-LABEL: define{{.*}}CasesFallthroughRangeLargeLLN + // CHECK: switch + // CHECK: {{.*}} !prof !8 + // CHECK: caserange + // CHECK: br{{.*}} !prof !15 + switch (i) { + [[likely]] case 0 ... 64: + ++i; + [[likely]] case 1003: + case 104: + i += 103; + break; + } +} + +void CasesFallthroughRangeLargeUUN() { + // CHECK-LABEL: define{{.*}}CasesFallthroughRangeLargeUUN + // CHECK: switch + // CHECK: {{.*}} !prof !9 + // CHECK: caserange + // CHECK: br{{.*}} !prof !16 + switch (i) { + [[unlikely]] case 0 ... 64: + ++i; + [[unlikely]] case 1003: + case 104: + i += 103; + break; + } +} + +// CHECK: !6 = !{!"branch_weights", i32 357913942, i32 715827883} +// CHECK: !7 = !{!"branch_weights", i32 536870912, i32 1} +// CHECK: !8 = !{!"branch_weights", i32 238609295, i32 715827883, i32 238609295} +// CHECK: !9 = !{!"branch_weights", i32 357913942, i32 1, i32 357913942} +// CHECK: !10 = !{!"branch_weights", i32 357913942, i32 715827883, i32 1} +// CHECK: !11 = !{!"branch_weights", i32 143165577, i32 143165577, i32 143165577, i32 715827883, i32 143165577} +// CHECK: !12 = !{!"branch_weights", i32 214748365, i32 214748365, i32 214748365, i32 1, i32 214748365} +// CHECK: !13 = !{!"branch_weights", i32 79536432, i32 79536432, i32 79536432, i32 79536432, i32 79536432, i32 79536432, i32 79536432, i32 715827883, i32 79536432} +// CHECK: !14 = !{!"branch_weights", i32 119304648, i32 119304648, i32 119304648, i32 119304648, i32 119304648, i32 119304648, i32 119304648, i32 1, i32 119304648} +// CHECK: !15 = !{!"branch_weights", i32 2000, i32 1} +// CHECK: !16 = !{!"branch_weights", i32 1, i32 2000} Index: clang/test/Preprocessor/has_attribute.cpp =================================================================== --- clang/test/Preprocessor/has_attribute.cpp +++ clang/test/Preprocessor/has_attribute.cpp @@ -62,13 +62,13 @@ // FIXME(201806L) CHECK: ensures: 0 // FIXME(201806L) CHECK: expects: 0 // CHECK: fallthrough: 201603L -// FIXME(201803L) CHECK: likely: 2L +// CHECK: likely: 201803L // CHECK: maybe_unused: 201603L // ITANIUM: no_unique_address: 201803L // WINDOWS: no_unique_address: 0 // CHECK: nodiscard: 201907L // CHECK: noreturn: 200809L -// FIXME(201803L) CHECK: unlikely: 2L +// CHECK: unlikely: 201803L // Test for Microsoft __declspec attributes Index: clang/www/cxx_status.html =================================================================== --- clang/www/cxx_status.html +++ clang/www/cxx_status.html @@ -987,7 +987,7 @@ [[likely]] and [[unlikely]] attributes P0479R5 - Clang 12 (partial) + Clang 12 typename optional in more contexts