]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
1 | //===-- SlotIndexes.cpp - Slot Indexes Pass ------------------------------===// |
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 | ||
223e47cc LB |
10 | #include "llvm/CodeGen/SlotIndexes.h" |
11 | #include "llvm/ADT/Statistic.h" | |
12 | #include "llvm/CodeGen/MachineFunction.h" | |
13 | #include "llvm/Support/Debug.h" | |
14 | #include "llvm/Support/raw_ostream.h" | |
15 | #include "llvm/Target/TargetInstrInfo.h" | |
16 | ||
17 | using namespace llvm; | |
18 | ||
1a4d82fc JJ |
19 | #define DEBUG_TYPE "slotindexes" |
20 | ||
223e47cc LB |
21 | char SlotIndexes::ID = 0; |
22 | INITIALIZE_PASS(SlotIndexes, "slotindexes", | |
23 | "Slot index numbering", false, false) | |
24 | ||
25 | STATISTIC(NumLocalRenum, "Number of local renumberings"); | |
26 | STATISTIC(NumGlobalRenum, "Number of global renumberings"); | |
27 | ||
28 | void SlotIndexes::getAnalysisUsage(AnalysisUsage &au) const { | |
29 | au.setPreservesAll(); | |
30 | MachineFunctionPass::getAnalysisUsage(au); | |
31 | } | |
32 | ||
33 | void SlotIndexes::releaseMemory() { | |
34 | mi2iMap.clear(); | |
35 | MBBRanges.clear(); | |
36 | idx2MBBMap.clear(); | |
37 | indexList.clear(); | |
38 | ileAllocator.Reset(); | |
39 | } | |
40 | ||
41 | bool SlotIndexes::runOnMachineFunction(MachineFunction &fn) { | |
42 | ||
43 | // Compute numbering as follows: | |
44 | // Grab an iterator to the start of the index list. | |
45 | // Iterate over all MBBs, and within each MBB all MIs, keeping the MI | |
46 | // iterator in lock-step (though skipping it over indexes which have | |
47 | // null pointers in the instruction field). | |
48 | // At each iteration assert that the instruction pointed to in the index | |
49 | // is the same one pointed to by the MI iterator. This | |
50 | ||
51 | // FIXME: This can be simplified. The mi2iMap_, Idx2MBBMap, etc. should | |
52 | // only need to be set up once after the first numbering is computed. | |
53 | ||
54 | mf = &fn; | |
55 | ||
56 | // Check that the list contains only the sentinal. | |
57 | assert(indexList.empty() && "Index list non-empty at initial numbering?"); | |
58 | assert(idx2MBBMap.empty() && | |
59 | "Index -> MBB mapping non-empty at initial numbering?"); | |
60 | assert(MBBRanges.empty() && | |
61 | "MBB -> Index mapping non-empty at initial numbering?"); | |
62 | assert(mi2iMap.empty() && | |
63 | "MachineInstr -> Index mapping non-empty at initial numbering?"); | |
64 | ||
65 | unsigned index = 0; | |
66 | MBBRanges.resize(mf->getNumBlockIDs()); | |
67 | idx2MBBMap.reserve(mf->size()); | |
68 | ||
1a4d82fc | 69 | indexList.push_back(createEntry(nullptr, index)); |
223e47cc LB |
70 | |
71 | // Iterate over the function. | |
72 | for (MachineFunction::iterator mbbItr = mf->begin(), mbbEnd = mf->end(); | |
73 | mbbItr != mbbEnd; ++mbbItr) { | |
74 | MachineBasicBlock *mbb = &*mbbItr; | |
75 | ||
76 | // Insert an index for the MBB start. | |
77 | SlotIndex blockStartIndex(&indexList.back(), SlotIndex::Slot_Block); | |
78 | ||
79 | for (MachineBasicBlock::iterator miItr = mbb->begin(), miEnd = mbb->end(); | |
80 | miItr != miEnd; ++miItr) { | |
81 | MachineInstr *mi = miItr; | |
82 | if (mi->isDebugValue()) | |
83 | continue; | |
84 | ||
85 | // Insert a store index for the instr. | |
86 | indexList.push_back(createEntry(mi, index += SlotIndex::InstrDist)); | |
87 | ||
88 | // Save this base index in the maps. | |
89 | mi2iMap.insert(std::make_pair(mi, SlotIndex(&indexList.back(), | |
90 | SlotIndex::Slot_Block))); | |
91 | } | |
92 | ||
93 | // We insert one blank instructions between basic blocks. | |
1a4d82fc | 94 | indexList.push_back(createEntry(nullptr, index += SlotIndex::InstrDist)); |
223e47cc LB |
95 | |
96 | MBBRanges[mbb->getNumber()].first = blockStartIndex; | |
97 | MBBRanges[mbb->getNumber()].second = SlotIndex(&indexList.back(), | |
98 | SlotIndex::Slot_Block); | |
99 | idx2MBBMap.push_back(IdxMBBPair(blockStartIndex, mbb)); | |
100 | } | |
101 | ||
102 | // Sort the Idx2MBBMap | |
103 | std::sort(idx2MBBMap.begin(), idx2MBBMap.end(), Idx2MBBCompare()); | |
104 | ||
105 | DEBUG(mf->print(dbgs(), this)); | |
106 | ||
107 | // And we're done! | |
108 | return false; | |
109 | } | |
110 | ||
111 | void SlotIndexes::renumberIndexes() { | |
112 | // Renumber updates the index of every element of the index list. | |
113 | DEBUG(dbgs() << "\n*** Renumbering SlotIndexes ***\n"); | |
114 | ++NumGlobalRenum; | |
115 | ||
116 | unsigned index = 0; | |
117 | ||
118 | for (IndexList::iterator I = indexList.begin(), E = indexList.end(); | |
119 | I != E; ++I) { | |
120 | I->setIndex(index); | |
121 | index += SlotIndex::InstrDist; | |
122 | } | |
123 | } | |
124 | ||
125 | // Renumber indexes locally after curItr was inserted, but failed to get a new | |
126 | // index. | |
127 | void SlotIndexes::renumberIndexes(IndexList::iterator curItr) { | |
128 | // Number indexes with half the default spacing so we can catch up quickly. | |
129 | const unsigned Space = SlotIndex::InstrDist/2; | |
130 | assert((Space & 3) == 0 && "InstrDist must be a multiple of 2*NUM"); | |
131 | ||
1a4d82fc | 132 | IndexList::iterator startItr = std::prev(curItr); |
223e47cc LB |
133 | unsigned index = startItr->getIndex(); |
134 | do { | |
135 | curItr->setIndex(index += Space); | |
136 | ++curItr; | |
137 | // If the next index is bigger, we have caught up. | |
138 | } while (curItr != indexList.end() && curItr->getIndex() <= index); | |
139 | ||
140 | DEBUG(dbgs() << "\n*** Renumbered SlotIndexes " << startItr->getIndex() << '-' | |
141 | << index << " ***\n"); | |
142 | ++NumLocalRenum; | |
143 | } | |
144 | ||
970d7e83 LB |
145 | // Repair indexes after adding and removing instructions. |
146 | void SlotIndexes::repairIndexesInRange(MachineBasicBlock *MBB, | |
147 | MachineBasicBlock::iterator Begin, | |
148 | MachineBasicBlock::iterator End) { | |
149 | // FIXME: Is this really necessary? The only caller repairIntervalsForRange() | |
150 | // does the same thing. | |
151 | // Find anchor points, which are at the beginning/end of blocks or at | |
152 | // instructions that already have indexes. | |
153 | while (Begin != MBB->begin() && !hasIndex(Begin)) | |
154 | --Begin; | |
155 | while (End != MBB->end() && !hasIndex(End)) | |
156 | ++End; | |
157 | ||
158 | bool includeStart = (Begin == MBB->begin()); | |
159 | SlotIndex startIdx; | |
160 | if (includeStart) | |
161 | startIdx = getMBBStartIdx(MBB); | |
162 | else | |
163 | startIdx = getInstructionIndex(Begin); | |
164 | ||
165 | SlotIndex endIdx; | |
166 | if (End == MBB->end()) | |
167 | endIdx = getMBBEndIdx(MBB); | |
168 | else | |
169 | endIdx = getInstructionIndex(End); | |
170 | ||
171 | // FIXME: Conceptually, this code is implementing an iterator on MBB that | |
172 | // optionally includes an additional position prior to MBB->begin(), indicated | |
173 | // by the includeStart flag. This is done so that we can iterate MIs in a MBB | |
174 | // in parallel with SlotIndexes, but there should be a better way to do this. | |
175 | IndexList::iterator ListB = startIdx.listEntry(); | |
176 | IndexList::iterator ListI = endIdx.listEntry(); | |
177 | MachineBasicBlock::iterator MBBI = End; | |
178 | bool pastStart = false; | |
179 | while (ListI != ListB || MBBI != Begin || (includeStart && !pastStart)) { | |
180 | assert(ListI->getIndex() >= startIdx.getIndex() && | |
181 | (includeStart || !pastStart) && | |
182 | "Decremented past the beginning of region to repair."); | |
183 | ||
184 | MachineInstr *SlotMI = ListI->getInstr(); | |
1a4d82fc | 185 | MachineInstr *MI = (MBBI != MBB->end() && !pastStart) ? MBBI : nullptr; |
970d7e83 LB |
186 | bool MBBIAtBegin = MBBI == Begin && (!includeStart || pastStart); |
187 | ||
188 | if (SlotMI == MI && !MBBIAtBegin) { | |
189 | --ListI; | |
190 | if (MBBI != Begin) | |
191 | --MBBI; | |
192 | else | |
193 | pastStart = true; | |
194 | } else if (MI && mi2iMap.find(MI) == mi2iMap.end()) { | |
195 | if (MBBI != Begin) | |
196 | --MBBI; | |
197 | else | |
198 | pastStart = true; | |
199 | } else { | |
200 | --ListI; | |
201 | if (SlotMI) | |
202 | removeMachineInstrFromMaps(SlotMI); | |
203 | } | |
204 | } | |
205 | ||
206 | // In theory this could be combined with the previous loop, but it is tricky | |
207 | // to update the IndexList while we are iterating it. | |
208 | for (MachineBasicBlock::iterator I = End; I != Begin;) { | |
209 | --I; | |
210 | MachineInstr *MI = I; | |
211 | if (!MI->isDebugValue() && mi2iMap.find(MI) == mi2iMap.end()) | |
212 | insertMachineInstrInMaps(MI); | |
213 | } | |
214 | } | |
223e47cc LB |
215 | |
216 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) | |
217 | void SlotIndexes::dump() const { | |
218 | for (IndexList::const_iterator itr = indexList.begin(); | |
219 | itr != indexList.end(); ++itr) { | |
220 | dbgs() << itr->getIndex() << " "; | |
221 | ||
1a4d82fc | 222 | if (itr->getInstr()) { |
223e47cc LB |
223 | dbgs() << *itr->getInstr(); |
224 | } else { | |
225 | dbgs() << "\n"; | |
226 | } | |
227 | } | |
228 | ||
229 | for (unsigned i = 0, e = MBBRanges.size(); i != e; ++i) | |
230 | dbgs() << "BB#" << i << "\t[" << MBBRanges[i].first << ';' | |
231 | << MBBRanges[i].second << ")\n"; | |
232 | } | |
233 | #endif | |
234 | ||
235 | // Print a SlotIndex to a raw_ostream. | |
236 | void SlotIndex::print(raw_ostream &os) const { | |
237 | if (isValid()) | |
238 | os << listEntry()->getIndex() << "Berd"[getSlot()]; | |
239 | else | |
240 | os << "invalid"; | |
241 | } | |
242 | ||
243 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) | |
244 | // Dump a SlotIndex to stderr. | |
245 | void SlotIndex::dump() const { | |
246 | print(dbgs()); | |
247 | dbgs() << "\n"; | |
248 | } | |
249 | #endif | |
250 |