SplitKit.cpp revision 4b3041c43e8134d0f2471255c736745f2eb3214d
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 "splitter"
16#include "SplitKit.h"
17#include "VirtRegMap.h"
18#include "llvm/CodeGen/CalcSpillWeights.h"
19#include "llvm/CodeGen/LiveIntervalAnalysis.h"
20#include "llvm/CodeGen/MachineInstrBuilder.h"
21#include "llvm/CodeGen/MachineLoopInfo.h"
22#include "llvm/CodeGen/MachineRegisterInfo.h"
23#include "llvm/Support/CommandLine.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
31static cl::opt<bool>
32AllowSplit("spiller-splits-edges",
33           cl::desc("Allow critical edge splitting during spilling"));
34
35//===----------------------------------------------------------------------===//
36//                                 Split Analysis
37//===----------------------------------------------------------------------===//
38
39SplitAnalysis::SplitAnalysis(const MachineFunction &mf,
40                             const LiveIntervals &lis,
41                             const MachineLoopInfo &mli)
42  : mf_(mf),
43    lis_(lis),
44    loops_(mli),
45    tii_(*mf.getTarget().getInstrInfo()),
46    curli_(0) {}
47
48void SplitAnalysis::clear() {
49  usingInstrs_.clear();
50  usingBlocks_.clear();
51  usingLoops_.clear();
52  curli_ = 0;
53}
54
55bool SplitAnalysis::canAnalyzeBranch(const MachineBasicBlock *MBB) {
56  MachineBasicBlock *T, *F;
57  SmallVector<MachineOperand, 4> Cond;
58  return !tii_.AnalyzeBranch(const_cast<MachineBasicBlock&>(*MBB), T, F, Cond);
59}
60
61/// analyzeUses - Count instructions, basic blocks, and loops using curli.
62void SplitAnalysis::analyzeUses() {
63  const MachineRegisterInfo &MRI = mf_.getRegInfo();
64  for (MachineRegisterInfo::reg_iterator I = MRI.reg_begin(curli_->reg);
65       MachineInstr *MI = I.skipInstruction();) {
66    if (MI->isDebugValue() || !usingInstrs_.insert(MI))
67      continue;
68    MachineBasicBlock *MBB = MI->getParent();
69    if (usingBlocks_[MBB]++)
70      continue;
71    for (MachineLoop *Loop = loops_.getLoopFor(MBB); Loop;
72         Loop = Loop->getParentLoop())
73      usingLoops_[Loop]++;
74  }
75  DEBUG(dbgs() << "  counted "
76               << usingInstrs_.size() << " instrs, "
77               << usingBlocks_.size() << " blocks, "
78               << usingLoops_.size()  << " loops.\n");
79}
80
81// Get three sets of basic blocks surrounding a loop: Blocks inside the loop,
82// predecessor blocks, and exit blocks.
83void SplitAnalysis::getLoopBlocks(const MachineLoop *Loop, LoopBlocks &Blocks) {
84  Blocks.clear();
85
86  // Blocks in the loop.
87  Blocks.Loop.insert(Loop->block_begin(), Loop->block_end());
88
89  // Predecessor blocks.
90  const MachineBasicBlock *Header = Loop->getHeader();
91  for (MachineBasicBlock::const_pred_iterator I = Header->pred_begin(),
92       E = Header->pred_end(); I != E; ++I)
93    if (!Blocks.Loop.count(*I))
94      Blocks.Preds.insert(*I);
95
96  // Exit blocks.
97  for (MachineLoop::block_iterator I = Loop->block_begin(),
98       E = Loop->block_end(); I != E; ++I) {
99    const MachineBasicBlock *MBB = *I;
100    for (MachineBasicBlock::const_succ_iterator SI = MBB->succ_begin(),
101       SE = MBB->succ_end(); SI != SE; ++SI)
102      if (!Blocks.Loop.count(*SI))
103        Blocks.Exits.insert(*SI);
104  }
105}
106
107/// analyzeLoopPeripheralUse - Return an enum describing how curli_ is used in
108/// and around the Loop.
109SplitAnalysis::LoopPeripheralUse SplitAnalysis::
110analyzeLoopPeripheralUse(const SplitAnalysis::LoopBlocks &Blocks) {
111  LoopPeripheralUse use = ContainedInLoop;
112  for (BlockCountMap::iterator I = usingBlocks_.begin(), E = usingBlocks_.end();
113       I != E; ++I) {
114    const MachineBasicBlock *MBB = I->first;
115    // Is this a peripheral block?
116    if (use < MultiPeripheral &&
117        (Blocks.Preds.count(MBB) || Blocks.Exits.count(MBB))) {
118      if (I->second > 1) use = MultiPeripheral;
119      else               use = SinglePeripheral;
120      continue;
121    }
122    // Is it a loop block?
123    if (Blocks.Loop.count(MBB))
124      continue;
125    // It must be an unrelated block.
126    return OutsideLoop;
127  }
128  return use;
129}
130
131/// getCriticalExits - It may be necessary to partially break critical edges
132/// leaving the loop if an exit block has phi uses of curli. Collect the exit
133/// blocks that need special treatment into CriticalExits.
134void SplitAnalysis::getCriticalExits(const SplitAnalysis::LoopBlocks &Blocks,
135                                     BlockPtrSet &CriticalExits) {
136  CriticalExits.clear();
137
138  // A critical exit block contains a phi def of curli, and has a predecessor
139  // that is not in the loop nor a loop predecessor.
140  // For such an exit block, the edges carrying the new variable must be moved
141  // to a new pre-exit block.
142  for (BlockPtrSet::iterator I = Blocks.Exits.begin(), E = Blocks.Exits.end();
143       I != E; ++I) {
144    const MachineBasicBlock *Succ = *I;
145    SlotIndex SuccIdx = lis_.getMBBStartIdx(Succ);
146    VNInfo *SuccVNI = curli_->getVNInfoAt(SuccIdx);
147    // This exit may not have curli live in at all. No need to split.
148    if (!SuccVNI)
149      continue;
150    // If this is not a PHI def, it is either using a value from before the
151    // loop, or a value defined inside the loop. Both are safe.
152    if (!SuccVNI->isPHIDef() || SuccVNI->def.getBaseIndex() != SuccIdx)
153      continue;
154    // This exit block does have a PHI. Does it also have a predecessor that is
155    // not a loop block or loop predecessor?
156    for (MachineBasicBlock::const_pred_iterator PI = Succ->pred_begin(),
157         PE = Succ->pred_end(); PI != PE; ++PI) {
158      const MachineBasicBlock *Pred = *PI;
159      if (Blocks.Loop.count(Pred) || Blocks.Preds.count(Pred))
160        continue;
161      // This is a critical exit block, and we need to split the exit edge.
162      CriticalExits.insert(Succ);
163      break;
164    }
165  }
166}
167
168/// canSplitCriticalExits - Return true if it is possible to insert new exit
169/// blocks before the blocks in CriticalExits.
170bool
171SplitAnalysis::canSplitCriticalExits(const SplitAnalysis::LoopBlocks &Blocks,
172                                     BlockPtrSet &CriticalExits) {
173  // If we don't allow critical edge splitting, require no critical exits.
174  if (!AllowSplit)
175    return CriticalExits.empty();
176
177  for (BlockPtrSet::iterator I = CriticalExits.begin(), E = CriticalExits.end();
178       I != E; ++I) {
179    const MachineBasicBlock *Succ = *I;
180    // We want to insert a new pre-exit MBB before Succ, and change all the
181    // in-loop blocks to branch to the pre-exit instead of Succ.
182    // Check that all the in-loop predecessors can be changed.
183    for (MachineBasicBlock::const_pred_iterator PI = Succ->pred_begin(),
184         PE = Succ->pred_end(); PI != PE; ++PI) {
185      const MachineBasicBlock *Pred = *PI;
186      // The external predecessors won't be altered.
187      if (!Blocks.Loop.count(Pred) && !Blocks.Preds.count(Pred))
188        continue;
189      if (!canAnalyzeBranch(Pred))
190        return false;
191    }
192
193    // If Succ's layout predecessor falls through, that too must be analyzable.
194    // We need to insert the pre-exit block in the gap.
195    MachineFunction::const_iterator MFI = Succ;
196    if (MFI == mf_.begin())
197      continue;
198    if (!canAnalyzeBranch(--MFI))
199      return false;
200  }
201  // No problems found.
202  return true;
203}
204
205void SplitAnalysis::analyze(const LiveInterval *li) {
206  clear();
207  curli_ = li;
208  analyzeUses();
209}
210
211const MachineLoop *SplitAnalysis::getBestSplitLoop() {
212  assert(curli_ && "Call analyze() before getBestSplitLoop");
213  if (usingLoops_.empty())
214    return 0;
215
216  LoopPtrSet Loops, SecondLoops;
217  LoopBlocks Blocks;
218  BlockPtrSet CriticalExits;
219
220  // Find first-class and second class candidate loops.
221  // We prefer to split around loops where curli is used outside the periphery.
222  for (LoopCountMap::const_iterator I = usingLoops_.begin(),
223       E = usingLoops_.end(); I != E; ++I) {
224    const MachineLoop *Loop = I->first;
225    getLoopBlocks(Loop, Blocks);
226
227    LoopPtrSet *LPS = 0;
228    switch(analyzeLoopPeripheralUse(Blocks)) {
229    case OutsideLoop:
230      LPS = &Loops;
231      break;
232    case MultiPeripheral:
233      LPS = &SecondLoops;
234      break;
235    case ContainedInLoop:
236      DEBUG(dbgs() << "  contained in " << *Loop);
237      continue;
238    case SinglePeripheral:
239      DEBUG(dbgs() << "  single peripheral use in " << *Loop);
240      continue;
241    }
242    // Will it be possible to split around this loop?
243    getCriticalExits(Blocks, CriticalExits);
244    DEBUG(dbgs() << "  " << CriticalExits.size() << " critical exits from "
245                 << *Loop);
246    if (!canSplitCriticalExits(Blocks, CriticalExits))
247      continue;
248    // This is a possible split.
249    assert(LPS);
250    LPS->insert(Loop);
251  }
252
253  DEBUG(dbgs() << "  getBestSplitLoop found " << Loops.size() << " + "
254               << SecondLoops.size() << " candidate loops.\n");
255
256  // If there are no first class loops available, look at second class loops.
257  if (Loops.empty())
258    Loops = SecondLoops;
259
260  if (Loops.empty())
261    return 0;
262
263  // Pick the earliest loop.
264  // FIXME: Are there other heuristics to consider?
265  const MachineLoop *Best = 0;
266  SlotIndex BestIdx;
267  for (LoopPtrSet::const_iterator I = Loops.begin(), E = Loops.end(); I != E;
268       ++I) {
269    SlotIndex Idx = lis_.getMBBStartIdx((*I)->getHeader());
270    if (!Best || Idx < BestIdx)
271      Best = *I, BestIdx = Idx;
272  }
273  DEBUG(dbgs() << "  getBestSplitLoop found " << *Best);
274  return Best;
275}
276
277/// getMultiUseBlocks - if curli has more than one use in a basic block, it
278/// may be an advantage to split curli for the duration of the block.
279bool SplitAnalysis::getMultiUseBlocks(BlockPtrSet &Blocks) {
280  // If curli is local to one block, there is no point to splitting it.
281  if (usingBlocks_.size() <= 1)
282    return false;
283  // Add blocks with multiple uses.
284  for (BlockCountMap::iterator I = usingBlocks_.begin(), E = usingBlocks_.end();
285       I != E; ++I)
286    switch (I->second) {
287    case 0:
288    case 1:
289      continue;
290    case 2: {
291      // It doesn't pay to split a 2-instr block if it redefines curli.
292      VNInfo *VN1 = curli_->getVNInfoAt(lis_.getMBBStartIdx(I->first));
293      VNInfo *VN2 =
294        curli_->getVNInfoAt(lis_.getMBBEndIdx(I->first).getPrevIndex());
295      // live-in and live-out with a different value.
296      if (VN1 && VN2 && VN1 != VN2)
297        continue;
298    } // Fall through.
299    default:
300      Blocks.insert(I->first);
301    }
302  return !Blocks.empty();
303}
304
305//===----------------------------------------------------------------------===//
306//                               LiveIntervalMap
307//===----------------------------------------------------------------------===//
308
309// Work around the fact that the std::pair constructors are broken for pointer
310// pairs in some implementations. makeVV(x, 0) works.
311static inline std::pair<const VNInfo*, VNInfo*>
312makeVV(const VNInfo *a, VNInfo *b) {
313  return std::make_pair(a, b);
314}
315
316void LiveIntervalMap::reset(LiveInterval *li) {
317  li_ = li;
318  valueMap_.clear();
319}
320
321bool LiveIntervalMap::isComplexMapped(const VNInfo *ParentVNI) const {
322  ValueMap::const_iterator i = valueMap_.find(ParentVNI);
323  return i != valueMap_.end() && i->second == 0;
324}
325
326// defValue - Introduce a li_ def for ParentVNI that could be later than
327// ParentVNI->def.
328VNInfo *LiveIntervalMap::defValue(const VNInfo *ParentVNI, SlotIndex Idx) {
329  assert(li_ && "call reset first");
330  assert(ParentVNI && "Mapping  NULL value");
331  assert(Idx.isValid() && "Invalid SlotIndex");
332  assert(parentli_.getVNInfoAt(Idx) == ParentVNI && "Bad ParentVNI");
333
334  // Create a new value.
335  VNInfo *VNI = li_->getNextValue(Idx, 0, lis_.getVNInfoAllocator());
336
337  // Use insert for lookup, so we can add missing values with a second lookup.
338  std::pair<ValueMap::iterator,bool> InsP =
339    valueMap_.insert(makeVV(ParentVNI, Idx == ParentVNI->def ? VNI : 0));
340
341  // This is now a complex def. Mark with a NULL in valueMap.
342  if (!InsP.second)
343    InsP.first->second = 0;
344
345  return VNI;
346}
347
348
349// mapValue - Find the mapped value for ParentVNI at Idx.
350// Potentially create phi-def values.
351VNInfo *LiveIntervalMap::mapValue(const VNInfo *ParentVNI, SlotIndex Idx,
352                                  bool *simple) {
353  assert(li_ && "call reset first");
354  assert(ParentVNI && "Mapping  NULL value");
355  assert(Idx.isValid() && "Invalid SlotIndex");
356  assert(parentli_.getVNInfoAt(Idx) == ParentVNI && "Bad ParentVNI");
357
358  // Use insert for lookup, so we can add missing values with a second lookup.
359  std::pair<ValueMap::iterator,bool> InsP =
360    valueMap_.insert(makeVV(ParentVNI, 0));
361
362  // This was an unknown value. Create a simple mapping.
363  if (InsP.second) {
364    if (simple) *simple = true;
365    return InsP.first->second = li_->createValueCopy(ParentVNI,
366                                                     lis_.getVNInfoAllocator());
367  }
368
369  // This was a simple mapped value.
370  if (InsP.first->second) {
371    if (simple) *simple = true;
372    return InsP.first->second;
373  }
374
375  // This is a complex mapped value. There may be multiple defs, and we may need
376  // to create phi-defs.
377  if (simple) *simple = false;
378  MachineBasicBlock *IdxMBB = lis_.getMBBFromIndex(Idx);
379  assert(IdxMBB && "No MBB at Idx");
380
381  // Is there a def in the same MBB we can extend?
382  if (VNInfo *VNI = extendTo(IdxMBB, Idx))
383    return VNI;
384
385  // Now for the fun part. We know that ParentVNI potentially has multiple defs,
386  // and we may need to create even more phi-defs to preserve VNInfo SSA form.
387  // Perform a depth-first search for predecessor blocks where we know the
388  // dominating VNInfo. Insert phi-def VNInfos along the path back to IdxMBB.
389
390  // Track MBBs where we have created or learned the dominating value.
391  // This may change during the DFS as we create new phi-defs.
392  typedef DenseMap<MachineBasicBlock*, VNInfo*> MBBValueMap;
393  MBBValueMap DomValue;
394  typedef SplitAnalysis::BlockPtrSet BlockPtrSet;
395  BlockPtrSet Visited;
396
397  // Iterate over IdxMBB predecessors in a depth-first order.
398  // Skip begin() since that is always IdxMBB.
399  for (idf_ext_iterator<MachineBasicBlock*, BlockPtrSet>
400         IDFI = llvm::next(idf_ext_begin(IdxMBB, Visited)),
401         IDFE = idf_ext_end(IdxMBB, Visited); IDFI != IDFE;) {
402    MachineBasicBlock *MBB = *IDFI;
403    SlotIndex End = lis_.getMBBEndIdx(MBB).getPrevSlot();
404
405    // We are operating on the restricted CFG where ParentVNI is live.
406    if (parentli_.getVNInfoAt(End) != ParentVNI) {
407      IDFI.skipChildren();
408      continue;
409    }
410
411    // Do we have a dominating value in this block?
412    VNInfo *VNI = extendTo(MBB, End);
413    if (!VNI) {
414      ++IDFI;
415      continue;
416    }
417
418    // Yes, VNI dominates MBB. Make sure we visit MBB again from other paths.
419    Visited.erase(MBB);
420
421    // Track the path back to IdxMBB, creating phi-defs
422    // as needed along the way.
423    for (unsigned PI = IDFI.getPathLength()-1; PI != 0; --PI) {
424      // Start from MBB's immediate successor. End at IdxMBB.
425      MachineBasicBlock *Succ = IDFI.getPath(PI-1);
426      std::pair<MBBValueMap::iterator, bool> InsP =
427        DomValue.insert(MBBValueMap::value_type(Succ, VNI));
428
429      // This is the first time we backtrack to Succ.
430      if (InsP.second)
431        continue;
432
433      // We reached Succ again with the same VNI. Nothing is going to change.
434      VNInfo *OVNI = InsP.first->second;
435      if (OVNI == VNI)
436        break;
437
438      // Succ already has a phi-def. No need to continue.
439      SlotIndex Start = lis_.getMBBStartIdx(Succ);
440      if (OVNI->def == Start)
441        break;
442
443      // We have a collision between the old and new VNI at Succ. That means
444      // neither dominates and we need a new phi-def.
445      VNI = li_->getNextValue(Start, 0, lis_.getVNInfoAllocator());
446      VNI->setIsPHIDef(true);
447      InsP.first->second = VNI;
448
449      // Replace OVNI with VNI in the remaining path.
450      for (; PI > 1 ; --PI) {
451        MBBValueMap::iterator I = DomValue.find(IDFI.getPath(PI-2));
452        if (I == DomValue.end() || I->second != OVNI)
453          break;
454        I->second = VNI;
455      }
456    }
457
458    // No need to search the children, we found a dominating value.
459    IDFI.skipChildren();
460  }
461
462  // The search should at least find a dominating value for IdxMBB.
463  assert(!DomValue.empty() && "Couldn't find a reaching definition");
464
465  // Since we went through the trouble of a full DFS visiting all reaching defs,
466  // the values in DomValue are now accurate. No more phi-defs are needed for
467  // these blocks, so we can color the live ranges.
468  // This makes the next mapValue call much faster.
469  VNInfo *IdxVNI = 0;
470  for (MBBValueMap::iterator I = DomValue.begin(), E = DomValue.end(); I != E;
471       ++I) {
472     MachineBasicBlock *MBB = I->first;
473     VNInfo *VNI = I->second;
474     SlotIndex Start = lis_.getMBBStartIdx(MBB);
475     if (MBB == IdxMBB) {
476       // Don't add full liveness to IdxMBB, stop at Idx.
477       if (Start != Idx)
478         li_->addRange(LiveRange(Start, Idx.getNextSlot(), VNI));
479       // The caller had better add some liveness to IdxVNI, or it leaks.
480       IdxVNI = VNI;
481     } else
482      li_->addRange(LiveRange(Start, lis_.getMBBEndIdx(MBB), VNI));
483  }
484
485  assert(IdxVNI && "Didn't find value for Idx");
486  return IdxVNI;
487}
488
489// extendTo - Find the last li_ value defined in MBB at or before Idx. The
490// parentli_ is assumed to be live at Idx. Extend the live range to Idx.
491// Return the found VNInfo, or NULL.
492VNInfo *LiveIntervalMap::extendTo(MachineBasicBlock *MBB, SlotIndex Idx) {
493  assert(li_ && "call reset first");
494  LiveInterval::iterator I = std::upper_bound(li_->begin(), li_->end(), Idx);
495  if (I == li_->begin())
496    return 0;
497  --I;
498  if (I->end <= lis_.getMBBStartIdx(MBB))
499    return 0;
500  if (I->end <= Idx)
501    I->end = Idx.getNextSlot();
502  return I->valno;
503}
504
505// addSimpleRange - Add a simple range from parentli_ to li_.
506// ParentVNI must be live in the [Start;End) interval.
507void LiveIntervalMap::addSimpleRange(SlotIndex Start, SlotIndex End,
508                                     const VNInfo *ParentVNI) {
509  assert(li_ && "call reset first");
510  bool simple;
511  VNInfo *VNI = mapValue(ParentVNI, Start, &simple);
512  // A simple mapping is easy.
513  if (simple) {
514    li_->addRange(LiveRange(Start, End, VNI));
515    return;
516  }
517
518  // ParentVNI is a complex value. We must map per MBB.
519  MachineFunction::iterator MBB = lis_.getMBBFromIndex(Start);
520  MachineFunction::iterator MBBE = lis_.getMBBFromIndex(End.getPrevSlot());
521
522  if (MBB == MBBE) {
523    li_->addRange(LiveRange(Start, End, VNI));
524    return;
525  }
526
527  // First block.
528  li_->addRange(LiveRange(Start, lis_.getMBBEndIdx(MBB), VNI));
529
530  // Run sequence of full blocks.
531  for (++MBB; MBB != MBBE; ++MBB) {
532    Start = lis_.getMBBStartIdx(MBB);
533    li_->addRange(LiveRange(Start, lis_.getMBBEndIdx(MBB),
534                            mapValue(ParentVNI, Start)));
535  }
536
537  // Final block.
538  Start = lis_.getMBBStartIdx(MBB);
539  if (Start != End)
540    li_->addRange(LiveRange(Start, End, mapValue(ParentVNI, Start)));
541}
542
543/// addRange - Add live ranges to li_ where [Start;End) intersects parentli_.
544/// All needed values whose def is not inside [Start;End) must be defined
545/// beforehand so mapValue will work.
546void LiveIntervalMap::addRange(SlotIndex Start, SlotIndex End) {
547  assert(li_ && "call reset first");
548  LiveInterval::const_iterator B = parentli_.begin(), E = parentli_.end();
549  LiveInterval::const_iterator I = std::lower_bound(B, E, Start);
550
551  // Check if --I begins before Start and overlaps.
552  if (I != B) {
553    --I;
554    if (I->end > Start)
555      addSimpleRange(Start, std::min(End, I->end), I->valno);
556    ++I;
557  }
558
559  // The remaining ranges begin after Start.
560  for (;I != E && I->start < End; ++I)
561    addSimpleRange(I->start, std::min(End, I->end), I->valno);
562}
563
564VNInfo *LiveIntervalMap::defByCopyFrom(unsigned Reg,
565                                       const VNInfo *ParentVNI,
566                                       MachineBasicBlock &MBB,
567                                       MachineBasicBlock::iterator I) {
568  const TargetInstrDesc &TID = MBB.getParent()->getTarget().getInstrInfo()->
569    get(TargetOpcode::COPY);
570  MachineInstr *MI = BuildMI(MBB, I, DebugLoc(), TID, li_->reg).addReg(Reg);
571  SlotIndex DefIdx = lis_.InsertMachineInstrInMaps(MI).getDefIndex();
572  VNInfo *VNI = defValue(ParentVNI, DefIdx);
573  VNI->setCopy(MI);
574  li_->addRange(LiveRange(DefIdx, DefIdx.getNextSlot(), VNI));
575  return VNI;
576}
577
578//===----------------------------------------------------------------------===//
579//                               Split Editor
580//===----------------------------------------------------------------------===//
581
582/// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
583SplitEditor::SplitEditor(SplitAnalysis &sa, LiveIntervals &lis, VirtRegMap &vrm,
584                         SmallVectorImpl<LiveInterval*> &intervals)
585  : sa_(sa), lis_(lis), vrm_(vrm),
586    mri_(vrm.getMachineFunction().getRegInfo()),
587    tii_(*vrm.getMachineFunction().getTarget().getInstrInfo()),
588    curli_(sa_.getCurLI()),
589    dupli_(lis_, *curli_),
590    openli_(lis_, *curli_),
591    intervals_(intervals),
592    firstInterval(intervals_.size())
593{
594  assert(curli_ && "SplitEditor created from empty SplitAnalysis");
595
596  // Make sure curli_ is assigned a stack slot, so all our intervals get the
597  // same slot as curli_.
598  if (vrm_.getStackSlot(curli_->reg) == VirtRegMap::NO_STACK_SLOT)
599    vrm_.assignVirt2StackSlot(curli_->reg);
600
601}
602
603LiveInterval *SplitEditor::createInterval() {
604  unsigned Reg = mri_.createVirtualRegister(mri_.getRegClass(curli_->reg));
605  LiveInterval &Intv = lis_.getOrCreateInterval(Reg);
606  vrm_.grow();
607  vrm_.assignVirt2StackSlot(Reg, vrm_.getStackSlot(curli_->reg));
608  return &Intv;
609}
610
611bool SplitEditor::intervalsLiveAt(SlotIndex Idx) const {
612  for (int i = firstInterval, e = intervals_.size(); i != e; ++i)
613    if (intervals_[i]->liveAt(Idx))
614      return true;
615  return false;
616}
617
618/// Create a new virtual register and live interval.
619void SplitEditor::openIntv() {
620  assert(!openli_.getLI() && "Previous LI not closed before openIntv");
621
622  if (!dupli_.getLI())
623    dupli_.reset(createInterval());
624
625  openli_.reset(createInterval());
626  intervals_.push_back(openli_.getLI());
627}
628
629/// enterIntvBefore - Enter openli before the instruction at Idx. If curli is
630/// not live before Idx, a COPY is not inserted.
631void SplitEditor::enterIntvBefore(SlotIndex Idx) {
632  assert(openli_.getLI() && "openIntv not called before enterIntvBefore");
633  DEBUG(dbgs() << "    enterIntvBefore " << Idx);
634  VNInfo *ParentVNI = curli_->getVNInfoAt(Idx.getUseIndex());
635  if (!ParentVNI) {
636    DEBUG(dbgs() << ": not live\n");
637    return;
638  }
639  DEBUG(dbgs() << ": valno " << ParentVNI->id);
640  truncatedValues.insert(ParentVNI);
641  MachineInstr *MI = lis_.getInstructionFromIndex(Idx);
642  assert(MI && "enterIntvBefore called with invalid index");
643  VNInfo *VNI = openli_.defByCopyFrom(curli_->reg, ParentVNI,
644                                      *MI->getParent(), MI);
645  openli_.getLI()->addRange(LiveRange(VNI->def, Idx.getDefIndex(), VNI));
646  DEBUG(dbgs() << ": " << *openli_.getLI() << '\n');
647}
648
649/// enterIntvAtEnd - Enter openli at the end of MBB.
650void SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) {
651  assert(openli_.getLI() && "openIntv not called before enterIntvAtEnd");
652  SlotIndex End = lis_.getMBBEndIdx(&MBB);
653  DEBUG(dbgs() << "    enterIntvAtEnd BB#" << MBB.getNumber() << ", " << End);
654  VNInfo *ParentVNI = curli_->getVNInfoAt(End.getPrevSlot());
655  if (!ParentVNI) {
656    DEBUG(dbgs() << ": not live\n");
657    return;
658  }
659  DEBUG(dbgs() << ": valno " << ParentVNI->id);
660  truncatedValues.insert(ParentVNI);
661  VNInfo *VNI = openli_.defByCopyFrom(curli_->reg, ParentVNI,
662                                      MBB, MBB.getFirstTerminator());
663  // Make sure openli is live out of MBB.
664  openli_.getLI()->addRange(LiveRange(VNI->def, End, VNI));
665  DEBUG(dbgs() << ": " << *openli_.getLI() << '\n');
666}
667
668/// useIntv - indicate that all instructions in MBB should use openli.
669void SplitEditor::useIntv(const MachineBasicBlock &MBB) {
670  useIntv(lis_.getMBBStartIdx(&MBB), lis_.getMBBEndIdx(&MBB));
671}
672
673void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) {
674  assert(openli_.getLI() && "openIntv not called before useIntv");
675  openli_.addRange(Start, End);
676  DEBUG(dbgs() << "    use [" << Start << ';' << End << "): "
677               << *openli_.getLI() << '\n');
678}
679
680/// leaveIntvAfter - Leave openli after the instruction at Idx.
681void SplitEditor::leaveIntvAfter(SlotIndex Idx) {
682  assert(openli_.getLI() && "openIntv not called before leaveIntvAfter");
683  DEBUG(dbgs() << "    leaveIntvAfter " << Idx);
684
685  // The interval must be live beyond the instruction at Idx.
686  VNInfo *ParentVNI = curli_->getVNInfoAt(Idx.getBoundaryIndex());
687  if (!ParentVNI) {
688    DEBUG(dbgs() << ": not live\n");
689    return;
690  }
691  DEBUG(dbgs() << ": valno " << ParentVNI->id);
692
693  MachineBasicBlock::iterator MII = lis_.getInstructionFromIndex(Idx);
694  MachineBasicBlock *MBB = MII->getParent();
695  VNInfo *VNI = dupli_.defByCopyFrom(openli_.getLI()->reg, ParentVNI, *MBB,
696                                     llvm::next(MII));
697
698  // Finally we must make sure that openli is properly extended from Idx to the
699  // new copy.
700  openli_.addSimpleRange(Idx.getBoundaryIndex(), VNI->def, ParentVNI);
701  DEBUG(dbgs() << ": " << *openli_.getLI() << '\n');
702}
703
704/// leaveIntvAtTop - Leave the interval at the top of MBB.
705/// Currently, only one value can leave the interval.
706void SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) {
707  assert(openli_.getLI() && "openIntv not called before leaveIntvAtTop");
708  SlotIndex Start = lis_.getMBBStartIdx(&MBB);
709  DEBUG(dbgs() << "    leaveIntvAtTop BB#" << MBB.getNumber() << ", " << Start);
710
711  VNInfo *ParentVNI = curli_->getVNInfoAt(Start);
712  if (!ParentVNI) {
713    DEBUG(dbgs() << ": not live\n");
714    return;
715  }
716
717  // We are going to insert a back copy, so we must have a dupli_.
718  VNInfo *VNI = dupli_.defByCopyFrom(openli_.getLI()->reg, ParentVNI,
719                                     MBB, MBB.begin());
720
721  // Finally we must make sure that openli is properly extended from Start to
722  // the new copy.
723  openli_.addSimpleRange(Start, VNI->def, ParentVNI);
724  DEBUG(dbgs() << ": " << *openli_.getLI() << '\n');
725}
726
727/// closeIntv - Indicate that we are done editing the currently open
728/// LiveInterval, and ranges can be trimmed.
729void SplitEditor::closeIntv() {
730  assert(openli_.getLI() && "openIntv not called before closeIntv");
731
732  DEBUG(dbgs() << "    closeIntv cleaning up\n");
733  DEBUG(dbgs() << "    open " << *openli_.getLI() << '\n');
734  openli_.reset(0);
735}
736
737void
738SplitEditor::addTruncSimpleRange(SlotIndex Start, SlotIndex End, VNInfo *VNI) {
739  // Build vector of iterator pairs from the intervals.
740  typedef std::pair<LiveInterval::const_iterator,
741                    LiveInterval::const_iterator> IIPair;
742  SmallVector<IIPair, 8> Iters;
743  for (int i = firstInterval, e = intervals_.size(); i != e; ++i) {
744    LiveInterval::const_iterator I = intervals_[i]->find(Start);
745    LiveInterval::const_iterator E = intervals_[i]->end();
746    if (I != E)
747      Iters.push_back(std::make_pair(I, E));
748  }
749
750  SlotIndex sidx = Start;
751  // Break [Start;End) into segments that don't overlap any intervals.
752  for (;;) {
753    SlotIndex next = sidx, eidx = End;
754    // Find overlapping intervals.
755    for (unsigned i = 0; i != Iters.size() && sidx < eidx; ++i) {
756      LiveInterval::const_iterator I = Iters[i].first;
757      // Interval I is overlapping [sidx;eidx). Trim sidx.
758      if (I->start <= sidx) {
759        sidx = I->end;
760        // Move to the next run, remove iters when all are consumed.
761        I = ++Iters[i].first;
762        if (I == Iters[i].second) {
763          Iters.erase(Iters.begin() + i);
764          --i;
765          continue;
766        }
767      }
768      // Trim eidx too if needed.
769      if (I->start >= eidx)
770        continue;
771      eidx = I->start;
772      next = I->end;
773    }
774    // Now, [sidx;eidx) doesn't overlap anything in intervals_.
775    if (sidx < eidx)
776      dupli_.addSimpleRange(sidx, eidx, VNI);
777    // If the interval end was truncated, we can try again from next.
778    if (next <= sidx)
779      break;
780    sidx = next;
781  }
782}
783
784/// rewrite - after all the new live ranges have been created, rewrite
785/// instructions using curli to use the new intervals.
786void SplitEditor::rewrite() {
787  assert(!openli_.getLI() && "Previous LI not closed before rewrite");
788  assert(dupli_.getLI() && "No dupli for rewrite. Noop spilt?");
789
790  // First we need to fill in the live ranges in dupli.
791  // If values were redefined, we need a full recoloring with SSA update.
792  // If values were truncated, we only need to truncate the ranges.
793  // If values were partially rematted, we should shrink to uses.
794  // If values were fully rematted, they should be omitted.
795  // FIXME: If a single value is redefined, just move the def and truncate.
796
797  // Values that are fully contained in the split intervals.
798  SmallPtrSet<const VNInfo*, 8> deadValues;
799
800  // Map all curli values that should have live defs in dupli.
801  for (LiveInterval::const_vni_iterator I = curli_->vni_begin(),
802       E = curli_->vni_end(); I != E; ++I) {
803    const VNInfo *VNI = *I;
804    // Original def is contained in the split intervals.
805    if (intervalsLiveAt(VNI->def)) {
806      // Did this value escape?
807      if (dupli_.isMapped(VNI))
808        truncatedValues.insert(VNI);
809      else
810        deadValues.insert(VNI);
811      continue;
812    }
813    // Add minimal live range at the definition.
814    VNInfo *DVNI = dupli_.defValue(VNI, VNI->def);
815    dupli_.getLI()->addRange(LiveRange(VNI->def, VNI->def.getNextSlot(), DVNI));
816  }
817
818  // Add all ranges to dupli.
819  for (LiveInterval::const_iterator I = curli_->begin(), E = curli_->end();
820       I != E; ++I) {
821    const LiveRange &LR = *I;
822    if (truncatedValues.count(LR.valno)) {
823      // recolor after removing intervals_.
824      addTruncSimpleRange(LR.start, LR.end, LR.valno);
825    } else if (!deadValues.count(LR.valno)) {
826      // recolor without truncation.
827      dupli_.addSimpleRange(LR.start, LR.end, LR.valno);
828    }
829  }
830
831
832  const LiveInterval *curli = sa_.getCurLI();
833  for (MachineRegisterInfo::reg_iterator RI = mri_.reg_begin(curli->reg),
834       RE = mri_.reg_end(); RI != RE;) {
835    MachineOperand &MO = RI.getOperand();
836    MachineInstr *MI = MO.getParent();
837    ++RI;
838    if (MI->isDebugValue()) {
839      DEBUG(dbgs() << "Zapping " << *MI);
840      // FIXME: We can do much better with debug values.
841      MO.setReg(0);
842      continue;
843    }
844    SlotIndex Idx = lis_.getInstructionIndex(MI);
845    Idx = MO.isUse() ? Idx.getUseIndex() : Idx.getDefIndex();
846    LiveInterval *LI = dupli_.getLI();
847    for (unsigned i = firstInterval, e = intervals_.size(); i != e; ++i) {
848      LiveInterval *testli = intervals_[i];
849      if (testli->liveAt(Idx)) {
850        LI = testli;
851        break;
852      }
853    }
854    MO.setReg(LI->reg);
855    DEBUG(dbgs() << "  rewrite " << Idx << '\t' << *MI);
856  }
857
858  // dupli_ goes in last, after rewriting.
859  if (dupli_.getLI()->empty()) {
860    DEBUG(dbgs() << "  dupli became empty?\n");
861    lis_.removeInterval(dupli_.getLI()->reg);
862    dupli_.reset(0);
863  } else {
864    dupli_.getLI()->RenumberValues(lis_);
865    intervals_.push_back(dupli_.getLI());
866  }
867
868  // Calculate spill weight and allocation hints for new intervals.
869  VirtRegAuxInfo vrai(vrm_.getMachineFunction(), lis_, sa_.loops_);
870  for (unsigned i = firstInterval, e = intervals_.size(); i != e; ++i) {
871    LiveInterval &li = *intervals_[i];
872    vrai.CalculateRegClass(li.reg);
873    vrai.CalculateWeightAndHint(li);
874    DEBUG(dbgs() << "  new interval " << mri_.getRegClass(li.reg)->getName()
875                 << ":" << li << '\n');
876  }
877}
878
879
880//===----------------------------------------------------------------------===//
881//                               Loop Splitting
882//===----------------------------------------------------------------------===//
883
884void SplitEditor::splitAroundLoop(const MachineLoop *Loop) {
885  SplitAnalysis::LoopBlocks Blocks;
886  sa_.getLoopBlocks(Loop, Blocks);
887
888  // Break critical edges as needed.
889  SplitAnalysis::BlockPtrSet CriticalExits;
890  sa_.getCriticalExits(Blocks, CriticalExits);
891  assert(CriticalExits.empty() && "Cannot break critical exits yet");
892
893  // Create new live interval for the loop.
894  openIntv();
895
896  // Insert copies in the predecessors.
897  for (SplitAnalysis::BlockPtrSet::iterator I = Blocks.Preds.begin(),
898       E = Blocks.Preds.end(); I != E; ++I) {
899    MachineBasicBlock &MBB = const_cast<MachineBasicBlock&>(**I);
900    enterIntvAtEnd(MBB);
901  }
902
903  // Switch all loop blocks.
904  for (SplitAnalysis::BlockPtrSet::iterator I = Blocks.Loop.begin(),
905       E = Blocks.Loop.end(); I != E; ++I)
906     useIntv(**I);
907
908  // Insert back copies in the exit blocks.
909  for (SplitAnalysis::BlockPtrSet::iterator I = Blocks.Exits.begin(),
910       E = Blocks.Exits.end(); I != E; ++I) {
911    MachineBasicBlock &MBB = const_cast<MachineBasicBlock&>(**I);
912    leaveIntvAtTop(MBB);
913  }
914
915  // Done.
916  closeIntv();
917  rewrite();
918}
919
920
921//===----------------------------------------------------------------------===//
922//                            Single Block Splitting
923//===----------------------------------------------------------------------===//
924
925/// splitSingleBlocks - Split curli into a separate live interval inside each
926/// basic block in Blocks.
927void SplitEditor::splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks) {
928  DEBUG(dbgs() << "  splitSingleBlocks for " << Blocks.size() << " blocks.\n");
929  // Determine the first and last instruction using curli in each block.
930  typedef std::pair<SlotIndex,SlotIndex> IndexPair;
931  typedef DenseMap<const MachineBasicBlock*,IndexPair> IndexPairMap;
932  IndexPairMap MBBRange;
933  for (SplitAnalysis::InstrPtrSet::const_iterator I = sa_.usingInstrs_.begin(),
934       E = sa_.usingInstrs_.end(); I != E; ++I) {
935    const MachineBasicBlock *MBB = (*I)->getParent();
936    if (!Blocks.count(MBB))
937      continue;
938    SlotIndex Idx = lis_.getInstructionIndex(*I);
939    DEBUG(dbgs() << "  BB#" << MBB->getNumber() << '\t' << Idx << '\t' << **I);
940    IndexPair &IP = MBBRange[MBB];
941    if (!IP.first.isValid() || Idx < IP.first)
942      IP.first = Idx;
943    if (!IP.second.isValid() || Idx > IP.second)
944      IP.second = Idx;
945  }
946
947  // Create a new interval for each block.
948  for (SplitAnalysis::BlockPtrSet::const_iterator I = Blocks.begin(),
949       E = Blocks.end(); I != E; ++I) {
950    IndexPair &IP = MBBRange[*I];
951    DEBUG(dbgs() << "  splitting for BB#" << (*I)->getNumber() << ": ["
952                 << IP.first << ';' << IP.second << ")\n");
953    assert(IP.first.isValid() && IP.second.isValid());
954
955    openIntv();
956    enterIntvBefore(IP.first);
957    useIntv(IP.first.getBaseIndex(), IP.second.getBoundaryIndex());
958    leaveIntvAfter(IP.second);
959    closeIntv();
960  }
961  rewrite();
962}
963
964
965//===----------------------------------------------------------------------===//
966//                            Sub Block Splitting
967//===----------------------------------------------------------------------===//
968
969/// getBlockForInsideSplit - If curli is contained inside a single basic block,
970/// and it wou pay to subdivide the interval inside that block, return it.
971/// Otherwise return NULL. The returned block can be passed to
972/// SplitEditor::splitInsideBlock.
973const MachineBasicBlock *SplitAnalysis::getBlockForInsideSplit() {
974  // The interval must be exclusive to one block.
975  if (usingBlocks_.size() != 1)
976    return 0;
977  // Don't to this for less than 4 instructions. We want to be sure that
978  // splitting actually reduces the instruction count per interval.
979  if (usingInstrs_.size() < 4)
980    return 0;
981  return usingBlocks_.begin()->first;
982}
983
984/// splitInsideBlock - Split curli into multiple intervals inside MBB.
985void SplitEditor::splitInsideBlock(const MachineBasicBlock *MBB) {
986  SmallVector<SlotIndex, 32> Uses;
987  Uses.reserve(sa_.usingInstrs_.size());
988  for (SplitAnalysis::InstrPtrSet::const_iterator I = sa_.usingInstrs_.begin(),
989       E = sa_.usingInstrs_.end(); I != E; ++I)
990    if ((*I)->getParent() == MBB)
991      Uses.push_back(lis_.getInstructionIndex(*I));
992  DEBUG(dbgs() << "  splitInsideBlock BB#" << MBB->getNumber() << " for "
993               << Uses.size() << " instructions.\n");
994  assert(Uses.size() >= 3 && "Need at least 3 instructions");
995  array_pod_sort(Uses.begin(), Uses.end());
996
997  // Simple algorithm: Find the largest gap between uses as determined by slot
998  // indices. Create new intervals for instructions before the gap and after the
999  // gap.
1000  unsigned bestPos = 0;
1001  int bestGap = 0;
1002  DEBUG(dbgs() << "    dist (" << Uses[0]);
1003  for (unsigned i = 1, e = Uses.size(); i != e; ++i) {
1004    int g = Uses[i-1].distance(Uses[i]);
1005    DEBUG(dbgs() << ") -" << g << "- (" << Uses[i]);
1006    if (g > bestGap)
1007      bestPos = i, bestGap = g;
1008  }
1009  DEBUG(dbgs() << "), best: -" << bestGap << "-\n");
1010
1011  // bestPos points to the first use after the best gap.
1012  assert(bestPos > 0 && "Invalid gap");
1013
1014  // FIXME: Don't create intervals for low densities.
1015
1016  // First interval before the gap. Don't create single-instr intervals.
1017  if (bestPos > 1) {
1018    openIntv();
1019    enterIntvBefore(Uses.front());
1020    useIntv(Uses.front().getBaseIndex(), Uses[bestPos-1].getBoundaryIndex());
1021    leaveIntvAfter(Uses[bestPos-1]);
1022    closeIntv();
1023  }
1024
1025  // Second interval after the gap.
1026  if (bestPos < Uses.size()-1) {
1027    openIntv();
1028    enterIntvBefore(Uses[bestPos]);
1029    useIntv(Uses[bestPos].getBaseIndex(), Uses.back().getBoundaryIndex());
1030    leaveIntvAfter(Uses.back());
1031    closeIntv();
1032  }
1033
1034  rewrite();
1035}
1036