SplitKit.cpp revision 71d9e65ee71712b965c79739e63de94fbb8078ad 
1//===---------- SplitKit.cpp - Toolkit for splitting live ranges ----------===//
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 contains the SplitAnalysis class as well as mutator functions for
11// live range splitting.
12//
13//===----------------------------------------------------------------------===//
14
15#define DEBUG_TYPE "regalloc"
16#include "SplitKit.h"
17#include "LiveRangeEdit.h"
18#include "VirtRegMap.h"
19#include "llvm/ADT/Statistic.h"
20#include "llvm/CodeGen/LiveIntervalAnalysis.h"
21#include "llvm/CodeGen/MachineDominators.h"
22#include "llvm/CodeGen/MachineInstrBuilder.h"
23#include "llvm/CodeGen/MachineRegisterInfo.h"
24#include "llvm/Support/Debug.h"
25#include "llvm/Support/raw_ostream.h"
26#include "llvm/Target/TargetInstrInfo.h"
27#include "llvm/Target/TargetMachine.h"
28
29using namespace llvm;
30
31STATISTIC(NumFinished, "Number of splits finished");
32STATISTIC(NumSimple,   "Number of splits that were simple");
33
34//===----------------------------------------------------------------------===//
35//                                 Split Analysis
36//===----------------------------------------------------------------------===//
37
38SplitAnalysis::SplitAnalysis(const VirtRegMap &vrm,
39                             const LiveIntervals &lis,
40                             const MachineLoopInfo &mli)
41  : MF(vrm.getMachineFunction()),
42    VRM(vrm),
43    LIS(lis),
44    Loops(mli),
45    TII(*MF.getTarget().getInstrInfo()),
46    CurLI(0),
47    LastSplitPoint(MF.getNumBlockIDs()) {}
48
49void SplitAnalysis::clear() {
50  UseSlots.clear();
51  LiveBlocks.clear();
52  CurLI = 0;
53}
54
55SlotIndex SplitAnalysis::computeLastSplitPoint(unsigned Num) {
56  const MachineBasicBlock *MBB = MF.getBlockNumbered(Num);
57  const MachineBasicBlock *LPad = MBB->getLandingPadSuccessor();
58  std::pair<SlotIndex, SlotIndex> &LSP = LastSplitPoint[Num];
59
60  // Compute split points on the first call. The pair is independent of the
61  // current live interval.
62  if (!LSP.first.isValid()) {
63    MachineBasicBlock::const_iterator FirstTerm = MBB->getFirstTerminator();
64    if (FirstTerm == MBB->end())
65      LSP.first = LIS.getMBBEndIdx(MBB);
66    else
67      LSP.first = LIS.getInstructionIndex(FirstTerm);
68
69    // If there is a landing pad successor, also find the call instruction.
70    if (!LPad)
71      return LSP.first;
72    // There may not be a call instruction (?) in which case we ignore LPad.
73    LSP.second = LSP.first;
74    for (MachineBasicBlock::const_iterator I = FirstTerm, E = MBB->begin();
75         I != E; --I)
76      if (I->getDesc().isCall()) {
77        LSP.second = LIS.getInstructionIndex(I);
78        break;
79      }
80  }
81
82  // If CurLI is live into a landing pad successor, move the last split point
83  // back to the call that may throw.
84  if (LPad && LSP.second.isValid() && LIS.isLiveInToMBB(*CurLI, LPad))
85    return LSP.second;
86  else
87    return LSP.first;
88}
89
90/// analyzeUses - Count instructions, basic blocks, and loops using CurLI.
91void SplitAnalysis::analyzeUses() {
92  assert(UseSlots.empty() && "Call clear first");
93
94  // First get all the defs from the interval values. This provides the correct
95  // slots for early clobbers.
96  for (LiveInterval::const_vni_iterator I = CurLI->vni_begin(),
97       E = CurLI->vni_end(); I != E; ++I)
98    if (!(*I)->isPHIDef() && !(*I)->isUnused())
99      UseSlots.push_back((*I)->def);
100
101  // Get use slots form the use-def chain.
102  const MachineRegisterInfo &MRI = MF.getRegInfo();
103  for (MachineRegisterInfo::use_nodbg_iterator
104       I = MRI.use_nodbg_begin(CurLI->reg), E = MRI.use_nodbg_end(); I != E;
105       ++I)
106    if (!I.getOperand().isUndef())
107      UseSlots.push_back(LIS.getInstructionIndex(&*I).getDefIndex());
108
109  array_pod_sort(UseSlots.begin(), UseSlots.end());
110
111  // Remove duplicates, keeping the smaller slot for each instruction.
112  // That is what we want for early clobbers.
113  UseSlots.erase(std::unique(UseSlots.begin(), UseSlots.end(),
114                             SlotIndex::isSameInstr),
115                 UseSlots.end());
116
117  // Compute per-live block info.
118  if (!calcLiveBlockInfo()) {
119    // FIXME: calcLiveBlockInfo found inconsistencies in the live range.
120    // I am looking at you, SimpleRegisterCoalescing!
121    DEBUG(dbgs() << "*** Fixing inconsistent live interval! ***\n");
122    const_cast<LiveIntervals&>(LIS)
123      .shrinkToUses(const_cast<LiveInterval*>(CurLI));
124    LiveBlocks.clear();
125    bool fixed = calcLiveBlockInfo();
126    (void)fixed;
127    assert(fixed && "Couldn't fix broken live interval");
128  }
129
130  DEBUG(dbgs() << "Analyze counted "
131               << UseSlots.size() << " instrs, "
132               << LiveBlocks.size() << " spanned.\n");
133}
134
135/// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks
136/// where CurLI is live.
137bool SplitAnalysis::calcLiveBlockInfo() {
138  if (CurLI->empty())
139    return true;
140
141  LiveInterval::const_iterator LVI = CurLI->begin();
142  LiveInterval::const_iterator LVE = CurLI->end();
143
144  SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE;
145  UseI = UseSlots.begin();
146  UseE = UseSlots.end();
147
148  // Loop over basic blocks where CurLI is live.
149  MachineFunction::iterator MFI = LIS.getMBBFromIndex(LVI->start);
150  for (;;) {
151    BlockInfo BI;
152    BI.MBB = MFI;
153    SlotIndex Start, Stop;
154    tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
155
156    // LVI is the first live segment overlapping MBB.
157    BI.LiveIn = LVI->start <= Start;
158    if (!BI.LiveIn)
159      BI.Def = LVI->start;
160
161    // Find the first and last uses in the block.
162    BI.Uses = UseI != UseE && *UseI < Stop;
163    if (BI.Uses) {
164      BI.FirstUse = *UseI;
165      assert(BI.FirstUse >= Start);
166      do ++UseI;
167      while (UseI != UseE && *UseI < Stop);
168      BI.LastUse = UseI[-1];
169      assert(BI.LastUse < Stop);
170    }
171
172    // Look for gaps in the live range.
173    bool hasGap = false;
174    BI.LiveOut = true;
175    while (LVI->end < Stop) {
176      SlotIndex LastStop = LVI->end;
177      if (++LVI == LVE || LVI->start >= Stop) {
178        BI.Kill = LastStop;
179        BI.LiveOut = false;
180        break;
181      }
182      if (LastStop < LVI->start) {
183        hasGap = true;
184        BI.Kill = LastStop;
185        BI.Def = LVI->start;
186      }
187    }
188
189    // Don't set LiveThrough when the block has a gap.
190    BI.LiveThrough = !hasGap && BI.LiveIn && BI.LiveOut;
191    LiveBlocks.push_back(BI);
192
193    // FIXME: This should never happen. The live range stops or starts without a
194    // corresponding use. An earlier pass did something wrong.
195    if (!BI.LiveThrough && !BI.Uses)
196      return false;
197
198    // LVI is now at LVE or LVI->end >= Stop.
199    if (LVI == LVE)
200      break;
201
202    // Live segment ends exactly at Stop. Move to the next segment.
203    if (LVI->end == Stop && ++LVI == LVE)
204      break;
205
206    // Pick the next basic block.
207    if (LVI->start < Stop)
208      ++MFI;
209    else
210      MFI = LIS.getMBBFromIndex(LVI->start);
211  }
212  return true;
213}
214
215bool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx) const {
216  unsigned OrigReg = VRM.getOriginal(CurLI->reg);
217  const LiveInterval &Orig = LIS.getInterval(OrigReg);
218  assert(!Orig.empty() && "Splitting empty interval?");
219  LiveInterval::const_iterator I = Orig.find(Idx);
220
221  // Range containing Idx should begin at Idx.
222  if (I != Orig.end() && I->start <= Idx)
223    return I->start == Idx;
224
225  // Range does not contain Idx, previous must end at Idx.
226  return I != Orig.begin() && (--I)->end == Idx;
227}
228
229void SplitAnalysis::analyze(const LiveInterval *li) {
230  clear();
231  CurLI = li;
232  analyzeUses();
233}
234
235
236//===----------------------------------------------------------------------===//
237//                               Split Editor
238//===----------------------------------------------------------------------===//
239
240/// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
241SplitEditor::SplitEditor(SplitAnalysis &sa,
242                         LiveIntervals &lis,
243                         VirtRegMap &vrm,
244                         MachineDominatorTree &mdt)
245  : SA(sa), LIS(lis), VRM(vrm),
246    MRI(vrm.getMachineFunction().getRegInfo()),
247    MDT(mdt),
248    TII(*vrm.getMachineFunction().getTarget().getInstrInfo()),
249    TRI(*vrm.getMachineFunction().getTarget().getRegisterInfo()),
250    Edit(0),
251    OpenIdx(0),
252    RegAssign(Allocator)
253{}
254
255void SplitEditor::reset(LiveRangeEdit &lre) {
256  Edit = &lre;
257  OpenIdx = 0;
258  RegAssign.clear();
259  Values.clear();
260
261  // We don't need to clear LiveOutCache, only LiveOutSeen entries are read.
262  LiveOutSeen.clear();
263
264  // We don't need an AliasAnalysis since we will only be performing
265  // cheap-as-a-copy remats anyway.
266  Edit->anyRematerializable(LIS, TII, 0);
267}
268
269void SplitEditor::dump() const {
270  if (RegAssign.empty()) {
271    dbgs() << " empty\n";
272    return;
273  }
274
275  for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I)
276    dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value();
277  dbgs() << '\n';
278}
279
280VNInfo *SplitEditor::defValue(unsigned RegIdx,
281                              const VNInfo *ParentVNI,
282                              SlotIndex Idx) {
283  assert(ParentVNI && "Mapping  NULL value");
284  assert(Idx.isValid() && "Invalid SlotIndex");
285  assert(Edit->getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI");
286  LiveInterval *LI = Edit->get(RegIdx);
287
288  // Create a new value.
289  VNInfo *VNI = LI->getNextValue(Idx, 0, LIS.getVNInfoAllocator());
290
291  // Use insert for lookup, so we can add missing values with a second lookup.
292  std::pair<ValueMap::iterator, bool> InsP =
293    Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), VNI));
294
295  // This was the first time (RegIdx, ParentVNI) was mapped.
296  // Keep it as a simple def without any liveness.
297  if (InsP.second)
298    return VNI;
299
300  // If the previous value was a simple mapping, add liveness for it now.
301  if (VNInfo *OldVNI = InsP.first->second) {
302    SlotIndex Def = OldVNI->def;
303    LI->addRange(LiveRange(Def, Def.getNextSlot(), OldVNI));
304    // No longer a simple mapping.
305    InsP.first->second = 0;
306  }
307
308  // This is a complex mapping, add liveness for VNI
309  SlotIndex Def = VNI->def;
310  LI->addRange(LiveRange(Def, Def.getNextSlot(), VNI));
311
312  return VNI;
313}
314
315void SplitEditor::markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI) {
316  assert(ParentVNI && "Mapping  NULL value");
317  VNInfo *&VNI = Values[std::make_pair(RegIdx, ParentVNI->id)];
318
319  // ParentVNI was either unmapped or already complex mapped. Either way.
320  if (!VNI)
321    return;
322
323  // This was previously a single mapping. Make sure the old def is represented
324  // by a trivial live range.
325  SlotIndex Def = VNI->def;
326  Edit->get(RegIdx)->addRange(LiveRange(Def, Def.getNextSlot(), VNI));
327  VNI = 0;
328}
329
330// extendRange - Extend the live range to reach Idx.
331// Potentially create phi-def values.
332void SplitEditor::extendRange(unsigned RegIdx, SlotIndex Idx) {
333  assert(Idx.isValid() && "Invalid SlotIndex");
334  MachineBasicBlock *IdxMBB = LIS.getMBBFromIndex(Idx);
335  assert(IdxMBB && "No MBB at Idx");
336  LiveInterval *LI = Edit->get(RegIdx);
337
338  // Is there a def in the same MBB we can extend?
339  if (LI->extendInBlock(LIS.getMBBStartIdx(IdxMBB), Idx))
340    return;
341
342  // Now for the fun part. We know that ParentVNI potentially has multiple defs,
343  // and we may need to create even more phi-defs to preserve VNInfo SSA form.
344  // Perform a search for all predecessor blocks where we know the dominating
345  // VNInfo. Insert phi-def VNInfos along the path back to IdxMBB.
346
347  // Initialize the live-out cache the first time it is needed.
348  if (LiveOutSeen.empty()) {
349    unsigned N = VRM.getMachineFunction().getNumBlockIDs();
350    LiveOutSeen.resize(N);
351    LiveOutCache.resize(N);
352  }
353
354  // Blocks where LI should be live-in.
355  SmallVector<MachineDomTreeNode*, 16> LiveIn;
356  LiveIn.push_back(MDT[IdxMBB]);
357
358  // Remember if we have seen more than one value.
359  bool UniqueVNI = true;
360  VNInfo *IdxVNI = 0;
361
362  // Using LiveOutCache as a visited set, perform a BFS for all reaching defs.
363  for (unsigned i = 0; i != LiveIn.size(); ++i) {
364    MachineBasicBlock *MBB = LiveIn[i]->getBlock();
365    assert(!MBB->pred_empty() && "Value live-in to entry block?");
366    for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
367           PE = MBB->pred_end(); PI != PE; ++PI) {
368       MachineBasicBlock *Pred = *PI;
369       LiveOutPair &LOP = LiveOutCache[Pred];
370
371       // Is this a known live-out block?
372       if (LiveOutSeen.test(Pred->getNumber())) {
373         if (VNInfo *VNI = LOP.first) {
374           if (IdxVNI && IdxVNI != VNI)
375             UniqueVNI = false;
376           IdxVNI = VNI;
377         }
378         continue;
379       }
380
381       // First time. LOP is garbage and must be cleared below.
382       LiveOutSeen.set(Pred->getNumber());
383
384       // Does Pred provide a live-out value?
385       SlotIndex Start, Last;
386       tie(Start, Last) = LIS.getSlotIndexes()->getMBBRange(Pred);
387       Last = Last.getPrevSlot();
388       VNInfo *VNI = LI->extendInBlock(Start, Last);
389       LOP.first = VNI;
390       if (VNI) {
391         LOP.second = MDT[LIS.getMBBFromIndex(VNI->def)];
392         if (IdxVNI && IdxVNI != VNI)
393           UniqueVNI = false;
394         IdxVNI = VNI;
395         continue;
396       }
397       LOP.second = 0;
398
399       // No, we need a live-in value for Pred as well
400       if (Pred != IdxMBB)
401         LiveIn.push_back(MDT[Pred]);
402       else
403         UniqueVNI = false; // Loopback to IdxMBB, ask updateSSA() for help.
404    }
405  }
406
407  // We may need to add phi-def values to preserve the SSA form.
408  if (UniqueVNI) {
409    LiveOutPair LOP(IdxVNI, MDT[LIS.getMBBFromIndex(IdxVNI->def)]);
410    // Update LiveOutCache, but skip IdxMBB at LiveIn[0].
411    for (unsigned i = 1, e = LiveIn.size(); i != e; ++i)
412      LiveOutCache[LiveIn[i]->getBlock()] = LOP;
413  } else
414    IdxVNI = updateSSA(RegIdx, LiveIn, Idx, IdxMBB);
415
416  // Since we went through the trouble of a full BFS visiting all reaching defs,
417  // the values in LiveIn are now accurate. No more phi-defs are needed
418  // for these blocks, so we can color the live ranges.
419  for (unsigned i = 0, e = LiveIn.size(); i != e; ++i) {
420    MachineBasicBlock *MBB = LiveIn[i]->getBlock();
421    SlotIndex Start = LIS.getMBBStartIdx(MBB);
422    VNInfo *VNI = LiveOutCache[MBB].first;
423
424    // Anything in LiveIn other than IdxMBB is live-through.
425    // In IdxMBB, we should stop at Idx unless the same value is live-out.
426    if (MBB == IdxMBB && IdxVNI != VNI)
427      LI->addRange(LiveRange(Start, Idx.getNextSlot(), IdxVNI));
428    else
429      LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI));
430  }
431}
432
433VNInfo *SplitEditor::updateSSA(unsigned RegIdx,
434                               SmallVectorImpl<MachineDomTreeNode*> &LiveIn,
435                               SlotIndex Idx,
436                               const MachineBasicBlock *IdxMBB) {
437  // This is essentially the same iterative algorithm that SSAUpdater uses,
438  // except we already have a dominator tree, so we don't have to recompute it.
439  LiveInterval *LI = Edit->get(RegIdx);
440  VNInfo *IdxVNI = 0;
441  unsigned Changes;
442  do {
443    Changes = 0;
444    // Propagate live-out values down the dominator tree, inserting phi-defs
445    // when necessary. Since LiveIn was created by a BFS, going backwards makes
446    // it more likely for us to visit immediate dominators before their
447    // children.
448    for (unsigned i = LiveIn.size(); i; --i) {
449      MachineDomTreeNode *Node = LiveIn[i-1];
450      MachineBasicBlock *MBB = Node->getBlock();
451      MachineDomTreeNode *IDom = Node->getIDom();
452      LiveOutPair IDomValue;
453
454      // We need a live-in value to a block with no immediate dominator?
455      // This is probably an unreachable block that has survived somehow.
456      bool needPHI = !IDom || !LiveOutSeen.test(IDom->getBlock()->getNumber());
457
458      // IDom dominates all of our predecessors, but it may not be the immediate
459      // dominator. Check if any of them have live-out values that are properly
460      // dominated by IDom. If so, we need a phi-def here.
461      if (!needPHI) {
462        IDomValue = LiveOutCache[IDom->getBlock()];
463        for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
464               PE = MBB->pred_end(); PI != PE; ++PI) {
465          LiveOutPair Value = LiveOutCache[*PI];
466          if (!Value.first || Value.first == IDomValue.first)
467            continue;
468          // This predecessor is carrying something other than IDomValue.
469          // It could be because IDomValue hasn't propagated yet, or it could be
470          // because MBB is in the dominance frontier of that value.
471          if (MDT.dominates(IDom, Value.second)) {
472            needPHI = true;
473            break;
474          }
475        }
476      }
477
478      // Create a phi-def if required.
479      if (needPHI) {
480        ++Changes;
481        SlotIndex Start = LIS.getMBBStartIdx(MBB);
482        VNInfo *VNI = LI->getNextValue(Start, 0, LIS.getVNInfoAllocator());
483        VNI->setIsPHIDef(true);
484        // We no longer need LI to be live-in.
485        LiveIn.erase(LiveIn.begin()+(i-1));
486        // Blocks in LiveIn are either IdxMBB, or have a value live-through.
487        if (MBB == IdxMBB)
488          IdxVNI = VNI;
489        // Check if we need to update live-out info.
490        LiveOutPair &LOP = LiveOutCache[MBB];
491        if (LOP.second == Node || !LiveOutSeen.test(MBB->getNumber())) {
492          // We already have a live-out defined in MBB, so this must be IdxMBB.
493          assert(MBB == IdxMBB && "Adding phi-def to known live-out");
494          LI->addRange(LiveRange(Start, Idx.getNextSlot(), VNI));
495        } else {
496          // This phi-def is also live-out, so color the whole block.
497          LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI));
498          LOP = LiveOutPair(VNI, Node);
499        }
500      } else if (IDomValue.first) {
501        // No phi-def here. Remember incoming value for IdxMBB.
502        if (MBB == IdxMBB) {
503          IdxVNI = IDomValue.first;
504          // IdxMBB need not be live-out.
505          if (!LiveOutSeen.test(MBB->getNumber()))
506            continue;
507        }
508        assert(LiveOutSeen.test(MBB->getNumber()) && "Expected live-out block");
509        // Propagate IDomValue if needed:
510        // MBB is live-out and doesn't define its own value.
511        LiveOutPair &LOP = LiveOutCache[MBB];
512        if (LOP.second != Node && LOP.first != IDomValue.first) {
513          ++Changes;
514          LOP = IDomValue;
515        }
516      }
517    }
518  } while (Changes);
519
520  assert(IdxVNI && "Didn't find value for Idx");
521  return IdxVNI;
522}
523
524VNInfo *SplitEditor::defFromParent(unsigned RegIdx,
525                                   VNInfo *ParentVNI,
526                                   SlotIndex UseIdx,
527                                   MachineBasicBlock &MBB,
528                                   MachineBasicBlock::iterator I) {
529  MachineInstr *CopyMI = 0;
530  SlotIndex Def;
531  LiveInterval *LI = Edit->get(RegIdx);
532
533  // Attempt cheap-as-a-copy rematerialization.
534  LiveRangeEdit::Remat RM(ParentVNI);
535  if (Edit->canRematerializeAt(RM, UseIdx, true, LIS)) {
536    Def = Edit->rematerializeAt(MBB, I, LI->reg, RM, LIS, TII, TRI);
537  } else {
538    // Can't remat, just insert a copy from parent.
539    CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg)
540               .addReg(Edit->getReg());
541    Def = LIS.InsertMachineInstrInMaps(CopyMI).getDefIndex();
542  }
543
544  // Define the value in Reg.
545  VNInfo *VNI = defValue(RegIdx, ParentVNI, Def);
546  VNI->setCopy(CopyMI);
547  return VNI;
548}
549
550/// Create a new virtual register and live interval.
551void SplitEditor::openIntv() {
552  assert(!OpenIdx && "Previous LI not closed before openIntv");
553
554  // Create the complement as index 0.
555  if (Edit->empty())
556    Edit->create(LIS, VRM);
557
558  // Create the open interval.
559  OpenIdx = Edit->size();
560  Edit->create(LIS, VRM);
561}
562
563SlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) {
564  assert(OpenIdx && "openIntv not called before enterIntvBefore");
565  DEBUG(dbgs() << "    enterIntvBefore " << Idx);
566  Idx = Idx.getBaseIndex();
567  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);
568  if (!ParentVNI) {
569    DEBUG(dbgs() << ": not live\n");
570    return Idx;
571  }
572  DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
573  MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
574  assert(MI && "enterIntvBefore called with invalid index");
575
576  VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI);
577  return VNI->def;
578}
579
580SlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) {
581  assert(OpenIdx && "openIntv not called before enterIntvAtEnd");
582  SlotIndex End = LIS.getMBBEndIdx(&MBB);
583  SlotIndex Last = End.getPrevSlot();
584  DEBUG(dbgs() << "    enterIntvAtEnd BB#" << MBB.getNumber() << ", " << Last);
585  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Last);
586  if (!ParentVNI) {
587    DEBUG(dbgs() << ": not live\n");
588    return End;
589  }
590  DEBUG(dbgs() << ": valno " << ParentVNI->id);
591  VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB,
592                              LIS.getLastSplitPoint(Edit->getParent(), &MBB));
593  RegAssign.insert(VNI->def, End, OpenIdx);
594  DEBUG(dump());
595  return VNI->def;
596}
597
598/// useIntv - indicate that all instructions in MBB should use OpenLI.
599void SplitEditor::useIntv(const MachineBasicBlock &MBB) {
600  useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB));
601}
602
603void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) {
604  assert(OpenIdx && "openIntv not called before useIntv");
605  DEBUG(dbgs() << "    useIntv [" << Start << ';' << End << "):");
606  RegAssign.insert(Start, End, OpenIdx);
607  DEBUG(dump());
608}
609
610SlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) {
611  assert(OpenIdx && "openIntv not called before leaveIntvAfter");
612  DEBUG(dbgs() << "    leaveIntvAfter " << Idx);
613
614  // The interval must be live beyond the instruction at Idx.
615  Idx = Idx.getBoundaryIndex();
616  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);
617  if (!ParentVNI) {
618    DEBUG(dbgs() << ": not live\n");
619    return Idx.getNextSlot();
620  }
621  DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
622
623  MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
624  assert(MI && "No instruction at index");
625  VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(),
626                              llvm::next(MachineBasicBlock::iterator(MI)));
627  return VNI->def;
628}
629
630SlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) {
631  assert(OpenIdx && "openIntv not called before leaveIntvBefore");
632  DEBUG(dbgs() << "    leaveIntvBefore " << Idx);
633
634  // The interval must be live into the instruction at Idx.
635  Idx = Idx.getBoundaryIndex();
636  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);
637  if (!ParentVNI) {
638    DEBUG(dbgs() << ": not live\n");
639    return Idx.getNextSlot();
640  }
641  DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
642
643  MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
644  assert(MI && "No instruction at index");
645  VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI);
646  return VNI->def;
647}
648
649SlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) {
650  assert(OpenIdx && "openIntv not called before leaveIntvAtTop");
651  SlotIndex Start = LIS.getMBBStartIdx(&MBB);
652  DEBUG(dbgs() << "    leaveIntvAtTop BB#" << MBB.getNumber() << ", " << Start);
653
654  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start);
655  if (!ParentVNI) {
656    DEBUG(dbgs() << ": not live\n");
657    return Start;
658  }
659
660  VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB,
661                              MBB.SkipPHIsAndLabels(MBB.begin()));
662  RegAssign.insert(Start, VNI->def, OpenIdx);
663  DEBUG(dump());
664  return VNI->def;
665}
666
667void SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) {
668  assert(OpenIdx && "openIntv not called before overlapIntv");
669  const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start);
670  assert(ParentVNI == Edit->getParent().getVNInfoAt(End.getPrevSlot()) &&
671         "Parent changes value in extended range");
672  assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) &&
673         "Range cannot span basic blocks");
674
675  // The complement interval will be extended as needed by extendRange().
676  if (ParentVNI)
677    markComplexMapped(0, ParentVNI);
678  DEBUG(dbgs() << "    overlapIntv [" << Start << ';' << End << "):");
679  RegAssign.insert(Start, End, OpenIdx);
680  DEBUG(dump());
681}
682
683/// closeIntv - Indicate that we are done editing the currently open
684/// LiveInterval, and ranges can be trimmed.
685void SplitEditor::closeIntv() {
686  assert(OpenIdx && "openIntv not called before closeIntv");
687  OpenIdx = 0;
688}
689
690/// transferSimpleValues - Transfer all simply defined values to the new live
691/// ranges.
692/// Values that were rematerialized or that have multiple defs are left alone.
693bool SplitEditor::transferSimpleValues() {
694  bool Skipped = false;
695  RegAssignMap::const_iterator AssignI = RegAssign.begin();
696  for (LiveInterval::const_iterator ParentI = Edit->getParent().begin(),
697         ParentE = Edit->getParent().end(); ParentI != ParentE; ++ParentI) {
698    DEBUG(dbgs() << "  blit " << *ParentI << ':');
699    VNInfo *ParentVNI = ParentI->valno;
700    // RegAssign has holes where RegIdx 0 should be used.
701    SlotIndex Start = ParentI->start;
702    AssignI.advanceTo(Start);
703    do {
704      unsigned RegIdx;
705      SlotIndex End = ParentI->end;
706      if (!AssignI.valid()) {
707        RegIdx = 0;
708      } else if (AssignI.start() <= Start) {
709        RegIdx = AssignI.value();
710        if (AssignI.stop() < End) {
711          End = AssignI.stop();
712          ++AssignI;
713        }
714      } else {
715        RegIdx = 0;
716        End = std::min(End, AssignI.start());
717      }
718      DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx);
719      if (VNInfo *VNI = Values.lookup(std::make_pair(RegIdx, ParentVNI->id))) {
720        DEBUG(dbgs() << ':' << VNI->id);
721        Edit->get(RegIdx)->addRange(LiveRange(Start, End, VNI));
722      } else
723        Skipped = true;
724      Start = End;
725    } while (Start != ParentI->end);
726    DEBUG(dbgs() << '\n');
727  }
728  return Skipped;
729}
730
731void SplitEditor::extendPHIKillRanges() {
732    // Extend live ranges to be live-out for successor PHI values.
733  for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(),
734       E = Edit->getParent().vni_end(); I != E; ++I) {
735    const VNInfo *PHIVNI = *I;
736    if (PHIVNI->isUnused() || !PHIVNI->isPHIDef())
737      continue;
738    unsigned RegIdx = RegAssign.lookup(PHIVNI->def);
739    MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def);
740    for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
741         PE = MBB->pred_end(); PI != PE; ++PI) {
742      SlotIndex End = LIS.getMBBEndIdx(*PI).getPrevSlot();
743      // The predecessor may not have a live-out value. That is OK, like an
744      // undef PHI operand.
745      if (Edit->getParent().liveAt(End)) {
746        assert(RegAssign.lookup(End) == RegIdx &&
747               "Different register assignment in phi predecessor");
748        extendRange(RegIdx, End);
749      }
750    }
751  }
752}
753
754/// rewriteAssigned - Rewrite all uses of Edit->getReg().
755void SplitEditor::rewriteAssigned(bool ExtendRanges) {
756  for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit->getReg()),
757       RE = MRI.reg_end(); RI != RE;) {
758    MachineOperand &MO = RI.getOperand();
759    MachineInstr *MI = MO.getParent();
760    ++RI;
761    // LiveDebugVariables should have handled all DBG_VALUE instructions.
762    if (MI->isDebugValue()) {
763      DEBUG(dbgs() << "Zapping " << *MI);
764      MO.setReg(0);
765      continue;
766    }
767
768    // <undef> operands don't really read the register, so just assign them to
769    // the complement.
770    if (MO.isUse() && MO.isUndef()) {
771      MO.setReg(Edit->get(0)->reg);
772      continue;
773    }
774
775    SlotIndex Idx = LIS.getInstructionIndex(MI);
776    if (MO.isDef())
777      Idx = MO.isEarlyClobber() ? Idx.getUseIndex() : Idx.getDefIndex();
778
779    // Rewrite to the mapped register at Idx.
780    unsigned RegIdx = RegAssign.lookup(Idx);
781    MO.setReg(Edit->get(RegIdx)->reg);
782    DEBUG(dbgs() << "  rewr BB#" << MI->getParent()->getNumber() << '\t'
783                 << Idx << ':' << RegIdx << '\t' << *MI);
784
785    // Extend liveness to Idx if the instruction reads reg.
786    if (!ExtendRanges)
787      continue;
788
789    // Skip instructions that don't read Reg.
790    if (MO.isDef()) {
791      if (!MO.getSubReg() && !MO.isEarlyClobber())
792        continue;
793      // We may wan't to extend a live range for a partial redef, or for a use
794      // tied to an early clobber.
795      Idx = Idx.getPrevSlot();
796      if (!Edit->getParent().liveAt(Idx))
797        continue;
798    } else
799      Idx = Idx.getUseIndex();
800
801    extendRange(RegIdx, Idx);
802  }
803}
804
805void SplitEditor::deleteRematVictims() {
806  SmallVector<MachineInstr*, 8> Dead;
807  for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I){
808    LiveInterval *LI = *I;
809    for (LiveInterval::const_iterator LII = LI->begin(), LIE = LI->end();
810           LII != LIE; ++LII) {
811      // Dead defs end at the store slot.
812      if (LII->end != LII->valno->def.getNextSlot())
813        continue;
814      MachineInstr *MI = LIS.getInstructionFromIndex(LII->valno->def);
815      assert(MI && "Missing instruction for dead def");
816      MI->addRegisterDead(LI->reg, &TRI);
817
818      if (!MI->allDefsAreDead())
819        continue;
820
821      DEBUG(dbgs() << "All defs dead: " << *MI);
822      Dead.push_back(MI);
823    }
824  }
825
826  if (Dead.empty())
827    return;
828
829  Edit->eliminateDeadDefs(Dead, LIS, VRM, TII);
830}
831
832void SplitEditor::finish() {
833  assert(OpenIdx == 0 && "Previous LI not closed before rewrite");
834  ++NumFinished;
835
836  // At this point, the live intervals in Edit contain VNInfos corresponding to
837  // the inserted copies.
838
839  // Add the original defs from the parent interval.
840  for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(),
841         E = Edit->getParent().vni_end(); I != E; ++I) {
842    const VNInfo *ParentVNI = *I;
843    if (ParentVNI->isUnused())
844      continue;
845    unsigned RegIdx = RegAssign.lookup(ParentVNI->def);
846    VNInfo *VNI = defValue(RegIdx, ParentVNI, ParentVNI->def);
847    VNI->setIsPHIDef(ParentVNI->isPHIDef());
848    VNI->setCopy(ParentVNI->getCopy());
849
850    // Mark rematted values as complex everywhere to force liveness computation.
851    // The new live ranges may be truncated.
852    if (Edit->didRematerialize(ParentVNI))
853      for (unsigned i = 0, e = Edit->size(); i != e; ++i)
854        markComplexMapped(i, ParentVNI);
855  }
856
857#ifndef NDEBUG
858  // Every new interval must have a def by now, otherwise the split is bogus.
859  for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I)
860    assert((*I)->hasAtLeastOneValue() && "Split interval has no value");
861#endif
862
863  // Transfer the simply mapped values, check if any are complex.
864  bool Complex = transferSimpleValues();
865  if (Complex)
866    extendPHIKillRanges();
867  else
868    ++NumSimple;
869
870  // Rewrite virtual registers, possibly extending ranges.
871  rewriteAssigned(Complex);
872
873  // Delete defs that were rematted everywhere.
874  if (Complex)
875    deleteRematVictims();
876
877  // Get rid of unused values and set phi-kill flags.
878  for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I)
879    (*I)->RenumberValues(LIS);
880
881  // Now check if any registers were separated into multiple components.
882  ConnectedVNInfoEqClasses ConEQ(LIS);
883  for (unsigned i = 0, e = Edit->size(); i != e; ++i) {
884    // Don't use iterators, they are invalidated by create() below.
885    LiveInterval *li = Edit->get(i);
886    unsigned NumComp = ConEQ.Classify(li);
887    if (NumComp <= 1)
888      continue;
889    DEBUG(dbgs() << "  " << NumComp << " components: " << *li << '\n');
890    SmallVector<LiveInterval*, 8> dups;
891    dups.push_back(li);
892    for (unsigned i = 1; i != NumComp; ++i)
893      dups.push_back(&Edit->create(LIS, VRM));
894    ConEQ.Distribute(&dups[0], MRI);
895  }
896
897  // Calculate spill weight and allocation hints for new intervals.
898  Edit->calculateRegClassAndHint(VRM.getMachineFunction(), LIS, SA.Loops);
899}
900
901
902//===----------------------------------------------------------------------===//
903//                            Single Block Splitting
904//===----------------------------------------------------------------------===//
905
906/// getMultiUseBlocks - if CurLI has more than one use in a basic block, it
907/// may be an advantage to split CurLI for the duration of the block.
908bool SplitAnalysis::getMultiUseBlocks(BlockPtrSet &Blocks) {
909  // If CurLI is local to one block, there is no point to splitting it.
910  if (LiveBlocks.size() <= 1)
911    return false;
912  // Add blocks with multiple uses.
913  for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
914    const BlockInfo &BI = LiveBlocks[i];
915    if (!BI.Uses || BI.FirstUse == BI.LastUse)
916      continue;
917    Blocks.insert(BI.MBB);
918  }
919  return !Blocks.empty();
920}
921
922/// splitSingleBlocks - Split CurLI into a separate live interval inside each
923/// basic block in Blocks.
924void SplitEditor::splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks) {
925  DEBUG(dbgs() << "  splitSingleBlocks for " << Blocks.size() << " blocks.\n");
926
927  for (unsigned i = 0, e = SA.LiveBlocks.size(); i != e; ++i) {
928    const SplitAnalysis::BlockInfo &BI = SA.LiveBlocks[i];
929    if (!BI.Uses || !Blocks.count(BI.MBB))
930      continue;
931
932    openIntv();
933    SlotIndex LastSplitPoint = SA.getLastSplitPoint(BI.MBB->getNumber());
934    SlotIndex SegStart = enterIntvBefore(std::min(BI.FirstUse,
935                                                  LastSplitPoint));
936    if (!BI.LiveOut || BI.LastUse < LastSplitPoint) {
937      useIntv(SegStart, leaveIntvAfter(BI.LastUse));
938    } else {
939      // The last use is after the last valid split point.
940      SlotIndex SegStop = leaveIntvBefore(LastSplitPoint);
941      useIntv(SegStart, SegStop);
942      overlapIntv(SegStop, BI.LastUse);
943    }
944    closeIntv();
945  }
946  finish();
947}
948