Index: llvm/trunk/include/llvm/IR/Instruction.h =================================================================== --- llvm/trunk/include/llvm/IR/Instruction.h +++ llvm/trunk/include/llvm/IR/Instruction.h @@ -217,6 +217,11 @@ /// Sets the metadata on this instruction from the AAMDNodes structure. void setAAMetadata(const AAMDNodes &N); + /// Retrieve the raw weight values of a conditional branch or select. + /// Returns true on success with profile weights filled in. + /// Returns false if no metadata or invalid metadata was found. + bool extractProfMetadata(uint64_t &TrueVal, uint64_t &FalseVal); + /// Set the debug location information for this instruction. void setDebugLoc(DebugLoc Loc) { DbgLoc = std::move(Loc); } Index: llvm/trunk/include/llvm/IR/Instructions.h =================================================================== --- llvm/trunk/include/llvm/IR/Instructions.h +++ llvm/trunk/include/llvm/IR/Instructions.h @@ -2906,11 +2906,6 @@ /// continues to map correctly to each operand. void swapSuccessors(); - /// Retrieve the raw weight values of a conditional branch. - /// Returns true on success with profile weights filled in. - /// Returns false if no metadata or invalid metadata was found. - bool extractProfMetadata(uint64_t &TrueVal, uint64_t &FalseVal); - // Methods for support type inquiry through isa, cast, and dyn_cast: static inline bool classof(const Instruction *I) { return (I->getOpcode() == Instruction::Br); Index: llvm/trunk/include/llvm/Target/TargetLowering.h =================================================================== --- llvm/trunk/include/llvm/Target/TargetLowering.h +++ llvm/trunk/include/llvm/Target/TargetLowering.h @@ -41,6 +41,7 @@ #include namespace llvm { + class BranchProbability; class CallInst; class CCState; class CCValAssign; @@ -261,6 +262,10 @@ return PredictableSelectIsExpensive; } + /// If a branch or a select condition is skewed in one direction by more than + /// this factor, it is very likely to be predicted correctly. + virtual BranchProbability getPredictableBranchThreshold() const; + /// isLoadBitCastBeneficial() - Return true if the following transform /// is beneficial. /// fold (conv (load x)) -> (load (conv*)x) Index: llvm/trunk/lib/CodeGen/CodeGenPrepare.cpp =================================================================== --- llvm/trunk/lib/CodeGen/CodeGenPrepare.cpp +++ llvm/trunk/lib/CodeGen/CodeGenPrepare.cpp @@ -40,6 +40,7 @@ #include "llvm/IR/ValueHandle.h" #include "llvm/IR/ValueMap.h" #include "llvm/Pass.h" +#include "llvm/Support/BranchProbability.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" @@ -4538,11 +4539,25 @@ /// Returns true if a SelectInst should be turned into an explicit branch. static bool isFormingBranchFromSelectProfitable(const TargetTransformInfo *TTI, + const TargetLowering *TLI, SelectInst *SI) { + // If even a predictable select is cheap, then a branch can't be cheaper. + if (!TLI->isPredictableSelectExpensive()) + return false; + // FIXME: This should use the same heuristics as IfConversion to determine - // whether a select is better represented as a branch. This requires that - // branch probability metadata is preserved for the select, which is not the - // case currently. + // whether a select is better represented as a branch. + + // If metadata tells us that the select condition is obviously predictable, + // then we want to replace the select with a branch. + uint64_t TrueWeight, FalseWeight; + if (SI->extractProfMetadata(TrueWeight, FalseWeight)) { + uint64_t Max = std::max(TrueWeight, FalseWeight); + uint64_t Sum = TrueWeight + FalseWeight; + auto Probability = BranchProbability::getBranchProbability(Max, Sum); + if (Probability > TLI->getPredictableBranchThreshold()) + return true; + } CmpInst *Cmp = dyn_cast(SI->getCondition()); @@ -4580,14 +4595,9 @@ else SelectKind = TargetLowering::ScalarValSelect; - // Do we have efficient codegen support for this kind of 'selects' ? - if (TLI->isSelectSupported(SelectKind)) { - // We have efficient codegen support for the select instruction. - // Check if it is profitable to keep this 'select'. - if (!TLI->isPredictableSelectExpensive() || - !isFormingBranchFromSelectProfitable(TTI, SI)) - return false; - } + if (TLI->isSelectSupported(SelectKind) && + !isFormingBranchFromSelectProfitable(TTI, TLI, SI)) + return false; ModifiedDT = true; Index: llvm/trunk/lib/CodeGen/TargetLoweringBase.cpp =================================================================== --- llvm/trunk/lib/CodeGen/TargetLoweringBase.cpp +++ llvm/trunk/lib/CodeGen/TargetLoweringBase.cpp @@ -28,6 +28,7 @@ #include "llvm/MC/MCAsmInfo.h" #include "llvm/MC/MCContext.h" #include "llvm/MC/MCExpr.h" +#include "llvm/Support/BranchProbability.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/MathExtras.h" @@ -43,6 +44,17 @@ cl::desc("Do not create extra branches to split comparison logic."), cl::Hidden); +// Although this default value is arbitrary, it is not random. It is assumed +// that a condition that evaluates the same way by a higher percentage than this +// is best represented as control flow. Therefore, the default value N should be +// set such that the win from N% correct executions is greater than the loss +// from (100 - N)% mispredicted executions for the majority of intended targets. +static cl::opt MinPercentageForPredictableBranch( + "min-predictable-branch", cl::init(99), + cl::desc("Minimum percentage (0-100) that a condition must be either true " + "or false to assume that the condition is predictable"), + cl::Hidden); + /// InitLibcallNames - Set default libcall names. /// static void InitLibcallNames(const char **Names, const Triple &TT) { @@ -1625,6 +1637,9 @@ return allowsMisalignedMemoryAccesses(VT, AddrSpace, Alignment, Fast); } +BranchProbability TargetLoweringBase::getPredictableBranchThreshold() const { + return BranchProbability(MinPercentageForPredictableBranch, 100); +} //===----------------------------------------------------------------------===// // TargetTransformInfo Helpers Index: llvm/trunk/lib/IR/Instructions.cpp =================================================================== --- llvm/trunk/lib/IR/Instructions.cpp +++ llvm/trunk/lib/IR/Instructions.cpp @@ -1120,28 +1120,6 @@ MDNode::get(ProfileData->getContext(), Ops)); } -bool BranchInst::extractProfMetadata(uint64_t &TrueVal, uint64_t &FalseVal) { - assert(isConditional() && - "Looking for probabilities on unconditional branch?"); - auto *ProfileData = getMetadata(LLVMContext::MD_prof); - if (!ProfileData || ProfileData->getNumOperands() != 3) - return false; - - auto *ProfDataName = dyn_cast(ProfileData->getOperand(0)); - if (!ProfDataName || !ProfDataName->getString().equals("branch_weights")) - return false; - - auto *CITrue = mdconst::dyn_extract(ProfileData->getOperand(1)); - auto *CIFalse = mdconst::dyn_extract(ProfileData->getOperand(2)); - if (!CITrue || !CIFalse) - return false; - - TrueVal = CITrue->getValue().getZExtValue(); - FalseVal = CIFalse->getValue().getZExtValue(); - - return true; -} - BasicBlock *BranchInst::getSuccessorV(unsigned idx) const { return getSuccessor(idx); } Index: llvm/trunk/lib/IR/Metadata.cpp =================================================================== --- llvm/trunk/lib/IR/Metadata.cpp +++ llvm/trunk/lib/IR/Metadata.cpp @@ -1251,6 +1251,30 @@ Info.getAll(Result); } +bool Instruction::extractProfMetadata(uint64_t &TrueVal, uint64_t &FalseVal) { + assert((getOpcode() == Instruction::Br || + getOpcode() == Instruction::Select) && + "Looking for branch weights on something besides branch or select"); + + auto *ProfileData = getMetadata(LLVMContext::MD_prof); + if (!ProfileData || ProfileData->getNumOperands() != 3) + return false; + + auto *ProfDataName = dyn_cast(ProfileData->getOperand(0)); + if (!ProfDataName || !ProfDataName->getString().equals("branch_weights")) + return false; + + auto *CITrue = mdconst::dyn_extract(ProfileData->getOperand(1)); + auto *CIFalse = mdconst::dyn_extract(ProfileData->getOperand(2)); + if (!CITrue || !CIFalse) + return false; + + TrueVal = CITrue->getValue().getZExtValue(); + FalseVal = CIFalse->getValue().getZExtValue(); + + return true; +} + void Instruction::clearMetadataHashEntries() { assert(hasMetadataHashEntry() && "Caller should check"); getContext().pImpl->InstructionMetadata.erase(this); Index: llvm/trunk/test/CodeGen/X86/cmov-into-branch.ll =================================================================== --- llvm/trunk/test/CodeGen/X86/cmov-into-branch.ll +++ llvm/trunk/test/CodeGen/X86/cmov-into-branch.ll @@ -79,13 +79,15 @@ ret i32 %sel } -; TODO: If a select is obviously predictable, turn it into a branch. +; If a select is obviously predictable, turn it into a branch. define i32 @weighted_select2(i32 %a, i32 %b) { ; CHECK-LABEL: weighted_select2: ; CHECK: # BB#0: ; CHECK-NEXT: testl %edi, %edi -; CHECK-NEXT: cmovnel %edi, %esi -; CHECK-NEXT: movl %esi, %eax +; CHECK-NEXT: jne [[LABEL_BB5:.*]] +; CHECK: movl %esi, %edi +; CHECK-NEXT: [[LABEL_BB5]] +; CHECK-NEXT: movl %edi, %eax ; CHECK-NEXT: retq ; %cmp = icmp ne i32 %a, 0 @@ -93,6 +95,27 @@ ret i32 %sel } +; Note the reversed profile weights: it doesn't matter if it's +; obviously true or obviously false. +; Either one should become a branch rather than conditional move. +; TODO: But likely true vs. likely false should affect basic block placement? +define i32 @weighted_select3(i32 %a, i32 %b) { +; CHECK-LABEL: weighted_select3: +; CHECK: # BB#0: +; CHECK-NEXT: testl %edi, %edi +; CHECK-NEXT: jne [[LABEL_BB6:.*]] +; CHECK: movl %esi, %edi +; CHECK-NEXT: [[LABEL_BB6]] +; CHECK-NEXT: movl %edi, %eax +; CHECK-NEXT: retq +; + %cmp = icmp ne i32 %a, 0 + %sel = select i1 %cmp, i32 %a, i32 %b, !prof !2 + ret i32 %sel +} + + !0 = !{!"branch_weights", i32 1, i32 99} !1 = !{!"branch_weights", i32 1, i32 100} +!2 = !{!"branch_weights", i32 100, i32 1}