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