48#define DEBUG_TYPE "select-optimize"
51 "Number of select groups considered for conversion to branch");
53 "Number of select groups converted due to expensive cold operand");
55 "Number of select groups converted due to high-predictability");
57 "Number of select groups not converted due to unpredictability");
59 "Number of select groups not converted due to cold basic block");
61 "Number of select groups converted due to loop-level analysis");
62STATISTIC(NumSelectsConverted,
"Number of selects converted");
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;
83 SelectOptimizeImpl() =
default;
84 SelectOptimizeImpl(
const TargetMachine *TM) : TM(TM){};
88 using Scaled64 = ScaledNumber<uint64_t>;
105 bool Inverted =
false;
112 SelectLike(Instruction *I,
bool Inverted =
false,
unsigned CondIdx = 0)
113 : I(I), Inverted(Inverted), CondIdx(CondIdx) {}
120 unsigned getConditionOpIndex() {
return CondIdx; };
126 Value *getTrueValue(
bool HonorInverts =
true)
const {
127 if (Inverted && HonorInverts)
128 return getFalseValue(
false);
130 return Sel->getTrueValue();
142 Value *getFalseValue(
bool HonorInverts =
true)
const {
143 if (Inverted && HonorInverts)
144 return getTrueValue(
false);
146 return Sel->getFalseValue();
151 return BO->getOperand(1 - CondIdx);
159 Scaled64 getOpCostOnBranch(
160 bool IsTrue,
const DenseMap<const Instruction *, CostInfo> &InstCostMap,
161 const TargetTransformInfo *
TTI) {
162 auto *
V = IsTrue ? getTrueValue() : getFalseValue();
165 auto It = InstCostMap.
find(
IV);
166 return It != InstCostMap.
end() ? It->second.NonPredCost
177 {TargetTransformInfo::OK_AnyValue, TargetTransformInfo::OP_None},
178 {TTI::OK_UniformConstantValue, TTI::OP_PowerOf2});
181 auto It = InstCostMap.find(OpI);
182 if (It != InstCostMap.end())
183 TotalCost += It->second.NonPredCost;
197 using SelectGroups = SmallVector<SelectGroup, 2>;
207 void optimizeSelectsBase(
Function &
F, SelectGroups &ProfSIGroups);
208 void optimizeSelectsInnerLoops(
Function &
F, SelectGroups &ProfSIGroups);
212 void convertProfitableSIGroups(SelectGroups &ProfSIGroups);
215 void collectSelectGroups(BasicBlock &BB, SelectGroups &SIGroups);
219 void findProfitableSIGroupsBase(SelectGroups &SIGroups,
220 SelectGroups &ProfSIGroups);
221 void findProfitableSIGroupsInnerLoops(
const Loop *L, SelectGroups &SIGroups,
222 SelectGroups &ProfSIGroups);
226 bool isConvertToBranchProfitableBase(
const SelectGroup &ASI);
231 bool hasExpensiveColdOperand(
const SelectGroup &ASI);
237 void getExclBackwardsSlice(Instruction *
I, std::stack<Instruction *> &Slice,
238 Instruction *SI,
bool ForSinking =
false,
239 const SelectGroup *Group =
nullptr);
242 bool isSelectHighlyPredictable(
const SelectLike SI);
246 bool checkLoopHeuristics(
const Loop *L,
const CostInfo LoopDepth[2]);
250 bool computeLoopCosts(
const Loop *L,
const SelectGroups &SIGroups,
251 DenseMap<const Instruction *, CostInfo> &InstCostMap,
255 SmallDenseMap<const Instruction *, SelectLike, 2>
256 getSImap(
const SelectGroups &SIGroups);
260 SmallDenseMap<const Instruction *, const SelectGroup *, 2>
261 getSGmap(
const SelectGroups &SIGroups);
264 std::optional<uint64_t> computeInstCost(
const Instruction *
I);
267 Scaled64 getMispredictionCost(
const SelectLike SI,
const Scaled64 CondCost);
270 Scaled64 getPredictedPathCost(Scaled64 TrueCost, Scaled64 FalseCost,
271 const SelectLike SI);
274 bool isSelectKindSupported(
const SelectLike SI);
278 SelectOptimizeImpl Impl;
283 SelectOptimize() : FunctionPass(ID) {}
289 return Impl.runOnFunction(
F, *
this);
292 void getAnalysisUsage(AnalysisUsage &AU)
const override {
298 AU.
addRequired<OptimizationRemarkEmitterWrapperPass>();
306 SelectOptimizeImpl Impl(TM);
307 return Impl.run(
F,
FAM);
310char SelectOptimize::ID = 0;
339 if (!
TTI->enableSelectOptimize())
343 .getCachedResult<ProfileSummaryAnalysis>(*
F.getParent());
346 "analysis to be available");
355 TSchedModel.
init(TSI);
376 if (!
TTI->enableSelectOptimize())
383 TSchedModel.
init(TSI);
389 return optimizeSelects(
F);
392bool SelectOptimizeImpl::optimizeSelects(
Function &
F) {
395 SelectGroups ProfSIGroups;
397 optimizeSelectsBase(
F, ProfSIGroups);
399 optimizeSelectsInnerLoops(
F, ProfSIGroups);
403 convertProfitableSIGroups(ProfSIGroups);
406 return !ProfSIGroups.empty();
409void SelectOptimizeImpl::optimizeSelectsBase(
Function &
F,
410 SelectGroups &ProfSIGroups) {
412 SelectGroups SIGroups;
416 if (L &&
L->isInnermost())
418 collectSelectGroups(BB, SIGroups);
422 findProfitableSIGroupsBase(SIGroups, ProfSIGroups);
425void SelectOptimizeImpl::optimizeSelectsInnerLoops(
Function &
F,
426 SelectGroups &ProfSIGroups) {
429 for (
unsigned long i = 0; i <
Loops.size(); ++i)
433 if (!
L->isInnermost())
436 SelectGroups SIGroups;
438 collectSelectGroups(*BB, SIGroups);
440 findProfitableSIGroupsInnerLoops(L, SIGroups, ProfSIGroups);
456 SelectOptimizeImpl::SelectLike &
SI,
bool isTrue,
459 Value *
V = isTrue ?
SI.getTrueValue() :
SI.getFalseValue();
462 if (
auto It = OptSelects.find(
IV); It != OptSelects.end())
463 return isTrue ? It->second.first : It->second.second;
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.");
473 auto *CBO = BO->clone();
474 auto CondIdx =
SI.getConditionOpIndex();
477 CBO->setOperand(CondIdx, ConstantInt::get(CBO->getType(), 1));
480 "Unexpected opcode");
484 unsigned OtherIdx = 1 - CondIdx;
486 if (
auto It = OptSelects.find(
IV); It != OptSelects.end())
487 CBO->setOperand(OtherIdx, isTrue ? It->second.first : It->second.second);
489 CBO->insertBefore(
B->getTerminator()->getIterator());
493void SelectOptimizeImpl::convertProfitableSIGroups(SelectGroups &ProfSIGroups) {
494 for (SelectGroup &ASI : ProfSIGroups) {
534 typedef std::stack<Instruction *>::size_type StackSizeType;
535 StackSizeType maxTrueSliceLen = 0, maxFalseSliceLen = 0;
537 bool SelectWithProfileIsInverted =
false;
538 for (SelectLike &
SI : ASI.Selects) {
544 std::stack<Instruction *> TrueSlice;
545 getExclBackwardsSlice(TI, TrueSlice,
SI.getI(),
true, &ASI);
546 maxTrueSliceLen = std::max(maxTrueSliceLen, TrueSlice.size());
551 std::stack<Instruction *> FalseSlice;
552 getExclBackwardsSlice(FI, FalseSlice,
SI.getI(),
true, &ASI);
553 maxFalseSliceLen = std::max(maxFalseSliceLen, FalseSlice.size());
560 if (
hasProfMD(*
SI.getI()) && ASI.Condition == SelectCondition) {
561 SelectWithProfile =
SI.getI();
564 SelectWithProfile =
SI.getI();
565 SelectWithProfileIsInverted =
true;
579 for (StackSizeType IS = 0;
IS < maxTrueSliceLen; ++
IS) {
580 for (
auto &S : TrueSlices) {
582 TrueSlicesInterleaved.
push_back(S.top());
587 for (StackSizeType IS = 0;
IS < maxFalseSliceLen; ++
IS) {
588 for (
auto &S : FalseSlices) {
590 FalseSlicesInterleaved.
push_back(S.top());
597 SelectLike &
SI = ASI.Selects.front();
598 SelectLike &LastSI = ASI.Selects.back();
606 SplitPt.setHeadBit(
true);
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())
624 for (
auto *HI : HoistInstrs)
625 HI->moveBefore(
SI.getI()->getIterator());
642 std::next(LastSI.getI()->getIterator()));
647 BasicBlock *TrueBlock =
nullptr, *FalseBlock =
nullptr;
648 UncondBrInst *TrueBranch =
nullptr, *FalseBranch =
nullptr;
650 auto HasSelectLike = [](SelectGroup &SG,
bool IsTrue) {
651 for (
auto &SL : SG.Selects) {
652 if ((IsTrue ? SL.getTrueValue() : SL.getFalseValue()) ==
nullptr)
657 if (!TrueSlicesInterleaved.
empty() || HasSelectLike(ASI,
true)) {
661 TrueBranch->
setDebugLoc(LastSI.getI()->getDebugLoc());
662 for (
Instruction *TrueInst : TrueSlicesInterleaved)
665 if (!FalseSlicesInterleaved.
empty() || HasSelectLike(ASI,
false)) {
670 FalseBranch->setDebugLoc(LastSI.getI()->getDebugLoc());
671 for (
Instruction *FalseInst : FalseSlicesInterleaved)
672 FalseInst->moveBefore(FalseBranch->getIterator());
676 if (TrueBlock == FalseBlock) {
677 assert(TrueBlock ==
nullptr &&
678 "Unexpected basic block transform while optimizing select");
683 FalseBranch->setDebugLoc(
SI.getI()->getDebugLoc());
692 if (TrueBlock ==
nullptr) {
695 TrueBlock = StartBlock;
696 }
else if (FalseBlock ==
nullptr) {
699 FalseBlock = StartBlock;
706 IB.CreateFreeze(ASI.Condition, ASI.Condition->getName() +
".frozen");
713 auto InsertionPoint = EndBlock->
begin();
714 for (SelectLike &
SI : ASI.Selects) {
722 for (
auto &SG : ProfSIGroups) {
723 if (SG.Condition ==
SI.getI())
727 SI.getI()->replaceAllUsesWith(PN);
734 ++NumSelectsConverted;
738 CondBr->
copyMetadata(*SelectWithProfile, {llvm::LLVMContext::MD_prof});
739 if (SelectWithProfileIsInverted)
746 for (SelectLike &
SI : ASI.Selects)
747 SI.getI()->eraseFromParent();
751void SelectOptimizeImpl::collectSelectGroups(
BasicBlock &BB,
752 SelectGroups &SIGroups) {
762 struct SelectLikeInfo {
766 unsigned ConditionIdx;
777 auto ProcessSelectInfo = [&SelectInfo, &SeenCmp](
Instruction *
I) {
780 return SelectInfo.
end();
785 Cond->getType()->isIntegerTy(1)) {
787 return SelectInfo.
insert({
I, {
Cond,
true, Inverted, 0}}).first;
791 return SelectInfo.
insert({
I, {
Cond,
true,
true, 0}}).first;
797 return SelectInfo.
insert({
I, {
Cond,
false, Inverted, 0}}).first;
802 I->getType()->getIntegerBitWidth() == Shift->
getZExtValue() + 1) {
803 for (
auto *CmpI : SeenCmp) {
804 auto Pred = CmpI->getPredicate();
805 if (Val != CmpI->getOperand(0))
817 return SelectInfo.
insert({
I, {CmpI,
true, Inverted, 0}}).first;
820 return SelectInfo.
end();
828 auto MatchZExtOrSExtPattern =
830 auto MatchShiftPattern =
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();
843 if (
I->getOpcode() == Instruction::Or &&
I->getType()->isIntegerTy(1))
844 return SelectInfo.
end();
850 unsigned Idx =
I->getOpcode() == Instruction::Sub ? 1 : 0;
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;
861 return SelectInfo.
end();
864 bool AlreadyProcessed =
false;
867 while (BBIt != BB.
end()) {
872 if (!AlreadyProcessed)
873 It = ProcessSelectInfo(
I);
875 AlreadyProcessed =
false;
877 if (It == SelectInfo.
end() || It->second.IsAuxiliary)
880 if (!
TTI->shouldTreatInstructionLikeSelect(
I))
885 if (!
Cond->getType()->isIntegerTy(1))
888 SelectGroup SIGroup = {
Cond, {}};
889 SIGroup.Selects.emplace_back(
I, It->second.IsInverted,
890 It->second.ConditionIdx);
894 if (!isSelectKindSupported(SIGroup.Selects.front()))
897 while (BBIt != BB.
end()) {
906 It = ProcessSelectInfo(NI);
907 if (It == SelectInfo.
end()) {
908 AlreadyProcessed =
true;
913 auto [CurrCond, IsAux, IsRev, CondIdx] = It->second;
914 if (
Cond != CurrCond) {
915 AlreadyProcessed =
true;
920 SIGroup.Selects.emplace_back(NI, IsRev, CondIdx);
924 dbgs() <<
"New Select group (" << SIGroup.Selects.size() <<
") with\n";
925 for (
auto &
SI : SIGroup.Selects)
926 dbgs() <<
" " << *
SI.getI() <<
"\n";
929 SIGroups.push_back(SIGroup);
933void SelectOptimizeImpl::findProfitableSIGroupsBase(
934 SelectGroups &SIGroups, SelectGroups &ProfSIGroups) {
935 for (SelectGroup &ASI : SIGroups) {
936 ++NumSelectOptAnalyzed;
937 if (isConvertToBranchProfitableBase(ASI))
938 ProfSIGroups.push_back(ASI);
948void SelectOptimizeImpl::findProfitableSIGroupsInnerLoops(
949 const Loop *L, SelectGroups &SIGroups, SelectGroups &ProfSIGroups) {
950 NumSelectOptAnalyzed += SIGroups.size();
962 CostInfo LoopCost[2] = {{Scaled64::getZero(), Scaled64::getZero()},
963 {Scaled64::getZero(), Scaled64::getZero()}};
964 if (!computeLoopCosts(L, SIGroups, InstCostMap, LoopCost) ||
965 !checkLoopHeuristics(L, LoopCost)) {
969 for (SelectGroup &ASI : SIGroups) {
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);
978 if (BranchCost < SelectCost) {
980 ASI.Selects.front().getI());
981 OR <<
"Profitable to convert to branch (loop analysis). BranchCost="
982 << BranchCost.toString() <<
", SelectCost=" << SelectCost.toString()
985 ++NumSelectConvertedLoop;
986 ProfSIGroups.push_back(ASI);
989 ASI.Selects.front().getI());
990 ORmiss <<
"Select is more profitable (loop analysis). BranchCost="
991 << BranchCost.toString()
992 <<
", SelectCost=" << SelectCost.toString() <<
". ";
998bool SelectOptimizeImpl::isConvertToBranchProfitableBase(
999 const SelectGroup &ASI) {
1000 const SelectLike &
SI = ASI.Selects.front();
1009 ORmiss <<
"Not converted to branch because of cold basic block. ";
1015 if (
SI.getI()->getMetadata(LLVMContext::MD_unpredictable)) {
1017 ORmiss <<
"Not converted to branch because of unpredictable branch. ";
1025 ++NumSelectConvertedHighPred;
1026 OR <<
"Converted to branch because of highly predictable branch. ";
1033 if (hasExpensiveColdOperand(ASI)) {
1034 ++NumSelectConvertedExpColdOperand;
1035 OR <<
"Converted to branch because of expensive cold operand.";
1043 auto *BB =
SI.getI()->getParent();
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.";
1052 ORmiss <<
"Not profitable to convert to branch (base heuristic).";
1059 return (Numerator + (Denominator / 2)) / Denominator;
1069bool SelectOptimizeImpl::hasExpensiveColdOperand(
const SelectGroup &ASI) {
1070 bool ColdOperand =
false;
1071 uint64_t TrueWeight, FalseWeight, TotalWeight;
1073 uint64_t MinWeight = std::min(TrueWeight, FalseWeight);
1074 TotalWeight = TrueWeight + FalseWeight;
1076 ColdOperand = TotalWeight * Opts->cold_operand_threshold > 100 * MinWeight;
1079 ASI.Selects.front().getI());
1080 ORmiss <<
"Profile data available but missing branch-weights metadata for "
1081 "select instruction. ";
1088 for (SelectLike
SI : ASI.Selects) {
1091 if (TrueWeight < FalseWeight) {
1093 HotWeight = FalseWeight;
1096 HotWeight = TrueWeight;
1099 std::stack<Instruction *> ColdSlice;
1100 getExclBackwardsSlice(ColdI, ColdSlice,
SI.getI());
1102 while (!ColdSlice.empty()) {
1103 SliceCost +=
TTI->getInstructionCost(ColdSlice.top(),
1113 if (AdjSliceCost >= Opts->cold_operand_max_cost_multiplier *
1129 while (&*It !=
SI) {
1130 if (It->mayWriteToMemory())
1143void SelectOptimizeImpl::getExclBackwardsSlice(
Instruction *
I,
1144 std::stack<Instruction *> &Slice,
1146 const SelectGroup *Group) {
1148 std::queue<Instruction *> Worklist;
1150 while (!Worklist.empty()) {
1158 if (!
II->hasOneUse())
1164 if (ForSinking && (
II->isTerminator() ||
II->mayHaveSideEffects() ||
1170 if (ForSinking && Group &&
1171 llvm::any_of(Group->Selects, [&](
auto &S) { return S.getI() == II; }))
1196bool SelectOptimizeImpl::isSelectHighlyPredictable(
const SelectLike
SI) {
1200 uint64_t Sum = TrueWeight + FalseWeight;
1203 if (Probability >
TTI->getPredictableBranchThreshold())
1210bool SelectOptimizeImpl::checkLoopHeuristics(
const Loop *L,
1211 const CostInfo LoopCost[2]) {
1215 if (!Opts->select_opti_loop_level_heuristics)
1219 &*
L->getHeader()->getFirstNonPHIIt());
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 "
1229 Scaled64 Gain[2] = {LoopCost[0].PredCost - LoopCost[0].NonPredCost,
1230 LoopCost[1].PredCost - LoopCost[1].NonPredCost};
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() <<
"%. ";
1252 if (Gain[1] > Gain[0]) {
1253 Scaled64 GradientGain = Scaled64::get(100) * (Gain[1] - Gain[0]) /
1254 (LoopCost[1].PredCost - LoopCost[0].PredCost);
1256 Scaled64::get(Opts->select_opti_loop_gradient_gain_threshold)) {
1257 ORmissL <<
"No select conversion in the loop due to small gradient gain. "
1259 << GradientGain.toString() <<
"%. ";
1265 else if (Gain[1] < Gain[0]) {
1267 <<
"No select conversion in the loop due to negative gradient gain. ";
1281bool SelectOptimizeImpl::computeLoopCosts(
1282 const Loop *L,
const SelectGroups &SIGroups,
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);
1290 const unsigned Iterations = 2;
1291 for (
unsigned Iter = 0; Iter < Iterations; ++Iter) {
1293 CostInfo &MaxCost = LoopCost[Iter];
1299 Scaled64 IPredCost = Scaled64::getZero(),
1300 INonPredCost = Scaled64::getZero();
1305 for (
const Use &U :
I.operands()) {
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);
1314 auto ILatency = computeInstCost(&
I);
1317 ORmissL <<
"Invalid instruction cost preventing analysis and "
1318 "optimization of the inner-most loop containing this "
1323 IPredCost += Scaled64::get(*ILatency);
1324 INonPredCost += Scaled64::get(*ILatency);
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);
1340 Scaled64 CondCost = Scaled64::getZero();
1342 if (
auto It = InstCostMap.
find(CI); It != InstCostMap.
end())
1343 CondCost = It->second.NonPredCost;
1344 Scaled64 MispredictCost = getMispredictionCost(
SI, CondCost);
1346 INonPredCost = PredictedPathCost + MispredictCost;
1349 << INonPredCost <<
" for " <<
I <<
"\n");
1351 InstCostMap[&
I] = {IPredCost, INonPredCost};
1352 MaxCost.PredCost = std::max(MaxCost.PredCost, IPredCost);
1353 MaxCost.NonPredCost = std::max(MaxCost.NonPredCost, INonPredCost);
1357 <<
" MaxCost = " << MaxCost.PredCost <<
" "
1358 << MaxCost.NonPredCost <<
"\n");
1364SelectOptimizeImpl::getSImap(
const SelectGroups &SIGroups) {
1366 for (
const SelectGroup &ASI : SIGroups)
1367 for (
const SelectLike &
SI : ASI.Selects)
1373SelectOptimizeImpl::getSGmap(
const SelectGroups &SIGroups) {
1375 for (
const SelectGroup &ASI : SIGroups)
1376 for (
const SelectLike &
SI : ASI.Selects)
1381std::optional<uint64_t>
1382SelectOptimizeImpl::computeInstCost(
const Instruction *
I) {
1386 return std::optional<uint64_t>(ICost.
getValue());
1387 return std::nullopt;
1391SelectOptimizeImpl::getMispredictionCost(
const SelectLike
SI,
1392 const Scaled64 CondCost) {
1397 uint64_t MispredictRate = Opts->mispredict_default_rate;
1400 if (isSelectHighlyPredictable(
SI))
1406 Scaled64 MispredictCost =
1407 std::max(Scaled64::get(MispredictPenalty), CondCost) *
1408 Scaled64::get(MispredictRate);
1409 MispredictCost /= Scaled64::get(100);
1411 return MispredictCost;
1417SelectOptimizeImpl::getPredictedPathCost(Scaled64 TrueCost, Scaled64 FalseCost,
1418 const SelectLike
SI) {
1419 Scaled64 PredPathCost;
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;
1432 PredPathCost = std::max(TrueCost * Scaled64::get(3) + FalseCost,
1433 FalseCost * Scaled64::get(3) + TrueCost);
1434 PredPathCost /= Scaled64::get(4);
1435 return PredPathCost;
1438bool SelectOptimizeImpl::isSelectKindSupported(
const SelectLike
SI) {
1440 if (
SI.getType()->isVectorTy())
const TargetLowering & TLI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
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)
print mir2vec MIR2Vec Vocabulary Printer Pass
uint64_t IntrinsicInst * II
FunctionAnalysisManager FAM
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
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)
static SymbolRef::Type getType(const Symbol *Sym)
This file describes how to lower LLVM code to machine code.
Target-Independent Code Generator Pass Configuration Options pass.
static const uint32_t IV[8]
AnalysisUsage & addRequired()
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
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.
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.
InstListType::iterator iterator
Instruction iterators...
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.
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
@ ICMP_SLE
signed less or equal
@ ICMP_SGT
signed greater than
@ ICMP_SGE
signed greater or equal
This is the shared class of boolean and integer constants.
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
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)
DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
Common features for diagnostics dealing with optimization remarks that are used by both IR and MIR pa...
std::string getMsg() const
FunctionPass class - This class is used to implement most global optimizations.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
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.
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.
Represents a single loop in the control flow graph.
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'.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
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.
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.
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
bool isIntegerTy() const
True if this is an instance of IntegerType.
Unconditional Branch instruction.
static UncondBrInst * Create(BasicBlock *Target, InsertPosition InsertBefore=nullptr)
A Use represents the edge between a Value definition and its users.
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
LLVM_ABI void takeName(Value *V)
Transfer the name from V to this value.
const ParentTy * getParent() const
self_iterator getIterator()
#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.
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.
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.
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.
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...
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
constexpr T divideNearest(U Numerator, V Denominator)
Returns (Numerator / Denominator) rounded by round-half-up.
auto dyn_cast_or_null(const Y &Val)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
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...
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.
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.