LLVM  9.0.0svn
EarlyIfConversion.cpp
Go to the documentation of this file.
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"
20 #include "llvm/ADT/SetVector.h"
21 #include "llvm/ADT/SmallPtrSet.h"
22 #include "llvm/ADT/SparseSet.h"
23 #include "llvm/ADT/Statistic.h"
31 #include "llvm/CodeGen/Passes.h"
36 #include "llvm/Support/Debug.h"
38 
39 using namespace llvm;
40 
41 #define DEBUG_TYPE "early-ifcvt"
42 
43 // Absolute maximum number of instructions allowed per speculated block.
44 // This bypasses all other heuristics, so it should be set fairly high.
45 static cl::opt<unsigned>
46 BlockInstrLimit("early-ifcvt-limit", cl::init(30), cl::Hidden,
47  cl::desc("Maximum number of instructions per speculated block."));
48 
49 // Stress testing mode - disable heuristics.
50 static cl::opt<bool> Stress("stress-early-ifcvt", cl::Hidden,
51  cl::desc("Turn all knobs to 11"));
52 
53 STATISTIC(NumDiamondsSeen, "Number of diamonds");
54 STATISTIC(NumDiamondsConv, "Number of diamonds converted");
55 STATISTIC(NumTrianglesSeen, "Number of triangles");
56 STATISTIC(NumTrianglesConv, "Number of triangles converted");
57 
58 //===----------------------------------------------------------------------===//
59 // SSAIfConv
60 //===----------------------------------------------------------------------===//
61 //
62 // The SSAIfConv class performs if-conversion on SSA form machine code after
63 // determining if it is possible. The class contains no heuristics; external
64 // code should be used to determine when if-conversion is a good idea.
65 //
66 // SSAIfConv can convert both triangles and diamonds:
67 //
68 // Triangle: Head Diamond: Head
69 // | \ / \_
70 // | \ / |
71 // | [TF]BB FBB TBB
72 // | / \ /
73 // | / \ /
74 // Tail Tail
75 //
76 // Instructions in the conditional blocks TBB and/or FBB are spliced into the
77 // Head block, and phis in the Tail block are converted to select instructions.
78 //
79 namespace {
80 class SSAIfConv {
81  const TargetInstrInfo *TII;
82  const TargetRegisterInfo *TRI;
84 
85 public:
86  /// The block containing the conditional branch.
87  MachineBasicBlock *Head;
88 
89  /// The block containing phis after the if-then-else.
90  MachineBasicBlock *Tail;
91 
92  /// The 'true' conditional block as determined by AnalyzeBranch.
93  MachineBasicBlock *TBB;
94 
95  /// The 'false' conditional block as determined by AnalyzeBranch.
96  MachineBasicBlock *FBB;
97 
98  /// isTriangle - When there is no 'else' block, either TBB or FBB will be
99  /// equal to Tail.
100  bool isTriangle() const { return TBB == Tail || FBB == Tail; }
101 
102  /// Returns the Tail predecessor for the True side.
103  MachineBasicBlock *getTPred() const { return TBB == Tail ? Head : TBB; }
104 
105  /// Returns the Tail predecessor for the False side.
106  MachineBasicBlock *getFPred() const { return FBB == Tail ? Head : FBB; }
107 
108  /// Information about each phi in the Tail block.
109  struct PHIInfo {
110  MachineInstr *PHI;
111  unsigned TReg, FReg;
112  // Latencies from Cond+Branch, TReg, and FReg to DstReg.
113  int CondCycles, TCycles, FCycles;
114 
115  PHIInfo(MachineInstr *phi)
116  : PHI(phi), TReg(0), FReg(0), CondCycles(0), TCycles(0), FCycles(0) {}
117  };
118 
120 
121 private:
122  /// The branch condition determined by AnalyzeBranch.
124 
125  /// Instructions in Head that define values used by the conditional blocks.
126  /// The hoisted instructions must be inserted after these instructions.
127  SmallPtrSet<MachineInstr*, 8> InsertAfter;
128 
129  /// Register units clobbered by the conditional blocks.
130  BitVector ClobberedRegUnits;
131 
132  // Scratch pad for findInsertionPoint.
134 
135  /// Insertion point in Head for speculatively executed instructions form TBB
136  /// and FBB.
137  MachineBasicBlock::iterator InsertionPoint;
138 
139  /// Return true if all non-terminator instructions in MBB can be safely
140  /// speculated.
141  bool canSpeculateInstrs(MachineBasicBlock *MBB);
142 
143  /// Find a valid insertion point in Head.
144  bool findInsertionPoint();
145 
146  /// Replace PHI instructions in Tail with selects.
147  void replacePHIInstrs();
148 
149  /// Insert selects and rewrite PHI operands to use them.
150  void rewritePHIOperands();
151 
152 public:
153  /// runOnMachineFunction - Initialize per-function data structures.
154  void runOnMachineFunction(MachineFunction &MF) {
155  TII = MF.getSubtarget().getInstrInfo();
156  TRI = MF.getSubtarget().getRegisterInfo();
157  MRI = &MF.getRegInfo();
158  LiveRegUnits.clear();
159  LiveRegUnits.setUniverse(TRI->getNumRegUnits());
160  ClobberedRegUnits.clear();
161  ClobberedRegUnits.resize(TRI->getNumRegUnits());
162  }
163 
164  /// canConvertIf - If the sub-CFG headed by MBB can be if-converted,
165  /// initialize the internal state, and return true.
166  bool canConvertIf(MachineBasicBlock *MBB);
167 
168  /// convertIf - If-convert the last block passed to canConvertIf(), assuming
169  /// it is possible. Add any erased blocks to RemovedBlocks.
170  void convertIf(SmallVectorImpl<MachineBasicBlock*> &RemovedBlocks);
171 };
172 } // end anonymous namespace
173 
174 
175 /// canSpeculateInstrs - Returns true if all the instructions in MBB can safely
176 /// be speculated. The terminators are not considered.
177 ///
178 /// If instructions use any values that are defined in the head basic block,
179 /// the defining instructions are added to InsertAfter.
180 ///
181 /// Any clobbered regunits are added to ClobberedRegUnits.
182 ///
183 bool SSAIfConv::canSpeculateInstrs(MachineBasicBlock *MBB) {
184  // Reject any live-in physregs. It's probably CPSR/EFLAGS, and very hard to
185  // get right.
186  if (!MBB->livein_empty()) {
187  LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has live-ins.\n");
188  return false;
189  }
190 
191  unsigned InstrCount = 0;
192 
193  // Check all instructions, except the terminators. It is assumed that
194  // terminators never have side effects or define any used register values.
195  for (MachineBasicBlock::iterator I = MBB->begin(),
196  E = MBB->getFirstTerminator(); I != E; ++I) {
197  if (I->isDebugInstr())
198  continue;
199 
200  if (++InstrCount > BlockInstrLimit && !Stress) {
201  LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has more than "
202  << BlockInstrLimit << " instructions.\n");
203  return false;
204  }
205 
206  // There shouldn't normally be any phis in a single-predecessor block.
207  if (I->isPHI()) {
208  LLVM_DEBUG(dbgs() << "Can't hoist: " << *I);
209  return false;
210  }
211 
212  // Don't speculate loads. Note that it may be possible and desirable to
213  // speculate GOT or constant pool loads that are guaranteed not to trap,
214  // but we don't support that for now.
215  if (I->mayLoad()) {
216  LLVM_DEBUG(dbgs() << "Won't speculate load: " << *I);
217  return false;
218  }
219 
220  // We never speculate stores, so an AA pointer isn't necessary.
221  bool DontMoveAcrossStore = true;
222  if (!I->isSafeToMove(nullptr, DontMoveAcrossStore)) {
223  LLVM_DEBUG(dbgs() << "Can't speculate: " << *I);
224  return false;
225  }
226 
227  // Check for any dependencies on Head instructions.
228  for (const MachineOperand &MO : I->operands()) {
229  if (MO.isRegMask()) {
230  LLVM_DEBUG(dbgs() << "Won't speculate regmask: " << *I);
231  return false;
232  }
233  if (!MO.isReg())
234  continue;
235  unsigned Reg = MO.getReg();
236 
237  // Remember clobbered regunits.
238  if (MO.isDef() && TargetRegisterInfo::isPhysicalRegister(Reg))
239  for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units)
240  ClobberedRegUnits.set(*Units);
241 
242  if (!MO.readsReg() || !TargetRegisterInfo::isVirtualRegister(Reg))
243  continue;
244  MachineInstr *DefMI = MRI->getVRegDef(Reg);
245  if (!DefMI || DefMI->getParent() != Head)
246  continue;
247  if (InsertAfter.insert(DefMI).second)
248  LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " depends on "
249  << *DefMI);
250  if (DefMI->isTerminator()) {
251  LLVM_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 ///
270 bool SSAIfConv::findInsertionPoint() {
271  // Keep track of live regunits before the current position.
272  // Only track RegUnits that are also in ClobberedRegUnits.
273  LiveRegUnits.clear();
278  while (I != B) {
279  --I;
280  // Some of the conditional code depends in I.
281  if (InsertAfter.count(&*I)) {
282  LLVM_DEBUG(dbgs() << "Can't insert code after " << *I);
283  return false;
284  }
285 
286  // Update live regunits.
287  for (const MachineOperand &MO : I->operands()) {
288  // We're ignoring regmask operands. That is conservatively correct.
289  if (!MO.isReg())
290  continue;
291  unsigned Reg = MO.getReg();
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  LLVM_DEBUG({
317  dbgs() << "Would clobber";
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  LLVM_DEBUG(dbgs() << "Can insert before " << *I);
329  return true;
330  }
331  LLVM_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 ///
340 bool 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  LLVM_DEBUG(dbgs() << "\nDiamond: " << printMBBReference(*Head) << " -> "
365  << printMBBReference(*Succ0) << "/"
366  << printMBBReference(*Succ1) << " -> "
367  << printMBBReference(*Tail) << '\n');
368 
369  // Live-in physregs are tricky to get right when speculating code.
370  if (!Tail->livein_empty()) {
371  LLVM_DEBUG(dbgs() << "Tail has live-ins.\n");
372  return false;
373  }
374  } else {
375  LLVM_DEBUG(dbgs() << "\nTriangle: " << printMBBReference(*Head) << " -> "
376  << printMBBReference(*Succ0) << " -> "
377  << printMBBReference(*Tail) << '\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  LLVM_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  LLVM_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  LLVM_DEBUG(dbgs() << "AnalyzeBranch didn't find conditional branch.\n");
397  return false;
398  }
399 
400  // Make sure the analyzed branch is conditional; one of the successors
401  // could be a landing pad. (Empty landing pads can be generated on Windows.)
402  if (Cond.empty()) {
403  LLVM_DEBUG(dbgs() << "AnalyzeBranch found an unconditional branch.\n");
404  return false;
405  }
406 
407  // AnalyzeBranch doesn't set FBB on a fall-through branch.
408  // Make sure it is always set.
409  FBB = TBB == Succ0 ? Succ1 : Succ0;
410 
411  // Any phis in the tail block must be convertible to selects.
412  PHIs.clear();
413  MachineBasicBlock *TPred = getTPred();
414  MachineBasicBlock *FPred = getFPred();
415  for (MachineBasicBlock::iterator I = Tail->begin(), E = Tail->end();
416  I != E && I->isPHI(); ++I) {
417  PHIs.push_back(&*I);
418  PHIInfo &PI = PHIs.back();
419  // Find PHI operands corresponding to TPred and FPred.
420  for (unsigned i = 1; i != PI.PHI->getNumOperands(); i += 2) {
421  if (PI.PHI->getOperand(i+1).getMBB() == TPred)
422  PI.TReg = PI.PHI->getOperand(i).getReg();
423  if (PI.PHI->getOperand(i+1).getMBB() == FPred)
424  PI.FReg = PI.PHI->getOperand(i).getReg();
425  }
426  assert(TargetRegisterInfo::isVirtualRegister(PI.TReg) && "Bad PHI");
427  assert(TargetRegisterInfo::isVirtualRegister(PI.FReg) && "Bad PHI");
428 
429  // Get target information.
430  if (!TII->canInsertSelect(*Head, Cond, PI.TReg, PI.FReg,
431  PI.CondCycles, PI.TCycles, PI.FCycles)) {
432  LLVM_DEBUG(dbgs() << "Can't convert: " << *PI.PHI);
433  return false;
434  }
435  }
436 
437  // Check that the conditional instructions can be speculated.
438  InsertAfter.clear();
439  ClobberedRegUnits.reset();
440  if (TBB != Tail && !canSpeculateInstrs(TBB))
441  return false;
442  if (FBB != Tail && !canSpeculateInstrs(FBB))
443  return false;
444 
445  // Try to find a valid insertion point for the speculated instructions in the
446  // head basic block.
447  if (!findInsertionPoint())
448  return false;
449 
450  if (isTriangle())
451  ++NumTrianglesSeen;
452  else
453  ++NumDiamondsSeen;
454  return true;
455 }
456 
457 /// replacePHIInstrs - Completely replace PHI instructions with selects.
458 /// This is possible when the only Tail predecessors are the if-converted
459 /// blocks.
460 void SSAIfConv::replacePHIInstrs() {
461  assert(Tail->pred_size() == 2 && "Cannot replace PHIs");
463  assert(FirstTerm != Head->end() && "No terminators");
464  DebugLoc HeadDL = FirstTerm->getDebugLoc();
465 
466  // Convert all PHIs to select instructions inserted before FirstTerm.
467  for (unsigned i = 0, e = PHIs.size(); i != e; ++i) {
468  PHIInfo &PI = PHIs[i];
469  LLVM_DEBUG(dbgs() << "If-converting " << *PI.PHI);
470  unsigned DstReg = PI.PHI->getOperand(0).getReg();
471  TII->insertSelect(*Head, FirstTerm, HeadDL, DstReg, Cond, PI.TReg, PI.FReg);
472  LLVM_DEBUG(dbgs() << " --> " << *std::prev(FirstTerm));
473  PI.PHI->eraseFromParent();
474  PI.PHI = nullptr;
475  }
476 }
477 
478 /// rewritePHIOperands - When there are additional Tail predecessors, insert
479 /// select instructions in Head and rewrite PHI operands to use the selects.
480 /// Keep the PHI instructions in Tail to handle the other predecessors.
481 void SSAIfConv::rewritePHIOperands() {
483  assert(FirstTerm != Head->end() && "No terminators");
484  DebugLoc HeadDL = FirstTerm->getDebugLoc();
485 
486  // Convert all PHIs to select instructions inserted before FirstTerm.
487  for (unsigned i = 0, e = PHIs.size(); i != e; ++i) {
488  PHIInfo &PI = PHIs[i];
489  unsigned DstReg = 0;
490 
491  LLVM_DEBUG(dbgs() << "If-converting " << *PI.PHI);
492  if (PI.TReg == PI.FReg) {
493  // We do not need the select instruction if both incoming values are
494  // equal.
495  DstReg = PI.TReg;
496  } else {
497  unsigned PHIDst = PI.PHI->getOperand(0).getReg();
498  DstReg = MRI->createVirtualRegister(MRI->getRegClass(PHIDst));
499  TII->insertSelect(*Head, FirstTerm, HeadDL,
500  DstReg, Cond, PI.TReg, PI.FReg);
501  LLVM_DEBUG(dbgs() << " --> " << *std::prev(FirstTerm));
502  }
503 
504  // Rewrite PHI operands TPred -> (DstReg, Head), remove FPred.
505  for (unsigned i = PI.PHI->getNumOperands(); i != 1; i -= 2) {
506  MachineBasicBlock *MBB = PI.PHI->getOperand(i-1).getMBB();
507  if (MBB == getTPred()) {
508  PI.PHI->getOperand(i-1).setMBB(Head);
509  PI.PHI->getOperand(i-2).setReg(DstReg);
510  } else if (MBB == getFPred()) {
511  PI.PHI->RemoveOperand(i-1);
512  PI.PHI->RemoveOperand(i-2);
513  }
514  }
515  LLVM_DEBUG(dbgs() << " --> " << *PI.PHI);
516  }
517 }
518 
519 /// convertIf - Execute the if conversion after canConvertIf has determined the
520 /// feasibility.
521 ///
522 /// Any basic blocks erased will be added to RemovedBlocks.
523 ///
524 void SSAIfConv::convertIf(SmallVectorImpl<MachineBasicBlock*> &RemovedBlocks) {
525  assert(Head && Tail && TBB && FBB && "Call canConvertIf first.");
526 
527  // Update statistics.
528  if (isTriangle())
529  ++NumTrianglesConv;
530  else
531  ++NumDiamondsConv;
532 
533  // Move all instructions into Head, except for the terminators.
534  if (TBB != Tail)
535  Head->splice(InsertionPoint, TBB, TBB->begin(), TBB->getFirstTerminator());
536  if (FBB != Tail)
537  Head->splice(InsertionPoint, FBB, FBB->begin(), FBB->getFirstTerminator());
538 
539  // Are there extra Tail predecessors?
540  bool ExtraPreds = Tail->pred_size() != 2;
541  if (ExtraPreds)
542  rewritePHIOperands();
543  else
544  replacePHIInstrs();
545 
546  // Fix up the CFG, temporarily leave Head without any successors.
547  Head->removeSuccessor(TBB);
548  Head->removeSuccessor(FBB, true);
549  if (TBB != Tail)
550  TBB->removeSuccessor(Tail, true);
551  if (FBB != Tail)
552  FBB->removeSuccessor(Tail, true);
553 
554  // Fix up Head's terminators.
555  // It should become a single branch or a fallthrough.
556  DebugLoc HeadDL = Head->getFirstTerminator()->getDebugLoc();
557  TII->removeBranch(*Head);
558 
559  // Erase the now empty conditional blocks. It is likely that Head can fall
560  // through to Tail, and we can join the two blocks.
561  if (TBB != Tail) {
562  RemovedBlocks.push_back(TBB);
563  TBB->eraseFromParent();
564  }
565  if (FBB != Tail) {
566  RemovedBlocks.push_back(FBB);
567  FBB->eraseFromParent();
568  }
569 
570  assert(Head->succ_empty() && "Additional head successors?");
571  if (!ExtraPreds && Head->isLayoutSuccessor(Tail)) {
572  // Splice Tail onto the end of Head.
573  LLVM_DEBUG(dbgs() << "Joining tail " << printMBBReference(*Tail)
574  << " into head " << printMBBReference(*Head) << '\n');
575  Head->splice(Head->end(), Tail,
576  Tail->begin(), Tail->end());
578  RemovedBlocks.push_back(Tail);
579  Tail->eraseFromParent();
580  } else {
581  // We need a branch to Tail, let code placement work it out later.
582  LLVM_DEBUG(dbgs() << "Converting to unconditional branch.\n");
584  TII->insertBranch(*Head, Tail, nullptr, EmptyCond, HeadDL);
585  Head->addSuccessor(Tail);
586  }
587  LLVM_DEBUG(dbgs() << *Head);
588 }
589 
590 
591 //===----------------------------------------------------------------------===//
592 // EarlyIfConverter Pass
593 //===----------------------------------------------------------------------===//
594 
595 namespace {
596 class EarlyIfConverter : public MachineFunctionPass {
597  const TargetInstrInfo *TII;
598  const TargetRegisterInfo *TRI;
599  MCSchedModel SchedModel;
601  MachineDominatorTree *DomTree;
603  MachineTraceMetrics *Traces;
605  SSAIfConv IfConv;
606 
607 public:
608  static char ID;
609  EarlyIfConverter() : MachineFunctionPass(ID) {}
610  void getAnalysisUsage(AnalysisUsage &AU) const override;
611  bool runOnMachineFunction(MachineFunction &MF) override;
612  StringRef getPassName() const override { return "Early If-Conversion"; }
613 
614 private:
615  bool tryConvertIf(MachineBasicBlock*);
616  void updateDomTree(ArrayRef<MachineBasicBlock*> Removed);
617  void updateLoops(ArrayRef<MachineBasicBlock*> Removed);
618  void invalidateTraces();
619  bool shouldConvertIf();
620 };
621 } // end anonymous namespace
622 
623 char EarlyIfConverter::ID = 0;
625 
626 INITIALIZE_PASS_BEGIN(EarlyIfConverter, DEBUG_TYPE,
627  "Early If Converter", false, false)
631 INITIALIZE_PASS_END(EarlyIfConverter, DEBUG_TYPE,
632  "Early If Converter", false, false)
633 
634 void EarlyIfConverter::getAnalysisUsage(AnalysisUsage &AU) const {
635  AU.addRequired<MachineBranchProbabilityInfo>();
636  AU.addRequired<MachineDominatorTree>();
637  AU.addPreserved<MachineDominatorTree>();
638  AU.addRequired<MachineLoopInfo>();
639  AU.addPreserved<MachineLoopInfo>();
640  AU.addRequired<MachineTraceMetrics>();
641  AU.addPreserved<MachineTraceMetrics>();
643 }
644 
645 /// Update the dominator tree after if-conversion erased some blocks.
646 void EarlyIfConverter::updateDomTree(ArrayRef<MachineBasicBlock*> Removed) {
647  // convertIf can remove TBB, FBB, and Tail can be merged into Head.
648  // TBB and FBB should not dominate any blocks.
649  // Tail children should be transferred to Head.
650  MachineDomTreeNode *HeadNode = DomTree->getNode(IfConv.Head);
651  for (unsigned i = 0, e = Removed.size(); i != e; ++i) {
652  MachineDomTreeNode *Node = DomTree->getNode(Removed[i]);
653  assert(Node != HeadNode && "Cannot erase the head node");
654  while (Node->getNumChildren()) {
655  assert(Node->getBlock() == IfConv.Tail && "Unexpected children");
656  DomTree->changeImmediateDominator(Node->getChildren().back(), HeadNode);
657  }
658  DomTree->eraseNode(Removed[i]);
659  }
660 }
661 
662 /// Update LoopInfo after if-conversion.
663 void EarlyIfConverter::updateLoops(ArrayRef<MachineBasicBlock*> Removed) {
664  if (!Loops)
665  return;
666  // If-conversion doesn't change loop structure, and it doesn't mess with back
667  // edges, so updating LoopInfo is simply removing the dead blocks.
668  for (unsigned i = 0, e = Removed.size(); i != e; ++i)
669  Loops->removeBlock(Removed[i]);
670 }
671 
672 /// Invalidate MachineTraceMetrics before if-conversion.
673 void EarlyIfConverter::invalidateTraces() {
674  Traces->verifyAnalysis();
675  Traces->invalidate(IfConv.Head);
676  Traces->invalidate(IfConv.Tail);
677  Traces->invalidate(IfConv.TBB);
678  Traces->invalidate(IfConv.FBB);
679  Traces->verifyAnalysis();
680 }
681 
682 // Adjust cycles with downward saturation.
683 static unsigned adjCycles(unsigned Cyc, int Delta) {
684  if (Delta < 0 && Cyc + Delta > Cyc)
685  return 0;
686  return Cyc + Delta;
687 }
688 
689 /// Apply cost model and heuristics to the if-conversion in IfConv.
690 /// Return true if the conversion is a good idea.
691 ///
692 bool EarlyIfConverter::shouldConvertIf() {
693  // Stress testing mode disables all cost considerations.
694  if (Stress)
695  return true;
696 
697  if (!MinInstr)
698  MinInstr = Traces->getEnsemble(MachineTraceMetrics::TS_MinInstrCount);
699 
700  MachineTraceMetrics::Trace TBBTrace = MinInstr->getTrace(IfConv.getTPred());
701  MachineTraceMetrics::Trace FBBTrace = MinInstr->getTrace(IfConv.getFPred());
702  LLVM_DEBUG(dbgs() << "TBB: " << TBBTrace << "FBB: " << FBBTrace);
703  unsigned MinCrit = std::min(TBBTrace.getCriticalPath(),
704  FBBTrace.getCriticalPath());
705 
706  // Set a somewhat arbitrary limit on the critical path extension we accept.
707  unsigned CritLimit = SchedModel.MispredictPenalty/2;
708 
709  // If-conversion only makes sense when there is unexploited ILP. Compute the
710  // maximum-ILP resource length of the trace after if-conversion. Compare it
711  // to the shortest critical path.
713  if (IfConv.TBB != IfConv.Tail)
714  ExtraBlocks.push_back(IfConv.TBB);
715  unsigned ResLength = FBBTrace.getResourceLength(ExtraBlocks);
716  LLVM_DEBUG(dbgs() << "Resource length " << ResLength
717  << ", minimal critical path " << MinCrit << '\n');
718  if (ResLength > MinCrit + CritLimit) {
719  LLVM_DEBUG(dbgs() << "Not enough available ILP.\n");
720  return false;
721  }
722 
723  // Assume that the depth of the first head terminator will also be the depth
724  // of the select instruction inserted, as determined by the flag dependency.
725  // TBB / FBB data dependencies may delay the select even more.
726  MachineTraceMetrics::Trace HeadTrace = MinInstr->getTrace(IfConv.Head);
727  unsigned BranchDepth =
728  HeadTrace.getInstrCycles(*IfConv.Head->getFirstTerminator()).Depth;
729  LLVM_DEBUG(dbgs() << "Branch depth: " << BranchDepth << '\n');
730 
731  // Look at all the tail phis, and compute the critical path extension caused
732  // by inserting select instructions.
733  MachineTraceMetrics::Trace TailTrace = MinInstr->getTrace(IfConv.Tail);
734  for (unsigned i = 0, e = IfConv.PHIs.size(); i != e; ++i) {
735  SSAIfConv::PHIInfo &PI = IfConv.PHIs[i];
736  unsigned Slack = TailTrace.getInstrSlack(*PI.PHI);
737  unsigned MaxDepth = Slack + TailTrace.getInstrCycles(*PI.PHI).Depth;
738  LLVM_DEBUG(dbgs() << "Slack " << Slack << ":\t" << *PI.PHI);
739 
740  // The condition is pulled into the critical path.
741  unsigned CondDepth = adjCycles(BranchDepth, PI.CondCycles);
742  if (CondDepth > MaxDepth) {
743  unsigned Extra = CondDepth - MaxDepth;
744  LLVM_DEBUG(dbgs() << "Condition adds " << Extra << " cycles.\n");
745  if (Extra > CritLimit) {
746  LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');
747  return false;
748  }
749  }
750 
751  // The TBB value is pulled into the critical path.
752  unsigned TDepth = adjCycles(TBBTrace.getPHIDepth(*PI.PHI), PI.TCycles);
753  if (TDepth > MaxDepth) {
754  unsigned Extra = TDepth - MaxDepth;
755  LLVM_DEBUG(dbgs() << "TBB data adds " << Extra << " cycles.\n");
756  if (Extra > CritLimit) {
757  LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');
758  return false;
759  }
760  }
761 
762  // The FBB value is pulled into the critical path.
763  unsigned FDepth = adjCycles(FBBTrace.getPHIDepth(*PI.PHI), PI.FCycles);
764  if (FDepth > MaxDepth) {
765  unsigned Extra = FDepth - MaxDepth;
766  LLVM_DEBUG(dbgs() << "FBB data adds " << Extra << " cycles.\n");
767  if (Extra > CritLimit) {
768  LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');
769  return false;
770  }
771  }
772  }
773  return true;
774 }
775 
776 /// Attempt repeated if-conversion on MBB, return true if successful.
777 ///
778 bool EarlyIfConverter::tryConvertIf(MachineBasicBlock *MBB) {
779  bool Changed = false;
780  while (IfConv.canConvertIf(MBB) && shouldConvertIf()) {
781  // If-convert MBB and update analyses.
782  invalidateTraces();
784  IfConv.convertIf(RemovedBlocks);
785  Changed = true;
786  updateDomTree(RemovedBlocks);
787  updateLoops(RemovedBlocks);
788  }
789  return Changed;
790 }
791 
792 bool EarlyIfConverter::runOnMachineFunction(MachineFunction &MF) {
793  LLVM_DEBUG(dbgs() << "********** EARLY IF-CONVERSION **********\n"
794  << "********** Function: " << MF.getName() << '\n');
795  if (skipFunction(MF.getFunction()))
796  return false;
797 
798  // Only run if conversion if the target wants it.
799  const TargetSubtargetInfo &STI = MF.getSubtarget();
800  if (!STI.enableEarlyIfConversion())
801  return false;
802 
803  TII = STI.getInstrInfo();
804  TRI = STI.getRegisterInfo();
805  SchedModel = STI.getSchedModel();
806  MRI = &MF.getRegInfo();
807  DomTree = &getAnalysis<MachineDominatorTree>();
808  Loops = getAnalysisIfAvailable<MachineLoopInfo>();
809  Traces = &getAnalysis<MachineTraceMetrics>();
810  MinInstr = nullptr;
811 
812  bool Changed = false;
813  IfConv.runOnMachineFunction(MF);
814 
815  // Visit blocks in dominator tree post-order. The post-order enables nested
816  // if-conversion in a single pass. The tryConvertIf() function may erase
817  // blocks, but only blocks dominated by the head block. This makes it safe to
818  // update the dominator tree while the post-order iterator is still active.
819  for (auto DomNode : post_order(DomTree))
820  if (tryConvertIf(DomNode->getBlock()))
821  Changed = true;
822 
823  return Changed;
824 }
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
Definition: BitVector.h:371
BitVector & set()
Definition: BitVector.h:397
static cl::opt< bool > Stress("stress-early-ifcvt", cl::Hidden, cl::desc("Turn all knobs to 11"))
virtual bool canInsertSelect(const MachineBasicBlock &MBB, ArrayRef< MachineOperand > Cond, unsigned TrueReg, unsigned FalseReg, int &CondCycles, int &TrueCycles, int &FalseCycles) const
Return true if it is possible to insert a select instruction that chooses between TrueReg and FalseRe...
virtual void insertSelect(MachineBasicBlock &MBB, MachineBasicBlock::iterator I, const DebugLoc &DL, unsigned DstReg, ArrayRef< MachineOperand > Cond, unsigned TrueReg, unsigned FalseReg) const
Insert a select instruction into MBB before I that will copy TrueReg to DstReg when Cond is true...
const TargetRegisterClass * getRegClass(unsigned Reg) const
Return the register class of the specified virtual register.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
std::pair< iterator, bool > insert(const ValueT &Val)
insert - Attempts to insert a new element.
Definition: SparseSet.h:249
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
unsigned Depth
Earliest issue cycle as determined by data dependencies and instruction latencies from the beginning ...
void push_back(const T &Elt)
Definition: SmallVector.h:211
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB)
Transfers all the successors, as in transferSuccessors, and update PHI operands in the successor bloc...
unsigned Reg
bool test(unsigned Idx) const
Definition: BitVector.h:501
virtual unsigned insertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB, MachineBasicBlock *FBB, ArrayRef< MachineOperand > Cond, const DebugLoc &DL, int *BytesAdded=nullptr) const
Insert branch code into the end of the specified MachineBasicBlock.
char & EarlyIfConverterID
EarlyIfConverter - This pass performs if-conversion on SSA form by inserting cmov instructions...
STATISTIC(NumFunctions, "Total number of functions")
unsigned const TargetRegisterInfo * TRI
A debug info location.
Definition: DebugLoc.h:33
A trace ensemble is a collection of traces selected using the same strategy, for example &#39;minimum res...
static unsigned InstrCount
bool isPHI() const
virtual unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const
Remove the branching code at the end of the specific MBB.
unsigned getNumRegUnits() const
Return the number of (native) register units in the target.
virtual bool enableEarlyIfConversion() const
Enable the use of the early if conversion pass.
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
Hexagon Hardware Loops
void eraseFromParent()
This method unlinks &#39;this&#39; from the containing function and deletes it.
void clear()
clear - Removes all bits from the bitvector. Does not change capacity.
Definition: BitVector.h:366
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
bool isTerminator(QueryType Type=AnyInBundle) const
Returns true if this instruction part of the terminator for a basic block.
Definition: MachineInstr.h:648
Printable printRegUnit(unsigned Unit, const TargetRegisterInfo *TRI)
Create Printable object to print register units on a raw_ostream.
MachineInstr * getVRegDef(unsigned Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
Select the trace through a block that has the fewest instructions.
INITIALIZE_PASS_BEGIN(EarlyIfConverter, DEBUG_TYPE, "Early If Converter", false, false) INITIALIZE_PASS_END(EarlyIfConverter
Base class for the actual dominator tree node.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
const std::vector< DomTreeNodeBase * > & getChildren() const
virtual const TargetInstrInfo * getInstrInfo() const
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
iterator erase(iterator I)
erase - Erases an existing element identified by a valid iterator.
Definition: SparseSet.h:285
TargetInstrInfo - Interface to description of machine instruction set.
bool empty() const
empty - Returns true if the set is empty.
Definition: SparseSet.h:183
NodeT * getBlock() const
Early If Converter
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:422
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
unsigned const MachineRegisterInfo * MRI
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:148
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
unsigned getCriticalPath() const
Return the length of the (data dependency) critical path through the trace.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:370
InstrCycles getInstrCycles(const MachineInstr &MI) const
Return the depth and height of MI.
Represent the analysis usage information of a pass.
BitVector & reset()
Definition: BitVector.h:438
iterator_range< po_iterator< T > > post_order(const T &G)
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:381
void setUniverse(unsigned U)
setUniverse - Set the universe size which determines the largest key the set can hold.
Definition: SparseSet.h:155
virtual bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify=false) const
Analyze the branching code at the end of MBB, returning true if it cannot be understood (e...
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
A trace represents a plausible sequence of executed basic blocks that passes through the current basi...
size_t size() const
Definition: SmallVector.h:52
const_iterator end() const
Definition: SparseSet.h:175
#define DEBUG_TYPE
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
const unsigned MaxDepth
static unsigned adjCycles(unsigned Cyc, int Delta)
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
MachineOperand class - Representation of each machine instruction operand.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:839
size_t getNumChildren() const
MachineInstrBuilder MachineInstrBuilder & DefMI
const_iterator begin() const
Definition: SparseSet.h:174
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:373
unsigned pred_size() const
bool isLayoutSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB will be emitted immediately after this block, such that if this bloc...
const Function & getFunction() const
Return the LLVM function that this machine code represents.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
static cl::opt< unsigned > BlockInstrLimit("early-ifcvt-limit", cl::init(30), cl::Hidden, cl::desc("Maximum number of instructions per speculated block."))
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:940
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
unsigned succ_size() const
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:253
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
TargetSubtargetInfo - Generic base class for all target subtargets.
Representation of each machine instruction.
Definition: MachineInstr.h:63
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB &#39;Other&#39; at the position From, and insert it into this MBB right before &#39;...
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
#define I(x, y, z)
Definition: MD5.cpp:58
A set of register units used to track register liveness.
Definition: LiveRegUnits.h:30
void removeSuccessor(MachineBasicBlock *Succ, bool NormalizeSuccProbs=false)
Remove successor from the successors list of this MachineBasicBlock.
void clear()
clear - Clears the set.
Definition: SparseSet.h:194
unsigned getPHIDepth(const MachineInstr &PHI) const
Return the Depth of a PHI instruction in a trace center block successor.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
unsigned getResourceLength(ArrayRef< const MachineBasicBlock *> Extrablocks=None, ArrayRef< const MCSchedClassDesc *> ExtraInstrs=None, ArrayRef< const MCSchedClassDesc *> RemoveInstrs=None) const
Return the resource length of the trace.
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
unsigned getInstrSlack(const MachineInstr &MI) const
Return the slack of MI.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
Machine model for scheduling, bundling, and heuristics.
Definition: MCSchedule.h:244
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
const MCSchedModel & getSchedModel() const
Get the machine model for this subtarget&#39;s CPU.
unsigned createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...