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