[SelectOpti][3/5] Base Heuristics

[apostolakis]

Summary

This patch adds the base heuristics for determining whether branches are more profitable than conditional moves.
Base heuristics apply to all code apart from inner-most loops.

Depends on D122259

[apostolakis]

Minor tweaks

[apostolakis]

Skip selects with vector condition

[apostolakis]

Rebase and move tests

[apostolakis]

Use opt tests instead of llc ones

[apostolakis]

Rebase

[davidxl]

llvm/lib/CodeGen/SelectOptimize.cpp

99

add some comments to the methods.

336

is less profitable?

397

This function deserves more comments in the code.

415

non-loop regions?

428

should the relative hotness of II be checked instead of looking at the loop context?

Also It might worth check if the instructions in slice can actually be wrapped in the cold branch -- checking hasOneUse is for this, but is it more restricted?

[apostolakis]

llvm/lib/CodeGen/SelectOptimize.cpp

99

Done.

336

Yes. Fixed.

397

Added more comments.

428

That's a good idea. It is better to check the relative hotness rather than looking at loop contexts. Changed the code. Skipping instructions less hot than the source instruction (the value operand of the select).

Checking for hasOneUse is a bit conservative (e.g., an instruction could have two uses that are both meant for the computation of the cold value operand of the target select) but it is much simpler than accurately identifying all the instructions used solely for the computation of the select’s true/false value operands. I originally implemented the latter but the experimental results did not show improved performance and thus the extra implementation complexity was not justified.

[apostolakis]

Address review comments

[davidxl]

llvm/lib/CodeGen/SelectOptimize.cpp

345

If the SI is in a cold basic block (as determined by profile summary), it may not be worth converting.

370

When profile data is available, but the select instruction does not have a meta data attached, we may want to emit a missed optimization warning.

386

assert ColdI != NULL?

390

what if all defs in the chain are cheap, but they add up to be expensive?

401

Perhaps make the name of the method more general to match its intention: get instructions that can be wrapped into the cold branch when converted to control flow. Also make it clear that current heuristic chooses only oneUse defs.

420

Is this possible?

[apostolakis]

llvm/lib/CodeGen/SelectOptimize.cpp

345

That's true.
Selects in cold functions will not be considered for conversion since this is tested earlier by calling llvm::shouldOptimizeForSize. But cold basic blocks within a non-cold function are not checked. Added a check for coldness at the basic block level to prevent any conversion.

370

Sure, added.

386

The value operands of the select instructions are not necessarily instructions, could be for example, a function argument.

390

Yes, many cheap ones could amount to be as costly as one expensive one. Tweaked the heuristic to account for that.

401

Good point. Changed the function name and the comments.

420

This branch can go both ways:

Example where freq(II) < freq(I):

II = ...
for () {
    I = II  + ...
    x = select c, I, ...
}

Example where freq(II) > freq(I):

for () {
   II = ...
}
I = II  + ...
x = select c, I, ...

[apostolakis]

Address review.

[davidxl]

llvm/lib/CodeGen/SelectOptimize.cpp

404

Should the cost also consider the frequency difference between the SI and the cold operand?

basically the colder the operand, the more expensive it is to use CMOV.

406

Suggest adding an option which is the multiplier of the TCC_expensive

[apostolakis]

llvm/lib/CodeGen/SelectOptimize.cpp

404

Yes that would seem a good idea.
Tested a couple of different ways of adjusting the cost and evaluated perf impact on search workload.
Added the one that showed some positive (although only slight) effect.

406

Good idea to make it customizable. Added.

[apostolakis]

Address comments.

[davidxl]

llvm/lib/CodeGen/SelectOptimize.cpp

421

Is there a concern on the overflow of the multiplication? Probably not if the meta data weight is 32 bit.

[apostolakis]

llvm/lib/CodeGen/SelectOptimize.cpp

421

The weight metadata indeed contains 32-bit values and the SliceCost is expected to be small (these cold slices contain a handful of instructions with typical costs of 1 to 4 for each instruction). So, no real concern of overflowing here.

[davidxl]

lgtm

[bsmith]

llvm/lib/CodeGen/SelectOptimize.cpp

142–144

Is this the correct thing to check for here?

Even if a select is cheap, the true/false values feeding it may not be, and given the later change you have that can sink these values when converted to a branch, this check may cause us to miss some cases where this pass is still useful. (Although perhaps changing this should be deferred to the patch that does the sinking).

[davidxl]

llvm/lib/CodeGen/SelectOptimize.cpp

