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