1//===-- llvm/CodeGen/Splitter.cpp -  Splitter -----------------------------===//
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#define DEBUG_TYPE "loopsplitter"
11
12#include "Splitter.h"
13
14#include "llvm/Module.h"
15#include "llvm/CodeGen/CalcSpillWeights.h"
16#include "llvm/CodeGen/LiveIntervalAnalysis.h"
17#include "llvm/CodeGen/LiveStackAnalysis.h"
18#include "llvm/CodeGen/MachineDominators.h"
19#include "llvm/CodeGen/MachineInstrBuilder.h"
20#include "llvm/CodeGen/MachineFunction.h"
21#include "llvm/CodeGen/MachineRegisterInfo.h"
22#include "llvm/CodeGen/Passes.h"
23#include "llvm/CodeGen/SlotIndexes.h"
24#include "llvm/Support/Debug.h"
25#include "llvm/Support/raw_ostream.h"
26#include "llvm/Target/TargetMachine.h"
27#include "llvm/Target/TargetInstrInfo.h"
28
29using namespace llvm;
30
31char LoopSplitter::ID = 0;
32INITIALIZE_PASS_BEGIN(LoopSplitter, "loop-splitting",
33                "Split virtual regists across loop boundaries.", false, false)
34INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
35INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
36INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
37INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
38INITIALIZE_PASS_END(LoopSplitter, "loop-splitting",
39                "Split virtual regists across loop boundaries.", false, false)
40
41namespace llvm {
42
43  class StartSlotComparator {
44  public:
45    StartSlotComparator(LiveIntervals &lis) : lis(lis) {}
46    bool operator()(const MachineBasicBlock *mbb1,
47                    const MachineBasicBlock *mbb2) const {
48      return lis.getMBBStartIdx(mbb1) < lis.getMBBStartIdx(mbb2);
49    }
50  private:
51    LiveIntervals &lis;
52  };
53
54  class LoopSplit {
55  public:
56    LoopSplit(LoopSplitter &ls, LiveInterval &li, MachineLoop &loop)
57      : ls(ls), li(li), loop(loop), valid(true), inSplit(false), newLI(0) {
58      assert(TargetRegisterInfo::isVirtualRegister(li.reg) &&
59             "Cannot split physical registers.");
60    }
61
62    LiveInterval& getLI() const { return li; }
63
64    MachineLoop& getLoop() const { return loop; }
65
66    bool isValid() const { return valid; }
67
68    bool isWorthwhile() const { return valid && (inSplit || !outSplits.empty()); }
69
70    void invalidate() { valid = false; }
71
72    void splitIncoming() { inSplit = true; }
73
74    void splitOutgoing(MachineLoop::Edge &edge) { outSplits.insert(edge); }
75
76    void addLoopInstr(MachineInstr *i) { loopInstrs.push_back(i); }
77
78    void apply() {
79      assert(valid && "Attempt to apply invalid split.");
80      applyIncoming();
81      applyOutgoing();
82      copyRanges();
83      renameInside();
84    }
85
86  private:
87    LoopSplitter &ls;
88    LiveInterval &li;
89    MachineLoop &loop;
90    bool valid, inSplit;
91    std::set<MachineLoop::Edge> outSplits;
92    std::vector<MachineInstr*> loopInstrs;
93
94    LiveInterval *newLI;
95    std::map<VNInfo*, VNInfo*> vniMap;
96
97    LiveInterval* getNewLI() {
98      if (newLI == 0) {
99        const TargetRegisterClass *trc = ls.mri->getRegClass(li.reg);
100        unsigned vreg = ls.mri->createVirtualRegister(trc);
101        newLI = &ls.lis->getOrCreateInterval(vreg);
102      }
103      return newLI;
104    }
105
106    VNInfo* getNewVNI(VNInfo *oldVNI) {
107      VNInfo *newVNI = vniMap[oldVNI];
108
109      if (newVNI == 0) {
110        newVNI = getNewLI()->createValueCopy(oldVNI,
111                                             ls.lis->getVNInfoAllocator());
112        vniMap[oldVNI] = newVNI;
113      }
114
115      return newVNI;
116    }
117
118    void applyIncoming() {
119      if (!inSplit) {
120        return;
121      }
122
123      MachineBasicBlock *preHeader = loop.getLoopPreheader();
124      if (preHeader == 0) {
125        assert(ls.canInsertPreHeader(loop) &&
126               "Can't insert required preheader.");
127        preHeader = &ls.insertPreHeader(loop);
128      }
129
130      LiveRange *preHeaderRange =
131        ls.lis->findExitingRange(li, preHeader);
132      assert(preHeaderRange != 0 && "Range not live into preheader.");
133
134      // Insert the new copy.
135      MachineInstr *copy = BuildMI(*preHeader,
136                                   preHeader->getFirstTerminator(),
137                                   DebugLoc(),
138                                   ls.tii->get(TargetOpcode::COPY))
139        .addReg(getNewLI()->reg, RegState::Define)
140        .addReg(li.reg, RegState::Kill);
141
142      ls.lis->InsertMachineInstrInMaps(copy);
143
144      SlotIndex copyDefIdx = ls.lis->getInstructionIndex(copy).getDefIndex();
145
146      VNInfo *newVal = getNewVNI(preHeaderRange->valno);
147      newVal->def = copyDefIdx;
148      newVal->setCopy(copy);
149      li.removeRange(copyDefIdx, ls.lis->getMBBEndIdx(preHeader), true);
150
151      getNewLI()->addRange(LiveRange(copyDefIdx,
152                                     ls.lis->getMBBEndIdx(preHeader),
153                                     newVal));
154    }
155
156    void applyOutgoing() {
157
158      for (std::set<MachineLoop::Edge>::iterator osItr = outSplits.begin(),
159                                                 osEnd = outSplits.end();
160           osItr != osEnd; ++osItr) {
161        MachineLoop::Edge edge = *osItr;
162        MachineBasicBlock *outBlock = edge.second;
163        if (ls.isCriticalEdge(edge)) {
164          assert(ls.canSplitEdge(edge) && "Unsplitable critical edge.");
165          outBlock = &ls.splitEdge(edge, loop);
166        }
167        LiveRange *outRange = ls.lis->findEnteringRange(li, outBlock);
168        assert(outRange != 0 && "No exiting range?");
169
170        MachineInstr *copy = BuildMI(*outBlock, outBlock->begin(),
171                                     DebugLoc(),
172                                     ls.tii->get(TargetOpcode::COPY))
173          .addReg(li.reg, RegState::Define)
174          .addReg(getNewLI()->reg, RegState::Kill);
175
176        ls.lis->InsertMachineInstrInMaps(copy);
177
178        SlotIndex copyDefIdx = ls.lis->getInstructionIndex(copy).getDefIndex();
179
180        // Blow away output range definition.
181        outRange->valno->def = ls.lis->getInvalidIndex();
182        li.removeRange(ls.lis->getMBBStartIdx(outBlock), copyDefIdx);
183
184        SlotIndex newDefIdx = ls.lis->getMBBStartIdx(outBlock);
185        assert(ls.lis->getInstructionFromIndex(newDefIdx) == 0 &&
186               "PHI def index points at actual instruction.");
187        VNInfo *newVal =
188          getNewLI()->getNextValue(newDefIdx, 0, ls.lis->getVNInfoAllocator());
189
190        getNewLI()->addRange(LiveRange(ls.lis->getMBBStartIdx(outBlock),
191                                       copyDefIdx, newVal));
192
193      }
194    }
195
196    void copyRange(LiveRange &lr) {
197      std::pair<bool, LoopSplitter::SlotPair> lsr =
198        ls.getLoopSubRange(lr, loop);
199
200      if (!lsr.first)
201        return;
202
203      LiveRange loopRange(lsr.second.first, lsr.second.second,
204                          getNewVNI(lr.valno));
205
206      li.removeRange(loopRange.start, loopRange.end, true);
207
208      getNewLI()->addRange(loopRange);
209    }
210
211    void copyRanges() {
212      for (std::vector<MachineInstr*>::iterator iItr = loopInstrs.begin(),
213                                                iEnd = loopInstrs.end();
214           iItr != iEnd; ++iItr) {
215        MachineInstr &instr = **iItr;
216        SlotIndex instrIdx = ls.lis->getInstructionIndex(&instr);
217        if (instr.modifiesRegister(li.reg, 0)) {
218          LiveRange *defRange =
219            li.getLiveRangeContaining(instrIdx.getDefIndex());
220          if (defRange != 0) // May have caught this already.
221            copyRange(*defRange);
222        }
223        if (instr.readsRegister(li.reg, 0)) {
224          LiveRange *useRange =
225            li.getLiveRangeContaining(instrIdx.getUseIndex());
226          if (useRange != 0) { // May have caught this already.
227            copyRange(*useRange);
228          }
229        }
230      }
231
232      for (MachineLoop::block_iterator bbItr = loop.block_begin(),
233                                       bbEnd = loop.block_end();
234           bbItr != bbEnd; ++bbItr) {
235        MachineBasicBlock &loopBlock = **bbItr;
236        LiveRange *enteringRange =
237          ls.lis->findEnteringRange(li, &loopBlock);
238        if (enteringRange != 0) {
239          copyRange(*enteringRange);
240        }
241      }
242    }
243
244    void renameInside() {
245      for (std::vector<MachineInstr*>::iterator iItr = loopInstrs.begin(),
246                                                iEnd = loopInstrs.end();
247           iItr != iEnd; ++iItr) {
248        MachineInstr &instr = **iItr;
249        for (unsigned i = 0; i < instr.getNumOperands(); ++i) {
250          MachineOperand &mop = instr.getOperand(i);
251          if (mop.isReg() && mop.getReg() == li.reg) {
252            mop.setReg(getNewLI()->reg);
253          }
254        }
255      }
256    }
257
258  };
259
260  void LoopSplitter::getAnalysisUsage(AnalysisUsage &au) const {
261    au.addRequired<MachineDominatorTree>();
262    au.addPreserved<MachineDominatorTree>();
263    au.addRequired<MachineLoopInfo>();
264    au.addPreserved<MachineLoopInfo>();
265    au.addPreservedID(RegisterCoalescerPassID);
266    au.addPreserved<CalculateSpillWeights>();
267    au.addPreserved<LiveStacks>();
268    au.addRequired<SlotIndexes>();
269    au.addPreserved<SlotIndexes>();
270    au.addRequired<LiveIntervals>();
271    au.addPreserved<LiveIntervals>();
272    MachineFunctionPass::getAnalysisUsage(au);
273  }
274
275  bool LoopSplitter::runOnMachineFunction(MachineFunction &fn) {
276
277    mf = &fn;
278    mri = &mf->getRegInfo();
279    tii = mf->getTarget().getInstrInfo();
280    tri = mf->getTarget().getRegisterInfo();
281    sis = &getAnalysis<SlotIndexes>();
282    lis = &getAnalysis<LiveIntervals>();
283    mli = &getAnalysis<MachineLoopInfo>();
284    mdt = &getAnalysis<MachineDominatorTree>();
285
286    fqn = mf->getFunction()->getParent()->getModuleIdentifier() + "." +
287      mf->getFunction()->getName().str();
288
289    dbgs() << "Splitting " << mf->getFunction()->getName() << ".";
290
291    dumpOddTerminators();
292
293//      dbgs() << "----------------------------------------\n";
294//      lis->dump();
295//      dbgs() << "----------------------------------------\n";
296
297//     std::deque<MachineLoop*> loops;
298//     std::copy(mli->begin(), mli->end(), std::back_inserter(loops));
299//     dbgs() << "Loops:\n";
300//     while (!loops.empty()) {
301//       MachineLoop &loop = *loops.front();
302//       loops.pop_front();
303//       std::copy(loop.begin(), loop.end(), std::back_inserter(loops));
304
305//       dumpLoopInfo(loop);
306//     }
307
308    //lis->dump();
309    //exit(0);
310
311    // Setup initial intervals.
312    for (LiveIntervals::iterator liItr = lis->begin(), liEnd = lis->end();
313         liItr != liEnd; ++liItr) {
314      LiveInterval *li = liItr->second;
315
316      if (TargetRegisterInfo::isVirtualRegister(li->reg) &&
317          !lis->intervalIsInOneMBB(*li)) {
318        intervals.push_back(li);
319      }
320    }
321
322    processIntervals();
323
324    intervals.clear();
325
326//     dbgs() << "----------------------------------------\n";
327//     lis->dump();
328//     dbgs() << "----------------------------------------\n";
329
330    dumpOddTerminators();
331
332    //exit(1);
333
334    return false;
335  }
336
337  void LoopSplitter::releaseMemory() {
338    fqn.clear();
339    intervals.clear();
340    loopRangeMap.clear();
341  }
342
343  void LoopSplitter::dumpOddTerminators() {
344    for (MachineFunction::iterator bbItr = mf->begin(), bbEnd = mf->end();
345         bbItr != bbEnd; ++bbItr) {
346      MachineBasicBlock *mbb = &*bbItr;
347      MachineBasicBlock *a = 0, *b = 0;
348      SmallVector<MachineOperand, 4> c;
349      if (tii->AnalyzeBranch(*mbb, a, b, c)) {
350        dbgs() << "MBB#" << mbb->getNumber() << " has multiway terminator.\n";
351        dbgs() << "  Terminators:\n";
352        for (MachineBasicBlock::iterator iItr = mbb->begin(), iEnd = mbb->end();
353             iItr != iEnd; ++iItr) {
354          MachineInstr *instr= &*iItr;
355          dbgs() << "    " << *instr << "";
356        }
357        dbgs() << "\n  Listed successors: [ ";
358        for (MachineBasicBlock::succ_iterator sItr = mbb->succ_begin(), sEnd = mbb->succ_end();
359             sItr != sEnd; ++sItr) {
360          MachineBasicBlock *succMBB = *sItr;
361          dbgs() << succMBB->getNumber() << " ";
362        }
363        dbgs() << "]\n\n";
364      }
365    }
366  }
367
368  void LoopSplitter::dumpLoopInfo(MachineLoop &loop) {
369    MachineBasicBlock &headerBlock = *loop.getHeader();
370    typedef SmallVector<MachineLoop::Edge, 8> ExitEdgesList;
371    ExitEdgesList exitEdges;
372    loop.getExitEdges(exitEdges);
373
374    dbgs() << "  Header: BB#" << headerBlock.getNumber() << ", Contains: [ ";
375    for (std::vector<MachineBasicBlock*>::const_iterator
376           subBlockItr = loop.getBlocks().begin(),
377           subBlockEnd = loop.getBlocks().end();
378         subBlockItr != subBlockEnd; ++subBlockItr) {
379      MachineBasicBlock &subBlock = **subBlockItr;
380      dbgs() << "BB#" << subBlock.getNumber() << " ";
381    }
382    dbgs() << "], Exit edges: [ ";
383    for (ExitEdgesList::iterator exitEdgeItr = exitEdges.begin(),
384                                 exitEdgeEnd = exitEdges.end();
385         exitEdgeItr != exitEdgeEnd; ++exitEdgeItr) {
386      MachineLoop::Edge &exitEdge = *exitEdgeItr;
387      dbgs() << "(MBB#" << exitEdge.first->getNumber()
388             << ", MBB#" << exitEdge.second->getNumber() << ") ";
389    }
390    dbgs() << "], Sub-Loop Headers: [ ";
391    for (MachineLoop::iterator subLoopItr = loop.begin(),
392                               subLoopEnd = loop.end();
393         subLoopItr != subLoopEnd; ++subLoopItr) {
394      MachineLoop &subLoop = **subLoopItr;
395      MachineBasicBlock &subLoopBlock = *subLoop.getHeader();
396      dbgs() << "BB#" << subLoopBlock.getNumber() << " ";
397    }
398    dbgs() << "]\n";
399  }
400
401  void LoopSplitter::updateTerminators(MachineBasicBlock &mbb) {
402    mbb.updateTerminator();
403
404    for (MachineBasicBlock::iterator miItr = mbb.begin(), miEnd = mbb.end();
405         miItr != miEnd; ++miItr) {
406      if (lis->isNotInMIMap(miItr)) {
407        lis->InsertMachineInstrInMaps(miItr);
408      }
409    }
410  }
411
412  bool LoopSplitter::canInsertPreHeader(MachineLoop &loop) {
413    MachineBasicBlock *header = loop.getHeader();
414    MachineBasicBlock *a = 0, *b = 0;
415    SmallVector<MachineOperand, 4> c;
416
417    for (MachineBasicBlock::pred_iterator pbItr = header->pred_begin(),
418                                          pbEnd = header->pred_end();
419         pbItr != pbEnd; ++pbItr) {
420      MachineBasicBlock *predBlock = *pbItr;
421      if (!!tii->AnalyzeBranch(*predBlock, a, b, c)) {
422        return false;
423      }
424    }
425
426    MachineFunction::iterator headerItr(header);
427    if (headerItr == mf->begin())
428      return true;
429    MachineBasicBlock *headerLayoutPred = llvm::prior(headerItr);
430    assert(headerLayoutPred != 0 && "Header should have layout pred.");
431
432    return (!tii->AnalyzeBranch(*headerLayoutPred, a, b, c));
433  }
434
435  MachineBasicBlock& LoopSplitter::insertPreHeader(MachineLoop &loop) {
436    assert(loop.getLoopPreheader() == 0 && "Loop already has preheader.");
437
438    MachineBasicBlock &header = *loop.getHeader();
439
440    // Save the preds - we'll need to update them once we insert the preheader.
441    typedef std::set<MachineBasicBlock*> HeaderPreds;
442    HeaderPreds headerPreds;
443
444    for (MachineBasicBlock::pred_iterator predItr = header.pred_begin(),
445                                          predEnd = header.pred_end();
446         predItr != predEnd; ++predItr) {
447      if (!loop.contains(*predItr))
448        headerPreds.insert(*predItr);
449    }
450
451    assert(!headerPreds.empty() && "No predecessors for header?");
452
453    //dbgs() << fqn << " MBB#" << header.getNumber() << " inserting preheader...";
454
455    MachineBasicBlock *preHeader =
456      mf->CreateMachineBasicBlock(header.getBasicBlock());
457
458    assert(preHeader != 0 && "Failed to create pre-header.");
459
460    mf->insert(header, preHeader);
461
462    for (HeaderPreds::iterator hpItr = headerPreds.begin(),
463                               hpEnd = headerPreds.end();
464         hpItr != hpEnd; ++hpItr) {
465      assert(*hpItr != 0 && "How'd a null predecessor get into this set?");
466      MachineBasicBlock &hp = **hpItr;
467      hp.ReplaceUsesOfBlockWith(&header, preHeader);
468    }
469    preHeader->addSuccessor(&header);
470
471    MachineBasicBlock *oldLayoutPred =
472      llvm::prior(MachineFunction::iterator(preHeader));
473    if (oldLayoutPred != 0) {
474      updateTerminators(*oldLayoutPred);
475    }
476
477    lis->InsertMBBInMaps(preHeader);
478
479    if (MachineLoop *parentLoop = loop.getParentLoop()) {
480      assert(parentLoop->getHeader() != loop.getHeader() &&
481             "Parent loop has same header?");
482      parentLoop->addBasicBlockToLoop(preHeader, mli->getBase());
483
484      // Invalidate all parent loop ranges.
485      while (parentLoop != 0) {
486        loopRangeMap.erase(parentLoop);
487        parentLoop = parentLoop->getParentLoop();
488      }
489    }
490
491    for (LiveIntervals::iterator liItr = lis->begin(),
492                                 liEnd = lis->end();
493         liItr != liEnd; ++liItr) {
494      LiveInterval &li = *liItr->second;
495
496      // Is this safe for physregs?
497      // TargetRegisterInfo::isPhysicalRegister(li.reg) ||
498      if (!lis->isLiveInToMBB(li, &header))
499        continue;
500
501      if (lis->isLiveInToMBB(li, preHeader)) {
502        assert(lis->isLiveOutOfMBB(li, preHeader) &&
503               "Range terminates in newly added preheader?");
504        continue;
505      }
506
507      bool insertRange = false;
508
509      for (MachineBasicBlock::pred_iterator predItr = preHeader->pred_begin(),
510                                            predEnd = preHeader->pred_end();
511           predItr != predEnd; ++predItr) {
512        MachineBasicBlock *predMBB = *predItr;
513        if (lis->isLiveOutOfMBB(li, predMBB)) {
514          insertRange = true;
515          break;
516        }
517      }
518
519      if (!insertRange)
520        continue;
521
522      SlotIndex newDefIdx = lis->getMBBStartIdx(preHeader);
523      assert(lis->getInstructionFromIndex(newDefIdx) == 0 &&
524             "PHI def index points at actual instruction.");
525      VNInfo *newVal = li.getNextValue(newDefIdx, 0, lis->getVNInfoAllocator());
526      li.addRange(LiveRange(lis->getMBBStartIdx(preHeader),
527                            lis->getMBBEndIdx(preHeader),
528                            newVal));
529    }
530
531
532    //dbgs() << "Dumping SlotIndexes:\n";
533    //sis->dump();
534
535    //dbgs() << "done. (Added MBB#" << preHeader->getNumber() << ")\n";
536
537    return *preHeader;
538  }
539
540  bool LoopSplitter::isCriticalEdge(MachineLoop::Edge &edge) {
541    assert(edge.first->succ_size() > 1 && "Non-sensical edge.");
542    if (edge.second->pred_size() > 1)
543      return true;
544    return false;
545  }
546
547  bool LoopSplitter::canSplitEdge(MachineLoop::Edge &edge) {
548    MachineFunction::iterator outBlockItr(edge.second);
549    if (outBlockItr == mf->begin())
550      return true;
551    MachineBasicBlock *outBlockLayoutPred = llvm::prior(outBlockItr);
552    assert(outBlockLayoutPred != 0 && "Should have a layout pred if out!=begin.");
553    MachineBasicBlock *a = 0, *b = 0;
554    SmallVector<MachineOperand, 4> c;
555    return (!tii->AnalyzeBranch(*outBlockLayoutPred, a, b, c) &&
556            !tii->AnalyzeBranch(*edge.first, a, b, c));
557  }
558
559  MachineBasicBlock& LoopSplitter::splitEdge(MachineLoop::Edge &edge,
560                                             MachineLoop &loop) {
561
562    MachineBasicBlock &inBlock = *edge.first;
563    MachineBasicBlock &outBlock = *edge.second;
564
565    assert((inBlock.succ_size() > 1) && (outBlock.pred_size() > 1) &&
566           "Splitting non-critical edge?");
567
568    //dbgs() << fqn << " Splitting edge (MBB#" << inBlock.getNumber()
569    //       << " -> MBB#" << outBlock.getNumber() << ")...";
570
571    MachineBasicBlock *splitBlock =
572      mf->CreateMachineBasicBlock();
573
574    assert(splitBlock != 0 && "Failed to create split block.");
575
576    mf->insert(&outBlock, splitBlock);
577
578    inBlock.ReplaceUsesOfBlockWith(&outBlock, splitBlock);
579    splitBlock->addSuccessor(&outBlock);
580
581    MachineBasicBlock *oldLayoutPred =
582      llvm::prior(MachineFunction::iterator(splitBlock));
583    if (oldLayoutPred != 0) {
584      updateTerminators(*oldLayoutPred);
585    }
586
587    lis->InsertMBBInMaps(splitBlock);
588
589    loopRangeMap.erase(&loop);
590
591    MachineLoop *splitParentLoop = loop.getParentLoop();
592    while (splitParentLoop != 0 &&
593           !splitParentLoop->contains(&outBlock)) {
594      splitParentLoop = splitParentLoop->getParentLoop();
595    }
596
597    if (splitParentLoop != 0) {
598      assert(splitParentLoop->contains(&loop) &&
599             "Split-block parent doesn't contain original loop?");
600      splitParentLoop->addBasicBlockToLoop(splitBlock, mli->getBase());
601
602      // Invalidate all parent loop ranges.
603      while (splitParentLoop != 0) {
604        loopRangeMap.erase(splitParentLoop);
605        splitParentLoop = splitParentLoop->getParentLoop();
606      }
607    }
608
609
610    for (LiveIntervals::iterator liItr = lis->begin(),
611                                 liEnd = lis->end();
612         liItr != liEnd; ++liItr) {
613      LiveInterval &li = *liItr->second;
614      bool intersects = lis->isLiveOutOfMBB(li, &inBlock) &&
615                       lis->isLiveInToMBB(li, &outBlock);
616      if (lis->isLiveInToMBB(li, splitBlock)) {
617        if (!intersects) {
618          li.removeRange(lis->getMBBStartIdx(splitBlock),
619                         lis->getMBBEndIdx(splitBlock), true);
620        }
621      } else if (intersects) {
622        SlotIndex newDefIdx = lis->getMBBStartIdx(splitBlock);
623        assert(lis->getInstructionFromIndex(newDefIdx) == 0 &&
624               "PHI def index points at actual instruction.");
625        VNInfo *newVal = li.getNextValue(newDefIdx, 0,
626                                         lis->getVNInfoAllocator());
627        li.addRange(LiveRange(lis->getMBBStartIdx(splitBlock),
628                              lis->getMBBEndIdx(splitBlock),
629                              newVal));
630      }
631    }
632
633    //dbgs() << "done. (Added MBB#" << splitBlock->getNumber() << ")\n";
634
635    return *splitBlock;
636  }
637
638  LoopSplitter::LoopRanges& LoopSplitter::getLoopRanges(MachineLoop &loop) {
639    typedef std::set<MachineBasicBlock*, StartSlotComparator> LoopMBBSet;
640    LoopRangeMap::iterator lrItr = loopRangeMap.find(&loop);
641    if (lrItr == loopRangeMap.end()) {
642      LoopMBBSet loopMBBs((StartSlotComparator(*lis)));
643      std::copy(loop.block_begin(), loop.block_end(),
644                std::inserter(loopMBBs, loopMBBs.begin()));
645
646      assert(!loopMBBs.empty() && "No blocks in loop?");
647
648      LoopRanges &loopRanges = loopRangeMap[&loop];
649      assert(loopRanges.empty() && "Loop encountered but not processed?");
650      SlotIndex oldEnd = lis->getMBBEndIdx(*loopMBBs.begin());
651      loopRanges.push_back(
652        std::make_pair(lis->getMBBStartIdx(*loopMBBs.begin()),
653                       lis->getInvalidIndex()));
654      for (LoopMBBSet::iterator curBlockItr = llvm::next(loopMBBs.begin()),
655                                curBlockEnd = loopMBBs.end();
656           curBlockItr != curBlockEnd; ++curBlockItr) {
657        SlotIndex newStart = lis->getMBBStartIdx(*curBlockItr);
658        if (newStart != oldEnd) {
659          loopRanges.back().second = oldEnd;
660          loopRanges.push_back(std::make_pair(newStart,
661                                              lis->getInvalidIndex()));
662        }
663        oldEnd = lis->getMBBEndIdx(*curBlockItr);
664      }
665
666      loopRanges.back().second =
667        lis->getMBBEndIdx(*llvm::prior(loopMBBs.end()));
668
669      return loopRanges;
670    }
671    return lrItr->second;
672  }
673
674  std::pair<bool, LoopSplitter::SlotPair> LoopSplitter::getLoopSubRange(
675                                                           const LiveRange &lr,
676                                                           MachineLoop &loop) {
677    LoopRanges &loopRanges = getLoopRanges(loop);
678    LoopRanges::iterator lrItr = loopRanges.begin(),
679                         lrEnd = loopRanges.end();
680    while (lrItr != lrEnd && lr.start >= lrItr->second) {
681      ++lrItr;
682    }
683
684    if (lrItr == lrEnd) {
685      SlotIndex invalid = lis->getInvalidIndex();
686      return std::make_pair(false, SlotPair(invalid, invalid));
687    }
688
689    SlotIndex srStart(lr.start < lrItr->first ? lrItr->first : lr.start);
690    SlotIndex srEnd(lr.end > lrItr->second ? lrItr->second : lr.end);
691
692    return std::make_pair(true, SlotPair(srStart, srEnd));
693  }
694
695  void LoopSplitter::dumpLoopRanges(MachineLoop &loop) {
696    LoopRanges &loopRanges = getLoopRanges(loop);
697    dbgs() << "For loop MBB#" << loop.getHeader()->getNumber() << ", subranges are: [ ";
698    for (LoopRanges::iterator lrItr = loopRanges.begin(), lrEnd = loopRanges.end();
699         lrItr != lrEnd; ++lrItr) {
700      dbgs() << "[" << lrItr->first << ", " << lrItr->second << ") ";
701    }
702    dbgs() << "]\n";
703  }
704
705  void LoopSplitter::processHeader(LoopSplit &split) {
706    MachineBasicBlock &header = *split.getLoop().getHeader();
707    //dbgs() << "  Processing loop header BB#" << header.getNumber() << "\n";
708
709    if (!lis->isLiveInToMBB(split.getLI(), &header))
710      return; // Not live in, but nothing wrong so far.
711
712    MachineBasicBlock *preHeader = split.getLoop().getLoopPreheader();
713    if (!preHeader) {
714
715      if (!canInsertPreHeader(split.getLoop())) {
716        split.invalidate();
717        return; // Couldn't insert a pre-header. Bail on this interval.
718      }
719
720      for (MachineBasicBlock::pred_iterator predItr = header.pred_begin(),
721                                            predEnd = header.pred_end();
722           predItr != predEnd; ++predItr) {
723        if (lis->isLiveOutOfMBB(split.getLI(), *predItr)) {
724          split.splitIncoming();
725          break;
726        }
727      }
728    } else if (lis->isLiveOutOfMBB(split.getLI(), preHeader)) {
729      split.splitIncoming();
730    }
731  }
732
733  void LoopSplitter::processLoopExits(LoopSplit &split) {
734    typedef SmallVector<MachineLoop::Edge, 8> ExitEdgesList;
735    ExitEdgesList exitEdges;
736    split.getLoop().getExitEdges(exitEdges);
737
738    //dbgs() << "  Processing loop exits:\n";
739
740    for (ExitEdgesList::iterator exitEdgeItr = exitEdges.begin(),
741                                 exitEdgeEnd = exitEdges.end();
742         exitEdgeItr != exitEdgeEnd; ++exitEdgeItr) {
743      MachineLoop::Edge exitEdge = *exitEdgeItr;
744
745      LiveRange *outRange =
746        split.getLI().getLiveRangeContaining(lis->getMBBStartIdx(exitEdge.second));
747
748      if (outRange != 0) {
749        if (isCriticalEdge(exitEdge) && !canSplitEdge(exitEdge)) {
750          split.invalidate();
751          return;
752        }
753
754        split.splitOutgoing(exitEdge);
755      }
756    }
757  }
758
759  void LoopSplitter::processLoopUses(LoopSplit &split) {
760    std::set<MachineInstr*> processed;
761
762    for (MachineRegisterInfo::reg_iterator
763           rItr = mri->reg_begin(split.getLI().reg),
764           rEnd = mri->reg_end();
765      rItr != rEnd; ++rItr) {
766      MachineInstr &instr = *rItr;
767      if (split.getLoop().contains(&instr) && processed.count(&instr) == 0) {
768        split.addLoopInstr(&instr);
769        processed.insert(&instr);
770      }
771    }
772
773    //dbgs() << "  Rewriting reg" << li.reg << " to reg" << newLI->reg
774    //       << " in blocks [ ";
775    //dbgs() << "]\n";
776  }
777
778  bool LoopSplitter::splitOverLoop(LiveInterval &li, MachineLoop &loop) {
779    assert(TargetRegisterInfo::isVirtualRegister(li.reg) &&
780           "Attempt to split physical register.");
781
782    LoopSplit split(*this, li, loop);
783    processHeader(split);
784    if (split.isValid())
785      processLoopExits(split);
786    if (split.isValid())
787      processLoopUses(split);
788    if (split.isValid() /* && split.isWorthwhile() */) {
789      split.apply();
790      DEBUG(dbgs() << "Success.\n");
791      return true;
792    }
793    DEBUG(dbgs() << "Failed.\n");
794    return false;
795  }
796
797  void LoopSplitter::processInterval(LiveInterval &li) {
798    std::deque<MachineLoop*> loops;
799    std::copy(mli->begin(), mli->end(), std::back_inserter(loops));
800
801    while (!loops.empty()) {
802      MachineLoop &loop = *loops.front();
803      loops.pop_front();
804      DEBUG(
805        dbgs() << fqn << " reg" << li.reg << " " << li.weight << " BB#"
806               << loop.getHeader()->getNumber() << " ";
807      );
808      if (!splitOverLoop(li, loop)) {
809        // Couldn't split over outer loop, schedule sub-loops to be checked.
810	std::copy(loop.begin(), loop.end(), std::back_inserter(loops));
811      }
812    }
813  }
814
815  void LoopSplitter::processIntervals() {
816    while (!intervals.empty()) {
817      LiveInterval &li = *intervals.front();
818      intervals.pop_front();
819
820      assert(!lis->intervalIsInOneMBB(li) &&
821             "Single interval in process worklist.");
822
823      processInterval(li);
824    }
825  }
826
827}
828