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