[CodeGenPrepare] use branch weight metadata to decide if a select should be turned into a branch

[spatel]

Summary

This is part of solving PR27344:
https://llvm.org/bugs/show_bug.cgi?id=27344

As noted in the bug report, I have a couple of questions about how to implement this. I've taken my best guesses at those questions in this patch:

1. Should SimplifyCFG use metadata and not create a select in the first place for an obviously predictable branch? Or should CGP be responsible for undoing that transform?

I decided that CGP should undo the transform for the same reason that earlier patches have used the same mechanism: it's possible that passes between SimplifyCFG and CGP may be able to optimize the IR further with a select in place.

2. Since we're relying on branch weight metadata, we need a TLI hook to determine just how lopsided that data must be before favoring branches over a select. What's a good default value for that ratio?

I selected >99% taken or not taken as the default threshold for a highly predictable branch. Even the most limited HW branch predictors will be correct on this branch almost all the time, so even a massive mispredict penalty perf loss would be overcome by the win from all the times the branch was predicted correctly.

As a follow-up, we could make the default target hook less conservative by using the SchedMachineModel's MispredictPenalty. Or we could just let targets override the default by implementing the hook with that and other target-specific options. Note that trying to statically determine mispredict rates for close-to-balanced profile weight data is generally impossible if the HW is sufficiently advanced. Ie, 50/50 taken/not-taken might still be 100% predictable.

Finally, note that this patch as-is will not solve PR27344 because the current __builtin_unpredictable() branch weight default values are 4 and 64. I proposed to change that in D19435.

[kbsmith1]

LGTM

[hfinkel]

lib/CodeGen/CodeGenPrepare.cpp

4558 ↗

