LLVM  13.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 /// 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 }
getName
static StringRef getName(Value *V)
Definition: ProvenanceAnalysisEvaluator.cpp:42
llvm
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:1167
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:46
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:92
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:634
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:122
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:180
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:132
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:1783
llvm::ValueHandleBase::ValueIsRAUWd
static void ValueIsRAUWd(Value *Old, Value *New)
Definition: Value.cpp:1166
llvm::Value::hasValueHandle
bool hasValueHandle() const
Return true if there is a value handle associated with this value.
Definition: Value.h:551
llvm::SSAUpdaterBulk::HasValueForBlock
bool HasValueForBlock(unsigned Var, BasicBlock *BB)
Return true if the SSAUpdater already has a value for the specified variable in the specified block.
Definition: SSAUpdaterBulk.cpp:70
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:2600
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:128
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