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