54#define DEBUG_TYPE "lcssa"
56STATISTIC(NumLCSSA,
"Number of live out of a loop variables");
58#ifdef EXPENSIVE_CHECKS
66 cl::desc(
"Verify loop lcssa form (time consuming)"));
92 while (!Worklist.
empty()) {
93 UsesToRewrite.
clear();
96 assert(!
I->getType()->isTokenTy() &&
"Tokens shouldn't be in the worklist");
99 assert(L &&
"Instruction belongs to a BB that's not part of a loop");
100 if (!LoopExitBlocks.
count(L))
101 L->getExitBlocks(LoopExitBlocks[L]);
105 if (ExitBlocks.
empty())
121 if (
auto *PN = dyn_cast<PHINode>(
User))
122 UserBB = PN->getIncomingBlock(U);
124 if (InstBB != UserBB && !L->contains(UserBB))
129 if (UsesToRewrite.
empty())
139 if (
auto *Inv = dyn_cast<InvokeInst>(
I))
140 DomBB = Inv->getNormalDest();
153 bool HasSCEV = SE && SE->
isSCEVable(
I->getType()) &&
163 I->getName() +
".lcssa", &ExitBB->front());
180 if (!L->contains(Pred))
200 if (!L->contains(OtherLoop))
213 for (
Use *UseToRewrite : UsesToRewrite) {
220 if (
auto *PN = dyn_cast<PHINode>(
User))
221 UserBB = PN->getIncomingBlock(*UseToRewrite);
228 UseToRewrite->set(&UserBB->
front());
234 if (AddedPHIs.
size() == 1) {
235 UseToRewrite->set(AddedPHIs[0]);
247 for (
auto *DVI : DbgValues) {
249 if (InstBB == UserBB || L->contains(UserBB))
254 Value *V = AddedPHIs.
size() == 1 ? AddedPHIs[0]
257 DVI->replaceVariableLocationOp(
I, V);
262 for (
PHINode *InsertedPN : LocalInsertedPHIs) {
263 if (
auto *OtherLoop = LI.
getLoopFor(InsertedPN->getParent()))
264 if (!L->contains(OtherLoop))
272 for (
auto *PostProcessPN : PostProcessPHIs)
273 if (!PostProcessPN->use_empty())
280 LocalPHIsToRemove.
insert(PN);
294 PHIsToRemove->
append(LocalPHIsToRemove.
begin(), LocalPHIsToRemove.
end());
296 for (
PHINode *PN : LocalPHIsToRemove)
298 PN->eraseFromParent();
311 while (!BBWorklist.
empty()) {
315 if (L.getHeader() == BB)
338 if (!L.contains(IDomBB))
341 if (BlocksDominatingExits.
insert(IDomBB))
348 bool Changed =
false;
350#ifdef EXPENSIVE_CHECKS
352 for (
Loop *SubLoop: L) {
354 assert(SubLoop->isRecursivelyLCSSAForm(DT, *LI) &&
"Subloop not in LCSSA!");
359 L.getExitBlocks(ExitBlocks);
360 if (ExitBlocks.
empty())
376 for (
BasicBlock *BB : BlocksDominatingExits) {
385 (
I.hasOneUse() &&
I.user_back()->getParent() == BB &&
386 !isa<PHINode>(
I.user_back())))
393 if (
I.getType()->isTokenTy())
402 assert(L.isLCSSAForm(DT));
410 bool Changed =
false;
413 for (
Loop *SubLoop : L.getSubLoops())
423 bool Changed =
false;
424 for (
const auto &L : *LI)
450 return L->isRecursivelyLCSSAForm(*DT, *LI);
452 "LCSSA form is broken!");
480char LCSSAWrapperPass::ID = 0;
493bool LCSSAWrapperPass::runOnFunction(
Function &
F) {
494 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
495 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
496 auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
497 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.
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 PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
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.
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
const SCEV * getExistingSCEV(Value *V)
Return an existing SCEV for V if there is one, otherwise return nullptr.
iterator end()
Get an iterator to the end of the SetVector.
iterator begin()
Get an iterator to the beginning of the SetVector.
bool insert(const value_type &X)
Insert a new element into 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, SmallVectorImpl< PHINode * > *PHIsToRemove=nullptr, SmallVectorImpl< PHINode * > *InsertedPHIs=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.