Go to the documentation of this file.
56 #define DEBUG_TYPE "lcssa"
58 STATISTIC(NumLCSSA,
"Number of live out of a loop variables");
60 #ifdef EXPENSIVE_CHECKS
68 cl::desc(
"Verify loop lcssa form (time consuming)"));
95 while (!Worklist.empty()) {
96 UsesToRewrite.
clear();
99 assert(!
I->getType()->isTokenTy() &&
"Tokens shouldn't be in the worklist");
102 assert(L &&
"Instruction belongs to a BB that's not part of a loop");
103 if (!LoopExitBlocks.
count(L))
108 if (ExitBlocks.empty())
111 for (
Use &U :
I->uses()) {
118 if (
auto *PN = dyn_cast<PHINode>(
User))
119 UserBB = PN->getIncomingBlock(U);
121 if (InstBB != UserBB && !L->contains(UserBB))
122 UsesToRewrite.push_back(&U);
126 if (UsesToRewrite.empty())
136 if (
auto *Inv = dyn_cast<InvokeInst>(
I))
137 DomBB = Inv->getNormalDest();
162 Builder.SetInsertPoint(&ExitBB->front());
164 I->getName() +
".lcssa");
179 if (!L->contains(Pred))
180 UsesToRewrite.push_back(
185 AddedPHIs.push_back(PN);
199 if (!L->contains(OtherLoop))
200 PostProcessPHIs.push_back(PN);
205 for (
Use *UseToRewrite : UsesToRewrite) {
212 if (
auto *PN = dyn_cast<PHINode>(
User))
213 UserBB = PN->getIncomingBlock(*UseToRewrite);
220 UseToRewrite->set(&UserBB->
front());
226 if (AddedPHIs.size() == 1) {
227 UseToRewrite->set(AddedPHIs[0]);
239 for (
auto DVI : DbgValues) {
241 if (InstBB == UserBB || L->contains(UserBB))
246 Value *V = AddedPHIs.size() == 1 ? AddedPHIs[0]
249 DVI->replaceVariableLocationOp(
I, V);
254 for (
PHINode *InsertedPN : InsertedPHIs) {
255 if (
auto *OtherLoop = LI.
getLoopFor(InsertedPN->getParent()))
256 if (!L->contains(OtherLoop))
257 PostProcessPHIs.push_back(InsertedPN);
262 for (
auto *PostProcessPN : PostProcessPHIs)
263 if (!PostProcessPN->use_empty())
264 Worklist.push_back(PostProcessPN);
270 LocalPHIsToRemove.
insert(PN);
284 PHIsToRemove->
append(LocalPHIsToRemove.
begin(), LocalPHIsToRemove.
end());
286 for (
PHINode *PN : LocalPHIsToRemove)
288 PN->eraseFromParent();
301 while (!BBWorklist.empty()) {
331 if (BlocksDominatingExits.
insert(IDomBB))
332 BBWorklist.push_back(IDomBB);
338 bool Changed =
false;
340 #ifdef EXPENSIVE_CHECKS
342 for (
Loop *SubLoop: L)
343 assert(SubLoop->isRecursivelyLCSSAForm(DT, *LI) &&
"Subloop not in LCSSA!");
347 L.getExitBlocks(ExitBlocks);
348 if (ExitBlocks.empty())
373 (
I.hasOneUse() &&
I.user_back()->getParent() ==
BB &&
374 !isa<PHINode>(
I.user_back())))
381 if (
I.getType()->isTokenTy())
384 Worklist.push_back(&
I);
397 assert(L.isLCSSAForm(DT));
405 bool Changed =
false;
418 bool Changed =
false;
437 void verifyAnalysis()
const override {
447 "LCSSA form is broken!");
489 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
490 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
491 auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
492 SE = SEWP ? &SEWP->getSE() :
nullptr;
Analysis pass providing a never-invalidated alias analysis result.
void Initialize(Type *Ty, StringRef Name)
Reset this object to get ready for a new set of SSA updates with type 'Ty'.
A set of analyses that are preserved following a run of a transformation pass.
bool formLCSSA(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put loop into LCSSA form.
Analysis pass providing a never-invalidated alias analysis result.
static void computeBlocksDominatingExits(Loop &L, const DominatorTree &DT, SmallVector< BasicBlock *, 8 > &ExitBlocks, SmallSetVector< BasicBlock *, 8 > &BlocksDominatingExits)
Analysis pass that exposes the ScalarEvolution for a function.
Analysis pass providing a never-invalidated alias analysis result.
void getExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all of the successor blocks of this loop.
const Function * getParent() const
Return the enclosing method, or null if none.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
LocationClass< Ty > location(Ty &L)
Represents a single loop in the control flow graph.
PredIteratorCache - This class is an extremely trivial cache for predecessor iterator queries.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
static bool formLCSSAOnAllLoops(const LoopInfo *LI, const DominatorTree &DT, ScalarEvolution *SE)
Process all loops in the function, inner-most out.
static unsigned getOperandNumForIncomingValue(unsigned i)
The main scalar evolution driver.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
The legacy pass manager's analysis pass to compute loop information.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::count size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
LLVM_NODISCARD T pop_back_val()
DomTreeNodeBase * getIDom() const
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
LLVM Basic Block Representation.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
const Use & getOperandUse(unsigned i) const
const std::vector< LoopT * > & getSubLoops() const
Return the loops contained entirely within this loop.
Analysis pass which computes BranchProbabilityInfo.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Legacy analysis pass which computes MemorySSA.
iterator begin()
Get an iterator to the beginning of the SetVector.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Legacy analysis pass which computes BranchProbabilityInfo.
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
size_t size(BasicBlock *BB) const
iterator begin()
Instruction iterator methods.
Represent the analysis usage information of a pass.
Legacy analysis pass which computes a DominatorTree.
STATISTIC(NumFunctions, "Total number of functions")
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Legacy wrapper pass to provide the SCEVAAResult object.
void preserve()
Mark an analysis as preserved.
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
static cl::opt< bool, true > VerifyLoopLCSSAFlag("verify-loop-lcssa", cl::location(VerifyLoopLCSSA), cl::Hidden, cl::desc("Verify loop lcssa form (time consuming)"))
Legacy wrapper pass to provide the BasicAAResult object.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
void findDbgValues(SmallVectorImpl< DbgValueInst * > &DbgValues, Value *V)
Finds the llvm.dbg.value intrinsics describing a value.
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
void initializeLCSSAWrapperPassPass(PassRegistry &)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
An analysis that produces MemorySSA for a function.
bool insert(const value_type &X)
Insert a new element into the SetVector.
static bool VerifyLoopLCSSA
void setPreservesCFG()
This function should be called by the pass, iff they do not:
AnalysisUsage & addPreservedID(const void *ID)
Represents analyses that only rely on functions' control flow.
Value * FindValueForBlock(BasicBlock *BB) const
Return the value for the specified block if the SSAUpdater has one, otherwise return nullptr.
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Common base class shared among various IRBuilders.
bool HasValueForBlock(BasicBlock *BB) const
Return true if the SSAUpdater already has a value for the specified block.
const Instruction & front() const
static bool runOnFunction(Function &F, bool PostInlining)
void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
BlockT * getHeader() const
bool isRecursivelyLCSSAForm(const DominatorTree &DT, const LoopInfo &LI) const
Return true if this Loop and all inner subloops are in LCSSA form.
Analysis pass which computes a DominatorTree.
iterator end()
Get an iterator to the end of the SetVector.
bool formLCSSAForInstructions(SmallVectorImpl< Instruction * > &Worklist, const DominatorTree &DT, const LoopInfo &LI, ScalarEvolution *SE, IRBuilderBase &Builder, SmallVectorImpl< PHINode * > *PHIsToRemove=nullptr)
Ensures LCSSA form for every instruction from the Worklist in the scope of innermost containing loop.
Pass interface - Implemented by all 'passes'.
void preserveSet()
Mark an analysis set as preserved.
static bool isExitBlock(BasicBlock *BB, const SmallVectorImpl< BasicBlock * > &ExitBlocks)
Return true if the specified block is in the list.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
void RewriteUse(Use &U)
Rewrite a use of the symbolic value.
Legacy wrapper pass to provide the GlobalsAAResult object.
ArrayRef< BasicBlock * > get(BasicBlock *BB)
A SetVector that performs no allocations if smaller than a certain size.
A container for analyses that lazily runs them and caches their results.
FunctionPass class - This class is used to implement most global optimizations.
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
AnalysisUsage & addRequired()
void AddAvailableValue(BasicBlock *BB, Value *V)
Indicate that a rewritten value is available in the specified block with the specified value.
Helper class for SSA formation on a set of values defined in multiple blocks.
LLVM Value Representation.
Analysis pass that exposes the LoopInfo for a function.
A Use represents the edge between a Value definition and its users.
INITIALIZE_PASS_BEGIN(LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass", false, false) INITIALIZE_PASS_END(LCSSAWrapperPass