LLVM  9.0.0svn
SSAUpdaterBulk.cpp
Go to the documentation of this file.
1 //===- SSAUpdaterBulk.cpp - Unstructured SSA Update Tool ------------------===//
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 implements the SSAUpdaterBulk class.
10 //
11 //===----------------------------------------------------------------------===//
12 
15 #include "llvm/IR/BasicBlock.h"
16 #include "llvm/IR/Dominators.h"
17 #include "llvm/IR/IRBuilder.h"
18 #include "llvm/IR/Instructions.h"
19 #include "llvm/IR/Use.h"
20 #include "llvm/IR/Value.h"
21 
22 using namespace llvm;
23 
24 #define DEBUG_TYPE "ssaupdaterbulk"
25 
26 /// Helper function for finding a block which should have a value for the given
27 /// user. For PHI-nodes this block is the corresponding predecessor, for other
28 /// instructions it's their parent block.
29 static BasicBlock *getUserBB(Use *U) {
30  auto *User = cast<Instruction>(U->getUser());
31 
32  if (auto *UserPN = dyn_cast<PHINode>(User))
33  return UserPN->getIncomingBlock(*U);
34  else
35  return User->getParent();
36 }
37 
38 /// Add a new variable to the SSA rewriter. This needs to be called before
39 /// AddAvailableValue or AddUse calls.
41  unsigned Var = Rewrites.size();
42  LLVM_DEBUG(dbgs() << "SSAUpdater: Var=" << Var << ": initialized with Ty = "
43  << *Ty << ", Name = " << Name << "\n");
44  RewriteInfo RI(Name, Ty);
45  Rewrites.push_back(RI);
46  return Var;
47 }
48 
49 /// Indicate that a rewritten value is available in the specified block with the
50 /// specified value.
51 void SSAUpdaterBulk::AddAvailableValue(unsigned Var, BasicBlock *BB, Value *V) {
52  assert(Var < Rewrites.size() && "Variable not found!");
53  LLVM_DEBUG(dbgs() << "SSAUpdater: Var=" << Var
54  << ": added new available value" << *V << " in "
55  << BB->getName() << "\n");
56  Rewrites[Var].Defines[BB] = V;
57 }
58 
59 /// Record a use of the symbolic value. This use will be updated with a
60 /// rewritten value when RewriteAllUses is called.
61 void SSAUpdaterBulk::AddUse(unsigned Var, Use *U) {
62  assert(Var < Rewrites.size() && "Variable not found!");
63  LLVM_DEBUG(dbgs() << "SSAUpdater: Var=" << Var << ": added a use" << *U->get()
64  << " in " << getUserBB(U)->getName() << "\n");
65  Rewrites[Var].Uses.push_back(U);
66 }
67 
68 /// Return true if the SSAUpdater already has a value for the specified variable
69 /// in the specified block.
71  return (Var < Rewrites.size()) ? Rewrites[Var].Defines.count(BB) : false;
72 }
73 
74 // Compute value at the given block BB. We either should already know it, or we
75 // should be able to recursively reach it going up dominator tree.
76 Value *SSAUpdaterBulk::computeValueAt(BasicBlock *BB, RewriteInfo &R,
77  DominatorTree *DT) {
78  if (!R.Defines.count(BB)) {
79  if (DT->isReachableFromEntry(BB) && PredCache.get(BB).size()) {
80  BasicBlock *IDom = DT->getNode(BB)->getIDom()->getBlock();
81  Value *V = computeValueAt(IDom, R, DT);
82  R.Defines[BB] = V;
83  } else
84  R.Defines[BB] = UndefValue::get(R.Ty);
85  }
86  return R.Defines[BB];
87 }
88 
89 /// Given sets of UsingBlocks and DefBlocks, compute the set of LiveInBlocks.
90 /// This is basically a subgraph limited by DefBlocks and UsingBlocks.
91 static void
93  const SmallPtrSetImpl<BasicBlock *> &DefBlocks,
94  SmallPtrSetImpl<BasicBlock *> &LiveInBlocks,
95  PredIteratorCache &PredCache) {
96  // To determine liveness, we must iterate through the predecessors of blocks
97  // where the def is live. Blocks are added to the worklist if we need to
98  // check their predecessors. Start with all the using blocks.
99  SmallVector<BasicBlock *, 64> LiveInBlockWorklist(UsingBlocks.begin(),
100  UsingBlocks.end());
101 
102  // Now that we have a set of blocks where the phi is live-in, recursively add
103  // their predecessors until we find the full region the value is live.
104  while (!LiveInBlockWorklist.empty()) {
105  BasicBlock *BB = LiveInBlockWorklist.pop_back_val();
106 
107  // The block really is live in here, insert it into the set. If already in
108  // the set, then it has already been processed.
109  if (!LiveInBlocks.insert(BB).second)
110  continue;
111 
112  // Since the value is live into BB, it is either defined in a predecessor or
113  // live into it to. Add the preds to the worklist unless they are a
114  // defining block.
115  for (BasicBlock *P : PredCache.get(BB)) {
116  // The value is not live into a predecessor if it defines the value.
117  if (DefBlocks.count(P))
118  continue;
119 
120  // Otherwise it is, add to the worklist.
121  LiveInBlockWorklist.push_back(P);
122  }
123  }
124 }
125 
126 /// Perform all the necessary updates, including new PHI-nodes insertion and the
127 /// requested uses update.
129  SmallVectorImpl<PHINode *> *InsertedPHIs) {
130  for (auto &R : Rewrites) {
131  // Compute locations for new phi-nodes.
132  // For that we need to initialize DefBlocks from definitions in R.Defines,
133  // UsingBlocks from uses in R.Uses, then compute LiveInBlocks, and then use
134  // this set for computing iterated dominance frontier (IDF).
135  // The IDF blocks are the blocks where we need to insert new phi-nodes.
136  ForwardIDFCalculator IDF(*DT);
137  LLVM_DEBUG(dbgs() << "SSAUpdater: rewriting " << R.Uses.size()
138  << " use(s)\n");
139 
141  for (auto &Def : R.Defines)
142  DefBlocks.insert(Def.first);
143  IDF.setDefiningBlocks(DefBlocks);
144 
145  SmallPtrSet<BasicBlock *, 2> UsingBlocks;
146  for (Use *U : R.Uses)
147  UsingBlocks.insert(getUserBB(U));
148 
150  SmallPtrSet<BasicBlock *, 32> LiveInBlocks;
151  ComputeLiveInBlocks(UsingBlocks, DefBlocks, LiveInBlocks, PredCache);
152  IDF.resetLiveInBlocks();
153  IDF.setLiveInBlocks(LiveInBlocks);
154  IDF.calculate(IDFBlocks);
155 
156  // We've computed IDF, now insert new phi-nodes there.
157  SmallVector<PHINode *, 4> InsertedPHIsForVar;
158  for (auto *FrontierBB : IDFBlocks) {
159  IRBuilder<> B(FrontierBB, FrontierBB->begin());
160  PHINode *PN = B.CreatePHI(R.Ty, 0, R.Name);
161  R.Defines[FrontierBB] = PN;
162  InsertedPHIsForVar.push_back(PN);
163  if (InsertedPHIs)
164  InsertedPHIs->push_back(PN);
165  }
166 
167  // Fill in arguments of the inserted PHIs.
168  for (auto *PN : InsertedPHIsForVar) {
169  BasicBlock *PBB = PN->getParent();
170  for (BasicBlock *Pred : PredCache.get(PBB))
171  PN->addIncoming(computeValueAt(Pred, R, DT), Pred);
172  }
173 
174  // Rewrite actual uses with the inserted definitions.
175  SmallPtrSet<Use *, 4> ProcessedUses;
176  for (Use *U : R.Uses) {
177  if (!ProcessedUses.insert(U).second)
178  continue;
179  Value *V = computeValueAt(getUserBB(U), R, DT);
180  Value *OldVal = U->get();
181  assert(OldVal && "Invalid use!");
182  // Notify that users of the existing value that it is being replaced.
183  if (OldVal != V && OldVal->hasValueHandle())
185  LLVM_DEBUG(dbgs() << "SSAUpdater: replacing " << *OldVal << " with " << *V
186  << "\n");
187  U->set(V);
188  }
189  }
190 }
This class represents lattice values for constants.
Definition: AllocatorList.h:23
amdgpu Simplify well known AMD library false FunctionCallee Value const Twine & Name
void push_back(const T &Elt)
Definition: SmallVector.h:211
bool hasValueHandle() const
Return true if there is a value handle associated with this value.
Definition: Value.h:485
This defines the Use class.
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:299
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
ArrayRef< BasicBlock * > get(BasicBlock *BB)
unsigned AddVariable(StringRef Name, Type *Ty)
Add a new variable to the SSA rewriter.
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
void setDefiningBlocks(const SmallPtrSetImpl< BasicBlock *> &Blocks)
Give the IDF calculator the set of blocks in which the value is defined.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:742
void AddAvailableValue(unsigned Var, BasicBlock *BB, Value *V)
Indicate that a rewritten value is available in the specified block with the specified value...
PredIteratorCache - This class is an extremely trivial cache for predecessor iterator queries...
static void ValueIsRAUWd(Value *Old, Value *New)
Definition: Value.cpp:889
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
NodeT * getBlock() const
#define P(N)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
static void ComputeLiveInBlocks(const SmallPtrSetImpl< BasicBlock *> &UsingBlocks, const SmallPtrSetImpl< BasicBlock *> &DefBlocks, SmallPtrSetImpl< BasicBlock *> &LiveInBlocks, PredIteratorCache &PredCache)
Given sets of UsingBlocks and DefBlocks, compute the set of LiveInBlocks.
DomTreeNodeBase * getIDom() const
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:370
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:381
void resetLiveInBlocks()
Reset the live-in block set to be empty, and tell the IDF calculator to not use liveness anymore...
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1424
void AddUse(unsigned Var, Use *U)
Record a use of the symbolic value.
size_t size() const
Definition: SmallVector.h:52
Compute iterated dominance frontiers using a linear time algorithm.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
void setLiveInBlocks(const SmallPtrSetImpl< BasicBlock *> &Blocks)
Give the IDF calculator the set of blocks in which the value is live on entry to the block...
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
void calculate(SmallVectorImpl< BasicBlock *> &IDFBlocks)
Calculate iterated dominance frontiers.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:841
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void RewriteAllUses(DominatorTree *DT, SmallVectorImpl< PHINode *> *InsertedPHIs=nullptr)
Perform all the necessary updates, including new PHI-nodes insertion and the requested uses update...
iterator begin() const
Definition: SmallPtrSet.h:396
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
iterator end() const
Definition: SmallPtrSet.h:401
Determine the iterated dominance frontier, given a set of defining blocks, and optionally, a set of live-in blocks.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:72
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
#define LLVM_DEBUG(X)
Definition: Debug.h:122
bool HasValueForBlock(unsigned Var, BasicBlock *BB)
Return true if the SSAUpdater already has a value for the specified variable in the specified block...
static BasicBlock * getUserBB(Use *U)
Helper function for finding a block which should have a value for the given user. ...