lib/CodeGen/EarlyIfConversion.cpp

   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 #define DEBUG_TYPE "early-ifcvt"
  20 #include "MachineTraceMetrics.h"
  21 #include "llvm/Function.h"
  22 #include "llvm/ADT/BitVector.h"
  23 #include "llvm/ADT/PostOrderIterator.h"
  24 #include "llvm/ADT/SetVector.h"
  25 #include "llvm/ADT/SmallPtrSet.h"
  26 #include "llvm/ADT/SparseSet.h"
  27 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
  28 #include "llvm/CodeGen/MachineDominators.h"
  29 #include "llvm/CodeGen/MachineFunction.h"
  30 #include "llvm/CodeGen/MachineFunctionPass.h"
  31 #include "llvm/CodeGen/MachineLoopInfo.h"
  32 #include "llvm/CodeGen/MachineRegisterInfo.h"
  33 #include "llvm/CodeGen/Passes.h"
  34 #include "llvm/MC/MCInstrItineraries.h"
  35 #include "llvm/Target/TargetInstrInfo.h"
  36 #include "llvm/Target/TargetRegisterInfo.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 // 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 typedef SmallSetVector<MachineBasicBlock*, 8> BlockSetVector;
  54
  55 //===----------------------------------------------------------------------===//
  56 //                                 SSAIfConv
  57 //===----------------------------------------------------------------------===//
  58 //
  59 // The SSAIfConv class performs if-conversion on SSA form machine code after
  60 // determining if it is possible. The class contains no heuristics; external
  61 // code should be used to determine when if-conversion is a good idea.
  62 //
  63 // SSAIfConv can convert both triangles and diamonds:
  64 //
  65 //   Triangle: Head              Diamond: Head
  66 //              | \                       /  \_
  67 //              |  \                     /    |
  68 //              |  [TF]BB              FBB    TBB
  69 //              |  /                     \    /
  70 //              | /                       \  /
  71 //             Tail                       Tail
  72 //
  73 // Instructions in the conditional blocks TBB and/or FBB are spliced into the
  74 // Head block, and phis in the Tail block are converted to select instructions.
  75 //
  76 namespace {
  77 class SSAIfConv {
  78   const TargetInstrInfo *TII;
  79   const TargetRegisterInfo *TRI;
  80   MachineRegisterInfo *MRI;
  81
  82 public:
  83   /// The block containing the conditional branch.
  84   MachineBasicBlock *Head;
  85
  86   /// The block containing phis after the if-then-else.
  87   MachineBasicBlock *Tail;
  88
  89   /// The 'true' conditional block as determined by AnalyzeBranch.
  90   MachineBasicBlock *TBB;
  91
  92   /// The 'false' conditional block as determined by AnalyzeBranch.
  93   MachineBasicBlock *FBB;
  94
  95   /// isTriangle - When there is no 'else' block, either TBB or FBB will be
  96   /// equal to Tail.
  97   bool isTriangle() const { return TBB == Tail || FBB == Tail; }
  98
  99   /// Information about each phi in the Tail block.
 100   struct PHIInfo {
 101     MachineInstr *PHI;
 102     unsigned TReg, FReg;
 103     // Latencies from Cond+Branch, TReg, and FReg to DstReg.
 104     int CondCycles, TCycles, FCycles;
 105
 106     PHIInfo(MachineInstr *phi)
 107       : PHI(phi), TReg(0), FReg(0), CondCycles(0), TCycles(0), FCycles(0) {}
 108   };
 109
 110   SmallVector<PHIInfo, 8> PHIs;
 111
 112 private:
 113   /// The branch condition determined by AnalyzeBranch.
 114   SmallVector<MachineOperand, 4> Cond;
 115
 116   /// Instructions in Head that define values used by the conditional blocks.
 117   /// The hoisted instructions must be inserted after these instructions.
 118   SmallPtrSet<MachineInstr*, 8> InsertAfter;
 119
 120   /// Register units clobbered by the conditional blocks.
 121   BitVector ClobberedRegUnits;
 122
 123   // Scratch pad for findInsertionPoint.
 124   SparseSet<unsigned> LiveRegUnits;
 125
 126   /// Insertion point in Head for speculatively executed instructions form TBB
 127   /// and FBB.
 128   MachineBasicBlock::iterator InsertionPoint;
 129
 130   /// Return true if all non-terminator instructions in MBB can be safely
 131   /// speculated.
 132   bool canSpeculateInstrs(MachineBasicBlock *MBB);
 133
 134   /// Find a valid insertion point in Head.
 135   bool findInsertionPoint();
 136
 137 public:
 138   /// runOnMachineFunction - Initialize per-function data structures.
 139   void runOnMachineFunction(MachineFunction &MF) {
 140     TII = MF.getTarget().getInstrInfo();
 141     TRI = MF.getTarget().getRegisterInfo();
 142     MRI = &MF.getRegInfo();
 143     LiveRegUnits.clear();
 144     LiveRegUnits.setUniverse(TRI->getNumRegUnits());
 145     ClobberedRegUnits.clear();
 146     ClobberedRegUnits.resize(TRI->getNumRegUnits());
 147   }
 148
 149   /// canConvertIf - If the sub-CFG headed by MBB can be if-converted,
 150   /// initialize the internal state, and return true.
 151   bool canConvertIf(MachineBasicBlock *MBB);
 152
 153   /// convertIf - If-convert the last block passed to canConvertIf(), assuming
 154   /// it is possible. Add any erased blocks to RemovedBlocks.
 155   void convertIf(SmallVectorImpl<MachineBasicBlock*> &RemovedBlocks);
 156 };
 157 } // end anonymous namespace
 158
 159
 160 /// canSpeculateInstrs - Returns true if all the instructions in MBB can safely
 161 /// be speculated. The terminators are not considered.
 162 ///
 163 /// If instructions use any values that are defined in the head basic block,
 164 /// the defining instructions are added to InsertAfter.
 165 ///
 166 /// Any clobbered regunits are added to ClobberedRegUnits.
 167 ///
 168 bool SSAIfConv::canSpeculateInstrs(MachineBasicBlock *MBB) {
 169   // Reject any live-in physregs. It's probably CPSR/EFLAGS, and very hard to
 170   // get right.
 171   if (!MBB->livein_empty()) {
 172     DEBUG(dbgs() << "BB#" << MBB->getNumber() << " has live-ins.\n");
 173     return false;
 174   }
 175
 176   unsigned InstrCount = 0;
 177
 178   // Check all instructions, except the terminators. It is assumed that
 179   // terminators never have side effects or define any used register values.
 180   for (MachineBasicBlock::iterator I = MBB->begin(),
 181        E = MBB->getFirstTerminator(); I != E; ++I) {
 182     if (I->isDebugValue())
 183       continue;
 184
 185     if (++InstrCount > BlockInstrLimit && !Stress) {
 186       DEBUG(dbgs() << "BB#" << MBB->getNumber() << " has more than "
 187                    << BlockInstrLimit << " instructions.\n");
 188       return false;
 189     }
 190
 191     // There shouldn't normally be any phis in a single-predecessor block.
 192     if (I->isPHI()) {
 193       DEBUG(dbgs() << "Can't hoist: " << *I);
 194       return false;
 195     }
 196
 197     // Don't speculate loads. Note that it may be possible and desirable to
 198     // speculate GOT or constant pool loads that are guaranteed not to trap,
 199     // but we don't support that for now.
 200     if (I->mayLoad()) {
 201       DEBUG(dbgs() << "Won't speculate load: " << *I);
 202       return false;
 203     }
 204
 205     // We never speculate stores, so an AA pointer isn't necessary.
 206     bool DontMoveAcrossStore = true;
 207     if (!I->isSafeToMove(TII, 0, DontMoveAcrossStore)) {
 208       DEBUG(dbgs() << "Can't speculate: " << *I);
 209       return false;
 210     }
 211
 212     // Check for any dependencies on Head instructions.
 213     for (MIOperands MO(I); MO.isValid(); ++MO) {
 214       if (MO->isRegMask()) {
 215         DEBUG(dbgs() << "Won't speculate regmask: " << *I);
 216         return false;
 217       }
 218       if (!MO->isReg())
 219         continue;
 220       unsigned Reg = MO->getReg();
 221
 222       // Remember clobbered regunits.
 223       if (MO->isDef() && TargetRegisterInfo::isPhysicalRegister(Reg))
 224         for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units)
 225           ClobberedRegUnits.set(*Units);
 226
 227       if (!MO->readsReg() || !TargetRegisterInfo::isVirtualRegister(Reg))
 228         continue;
 229       MachineInstr *DefMI = MRI->getVRegDef(Reg);
 230       if (!DefMI || DefMI->getParent() != Head)
 231         continue;
 232       if (InsertAfter.insert(DefMI))
 233         DEBUG(dbgs() << "BB#" << MBB->getNumber() << " depends on " << *DefMI);
 234       if (DefMI->isTerminator()) {
 235         DEBUG(dbgs() << "Can't insert instructions below terminator.\n");
 236         return false;
 237       }
 238     }
 239   }
 240   return true;
 241 }
 242
 243
 244 /// Find an insertion point in Head for the speculated instructions. The
 245 /// insertion point must be:
 246 ///
 247 /// 1. Before any terminators.
 248 /// 2. After any instructions in InsertAfter.
 249 /// 3. Not have any clobbered regunits live.
 250 ///
 251 /// This function sets InsertionPoint and returns true when successful, it
 252 /// returns false if no valid insertion point could be found.
 253 ///
 254 bool SSAIfConv::findInsertionPoint() {
 255   // Keep track of live regunits before the current position.
 256   // Only track RegUnits that are also in ClobberedRegUnits.
 257   LiveRegUnits.clear();
 258   SmallVector<unsigned, 8> Reads;
 259   MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator();
 260   MachineBasicBlock::iterator I = Head->end();
 261   MachineBasicBlock::iterator B = Head->begin();
 262   while (I != B) {
 263     --I;
 264     // Some of the conditional code depends in I.
 265     if (InsertAfter.count(I)) {
 266       DEBUG(dbgs() << "Can't insert code after " << *I);
 267       return false;
 268     }
 269
 270     // Update live regunits.
 271     for (MIOperands MO(I); MO.isValid(); ++MO) {
 272       // We're ignoring regmask operands. That is conservatively correct.
 273       if (!MO->isReg())
 274         continue;
 275       unsigned Reg = MO->getReg();
 276       if (!TargetRegisterInfo::isPhysicalRegister(Reg))
 277         continue;
 278       // I clobbers Reg, so it isn't live before I.
 279       if (MO->isDef())
 280         for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units)
 281           LiveRegUnits.erase(*Units);
 282       // Unless I reads Reg.
 283       if (MO->readsReg())
 284         Reads.push_back(Reg);
 285     }
 286     // Anything read by I is live before I.
 287     while (!Reads.empty())
 288       for (MCRegUnitIterator Units(Reads.pop_back_val(), TRI); Units.isValid();
 289            ++Units)
 290         if (ClobberedRegUnits.test(*Units))
 291           LiveRegUnits.insert(*Units);
 292
 293     // We can't insert before a terminator.
 294     if (I != FirstTerm && I->isTerminator())
 295       continue;
 296
 297     // Some of the clobbered registers are live before I, not a valid insertion
 298     // point.
 299     if (!LiveRegUnits.empty()) {
 300       DEBUG({
 301         dbgs() << "Would clobber";
 302         for (SparseSet<unsigned>::const_iterator
 303              i = LiveRegUnits.begin(), e = LiveRegUnits.end(); i != e; ++i)
 304           dbgs() << ' ' << PrintRegUnit(*i, TRI);
 305         dbgs() << " live before " << *I;
 306       });
 307       continue;
 308     }
 309
 310     // This is a valid insertion point.
 311     InsertionPoint = I;
 312     DEBUG(dbgs() << "Can insert before " << *I);
 313     return true;
 314   }
 315   DEBUG(dbgs() << "No legal insertion point found.\n");
 316   return false;
 317 }
 318
 319
 320
 321 /// canConvertIf - analyze the sub-cfg rooted in MBB, and return true if it is
 322 /// a potential candidate for if-conversion. Fill out the internal state.
 323 ///
 324 bool SSAIfConv::canConvertIf(MachineBasicBlock *MBB) {
 325   Head = MBB;
 326   TBB = FBB = Tail = 0;
 327
 328   if (Head->succ_size() != 2)
 329     return false;
 330   MachineBasicBlock *Succ0 = Head->succ_begin()[0];
 331   MachineBasicBlock *Succ1 = Head->succ_begin()[1];
 332
 333   // Canonicalize so Succ0 has MBB as its single predecessor.
 334   if (Succ0->pred_size() != 1)
 335     std::swap(Succ0, Succ1);
 336
 337   if (Succ0->pred_size() != 1 || Succ0->succ_size() != 1)
 338     return false;
 339
 340   // We could support additional Tail predecessors by updating phis instead of
 341   // eliminating them. Let's see an example where it matters first.
 342   Tail = Succ0->succ_begin()[0];
 343   if (Tail->pred_size() != 2)
 344     return false;
 345
 346   // This is not a triangle.
 347   if (Tail != Succ1) {
 348     // Check for a diamond. We won't deal with any critical edges.
 349     if (Succ1->pred_size() != 1 || Succ1->succ_size() != 1 ||
 350         Succ1->succ_begin()[0] != Tail)
 351       return false;
 352     DEBUG(dbgs() << "\nDiamond: BB#" << Head->getNumber()
 353                  << " -> BB#" << Succ0->getNumber()
 354                  << "/BB#" << Succ1->getNumber()
 355                  << " -> BB#" << Tail->getNumber() << '\n');
 356
 357     // Live-in physregs are tricky to get right when speculating code.
 358     if (!Tail->livein_empty()) {
 359       DEBUG(dbgs() << "Tail has live-ins.\n");
 360       return false;
 361     }
 362   } else {
 363     DEBUG(dbgs() << "\nTriangle: BB#" << Head->getNumber()
 364                  << " -> BB#" << Succ0->getNumber()
 365                  << " -> BB#" << Tail->getNumber() << '\n');
 366   }
 367
 368   // This is a triangle or a diamond.
 369   // If Tail doesn't have any phis, there must be side effects.
 370   if (Tail->empty() || !Tail->front().isPHI()) {
 371     DEBUG(dbgs() << "No phis in tail.\n");
 372     return false;
 373   }
 374
 375   // The branch we're looking to eliminate must be analyzable.
 376   Cond.clear();
 377   if (TII->AnalyzeBranch(*Head, TBB, FBB, Cond)) {
 378     DEBUG(dbgs() << "Branch not analyzable.\n");
 379     return false;
 380   }
 381
 382   // This is weird, probably some sort of degenerate CFG.
 383   if (!TBB) {
 384     DEBUG(dbgs() << "AnalyzeBranch didn't find conditional branch.\n");
 385     return false;
 386   }
 387
 388   // AnalyzeBranch doesn't set FBB on a fall-through branch.
 389   // Make sure it is always set.
 390   FBB = TBB == Succ0 ? Succ1 : Succ0;
 391
 392   // Any phis in the tail block must be convertible to selects.
 393   PHIs.clear();
 394   MachineBasicBlock *TPred = TBB == Tail ? Head : TBB;
 395   MachineBasicBlock *FPred = FBB == Tail ? Head : FBB;
 396   for (MachineBasicBlock::iterator I = Tail->begin(), E = Tail->end();
 397        I != E && I->isPHI(); ++I) {
 398     PHIs.push_back(&*I);
 399     PHIInfo &PI = PHIs.back();
 400     // Find PHI operands corresponding to TPred and FPred.
 401     for (unsigned i = 1; i != PI.PHI->getNumOperands(); i += 2) {
 402       if (PI.PHI->getOperand(i+1).getMBB() == TPred)
 403         PI.TReg = PI.PHI->getOperand(i).getReg();
 404       if (PI.PHI->getOperand(i+1).getMBB() == FPred)
 405         PI.FReg = PI.PHI->getOperand(i).getReg();
 406     }
 407     assert(TargetRegisterInfo::isVirtualRegister(PI.TReg) && "Bad PHI");
 408     assert(TargetRegisterInfo::isVirtualRegister(PI.FReg) && "Bad PHI");
 409
 410     // Get target information.
 411     if (!TII->canInsertSelect(*Head, Cond, PI.TReg, PI.FReg,
 412                               PI.CondCycles, PI.TCycles, PI.FCycles)) {
 413       DEBUG(dbgs() << "Can't convert: " << *PI.PHI);
 414       return false;
 415     }
 416   }
 417
 418   // Check that the conditional instructions can be speculated.
 419   InsertAfter.clear();
 420   ClobberedRegUnits.reset();
 421   if (TBB != Tail && !canSpeculateInstrs(TBB))
 422     return false;
 423   if (FBB != Tail && !canSpeculateInstrs(FBB))
 424     return false;
 425
 426   // Try to find a valid insertion point for the speculated instructions in the
 427   // head basic block.
 428   if (!findInsertionPoint())
 429     return false;
 430
 431   return true;
 432 }
 433
 434
 435 /// convertIf - Execute the if conversion after canConvertIf has determined the
 436 /// feasibility.
 437 ///
 438 /// Any basic blocks erased will be added to RemovedBlocks.
 439 ///
 440 void SSAIfConv::convertIf(SmallVectorImpl<MachineBasicBlock*> &RemovedBlocks) {
 441   assert(Head && Tail && TBB && FBB && "Call canConvertIf first.");
 442
 443   // Move all instructions into Head, except for the terminators.
 444   if (TBB != Tail)
 445     Head->splice(InsertionPoint, TBB, TBB->begin(), TBB->getFirstTerminator());
 446   if (FBB != Tail)
 447     Head->splice(InsertionPoint, FBB, FBB->begin(), FBB->getFirstTerminator());
 448
 449   MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator();
 450   assert(FirstTerm != Head->end() && "No terminators");
 451   DebugLoc HeadDL = FirstTerm->getDebugLoc();
 452
 453   // Convert all PHIs to select instructions inserted before FirstTerm.
 454   for (unsigned i = 0, e = PHIs.size(); i != e; ++i) {
 455     PHIInfo &PI = PHIs[i];
 456     DEBUG(dbgs() << "If-converting " << *PI.PHI);
 457     assert(PI.PHI->getNumOperands() == 5 && "Unexpected PHI operands.");
 458     unsigned DstReg = PI.PHI->getOperand(0).getReg();
 459     TII->insertSelect(*Head, FirstTerm, HeadDL, DstReg, Cond, PI.TReg, PI.FReg);
 460     DEBUG(dbgs() << "          --> " << *llvm::prior(FirstTerm));
 461     PI.PHI->eraseFromParent();
 462     PI.PHI = 0;
 463   }
 464
 465   // Fix up the CFG, temporarily leave Head without any successors.
 466   Head->removeSuccessor(TBB);
 467   Head->removeSuccessor(FBB);
 468   if (TBB != Tail)
 469     TBB->removeSuccessor(Tail);
 470   if (FBB != Tail)
 471     FBB->removeSuccessor(Tail);
 472
 473   // Fix up Head's terminators.
 474   // It should become a single branch or a fallthrough.
 475   TII->RemoveBranch(*Head);
 476
 477   // Erase the now empty conditional blocks. It is likely that Head can fall
 478   // through to Tail, and we can join the two blocks.
 479   if (TBB != Tail) {
 480     RemovedBlocks.push_back(TBB);
 481     TBB->eraseFromParent();
 482   }
 483   if (FBB != Tail) {
 484     RemovedBlocks.push_back(FBB);
 485     FBB->eraseFromParent();
 486   }
 487
 488   assert(Head->succ_empty() && "Additional head successors?");
 489   if (Head->isLayoutSuccessor(Tail)) {
 490     // Splice Tail onto the end of Head.
 491     DEBUG(dbgs() << "Joining tail BB#" << Tail->getNumber()
 492                  << " into head BB#" << Head->getNumber() << '\n');
 493     Head->splice(Head->end(), Tail,
 494                      Tail->begin(), Tail->end());
 495     Head->transferSuccessorsAndUpdatePHIs(Tail);
 496     RemovedBlocks.push_back(Tail);
 497     Tail->eraseFromParent();
 498   } else {
 499     // We need a branch to Tail, let code placement work it out later.
 500     DEBUG(dbgs() << "Converting to unconditional branch.\n");
 501     SmallVector<MachineOperand, 0> EmptyCond;
 502     TII->InsertBranch(*Head, Tail, 0, EmptyCond, HeadDL);
 503     Head->addSuccessor(Tail);
 504   }
 505   DEBUG(dbgs() << *Head);
 506 }
 507
 508
 509 //===----------------------------------------------------------------------===//
 510 //                           EarlyIfConverter Pass
 511 //===----------------------------------------------------------------------===//
 512
 513 namespace {
 514 class EarlyIfConverter : public MachineFunctionPass {
 515   const TargetInstrInfo *TII;
 516   const TargetRegisterInfo *TRI;
 517   const MCSchedModel *SchedModel;
 518   MachineRegisterInfo *MRI;
 519   MachineDominatorTree *DomTree;
 520   MachineLoopInfo *Loops;
 521   MachineTraceMetrics *Traces;
 522   MachineTraceMetrics::Ensemble *MinInstr;
 523   SSAIfConv IfConv;
 524
 525 public:
 526   static char ID;
 527   EarlyIfConverter() : MachineFunctionPass(ID) {}
 528   void getAnalysisUsage(AnalysisUsage &AU) const;
 529   bool runOnMachineFunction(MachineFunction &MF);
 530
 531 private:
 532   bool tryConvertIf(MachineBasicBlock*);
 533   void updateDomTree(ArrayRef<MachineBasicBlock*> Removed);
 534   void updateLoops(ArrayRef<MachineBasicBlock*> Removed);
 535   void invalidateTraces();
 536   bool shouldConvertIf();
 537 };
 538 } // end anonymous namespace
 539
 540 char EarlyIfConverter::ID = 0;
 541 char &llvm::EarlyIfConverterID = EarlyIfConverter::ID;
 542
 543 INITIALIZE_PASS_BEGIN(EarlyIfConverter,
 544                       "early-ifcvt", "Early If Converter", false, false)
 545 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
 546 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
 547 INITIALIZE_PASS_DEPENDENCY(MachineTraceMetrics)
 548 INITIALIZE_PASS_END(EarlyIfConverter,
 549                       "early-ifcvt", "Early If Converter", false, false)
 550
 551 void EarlyIfConverter::getAnalysisUsage(AnalysisUsage &AU) const {
 552   AU.addRequired<MachineBranchProbabilityInfo>();
 553   AU.addRequired<MachineDominatorTree>();
 554   AU.addPreserved<MachineDominatorTree>();
 555   AU.addRequired<MachineLoopInfo>();
 556   AU.addPreserved<MachineLoopInfo>();
 557   AU.addRequired<MachineTraceMetrics>();
 558   AU.addPreserved<MachineTraceMetrics>();
 559   MachineFunctionPass::getAnalysisUsage(AU);
 560 }
 561
 562 /// Update the dominator tree after if-conversion erased some blocks.
 563 void EarlyIfConverter::updateDomTree(ArrayRef<MachineBasicBlock*> Removed) {
 564   // convertIf can remove TBB, FBB, and Tail can be merged into Head.
 565   // TBB and FBB should not dominate any blocks.
 566   // Tail children should be transferred to Head.
 567   MachineDomTreeNode *HeadNode = DomTree->getNode(IfConv.Head);
 568   for (unsigned i = 0, e = Removed.size(); i != e; ++i) {
 569     MachineDomTreeNode *Node = DomTree->getNode(Removed[i]);
 570     assert(Node != HeadNode && "Cannot erase the head node");
 571     while (Node->getNumChildren()) {
 572       assert(Node->getBlock() == IfConv.Tail && "Unexpected children");
 573       DomTree->changeImmediateDominator(Node->getChildren().back(), HeadNode);
 574     }
 575     DomTree->eraseNode(Removed[i]);
 576   }
 577 }
 578
 579 /// Update LoopInfo after if-conversion.
 580 void EarlyIfConverter::updateLoops(ArrayRef<MachineBasicBlock*> Removed) {
 581   if (!Loops)
 582     return;
 583   // If-conversion doesn't change loop structure, and it doesn't mess with back
 584   // edges, so updating LoopInfo is simply removing the dead blocks.
 585   for (unsigned i = 0, e = Removed.size(); i != e; ++i)
 586     Loops->removeBlock(Removed[i]);
 587 }
 588
 589 /// Invalidate MachineTraceMetrics before if-conversion.
 590 void EarlyIfConverter::invalidateTraces() {
 591   Traces->verifyAnalysis();
 592   Traces->invalidate(IfConv.Head);
 593   Traces->invalidate(IfConv.Tail);
 594   Traces->invalidate(IfConv.TBB);
 595   Traces->invalidate(IfConv.FBB);
 596   DEBUG(if (MinInstr) MinInstr->print(dbgs()));
 597   Traces->verifyAnalysis();
 598 }
 599
 600 /// Apply cost model and heuristics to the if-conversion in IfConv.
 601 /// Return true if the conversion is a good idea.
 602 ///
 603 bool EarlyIfConverter::shouldConvertIf() {
 604   if (!MinInstr)
 605     MinInstr = Traces->getEnsemble(MachineTraceMetrics::TS_MinInstrCount);
 606
 607   // Compare the critical path through TBB and FBB. If the difference is
 608   // greater than the branch misprediction penalty, it would never pay to
 609   // if-convert. The triangle/diamond topology guarantees that these traces
 610   // have the same head and tail, so they can be compared.
 611   MachineTraceMetrics::Trace TBBTrace = MinInstr->getTrace(IfConv.TBB);
 612   MachineTraceMetrics::Trace FBBTrace = MinInstr->getTrace(IfConv.FBB);
 613   DEBUG(dbgs() << "TBB: " << TBBTrace << "FBB: " << FBBTrace);
 614   unsigned TBBCrit = TBBTrace.getCriticalPath();
 615   unsigned FBBCrit = FBBTrace.getCriticalPath();
 616   unsigned ExtraCrit = TBBCrit > FBBCrit ? TBBCrit-FBBCrit : FBBCrit-TBBCrit;
 617   if (ExtraCrit >= SchedModel->MispredictPenalty) {
 618     DEBUG(dbgs() << "Critical path difference larger than "
 619                  << SchedModel->MispredictPenalty << ".\n");
 620     return false;
 621   }
 622   return true;
 623 }
 624
 625 /// Attempt repeated if-conversion on MBB, return true if successful.
 626 ///
 627 bool EarlyIfConverter::tryConvertIf(MachineBasicBlock *MBB) {
 628   bool Changed = false;
 629   while (IfConv.canConvertIf(MBB) && shouldConvertIf()) {
 630     // If-convert MBB and update analyses.
 631     invalidateTraces();
 632     SmallVector<MachineBasicBlock*, 4> RemovedBlocks;
 633     IfConv.convertIf(RemovedBlocks);
 634     Changed = true;
 635     updateDomTree(RemovedBlocks);
 636     updateLoops(RemovedBlocks);
 637   }
 638   return Changed;
 639 }
 640
 641 bool EarlyIfConverter::runOnMachineFunction(MachineFunction &MF) {
 642   DEBUG(dbgs() << "********** EARLY IF-CONVERSION **********\n"
 643                << "********** Function: "
 644                << ((Value*)MF.getFunction())->getName() << '\n');
 645   TII = MF.getTarget().getInstrInfo();
 646   TRI = MF.getTarget().getRegisterInfo();
 647   SchedModel = MF.getTarget().getInstrItineraryData()->SchedModel;
 648   MRI = &MF.getRegInfo();
 649   DomTree = &getAnalysis<MachineDominatorTree>();
 650   Loops = getAnalysisIfAvailable<MachineLoopInfo>();
 651   Traces = &getAnalysis<MachineTraceMetrics>();
 652   MinInstr = 0;
 653
 654   bool Changed = false;
 655   IfConv.runOnMachineFunction(MF);
 656
 657   // Visit blocks in dominator tree post-order. The post-order enables nested
 658   // if-conversion in a single pass. The tryConvertIf() function may erase
 659   // blocks, but only blocks dominated by the head block. This makes it safe to
 660   // update the dominator tree while the post-order iterator is still active.
 661   for (po_iterator<MachineDominatorTree*>
 662        I = po_begin(DomTree), E = po_end(DomTree); I != E; ++I)
 663     if (tryConvertIf(I->getBlock()))
 664       Changed = true;
 665
 666   MF.verify(this, "After early if-conversion");
 667   return Changed;
 668 }