[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

81

add some comments to the methods.

143

is less profitable?

204

This function deserves more comments in the code.

222

non-loop regions?

235

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

81

Done.

143

Yes. Fixed.

204

Added more comments.

235

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

152

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

177

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.

193

assert ColdI != NULL?

197

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

208

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.

227

Is this possible?

[apostolakis]

llvm/lib/CodeGen/SelectOptimize.cpp

152

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.

177

Sure, added.

193

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

197

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

208

Good point. Changed the function name and the comments.

227

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

211

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.

213

Suggest adding an option which is the multiplier of the TCC_expensive

[apostolakis]

llvm/lib/CodeGen/SelectOptimize.cpp

211

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.

213

Good idea to make it customizable. Added.

[apostolakis]

Address comments.

[davidxl]

llvm/lib/CodeGen/SelectOptimize.cpp

228

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

228

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

137–139

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

137–139

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

137–139

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

 //===--- SelectOptimize.cpp - Convert select to branches if profitable ---===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This pass converts selects to conditional jumps when profitable.
 //
 //===----------------------------------------------------------------------===//
 
+#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/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");
+
+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 {}
+  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(SelectOptimize, "select-optimize", "Optimize selects", false,
+
+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) {
+  // Determine for which select groups it is profitable converting to branches.
+  SelectGroups ProfSIGroups;
+  // 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) {
   llvm_unreachable("Unimplemented");
 }
+
+void SelectOptimize::convertProfitableSIGroups(SelectGroups &ProfSIGroups) {
+  llvm_unreachable("Unimplemented");
+}
+
+void SelectOptimize::collectSelectGroups(BasicBlock &BB,
+                                         SelectGroups &SIGroups) {
+  BasicBlock::iterator BBIt = BB.begin();
+  while (BBIt != BB.end()) {
+    Instruction *I = &*BBIt++;
+    if (SelectInst *SI = dyn_cast<SelectInst>(I)) {
+      SelectGroup SIGroup;
+      SIGroup.push_back(SI);
+      while (BBIt != BB.end()) {
+        SelectInst *NI = dyn_cast<SelectInst>(&*BBIt);
+        if (NI && SI->getCondition() == NI->getCondition()) {
+          SIGroup.push_back(NI);
+          ++BBIt;
+        } else {
+          break;
+        }
+      }
+
+      // If the select type is not supported, no point optimizing it.
+      // Instruction selection will take care of it.
+      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);
+}