1//===--- SelectOptimize.cpp - Convert select to branches if profitable ---===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This pass converts selects to conditional jumps when profitable.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/CodeGen/SelectOptimize.h"
14#include "llvm/ADT/SetVector.h"
15#include "llvm/ADT/SmallVector.h"
16#include "llvm/ADT/Statistic.h"
17#include "llvm/Analysis/BlockFrequencyInfo.h"
18#include "llvm/Analysis/BranchProbabilityInfo.h"
19#include "llvm/Analysis/LoopInfo.h"
20#include "llvm/Analysis/OptimizationRemarkEmitter.h"
21#include "llvm/Analysis/ProfileSummaryInfo.h"
22#include "llvm/Analysis/TargetTransformInfo.h"
23#include "llvm/CodeGen/Passes.h"
24#include "llvm/CodeGen/TargetLowering.h"
25#include "llvm/CodeGen/TargetPassConfig.h"
26#include "llvm/CodeGen/TargetSchedule.h"
27#include "llvm/CodeGen/TargetSubtargetInfo.h"
28#include "llvm/IR/BasicBlock.h"
29#include "llvm/IR/Dominators.h"
30#include "llvm/IR/Function.h"
31#include "llvm/IR/IRBuilder.h"
32#include "llvm/IR/Instruction.h"
33#include "llvm/IR/PatternMatch.h"
34#include "llvm/IR/ProfDataUtils.h"
35#include "llvm/InitializePasses.h"
36#include "llvm/Pass.h"
37#include "llvm/Support/ScaledNumber.h"
38#include "llvm/Target/TargetMachine.h"
39#include "llvm/Transforms/Utils/SizeOpts.h"
40#include <algorithm>
41#include <queue>
42#include <stack>
43
44using namespace llvm;
45using namespace llvm::PatternMatch;
46
47#define DEBUG_TYPE "select-optimize"
48
49STATISTIC(NumSelectOptAnalyzed,
50 "Number of select groups considered for conversion to branch");
51STATISTIC(NumSelectConvertedExpColdOperand,
52 "Number of select groups converted due to expensive cold operand");
53STATISTIC(NumSelectConvertedHighPred,
54 "Number of select groups converted due to high-predictability");
55STATISTIC(NumSelectUnPred,
56 "Number of select groups not converted due to unpredictability");
57STATISTIC(NumSelectColdBB,
58 "Number of select groups not converted due to cold basic block");
59STATISTIC(NumSelectConvertedLoop,
60 "Number of select groups converted due to loop-level analysis");
61STATISTIC(NumSelectsConverted, "Number of selects converted");
62
63static cl::opt<unsigned> ColdOperandThreshold(
64 "cold-operand-threshold",
65 cl::desc("Maximum frequency of path for an operand to be considered cold."),
66 cl::init(Val: 20), cl::Hidden);
67
68static cl::opt<unsigned> ColdOperandMaxCostMultiplier(
69 "cold-operand-max-cost-multiplier",
70 cl::desc("Maximum cost multiplier of TCC_expensive for the dependence "
71 "slice of a cold operand to be considered inexpensive."),
72 cl::init(Val: 1), cl::Hidden);
73
74static cl::opt<unsigned>
75 GainGradientThreshold("select-opti-loop-gradient-gain-threshold",
76 cl::desc("Gradient gain threshold (%)."),
77 cl::init(Val: 25), cl::Hidden);
78
79static cl::opt<unsigned>
80 GainCycleThreshold("select-opti-loop-cycle-gain-threshold",
81 cl::desc("Minimum gain per loop (in cycles) threshold."),
82 cl::init(Val: 4), cl::Hidden);
83
84static cl::opt<unsigned> GainRelativeThreshold(
85 "select-opti-loop-relative-gain-threshold",
86 cl::desc(
87 "Minimum relative gain per loop threshold (1/X). Defaults to 12.5%"),
88 cl::init(Val: 8), cl::Hidden);
89
90static cl::opt<unsigned> MispredictDefaultRate(
91 "mispredict-default-rate", cl::Hidden, cl::init(Val: 25),
92 cl::desc("Default mispredict rate (initialized to 25%)."));
93
94static cl::opt<bool>
95 DisableLoopLevelHeuristics("disable-loop-level-heuristics", cl::Hidden,
96 cl::init(Val: false),
97 cl::desc("Disable loop-level heuristics."));
98
99namespace {
100
101class SelectOptimizeImpl {
102 const TargetMachine *TM = nullptr;
103 const TargetSubtargetInfo *TSI = nullptr;
104 const TargetLowering *TLI = nullptr;
105 const TargetTransformInfo *TTI = nullptr;
106 const LoopInfo *LI = nullptr;
107 BlockFrequencyInfo *BFI;
108 ProfileSummaryInfo *PSI = nullptr;
109 OptimizationRemarkEmitter *ORE = nullptr;
110 TargetSchedModel TSchedModel;
111
112public:
113 SelectOptimizeImpl() = default;
114 SelectOptimizeImpl(const TargetMachine *TM) : TM(TM){};
115 PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM);
116 bool runOnFunction(Function &F, Pass &P);
117
118 using Scaled64 = ScaledNumber<uint64_t>;
119
120 struct CostInfo {
121 /// Predicated cost (with selects as conditional moves).
122 Scaled64 PredCost;
123 /// Non-predicated cost (with selects converted to branches).
124 Scaled64 NonPredCost;
125 };
126
127 /// SelectLike is an abstraction over SelectInst and other operations that can
128 /// act like selects. For example Or(Zext(icmp), X) can be treated like
129 /// select(icmp, X|1, X).
130 class SelectLike {
131 /// The select (/or) instruction.
132 Instruction *I;
133 /// Whether this select is inverted, "not(cond), FalseVal, TrueVal", as
134 /// opposed to the original condition.
135 bool Inverted = false;
136
137 /// The index of the operand that depends on condition. Only for select-like
138 /// instruction such as Or/Add.
139 unsigned CondIdx;
140
141 public:
142 SelectLike(Instruction *I, bool Inverted = false, unsigned CondIdx = 0)
143 : I(I), Inverted(Inverted), CondIdx(CondIdx) {}
144
145 Instruction *getI() { return I; }
146 const Instruction *getI() const { return I; }
147
148 Type *getType() const { return I->getType(); }
149
150 unsigned getConditionOpIndex() { return CondIdx; };
151
152 /// Return the true value for the SelectLike instruction. Note this may not
153 /// exist for all SelectLike instructions. For example, for `or(zext(c), x)`
154 /// the true value would be `or(x,1)`. As this value does not exist, nullptr
155 /// is returned.
156 Value *getTrueValue(bool HonorInverts = true) const {
157 if (Inverted && HonorInverts)
158 return getFalseValue(/*HonorInverts=*/false);
159 if (auto *Sel = dyn_cast<SelectInst>(Val: I))
160 return Sel->getTrueValue();
161 // Or(zext) case - The true value is Or(X), so return nullptr as the value
162 // does not yet exist.
163 if (isa<BinaryOperator>(Val: I))
164 return nullptr;
165
166 llvm_unreachable("Unhandled case in getTrueValue");
167 }
168
169 /// Return the false value for the SelectLike instruction. For example the
170 /// getFalseValue of a select or `x` in `or(zext(c), x)` (which is
171 /// `select(c, x|1, x)`)
172 Value *getFalseValue(bool HonorInverts = true) const {
173 if (Inverted && HonorInverts)
174 return getTrueValue(/*HonorInverts=*/false);
175 if (auto *Sel = dyn_cast<SelectInst>(Val: I))
176 return Sel->getFalseValue();
177 // We are on the branch where the condition is zero, which means BinOp
178 // does not perform any computation, and we can simply return the operand
179 // that is not related to the condition
180 if (auto *BO = dyn_cast<BinaryOperator>(Val: I))
181 return BO->getOperand(i_nocapture: 1 - CondIdx);
182
183 llvm_unreachable("Unhandled case in getFalseValue");
184 }
185
186 /// Return the NonPredCost cost of the op on \p isTrue branch, given the
187 /// costs in \p InstCostMap. This may need to be generated for select-like
188 /// instructions.
189 Scaled64 getOpCostOnBranch(
190 bool IsTrue, const DenseMap<const Instruction *, CostInfo> &InstCostMap,
191 const TargetTransformInfo *TTI) {
192 auto *V = IsTrue ? getTrueValue() : getFalseValue();
193 if (V) {
194 if (auto *IV = dyn_cast<Instruction>(Val: V)) {
195 auto It = InstCostMap.find(Val: IV);
196 return It != InstCostMap.end() ? It->second.NonPredCost
197 : Scaled64::getZero();
198 }
199 return Scaled64::getZero();
200 }
201 // If getTrue(False)Value() return nullptr, it means we are dealing with
202 // select-like instructions on the branch where the actual computation is
203 // happening. In that case the cost is equal to the cost of computation +
204 // cost of non-dependant on condition operand
205 InstructionCost Cost = TTI->getArithmeticInstrCost(
206 Opcode: getI()->getOpcode(), Ty: I->getType(), CostKind: TargetTransformInfo::TCK_Latency,
207 Opd1Info: {.Kind: TargetTransformInfo::OK_AnyValue, .Properties: TargetTransformInfo::OP_None},
208 Opd2Info: {.Kind: TTI::OK_UniformConstantValue, .Properties: TTI::OP_PowerOf2});
209 auto TotalCost = Scaled64::get(N: Cost.getValue());
210 if (auto *OpI = dyn_cast<Instruction>(Val: I->getOperand(i: 1 - CondIdx))) {
211 auto It = InstCostMap.find(Val: OpI);
212 if (It != InstCostMap.end())
213 TotalCost += It->second.NonPredCost;
214 }
215 return TotalCost;
216 }
217 };
218
219private:
220 // Select groups consist of consecutive select-like instructions with the same
221 // condition. Between select-likes could be any number of auxiliary
222 // instructions related to the condition like not, zext, ashr/lshr
223 struct SelectGroup {
224 Value *Condition;
225 SmallVector<SelectLike, 2> Selects;
226 };
227 using SelectGroups = SmallVector<SelectGroup, 2>;
228
229 // Converts select instructions of a function to conditional jumps when deemed
230 // profitable. Returns true if at least one select was converted.
231 bool optimizeSelects(Function &F);
232
233 // Heuristics for determining which select instructions can be profitably
234 // conveted to branches. Separate heuristics for selects in inner-most loops
235 // and the rest of code regions (base heuristics for non-inner-most loop
236 // regions).
237 void optimizeSelectsBase(Function &F, SelectGroups &ProfSIGroups);
238 void optimizeSelectsInnerLoops(Function &F, SelectGroups &ProfSIGroups);
239
240 // Converts to branches the select groups that were deemed
241 // profitable-to-convert.
242 void convertProfitableSIGroups(SelectGroups &ProfSIGroups);
243
244 // Splits selects of a given basic block into select groups.
245 void collectSelectGroups(BasicBlock &BB, SelectGroups &SIGroups);
246
247 // Determines for which select groups it is profitable converting to branches
248 // (base and inner-most-loop heuristics).
249 void findProfitableSIGroupsBase(SelectGroups &SIGroups,
250 SelectGroups &ProfSIGroups);
251 void findProfitableSIGroupsInnerLoops(const Loop *L, SelectGroups &SIGroups,
252 SelectGroups &ProfSIGroups);
253
254 // Determines if a select group should be converted to a branch (base
255 // heuristics).
256 bool isConvertToBranchProfitableBase(const SelectGroup &ASI);
257
258 // Returns true if there are expensive instructions in the cold value
259 // operand's (if any) dependence slice of any of the selects of the given
260 // group.
261 bool hasExpensiveColdOperand(const SelectGroup &ASI);
262
263 // For a given source instruction, collect its backwards dependence slice
264 // consisting of instructions exclusively computed for producing the operands
265 // of the source instruction.
266 void getExclBackwardsSlice(Instruction *I, std::stack<Instruction *> &Slice,
267 Instruction *SI, bool ForSinking = false);
268
269 // Returns true if the condition of the select is highly predictable.
270 bool isSelectHighlyPredictable(const SelectLike SI);
271
272 // Loop-level checks to determine if a non-predicated version (with branches)
273 // of the given loop is more profitable than its predicated version.
274 bool checkLoopHeuristics(const Loop *L, const CostInfo LoopDepth[2]);
275
276 // Computes instruction and loop-critical-path costs for both the predicated
277 // and non-predicated version of the given loop.
278 bool computeLoopCosts(const Loop *L, const SelectGroups &SIGroups,
279 DenseMap<const Instruction *, CostInfo> &InstCostMap,
280 CostInfo *LoopCost);
281
282 // Returns a set of all the select instructions in the given select groups.
283 SmallDenseMap<const Instruction *, SelectLike, 2>
284 getSImap(const SelectGroups &SIGroups);
285
286 // Returns a map from select-like instructions to the corresponding select
287 // group.
288 SmallDenseMap<const Instruction *, const SelectGroup *, 2>
289 getSGmap(const SelectGroups &SIGroups);
290
291 // Returns the latency cost of a given instruction.
292 std::optional<uint64_t> computeInstCost(const Instruction *I);
293
294 // Returns the misprediction cost of a given select when converted to branch.
295 Scaled64 getMispredictionCost(const SelectLike SI, const Scaled64 CondCost);
296
297 // Returns the cost of a branch when the prediction is correct.
298 Scaled64 getPredictedPathCost(Scaled64 TrueCost, Scaled64 FalseCost,
299 const SelectLike SI);
300
301 // Returns true if the target architecture supports lowering a given select.
302 bool isSelectKindSupported(const SelectLike SI);
303};
304
305class SelectOptimize : public FunctionPass {
306 SelectOptimizeImpl Impl;
307
308public:
309 static char ID;
310
311 SelectOptimize() : FunctionPass(ID) {
312 initializeSelectOptimizePass(*PassRegistry::getPassRegistry());
313 }
314
315 bool runOnFunction(Function &F) override {
316 return Impl.runOnFunction(F, P&: *this);
317 }
318
319 void getAnalysisUsage(AnalysisUsage &AU) const override {
320 AU.addRequired<ProfileSummaryInfoWrapperPass>();
321 AU.addRequired<TargetPassConfig>();
322 AU.addRequired<TargetTransformInfoWrapperPass>();
323 AU.addRequired<LoopInfoWrapperPass>();
324 AU.addRequired<BlockFrequencyInfoWrapperPass>();
325 AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
326 }
327};
328
329} // namespace
330
331PreservedAnalyses SelectOptimizePass::run(Function &F,
332 FunctionAnalysisManager &FAM) {
333 SelectOptimizeImpl Impl(TM);
334 return Impl.run(F, FAM);
335}
336
337char SelectOptimize::ID = 0;
338
339INITIALIZE_PASS_BEGIN(SelectOptimize, DEBUG_TYPE, "Optimize selects", false,
340 false)
341INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
342INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
343INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
344INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
345INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
346INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)
347INITIALIZE_PASS_END(SelectOptimize, DEBUG_TYPE, "Optimize selects", false,
348 false)
349
350FunctionPass *llvm::createSelectOptimizePass() { return new SelectOptimize(); }
351
352PreservedAnalyses SelectOptimizeImpl::run(Function &F,
353 FunctionAnalysisManager &FAM) {
354 TSI = TM->getSubtargetImpl(F);
355 TLI = TSI->getTargetLowering();
356
357 // If none of the select types are supported then skip this pass.
358 // This is an optimization pass. Legality issues will be handled by
359 // instruction selection.
360 if (!TLI->isSelectSupported(TargetLowering::ScalarValSelect) &&
361 !TLI->isSelectSupported(TargetLowering::ScalarCondVectorVal) &&
362 !TLI->isSelectSupported(TargetLowering::VectorMaskSelect))
363 return PreservedAnalyses::all();
364
365 TTI = &FAM.getResult<TargetIRAnalysis>(IR&: F);
366 if (!TTI->enableSelectOptimize())
367 return PreservedAnalyses::all();
368
369 PSI = FAM.getResult<ModuleAnalysisManagerFunctionProxy>(IR&: F)
370 .getCachedResult<ProfileSummaryAnalysis>(IR&: *F.getParent());
371 assert(PSI && "This pass requires module analysis pass `profile-summary`!");
372 BFI = &FAM.getResult<BlockFrequencyAnalysis>(IR&: F);
373
374 // When optimizing for size, selects are preferable over branches.
375 if (llvm::shouldOptimizeForSize(F: &F, PSI, BFI))
376 return PreservedAnalyses::all();
377
378 LI = &FAM.getResult<LoopAnalysis>(IR&: F);
379 ORE = &FAM.getResult<OptimizationRemarkEmitterAnalysis>(IR&: F);
380 TSchedModel.init(TSInfo: TSI);
381
382 bool Changed = optimizeSelects(F);
383 return Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
384}
385
386bool SelectOptimizeImpl::runOnFunction(Function &F, Pass &P) {
387 TM = &P.getAnalysis<TargetPassConfig>().getTM<TargetMachine>();
388 TSI = TM->getSubtargetImpl(F);
389 TLI = TSI->getTargetLowering();
390
391 // If none of the select types are supported then skip this pass.
392 // This is an optimization pass. Legality issues will be handled by
393 // instruction selection.
394 if (!TLI->isSelectSupported(TargetLowering::ScalarValSelect) &&
395 !TLI->isSelectSupported(TargetLowering::ScalarCondVectorVal) &&
396 !TLI->isSelectSupported(TargetLowering::VectorMaskSelect))
397 return false;
398
399 TTI = &P.getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
400
401 if (!TTI->enableSelectOptimize())
402 return false;
403
404 LI = &P.getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
405 BFI = &P.getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI();
406 PSI = &P.getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
407 ORE = &P.getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
408 TSchedModel.init(TSInfo: TSI);
409
410 // When optimizing for size, selects are preferable over branches.
411 if (llvm::shouldOptimizeForSize(F: &F, PSI, BFI))
412 return false;
413
414 return optimizeSelects(F);
415}
416
417bool SelectOptimizeImpl::optimizeSelects(Function &F) {
418 // Determine for which select groups it is profitable converting to branches.
419 SelectGroups ProfSIGroups;
420 // Base heuristics apply only to non-loops and outer loops.
421 optimizeSelectsBase(F, ProfSIGroups);
422 // Separate heuristics for inner-most loops.
423 optimizeSelectsInnerLoops(F, ProfSIGroups);
424
425 // Convert to branches the select groups that were deemed
426 // profitable-to-convert.
427 convertProfitableSIGroups(ProfSIGroups);
428
429 // Code modified if at least one select group was converted.
430 return !ProfSIGroups.empty();
431}
432
433void SelectOptimizeImpl::optimizeSelectsBase(Function &F,
434 SelectGroups &ProfSIGroups) {
435 // Collect all the select groups.
436 SelectGroups SIGroups;
437 for (BasicBlock &BB : F) {
438 // Base heuristics apply only to non-loops and outer loops.
439 Loop *L = LI->getLoopFor(BB: &BB);
440 if (L && L->isInnermost())
441 continue;
442 collectSelectGroups(BB, SIGroups);
443 }
444
445 // Determine for which select groups it is profitable converting to branches.
446 findProfitableSIGroupsBase(SIGroups, ProfSIGroups);
447}
448
449void SelectOptimizeImpl::optimizeSelectsInnerLoops(Function &F,
450 SelectGroups &ProfSIGroups) {
451 SmallVector<Loop *, 4> Loops(LI->begin(), LI->end());
452 // Need to check size on each iteration as we accumulate child loops.
453 for (unsigned long i = 0; i < Loops.size(); ++i)
454 llvm::append_range(C&: Loops, R: Loops[i]->getSubLoops());
455
456 for (Loop *L : Loops) {
457 if (!L->isInnermost())
458 continue;
459
460 SelectGroups SIGroups;
461 for (BasicBlock *BB : L->getBlocks())
462 collectSelectGroups(BB&: *BB, SIGroups);
463
464 findProfitableSIGroupsInnerLoops(L, SIGroups, ProfSIGroups);
465 }
466}
467
468/// Returns optimised value on \p IsTrue branch. For SelectInst that would be
469/// either True or False value. For (BinaryOperator) instructions, where the
470/// condition may be skipped, the operation will use a non-conditional operand.
471/// For example, for `or(V,zext(cond))` this function would return V.
472/// However, if the conditional operand on \p IsTrue branch matters, we create a
473/// clone of instruction at the end of that branch \p B and replace the
474/// condition operand with a constant.
475///
476/// Also /p OptSelects contains previously optimised select-like instructions.
477/// If the current value uses one of the optimised values, we can optimise it
478/// further by replacing it with the corresponding value on the given branch
479static Value *getTrueOrFalseValue(
480 SelectOptimizeImpl::SelectLike &SI, bool isTrue,
481 SmallDenseMap<Instruction *, std::pair<Value *, Value *>, 2> &OptSelects,
482 BasicBlock *B) {
483 Value *V = isTrue ? SI.getTrueValue() : SI.getFalseValue();
484 if (V) {
485 if (auto *IV = dyn_cast<Instruction>(Val: V))
486 if (auto It = OptSelects.find(Val: IV); It != OptSelects.end())
487 return isTrue ? It->second.first : It->second.second;
488 return V;
489 }
490
491 auto *BO = cast<BinaryOperator>(Val: SI.getI());
492 assert((BO->getOpcode() == Instruction::Add ||
493 BO->getOpcode() == Instruction::Or ||
494 BO->getOpcode() == Instruction::Sub) &&
495 "Only currently handling Add, Or and Sub binary operators.");
496
497 auto *CBO = BO->clone();
498 auto CondIdx = SI.getConditionOpIndex();
499 auto *AuxI = cast<Instruction>(Val: CBO->getOperand(i: CondIdx));
500 if (isa<ZExtInst>(Val: AuxI) || isa<LShrOperator>(Val: AuxI)) {
501 CBO->setOperand(i: CondIdx, Val: ConstantInt::get(Ty: CBO->getType(), V: 1));
502 } else {
503 assert((isa<AShrOperator>(AuxI) || isa<SExtInst>(AuxI)) &&
504 "Unexpected opcode");
505 CBO->setOperand(i: CondIdx, Val: ConstantInt::get(Ty: CBO->getType(), V: -1));
506 }
507
508 unsigned OtherIdx = 1 - CondIdx;
509 if (auto *IV = dyn_cast<Instruction>(Val: CBO->getOperand(i: OtherIdx))) {
510 if (auto It = OptSelects.find(Val: IV); It != OptSelects.end())
511 CBO->setOperand(i: OtherIdx, Val: isTrue ? It->second.first : It->second.second);
512 }
513 CBO->insertBefore(InsertPos: B->getTerminator()->getIterator());
514 return CBO;
515}
516
517void SelectOptimizeImpl::convertProfitableSIGroups(SelectGroups &ProfSIGroups) {
518 for (SelectGroup &ASI : ProfSIGroups) {
519 // The code transformation here is a modified version of the sinking
520 // transformation in CodeGenPrepare::optimizeSelectInst with a more
521 // aggressive strategy of which instructions to sink.
522 //
523 // TODO: eliminate the redundancy of logic transforming selects to branches
524 // by removing CodeGenPrepare::optimizeSelectInst and optimizing here
525 // selects for all cases (with and without profile information).
526
527 // Transform a sequence like this:
528 // start:
529 // %cmp = cmp uge i32 %a, %b
530 // %sel = select i1 %cmp, i32 %c, i32 %d
531 //
532 // Into:
533 // start:
534 // %cmp = cmp uge i32 %a, %b
535 // %cmp.frozen = freeze %cmp
536 // br i1 %cmp.frozen, label %select.true, label %select.false
537 // select.true:
538 // br label %select.end
539 // select.false:
540 // br label %select.end
541 // select.end:
542 // %sel = phi i32 [ %c, %select.true ], [ %d, %select.false ]
543 //
544 // %cmp should be frozen, otherwise it may introduce undefined behavior.
545 // In addition, we may sink instructions that produce %c or %d into the
546 // destination(s) of the new branch.
547 // If the true or false blocks do not contain a sunken instruction, that
548 // block and its branch may be optimized away. In that case, one side of the
549 // first branch will point directly to select.end, and the corresponding PHI
550 // predecessor block will be the start block.
551
552 // Find all the instructions that can be soundly sunk to the true/false
553 // blocks. These are instructions that are computed solely for producing the
554 // operands of the select instructions in the group and can be sunk without
555 // breaking the semantics of the LLVM IR (e.g., cannot sink instructions
556 // with side effects).
557 SmallVector<std::stack<Instruction *>, 2> TrueSlices, FalseSlices;
558 typedef std::stack<Instruction *>::size_type StackSizeType;
559 StackSizeType maxTrueSliceLen = 0, maxFalseSliceLen = 0;
560 for (SelectLike &SI : ASI.Selects) {
561 if (!isa<SelectInst>(Val: SI.getI()))
562 continue;
563 // For each select, compute the sinkable dependence chains of the true and
564 // false operands.
565 if (auto *TI = dyn_cast_or_null<Instruction>(Val: SI.getTrueValue())) {
566 std::stack<Instruction *> TrueSlice;
567 getExclBackwardsSlice(I: TI, Slice&: TrueSlice, SI: SI.getI(), ForSinking: true);
568 maxTrueSliceLen = std::max(a: maxTrueSliceLen, b: TrueSlice.size());
569 TrueSlices.push_back(Elt: TrueSlice);
570 }
571 if (auto *FI = dyn_cast_or_null<Instruction>(Val: SI.getFalseValue())) {
572 if (isa<SelectInst>(Val: SI.getI()) || !FI->hasOneUse()) {
573 std::stack<Instruction *> FalseSlice;
574 getExclBackwardsSlice(I: FI, Slice&: FalseSlice, SI: SI.getI(), ForSinking: true);
575 maxFalseSliceLen = std::max(a: maxFalseSliceLen, b: FalseSlice.size());
576 FalseSlices.push_back(Elt: FalseSlice);
577 }
578 }
579 }
580 // In the case of multiple select instructions in the same group, the order
581 // of non-dependent instructions (instructions of different dependence
582 // slices) in the true/false blocks appears to affect performance.
583 // Interleaving the slices seems to experimentally be the optimal approach.
584 // This interleaving scheduling allows for more ILP (with a natural downside
585 // of increasing a bit register pressure) compared to a simple ordering of
586 // one whole chain after another. One would expect that this ordering would
587 // not matter since the scheduling in the backend of the compiler would
588 // take care of it, but apparently the scheduler fails to deliver optimal
589 // ILP with a naive ordering here.
590 SmallVector<Instruction *, 2> TrueSlicesInterleaved, FalseSlicesInterleaved;
591 for (StackSizeType IS = 0; IS < maxTrueSliceLen; ++IS) {
592 for (auto &S : TrueSlices) {
593 if (!S.empty()) {
594 TrueSlicesInterleaved.push_back(Elt: S.top());
595 S.pop();
596 }
597 }
598 }
599 for (StackSizeType IS = 0; IS < maxFalseSliceLen; ++IS) {
600 for (auto &S : FalseSlices) {
601 if (!S.empty()) {
602 FalseSlicesInterleaved.push_back(Elt: S.top());
603 S.pop();
604 }
605 }
606 }
607
608 // We split the block containing the select(s) into two blocks.
609 SelectLike &SI = ASI.Selects.front();
610 SelectLike &LastSI = ASI.Selects.back();
611 BasicBlock *StartBlock = SI.getI()->getParent();
612 BasicBlock::iterator SplitPt = ++(BasicBlock::iterator(LastSI.getI()));
613 // With RemoveDIs turned off, SplitPt can be a dbg.* intrinsic. With
614 // RemoveDIs turned on, SplitPt would instead point to the next
615 // instruction. To match existing dbg.* intrinsic behaviour with RemoveDIs,
616 // tell splitBasicBlock that we want to include any DbgVariableRecords
617 // attached to SplitPt in the splice.
618 SplitPt.setHeadBit(true);
619 BasicBlock *EndBlock = StartBlock->splitBasicBlock(I: SplitPt, BBName: "select.end");
620 BFI->setBlockFreq(BB: EndBlock, Freq: BFI->getBlockFreq(BB: StartBlock));
621 // Delete the unconditional branch that was just created by the split.
622 StartBlock->getTerminator()->eraseFromParent();
623
624 // Move any debug/pseudo and auxiliary instructions that were in-between the
625 // select group to the newly-created end block.
626 SmallVector<Instruction *, 2> SinkInstrs;
627 auto DIt = SI.getI()->getIterator();
628 auto NIt = ASI.Selects.begin();
629 while (&*DIt != LastSI.getI()) {
630 if (NIt != ASI.Selects.end() && &*DIt == NIt->getI())
631 ++NIt;
632 else
633 SinkInstrs.push_back(Elt: &*DIt);
634 DIt++;
635 }
636 auto InsertionPoint = EndBlock->getFirstInsertionPt();
637 for (auto *DI : SinkInstrs)
638 DI->moveBeforePreserving(MovePos: InsertionPoint);
639
640 // Duplicate implementation for DbgRecords, the non-instruction debug-info
641 // format. Helper lambda for moving DbgRecords to the end block.
642 auto TransferDbgRecords = [&](Instruction &I) {
643 for (auto &DbgRecord :
644 llvm::make_early_inc_range(Range: I.getDbgRecordRange())) {
645 DbgRecord.removeFromParent();
646 EndBlock->insertDbgRecordBefore(DR: &DbgRecord,
647 Here: EndBlock->getFirstInsertionPt());
648 }
649 };
650
651 // Iterate over all instructions in between SI and LastSI, not including
652 // SI itself. These are all the variable assignments that happen "in the
653 // middle" of the select group.
654 auto R = make_range(x: std::next(x: SI.getI()->getIterator()),
655 y: std::next(x: LastSI.getI()->getIterator()));
656 llvm::for_each(Range&: R, F: TransferDbgRecords);
657
658 // These are the new basic blocks for the conditional branch.
659 // At least one will become an actual new basic block.
660 BasicBlock *TrueBlock = nullptr, *FalseBlock = nullptr;
661 BranchInst *TrueBranch = nullptr, *FalseBranch = nullptr;
662 // Checks if select-like instruction would materialise on the given branch
663 auto HasSelectLike = [](SelectGroup &SG, bool IsTrue) {
664 for (auto &SL : SG.Selects) {
665 if ((IsTrue ? SL.getTrueValue() : SL.getFalseValue()) == nullptr)
666 return true;
667 }
668 return false;
669 };
670 if (!TrueSlicesInterleaved.empty() || HasSelectLike(ASI, true)) {
671 TrueBlock = BasicBlock::Create(Context&: EndBlock->getContext(), Name: "select.true.sink",
672 Parent: EndBlock->getParent(), InsertBefore: EndBlock);
673 TrueBranch = BranchInst::Create(IfTrue: EndBlock, InsertBefore: TrueBlock);
674 TrueBranch->setDebugLoc(LastSI.getI()->getDebugLoc());
675 for (Instruction *TrueInst : TrueSlicesInterleaved)
676 TrueInst->moveBefore(InsertPos: TrueBranch->getIterator());
677 }
678 if (!FalseSlicesInterleaved.empty() || HasSelectLike(ASI, false)) {
679 FalseBlock =
680 BasicBlock::Create(Context&: EndBlock->getContext(), Name: "select.false.sink",
681 Parent: EndBlock->getParent(), InsertBefore: EndBlock);
682 FalseBranch = BranchInst::Create(IfTrue: EndBlock, InsertBefore: FalseBlock);
683 FalseBranch->setDebugLoc(LastSI.getI()->getDebugLoc());
684 for (Instruction *FalseInst : FalseSlicesInterleaved)
685 FalseInst->moveBefore(InsertPos: FalseBranch->getIterator());
686 }
687 // If there was nothing to sink, then arbitrarily choose the 'false' side
688 // for a new input value to the PHI.
689 if (TrueBlock == FalseBlock) {
690 assert(TrueBlock == nullptr &&
691 "Unexpected basic block transform while optimizing select");
692
693 FalseBlock = BasicBlock::Create(Context&: StartBlock->getContext(), Name: "select.false",
694 Parent: EndBlock->getParent(), InsertBefore: EndBlock);
695 auto *FalseBranch = BranchInst::Create(IfTrue: EndBlock, InsertBefore: FalseBlock);
696 FalseBranch->setDebugLoc(SI.getI()->getDebugLoc());
697 }
698
699 // Insert the real conditional branch based on the original condition.
700 // If we did not create a new block for one of the 'true' or 'false' paths
701 // of the condition, it means that side of the branch goes to the end block
702 // directly and the path originates from the start block from the point of
703 // view of the new PHI.
704 BasicBlock *TT, *FT;
705 if (TrueBlock == nullptr) {
706 TT = EndBlock;
707 FT = FalseBlock;
708 TrueBlock = StartBlock;
709 } else if (FalseBlock == nullptr) {
710 TT = TrueBlock;
711 FT = EndBlock;
712 FalseBlock = StartBlock;
713 } else {
714 TT = TrueBlock;
715 FT = FalseBlock;
716 }
717 IRBuilder<> IB(SI.getI());
718 auto *CondFr =
719 IB.CreateFreeze(V: ASI.Condition, Name: ASI.Condition->getName() + ".frozen");
720
721 SmallDenseMap<Instruction *, std::pair<Value *, Value *>, 2> INS;
722
723 // Use reverse iterator because later select may use the value of the
724 // earlier select, and we need to propagate value through earlier select
725 // to get the PHI operand.
726 InsertionPoint = EndBlock->begin();
727 for (SelectLike &SI : ASI.Selects) {
728 // The select itself is replaced with a PHI Node.
729 PHINode *PN = PHINode::Create(Ty: SI.getType(), NumReservedValues: 2, NameStr: "");
730 PN->insertBefore(InsertPos: InsertionPoint);
731 PN->takeName(V: SI.getI());
732 // Current instruction might be a condition of some other group, so we
733 // need to replace it there to avoid dangling pointer
734 if (PN->getType()->isIntegerTy(Bitwidth: 1)) {
735 for (auto &SG : ProfSIGroups) {
736 if (SG.Condition == SI.getI())
737 SG.Condition = PN;
738 }
739 }
740 SI.getI()->replaceAllUsesWith(V: PN);
741 auto *TV = getTrueOrFalseValue(SI, isTrue: true, OptSelects&: INS, B: TrueBlock);
742 auto *FV = getTrueOrFalseValue(SI, isTrue: false, OptSelects&: INS, B: FalseBlock);
743 INS[PN] = {TV, FV};
744 PN->addIncoming(V: TV, BB: TrueBlock);
745 PN->addIncoming(V: FV, BB: FalseBlock);
746 PN->setDebugLoc(SI.getI()->getDebugLoc());
747 ++NumSelectsConverted;
748 }
749 IB.CreateCondBr(Cond: CondFr, True: TT, False: FT, MDSrc: SI.getI());
750
751 // Remove the old select instructions, now that they are not longer used.
752 for (SelectLike &SI : ASI.Selects)
753 SI.getI()->eraseFromParent();
754 }
755}
756
757void SelectOptimizeImpl::collectSelectGroups(BasicBlock &BB,
758 SelectGroups &SIGroups) {
759 // Represents something that can be considered as select instruction.
760 // Auxiliary instruction are instructions that depends on a condition and have
761 // zero or some constant value on True/False branch, such as:
762 // * ZExt(1bit)
763 // * SExt(1bit)
764 // * Not(1bit)
765 // * A(L)Shr(Val), ValBitSize - 1, where there is a condition like `Val <= 0`
766 // earlier in the BB. For conditions that check the sign of the Val compiler
767 // may generate shifts instead of ZExt/SExt.
768 struct SelectLikeInfo {
769 Value *Cond;
770 bool IsAuxiliary;
771 bool IsInverted;
772 unsigned ConditionIdx;
773 };
774
775 DenseMap<Value *, SelectLikeInfo> SelectInfo;
776 // Keeps visited comparisons to help identify AShr/LShr variants of auxiliary
777 // instructions.
778 SmallSetVector<CmpInst *, 4> SeenCmp;
779
780 // Check if the instruction is SelectLike or might be part of SelectLike
781 // expression, put information into SelectInfo and return the iterator to the
782 // inserted position.
783 auto ProcessSelectInfo = [&SelectInfo, &SeenCmp](Instruction *I) {
784 if (auto *Cmp = dyn_cast<CmpInst>(Val: I)) {
785 SeenCmp.insert(X: Cmp);
786 return SelectInfo.end();
787 }
788
789 Value *Cond;
790 if (match(V: I, P: m_OneUse(SubPattern: m_ZExtOrSExt(Op: m_Value(V&: Cond)))) &&
791 Cond->getType()->isIntegerTy(Bitwidth: 1)) {
792 bool Inverted = match(V: Cond, P: m_Not(V: m_Value(V&: Cond)));
793 return SelectInfo.insert(KV: {I, {.Cond: Cond, .IsAuxiliary: true, .IsInverted: Inverted, .ConditionIdx: 0}}).first;
794 }
795
796 if (match(V: I, P: m_Not(V: m_Value(V&: Cond)))) {
797 return SelectInfo.insert(KV: {I, {.Cond: Cond, .IsAuxiliary: true, .IsInverted: true, .ConditionIdx: 0}}).first;
798 }
799
800 // Select instruction are what we are usually looking for.
801 if (match(V: I, P: m_Select(C: m_Value(V&: Cond), L: m_Value(), R: m_Value()))) {
802 bool Inverted = match(V: Cond, P: m_Not(V: m_Value(V&: Cond)));
803 return SelectInfo.insert(KV: {I, {.Cond: Cond, .IsAuxiliary: false, .IsInverted: Inverted, .ConditionIdx: 0}}).first;
804 }
805 Value *Val;
806 ConstantInt *Shift;
807 if (match(V: I, P: m_Shr(L: m_Value(V&: Val), R: m_ConstantInt(CI&: Shift))) &&
808 I->getType()->getIntegerBitWidth() == Shift->getZExtValue() + 1) {
809 for (auto *CmpI : SeenCmp) {
810 auto Pred = CmpI->getPredicate();
811 if (Val != CmpI->getOperand(i_nocapture: 0))
812 continue;
813 if ((Pred == CmpInst::ICMP_SGT &&
814 match(V: CmpI->getOperand(i_nocapture: 1), P: m_ConstantInt<-1>())) ||
815 (Pred == CmpInst::ICMP_SGE &&
816 match(V: CmpI->getOperand(i_nocapture: 1), P: m_Zero())) ||
817 (Pred == CmpInst::ICMP_SLT &&
818 match(V: CmpI->getOperand(i_nocapture: 1), P: m_Zero())) ||
819 (Pred == CmpInst::ICMP_SLE &&
820 match(V: CmpI->getOperand(i_nocapture: 1), P: m_ConstantInt<-1>()))) {
821 bool Inverted =
822 Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_SGE;
823 return SelectInfo.insert(KV: {I, {.Cond: CmpI, .IsAuxiliary: true, .IsInverted: Inverted, .ConditionIdx: 0}}).first;
824 }
825 }
826 return SelectInfo.end();
827 }
828
829 // An BinOp(Aux(X), Y) can also be treated like a select, with condition X
830 // and values Y|1 and Y.
831 // `Aux` can be either `ZExt(1bit)`, `SExt(1bit)` or `XShr(Val), ValBitSize
832 // - 1` `BinOp` can be Add, Sub, Or
833 Value *X;
834 auto MatchZExtOrSExtPattern =
835 m_c_BinOp(L: m_Value(), R: m_OneUse(SubPattern: m_ZExtOrSExt(Op: m_Value(V&: X))));
836 auto MatchShiftPattern =
837 m_c_BinOp(L: m_Value(), R: m_OneUse(SubPattern: m_Shr(L: m_Value(V&: X), R: m_ConstantInt(CI&: Shift))));
838
839 // This check is unnecessary, but it prevents costly access to the
840 // SelectInfo map.
841 if ((match(V: I, P: MatchZExtOrSExtPattern) && X->getType()->isIntegerTy(Bitwidth: 1)) ||
842 (match(V: I, P: MatchShiftPattern) &&
843 X->getType()->getIntegerBitWidth() == Shift->getZExtValue() + 1)) {
844 if (I->getOpcode() != Instruction::Add &&
845 I->getOpcode() != Instruction::Sub &&
846 I->getOpcode() != Instruction::Or)
847 return SelectInfo.end();
848
849 if (I->getOpcode() == Instruction::Or && I->getType()->isIntegerTy(Bitwidth: 1))
850 return SelectInfo.end();
851
852 // Iterate through operands and find dependant on recognised sign
853 // extending auxiliary select-like instructions. The operand index does
854 // not matter for Add and Or. However, for Sub, we can only safely
855 // transform when the operand is second.
856 unsigned Idx = I->getOpcode() == Instruction::Sub ? 1 : 0;
857 for (; Idx < 2; Idx++) {
858 auto *Op = I->getOperand(i: Idx);
859 auto It = SelectInfo.find(Val: Op);
860 if (It != SelectInfo.end() && It->second.IsAuxiliary) {
861 Cond = It->second.Cond;
862 bool Inverted = It->second.IsInverted;
863 return SelectInfo.insert(KV: {I, {.Cond: Cond, .IsAuxiliary: false, .IsInverted: Inverted, .ConditionIdx: Idx}}).first;
864 }
865 }
866 }
867 return SelectInfo.end();
868 };
869
870 bool AlreadyProcessed = false;
871 BasicBlock::iterator BBIt = BB.begin();
872 DenseMap<Value *, SelectLikeInfo>::iterator It;
873 while (BBIt != BB.end()) {
874 Instruction *I = &*BBIt++;
875 if (I->isDebugOrPseudoInst())
876 continue;
877
878 if (!AlreadyProcessed)
879 It = ProcessSelectInfo(I);
880 else
881 AlreadyProcessed = false;
882
883 if (It == SelectInfo.end() || It->second.IsAuxiliary)
884 continue;
885
886 if (!TTI->shouldTreatInstructionLikeSelect(I))
887 continue;
888
889 Value *Cond = It->second.Cond;
890 // Vector conditions are not supported.
891 if (!Cond->getType()->isIntegerTy(Bitwidth: 1))
892 continue;
893
894 SelectGroup SIGroup = {.Condition: Cond, .Selects: {}};
895 SIGroup.Selects.emplace_back(Args&: I, Args&: It->second.IsInverted,
896 Args&: It->second.ConditionIdx);
897
898 // If the select type is not supported, no point optimizing it.
899 // Instruction selection will take care of it.
900 if (!isSelectKindSupported(SI: SIGroup.Selects.front()))
901 continue;
902
903 while (BBIt != BB.end()) {
904 Instruction *NI = &*BBIt;
905 // Debug/pseudo instructions should be skipped and not prevent the
906 // formation of a select group.
907 if (NI->isDebugOrPseudoInst()) {
908 ++BBIt;
909 continue;
910 }
911
912 It = ProcessSelectInfo(NI);
913 if (It == SelectInfo.end()) {
914 AlreadyProcessed = true;
915 break;
916 }
917
918 // Auxiliary with same condition
919 auto [CurrCond, IsAux, IsRev, CondIdx] = It->second;
920 if (Cond != CurrCond) {
921 AlreadyProcessed = true;
922 break;
923 }
924
925 if (!IsAux)
926 SIGroup.Selects.emplace_back(Args&: NI, Args&: IsRev, Args&: CondIdx);
927 ++BBIt;
928 }
929 LLVM_DEBUG({
930 dbgs() << "New Select group (" << SIGroup.Selects.size() << ") with\n";
931 for (auto &SI : SIGroup.Selects)
932 dbgs() << " " << *SI.getI() << "\n";
933 });
934
935 SIGroups.push_back(Elt: SIGroup);
936 }
937}
938
939void SelectOptimizeImpl::findProfitableSIGroupsBase(
940 SelectGroups &SIGroups, SelectGroups &ProfSIGroups) {
941 for (SelectGroup &ASI : SIGroups) {
942 ++NumSelectOptAnalyzed;
943 if (isConvertToBranchProfitableBase(ASI))
944 ProfSIGroups.push_back(Elt: ASI);
945 }
946}
947
948static void EmitAndPrintRemark(OptimizationRemarkEmitter *ORE,
949 DiagnosticInfoOptimizationBase &Rem) {
950 LLVM_DEBUG(dbgs() << Rem.getMsg() << "\n");
951 ORE->emit(OptDiag&: Rem);
952}
953
954void SelectOptimizeImpl::findProfitableSIGroupsInnerLoops(
955 const Loop *L, SelectGroups &SIGroups, SelectGroups &ProfSIGroups) {
956 NumSelectOptAnalyzed += SIGroups.size();
957 // For each select group in an inner-most loop,
958 // a branch is more preferable than a select/conditional-move if:
959 // i) conversion to branches for all the select groups of the loop satisfies
960 // loop-level heuristics including reducing the loop's critical path by
961 // some threshold (see SelectOptimizeImpl::checkLoopHeuristics); and
962 // ii) the total cost of the select group is cheaper with a branch compared
963 // to its predicated version. The cost is in terms of latency and the cost
964 // of a select group is the cost of its most expensive select instruction
965 // (assuming infinite resources and thus fully leveraging available ILP).
966
967 DenseMap<const Instruction *, CostInfo> InstCostMap;
968 CostInfo LoopCost[2] = {{.PredCost: Scaled64::getZero(), .NonPredCost: Scaled64::getZero()},
969 {.PredCost: Scaled64::getZero(), .NonPredCost: Scaled64::getZero()}};
970 if (!computeLoopCosts(L, SIGroups, InstCostMap, LoopCost) ||
971 !checkLoopHeuristics(L, LoopDepth: LoopCost)) {
972 return;
973 }
974
975 for (SelectGroup &ASI : SIGroups) {
976 // Assuming infinite resources, the cost of a group of instructions is the
977 // cost of the most expensive instruction of the group.
978 Scaled64 SelectCost = Scaled64::getZero(), BranchCost = Scaled64::getZero();
979 for (SelectLike &SI : ASI.Selects) {
980 const auto &ICM = InstCostMap[SI.getI()];
981 SelectCost = std::max(a: SelectCost, b: ICM.PredCost);
982 BranchCost = std::max(a: BranchCost, b: ICM.NonPredCost);
983 }
984 if (BranchCost < SelectCost) {
985 OptimizationRemark OR(DEBUG_TYPE, "SelectOpti",
986 ASI.Selects.front().getI());
987 OR << "Profitable to convert to branch (loop analysis). BranchCost="
988 << BranchCost.toString() << ", SelectCost=" << SelectCost.toString()
989 << ". ";
990 EmitAndPrintRemark(ORE, Rem&: OR);
991 ++NumSelectConvertedLoop;
992 ProfSIGroups.push_back(Elt: ASI);
993 } else {
994 OptimizationRemarkMissed ORmiss(DEBUG_TYPE, "SelectOpti",
995 ASI.Selects.front().getI());
996 ORmiss << "Select is more profitable (loop analysis). BranchCost="
997 << BranchCost.toString()
998 << ", SelectCost=" << SelectCost.toString() << ". ";
999 EmitAndPrintRemark(ORE, Rem&: ORmiss);
1000 }
1001 }
1002}
1003
1004bool SelectOptimizeImpl::isConvertToBranchProfitableBase(
1005 const SelectGroup &ASI) {
1006 const SelectLike &SI = ASI.Selects.front();
1007 LLVM_DEBUG(dbgs() << "Analyzing select group containing " << *SI.getI()
1008 << "\n");
1009 OptimizationRemark OR(DEBUG_TYPE, "SelectOpti", SI.getI());
1010 OptimizationRemarkMissed ORmiss(DEBUG_TYPE, "SelectOpti", SI.getI());
1011
1012 // Skip cold basic blocks. Better to optimize for size for cold blocks.
1013 if (PSI->isColdBlock(BB: SI.getI()->getParent(), BFI)) {
1014 ++NumSelectColdBB;
1015 ORmiss << "Not converted to branch because of cold basic block. ";
1016 EmitAndPrintRemark(ORE, Rem&: ORmiss);
1017 return false;
1018 }
1019
1020 // If unpredictable, branch form is less profitable.
1021 if (SI.getI()->getMetadata(KindID: LLVMContext::MD_unpredictable)) {
1022 ++NumSelectUnPred;
1023 ORmiss << "Not converted to branch because of unpredictable branch. ";
1024 EmitAndPrintRemark(ORE, Rem&: ORmiss);
1025 return false;
1026 }
1027
1028 // If highly predictable, branch form is more profitable, unless a
1029 // predictable select is inexpensive in the target architecture.
1030 if (isSelectHighlyPredictable(SI) && TLI->isPredictableSelectExpensive()) {
1031 ++NumSelectConvertedHighPred;
1032 OR << "Converted to branch because of highly predictable branch. ";
1033 EmitAndPrintRemark(ORE, Rem&: OR);
1034 return true;
1035 }
1036
1037 // Look for expensive instructions in the cold operand's (if any) dependence
1038 // slice of any of the selects in the group.
1039 if (hasExpensiveColdOperand(ASI)) {
1040 ++NumSelectConvertedExpColdOperand;
1041 OR << "Converted to branch because of expensive cold operand.";
1042 EmitAndPrintRemark(ORE, Rem&: OR);
1043 return true;
1044 }
1045
1046 // If latch has a select group with several elements, it is usually profitable
1047 // to convert it to branches. We let `optimizeSelectsInnerLoops` decide if
1048 // conversion is profitable for innermost loops.
1049 auto *BB = SI.getI()->getParent();
1050 auto *L = LI->getLoopFor(BB);
1051 if (L && !L->isInnermost() && L->getLoopLatch() == BB &&
1052 ASI.Selects.size() >= 3) {
1053 OR << "Converted to branch because select group in the latch block is big.";
1054 EmitAndPrintRemark(ORE, Rem&: OR);
1055 return true;
1056 }
1057
1058 ORmiss << "Not profitable to convert to branch (base heuristic).";
1059 EmitAndPrintRemark(ORE, Rem&: ORmiss);
1060 return false;
1061}
1062
1063static InstructionCost divideNearest(InstructionCost Numerator,
1064 uint64_t Denominator) {
1065 return (Numerator + (Denominator / 2)) / Denominator;
1066}
1067
1068static bool extractBranchWeights(const SelectOptimizeImpl::SelectLike SI,
1069 uint64_t &TrueVal, uint64_t &FalseVal) {
1070 if (isa<SelectInst>(Val: SI.getI()))
1071 return extractBranchWeights(I: *SI.getI(), TrueVal, FalseVal);
1072 return false;
1073}
1074
1075bool SelectOptimizeImpl::hasExpensiveColdOperand(const SelectGroup &ASI) {
1076 bool ColdOperand = false;
1077 uint64_t TrueWeight, FalseWeight, TotalWeight;
1078 if (extractBranchWeights(SI: ASI.Selects.front(), TrueVal&: TrueWeight, FalseVal&: FalseWeight)) {
1079 uint64_t MinWeight = std::min(a: TrueWeight, b: FalseWeight);
1080 TotalWeight = TrueWeight + FalseWeight;
1081 // Is there a path with frequency <ColdOperandThreshold% (default:20%) ?
1082 ColdOperand = TotalWeight * ColdOperandThreshold > 100 * MinWeight;
1083 } else if (PSI->hasProfileSummary()) {
1084 OptimizationRemarkMissed ORmiss(DEBUG_TYPE, "SelectOpti",
1085 ASI.Selects.front().getI());
1086 ORmiss << "Profile data available but missing branch-weights metadata for "
1087 "select instruction. ";
1088 EmitAndPrintRemark(ORE, Rem&: ORmiss);
1089 }
1090 if (!ColdOperand)
1091 return false;
1092 // Check if the cold path's dependence slice is expensive for any of the
1093 // selects of the group.
1094 for (SelectLike SI : ASI.Selects) {
1095 Instruction *ColdI = nullptr;
1096 uint64_t HotWeight;
1097 if (TrueWeight < FalseWeight) {
1098 ColdI = dyn_cast_or_null<Instruction>(Val: SI.getTrueValue());
1099 HotWeight = FalseWeight;
1100 } else {
1101 ColdI = dyn_cast_or_null<Instruction>(Val: SI.getFalseValue());
1102 HotWeight = TrueWeight;
1103 }
1104 if (ColdI) {
1105 std::stack<Instruction *> ColdSlice;
1106 getExclBackwardsSlice(I: ColdI, Slice&: ColdSlice, SI: SI.getI());
1107 InstructionCost SliceCost = 0;
1108 while (!ColdSlice.empty()) {
1109 SliceCost += TTI->getInstructionCost(U: ColdSlice.top(),
1110 CostKind: TargetTransformInfo::TCK_Latency);
1111 ColdSlice.pop();
1112 }
1113 // The colder the cold value operand of the select is the more expensive
1114 // the cmov becomes for computing the cold value operand every time. Thus,
1115 // the colder the cold operand is the more its cost counts.
1116 // Get nearest integer cost adjusted for coldness.
1117 InstructionCost AdjSliceCost =
1118 divideNearest(Numerator: SliceCost * HotWeight, Denominator: TotalWeight);
1119 if (AdjSliceCost >=
1120 ColdOperandMaxCostMultiplier * TargetTransformInfo::TCC_Expensive)
1121 return true;
1122 }
1123 }
1124 return false;
1125}
1126
1127// Check if it is safe to move LoadI next to the SI.
1128// Conservatively assume it is safe only if there is no instruction
1129// modifying memory in-between the load and the select instruction.
1130static bool isSafeToSinkLoad(Instruction *LoadI, Instruction *SI) {
1131 // Assume loads from different basic blocks are unsafe to move.
1132 if (LoadI->getParent() != SI->getParent())
1133 return false;
1134 auto It = LoadI->getIterator();
1135 while (&*It != SI) {
1136 if (It->mayWriteToMemory())
1137 return false;
1138 It++;
1139 }
1140 return true;
1141}
1142
1143// For a given source instruction, collect its backwards dependence slice
1144// consisting of instructions exclusively computed for the purpose of producing
1145// the operands of the source instruction. As an approximation
1146// (sufficiently-accurate in practice), we populate this set with the
1147// instructions of the backwards dependence slice that only have one-use and
1148// form an one-use chain that leads to the source instruction.
1149void SelectOptimizeImpl::getExclBackwardsSlice(Instruction *I,
1150 std::stack<Instruction *> &Slice,
1151 Instruction *SI,
1152 bool ForSinking) {
1153 SmallPtrSet<Instruction *, 2> Visited;
1154 std::queue<Instruction *> Worklist;
1155 Worklist.push(x: I);
1156 while (!Worklist.empty()) {
1157 Instruction *II = Worklist.front();
1158 Worklist.pop();
1159
1160 // Avoid cycles.
1161 if (!Visited.insert(Ptr: II).second)
1162 continue;
1163
1164 if (!II->hasOneUse())
1165 continue;
1166
1167 // Cannot soundly sink instructions with side-effects.
1168 // Terminator or phi instructions cannot be sunk.
1169 // Avoid sinking other select instructions (should be handled separetely).
1170 if (ForSinking && (II->isTerminator() || II->mayHaveSideEffects() ||
1171 isa<SelectInst>(Val: II) || isa<PHINode>(Val: II)))
1172 continue;
1173
1174 // Avoid sinking loads in order not to skip state-modifying instructions,
1175 // that may alias with the loaded address.
1176 // Only allow sinking of loads within the same basic block that are
1177 // conservatively proven to be safe.
1178 if (ForSinking && II->mayReadFromMemory() && !isSafeToSinkLoad(LoadI: II, SI))
1179 continue;
1180
1181 // Avoid considering instructions with less frequency than the source
1182 // instruction (i.e., avoid colder code regions of the dependence slice).
1183 if (BFI->getBlockFreq(BB: II->getParent()) < BFI->getBlockFreq(BB: I->getParent()))
1184 continue;
1185
1186 // Eligible one-use instruction added to the dependence slice.
1187 Slice.push(x: II);
1188
1189 // Explore all the operands of the current instruction to expand the slice.
1190 for (Value *Op : II->operand_values())
1191 if (auto *OpI = dyn_cast<Instruction>(Val: Op))
1192 Worklist.push(x: OpI);
1193 }
1194}
1195
1196bool SelectOptimizeImpl::isSelectHighlyPredictable(const SelectLike SI) {
1197 uint64_t TrueWeight, FalseWeight;
1198 if (extractBranchWeights(SI, TrueVal&: TrueWeight, FalseVal&: FalseWeight)) {
1199 uint64_t Max = std::max(a: TrueWeight, b: FalseWeight);
1200 uint64_t Sum = TrueWeight + FalseWeight;
1201 if (Sum != 0) {
1202 auto Probability = BranchProbability::getBranchProbability(Numerator: Max, Denominator: Sum);
1203 if (Probability > TTI->getPredictableBranchThreshold())
1204 return true;
1205 }
1206 }
1207 return false;
1208}
1209
1210bool SelectOptimizeImpl::checkLoopHeuristics(const Loop *L,
1211 const CostInfo LoopCost[2]) {
1212 // Loop-level checks to determine if a non-predicated version (with branches)
1213 // of the loop is more profitable than its predicated version.
1214
1215 if (DisableLoopLevelHeuristics)
1216 return true;
1217
1218 OptimizationRemarkMissed ORmissL(DEBUG_TYPE, "SelectOpti",
1219 &*L->getHeader()->getFirstNonPHIIt());
1220
1221 if (LoopCost[0].NonPredCost > LoopCost[0].PredCost ||
1222 LoopCost[1].NonPredCost >= LoopCost[1].PredCost) {
1223 ORmissL << "No select conversion in the loop due to no reduction of loop's "
1224 "critical path. ";
1225 EmitAndPrintRemark(ORE, Rem&: ORmissL);
1226 return false;
1227 }
1228
1229 Scaled64 Gain[2] = {LoopCost[0].PredCost - LoopCost[0].NonPredCost,
1230 LoopCost[1].PredCost - LoopCost[1].NonPredCost};
1231
1232 // Profitably converting to branches need to reduce the loop's critical path
1233 // by at least some threshold (absolute gain of GainCycleThreshold cycles and
1234 // relative gain of 12.5%).
1235 if (Gain[1] < Scaled64::get(N: GainCycleThreshold) ||
1236 Gain[1] * Scaled64::get(N: GainRelativeThreshold) < LoopCost[1].PredCost) {
1237 Scaled64 RelativeGain = Scaled64::get(N: 100) * Gain[1] / LoopCost[1].PredCost;
1238 ORmissL << "No select conversion in the loop due to small reduction of "
1239 "loop's critical path. Gain="
1240 << Gain[1].toString()
1241 << ", RelativeGain=" << RelativeGain.toString() << "%. ";
1242 EmitAndPrintRemark(ORE, Rem&: ORmissL);
1243 return false;
1244 }
1245
1246 // If the loop's critical path involves loop-carried dependences, the gradient
1247 // of the gain needs to be at least GainGradientThreshold% (defaults to 25%).
1248 // This check ensures that the latency reduction for the loop's critical path
1249 // keeps decreasing with sufficient rate beyond the two analyzed loop
1250 // iterations.
1251 if (Gain[1] > Gain[0]) {
1252 Scaled64 GradientGain = Scaled64::get(N: 100) * (Gain[1] - Gain[0]) /
1253 (LoopCost[1].PredCost - LoopCost[0].PredCost);
1254 if (GradientGain < Scaled64::get(N: GainGradientThreshold)) {
1255 ORmissL << "No select conversion in the loop due to small gradient gain. "
1256 "GradientGain="
1257 << GradientGain.toString() << "%. ";
1258 EmitAndPrintRemark(ORE, Rem&: ORmissL);
1259 return false;
1260 }
1261 }
1262 // If the gain decreases it is not profitable to convert.
1263 else if (Gain[1] < Gain[0]) {
1264 ORmissL
1265 << "No select conversion in the loop due to negative gradient gain. ";
1266 EmitAndPrintRemark(ORE, Rem&: ORmissL);
1267 return false;
1268 }
1269
1270 // Non-predicated version of the loop is more profitable than its
1271 // predicated version.
1272 return true;
1273}
1274
1275// Computes instruction and loop-critical-path costs for both the predicated
1276// and non-predicated version of the given loop.
1277// Returns false if unable to compute these costs due to invalid cost of loop
1278// instruction(s).
1279bool SelectOptimizeImpl::computeLoopCosts(
1280 const Loop *L, const SelectGroups &SIGroups,
1281 DenseMap<const Instruction *, CostInfo> &InstCostMap, CostInfo *LoopCost) {
1282 LLVM_DEBUG(dbgs() << "Calculating Latency / IPredCost / INonPredCost of loop "
1283 << L->getHeader()->getName() << "\n");
1284 const auto SImap = getSImap(SIGroups);
1285 const auto SGmap = getSGmap(SIGroups);
1286 // Compute instruction and loop-critical-path costs across two iterations for
1287 // both predicated and non-predicated version.
1288 const unsigned Iterations = 2;
1289 for (unsigned Iter = 0; Iter < Iterations; ++Iter) {
1290 // Cost of the loop's critical path.
1291 CostInfo &MaxCost = LoopCost[Iter];
1292 for (BasicBlock *BB : L->getBlocks()) {
1293 for (const Instruction &I : *BB) {
1294 if (I.isDebugOrPseudoInst())
1295 continue;
1296 // Compute the predicated and non-predicated cost of the instruction.
1297 Scaled64 IPredCost = Scaled64::getZero(),
1298 INonPredCost = Scaled64::getZero();
1299
1300 // Assume infinite resources that allow to fully exploit the available
1301 // instruction-level parallelism.
1302 // InstCost = InstLatency + max(Op1Cost, Op2Cost, … OpNCost)
1303 for (const Use &U : I.operands()) {
1304 auto UI = dyn_cast<Instruction>(Val: U.get());
1305 if (!UI)
1306 continue;
1307 if (auto It = InstCostMap.find(Val: UI); It != InstCostMap.end()) {
1308 IPredCost = std::max(a: IPredCost, b: It->second.PredCost);
1309 INonPredCost = std::max(a: INonPredCost, b: It->second.NonPredCost);
1310 }
1311 }
1312 auto ILatency = computeInstCost(I: &I);
1313 if (!ILatency) {
1314 OptimizationRemarkMissed ORmissL(DEBUG_TYPE, "SelectOpti", &I);
1315 ORmissL << "Invalid instruction cost preventing analysis and "
1316 "optimization of the inner-most loop containing this "
1317 "instruction. ";
1318 EmitAndPrintRemark(ORE, Rem&: ORmissL);
1319 return false;
1320 }
1321 IPredCost += Scaled64::get(N: *ILatency);
1322 INonPredCost += Scaled64::get(N: *ILatency);
1323
1324 // For a select that can be converted to branch,
1325 // compute its cost as a branch (non-predicated cost).
1326 //
1327 // BranchCost = PredictedPathCost + MispredictCost
1328 // PredictedPathCost = TrueOpCost * TrueProb + FalseOpCost * FalseProb
1329 // MispredictCost = max(MispredictPenalty, CondCost) * MispredictRate
1330 if (auto It = SImap.find(Val: &I); It != SImap.end()) {
1331 auto SI = It->second;
1332 const auto *SG = SGmap.at(Val: &I);
1333 Scaled64 TrueOpCost = SI.getOpCostOnBranch(IsTrue: true, InstCostMap, TTI);
1334 Scaled64 FalseOpCost = SI.getOpCostOnBranch(IsTrue: false, InstCostMap, TTI);
1335 Scaled64 PredictedPathCost =
1336 getPredictedPathCost(TrueCost: TrueOpCost, FalseCost: FalseOpCost, SI);
1337
1338 Scaled64 CondCost = Scaled64::getZero();
1339 if (auto *CI = dyn_cast<Instruction>(Val: SG->Condition))
1340 if (auto It = InstCostMap.find(Val: CI); It != InstCostMap.end())
1341 CondCost = It->second.NonPredCost;
1342 Scaled64 MispredictCost = getMispredictionCost(SI, CondCost);
1343
1344 INonPredCost = PredictedPathCost + MispredictCost;
1345 }
1346 LLVM_DEBUG(dbgs() << " " << ILatency << "/" << IPredCost << "/"
1347 << INonPredCost << " for " << I << "\n");
1348
1349 InstCostMap[&I] = {.PredCost: IPredCost, .NonPredCost: INonPredCost};
1350 MaxCost.PredCost = std::max(a: MaxCost.PredCost, b: IPredCost);
1351 MaxCost.NonPredCost = std::max(a: MaxCost.NonPredCost, b: INonPredCost);
1352 }
1353 }
1354 LLVM_DEBUG(dbgs() << "Iteration " << Iter + 1
1355 << " MaxCost = " << MaxCost.PredCost << " "
1356 << MaxCost.NonPredCost << "\n");
1357 }
1358 return true;
1359}
1360
1361SmallDenseMap<const Instruction *, SelectOptimizeImpl::SelectLike, 2>
1362SelectOptimizeImpl::getSImap(const SelectGroups &SIGroups) {
1363 SmallDenseMap<const Instruction *, SelectLike, 2> SImap;
1364 for (const SelectGroup &ASI : SIGroups)
1365 for (const SelectLike &SI : ASI.Selects)
1366 SImap.try_emplace(Key: SI.getI(), Args: SI);
1367 return SImap;
1368}
1369
1370SmallDenseMap<const Instruction *, const SelectOptimizeImpl::SelectGroup *, 2>
1371SelectOptimizeImpl::getSGmap(const SelectGroups &SIGroups) {
1372 SmallDenseMap<const Instruction *, const SelectGroup *, 2> SImap;
1373 for (const SelectGroup &ASI : SIGroups)
1374 for (const SelectLike &SI : ASI.Selects)
1375 SImap.try_emplace(Key: SI.getI(), Args: &ASI);
1376 return SImap;
1377}
1378
1379std::optional<uint64_t>
1380SelectOptimizeImpl::computeInstCost(const Instruction *I) {
1381 InstructionCost ICost =
1382 TTI->getInstructionCost(U: I, CostKind: TargetTransformInfo::TCK_Latency);
1383 if (ICost.isValid())
1384 return std::optional<uint64_t>(ICost.getValue());
1385 return std::nullopt;
1386}
1387
1388ScaledNumber<uint64_t>
1389SelectOptimizeImpl::getMispredictionCost(const SelectLike SI,
1390 const Scaled64 CondCost) {
1391 uint64_t MispredictPenalty = TSchedModel.getMCSchedModel()->MispredictPenalty;
1392
1393 // Account for the default misprediction rate when using a branch
1394 // (conservatively set to 25% by default).
1395 uint64_t MispredictRate = MispredictDefaultRate;
1396 // If the select condition is obviously predictable, then the misprediction
1397 // rate is zero.
1398 if (isSelectHighlyPredictable(SI))
1399 MispredictRate = 0;
1400
1401 // CondCost is included to account for cases where the computation of the
1402 // condition is part of a long dependence chain (potentially loop-carried)
1403 // that would delay detection of a misprediction and increase its cost.
1404 Scaled64 MispredictCost =
1405 std::max(a: Scaled64::get(N: MispredictPenalty), b: CondCost) *
1406 Scaled64::get(N: MispredictRate);
1407 MispredictCost /= Scaled64::get(N: 100);
1408
1409 return MispredictCost;
1410}
1411
1412// Returns the cost of a branch when the prediction is correct.
1413// TrueCost * TrueProbability + FalseCost * FalseProbability.
1414ScaledNumber<uint64_t>
1415SelectOptimizeImpl::getPredictedPathCost(Scaled64 TrueCost, Scaled64 FalseCost,
1416 const SelectLike SI) {
1417 Scaled64 PredPathCost;
1418 uint64_t TrueWeight, FalseWeight;
1419 if (extractBranchWeights(SI, TrueVal&: TrueWeight, FalseVal&: FalseWeight)) {
1420 uint64_t SumWeight = TrueWeight + FalseWeight;
1421 if (SumWeight != 0) {
1422 PredPathCost = TrueCost * Scaled64::get(N: TrueWeight) +
1423 FalseCost * Scaled64::get(N: FalseWeight);
1424 PredPathCost /= Scaled64::get(N: SumWeight);
1425 return PredPathCost;
1426 }
1427 }
1428 // Without branch weight metadata, we assume 75% for the one path and 25% for
1429 // the other, and pick the result with the biggest cost.
1430 PredPathCost = std::max(a: TrueCost * Scaled64::get(N: 3) + FalseCost,
1431 b: FalseCost * Scaled64::get(N: 3) + TrueCost);
1432 PredPathCost /= Scaled64::get(N: 4);
1433 return PredPathCost;
1434}
1435
1436bool SelectOptimizeImpl::isSelectKindSupported(const SelectLike SI) {
1437 TargetLowering::SelectSupportKind SelectKind;
1438 if (SI.getType()->isVectorTy())
1439 SelectKind = TargetLowering::ScalarCondVectorVal;
1440 else
1441 SelectKind = TargetLowering::ScalarValSelect;
1442 return TLI->isSelectSupported(SelectKind);
1443}
1444