LLVM  8.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 to speed up subsequent uses of this
361  // SSAUpdater for the same value.
362  (*AvailableVals)[Info->BB] = Info->DefBB->AvailableVal;
363  continue;
364  }
365 
366  // Check if this block contains a newly added PHI.
367  PhiT *PHI = Traits::ValueIsNewPHI(Info->AvailableVal, Updater);
368  if (!PHI)
369  continue;
370 
371  // Iterate through the block's predecessors.
372  for (unsigned p = 0; p != Info->NumPreds; ++p) {
373  BBInfo *PredInfo = Info->Preds[p];
374  BlkT *Pred = PredInfo->BB;
375  // Skip to the nearest preceding definition.
376  if (PredInfo->DefBB != PredInfo)
377  PredInfo = PredInfo->DefBB;
378  Traits::AddPHIOperand(PHI, PredInfo->AvailableVal, Pred);
379  }
380 
381  LLVM_DEBUG(dbgs() << " Inserted PHI: " << *PHI << "\n");
382 
383  // If the client wants to know about all new instructions, tell it.
384  if (InsertedPHIs) InsertedPHIs->push_back(PHI);
385  }
386  }
387 
388  /// FindExistingPHI - Look through the PHI nodes in a block to see if any of
389  /// them match what is needed.
390  void FindExistingPHI(BlkT *BB, BlockListTy *BlockList) {
391  for (auto &SomePHI : BB->phis()) {
392  if (CheckIfPHIMatches(&SomePHI)) {
393  RecordMatchingPHIs(BlockList);
394  break;
395  }
396  // Match failed: clear all the PHITag values.
397  for (typename BlockListTy::iterator I = BlockList->begin(),
398  E = BlockList->end(); I != E; ++I)
399  (*I)->PHITag = nullptr;
400  }
401  }
402 
403  /// CheckIfPHIMatches - Check if a PHI node matches the placement and values
404  /// in the BBMap.
405  bool CheckIfPHIMatches(PhiT *PHI) {
406  SmallVector<PhiT *, 20> WorkList;
407  WorkList.push_back(PHI);
408 
409  // Mark that the block containing this PHI has been visited.
410  BBMap[PHI->getParent()]->PHITag = PHI;
411 
412  while (!WorkList.empty()) {
413  PHI = WorkList.pop_back_val();
414 
415  // Iterate through the PHI's incoming values.
416  for (typename Traits::PHI_iterator I = Traits::PHI_begin(PHI),
417  E = Traits::PHI_end(PHI); I != E; ++I) {
418  ValT IncomingVal = I.getIncomingValue();
419  BBInfo *PredInfo = BBMap[I.getIncomingBlock()];
420  // Skip to the nearest preceding definition.
421  if (PredInfo->DefBB != PredInfo)
422  PredInfo = PredInfo->DefBB;
423 
424  // Check if it matches the expected value.
425  if (PredInfo->AvailableVal) {
426  if (IncomingVal == PredInfo->AvailableVal)
427  continue;
428  return false;
429  }
430 
431  // Check if the value is a PHI in the correct block.
432  PhiT *IncomingPHIVal = Traits::ValueIsPHI(IncomingVal, Updater);
433  if (!IncomingPHIVal || IncomingPHIVal->getParent() != PredInfo->BB)
434  return false;
435 
436  // If this block has already been visited, check if this PHI matches.
437  if (PredInfo->PHITag) {
438  if (IncomingPHIVal == PredInfo->PHITag)
439  continue;
440  return false;
441  }
442  PredInfo->PHITag = IncomingPHIVal;
443 
444  WorkList.push_back(IncomingPHIVal);
445  }
446  }
447  return true;
448  }
449 
450  /// RecordMatchingPHIs - For each PHI node that matches, record it in both
451  /// the BBMap and the AvailableVals mapping.
452  void RecordMatchingPHIs(BlockListTy *BlockList) {
453  for (typename BlockListTy::iterator I = BlockList->begin(),
454  E = BlockList->end(); I != E; ++I)
455  if (PhiT *PHI = (*I)->PHITag) {
456  BlkT *BB = PHI->getParent();
457  ValT PHIVal = Traits::GetPHIValue(PHI);
458  (*AvailableVals)[BB] = PHIVal;
459  BBMap[BB]->AvailableVal = PHIVal;
460  }
461  }
462 };
463 
464 } // end namespace llvm
465 
466 #undef DEBUG_TYPE // "ssaupdater"
467 
468 #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
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:292
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:141
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:129
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:215
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:120
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...
size_t size() const
Definition: SmallVector.h:53
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:847
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:381
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:133
typename SuperClass::iterator iterator
Definition: SmallVector.h:327
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:133
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:56
#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:186
BBInfo * BuildBlockList(BlkT *BB, BlockListTy *BlockList)
BuildBlockList - Starting from the specified basic block, traverse back through its predecessors unti...
#define LLVM_DEBUG(X)
Definition: Debug.h:123