lib/CodeGen/PreAllocSplitting.cpp

   1 //===-- PreAllocSplitting.cpp - Pre-allocation Interval Spltting Pass. ----===//
   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 file implements the machine instruction level pre-register allocation
  11 // live interval splitting pass. It finds live interval barriers, i.e.
  12 // instructions which will kill all physical registers in certain register
  13 // classes, and split all live intervals which cross the barrier.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #define DEBUG_TYPE "pre-alloc-split"
  18 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  19 #include "llvm/CodeGen/LiveStackAnalysis.h"
  20 #include "llvm/CodeGen/MachineDominators.h"
  21 #include "llvm/CodeGen/MachineFrameInfo.h"
  22 #include "llvm/CodeGen/MachineFunctionPass.h"
  23 #include "llvm/CodeGen/MachineLoopInfo.h"
  24 #include "llvm/CodeGen/MachineRegisterInfo.h"
  25 #include "llvm/CodeGen/Passes.h"
  26 #include "llvm/CodeGen/RegisterCoalescer.h"
  27 #include "llvm/Target/TargetInstrInfo.h"
  28 #include "llvm/Target/TargetMachine.h"
  29 #include "llvm/Target/TargetOptions.h"
  30 #include "llvm/Target/TargetRegisterInfo.h"
  31 #include "llvm/Support/CommandLine.h"
  32 #include "llvm/Support/Debug.h"
  33 #include "llvm/ADT/DenseMap.h"
  34 #include "llvm/ADT/DepthFirstIterator.h"
  35 #include "llvm/ADT/SmallPtrSet.h"
  36 #include "llvm/ADT/Statistic.h"
  37 using namespace llvm;
  38
  39 static cl::opt<int> PreSplitLimit("pre-split-limit", cl::init(-1), cl::Hidden);
  40
  41 STATISTIC(NumSplits, "Number of intervals split");
  42 STATISTIC(NumRemats, "Number of intervals split by rematerialization");
  43 STATISTIC(NumFolds, "Number of intervals split with spill folding");
  44
  45 namespace {
  46   class VISIBILITY_HIDDEN PreAllocSplitting : public MachineFunctionPass {
  47     MachineFunction       *CurrMF;
  48     const TargetMachine   *TM;
  49     const TargetInstrInfo *TII;
  50     MachineFrameInfo      *MFI;
  51     MachineRegisterInfo   *MRI;
  52     LiveIntervals         *LIs;
  53     LiveStacks            *LSs;
  54
  55     // Barrier - Current barrier being processed.
  56     MachineInstr          *Barrier;
  57
  58     // BarrierMBB - Basic block where the barrier resides in.
  59     MachineBasicBlock     *BarrierMBB;
  60
  61     // Barrier - Current barrier index.
  62     unsigned              BarrierIdx;
  63
  64     // CurrLI - Current live interval being split.
  65     LiveInterval          *CurrLI;
  66
  67     // CurrSLI - Current stack slot live interval.
  68     LiveInterval          *CurrSLI;
  69
  70     // CurrSValNo - Current val# for the stack slot live interval.
  71     VNInfo                *CurrSValNo;
  72
  73     // IntervalSSMap - A map from live interval to spill slots.
  74     DenseMap<unsigned, int> IntervalSSMap;
  75
  76     // Def2SpillMap - A map from a def instruction index to spill index.
  77     DenseMap<unsigned, unsigned> Def2SpillMap;
  78
  79   public:
  80     static char ID;
  81     PreAllocSplitting() : MachineFunctionPass(&ID) {}
  82
  83     virtual bool runOnMachineFunction(MachineFunction &MF);
  84
  85     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  86       AU.addRequired<LiveIntervals>();
  87       AU.addPreserved<LiveIntervals>();
  88       AU.addRequired<LiveStacks>();
  89       AU.addPreserved<LiveStacks>();
  90       AU.addPreserved<RegisterCoalescer>();
  91       if (StrongPHIElim)
  92         AU.addPreservedID(StrongPHIEliminationID);
  93       else
  94         AU.addPreservedID(PHIEliminationID);
  95       AU.addRequired<MachineDominatorTree>();
  96       AU.addRequired<MachineLoopInfo>();
  97       AU.addPreserved<MachineDominatorTree>();
  98       AU.addPreserved<MachineLoopInfo>();
  99       MachineFunctionPass::getAnalysisUsage(AU);
 100     }
 101
 102     virtual void releaseMemory() {
 103       IntervalSSMap.clear();
 104       Def2SpillMap.clear();
 105     }
 106
 107     virtual const char *getPassName() const {
 108       return "Pre-Register Allocaton Live Interval Splitting";
 109     }
 110
 111     /// print - Implement the dump method.
 112     virtual void print(std::ostream &O, const Module* M = 0) const {
 113       LIs->print(O, M);
 114     }
 115
 116     void print(std::ostream *O, const Module* M = 0) const {
 117       if (O) print(*O, M);
 118     }
 119
 120   private:
 121     MachineBasicBlock::iterator
 122       findNextEmptySlot(MachineBasicBlock*, MachineInstr*,
 123                         unsigned&);
 124
 125     MachineBasicBlock::iterator
 126       findSpillPoint(MachineBasicBlock*, MachineInstr*, MachineInstr*,
 127                      SmallPtrSet<MachineInstr*, 4>&, unsigned&);
 128
 129     MachineBasicBlock::iterator
 130       findRestorePoint(MachineBasicBlock*, MachineInstr*, unsigned,
 131                      SmallPtrSet<MachineInstr*, 4>&, unsigned&);
 132
 133     int CreateSpillStackSlot(unsigned, const TargetRegisterClass *);
 134
 135     bool IsAvailableInStack(MachineBasicBlock*, unsigned, unsigned, unsigned,
 136                             unsigned&, int&) const;
 137
 138     void UpdateSpillSlotInterval(VNInfo*, unsigned, unsigned);
 139
 140     void UpdateRegisterInterval(VNInfo*, unsigned, unsigned);
 141
 142     bool ShrinkWrapToLastUse(MachineBasicBlock*, VNInfo*,
 143                              SmallVector<MachineOperand*, 4>&,
 144                              SmallPtrSet<MachineInstr*, 4>&);
 145
 146     void ShrinkWrapLiveInterval(VNInfo*, MachineBasicBlock*, MachineBasicBlock*,
 147                         MachineBasicBlock*, SmallPtrSet<MachineBasicBlock*, 8>&,
 148                 DenseMap<MachineBasicBlock*, SmallVector<MachineOperand*, 4> >&,
 149                   DenseMap<MachineBasicBlock*, SmallPtrSet<MachineInstr*, 4> >&,
 150                                 SmallVector<MachineBasicBlock*, 4>&);
 151
 152     bool SplitRegLiveInterval(LiveInterval*);
 153
 154     bool SplitRegLiveIntervals(const TargetRegisterClass **);
 155
 156     void RepairLiveInterval(LiveInterval* CurrLI, VNInfo* ValNo,
 157                             MachineInstr* DefMI, unsigned RestoreIdx);
 158
 159     bool createsNewJoin(LiveRange* LR, MachineBasicBlock* DefMBB,
 160                         MachineBasicBlock* BarrierMBB);
 161     bool Rematerialize(unsigned vreg, VNInfo* ValNo,
 162                        MachineInstr* DefMI,
 163                        MachineBasicBlock::iterator RestorePt,
 164                        unsigned RestoreIdx,
 165                        SmallPtrSet<MachineInstr*, 4>& RefsInMBB);
 166     MachineInstr* FoldSpill(unsigned vreg, const TargetRegisterClass* RC,
 167                             MachineInstr* DefMI,
 168                             MachineInstr* Barrier,
 169                             MachineBasicBlock* MBB,
 170                             int& SS,
 171                             SmallPtrSet<MachineInstr*, 4>& RefsInMBB);
 172   };
 173 } // end anonymous namespace
 174
 175 char PreAllocSplitting::ID = 0;
 176
 177 static RegisterPass<PreAllocSplitting>
 178 X("pre-alloc-splitting", "Pre-Register Allocation Live Interval Splitting");
 179
 180 const PassInfo *const llvm::PreAllocSplittingID = &X;
 181
 182
 183 /// findNextEmptySlot - Find a gap after the given machine instruction in the
 184 /// instruction index map. If there isn't one, return end().
 185 MachineBasicBlock::iterator
 186 PreAllocSplitting::findNextEmptySlot(MachineBasicBlock *MBB, MachineInstr *MI,
 187                                      unsigned &SpotIndex) {
 188   MachineBasicBlock::iterator MII = MI;
 189   if (++MII != MBB->end()) {
 190     unsigned Index = LIs->findGapBeforeInstr(LIs->getInstructionIndex(MII));
 191     if (Index) {
 192       SpotIndex = Index;
 193       return MII;
 194     }
 195   }
 196   return MBB->end();
 197 }
 198
 199 /// findSpillPoint - Find a gap as far away from the given MI that's suitable
 200 /// for spilling the current live interval. The index must be before any
 201 /// defs and uses of the live interval register in the mbb. Return begin() if
 202 /// none is found.
 203 MachineBasicBlock::iterator
 204 PreAllocSplitting::findSpillPoint(MachineBasicBlock *MBB, MachineInstr *MI,
 205                                   MachineInstr *DefMI,
 206                                   SmallPtrSet<MachineInstr*, 4> &RefsInMBB,
 207                                   unsigned &SpillIndex) {
 208   MachineBasicBlock::iterator Pt = MBB->begin();
 209
 210   // Go top down if RefsInMBB is empty.
 211   if (RefsInMBB.empty() && !DefMI) {
 212     MachineBasicBlock::iterator MII = MBB->begin();
 213     MachineBasicBlock::iterator EndPt = MI;
 214     do {
 215       ++MII;
 216       unsigned Index = LIs->getInstructionIndex(MII);
 217       unsigned Gap = LIs->findGapBeforeInstr(Index);
 218       if (Gap) {
 219         Pt = MII;
 220         SpillIndex = Gap;
 221         break;
 222       }
 223     } while (MII != EndPt);
 224   } else {
 225     MachineBasicBlock::iterator MII = MI;
 226     MachineBasicBlock::iterator EndPt = DefMI
 227       ? MachineBasicBlock::iterator(DefMI) : MBB->begin();
 228     while (MII != EndPt && !RefsInMBB.count(MII)) {
 229       unsigned Index = LIs->getInstructionIndex(MII);
 230       if (LIs->hasGapBeforeInstr(Index)) {
 231         Pt = MII;
 232         SpillIndex = LIs->findGapBeforeInstr(Index, true);
 233       }
 234       --MII;
 235     }
 236   }
 237
 238   return Pt;
 239 }
 240
 241 /// findRestorePoint - Find a gap in the instruction index map that's suitable
 242 /// for restoring the current live interval value. The index must be before any
 243 /// uses of the live interval register in the mbb. Return end() if none is
 244 /// found.
 245 MachineBasicBlock::iterator
 246 PreAllocSplitting::findRestorePoint(MachineBasicBlock *MBB, MachineInstr *MI,
 247                                     unsigned LastIdx,
 248                                     SmallPtrSet<MachineInstr*, 4> &RefsInMBB,
 249                                     unsigned &RestoreIndex) {
 250   // FIXME: Allow spill to be inserted to the beginning of the mbb. Update mbb
 251   // begin index accordingly.
 252   MachineBasicBlock::iterator Pt = MBB->end();
 253   unsigned EndIdx = LIs->getMBBEndIdx(MBB);
 254
 255   // Go bottom up if RefsInMBB is empty and the end of the mbb isn't beyond
 256   // the last index in the live range.
 257   if (RefsInMBB.empty() && LastIdx >= EndIdx) {
 258     MachineBasicBlock::iterator MII = MBB->getFirstTerminator();
 259     MachineBasicBlock::iterator EndPt = MI;
 260     --MII;
 261     do {
 262       unsigned Index = LIs->getInstructionIndex(MII);
 263       unsigned Gap = LIs->findGapBeforeInstr(Index);
 264       if (Gap) {
 265         Pt = MII;
 266         RestoreIndex = Gap;
 267         break;
 268       }
 269       --MII;
 270     } while (MII != EndPt);
 271   } else {
 272     MachineBasicBlock::iterator MII = MI;
 273     MII = ++MII;
 274     // FIXME: Limit the number of instructions to examine to reduce
 275     // compile time?
 276     while (MII != MBB->end()) {
 277       unsigned Index = LIs->getInstructionIndex(MII);
 278       if (Index > LastIdx)
 279         break;
 280       unsigned Gap = LIs->findGapBeforeInstr(Index);
 281       if (Gap) {
 282         Pt = MII;
 283         RestoreIndex = Gap;
 284       }
 285       if (RefsInMBB.count(MII))
 286         break;
 287       ++MII;
 288     }
 289   }
 290
 291   return Pt;
 292 }
 293
 294 /// CreateSpillStackSlot - Create a stack slot for the live interval being
 295 /// split. If the live interval was previously split, just reuse the same
 296 /// slot.
 297 int PreAllocSplitting::CreateSpillStackSlot(unsigned Reg,
 298                                             const TargetRegisterClass *RC) {
 299   int SS;
 300   DenseMap<unsigned, int>::iterator I = IntervalSSMap.find(Reg);
 301   if (I != IntervalSSMap.end()) {
 302     SS = I->second;
 303   } else {
 304     SS = MFI->CreateStackObject(RC->getSize(), RC->getAlignment());
 305     IntervalSSMap[Reg] = SS;
 306   }
 307
 308   // Create live interval for stack slot.
 309   CurrSLI = &LSs->getOrCreateInterval(SS);
 310   if (CurrSLI->hasAtLeastOneValue())
 311     CurrSValNo = CurrSLI->getValNumInfo(0);
 312   else
 313     CurrSValNo = CurrSLI->getNextValue(~0U, 0, LSs->getVNInfoAllocator());
 314   return SS;
 315 }
 316
 317 /// IsAvailableInStack - Return true if register is available in a split stack
 318 /// slot at the specified index.
 319 bool
 320 PreAllocSplitting::IsAvailableInStack(MachineBasicBlock *DefMBB,
 321                                     unsigned Reg, unsigned DefIndex,
 322                                     unsigned RestoreIndex, unsigned &SpillIndex,
 323                                     int& SS) const {
 324   if (!DefMBB)
 325     return false;
 326
 327   DenseMap<unsigned, int>::iterator I = IntervalSSMap.find(Reg);
 328   if (I == IntervalSSMap.end())
 329     return false;
 330   DenseMap<unsigned, unsigned>::iterator II = Def2SpillMap.find(DefIndex);
 331   if (II == Def2SpillMap.end())
 332     return false;
 333
 334   // If last spill of def is in the same mbb as barrier mbb (where restore will
 335   // be), make sure it's not below the intended restore index.
 336   // FIXME: Undo the previous spill?
 337   assert(LIs->getMBBFromIndex(II->second) == DefMBB);
 338   if (DefMBB == BarrierMBB && II->second >= RestoreIndex)
 339     return false;
 340
 341   SS = I->second;
 342   SpillIndex = II->second;
 343   return true;
 344 }
 345
 346 /// UpdateSpillSlotInterval - Given the specified val# of the register live
 347 /// interval being split, and the spill and restore indicies, update the live
 348 /// interval of the spill stack slot.
 349 void
 350 PreAllocSplitting::UpdateSpillSlotInterval(VNInfo *ValNo, unsigned SpillIndex,
 351                                            unsigned RestoreIndex) {
 352   assert(LIs->getMBBFromIndex(RestoreIndex) == BarrierMBB &&
 353          "Expect restore in the barrier mbb");
 354
 355   MachineBasicBlock *MBB = LIs->getMBBFromIndex(SpillIndex);
 356   if (MBB == BarrierMBB) {
 357     // Intra-block spill + restore. We are done.
 358     LiveRange SLR(SpillIndex, RestoreIndex, CurrSValNo);
 359     CurrSLI->addRange(SLR);
 360     return;
 361   }
 362
 363   SmallPtrSet<MachineBasicBlock*, 4> Processed;
 364   unsigned EndIdx = LIs->getMBBEndIdx(MBB);
 365   LiveRange SLR(SpillIndex, EndIdx+1, CurrSValNo);
 366   CurrSLI->addRange(SLR);
 367   Processed.insert(MBB);
 368
 369   // Start from the spill mbb, figure out the extend of the spill slot's
 370   // live interval.
 371   SmallVector<MachineBasicBlock*, 4> WorkList;
 372   const LiveRange *LR = CurrLI->getLiveRangeContaining(SpillIndex);
 373   if (LR->end > EndIdx)
 374     // If live range extend beyond end of mbb, add successors to work list.
 375     for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
 376            SE = MBB->succ_end(); SI != SE; ++SI)
 377       WorkList.push_back(*SI);
 378
 379   while (!WorkList.empty()) {
 380     MachineBasicBlock *MBB = WorkList.back();
 381     WorkList.pop_back();
 382     if (Processed.count(MBB))
 383       continue;
 384     unsigned Idx = LIs->getMBBStartIdx(MBB);
 385     LR = CurrLI->getLiveRangeContaining(Idx);
 386     if (LR && LR->valno == ValNo) {
 387       EndIdx = LIs->getMBBEndIdx(MBB);
 388       if (Idx <= RestoreIndex && RestoreIndex < EndIdx) {
 389         // Spill slot live interval stops at the restore.
 390         LiveRange SLR(Idx, RestoreIndex, CurrSValNo);
 391         CurrSLI->addRange(SLR);
 392       } else if (LR->end > EndIdx) {
 393         // Live range extends beyond end of mbb, process successors.
 394         LiveRange SLR(Idx, EndIdx+1, CurrSValNo);
 395         CurrSLI->addRange(SLR);
 396         for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
 397                SE = MBB->succ_end(); SI != SE; ++SI)
 398           WorkList.push_back(*SI);
 399       } else {
 400         LiveRange SLR(Idx, LR->end, CurrSValNo);
 401         CurrSLI->addRange(SLR);
 402       }
 403       Processed.insert(MBB);
 404     }
 405   }
 406 }
 407
 408 /// UpdateRegisterInterval - Given the specified val# of the current live
 409 /// interval is being split, and the spill and restore indices, update the live
 410 /// interval accordingly.
 411 void
 412 PreAllocSplitting::UpdateRegisterInterval(VNInfo *ValNo, unsigned SpillIndex,
 413                                           unsigned RestoreIndex) {
 414   assert(LIs->getMBBFromIndex(RestoreIndex) == BarrierMBB &&
 415          "Expect restore in the barrier mbb");
 416
 417   SmallVector<std::pair<unsigned,unsigned>, 4> Before;
 418   SmallVector<std::pair<unsigned,unsigned>, 4> After;
 419   SmallVector<unsigned, 4> BeforeKills;
 420   SmallVector<unsigned, 4> AfterKills;
 421   SmallPtrSet<const LiveRange*, 4> Processed;
 422
 423   // First, let's figure out which parts of the live interval is now defined
 424   // by the restore, which are defined by the original definition.
 425   const LiveRange *LR = CurrLI->getLiveRangeContaining(RestoreIndex);
 426   After.push_back(std::make_pair(RestoreIndex, LR->end));
 427   if (CurrLI->isKill(ValNo, LR->end))
 428     AfterKills.push_back(LR->end);
 429
 430   assert(LR->contains(SpillIndex));
 431   if (SpillIndex > LR->start) {
 432     Before.push_back(std::make_pair(LR->start, SpillIndex));
 433     BeforeKills.push_back(SpillIndex);
 434   }
 435   Processed.insert(LR);
 436
 437   // Start from the restore mbb, figure out what part of the live interval
 438   // are defined by the restore.
 439   SmallVector<MachineBasicBlock*, 4> WorkList;
 440   MachineBasicBlock *MBB = BarrierMBB;
 441   for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
 442          SE = MBB->succ_end(); SI != SE; ++SI)
 443     WorkList.push_back(*SI);
 444
 445   SmallPtrSet<MachineBasicBlock*, 4> ProcessedBlocks;
 446   ProcessedBlocks.insert(MBB);
 447
 448   while (!WorkList.empty()) {
 449     MBB = WorkList.back();
 450     WorkList.pop_back();
 451     unsigned Idx = LIs->getMBBStartIdx(MBB);
 452     LR = CurrLI->getLiveRangeContaining(Idx);
 453     if (LR && LR->valno == ValNo && !Processed.count(LR)) {
 454       After.push_back(std::make_pair(LR->start, LR->end));
 455       if (CurrLI->isKill(ValNo, LR->end))
 456         AfterKills.push_back(LR->end);
 457       Idx = LIs->getMBBEndIdx(MBB);
 458       if (LR->end > Idx) {
 459         // Live range extend beyond at least one mbb. Let's see what other
 460         // mbbs it reaches.
 461         LIs->findReachableMBBs(LR->start, LR->end, WorkList);
 462       }
 463       Processed.insert(LR);
 464     }
 465
 466     ProcessedBlocks.insert(MBB);
 467     if (LR)
 468       for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
 469             SE = MBB->succ_end(); SI != SE; ++SI)
 470         if (!ProcessedBlocks.count(*SI))
 471           WorkList.push_back(*SI);
 472   }
 473
 474   for (LiveInterval::iterator I = CurrLI->begin(), E = CurrLI->end();
 475        I != E; ++I) {
 476     LiveRange *LR = I;
 477     if (LR->valno == ValNo && !Processed.count(LR)) {
 478       Before.push_back(std::make_pair(LR->start, LR->end));
 479       if (CurrLI->isKill(ValNo, LR->end))
 480         BeforeKills.push_back(LR->end);
 481     }
 482   }
 483
 484   // Now create new val#s to represent the live ranges defined by the old def
 485   // those defined by the restore.
 486   unsigned AfterDef = ValNo->def;
 487   MachineInstr *AfterCopy = ValNo->copy;
 488   bool HasPHIKill = ValNo->hasPHIKill;
 489   CurrLI->removeValNo(ValNo);
 490   VNInfo *BValNo = (Before.empty())
 491     ? NULL
 492     : CurrLI->getNextValue(AfterDef, AfterCopy, LIs->getVNInfoAllocator());
 493   if (BValNo)
 494     CurrLI->addKills(BValNo, BeforeKills);
 495
 496   VNInfo *AValNo = (After.empty())
 497     ? NULL
 498     : CurrLI->getNextValue(RestoreIndex, 0, LIs->getVNInfoAllocator());
 499   if (AValNo) {
 500     AValNo->hasPHIKill = HasPHIKill;
 501     CurrLI->addKills(AValNo, AfterKills);
 502   }
 503
 504   for (unsigned i = 0, e = Before.size(); i != e; ++i) {
 505     unsigned Start = Before[i].first;
 506     unsigned End   = Before[i].second;
 507     CurrLI->addRange(LiveRange(Start, End, BValNo));
 508   }
 509   for (unsigned i = 0, e = After.size(); i != e; ++i) {
 510     unsigned Start = After[i].first;
 511     unsigned End   = After[i].second;
 512     CurrLI->addRange(LiveRange(Start, End, AValNo));
 513   }
 514 }
 515
 516 /// ShrinkWrapToLastUse - There are uses of the current live interval in the
 517 /// given block, shrink wrap the live interval to the last use (i.e. remove
 518 /// from last use to the end of the mbb). In case mbb is the where the barrier
 519 /// is, remove from the last use to the barrier.
 520 bool
 521 PreAllocSplitting::ShrinkWrapToLastUse(MachineBasicBlock *MBB, VNInfo *ValNo,
 522                                        SmallVector<MachineOperand*, 4> &Uses,
 523                                        SmallPtrSet<MachineInstr*, 4> &UseMIs) {
 524   MachineOperand *LastMO = 0;
 525   MachineInstr *LastMI = 0;
 526   if (MBB != BarrierMBB && Uses.size() == 1) {
 527     // Single use, no need to traverse the block. We can't assume this for the
 528     // barrier bb though since the use is probably below the barrier.
 529     LastMO = Uses[0];
 530     LastMI = LastMO->getParent();
 531   } else {
 532     MachineBasicBlock::iterator MEE = MBB->begin();
 533     MachineBasicBlock::iterator MII;
 534     if (MBB == BarrierMBB)
 535       MII = Barrier;
 536     else
 537       MII = MBB->end();
 538     while (MII != MEE) {
 539       --MII;
 540       MachineInstr *UseMI = &*MII;
 541       if (!UseMIs.count(UseMI))
 542         continue;
 543       for (unsigned i = 0, e = UseMI->getNumOperands(); i != e; ++i) {
 544         MachineOperand &MO = UseMI->getOperand(i);
 545         if (MO.isReg() && MO.getReg() == CurrLI->reg) {
 546           LastMO = &MO;
 547           break;
 548         }
 549       }
 550       LastMI = UseMI;
 551       break;
 552     }
 553   }
 554
 555   // Cut off live range from last use (or beginning of the mbb if there
 556   // are no uses in it) to the end of the mbb.
 557   unsigned RangeStart, RangeEnd = LIs->getMBBEndIdx(MBB)+1;
 558   if (LastMI) {
 559     RangeStart = LIs->getUseIndex(LIs->getInstructionIndex(LastMI))+1;
 560     assert(!LastMO->isKill() && "Last use already terminates the interval?");
 561     LastMO->setIsKill();
 562   } else {
 563     assert(MBB == BarrierMBB);
 564     RangeStart = LIs->getMBBStartIdx(MBB);
 565   }
 566   if (MBB == BarrierMBB)
 567     RangeEnd = LIs->getUseIndex(BarrierIdx)+1;
 568   CurrLI->removeRange(RangeStart, RangeEnd);
 569   if (LastMI)
 570     CurrLI->addKill(ValNo, RangeStart);
 571
 572   // Return true if the last use becomes a new kill.
 573   return LastMI;
 574 }
 575
 576 /// ShrinkWrapLiveInterval - Recursively traverse the predecessor
 577 /// chain to find the new 'kills' and shrink wrap the live interval to the
 578 /// new kill indices.
 579 void
 580 PreAllocSplitting::ShrinkWrapLiveInterval(VNInfo *ValNo, MachineBasicBlock *MBB,
 581                           MachineBasicBlock *SuccMBB, MachineBasicBlock *DefMBB,
 582                                     SmallPtrSet<MachineBasicBlock*, 8> &Visited,
 583            DenseMap<MachineBasicBlock*, SmallVector<MachineOperand*, 4> > &Uses,
 584            DenseMap<MachineBasicBlock*, SmallPtrSet<MachineInstr*, 4> > &UseMIs,
 585                                   SmallVector<MachineBasicBlock*, 4> &UseMBBs) {
 586   if (Visited.count(MBB))
 587     return;
 588
 589   // If live interval is live in another successor path, then we can't process
 590   // this block. But we may able to do so after all the successors have been
 591   // processed.
 592   if (MBB != BarrierMBB) {
 593     for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
 594            SE = MBB->succ_end(); SI != SE; ++SI) {
 595       MachineBasicBlock *SMBB = *SI;
 596       if (SMBB == SuccMBB)
 597         continue;
 598       if (CurrLI->liveAt(LIs->getMBBStartIdx(SMBB)))
 599         return;
 600     }
 601   }
 602
 603   Visited.insert(MBB);
 604
 605   DenseMap<MachineBasicBlock*, SmallVector<MachineOperand*, 4> >::iterator
 606     UMII = Uses.find(MBB);
 607   if (UMII != Uses.end()) {
 608     // At least one use in this mbb, lets look for the kill.
 609     DenseMap<MachineBasicBlock*, SmallPtrSet<MachineInstr*, 4> >::iterator
 610       UMII2 = UseMIs.find(MBB);
 611     if (ShrinkWrapToLastUse(MBB, ValNo, UMII->second, UMII2->second))
 612       // Found a kill, shrink wrapping of this path ends here.
 613       return;
 614   } else if (MBB == DefMBB) {
 615     // There are no uses after the def.
 616     MachineInstr *DefMI = LIs->getInstructionFromIndex(ValNo->def);
 617     if (UseMBBs.empty()) {
 618       // The only use must be below barrier in the barrier block. It's safe to
 619       // remove the def.
 620       LIs->RemoveMachineInstrFromMaps(DefMI);
 621       DefMI->eraseFromParent();
 622       CurrLI->removeRange(ValNo->def, LIs->getMBBEndIdx(MBB)+1);
 623     }
 624   } else if (MBB == BarrierMBB) {
 625     // Remove entire live range from start of mbb to barrier.
 626     CurrLI->removeRange(LIs->getMBBStartIdx(MBB),
 627                         LIs->getUseIndex(BarrierIdx)+1);
 628   } else {
 629     // Remove entire live range of the mbb out of the live interval.
 630     CurrLI->removeRange(LIs->getMBBStartIdx(MBB), LIs->getMBBEndIdx(MBB)+1);
 631   }
 632
 633   if (MBB == DefMBB)
 634     // Reached the def mbb, stop traversing this path further.
 635     return;
 636
 637   // Traverse the pathes up the predecessor chains further.
 638   for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
 639          PE = MBB->pred_end(); PI != PE; ++PI) {
 640     MachineBasicBlock *Pred = *PI;
 641     if (Pred == MBB)
 642       continue;
 643     if (Pred == DefMBB && ValNo->hasPHIKill)
 644       // Pred is the def bb and the def reaches other val#s, we must
 645       // allow the value to be live out of the bb.
 646       continue;
 647     if (!CurrLI->liveAt(LIs->getMBBEndIdx(Pred)-1))
 648       return;
 649     ShrinkWrapLiveInterval(ValNo, Pred, MBB, DefMBB, Visited,
 650                            Uses, UseMIs, UseMBBs);
 651   }
 652
 653   return;
 654 }
 655
 656
 657 void PreAllocSplitting::RepairLiveInterval(LiveInterval* CurrLI,
 658                                            VNInfo* ValNo,
 659                                            MachineInstr* DefMI,
 660                                            unsigned RestoreIdx) {
 661   // Shrink wrap the live interval by walking up the CFG and find the
 662   // new kills.
 663   // Now let's find all the uses of the val#.
 664   DenseMap<MachineBasicBlock*, SmallVector<MachineOperand*, 4> > Uses;
 665   DenseMap<MachineBasicBlock*, SmallPtrSet<MachineInstr*, 4> > UseMIs;
 666   SmallPtrSet<MachineBasicBlock*, 4> Seen;
 667   SmallVector<MachineBasicBlock*, 4> UseMBBs;
 668   for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(CurrLI->reg),
 669          UE = MRI->use_end(); UI != UE; ++UI) {
 670     MachineOperand &UseMO = UI.getOperand();
 671     MachineInstr *UseMI = UseMO.getParent();
 672     unsigned UseIdx = LIs->getInstructionIndex(UseMI);
 673     LiveInterval::iterator ULR = CurrLI->FindLiveRangeContaining(UseIdx);
 674     if (ULR->valno != ValNo)
 675       continue;
 676     MachineBasicBlock *UseMBB = UseMI->getParent();
 677     // Remember which other mbb's use this val#.
 678     if (Seen.insert(UseMBB) && UseMBB != BarrierMBB)
 679       UseMBBs.push_back(UseMBB);
 680     DenseMap<MachineBasicBlock*, SmallVector<MachineOperand*, 4> >::iterator
 681       UMII = Uses.find(UseMBB);
 682     if (UMII != Uses.end()) {
 683       DenseMap<MachineBasicBlock*, SmallPtrSet<MachineInstr*, 4> >::iterator
 684         UMII2 = UseMIs.find(UseMBB);
 685       UMII->second.push_back(&UseMO);
 686       UMII2->second.insert(UseMI);
 687     } else {
 688       SmallVector<MachineOperand*, 4> Ops;
 689       Ops.push_back(&UseMO);
 690       Uses.insert(std::make_pair(UseMBB, Ops));
 691       SmallPtrSet<MachineInstr*, 4> MIs;
 692       MIs.insert(UseMI);
 693       UseMIs.insert(std::make_pair(UseMBB, MIs));
 694     }
 695   }
 696
 697   // Walk up the predecessor chains.
 698   SmallPtrSet<MachineBasicBlock*, 8> Visited;
 699   ShrinkWrapLiveInterval(ValNo, BarrierMBB, NULL, DefMI->getParent(), Visited,
 700                          Uses, UseMIs, UseMBBs);
 701
 702   // FIXME: If ValNo->hasPHIKill is false, then renumber the val# by
 703   // the restore.
 704
 705   // Remove live range from barrier to the restore. FIXME: Find a better
 706   // point to re-start the live interval.
 707   UpdateRegisterInterval(ValNo, LIs->getUseIndex(BarrierIdx)+1,
 708                          LIs->getDefIndex(RestoreIdx));
 709 }
 710 bool PreAllocSplitting::Rematerialize(unsigned vreg, VNInfo* ValNo,
 711                                       MachineInstr* DefMI,
 712                                       MachineBasicBlock::iterator RestorePt,
 713                                       unsigned RestoreIdx,
 714                                     SmallPtrSet<MachineInstr*, 4>& RefsInMBB) {
 715   MachineBasicBlock& MBB = *RestorePt->getParent();
 716
 717   MachineBasicBlock::iterator KillPt = BarrierMBB->end();
 718   unsigned KillIdx = 0;
 719   if (ValNo->def == ~0U || DefMI->getParent() == BarrierMBB)
 720     KillPt = findSpillPoint(BarrierMBB, Barrier, NULL, RefsInMBB, KillIdx);
 721   else
 722     KillPt = findNextEmptySlot(DefMI->getParent(), DefMI, KillIdx);
 723
 724   if (KillPt == DefMI->getParent()->end())
 725     return false;
 726
 727   TII->reMaterialize(MBB, RestorePt, vreg, DefMI);
 728   LIs->InsertMachineInstrInMaps(prior(RestorePt), RestoreIdx);
 729
 730   if (KillPt->getParent() == BarrierMBB) {
 731     UpdateRegisterInterval(ValNo, LIs->getUseIndex(KillIdx)+1,
 732                            LIs->getDefIndex(RestoreIdx));
 733
 734     ++NumSplits;
 735     ++NumRemats;
 736     return true;
 737   }
 738
 739   RepairLiveInterval(CurrLI, ValNo, DefMI, RestoreIdx);
 740
 741   ++NumSplits;
 742   ++NumRemats;
 743   return true;
 744 }
 745
 746 MachineInstr* PreAllocSplitting::FoldSpill(unsigned vreg,
 747                                            const TargetRegisterClass* RC,
 748                                            MachineInstr* DefMI,
 749                                            MachineInstr* Barrier,
 750                                            MachineBasicBlock* MBB,
 751                                            int& SS,
 752                                     SmallPtrSet<MachineInstr*, 4>& RefsInMBB) {
 753   MachineBasicBlock::iterator Pt = MBB->begin();
 754
 755   // Go top down if RefsInMBB is empty.
 756   if (RefsInMBB.empty())
 757     return 0;
 758
 759   MachineBasicBlock::iterator FoldPt = Barrier;
 760   while (&*FoldPt != DefMI && FoldPt != MBB->begin() &&
 761          !RefsInMBB.count(FoldPt))
 762     --FoldPt;
 763
 764   int OpIdx = FoldPt->findRegisterDefOperandIdx(vreg, false);
 765   if (OpIdx == -1)
 766     return 0;
 767
 768   SmallVector<unsigned, 1> Ops;
 769   Ops.push_back(OpIdx);
 770
 771   if (!TII->canFoldMemoryOperand(FoldPt, Ops))
 772     return 0;
 773
 774   DenseMap<unsigned, int>::iterator I = IntervalSSMap.find(vreg);
 775   if (I != IntervalSSMap.end()) {
 776     SS = I->second;
 777   } else {
 778     SS = MFI->CreateStackObject(RC->getSize(), RC->getAlignment());
 779
 780   }
 781
 782   MachineInstr* FMI = TII->foldMemoryOperand(*MBB->getParent(),
 783                                              FoldPt, Ops, SS);
 784
 785   if (FMI) {
 786     LIs->ReplaceMachineInstrInMaps(FoldPt, FMI);
 787     FMI = MBB->insert(MBB->erase(FoldPt), FMI);
 788     ++NumFolds;
 789
 790     IntervalSSMap[vreg] = SS;
 791     CurrSLI = &LSs->getOrCreateInterval(SS);
 792     if (CurrSLI->hasAtLeastOneValue())
 793       CurrSValNo = CurrSLI->getValNumInfo(0);
 794     else
 795       CurrSValNo = CurrSLI->getNextValue(~0U, 0, LSs->getVNInfoAllocator());
 796   }
 797
 798   return FMI;
 799 }
 800
 801 /// SplitRegLiveInterval - Split (spill and restore) the given live interval
 802 /// so it would not cross the barrier that's being processed. Shrink wrap
 803 /// (minimize) the live interval to the last uses.
 804 bool PreAllocSplitting::SplitRegLiveInterval(LiveInterval *LI) {
 805   CurrLI = LI;
 806
 807   // Find live range where current interval cross the barrier.
 808   LiveInterval::iterator LR =
 809     CurrLI->FindLiveRangeContaining(LIs->getUseIndex(BarrierIdx));
 810   VNInfo *ValNo = LR->valno;
 811
 812   if (ValNo->def == ~1U) {
 813     // Defined by a dead def? How can this be?
 814     assert(0 && "Val# is defined by a dead def?");
 815     abort();
 816   }
 817
 818   MachineInstr *DefMI = (ValNo->def != ~0U)
 819     ? LIs->getInstructionFromIndex(ValNo->def) : NULL;
 820
 821   // If this would create a new join point, do not split.
 822   if (DefMI && createsNewJoin(LR, DefMI->getParent(), Barrier->getParent()))
 823     return false;
 824
 825   // Find all references in the barrier mbb.
 826   SmallPtrSet<MachineInstr*, 4> RefsInMBB;
 827   for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(CurrLI->reg),
 828          E = MRI->reg_end(); I != E; ++I) {
 829     MachineInstr *RefMI = &*I;
 830     if (RefMI->getParent() == BarrierMBB)
 831       RefsInMBB.insert(RefMI);
 832   }
 833
 834   // Find a point to restore the value after the barrier.
 835   unsigned RestoreIndex;
 836   MachineBasicBlock::iterator RestorePt =
 837     findRestorePoint(BarrierMBB, Barrier, LR->end, RefsInMBB, RestoreIndex);
 838   if (RestorePt == BarrierMBB->end())
 839     return false;
 840
 841   if (DefMI && LIs->isReMaterializable(*LI, ValNo, DefMI))
 842     if (Rematerialize(LI->reg, ValNo, DefMI, RestorePt,
 843                       RestoreIndex, RefsInMBB))
 844     return true;
 845
 846   // Add a spill either before the barrier or after the definition.
 847   MachineBasicBlock *DefMBB = DefMI ? DefMI->getParent() : NULL;
 848   const TargetRegisterClass *RC = MRI->getRegClass(CurrLI->reg);
 849   unsigned SpillIndex = 0;
 850   MachineInstr *SpillMI = NULL;
 851   int SS = -1;
 852   if (ValNo->def == ~0U) {
 853     // If it's defined by a phi, we must split just before the barrier.
 854     if ((SpillMI = FoldSpill(LI->reg, RC, 0, Barrier,
 855                             BarrierMBB, SS, RefsInMBB))) {
 856       SpillIndex = LIs->getInstructionIndex(SpillMI);
 857     } else {
 858       MachineBasicBlock::iterator SpillPt =
 859         findSpillPoint(BarrierMBB, Barrier, NULL, RefsInMBB, SpillIndex);
 860       if (SpillPt == BarrierMBB->begin())
 861         return false; // No gap to insert spill.
 862       // Add spill.
 863
 864       SS = CreateSpillStackSlot(CurrLI->reg, RC);
 865       TII->storeRegToStackSlot(*BarrierMBB, SpillPt, CurrLI->reg, true, SS, RC);
 866       SpillMI = prior(SpillPt);
 867       LIs->InsertMachineInstrInMaps(SpillMI, SpillIndex);
 868     }
 869   } else if (!IsAvailableInStack(DefMBB, CurrLI->reg, ValNo->def,
 870                                  RestoreIndex, SpillIndex, SS)) {
 871     // If it's already split, just restore the value. There is no need to spill
 872     // the def again.
 873     if (!DefMI)
 874       return false; // Def is dead. Do nothing.
 875
 876     if ((SpillMI = FoldSpill(LI->reg, RC, DefMI, Barrier,
 877                             BarrierMBB, SS, RefsInMBB))) {
 878       SpillIndex = LIs->getInstructionIndex(SpillMI);
 879     } else {
 880       // Check if it's possible to insert a spill after the def MI.
 881       MachineBasicBlock::iterator SpillPt;
 882       if (DefMBB == BarrierMBB) {
 883         // Add spill after the def and the last use before the barrier.
 884         SpillPt = findSpillPoint(BarrierMBB, Barrier, DefMI,
 885                                  RefsInMBB, SpillIndex);
 886         if (SpillPt == DefMBB->begin())
 887           return false; // No gap to insert spill.
 888       } else {
 889         SpillPt = findNextEmptySlot(DefMBB, DefMI, SpillIndex);
 890         if (SpillPt == DefMBB->end())
 891           return false; // No gap to insert spill.
 892       }
 893       // Add spill. The store instruction kills the register if def is before
 894       // the barrier in the barrier block.
 895       SS = CreateSpillStackSlot(CurrLI->reg, RC);
 896       TII->storeRegToStackSlot(*DefMBB, SpillPt, CurrLI->reg,
 897                                DefMBB == BarrierMBB, SS, RC);
 898       SpillMI = prior(SpillPt);
 899       LIs->InsertMachineInstrInMaps(SpillMI, SpillIndex);
 900     }
 901   }
 902
 903   // Remember def instruction index to spill index mapping.
 904   if (DefMI && SpillMI)
 905     Def2SpillMap[ValNo->def] = SpillIndex;
 906
 907   // Add restore.
 908   TII->loadRegFromStackSlot(*BarrierMBB, RestorePt, CurrLI->reg, SS, RC);
 909   MachineInstr *LoadMI = prior(RestorePt);
 910   LIs->InsertMachineInstrInMaps(LoadMI, RestoreIndex);
 911
 912   // If live interval is spilled in the same block as the barrier, just
 913   // create a hole in the interval.
 914   if (!DefMBB ||
 915       (SpillMI && SpillMI->getParent() == BarrierMBB)) {
 916     // Update spill stack slot live interval.
 917     UpdateSpillSlotInterval(ValNo, LIs->getUseIndex(SpillIndex)+1,
 918                             LIs->getDefIndex(RestoreIndex));
 919
 920     UpdateRegisterInterval(ValNo, LIs->getUseIndex(SpillIndex)+1,
 921                            LIs->getDefIndex(RestoreIndex));
 922
 923     ++NumSplits;
 924     return true;
 925   }
 926
 927   // Update spill stack slot live interval.
 928   UpdateSpillSlotInterval(ValNo, LIs->getUseIndex(SpillIndex)+1,
 929                           LIs->getDefIndex(RestoreIndex));
 930
 931   RepairLiveInterval(CurrLI, ValNo, DefMI, RestoreIndex);
 932
 933   ++NumSplits;
 934   return true;
 935 }
 936
 937 /// SplitRegLiveIntervals - Split all register live intervals that cross the
 938 /// barrier that's being processed.
 939 bool
 940 PreAllocSplitting::SplitRegLiveIntervals(const TargetRegisterClass **RCs) {
 941   // First find all the virtual registers whose live intervals are intercepted
 942   // by the current barrier.
 943   SmallVector<LiveInterval*, 8> Intervals;
 944   for (const TargetRegisterClass **RC = RCs; *RC; ++RC) {
 945     if (TII->IgnoreRegisterClassBarriers(*RC))
 946       continue;
 947     std::vector<unsigned> &VRs = MRI->getRegClassVirtRegs(*RC);
 948     for (unsigned i = 0, e = VRs.size(); i != e; ++i) {
 949       unsigned Reg = VRs[i];
 950       if (!LIs->hasInterval(Reg))
 951         continue;
 952       LiveInterval *LI = &LIs->getInterval(Reg);
 953       if (LI->liveAt(BarrierIdx) && !Barrier->readsRegister(Reg))
 954         // Virtual register live interval is intercepted by the barrier. We
 955         // should split and shrink wrap its interval if possible.
 956         Intervals.push_back(LI);
 957     }
 958   }
 959
 960   // Process the affected live intervals.
 961   bool Change = false;
 962   while (!Intervals.empty()) {
 963     if (PreSplitLimit != -1 && (int)NumSplits == PreSplitLimit)
 964       break;
 965     LiveInterval *LI = Intervals.back();
 966     Intervals.pop_back();
 967     Change |= SplitRegLiveInterval(LI);
 968   }
 969
 970   return Change;
 971 }
 972
 973 bool PreAllocSplitting::createsNewJoin(LiveRange* LR,
 974                                        MachineBasicBlock* DefMBB,
 975                                        MachineBasicBlock* BarrierMBB) {
 976   if (DefMBB == BarrierMBB)
 977     return false;
 978
 979   if (LR->valno->hasPHIKill)
 980     return false;
 981
 982   unsigned MBBEnd = LIs->getMBBEndIdx(BarrierMBB);
 983   if (LR->end < MBBEnd)
 984     return false;
 985
 986   MachineLoopInfo& MLI = getAnalysis<MachineLoopInfo>();
 987   if (MLI.getLoopFor(DefMBB) != MLI.getLoopFor(BarrierMBB))
 988     return true;
 989
 990   MachineDominatorTree& MDT = getAnalysis<MachineDominatorTree>();
 991   SmallPtrSet<MachineBasicBlock*, 4> Visited;
 992   typedef std::pair<MachineBasicBlock*,
 993                     MachineBasicBlock::succ_iterator> ItPair;
 994   SmallVector<ItPair, 4> Stack;
 995   Stack.push_back(std::make_pair(BarrierMBB, BarrierMBB->succ_begin()));
 996
 997   while (!Stack.empty()) {
 998     ItPair P = Stack.back();
 999     Stack.pop_back();
1000
1001     MachineBasicBlock* PredMBB = P.first;
1002     MachineBasicBlock::succ_iterator S = P.second;
1003
1004     if (S == PredMBB->succ_end())
1005       continue;
1006     else if (Visited.count(*S)) {
1007       Stack.push_back(std::make_pair(PredMBB, ++S));
1008       continue;
1009     } else
1010       Stack.push_back(std::make_pair(PredMBB, S+1));
1011
1012     MachineBasicBlock* MBB = *S;
1013     Visited.insert(MBB);
1014
1015     if (MBB == BarrierMBB)
1016       return true;
1017
1018     MachineDomTreeNode* DefMDTN = MDT.getNode(DefMBB);
1019     MachineDomTreeNode* BarrierMDTN = MDT.getNode(BarrierMBB);
1020     MachineDomTreeNode* MDTN = MDT.getNode(MBB)->getIDom();
1021     while (MDTN) {
1022       if (MDTN == DefMDTN)
1023         return true;
1024       else if (MDTN == BarrierMDTN)
1025         break;
1026       MDTN = MDTN->getIDom();
1027     }
1028
1029     MBBEnd = LIs->getMBBEndIdx(MBB);
1030     if (LR->end > MBBEnd)
1031       Stack.push_back(std::make_pair(MBB, MBB->succ_begin()));
1032   }
1033
1034   return false;
1035 }
1036
1037
1038 bool PreAllocSplitting::runOnMachineFunction(MachineFunction &MF) {
1039   CurrMF = &MF;
1040   TM     = &MF.getTarget();
1041   TII    = TM->getInstrInfo();
1042   MFI    = MF.getFrameInfo();
1043   MRI    = &MF.getRegInfo();
1044   LIs    = &getAnalysis<LiveIntervals>();
1045   LSs    = &getAnalysis<LiveStacks>();
1046
1047   bool MadeChange = false;
1048
1049   // Make sure blocks are numbered in order.
1050   MF.RenumberBlocks();
1051
1052 #if 1
1053   // FIXME: Go top down.
1054   MachineBasicBlock *Entry = MF.begin();
1055   SmallPtrSet<MachineBasicBlock*,16> Visited;
1056
1057   for (df_ext_iterator<MachineBasicBlock*, SmallPtrSet<MachineBasicBlock*,16> >
1058          DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited);
1059        DFI != E; ++DFI) {
1060     BarrierMBB = *DFI;
1061     for (MachineBasicBlock::iterator I = BarrierMBB->begin(),
1062            E = BarrierMBB->end(); I != E; ++I) {
1063       Barrier = &*I;
1064       const TargetRegisterClass **BarrierRCs =
1065         Barrier->getDesc().getRegClassBarriers();
1066       if (!BarrierRCs)
1067         continue;
1068       BarrierIdx = LIs->getInstructionIndex(Barrier);
1069       MadeChange |= SplitRegLiveIntervals(BarrierRCs);
1070     }
1071   }
1072 #else
1073   for (MachineFunction::reverse_iterator I = MF.rbegin(), E = MF.rend();
1074        I != E; ++I) {
1075     BarrierMBB = &*I;
1076     for (MachineBasicBlock::reverse_iterator II = BarrierMBB->rbegin(),
1077            EE = BarrierMBB->rend(); II != EE; ++II) {
1078       Barrier = &*II;
1079       const TargetRegisterClass **BarrierRCs =
1080         Barrier->getDesc().getRegClassBarriers();
1081       if (!BarrierRCs)
1082         continue;
1083       BarrierIdx = LIs->getInstructionIndex(Barrier);
1084       MadeChange |= SplitRegLiveIntervals(BarrierRCs);
1085     }
1086   }
1087 #endif
1088
1089   return MadeChange;
1090 }