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