(On Diff #54874)

Does this handle both extremes (i.e. almost always true and almost always false)?

[spatel]

lib/CodeGen/CodeGenPrepare.cpp

4558 ↗

(On Diff #54874)

Yes - since we're using the max value of true or false, it will work.

It was just laziness for me to not include that test case. Let me add it and update the patch. Thanks!

[hfinkel]

lib/CodeGen/CodeGenPrepare.cpp

4558 ↗

(On Diff #54874)

Ah, sounds good. LGTM then too.

[spatel]

Patch updated:

1. Added test case to show that likely true and likely false are both handled.
2. Made auto-generated checks a bit more flexible by using regex.

[davidxl]

include/llvm/Target/TargetLowering.h

268 ↗

(On Diff #54874)

hard coding default value like this make it hard to do performance experiment -- suggest an internal option to control

lib/CodeGen/CodeGenPrepare.cpp

4551 ↗

(On Diff #54874)

Why is unpredictable meta data is not looked at here?

lib/IR/Metadata.cpp

1263 ↗

(On Diff #54874)

This fix can be committed as a different patch?

test/CodeGen/X86/cmov-into-branch.ll

99 ↗

(On Diff #54874)

Worth adding a test case where probability is < 1% ?

[davidxl]

lib/CodeGen/CodeGenPrepare.cpp

4558 ↗

(On Diff #54903)

Hal, this is an example that profile meta data is directly looked at instead of via BPI (I don't have an issue with it -- but just a note this scenario exists).

[hfinkel]

include/llvm/Target/TargetLowering.h

268 ↗

(On Diff #54903)

Agreed. A command-line option to override the default would be significantly more convenient.

lib/CodeGen/CodeGenPrepare.cpp

4558 ↗

(On Diff #54903)

I was thinking that :-) -- but this use did not seem to fit into BPI's interface. If/when we start preserving BPI, we'd need to update here, however.

[spatel]

include/llvm/Target/TargetLowering.h

268 ↗

(On Diff #54903)

Yes - will fix and update the patch.

lib/CodeGen/CodeGenPrepare.cpp

4551 ↗

(On Diff #54903)

Good point - we use it in splitBranchCondition() but forgot to update this path.
I'll fix that ahead of this patch.

lib/IR/Metadata.cpp

1263 ↗

(On Diff #54903)

Sure - I'll check-in the extra check + comment + variable name changes and update this.

test/CodeGen/X86/cmov-into-branch.ll

118 ↗

(On Diff #54903)

Hmm - do you want to check for something different than 'weighted_select1()' above?

[davidxl]

test/CodeGen/X86/cmov-into-branch.ll

118 ↗

(On Diff #54903)

Ok - I mis-read the case -- what needs to be covered is already covered. A minor suggestion -- the tests (select2, select3) are intended to test that meta data can drive decision to create branch -- but not necessarily to test the actual default 99%,1% threshold. For this reason, it might be better to make !1 and !2 prof data more extreme so that the tests are more robust.

[flyingforyou]

LGTM.

test/CodeGen/X86/cmov-into-branch.ll

101 ↗

(On Diff #54903)

Please, remove trailing white space.

[spatel]

lib/CodeGen/CodeGenPrepare.cpp

4551 ↗

(On Diff #54903)

rL267504

lib/IR/Metadata.cpp

1263 ↗

(On Diff #54903)

rL267491

test/CodeGen/X86/cmov-into-branch.ll

118 ↗

(On Diff #54903)

I actually want these tests to perform double-duty:

1. They check that profile data is driving the codegen.
2. They check the exact boundary where that decision changes.

If we make the prof data more extreme, then someone can come by in the future and change the default threshold without breaking any tests. I don't think we want that. We want a change in the default value to be justified and testable.

[spatel]

Patch updated:

1. Added a cl::opt and code comment for the default min percentage threshold to enable the transform.
2. Rebased to account for rL267491 and rL267504 .
3. Removed trailing whitespace in test file.

[davidxl]

lgtm

llvm/trunk/include/llvm/IR/Instruction.h

void dropUnknownNonDebugMetadata(unsigned ID1, unsigned ID2) {
     unsigned IDs[] = {ID1, ID2};
     return dropUnknownNonDebugMetadata(IDs);
   }
   /// @}
 
   /// 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); }
 
   /// Return the debug location for this node as a DebugLoc.
   const DebugLoc &getDebugLoc() const { return DbgLoc; }
 
   /// Set or clear the nsw flag on this instruction, which must be an operator
   /// which supports this flag. See LangRef.html for the meaning of this flag.

llvm/trunk/include/llvm/IR/Instructions.h

public:
 
   /// \brief Swap the successors of this branch instruction.
   ///
   /// Swaps the successors of the branch instruction. This also swaps any
   /// branch weight metadata associated with the instruction so that it
   /// 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);
   }
   static inline bool classof(const Value *V) {
     return isa<Instruction>(V) && classof(cast<Instruction>(V));
   }
 

llvm/trunk/include/llvm/Target/TargetLowering.h

 #include "llvm/MC/MCRegisterInfo.h"
 #include "llvm/Target/TargetCallingConv.h"
 #include "llvm/Target/TargetMachine.h"
 #include <climits>
 #include <map>
 #include <vector>
 
 namespace llvm {
+  class BranchProbability;
   class CallInst;
   class CCState;
   class CCValAssign;
   class FastISel;
   class FunctionLoweringInfo;
   class ImmutableCallSite;
   class IntrinsicInst;
   class MachineBasicBlock;
public:
   bool isJumpExpensive() const { return JumpIsExpensive; }
 
   /// Return true if selects are only cheaper than branches if the branch is
   /// unlikely to be predicted right.
   bool isPredictableSelectExpensive() const {
     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)
   /// On architectures that don't natively support some vector loads
   /// efficiently, casting the load to a smaller vector of larger types and
   /// loading is more efficient, however, this can be undone by optimizations in
   /// dag combiner.
   virtual bool isLoadBitCastBeneficial(EVT LoadVT,

llvm/trunk/lib/CodeGen/CodeGenPrepare.cpp

 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/MDBuilder.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/Statepoint.h"
 #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"
 #include "llvm/Target/TargetLowering.h"
 #include "llvm/Target/TargetSubtargetInfo.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/BuildLibCalls.h"
 #include "llvm/Transforms/Utils/BypassSlowDivision.h"
static bool sinkSelectOperand(const TargetTransformInfo *TTI, Value *V) {
   // If it's safe to speculatively execute, then it should not have side
   // effects; therefore, it's safe to sink and possibly *not* execute.
   return I && I->hasOneUse() && isSafeToSpeculativelyExecute(I) &&
          TTI->getUserCost(I) >= TargetTransformInfo::TCC_Expensive;
 }
 
 /// 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<CmpInst>(SI->getCondition());
 
   // If a branch is predictable, an out-of-order CPU can avoid blocking on its
   // comparison condition. If the compare has more than one use, there's
   // probably another cmov or setcc around, so it's not worth emitting a branch.
   if (!Cmp || !Cmp->hasOneUse())
     return false;
bool CodeGenPrepare::optimizeSelectInst(SelectInst *SI) {
   TargetLowering::SelectSupportKind SelectKind;
   if (VectorCond)
     SelectKind = TargetLowering::VectorMaskSelect;
   else if (SI->getType()->isVectorTy())
     SelectKind = TargetLowering::ScalarCondVectorVal;
   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))
 
   ModifiedDT = true;
 
   // Transform a sequence like this:
   //    start:
   //       %cmp = cmp uge i32 %a, %b
   //       %sel = select i1 %cmp, i32 %c, i32 %d
   //

llvm/trunk/lib/CodeGen/TargetLoweringBase.cpp

 #include "llvm/CodeGen/StackMaps.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/Mangler.h"
 #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"
 #include "llvm/Target/TargetLoweringObjectFile.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetRegisterInfo.h"
 #include "llvm/Target/TargetSubtargetInfo.h"
 #include <cctype>
 using namespace llvm;
 
 static cl::opt<bool> JumpIsExpensiveOverride(
     "jump-is-expensive", cl::init(false),
     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<int> 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) {
   Names[RTLIB::SHL_I16] = "__ashlhi3";
   Names[RTLIB::SHL_I32] = "__ashlsi3";
   Names[RTLIB::SHL_I64] = "__ashldi3";
   Names[RTLIB::SHL_I128] = "__ashlti3";
   Names[RTLIB::SRL_I16] = "__lshrhi3";
if (Fast != nullptr)
       *Fast = true;
     return true;
   }
   
   // This is a misaligned access.
   return allowsMisalignedMemoryAccesses(VT, AddrSpace, Alignment, Fast);
 }
 
+BranchProbability TargetLoweringBase::getPredictableBranchThreshold() const {
+  return BranchProbability(MinPercentageForPredictableBranch, 100);
+}
 
 //===----------------------------------------------------------------------===//
 //  TargetTransformInfo Helpers
 //===----------------------------------------------------------------------===//
 
 int TargetLoweringBase::InstructionOpcodeToISD(unsigned Opcode) const {
   enum InstructionOpcodes {
 #define HANDLE_INST(NUM, OPCODE, CLASS) OPCODE = NUM,

llvm/trunk/lib/IR/Instructions.cpp

void BranchInst::swapSuccessors() {
 
   // The first operand is the name. Fetch them backwards and build a new one.
   Metadata *Ops[] = {ProfileData->getOperand(0), ProfileData->getOperand(2),
                      ProfileData->getOperand(1)};
   setMetadata(LLVMContext::MD_prof,
               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<MDString>(ProfileData->getOperand(0));
-  if (!ProfDataName || !ProfDataName->getString().equals("branch_weights"))
-    return false;
-
-  auto *CITrue = mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(1));
-  auto *CIFalse = mdconst::dyn_extract<ConstantInt>(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);
 }
 unsigned BranchInst::getNumSuccessorsV() const {
   return getNumSuccessors();
 }
 void BranchInst::setSuccessorV(unsigned idx, BasicBlock *B) {
   setSuccessor(idx, B);

llvm/trunk/lib/IR/Metadata.cpp

void Instruction::getAllMetadataOtherThanDebugLocImpl(
   assert(hasMetadataHashEntry() &&
          getContext().pImpl->InstructionMetadata.count(this) &&
          "Shouldn't have called this");
   const auto &Info = getContext().pImpl->InstructionMetadata.find(this)->second;
   assert(!Info.empty() && "Shouldn't have called this");
   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<MDString>(ProfileData->getOperand(0));
+  if (!ProfDataName || !ProfDataName->getString().equals("branch_weights"))
+    return false;
+
+  auto *CITrue = mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(1));
+  auto *CIFalse = mdconst::dyn_extract<ConstantInt>(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);
   setHasMetadataHashEntry(false);
 }
 
 MDNode *Function::getMetadata(unsigned KindID) const {
   if (!hasMetadata())

llvm/trunk/test/CodeGen/X86/cmov-into-branch.ll

 ; CHECK-NEXT:    movl %esi, %eax
 ; CHECK-NEXT:    retq
 ;
   %cmp = icmp ne i32 %a, 0
   %sel = select i1 %cmp, i32 %a, i32 %b, !prof !0
   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
   %sel = select i1 %cmp, i32 %a, i32 %b, !prof !1
   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}