LLVM 24.0.0git
SelectOptimize.cpp
Go to the documentation of this file.
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
14#include "CodeGenOptions.h"
15#include "llvm/ADT/SetVector.h"
17#include "llvm/ADT/Statistic.h"
24#include "llvm/CodeGen/Passes.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"
37#include "llvm/Pass.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 {
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>(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>(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>(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>(I))
151 return BO->getOperand(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>(V)) {
165 auto It = InstCostMap.find(IV);
166 return It != InstCostMap.end() ? It->second.NonPredCost
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
176 getI()->getOpcode(), I->getType(), TargetTransformInfo::TCK_Latency,
177 {TargetTransformInfo::OK_AnyValue, TargetTransformInfo::OP_None},
178 {TTI::OK_UniformConstantValue, TTI::OP_PowerOf2});
179 auto TotalCost = Scaled64::get(Cost.getValue());
180 if (auto *OpI = dyn_cast<Instruction>(I->getOperand(1 - CondIdx))) {
181 auto It = InstCostMap.find(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;
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, *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
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)
320INITIALIZE_PASS_END(SelectOptimize, DEBUG_TYPE, "Optimize selects", false,
321 false)
322
323FunctionPass *llvm::createSelectOptimizePass() { return new SelectOptimize(); }
324
325PreservedAnalyses SelectOptimizeImpl::run(Function &F,
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>(F);
339 if (!TTI->enableSelectOptimize())
340 return PreservedAnalyses::all();
341
343 .getCachedResult<ProfileSummaryAnalysis>(*F.getParent());
344 if (!PSI)
345 reportFatalUsageError("this pass requires the profile-summary module "
346 "analysis to be available");
347 BFI = &FAM.getResult<BlockFrequencyAnalysis>(F);
348
349 // When optimizing for size, selects are preferable over branches.
350 if (llvm::shouldOptimizeForSize(&F, PSI, BFI))
351 return PreservedAnalyses::all();
352
353 LI = &FAM.getResult<LoopAnalysis>(F);
354 ORE = &FAM.getResult<OptimizationRemarkEmitterAnalysis>(F);
355 TSchedModel.init(TSI);
356
357 bool Changed = optimizeSelects(F);
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.
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(TSI);
384
385 // When optimizing for size, selects are preferable over branches.
386 if (llvm::shouldOptimizeForSize(&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);
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) {
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(Loops, 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, 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
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>(V))
462 if (auto It = OptSelects.find(IV); It != OptSelects.end())
463 return isTrue ? It->second.first : It->second.second;
464 return V;
465 }
466
467 auto *BO = cast<BinaryOperator>(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>(CBO->getOperand(CondIdx));
476 if (isa<ZExtInst>(AuxI) || isa<LShrOperator>(AuxI)) {
477 CBO->setOperand(CondIdx, ConstantInt::get(CBO->getType(), 1));
478 } else {
479 assert((isa<AShrOperator>(AuxI) || isa<SExtInst>(AuxI)) &&
480 "Unexpected opcode");
481 CBO->setOperand(CondIdx, ConstantInt::getAllOnesValue(CBO->getType()));
482 }
483
484 unsigned OtherIdx = 1 - CondIdx;
485 if (auto *IV = dyn_cast<Instruction>(CBO->getOperand(OtherIdx))) {
486 if (auto It = OptSelects.find(IV); It != OptSelects.end())
487 CBO->setOperand(OtherIdx, isTrue ? It->second.first : It->second.second);
488 }
489 CBO->insertBefore(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>(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>(SI.getTrueValue())) {
544 std::stack<Instruction *> TrueSlice;
545 getExclBackwardsSlice(TI, TrueSlice, SI.getI(), true, &ASI);
546 maxTrueSliceLen = std::max(maxTrueSliceLen, TrueSlice.size());
547 TrueSlices.push_back(TrueSlice);
548 }
549 if (auto *FI = dyn_cast_or_null<Instruction>(SI.getFalseValue())) {
550 if (isa<SelectInst>(SI.getI()) || !FI->hasOneUse()) {
551 std::stack<Instruction *> FalseSlice;
552 getExclBackwardsSlice(FI, FalseSlice, SI.getI(), true, &ASI);
553 maxFalseSliceLen = std::max(maxFalseSliceLen, FalseSlice.size());
554 FalseSlices.push_back(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>(SI.getI())->getCondition();
560 if (hasProfMD(*SI.getI()) && ASI.Condition == SelectCondition) {
561 SelectWithProfile = SI.getI();
562 } else if (hasProfMD(*SI.getI()) &&
563 match(SelectCondition, m_Not(m_Value(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(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(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(SplitPt, "select.end");
608 BFI->setBlockFreq(EndBlock, BFI->getBlockFreq(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.
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(&*DIt);
622 DIt++;
623 }
624 for (auto *HI : HoistInstrs)
625 HI->moveBefore(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(I.getDbgRecordRange())) {
634 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(std::next(SI.getI()->getIterator()),
642 std::next(LastSI.getI()->getIterator()));
643 llvm::for_each(R, 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(EndBlock->getContext(), "select.true.sink",
659 EndBlock->getParent(), EndBlock);
660 TrueBranch = UncondBrInst::Create(EndBlock, TrueBlock);
661 TrueBranch->setDebugLoc(LastSI.getI()->getDebugLoc());
662 for (Instruction *TrueInst : TrueSlicesInterleaved)
663 TrueInst->moveBefore(TrueBranch->getIterator());
664 }
665 if (!FalseSlicesInterleaved.empty() || HasSelectLike(ASI, false)) {
666 FalseBlock =
667 BasicBlock::Create(EndBlock->getContext(), "select.false.sink",
668 EndBlock->getParent(), EndBlock);
669 FalseBranch = UncondBrInst::Create(EndBlock, FalseBlock);
670 FalseBranch->setDebugLoc(LastSI.getI()->getDebugLoc());
671 for (Instruction *FalseInst : FalseSlicesInterleaved)
672 FalseInst->moveBefore(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(StartBlock->getContext(), "select.false",
681 EndBlock->getParent(), EndBlock);
682 auto *FalseBranch = UncondBrInst::Create(EndBlock, 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(ASI.Condition, ASI.Condition->getName() + ".frozen");
707
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(SI.getType(), 2, "");
717 PN->insertBefore(InsertionPoint);
718 PN->takeName(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(1)) {
722 for (auto &SG : ProfSIGroups) {
723 if (SG.Condition == SI.getI())
724 SG.Condition = PN;
725 }
726 }
727 SI.getI()->replaceAllUsesWith(PN);
728 auto *TV = getTrueOrFalseValue(SI, true, INS, TrueBlock);
729 auto *FV = getTrueOrFalseValue(SI, false, INS, FalseBlock);
730 INS[PN] = {TV, FV};
731 PN->addIncoming(TV, TrueBlock);
732 PN->addIncoming(FV, FalseBlock);
733 PN->setDebugLoc(SI.getI()->getDebugLoc());
734 ++NumSelectsConverted;
735 }
736 Instruction *CondBr = IB.CreateCondBr(CondFr, TT, FT, SI.getI());
737 if (!ProfcheckDisableMetadataFixes && SelectWithProfile) {
738 CondBr->copyMetadata(*SelectWithProfile, {llvm::LLVMContext::MD_prof});
739 if (SelectWithProfileIsInverted)
740 CondBr->swapProfMetadata();
741 } else {
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
770 // Keeps visited comparisons to help identify AShr/LShr variants of auxiliary
771 // instructions.
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>(I)) {
779 SeenCmp.insert(Cmp);
780 return SelectInfo.end();
781 }
782
783 Value *Cond;
785 Cond->getType()->isIntegerTy(1)) {
786 bool Inverted = match(Cond, m_Not(m_Value(Cond)));
787 return SelectInfo.insert({I, {Cond, true, Inverted, 0}}).first;
788 }
789
790 if (match(I, m_Not(m_Value(Cond)))) {
791 return SelectInfo.insert({I, {Cond, true, true, 0}}).first;
792 }
793
794 // Select instruction are what we are usually looking for.
795 if (match(I, m_Select(m_Value(Cond), m_Value(), m_Value()))) {
796 bool Inverted = match(Cond, m_Not(m_Value(Cond)));
797 return SelectInfo.insert({I, {Cond, false, Inverted, 0}}).first;
798 }
799 Value *Val;
800 ConstantInt *Shift;
801 if (match(I, m_Shr(m_Value(Val), m_ConstantInt(Shift))) &&
802 I->getType()->getIntegerBitWidth() == Shift->getZExtValue() + 1) {
803 for (auto *CmpI : SeenCmp) {
804 auto Pred = CmpI->getPredicate();
805 if (Val != CmpI->getOperand(0))
806 continue;
807 if ((Pred == CmpInst::ICMP_SGT &&
808 match(CmpI->getOperand(1), m_ConstantInt<-1>())) ||
810 match(CmpI->getOperand(1), m_Zero())) ||
812 match(CmpI->getOperand(1), m_Zero())) ||
814 match(CmpI->getOperand(1), m_ConstantInt<-1>()))) {
815 bool Inverted =
817 return SelectInfo.insert({I, {CmpI, true, Inverted, 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 =
830 auto MatchShiftPattern =
832
833 // This check is unnecessary, but it prevents costly access to the
834 // SelectInfo map.
835 if ((match(I, MatchZExtOrSExtPattern) && X->getType()->isIntegerTy(1)) ||
836 (match(I, 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(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(Idx);
853 auto It = SelectInfo.find(Op);
854 if (It != SelectInfo.end() && It->second.IsAuxiliary) {
855 Cond = It->second.Cond;
856 bool Inverted = It->second.IsInverted;
857 return SelectInfo.insert({I, {Cond, false, Inverted, Idx}}).first;
858 }
859 }
860 }
861 return SelectInfo.end();
862 };
863
864 bool AlreadyProcessed = false;
865 BasicBlock::iterator BBIt = BB.begin();
867 while (BBIt != BB.end()) {
868 Instruction *I = &*BBIt++;
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(1))
886 continue;
887
888 SelectGroup SIGroup = {Cond, {}};
889 SIGroup.Selects.emplace_back(I, It->second.IsInverted,
890 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(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>(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(NI, IsRev, 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(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(ASI);
939 }
940}
941
944 LLVM_DEBUG(dbgs() << Rem.getMsg() << "\n");
945 ORE->emit(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
962 CostInfo LoopCost[2] = {{Scaled64::getZero(), Scaled64::getZero()},
963 {Scaled64::getZero(), Scaled64::getZero()}};
964 if (!computeLoopCosts(L, SIGroups, InstCostMap, LoopCost) ||
965 !checkLoopHeuristics(L, 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(SelectCost, ICM.PredCost);
976 BranchCost = std::max(BranchCost, 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, OR);
985 ++NumSelectConvertedLoop;
986 ProfSIGroups.push_back(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, 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(SI.getI()->getParent(), BFI)) {
1008 ++NumSelectColdBB;
1009 ORmiss << "Not converted to branch because of cold basic block. ";
1010 EmitAndPrintRemark(ORE, ORmiss);
1011 return false;
1012 }
1013
1014 // If unpredictable, branch form is less profitable.
1015 if (SI.getI()->getMetadata(LLVMContext::MD_unpredictable)) {
1016 ++NumSelectUnPred;
1017 ORmiss << "Not converted to branch because of unpredictable branch. ";
1018 EmitAndPrintRemark(ORE, 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, 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, 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, OR);
1049 return true;
1050 }
1051
1052 ORmiss << "Not profitable to convert to branch (base heuristic).";
1053 EmitAndPrintRemark(ORE, ORmiss);
1054 return false;
1055}
1056
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>(SI.getI()))
1065 return extractBranchWeights(*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(ASI.Selects.front(), TrueWeight, FalseWeight)) {
1073 uint64_t MinWeight = std::min(TrueWeight, 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, 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>(SI.getTrueValue());
1093 HotWeight = FalseWeight;
1094 } else {
1095 ColdI = dyn_cast_or_null<Instruction>(SI.getFalseValue());
1096 HotWeight = TrueWeight;
1097 }
1098 if (ColdI) {
1099 std::stack<Instruction *> ColdSlice;
1100 getExclBackwardsSlice(ColdI, ColdSlice, SI.getI());
1101 InstructionCost SliceCost = 0;
1102 while (!ColdSlice.empty()) {
1103 SliceCost += TTI->getInstructionCost(ColdSlice.top(),
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(SliceCost * HotWeight, TotalWeight);
1113 if (AdjSliceCost >= Opts->cold_operand_max_cost_multiplier *
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.
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) {
1148 std::queue<Instruction *> Worklist;
1149 Worklist.push(I);
1150 while (!Worklist.empty()) {
1151 Instruction *II = Worklist.front();
1152 Worklist.pop();
1153
1154 // Avoid cycles.
1155 if (!Visited.insert(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() ||
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(Group->Selects, [&](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(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(II->getParent()) < BFI->getBlockFreq(I->getParent()))
1184 continue;
1185
1186 // Eligible one-use instruction added to the dependence slice.
1187 Slice.push(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>(Op))
1192 Worklist.push(OpI);
1193 }
1194}
1195
1196bool SelectOptimizeImpl::isSelectHighlyPredictable(const SelectLike SI) {
1197 uint64_t TrueWeight, FalseWeight;
1198 if (extractBranchWeights(SI, TrueWeight, FalseWeight)) {
1199 uint64_t Max = std::max(TrueWeight, FalseWeight);
1200 uint64_t Sum = TrueWeight + FalseWeight;
1201 if (Sum != 0) {
1202 auto Probability = BranchProbability::getBranchProbability(Max, 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, 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(Opts->select_opti_loop_cycle_gain_threshold) ||
1236 Gain[1] * Scaled64::get(Opts->select_opti_loop_relative_gain_threshold) <
1237 LoopCost[1].PredCost) {
1238 Scaled64 RelativeGain = Scaled64::get(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, 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(100) * (Gain[1] - Gain[0]) /
1254 (LoopCost[1].PredCost - LoopCost[0].PredCost);
1255 if (GradientGain <
1256 Scaled64::get(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, 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, 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) {
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>(U.get());
1307 if (!UI)
1308 continue;
1309 if (auto It = InstCostMap.find(UI); It != InstCostMap.end()) {
1310 IPredCost = std::max(IPredCost, It->second.PredCost);
1311 INonPredCost = std::max(INonPredCost, It->second.NonPredCost);
1312 }
1313 }
1314 auto ILatency = computeInstCost(&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, ORmissL);
1321 return false;
1322 }
1323 IPredCost += Scaled64::get(*ILatency);
1324 INonPredCost += Scaled64::get(*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(&I); It != SImap.end()) {
1333 auto SI = It->second;
1334 const auto *SG = SGmap.at(&I);
1335 Scaled64 TrueOpCost = SI.getOpCostOnBranch(true, InstCostMap, TTI);
1336 Scaled64 FalseOpCost = SI.getOpCostOnBranch(false, InstCostMap, TTI);
1337 Scaled64 PredictedPathCost =
1338 getPredictedPathCost(TrueOpCost, FalseOpCost, SI);
1339
1340 Scaled64 CondCost = Scaled64::getZero();
1341 if (auto *CI = dyn_cast<Instruction>(SG->Condition))
1342 if (auto It = InstCostMap.find(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] = {IPredCost, INonPredCost};
1352 MaxCost.PredCost = std::max(MaxCost.PredCost, IPredCost);
1353 MaxCost.NonPredCost = std::max(MaxCost.NonPredCost, INonPredCost);
1354 }
1355 }
1356 LLVM_DEBUG(dbgs() << "Iteration " << Iter + 1
1357 << " MaxCost = " << MaxCost.PredCost << " "
1358 << MaxCost.NonPredCost << "\n");
1359 }
1360 return true;
1361}
1362
1364SelectOptimizeImpl::getSImap(const SelectGroups &SIGroups) {
1366 for (const SelectGroup &ASI : SIGroups)
1367 for (const SelectLike &SI : ASI.Selects)
1368 SImap.try_emplace(SI.getI(), SI);
1369 return SImap;
1370}
1371
1373SelectOptimizeImpl::getSGmap(const SelectGroups &SIGroups) {
1375 for (const SelectGroup &ASI : SIGroups)
1376 for (const SelectLike &SI : ASI.Selects)
1377 SImap.try_emplace(SI.getI(), &ASI);
1378 return SImap;
1379}
1380
1381std::optional<uint64_t>
1382SelectOptimizeImpl::computeInstCost(const Instruction *I) {
1383 InstructionCost ICost =
1384 TTI->getInstructionCost(I, TargetTransformInfo::TCK_Latency);
1385 if (ICost.isValid())
1386 return std::optional<uint64_t>(ICost.getValue());
1387 return std::nullopt;
1388}
1389
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(Scaled64::get(MispredictPenalty), CondCost) *
1408 Scaled64::get(MispredictRate);
1409 MispredictCost /= Scaled64::get(100);
1410
1411 return MispredictCost;
1412}
1413
1414// Returns the cost of a branch when the prediction is correct.
1415// TrueCost * TrueProbability + FalseCost * FalseProbability.
1417SelectOptimizeImpl::getPredictedPathCost(Scaled64 TrueCost, Scaled64 FalseCost,
1418 const SelectLike SI) {
1419 Scaled64 PredPathCost;
1420 uint64_t TrueWeight, FalseWeight;
1421 if (extractBranchWeights(SI, TrueWeight, FalseWeight)) {
1422 uint64_t SumWeight = TrueWeight + FalseWeight;
1423 if (SumWeight != 0) {
1424 PredPathCost = TrueCost * Scaled64::get(TrueWeight) +
1425 FalseCost * Scaled64::get(FalseWeight);
1426 PredPathCost /= Scaled64::get(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(TrueCost * Scaled64::get(3) + FalseCost,
1433 FalseCost * Scaled64::get(3) + TrueCost);
1434 PredPathCost /= Scaled64::get(4);
1435 return PredPathCost;
1436}
1437
1438bool SelectOptimizeImpl::isSelectKindSupported(const SelectLike SI) {
1440 if (SI.getType()->isVectorTy())
1442 else
1444 return TLI->isSelectSupported(SelectKind);
1445}
const TargetLowering & TLI
SDValue Pred
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
uint64_t uint64_t
#define X(NUM, ENUM, NAME)
Definition ELF.h:665
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static Value * getTrueOrFalseValue(SelectInst *SI, bool isTrue, const SmallPtrSet< const Instruction *, 2 > &Selects)
If isTrue is true, return the true value of SI, otherwise return false value of SI.
static bool runOnFunction(Function &F, bool PostInlining)
#define DEBUG_TYPE
Hexagon Hardware Loops
#define F(x, y, z)
Definition MD5.cpp:54
#define I(x, y, z)
Definition MD5.cpp:57
print mir2vec MIR2Vec Vocabulary Printer Pass
Definition MIR2Vec.cpp:656
uint64_t IntrinsicInst * II
#define P(N)
FunctionAnalysisManager FAM
if(PassOpts->AAPipeline)
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition PassSupport.h:42
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition PassSupport.h:44
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition PassSupport.h:39
This file contains the declarations for profiling metadata utility functions.
SmallVector< MachineOperand, 4 > Cond
const GCNTargetMachine & getTM(const GCNSubtarget *STI)
static bool isSafeToSinkLoad(Instruction *LoadI, Instruction *SI)
static void EmitAndPrintRemark(OptimizationRemarkEmitter *ORE, DiagnosticInfoOptimizationBase &Rem)
This file contains the declaration of the SelectOptimizePass class, its corresponding pass name is se...
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition Statistic.h:171
#define LLVM_DEBUG(...)
Definition Debug.h:119
static SymbolRef::Type getType(const Symbol *Sym)
Definition TapiFile.cpp:39
This file describes how to lower LLVM code to machine code.
Target-Independent Code Generator Pass Configuration Options pass.
This pass exposes codegen information to IR-level passes.
static const uint32_t IV[8]
Definition blake3_impl.h:83
AnalysisUsage & addRequired()
LLVM Basic Block Representation.
Definition BasicBlock.h:62
iterator end()
Definition BasicBlock.h:453
iterator begin()
Instruction iterator methods.
Definition BasicBlock.h:440
LLVM_ABI const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
LLVM_ABI BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="")
Split the basic block into two basic blocks at the specified instruction.
const Function * getParent() const
Return the enclosing method, or null if none.
Definition BasicBlock.h:213
LLVM_ABI void insertDbgRecordBefore(DbgRecord *DR, InstListType::iterator Here)
Insert a DbgRecord into a block at the position given by Here.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition BasicBlock.h:206
InstListType::iterator iterator
Instruction iterators...
Definition BasicBlock.h:170
LLVM_ABI LLVMContext & getContext() const
Get the context in which this basic block lives.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; assumes that the block is well-formed.
Definition BasicBlock.h:237
Analysis pass which computes BlockFrequencyInfo.
Legacy analysis pass which computes BlockFrequencyInfo.
LLVM_ABI void setBlockFreq(const BasicBlock *BB, BlockFrequency Freq)
LLVM_ABI BlockFrequency getBlockFreq(const BasicBlock *BB) const
getblockFreq - Return block frequency.
static LLVM_ABI BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
@ ICMP_SLT
signed less than
Definition InstrTypes.h:769
@ ICMP_SLE
signed less or equal
Definition InstrTypes.h:770
@ ICMP_SGT
signed greater than
Definition InstrTypes.h:767
@ ICMP_SGE
signed greater or equal
Definition InstrTypes.h:768
This is the shared class of boolean and integer constants.
Definition Constants.h:87
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
Definition Constants.h:168
static LLVM_ABI Constant * getAllOnesValue(Type *Ty)
Base class for non-instruction debug metadata records that have positions within IR.
LLVM_ABI void removeFromParent()
iterator find(const_arg_type_t< KeyT > Val)
Definition DenseMap.h:766
iterator end()
Definition DenseMap.h:686
DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator
Definition DenseMap.h:678
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition DenseMap.h:827
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
Definition DenseMap.h:856
Common features for diagnostics dealing with optimization remarks that are used by both IR and MIR pa...
FunctionPass class - This class is used to implement most global optimizations.
Definition Pass.h:312
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition IRBuilder.h:2990
CostType getValue() const
This function is intended to be used as sparingly as possible, since the class provides the full rang...
LLVM_ABI void insertBefore(InstListType::iterator InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified position.
LLVM_ABI InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
LLVM_ABI void swapProfMetadata()
If the instruction has "branch_weights" MD_prof metadata and the MDNode has three operands (including...
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
LLVM_ABI void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())
Copy metadata from SrcInst to this instruction.
Analysis pass that exposes the LoopInfo for a function.
Definition LoopInfo.h:598
iterator end() const
iterator begin() const
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
The legacy pass manager's analysis pass to compute loop information.
Definition LoopInfo.h:623
Represents a single loop in the control flow graph.
Definition LoopInfo.h:40
OptimizationRemarkEmitter legacy analysis pass.
The optimization diagnostic interface.
LLVM_ABI void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file.
Diagnostic information for missed-optimization remarks.
Diagnostic information for applied optimization remarks.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
Pass interface - Implemented by all 'passes'.
Definition Pass.h:97
A set of analyses that are preserved following a run of a transformation pass.
Definition Analysis.h:112
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition Analysis.h:115
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition Analysis.h:118
An analysis pass based on legacy pass manager to deliver ProfileSummaryInfo.
bool hasProfileSummary() const
Returns true if profile summary is available.
bool isColdBlock(const BBType *BB, BFIT *BFI) const
Returns true if BasicBlock BB is considered cold.
Simple representation of a scaled number.
static ScaledNumber get(uint64_t N)
static ScaledNumber getZero()
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition SetVector.h:157
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
Definition SetVector.h:346
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Analysis pass providing the TargetTransformInfo.
virtual bool isSelectSupported(SelectSupportKind) const
SelectSupportKind
Enum that describes what type of support for selects the target has.
bool isPredictableSelectExpensive() const
Return true if selects are only cheaper than branches if the branch is unlikely to be predicted right...
virtual const TargetSubtargetInfo * getSubtargetImpl(const Function &) const
Virtual method implemented by subclasses that returns a reference to that target's TargetSubtargetInf...
Target-Independent Code Generator Pass Configuration Options.
LLVM_ABI void init(const TargetSubtargetInfo *TSInfo, bool EnableSModel=true, bool EnableSItins=true)
Initialize the machine model for instruction scheduling.
virtual unsigned getMispredictionPenalty() const
Return the number of extra cycles the processor takes to recover from a branch misprediction.
virtual const TargetLowering * getTargetLowering() const
Wrapper pass for TargetTransformInfo.
@ TCK_Latency
The latency of instruction.
LLVM_ABI InstructionCost getArithmeticInstrCost(unsigned Opcode, Type *Ty, TTI::TargetCostKind CostKind, TTI::OperandValueInfo Opd1Info={TTI::OK_AnyValue, TTI::OP_None}, TTI::OperandValueInfo Opd2Info={TTI::OK_AnyValue, TTI::OP_None}, ArrayRef< const Value * > Args={}, const Instruction *CtxI=nullptr, const TargetLibraryInfo *TLibInfo=nullptr) const
This is an approximation of reciprocal throughput of a math/logic op.
@ TCC_Expensive
The cost of a 'div' instruction on x86.
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition Type.h:252
Unconditional Branch instruction.
static UncondBrInst * Create(BasicBlock *Target, InsertPosition InsertBefore=nullptr)
A Use represents the edge between a Value definition and its users.
Definition Use.h:35
LLVM Value Representation.
Definition Value.h:75
Type * getType() const
All values are typed, get the type of this value.
Definition Value.h:257
LLVM_ABI void takeName(Value *V)
Transfer the name from V to this value.
Definition Value.cpp:395
const ParentTy * getParent() const
Definition ilist_node.h:34
self_iterator getIterator()
Definition ilist_node.h:123
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
BinaryOp_match< SrcTy, SpecificConstantMatch, TargetOpcode::G_XOR, true > m_Not(const SrcTy &&Src)
Matches a register not-ed by a G_XOR.
OneUse_match< SubPat > m_OneUse(const SubPat &SP)
bool match(Val *V, const Pattern &P)
BinOpPred_match< LHS, RHS, is_right_shift_op > m_Shr(const LHS &L, const RHS &R)
Matches logical shift operations.
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
auto m_Value()
Match an arbitrary value and ignore it.
is_zero< true > m_Zero()
Match any null constant or a vector with all elements equal to 0.
AnyBinaryOp_match< LHS, RHS, true > m_c_BinOp(const LHS &L, const RHS &R)
Matches a BinaryOperator with LHS and RHS in either order.
match_combine_or< CastInst_match< OpTy, ZExtInst >, CastInst_match< OpTy, SExtInst > > m_ZExtOrSExt(const OpTy &Op)
auto m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
friend class Instruction
Iterator for Instructions in a `BasicBlock.
Definition BasicBlock.h:73
unsigned getOpcode(const VPValue *V)
Return the instruction opcode for the recipe defining V or 0 for unsupported recipes and VPValues not...
This is an optimization pass for GlobalISel generic memory operations.
LLVM_ABI cl::opt< bool > ProfcheckDisableMetadataFixes
UnaryFunction for_each(R &&Range, UnaryFunction F)
Provide wrappers to std::for_each which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1748
InstructionCost Cost
LLVM_ABI void setExplicitlyUnknownBranchWeightsIfProfiled(Instruction &I, StringRef PassName, const Function *F=nullptr)
Like setExplicitlyUnknownBranchWeights(...), but only sets unknown branch weights in the new instruct...
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:643
OuterAnalysisManagerProxy< ModuleAnalysisManager, Function > ModuleAnalysisManagerFunctionProxy
Provide the ModuleAnalysisManager to Function proxy.
LLVM_ABI FunctionPass * createSelectOptimizePass()
This pass converts conditional moves to conditional jumps when profitable.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
Definition STLExtras.h:2224
LLVM_ABI bool shouldOptimizeForSize(const MachineFunction *MF, ProfileSummaryInfo *PSI, const MachineBlockFrequencyInfo *BFI, PGSOQueryType QueryType=PGSOQueryType::Other)
Returns true if machine function MF is suggested to be size-optimized based on the profile.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition STLExtras.h:649
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
Definition InstrProf.h:143
constexpr T divideNearest(U Numerator, V Denominator)
Returns (Numerator / Denominator) rounded by round-half-up.
Definition MathExtras.h:453
auto dyn_cast_or_null(const Y &Val)
Definition Casting.h:753
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1762
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:209
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
Definition Casting.h:547
TargetTransformInfo TTI
LLVM_ABI bool hasProfMD(const Instruction &I)
Checks if an Instruction has MD_prof Metadata.
DWARFExpression::Operation Op
LLVM_ABI bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:559
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
const CodeGenOptions & getCodeGenOptions(const LLVMContext &C)
LLVM_ABI void reportFatalUsageError(Error Err)
Report a fatal error that does not indicate a bug in LLVM.
Definition Error.cpp:177