LLVM  7.0.0svn
SlotIndexes.cpp
Go to the documentation of this file.
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 
11 #include "llvm/ADT/Statistic.h"
13 #include "llvm/Support/Debug.h"
15 
16 using namespace llvm;
17 
18 #define DEBUG_TYPE "slotindexes"
19 
20 char SlotIndexes::ID = 0;
22  "Slot index numbering", false, false)
23 
24 STATISTIC(NumLocalRenum, "Number of local renumberings");
25 STATISTIC(NumGlobalRenum, "Number of global renumberings");
26 
27 void SlotIndexes::getAnalysisUsage(AnalysisUsage &au) const {
28  au.setPreservesAll();
30 }
31 
33  mi2iMap.clear();
34  MBBRanges.clear();
35  idx2MBBMap.clear();
36  indexList.clear();
37  ileAllocator.Reset();
38 }
39 
41 
42  // Compute numbering as follows:
43  // Grab an iterator to the start of the index list.
44  // Iterate over all MBBs, and within each MBB all MIs, keeping the MI
45  // iterator in lock-step (though skipping it over indexes which have
46  // null pointers in the instruction field).
47  // At each iteration assert that the instruction pointed to in the index
48  // is the same one pointed to by the MI iterator. This
49 
50  // FIXME: This can be simplified. The mi2iMap_, Idx2MBBMap, etc. should
51  // only need to be set up once after the first numbering is computed.
52 
53  mf = &fn;
54 
55  // Check that the list contains only the sentinal.
56  assert(indexList.empty() && "Index list non-empty at initial numbering?");
57  assert(idx2MBBMap.empty() &&
58  "Index -> MBB mapping non-empty at initial numbering?");
59  assert(MBBRanges.empty() &&
60  "MBB -> Index mapping non-empty at initial numbering?");
61  assert(mi2iMap.empty() &&
62  "MachineInstr -> Index mapping non-empty at initial numbering?");
63 
64  unsigned index = 0;
65  MBBRanges.resize(mf->getNumBlockIDs());
66  idx2MBBMap.reserve(mf->size());
67 
68  indexList.push_back(createEntry(nullptr, index));
69 
70  // Iterate over the function.
71  for (MachineBasicBlock &MBB : *mf) {
72  // Insert an index for the MBB start.
73  SlotIndex blockStartIndex(&indexList.back(), SlotIndex::Slot_Block);
74 
75  for (MachineInstr &MI : MBB) {
76  if (MI.isDebugValue())
77  continue;
78 
79  // Insert a store index for the instr.
80  indexList.push_back(createEntry(&MI, index += SlotIndex::InstrDist));
81 
82  // Save this base index in the maps.
83  mi2iMap.insert(std::make_pair(
84  &MI, SlotIndex(&indexList.back(), SlotIndex::Slot_Block)));
85  }
86 
87  // We insert one blank instructions between basic blocks.
88  indexList.push_back(createEntry(nullptr, index += SlotIndex::InstrDist));
89 
90  MBBRanges[MBB.getNumber()].first = blockStartIndex;
91  MBBRanges[MBB.getNumber()].second = SlotIndex(&indexList.back(),
92  SlotIndex::Slot_Block);
93  idx2MBBMap.push_back(IdxMBBPair(blockStartIndex, &MBB));
94  }
95 
96  // Sort the Idx2MBBMap
97  std::sort(idx2MBBMap.begin(), idx2MBBMap.end(), Idx2MBBCompare());
98 
99  DEBUG(mf->print(dbgs(), this));
100 
101  // And we're done!
102  return false;
103 }
104 
106  assert(!MI.isBundledWithPred() &&
107  "Use removeSingleMachineInstrFromMaps() instread");
108  Mi2IndexMap::iterator mi2iItr = mi2iMap.find(&MI);
109  if (mi2iItr == mi2iMap.end())
110  return;
111 
112  SlotIndex MIIndex = mi2iItr->second;
113  IndexListEntry &MIEntry = *MIIndex.listEntry();
114  assert(MIEntry.getInstr() == &MI && "Instruction indexes broken.");
115  mi2iMap.erase(mi2iItr);
116  // FIXME: Eventually we want to actually delete these indexes.
117  MIEntry.setInstr(nullptr);
118 }
119 
121  Mi2IndexMap::iterator mi2iItr = mi2iMap.find(&MI);
122  if (mi2iItr == mi2iMap.end())
123  return;
124 
125  SlotIndex MIIndex = mi2iItr->second;
126  IndexListEntry &MIEntry = *MIIndex.listEntry();
127  assert(MIEntry.getInstr() == &MI && "Instruction indexes broken.");
128  mi2iMap.erase(mi2iItr);
129 
130  // When removing the first instruction of a bundle update mapping to next
131  // instruction.
132  if (MI.isBundledWithSucc()) {
133  // Only the first instruction of a bundle should have an index assigned.
134  assert(!MI.isBundledWithPred() && "Should have first bundle isntruction");
135 
136  MachineBasicBlock::instr_iterator Next = std::next(MI.getIterator());
137  MachineInstr &NextMI = *Next;
138  MIEntry.setInstr(&NextMI);
139  mi2iMap.insert(std::make_pair(&NextMI, MIIndex));
140  return;
141  } else {
142  // FIXME: Eventually we want to actually delete these indexes.
143  MIEntry.setInstr(nullptr);
144  }
145 }
146 
148  // Renumber updates the index of every element of the index list.
149  DEBUG(dbgs() << "\n*** Renumbering SlotIndexes ***\n");
150  ++NumGlobalRenum;
151 
152  unsigned index = 0;
153 
154  for (IndexList::iterator I = indexList.begin(), E = indexList.end();
155  I != E; ++I) {
156  I->setIndex(index);
157  index += SlotIndex::InstrDist;
158  }
159 }
160 
161 // Renumber indexes locally after curItr was inserted, but failed to get a new
162 // index.
164  // Number indexes with half the default spacing so we can catch up quickly.
165  const unsigned Space = SlotIndex::InstrDist/2;
166  static_assert((Space & 3) == 0, "InstrDist must be a multiple of 2*NUM");
167 
168  IndexList::iterator startItr = std::prev(curItr);
169  unsigned index = startItr->getIndex();
170  do {
171  curItr->setIndex(index += Space);
172  ++curItr;
173  // If the next index is bigger, we have caught up.
174  } while (curItr != indexList.end() && curItr->getIndex() <= index);
175 
176  DEBUG(dbgs() << "\n*** Renumbered SlotIndexes " << startItr->getIndex() << '-'
177  << index << " ***\n");
178  ++NumLocalRenum;
179 }
180 
181 // Repair indexes after adding and removing instructions.
185  // FIXME: Is this really necessary? The only caller repairIntervalsForRange()
186  // does the same thing.
187  // Find anchor points, which are at the beginning/end of blocks or at
188  // instructions that already have indexes.
189  while (Begin != MBB->begin() && !hasIndex(*Begin))
190  --Begin;
191  while (End != MBB->end() && !hasIndex(*End))
192  ++End;
193 
194  bool includeStart = (Begin == MBB->begin());
195  SlotIndex startIdx;
196  if (includeStart)
197  startIdx = getMBBStartIdx(MBB);
198  else
199  startIdx = getInstructionIndex(*Begin);
200 
201  SlotIndex endIdx;
202  if (End == MBB->end())
203  endIdx = getMBBEndIdx(MBB);
204  else
205  endIdx = getInstructionIndex(*End);
206 
207  // FIXME: Conceptually, this code is implementing an iterator on MBB that
208  // optionally includes an additional position prior to MBB->begin(), indicated
209  // by the includeStart flag. This is done so that we can iterate MIs in a MBB
210  // in parallel with SlotIndexes, but there should be a better way to do this.
211  IndexList::iterator ListB = startIdx.listEntry()->getIterator();
212  IndexList::iterator ListI = endIdx.listEntry()->getIterator();
214  bool pastStart = false;
215  while (ListI != ListB || MBBI != Begin || (includeStart && !pastStart)) {
216  assert(ListI->getIndex() >= startIdx.getIndex() &&
217  (includeStart || !pastStart) &&
218  "Decremented past the beginning of region to repair.");
219 
220  MachineInstr *SlotMI = ListI->getInstr();
221  MachineInstr *MI = (MBBI != MBB->end() && !pastStart) ? &*MBBI : nullptr;
222  bool MBBIAtBegin = MBBI == Begin && (!includeStart || pastStart);
223 
224  if (SlotMI == MI && !MBBIAtBegin) {
225  --ListI;
226  if (MBBI != Begin)
227  --MBBI;
228  else
229  pastStart = true;
230  } else if (MI && mi2iMap.find(MI) == mi2iMap.end()) {
231  if (MBBI != Begin)
232  --MBBI;
233  else
234  pastStart = true;
235  } else {
236  --ListI;
237  if (SlotMI)
239  }
240  }
241 
242  // In theory this could be combined with the previous loop, but it is tricky
243  // to update the IndexList while we are iterating it.
244  for (MachineBasicBlock::iterator I = End; I != Begin;) {
245  --I;
246  MachineInstr &MI = *I;
247  if (!MI.isDebugValue() && mi2iMap.find(&MI) == mi2iMap.end())
249  }
250 }
251 
252 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
254  for (IndexList::const_iterator itr = indexList.begin();
255  itr != indexList.end(); ++itr) {
256  dbgs() << itr->getIndex() << " ";
257 
258  if (itr->getInstr()) {
259  dbgs() << *itr->getInstr();
260  } else {
261  dbgs() << "\n";
262  }
263  }
264 
265  for (unsigned i = 0, e = MBBRanges.size(); i != e; ++i)
266  dbgs() << "%bb." << i << "\t[" << MBBRanges[i].first << ';'
267  << MBBRanges[i].second << ")\n";
268 }
269 #endif
270 
271 // Print a SlotIndex to a raw_ostream.
272 void SlotIndex::print(raw_ostream &os) const {
273  if (isValid())
274  os << listEntry()->getIndex() << "Berd"[getSlot()];
275  else
276  os << "invalid";
277 }
278 
279 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
280 // Dump a SlotIndex to stderr.
282  print(dbgs());
283  dbgs() << "\n";
284 }
285 #endif
286 
void push_back(const T &Elt)
Definition: SmallVector.h:212
void renumberIndexes()
Renumber the index list, providing space for new instructions.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:449
void removeSingleMachineInstrFromMaps(MachineInstr &MI)
Removes a single machine instruction MI from the mapping.
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID&#39;s allocated.
bool isBundledWithPred() const
Return true if this instruction is part of a bundle, and it is not the first instruction in the bundl...
Definition: MachineInstr.h:250
unsigned size() const
void removeMachineInstrFromMaps(MachineInstr &MI)
Removes machine instruction (bundle) MI from the mapping.
STATISTIC(NumFunctions, "Total number of functions")
void reserve(size_type N)
Definition: SmallVector.h:378
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:191
#define DEBUG_TYPE
Definition: SlotIndexes.cpp:18
void Reset()
Deallocate all but the current slab and reset the current pointer to the beginning of it...
Definition: Allocator.h:197
bool isBundledWithSucc() const
Return true if this instruction is part of a bundle, and it is not the last instruction in the bundle...
Definition: MachineInstr.h:254
SlotIndex getInstructionIndex(const MachineInstr &MI) const
Returns the base index for the given instruction.
Definition: SlotIndexes.h:414
SlotIndexes pass.
Definition: SlotIndexes.h:331
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:146
void dump() const
Dump this index to stderr.
SlotIndex insertMachineInstrInMaps(MachineInstr &MI, bool Late=false)
Insert the given machine instruction into the mapping.
Definition: SlotIndexes.h:577
MachineInstr * getInstr() const
Definition: SlotIndexes.h:54
bool erase(const KeyT &Val)
Definition: DenseMap.h:268
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:116
bool hasIndex(const MachineInstr &instr) const
Returns true if the given machine instr is mapped to an index, otherwise returns false.
Definition: SlotIndexes.h:409
SlotIndex getMBBStartIdx(unsigned Num) const
Returns the first index in the given basic block number.
Definition: SlotIndexes.h:487
Represent the analysis usage information of a pass.
std::pair< SlotIndex, MachineBasicBlock * > IdxMBBPair
Definition: SlotIndexes.h:312
static const unsigned End
self_iterator getIterator()
Definition: ilist_node.h:82
void setInstr(MachineInstr *mi)
Definition: SlotIndexes.h:55
void dump() const
Dump the indexes.
SlotIndex getMBBEndIdx(unsigned Num) const
Returns the last index in the given basic block number.
Definition: SlotIndexes.h:497
Iterator for intrusive lists based on ilist_node.
bool isDebugValue() const
Definition: MachineInstr.h:819
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void push_back(pointer val)
Definition: ilist.h:326
void repairIndexesInRange(MachineBasicBlock *MBB, MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End)
Repair indexes after adding and removing instructions.
Representation of each machine instruction.
Definition: MachineInstr.h:60
static char ID
Definition: SlotIndexes.h:369
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:120
This class represents an entry in the slot index list held in the SlotIndexes pass.
Definition: SlotIndexes.h:47
bool runOnMachineFunction(MachineFunction &fn) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
Definition: SlotIndexes.cpp:40
void clear()
Definition: ilist.h:322
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
Definition: SlotIndexes.cpp:32
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
#define I(x, y, z)
Definition: MD5.cpp:58
iterator end()
Definition: DenseMap.h:79
virtual void print(raw_ostream &OS, const Module *M) const
print - Print out the internal state of the pass.
Definition: Pass.cpp:123
INITIALIZE_PASS(SlotIndexes, DEBUG_TYPE, "Slot index numbering", false, false) STATISTIC(NumLocalRenum
LLVM_NODISCARD bool empty() const
Definition: DenseMap.h:93
The default distance between instructions as returned by distance().
Definition: SlotIndexes.h:138
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
#define DEBUG(X)
Definition: Debug.h:118
IRTranslator LLVM IR MI
void print(raw_ostream &os) const
Print this index to the given raw_ostream.
void sort(Policy policy, RandomAccessIterator Start, RandomAccessIterator End, const Comparator &Comp=Comparator())
Definition: Parallel.h:199
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:84
Number of local renumberings
Definition: SlotIndexes.cpp:24