142–144

This is a good point. Perhaps the target specific behavior should be modeled using a cost value (SelectCost) instead of using the binary knob.

[apostolakis]

llvm/lib/CodeGen/SelectOptimize.cpp

142–144

You are right that there are still cases where it is worth considering converting to a branch even for architectures with cheap selects. I left this check since it was used in CodeGenPrepare when optimizing selects and I wanted to avoid unexpected optimizations for non-x86 architectures. However, since this pass will be, at least initially, opt-in and this check is not always useful, I will remove it. It will allow for easier non-x86 testing of the pass. Actually, when I tested some small examples on AArch64, I had to comment out this check since this pass got skipped otherwise.

The cost of the select is already taken into account in the loop-level heuristics.
For the base heuristics, the heuristic looking for the expensive cold operand applies regardless of the cost of the select.
Yet, for the heuristic that converts highly predictable selects to branches, this check still applies. If a predictable select is not expensive, then the high predictability of the select does not suffice on its own for conversion to a branch. So, I added this check for this heuristic.

By the way, @bsmith let me know if you do any perfomance testing of this pass on ARM architectures. I will be happy to incorporate feedback and refine this pass to profitably target both x86 and ARM archs.

[apostolakis]

Limit the isPredictableSelectExpensive check to only the highly-predictable heuristic.

llvm/lib/CodeGen/SelectOptimize.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/BranchProbabilityInfo.h"
 #include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/OptimizationRemarkEmitter.h"
+#include "llvm/Analysis/ProfileSummaryInfo.h"
+#include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/TargetLowering.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
 #include "llvm/CodeGen/TargetSchedule.h"
 #include "llvm/CodeGen/TargetSubtargetInfo.h"
 #include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
 #include "llvm/Target/TargetMachine.h"
+#include "llvm/Transforms/Utils/SizeOpts.h"
+#include <algorithm>
+#include <memory>
+#include <queue>
+#include <stack>
+#include <string>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "select-optimize"
 
+STATISTIC(NumSelectOptAnalyzed,
+          "Number of select groups considered for conversion to branch");
+STATISTIC(NumSelectConvertedExpColdOperand,
+          "Number of select groups converted due to expensive cold operand");
+STATISTIC(NumSelectConvertedHighPred,
+          "Number of select groups converted due to high-predictability");
+STATISTIC(NumSelectUnPred,
+          "Number of select groups not converted due to unpredictability");
 STATISTIC(NumSelectsConverted, "Number of selects converted");
 
