Index: clang/include/clang/AST/Stmt.h =================================================================== --- clang/include/clang/AST/Stmt.h +++ clang/include/clang/AST/Stmt.h @@ -56,6 +56,15 @@ class Token; class VarDecl; +// i don't konw where else to put this +enum BranchHint : unsigned { + NoHint = 0, + Taken = 1, + NotTaken = 2 + // we could add unpredictable it is directly related and the enum would fit + // nicely on 2 bits +}; + //===----------------------------------------------------------------------===// // AST classes for statements. //===----------------------------------------------------------------------===// @@ -167,6 +176,9 @@ /// True if this if statement has storage for an init statement. unsigned HasInit : 1; + /// holds information about likeliness of the branch being taken + BranchHint Hint : 2; + /// The location of the "if". SourceLocation IfLoc; }; @@ -1752,7 +1764,8 @@ /// Build an if/then/else statement. IfStmt(const ASTContext &Ctx, SourceLocation IL, bool IsConstexpr, Stmt *Init, - VarDecl *Var, Expr *Cond, Stmt *Then, SourceLocation EL, Stmt *Else); + VarDecl *Var, Expr *Cond, Stmt *Then, SourceLocation EL, Stmt *Else, + BranchHint Hint = NoHint); /// Build an empty if/then/else statement. explicit IfStmt(EmptyShell Empty, bool HasElse, bool HasVar, bool HasInit); @@ -1762,7 +1775,8 @@ static IfStmt *Create(const ASTContext &Ctx, SourceLocation IL, bool IsConstexpr, Stmt *Init, VarDecl *Var, Expr *Cond, Stmt *Then, SourceLocation EL = SourceLocation(), - Stmt *Else = nullptr); + Stmt *Else = nullptr, + BranchHint Hint = BranchHint::NoHint); /// Create an empty IfStmt optionally with storage for an else statement, /// condition variable and init expression. @@ -1778,6 +1792,10 @@ /// True if this IfStmt has storage for an else statement. bool hasElseStorage() const { return IfStmtBits.HasElse; } + BranchHint getBranchHint() const { return IfStmtBits.Hint; } + + void setBranchHint(BranchHint Hint) { IfStmtBits.Hint = Hint; } + Expr *getCond() { return reinterpret_cast(getTrailingObjects()[condOffset()]); } Index: clang/include/clang/Basic/Attr.td =================================================================== --- clang/include/clang/Basic/Attr.td +++ clang/include/clang/Basic/Attr.td @@ -1147,6 +1147,12 @@ let Documentation = [FallthroughDocs]; } +def Likelihood : StmtAttr { + let Spellings = [CXX11<"", "likely", 201803>, Clang<"likely">, CXX11<"", "unlikely", 201803>, Clang<"unlikely">]; +// let Subjects = [Stmt, LabelStmt]; + let Documentation = [LikelihoodDocs]; +} + def FastCall : DeclOrTypeAttr { let Spellings = [GCC<"fastcall">, Keyword<"__fastcall">, Keyword<"_fastcall">]; Index: clang/include/clang/Basic/AttrDocs.td =================================================================== --- clang/include/clang/Basic/AttrDocs.td +++ clang/include/clang/Basic/AttrDocs.td @@ -1492,6 +1492,39 @@ }]; } +def LikelihoodDocs : Documentation { + let Category = DocCatStmt; + let Heading = "likely / unlikely"; + let Content = [{ + +The ``likely`` or ``unlikely`` attribute is used to annotate that a statement or label is likely or unlikely to executed + +Here is an example: + +.. code-block:: c++ + + void g(int); + int f(int n) { + if (n > 5) [[unlikely]] { // n > 5 is considered to be arbitrarily unlikely + g(0); + return n * 2 + 1; + } + + switch (n) { + case 1: + g(1); + [[fallthrough]]; + + [[likely]] case 2: // n == 2 is considered to be arbitrarily more + g(2); // likely than any other value of n + break; + } + return 3; + } + + }]; +} + def ARMInterruptDocs : Documentation { let Category = DocCatFunction; let Heading = "interrupt (ARM)"; Index: clang/include/clang/Basic/DiagnosticSemaKinds.td =================================================================== --- clang/include/clang/Basic/DiagnosticSemaKinds.td +++ clang/include/clang/Basic/DiagnosticSemaKinds.td @@ -7339,6 +7339,8 @@ "use of the %0 attribute is a C++14 extension">, InGroup; def ext_cxx17_attr : Extension< "use of the %0 attribute is a C++17 extension">, InGroup; +def ext_cxx2a_attr : Extension< + "use of the %0 attribute is a C++2a extension">, InGroup; def warn_unused_comparison : Warning< "%select{equality|inequality|relational|three-way}0 comparison result unused">, @@ -8158,6 +8160,11 @@ "fallthrough annotation in unreachable code">, InGroup, DefaultIgnore; +def warn_no_associated_branch : Warning< + "attribute %0 not assiciated to any branch is ignored">, InGroup; +def warn_conflicting_attribute : Warning< + "%0 contradicing with previous %1 attribute">, InGroup; + def warn_unreachable_default : Warning< "default label in switch which covers all enumeration values">, InGroup, DefaultIgnore; Index: clang/include/clang/Sema/Scope.h =================================================================== --- clang/include/clang/Sema/Scope.h +++ clang/include/clang/Sema/Scope.h @@ -160,6 +160,9 @@ /// declared in this scope. unsigned short PrototypeIndex; + /// BranchAttr - Likelihood attribute associated with this Branch or nullptr + Attr *BranchAttr; + /// FnParent - If this scope has a parent scope that is a function body, this /// pointer is non-null and points to it. This is used for label processing. Scope *FnParent; @@ -221,6 +224,12 @@ /// isBlockScope - Return true if this scope correspond to a closure. bool isBlockScope() const { return Flags & BlockScope; } + /// getBranchAttr - Return the branching attribute associated with this scope. + const Attr *getBranchAttr() const { return BranchAttr; } + Attr *getBranchAttr() { return BranchAttr; } + + void setBranchAttr(Attr *Attribute) { BranchAttr = Attribute; } + /// getParent - Return the scope that this is nested in. const Scope *getParent() const { return AnyParent; } Scope *getParent() { return AnyParent; } Index: clang/include/clang/Sema/Sema.h =================================================================== --- clang/include/clang/Sema/Sema.h +++ clang/include/clang/Sema/Sema.h @@ -3841,14 +3841,18 @@ Stmt *SubStmt); class ConditionResult; - StmtResult ActOnIfStmt(SourceLocation IfLoc, bool IsConstexpr, - Stmt *InitStmt, + /// emit diagnostics and determinate the hint for and If statement + BranchHint HandleIfStmtHint(Stmt *thenStmt, Stmt *elseStmt, Attr *ThenAttr, + Attr *ElseAttr); + + StmtResult ActOnIfStmt(SourceLocation IfLoc, bool IsConstexpr, Stmt *InitStmt, ConditionResult Cond, Stmt *ThenVal, - SourceLocation ElseLoc, Stmt *ElseVal); - StmtResult BuildIfStmt(SourceLocation IfLoc, bool IsConstexpr, - Stmt *InitStmt, + SourceLocation ElseLoc, Stmt *ElseVal, + Attr *ThenAttr = nullptr, Attr *ElseAttr = nullptr); + StmtResult BuildIfStmt(SourceLocation IfLoc, bool IsConstexpr, Stmt *InitStmt, ConditionResult Cond, Stmt *ThenVal, - SourceLocation ElseLoc, Stmt *ElseVal); + SourceLocation ElseLoc, Stmt *ElseVal, + BranchHint Hint = NoHint); StmtResult ActOnStartOfSwitchStmt(SourceLocation SwitchLoc, Stmt *InitStmt, ConditionResult Cond); Index: clang/lib/AST/Stmt.cpp =================================================================== --- clang/lib/AST/Stmt.cpp +++ clang/lib/AST/Stmt.cpp @@ -798,7 +798,7 @@ IfStmt::IfStmt(const ASTContext &Ctx, SourceLocation IL, bool IsConstexpr, Stmt *Init, VarDecl *Var, Expr *Cond, Stmt *Then, - SourceLocation EL, Stmt *Else) + SourceLocation EL, Stmt *Else, BranchHint Hint) : Stmt(IfStmtClass) { bool HasElse = Else != nullptr; bool HasVar = Var != nullptr; @@ -806,6 +806,7 @@ IfStmtBits.HasElse = HasElse; IfStmtBits.HasVar = HasVar; IfStmtBits.HasInit = HasInit; + IfStmtBits.Hint = Hint; setConstexpr(IsConstexpr); @@ -828,11 +829,13 @@ IfStmtBits.HasElse = HasElse; IfStmtBits.HasVar = HasVar; IfStmtBits.HasInit = HasInit; + IfStmtBits.Hint = NoHint; } IfStmt *IfStmt::Create(const ASTContext &Ctx, SourceLocation IL, bool IsConstexpr, Stmt *Init, VarDecl *Var, Expr *Cond, - Stmt *Then, SourceLocation EL, Stmt *Else) { + Stmt *Then, SourceLocation EL, Stmt *Else, + BranchHint Hint) { bool HasElse = Else != nullptr; bool HasVar = Var != nullptr; bool HasInit = Init != nullptr; @@ -841,7 +844,7 @@ NumMandatoryStmtPtr + HasElse + HasVar + HasInit, HasElse), alignof(IfStmt)); return new (Mem) - IfStmt(Ctx, IL, IsConstexpr, Init, Var, Cond, Then, EL, Else); + IfStmt(Ctx, IL, IsConstexpr, Init, Var, Cond, Then, EL, Else, Hint); } IfStmt *IfStmt::CreateEmpty(const ASTContext &Ctx, bool HasElse, bool HasVar, Index: clang/lib/CodeGen/CGStmt.cpp =================================================================== --- clang/lib/CodeGen/CGStmt.cpp +++ clang/lib/CodeGen/CGStmt.cpp @@ -658,7 +658,7 @@ ElseBlock = createBasicBlock("if.else"); EmitBranchOnBoolExpr(S.getCond(), ThenBlock, ElseBlock, - getProfileCount(S.getThen())); + getProfileCount(S.getThen()), S.getBranchHint()); // Emit the 'then' code. EmitBlock(ThenBlock); @@ -691,6 +691,18 @@ EmitBlock(ContBlock, true); } +void CodeGenFunction::MaybeEmitLikelihoodHint(const Stmt *branch, + llvm::Value *CondV) { + BranchHint hint = NoHint; + if (hint != NoHint && CGM.getCodeGenOpts().OptimizationLevel != 0) { + llvm::Constant *ExpectedValue = llvm::ConstantInt::get( + llvm::Type::getInt1Ty(this->getLLVMContext()), hint == Taken); + llvm::Function *FnExpect = + CGM.getIntrinsic(llvm::Intrinsic::expect, CondV->getType()); + Builder.CreateCall(FnExpect, {CondV, ExpectedValue}, "expval"); + } +} + void CodeGenFunction::EmitWhileStmt(const WhileStmt &S, ArrayRef WhileAttrs) { // Emit the header for the loop, which will also become @@ -740,6 +752,7 @@ llvm::BasicBlock *ExitBlock = LoopExit.getBlock(); if (ConditionScope.requiresCleanups()) ExitBlock = createBasicBlock("while.exit"); + MaybeEmitLikelihoodHint(S.getBody(), BoolCondVal); Builder.CreateCondBr( BoolCondVal, LoopBody, ExitBlock, createProfileWeightsForLoop(S.getCond(), getProfileCount(S.getBody()))); @@ -825,6 +838,7 @@ // As long as the condition is true, iterate the loop. if (EmitBoolCondBranch) { uint64_t BackedgeCount = getProfileCount(S.getBody()) - ParentCount; + MaybeEmitLikelihoodHint(S.getBody(), BoolCondVal); Builder.CreateCondBr( BoolCondVal, LoopBody, LoopExit.getBlock(), createProfileWeightsForLoop(S.getCond(), BackedgeCount)); @@ -895,6 +909,7 @@ // C99 6.8.5p2/p4: The first substatement is executed if the expression // compares unequal to 0. The condition must be a scalar type. llvm::Value *BoolCondVal = EvaluateExprAsBool(S.getCond()); + MaybeEmitLikelihoodHint(S.getBody(), BoolCondVal); Builder.CreateCondBr( BoolCondVal, ForBody, ExitBlock, createProfileWeightsForLoop(S.getCond(), getProfileCount(S.getBody()))); @@ -976,6 +991,7 @@ // The body is executed if the expression, contextually converted // to bool, is true. llvm::Value *BoolCondVal = EvaluateExprAsBool(S.getCond()); + MaybeEmitLikelihoodHint(S.getBody(), BoolCondVal); Builder.CreateCondBr( BoolCondVal, ForBody, ExitBlock, createProfileWeightsForLoop(S.getCond(), getProfileCount(S.getBody()))); Index: clang/lib/CodeGen/CodeGenFunction.h =================================================================== --- clang/lib/CodeGen/CodeGenFunction.h +++ clang/lib/CodeGen/CodeGenFunction.h @@ -2852,6 +2852,8 @@ AggValueSlot AVS = AggValueSlot::ignored()); + void MaybeEmitLikelihoodHint(const Stmt *branch, llvm::Value *CondV); + /// EmitLabel - Emit the block for the given label. It is legal to call this /// function even if there is no current insertion point. void EmitLabel(const LabelDecl *D); // helper for EmitLabelStmt. @@ -4041,7 +4043,8 @@ /// TrueCount should be the number of times we expect the condition to /// evaluate to true based on PGO data. void EmitBranchOnBoolExpr(const Expr *Cond, llvm::BasicBlock *TrueBlock, - llvm::BasicBlock *FalseBlock, uint64_t TrueCount); + llvm::BasicBlock *FalseBlock, uint64_t TrueCount, + BranchHint hint = NoHint); /// Given an assignment `*LHS = RHS`, emit a test that checks if \p RHS is /// nonnull, if \p LHS is marked _Nonnull. Index: clang/lib/CodeGen/CodeGenFunction.cpp =================================================================== --- clang/lib/CodeGen/CodeGenFunction.cpp +++ clang/lib/CodeGen/CodeGenFunction.cpp @@ -1531,7 +1531,8 @@ void CodeGenFunction::EmitBranchOnBoolExpr(const Expr *Cond, llvm::BasicBlock *TrueBlock, llvm::BasicBlock *FalseBlock, - uint64_t TrueCount) { + uint64_t TrueCount, + BranchHint Hint) { Cond = Cond->IgnoreParens(); if (const BinaryOperator *CondBOp = dyn_cast(Cond)) { @@ -1720,6 +1721,14 @@ ApplyDebugLocation DL(*this, Cond); CondV = EvaluateExprAsBool(Cond); } + + if (Hint != NoHint && CGM.getCodeGenOpts().OptimizationLevel != 0) { + llvm::Constant *ExpectedValue = llvm::ConstantInt::get( + llvm::Type::getInt1Ty(this->getLLVMContext()), Hint == Taken); + llvm::Function *FnExpect = + CGM.getIntrinsic(llvm::Intrinsic::expect, CondV->getType()); + Builder.CreateCall(FnExpect, {CondV, ExpectedValue}, "expval"); + } Builder.CreateCondBr(CondV, TrueBlock, FalseBlock, Weights, Unpredictable); } Index: clang/lib/Parse/ParseStmt.cpp =================================================================== --- clang/lib/Parse/ParseStmt.cpp +++ clang/lib/Parse/ParseStmt.cpp @@ -19,6 +19,7 @@ #include "clang/Parse/RAIIObjectsForParser.h" #include "clang/Sema/DeclSpec.h" #include "clang/Sema/Scope.h" +#include "clang/Sema/SemaDiagnostic.h" #include "clang/Sema/TypoCorrection.h" using namespace clang; @@ -1256,6 +1257,9 @@ // Pop the 'if' scope if needed. InnerScope.Exit(); + Attr *ThenAttr = getCurScope()->getBranchAttr(); + getCurScope()->setBranchAttr(nullptr); + // If it has an else, parse it. SourceLocation ElseLoc; SourceLocation ElseStmtLoc; @@ -1295,6 +1299,7 @@ } else if (InnerStatementTrailingElseLoc.isValid()) { Diag(InnerStatementTrailingElseLoc, diag::warn_dangling_else); } + Attr *ElseAttr = getCurScope()->getBranchAttr(); IfScope.Exit(); @@ -1315,7 +1320,8 @@ ElseStmt = Actions.ActOnNullStmt(ElseStmtLoc); return Actions.ActOnIfStmt(IfLoc, IsConstexpr, InitStmt.get(), Cond, - ThenStmt.get(), ElseLoc, ElseStmt.get()); + ThenStmt.get(), ElseLoc, ElseStmt.get(), ThenAttr, + ElseAttr); } /// ParseSwitchStatement Index: clang/lib/Sema/Scope.cpp =================================================================== --- clang/lib/Sema/Scope.cpp +++ clang/lib/Sema/Scope.cpp @@ -87,6 +87,7 @@ void Scope::Init(Scope *parent, unsigned flags) { setFlags(parent, flags); + BranchAttr = 0; DeclsInScope.clear(); UsingDirectives.clear(); Entity = nullptr; Index: clang/lib/Sema/SemaStmt.cpp =================================================================== --- clang/lib/Sema/SemaStmt.cpp +++ clang/lib/Sema/SemaStmt.cpp @@ -521,11 +521,48 @@ }; } -StmtResult -Sema::ActOnIfStmt(SourceLocation IfLoc, bool IsConstexpr, Stmt *InitStmt, - ConditionResult Cond, - Stmt *thenStmt, SourceLocation ElseLoc, - Stmt *elseStmt) { +BranchHint Sema::HandleIfStmtHint(Stmt *thenStmt, Stmt *elseStmt, + Attr *ThenAttr, Attr *ElseAttr) { + // diagnose branch with attribute and null statement as empty body + if (thenStmt && isa(thenStmt) && + isa(dyn_cast(thenStmt)->getSubStmt())) + DiagnoseEmptyStmtBody( + dyn_cast(thenStmt)->getSubStmt()->getBeginLoc(), + dyn_cast(thenStmt)->getSubStmt(), + diag::warn_empty_if_body); + if (elseStmt && isa(elseStmt) && + isa(dyn_cast(elseStmt)->getSubStmt())) + DiagnoseEmptyStmtBody( + dyn_cast(elseStmt)->getSubStmt()->getBeginLoc(), + dyn_cast(elseStmt)->getSubStmt(), + diag::warn_empty_if_body); + + BranchHint Hint = NoHint; + // diagnose conflicting attribute and determinate hint + if (ThenAttr) { + if (ElseAttr && ThenAttr->getSpelling()[0] == ElseAttr->getSpelling()[0]) { + Diag(ElseAttr->getLocation(), diag::warn_conflicting_attribute) + << ElseAttr->getSpelling() << ThenAttr->getSpelling(); + Diag(ThenAttr->getLocation(), diag::note_conflicting_attribute); + } else { + if (ThenAttr->getSpelling()[0] == 'l') + Hint = Taken; + else + Hint = NotTaken; + } + } else if (ElseAttr) { + if (ElseAttr->getSpelling()[0] == 'u') + Hint = Taken; + else + Hint = NotTaken; + } + return Hint; +} + +StmtResult Sema::ActOnIfStmt(SourceLocation IfLoc, bool IsConstexpr, + Stmt *InitStmt, ConditionResult Cond, + Stmt *thenStmt, SourceLocation ElseLoc, + Stmt *elseStmt, Attr *ThenAttr, Attr *ElseAttr) { if (Cond.isInvalid()) Cond = ConditionResult( *this, nullptr, @@ -545,13 +582,14 @@ diag::warn_empty_if_body); return BuildIfStmt(IfLoc, IsConstexpr, InitStmt, Cond, thenStmt, ElseLoc, - elseStmt); + elseStmt, + HandleIfStmtHint(thenStmt, elseStmt, ThenAttr, ElseAttr)); } StmtResult Sema::BuildIfStmt(SourceLocation IfLoc, bool IsConstexpr, Stmt *InitStmt, ConditionResult Cond, Stmt *thenStmt, SourceLocation ElseLoc, - Stmt *elseStmt) { + Stmt *elseStmt, BranchHint Hint) { if (Cond.isInvalid()) return StmtError(); @@ -559,7 +597,7 @@ setFunctionHasBranchProtectedScope(); return IfStmt::Create(Context, IfLoc, IsConstexpr, InitStmt, Cond.get().first, - Cond.get().second, thenStmt, ElseLoc, elseStmt); + Cond.get().second, thenStmt, ElseLoc, elseStmt, Hint); } namespace { Index: clang/lib/Sema/SemaStmtAttr.cpp =================================================================== --- clang/lib/Sema/SemaStmtAttr.cpp +++ clang/lib/Sema/SemaStmtAttr.cpp @@ -51,6 +51,46 @@ return ::new (S.Context) auto(Attr); } +static Attr *handleLikelihoodAttr(Sema &S, Stmt *St, const ParsedAttr &A, + SourceRange Range) { + Attr *Attr = ::new (S.Context) LikelihoodAttr( + A.getRange(), S.Context, A.getAttributeSpellingListIndex()); + + if (!S.getLangOpts().CPlusPlus2a && A.isCXX11Attribute()) + S.Diag(A.getLoc(), diag::ext_cxx2a_attr) << A.getName(); + + Scope *CurScope = S.getCurScope(); + + if (CurScope) { + Scope *ControlScope = CurScope->getParent(); + if (!ControlScope || + !(ControlScope->getFlags() & Scope::ControlScope || + ControlScope->getFlags() & Scope::BreakScope) || + ControlScope->getFlags() & Scope::SEHExceptScope || + ControlScope->getFlags() & Scope::SEHTryScope || + ControlScope->getFlags() & Scope::TryScope || + ControlScope->getFlags() & Scope::FnTryCatchScope) { + S.Diag(A.getLoc(), diag::warn_no_associated_branch) << A.getName(); + return Attr; + } + + if (ControlScope->getBranchAttr()) { + if (ControlScope->getBranchAttr()->getSpelling()[0] == + Attr->getSpelling()[0]) + S.Diag(Attr->getLocation(), diag::err_repeat_attribute) + << Attr->getSpelling(); + else + S.Diag(Attr->getLocation(), diag::err_attributes_are_not_compatible) + << Attr->getSpelling() + << ControlScope->getBranchAttr()->getSpelling(); + S.Diag(ControlScope->getBranchAttr()->getLocation(), + diag::note_previous_attribute); + } else + ControlScope->setBranchAttr(Attr); + } + return Attr; +} + static Attr *handleSuppressAttr(Sema &S, Stmt *St, const ParsedAttr &A, SourceRange Range) { if (A.getNumArgs() < 1) { @@ -336,6 +376,8 @@ return nullptr; case ParsedAttr::AT_FallThrough: return handleFallThroughAttr(S, St, A, Range); + case ParsedAttr::AT_Likelihood: + return handleLikelihoodAttr(S, St, A, Range); case ParsedAttr::AT_LoopHint: return handleLoopHintAttr(S, St, A, Range); case ParsedAttr::AT_OpenCLUnrollHint: Index: clang/lib/Serialization/ASTReaderStmt.cpp =================================================================== --- clang/lib/Serialization/ASTReaderStmt.cpp +++ clang/lib/Serialization/ASTReaderStmt.cpp @@ -222,6 +222,7 @@ bool HasElse = Record.readInt(); bool HasVar = Record.readInt(); bool HasInit = Record.readInt(); + S->setBranchHint(static_cast(Record.readInt())); S->setCond(Record.readSubExpr()); S->setThen(Record.readSubStmt()); Index: clang/lib/Serialization/ASTWriterStmt.cpp =================================================================== --- clang/lib/Serialization/ASTWriterStmt.cpp +++ clang/lib/Serialization/ASTWriterStmt.cpp @@ -139,6 +139,7 @@ Record.push_back(HasElse); Record.push_back(HasVar); Record.push_back(HasInit); + Record.push_back(S->getBranchHint()); Record.AddStmt(S->getCond()); Record.AddStmt(S->getThen());