55#define DEBUG_TYPE "lcssa"
57STATISTIC(NumLCSSA,
"Number of live out of a loop variables");
59#ifdef EXPENSIVE_CHECKS
67 cl::desc(
"Verify loop lcssa form (time consuming)"));
94 while (!Worklist.
empty()) {
95 UsesToRewrite.
clear();
98 assert(!
I->getType()->isTokenTy() &&
"Tokens shouldn't be in the worklist");
101 assert(L &&
"Instruction belongs to a BB that's not part of a loop");
102 if (!LoopExitBlocks.
count(L))
103 L->getExitBlocks(LoopExitBlocks[L]);
107 if (ExitBlocks.
empty())
123 if (
auto *PN = dyn_cast<PHINode>(
User))
124 UserBB = PN->getIncomingBlock(U);
126 if (InstBB != UserBB && !L->contains(UserBB))
131 if (UsesToRewrite.
empty())
141 if (
auto *Inv = dyn_cast<InvokeInst>(
I))
142 DomBB = Inv->getNormalDest();
167 Builder.SetInsertPoint(&ExitBB->front());
169 I->getName() +
".lcssa");
184 if (!L->contains(Pred))
204 if (!L->contains(OtherLoop))
210 for (
Use *UseToRewrite : UsesToRewrite) {
217 if (
auto *PN = dyn_cast<PHINode>(
User))
218 UserBB = PN->getIncomingBlock(*UseToRewrite);
225 UseToRewrite->set(&UserBB->
front());
231 if (AddedPHIs.
size() == 1) {
232 UseToRewrite->set(AddedPHIs[0]);
244 for (
auto *DVI : DbgValues) {
246 if (InstBB == UserBB || L->contains(UserBB))
251 Value *V = AddedPHIs.
size() == 1 ? AddedPHIs[0]
254 DVI->replaceVariableLocationOp(
I, V);
259 for (
PHINode *InsertedPN : InsertedPHIs) {
260 if (
auto *OtherLoop = LI.
getLoopFor(InsertedPN->getParent()))
261 if (!L->contains(OtherLoop))
267 for (
auto *PostProcessPN : PostProcessPHIs)
268 if (!PostProcessPN->use_empty())
275 LocalPHIsToRemove.
insert(PN);
289 PHIsToRemove->
append(LocalPHIsToRemove.
begin(), LocalPHIsToRemove.
end());
291 for (
PHINode *PN : LocalPHIsToRemove)
293 PN->eraseFromParent();
306 while (!BBWorklist.
empty()) {
310 if (L.getHeader() == BB)
333 if (!L.contains(IDomBB))
336 if (BlocksDominatingExits.
insert(IDomBB))
343 bool Changed =
false;
345#ifdef EXPENSIVE_CHECKS
347 for (
Loop *SubLoop: L) {
349 assert(SubLoop->isRecursivelyLCSSAForm(DT, *LI) &&
"Subloop not in LCSSA!");
354 L.getExitBlocks(ExitBlocks);
355 if (ExitBlocks.
empty())
371 for (
BasicBlock *BB : BlocksDominatingExits) {
380 (
I.hasOneUse() &&
I.user_back()->getParent() == BB &&
381 !isa<PHINode>(
I.user_back())))
388 if (
I.getType()->isTokenTy())
404 assert(L.isLCSSAForm(DT));
412 bool Changed =
false;
415 for (
Loop *SubLoop : L.getSubLoops())
425 bool Changed =
false;
426 for (
const auto &L : *LI)
452 return L->isRecursivelyLCSSAForm(*DT, *LI);
454 "LCSSA form is broken!");
482char LCSSAWrapperPass::ID = 0;
495bool LCSSAWrapperPass::runOnFunction(
Function &
F) {
496 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
497 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
498 auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
499 SE = SEWP ? &SEWP->getSE() :
nullptr;
This is the interface for LLVM's primary stateless and local alias analysis.
This is the interface for a simple mod/ref and alias analysis over globals.
static bool isExitBlock(BasicBlock *BB, const SmallVectorImpl< BasicBlock * > &ExitBlocks)
Return true if the specified block is in the list.
static bool VerifyLoopLCSSA
static bool formLCSSAOnAllLoops(const LoopInfo *LI, const DominatorTree &DT, ScalarEvolution *SE)
Process all loops in the function, inner-most out.
static void computeBlocksDominatingExits(Loop &L, const DominatorTree &DT, SmallVector< BasicBlock *, 8 > &ExitBlocks, SmallSetVector< BasicBlock *, 8 > &BlocksDominatingExits)
static cl::opt< bool, true > VerifyLoopLCSSAFlag("verify-loop-lcssa", cl::location(VerifyLoopLCSSA), cl::Hidden, cl::desc("Verify loop lcssa form (time consuming)"))
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This is the interface for a SCEV-based alias analysis.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
A container for analyses that lazily runs them and caches their results.
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
AnalysisUsage & addPreservedID(const void *ID)
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Legacy wrapper pass to provide the BasicAAResult object.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
const Instruction & front() const
const Function * getParent() const
Return the enclosing method, or null if none.
Analysis pass which computes BranchProbabilityInfo.
Legacy analysis pass which computes BranchProbabilityInfo.
Represents analyses that only rely on functions' control flow.
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
DomTreeNodeBase * getIDom() const
Analysis pass which computes a DominatorTree.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
FunctionPass class - This class is used to implement most global optimizations.
virtual bool runOnFunction(Function &F)=0
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Legacy wrapper pass to provide the GlobalsAAResult object.
Common base class shared among various IRBuilders.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Analysis pass that exposes the LoopInfo for a function.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
The legacy pass manager's analysis pass to compute loop information.
Represents a single loop in the control flow graph.
An analysis that produces MemorySSA for a function.
Legacy analysis pass which computes MemorySSA.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static unsigned getOperandNumForIncomingValue(unsigned i)
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Pass interface - Implemented by all 'passes'.
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
virtual void verifyAnalysis() const
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
PredIteratorCache - This class is an extremely trivial cache for predecessor iterator queries.
size_t size(BasicBlock *BB) const
ArrayRef< BasicBlock * > get(BasicBlock *BB)
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
void preserveSet()
Mark an analysis set as preserved.
void preserve()
Mark an analysis as preserved.
Legacy wrapper pass to provide the SCEVAAResult object.
Helper class for SSA formation on a set of values defined in multiple blocks.
void RewriteUse(Use &U)
Rewrite a use of the symbolic value.
Value * FindValueForBlock(BasicBlock *BB) const
Return the value for the specified block if the SSAUpdater has one, otherwise return nullptr.
void Initialize(Type *Ty, StringRef Name)
Reset this object to get ready for a new set of SSA updates with type 'Ty'.
bool HasValueForBlock(BasicBlock *BB) const
Return true if the SSAUpdater already has a value for the specified block.
void AddAvailableValue(BasicBlock *BB, Value *V)
Indicate that a rewritten value is available in the specified block with the specified value.
Analysis pass that exposes the ScalarEvolution for a function.
The main scalar evolution driver.
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...
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...
bool insert(const value_type &X)
Insert a new element into the SetVector.
iterator begin()
Get an iterator to the beginning of the SetVector.
iterator end()
Get an iterator to the end of the SetVector.
A SetVector that performs no allocations if smaller than a certain size.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
A Use represents the edge between a Value definition and its users.
const Use & getOperandUse(unsigned i) const
LLVM Value Representation.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
LocationClass< Ty > location(Ty &L)
This is an optimization pass for GlobalISel generic memory operations.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
void initializeLCSSAWrapperPassPass(PassRegistry &)
bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
void findDbgValues(SmallVectorImpl< DbgValueInst * > &DbgValues, Value *V)
Finds the llvm.dbg.value intrinsics describing a value.
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.
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
bool formLCSSA(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put loop into LCSSA form.