+static cl::opt<unsigned> ColdOperandThreshold(
+    "cold-operand-threshold",
+    cl::desc("Maximum frequency of path for an operand to be considered cold."),
+    cl::init(20), cl::Hidden);
+
 namespace {
 
 class SelectOptimize : public FunctionPass {
   const TargetMachine *TM = nullptr;
   const TargetSubtargetInfo *TSI;
   const TargetLowering *TLI = nullptr;
+  const TargetTransformInfo *TTI = nullptr;
   const LoopInfo *LI;
+  DominatorTree *DT;
   std::unique_ptr<BlockFrequencyInfo> BFI;
   std::unique_ptr<BranchProbabilityInfo> BPI;
+  ProfileSummaryInfo *PSI;
+  OptimizationRemarkEmitter *ORE;
 
 public:
   static char ID;
+
   SelectOptimize() : FunctionPass(ID) {
     initializeSelectOptimizePass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnFunction(Function &F) override;
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequired<ProfileSummaryInfoWrapperPass>();
     AU.addRequired<TargetPassConfig>();
+    AU.addRequired<TargetTransformInfoWrapperPass>();
+    AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<LoopInfoWrapperPass>();
+    AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
   }
 
 private:
   // Select groups consist of consecutive select instructions with the same
   // condition.
   using SelectGroup = SmallVector<SelectInst *, 2>;
   using SelectGroups = SmallVector<SelectGroup, 2>;
 
   bool optimizeSelects(Function &F);
+  void optimizeSelectsBase(Function &F, SelectGroups &ProfSIGroups);
+  void optimizeSelectsInnerLoops(Function &F, SelectGroups &ProfSIGroups);
   void convertProfitableSIGroups(SelectGroups &ProfSIGroups);
   void collectSelectGroups(BasicBlock &BB, SelectGroups &SIGroups);
+  void findProfitableSIGroupsBase(SelectGroups &SIGroups,
+                                  SelectGroups &ProfSIGroups);
+  bool isConvertToBranchProfitableBase(const SmallVector<SelectInst *, 2> &ASI);
+  bool hasExpensiveColdOperand(const SmallVector<SelectInst *, 2> &ASI);
+  void getOneUseSlice(Instruction *I, SmallVector<Instruction *, 2> &Slice);
+  bool isSelectHighlyPredictable(const SelectInst *SI);
+  bool isExpensiveInst(Instruction *I);
   bool isSelectKindSupported(SelectInst *SI);
 };
 } // namespace
 
 char SelectOptimize::ID = 0;
 
 INITIALIZE_PASS_BEGIN(SelectOptimize, DEBUG_TYPE, "Optimize selects", false,
                       false)
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
+INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)
 INITIALIZE_PASS_END(SelectOptimize, DEBUG_TYPE, "Optimize selects", false,
                     false)
 
 FunctionPass *llvm::createSelectOptimizePass() { return new SelectOptimize(); }
 
 bool SelectOptimize::runOnFunction(Function &F) {
   TM = &getAnalysis<TargetPassConfig>().getTM<TargetMachine>();
   TSI = TM->getSubtargetImpl(F);
   TLI = TSI->getTargetLowering();
+
+  // If none of the select types is supported then skip this pass.
+  // This is an optimization pass. Legality issues will be handled by
+  // instruction selection.
+  if (!TLI->isSelectSupported(TargetLowering::ScalarValSelect) &&
+      !TLI->isSelectSupported(TargetLowering::ScalarCondVectorVal) &&
+      !TLI->isSelectSupported(TargetLowering::VectorMaskSelect))
+    return false;
+
+  // If even a predictable select is cheap, then a branch cannot be cheaper.
+  if (!TLI->isPredictableSelectExpensive())
+    return false;
+
+  TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
+  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   BPI.reset(new BranchProbabilityInfo(F, *LI));
   BFI.reset(new BlockFrequencyInfo(F, *BPI, *LI));
+  PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
+  ORE = &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
+
+  // When optimizing for size, selects are preferable over branches.
+  if (F.hasOptSize() || llvm::shouldOptimizeForSize(&F, PSI, BFI.get()))
+    return false;
 
   return optimizeSelects(F);
 }
 
 bool SelectOptimize::optimizeSelects(Function &F) {
-  // Collect all the select groups.
-  SelectGroups SIGroups;
-  for (BasicBlock &BB : F) {
-    collectSelectGroups(BB, SIGroups);
-  }
-
   // Determine for which select groups it is profitable converting to branches.
   SelectGroups ProfSIGroups;
-  // For now assume that all select groups can be profitably converted to
-  // branches.
-  for (SelectGroup &ASI : SIGroups) {
-    ProfSIGroups.push_back(ASI);
-  }
+  // Base heuristics apply only to non-loops and outer loops.
+  optimizeSelectsBase(F, ProfSIGroups);
+  // Separate heuristics for inner-most loops.
+  optimizeSelectsInnerLoops(F, ProfSIGroups);
 
   // Convert to branches the select groups that were deemed
   // profitable-to-convert.
   convertProfitableSIGroups(ProfSIGroups);
 
   // Code modified if at least one select group was converted.
   return !ProfSIGroups.empty();
 }
 
+void SelectOptimize::optimizeSelectsBase(Function &F,
+                                         SelectGroups &ProfSIGroups) {
+  // Collect all the select groups.
+  SelectGroups SIGroups;
+  for (BasicBlock &BB : F) {
+    // Base heuristics apply only to non-loops and outer loops.
+    Loop *L = LI->getLoopFor(&BB);
+    if (L && L->isInnermost())
+      continue;
+    collectSelectGroups(BB, SIGroups);
+  }
+
+  // Determine for which select groups it is profitable converting to branches.
+  findProfitableSIGroupsBase(SIGroups, ProfSIGroups);
+}
+
+void SelectOptimize::optimizeSelectsInnerLoops(Function &F,
+                                               SelectGroups &ProfSIGroups) {}
+
 /// If \p isTrue is true, return the true value of \p SI, otherwise return
 /// false value of \p SI. If the true/false value of \p SI is defined by any
 /// select instructions in \p Selects, look through the defining select
 /// instruction until the true/false value is not defined in \p Selects.
 static Value *
 getTrueOrFalseValue(SelectInst *SI, bool isTrue,
                     const SmallPtrSet<const Instruction *, 2> &Selects) {
   Value *V = nullptr;
if (SelectInst *SI = dyn_cast<SelectInst>(I)) {
       if (!isSelectKindSupported(SI))
         continue;
 
       SIGroups.push_back(SIGroup);
     }
   }
 }
 
