50#define DEBUG_TYPE "early-ifcvt"
53STATISTIC(NumDiamondsConv,
"Number of diamonds converted");
55STATISTIC(NumTrianglesConv,
"Number of triangles converted");
57 "Number of data dependent conditional branches encountered");
58STATISTIC(NumLikelyBiased,
"Number of branches with a hot path encountered");
60 "Number of branches with reduced critical-path budget");
85 const CodeGenOptions *Opts;
105 bool isTriangle()
const {
return TBB == Tail || FBB == Tail; }
108 MachineBasicBlock *getTPred()
const {
return TBB == Tail ? Head : TBB; }
111 MachineBasicBlock *getFPred()
const {
return FBB == Tail ? Head : FBB; }
118 TargetInstrInfo::SelectExpansion Select;
120 PHIInfo(MachineInstr *phi) : PHI(
phi) {}
126 SmallVector<MachineOperand, 4> Cond;
131 SmallPtrSet<MachineInstr*, 8> InsertAfter;
134 BitVector ClobberedRegUnits;
137 SparseSet<MCRegUnit, MCRegUnit, MCRegUnitToIndex> LiveRegUnits;
145 bool canSpeculateInstrs(MachineBasicBlock *
MBB);
149 bool canPredicateInstrs(MachineBasicBlock *
MBB);
153 bool InstrDependenciesAllowIfConv(MachineInstr *
I);
157 void PredicateBlock(MachineBasicBlock *
MBB,
bool ReversePredicate);
160 bool findInsertionPoint();
163 void replacePHIInstrs();
166 void rewritePHIOperands();
175 LiveRegUnits.clear();
176 LiveRegUnits.setUniverse(TRI->getNumRegUnits());
177 ClobberedRegUnits.clear();
178 ClobberedRegUnits.resize(TRI->getNumRegUnits());
185 bool canConvertIf(MachineBasicBlock *
MBB,
bool Predicate =
false);
189 void convertIf(SmallVectorImpl<MachineBasicBlock *> &RemoveBlocks,
190 bool Predicate =
false);
214 for (MachineInstr &
MI :
216 if (
MI.isDebugInstr())
219 if (++
InstrCount > Opts->early_ifcvt_limit && !Opts->stress_early_ifcvt) {
221 << Opts->early_ifcvt_limit <<
" instructions.\n");
240 bool DontMoveAcrossStore =
true;
241 if (!
MI.isSafeToMove(DontMoveAcrossStore)) {
247 if (!InstrDependenciesAllowIfConv(&
MI))
257bool SSAIfConv::InstrDependenciesAllowIfConv(MachineInstr *
I) {
258 for (
const MachineOperand &MO :
I->operands()) {
259 if (MO.isRegMask()) {
270 ClobberedRegUnits.
set(
static_cast<unsigned>(Unit));
281 LLVM_DEBUG(
dbgs() <<
"Can't insert instructions below terminator.\n");
296bool SSAIfConv::canPredicateInstrs(MachineBasicBlock *
MBB) {
311 if (
I->isDebugInstr())
314 if (++
InstrCount > Opts->early_ifcvt_limit && !Opts->stress_early_ifcvt) {
316 << Opts->early_ifcvt_limit <<
" instructions.\n");
339 if (!InstrDependenciesAllowIfConv(&(*
I)))
346void SSAIfConv::PredicateBlock(MachineBasicBlock *
MBB,
bool ReversePredicate) {
347 auto Condition =
Cond;
348 if (ReversePredicate) {
350 assert(CanRevCond &&
"Reversed predicate is not supported");
357 if (
I->isDebugInstr())
373bool SSAIfConv::findInsertionPoint() {
376 LiveRegUnits.
clear();
384 if (InsertAfter.
count(&*
I)) {
390 for (
const MachineOperand &MO :
I->operands()) {
400 LiveRegUnits.
erase(Unit);
406 while (!Reads.
empty())
408 if (ClobberedRegUnits.
test(
static_cast<unsigned>(Unit)))
409 LiveRegUnits.
insert(Unit);
412 if (
I != FirstTerm &&
I->isTerminator())
417 if (!LiveRegUnits.
empty()) {
419 dbgs() <<
"Would clobber";
420 for (MCRegUnit LRU : LiveRegUnits)
422 dbgs() <<
" live before " << *
I;
441bool SSAIfConv::canConvertIf(MachineBasicBlock *
MBB,
bool Predicate) {
447 MachineBasicBlock *Succ0 = Head->
succ_begin()[0];
448 MachineBasicBlock *Succ1 = Head->
succ_begin()[1];
471 if (!
Tail->livein_empty()) {
484 if (!Predicate && (
Tail->empty() || !
Tail->front().isPHI())) {
498 LLVM_DEBUG(
dbgs() <<
"analyzeBranch didn't find conditional branch.\n");
505 LLVM_DEBUG(
dbgs() <<
"analyzeBranch found an unconditional branch.\n");
511 FBB =
TBB == Succ0 ? Succ1 : Succ0;
515 MachineBasicBlock *TPred = getTPred();
516 MachineBasicBlock *FPred = getFPred();
518 I !=
E &&
I->isPHI(); ++
I) {
520 PHIInfo &PI = PHIs.
back();
522 for (
unsigned i = 1; i != PI.PHI->getNumOperands(); i += 2) {
523 if (PI.PHI->getOperand(i+1).getMBB() == TPred)
524 PI.TReg = PI.PHI->getOperand(i).getReg();
525 if (PI.PHI->getOperand(i+1).getMBB() == FPred)
526 PI.FReg = PI.PHI->getOperand(i).getReg();
528 assert(PI.TReg.isVirtual() &&
"Bad PHI");
529 assert(PI.FReg.isVirtual() &&
"Bad PHI");
532 if (!
TII->canInsertSelect(*Head,
Cond, PI.PHI->getOperand(0).getReg(),
533 PI.TReg, PI.FReg, PI.Select)) {
541 ClobberedRegUnits.
reset();
543 if (
TBB != Tail && !canPredicateInstrs(
TBB))
545 if (FBB != Tail && !canPredicateInstrs(FBB))
548 if (
TBB != Tail && !canSpeculateInstrs(
TBB))
550 if (FBB != Tail && !canSpeculateInstrs(FBB))
556 if (!findInsertionPoint())
573 if (!TReg.isVirtual() || !FReg.
isVirtual())
595 return MO.isReg() && MO.getReg().isPhysical();
600 if (!
TII->produceSameValue(*TDef, *FDef, &
MRI))
606 if (TIdx == -1 || FIdx == -1)
615void SSAIfConv::replacePHIInstrs() {
616 assert(
Tail->pred_size() == 2 &&
"Cannot replace PHIs");
618 assert(FirstTerm != Head->
end() &&
"No terminators");
619 DebugLoc HeadDL = FirstTerm->getDebugLoc();
622 for (PHIInfo &PI : PHIs) {
624 Register DstReg = PI.PHI->getOperand(0).getReg();
628 BuildMI(*Head, FirstTerm, HeadDL,
TII->get(TargetOpcode::COPY), DstReg)
631 TII->insertSelect(*Head, FirstTerm, HeadDL, DstReg,
Cond, PI.TReg,
635 PI.PHI->eraseFromParent();
643void SSAIfConv::rewritePHIOperands() {
645 assert(FirstTerm != Head->
end() &&
"No terminators");
646 DebugLoc HeadDL = FirstTerm->getDebugLoc();
649 for (PHIInfo &PI : PHIs) {
658 Register PHIDst = PI.PHI->getOperand(0).getReg();
660 TII->insertSelect(*Head, FirstTerm, HeadDL,
661 DstReg,
Cond, PI.TReg, PI.FReg);
666 for (
unsigned i = PI.PHI->getNumOperands(); i != 1; i -= 2) {
667 MachineBasicBlock *
MBB = PI.PHI->getOperand(i-1).getMBB();
668 if (
MBB == getTPred()) {
669 PI.PHI->getOperand(i-1).setMBB(Head);
670 PI.PHI->getOperand(i-2).setReg(DstReg);
671 }
else if (
MBB == getFPred()) {
672 PI.PHI->removeOperand(i-1);
673 PI.PHI->removeOperand(i-2);
685void SSAIfConv::convertIf(SmallVectorImpl<MachineBasicBlock *> &RemoveBlocks,
687 assert(Head && Tail &&
TBB && FBB &&
"Call canConvertIf first.");
698 PredicateBlock(
TBB,
false);
703 PredicateBlock(FBB,
true);
707 bool ExtraPreds =
Tail->pred_size() != 2;
709 rewritePHIOperands();
717 TBB->removeSuccessor(Tail,
true);
749 if (Tail != &
Tail->getParent()->back())
750 Tail->moveAfter(&
Tail->getParent()->back());
766class EarlyIfConverter {
767 const CodeGenOptions &Opts;
768 const TargetInstrInfo *
TII =
nullptr;
769 const TargetRegisterInfo *
TRI =
nullptr;
770 const TargetSubtargetInfo *STI =
nullptr;
771 MachineRegisterInfo *
MRI =
nullptr;
772 MachineDominatorTree *DomTree =
nullptr;
773 MachineLoopInfo *
Loops =
nullptr;
774 MachineTraceMetrics *Traces =
nullptr;
776 MachineBranchProbabilityInfo &MBPI;
781 DenseMap<const MachineBasicBlock *, unsigned> NoCallBlocksCache;
784 EarlyIfConverter(
const CodeGenOptions &Opts, MachineDominatorTree &DT,
785 MachineLoopInfo &LI, MachineTraceMetrics &MTM,
786 MachineBranchProbabilityInfo &MBPI)
787 : Opts(Opts), DomTree(&DT),
Loops(&LI), Traces(&MTM), MBPI(MBPI) {}
788 EarlyIfConverter() =
delete;
793 bool tryConvertIf(MachineBasicBlock *);
794 void invalidateTraces();
795 bool shouldConvertIf();
796 bool isConditionDataDependent();
797 bool doOperandsComeFromMemory(
const MachineInstr *ConditionDef);
798 bool hasCallOrLoopInRange(
const MachineInstr *From,
const MachineInstr *To);
801class EarlyIfConverterLegacy :
public MachineFunctionPass {
804 EarlyIfConverterLegacy() : MachineFunctionPass(
ID) {}
805 void getAnalysisUsage(AnalysisUsage &AU)
const override;
807 StringRef getPassName()
const override {
return "Early If-Conversion"; }
811char EarlyIfConverterLegacy::ID = 0;
822void EarlyIfConverterLegacy::getAnalysisUsage(
AnalysisUsage &AU)
const {
836void updateDomTree(MachineDominatorTree *DomTree,
const SSAIfConv &IfConv,
842 for (
auto *
B : Removed) {
844 assert(Node != HeadNode &&
"Cannot erase the head node");
845 while (!
Node->isLeaf()) {
846 assert(
Node->getBlock() == IfConv.Tail &&
"Unexpected children");
854void updateLoops(MachineLoopInfo *
Loops,
858 for (
auto *
B : Removed)
864void EarlyIfConverter::invalidateTraces() {
875 const PseudoSourceValue *PSV = MOp->getPseudoValue();
876 return PSV && PSV->isConstantPool();
886bool EarlyIfConverter::hasCallOrLoopInRange(
const MachineInstr *From,
887 const MachineInstr *To) {
891 LLVM_DEBUG(
dbgs() <<
" checking for a call or loop between " << *From
893 assert(DomTree->
dominates(From, To) &&
"From is expected to dominate To");
895 const MachineBasicBlock *FromBB = From->
getParent();
896 const MachineBasicBlock *ToBB = To->
getParent();
898 unsigned NumScanned = 0;
899 auto HitSearchLimit = [&](
unsigned N) {
901 if (NumScanned <= Opts.early_ifcvt_max_region_instrs)
904 << Opts.early_ifcvt_max_region_instrs
905 <<
" instructions\n");
908 auto FoundCall = [](
const MachineInstr &
MI) {
912 auto IsCallOrHitSearchLimit = [&](
const MachineInstr &
MI) {
913 if (HitSearchLimit(1))
917 return FoundCall(
MI);
921 if (FromBB == ToBB) {
925 if (IsCallOrHitSearchLimit(
MI))
934 if (IsCallOrHitSearchLimit(
MI))
936 for (
const MachineInstr &
MI :
939 if (IsCallOrHitSearchLimit(
MI))
944 SmallPtrSet<const MachineBasicBlock *, 16> Enqueued = {FromBB, ToBB};
946 auto Enqueue = [&](
const MachineBasicBlock *BB) {
954 while (!Worklist.
empty()) {
960 if (
const MachineLoop *BBLoop =
Loops->getLoopFor(BB)) {
961 if (!BBLoop->contains(ToBB) && !BBLoop->contains(FromBB)) {
969 auto CacheIt = NoCallBlocksCache.find(BB);
970 if (CacheIt != NoCallBlocksCache.end()) {
971 if (HitSearchLimit(CacheIt->second))
974 unsigned NumBlockInstrs = 0;
975 for (
const MachineInstr &
MI :
979 if (IsCallOrHitSearchLimit(
MI))
982 NoCallBlocksCache[BB] = NumBlockInstrs;
998bool EarlyIfConverter::doOperandsComeFromMemory(
999 const MachineInstr *ConditionDef) {
1004 LLVM_DEBUG(
dbgs() <<
" doOperandsComeFromMemory starting from reg "
1010 MachineLoop *IfConvLoop =
Loops->getLoopFor(IfConv.Head);
1013 SmallPtrSet<const MachineInstr *, 8> VisitedInstrs;
1014 SmallVector<const MachineInstr *> Worklist;
1024 while (!Worklist.
empty() &&
1025 VisitedInstrs.
size() < Opts.early_ifcvt_max_steps) {
1027 if (!VisitedInstrs.
insert(
MI).second)
1036 const MachineBasicBlock *Parent =
MI->getParent();
1037 MachineLoop *ParentLoop =
Loops->getLoopFor(Parent);
1040 if (IfConvLoop && ParentLoop != IfConvLoop)
1047 !
MI->isDereferenceableInvariantLoad()) {
1052 if (!DomTree->
dominates(
MI, Br) || hasCallOrLoopInRange(
MI, Br))
1059 for (
const MachineOperand &MO :
MI->operands()) {
1060 if (!MO.isReg() || !MO.isUse())
1067 if (!VisitedInstrs.
count(UseDef)) {
1078bool EarlyIfConverter::isConditionDataDependent() {
1079 TargetInstrInfo::MachineBranchPredicate MBP;
1080 if (
TII->analyzeBranchPredicate(*IfConv.Head, MBP,
false))
1091 if (TBBProb != FBBProb) {
1109 if (Delta < 0 && Cyc + Delta > Cyc)
1121 return R <<
ore::NV(
C.Key,
C.Value) << (
C.Value == 1 ?
" cycle" :
" cycles");
1128bool EarlyIfConverter::shouldConvertIf() {
1130 if (Opts.stress_early_ifcvt)
1135 MachineLoop *CurrentLoop =
Loops->getLoopFor(IfConv.Head);
1141 if (CurrentLoop &&
any_of(IfConv.Cond, [&](MachineOperand &MO) {
1142 if (!MO.isReg() || !MO.isUse())
1144 Register Reg = MO.getReg();
1145 if (Reg.isPhysical())
1148 MachineInstr *Def = MRI->getVRegDef(Reg);
1149 return CurrentLoop->isLoopInvariant(*Def) ||
1150 all_of(Def->operands(), [&](MachineOperand &Op) {
1153 if (!Op.isReg() || !Op.isUse())
1155 Register Reg = Op.getReg();
1156 if (Reg.isPhysical())
1159 MachineInstr *Def = MRI->getVRegDef(Reg);
1160 return CurrentLoop->isLoopInvariant(*Def);
1166 MinInstr = Traces->getEnsemble(MachineTraceStrategy::TS_MinInstrCount);
1170 LLVM_DEBUG(
dbgs() <<
"TBB: " << TBBTrace <<
"FBB: " << FBBTrace);
1179 bool DataDependent =
false;
1180 if (Opts.enable_early_ifcvt_data_dependent)
1181 DataDependent = isConditionDataDependent();
1183 const unsigned MispredictPenalty = STI->getMispredictionPenalty();
1184 unsigned CritLimit =
1185 DataDependent ? MispredictPenalty : MispredictPenalty / 2;
1186 const BranchProbability ColdProb =
1187 std::min(MBPI.getEdgeProbability(IfConv.Head, IfConv.TBB),
1188 MBPI.getEdgeProbability(IfConv.Head, IfConv.FBB));
1189 const unsigned ColdEdgePercent =
1190 std::min(Opts.early_ifcvt_cold_edge_threshold, 50U);
1191 const bool StronglyBiased =
1192 ColdProb < BranchProbability(ColdEdgePercent, 100);
1193 if (StronglyBiased) {
1195 ++NumStronglyBiased;
1198 MachineBasicBlock &
MBB = *IfConv.Head;
1202 <<
", critical-path budget: " << CritLimit <<
" cycles\n");
1203 if (StronglyBiased) {
1205 return MachineOptimizationRemarkAnalysis(
DEBUG_TYPE,
1206 "StronglyBiasedBranch",
1208 <<
"branch has a cold edge below "
1209 <<
ore::NV(
"ColdEdgeThreshold", ColdEdgePercent)
1210 <<
"%, using a critical-path "
1211 "extension budget of "
1212 <<
ore::NV(
"CritLimit", CritLimit) <<
" cycles";
1217 if (DataDependent) {
1219 return MachineOptimizationRemarkAnalysis(
DEBUG_TYPE,
1220 "DataDependentCondition",
1222 <<
"branch condition is data-dependent (from memory load), "
1223 <<
"using higher CritLimit of " <<
ore::NV(
"CritLimit", CritLimit)
1232 if (IfConv.TBB != IfConv.Tail)
1236 <<
", minimal critical path " << MinCrit <<
'\n');
1237 if (ResLength > MinCrit + CritLimit) {
1240 MachineOptimizationRemarkMissed
R(
DEBUG_TYPE,
"IfConversion",
1242 R <<
"did not if-convert branch: the resulting critical path ("
1243 << Cycles{
"ResLength", ResLength}
1244 <<
") would extend the shorter leg's critical path ("
1245 << Cycles{
"MinCrit", MinCrit} <<
") by more than the threshold of "
1246 << Cycles{
"CritLimit", CritLimit}
1247 <<
", which cannot be hidden by available ILP.";
1257 unsigned BranchDepth =
1264 struct CriticalPathInfo {
1268 CriticalPathInfo
Cond{};
1269 CriticalPathInfo TBlock{};
1270 CriticalPathInfo FBlock{};
1271 bool ShouldConvert =
true;
1272 for (SSAIfConv::PHIInfo &PI : IfConv.PHIs) {
1279 if (CondDepth > MaxDepth) {
1280 unsigned Extra = CondDepth - MaxDepth;
1281 LLVM_DEBUG(
dbgs() <<
"Condition adds " << Extra <<
" cycles.\n");
1282 if (Extra >
Cond.Extra)
1283 Cond = {Extra, CondDepth};
1284 if (Extra > CritLimit) {
1286 ShouldConvert =
false;
1293 if (TDepth > MaxDepth) {
1294 unsigned Extra = TDepth - MaxDepth;
1296 if (Extra > TBlock.Extra)
1297 TBlock = {Extra, TDepth};
1298 if (Extra > CritLimit) {
1300 ShouldConvert =
false;
1307 if (FDepth > MaxDepth) {
1308 unsigned Extra = FDepth - MaxDepth;
1310 if (Extra > FBlock.Extra)
1311 FBlock = {Extra, FDepth};
1312 if (Extra > CritLimit) {
1314 ShouldConvert =
false;
1322 const CriticalPathInfo
Short = TBlock.Extra > FBlock.Extra ? FBlock : TBlock;
1323 const CriticalPathInfo
Long = TBlock.Extra > FBlock.Extra ? TBlock : FBlock;
1325 if (ShouldConvert) {
1327 MachineOptimizationRemark
R(
DEBUG_TYPE,
"IfConversion",
1329 R <<
"performing if-conversion on branch: the condition adds "
1330 << Cycles{
"CondCycles",
Cond.Extra} <<
" to the critical path";
1331 if (
Short.Extra > 0)
1332 R <<
", and the short leg adds another "
1333 << Cycles{
"ShortCycles",
Short.Extra};
1335 R <<
", and the long leg adds another "
1336 << Cycles{
"LongCycles",
Long.Extra};
1337 R <<
", each staying under the threshold of "
1338 << Cycles{
"CritLimit", CritLimit} <<
".";
1343 MachineOptimizationRemarkMissed
R(
DEBUG_TYPE,
"IfConversion",
1345 R <<
"did not if-convert branch: the condition would add "
1346 << Cycles{
"CondCycles",
Cond.Extra} <<
" to the critical path";
1347 if (
Cond.Extra > CritLimit)
1348 R <<
" exceeding the limit of " << Cycles{
"CritLimit", CritLimit};
1349 if (
Short.Extra > 0) {
1350 R <<
", and the short leg would add another "
1351 << Cycles{
"ShortCycles",
Short.Extra};
1352 if (
Short.Extra > CritLimit)
1353 R <<
" exceeding the limit of " << Cycles{
"CritLimit", CritLimit};
1355 if (
Long.Extra > 0) {
1356 R <<
", and the long leg would add another "
1357 << Cycles{
"LongCycles",
Long.Extra};
1358 if (
Long.Extra > CritLimit)
1359 R <<
" exceeding the limit of " << Cycles{
"CritLimit", CritLimit};
1366 return ShouldConvert;
1371bool EarlyIfConverter::tryConvertIf(MachineBasicBlock *
MBB) {
1373 while (IfConv.canConvertIf(
MBB) && shouldConvertIf()) {
1376 SmallVector<MachineBasicBlock *, 4> RemoveBlocks;
1377 IfConv.convertIf(RemoveBlocks);
1379 updateDomTree(DomTree, IfConv, RemoveBlocks);
1380 updateLoops(
Loops, RemoveBlocks);
1383 NoCallBlocksCache.erase(IfConv.Head);
1384 for (MachineBasicBlock *
MBB : RemoveBlocks) {
1385 NoCallBlocksCache.erase(
MBB);
1393 LLVM_DEBUG(
dbgs() <<
"********** EARLY IF-CONVERSION **********\n"
1394 <<
"********** Function: " << MF.
getName() <<
'\n');
1414 if (tryConvertIf(DomNode->getBlock()))
1441bool EarlyIfConverterLegacy::runOnMachineFunction(
MachineFunction &MF) {
1446 getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
1447 MachineLoopInfo &LI = getAnalysis<MachineLoopInfoWrapperPass>().getLI();
1449 getAnalysis<MachineTraceMetricsWrapperPass>().getMTM();
1451 getAnalysis<MachineBranchProbabilityInfoWrapperPass>().getMBPI();
1474 void getAnalysisUsage(AnalysisUsage &AU)
const override;
1476 StringRef getPassName()
const override {
return "Early If-predicator"; }
1479 bool tryConvertIf(MachineBasicBlock *);
1480 bool shouldConvertIf();
1485#define DEBUG_TYPE "early-if-predicator"
1487char EarlyIfPredicator::ID = 0;
1497void EarlyIfPredicator::getAnalysisUsage(
AnalysisUsage &AU)
const {
1507bool EarlyIfPredicator::shouldConvertIf() {
1509 if (IfConv.isTriangle()) {
1510 MachineBasicBlock &IfBlock =
1511 (IfConv.TBB == IfConv.Tail) ? *IfConv.FBB : *IfConv.
TBB;
1513 unsigned ExtraPredCost = 0;
1514 unsigned Cycles = 0;
1515 for (MachineInstr &
I : IfBlock) {
1516 unsigned NumCycles = SchedModel.computeInstrLatency(&
I,
false);
1518 Cycles += NumCycles - 1;
1519 ExtraPredCost +=
TII->getPredicationCost(
I);
1525 unsigned TExtra = 0;
1526 unsigned FExtra = 0;
1527 unsigned TCycle = 0;
1528 unsigned FCycle = 0;
1529 for (MachineInstr &
I : *IfConv.TBB) {
1530 unsigned NumCycles = SchedModel.computeInstrLatency(&
I,
false);
1532 TCycle += NumCycles - 1;
1533 TExtra +=
TII->getPredicationCost(
I);
1535 for (MachineInstr &
I : *IfConv.FBB) {
1536 unsigned NumCycles = SchedModel.computeInstrLatency(&
I,
false);
1538 FCycle += NumCycles - 1;
1539 FExtra +=
TII->getPredicationCost(
I);
1542 FCycle, FExtra, TrueProbability);
1547bool EarlyIfPredicator::tryConvertIf(MachineBasicBlock *
MBB) {
1549 while (IfConv.canConvertIf(
MBB,
true) && shouldConvertIf()) {
1551 SmallVector<MachineBasicBlock *, 4> RemoveBlocks;
1552 IfConv.convertIf(RemoveBlocks,
true);
1554 updateDomTree(DomTree, IfConv, RemoveBlocks);
1555 updateLoops(
Loops, RemoveBlocks);
1556 for (MachineBasicBlock *
MBB : RemoveBlocks)
1563 LLVM_DEBUG(
dbgs() <<
"********** EARLY IF-PREDICATOR **********\n"
1564 <<
"********** Function: " << MF.
getName() <<
'\n');
1572 SchedModel.
init(&STI);
1573 DomTree = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
1574 Loops = &getAnalysis<MachineLoopInfoWrapperPass>().getLI();
1575 MBPI = &getAnalysis<MachineBranchProbabilityInfoWrapperPass>().getMBPI();
1585 if (tryConvertIf(DomNode->getBlock()))
MachineInstrBuilder MachineInstrBuilder & DefMI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file implements the BitVector class.
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static unsigned InstrCount
This file defines the DenseMap class.
static bool hasSameValue(const MachineRegisterInfo &MRI, const TargetInstrInfo *TII, Register TReg, Register FReg)
static unsigned adjCycles(unsigned Cyc, int Delta)
static bool isConstantPoolLoad(const MachineInstr *MI)
static Register UseReg(const MachineOperand &MO)
const HexagonInstrInfo * TII
Register const TargetRegisterInfo * TRI
Promote Memory to Register
#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 builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
SmallVector< MachineOperand, 4 > Cond
MachineRegisterInfo & MRI
const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB
This file defines the SmallPtrSet class.
This file defines the SparseSet class derived from the version described in Briggs,...
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
bool test(unsigned Idx) const
Returns true if bit Idx is set.
BitVector & reset()
Reset all bits in the bitvector.
BitVector & set()
Set all bits in the bitvector.
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node's...
void eraseNode(NodeT *BB)
eraseNode - Removes a node from the dominator tree.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
LLVM_ABI PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const override
Remove the branching code at the end of the specific MBB.
bool isPredicated(const MachineInstr &MI) const override
Returns true if the instruction is already predicated.
bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify) const override
Analyze the branching code at the end of MBB, returning true if it cannot be understood (e....
bool reverseBranchCondition(SmallVectorImpl< MachineOperand > &Cond) const override
Reverses the branch condition of the specified condition list, returning false on success and true if...
unsigned insertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB, MachineBasicBlock *FBB, ArrayRef< MachineOperand > Cond, const DebugLoc &DL, int *BytesAdded=nullptr) const override
Insert branch code into the end of the specified MachineBasicBlock.
bool isProfitableToIfCvt(MachineBasicBlock &MBB, unsigned NumCycles, unsigned ExtraPredCycles, BranchProbability Probability) const override
Return true if it's profitable to predicate instructions with accumulated instruction latency of "Num...
bool PredicateInstruction(MachineInstr &MI, ArrayRef< MachineOperand > Cond) const override
Convert the instruction into a predicated instruction.
bool isPredicable(const MachineInstr &MI) const override
Return true if the specified instruction can be predicated.
unsigned pred_size() const
LLVM_ABI void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB)
Transfers all the successors, as in transferSuccessors, and update PHI operands in the successor bloc...
instr_iterator instr_begin()
succ_iterator succ_begin()
bool livein_empty() const
LLVM_ABI iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
unsigned succ_size() const
LLVM_ABI void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
LLVM_ABI void removeSuccessor(MachineBasicBlock *Succ, bool NormalizeSuccProbs=false)
Remove successor from the successors list of this MachineBasicBlock.
LLVM_ABI DebugLoc findDebugLoc(instr_iterator MBBI)
Find the next valid DebugLoc starting at MBBI, skipping any debug instructions.
LLVM_ABI bool isLayoutSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB will be emitted immediately after this block, such that if this bloc...
LLVM_ABI void eraseFromParent()
This method unlinks 'this' from the containing function and deletes it.
instr_iterator instr_end()
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
iterator_range< pred_iterator > predecessors()
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...
MachineInstrBundleIterator< MachineInstr > iterator
LLVM_ABI void moveAfter(MachineBasicBlock *NewBefore)
LLVM_ABI BranchProbability getEdgeProbability(const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const
Analysis pass which computes a MachineDominatorTree.
Analysis pass which computes a MachineDominatorTree.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
bool dominates(const MachineInstr *A, const MachineInstr *B) const
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Function & getFunction()
Return the LLVM function that this machine code represents.
const MachineBasicBlock & back() const
const MachineInstrBuilder & addReg(Register RegNo, RegState Flags={}, unsigned SubReg=0) const
Add a new virtual register operand.
Representation of each machine instruction.
bool isTerminator(QueryType Type=AnyInBundle) const
Returns true if this instruction part of the terminator for a basic block.
bool mayLoadOrStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read or modify memory.
const MachineBasicBlock * getParent() const
LLVM_ABI bool isDereferenceableInvariantLoad() const
Return true if this load instruction never traps and points to a memory location whose value doesn't ...
LLVM_ABI bool hasUnmodeledSideEffects() const
Return true if this instruction has side effects that are not modeled by mayLoad / mayStore,...
mop_range uses()
Returns all operands which may be register uses.
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
const MachineOperand & getOperand(unsigned i) const
LLVM_ABI int findRegisterDefOperandIdx(Register Reg, const TargetRegisterInfo *TRI, bool isDead=false, bool Overlap=false) const
Returns the operand index that is a def of the specified register or -1 if it is not found.
Analysis pass that exposes the MachineLoopInfo for a machine function.
A description of a memory reference used in the backend.
MachineOperand class - Representation of each machine instruction operand.
Register getReg() const
getReg - Returns the register number.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
LLVM_ABI LLVM_READONLY MachineInstr * getVRegDef(Register Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
LLVM_ABI Register createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
LLVM_ABI unsigned getResourceLength(ArrayRef< const MachineBasicBlock * > Extrablocks={}, ArrayRef< const MCSchedClassDesc * > ExtraInstrs={}, ArrayRef< const MCSchedClassDesc * > RemoveInstrs={}) const
Return the resource length of the trace.
InstrCycles getInstrCycles(const MachineInstr &MI) const
Return the depth and height of MI.
LLVM_ABI unsigned getInstrSlack(const MachineInstr &MI) const
Return the slack of MI.
unsigned getCriticalPath() const
Return the length of the (data dependency) critical path through the trace.
LLVM_ABI unsigned getPHIDepth(const MachineInstr &PHI) const
Return the Depth of a PHI instruction in a trace center block successor.
LLVM_ABI void verifyAnalysis() const
LLVM_ABI void invalidate(const MachineBasicBlock *MBB)
Invalidate cached information about MBB.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Wrapper class representing virtual and physical registers.
MCRegister asMCReg() const
Utility to check-convert this value to a MCRegister.
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
constexpr bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
void push_back(const T &Elt)
iterator erase(iterator I)
erase - Erases an existing element identified by a valid iterator.
void clear()
clear - Clears the set.
std::pair< iterator, bool > insert(const ValueT &Val)
insert - Attempts to insert a new element.
bool empty() const
empty - Returns true if the set is empty.
TargetInstrInfo - Interface to description of machine instruction set.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Provide an instruction scheduling machine model to CodeGen passes.
LLVM_ABI void init(const TargetSubtargetInfo *TSInfo, bool EnableSModel=true, bool EnableSItins=true)
Initialize the machine model for instruction scheduling.
virtual const TargetInstrInfo * getInstrInfo() const
virtual const TargetRegisterInfo * getRegisterInfo() const =0
Return the target's register information.
virtual bool enableEarlyIfConversion() const
Enable the use of the early if conversion pass.
self_iterator getIterator()
@ Tail
Attemps to make calls as fast as possible while guaranteeing that tail call optimization can always b...
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
DiagnosticInfoOptimizationBase::Argument NV
NodeAddr< NodeBase * > Node
This is an optimization pass for GlobalISel generic memory operations.
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
LLVM_ABI Printable printRegUnit(MCRegUnit Unit, const TargetRegisterInfo *TRI)
Create Printable object to print register units on a raw_ostream.
AnalysisManager< MachineFunction > MachineFunctionAnalysisManager
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
LLVM_ABI char & EarlyIfConverterLegacyID
EarlyIfConverter - This pass performs if-conversion on SSA form by inserting cmov instructions.
LLVM_ABI PreservedAnalyses getMachineFunctionPassPreservedAnalyses()
Returns the minimum set of Analyses that all machine function passes must preserve.
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...
auto post_order(const T &G)
Post-order traversal of a graph.
auto instructionsWithoutDebug(IterT It, IterT End, bool SkipPseudoOp=true)
Construct a range iterator which begins at It and moves forwards until End is reached,...
LLVM_ABI char & EarlyIfPredicatorID
EarlyIfPredicator - This pass performs if-conversion on SSA form by predicating if/else block and ins...
DomTreeNodeBase< MachineBasicBlock > MachineDomTreeNode
LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
ArrayRef(const T &OneElt) -> ArrayRef< T >
LLVM_ABI Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
LLVM_ABI Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
const CodeGenOptions & getCodeGenOptions(const LLVMContext &C)
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
unsigned Depth
Earliest issue cycle as determined by data dependencies and instruction latencies from the beginning ...
MachineInstr * ConditionDef