1//===-- EarlyIfConversion.cpp - If-conversion on SSA form machine code ----===//
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// Early if-conversion is for out-of-order CPUs that don't have a lot of
10// predicable instructions. The goal is to eliminate conditional branches that
11// may mispredict.
12//
13// Instructions from both sides of the branch are executed specutatively, and a
14// cmov instruction selects the result.
15//
16//===----------------------------------------------------------------------===//
17
18#include "llvm/CodeGen/EarlyIfConversion.h"
19#include "llvm/ADT/BitVector.h"
20#include "llvm/ADT/DenseMap.h"
21#include "llvm/ADT/DenseSet.h"
22#include "llvm/ADT/PostOrderIterator.h"
23#include "llvm/ADT/SmallPtrSet.h"
24#include "llvm/ADT/SparseSet.h"
25#include "llvm/ADT/Statistic.h"
26#include "llvm/Analysis/OptimizationRemarkEmitter.h"
27#include "llvm/CodeGen/MachineBasicBlock.h"
28#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
29#include "llvm/CodeGen/MachineDominators.h"
30#include "llvm/CodeGen/MachineFunction.h"
31#include "llvm/CodeGen/MachineFunctionPass.h"
32#include "llvm/CodeGen/MachineInstr.h"
33#include "llvm/CodeGen/MachineLoopInfo.h"
34#include "llvm/CodeGen/MachineMemOperand.h"
35#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
36#include "llvm/CodeGen/MachineRegisterInfo.h"
37#include "llvm/CodeGen/MachineTraceMetrics.h"
38#include "llvm/CodeGen/PseudoSourceValue.h"
39#include "llvm/CodeGen/Register.h"
40#include "llvm/CodeGen/RegisterClassInfo.h"
41#include "llvm/CodeGen/TargetInstrInfo.h"
42#include "llvm/CodeGen/TargetRegisterInfo.h"
43#include "llvm/CodeGen/TargetSubtargetInfo.h"
44#include "llvm/InitializePasses.h"
45#include "llvm/Support/CommandLine.h"
46#include "llvm/Support/Debug.h"
47#include "llvm/Support/raw_ostream.h"
48
49using namespace llvm;
50
51#define DEBUG_TYPE "early-ifcvt"
52
53// Absolute maximum number of instructions allowed per speculated block.
54// This bypasses all other heuristics, so it should be set fairly high.
55static cl::opt<unsigned>
56BlockInstrLimit("early-ifcvt-limit", cl::init(Val: 30), cl::Hidden,
57 cl::desc("Maximum number of instructions per speculated block."));
58
59// Stress testing mode - disable heuristics.
60static cl::opt<bool> Stress("stress-early-ifcvt", cl::Hidden,
61 cl::desc("Turn all knobs to 11"));
62
63// Enable analysis of data dependent branches (conditions derived from loads).
64static cl::opt<bool> EnableDataDependentBranchAnalysis(
65 "enable-early-ifcvt-data-dependent", cl::Hidden, cl::init(Val: false),
66 cl::desc("Enable hard-to-predict branch analysis for if-conversion"));
67
68// Limit the number steps we take when searching conditions that depend on
69// values recently loaded from memory.
70static cl::opt<unsigned>
71 MaxNumSteps("early-ifcvt-max-steps", cl::Hidden, cl::init(Val: 16),
72 cl::desc("Limit the number of steps taken when searching for a "
73 "recently loaded value"));
74
75// Limit the work done when looking for calls between a load and the condition
76// it feeds.
77static cl::opt<unsigned> MaxRegionInstrs(
78 "early-ifcvt-max-region-instrs", cl::Hidden, cl::init(Val: 64),
79 cl::desc("Limit the number of blocks and instructions examined when "
80 "searching for calls between a load and the condition it feeds"));
81
82static cl::opt<unsigned> ColdEdgeThreshold(
83 "early-ifcvt-cold-edge-threshold", cl::Hidden, cl::init(Val: 1),
84 cl::desc("Cold edge probability threshold in percent for using no "
85 "critical-path extension budget (0 disables the threshold)"));
86
87STATISTIC(NumDiamondsSeen, "Number of diamonds");
88STATISTIC(NumDiamondsConv, "Number of diamonds converted");
89STATISTIC(NumTrianglesSeen, "Number of triangles");
90STATISTIC(NumTrianglesConv, "Number of triangles converted");
91STATISTIC(NumDataDependant,
92 "Number of data dependent conditional branches encountered");
93STATISTIC(NumLikelyBiased, "Number of branches with a hot path encountered");
94STATISTIC(NumStronglyBiased,
95 "Number of branches with reduced critical-path budget");
96
97//===----------------------------------------------------------------------===//
98// SSAIfConv
99//===----------------------------------------------------------------------===//
100//
101// The SSAIfConv class performs if-conversion on SSA form machine code after
102// determining if it is possible. The class contains no heuristics; external
103// code should be used to determine when if-conversion is a good idea.
104//
105// SSAIfConv can convert both triangles and diamonds:
106//
107// Triangle: Head Diamond: Head
108// | \ / \_
109// | \ / |
110// | [TF]BB FBB TBB
111// | / \ /
112// | / \ /
113// Tail Tail
114//
115// Instructions in the conditional blocks TBB and/or FBB are spliced into the
116// Head block, and phis in the Tail block are converted to select instructions.
117//
118namespace {
119class SSAIfConv {
120 const TargetInstrInfo *TII;
121 const TargetRegisterInfo *TRI;
122 MachineRegisterInfo *MRI;
123
124public:
125 /// The block containing the conditional branch.
126 MachineBasicBlock *Head;
127
128 /// The block containing phis after the if-then-else.
129 MachineBasicBlock *Tail;
130
131 /// The 'true' conditional block as determined by analyzeBranch.
132 MachineBasicBlock *TBB;
133
134 /// The 'false' conditional block as determined by analyzeBranch.
135 MachineBasicBlock *FBB;
136
137 /// isTriangle - When there is no 'else' block, either TBB or FBB will be
138 /// equal to Tail.
139 bool isTriangle() const { return TBB == Tail || FBB == Tail; }
140
141 /// Returns the Tail predecessor for the True side.
142 MachineBasicBlock *getTPred() const { return TBB == Tail ? Head : TBB; }
143
144 /// Returns the Tail predecessor for the False side.
145 MachineBasicBlock *getFPred() const { return FBB == Tail ? Head : FBB; }
146
147 /// Information about each phi in the Tail block.
148 struct PHIInfo {
149 MachineInstr *PHI;
150 Register TReg, FReg;
151 /// Description of the select that will replace this phi.
152 TargetInstrInfo::SelectExpansion Select;
153
154 PHIInfo(MachineInstr *phi) : PHI(phi) {}
155 };
156
157 SmallVector<PHIInfo, 8> PHIs;
158
159 /// The branch condition determined by analyzeBranch.
160 SmallVector<MachineOperand, 4> Cond;
161
162private:
163 /// Instructions in Head that define values used by the conditional blocks.
164 /// The hoisted instructions must be inserted after these instructions.
165 SmallPtrSet<MachineInstr*, 8> InsertAfter;
166
167 /// Register units clobbered by the conditional blocks.
168 BitVector ClobberedRegUnits;
169
170 // Scratch pad for findInsertionPoint.
171 SparseSet<MCRegUnit, MCRegUnit, MCRegUnitToIndex> LiveRegUnits;
172
173 /// Insertion point in Head for speculatively executed instructions form TBB
174 /// and FBB.
175 MachineBasicBlock::iterator InsertionPoint;
176
177 /// Return true if all non-terminator instructions in MBB can be safely
178 /// speculated.
179 bool canSpeculateInstrs(MachineBasicBlock *MBB);
180
181 /// Return true if all non-terminator instructions in MBB can be safely
182 /// predicated.
183 bool canPredicateInstrs(MachineBasicBlock *MBB);
184
185 /// Scan through instruction dependencies and update InsertAfter array.
186 /// Return false if any dependency is incompatible with if conversion.
187 bool InstrDependenciesAllowIfConv(MachineInstr *I);
188
189 /// Predicate all instructions of the basic block with current condition
190 /// except for terminators. Reverse the condition if ReversePredicate is set.
191 void PredicateBlock(MachineBasicBlock *MBB, bool ReversePredicate);
192
193 /// Find a valid insertion point in Head.
194 bool findInsertionPoint();
195
196 /// Replace PHI instructions in Tail with selects.
197 void replacePHIInstrs();
198
199 /// Insert selects and rewrite PHI operands to use them.
200 void rewritePHIOperands();
201
202 /// If virtual register has "killed" flag in TBB and FBB basic blocks, remove
203 /// the flag in TBB instruction.
204 void clearRepeatedKillFlagsFromTBB(MachineBasicBlock *TBB,
205 MachineBasicBlock *FBB);
206
207public:
208 /// init - Initialize per-function data structures.
209 void init(MachineFunction &MF) {
210 TII = MF.getSubtarget().getInstrInfo();
211 TRI = MF.getSubtarget().getRegisterInfo();
212 MRI = &MF.getRegInfo();
213 LiveRegUnits.clear();
214 LiveRegUnits.setUniverse(TRI->getNumRegUnits());
215 ClobberedRegUnits.clear();
216 ClobberedRegUnits.resize(N: TRI->getNumRegUnits());
217 }
218
219 /// canConvertIf - If the sub-CFG headed by MBB can be if-converted,
220 /// initialize the internal state, and return true.
221 /// If predicate is set try to predicate the block otherwise try to
222 /// speculatively execute it.
223 bool canConvertIf(MachineBasicBlock *MBB, bool Predicate = false);
224
225 /// convertIf - If-convert the last block passed to canConvertIf(), assuming
226 /// it is possible. Add any blocks that are to be erased to RemoveBlocks.
227 void convertIf(SmallVectorImpl<MachineBasicBlock *> &RemoveBlocks,
228 bool Predicate = false);
229};
230} // end anonymous namespace
231
232/// canSpeculateInstrs - Returns true if all the instructions in MBB can safely
233/// be speculated. The terminators are not considered.
234///
235/// If instructions use any values that are defined in the head basic block,
236/// the defining instructions are added to InsertAfter.
237///
238/// Any clobbered regunits are added to ClobberedRegUnits.
239///
240bool SSAIfConv::canSpeculateInstrs(MachineBasicBlock *MBB) {
241 // Reject any live-in physregs. It's probably CPSR/EFLAGS, and very hard to
242 // get right.
243 if (!MBB->livein_empty()) {
244 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has live-ins.\n");
245 return false;
246 }
247
248 unsigned InstrCount = 0;
249
250 // Check all instructions, except the terminators. It is assumed that
251 // terminators never have side effects or define any used register values.
252 for (MachineInstr &MI :
253 llvm::make_range(x: MBB->begin(), y: MBB->getFirstTerminator())) {
254 if (MI.isDebugInstr())
255 continue;
256
257 if (++InstrCount > BlockInstrLimit && !Stress) {
258 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has more than "
259 << BlockInstrLimit << " instructions.\n");
260 return false;
261 }
262
263 // There shouldn't normally be any phis in a single-predecessor block.
264 if (MI.isPHI()) {
265 LLVM_DEBUG(dbgs() << "Can't hoist: " << MI);
266 return false;
267 }
268
269 // Don't speculate loads. Note that it may be possible and desirable to
270 // speculate GOT or constant pool loads that are guaranteed not to trap,
271 // but we don't support that for now.
272 if (MI.mayLoad()) {
273 LLVM_DEBUG(dbgs() << "Won't speculate load: " << MI);
274 return false;
275 }
276
277 // We never speculate stores, so an AA pointer isn't necessary.
278 bool DontMoveAcrossStore = true;
279 if (!MI.isSafeToMove(SawStore&: DontMoveAcrossStore)) {
280 LLVM_DEBUG(dbgs() << "Can't speculate: " << MI);
281 return false;
282 }
283
284 // Check for any dependencies on Head instructions.
285 if (!InstrDependenciesAllowIfConv(I: &MI))
286 return false;
287 }
288 return true;
289}
290
291/// Check that there is no dependencies preventing if conversion.
292///
293/// If instruction uses any values that are defined in the head basic block,
294/// the defining instructions are added to InsertAfter.
295bool SSAIfConv::InstrDependenciesAllowIfConv(MachineInstr *I) {
296 for (const MachineOperand &MO : I->operands()) {
297 if (MO.isRegMask()) {
298 LLVM_DEBUG(dbgs() << "Won't speculate regmask: " << *I);
299 return false;
300 }
301 if (!MO.isReg())
302 continue;
303 Register Reg = MO.getReg();
304
305 // Remember clobbered regunits.
306 if (MO.isDef() && Reg.isPhysical())
307 for (MCRegUnit Unit : TRI->regunits(Reg: Reg.asMCReg()))
308 ClobberedRegUnits.set(static_cast<unsigned>(Unit));
309
310 if (!MO.readsReg() || !Reg.isVirtual())
311 continue;
312 MachineInstr *DefMI = MRI->getVRegDef(Reg);
313 if (!DefMI || DefMI->getParent() != Head)
314 continue;
315 if (InsertAfter.insert(Ptr: DefMI).second)
316 LLVM_DEBUG(dbgs() << printMBBReference(*I->getParent()) << " depends on "
317 << *DefMI);
318 if (DefMI->isTerminator()) {
319 LLVM_DEBUG(dbgs() << "Can't insert instructions below terminator.\n");
320 return false;
321 }
322 }
323 return true;
324}
325
326/// canPredicateInstrs - Returns true if all the instructions in MBB can safely
327/// be predicates. The terminators are not considered.
328///
329/// If instructions use any values that are defined in the head basic block,
330/// the defining instructions are added to InsertAfter.
331///
332/// Any clobbered regunits are added to ClobberedRegUnits.
333///
334bool SSAIfConv::canPredicateInstrs(MachineBasicBlock *MBB) {
335 // Reject any live-in physregs. It's probably CPSR/EFLAGS, and very hard to
336 // get right.
337 if (!MBB->livein_empty()) {
338 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has live-ins.\n");
339 return false;
340 }
341
342 unsigned InstrCount = 0;
343
344 // Check all instructions, except the terminators. It is assumed that
345 // terminators never have side effects or define any used register values.
346 for (MachineBasicBlock::iterator I = MBB->begin(),
347 E = MBB->getFirstTerminator();
348 I != E; ++I) {
349 if (I->isDebugInstr())
350 continue;
351
352 if (++InstrCount > BlockInstrLimit && !Stress) {
353 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has more than "
354 << BlockInstrLimit << " instructions.\n");
355 return false;
356 }
357
358 // There shouldn't normally be any phis in a single-predecessor block.
359 if (I->isPHI()) {
360 LLVM_DEBUG(dbgs() << "Can't predicate: " << *I);
361 return false;
362 }
363
364 // Check that instruction is predicable
365 if (!TII->isPredicable(MI: *I)) {
366 LLVM_DEBUG(dbgs() << "Isn't predicable: " << *I);
367 return false;
368 }
369
370 // Check that instruction is not already predicated.
371 if (TII->isPredicated(MI: *I) && !TII->canPredicatePredicatedInstr(MI: *I)) {
372 LLVM_DEBUG(dbgs() << "Is already predicated: " << *I);
373 return false;
374 }
375
376 // Check for any dependencies on Head instructions.
377 if (!InstrDependenciesAllowIfConv(I: &(*I)))
378 return false;
379 }
380 return true;
381}
382
383// Apply predicate to all instructions in the machine block.
384void SSAIfConv::PredicateBlock(MachineBasicBlock *MBB, bool ReversePredicate) {
385 auto Condition = Cond;
386 if (ReversePredicate) {
387 bool CanRevCond = !TII->reverseBranchCondition(Cond&: Condition);
388 assert(CanRevCond && "Reversed predicate is not supported");
389 (void)CanRevCond;
390 }
391 // Terminators don't need to be predicated as they will be removed.
392 for (MachineBasicBlock::iterator I = MBB->begin(),
393 E = MBB->getFirstTerminator();
394 I != E; ++I) {
395 if (I->isDebugInstr())
396 continue;
397 TII->PredicateInstruction(MI&: *I, Pred: Condition);
398 }
399}
400
401/// Find an insertion point in Head for the speculated instructions. The
402/// insertion point must be:
403///
404/// 1. Before any terminators.
405/// 2. After any instructions in InsertAfter.
406/// 3. Not have any clobbered regunits live.
407///
408/// This function sets InsertionPoint and returns true when successful, it
409/// returns false if no valid insertion point could be found.
410///
411bool SSAIfConv::findInsertionPoint() {
412 // Keep track of live regunits before the current position.
413 // Only track RegUnits that are also in ClobberedRegUnits.
414 LiveRegUnits.clear();
415 SmallVector<MCRegister, 8> Reads;
416 MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator();
417 MachineBasicBlock::iterator I = Head->end();
418 MachineBasicBlock::iterator B = Head->begin();
419 while (I != B) {
420 --I;
421 // Some of the conditional code depends in I.
422 if (InsertAfter.count(Ptr: &*I)) {
423 LLVM_DEBUG(dbgs() << "Can't insert code after " << *I);
424 return false;
425 }
426
427 // Update live regunits.
428 for (const MachineOperand &MO : I->operands()) {
429 // We're ignoring regmask operands. That is conservatively correct.
430 if (!MO.isReg())
431 continue;
432 Register Reg = MO.getReg();
433 if (!Reg.isPhysical())
434 continue;
435 // I clobbers Reg, so it isn't live before I.
436 if (MO.isDef())
437 for (MCRegUnit Unit : TRI->regunits(Reg: Reg.asMCReg()))
438 LiveRegUnits.erase(Key: Unit);
439 // Unless I reads Reg.
440 if (MO.readsReg())
441 Reads.push_back(Elt: Reg.asMCReg());
442 }
443 // Anything read by I is live before I.
444 while (!Reads.empty())
445 for (MCRegUnit Unit : TRI->regunits(Reg: Reads.pop_back_val()))
446 if (ClobberedRegUnits.test(Idx: static_cast<unsigned>(Unit)))
447 LiveRegUnits.insert(Val: Unit);
448
449 // We can't insert before a terminator.
450 if (I != FirstTerm && I->isTerminator())
451 continue;
452
453 // Some of the clobbered registers are live before I, not a valid insertion
454 // point.
455 if (!LiveRegUnits.empty()) {
456 LLVM_DEBUG({
457 dbgs() << "Would clobber";
458 for (MCRegUnit LRU : LiveRegUnits)
459 dbgs() << ' ' << printRegUnit(LRU, TRI);
460 dbgs() << " live before " << *I;
461 });
462 continue;
463 }
464
465 // This is a valid insertion point.
466 InsertionPoint = I;
467 LLVM_DEBUG(dbgs() << "Can insert before " << *I);
468 return true;
469 }
470 LLVM_DEBUG(dbgs() << "No legal insertion point found.\n");
471 return false;
472}
473
474
475
476/// canConvertIf - analyze the sub-cfg rooted in MBB, and return true if it is
477/// a potential candidate for if-conversion. Fill out the internal state.
478///
479bool SSAIfConv::canConvertIf(MachineBasicBlock *MBB, bool Predicate) {
480 Head = MBB;
481 TBB = FBB = Tail = nullptr;
482
483 if (Head->succ_size() != 2)
484 return false;
485 MachineBasicBlock *Succ0 = Head->succ_begin()[0];
486 MachineBasicBlock *Succ1 = Head->succ_begin()[1];
487
488 // Canonicalize so Succ0 has MBB as its single predecessor.
489 if (Succ0->pred_size() != 1)
490 std::swap(a&: Succ0, b&: Succ1);
491
492 if (Succ0->pred_size() != 1 || Succ0->succ_size() != 1)
493 return false;
494
495 Tail = Succ0->succ_begin()[0];
496
497 // This is not a triangle.
498 if (Tail != Succ1) {
499 // Check for a diamond. We won't deal with any critical edges.
500 if (Succ1->pred_size() != 1 || Succ1->succ_size() != 1 ||
501 Succ1->succ_begin()[0] != Tail)
502 return false;
503 LLVM_DEBUG(dbgs() << "\nDiamond: " << printMBBReference(*Head) << " -> "
504 << printMBBReference(*Succ0) << "/"
505 << printMBBReference(*Succ1) << " -> "
506 << printMBBReference(*Tail) << '\n');
507
508 // Live-in physregs are tricky to get right when speculating code.
509 if (!Tail->livein_empty()) {
510 LLVM_DEBUG(dbgs() << "Tail has live-ins.\n");
511 return false;
512 }
513 } else {
514 LLVM_DEBUG(dbgs() << "\nTriangle: " << printMBBReference(*Head) << " -> "
515 << printMBBReference(*Succ0) << " -> "
516 << printMBBReference(*Tail) << '\n');
517 }
518
519 // This is a triangle or a diamond.
520 // Skip if we cannot predicate and there are no phis skip as there must be
521 // side effects that can only be handled with predication.
522 if (!Predicate && (Tail->empty() || !Tail->front().isPHI())) {
523 LLVM_DEBUG(dbgs() << "No phis in tail.\n");
524 return false;
525 }
526
527 // The branch we're looking to eliminate must be analyzable.
528 Cond.clear();
529 if (TII->analyzeBranch(MBB&: *Head, TBB, FBB, Cond)) {
530 LLVM_DEBUG(dbgs() << "Branch not analyzable.\n");
531 return false;
532 }
533
534 // This is weird, probably some sort of degenerate CFG.
535 if (!TBB) {
536 LLVM_DEBUG(dbgs() << "analyzeBranch didn't find conditional branch.\n");
537 return false;
538 }
539
540 // Make sure the analyzed branch is conditional; one of the successors
541 // could be a landing pad. (Empty landing pads can be generated on Windows.)
542 if (Cond.empty()) {
543 LLVM_DEBUG(dbgs() << "analyzeBranch found an unconditional branch.\n");
544 return false;
545 }
546
547 // analyzeBranch doesn't set FBB on a fall-through branch.
548 // Make sure it is always set.
549 FBB = TBB == Succ0 ? Succ1 : Succ0;
550
551 // Any phis in the tail block must be convertible to selects.
552 PHIs.clear();
553 MachineBasicBlock *TPred = getTPred();
554 MachineBasicBlock *FPred = getFPred();
555 for (MachineBasicBlock::iterator I = Tail->begin(), E = Tail->end();
556 I != E && I->isPHI(); ++I) {
557 PHIs.push_back(Elt: &*I);
558 PHIInfo &PI = PHIs.back();
559 // Find PHI operands corresponding to TPred and FPred.
560 for (unsigned i = 1; i != PI.PHI->getNumOperands(); i += 2) {
561 if (PI.PHI->getOperand(i: i+1).getMBB() == TPred)
562 PI.TReg = PI.PHI->getOperand(i).getReg();
563 if (PI.PHI->getOperand(i: i+1).getMBB() == FPred)
564 PI.FReg = PI.PHI->getOperand(i).getReg();
565 }
566 assert(PI.TReg.isVirtual() && "Bad PHI");
567 assert(PI.FReg.isVirtual() && "Bad PHI");
568
569 // Get target information.
570 if (!TII->canInsertSelect(MBB: *Head, Cond, DstReg: PI.PHI->getOperand(i: 0).getReg(),
571 TrueReg: PI.TReg, FalseReg: PI.FReg, Exp&: PI.Select)) {
572 LLVM_DEBUG(dbgs() << "Can't convert: " << *PI.PHI);
573 return false;
574 }
575 }
576
577 // Check that the conditional instructions can be speculated.
578 InsertAfter.clear();
579 ClobberedRegUnits.reset();
580 if (Predicate) {
581 if (TBB != Tail && !canPredicateInstrs(MBB: TBB))
582 return false;
583 if (FBB != Tail && !canPredicateInstrs(MBB: FBB))
584 return false;
585 } else {
586 if (TBB != Tail && !canSpeculateInstrs(MBB: TBB))
587 return false;
588 if (FBB != Tail && !canSpeculateInstrs(MBB: FBB))
589 return false;
590 }
591
592 // Try to find a valid insertion point for the speculated instructions in the
593 // head basic block.
594 if (!findInsertionPoint())
595 return false;
596
597 if (isTriangle())
598 ++NumTrianglesSeen;
599 else
600 ++NumDiamondsSeen;
601 return true;
602}
603
604/// \return true iff the two registers are known to have the same value.
605static bool hasSameValue(const MachineRegisterInfo &MRI,
606 const TargetInstrInfo *TII, Register TReg,
607 Register FReg) {
608 if (TReg == FReg)
609 return true;
610
611 if (!TReg.isVirtual() || !FReg.isVirtual())
612 return false;
613
614 const MachineInstr *TDef = MRI.getUniqueVRegDef(Reg: TReg);
615 const MachineInstr *FDef = MRI.getUniqueVRegDef(Reg: FReg);
616 if (!TDef || !FDef)
617 return false;
618
619 // If there are side-effects, all bets are off.
620 if (TDef->hasUnmodeledSideEffects())
621 return false;
622
623 // If the instruction could modify memory, or there may be some intervening
624 // store between the two, we can't consider them to be equal.
625 if (TDef->mayLoadOrStore() && !TDef->isDereferenceableInvariantLoad())
626 return false;
627
628 // We also can't guarantee that they are the same if, for example, the
629 // instructions are both a copy from a physical reg, because some other
630 // instruction may have modified the value in that reg between the two
631 // defining insts.
632 if (any_of(Range: TDef->uses(), P: [](const MachineOperand &MO) {
633 return MO.isReg() && MO.getReg().isPhysical();
634 }))
635 return false;
636
637 // Check whether the two defining instructions produce the same value(s).
638 if (!TII->produceSameValue(MI0: *TDef, MI1: *FDef, MRI: &MRI))
639 return false;
640
641 // Further, check that the two defs come from corresponding operands.
642 int TIdx = TDef->findRegisterDefOperandIdx(Reg: TReg, /*TRI=*/nullptr);
643 int FIdx = FDef->findRegisterDefOperandIdx(Reg: FReg, /*TRI=*/nullptr);
644 if (TIdx == -1 || FIdx == -1)
645 return false;
646
647 return TIdx == FIdx;
648}
649
650/// replacePHIInstrs - Completely replace PHI instructions with selects.
651/// This is possible when the only Tail predecessors are the if-converted
652/// blocks.
653void SSAIfConv::replacePHIInstrs() {
654 assert(Tail->pred_size() == 2 && "Cannot replace PHIs");
655 MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator();
656 assert(FirstTerm != Head->end() && "No terminators");
657 DebugLoc HeadDL = FirstTerm->getDebugLoc();
658
659 // Convert all PHIs to select instructions inserted before FirstTerm.
660 for (PHIInfo &PI : PHIs) {
661 LLVM_DEBUG(dbgs() << "If-converting " << *PI.PHI);
662 Register DstReg = PI.PHI->getOperand(i: 0).getReg();
663 if (hasSameValue(MRI: *MRI, TII, TReg: PI.TReg, FReg: PI.FReg)) {
664 // We do not need the select instruction if both incoming values are
665 // equal, but we do need a COPY.
666 BuildMI(BB&: *Head, I: FirstTerm, MIMD: HeadDL, MCID: TII->get(Opcode: TargetOpcode::COPY), DestReg: DstReg)
667 .addReg(RegNo: PI.TReg);
668 } else {
669 TII->insertSelect(MBB&: *Head, I: FirstTerm, DL: HeadDL, DstReg, Cond, TrueReg: PI.TReg,
670 FalseReg: PI.FReg);
671 }
672 LLVM_DEBUG(dbgs() << " --> " << *std::prev(FirstTerm));
673 PI.PHI->eraseFromParent();
674 PI.PHI = nullptr;
675 }
676}
677
678/// rewritePHIOperands - When there are additional Tail predecessors, insert
679/// select instructions in Head and rewrite PHI operands to use the selects.
680/// Keep the PHI instructions in Tail to handle the other predecessors.
681void SSAIfConv::rewritePHIOperands() {
682 MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator();
683 assert(FirstTerm != Head->end() && "No terminators");
684 DebugLoc HeadDL = FirstTerm->getDebugLoc();
685
686 // Convert all PHIs to select instructions inserted before FirstTerm.
687 for (PHIInfo &PI : PHIs) {
688 Register DstReg;
689
690 LLVM_DEBUG(dbgs() << "If-converting " << *PI.PHI);
691 if (hasSameValue(MRI: *MRI, TII, TReg: PI.TReg, FReg: PI.FReg)) {
692 // We do not need the select instruction if both incoming values are
693 // equal.
694 DstReg = PI.TReg;
695 } else {
696 Register PHIDst = PI.PHI->getOperand(i: 0).getReg();
697 DstReg = MRI->createVirtualRegister(RegClass: MRI->getRegClass(Reg: PHIDst));
698 TII->insertSelect(MBB&: *Head, I: FirstTerm, DL: HeadDL,
699 DstReg, Cond, TrueReg: PI.TReg, FalseReg: PI.FReg);
700 LLVM_DEBUG(dbgs() << " --> " << *std::prev(FirstTerm));
701 }
702
703 // Rewrite PHI operands TPred -> (DstReg, Head), remove FPred.
704 for (unsigned i = PI.PHI->getNumOperands(); i != 1; i -= 2) {
705 MachineBasicBlock *MBB = PI.PHI->getOperand(i: i-1).getMBB();
706 if (MBB == getTPred()) {
707 PI.PHI->getOperand(i: i-1).setMBB(Head);
708 PI.PHI->getOperand(i: i-2).setReg(DstReg);
709 } else if (MBB == getFPred()) {
710 PI.PHI->removeOperand(OpNo: i-1);
711 PI.PHI->removeOperand(OpNo: i-2);
712 }
713 }
714 LLVM_DEBUG(dbgs() << " --> " << *PI.PHI);
715 }
716}
717
718void SSAIfConv::clearRepeatedKillFlagsFromTBB(MachineBasicBlock *TBB,
719 MachineBasicBlock *FBB) {
720 assert(TBB != FBB);
721
722 // Collect virtual registers killed in FBB.
723 SmallDenseSet<Register> FBBKilledRegs;
724 for (MachineInstr &MI : FBB->instrs()) {
725 for (MachineOperand &MO : MI.operands()) {
726 if (MO.isReg() && MO.isKill() && MO.getReg().isVirtual())
727 FBBKilledRegs.insert(V: MO.getReg());
728 }
729 }
730
731 if (FBBKilledRegs.empty())
732 return;
733
734 // Find the same killed registers in TBB and clear kill flags for them.
735 for (MachineInstr &MI : TBB->instrs()) {
736 for (MachineOperand &MO : MI.operands()) {
737 if (MO.isReg() && MO.isKill() && FBBKilledRegs.contains(V: MO.getReg()))
738 MO.setIsKill(false);
739 }
740 }
741}
742
743/// convertIf - Execute the if conversion after canConvertIf has determined the
744/// feasibility.
745///
746/// Any basic blocks that need to be erased will be added to RemoveBlocks.
747///
748void SSAIfConv::convertIf(SmallVectorImpl<MachineBasicBlock *> &RemoveBlocks,
749 bool Predicate) {
750 assert(Head && Tail && TBB && FBB && "Call canConvertIf first.");
751
752 // Update statistics.
753 if (isTriangle())
754 ++NumTrianglesConv;
755 else
756 ++NumDiamondsConv;
757
758 // If both blocks are going to be merged into Head, remove "killed" flag in
759 // TBB for registers, which are killed in TBB and FBB. Otherwise, register
760 // will be killed twice in Head after splice. Register killed twice is an
761 // incorrect MIR.
762 if (TBB != Tail && FBB != Tail)
763 clearRepeatedKillFlagsFromTBB(TBB, FBB);
764
765 // Move all instructions into Head, except for the terminators.
766 if (TBB != Tail) {
767 if (Predicate)
768 PredicateBlock(MBB: TBB, /*ReversePredicate=*/false);
769 Head->splice(Where: InsertionPoint, Other: TBB, From: TBB->begin(), To: TBB->getFirstTerminator());
770 }
771 if (FBB != Tail) {
772 if (Predicate)
773 PredicateBlock(MBB: FBB, /*ReversePredicate=*/true);
774 Head->splice(Where: InsertionPoint, Other: FBB, From: FBB->begin(), To: FBB->getFirstTerminator());
775 }
776 // Are there extra Tail predecessors?
777 bool ExtraPreds = Tail->pred_size() != 2;
778 if (ExtraPreds)
779 rewritePHIOperands();
780 else
781 replacePHIInstrs();
782
783 // Fix up the CFG, temporarily leave Head without any successors.
784 Head->removeSuccessor(Succ: TBB);
785 Head->removeSuccessor(Succ: FBB, NormalizeSuccProbs: true);
786 if (TBB != Tail)
787 TBB->removeSuccessor(Succ: Tail, NormalizeSuccProbs: true);
788 if (FBB != Tail)
789 FBB->removeSuccessor(Succ: Tail, NormalizeSuccProbs: true);
790
791 // Fix up Head's terminators.
792 // It should become a single branch or a fallthrough.
793 DebugLoc HeadDL = Head->getFirstTerminator()->getDebugLoc();
794 TII->removeBranch(MBB&: *Head);
795
796 // Mark the now empty conditional blocks for removal and move them to the end.
797 // It is likely that Head can fall
798 // through to Tail, and we can join the two blocks.
799 if (TBB != Tail) {
800 RemoveBlocks.push_back(Elt: TBB);
801 if (TBB != &TBB->getParent()->back())
802 TBB->moveAfter(NewBefore: &TBB->getParent()->back());
803 }
804 if (FBB != Tail) {
805 RemoveBlocks.push_back(Elt: FBB);
806 if (FBB != &FBB->getParent()->back())
807 FBB->moveAfter(NewBefore: &FBB->getParent()->back());
808 }
809
810 assert(Head->succ_empty() && "Additional head successors?");
811 if (!ExtraPreds && Head->isLayoutSuccessor(MBB: Tail)) {
812 // Splice Tail onto the end of Head.
813 LLVM_DEBUG(dbgs() << "Joining tail " << printMBBReference(*Tail)
814 << " into head " << printMBBReference(*Head) << '\n');
815 Head->splice(Where: Head->end(), Other: Tail,
816 From: Tail->begin(), To: Tail->end());
817 Head->transferSuccessorsAndUpdatePHIs(FromMBB: Tail);
818 RemoveBlocks.push_back(Elt: Tail);
819 if (Tail != &Tail->getParent()->back())
820 Tail->moveAfter(NewBefore: &Tail->getParent()->back());
821 } else {
822 // We need a branch to Tail, let code placement work it out later.
823 LLVM_DEBUG(dbgs() << "Converting to unconditional branch.\n");
824 SmallVector<MachineOperand, 0> EmptyCond;
825 TII->insertBranch(MBB&: *Head, TBB: Tail, FBB: nullptr, Cond: EmptyCond, DL: HeadDL);
826 Head->addSuccessor(Succ: Tail);
827 }
828 LLVM_DEBUG(dbgs() << *Head);
829}
830
831//===----------------------------------------------------------------------===//
832// EarlyIfConverter Pass
833//===----------------------------------------------------------------------===//
834
835namespace {
836class EarlyIfConverter {
837 const TargetInstrInfo *TII = nullptr;
838 const TargetRegisterInfo *TRI = nullptr;
839 const TargetSubtargetInfo *STI = nullptr;
840 MachineRegisterInfo *MRI = nullptr;
841 MachineDominatorTree *DomTree = nullptr;
842 MachineLoopInfo *Loops = nullptr;
843 MachineTraceMetrics *Traces = nullptr;
844 MachineTraceMetrics::Ensemble *MinInstr = nullptr;
845 MachineBranchProbabilityInfo &MBPI;
846 SSAIfConv IfConv;
847
848 /// Cache of basic blocks verified to contain no call instructions, mapping
849 /// each block to the number of instructions scanned in it.
850 DenseMap<const MachineBasicBlock *, unsigned> NoCallBlocksCache;
851
852public:
853 EarlyIfConverter(MachineDominatorTree &DT, MachineLoopInfo &LI,
854 MachineTraceMetrics &MTM, MachineBranchProbabilityInfo &MBPI)
855 : DomTree(&DT), Loops(&LI), Traces(&MTM), MBPI(MBPI) {}
856 EarlyIfConverter() = delete;
857
858 bool run(MachineFunction &MF);
859
860private:
861 bool tryConvertIf(MachineBasicBlock *);
862 void invalidateTraces();
863 bool shouldConvertIf();
864 bool isConditionDataDependent();
865 bool doOperandsComeFromMemory(const MachineInstr *ConditionDef);
866 bool hasCallOrLoopInRange(const MachineInstr *From, const MachineInstr *To);
867};
868
869class EarlyIfConverterLegacy : public MachineFunctionPass {
870public:
871 static char ID;
872 EarlyIfConverterLegacy() : MachineFunctionPass(ID) {}
873 void getAnalysisUsage(AnalysisUsage &AU) const override;
874 bool runOnMachineFunction(MachineFunction &MF) override;
875 StringRef getPassName() const override { return "Early If-Conversion"; }
876};
877} // end anonymous namespace
878
879char EarlyIfConverterLegacy::ID = 0;
880char &llvm::EarlyIfConverterLegacyID = EarlyIfConverterLegacy::ID;
881
882INITIALIZE_PASS_BEGIN(EarlyIfConverterLegacy, DEBUG_TYPE, "Early If Converter",
883 false, false)
884INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfoWrapperPass)
885INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
886INITIALIZE_PASS_DEPENDENCY(MachineTraceMetricsWrapperPass)
887INITIALIZE_PASS_END(EarlyIfConverterLegacy, DEBUG_TYPE, "Early If Converter",
888 false, false)
889
890void EarlyIfConverterLegacy::getAnalysisUsage(AnalysisUsage &AU) const {
891 AU.addPreserved<MachineRegisterClassInfoWrapperPass>();
892 AU.addRequired<MachineBranchProbabilityInfoWrapperPass>();
893 AU.addRequired<MachineDominatorTreeWrapperPass>();
894 AU.addPreserved<MachineDominatorTreeWrapperPass>();
895 AU.addRequired<MachineLoopInfoWrapperPass>();
896 AU.addPreserved<MachineLoopInfoWrapperPass>();
897 AU.addRequired<MachineTraceMetricsWrapperPass>();
898 AU.addPreserved<MachineTraceMetricsWrapperPass>();
899 MachineFunctionPass::getAnalysisUsage(AU);
900}
901
902namespace {
903/// Update the dominator tree after if-conversion erased some blocks.
904void updateDomTree(MachineDominatorTree *DomTree, const SSAIfConv &IfConv,
905 ArrayRef<MachineBasicBlock *> Removed) {
906 // convertIf can remove TBB, FBB, and Tail can be merged into Head.
907 // TBB and FBB should not dominate any blocks.
908 // Tail children should be transferred to Head.
909 MachineDomTreeNode *HeadNode = DomTree->getNode(BB: IfConv.Head);
910 for (auto *B : Removed) {
911 MachineDomTreeNode *Node = DomTree->getNode(BB: B);
912 assert(Node != HeadNode && "Cannot erase the head node");
913 while (!Node->isLeaf()) {
914 assert(Node->getBlock() == IfConv.Tail && "Unexpected children");
915 DomTree->changeImmediateDominator(N: *Node->begin(), NewIDom: HeadNode);
916 }
917 DomTree->eraseNode(BB: B);
918 }
919}
920
921/// Update LoopInfo after if-conversion.
922void updateLoops(MachineLoopInfo *Loops,
923 ArrayRef<MachineBasicBlock *> Removed) {
924 // If-conversion doesn't change loop structure, and it doesn't mess with back
925 // edges, so updating LoopInfo is simply removing the dead blocks.
926 for (auto *B : Removed)
927 Loops->removeBlock(BB: B);
928}
929} // namespace
930
931/// Invalidate MachineTraceMetrics before if-conversion.
932void EarlyIfConverter::invalidateTraces() {
933 Traces->verifyAnalysis();
934 Traces->invalidate(MBB: IfConv.Head);
935 Traces->invalidate(MBB: IfConv.Tail);
936 Traces->invalidate(MBB: IfConv.TBB);
937 Traces->invalidate(MBB: IfConv.FBB);
938 Traces->verifyAnalysis();
939}
940
941static bool isConstantPoolLoad(const MachineInstr *MI) {
942 return MI->mayLoad() && any_of(Range: MI->memoperands(), P: [](MachineMemOperand *MOp) {
943 const PseudoSourceValue *PSV = MOp->getPseudoValue();
944 return PSV && PSV->isConstantPool();
945 });
946}
947
948/// Check whether the load in From and the condition in To are far apart, i.e.
949/// whether a call or a loop can be executed between them. This is done by first
950/// scanning the instructions within From and To MBBs. If no call is found, we
951/// then scan all blocks which are dominated by From (the load) and can reach To
952/// (the condition), looking for calls and for blocks belonging to a loop the
953/// condition is not part of.
954bool EarlyIfConverter::hasCallOrLoopInRange(const MachineInstr *From,
955 const MachineInstr *To) {
956 if (From == To)
957 return false;
958
959 LLVM_DEBUG(dbgs() << " checking for a call or loop between " << *From
960 << " and " << *To);
961 assert(DomTree->dominates(From, To) && "From is expected to dominate To");
962
963 const MachineBasicBlock *FromBB = From->getParent();
964 const MachineBasicBlock *ToBB = To->getParent();
965
966 unsigned NumScanned = 0;
967 auto HitSearchLimit = [&](unsigned N) {
968 NumScanned += N;
969 if (NumScanned <= MaxRegionInstrs)
970 return false;
971 LLVM_DEBUG(dbgs() << " hasCallOrLoopInRange scanned more than "
972 << MaxRegionInstrs << " instructions\n");
973 return true;
974 };
975 auto FoundCall = [](const MachineInstr &MI) {
976 LLVM_DEBUG(dbgs() << " found a call before the condition: " << MI);
977 return true;
978 };
979 auto IsCallOrHitSearchLimit = [&](const MachineInstr &MI) {
980 if (HitSearchLimit(1))
981 return true;
982 if (!MI.isCall())
983 return false;
984 return FoundCall(MI);
985 };
986
987 // If From and To are in the same block, just check (From, To).
988 if (FromBB == ToBB) {
989 for (const MachineInstr &MI : instructionsWithoutDebug(
990 It: std::next(x: From->getIterator()), End: To->getIterator(),
991 /*SkipPseudoOp=*/false))
992 if (IsCallOrHitSearchLimit(MI))
993 return true;
994 return false;
995 }
996
997 // Check (From, end of From's block] and [start of To's block, To).
998 for (const MachineInstr &MI : instructionsWithoutDebug(
999 It: std::next(x: From->getIterator()), End: FromBB->instr_end(),
1000 /*SkipPseudoOp=*/false))
1001 if (IsCallOrHitSearchLimit(MI))
1002 return true;
1003 for (const MachineInstr &MI :
1004 instructionsWithoutDebug(It: ToBB->instr_begin(), End: To->getIterator(),
1005 /*SkipPseudoOp=*/false))
1006 if (IsCallOrHitSearchLimit(MI))
1007 return true;
1008
1009 // Enqueued guards the traversal: the endpoint blocks are traversed through
1010 // but their instructions were already handled above.
1011 SmallPtrSet<const MachineBasicBlock *, 16> Enqueued = {FromBB, ToBB};
1012 SmallVector<const MachineBasicBlock *, 16> Worklist;
1013 auto Enqueue = [&](const MachineBasicBlock *BB) {
1014 if (DomTree->dominates(A: FromBB, B: BB) && Enqueued.insert(Ptr: BB).second)
1015 Worklist.push_back(Elt: BB);
1016 };
1017
1018 for (const MachineBasicBlock *Pred : ToBB->predecessors())
1019 Enqueue(Pred);
1020
1021 while (!Worklist.empty()) {
1022 const MachineBasicBlock *BB = Worklist.pop_back_val();
1023
1024 // If the block belongs to a loop containing neither the load nor the
1025 // condition, that loop is executed entirely between the two, so consider
1026 // them far apart.
1027 if (const MachineLoop *BBLoop = Loops->getLoopFor(BB)) {
1028 if (!BBLoop->contains(BB: ToBB) && !BBLoop->contains(BB: FromBB)) {
1029 LLVM_DEBUG(dbgs() << " found a loop before the condition in "
1030 << printMBBReference(*BB) << '\n');
1031 return true;
1032 }
1033 }
1034
1035 // Next check for calls in the block.
1036 auto CacheIt = NoCallBlocksCache.find(Val: BB);
1037 if (CacheIt != NoCallBlocksCache.end()) {
1038 if (HitSearchLimit(CacheIt->second))
1039 return true;
1040 } else {
1041 unsigned NumBlockInstrs = 0;
1042 for (const MachineInstr &MI :
1043 instructionsWithoutDebug(It: BB->instr_begin(), End: BB->instr_end(),
1044 /*SkipPseudoOp=*/false)) {
1045 ++NumBlockInstrs;
1046 if (IsCallOrHitSearchLimit(MI))
1047 return true;
1048 }
1049 NoCallBlocksCache[BB] = NumBlockInstrs;
1050 }
1051
1052 for (const MachineBasicBlock *Pred : BB->predecessors())
1053 Enqueue(Pred);
1054 }
1055
1056 return false;
1057}
1058
1059/// Check if a register's value comes from a memory load by walking the
1060/// def-use chain. We want to prioritize converting branches which
1061/// depend on values loaded from memory (unless they are loop invariant,
1062/// or come from a constant pool). The walk starts from the definition of
1063/// ConditionDef's first operand, which is not ConditionDef itself for
1064/// instructions such as FCMPSrr, where that operand is a use.
1065bool EarlyIfConverter::doOperandsComeFromMemory(
1066 const MachineInstr *ConditionDef) {
1067 Register Reg = ConditionDef->getOperand(i: 0).getReg();
1068 if (!Reg.isVirtual())
1069 return false;
1070
1071 LLVM_DEBUG(dbgs() << " doOperandsComeFromMemory starting from reg "
1072 << printReg(Reg) << "\n");
1073
1074 // The condition is consumed by the branch terminating Head, so this is the
1075 // end of the interval a load has to survive without a call in between.
1076 const MachineInstr *Br = &*IfConv.Head->getFirstTerminator();
1077 MachineLoop *IfConvLoop = Loops->getLoopFor(BB: IfConv.Head);
1078
1079 // Walk the def-use chain.
1080 SmallPtrSet<const MachineInstr *, 8> VisitedInstrs;
1081 SmallVector<const MachineInstr *> Worklist;
1082
1083 MachineInstr *DefMI = MRI->getVRegDef(Reg);
1084 // The operand is defined outside of the function - it does not
1085 // come from memory access.
1086 if (!DefMI)
1087 return false;
1088
1089 Worklist.push_back(Elt: DefMI);
1090
1091 while (!Worklist.empty() && VisitedInstrs.size() < MaxNumSteps) {
1092 const MachineInstr *MI = Worklist.pop_back_val();
1093 if (!VisitedInstrs.insert(Ptr: MI).second)
1094 continue;
1095
1096 // Don't walk through PHIs: a value arriving on a back edge is loaded in a
1097 // previous iteration, so the interval between the load and the branch is
1098 // not the one hasCallOrLoopInRange measures.
1099 if (MI->isPHI())
1100 continue;
1101
1102 const MachineBasicBlock *Parent = MI->getParent();
1103 MachineLoop *ParentLoop = Loops->getLoopFor(BB: Parent);
1104
1105 // If the instruction is outside the loop, skip it (loop-invariant).
1106 if (IfConvLoop && ParentLoop != IfConvLoop)
1107 continue;
1108
1109 // Check if this instruction is a load, and there are no calls or loops
1110 // between the load and the condition (which would break the "close in
1111 // time" assumption).
1112 if (MI->mayLoad() && !isConstantPoolLoad(MI) &&
1113 !MI->isDereferenceableInvariantLoad()) {
1114 // If the load doesn't dominate the branch (e.g., comes after it in
1115 // the same block via a loop back-edge), it can't affect this iteration.
1116 // If not - check if there is a call or a loop between the load
1117 // instruction and the branch.
1118 if (!DomTree->dominates(A: MI, B: Br) || hasCallOrLoopInRange(From: MI, To: Br))
1119 continue;
1120
1121 return true;
1122 }
1123
1124 // Walk through all register use operands and find their definitions.
1125 for (const MachineOperand &MO : MI->operands()) {
1126 if (!MO.isReg() || !MO.isUse())
1127 continue;
1128 Register UseReg = MO.getReg();
1129 if (!UseReg.isVirtual())
1130 continue;
1131
1132 if (MachineInstr *UseDef = MRI->getVRegDef(Reg: UseReg)) {
1133 if (!VisitedInstrs.count(Ptr: UseDef)) {
1134 Worklist.push_back(Elt: UseDef);
1135 }
1136 }
1137 }
1138 }
1139
1140 return false;
1141}
1142
1143/// Check if the branch condition is data-dependent (comes from memory loads).
1144bool EarlyIfConverter::isConditionDataDependent() {
1145 TargetInstrInfo::MachineBranchPredicate MBP;
1146 if (TII->analyzeBranchPredicate(MBB&: *IfConv.Head, MBP, /*AllowModify=*/false))
1147 return false;
1148
1149 if (!MBP.ConditionDef)
1150 return false;
1151
1152 // If the branch is biased (not 50/50), don't consider it data dependent.
1153 // This is to prevent converting unprofitable checks such as
1154 // `x[i] != 0;`
1155 auto TBBProb = MBPI.getEdgeProbability(Src: IfConv.Head, Dst: IfConv.TBB);
1156 auto FBBProb = MBPI.getEdgeProbability(Src: IfConv.Head, Dst: IfConv.FBB);
1157 if (TBBProb != FBBProb) {
1158 ++NumLikelyBiased;
1159 return false;
1160 }
1161
1162 // Check if operands used to compute the branch condition were loaded recently
1163 // from memory, starting by the ConditionDef itself and walking up the use-def
1164 // chain.
1165 if (doOperandsComeFromMemory(ConditionDef: MBP.ConditionDef)) {
1166 ++NumDataDependant;
1167 return true;
1168 }
1169
1170 return false;
1171}
1172
1173// Adjust cycles with downward saturation.
1174static unsigned adjCycles(unsigned Cyc, int Delta) {
1175 if (Delta < 0 && Cyc + Delta > Cyc)
1176 return 0;
1177 return Cyc + Delta;
1178}
1179
1180namespace {
1181/// Helper class to simplify emission of cycle counts into optimization remarks.
1182struct Cycles {
1183 const char *Key;
1184 unsigned Value;
1185};
1186template <typename Remark> Remark &operator<<(Remark &R, Cycles C) {
1187 return R << ore::NV(C.Key, C.Value) << (C.Value == 1 ? " cycle" : " cycles");
1188}
1189} // anonymous namespace
1190
1191/// Apply cost model and heuristics to the if-conversion in IfConv.
1192/// Return true if the conversion is a good idea.
1193///
1194bool EarlyIfConverter::shouldConvertIf() {
1195 // Stress testing mode disables all cost considerations.
1196 if (Stress)
1197 return true;
1198
1199 // Do not try to if-convert if the condition has a high chance of being
1200 // predictable.
1201 MachineLoop *CurrentLoop = Loops->getLoopFor(BB: IfConv.Head);
1202 // If the condition is in a loop, consider it predictable if the condition
1203 // itself or all its operands are loop-invariant. E.g. this considers a load
1204 // from a loop-invariant address predictable; we were unable to prove that it
1205 // doesn't alias any of the memory-writes in the loop, but it is likely to
1206 // read to same value multiple times.
1207 if (CurrentLoop && any_of(Range&: IfConv.Cond, P: [&](MachineOperand &MO) {
1208 if (!MO.isReg() || !MO.isUse())
1209 return false;
1210 Register Reg = MO.getReg();
1211 if (Reg.isPhysical())
1212 return false;
1213
1214 MachineInstr *Def = MRI->getVRegDef(Reg);
1215 return CurrentLoop->isLoopInvariant(I&: *Def) ||
1216 all_of(Range: Def->operands(), P: [&](MachineOperand &Op) {
1217 if (Op.isImm())
1218 return true;
1219 if (!Op.isReg() || !Op.isUse())
1220 return true;
1221 Register Reg = Op.getReg();
1222 if (Reg.isPhysical())
1223 return false;
1224
1225 MachineInstr *Def = MRI->getVRegDef(Reg);
1226 return CurrentLoop->isLoopInvariant(I&: *Def);
1227 });
1228 }))
1229 return false;
1230
1231 if (!MinInstr)
1232 MinInstr = Traces->getEnsemble(MachineTraceStrategy::TS_MinInstrCount);
1233
1234 MachineTraceMetrics::Trace TBBTrace = MinInstr->getTrace(MBB: IfConv.getTPred());
1235 MachineTraceMetrics::Trace FBBTrace = MinInstr->getTrace(MBB: IfConv.getFPred());
1236 LLVM_DEBUG(dbgs() << "TBB: " << TBBTrace << "FBB: " << FBBTrace);
1237 unsigned MinCrit = std::min(a: TBBTrace.getCriticalPath(),
1238 b: FBBTrace.getCriticalPath());
1239
1240 // Set a somewhat arbitrary limit on the critical path extension we accept.
1241 // Use the full misprediction penalty for data-dependent branches and half
1242 // for others. A branch with a cold edge below ColdEdgeThreshold gets no
1243 // extending the critical path: it is unlikely to mispredict often enough
1244 // to recover the extra latency from if-conversion.
1245 bool DataDependent = false;
1246 if (EnableDataDependentBranchAnalysis)
1247 DataDependent = isConditionDataDependent();
1248
1249 const unsigned MispredictPenalty = STI->getMispredictionPenalty();
1250 unsigned CritLimit =
1251 DataDependent ? MispredictPenalty : MispredictPenalty / 2;
1252 const BranchProbability ColdProb =
1253 std::min(a: MBPI.getEdgeProbability(Src: IfConv.Head, Dst: IfConv.TBB),
1254 b: MBPI.getEdgeProbability(Src: IfConv.Head, Dst: IfConv.FBB));
1255 const unsigned ColdEdgePercent = std::min(a: ColdEdgeThreshold.getValue(), b: 50U);
1256 const bool StronglyBiased =
1257 ColdProb < BranchProbability(ColdEdgePercent, 100);
1258 if (StronglyBiased) {
1259 CritLimit = 0;
1260 ++NumStronglyBiased;
1261 }
1262
1263 MachineBasicBlock &MBB = *IfConv.Head;
1264 MachineOptimizationRemarkEmitter MORE(*MBB.getParent(), nullptr);
1265
1266 LLVM_DEBUG(dbgs() << "Cold edge probability: " << ColdProb
1267 << ", critical-path budget: " << CritLimit << " cycles\n");
1268 if (StronglyBiased) {
1269 MORE.emit(RemarkBuilder: [&]() {
1270 return MachineOptimizationRemarkAnalysis(DEBUG_TYPE,
1271 "StronglyBiasedBranch",
1272 MBB.back().getDebugLoc(), &MBB)
1273 << "branch has a cold edge below "
1274 << ore::NV("ColdEdgeThreshold", ColdEdgePercent)
1275 << "%, using a critical-path "
1276 "extension budget of "
1277 << ore::NV("CritLimit", CritLimit) << " cycles";
1278 });
1279 }
1280
1281 // Emit analysis remark about data-dependent condition.
1282 if (DataDependent) {
1283 MORE.emit(RemarkBuilder: [&]() {
1284 return MachineOptimizationRemarkAnalysis(DEBUG_TYPE,
1285 "DataDependentCondition",
1286 MBB.back().getDebugLoc(), &MBB)
1287 << "branch condition is data-dependent (from memory load), "
1288 << "using higher CritLimit of " << ore::NV("CritLimit", CritLimit)
1289 << " cycles";
1290 });
1291 }
1292
1293 // If-conversion only makes sense when there is unexploited ILP. Compute the
1294 // maximum-ILP resource length of the trace after if-conversion. Compare it
1295 // to the shortest critical path.
1296 SmallVector<const MachineBasicBlock*, 1> ExtraBlocks;
1297 if (IfConv.TBB != IfConv.Tail)
1298 ExtraBlocks.push_back(Elt: IfConv.TBB);
1299 unsigned ResLength = FBBTrace.getResourceLength(Extrablocks: ExtraBlocks);
1300 LLVM_DEBUG(dbgs() << "Resource length " << ResLength
1301 << ", minimal critical path " << MinCrit << '\n');
1302 if (ResLength > MinCrit + CritLimit) {
1303 LLVM_DEBUG(dbgs() << "Not enough available ILP.\n");
1304 MORE.emit(RemarkBuilder: [&]() {
1305 MachineOptimizationRemarkMissed R(DEBUG_TYPE, "IfConversion",
1306 MBB.findDebugLoc(MBBI: MBB.back()), &MBB);
1307 R << "did not if-convert branch: the resulting critical path ("
1308 << Cycles{.Key: "ResLength", .Value: ResLength}
1309 << ") would extend the shorter leg's critical path ("
1310 << Cycles{.Key: "MinCrit", .Value: MinCrit} << ") by more than the threshold of "
1311 << Cycles{.Key: "CritLimit", .Value: CritLimit}
1312 << ", which cannot be hidden by available ILP.";
1313 return R;
1314 });
1315 return false;
1316 }
1317
1318 // Assume that the depth of the first head terminator will also be the depth
1319 // of the select instruction inserted, as determined by the flag dependency.
1320 // TBB / FBB data dependencies may delay the select even more.
1321 MachineTraceMetrics::Trace HeadTrace = MinInstr->getTrace(MBB: IfConv.Head);
1322 unsigned BranchDepth =
1323 HeadTrace.getInstrCycles(MI: *IfConv.Head->getFirstTerminator()).Depth;
1324 LLVM_DEBUG(dbgs() << "Branch depth: " << BranchDepth << '\n');
1325
1326 // Look at all the tail phis, and compute the critical path extension caused
1327 // by inserting select instructions.
1328 MachineTraceMetrics::Trace TailTrace = MinInstr->getTrace(MBB: IfConv.Tail);
1329 struct CriticalPathInfo {
1330 unsigned Extra; // Count of extra cycles that the component adds.
1331 unsigned Depth; // Absolute depth of the component in cycles.
1332 };
1333 CriticalPathInfo Cond{};
1334 CriticalPathInfo TBlock{};
1335 CriticalPathInfo FBlock{};
1336 bool ShouldConvert = true;
1337 for (SSAIfConv::PHIInfo &PI : IfConv.PHIs) {
1338 unsigned Slack = TailTrace.getInstrSlack(MI: *PI.PHI);
1339 unsigned MaxDepth = Slack + TailTrace.getInstrCycles(MI: *PI.PHI).Depth;
1340 LLVM_DEBUG(dbgs() << "Slack " << Slack << ":\t" << *PI.PHI);
1341
1342 // The condition is pulled into the critical path.
1343 unsigned CondDepth = adjCycles(Cyc: BranchDepth, Delta: PI.Select.CondCycles);
1344 if (CondDepth > MaxDepth) {
1345 unsigned Extra = CondDepth - MaxDepth;
1346 LLVM_DEBUG(dbgs() << "Condition adds " << Extra << " cycles.\n");
1347 if (Extra > Cond.Extra)
1348 Cond = {.Extra: Extra, .Depth: CondDepth};
1349 if (Extra > CritLimit) {
1350 LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');
1351 ShouldConvert = false;
1352 }
1353 }
1354
1355 // The TBB value is pulled into the critical path.
1356 unsigned TDepth =
1357 adjCycles(Cyc: TBBTrace.getPHIDepth(PHI: *PI.PHI), Delta: PI.Select.TrueCycles);
1358 if (TDepth > MaxDepth) {
1359 unsigned Extra = TDepth - MaxDepth;
1360 LLVM_DEBUG(dbgs() << "TBB data adds " << Extra << " cycles.\n");
1361 if (Extra > TBlock.Extra)
1362 TBlock = {.Extra: Extra, .Depth: TDepth};
1363 if (Extra > CritLimit) {
1364 LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');
1365 ShouldConvert = false;
1366 }
1367 }
1368
1369 // The FBB value is pulled into the critical path.
1370 unsigned FDepth =
1371 adjCycles(Cyc: FBBTrace.getPHIDepth(PHI: *PI.PHI), Delta: PI.Select.FalseCycles);
1372 if (FDepth > MaxDepth) {
1373 unsigned Extra = FDepth - MaxDepth;
1374 LLVM_DEBUG(dbgs() << "FBB data adds " << Extra << " cycles.\n");
1375 if (Extra > FBlock.Extra)
1376 FBlock = {.Extra: Extra, .Depth: FDepth};
1377 if (Extra > CritLimit) {
1378 LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');
1379 ShouldConvert = false;
1380 }
1381 }
1382 }
1383
1384 // Organize by "short" and "long" legs, since the diagnostics get confusing
1385 // when referring to the "true" and "false" sides of the branch, given that
1386 // those don't always correlate with what the user wrote in source-terms.
1387 const CriticalPathInfo Short = TBlock.Extra > FBlock.Extra ? FBlock : TBlock;
1388 const CriticalPathInfo Long = TBlock.Extra > FBlock.Extra ? TBlock : FBlock;
1389
1390 if (ShouldConvert) {
1391 MORE.emit(RemarkBuilder: [&]() {
1392 MachineOptimizationRemark R(DEBUG_TYPE, "IfConversion",
1393 MBB.back().getDebugLoc(), &MBB);
1394 R << "performing if-conversion on branch: the condition adds "
1395 << Cycles{.Key: "CondCycles", .Value: Cond.Extra} << " to the critical path";
1396 if (Short.Extra > 0)
1397 R << ", and the short leg adds another "
1398 << Cycles{.Key: "ShortCycles", .Value: Short.Extra};
1399 if (Long.Extra > 0)
1400 R << ", and the long leg adds another "
1401 << Cycles{.Key: "LongCycles", .Value: Long.Extra};
1402 R << ", each staying under the threshold of "
1403 << Cycles{.Key: "CritLimit", .Value: CritLimit} << ".";
1404 return R;
1405 });
1406 } else {
1407 MORE.emit(RemarkBuilder: [&]() {
1408 MachineOptimizationRemarkMissed R(DEBUG_TYPE, "IfConversion",
1409 MBB.back().getDebugLoc(), &MBB);
1410 R << "did not if-convert branch: the condition would add "
1411 << Cycles{.Key: "CondCycles", .Value: Cond.Extra} << " to the critical path";
1412 if (Cond.Extra > CritLimit)
1413 R << " exceeding the limit of " << Cycles{.Key: "CritLimit", .Value: CritLimit};
1414 if (Short.Extra > 0) {
1415 R << ", and the short leg would add another "
1416 << Cycles{.Key: "ShortCycles", .Value: Short.Extra};
1417 if (Short.Extra > CritLimit)
1418 R << " exceeding the limit of " << Cycles{.Key: "CritLimit", .Value: CritLimit};
1419 }
1420 if (Long.Extra > 0) {
1421 R << ", and the long leg would add another "
1422 << Cycles{.Key: "LongCycles", .Value: Long.Extra};
1423 if (Long.Extra > CritLimit)
1424 R << " exceeding the limit of " << Cycles{.Key: "CritLimit", .Value: CritLimit};
1425 }
1426 R << ".";
1427 return R;
1428 });
1429 }
1430
1431 return ShouldConvert;
1432}
1433
1434/// Attempt repeated if-conversion on MBB, return true if successful.
1435///
1436bool EarlyIfConverter::tryConvertIf(MachineBasicBlock *MBB) {
1437 bool Changed = false;
1438 while (IfConv.canConvertIf(MBB) && shouldConvertIf()) {
1439 // If-convert MBB and update analyses.
1440 invalidateTraces();
1441 SmallVector<MachineBasicBlock *, 4> RemoveBlocks;
1442 IfConv.convertIf(RemoveBlocks);
1443 Changed = true;
1444 updateDomTree(DomTree, IfConv, Removed: RemoveBlocks);
1445 updateLoops(Loops, Removed: RemoveBlocks);
1446 // Head absorbs the instructions of the removed blocks, including any calls,
1447 // so a Head cached as call-free may no longer be.
1448 NoCallBlocksCache.erase(Val: IfConv.Head);
1449 for (MachineBasicBlock *MBB : RemoveBlocks) {
1450 NoCallBlocksCache.erase(Val: MBB);
1451 MBB->eraseFromParent();
1452 }
1453 }
1454 return Changed;
1455}
1456
1457bool EarlyIfConverter::run(MachineFunction &MF) {
1458 LLVM_DEBUG(dbgs() << "********** EARLY IF-CONVERSION **********\n"
1459 << "********** Function: " << MF.getName() << '\n');
1460
1461 STI = &MF.getSubtarget();
1462 // Only run if conversion if the target wants it.
1463 if (!STI->enableEarlyIfConversion())
1464 return false;
1465
1466 TII = STI->getInstrInfo();
1467 TRI = STI->getRegisterInfo();
1468 MRI = &MF.getRegInfo();
1469 MinInstr = nullptr;
1470
1471 bool Changed = false;
1472 IfConv.init(MF);
1473
1474 // Visit blocks in dominator tree post-order. The post-order enables nested
1475 // if-conversion in a single pass. The tryConvertIf() function may erase
1476 // blocks, but only blocks dominated by the head block. This makes it safe to
1477 // update the dominator tree while the post-order iterator is still active.
1478 for (auto *DomNode : post_order(G: DomTree))
1479 if (tryConvertIf(MBB: DomNode->getBlock()))
1480 Changed = true;
1481
1482 return Changed;
1483}
1484
1485PreservedAnalyses
1486EarlyIfConverterPass::run(MachineFunction &MF,
1487 MachineFunctionAnalysisManager &MFAM) {
1488 MachineDominatorTree &MDT = MFAM.getResult<MachineDominatorTreeAnalysis>(IR&: MF);
1489 MachineLoopInfo &LI = MFAM.getResult<MachineLoopAnalysis>(IR&: MF);
1490 MachineTraceMetrics &MTM = MFAM.getResult<MachineTraceMetricsAnalysis>(IR&: MF);
1491 MachineBranchProbabilityInfo &MBPI =
1492 MFAM.getResult<MachineBranchProbabilityAnalysis>(IR&: MF);
1493
1494 EarlyIfConverter Impl(MDT, LI, MTM, MBPI);
1495 bool Changed = Impl.run(MF);
1496 if (!Changed)
1497 return PreservedAnalyses::all();
1498
1499 auto PA = getMachineFunctionPassPreservedAnalyses();
1500 PA.preserve<MachineDominatorTreeAnalysis>();
1501 PA.preserve<MachineLoopAnalysis>();
1502 PA.preserve<MachineTraceMetricsAnalysis>();
1503 return PA;
1504}
1505
1506bool EarlyIfConverterLegacy::runOnMachineFunction(MachineFunction &MF) {
1507 if (skipFunction(F: MF.getFunction()))
1508 return false;
1509
1510 MachineDominatorTree &MDT =
1511 getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
1512 MachineLoopInfo &LI = getAnalysis<MachineLoopInfoWrapperPass>().getLI();
1513 MachineTraceMetrics &MTM =
1514 getAnalysis<MachineTraceMetricsWrapperPass>().getMTM();
1515 MachineBranchProbabilityInfo &MBPI =
1516 getAnalysis<MachineBranchProbabilityInfoWrapperPass>().getMBPI();
1517
1518 return EarlyIfConverter(MDT, LI, MTM, MBPI).run(MF);
1519}
1520
1521//===----------------------------------------------------------------------===//
1522// EarlyIfPredicator Pass
1523//===----------------------------------------------------------------------===//
1524
1525namespace {
1526class EarlyIfPredicator : public MachineFunctionPass {
1527 const TargetInstrInfo *TII = nullptr;
1528 const TargetRegisterInfo *TRI = nullptr;
1529 TargetSchedModel SchedModel;
1530 MachineRegisterInfo *MRI = nullptr;
1531 MachineDominatorTree *DomTree = nullptr;
1532 MachineBranchProbabilityInfo *MBPI = nullptr;
1533 MachineLoopInfo *Loops = nullptr;
1534 SSAIfConv IfConv;
1535
1536public:
1537 static char ID;
1538 EarlyIfPredicator() : MachineFunctionPass(ID) {}
1539 void getAnalysisUsage(AnalysisUsage &AU) const override;
1540 bool runOnMachineFunction(MachineFunction &MF) override;
1541 StringRef getPassName() const override { return "Early If-predicator"; }
1542
1543protected:
1544 bool tryConvertIf(MachineBasicBlock *);
1545 bool shouldConvertIf();
1546};
1547} // end anonymous namespace
1548
1549#undef DEBUG_TYPE
1550#define DEBUG_TYPE "early-if-predicator"
1551
1552char EarlyIfPredicator::ID = 0;
1553char &llvm::EarlyIfPredicatorID = EarlyIfPredicator::ID;
1554
1555INITIALIZE_PASS_BEGIN(EarlyIfPredicator, DEBUG_TYPE, "Early If Predicator",
1556 false, false)
1557INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
1558INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfoWrapperPass)
1559INITIALIZE_PASS_END(EarlyIfPredicator, DEBUG_TYPE, "Early If Predicator", false,
1560 false)
1561
1562void EarlyIfPredicator::getAnalysisUsage(AnalysisUsage &AU) const {
1563 AU.addRequired<MachineBranchProbabilityInfoWrapperPass>();
1564 AU.addRequired<MachineDominatorTreeWrapperPass>();
1565 AU.addPreserved<MachineDominatorTreeWrapperPass>();
1566 AU.addRequired<MachineLoopInfoWrapperPass>();
1567 AU.addPreserved<MachineLoopInfoWrapperPass>();
1568 MachineFunctionPass::getAnalysisUsage(AU);
1569}
1570
1571/// Apply the target heuristic to decide if the transformation is profitable.
1572bool EarlyIfPredicator::shouldConvertIf() {
1573 auto TrueProbability = MBPI->getEdgeProbability(Src: IfConv.Head, Dst: IfConv.TBB);
1574 if (IfConv.isTriangle()) {
1575 MachineBasicBlock &IfBlock =
1576 (IfConv.TBB == IfConv.Tail) ? *IfConv.FBB : *IfConv.TBB;
1577
1578 unsigned ExtraPredCost = 0;
1579 unsigned Cycles = 0;
1580 for (MachineInstr &I : IfBlock) {
1581 unsigned NumCycles = SchedModel.computeInstrLatency(MI: &I, UseDefaultDefLatency: false);
1582 if (NumCycles > 1)
1583 Cycles += NumCycles - 1;
1584 ExtraPredCost += TII->getPredicationCost(MI: I);
1585 }
1586
1587 return TII->isProfitableToIfCvt(MBB&: IfBlock, NumCycles: Cycles, ExtraPredCycles: ExtraPredCost,
1588 Probability: TrueProbability);
1589 }
1590 unsigned TExtra = 0;
1591 unsigned FExtra = 0;
1592 unsigned TCycle = 0;
1593 unsigned FCycle = 0;
1594 for (MachineInstr &I : *IfConv.TBB) {
1595 unsigned NumCycles = SchedModel.computeInstrLatency(MI: &I, UseDefaultDefLatency: false);
1596 if (NumCycles > 1)
1597 TCycle += NumCycles - 1;
1598 TExtra += TII->getPredicationCost(MI: I);
1599 }
1600 for (MachineInstr &I : *IfConv.FBB) {
1601 unsigned NumCycles = SchedModel.computeInstrLatency(MI: &I, UseDefaultDefLatency: false);
1602 if (NumCycles > 1)
1603 FCycle += NumCycles - 1;
1604 FExtra += TII->getPredicationCost(MI: I);
1605 }
1606 return TII->isProfitableToIfCvt(TMBB&: *IfConv.TBB, NumTCycles: TCycle, ExtraTCycles: TExtra, FMBB&: *IfConv.FBB,
1607 NumFCycles: FCycle, ExtraFCycles: FExtra, Probability: TrueProbability);
1608}
1609
1610/// Attempt repeated if-conversion on MBB, return true if successful.
1611///
1612bool EarlyIfPredicator::tryConvertIf(MachineBasicBlock *MBB) {
1613 bool Changed = false;
1614 while (IfConv.canConvertIf(MBB, /*Predicate*/ true) && shouldConvertIf()) {
1615 // If-convert MBB and update analyses.
1616 SmallVector<MachineBasicBlock *, 4> RemoveBlocks;
1617 IfConv.convertIf(RemoveBlocks, /*Predicate*/ true);
1618 Changed = true;
1619 updateDomTree(DomTree, IfConv, Removed: RemoveBlocks);
1620 updateLoops(Loops, Removed: RemoveBlocks);
1621 for (MachineBasicBlock *MBB : RemoveBlocks)
1622 MBB->eraseFromParent();
1623 }
1624 return Changed;
1625}
1626
1627bool EarlyIfPredicator::runOnMachineFunction(MachineFunction &MF) {
1628 LLVM_DEBUG(dbgs() << "********** EARLY IF-PREDICATOR **********\n"
1629 << "********** Function: " << MF.getName() << '\n');
1630 if (skipFunction(F: MF.getFunction()))
1631 return false;
1632
1633 const TargetSubtargetInfo &STI = MF.getSubtarget();
1634 TII = STI.getInstrInfo();
1635 TRI = STI.getRegisterInfo();
1636 MRI = &MF.getRegInfo();
1637 SchedModel.init(TSInfo: &STI);
1638 DomTree = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
1639 Loops = &getAnalysis<MachineLoopInfoWrapperPass>().getLI();
1640 MBPI = &getAnalysis<MachineBranchProbabilityInfoWrapperPass>().getMBPI();
1641
1642 bool Changed = false;
1643 IfConv.init(MF);
1644
1645 // Visit blocks in dominator tree post-order. The post-order enables nested
1646 // if-conversion in a single pass. The tryConvertIf() function may erase
1647 // blocks, but only blocks dominated by the head block. This makes it safe to
1648 // update the dominator tree while the post-order iterator is still active.
1649 for (auto *DomNode : post_order(G: DomTree))
1650 if (tryConvertIf(MBB: DomNode->getBlock()))
1651 Changed = true;
1652
1653 return Changed;
1654}
1655