+void SelectOptimize::findProfitableSIGroupsBase(SelectGroups &SIGroups,
+                                                SelectGroups &ProfSIGroups) {
+  for (SelectGroup &ASI : SIGroups) {
+    ++NumSelectOptAnalyzed;
+    if (isConvertToBranchProfitableBase(ASI))
+      ProfSIGroups.push_back(ASI);
+  }
+}
+
+bool SelectOptimize::isConvertToBranchProfitableBase(
+    const SmallVector<SelectInst *, 2> &ASI) {
+  SelectInst *SI = ASI.front();
+  OptimizationRemark OR(DEBUG_TYPE, "SelectOpti", SI);
+  OptimizationRemarkMissed ORmiss(DEBUG_TYPE, "SelectOpti", SI);
+
+  // If unpredictable, branch form is more profitable.
+  if (SI->getMetadata(LLVMContext::MD_unpredictable)) {
+    ++NumSelectUnPred;
+    ORmiss << "Not converted to branch because of unpredictable branch. ";
+    ORE->emit(ORmiss);
+    return false;
+  }
+
+  // If highly predictable, branch form is more profitable.
+  if (isSelectHighlyPredictable(SI)) {
+    ++NumSelectConvertedHighPred;
+    OR << "Converted to branch because of highly predictable branch. ";
+    ORE->emit(OR);
+    return true;
+  }
+
+  // Look for expensive operands in the cold operand's (if any) dependence
+  // slice of any of the selects in the group.
+  if (hasExpensiveColdOperand(ASI)) {
+    ++NumSelectConvertedExpColdOperand;
+    OR << "Converted to branch because of expensive cold operand.";
+    ORE->emit(OR);
+    return true;
+  }
+
+  ORmiss << "Not profitable to convert to branch (base heuristic).";
+  ORE->emit(ORmiss);
+  return false;
+}
+
+bool SelectOptimize::hasExpensiveColdOperand(
+    const SmallVector<SelectInst *, 2> &ASI) {
+  bool ColdOperand = false;
+  uint64_t TrueWeight, FalseWeight;
+  if (ASI.front()->extractProfMetadata(TrueWeight, FalseWeight)) {
+    uint64_t Min = std::min(TrueWeight, FalseWeight);
+    uint64_t Sum = TrueWeight + FalseWeight;
+    // Is there a path with frequency <ColdOperandThreshold% (default:20%) ?
+    ColdOperand = Sum * ColdOperandThreshold > 100 * Min;
+  }
+  if (!ColdOperand)
+    return false;
+  // Check if the cold path's dependence slice has an expensive operation for
+  // any of the selects of the group.
+  for (SelectInst *SI : ASI) {
+    Instruction *ColdI = nullptr;
+    if (TrueWeight < FalseWeight)
+      ColdI = dyn_cast<Instruction>(SI->getTrueValue());
+    else
+      ColdI = dyn_cast<Instruction>(SI->getFalseValue());
+    if (ColdI) {
+      SmallVector<Instruction *, 2> ColdSlice;
+      getOneUseSlice(ColdI, ColdSlice);
+      for (auto *ColdII : ColdSlice)
+        if (isExpensiveInst(ColdII))
+          return true;
+    }
+  }
+  return false;
+}
+
+void SelectOptimize::getOneUseSlice(Instruction *I,
+                                    SmallVector<Instruction *, 2> &Slice) {
+  std::queue<Instruction *> Worklist;
+  Worklist.push(I);
+  SmallPtrSet<Instruction *, 2> Visited;
+  const Loop *L = LI->getLoopFor(I->getParent());
+  while (!Worklist.empty()) {
+    Instruction *II = Worklist.front();
+    Worklist.pop();
+
+    if (Visited.count(II))
+      continue;
+    Visited.insert(II);
+
+    if (!II->hasOneUse())
+      continue;
+
+    // Avoid considering instructions in outer or independent loops, or non-loop
+    // instructions (instructions with potentially much less frequency than the
+    // operand of the select).
+    const Loop *LII = LI->getLoopFor(II->getParent());
+    if (L && L != LII && (!LII || !L->contains(LII)))
+      continue;
+
+    // Avoid phi nodes that are not part of a loop-carried dependence.
+    // Could source from a cold basic block.
+    if (isa<PHINode>(II)) {
+      if (!LII)
+        continue;
+      if (LII->getHeader() != II->getParent())
+        continue;
+    }
+
+    Slice.push_back(II);
+    for (unsigned k = 0; k < II->getNumOperands(); ++k)
+      if (auto *OpI = dyn_cast<Instruction>(II->getOperand(k)))
+        Worklist.push(OpI);
+  }
+}
+
+bool SelectOptimize::isSelectHighlyPredictable(const SelectInst *SI) {
+  uint64_t TrueWeight, FalseWeight;
+  if (SI->extractProfMetadata(TrueWeight, FalseWeight)) {
+    uint64_t Max = std::max(TrueWeight, FalseWeight);
+    uint64_t Sum = TrueWeight + FalseWeight;
+    if (Sum != 0) {
+      auto Probability = BranchProbability::getBranchProbability(Max, Sum);
+      if (Probability > TTI->getPredictableBranchThreshold())
+        return true;
+    }
+  }
+  return false;
+}
+
+bool SelectOptimize::isExpensiveInst(Instruction *I) {
+  return TTI->getInstructionCost(I, TargetTransformInfo::TCK_Latency) >=
+         TargetTransformInfo::TCC_Expensive;
+}
+
 bool SelectOptimize::isSelectKindSupported(SelectInst *SI) {
   bool VectorCond = !SI->getCondition()->getType()->isIntegerTy(1);
   if (VectorCond)
     return false;
   TargetLowering::SelectSupportKind SelectKind;
   if (SI->getType()->isVectorTy())
     SelectKind = TargetLowering::ScalarCondVectorVal;
   else
     SelectKind = TargetLowering::ScalarValSelect;
   return TLI->isSelectSupported(SelectKind);
 }

