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