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 STATISTIC(NumRenumbers, "Number of intervals renumbered into new registers");
  45
  46 namespace {
  47   class VISIBILITY_HIDDEN PreAllocSplitting : public MachineFunctionPass {
  48     MachineFunction       *CurrMF;
  49     const TargetMachine   *TM;
  50     const TargetInstrInfo *TII;
  51     MachineFrameInfo      *MFI;
  52     MachineRegisterInfo   *MRI;
  53     LiveIntervals         *LIs;
  54     LiveStacks            *LSs;
  55
  56     // Barrier - Current barrier being processed.
  57     MachineInstr          *Barrier;
  58
  59     // BarrierMBB - Basic block where the barrier resides in.
  60     MachineBasicBlock     *BarrierMBB;
  61
  62     // Barrier - Current barrier index.
  63     unsigned              BarrierIdx;
  64
  65     // CurrLI - Current live interval being split.
  66     LiveInterval          *CurrLI;
  67
  68     // CurrSLI - Current stack slot live interval.
  69     LiveInterval          *CurrSLI;
  70
  71     // CurrSValNo - Current val# for the stack slot live interval.
  72     VNInfo                *CurrSValNo;
  73
  74     // IntervalSSMap - A map from live interval to spill slots.
  75     DenseMap<unsigned, int> IntervalSSMap;
  76
  77     // Def2SpillMap - A map from a def instruction index to spill index.
  78     DenseMap<unsigned, unsigned> Def2SpillMap;
  79
  80   public:
  81     static char ID;
  82     PreAllocSplitting() : MachineFunctionPass(&ID) {}
  83
  84     virtual bool runOnMachineFunction(MachineFunction &MF);
  85
  86     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  87       AU.addRequired<LiveIntervals>();
  88       AU.addPreserved<LiveIntervals>();
  89       AU.addRequired<LiveStacks>();
  90       AU.addPreserved<LiveStacks>();
  91       AU.addPreserved<RegisterCoalescer>();
  92       if (StrongPHIElim)
  93         AU.addPreservedID(StrongPHIEliminationID);
  94       else
  95         AU.addPreservedID(PHIEliminationID);
  96       AU.addRequired<MachineDominatorTree>();
  97       AU.addRequired<MachineLoopInfo>();
  98       AU.addPreserved<MachineDominatorTree>();
  99       AU.addPreserved<MachineLoopInfo>();
 100       MachineFunctionPass::getAnalysisUsage(AU);
 101     }
 102
 103     virtual void releaseMemory() {
 104       IntervalSSMap.clear();
 105       Def2SpillMap.clear();
 106     }
 107
 108     virtual const char *getPassName() const {
 109       return "Pre-Register Allocaton Live Interval Splitting";
 110     }
 111
 112     /// print - Implement the dump method.
 113     virtual void print(std::ostream &O, const Module* M = 0) const {
 114       LIs->print(O, M);
 115     }
 116
 117     void print(std::ostream *O, const Module* M = 0) const {
 118       if (O) print(*O, M);
 119     }
 120
 121   private:
 122     MachineBasicBlock::iterator
 123       findNextEmptySlot(MachineBasicBlock*, MachineInstr*,
 124                         unsigned&);
 125
 126     MachineBasicBlock::iterator
 127       findSpillPoint(MachineBasicBlock*, MachineInstr*, MachineInstr*,
 128                      SmallPtrSet<MachineInstr*, 4>&, unsigned&);
 129
 130     MachineBasicBlock::iterator
 131       findRestorePoint(MachineBasicBlock*, MachineInstr*, unsigned,
 132                      SmallPtrSet<MachineInstr*, 4>&, unsigned&);
 133
 134     int CreateSpillStackSlot(unsigned, const TargetRegisterClass *);
 135
 136     bool IsAvailableInStack(MachineBasicBlock*, unsigned, unsigned, unsigned,
 137                             unsigned&, int&) const;
 138
 139     void UpdateSpillSlotInterval(VNInfo*, unsigned, unsigned);
 140
 141     VNInfo* UpdateRegisterInterval(VNInfo*, unsigned, unsigned);
 142
 143     bool ShrinkWrapToLastUse(MachineBasicBlock*, VNInfo*,
 144                              SmallVector<MachineOperand*, 4>&,
 145                              SmallPtrSet<MachineInstr*, 4>&);
 146
 147     void ShrinkWrapLiveInterval(VNInfo*, MachineBasicBlock*, MachineBasicBlock*,
 148                         MachineBasicBlock*, SmallPtrSet<MachineBasicBlock*, 8>&,
 149                 DenseMap<MachineBasicBlock*, SmallVector<MachineOperand*, 4> >&,
 150                   DenseMap<MachineBasicBlock*, SmallPtrSet<MachineInstr*, 4> >&,
 151                                 SmallVector<MachineBasicBlock*, 4>&);
 152
 153     bool SplitRegLiveInterval(LiveInterval*);
 154
 155     bool SplitRegLiveIntervals(const TargetRegisterClass **);
 156
 157     void RepairLiveInterval(LiveInterval* CurrLI, VNInfo* ValNo,
 158                             MachineInstr* DefMI, unsigned RestoreIdx);
 159
 160     bool createsNewJoin(LiveRange* LR, MachineBasicBlock* DefMBB,
 161                         MachineBasicBlock* BarrierMBB);
 162     bool Rematerialize(unsigned vreg, VNInfo* ValNo,
 163                        MachineInstr* DefMI,
 164                        MachineBasicBlock::iterator RestorePt,
 165                        unsigned RestoreIdx,
 166                        SmallPtrSet<MachineInstr*, 4>& RefsInMBB);
 167     MachineInstr* FoldSpill(unsigned vreg, const TargetRegisterClass* RC,
 168                             MachineInstr* DefMI,
 169                             MachineInstr* Barrier,
 170                             MachineBasicBlock* MBB,
 171                             int& SS,
 172                             SmallPtrSet<MachineInstr*, 4>& RefsInMBB);
 173     void RenumberValno(VNInfo* VN);
 174     void ReconstructLiveInterval(LiveInterval* LI);
 175     VNInfo* PerformPHIConstruction(MachineBasicBlock::iterator use,
 176                                    MachineBasicBlock* MBB,
 177                                    LiveInterval* LI,
 178             DenseMap<MachineBasicBlock*, SmallPtrSet<MachineInstr*, 2> >& Defs,
 179             DenseMap<MachineBasicBlock*, SmallPtrSet<MachineInstr*, 2> >& Uses,
 180                                       DenseMap<MachineInstr*, VNInfo*>& NewVNs,
 181                                 DenseMap<MachineBasicBlock*, VNInfo*>& LiveOut,
 182                                 DenseMap<MachineBasicBlock*, VNInfo*>& Phis,
 183                                         bool toplevel, bool intrablock);
 184 };
 185 } // end anonymous namespace
 186
 187 char PreAllocSplitting::ID = 0;
 188
 189 static RegisterPass<PreAllocSplitting>
 190 X("pre-alloc-splitting", "Pre-Register Allocation Live Interval Splitting");
 191
 192 const PassInfo *const llvm::PreAllocSplittingID = &X;
 193
 194
 195 /// findNextEmptySlot - Find a gap after the given machine instruction in the
 196 /// instruction index map. If there isn't one, return end().
 197 MachineBasicBlock::iterator
 198 PreAllocSplitting::findNextEmptySlot(MachineBasicBlock *MBB, MachineInstr *MI,
 199                                      unsigned &SpotIndex) {
 200   MachineBasicBlock::iterator MII = MI;
 201   if (++MII != MBB->end()) {
 202     unsigned Index = LIs->findGapBeforeInstr(LIs->getInstructionIndex(MII));
 203     if (Index) {
 204       SpotIndex = Index;
 205       return MII;
 206     }
 207   }
 208   return MBB->end();
 209 }
 210
 211 /// findSpillPoint - Find a gap as far away from the given MI that's suitable
 212 /// for spilling the current live interval. The index must be before any
 213 /// defs and uses of the live interval register in the mbb. Return begin() if
 214 /// none is found.
 215 MachineBasicBlock::iterator
 216 PreAllocSplitting::findSpillPoint(MachineBasicBlock *MBB, MachineInstr *MI,
 217                                   MachineInstr *DefMI,
 218                                   SmallPtrSet<MachineInstr*, 4> &RefsInMBB,
 219                                   unsigned &SpillIndex) {
 220   MachineBasicBlock::iterator Pt = MBB->begin();
 221
 222   // Go top down if RefsInMBB is empty.
 223   if (RefsInMBB.empty() && !DefMI) {
 224     MachineBasicBlock::iterator MII = MBB->begin();
 225     MachineBasicBlock::iterator EndPt = MI;
 226     do {
 227       ++MII;
 228       unsigned Index = LIs->getInstructionIndex(MII);
 229       unsigned Gap = LIs->findGapBeforeInstr(Index);
 230       if (Gap) {
 231         Pt = MII;
 232         SpillIndex = Gap;
 233         break;
 234       }
 235     } while (MII != EndPt);
 236   } else {
 237     MachineBasicBlock::iterator MII = MI;
 238     MachineBasicBlock::iterator EndPt = DefMI
 239       ? MachineBasicBlock::iterator(DefMI) : MBB->begin();
 240     while (MII != EndPt && !RefsInMBB.count(MII)) {
 241       unsigned Index = LIs->getInstructionIndex(MII);
 242       if (LIs->hasGapBeforeInstr(Index)) {
 243         Pt = MII;
 244         SpillIndex = LIs->findGapBeforeInstr(Index, true);
 245       }
 246       --MII;
 247     }
 248   }
 249
 250   return Pt;
 251 }
 252
 253 /// findRestorePoint - Find a gap in the instruction index map that's suitable
 254 /// for restoring the current live interval value. The index must be before any
 255 /// uses of the live interval register in the mbb. Return end() if none is
 256 /// found.
 257 MachineBasicBlock::iterator
 258 PreAllocSplitting::findRestorePoint(MachineBasicBlock *MBB, MachineInstr *MI,
 259                                     unsigned LastIdx,
 260                                     SmallPtrSet<MachineInstr*, 4> &RefsInMBB,
 261                                     unsigned &RestoreIndex) {
 262   // FIXME: Allow spill to be inserted to the beginning of the mbb. Update mbb
 263   // begin index accordingly.
 264   MachineBasicBlock::iterator Pt = MBB->end();
 265   unsigned EndIdx = LIs->getMBBEndIdx(MBB);
 266
 267   // Go bottom up if RefsInMBB is empty and the end of the mbb isn't beyond
 268   // the last index in the live range.
 269   if (RefsInMBB.empty() && LastIdx >= EndIdx) {
 270     MachineBasicBlock::iterator MII = MBB->getFirstTerminator();
 271     MachineBasicBlock::iterator EndPt = MI;
 272     --MII;
 273     do {
 274       unsigned Index = LIs->getInstructionIndex(MII);
 275       unsigned Gap = LIs->findGapBeforeInstr(Index);
 276       if (Gap) {
 277         Pt = MII;
 278         RestoreIndex = Gap;
 279         break;
 280       }
 281       --MII;
 282     } while (MII != EndPt);
 283   } else {
 284     MachineBasicBlock::iterator MII = MI;
 285     MII = ++MII;
 286     // FIXME: Limit the number of instructions to examine to reduce
 287     // compile time?
 288     while (MII != MBB->end()) {
 289       unsigned Index = LIs->getInstructionIndex(MII);
 290       if (Index > LastIdx)
 291         break;
 292       unsigned Gap = LIs->findGapBeforeInstr(Index);
 293       if (Gap) {
 294         Pt = MII;
 295         RestoreIndex = Gap;
 296       }
 297       if (RefsInMBB.count(MII))
 298         break;
 299       ++MII;
 300     }
 301   }
 302
 303   return Pt;
 304 }
 305
 306 /// CreateSpillStackSlot - Create a stack slot for the live interval being
 307 /// split. If the live interval was previously split, just reuse the same
 308 /// slot.
 309 int PreAllocSplitting::CreateSpillStackSlot(unsigned Reg,
 310                                             const TargetRegisterClass *RC) {
 311   int SS;
 312   DenseMap<unsigned, int>::iterator I = IntervalSSMap.find(Reg);
 313   if (I != IntervalSSMap.end()) {
 314     SS = I->second;
 315   } else {
 316     SS = MFI->CreateStackObject(RC->getSize(), RC->getAlignment());
 317     IntervalSSMap[Reg] = SS;
 318   }
 319
 320   // Create live interval for stack slot.
 321   CurrSLI = &LSs->getOrCreateInterval(SS);
 322   if (CurrSLI->hasAtLeastOneValue())
 323     CurrSValNo = CurrSLI->getValNumInfo(0);
 324   else
 325     CurrSValNo = CurrSLI->getNextValue(~0U, 0, LSs->getVNInfoAllocator());
 326   return SS;
 327 }
 328
 329 /// IsAvailableInStack - Return true if register is available in a split stack
 330 /// slot at the specified index.
 331 bool
 332 PreAllocSplitting::IsAvailableInStack(MachineBasicBlock *DefMBB,
 333                                     unsigned Reg, unsigned DefIndex,
 334                                     unsigned RestoreIndex, unsigned &SpillIndex,
 335                                     int& SS) const {
 336   if (!DefMBB)
 337     return false;
 338
 339   DenseMap<unsigned, int>::iterator I = IntervalSSMap.find(Reg);
 340   if (I == IntervalSSMap.end())
 341     return false;
 342   DenseMap<unsigned, unsigned>::iterator II = Def2SpillMap.find(DefIndex);
 343   if (II == Def2SpillMap.end())
 344     return false;
 345
 346   // If last spill of def is in the same mbb as barrier mbb (where restore will
 347   // be), make sure it's not below the intended restore index.
 348   // FIXME: Undo the previous spill?
 349   assert(LIs->getMBBFromIndex(II->second) == DefMBB);
 350   if (DefMBB == BarrierMBB && II->second >= RestoreIndex)
 351     return false;
 352
 353   SS = I->second;
 354   SpillIndex = II->second;
 355   return true;
 356 }
 357
 358 /// UpdateSpillSlotInterval - Given the specified val# of the register live
 359 /// interval being split, and the spill and restore indicies, update the live
 360 /// interval of the spill stack slot.
 361 void
 362 PreAllocSplitting::UpdateSpillSlotInterval(VNInfo *ValNo, unsigned SpillIndex,
 363                                            unsigned RestoreIndex) {
 364   assert(LIs->getMBBFromIndex(RestoreIndex) == BarrierMBB &&
 365          "Expect restore in the barrier mbb");
 366
 367   MachineBasicBlock *MBB = LIs->getMBBFromIndex(SpillIndex);
 368   if (MBB == BarrierMBB) {
 369     // Intra-block spill + restore. We are done.
 370     LiveRange SLR(SpillIndex, RestoreIndex, CurrSValNo);
 371     CurrSLI->addRange(SLR);
 372     return;
 373   }
 374
 375   SmallPtrSet<MachineBasicBlock*, 4> Processed;
 376   unsigned EndIdx = LIs->getMBBEndIdx(MBB);
 377   LiveRange SLR(SpillIndex, EndIdx+1, CurrSValNo);
 378   CurrSLI->addRange(SLR);
 379   Processed.insert(MBB);
 380
 381   // Start from the spill mbb, figure out the extend of the spill slot's
 382   // live interval.
 383   SmallVector<MachineBasicBlock*, 4> WorkList;
 384   const LiveRange *LR = CurrLI->getLiveRangeContaining(SpillIndex);
 385   if (LR->end > EndIdx)
 386     // If live range extend beyond end of mbb, add successors to work list.
 387     for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
 388            SE = MBB->succ_end(); SI != SE; ++SI)
 389       WorkList.push_back(*SI);
 390
 391   while (!WorkList.empty()) {
 392     MachineBasicBlock *MBB = WorkList.back();
 393     WorkList.pop_back();
 394     if (Processed.count(MBB))
 395       continue;
 396     unsigned Idx = LIs->getMBBStartIdx(MBB);
 397     LR = CurrLI->getLiveRangeContaining(Idx);
 398     if (LR && LR->valno == ValNo) {
 399       EndIdx = LIs->getMBBEndIdx(MBB);
 400       if (Idx <= RestoreIndex && RestoreIndex < EndIdx) {
 401         // Spill slot live interval stops at the restore.
 402         LiveRange SLR(Idx, RestoreIndex, CurrSValNo);
 403         CurrSLI->addRange(SLR);
 404       } else if (LR->end > EndIdx) {
 405         // Live range extends beyond end of mbb, process successors.
 406         LiveRange SLR(Idx, EndIdx+1, CurrSValNo);
 407         CurrSLI->addRange(SLR);
 408         for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
 409                SE = MBB->succ_end(); SI != SE; ++SI)
 410           WorkList.push_back(*SI);
 411       } else {
 412         LiveRange SLR(Idx, LR->end, CurrSValNo);
 413         CurrSLI->addRange(SLR);
 414       }
 415       Processed.insert(MBB);
 416     }
 417   }
 418 }
 419
 420 /// UpdateRegisterInterval - Given the specified val# of the current live
 421 /// interval is being split, and the spill and restore indices, update the live
 422 /// interval accordingly.
 423 VNInfo*
 424 PreAllocSplitting::UpdateRegisterInterval(VNInfo *ValNo, unsigned SpillIndex,
 425                                           unsigned RestoreIndex) {
 426   assert(LIs->getMBBFromIndex(RestoreIndex) == BarrierMBB &&
 427          "Expect restore in the barrier mbb");
 428
 429   SmallVector<std::pair<unsigned,unsigned>, 4> Before;
 430   SmallVector<std::pair<unsigned,unsigned>, 4> After;
 431   SmallVector<unsigned, 4> BeforeKills;
 432   SmallVector<unsigned, 4> AfterKills;
 433   SmallPtrSet<const LiveRange*, 4> Processed;
 434
 435   // First, let's figure out which parts of the live interval is now defined
 436   // by the restore, which are defined by the original definition.
 437   const LiveRange *LR = CurrLI->getLiveRangeContaining(RestoreIndex);
 438   After.push_back(std::make_pair(RestoreIndex, LR->end));
 439   if (CurrLI->isKill(ValNo, LR->end))
 440     AfterKills.push_back(LR->end);
 441
 442   assert(LR->contains(SpillIndex));
 443   if (SpillIndex > LR->start) {
 444     Before.push_back(std::make_pair(LR->start, SpillIndex));
 445     BeforeKills.push_back(SpillIndex);
 446   }
 447   Processed.insert(LR);
 448
 449   // Start from the restore mbb, figure out what part of the live interval
 450   // are defined by the restore.
 451   SmallVector<MachineBasicBlock*, 4> WorkList;
 452   MachineBasicBlock *MBB = BarrierMBB;
 453   for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
 454          SE = MBB->succ_end(); SI != SE; ++SI)
 455     WorkList.push_back(*SI);
 456
 457   SmallPtrSet<MachineBasicBlock*, 4> ProcessedBlocks;
 458   ProcessedBlocks.insert(MBB);
 459
 460   while (!WorkList.empty()) {
 461     MBB = WorkList.back();
 462     WorkList.pop_back();
 463     unsigned Idx = LIs->getMBBStartIdx(MBB);
 464     LR = CurrLI->getLiveRangeContaining(Idx);
 465     if (LR && LR->valno == ValNo && !Processed.count(LR)) {
 466       After.push_back(std::make_pair(LR->start, LR->end));
 467       if (CurrLI->isKill(ValNo, LR->end))
 468         AfterKills.push_back(LR->end);
 469       Idx = LIs->getMBBEndIdx(MBB);
 470       if (LR->end > Idx) {
 471         // Live range extend beyond at least one mbb. Let's see what other
 472         // mbbs it reaches.
 473         LIs->findReachableMBBs(LR->start, LR->end, WorkList);
 474       }
 475       Processed.insert(LR);
 476     }
 477
 478     ProcessedBlocks.insert(MBB);
 479     if (LR)
 480       for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
 481             SE = MBB->succ_end(); SI != SE; ++SI)
 482         if (!ProcessedBlocks.count(*SI))
 483           WorkList.push_back(*SI);
 484   }
 485
 486   for (LiveInterval::iterator I = CurrLI->begin(), E = CurrLI->end();
 487        I != E; ++I) {
 488     LiveRange *LR = I;
 489     if (LR->valno == ValNo && !Processed.count(LR)) {
 490       Before.push_back(std::make_pair(LR->start, LR->end));
 491       if (CurrLI->isKill(ValNo, LR->end))
 492         BeforeKills.push_back(LR->end);
 493     }
 494   }
 495
 496   // Now create new val#s to represent the live ranges defined by the old def
 497   // those defined by the restore.
 498   unsigned AfterDef = ValNo->def;
 499   MachineInstr *AfterCopy = ValNo->copy;
 500   bool HasPHIKill = ValNo->hasPHIKill;
 501   CurrLI->removeValNo(ValNo);
 502   VNInfo *BValNo = (Before.empty())
 503     ? NULL
 504     : CurrLI->getNextValue(AfterDef, AfterCopy, LIs->getVNInfoAllocator());
 505   if (BValNo)
 506     CurrLI->addKills(BValNo, BeforeKills);
 507
 508   VNInfo *AValNo = (After.empty())
 509     ? NULL
 510     : CurrLI->getNextValue(RestoreIndex, 0, LIs->getVNInfoAllocator());
 511   if (AValNo) {
 512     AValNo->hasPHIKill = HasPHIKill;
 513     CurrLI->addKills(AValNo, AfterKills);
 514   }
 515
 516   for (unsigned i = 0, e = Before.size(); i != e; ++i) {
 517     unsigned Start = Before[i].first;
 518     unsigned End   = Before[i].second;
 519     CurrLI->addRange(LiveRange(Start, End, BValNo));
 520   }
 521   for (unsigned i = 0, e = After.size(); i != e; ++i) {
 522     unsigned Start = After[i].first;
 523     unsigned End   = After[i].second;
 524     CurrLI->addRange(LiveRange(Start, End, AValNo));
 525   }
 526
 527   return AValNo;
 528 }
 529
 530 /// ShrinkWrapToLastUse - There are uses of the current live interval in the
 531 /// given block, shrink wrap the live interval to the last use (i.e. remove
 532 /// from last use to the end of the mbb). In case mbb is the where the barrier
 533 /// is, remove from the last use to the barrier.
 534 bool
 535 PreAllocSplitting::ShrinkWrapToLastUse(MachineBasicBlock *MBB, VNInfo *ValNo,
 536                                        SmallVector<MachineOperand*, 4> &Uses,
 537                                        SmallPtrSet<MachineInstr*, 4> &UseMIs) {
 538   MachineOperand *LastMO = 0;
 539   MachineInstr *LastMI = 0;
 540   if (MBB != BarrierMBB && Uses.size() == 1) {
 541     // Single use, no need to traverse the block. We can't assume this for the
 542     // barrier bb though since the use is probably below the barrier.
 543     LastMO = Uses[0];
 544     LastMI = LastMO->getParent();
 545   } else {
 546     MachineBasicBlock::iterator MEE = MBB->begin();
 547     MachineBasicBlock::iterator MII;
 548     if (MBB == BarrierMBB)
 549       MII = Barrier;
 550     else
 551       MII = MBB->end();
 552     while (MII != MEE) {
 553       --MII;
 554       MachineInstr *UseMI = &*MII;
 555       if (!UseMIs.count(UseMI))
 556         continue;
 557       for (unsigned i = 0, e = UseMI->getNumOperands(); i != e; ++i) {
 558         MachineOperand &MO = UseMI->getOperand(i);
 559         if (MO.isReg() && MO.getReg() == CurrLI->reg) {
 560           LastMO = &MO;
 561           break;
 562         }
 563       }
 564       LastMI = UseMI;
 565       break;
 566     }
 567   }
 568
 569   // Cut off live range from last use (or beginning of the mbb if there
 570   // are no uses in it) to the end of the mbb.
 571   unsigned RangeStart, RangeEnd = LIs->getMBBEndIdx(MBB)+1;
 572   if (LastMI) {
 573     RangeStart = LIs->getUseIndex(LIs->getInstructionIndex(LastMI))+1;
 574     assert(!LastMO->isKill() && "Last use already terminates the interval?");
 575     LastMO->setIsKill();
 576   } else {
 577     assert(MBB == BarrierMBB);
 578     RangeStart = LIs->getMBBStartIdx(MBB);
 579   }
 580   if (MBB == BarrierMBB)
 581     RangeEnd = LIs->getUseIndex(BarrierIdx)+1;
 582   CurrLI->removeRange(RangeStart, RangeEnd);
 583   if (LastMI)
 584     CurrLI->addKill(ValNo, RangeStart);
 585
 586   // Return true if the last use becomes a new kill.
 587   return LastMI;
 588 }
 589
 590 /// PerformPHIConstruction - From properly set up use and def lists, use a PHI
 591 /// construction algorithm to compute the ranges and valnos for an interval.
 592 VNInfo* PreAllocSplitting::PerformPHIConstruction(
 593                                                 MachineBasicBlock::iterator use,
 594                                                          MachineBasicBlock* MBB,
 595                                                                LiveInterval* LI,
 596              DenseMap<MachineBasicBlock*, SmallPtrSet<MachineInstr*, 2> >& Defs,
 597              DenseMap<MachineBasicBlock*, SmallPtrSet<MachineInstr*, 2> >& Uses,
 598                                        DenseMap<MachineInstr*, VNInfo*>& NewVNs,
 599                                  DenseMap<MachineBasicBlock*, VNInfo*>& LiveOut,
 600                                  DenseMap<MachineBasicBlock*, VNInfo*>& Phis,
 601                                               bool toplevel, bool intrablock) {
 602   // Return memoized result if it's available.
 603   if (intrablock && NewVNs.count(use))
 604     return NewVNs[use];
 605   else if (!intrablock && LiveOut.count(MBB))
 606     return LiveOut[MBB];
 607
 608   // Insert a sentinel into the map (which also acts as the DFS stack) so that
 609   // we won't get stuck in infinite recursion when processing a loop.
 610   if (!intrablock)
 611     LiveOut[MBB] = 0;
 612
 613   typedef DenseMap<MachineBasicBlock*, SmallPtrSet<MachineInstr*, 2> > RegMap;
 614
 615   // Check if our block contains any uses or defs.
 616   bool ContainsDefs = Defs.count(MBB);
 617   bool ContainsUses = Uses.count(MBB);
 618
 619   VNInfo* ret = 0;
 620
 621   // Enumerate the cases of use/def contaning blocks.
 622   if (!ContainsDefs && !ContainsUses) {
 623   Fallback:
 624     // NOTE: Because this is the fallback case from other cases, we do NOT
 625     // assume that we are not intrablock here.
 626     if (Phis.count(MBB)) return Phis[MBB];
 627
 628     unsigned StartIndex = LIs->getMBBStartIdx(MBB);
 629
 630     if (MBB->pred_size() == 1) {
 631       Phis[MBB] = ret = PerformPHIConstruction((*MBB->pred_begin())->end(),
 632                                           *(MBB->pred_begin()), LI, Defs,
 633                                           Uses, NewVNs, LiveOut, Phis,
 634                                           false, false);
 635       unsigned EndIndex = 0;
 636       if (intrablock) {
 637         EndIndex = LIs->getInstructionIndex(use);
 638         EndIndex = LiveIntervals::getUseIndex(EndIndex);
 639       } else
 640         EndIndex = LIs->getMBBEndIdx(MBB);
 641
 642       LI->addRange(LiveRange(StartIndex, EndIndex+1, ret));
 643     } else {
 644       Phis[MBB] = ret = LI->getNextValue(~0U, /*FIXME*/ 0,
 645                                           LIs->getVNInfoAllocator());
 646       if (!intrablock) LiveOut[MBB] = ret;
 647
 648       // If there are no uses or defs between our starting point and the
 649       // beginning of the block, then recursive perform phi construction
 650       // on our predecessors.
 651       DenseMap<MachineBasicBlock*, VNInfo*> IncomingVNs;
 652       for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
 653            PE = MBB->pred_end(); PI != PE; ++PI) {
 654         VNInfo* Incoming = PerformPHIConstruction((*PI)->end(), *PI, LI, Defs,
 655                                             Uses, NewVNs, LiveOut, Phis,
 656                                             false, false);
 657         if (Incoming != 0)
 658           IncomingVNs[*PI] = Incoming;
 659       }
 660
 661       // Otherwise, merge the incoming VNInfos with a phi join.  Create a new
 662       // VNInfo to represent the joined value.
 663       for (DenseMap<MachineBasicBlock*, VNInfo*>::iterator I =
 664            IncomingVNs.begin(), E = IncomingVNs.end(); I != E; ++I) {
 665         I->second->hasPHIKill = true;
 666         unsigned KillIndex = LIs->getMBBEndIdx(I->first);
 667         LI->addKill(I->second, KillIndex);
 668       }
 669
 670       unsigned EndIndex = 0;
 671       if (intrablock) {
 672         EndIndex = LIs->getInstructionIndex(use);
 673         EndIndex = LiveIntervals::getUseIndex(EndIndex);
 674       } else
 675         EndIndex = LIs->getMBBEndIdx(MBB);
 676       LI->addRange(LiveRange(StartIndex, EndIndex+1, ret));
 677     }
 678   } else if (ContainsDefs && !ContainsUses) {
 679     SmallPtrSet<MachineInstr*, 2>& BlockDefs = Defs[MBB];
 680
 681     // Search for the def in this block.  If we don't find it before the
 682     // instruction we care about, go to the fallback case.  Note that that
 683     // should never happen: this cannot be intrablock, so use should
 684     // always be an end() iterator.
 685     assert(use == MBB->end() && "No use marked in intrablock");
 686
 687     MachineBasicBlock::iterator walker = use;
 688     --walker;
 689     while (walker != MBB->begin())
 690       if (BlockDefs.count(walker)) {
 691         break;
 692       } else
 693         --walker;
 694
 695     // Once we've found it, extend its VNInfo to our instruction.
 696     unsigned DefIndex = LIs->getInstructionIndex(walker);
 697     DefIndex = LiveIntervals::getDefIndex(DefIndex);
 698     unsigned EndIndex = LIs->getMBBEndIdx(MBB);
 699
 700     ret = NewVNs[walker];
 701     LI->addRange(LiveRange(DefIndex, EndIndex+1, ret));
 702   } else if (!ContainsDefs && ContainsUses) {
 703     SmallPtrSet<MachineInstr*, 2>& BlockUses = Uses[MBB];
 704
 705     // Search for the use in this block that precedes the instruction we care
 706     // about, going to the fallback case if we don't find it.
 707
 708     if (use == MBB->begin())
 709       goto Fallback;
 710
 711     MachineBasicBlock::iterator walker = use;
 712     --walker;
 713     bool found = false;
 714     while (walker != MBB->begin())
 715       if (BlockUses.count(walker)) {
 716         found = true;
 717         break;
 718       } else
 719         --walker;
 720
 721     // Must check begin() too.
 722     if (!found) {
 723       if (BlockUses.count(walker))
 724         found = true;
 725       else
 726         goto Fallback;
 727     }
 728
 729     unsigned UseIndex = LIs->getInstructionIndex(walker);
 730     UseIndex = LiveIntervals::getUseIndex(UseIndex);
 731     unsigned EndIndex = 0;
 732     if (intrablock) {
 733       EndIndex = LIs->getInstructionIndex(use);
 734       EndIndex = LiveIntervals::getUseIndex(EndIndex);
 735     } else
 736       EndIndex = LIs->getMBBEndIdx(MBB);
 737
 738     // Now, recursively phi construct the VNInfo for the use we found,
 739     // and then extend it to include the instruction we care about
 740     ret = PerformPHIConstruction(walker, MBB, LI, Defs, Uses,
 741                                  NewVNs, LiveOut, Phis, false, true);
 742
 743     // FIXME: Need to set kills properly for inter-block stuff.
 744     if (LI->isKill(ret, UseIndex)) LI->removeKill(ret, UseIndex);
 745     if (intrablock)
 746       LI->addKill(ret, EndIndex);
 747
 748     LI->addRange(LiveRange(UseIndex, EndIndex+1, ret));
 749   } else if (ContainsDefs && ContainsUses){
 750     SmallPtrSet<MachineInstr*, 2>& BlockDefs = Defs[MBB];
 751     SmallPtrSet<MachineInstr*, 2>& BlockUses = Uses[MBB];
 752
 753     // This case is basically a merging of the two preceding case, with the
 754     // special note that checking for defs must take precedence over checking
 755     // for uses, because of two-address instructions.
 756
 757     if (use == MBB->begin())
 758       goto Fallback;
 759
 760     MachineBasicBlock::iterator walker = use;
 761     --walker;
 762     bool foundDef = false;
 763     bool foundUse = false;
 764     while (walker != MBB->begin())
 765       if (BlockDefs.count(walker)) {
 766         foundDef = true;
 767         break;
 768       } else if (BlockUses.count(walker)) {
 769         foundUse = true;
 770         break;
 771       } else
 772         --walker;
 773
 774     // Must check begin() too.
 775     if (!foundDef && !foundUse) {
 776       if (BlockDefs.count(walker))
 777         foundDef = true;
 778       else if (BlockUses.count(walker))
 779         foundUse = true;
 780       else
 781         goto Fallback;
 782     }
 783
 784     unsigned StartIndex = LIs->getInstructionIndex(walker);
 785     StartIndex = foundDef ? LiveIntervals::getDefIndex(StartIndex) :
 786                             LiveIntervals::getUseIndex(StartIndex);
 787     unsigned EndIndex = 0;
 788     if (intrablock) {
 789       EndIndex = LIs->getInstructionIndex(use);
 790       EndIndex = LiveIntervals::getUseIndex(EndIndex);
 791     } else
 792       EndIndex = LIs->getMBBEndIdx(MBB);
 793
 794     if (foundDef)
 795       ret = NewVNs[walker];
 796     else
 797       ret = PerformPHIConstruction(walker, MBB, LI, Defs, Uses,
 798                                    NewVNs, LiveOut, Phis, false, true);
 799
 800     if (foundUse && LI->isKill(ret, StartIndex))
 801       LI->removeKill(ret, StartIndex);
 802     if (intrablock) {
 803       LI->addKill(ret, EndIndex);
 804     }
 805
 806     LI->addRange(LiveRange(StartIndex, EndIndex+1, ret));
 807   }
 808
 809   // Memoize results so we don't have to recompute them.
 810   if (!intrablock) LiveOut[MBB] = ret;
 811   else NewVNs[use] = ret;
 812
 813   return ret;
 814 }
 815
 816 /// ReconstructLiveInterval - Recompute a live interval from scratch.
 817 void PreAllocSplitting::ReconstructLiveInterval(LiveInterval* LI) {
 818   BumpPtrAllocator& Alloc = LIs->getVNInfoAllocator();
 819
 820   // Clear the old ranges and valnos;
 821   LI->clear();
 822
 823   // Cache the uses and defs of the register
 824   typedef DenseMap<MachineBasicBlock*, SmallPtrSet<MachineInstr*, 2> > RegMap;
 825   RegMap Defs, Uses;
 826
 827   // Keep track of the new VNs we're creating.
 828   DenseMap<MachineInstr*, VNInfo*> NewVNs;
 829   SmallPtrSet<VNInfo*, 2> PhiVNs;
 830
 831   // Cache defs, and create a new VNInfo for each def.
 832   for (MachineRegisterInfo::def_iterator DI = MRI->def_begin(LI->reg),
 833        DE = MRI->def_end(); DI != DE; ++DI) {
 834     Defs[(*DI).getParent()].insert(&*DI);
 835
 836     unsigned DefIdx = LIs->getInstructionIndex(&*DI);
 837     DefIdx = LiveIntervals::getDefIndex(DefIdx);
 838
 839     VNInfo* NewVN = LI->getNextValue(DefIdx, /*FIXME*/ 0, Alloc);
 840     NewVNs[&*DI] = NewVN;
 841   }
 842
 843   // Cache uses as a separate pass from actually processing them.
 844   for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(LI->reg),
 845        UE = MRI->use_end(); UI != UE; ++UI)
 846     Uses[(*UI).getParent()].insert(&*UI);
 847
 848   // Now, actually process every use and use a phi construction algorithm
 849   // to walk from it to its reaching definitions, building VNInfos along
 850   // the way.
 851   DenseMap<MachineBasicBlock*, VNInfo*> LiveOut;
 852   DenseMap<MachineBasicBlock*, VNInfo*> Phis;
 853   for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(LI->reg),
 854        UE = MRI->use_end(); UI != UE; ++UI) {
 855     PerformPHIConstruction(&*UI, UI->getParent(), LI, Defs,
 856                            Uses, NewVNs, LiveOut, Phis, true, true);
 857   }
 858
 859   // Add ranges for dead defs
 860   for (MachineRegisterInfo::def_iterator DI = MRI->def_begin(LI->reg),
 861        DE = MRI->def_end(); DI != DE; ++DI) {
 862     unsigned DefIdx = LIs->getInstructionIndex(&*DI);
 863     DefIdx = LiveIntervals::getDefIndex(DefIdx);
 864
 865     if (LI->liveAt(DefIdx)) continue;
 866
 867     VNInfo* DeadVN = NewVNs[&*DI];
 868     LI->addRange(LiveRange(DefIdx, DefIdx+1, DeadVN));
 869     LI->addKill(DeadVN, DefIdx);
 870   }
 871 }
 872
 873 /// ShrinkWrapLiveInterval - Recursively traverse the predecessor
 874 /// chain to find the new 'kills' and shrink wrap the live interval to the
 875 /// new kill indices.
 876 void
 877 PreAllocSplitting::ShrinkWrapLiveInterval(VNInfo *ValNo, MachineBasicBlock *MBB,
 878                           MachineBasicBlock *SuccMBB, MachineBasicBlock *DefMBB,
 879                                     SmallPtrSet<MachineBasicBlock*, 8> &Visited,
 880            DenseMap<MachineBasicBlock*, SmallVector<MachineOperand*, 4> > &Uses,
 881            DenseMap<MachineBasicBlock*, SmallPtrSet<MachineInstr*, 4> > &UseMIs,
 882                                   SmallVector<MachineBasicBlock*, 4> &UseMBBs) {
 883   if (Visited.count(MBB))
 884     return;
 885
 886   // If live interval is live in another successor path, then we can't process
 887   // this block. But we may able to do so after all the successors have been
 888   // processed.
 889   if (MBB != BarrierMBB) {
 890     for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
 891            SE = MBB->succ_end(); SI != SE; ++SI) {
 892       MachineBasicBlock *SMBB = *SI;
 893       if (SMBB == SuccMBB)
 894         continue;
 895       if (CurrLI->liveAt(LIs->getMBBStartIdx(SMBB)))
 896         return;
 897     }
 898   }
 899
 900   Visited.insert(MBB);
 901
 902   DenseMap<MachineBasicBlock*, SmallVector<MachineOperand*, 4> >::iterator
 903     UMII = Uses.find(MBB);
 904   if (UMII != Uses.end()) {
 905     // At least one use in this mbb, lets look for the kill.
 906     DenseMap<MachineBasicBlock*, SmallPtrSet<MachineInstr*, 4> >::iterator
 907       UMII2 = UseMIs.find(MBB);
 908     if (ShrinkWrapToLastUse(MBB, ValNo, UMII->second, UMII2->second))
 909       // Found a kill, shrink wrapping of this path ends here.
 910       return;
 911   } else if (MBB == DefMBB) {
 912     // There are no uses after the def.
 913     MachineInstr *DefMI = LIs->getInstructionFromIndex(ValNo->def);
 914     if (UseMBBs.empty()) {
 915       // The only use must be below barrier in the barrier block. It's safe to
 916       // remove the def.
 917       LIs->RemoveMachineInstrFromMaps(DefMI);
 918       DefMI->eraseFromParent();
 919       CurrLI->removeRange(ValNo->def, LIs->getMBBEndIdx(MBB)+1);
 920     }
 921   } else if (MBB == BarrierMBB) {
 922     // Remove entire live range from start of mbb to barrier.
 923     CurrLI->removeRange(LIs->getMBBStartIdx(MBB),
 924                         LIs->getUseIndex(BarrierIdx)+1);
 925   } else {
 926     // Remove entire live range of the mbb out of the live interval.
 927     CurrLI->removeRange(LIs->getMBBStartIdx(MBB), LIs->getMBBEndIdx(MBB)+1);
 928   }
 929
 930   if (MBB == DefMBB)
 931     // Reached the def mbb, stop traversing this path further.
 932     return;
 933
 934   // Traverse the pathes up the predecessor chains further.
 935   for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
 936          PE = MBB->pred_end(); PI != PE; ++PI) {
 937     MachineBasicBlock *Pred = *PI;
 938     if (Pred == MBB)
 939       continue;
 940     if (Pred == DefMBB && ValNo->hasPHIKill)
 941       // Pred is the def bb and the def reaches other val#s, we must
 942       // allow the value to be live out of the bb.
 943       continue;
 944     if (!CurrLI->liveAt(LIs->getMBBEndIdx(Pred)-1))
 945       return;
 946     ShrinkWrapLiveInterval(ValNo, Pred, MBB, DefMBB, Visited,
 947                            Uses, UseMIs, UseMBBs);
 948   }
 949
 950   return;
 951 }
 952
 953
 954 void PreAllocSplitting::RepairLiveInterval(LiveInterval* CurrLI,
 955                                            VNInfo* ValNo,
 956                                            MachineInstr* DefMI,
 957                                            unsigned RestoreIdx) {
 958   // Shrink wrap the live interval by walking up the CFG and find the
 959   // new kills.
 960   // Now let's find all the uses of the val#.
 961   DenseMap<MachineBasicBlock*, SmallVector<MachineOperand*, 4> > Uses;
 962   DenseMap<MachineBasicBlock*, SmallPtrSet<MachineInstr*, 4> > UseMIs;
 963   SmallPtrSet<MachineBasicBlock*, 4> Seen;
 964   SmallVector<MachineBasicBlock*, 4> UseMBBs;
 965   for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(CurrLI->reg),
 966          UE = MRI->use_end(); UI != UE; ++UI) {
 967     MachineOperand &UseMO = UI.getOperand();
 968     MachineInstr *UseMI = UseMO.getParent();
 969     unsigned UseIdx = LIs->getInstructionIndex(UseMI);
 970     LiveInterval::iterator ULR = CurrLI->FindLiveRangeContaining(UseIdx);
 971     if (ULR->valno != ValNo)
 972       continue;
 973     MachineBasicBlock *UseMBB = UseMI->getParent();
 974     // Remember which other mbb's use this val#.
 975     if (Seen.insert(UseMBB) && UseMBB != BarrierMBB)
 976       UseMBBs.push_back(UseMBB);
 977     DenseMap<MachineBasicBlock*, SmallVector<MachineOperand*, 4> >::iterator
 978       UMII = Uses.find(UseMBB);
 979     if (UMII != Uses.end()) {
 980       DenseMap<MachineBasicBlock*, SmallPtrSet<MachineInstr*, 4> >::iterator
 981         UMII2 = UseMIs.find(UseMBB);
 982       UMII->second.push_back(&UseMO);
 983       UMII2->second.insert(UseMI);
 984     } else {
 985       SmallVector<MachineOperand*, 4> Ops;
 986       Ops.push_back(&UseMO);
 987       Uses.insert(std::make_pair(UseMBB, Ops));
 988       SmallPtrSet<MachineInstr*, 4> MIs;
 989       MIs.insert(UseMI);
 990       UseMIs.insert(std::make_pair(UseMBB, MIs));
 991     }
 992   }
 993
 994   // Walk up the predecessor chains.
 995   SmallPtrSet<MachineBasicBlock*, 8> Visited;
 996   ShrinkWrapLiveInterval(ValNo, BarrierMBB, NULL, DefMI->getParent(), Visited,
 997                          Uses, UseMIs, UseMBBs);
 998
 999   // Remove live range from barrier to the restore. FIXME: Find a better