llvm/test/CodeGen/X86/select-optimize.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -mtriple=x86_64-unknown-unknown -select-optimize -S < %s | FileCheck %s
 
-; Single select converted to branch
-define i32 @single_select(i32 %a, i32 %b, i1 %cmp) {
-; CHECK-LABEL: @single_select(
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+;; Test base heuristic 1:
+;; highly-biased selects assumed to be highly predictable, converted to branches
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+
+; If a select is obviously predictable, turn it into a branch.
+define i32 @weighted_select1(i32 %a, i32 %b, i1 %cmp) {
+; CHECK-LABEL: @weighted_select1(
 ; CHECK-NEXT:    [[SEL_FROZEN:%.*]] = freeze i1 [[CMP:%.*]]
-; CHECK-NEXT:    br i1 [[SEL_FROZEN]], label [[SELECT_END:%.*]], label [[SELECT_FALSE:%.*]], !prof [[PROF0:![0-9]+]]
+; CHECK-NEXT:    br i1 [[SEL_FROZEN]], label [[SELECT_END:%.*]], label [[SELECT_FALSE:%.*]], !prof [[PROF14:![0-9]+]]
 ; CHECK:       select.false:
 ; CHECK-NEXT:    br label [[SELECT_END]]
 ; CHECK:       select.end:
 ; CHECK-NEXT:    [[SEL:%.*]] = phi i32 [ [[A:%.*]], [[TMP0:%.*]] ], [ [[B:%.*]], [[SELECT_FALSE]] ]
 ; CHECK-NEXT:    ret i32 [[SEL]]
 ;
-  %sel = select i1 %cmp, i32 %a, i32 %b, !prof !0
+  %sel = select i1 %cmp, i32 %a, i32 %b, !prof !15
   ret i32 %sel
 }
 
-; Select group converted to branch
-define i32 @select_group(i32 %a, i32 %b, i32 %c, i1 %cmp) {
-; CHECK-LABEL: @select_group(
+; If a select is obviously predictable (reversed profile weights),
+; turn it into a branch.
+define i32 @weighted_select2(i32 %a, i32 %b, i1 %cmp) {
+; CHECK-LABEL: @weighted_select2(
+; CHECK-NEXT:    [[SEL_FROZEN:%.*]] = freeze i1 [[CMP:%.*]]
+; CHECK-NEXT:    br i1 [[SEL_FROZEN]], label [[SELECT_END:%.*]], label [[SELECT_FALSE:%.*]], !prof [[PROF15:![0-9]+]]
+; CHECK:       select.false:
+; CHECK-NEXT:    br label [[SELECT_END]]
+; CHECK:       select.end:
+; CHECK-NEXT:    [[SEL:%.*]] = phi i32 [ [[A:%.*]], [[TMP0:%.*]] ], [ [[B:%.*]], [[SELECT_FALSE]] ]
+; CHECK-NEXT:    ret i32 [[SEL]]
+;
+  %sel = select i1 %cmp, i32 %a, i32 %b, !prof !16
+  ret i32 %sel
+}
+
+; Not obvioulsy predictable select.
+define i32 @weighted_select3(i32 %a, i32 %b, i1 %cmp) {
+; CHECK-LABEL: @weighted_select3(
+; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP:%.*]], i32 [[A:%.*]], i32 [[B:%.*]], !prof [[PROF16:![0-9]+]]
+; CHECK-NEXT:    ret i32 [[SEL]]
+;
+  %sel = select i1 %cmp, i32 %a, i32 %b, !prof !17
+  ret i32 %sel
+}
+
+; Unpredictable select should not form a branch.
+define i32 @unpred_select(i32 %a, i32 %b, i1 %cmp) {
+; CHECK-LABEL: @unpred_select(
+; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP:%.*]], i32 [[A:%.*]], i32 [[B:%.*]], !unpredictable !17
+; CHECK-NEXT:    ret i32 [[SEL]]
+;
+  %sel = select i1 %cmp, i32 %a, i32 %b, !unpredictable !20
+  ret i32 %sel
+}
+
+; Predictable select in function with optsize attribute should not form branch.
+define i32 @weighted_select_optsize(i32 %a, i32 %b, i1 %cmp) optsize {
+; CHECK-LABEL: @weighted_select_optsize(
+; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP:%.*]], i32 [[A:%.*]], i32 [[B:%.*]], !prof [[PROF14]]
+; CHECK-NEXT:    ret i32 [[SEL]]
+;
+  %sel = select i1 %cmp, i32 %a, i32 %b, !prof !15
+  ret i32 %sel
+}
+
+define i32 @weighted_select_pgso(i32 %a, i32 %b, i1 %cmp) !prof !14 {
+; CHECK-LABEL: @weighted_select_pgso(
+; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP:%.*]], i32 [[A:%.*]], i32 [[B:%.*]], !prof [[PROF14]]
+; CHECK-NEXT:    ret i32 [[SEL]]
+;
+  %sel = select i1 %cmp, i32 %a, i32 %b, !prof !15
+  ret i32 %sel
+}
+
+; If two selects in a row are predictable, turn them into branches.
+define i32 @weighted_selects(i32 %a, i32 %b) !prof !19 {
+; CHECK-LABEL: @weighted_selects(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[A:%.*]], 0
+; CHECK-NEXT:    [[SEL_FROZEN:%.*]] = freeze i1 [[CMP]]
+; CHECK-NEXT:    br i1 [[SEL_FROZEN]], label [[SELECT_END:%.*]], label [[SELECT_FALSE:%.*]], !prof [[PROF14]]
+; CHECK:       select.false:
+; CHECK-NEXT:    br label [[SELECT_END]]
+; CHECK:       select.end:
+; CHECK-NEXT:    [[SEL:%.*]] = phi i32 [ [[A]], [[TMP0:%.*]] ], [ [[B:%.*]], [[SELECT_FALSE]] ]
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ne i32 [[SEL]], 0
+; CHECK-NEXT:    [[SEL1_FROZEN:%.*]] = freeze i1 [[CMP1]]
+; CHECK-NEXT:    br i1 [[SEL1_FROZEN]], label [[SELECT_END1:%.*]], label [[SELECT_FALSE2:%.*]], !prof [[PROF14]]
+; CHECK:       select.false2:
+; CHECK-NEXT:    br label [[SELECT_END1]]
+; CHECK:       select.end1:
+; CHECK-NEXT:    [[SEL1:%.*]] = phi i32 [ [[B]], [[SELECT_END]] ], [ [[A]], [[SELECT_FALSE2]] ]
+; CHECK-NEXT:    ret i32 [[SEL1]]
+;
+  %cmp = icmp ne i32 %a, 0
+  %sel = select i1 %cmp, i32 %a, i32 %b, !prof !15
+  %cmp1 = icmp ne i32 %sel, 0
+  %sel1 = select i1 %cmp1, i32 %b, i32 %a, !prof !15
+  ret i32 %sel1
+}
+
+; If select group predictable, turn it into a branch.
+define i32 @weighted_select_group(i32 %a, i32 %b, i32 %c, i1 %cmp) !prof !19 {
+; CHECK-LABEL: @weighted_select_group(
 ; CHECK-NEXT:    [[SEL1_FROZEN:%.*]] = freeze i1 [[CMP:%.*]]
-; CHECK-NEXT:    br i1 [[SEL1_FROZEN]], label [[SELECT_END:%.*]], label [[SELECT_FALSE:%.*]], !prof [[PROF0]]
+; CHECK-NEXT:    br i1 [[SEL1_FROZEN]], label [[SELECT_END:%.*]], label [[SELECT_FALSE:%.*]], !prof [[PROF14]]
 ; CHECK:       select.false:
 ; CHECK-NEXT:    br label [[SELECT_END]]
 ; CHECK:       select.end:
 ; CHECK-NEXT:    [[SEL1:%.*]] = phi i32 [ [[A:%.*]], [[TMP0:%.*]] ], [ [[B:%.*]], [[SELECT_FALSE]] ]
 ; CHECK-NEXT:    [[SEL2:%.*]] = phi i32 [ [[C:%.*]], [[TMP0]] ], [ [[A]], [[SELECT_FALSE]] ]
 ; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[SEL1]], [[SEL2]]
 ; CHECK-NEXT:    ret i32 [[ADD]]
 ;
-  %sel1 = select i1 %cmp, i32 %a, i32 %b, !prof !0
-  %sel2 = select i1 %cmp, i32 %c, i32 %a, !prof !0
+  %sel1 = select i1 %cmp, i32 %a, i32 %b, !prof !15
+  %sel2 = select i1 %cmp, i32 %c, i32 %a, !prof !15
   %add = add i32 %sel1, %sel2
   ret i32 %add
 }
 
-; Select group with intra-group dependence converted to branch
+; Predictable select group with intra-group dependence converted to branch
 define i32 @select_group_intra_group(i32 %a, i32 %b, i32 %c, i1 %cmp) {
 ; CHECK-LABEL: @select_group_intra_group(
 ; CHECK-NEXT:    [[SEL1_FROZEN:%.*]] = freeze i1 [[CMP:%.*]]
-; CHECK-NEXT:    br i1 [[SEL1_FROZEN]], label [[SELECT_END:%.*]], label [[SELECT_FALSE:%.*]], !prof [[PROF0]]
+; CHECK-NEXT:    br i1 [[SEL1_FROZEN]], label [[SELECT_END:%.*]], label [[SELECT_FALSE:%.*]], !prof [[PROF14]]
 ; CHECK:       select.false:
 ; CHECK-NEXT:    br label [[SELECT_END]]
 ; CHECK:       select.end:
 ; CHECK-NEXT:    [[SEL1:%.*]] = phi i32 [ [[A:%.*]], [[TMP0:%.*]] ], [ [[B:%.*]], [[SELECT_FALSE]] ]
 ; CHECK-NEXT:    [[SEL2:%.*]] = phi i32 [ [[C:%.*]], [[TMP0]] ], [ [[B]], [[SELECT_FALSE]] ]
 ; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[SEL1]], [[SEL2]]
 ; CHECK-NEXT:    ret i32 [[SUB]]
 ;
-  %sel1 = select i1 %cmp, i32 %a, i32 %b, !prof !0
-  %sel2 = select i1 %cmp, i32 %c, i32 %sel1, !prof !0
+  %sel1 = select i1 %cmp, i32 %a, i32 %b,!prof !15
+  %sel2 = select i1 %cmp, i32 %c, i32 %sel1, !prof !15
   %sub = sub i32 %sel1, %sel2
   ret i32 %sub
 }
 
-!0 = !{!"branch_weights", i32 1, i32 100}
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+;; Test base heuristic 2:
+;; look for expensive instructions in the one-use slice of the cold path
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+
+; Select with cold one-use load value operand should form branch and
+; sink load
+define i32 @expensive_val_operand1(i32* nocapture %a, i32 %y, i1 %cmp) {
+; CHECK-LABEL: @expensive_val_operand1(
+; CHECK-NEXT:    [[LOAD:%.*]] = load i32, i32* [[A:%.*]], align 8
+; CHECK-NEXT:    [[SEL_FROZEN:%.*]] = freeze i1 [[CMP:%.*]]
+; CHECK-NEXT:    br i1 [[SEL_FROZEN]], label [[SELECT_END:%.*]], label [[SELECT_FALSE:%.*]], !prof [[PROF16]]
+; CHECK:       select.false:
+; CHECK-NEXT:    br label [[SELECT_END]]
+; CHECK:       select.end:
+; CHECK-NEXT:    [[SEL:%.*]] = phi i32 [ [[LOAD]], [[TMP0:%.*]] ], [ [[Y:%.*]], [[SELECT_FALSE]] ]
+; CHECK-NEXT:    ret i32 [[SEL]]
+;
+  %load = load i32, i32* %a, align 8
+  %sel = select i1 %cmp, i32 %load, i32 %y, !prof !17
+  ret i32 %sel
+}
+
+; Expensive hot value operand and cheap cold value operand.
+define i32 @expensive_val_operand2(i32* nocapture %a, i32 %x, i1 %cmp) {
+; CHECK-LABEL: @expensive_val_operand2(
+; CHECK-NEXT:    [[LOAD:%.*]] = load i32, i32* [[A:%.*]], align 8
+; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP:%.*]], i32 [[X:%.*]], i32 [[LOAD]], !prof [[PROF16]]
+; CHECK-NEXT:    ret i32 [[SEL]]
+;
+  %load = load i32, i32* %a, align 8
+  %sel = select i1 %cmp, i32 %x, i32 %load, !prof !17
+  ret i32 %sel
+}
+
+; Cold value operand with load in its one-use dependence slice shoud result
+; into a branch with sinked dependence slice.
+define i32 @expensive_val_operand3(i32* nocapture %a, i32 %b, i32 %y, i1 %cmp) {
+; CHECK-LABEL: @expensive_val_operand3(
+; CHECK-NEXT:    [[LOAD:%.*]] = load i32, i32* [[A:%.*]], align 8
+; CHECK-NEXT:    [[X:%.*]] = add i32 [[LOAD]], [[B:%.*]]
+; CHECK-NEXT:    [[SEL_FROZEN:%.*]] = freeze i1 [[CMP:%.*]]
+; CHECK-NEXT:    br i1 [[SEL_FROZEN]], label [[SELECT_END:%.*]], label [[SELECT_FALSE:%.*]], !prof [[PROF16]]
+; CHECK:       select.false:
+; CHECK-NEXT:    br label [[SELECT_END]]
+; CHECK:       select.end:
+; CHECK-NEXT:    [[SEL:%.*]] = phi i32 [ [[X]], [[TMP0:%.*]] ], [ [[Y:%.*]], [[SELECT_FALSE]] ]
+; CHECK-NEXT:    ret i32 [[SEL]]
+;
+  %load = load i32, i32* %a, align 8
+  %x = add i32 %load, %b
+  %sel = select i1 %cmp, i32 %x, i32 %y, !prof !17
+  ret i32 %sel
+}
+
+; Multiple uses of the load value operand.
+define i32 @expensive_val_operand4(i32 %a, i32* nocapture %b, i32 %x, i1 %cmp) {
+; CHECK-LABEL: @expensive_val_operand4(
+; CHECK-NEXT:    [[LOAD:%.*]] = load i32, i32* [[B:%.*]], align 4
+; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP:%.*]], i32 [[X:%.*]], i32 [[LOAD]]
+; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[SEL]], [[LOAD]]
+; CHECK-NEXT:    ret i32 [[ADD]]
+;
+  %load = load i32, i32* %b, align 4
+  %sel = select i1 %cmp, i32 %x, i32 %load
+  %add = add i32 %sel, %load
+  ret i32 %add
+}
+
+!llvm.module.flags = !{!0}
+!0 = !{i32 1, !"ProfileSummary", !1}
+!1 = !{!2, !3, !4, !5, !6, !7, !8, !9}
+!2 = !{!"ProfileFormat", !"InstrProf"}
+!3 = !{!"TotalCount", i64 10000}
+!4 = !{!"MaxCount", i64 10}
+!5 = !{!"MaxInternalCount", i64 1}
+!6 = !{!"MaxFunctionCount", i64 1000}
+!7 = !{!"NumCounts", i64 3}
+!8 = !{!"NumFunctions", i64 3}
+!9 = !{!"DetailedSummary", !10}
+!10 = !{!11, !12, !13}
+!11 = !{i32 10000, i64 100, i32 1}
+!12 = !{i32 999000, i64 100, i32 1}
+!13 = !{i32 999999, i64 1, i32 2}
+!14 = !{!"function_entry_count", i64 0}
+!15 = !{!"branch_weights", i32 1, i32 100}
+!16 = !{!"branch_weights", i32 100, i32 1}
+!17 = !{!"branch_weights", i32 1, i32 99}
+!18 = !{!"branch_weights", i32 50, i32 50}
+!19 = !{!"function_entry_count", i64 100}
+!20 = !{}