1//===-- EarlyIfConversion.cpp - If-conversion on SSA form machine code ----===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// Early if-conversion is for out-of-order CPUs that don't have a lot of
11// predicable instructions. The goal is to eliminate conditional branches that
12// may mispredict.
13//
14// Instructions from both sides of the branch are executed specutatively, and a
15// cmov instruction selects the result.
16//
17//===----------------------------------------------------------------------===//
18
19#include "llvm/ADT/BitVector.h"
20#include "llvm/ADT/PostOrderIterator.h"
21#include "llvm/ADT/SetVector.h"
22#include "llvm/ADT/SmallPtrSet.h"
23#include "llvm/ADT/SparseSet.h"
24#include "llvm/ADT/Statistic.h"
25#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
26#include "llvm/CodeGen/MachineDominators.h"
27#include "llvm/CodeGen/MachineFunction.h"
28#include "llvm/CodeGen/MachineFunctionPass.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/Support/CommandLine.h"
34#include "llvm/Support/Debug.h"
35#include "llvm/Support/raw_ostream.h"
36#include "llvm/Target/TargetInstrInfo.h"
37#include "llvm/Target/TargetRegisterInfo.h"
38#include "llvm/Target/TargetSubtargetInfo.h"
39
40using namespace llvm;
41
42#define DEBUG_TYPE "early-ifcvt"
43
44// Absolute maximum number of instructions allowed per speculated block.
45// This bypasses all other heuristics, so it should be set fairly high.
46static cl::opt<unsigned>
47BlockInstrLimit("early-ifcvt-limit", cl::init(30), cl::Hidden,
48  cl::desc("Maximum number of instructions per speculated block."));
49
50// Stress testing mode - disable heuristics.
51static cl::opt<bool> Stress("stress-early-ifcvt", cl::Hidden,
52  cl::desc("Turn all knobs to 11"));
53
54STATISTIC(NumDiamondsSeen,  "Number of diamonds");
55STATISTIC(NumDiamondsConv,  "Number of diamonds converted");
56STATISTIC(NumTrianglesSeen, "Number of triangles");
57STATISTIC(NumTrianglesConv, "Number of triangles converted");
58
59//===----------------------------------------------------------------------===//
60//                                 SSAIfConv
61//===----------------------------------------------------------------------===//
62//
63// The SSAIfConv class performs if-conversion on SSA form machine code after
64// determining if it is possible. The class contains no heuristics; external
65// code should be used to determine when if-conversion is a good idea.
66//
67// SSAIfConv can convert both triangles and diamonds:
68//
69//   Triangle: Head              Diamond: Head
70//              | \                       /  \_
71//              |  \                     /    |
72//              |  [TF]BB              FBB    TBB
73//              |  /                     \    /
74//              | /                       \  /
75//             Tail                       Tail
76//
77// Instructions in the conditional blocks TBB and/or FBB are spliced into the
78// Head block, and phis in the Tail block are converted to select instructions.
79//
80namespace {
81class SSAIfConv {
82  const TargetInstrInfo *TII;
83  const TargetRegisterInfo *TRI;
84  MachineRegisterInfo *MRI;
85
86public:
87  /// The block containing the conditional branch.
88  MachineBasicBlock *Head;
89
90  /// The block containing phis after the if-then-else.
91  MachineBasicBlock *Tail;
92
93  /// The 'true' conditional block as determined by AnalyzeBranch.
94  MachineBasicBlock *TBB;
95
96  /// The 'false' conditional block as determined by AnalyzeBranch.
97  MachineBasicBlock *FBB;
98
99  /// isTriangle - When there is no 'else' block, either TBB or FBB will be
100  /// equal to Tail.
101  bool isTriangle() const { return TBB == Tail || FBB == Tail; }
102
103  /// Returns the Tail predecessor for the True side.
104  MachineBasicBlock *getTPred() const { return TBB == Tail ? Head : TBB; }
105
106  /// Returns the Tail predecessor for the  False side.
107  MachineBasicBlock *getFPred() const { return FBB == Tail ? Head : FBB; }
108
109  /// Information about each phi in the Tail block.
110  struct PHIInfo {
111    MachineInstr *PHI;
112    unsigned TReg, FReg;
113    // Latencies from Cond+Branch, TReg, and FReg to DstReg.
114    int CondCycles, TCycles, FCycles;
115
116    PHIInfo(MachineInstr *phi)
117      : PHI(phi), TReg(0), FReg(0), CondCycles(0), TCycles(0), FCycles(0) {}
118  };
119
120  SmallVector<PHIInfo, 8> PHIs;
121
122private:
123  /// The branch condition determined by AnalyzeBranch.
124  SmallVector<MachineOperand, 4> Cond;
125
126  /// Instructions in Head that define values used by the conditional blocks.
127  /// The hoisted instructions must be inserted after these instructions.
128  SmallPtrSet<MachineInstr*, 8> InsertAfter;
129
130  /// Register units clobbered by the conditional blocks.
131  BitVector ClobberedRegUnits;
132
133  // Scratch pad for findInsertionPoint.
134  SparseSet<unsigned> LiveRegUnits;
135
136  /// Insertion point in Head for speculatively executed instructions form TBB
137  /// and FBB.
138  MachineBasicBlock::iterator InsertionPoint;
139
140  /// Return true if all non-terminator instructions in MBB can be safely
141  /// speculated.
142  bool canSpeculateInstrs(MachineBasicBlock *MBB);
143
144  /// Find a valid insertion point in Head.
145  bool findInsertionPoint();
146
147  /// Replace PHI instructions in Tail with selects.
148  void replacePHIInstrs();
149
150  /// Insert selects and rewrite PHI operands to use them.
151  void rewritePHIOperands();
152
153public:
154  /// runOnMachineFunction - Initialize per-function data structures.
155  void runOnMachineFunction(MachineFunction &MF) {
156    TII = MF.getSubtarget().getInstrInfo();
157    TRI = MF.getSubtarget().getRegisterInfo();
158    MRI = &MF.getRegInfo();
159    LiveRegUnits.clear();
160    LiveRegUnits.setUniverse(TRI->getNumRegUnits());
161    ClobberedRegUnits.clear();
162    ClobberedRegUnits.resize(TRI->getNumRegUnits());
163  }
164
165  /// canConvertIf - If the sub-CFG headed by MBB can be if-converted,
166  /// initialize the internal state, and return true.
167  bool canConvertIf(MachineBasicBlock *MBB);
168
169  /// convertIf - If-convert the last block passed to canConvertIf(), assuming
170  /// it is possible. Add any erased blocks to RemovedBlocks.
171  void convertIf(SmallVectorImpl<MachineBasicBlock*> &RemovedBlocks);
172};
173} // end anonymous namespace
174
175
176/// canSpeculateInstrs - Returns true if all the instructions in MBB can safely
177/// be speculated. The terminators are not considered.
178///
179/// If instructions use any values that are defined in the head basic block,
180/// the defining instructions are added to InsertAfter.
181///
182/// Any clobbered regunits are added to ClobberedRegUnits.
183///
184bool SSAIfConv::canSpeculateInstrs(MachineBasicBlock *MBB) {
185  // Reject any live-in physregs. It's probably CPSR/EFLAGS, and very hard to
186  // get right.
187  if (!MBB->livein_empty()) {
188    DEBUG(dbgs() << "BB#" << MBB->getNumber() << " has live-ins.\n");
189    return false;
190  }
191
192  unsigned InstrCount = 0;
193
194  // Check all instructions, except the terminators. It is assumed that
195  // terminators never have side effects or define any used register values.
196  for (MachineBasicBlock::iterator I = MBB->begin(),
197       E = MBB->getFirstTerminator(); I != E; ++I) {
198    if (I->isDebugValue())
199      continue;
200
201    if (++InstrCount > BlockInstrLimit && !Stress) {
202      DEBUG(dbgs() << "BB#" << MBB->getNumber() << " has more than "
203                   << BlockInstrLimit << " instructions.\n");
204      return false;
205    }
206
207    // There shouldn't normally be any phis in a single-predecessor block.
208    if (I->isPHI()) {
209      DEBUG(dbgs() << "Can't hoist: " << *I);
210      return false;
211    }
212
213    // Don't speculate loads. Note that it may be possible and desirable to
214    // speculate GOT or constant pool loads that are guaranteed not to trap,
215    // but we don't support that for now.
216    if (I->mayLoad()) {
217      DEBUG(dbgs() << "Won't speculate load: " << *I);
218      return false;
219    }
220
221    // We never speculate stores, so an AA pointer isn't necessary.
222    bool DontMoveAcrossStore = true;
223    if (!I->isSafeToMove(TII, nullptr, DontMoveAcrossStore)) {
224      DEBUG(dbgs() << "Can't speculate: " << *I);
225      return false;
226    }
227
228    // Check for any dependencies on Head instructions.
229    for (MIOperands MO(I); MO.isValid(); ++MO) {
230      if (MO->isRegMask()) {
231        DEBUG(dbgs() << "Won't speculate regmask: " << *I);
232        return false;
233      }
234      if (!MO->isReg())
235        continue;
236      unsigned Reg = MO->getReg();
237
238      // Remember clobbered regunits.
239      if (MO->isDef() && TargetRegisterInfo::isPhysicalRegister(Reg))
240        for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units)
241          ClobberedRegUnits.set(*Units);
242
243      if (!MO->readsReg() || !TargetRegisterInfo::isVirtualRegister(Reg))
244        continue;
245      MachineInstr *DefMI = MRI->getVRegDef(Reg);
246      if (!DefMI || DefMI->getParent() != Head)
247        continue;
248      if (InsertAfter.insert(DefMI).second)
249        DEBUG(dbgs() << "BB#" << MBB->getNumber() << " depends on " << *DefMI);
250      if (DefMI->isTerminator()) {
251        DEBUG(dbgs() << "Can't insert instructions below terminator.\n");
252        return false;
253      }
254    }
255  }
256  return true;
257}
258
259
260/// Find an insertion point in Head for the speculated instructions. The
261/// insertion point must be:
262///
263/// 1. Before any terminators.
264/// 2. After any instructions in InsertAfter.
265/// 3. Not have any clobbered regunits live.
266///
267/// This function sets InsertionPoint and returns true when successful, it
268/// returns false if no valid insertion point could be found.
269///
270bool SSAIfConv::findInsertionPoint() {
271  // Keep track of live regunits before the current position.
272  // Only track RegUnits that are also in ClobberedRegUnits.
273  LiveRegUnits.clear();
274  SmallVector<unsigned, 8> Reads;
275  MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator();
276  MachineBasicBlock::iterator I = Head->end();
277  MachineBasicBlock::iterator B = Head->begin();
278  while (I != B) {
279    --I;
280    // Some of the conditional code depends in I.
281    if (InsertAfter.count(I)) {
282      DEBUG(dbgs() << "Can't insert code after " << *I);
283      return false;
284    }
285
286    // Update live regunits.
287    for (MIOperands MO(I); MO.isValid(); ++MO) {
288      // We're ignoring regmask operands. That is conservatively correct.
289      if (!MO->isReg())
290        continue;
291      unsigned Reg = MO->getReg();
292      if (!TargetRegisterInfo::isPhysicalRegister(Reg))
293        continue;
294      // I clobbers Reg, so it isn't live before I.
295      if (MO->isDef())
296        for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units)
297          LiveRegUnits.erase(*Units);
298      // Unless I reads Reg.
299      if (MO->readsReg())
300        Reads.push_back(Reg);
301    }
302    // Anything read by I is live before I.
303    while (!Reads.empty())
304      for (MCRegUnitIterator Units(Reads.pop_back_val(), TRI); Units.isValid();
305           ++Units)
306        if (ClobberedRegUnits.test(*Units))
307          LiveRegUnits.insert(*Units);
308
309    // We can't insert before a terminator.
310    if (I != FirstTerm && I->isTerminator())
311      continue;
312
313    // Some of the clobbered registers are live before I, not a valid insertion
314    // point.
315    if (!LiveRegUnits.empty()) {
316      DEBUG({
317        dbgs() << "Would clobber";
318        for (SparseSet<unsigned>::const_iterator
319             i = LiveRegUnits.begin(), e = LiveRegUnits.end(); i != e; ++i)
320          dbgs() << ' ' << PrintRegUnit(*i, TRI);
321        dbgs() << " live before " << *I;
322      });
323      continue;
324    }
325
326    // This is a valid insertion point.
327    InsertionPoint = I;
328    DEBUG(dbgs() << "Can insert before " << *I);
329    return true;
330  }
331  DEBUG(dbgs() << "No legal insertion point found.\n");
332  return false;
333}
334
335
336
337/// canConvertIf - analyze the sub-cfg rooted in MBB, and return true if it is
338/// a potential candidate for if-conversion. Fill out the internal state.
339///
340bool SSAIfConv::canConvertIf(MachineBasicBlock *MBB) {
341  Head = MBB;
342  TBB = FBB = Tail = nullptr;
343
344  if (Head->succ_size() != 2)
345    return false;
346  MachineBasicBlock *Succ0 = Head->succ_begin()[0];
347  MachineBasicBlock *Succ1 = Head->succ_begin()[1];
348
349  // Canonicalize so Succ0 has MBB as its single predecessor.
350  if (Succ0->pred_size() != 1)
351    std::swap(Succ0, Succ1);
352
353  if (Succ0->pred_size() != 1 || Succ0->succ_size() != 1)
354    return false;
355
356  Tail = Succ0->succ_begin()[0];
357
358  // This is not a triangle.
359  if (Tail != Succ1) {
360    // Check for a diamond. We won't deal with any critical edges.
361    if (Succ1->pred_size() != 1 || Succ1->succ_size() != 1 ||
362        Succ1->succ_begin()[0] != Tail)
363      return false;
364    DEBUG(dbgs() << "\nDiamond: BB#" << Head->getNumber()
365                 << " -> BB#" << Succ0->getNumber()
366                 << "/BB#" << Succ1->getNumber()
367                 << " -> BB#" << Tail->getNumber() << '\n');
368
369    // Live-in physregs are tricky to get right when speculating code.
370    if (!Tail->livein_empty()) {
371      DEBUG(dbgs() << "Tail has live-ins.\n");
372      return false;
373    }
374  } else {
375    DEBUG(dbgs() << "\nTriangle: BB#" << Head->getNumber()
376                 << " -> BB#" << Succ0->getNumber()
377                 << " -> BB#" << Tail->getNumber() << '\n');
378  }
379
380  // This is a triangle or a diamond.
381  // If Tail doesn't have any phis, there must be side effects.
382  if (Tail->empty() || !Tail->front().isPHI()) {
383    DEBUG(dbgs() << "No phis in tail.\n");
384    return false;
385  }
386
387  // The branch we're looking to eliminate must be analyzable.
388  Cond.clear();
389  if (TII->AnalyzeBranch(*Head, TBB, FBB, Cond)) {
390    DEBUG(dbgs() << "Branch not analyzable.\n");
391    return false;
392  }
393
394  // This is weird, probably some sort of degenerate CFG.
395  if (!TBB) {
396    DEBUG(dbgs() << "AnalyzeBranch didn't find conditional branch.\n");
397    return false;
398  }
399
400  // AnalyzeBranch doesn't set FBB on a fall-through branch.
401  // Make sure it is always set.
402  FBB = TBB == Succ0 ? Succ1 : Succ0;
403
404  // Any phis in the tail block must be convertible to selects.
405  PHIs.clear();
406  MachineBasicBlock *TPred = getTPred();
407  MachineBasicBlock *FPred = getFPred();
408  for (MachineBasicBlock::iterator I = Tail->begin(), E = Tail->end();
409       I != E && I->isPHI(); ++I) {
410    PHIs.push_back(&*I);
411    PHIInfo &PI = PHIs.back();
412    // Find PHI operands corresponding to TPred and FPred.
413    for (unsigned i = 1; i != PI.PHI->getNumOperands(); i += 2) {
414      if (PI.PHI->getOperand(i+1).getMBB() == TPred)
415        PI.TReg = PI.PHI->getOperand(i).getReg();
416      if (PI.PHI->getOperand(i+1).getMBB() == FPred)
417        PI.FReg = PI.PHI->getOperand(i).getReg();
418    }
419    assert(TargetRegisterInfo::isVirtualRegister(PI.TReg) && "Bad PHI");
420    assert(TargetRegisterInfo::isVirtualRegister(PI.FReg) && "Bad PHI");
421
422    // Get target information.
423    if (!TII->canInsertSelect(*Head, Cond, PI.TReg, PI.FReg,
424                              PI.CondCycles, PI.TCycles, PI.FCycles)) {
425      DEBUG(dbgs() << "Can't convert: " << *PI.PHI);
426      return false;
427    }
428  }
429
430  // Check that the conditional instructions can be speculated.
431  InsertAfter.clear();
432  ClobberedRegUnits.reset();
433  if (TBB != Tail && !canSpeculateInstrs(TBB))
434    return false;
435  if (FBB != Tail && !canSpeculateInstrs(FBB))
436    return false;
437
438  // Try to find a valid insertion point for the speculated instructions in the
439  // head basic block.
440  if (!findInsertionPoint())
441    return false;
442
443  if (isTriangle())
444    ++NumTrianglesSeen;
445  else
446    ++NumDiamondsSeen;
447  return true;
448}
449
450/// replacePHIInstrs - Completely replace PHI instructions with selects.
451/// This is possible when the only Tail predecessors are the if-converted
452/// blocks.
453void SSAIfConv::replacePHIInstrs() {
454  assert(Tail->pred_size() == 2 && "Cannot replace PHIs");
455  MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator();
456  assert(FirstTerm != Head->end() && "No terminators");
457  DebugLoc HeadDL = FirstTerm->getDebugLoc();
458
459  // Convert all PHIs to select instructions inserted before FirstTerm.
460  for (unsigned i = 0, e = PHIs.size(); i != e; ++i) {
461    PHIInfo &PI = PHIs[i];
462    DEBUG(dbgs() << "If-converting " << *PI.PHI);
463    unsigned DstReg = PI.PHI->getOperand(0).getReg();
464    TII->insertSelect(*Head, FirstTerm, HeadDL, DstReg, Cond, PI.TReg, PI.FReg);
465    DEBUG(dbgs() << "          --> " << *std::prev(FirstTerm));
466    PI.PHI->eraseFromParent();
467    PI.PHI = nullptr;
468  }
469}
470
471/// rewritePHIOperands - When there are additional Tail predecessors, insert
472/// select instructions in Head and rewrite PHI operands to use the selects.
473/// Keep the PHI instructions in Tail to handle the other predecessors.
474void SSAIfConv::rewritePHIOperands() {
475  MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator();
476  assert(FirstTerm != Head->end() && "No terminators");
477  DebugLoc HeadDL = FirstTerm->getDebugLoc();
478
479  // Convert all PHIs to select instructions inserted before FirstTerm.
480  for (unsigned i = 0, e = PHIs.size(); i != e; ++i) {
481    PHIInfo &PI = PHIs[i];
482    DEBUG(dbgs() << "If-converting " << *PI.PHI);
483    unsigned PHIDst = PI.PHI->getOperand(0).getReg();
484    unsigned DstReg = MRI->createVirtualRegister(MRI->getRegClass(PHIDst));
485    TII->insertSelect(*Head, FirstTerm, HeadDL, DstReg, Cond, PI.TReg, PI.FReg);
486    DEBUG(dbgs() << "          --> " << *std::prev(FirstTerm));
487
488    // Rewrite PHI operands TPred -> (DstReg, Head), remove FPred.
489    for (unsigned i = PI.PHI->getNumOperands(); i != 1; i -= 2) {
490      MachineBasicBlock *MBB = PI.PHI->getOperand(i-1).getMBB();
491      if (MBB == getTPred()) {
492        PI.PHI->getOperand(i-1).setMBB(Head);
493        PI.PHI->getOperand(i-2).setReg(DstReg);
494      } else if (MBB == getFPred()) {
495        PI.PHI->RemoveOperand(i-1);
496        PI.PHI->RemoveOperand(i-2);
497      }
498    }
499    DEBUG(dbgs() << "          --> " << *PI.PHI);
500  }
501}
502
503/// convertIf - Execute the if conversion after canConvertIf has determined the
504/// feasibility.
505///
506/// Any basic blocks erased will be added to RemovedBlocks.
507///
508void SSAIfConv::convertIf(SmallVectorImpl<MachineBasicBlock*> &RemovedBlocks) {
509  assert(Head && Tail && TBB && FBB && "Call canConvertIf first.");
510
511  // Update statistics.
512  if (isTriangle())
513    ++NumTrianglesConv;
514  else
515    ++NumDiamondsConv;
516
517  // Move all instructions into Head, except for the terminators.
518  if (TBB != Tail)
519    Head->splice(InsertionPoint, TBB, TBB->begin(), TBB->getFirstTerminator());
520  if (FBB != Tail)
521    Head->splice(InsertionPoint, FBB, FBB->begin(), FBB->getFirstTerminator());
522
523  // Are there extra Tail predecessors?
524  bool ExtraPreds = Tail->pred_size() != 2;
525  if (ExtraPreds)
526    rewritePHIOperands();
527  else
528    replacePHIInstrs();
529
530  // Fix up the CFG, temporarily leave Head without any successors.
531  Head->removeSuccessor(TBB);
532  Head->removeSuccessor(FBB);
533  if (TBB != Tail)
534    TBB->removeSuccessor(Tail);
535  if (FBB != Tail)
536    FBB->removeSuccessor(Tail);
537
538  // Fix up Head's terminators.
539  // It should become a single branch or a fallthrough.
540  DebugLoc HeadDL = Head->getFirstTerminator()->getDebugLoc();
541  TII->RemoveBranch(*Head);
542
543  // Erase the now empty conditional blocks. It is likely that Head can fall
544  // through to Tail, and we can join the two blocks.
545  if (TBB != Tail) {
546    RemovedBlocks.push_back(TBB);
547    TBB->eraseFromParent();
548  }
549  if (FBB != Tail) {
550    RemovedBlocks.push_back(FBB);
551    FBB->eraseFromParent();
552  }
553
554  assert(Head->succ_empty() && "Additional head successors?");
555  if (!ExtraPreds && Head->isLayoutSuccessor(Tail)) {
556    // Splice Tail onto the end of Head.
557    DEBUG(dbgs() << "Joining tail BB#" << Tail->getNumber()
558                 << " into head BB#" << Head->getNumber() << '\n');
559    Head->splice(Head->end(), Tail,
560                     Tail->begin(), Tail->end());
561    Head->transferSuccessorsAndUpdatePHIs(Tail);
562    RemovedBlocks.push_back(Tail);
563    Tail->eraseFromParent();
564  } else {
565    // We need a branch to Tail, let code placement work it out later.
566    DEBUG(dbgs() << "Converting to unconditional branch.\n");
567    SmallVector<MachineOperand, 0> EmptyCond;
568    TII->InsertBranch(*Head, Tail, nullptr, EmptyCond, HeadDL);
569    Head->addSuccessor(Tail);
570  }
571  DEBUG(dbgs() << *Head);
572}
573
574
575//===----------------------------------------------------------------------===//
576//                           EarlyIfConverter Pass
577//===----------------------------------------------------------------------===//
578
579namespace {
580class EarlyIfConverter : public MachineFunctionPass {
581  const TargetInstrInfo *TII;
582  const TargetRegisterInfo *TRI;
583  MCSchedModel SchedModel;
584  MachineRegisterInfo *MRI;
585  MachineDominatorTree *DomTree;
586  MachineLoopInfo *Loops;
587  MachineTraceMetrics *Traces;
588  MachineTraceMetrics::Ensemble *MinInstr;
589  SSAIfConv IfConv;
590
591public:
592  static char ID;
593  EarlyIfConverter() : MachineFunctionPass(ID) {}
594  void getAnalysisUsage(AnalysisUsage &AU) const override;
595  bool runOnMachineFunction(MachineFunction &MF) override;
596  const char *getPassName() const override { return "Early If-Conversion"; }
597
598private:
599  bool tryConvertIf(MachineBasicBlock*);
600  void updateDomTree(ArrayRef<MachineBasicBlock*> Removed);
601  void updateLoops(ArrayRef<MachineBasicBlock*> Removed);
602  void invalidateTraces();
603  bool shouldConvertIf();
604};
605} // end anonymous namespace
606
607char EarlyIfConverter::ID = 0;
608char &llvm::EarlyIfConverterID = EarlyIfConverter::ID;
609
610INITIALIZE_PASS_BEGIN(EarlyIfConverter,
611                      "early-ifcvt", "Early If Converter", false, false)
612INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
613INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
614INITIALIZE_PASS_DEPENDENCY(MachineTraceMetrics)
615INITIALIZE_PASS_END(EarlyIfConverter,
616                      "early-ifcvt", "Early If Converter", false, false)
617
618void EarlyIfConverter::getAnalysisUsage(AnalysisUsage &AU) const {
619  AU.addRequired<MachineBranchProbabilityInfo>();
620  AU.addRequired<MachineDominatorTree>();
621  AU.addPreserved<MachineDominatorTree>();
622  AU.addRequired<MachineLoopInfo>();
623  AU.addPreserved<MachineLoopInfo>();
624  AU.addRequired<MachineTraceMetrics>();
625  AU.addPreserved<MachineTraceMetrics>();
626  MachineFunctionPass::getAnalysisUsage(AU);
627}
628
629/// Update the dominator tree after if-conversion erased some blocks.
630void EarlyIfConverter::updateDomTree(ArrayRef<MachineBasicBlock*> Removed) {
631  // convertIf can remove TBB, FBB, and Tail can be merged into Head.
632  // TBB and FBB should not dominate any blocks.
633  // Tail children should be transferred to Head.
634  MachineDomTreeNode *HeadNode = DomTree->getNode(IfConv.Head);
635  for (unsigned i = 0, e = Removed.size(); i != e; ++i) {
636    MachineDomTreeNode *Node = DomTree->getNode(Removed[i]);
637    assert(Node != HeadNode && "Cannot erase the head node");
638    while (Node->getNumChildren()) {
639      assert(Node->getBlock() == IfConv.Tail && "Unexpected children");
640      DomTree->changeImmediateDominator(Node->getChildren().back(), HeadNode);
641    }
642    DomTree->eraseNode(Removed[i]);
643  }
644}
645
646/// Update LoopInfo after if-conversion.
647void EarlyIfConverter::updateLoops(ArrayRef<MachineBasicBlock*> Removed) {
648  if (!Loops)
649    return;
650  // If-conversion doesn't change loop structure, and it doesn't mess with back
651  // edges, so updating LoopInfo is simply removing the dead blocks.
652  for (unsigned i = 0, e = Removed.size(); i != e; ++i)
653    Loops->removeBlock(Removed[i]);
654}
655
656/// Invalidate MachineTraceMetrics before if-conversion.
657void EarlyIfConverter::invalidateTraces() {
658  Traces->verifyAnalysis();
659  Traces->invalidate(IfConv.Head);
660  Traces->invalidate(IfConv.Tail);
661  Traces->invalidate(IfConv.TBB);
662  Traces->invalidate(IfConv.FBB);
663  Traces->verifyAnalysis();
664}
665
666// Adjust cycles with downward saturation.
667static unsigned adjCycles(unsigned Cyc, int Delta) {
668  if (Delta < 0 && Cyc + Delta > Cyc)
669    return 0;
670  return Cyc + Delta;
671}
672
673/// Apply cost model and heuristics to the if-conversion in IfConv.
674/// Return true if the conversion is a good idea.
675///
676bool EarlyIfConverter::shouldConvertIf() {
677  // Stress testing mode disables all cost considerations.
678  if (Stress)
679    return true;
680
681  if (!MinInstr)
682    MinInstr = Traces->getEnsemble(MachineTraceMetrics::TS_MinInstrCount);
683
684  MachineTraceMetrics::Trace TBBTrace = MinInstr->getTrace(IfConv.getTPred());
685  MachineTraceMetrics::Trace FBBTrace = MinInstr->getTrace(IfConv.getFPred());
686  DEBUG(dbgs() << "TBB: " << TBBTrace << "FBB: " << FBBTrace);
687  unsigned MinCrit = std::min(TBBTrace.getCriticalPath(),
688                              FBBTrace.getCriticalPath());
689
690  // Set a somewhat arbitrary limit on the critical path extension we accept.
691  unsigned CritLimit = SchedModel.MispredictPenalty/2;
692
693  // If-conversion only makes sense when there is unexploited ILP. Compute the
694  // maximum-ILP resource length of the trace after if-conversion. Compare it
695  // to the shortest critical path.
696  SmallVector<const MachineBasicBlock*, 1> ExtraBlocks;
697  if (IfConv.TBB != IfConv.Tail)
698    ExtraBlocks.push_back(IfConv.TBB);
699  unsigned ResLength = FBBTrace.getResourceLength(ExtraBlocks);
700  DEBUG(dbgs() << "Resource length " << ResLength
701               << ", minimal critical path " << MinCrit << '\n');
702  if (ResLength > MinCrit + CritLimit) {
703    DEBUG(dbgs() << "Not enough available ILP.\n");
704    return false;
705  }
706
707  // Assume that the depth of the first head terminator will also be the depth
708  // of the select instruction inserted, as determined by the flag dependency.
709  // TBB / FBB data dependencies may delay the select even more.
710  MachineTraceMetrics::Trace HeadTrace = MinInstr->getTrace(IfConv.Head);
711  unsigned BranchDepth =
712    HeadTrace.getInstrCycles(IfConv.Head->getFirstTerminator()).Depth;
713  DEBUG(dbgs() << "Branch depth: " << BranchDepth << '\n');
714
715  // Look at all the tail phis, and compute the critical path extension caused
716  // by inserting select instructions.
717  MachineTraceMetrics::Trace TailTrace = MinInstr->getTrace(IfConv.Tail);
718  for (unsigned i = 0, e = IfConv.PHIs.size(); i != e; ++i) {
719    SSAIfConv::PHIInfo &PI = IfConv.PHIs[i];
720    unsigned Slack = TailTrace.getInstrSlack(PI.PHI);
721    unsigned MaxDepth = Slack + TailTrace.getInstrCycles(PI.PHI).Depth;
722    DEBUG(dbgs() << "Slack " << Slack << ":\t" << *PI.PHI);
723
724    // The condition is pulled into the critical path.
725    unsigned CondDepth = adjCycles(BranchDepth, PI.CondCycles);
726    if (CondDepth > MaxDepth) {
727      unsigned Extra = CondDepth - MaxDepth;
728      DEBUG(dbgs() << "Condition adds " << Extra << " cycles.\n");
729      if (Extra > CritLimit) {
730        DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');
731        return false;
732      }
733    }
734
735    // The TBB value is pulled into the critical path.
736    unsigned TDepth = adjCycles(TBBTrace.getPHIDepth(PI.PHI), PI.TCycles);
737    if (TDepth > MaxDepth) {
738      unsigned Extra = TDepth - MaxDepth;
739      DEBUG(dbgs() << "TBB data adds " << Extra << " cycles.\n");
740      if (Extra > CritLimit) {
741        DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');
742        return false;
743      }
744    }
745
746    // The FBB value is pulled into the critical path.
747    unsigned FDepth = adjCycles(FBBTrace.getPHIDepth(PI.PHI), PI.FCycles);
748    if (FDepth > MaxDepth) {
749      unsigned Extra = FDepth - MaxDepth;
750      DEBUG(dbgs() << "FBB data adds " << Extra << " cycles.\n");
751      if (Extra > CritLimit) {
752        DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');
753        return false;
754      }
755    }
756  }
757  return true;
758}
759
760/// Attempt repeated if-conversion on MBB, return true if successful.
761///
762bool EarlyIfConverter::tryConvertIf(MachineBasicBlock *MBB) {
763  bool Changed = false;
764  while (IfConv.canConvertIf(MBB) && shouldConvertIf()) {
765    // If-convert MBB and update analyses.
766    invalidateTraces();
767    SmallVector<MachineBasicBlock*, 4> RemovedBlocks;
768    IfConv.convertIf(RemovedBlocks);
769    Changed = true;
770    updateDomTree(RemovedBlocks);
771    updateLoops(RemovedBlocks);
772  }
773  return Changed;
774}
775
776bool EarlyIfConverter::runOnMachineFunction(MachineFunction &MF) {
777  DEBUG(dbgs() << "********** EARLY IF-CONVERSION **********\n"
778               << "********** Function: " << MF.getName() << '\n');
779  // Only run if conversion if the target wants it.
780  const TargetSubtargetInfo &STI = MF.getSubtarget();
781  if (!STI.enableEarlyIfConversion())
782    return false;
783
784  TII = STI.getInstrInfo();
785  TRI = STI.getRegisterInfo();
786  SchedModel = STI.getSchedModel();
787  MRI = &MF.getRegInfo();
788  DomTree = &getAnalysis<MachineDominatorTree>();
789  Loops = getAnalysisIfAvailable<MachineLoopInfo>();
790  Traces = &getAnalysis<MachineTraceMetrics>();
791  MinInstr = nullptr;
792
793  bool Changed = false;
794  IfConv.runOnMachineFunction(MF);
795
796  // Visit blocks in dominator tree post-order. The post-order enables nested
797  // if-conversion in a single pass. The tryConvertIf() function may erase
798  // blocks, but only blocks dominated by the head block. This makes it safe to
799  // update the dominator tree while the post-order iterator is still active.
800  for (auto DomNode : post_order(DomTree))
801    if (tryConvertIf(DomNode->getBlock()))
802      Changed = true;
803
804  return Changed;
805}
806