1000   // point to re-start the live interval.
1001   VNInfo* AfterValNo = UpdateRegisterInterval(ValNo,
1002                                               LIs->getUseIndex(BarrierIdx)+1,
1003                                               LIs->getDefIndex(RestoreIdx));
1004
1005   // Attempt to renumber the new valno into a new vreg.
1006   RenumberValno(AfterValNo);
1007 }
1008
1009 /// RenumberValno - Split the given valno out into a new vreg, allowing it to
1010 /// be allocated to a different register.  This function creates a new vreg,
1011 /// copies the valno and its live ranges over to the new vreg's interval,
1012 /// removes them from the old interval, and rewrites all uses and defs of
1013 /// the original reg to the new vreg within those ranges.
1014 void PreAllocSplitting::RenumberValno(VNInfo* VN) {
1015   SmallVector<VNInfo*, 4> Stack;
1016   SmallVector<VNInfo*, 4> VNsToCopy;
1017   Stack.push_back(VN);
1018
1019   // Walk through and copy the valno we care about, and any other valnos
1020   // that are two-address redefinitions of the one we care about.  These
1021   // will need to be rewritten as well.  We also check for safety of the
1022   // renumbering here, by making sure that none of the valno involved has
1023   // phi kills.
1024   while (!Stack.empty()) {
1025     VNInfo* OldVN = Stack.back();
1026     Stack.pop_back();
1027
1028     // Bail out if we ever encounter a valno that has a PHI kill.  We can't
1029     // renumber these.
1030     if (OldVN->hasPHIKill) return;
1031
1032     VNsToCopy.push_back(OldVN);
1033
1034     // Locate two-address redefinitions
1035     for (SmallVector<unsigned, 4>::iterator KI = OldVN->kills.begin(),
1036          KE = OldVN->kills.end(); KI != KE; ++KI) {
1037       MachineInstr* MI = LIs->getInstructionFromIndex(*KI);
1038       //if (!MI) continue;
1039       unsigned DefIdx = MI->findRegisterDefOperandIdx(CurrLI->reg);
1040       if (DefIdx == ~0U) continue;
1041       if (MI->isRegReDefinedByTwoAddr(DefIdx)) {
1042         VNInfo* NextVN =
1043                      CurrLI->findDefinedVNInfo(LiveIntervals::getDefIndex(*KI));
1044         Stack.push_back(NextVN);
1045       }
1046     }
1047   }
1048
1049   // Create the new vreg
1050   unsigned NewVReg = MRI->createVirtualRegister(MRI->getRegClass(CurrLI->reg));
1051
1052   // Create the new live interval
1053   LiveInterval& NewLI = LIs->getOrCreateInterval(NewVReg);
1054
1055   for (SmallVector<VNInfo*, 4>::iterator OI = VNsToCopy.begin(), OE =
1056        VNsToCopy.end(); OI != OE; ++OI) {
1057     VNInfo* OldVN = *OI;
1058
1059     // Copy the valno over
1060     VNInfo* NewVN = NewLI.getNextValue(OldVN->def, OldVN->copy,
1061                                        LIs->getVNInfoAllocator());
1062     NewLI.copyValNumInfo(NewVN, OldVN);
1063     NewLI.MergeValueInAsValue(*CurrLI, OldVN, NewVN);
1064
1065     // Remove the valno from the old interval
1066     CurrLI->removeValNo(OldVN);
1067   }
1068
1069   // Rewrite defs and uses.  This is done in two stages to avoid invalidating
1070   // the reg_iterator.
1071   SmallVector<std::pair<MachineInstr*, unsigned>, 8> OpsToChange;
1072
1073   for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(CurrLI->reg),
1074          E = MRI->reg_end(); I != E; ++I) {
1075     MachineOperand& MO = I.getOperand();
1076     unsigned InstrIdx = LIs->getInstructionIndex(&*I);
1077
1078     if ((MO.isUse() && NewLI.liveAt(LiveIntervals::getUseIndex(InstrIdx))) ||
1079         (MO.isDef() && NewLI.liveAt(LiveIntervals::getDefIndex(InstrIdx))))
1080       OpsToChange.push_back(std::make_pair(&*I, I.getOperandNo()));
1081   }
1082
1083   for (SmallVector<std::pair<MachineInstr*, unsigned>, 8>::iterator I =
1084        OpsToChange.begin(), E = OpsToChange.end(); I != E; ++I) {
1085     MachineInstr* Inst = I->first;
1086     unsigned OpIdx = I->second;
1087     MachineOperand& MO = Inst->getOperand(OpIdx);
1088     MO.setReg(NewVReg);
1089   }
1090
1091   NumRenumbers++;
1092 }
1093
1094 bool PreAllocSplitting::Rematerialize(unsigned vreg, VNInfo* ValNo,
1095                                       MachineInstr* DefMI,
1096                                       MachineBasicBlock::iterator RestorePt,
1097                                       unsigned RestoreIdx,
1098                                     SmallPtrSet<MachineInstr*, 4>& RefsInMBB) {
1099   MachineBasicBlock& MBB = *RestorePt->getParent();
1100
1101   MachineBasicBlock::iterator KillPt = BarrierMBB->end();
1102   unsigned KillIdx = 0;
1103   if (ValNo->def == ~0U || DefMI->getParent() == BarrierMBB)
1104     KillPt = findSpillPoint(BarrierMBB, Barrier, NULL, RefsInMBB, KillIdx);
1105   else
1106     KillPt = findNextEmptySlot(DefMI->getParent(), DefMI, KillIdx);
1107
1108   if (KillPt == DefMI->getParent()->end())
1109     return false;
1110
1111   TII->reMaterialize(MBB, RestorePt, vreg, DefMI);
1112   LIs->InsertMachineInstrInMaps(prior(RestorePt), RestoreIdx);
1113
1114   if (KillPt->getParent() == BarrierMBB) {
1115     UpdateRegisterInterval(ValNo, LIs->getUseIndex(KillIdx)+1,
1116                            LIs->getDefIndex(RestoreIdx));
1117
1118     ++NumSplits;
1119     ++NumRemats;
1120     return true;
1121   }
1122
1123   RepairLiveInterval(CurrLI, ValNo, DefMI, RestoreIdx);
1124
1125   ++NumSplits;
1126   ++NumRemats;
1127   return true;
1128 }
1129
1130 MachineInstr* PreAllocSplitting::FoldSpill(unsigned vreg,
1131                                            const TargetRegisterClass* RC,
1132                                            MachineInstr* DefMI,
1133                                            MachineInstr* Barrier,
1134                                            MachineBasicBlock* MBB,
1135                                            int& SS,
1136                                     SmallPtrSet<MachineInstr*, 4>& RefsInMBB) {
1137   MachineBasicBlock::iterator Pt = MBB->begin();
1138
1139   // Go top down if RefsInMBB is empty.
1140   if (RefsInMBB.empty())
1141     return 0;
1142
1143   MachineBasicBlock::iterator FoldPt = Barrier;
1144   while (&*FoldPt != DefMI && FoldPt != MBB->begin() &&
1145          !RefsInMBB.count(FoldPt))
1146     --FoldPt;
1147
1148   int OpIdx = FoldPt->findRegisterDefOperandIdx(vreg, false);
1149   if (OpIdx == -1)
1150     return 0;
1151
1152   SmallVector<unsigned, 1> Ops;
1153   Ops.push_back(OpIdx);
1154
1155   if (!TII->canFoldMemoryOperand(FoldPt, Ops))
1156     return 0;
1157
1158   DenseMap<unsigned, int>::iterator I = IntervalSSMap.find(vreg);
1159   if (I != IntervalSSMap.end()) {
1160     SS = I->second;
1161   } else {
1162     SS = MFI->CreateStackObject(RC->getSize(), RC->getAlignment());
1163
1164   }
1165
1166   MachineInstr* FMI = TII->foldMemoryOperand(*MBB->getParent(),
1167                                              FoldPt, Ops, SS);
1168
1169   if (FMI) {
1170     LIs->ReplaceMachineInstrInMaps(FoldPt, FMI);
1171     FMI = MBB->insert(MBB->erase(FoldPt), FMI);
1172     ++NumFolds;
1173
1174     IntervalSSMap[vreg] = SS;
1175     CurrSLI = &LSs->getOrCreateInterval(SS);
1176     if (CurrSLI->hasAtLeastOneValue())
1177       CurrSValNo = CurrSLI->getValNumInfo(0);
1178     else
1179       CurrSValNo = CurrSLI->getNextValue(~0U, 0, LSs->getVNInfoAllocator());
1180   }
1181
1182   return FMI;
1183 }
1184
1185 /// SplitRegLiveInterval - Split (spill and restore) the given live interval
1186 /// so it would not cross the barrier that's being processed. Shrink wrap
1187 /// (minimize) the live interval to the last uses.
1188 bool PreAllocSplitting::SplitRegLiveInterval(LiveInterval *LI) {
1189   CurrLI = LI;
1190
1191   // Find live range where current interval cross the barrier.
1192   LiveInterval::iterator LR =
1193     CurrLI->FindLiveRangeContaining(LIs->getUseIndex(BarrierIdx));
1194   VNInfo *ValNo = LR->valno;
1195
1196   if (ValNo->def == ~1U) {
1197     // Defined by a dead def? How can this be?
1198     assert(0 && "Val# is defined by a dead def?");
1199     abort();
1200   }
1201
1202   MachineInstr *DefMI = (ValNo->def != ~0U)
1203     ? LIs->getInstructionFromIndex(ValNo->def) : NULL;
1204
1205   // If this would create a new join point, do not split.
1206   if (DefMI && createsNewJoin(LR, DefMI->getParent(), Barrier->getParent()))
1207     return false;
1208
1209   // Find all references in the barrier mbb.
1210   SmallPtrSet<MachineInstr*, 4> RefsInMBB;
1211   for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(CurrLI->reg),
1212          E = MRI->reg_end(); I != E; ++I) {
1213     MachineInstr *RefMI = &*I;
1214     if (RefMI->getParent() == BarrierMBB)
1215       RefsInMBB.insert(RefMI);
1216   }
1217
1218   // Find a point to restore the value after the barrier.
1219   unsigned RestoreIndex;
1220   MachineBasicBlock::iterator RestorePt =
1221     findRestorePoint(BarrierMBB, Barrier, LR->end, RefsInMBB, RestoreIndex);
1222   if (RestorePt == BarrierMBB->end())
1223     return false;
1224
1225   if (DefMI && LIs->isReMaterializable(*LI, ValNo, DefMI))
1226     if (Rematerialize(LI->reg, ValNo, DefMI, RestorePt,
1227                       RestoreIndex, RefsInMBB))
1228     return true;
1229
1230   // Add a spill either before the barrier or after the definition.
1231   MachineBasicBlock *DefMBB = DefMI ? DefMI->getParent() : NULL;
1232   const TargetRegisterClass *RC = MRI->getRegClass(CurrLI->reg);
1233   unsigned SpillIndex = 0;
1234   MachineInstr *SpillMI = NULL;
1235   int SS = -1;
1236   if (ValNo->def == ~0U) {
1237     // If it's defined by a phi, we must split just before the barrier.
1238     if ((SpillMI = FoldSpill(LI->reg, RC, 0, Barrier,
1239                             BarrierMBB, SS, RefsInMBB))) {
1240       SpillIndex = LIs->getInstructionIndex(SpillMI);
1241     } else {
1242       MachineBasicBlock::iterator SpillPt =
1243         findSpillPoint(BarrierMBB, Barrier, NULL, RefsInMBB, SpillIndex);
1244       if (SpillPt == BarrierMBB->begin())
1245         return false; // No gap to insert spill.
1246       // Add spill.
1247
1248       SS = CreateSpillStackSlot(CurrLI->reg, RC);
1249       TII->storeRegToStackSlot(*BarrierMBB, SpillPt, CurrLI->reg, true, SS, RC);
1250       SpillMI = prior(SpillPt);
1251       LIs->InsertMachineInstrInMaps(SpillMI, SpillIndex);
1252     }
1253   } else if (!IsAvailableInStack(DefMBB, CurrLI->reg, ValNo->def,
1254                                  RestoreIndex, SpillIndex, SS)) {
1255     // If it's already split, just restore the value. There is no need to spill
1256     // the def again.
1257     if (!DefMI)
1258       return false; // Def is dead. Do nothing.
1259
1260     if ((SpillMI = FoldSpill(LI->reg, RC, DefMI, Barrier,
1261                             BarrierMBB, SS, RefsInMBB))) {
1262       SpillIndex = LIs->getInstructionIndex(SpillMI);
1263     } else {
1264       // Check if it's possible to insert a spill after the def MI.
1265       MachineBasicBlock::iterator SpillPt;
1266       if (DefMBB == BarrierMBB) {
1267         // Add spill after the def and the last use before the barrier.
1268         SpillPt = findSpillPoint(BarrierMBB, Barrier, DefMI,
1269                                  RefsInMBB, SpillIndex);
1270         if (SpillPt == DefMBB->begin())
1271           return false; // No gap to insert spill.
1272       } else {
1273         SpillPt = findNextEmptySlot(DefMBB, DefMI, SpillIndex);
1274         if (SpillPt == DefMBB->end())
1275           return false; // No gap to insert spill.
1276       }
1277       // Add spill. The store instruction kills the register if def is before
1278       // the barrier in the barrier block.
1279       SS = CreateSpillStackSlot(CurrLI->reg, RC);
1280       TII->storeRegToStackSlot(*DefMBB, SpillPt, CurrLI->reg,
1281                                DefMBB == BarrierMBB, SS, RC);
1282       SpillMI = prior(SpillPt);
1283       LIs->InsertMachineInstrInMaps(SpillMI, SpillIndex);
1284     }
1285   }
1286
1287   // Remember def instruction index to spill index mapping.
1288   if (DefMI && SpillMI)
1289     Def2SpillMap[ValNo->def] = SpillIndex;
1290
1291   // Add restore.
1292   TII->loadRegFromStackSlot(*BarrierMBB, RestorePt, CurrLI->reg, SS, RC);
1293   MachineInstr *LoadMI = prior(RestorePt);
1294   LIs->InsertMachineInstrInMaps(LoadMI, RestoreIndex);
1295
1296   // If live interval is spilled in the same block as the barrier, just
1297   // create a hole in the interval.
1298   if (!DefMBB ||
1299       (SpillMI && SpillMI->getParent() == BarrierMBB)) {
1300     // Update spill stack slot live interval.
1301     UpdateSpillSlotInterval(ValNo, LIs->getUseIndex(SpillIndex)+1,
1302                             LIs->getDefIndex(RestoreIndex));
1303
1304     UpdateRegisterInterval(ValNo, LIs->getUseIndex(SpillIndex)+1,
1305                            LIs->getDefIndex(RestoreIndex));
1306
1307     ++NumSplits;
1308     return true;
1309   }
1310
1311   // Update spill stack slot live interval.
1312   UpdateSpillSlotInterval(ValNo, LIs->getUseIndex(SpillIndex)+1,
1313                           LIs->getDefIndex(RestoreIndex));
1314
1315   RepairLiveInterval(CurrLI, ValNo, DefMI, RestoreIndex);
1316
1317   ++NumSplits;
1318   return true;
1319 }
1320
1321 /// SplitRegLiveIntervals - Split all register live intervals that cross the
1322 /// barrier that's being processed.
1323 bool
1324 PreAllocSplitting::SplitRegLiveIntervals(const TargetRegisterClass **RCs) {
1325   // First find all the virtual registers whose live intervals are intercepted
1326   // by the current barrier.
1327   SmallVector<LiveInterval*, 8> Intervals;
1328   for (const TargetRegisterClass **RC = RCs; *RC; ++RC) {
1329     if (TII->IgnoreRegisterClassBarriers(*RC))
1330       continue;
1331     std::vector<unsigned> &VRs = MRI->getRegClassVirtRegs(*RC);
1332     for (unsigned i = 0, e = VRs.size(); i != e; ++i) {
1333       unsigned Reg = VRs[i];
1334       if (!LIs->hasInterval(Reg))
1335         continue;
1336       LiveInterval *LI = &LIs->getInterval(Reg);
1337       if (LI->liveAt(BarrierIdx) && !Barrier->readsRegister(Reg))
1338         // Virtual register live interval is intercepted by the barrier. We
1339         // should split and shrink wrap its interval if possible.
1340         Intervals.push_back(LI);
1341     }
1342   }
1343
1344   // Process the affected live intervals.
1345   bool Change = false;
1346   while (!Intervals.empty()) {
1347     if (PreSplitLimit != -1 && (int)NumSplits == PreSplitLimit)
1348       break;
1349     LiveInterval *LI = Intervals.back();
1350     Intervals.pop_back();
1351     Change |= SplitRegLiveInterval(LI);
1352   }
1353
1354   return Change;
1355 }
1356
1357 bool PreAllocSplitting::createsNewJoin(LiveRange* LR,
1358                                        MachineBasicBlock* DefMBB,
1359                                        MachineBasicBlock* BarrierMBB) {
1360   if (DefMBB == BarrierMBB)
1361     return false;
1362
1363   if (LR->valno->hasPHIKill)
1364     return false;
1365
1366   unsigned MBBEnd = LIs->getMBBEndIdx(BarrierMBB);
1367   if (LR->end < MBBEnd)
1368     return false;
1369
1370   MachineLoopInfo& MLI = getAnalysis<MachineLoopInfo>();
1371   if (MLI.getLoopFor(DefMBB) != MLI.getLoopFor(BarrierMBB))
1372     return true;
1373
1374   MachineDominatorTree& MDT = getAnalysis<MachineDominatorTree>();
1375   SmallPtrSet<MachineBasicBlock*, 4> Visited;
1376   typedef std::pair<MachineBasicBlock*,
1377                     MachineBasicBlock::succ_iterator> ItPair;
1378   SmallVector<ItPair, 4> Stack;
1379   Stack.push_back(std::make_pair(BarrierMBB, BarrierMBB->succ_begin()));
1380
1381   while (!Stack.empty()) {
1382     ItPair P = Stack.back();
1383     Stack.pop_back();
1384
1385     MachineBasicBlock* PredMBB = P.first;
1386     MachineBasicBlock::succ_iterator S = P.second;
1387
1388     if (S == PredMBB->succ_end())
1389       continue;
1390     else if (Visited.count(*S)) {
1391       Stack.push_back(std::make_pair(PredMBB, ++S));
1392       continue;
1393     } else
1394       Stack.push_back(std::make_pair(PredMBB, S+1));
1395
1396     MachineBasicBlock* MBB = *S;
1397     Visited.insert(MBB);
1398
1399     if (MBB == BarrierMBB)
1400       return true;
1401
1402     MachineDomTreeNode* DefMDTN = MDT.getNode(DefMBB);
1403     MachineDomTreeNode* BarrierMDTN = MDT.getNode(BarrierMBB);
1404     MachineDomTreeNode* MDTN = MDT.getNode(MBB)->getIDom();
1405     while (MDTN) {
1406       if (MDTN == DefMDTN)
1407         return true;
1408       else if (MDTN == BarrierMDTN)
1409         break;
1410       MDTN = MDTN->getIDom();
1411     }
1412
1413     MBBEnd = LIs->getMBBEndIdx(MBB);
1414     if (LR->end > MBBEnd)
1415       Stack.push_back(std::make_pair(MBB, MBB->succ_begin()));
1416   }
1417
1418   return false;
1419 }
1420
1421
1422 bool PreAllocSplitting::runOnMachineFunction(MachineFunction &MF) {
1423   CurrMF = &MF;
1424   TM     = &MF.getTarget();
1425   TII    = TM->getInstrInfo();
1426   MFI    = MF.getFrameInfo();
1427   MRI    = &MF.getRegInfo();
1428   LIs    = &getAnalysis<LiveIntervals>();
1429   LSs    = &getAnalysis<LiveStacks>();
1430
1431   bool MadeChange = false;
1432
1433   // Make sure blocks are numbered in order.
1434   MF.RenumberBlocks();
1435
1436   MachineBasicBlock *Entry = MF.begin();
1437   SmallPtrSet<MachineBasicBlock*,16> Visited;
1438
1439   for (df_ext_iterator<MachineBasicBlock*, SmallPtrSet<MachineBasicBlock*,16> >
1440          DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited);
1441        DFI != E; ++DFI) {
1442     BarrierMBB = *DFI;
1443     for (MachineBasicBlock::iterator I = BarrierMBB->begin(),
1444            E = BarrierMBB->end(); I != E; ++I) {
1445       Barrier = &*I;
1446       const TargetRegisterClass **BarrierRCs =
1447         Barrier->getDesc().getRegClassBarriers();
1448       if (!BarrierRCs)
1449         continue;
1450       BarrierIdx = LIs->getInstructionIndex(Barrier);
1451       MadeChange |= SplitRegLiveIntervals(BarrierRCs);
1452     }
1453   }
1454
1455   return MadeChange;
1456 }