LLVM  14.0.0git
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.
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 // Compute value at the given block BB. We either should already know it, or we
69 // should be able to recursively reach it going up dominator tree.
70 Value *SSAUpdaterBulk::computeValueAt(BasicBlock *BB, RewriteInfo &R,
71  DominatorTree *DT) {
72  if (!R.Defines.count(BB)) {
73  if (DT->isReachableFromEntry(BB) && PredCache.get(BB).size()) {
74  BasicBlock *IDom = DT->getNode(BB)->getIDom()->getBlock();
75  Value *V = computeValueAt(IDom, R, DT);
76  R.Defines[BB] = V;
77  } else
78  R.Defines[BB] = UndefValue::get(R.Ty);
79  }
80  return R.Defines[BB];
81 }
82 
83 /// Given sets of UsingBlocks and DefBlocks, compute the set of LiveInBlocks.
84 /// This is basically a subgraph limited by DefBlocks and UsingBlocks.
85 static void
87  const SmallPtrSetImpl<BasicBlock *> &DefBlocks,
88  SmallPtrSetImpl<BasicBlock *> &LiveInBlocks,
89  PredIteratorCache &PredCache) {
90  // To determine liveness, we must iterate through the predecessors of blocks
91  // where the def is live. Blocks are added to the worklist if we need to
92  // check their predecessors. Start with all the using blocks.
93  SmallVector<BasicBlock *, 64> LiveInBlockWorklist(UsingBlocks.begin(),
94  UsingBlocks.end());
95 
96  // Now that we have a set of blocks where the phi is live-in, recursively add
97  // their predecessors until we find the full region the value is live.
98  while (!LiveInBlockWorklist.empty()) {
99  BasicBlock *BB = LiveInBlockWorklist.pop_back_val();
100 
101  // The block really is live in here, insert it into the set. If already in
102  // the set, then it has already been processed.
103  if (!LiveInBlocks.insert(BB).second)
104  continue;
105 
106  // Since the value is live into BB, it is either defined in a predecessor or
107  // live into it to. Add the preds to the worklist unless they are a
108  // defining block.
109  for (BasicBlock *P : PredCache.get(BB)) {
110  // The value is not live into a predecessor if it defines the value.
111  if (DefBlocks.count(P))
112  continue;
113 
114  // Otherwise it is, add to the worklist.
115  LiveInBlockWorklist.push_back(P);
116  }
117  }
118 }
119 
120 /// Perform all the necessary updates, including new PHI-nodes insertion and the
121 /// requested uses update.
123  SmallVectorImpl<PHINode *> *InsertedPHIs) {
124  for (auto &R : Rewrites) {
125  // Compute locations for new phi-nodes.
126  // For that we need to initialize DefBlocks from definitions in R.Defines,
127  // UsingBlocks from uses in R.Uses, then compute LiveInBlocks, and then use
128  // this set for computing iterated dominance frontier (IDF).
129  // The IDF blocks are the blocks where we need to insert new phi-nodes.
130  ForwardIDFCalculator IDF(*DT);
131  LLVM_DEBUG(dbgs() << "SSAUpdater: rewriting " << R.Uses.size()
132  << " use(s)\n");
133 
135  for (auto &Def : R.Defines)
136  DefBlocks.insert(Def.first);
137  IDF.setDefiningBlocks(DefBlocks);
138 
139  SmallPtrSet<BasicBlock *, 2> UsingBlocks;
140  for (Use *U : R.Uses)
141  UsingBlocks.insert(getUserBB(U));
142 
144  SmallPtrSet<BasicBlock *, 32> LiveInBlocks;
145  ComputeLiveInBlocks(UsingBlocks, DefBlocks, LiveInBlocks, PredCache);
146  IDF.resetLiveInBlocks();
147  IDF.setLiveInBlocks(LiveInBlocks);
148  IDF.calculate(IDFBlocks);
149 
150  // We've computed IDF, now insert new phi-nodes there.
151  SmallVector<PHINode *, 4> InsertedPHIsForVar;
152  for (auto *FrontierBB : IDFBlocks) {
153  IRBuilder<> B(FrontierBB, FrontierBB->begin());
154  PHINode *PN = B.CreatePHI(R.Ty, 0, R.Name);
155  R.Defines[FrontierBB] = PN;
156  InsertedPHIsForVar.push_back(PN);
157  if (InsertedPHIs)
158  InsertedPHIs->push_back(PN);
159  }
160 
161  // Fill in arguments of the inserted PHIs.
162  for (auto *PN : InsertedPHIsForVar) {
163  BasicBlock *PBB = PN->getParent();
164  for (BasicBlock *Pred : PredCache.get(PBB))
165  PN->addIncoming(computeValueAt(Pred, R, DT), Pred);
166  }
167 
168  // Rewrite actual uses with the inserted definitions.
169  SmallPtrSet<Use *, 4> ProcessedUses;
170  for (Use *U : R.Uses) {
171  if (!ProcessedUses.insert(U).second)
172  continue;
173  Value *V = computeValueAt(getUserBB(U), R, DT);
174  Value *OldVal = U->get();
175  assert(OldVal && "Invalid use!");
176  // Notify that users of the existing value that it is being replaced.
177  if (OldVal != V && OldVal->hasValueHandle())
179  LLVM_DEBUG(dbgs() << "SSAUpdater: replacing " << *OldVal << " with " << *V
180  << "\n");
181  U->set(V);
182  }
183  }
184 }
getName
static StringRef getName(Value *V)
Definition: ProvenanceAnalysisEvaluator.cpp:42
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
llvm::IDFCalculatorBase::setLiveInBlocks
void setLiveInBlocks(const SmallPtrSetImpl< NodeTy * > &Blocks)
Give the IDF calculator the set of blocks in which the value is live on entry to the block.
Definition: GenericIteratedDominanceFrontier.h:84
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::PredIteratorCache
PredIteratorCache - This class is an extremely trivial cache for predecessor iterator queries.
Definition: PredIteratorCache.h:27
llvm::SSAUpdaterBulk::AddUse
void AddUse(unsigned Var, Use *U)
Record a use of the symbolic value.
Definition: SSAUpdaterBulk.cpp:61
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::IRBuilder<>
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::DominatorTreeBase::getNode
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Definition: GenericDomTree.h:351
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
ComputeLiveInBlocks
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.
Definition: SSAUpdaterBulk.cpp:86
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
llvm::DomTreeNodeBase::getIDom
DomTreeNodeBase * getIDom() const
Definition: GenericDomTree.h:89
llvm::IDFCalculatorBase::calculate
void calculate(SmallVectorImpl< NodeTy * > &IDFBlocks)
Calculate iterated dominance frontiers.
Definition: GenericIteratedDominanceFrontier.h:131
Use.h
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:193
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
SSAUpdaterBulk.h
llvm::IDFCalculatorBase::resetLiveInBlocks
void resetLiveInBlocks()
Reset the live-in block set to be empty, and tell the IDF calculator to not use liveness anymore.
Definition: GenericIteratedDominanceFrontier.h:91
llvm::User
Definition: User.h:44
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1771
llvm::ValueHandleBase::ValueIsRAUWd
static void ValueIsRAUWd(Value *Old, Value *New)
Definition: Value.cpp:1190
llvm::Value::hasValueHandle
bool hasValueHandle() const
Return true if there is a value handle associated with this value.
Definition: Value.h:555
BasicBlock.h
llvm::DomTreeNodeBase::getBlock
NodeT * getBlock() const
Definition: GenericDomTree.h:88
llvm::SmallPtrSetImpl::end
iterator end() const
Definition: SmallPtrSet.h:407
llvm::SmallPtrSetImpl::begin
iterator begin() const
Definition: SmallPtrSet.h:402
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::DominatorTree::isReachableFromEntry
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:328
llvm::IDFCalculator
Definition: IteratedDominanceFrontier.h:39
llvm::IDFCalculatorBase::setDefiningBlocks
void setDefiningBlocks(const SmallPtrSetImpl< NodeTy * > &Blocks)
Give the IDF calculator the set of blocks in which the value is defined.
Definition: GenericIteratedDominanceFrontier.h:75
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:52
llvm::SSAUpdaterBulk::AddVariable
unsigned AddVariable(StringRef Name, Type *Ty)
Add a new variable to the SSA rewriter.
Definition: SSAUpdaterBulk.cpp:40
llvm::SSAUpdaterBulk::AddAvailableValue
void AddAvailableValue(unsigned Var, BasicBlock *BB, Value *V)
Indicate that a rewritten value is available in the specified block with the specified value.
Definition: SSAUpdaterBulk.cpp:51
IteratedDominanceFrontier.h
getUserBB
static BasicBlock * getUserBB(Use *U)
Helper function for finding a block which should have a value for the given user.
Definition: SSAUpdaterBulk.cpp:29
Instructions.h
Dominators.h
llvm::PHINode
Definition: Instructions.h:2633
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
llvm::PredIteratorCache::get
ArrayRef< BasicBlock * > get(BasicBlock *BB)
Definition: PredIteratorCache.h:66
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
Value.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::SSAUpdaterBulk::RewriteAllUses
void RewriteAllUses(DominatorTree *DT, SmallVectorImpl< PHINode * > *InsertedPHIs=nullptr)
Perform all the necessary updates, including new PHI-nodes insertion and the requested uses update.
Definition: SSAUpdaterBulk.cpp:122
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::SmallPtrSetImpl::insert
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:364