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 "llvm/CodeGen/LiveIntervalAnalysis.h"
18 #include "llvm/CodeGen/MachineFunctionPass.h"
19 #include "llvm/CodeGen/MachineLoopInfo.h"
20 #include "llvm/CodeGen/MachineRegisterInfo.h"
21 #include "llvm/Support/Debug.h"
22 #include "llvm/Support/raw_ostream.h"
23 
24 using namespace llvm;
25 
26 
27 //===----------------------------------------------------------------------===//
28 //                                 Split Analysis
29 //===----------------------------------------------------------------------===//
30 
31 SplitAnalysis::SplitAnalysis(const MachineFunction *mf,
32                              const LiveIntervals *lis,
33                              const MachineLoopInfo *mli)
34   : mf_(*mf),
35     lis_(*lis),
36     loops_(*mli),
37     curli_(0) {}
38 
39 void SplitAnalysis::clear() {
40   usingInstrs_.clear();
41   usingBlocks_.clear();
42   usingLoops_.clear();
43 }
44 
45 /// analyseUses - Count instructions, basic blocks, and loops using curli.
46 void SplitAnalysis::analyseUses() {
47   const MachineRegisterInfo &MRI = mf_.getRegInfo();
48   for (MachineRegisterInfo::reg_iterator I = MRI.reg_begin(curli_->reg);
49        MachineInstr *MI = I.skipInstruction();) {
50     if (MI->isDebugValue() || !usingInstrs_.insert(MI))
51       continue;
52     MachineBasicBlock *MBB = MI->getParent();
53     if (usingBlocks_[MBB]++)
54       continue;
55     if (MachineLoop *Loop = loops_.getLoopFor(MBB))
56       usingLoops_.insert(Loop);
57   }
58   DEBUG(dbgs() << "Counted "
59                << usingInstrs_.size() << " instrs, "
60                << usingBlocks_.size() << " blocks, "
61                << usingLoops_.size()  << " loops in "
62                << *curli_ << "\n");
63 }
64 
65 SplitAnalysis::LoopPeripheralUse
66 SplitAnalysis::analyzeLoopPeripheralUse(const MachineLoop *Loop) {
67   // Peripheral blocks.
68   SmallVector<MachineBasicBlock*, 16> Peri;
69   Loop->getExitBlocks(Peri);
70   if (MachineBasicBlock *PredBB = Loop->getLoopPredecessor())
71     Peri.push_back(PredBB);
72   array_pod_sort(Peri.begin(), Peri.end());
73   Peri.erase(std::unique(Peri.begin(), Peri.end()), Peri.end());
74 
75   LoopPeripheralUse use = ContainedInLoop;
76   for (BlockCountMap::iterator I = usingBlocks_.begin(), E = usingBlocks_.end();
77        I != E; ++I) {
78     const MachineBasicBlock *MBB = I->first;
79     // Is this a peripheral block?
80     if (use < MultiPeripheral &&
81         std::binary_search(Peri.begin(), Peri.end(), MBB)) {
82       if (I->second > 1) use = MultiPeripheral;
83       else               use = SinglePeripheral;
84       continue;
85     }
86     // Is it a loop block?
87     if (Loop->contains(MBB))
88       continue;
89     // It must be an unrelated block.
90     return OutsideLoop;
91   }
92   return use;
93 }
94 
95 void SplitAnalysis::analyze(const LiveInterval *li) {
96   clear();
97   curli_ = li;
98   analyseUses();
99 }
100 
101 const MachineLoop *SplitAnalysis::getBestSplitLoop() {
102   LoopPtrSet Loops, SecondLoops;
103 
104   // Find first-class and second class candidate loops.
105   // We prefer to split around loops where curli is used outside the periphery.
106   for (LoopPtrSet::const_iterator I = usingLoops_.begin(),
107        E = usingLoops_.end(); I != E; ++I)
108     switch(analyzeLoopPeripheralUse(*I)) {
109     case OutsideLoop:
110       Loops.insert(*I);
111       break;
112     case MultiPeripheral:
113       SecondLoops.insert(*I);
114       break;
115     default:
116       continue;
117     }
118 
119   // If there are no first class loops available, look at second class loops.
120   if (Loops.empty())
121     Loops = SecondLoops;
122 
123   if (Loops.empty())
124     return 0;
125 
126   // Pick the earliest loop.
127   // FIXME: Are there other heuristics to consider?
128   // - avoid breaking critical edges.
129   // - avoid impossible loops.
130   const MachineLoop *Best = 0;
131   SlotIndex BestIdx;
132   for (LoopPtrSet::const_iterator I = Loops.begin(), E = Loops.end(); I != E;
133        ++I) {
134     SlotIndex Idx = lis_.getMBBStartIdx((*I)->getHeader());
135     if (!Best || Idx < BestIdx)
136       Best = *I, BestIdx = Idx;
137   }
138   return Best;
139 }
140 
141 //===----------------------------------------------------------------------===//
142 //                               Loop Splitting
143 //===----------------------------------------------------------------------===//
144 
145 bool llvm::splitAroundLoop(SplitAnalysis &sa, const MachineLoop *loop) {
146   return false;
147 }
148 
149