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