LLVM  6.0.0svn
SSAUpdaterImpl.h
Go to the documentation of this file.
1 //===-- SSAUpdaterImpl.h - SSA Updater Implementation -----------*- C++ -*-===//
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 provides a template that implements the core algorithm for the
11 // SSAUpdater and MachineSSAUpdater.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H
16 #define LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H
17 
18 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/IR/Instructions.h"
21 #include "llvm/IR/ValueHandle.h"
22 #include "llvm/Support/Allocator.h"
23 #include "llvm/Support/Debug.h"
24 
25 #define DEBUG_TYPE "ssaupdater"
26 
27 namespace llvm {
28 
29 class CastInst;
30 class PHINode;
31 template<typename T> class SSAUpdaterTraits;
32 
33 template<typename UpdaterT>
35 private:
36  UpdaterT *Updater;
37 
39  typedef typename Traits::BlkT BlkT;
40  typedef typename Traits::ValT ValT;
41  typedef typename Traits::PhiT PhiT;
42 
43  /// BBInfo - Per-basic block information used internally by SSAUpdaterImpl.
44  /// The predecessors of each block are cached here since pred_iterator is
45  /// slow and we need to iterate over the blocks at least a few times.
46  class BBInfo {
47  public:
48  BlkT *BB; // Back-pointer to the corresponding block.
49  ValT AvailableVal; // Value to use in this block.
50  BBInfo *DefBB; // Block that defines the available value.
51  int BlkNum; // Postorder number.
52  BBInfo *IDom; // Immediate dominator.
53  unsigned NumPreds; // Number of predecessor blocks.
54  BBInfo **Preds; // Array[NumPreds] of predecessor blocks.
55  PhiT *PHITag; // Marker for existing PHIs that match.
56 
57  BBInfo(BlkT *ThisBB, ValT V)
58  : BB(ThisBB), AvailableVal(V), DefBB(V ? this : nullptr), BlkNum(0),
59  IDom(nullptr), NumPreds(0), Preds(nullptr), PHITag(nullptr) {}
60  };
61 
63  AvailableValsTy *AvailableVals;
64 
65  SmallVectorImpl<PhiT*> *InsertedPHIs;
66 
69  BBMapTy BBMap;
71 
72 public:
73  explicit SSAUpdaterImpl(UpdaterT *U, AvailableValsTy *A,
75  Updater(U), AvailableVals(A), InsertedPHIs(Ins) { }
76 
77  /// GetValue - Check to see if AvailableVals has an entry for the specified
78  /// BB and if so, return it. If not, construct SSA form by first
79  /// calculating the required placement of PHIs and then inserting new PHIs
80  /// where needed.
81  ValT GetValue(BlkT *BB) {
82  SmallVector<BBInfo*, 100> BlockList;
83  BBInfo *PseudoEntry = BuildBlockList(BB, &BlockList);
84 
85  // Special case: bail out if BB is unreachable.
86  if (BlockList.size() == 0) {
87  ValT V = Traits::GetUndefVal(BB, Updater);
88  (*AvailableVals)[BB] = V;
89  return V;
90  }
91 
92  FindDominators(&BlockList, PseudoEntry);
93  FindPHIPlacement(&BlockList);
94  FindAvailableVals(&BlockList);
95 
96  return BBMap[BB]->DefBB->AvailableVal;
97  }
98 
99  /// BuildBlockList - Starting from the specified basic block, traverse back
100  /// through its predecessors until reaching blocks with known values.
101  /// Create BBInfo structures for the blocks and append them to the block
102  /// list.
103  BBInfo *BuildBlockList(BlkT *BB, BlockListTy *BlockList) {
104  SmallVector<BBInfo*, 10> RootList;
105  SmallVector<BBInfo*, 64> WorkList;
106 
107  BBInfo *Info = new (Allocator) BBInfo(BB, 0);
108  BBMap[BB] = Info;
109  WorkList.push_back(Info);
110 
111  // Search backward from BB, creating BBInfos along the way and stopping
112  // when reaching blocks that define the value. Record those defining
113  // blocks on the RootList.
115  while (!WorkList.empty()) {
116  Info = WorkList.pop_back_val();
117  Preds.clear();
118  Traits::FindPredecessorBlocks(Info->BB, &Preds);
119  Info->NumPreds = Preds.size();
120  if (Info->NumPreds == 0)
121  Info->Preds = nullptr;
122  else
123  Info->Preds = static_cast<BBInfo **>(Allocator.Allocate(
124  Info->NumPreds * sizeof(BBInfo *), alignof(BBInfo *)));
125 
126  for (unsigned p = 0; p != Info->NumPreds; ++p) {
127  BlkT *Pred = Preds[p];
128  // Check if BBMap already has a BBInfo for the predecessor block.
129  typename BBMapTy::value_type &BBMapBucket =
130  BBMap.FindAndConstruct(Pred);
131  if (BBMapBucket.second) {
132  Info->Preds[p] = BBMapBucket.second;
133  continue;
134  }
135 
136  // Create a new BBInfo for the predecessor.
137  ValT PredVal = AvailableVals->lookup(Pred);
138  BBInfo *PredInfo = new (Allocator) BBInfo(Pred, PredVal);
139  BBMapBucket.second = PredInfo;
140  Info->Preds[p] = PredInfo;
141 
142  if (PredInfo->AvailableVal) {
143  RootList.push_back(PredInfo);
144  continue;
145  }
146  WorkList.push_back(PredInfo);
147  }
148  }
149 
150  // Now that we know what blocks are backwards-reachable from the starting
151  // block, do a forward depth-first traversal to assign postorder numbers
152  // to those blocks.
153  BBInfo *PseudoEntry = new (Allocator) BBInfo(nullptr, 0);
154  unsigned BlkNum = 1;
155 
156  // Initialize the worklist with the roots from the backward traversal.
157  while (!RootList.empty()) {
158  Info = RootList.pop_back_val();
159  Info->IDom = PseudoEntry;
160  Info->BlkNum = -1;
161  WorkList.push_back(Info);
162  }
163 
164  while (!WorkList.empty()) {
165  Info = WorkList.back();
166 
167  if (Info->BlkNum == -2) {
168  // All the successors have been handled; assign the postorder number.
169  Info->BlkNum = BlkNum++;
170  // If not a root, put it on the BlockList.
171  if (!Info->AvailableVal)
172  BlockList->push_back(Info);
173  WorkList.pop_back();
174  continue;
175  }
176 
177  // Leave this entry on the worklist, but set its BlkNum to mark that its
178  // successors have been put on the worklist. When it returns to the top
179  // the list, after handling its successors, it will be assigned a
180  // number.
181  Info->BlkNum = -2;
182 
183  // Add unvisited successors to the work list.
184  for (typename Traits::BlkSucc_iterator SI =
185  Traits::BlkSucc_begin(Info->BB),
186  E = Traits::BlkSucc_end(Info->BB); SI != E; ++SI) {
187  BBInfo *SuccInfo = BBMap[*SI];
188  if (!SuccInfo || SuccInfo->BlkNum)
189  continue;
190  SuccInfo->BlkNum = -1;
191  WorkList.push_back(SuccInfo);
192  }
193  }
194  PseudoEntry->BlkNum = BlkNum;
195  return PseudoEntry;
196  }
197 
198  /// IntersectDominators - This is the dataflow lattice "meet" operation for
199  /// finding dominators. Given two basic blocks, it walks up the dominator
200  /// tree until it finds a common dominator of both. It uses the postorder
201  /// number of the blocks to determine how to do that.
202  BBInfo *IntersectDominators(BBInfo *Blk1, BBInfo *Blk2) {
203  while (Blk1 != Blk2) {
204  while (Blk1->BlkNum < Blk2->BlkNum) {
205  Blk1 = Blk1->IDom;
206  if (!Blk1)
207  return Blk2;
208  }
209  while (Blk2->BlkNum < Blk1->BlkNum) {
210  Blk2 = Blk2->IDom;
211  if (!Blk2)
212  return Blk1;
213  }
214  }
215  return Blk1;
216  }
217 
218  /// FindDominators - Calculate the dominator tree for the subset of the CFG
219  /// corresponding to the basic blocks on the BlockList. This uses the
220  /// algorithm from: "A Simple, Fast Dominance Algorithm" by Cooper, Harvey
221  /// and Kennedy, published in Software--Practice and Experience, 2001,
222  /// 4:1-10. Because the CFG subset does not include any edges leading into
223  /// blocks that define the value, the results are not the usual dominator
224  /// tree. The CFG subset has a single pseudo-entry node with edges to a set
225  /// of root nodes for blocks that define the value. The dominators for this
226  /// subset CFG are not the standard dominators but they are adequate for
227  /// placing PHIs within the subset CFG.
228  void FindDominators(BlockListTy *BlockList, BBInfo *PseudoEntry) {
229  bool Changed;
230  do {
231  Changed = false;
232  // Iterate over the list in reverse order, i.e., forward on CFG edges.
233  for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
234  E = BlockList->rend(); I != E; ++I) {
235  BBInfo *Info = *I;
236  BBInfo *NewIDom = nullptr;
237 
238  // Iterate through the block's predecessors.
239  for (unsigned p = 0; p != Info->NumPreds; ++p) {
240  BBInfo *Pred = Info->Preds[p];
241 
242  // Treat an unreachable predecessor as a definition with 'undef'.
243  if (Pred->BlkNum == 0) {
244  Pred->AvailableVal = Traits::GetUndefVal(Pred->BB, Updater);
245  (*AvailableVals)[Pred->BB] = Pred->AvailableVal;
246  Pred->DefBB = Pred;
247  Pred->BlkNum = PseudoEntry->BlkNum;
248  PseudoEntry->BlkNum++;
249  }
250 
251  if (!NewIDom)
252  NewIDom = Pred;
253  else
254  NewIDom = IntersectDominators(NewIDom, Pred);
255  }
256 
257  // Check if the IDom value has changed.
258  if (NewIDom && NewIDom != Info->IDom) {
259  Info->IDom = NewIDom;
260  Changed = true;
261  }
262  }
263  } while (Changed);
264  }
265 
266  /// IsDefInDomFrontier - Search up the dominator tree from Pred to IDom for
267  /// any blocks containing definitions of the value. If one is found, then
268  /// the successor of Pred is in the dominance frontier for the definition,
269  /// and this function returns true.
270  bool IsDefInDomFrontier(const BBInfo *Pred, const BBInfo *IDom) {
271  for (; Pred != IDom; Pred = Pred->IDom) {
272  if (Pred->DefBB == Pred)
273  return true;
274  }
275  return false;
276  }
277 
278  /// FindPHIPlacement - PHIs are needed in the iterated dominance frontiers
279  /// of the known definitions. Iteratively add PHIs in the dom frontiers
280  /// until nothing changes. Along the way, keep track of the nearest
281  /// dominating definitions for non-PHI blocks.
282  void FindPHIPlacement(BlockListTy *BlockList) {
283  bool Changed;
284  do {
285  Changed = false;
286  // Iterate over the list in reverse order, i.e., forward on CFG edges.
287  for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
288  E = BlockList->rend(); I != E; ++I) {
289  BBInfo *Info = *I;
290 
291  // If this block already needs a PHI, there is nothing to do here.
292  if (Info->DefBB == Info)
293  continue;
294 
295  // Default to use the same def as the immediate dominator.
296  BBInfo *NewDefBB = Info->IDom->DefBB;
297  for (unsigned p = 0; p != Info->NumPreds; ++p) {
298  if (IsDefInDomFrontier(Info->Preds[p], Info->IDom)) {
299  // Need a PHI here.
300  NewDefBB = Info;
301  break;
302  }
303  }
304 
305  // Check if anything changed.
306  if (NewDefBB != Info->DefBB) {
307  Info->DefBB = NewDefBB;
308  Changed = true;
309  }
310  }
311  } while (Changed);
312  }
313 
314  /// FindAvailableVal - If this block requires a PHI, first check if an
315  /// existing PHI matches the PHI placement and reaching definitions computed
316  /// earlier, and if not, create a new PHI. Visit all the block's
317  /// predecessors to calculate the available value for each one and fill in
318  /// the incoming values for a new PHI.
319  void FindAvailableVals(BlockListTy *BlockList) {
320  // Go through the worklist in forward order (i.e., backward through the CFG)
321  // and check if existing PHIs can be used. If not, create empty PHIs where
322  // they are needed.
323  for (typename BlockListTy::iterator I = BlockList->begin(),
324  E = BlockList->end(); I != E; ++I) {
325  BBInfo *Info = *I;
326  // Check if there needs to be a PHI in BB.
327  if (Info->DefBB != Info)
328  continue;
329 
330  // Look for an existing PHI.
331  FindExistingPHI(Info->BB, BlockList);
332  if (Info->AvailableVal)
333  continue;
334 
335  ValT PHI = Traits::CreateEmptyPHI(Info->BB, Info->NumPreds, Updater);
336  Info->AvailableVal = PHI;
337  (*AvailableVals)[Info->BB] = PHI;
338  }
339 
340  // Now go back through the worklist in reverse order to fill in the
341  // arguments for any new PHIs added in the forward traversal.
342  for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
343  E = BlockList->rend(); I != E; ++I) {
344  BBInfo *Info = *I;
345 
346  if (Info->DefBB != Info) {
347  // Record the available value at join nodes to speed up subsequent
348  // uses of this SSAUpdater for the same value.
349  if (Info->NumPreds > 1)
350  (*AvailableVals)[Info->BB] = Info->DefBB->AvailableVal;
351  continue;
352  }
353 
354  // Check if this block contains a newly added PHI.
355  PhiT *PHI = Traits::ValueIsNewPHI(Info->AvailableVal, Updater);
356  if (!PHI)
357  continue;
358 
359  // Iterate through the block's predecessors.
360  for (unsigned p = 0; p != Info->NumPreds; ++p) {
361  BBInfo *PredInfo = Info->Preds[p];
362  BlkT *Pred = PredInfo->BB;
363  // Skip to the nearest preceding definition.
364  if (PredInfo->DefBB != PredInfo)
365  PredInfo = PredInfo->DefBB;
366  Traits::AddPHIOperand(PHI, PredInfo->AvailableVal, Pred);
367  }
368 
369  DEBUG(dbgs() << " Inserted PHI: " << *PHI << "\n");
370 
371  // If the client wants to know about all new instructions, tell it.
372  if (InsertedPHIs) InsertedPHIs->push_back(PHI);
373  }
374  }
375 
376  /// FindExistingPHI - Look through the PHI nodes in a block to see if any of
377  /// them match what is needed.
378  void FindExistingPHI(BlkT *BB, BlockListTy *BlockList) {
379  for (typename BlkT::iterator BBI = BB->begin(), BBE = BB->end();
380  BBI != BBE; ++BBI) {
381  PhiT *SomePHI = Traits::InstrIsPHI(&*BBI);
382  if (!SomePHI)
383  break;
384  if (CheckIfPHIMatches(SomePHI)) {
385  RecordMatchingPHIs(BlockList);
386  break;
387  }
388  // Match failed: clear all the PHITag values.
389  for (typename BlockListTy::iterator I = BlockList->begin(),
390  E = BlockList->end(); I != E; ++I)
391  (*I)->PHITag = nullptr;
392  }
393  }
394 
395  /// CheckIfPHIMatches - Check if a PHI node matches the placement and values
396  /// in the BBMap.
397  bool CheckIfPHIMatches(PhiT *PHI) {
398  SmallVector<PhiT*, 20> WorkList;
399  WorkList.push_back(PHI);
400 
401  // Mark that the block containing this PHI has been visited.
402  BBMap[PHI->getParent()]->PHITag = PHI;
403 
404  while (!WorkList.empty()) {
405  PHI = WorkList.pop_back_val();
406 
407  // Iterate through the PHI's incoming values.
408  for (typename Traits::PHI_iterator I = Traits::PHI_begin(PHI),
409  E = Traits::PHI_end(PHI); I != E; ++I) {
410  ValT IncomingVal = I.getIncomingValue();
411  BBInfo *PredInfo = BBMap[I.getIncomingBlock()];
412  // Skip to the nearest preceding definition.
413  if (PredInfo->DefBB != PredInfo)
414  PredInfo = PredInfo->DefBB;
415 
416  // Check if it matches the expected value.
417  if (PredInfo->AvailableVal) {
418  if (IncomingVal == PredInfo->AvailableVal)
419  continue;
420  return false;
421  }
422 
423  // Check if the value is a PHI in the correct block.
424  PhiT *IncomingPHIVal = Traits::ValueIsPHI(IncomingVal, Updater);
425  if (!IncomingPHIVal || IncomingPHIVal->getParent() != PredInfo->BB)
426  return false;
427 
428  // If this block has already been visited, check if this PHI matches.
429  if (PredInfo->PHITag) {
430  if (IncomingPHIVal == PredInfo->PHITag)
431  continue;
432  return false;
433  }
434  PredInfo->PHITag = IncomingPHIVal;
435 
436  WorkList.push_back(IncomingPHIVal);
437  }
438  }
439  return true;
440  }
441 
442  /// RecordMatchingPHIs - For each PHI node that matches, record it in both
443  /// the BBMap and the AvailableVals mapping.
444  void RecordMatchingPHIs(BlockListTy *BlockList) {
445  for (typename BlockListTy::iterator I = BlockList->begin(),
446  E = BlockList->end(); I != E; ++I)
447  if (PhiT *PHI = (*I)->PHITag) {
448  BlkT *BB = PHI->getParent();
449  ValT PHIVal = Traits::GetPHIValue(PHI);
450  (*AvailableVals)[BB] = PHIVal;
451  BBMap[BB]->AvailableVal = PHIVal;
452  }
453  }
454 };
455 
456 } // end llvm namespace
457 
458 #undef DEBUG_TYPE // "ssaupdater"
459 
460 #endif // LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H
SSAUpdaterImpl(UpdaterT *U, AvailableValsTy *A, SmallVectorImpl< PhiT *> *Ins)
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
ValT GetValue(BlkT *BB)
GetValue - Check to see if AvailableVals has an entry for the specified BB and if so...
void FindPHIPlacement(BlockListTy *BlockList)
FindPHIPlacement - PHIs are needed in the iterated dominance frontiers of the known definitions...
void FindExistingPHI(BlkT *BB, BlockListTy *BlockList)
FindExistingPHI - Look through the PHI nodes in a block to see if any of them match what is needed...
This file defines the MallocAllocator and BumpPtrAllocator interfaces.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
bool CheckIfPHIMatches(PhiT *PHI)
CheckIfPHIMatches - Check if a PHI node matches the placement and values in the BBMap.
value_type & FindAndConstruct(const KeyT &Key)
Definition: DenseMap.h:266
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:138
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:116
LLVM_ATTRIBUTE_RETURNS_NONNULL LLVM_ATTRIBUTE_RETURNS_NOALIAS void * Allocate(size_t Size, size_t Alignment)
Allocate space at the specified alignment.
Definition: Allocator.h:212
void FindDominators(BlockListTy *BlockList, BBInfo *PseudoEntry)
FindDominators - Calculate the dominator tree for the subset of the CFG corresponding to the basic bl...
#define A
Definition: LargeTest.cpp:12
std::reverse_iterator< iterator > reverse_iterator
Definition: SmallVector.h:107
bool IsDefInDomFrontier(const BBInfo *Pred, const BBInfo *IDom)
IsDefInDomFrontier - Search up the dominator tree from Pred to IDom for any blocks containing definit...
void RecordMatchingPHIs(BlockListTy *BlockList)
RecordMatchingPHIs - For each PHI node that matches, record it in both the BBMap and the AvailableVal...
Basic Register Allocator
#define E
Definition: LargeTest.cpp:27
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:385
void FindAvailableVals(BlockListTy *BlockList)
FindAvailableVal - If this block requires a PHI, first check if an existing PHI matches the PHI place...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
typename SuperClass::iterator iterator
Definition: SmallVector.h:328
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:120
BBInfo * IntersectDominators(BBInfo *Blk1, BBInfo *Blk2)
IntersectDominators - This is the dataflow lattice "meet" operation for finding dominators.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
#define I(x, y, z)
Definition: MD5.cpp:58
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:166
BBInfo * BuildBlockList(BlkT *BB, BlockListTy *BlockList)
BuildBlockList - Starting from the specified basic block, traverse back through its predecessors unti...
#define DEBUG(X)
Definition: Debug.h:118