xref: /freebsd/contrib/llvm-project/llvm/lib/CodeGen/EarlyIfConversion.cpp (revision cfd6422a5217410fbd66f7a7a8a64d9d85e61229)
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/ADT/BitVector.h"
19 #include "llvm/ADT/PostOrderIterator.h"
20 #include "llvm/ADT/SetVector.h"
21 #include "llvm/ADT/SmallPtrSet.h"
22 #include "llvm/ADT/SparseSet.h"
23 #include "llvm/ADT/Statistic.h"
24 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
25 #include "llvm/CodeGen/MachineDominators.h"
26 #include "llvm/CodeGen/MachineFunction.h"
27 #include "llvm/CodeGen/MachineFunctionPass.h"
28 #include "llvm/CodeGen/MachineInstr.h"
29 #include "llvm/CodeGen/MachineLoopInfo.h"
30 #include "llvm/CodeGen/MachineRegisterInfo.h"
31 #include "llvm/CodeGen/MachineTraceMetrics.h"
32 #include "llvm/CodeGen/Passes.h"
33 #include "llvm/CodeGen/TargetInstrInfo.h"
34 #include "llvm/CodeGen/TargetRegisterInfo.h"
35 #include "llvm/CodeGen/TargetSubtargetInfo.h"
36 #include "llvm/InitializePasses.h"
37 #include "llvm/Support/CommandLine.h"
38 #include "llvm/Support/Debug.h"
39 #include "llvm/Support/raw_ostream.h"
40 
41 using namespace llvm;
42 
43 #define DEBUG_TYPE "early-ifcvt"
44 
45 // Absolute maximum number of instructions allowed per speculated block.
46 // This bypasses all other heuristics, so it should be set fairly high.
47 static cl::opt<unsigned>
48 BlockInstrLimit("early-ifcvt-limit", cl::init(30), cl::Hidden,
49   cl::desc("Maximum number of instructions per speculated block."));
50 
51 // Stress testing mode - disable heuristics.
52 static cl::opt<bool> Stress("stress-early-ifcvt", cl::Hidden,
53   cl::desc("Turn all knobs to 11"));
54 
55 STATISTIC(NumDiamondsSeen,  "Number of diamonds");
56 STATISTIC(NumDiamondsConv,  "Number of diamonds converted");
57 STATISTIC(NumTrianglesSeen, "Number of triangles");
58 STATISTIC(NumTrianglesConv, "Number of triangles converted");
59 
60 //===----------------------------------------------------------------------===//
61 //                                 SSAIfConv
62 //===----------------------------------------------------------------------===//
63 //
64 // The SSAIfConv class performs if-conversion on SSA form machine code after
65 // determining if it is possible. The class contains no heuristics; external
66 // code should be used to determine when if-conversion is a good idea.
67 //
68 // SSAIfConv can convert both triangles and diamonds:
69 //
70 //   Triangle: Head              Diamond: Head
71 //              | \                       /  \_
72 //              |  \                     /    |
73 //              |  [TF]BB              FBB    TBB
74 //              |  /                     \    /
75 //              | /                       \  /
76 //             Tail                       Tail
77 //
78 // Instructions in the conditional blocks TBB and/or FBB are spliced into the
79 // Head block, and phis in the Tail block are converted to select instructions.
80 //
81 namespace {
82 class SSAIfConv {
83   const TargetInstrInfo *TII;
84   const TargetRegisterInfo *TRI;
85   MachineRegisterInfo *MRI;
86 
87 public:
88   /// The block containing the conditional branch.
89   MachineBasicBlock *Head;
90 
91   /// The block containing phis after the if-then-else.
92   MachineBasicBlock *Tail;
93 
94   /// The 'true' conditional block as determined by analyzeBranch.
95   MachineBasicBlock *TBB;
96 
97   /// The 'false' conditional block as determined by analyzeBranch.
98   MachineBasicBlock *FBB;
99 
100   /// isTriangle - When there is no 'else' block, either TBB or FBB will be
101   /// equal to Tail.
102   bool isTriangle() const { return TBB == Tail || FBB == Tail; }
103 
104   /// Returns the Tail predecessor for the True side.
105   MachineBasicBlock *getTPred() const { return TBB == Tail ? Head : TBB; }
106 
107   /// Returns the Tail predecessor for the  False side.
108   MachineBasicBlock *getFPred() const { return FBB == Tail ? Head : FBB; }
109 
110   /// Information about each phi in the Tail block.
111   struct PHIInfo {
112     MachineInstr *PHI;
113     unsigned TReg, FReg;
114     // Latencies from Cond+Branch, TReg, and FReg to DstReg.
115     int CondCycles, TCycles, FCycles;
116 
117     PHIInfo(MachineInstr *phi)
118       : PHI(phi), TReg(0), FReg(0), CondCycles(0), TCycles(0), FCycles(0) {}
119   };
120 
121   SmallVector<PHIInfo, 8> PHIs;
122 
123 private:
124   /// The branch condition determined by analyzeBranch.
125   SmallVector<MachineOperand, 4> Cond;
126 
127   /// Instructions in Head that define values used by the conditional blocks.
128   /// The hoisted instructions must be inserted after these instructions.
129   SmallPtrSet<MachineInstr*, 8> InsertAfter;
130 
131   /// Register units clobbered by the conditional blocks.
132   BitVector ClobberedRegUnits;
133 
134   // Scratch pad for findInsertionPoint.
135   SparseSet<unsigned> LiveRegUnits;
136 
137   /// Insertion point in Head for speculatively executed instructions form TBB
138   /// and FBB.
139   MachineBasicBlock::iterator InsertionPoint;
140 
141   /// Return true if all non-terminator instructions in MBB can be safely
142   /// speculated.
143   bool canSpeculateInstrs(MachineBasicBlock *MBB);
144 
145   /// Return true if all non-terminator instructions in MBB can be safely
146   /// predicated.
147   bool canPredicateInstrs(MachineBasicBlock *MBB);
148 
149   /// Scan through instruction dependencies and update InsertAfter array.
150   /// Return false if any dependency is incompatible with if conversion.
151   bool InstrDependenciesAllowIfConv(MachineInstr *I);
152 
153   /// Predicate all instructions of the basic block with current condition
154   /// except for terminators. Reverse the condition if ReversePredicate is set.
155   void PredicateBlock(MachineBasicBlock *MBB, bool ReversePredicate);
156 
157   /// Find a valid insertion point in Head.
158   bool findInsertionPoint();
159 
160   /// Replace PHI instructions in Tail with selects.
161   void replacePHIInstrs();
162 
163   /// Insert selects and rewrite PHI operands to use them.
164   void rewritePHIOperands();
165 
166 public:
167   /// runOnMachineFunction - Initialize per-function data structures.
168   void runOnMachineFunction(MachineFunction &MF) {
169     TII = MF.getSubtarget().getInstrInfo();
170     TRI = MF.getSubtarget().getRegisterInfo();
171     MRI = &MF.getRegInfo();
172     LiveRegUnits.clear();
173     LiveRegUnits.setUniverse(TRI->getNumRegUnits());
174     ClobberedRegUnits.clear();
175     ClobberedRegUnits.resize(TRI->getNumRegUnits());
176   }
177 
178   /// canConvertIf - If the sub-CFG headed by MBB can be if-converted,
179   /// initialize the internal state, and return true.
180   /// If predicate is set try to predicate the block otherwise try to
181   /// speculatively execute it.
182   bool canConvertIf(MachineBasicBlock *MBB, bool Predicate = false);
183 
184   /// convertIf - If-convert the last block passed to canConvertIf(), assuming
185   /// it is possible. Add any erased blocks to RemovedBlocks.
186   void convertIf(SmallVectorImpl<MachineBasicBlock *> &RemovedBlocks,
187                  bool Predicate = false);
188 };
189 } // end anonymous namespace
190 
191 
192 /// canSpeculateInstrs - Returns true if all the instructions in MBB can safely
193 /// be speculated. The terminators are not considered.
194 ///
195 /// If instructions use any values that are defined in the head basic block,
196 /// the defining instructions are added to InsertAfter.
197 ///
198 /// Any clobbered regunits are added to ClobberedRegUnits.
199 ///
200 bool SSAIfConv::canSpeculateInstrs(MachineBasicBlock *MBB) {
201   // Reject any live-in physregs. It's probably CPSR/EFLAGS, and very hard to
202   // get right.
203   if (!MBB->livein_empty()) {
204     LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has live-ins.\n");
205     return false;
206   }
207 
208   unsigned InstrCount = 0;
209 
210   // Check all instructions, except the terminators. It is assumed that
211   // terminators never have side effects or define any used register values.
212   for (MachineBasicBlock::iterator I = MBB->begin(),
213        E = MBB->getFirstTerminator(); I != E; ++I) {
214     if (I->isDebugInstr())
215       continue;
216 
217     if (++InstrCount > BlockInstrLimit && !Stress) {
218       LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has more than "
219                         << BlockInstrLimit << " instructions.\n");
220       return false;
221     }
222 
223     // There shouldn't normally be any phis in a single-predecessor block.
224     if (I->isPHI()) {
225       LLVM_DEBUG(dbgs() << "Can't hoist: " << *I);
226       return false;
227     }
228 
229     // Don't speculate loads. Note that it may be possible and desirable to
230     // speculate GOT or constant pool loads that are guaranteed not to trap,
231     // but we don't support that for now.
232     if (I->mayLoad()) {
233       LLVM_DEBUG(dbgs() << "Won't speculate load: " << *I);
234       return false;
235     }
236 
237     // We never speculate stores, so an AA pointer isn't necessary.
238     bool DontMoveAcrossStore = true;
239     if (!I->isSafeToMove(nullptr, DontMoveAcrossStore)) {
240       LLVM_DEBUG(dbgs() << "Can't speculate: " << *I);
241       return false;
242     }
243 
244     // Check for any dependencies on Head instructions.
245     if (!InstrDependenciesAllowIfConv(&(*I)))
246       return false;
247   }
248   return true;
249 }
250 
251 /// Check that there is no dependencies preventing if conversion.
252 ///
253 /// If instruction uses any values that are defined in the head basic block,
254 /// the defining instructions are added to InsertAfter.
255 bool SSAIfConv::InstrDependenciesAllowIfConv(MachineInstr *I) {
256   for (const MachineOperand &MO : I->operands()) {
257     if (MO.isRegMask()) {
258       LLVM_DEBUG(dbgs() << "Won't speculate regmask: " << *I);
259       return false;
260     }
261     if (!MO.isReg())
262       continue;
263     Register Reg = MO.getReg();
264 
265     // Remember clobbered regunits.
266     if (MO.isDef() && Register::isPhysicalRegister(Reg))
267       for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units)
268         ClobberedRegUnits.set(*Units);
269 
270     if (!MO.readsReg() || !Register::isVirtualRegister(Reg))
271       continue;
272     MachineInstr *DefMI = MRI->getVRegDef(Reg);
273     if (!DefMI || DefMI->getParent() != Head)
274       continue;
275     if (InsertAfter.insert(DefMI).second)
276       LLVM_DEBUG(dbgs() << printMBBReference(*I->getParent()) << " depends on "
277                         << *DefMI);
278     if (DefMI->isTerminator()) {
279       LLVM_DEBUG(dbgs() << "Can't insert instructions below terminator.\n");
280       return false;
281     }
282   }
283   return true;
284 }
285 
286 /// canPredicateInstrs - Returns true if all the instructions in MBB can safely
287 /// be predicates. The terminators are not considered.
288 ///
289 /// If instructions use any values that are defined in the head basic block,
290 /// the defining instructions are added to InsertAfter.
291 ///
292 /// Any clobbered regunits are added to ClobberedRegUnits.
293 ///
294 bool SSAIfConv::canPredicateInstrs(MachineBasicBlock *MBB) {
295   // Reject any live-in physregs. It's probably CPSR/EFLAGS, and very hard to
296   // get right.
297   if (!MBB->livein_empty()) {
298     LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has live-ins.\n");
299     return false;
300   }
301 
302   unsigned InstrCount = 0;
303 
304   // Check all instructions, except the terminators. It is assumed that
305   // terminators never have side effects or define any used register values.
306   for (MachineBasicBlock::iterator I = MBB->begin(),
307                                    E = MBB->getFirstTerminator();
308        I != E; ++I) {
309     if (I->isDebugInstr())
310       continue;
311 
312     if (++InstrCount > BlockInstrLimit && !Stress) {
313       LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has more than "
314                         << BlockInstrLimit << " instructions.\n");
315       return false;
316     }
317 
318     // There shouldn't normally be any phis in a single-predecessor block.
319     if (I->isPHI()) {
320       LLVM_DEBUG(dbgs() << "Can't predicate: " << *I);
321       return false;
322     }
323 
324     // Check that instruction is predicable and that it is not already
325     // predicated.
326     if (!TII->isPredicable(*I) || TII->isPredicated(*I)) {
327       return false;
328     }
329 
330     // Check for any dependencies on Head instructions.
331     if (!InstrDependenciesAllowIfConv(&(*I)))
332       return false;
333   }
334   return true;
335 }
336 
337 // Apply predicate to all instructions in the machine block.
338 void SSAIfConv::PredicateBlock(MachineBasicBlock *MBB, bool ReversePredicate) {
339   auto Condition = Cond;
340   if (ReversePredicate)
341     TII->reverseBranchCondition(Condition);
342   // Terminators don't need to be predicated as they will be removed.
343   for (MachineBasicBlock::iterator I = MBB->begin(),
344                                    E = MBB->getFirstTerminator();
345        I != E; ++I) {
346     if (I->isDebugInstr())
347       continue;
348     TII->PredicateInstruction(*I, Condition);
349   }
350 }
351 
352 /// Find an insertion point in Head for the speculated instructions. The
353 /// insertion point must be:
354 ///
355 /// 1. Before any terminators.
356 /// 2. After any instructions in InsertAfter.
357 /// 3. Not have any clobbered regunits live.
358 ///
359 /// This function sets InsertionPoint and returns true when successful, it
360 /// returns false if no valid insertion point could be found.
361 ///
362 bool SSAIfConv::findInsertionPoint() {
363   // Keep track of live regunits before the current position.
364   // Only track RegUnits that are also in ClobberedRegUnits.
365   LiveRegUnits.clear();
366   SmallVector<unsigned, 8> Reads;
367   MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator();
368   MachineBasicBlock::iterator I = Head->end();
369   MachineBasicBlock::iterator B = Head->begin();
370   while (I != B) {
371     --I;
372     // Some of the conditional code depends in I.
373     if (InsertAfter.count(&*I)) {
374       LLVM_DEBUG(dbgs() << "Can't insert code after " << *I);
375       return false;
376     }
377 
378     // Update live regunits.
379     for (const MachineOperand &MO : I->operands()) {
380       // We're ignoring regmask operands. That is conservatively correct.
381       if (!MO.isReg())
382         continue;
383       Register Reg = MO.getReg();
384       if (!Register::isPhysicalRegister(Reg))
385         continue;
386       // I clobbers Reg, so it isn't live before I.
387       if (MO.isDef())
388         for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units)
389           LiveRegUnits.erase(*Units);
390       // Unless I reads Reg.
391       if (MO.readsReg())
392         Reads.push_back(Reg);
393     }
394     // Anything read by I is live before I.
395     while (!Reads.empty())
396       for (MCRegUnitIterator Units(Reads.pop_back_val(), TRI); Units.isValid();
397            ++Units)
398         if (ClobberedRegUnits.test(*Units))
399           LiveRegUnits.insert(*Units);
400 
401     // We can't insert before a terminator.
402     if (I != FirstTerm && I->isTerminator())
403       continue;
404 
405     // Some of the clobbered registers are live before I, not a valid insertion
406     // point.
407     if (!LiveRegUnits.empty()) {
408       LLVM_DEBUG({
409         dbgs() << "Would clobber";
410         for (SparseSet<unsigned>::const_iterator
411              i = LiveRegUnits.begin(), e = LiveRegUnits.end(); i != e; ++i)
412           dbgs() << ' ' << printRegUnit(*i, TRI);
413         dbgs() << " live before " << *I;
414       });
415       continue;
416     }
417 
418     // This is a valid insertion point.
419     InsertionPoint = I;
420     LLVM_DEBUG(dbgs() << "Can insert before " << *I);
421     return true;
422   }
423   LLVM_DEBUG(dbgs() << "No legal insertion point found.\n");
424   return false;
425 }
426 
427 
428 
429 /// canConvertIf - analyze the sub-cfg rooted in MBB, and return true if it is
430 /// a potential candidate for if-conversion. Fill out the internal state.
431 ///
432 bool SSAIfConv::canConvertIf(MachineBasicBlock *MBB, bool Predicate) {
433   Head = MBB;
434   TBB = FBB = Tail = nullptr;
435 
436   if (Head->succ_size() != 2)
437     return false;
438   MachineBasicBlock *Succ0 = Head->succ_begin()[0];
439   MachineBasicBlock *Succ1 = Head->succ_begin()[1];
440 
441   // Canonicalize so Succ0 has MBB as its single predecessor.
442   if (Succ0->pred_size() != 1)
443     std::swap(Succ0, Succ1);
444 
445   if (Succ0->pred_size() != 1 || Succ0->succ_size() != 1)
446     return false;
447 
448   Tail = Succ0->succ_begin()[0];
449 
450   // This is not a triangle.
451   if (Tail != Succ1) {
452     // Check for a diamond. We won't deal with any critical edges.
453     if (Succ1->pred_size() != 1 || Succ1->succ_size() != 1 ||
454         Succ1->succ_begin()[0] != Tail)
455       return false;
456     LLVM_DEBUG(dbgs() << "\nDiamond: " << printMBBReference(*Head) << " -> "
457                       << printMBBReference(*Succ0) << "/"
458                       << printMBBReference(*Succ1) << " -> "
459                       << printMBBReference(*Tail) << '\n');
460 
461     // Live-in physregs are tricky to get right when speculating code.
462     if (!Tail->livein_empty()) {
463       LLVM_DEBUG(dbgs() << "Tail has live-ins.\n");
464       return false;
465     }
466   } else {
467     LLVM_DEBUG(dbgs() << "\nTriangle: " << printMBBReference(*Head) << " -> "
468                       << printMBBReference(*Succ0) << " -> "
469                       << printMBBReference(*Tail) << '\n');
470   }
471 
472   // This is a triangle or a diamond.
473   // Skip if we cannot predicate and there are no phis skip as there must be
474   // side effects that can only be handled with predication.
475   if (!Predicate && (Tail->empty() || !Tail->front().isPHI())) {
476     LLVM_DEBUG(dbgs() << "No phis in tail.\n");
477     return false;
478   }
479 
480   // The branch we're looking to eliminate must be analyzable.
481   Cond.clear();
482   if (TII->analyzeBranch(*Head, TBB, FBB, Cond)) {
483     LLVM_DEBUG(dbgs() << "Branch not analyzable.\n");
484     return false;
485   }
486 
487   // This is weird, probably some sort of degenerate CFG.
488   if (!TBB) {
489     LLVM_DEBUG(dbgs() << "analyzeBranch didn't find conditional branch.\n");
490     return false;
491   }
492 
493   // Make sure the analyzed branch is conditional; one of the successors
494   // could be a landing pad. (Empty landing pads can be generated on Windows.)
495   if (Cond.empty()) {
496     LLVM_DEBUG(dbgs() << "analyzeBranch found an unconditional branch.\n");
497     return false;
498   }
499 
500   // analyzeBranch doesn't set FBB on a fall-through branch.
501   // Make sure it is always set.
502   FBB = TBB == Succ0 ? Succ1 : Succ0;
503 
504   // Any phis in the tail block must be convertible to selects.
505   PHIs.clear();
506   MachineBasicBlock *TPred = getTPred();
507   MachineBasicBlock *FPred = getFPred();
508   for (MachineBasicBlock::iterator I = Tail->begin(), E = Tail->end();
509        I != E && I->isPHI(); ++I) {
510     PHIs.push_back(&*I);
511     PHIInfo &PI = PHIs.back();
512     // Find PHI operands corresponding to TPred and FPred.
513     for (unsigned i = 1; i != PI.PHI->getNumOperands(); i += 2) {
514       if (PI.PHI->getOperand(i+1).getMBB() == TPred)
515         PI.TReg = PI.PHI->getOperand(i).getReg();
516       if (PI.PHI->getOperand(i+1).getMBB() == FPred)
517         PI.FReg = PI.PHI->getOperand(i).getReg();
518     }
519     assert(Register::isVirtualRegister(PI.TReg) && "Bad PHI");
520     assert(Register::isVirtualRegister(PI.FReg) && "Bad PHI");
521 
522     // Get target information.
523     if (!TII->canInsertSelect(*Head, Cond, PI.PHI->getOperand(0).getReg(),
524                               PI.TReg, PI.FReg, PI.CondCycles, PI.TCycles,
525                               PI.FCycles)) {
526       LLVM_DEBUG(dbgs() << "Can't convert: " << *PI.PHI);
527       return false;
528     }
529   }
530 
531   // Check that the conditional instructions can be speculated.
532   InsertAfter.clear();
533   ClobberedRegUnits.reset();
534   if (Predicate) {
535     if (TBB != Tail && !canPredicateInstrs(TBB))
536       return false;
537     if (FBB != Tail && !canPredicateInstrs(FBB))
538       return false;
539   } else {
540     if (TBB != Tail && !canSpeculateInstrs(TBB))
541       return false;
542     if (FBB != Tail && !canSpeculateInstrs(FBB))
543       return false;
544   }
545 
546   // Try to find a valid insertion point for the speculated instructions in the
547   // head basic block.
548   if (!findInsertionPoint())
549     return false;
550 
551   if (isTriangle())
552     ++NumTrianglesSeen;
553   else
554     ++NumDiamondsSeen;
555   return true;
556 }
557 
558 /// replacePHIInstrs - Completely replace PHI instructions with selects.
559 /// This is possible when the only Tail predecessors are the if-converted
560 /// blocks.
561 void SSAIfConv::replacePHIInstrs() {
562   assert(Tail->pred_size() == 2 && "Cannot replace PHIs");
563   MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator();
564   assert(FirstTerm != Head->end() && "No terminators");
565   DebugLoc HeadDL = FirstTerm->getDebugLoc();
566 
567   // Convert all PHIs to select instructions inserted before FirstTerm.
568   for (unsigned i = 0, e = PHIs.size(); i != e; ++i) {
569     PHIInfo &PI = PHIs[i];
570     LLVM_DEBUG(dbgs() << "If-converting " << *PI.PHI);
571     Register DstReg = PI.PHI->getOperand(0).getReg();
572     TII->insertSelect(*Head, FirstTerm, HeadDL, DstReg, Cond, PI.TReg, PI.FReg);
573     LLVM_DEBUG(dbgs() << "          --> " << *std::prev(FirstTerm));
574     PI.PHI->eraseFromParent();
575     PI.PHI = nullptr;
576   }
577 }
578 
579 /// rewritePHIOperands - When there are additional Tail predecessors, insert
580 /// select instructions in Head and rewrite PHI operands to use the selects.
581 /// Keep the PHI instructions in Tail to handle the other predecessors.
582 void SSAIfConv::rewritePHIOperands() {
583   MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator();
584   assert(FirstTerm != Head->end() && "No terminators");
585   DebugLoc HeadDL = FirstTerm->getDebugLoc();
586 
587   // Convert all PHIs to select instructions inserted before FirstTerm.
588   for (unsigned i = 0, e = PHIs.size(); i != e; ++i) {
589     PHIInfo &PI = PHIs[i];
590     unsigned DstReg = 0;
591 
592     LLVM_DEBUG(dbgs() << "If-converting " << *PI.PHI);
593     if (PI.TReg == PI.FReg) {
594       // We do not need the select instruction if both incoming values are
595       // equal.
596       DstReg = PI.TReg;
597     } else {
598       Register PHIDst = PI.PHI->getOperand(0).getReg();
599       DstReg = MRI->createVirtualRegister(MRI->getRegClass(PHIDst));
600       TII->insertSelect(*Head, FirstTerm, HeadDL,
601                          DstReg, Cond, PI.TReg, PI.FReg);
602       LLVM_DEBUG(dbgs() << "          --> " << *std::prev(FirstTerm));
603     }
604 
605     // Rewrite PHI operands TPred -> (DstReg, Head), remove FPred.
606     for (unsigned i = PI.PHI->getNumOperands(); i != 1; i -= 2) {
607       MachineBasicBlock *MBB = PI.PHI->getOperand(i-1).getMBB();
608       if (MBB == getTPred()) {
609         PI.PHI->getOperand(i-1).setMBB(Head);
610         PI.PHI->getOperand(i-2).setReg(DstReg);
611       } else if (MBB == getFPred()) {
612         PI.PHI->RemoveOperand(i-1);
613         PI.PHI->RemoveOperand(i-2);
614       }
615     }
616     LLVM_DEBUG(dbgs() << "          --> " << *PI.PHI);
617   }
618 }
619 
620 /// convertIf - Execute the if conversion after canConvertIf has determined the
621 /// feasibility.
622 ///
623 /// Any basic blocks erased will be added to RemovedBlocks.
624 ///
625 void SSAIfConv::convertIf(SmallVectorImpl<MachineBasicBlock *> &RemovedBlocks,
626                           bool Predicate) {
627   assert(Head && Tail && TBB && FBB && "Call canConvertIf first.");
628 
629   // Update statistics.
630   if (isTriangle())
631     ++NumTrianglesConv;
632   else
633     ++NumDiamondsConv;
634 
635   // Move all instructions into Head, except for the terminators.
636   if (TBB != Tail) {
637     if (Predicate)
638       PredicateBlock(TBB, /*ReversePredicate=*/false);
639     Head->splice(InsertionPoint, TBB, TBB->begin(), TBB->getFirstTerminator());
640   }
641   if (FBB != Tail) {
642     if (Predicate)
643       PredicateBlock(FBB, /*ReversePredicate=*/true);
644     Head->splice(InsertionPoint, FBB, FBB->begin(), FBB->getFirstTerminator());
645   }
646   // Are there extra Tail predecessors?
647   bool ExtraPreds = Tail->pred_size() != 2;
648   if (ExtraPreds)
649     rewritePHIOperands();
650   else
651     replacePHIInstrs();
652 
653   // Fix up the CFG, temporarily leave Head without any successors.
654   Head->removeSuccessor(TBB);
655   Head->removeSuccessor(FBB, true);
656   if (TBB != Tail)
657     TBB->removeSuccessor(Tail, true);
658   if (FBB != Tail)
659     FBB->removeSuccessor(Tail, true);
660 
661   // Fix up Head's terminators.
662   // It should become a single branch or a fallthrough.
663   DebugLoc HeadDL = Head->getFirstTerminator()->getDebugLoc();
664   TII->removeBranch(*Head);
665 
666   // Erase the now empty conditional blocks. It is likely that Head can fall
667   // through to Tail, and we can join the two blocks.
668   if (TBB != Tail) {
669     RemovedBlocks.push_back(TBB);
670     TBB->eraseFromParent();
671   }
672   if (FBB != Tail) {
673     RemovedBlocks.push_back(FBB);
674     FBB->eraseFromParent();
675   }
676 
677   assert(Head->succ_empty() && "Additional head successors?");
678   if (!ExtraPreds && Head->isLayoutSuccessor(Tail)) {
679     // Splice Tail onto the end of Head.
680     LLVM_DEBUG(dbgs() << "Joining tail " << printMBBReference(*Tail)
681                       << " into head " << printMBBReference(*Head) << '\n');
682     Head->splice(Head->end(), Tail,
683                      Tail->begin(), Tail->end());
684     Head->transferSuccessorsAndUpdatePHIs(Tail);
685     RemovedBlocks.push_back(Tail);
686     Tail->eraseFromParent();
687   } else {
688     // We need a branch to Tail, let code placement work it out later.
689     LLVM_DEBUG(dbgs() << "Converting to unconditional branch.\n");
690     SmallVector<MachineOperand, 0> EmptyCond;
691     TII->insertBranch(*Head, Tail, nullptr, EmptyCond, HeadDL);
692     Head->addSuccessor(Tail);
693   }
694   LLVM_DEBUG(dbgs() << *Head);
695 }
696 
697 //===----------------------------------------------------------------------===//
698 //                           EarlyIfConverter Pass
699 //===----------------------------------------------------------------------===//
700 
701 namespace {
702 class EarlyIfConverter : public MachineFunctionPass {
703   const TargetInstrInfo *TII;
704   const TargetRegisterInfo *TRI;
705   MCSchedModel SchedModel;
706   MachineRegisterInfo *MRI;
707   MachineDominatorTree *DomTree;
708   MachineLoopInfo *Loops;
709   MachineTraceMetrics *Traces;
710   MachineTraceMetrics::Ensemble *MinInstr;
711   SSAIfConv IfConv;
712 
713 public:
714   static char ID;
715   EarlyIfConverter() : MachineFunctionPass(ID) {}
716   void getAnalysisUsage(AnalysisUsage &AU) const override;
717   bool runOnMachineFunction(MachineFunction &MF) override;
718   StringRef getPassName() const override { return "Early If-Conversion"; }
719 
720 private:
721   bool tryConvertIf(MachineBasicBlock*);
722   void invalidateTraces();
723   bool shouldConvertIf();
724 };
725 } // end anonymous namespace
726 
727 char EarlyIfConverter::ID = 0;
728 char &llvm::EarlyIfConverterID = EarlyIfConverter::ID;
729 
730 INITIALIZE_PASS_BEGIN(EarlyIfConverter, DEBUG_TYPE,
731                       "Early If Converter", false, false)
732 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
733 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
734 INITIALIZE_PASS_DEPENDENCY(MachineTraceMetrics)
735 INITIALIZE_PASS_END(EarlyIfConverter, DEBUG_TYPE,
736                     "Early If Converter", false, false)
737 
738 void EarlyIfConverter::getAnalysisUsage(AnalysisUsage &AU) const {
739   AU.addRequired<MachineBranchProbabilityInfo>();
740   AU.addRequired<MachineDominatorTree>();
741   AU.addPreserved<MachineDominatorTree>();
742   AU.addRequired<MachineLoopInfo>();
743   AU.addPreserved<MachineLoopInfo>();
744   AU.addRequired<MachineTraceMetrics>();
745   AU.addPreserved<MachineTraceMetrics>();
746   MachineFunctionPass::getAnalysisUsage(AU);
747 }
748 
749 namespace {
750 /// Update the dominator tree after if-conversion erased some blocks.
751 void updateDomTree(MachineDominatorTree *DomTree, const SSAIfConv &IfConv,
752                    ArrayRef<MachineBasicBlock *> Removed) {
753   // convertIf can remove TBB, FBB, and Tail can be merged into Head.
754   // TBB and FBB should not dominate any blocks.
755   // Tail children should be transferred to Head.
756   MachineDomTreeNode *HeadNode = DomTree->getNode(IfConv.Head);
757   for (auto B : Removed) {
758     MachineDomTreeNode *Node = DomTree->getNode(B);
759     assert(Node != HeadNode && "Cannot erase the head node");
760     while (Node->getNumChildren()) {
761       assert(Node->getBlock() == IfConv.Tail && "Unexpected children");
762       DomTree->changeImmediateDominator(Node->back(), HeadNode);
763     }
764     DomTree->eraseNode(B);
765   }
766 }
767 
768 /// Update LoopInfo after if-conversion.
769 void updateLoops(MachineLoopInfo *Loops,
770                  ArrayRef<MachineBasicBlock *> Removed) {
771   if (!Loops)
772     return;
773   // If-conversion doesn't change loop structure, and it doesn't mess with back
774   // edges, so updating LoopInfo is simply removing the dead blocks.
775   for (auto B : Removed)
776     Loops->removeBlock(B);
777 }
778 } // namespace
779 
780 /// Invalidate MachineTraceMetrics before if-conversion.
781 void EarlyIfConverter::invalidateTraces() {
782   Traces->verifyAnalysis();
783   Traces->invalidate(IfConv.Head);
784   Traces->invalidate(IfConv.Tail);
785   Traces->invalidate(IfConv.TBB);
786   Traces->invalidate(IfConv.FBB);
787   Traces->verifyAnalysis();
788 }
789 
790 // Adjust cycles with downward saturation.
791 static unsigned adjCycles(unsigned Cyc, int Delta) {
792   if (Delta < 0 && Cyc + Delta > Cyc)
793     return 0;
794   return Cyc + Delta;
795 }
796 
797 /// Apply cost model and heuristics to the if-conversion in IfConv.
798 /// Return true if the conversion is a good idea.
799 ///
800 bool EarlyIfConverter::shouldConvertIf() {
801   // Stress testing mode disables all cost considerations.
802   if (Stress)
803     return true;
804 
805   if (!MinInstr)
806     MinInstr = Traces->getEnsemble(MachineTraceMetrics::TS_MinInstrCount);
807 
808   MachineTraceMetrics::Trace TBBTrace = MinInstr->getTrace(IfConv.getTPred());
809   MachineTraceMetrics::Trace FBBTrace = MinInstr->getTrace(IfConv.getFPred());
810   LLVM_DEBUG(dbgs() << "TBB: " << TBBTrace << "FBB: " << FBBTrace);
811   unsigned MinCrit = std::min(TBBTrace.getCriticalPath(),
812                               FBBTrace.getCriticalPath());
813 
814   // Set a somewhat arbitrary limit on the critical path extension we accept.
815   unsigned CritLimit = SchedModel.MispredictPenalty/2;
816 
817   // If-conversion only makes sense when there is unexploited ILP. Compute the
818   // maximum-ILP resource length of the trace after if-conversion. Compare it
819   // to the shortest critical path.
820   SmallVector<const MachineBasicBlock*, 1> ExtraBlocks;
821   if (IfConv.TBB != IfConv.Tail)
822     ExtraBlocks.push_back(IfConv.TBB);
823   unsigned ResLength = FBBTrace.getResourceLength(ExtraBlocks);
824   LLVM_DEBUG(dbgs() << "Resource length " << ResLength
825                     << ", minimal critical path " << MinCrit << '\n');
826   if (ResLength > MinCrit + CritLimit) {
827     LLVM_DEBUG(dbgs() << "Not enough available ILP.\n");
828     return false;
829   }
830 
831   // Assume that the depth of the first head terminator will also be the depth
832   // of the select instruction inserted, as determined by the flag dependency.
833   // TBB / FBB data dependencies may delay the select even more.
834   MachineTraceMetrics::Trace HeadTrace = MinInstr->getTrace(IfConv.Head);
835   unsigned BranchDepth =
836       HeadTrace.getInstrCycles(*IfConv.Head->getFirstTerminator()).Depth;
837   LLVM_DEBUG(dbgs() << "Branch depth: " << BranchDepth << '\n');
838 
839   // Look at all the tail phis, and compute the critical path extension caused
840   // by inserting select instructions.
841   MachineTraceMetrics::Trace TailTrace = MinInstr->getTrace(IfConv.Tail);
842   for (unsigned i = 0, e = IfConv.PHIs.size(); i != e; ++i) {
843     SSAIfConv::PHIInfo &PI = IfConv.PHIs[i];
844     unsigned Slack = TailTrace.getInstrSlack(*PI.PHI);
845     unsigned MaxDepth = Slack + TailTrace.getInstrCycles(*PI.PHI).Depth;
846     LLVM_DEBUG(dbgs() << "Slack " << Slack << ":\t" << *PI.PHI);
847 
848     // The condition is pulled into the critical path.
849     unsigned CondDepth = adjCycles(BranchDepth, PI.CondCycles);
850     if (CondDepth > MaxDepth) {
851       unsigned Extra = CondDepth - MaxDepth;
852       LLVM_DEBUG(dbgs() << "Condition adds " << Extra << " cycles.\n");
853       if (Extra > CritLimit) {
854         LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');
855         return false;
856       }
857     }
858 
859     // The TBB value is pulled into the critical path.
860     unsigned TDepth = adjCycles(TBBTrace.getPHIDepth(*PI.PHI), PI.TCycles);
861     if (TDepth > MaxDepth) {
862       unsigned Extra = TDepth - MaxDepth;
863       LLVM_DEBUG(dbgs() << "TBB data adds " << Extra << " cycles.\n");
864       if (Extra > CritLimit) {
865         LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');
866         return false;
867       }
868     }
869 
870     // The FBB value is pulled into the critical path.
871     unsigned FDepth = adjCycles(FBBTrace.getPHIDepth(*PI.PHI), PI.FCycles);
872     if (FDepth > MaxDepth) {
873       unsigned Extra = FDepth - MaxDepth;
874       LLVM_DEBUG(dbgs() << "FBB data adds " << Extra << " cycles.\n");
875       if (Extra > CritLimit) {
876         LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');
877         return false;
878       }
879     }
880   }
881   return true;
882 }
883 
884 /// Attempt repeated if-conversion on MBB, return true if successful.
885 ///
886 bool EarlyIfConverter::tryConvertIf(MachineBasicBlock *MBB) {
887   bool Changed = false;
888   while (IfConv.canConvertIf(MBB) && shouldConvertIf()) {
889     // If-convert MBB and update analyses.
890     invalidateTraces();
891     SmallVector<MachineBasicBlock*, 4> RemovedBlocks;
892     IfConv.convertIf(RemovedBlocks);
893     Changed = true;
894     updateDomTree(DomTree, IfConv, RemovedBlocks);
895     updateLoops(Loops, RemovedBlocks);
896   }
897   return Changed;
898 }
899 
900 bool EarlyIfConverter::runOnMachineFunction(MachineFunction &MF) {
901   LLVM_DEBUG(dbgs() << "********** EARLY IF-CONVERSION **********\n"
902                     << "********** Function: " << MF.getName() << '\n');
903   if (skipFunction(MF.getFunction()))
904     return false;
905 
906   // Only run if conversion if the target wants it.
907   const TargetSubtargetInfo &STI = MF.getSubtarget();
908   if (!STI.enableEarlyIfConversion())
909     return false;
910 
911   TII = STI.getInstrInfo();
912   TRI = STI.getRegisterInfo();
913   SchedModel = STI.getSchedModel();
914   MRI = &MF.getRegInfo();
915   DomTree = &getAnalysis<MachineDominatorTree>();
916   Loops = getAnalysisIfAvailable<MachineLoopInfo>();
917   Traces = &getAnalysis<MachineTraceMetrics>();
918   MinInstr = nullptr;
919 
920   bool Changed = false;
921   IfConv.runOnMachineFunction(MF);
922 
923   // Visit blocks in dominator tree post-order. The post-order enables nested
924   // if-conversion in a single pass. The tryConvertIf() function may erase
925   // blocks, but only blocks dominated by the head block. This makes it safe to
926   // update the dominator tree while the post-order iterator is still active.
927   for (auto DomNode : post_order(DomTree))
928     if (tryConvertIf(DomNode->getBlock()))
929       Changed = true;
930 
931   return Changed;
932 }
933 
934 //===----------------------------------------------------------------------===//
935 //                           EarlyIfPredicator Pass
936 //===----------------------------------------------------------------------===//
937 
938 namespace {
939 class EarlyIfPredicator : public MachineFunctionPass {
940   const TargetInstrInfo *TII;
941   const TargetRegisterInfo *TRI;
942   TargetSchedModel SchedModel;
943   MachineRegisterInfo *MRI;
944   MachineDominatorTree *DomTree;
945   MachineBranchProbabilityInfo *MBPI;
946   MachineLoopInfo *Loops;
947   SSAIfConv IfConv;
948 
949 public:
950   static char ID;
951   EarlyIfPredicator() : MachineFunctionPass(ID) {}
952   void getAnalysisUsage(AnalysisUsage &AU) const override;
953   bool runOnMachineFunction(MachineFunction &MF) override;
954   StringRef getPassName() const override { return "Early If-predicator"; }
955 
956 protected:
957   bool tryConvertIf(MachineBasicBlock *);
958   bool shouldConvertIf();
959 };
960 } // end anonymous namespace
961 
962 #undef DEBUG_TYPE
963 #define DEBUG_TYPE "early-if-predicator"
964 
965 char EarlyIfPredicator::ID = 0;
966 char &llvm::EarlyIfPredicatorID = EarlyIfPredicator::ID;
967 
968 INITIALIZE_PASS_BEGIN(EarlyIfPredicator, DEBUG_TYPE, "Early If Predicator",
969                       false, false)
970 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
971 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
972 INITIALIZE_PASS_END(EarlyIfPredicator, DEBUG_TYPE, "Early If Predicator", false,
973                     false)
974 
975 void EarlyIfPredicator::getAnalysisUsage(AnalysisUsage &AU) const {
976   AU.addRequired<MachineBranchProbabilityInfo>();
977   AU.addRequired<MachineDominatorTree>();
978   AU.addPreserved<MachineDominatorTree>();
979   AU.addRequired<MachineLoopInfo>();
980   AU.addPreserved<MachineLoopInfo>();
981   MachineFunctionPass::getAnalysisUsage(AU);
982 }
983 
984 /// Apply the target heuristic to decide if the transformation is profitable.
985 bool EarlyIfPredicator::shouldConvertIf() {
986   auto TrueProbability = MBPI->getEdgeProbability(IfConv.Head, IfConv.TBB);
987   if (IfConv.isTriangle()) {
988     MachineBasicBlock &IfBlock =
989         (IfConv.TBB == IfConv.Tail) ? *IfConv.FBB : *IfConv.TBB;
990 
991     unsigned ExtraPredCost = 0;
992     unsigned Cycles = 0;
993     for (MachineInstr &I : IfBlock) {
994       unsigned NumCycles = SchedModel.computeInstrLatency(&I, false);
995       if (NumCycles > 1)
996         Cycles += NumCycles - 1;
997       ExtraPredCost += TII->getPredicationCost(I);
998     }
999 
1000     return TII->isProfitableToIfCvt(IfBlock, Cycles, ExtraPredCost,
1001                                     TrueProbability);
1002   }
1003   unsigned TExtra = 0;
1004   unsigned FExtra = 0;
1005   unsigned TCycle = 0;
1006   unsigned FCycle = 0;
1007   for (MachineInstr &I : *IfConv.TBB) {
1008     unsigned NumCycles = SchedModel.computeInstrLatency(&I, false);
1009     if (NumCycles > 1)
1010       TCycle += NumCycles - 1;
1011     TExtra += TII->getPredicationCost(I);
1012   }
1013   for (MachineInstr &I : *IfConv.FBB) {
1014     unsigned NumCycles = SchedModel.computeInstrLatency(&I, false);
1015     if (NumCycles > 1)
1016       FCycle += NumCycles - 1;
1017     FExtra += TII->getPredicationCost(I);
1018   }
1019   return TII->isProfitableToIfCvt(*IfConv.TBB, TCycle, TExtra, *IfConv.FBB,
1020                                   FCycle, FExtra, TrueProbability);
1021 }
1022 
1023 /// Attempt repeated if-conversion on MBB, return true if successful.
1024 ///
1025 bool EarlyIfPredicator::tryConvertIf(MachineBasicBlock *MBB) {
1026   bool Changed = false;
1027   while (IfConv.canConvertIf(MBB, /*Predicate*/ true) && shouldConvertIf()) {
1028     // If-convert MBB and update analyses.
1029     SmallVector<MachineBasicBlock *, 4> RemovedBlocks;
1030     IfConv.convertIf(RemovedBlocks, /*Predicate*/ true);
1031     Changed = true;
1032     updateDomTree(DomTree, IfConv, RemovedBlocks);
1033     updateLoops(Loops, RemovedBlocks);
1034   }
1035   return Changed;
1036 }
1037 
1038 bool EarlyIfPredicator::runOnMachineFunction(MachineFunction &MF) {
1039   LLVM_DEBUG(dbgs() << "********** EARLY IF-PREDICATOR **********\n"
1040                     << "********** Function: " << MF.getName() << '\n');
1041   if (skipFunction(MF.getFunction()))
1042     return false;
1043 
1044   const TargetSubtargetInfo &STI = MF.getSubtarget();
1045   TII = STI.getInstrInfo();
1046   TRI = STI.getRegisterInfo();
1047   MRI = &MF.getRegInfo();
1048   SchedModel.init(&STI);
1049   DomTree = &getAnalysis<MachineDominatorTree>();
1050   Loops = getAnalysisIfAvailable<MachineLoopInfo>();
1051   MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
1052 
1053   bool Changed = false;
1054   IfConv.runOnMachineFunction(MF);
1055 
1056   // Visit blocks in dominator tree post-order. The post-order enables nested
1057   // if-conversion in a single pass. The tryConvertIf() function may erase
1058   // blocks, but only blocks dominated by the head block. This makes it safe to
1059   // update the dominator tree while the post-order iterator is still active.
1060   for (auto DomNode : post_order(DomTree))
1061     if (tryConvertIf(DomNode->getBlock()))
1062       Changed = true;
1063 
1064   return Changed;
1065 }
1066