lib/CodeGen/ScheduleDAGInstrs.cpp

   1 //===---- ScheduleDAGInstrs.cpp - MachineInstr Rescheduling ---------------===//
   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 // This implements the ScheduleDAGInstrs class, which implements re-scheduling
  11 // of MachineInstrs.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #define DEBUG_TYPE "sched-instrs"
  16 #include "ScheduleDAGInstrs.h"
  17 #include "llvm/Analysis/AliasAnalysis.h"
  18 #include "llvm/CodeGen/MachineDominators.h"
  19 #include "llvm/CodeGen/MachineFunctionPass.h"
  20 #include "llvm/CodeGen/MachineLoopInfo.h"
  21 #include "llvm/CodeGen/MachineRegisterInfo.h"
  22 #include "llvm/CodeGen/PseudoSourceValue.h"
  23 #include "llvm/Target/TargetMachine.h"
  24 #include "llvm/Target/TargetInstrInfo.h"
  25 #include "llvm/Target/TargetRegisterInfo.h"
  26 #include "llvm/Target/TargetSubtarget.h"
  27 #include "llvm/Support/Compiler.h"
  28 #include "llvm/Support/Debug.h"
  29 #include "llvm/Support/raw_ostream.h"
  30 #include "llvm/ADT/SmallSet.h"
  31 #include <map>
  32 using namespace llvm;
  33
  34 namespace {
  35   class VISIBILITY_HIDDEN LoopDependencies {
  36     const MachineLoopInfo &MLI;
  37     const MachineDominatorTree &MDT;
  38
  39   public:
  40     typedef std::map<unsigned, std::pair<const MachineOperand *, unsigned> >
  41       LoopDeps;
  42     LoopDeps Deps;
  43
  44     LoopDependencies(const MachineLoopInfo &mli,
  45                      const MachineDominatorTree &mdt) :
  46       MLI(mli), MDT(mdt) {}
  47
  48     void VisitLoop(const MachineLoop *Loop) {
  49       Deps.clear();
  50       MachineBasicBlock *Header = Loop->getHeader();
  51       SmallSet<unsigned, 8> LoopLiveIns;
  52       for (MachineBasicBlock::livein_iterator LI = Header->livein_begin(),
  53            LE = Header->livein_end(); LI != LE; ++LI)
  54         LoopLiveIns.insert(*LI);
  55
  56       const MachineDomTreeNode *Node = MDT.getNode(Header);
  57       const MachineBasicBlock *MBB = Node->getBlock();
  58       assert(Loop->contains(MBB) &&
  59              "Loop does not contain header!");
  60       VisitRegion(Node, MBB, Loop, LoopLiveIns);
  61     }
  62
  63   private:
  64     void VisitRegion(const MachineDomTreeNode *Node,
  65                      const MachineBasicBlock *MBB,
  66                      const MachineLoop *Loop,
  67                      const SmallSet<unsigned, 8> &LoopLiveIns) {
  68       unsigned Count = 0;
  69       for (MachineBasicBlock::const_iterator I = MBB->begin(), E = MBB->end();
  70            I != E; ++I, ++Count) {
  71         const MachineInstr *MI = I;
  72         for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
  73           const MachineOperand &MO = MI->getOperand(i);
  74           if (!MO.isReg() || !MO.isUse())
  75             continue;
  76           unsigned MOReg = MO.getReg();
  77           if (LoopLiveIns.count(MOReg))
  78             Deps.insert(std::make_pair(MOReg, std::make_pair(&MO, Count)));
  79         }
  80       }
  81
  82       const std::vector<MachineDomTreeNode*> &Children = Node->getChildren();
  83       for (std::vector<MachineDomTreeNode*>::const_iterator I =
  84            Children.begin(), E = Children.end(); I != E; ++I) {
  85         const MachineDomTreeNode *ChildNode = *I;
  86         MachineBasicBlock *ChildBlock = ChildNode->getBlock();
  87         if (Loop->contains(ChildBlock))
  88           VisitRegion(ChildNode, ChildBlock, Loop, LoopLiveIns);
  89       }
  90     }
  91   };
  92 }
  93
  94 ScheduleDAGInstrs::ScheduleDAGInstrs(MachineFunction &mf,
  95                                      const MachineLoopInfo &mli,
  96                                      const MachineDominatorTree &mdt)
  97   : ScheduleDAG(mf), MLI(mli), MDT(mdt) {}
  98
  99 /// getOpcode - If this is an Instruction or a ConstantExpr, return the
 100 /// opcode value. Otherwise return UserOp1.
 101 static unsigned getOpcode(const Value *V) {
 102   if (const Instruction *I = dyn_cast<Instruction>(V))
 103     return I->getOpcode();
 104   if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
 105     return CE->getOpcode();
 106   // Use UserOp1 to mean there's no opcode.
 107   return Instruction::UserOp1;
 108 }
 109
 110 /// getUnderlyingObjectFromInt - This is the function that does the work of
 111 /// looking through basic ptrtoint+arithmetic+inttoptr sequences.
 112 static const Value *getUnderlyingObjectFromInt(const Value *V) {
 113   do {
 114     if (const User *U = dyn_cast<User>(V)) {
 115       // If we find a ptrtoint, we can transfer control back to the
 116       // regular getUnderlyingObjectFromInt.
 117       if (getOpcode(U) == Instruction::PtrToInt)
 118         return U->getOperand(0);
 119       // If we find an add of a constant or a multiplied value, it's
 120       // likely that the other operand will lead us to the base
 121       // object. We don't have to worry about the case where the
 122       // object address is somehow being computed bt the multiply,
 123       // because our callers only care when the result is an
 124       // identifibale object.
 125       if (getOpcode(U) != Instruction::Add ||
 126           (!isa<ConstantInt>(U->getOperand(1)) &&
 127            getOpcode(U->getOperand(1)) != Instruction::Mul))
 128         return V;
 129       V = U->getOperand(0);
 130     } else {
 131       return V;
 132     }
 133     assert(isa<IntegerType>(V->getType()) && "Unexpected operand type!");
 134   } while (1);
 135 }
 136
 137 /// getUnderlyingObject - This is a wrapper around Value::getUnderlyingObject
 138 /// and adds support for basic ptrtoint+arithmetic+inttoptr sequences.
 139 static const Value *getUnderlyingObject(const Value *V) {
 140   // First just call Value::getUnderlyingObject to let it do what it does.
 141   do {
 142     V = V->getUnderlyingObject();
 143     // If it found an inttoptr, use special code to continue climing.
 144     if (getOpcode(V) != Instruction::IntToPtr)
 145       break;
 146     const Value *O = getUnderlyingObjectFromInt(cast<User>(V)->getOperand(0));
 147     // If that succeeded in finding a pointer, continue the search.
 148     if (!isa<PointerType>(O->getType()))
 149       break;
 150     V = O;
 151   } while (1);
 152   return V;
 153 }
 154
 155 /// getUnderlyingObjectForInstr - If this machine instr has memory reference
 156 /// information and it can be tracked to a normal reference to a known
 157 /// object, return the Value for that object. Otherwise return null.
 158 static const Value *getUnderlyingObjectForInstr(const MachineInstr *MI) {
 159   if (!MI->hasOneMemOperand() ||
 160       !MI->memoperands_begin()->getValue() ||
 161       MI->memoperands_begin()->isVolatile())
 162     return 0;
 163
 164   const Value *V = MI->memoperands_begin()->getValue();
 165   if (!V)
 166     return 0;
 167
 168   V = getUnderlyingObject(V);
 169   if (!isa<PseudoSourceValue>(V) && !isIdentifiedObject(V))
 170     return 0;
 171
 172   return V;
 173 }
 174
 175 void ScheduleDAGInstrs::BuildSchedGraph() {
 176   SUnits.reserve(BB->size());
 177
 178   // We build scheduling units by walking a block's instruction list from bottom
 179   // to top.
 180
 181   // Remember where a generic side-effecting instruction is as we procede. If
 182   // ChainMMO is null, this is assumed to have arbitrary side-effects. If
 183   // ChainMMO is non-null, then Chain makes only a single memory reference.
 184   SUnit *Chain = 0;
 185   MachineMemOperand *ChainMMO = 0;
 186
 187   // Memory references to specific known memory locations are tracked so that
 188   // they can be given more precise dependencies.
 189   std::map<const Value *, SUnit *> MemDefs;
 190   std::map<const Value *, std::vector<SUnit *> > MemUses;
 191
 192   // If we have an SUnit which is representing a terminator instruction, we
 193   // can use it as a place-holder successor for inter-block dependencies.
 194   SUnit *Terminator = 0;
 195
 196   // Terminators can perform control transfers, we we need to make sure that
 197   // all the work of the block is done before the terminator. Labels can
 198   // mark points of interest for various types of meta-data (eg. EH data),
 199   // and we need to make sure nothing is scheduled around them.
 200   SUnit *SchedulingBarrier = 0;
 201
 202   LoopDependencies LoopRegs(MLI, MDT);
 203
 204   // Track which regs are live into a loop, to help guide back-edge-aware
 205   // scheduling.
 206   SmallSet<unsigned, 8> LoopLiveInRegs;
 207   if (MachineLoop *ML = MLI.getLoopFor(BB))
 208     if (BB == ML->getLoopLatch()) {
 209       MachineBasicBlock *Header = ML->getHeader();
 210       for (MachineBasicBlock::livein_iterator I = Header->livein_begin(),
 211            E = Header->livein_end(); I != E; ++I)
 212         LoopLiveInRegs.insert(*I);
 213       LoopRegs.VisitLoop(ML);
 214     }
 215
 216   // Check to see if the scheduler cares about latencies.
 217   bool UnitLatencies = ForceUnitLatencies();
 218
 219   // Ask the target if address-backscheduling is desirable, and if so how much.
 220   unsigned SpecialAddressLatency =
 221     TM.getSubtarget<TargetSubtarget>().getSpecialAddressLatency();
 222
 223   for (MachineBasicBlock::iterator MII = End, MIE = Begin;
 224        MII != MIE; --MII) {
 225     MachineInstr *MI = prior(MII);
 226     const TargetInstrDesc &TID = MI->getDesc();
 227     SUnit *SU = NewSUnit(MI);
 228
 229     // Assign the Latency field of SU using target-provided information.
 230     if (UnitLatencies)
 231       SU->Latency = 1;
 232     else
 233       ComputeLatency(SU);
 234
 235     // Add register-based dependencies (data, anti, and output).
 236     for (unsigned j = 0, n = MI->getNumOperands(); j != n; ++j) {
 237       const MachineOperand &MO = MI->getOperand(j);
 238       if (!MO.isReg()) continue;
 239       unsigned Reg = MO.getReg();
 240       if (Reg == 0) continue;
 241
 242       assert(TRI->isPhysicalRegister(Reg) && "Virtual register encountered!");
 243       std::vector<SUnit *> &UseList = Uses[Reg];
 244       std::vector<SUnit *> &DefList = Defs[Reg];
 245       // Optionally add output and anti dependencies.
 246       // TODO: Using a latency of 1 here assumes there's no cost for
 247       //       reusing registers.
 248       SDep::Kind Kind = MO.isUse() ? SDep::Anti : SDep::Output;
 249       for (unsigned i = 0, e = DefList.size(); i != e; ++i) {
 250         SUnit *DefSU = DefList[i];
 251         if (DefSU != SU &&
 252             (Kind != SDep::Output || !MO.isDead() ||
 253              !DefSU->getInstr()->registerDefIsDead(Reg)))
 254           DefSU->addPred(SDep(SU, Kind, /*Latency=*/1, /*Reg=*/Reg));
 255       }
 256       for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
 257         std::vector<SUnit *> &DefList = Defs[*Alias];
 258         for (unsigned i = 0, e = DefList.size(); i != e; ++i) {
 259           SUnit *DefSU = DefList[i];
 260           if (DefSU != SU &&
 261               (Kind != SDep::Output || !MO.isDead() ||
 262                !DefSU->getInstr()->registerDefIsDead(Reg)))
 263             DefSU->addPred(SDep(SU, Kind, /*Latency=*/1, /*Reg=*/ *Alias));
 264         }
 265       }
 266
 267       if (MO.isDef()) {
 268         // Add any data dependencies.
 269         unsigned DataLatency = SU->Latency;
 270         for (unsigned i = 0, e = UseList.size(); i != e; ++i) {
 271           SUnit *UseSU = UseList[i];
 272           if (UseSU != SU) {
 273             unsigned LDataLatency = DataLatency;
 274             // Optionally add in a special extra latency for nodes that
 275             // feed addresses.
 276             // TODO: Do this for register aliases too.
 277             if (SpecialAddressLatency != 0 && !UnitLatencies) {
 278               MachineInstr *UseMI = UseSU->getInstr();
 279               const TargetInstrDesc &UseTID = UseMI->getDesc();
 280               int RegUseIndex = UseMI->findRegisterUseOperandIdx(Reg);
 281               assert(RegUseIndex >= 0 && "UseMI doesn's use register!");
 282               if ((UseTID.mayLoad() || UseTID.mayStore()) &&
 283                   (unsigned)RegUseIndex < UseTID.getNumOperands() &&
 284                   UseTID.OpInfo[RegUseIndex].isLookupPtrRegClass())
 285                 LDataLatency += SpecialAddressLatency;
 286             }
 287             UseSU->addPred(SDep(SU, SDep::Data, LDataLatency, Reg));
 288           }
 289         }
 290         for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
 291           std::vector<SUnit *> &UseList = Uses[*Alias];
 292           for (unsigned i = 0, e = UseList.size(); i != e; ++i) {
 293             SUnit *UseSU = UseList[i];
 294             if (UseSU != SU)
 295               UseSU->addPred(SDep(SU, SDep::Data, DataLatency, *Alias));
 296           }
 297         }
 298
 299         // If a def is going to wrap back around to the top of the loop,
 300         // backschedule it.
 301         // TODO: Blocks in loops without terminators can benefit too.
 302         if (!UnitLatencies && Terminator && DefList.empty()) {
 303           LoopDependencies::LoopDeps::iterator I = LoopRegs.Deps.find(Reg);
 304           if (I != LoopRegs.Deps.end()) {
 305             const MachineOperand *UseMO = I->second.first;
 306             unsigned Count = I->second.second;
 307             const MachineInstr *UseMI = UseMO->getParent();
 308             unsigned UseMOIdx = UseMO - &UseMI->getOperand(0);
 309             const TargetInstrDesc &UseTID = UseMI->getDesc();
 310             // TODO: If we knew the total depth of the region here, we could
 311             // handle the case where the whole loop is inside the region but
 312             // is large enough that the isScheduleHigh trick isn't needed.
 313             if (UseMOIdx < UseTID.getNumOperands()) {
 314               // Currently, we only support scheduling regions consisting of
 315               // single basic blocks. Check to see if the instruction is in
 316               // the same region by checking to see if it has the same parent.
 317               if (UseMI->getParent() != MI->getParent()) {
 318                 unsigned Latency = SU->Latency;
 319                 if (UseTID.OpInfo[UseMOIdx].isLookupPtrRegClass())
 320                   Latency += SpecialAddressLatency;
 321                 // This is a wild guess as to the portion of the latency which
 322                 // will be overlapped by work done outside the current
 323                 // scheduling region.
 324                 Latency -= std::min(Latency, Count);
 325                 // Add the artifical edge.
 326                 Terminator->addPred(SDep(SU, SDep::Order, Latency,
 327                                          /*Reg=*/0, /*isNormalMemory=*/false,
 328                                          /*isMustAlias=*/false,
 329                                          /*isArtificial=*/true));
 330               } else if (SpecialAddressLatency > 0 &&
 331                          UseTID.OpInfo[UseMOIdx].isLookupPtrRegClass()) {
 332                 // The entire loop body is within the current scheduling region
 333                 // and the latency of this operation is assumed to be greater
 334                 // than the latency of the loop.
 335                 // TODO: Recursively mark data-edge predecessors as
 336                 //       isScheduleHigh too.
 337                 SU->isScheduleHigh = true;
 338               }
 339             }
 340             LoopRegs.Deps.erase(I);
 341           }
 342         }
 343
 344         UseList.clear();
 345         if (!MO.isDead())
 346           DefList.clear();
 347         DefList.push_back(SU);
 348       } else {
 349         UseList.push_back(SU);
 350       }
 351     }
 352
 353     // Add chain dependencies.
 354     // Note that isStoreToStackSlot and isLoadFromStackSLot are not usable
 355     // after stack slots are lowered to actual addresses.
 356     // TODO: Use an AliasAnalysis and do real alias-analysis queries, and
 357     // produce more precise dependence information.
 358     if (TID.isCall() || TID.isTerminator() || TID.hasUnmodeledSideEffects()) {
 359     new_chain:
 360       // This is the conservative case. Add dependencies on all memory
 361       // references.
 362       if (Chain)
 363         Chain->addPred(SDep(SU, SDep::Order, SU->Latency));
 364       Chain = SU;
 365       for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k)
 366         PendingLoads[k]->addPred(SDep(SU, SDep::Order, SU->Latency));
 367       PendingLoads.clear();
 368       for (std::map<const Value *, SUnit *>::iterator I = MemDefs.begin(),
 369            E = MemDefs.end(); I != E; ++I) {
 370         I->second->addPred(SDep(SU, SDep::Order, SU->Latency));
 371         I->second = SU;
 372       }
 373       for (std::map<const Value *, std::vector<SUnit *> >::iterator I =
 374            MemUses.begin(), E = MemUses.end(); I != E; ++I) {
 375         for (unsigned i = 0, e = I->second.size(); i != e; ++i)
 376           I->second[i]->addPred(SDep(SU, SDep::Order, SU->Latency));
 377         I->second.clear();
 378       }
 379       // See if it is known to just have a single memory reference.
 380       MachineInstr *ChainMI = Chain->getInstr();
 381       const TargetInstrDesc &ChainTID = ChainMI->getDesc();
 382       if (!ChainTID.isCall() && !ChainTID.isTerminator() &&
 383           !ChainTID.hasUnmodeledSideEffects() &&
 384           ChainMI->hasOneMemOperand() &&
 385           !ChainMI->memoperands_begin()->isVolatile() &&
 386           ChainMI->memoperands_begin()->getValue())
 387         // We know that the Chain accesses one specific memory location.
 388         ChainMMO = &*ChainMI->memoperands_begin();
 389       else
 390         // Unknown memory accesses. Assume the worst.
 391         ChainMMO = 0;
 392     } else if (TID.mayStore()) {
 393       if (const Value *V = getUnderlyingObjectForInstr(MI)) {
 394         // A store to a specific PseudoSourceValue. Add precise dependencies.
 395         // Handle the def in MemDefs, if there is one.
 396         std::map<const Value *, SUnit *>::iterator I = MemDefs.find(V);
 397         if (I != MemDefs.end()) {
 398           I->second->addPred(SDep(SU, SDep::Order, SU->Latency, /*Reg=*/0,
 399                                   /*isNormalMemory=*/true));
 400           I->second = SU;
 401         } else {
 402           MemDefs[V] = SU;
 403         }
 404         // Handle the uses in MemUses, if there are any.
 405         std::map<const Value *, std::vector<SUnit *> >::iterator J =
 406           MemUses.find(V);
 407         if (J != MemUses.end()) {
 408           for (unsigned i = 0, e = J->second.size(); i != e; ++i)
 409             J->second[i]->addPred(SDep(SU, SDep::Order, SU->Latency, /*Reg=*/0,
 410                                        /*isNormalMemory=*/true));
 411           J->second.clear();
 412         }
 413         // Add dependencies from all the PendingLoads, since without
 414         // memoperands we must assume they alias anything.
 415         for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k)
 416           PendingLoads[k]->addPred(SDep(SU, SDep::Order, SU->Latency));
 417         // Add a general dependence too, if needed.
 418         if (Chain)
 419           Chain->addPred(SDep(SU, SDep::Order, SU->Latency));
 420       } else
 421         // Treat all other stores conservatively.
 422         goto new_chain;
 423     } else if (TID.mayLoad()) {
 424       if (TII->isInvariantLoad(MI)) {
 425         // Invariant load, no chain dependencies needed!
 426       } else if (const Value *V = getUnderlyingObjectForInstr(MI)) {
 427         // A load from a specific PseudoSourceValue. Add precise dependencies.
 428         std::map<const Value *, SUnit *>::iterator I = MemDefs.find(V);
 429         if (I != MemDefs.end())
 430           I->second->addPred(SDep(SU, SDep::Order, SU->Latency, /*Reg=*/0,
 431                                   /*isNormalMemory=*/true));
 432         MemUses[V].push_back(SU);
 433
 434         // Add a general dependence too, if needed.
 435         if (Chain && (!ChainMMO ||
 436                       (ChainMMO->isStore() || ChainMMO->isVolatile())))
 437           Chain->addPred(SDep(SU, SDep::Order, SU->Latency));
 438       } else if (MI->hasVolatileMemoryRef()) {
 439         // Treat volatile loads conservatively. Note that this includes
 440         // cases where memoperand information is unavailable.
 441         goto new_chain;
 442       } else {
 443         // A normal load. Depend on the general chain, as well as on
 444         // all stores. In the absense of MachineMemOperand information,
 445         // we can't even assume that the load doesn't alias well-behaved
 446         // memory locations.
 447         if (Chain)
 448           Chain->addPred(SDep(SU, SDep::Order, SU->Latency));
 449         for (std::map<const Value *, SUnit *>::iterator I = MemDefs.begin(),
 450              E = MemDefs.end(); I != E; ++I)
 451           I->second->addPred(SDep(SU, SDep::Order, SU->Latency));
 452         PendingLoads.push_back(SU);
 453       }
 454     }
 455
 456     // Add chain edges from terminators and labels to ensure that no
 457     // instructions are scheduled past them.
 458     if (SchedulingBarrier && SU->Succs.empty())
 459       SchedulingBarrier->addPred(SDep(SU, SDep::Order, SU->Latency));
 460     // If we encounter a mid-block label, we need to go back and add
 461     // dependencies on SUnits we've already processed to prevent the
 462     // label from moving downward.
 463     if (MI->isLabel())
 464       for (SUnit *I = SU; I != &SUnits[0]; --I) {
 465         SUnit *SuccSU = SU-1;
 466         SuccSU->addPred(SDep(SU, SDep::Order, SU->Latency));
 467         MachineInstr *SuccMI = SuccSU->getInstr();
 468         if (SuccMI->getDesc().isTerminator() || SuccMI->isLabel())
 469           break;
 470       }
 471     // If this instruction obstructs all scheduling, remember it.
 472     if (TID.isTerminator() || MI->isLabel())
 473       SchedulingBarrier = SU;
 474     // If this instruction is a terminator, remember it.
 475     if (TID.isTerminator())
 476       Terminator = SU;
 477   }
 478
 479   for (int i = 0, e = TRI->getNumRegs(); i != e; ++i) {
 480     Defs[i].clear();
 481     Uses[i].clear();
 482   }
 483   PendingLoads.clear();
 484 }
 485
 486 void ScheduleDAGInstrs::ComputeLatency(SUnit *SU) {
 487   const InstrItineraryData &InstrItins = TM.getInstrItineraryData();
 488
 489   // Compute the latency for the node.  We use the sum of the latencies for
 490   // all nodes flagged together into this SUnit.
 491   SU->Latency =
 492     InstrItins.getLatency(SU->getInstr()->getDesc().getSchedClass());
 493
 494   // Simplistic target-independent heuristic: assume that loads take
 495   // extra time.
 496   if (InstrItins.isEmpty())
 497     if (SU->getInstr()->getDesc().mayLoad())
 498       SU->Latency += 2;
 499 }
 500
 501 void ScheduleDAGInstrs::dumpNode(const SUnit *SU) const {
 502   SU->getInstr()->dump();
 503 }
 504
 505 std::string ScheduleDAGInstrs::getGraphNodeLabel(const SUnit *SU) const {
 506   std::string s;
 507   raw_string_ostream oss(s);
 508   SU->getInstr()->print(oss);
 509   return oss.str();
 510 }
 511
 512 // EmitSchedule - Emit the machine code in scheduled order.
 513 MachineBasicBlock *ScheduleDAGInstrs::EmitSchedule() {
 514   // For MachineInstr-based scheduling, we're rescheduling the instructions in
 515   // the block, so start by removing them from the block.
 516   while (Begin != End) {
 517     MachineBasicBlock::iterator I = Begin;
 518     ++Begin;
 519     BB->remove(I);
 520   }
 521
 522   // Then re-insert them according to the given schedule.
 523   for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
 524     SUnit *SU = Sequence[i];
 525     if (!SU) {
 526       // Null SUnit* is a noop.
 527       EmitNoop();
 528       continue;
 529     }
 530
 531     BB->insert(End, SU->getInstr());
 532   }
 533
 534   return BB;
 535 }