Go to the documentation of this file.
29 #define DEBUG_TYPE "unify-loop-exits"
56 return new UnifyLoopExitsLegacyPass();
60 "Fixup each natural loop to have a single exit block",
91 for (
auto BB : L->blocks()) {
93 for (
auto &U :
I.uses()) {
94 auto UserInst = cast<Instruction>(U.getUser());
95 auto UserBlock = UserInst->getParent();
96 if (UserBlock == LoopExitBlock)
98 if (L->contains(UserBlock))
101 <<
BB->getName() <<
")"
102 <<
": " << UserInst->getName() <<
"("
103 << UserBlock->getName() <<
")"
105 ExternalUsers[&
I].push_back(UserInst);
110 for (
auto II : ExternalUsers) {
118 Def->getName() +
".moved",
119 LoopExitBlock->getTerminator());
120 for (
auto In : Incoming) {
122 if (
Def->getParent() ==
In || DT.dominates(
Def,
In)) {
124 NewPhi->addIncoming(
Def,
In);
132 for (
auto U : II.second) {
134 U->replaceUsesOfWith(
Def, NewPhi);
152 for (
auto BB : Temp) {
165 dbgs() <<
"Found exit blocks:";
166 for (
auto Exit : Exits) {
167 dbgs() <<
" " << Exit->getName();
171 dbgs() <<
"Found exiting blocks:";
172 for (
auto EB : ExitingBlocks) {
173 dbgs() <<
" " << EB->getName();
177 if (Exits.size() <= 1) {
178 LLVM_DEBUG(
dbgs() <<
"loop does not have multiple exits; nothing to do\n");
187 restoreSSA(DT, L, ExitingBlocks, LoopExitBlock);
189 #if defined(EXPENSIVE_CHECKS)
193 #endif // EXPENSIVE_CHECKS
199 for (
auto G : GuardBlocks) {
200 ParentLoop->addBasicBlockToLoop(
G, LI);
202 ParentLoop->verifyLoop();
205 #if defined(EXPENSIVE_CHECKS)
207 #endif // EXPENSIVE_CHECKS
214 bool Changed =
false;
216 for (
auto L :
Loops) {
217 LLVM_DEBUG(
dbgs() <<
"Loop: " << L->getHeader()->getName() <<
" (depth: "
225 LLVM_DEBUG(
dbgs() <<
"===== Unifying loop exits in function " <<
F.getName()
227 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
228 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
A set of analyses that are preserved following a run of a transformation pass.
static bool unifyLoopExits(DominatorTree &DT, LoopInfo &LI, Loop *L)
This is an optimization pass for GlobalISel generic memory operations.
INITIALIZE_PASS_BEGIN(UnifyLoopExitsLegacyPass, "unify-loop-exits", "Fixup each natural loop to have a single exit block", false, false) INITIALIZE_PASS_END(UnifyLoopExitsLegacyPass
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represents a single loop in the control flow graph.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
The legacy pass manager's analysis pass to compute loop information.
This class implements a map that also provides access to all stored values in a deterministic order.
auto successors(MachineBasicBlock *BB)
Analysis the ScalarEvolution expression for r is< loop > Outside the loop
LLVM Basic Block Representation.
=0.0 ? 0.0 :(a > 0.0 ? 1.0 :-1.0) a
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void initializeUnifyLoopExitsLegacyPassPass(PassRegistry &)
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
BasicBlock * CreateControlFlowHub(DomTreeUpdater *DTU, SmallVectorImpl< BasicBlock * > &GuardBlocks, const SetVector< BasicBlock * > &Predecessors, const SetVector< BasicBlock * > &Successors, const StringRef Prefix)
Given a set of incoming and outgoing blocks, create a "hub" such that every edge from an incoming blo...
static bool runImpl(LoopInfo &LI, DominatorTree &DT)
Represent the analysis usage information of a pass.
void verifyLoop() const
Verify loop structure.
Legacy analysis pass which computes a DominatorTree.
FunctionPass * createUnifyLoopExitsPass()
void getExitingBlocks(SmallVectorImpl< BlockT * > &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
void preserve()
Mark an analysis as preserved.
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool insert(const value_type &X)
Insert a new element into the SetVector.
unsigned getLoopDepth(const BlockT *BB) const
Return the loop nesting level of the specified block.
AnalysisUsage & addPreservedID(const void *ID)
unify loop Fixup each natural loop to have a single exit block
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
unify loop Fixup each natural loop to have a single exit static false void restoreSSA(const DominatorTree &DT, const Loop *L, const SetVector< BasicBlock * > &Incoming, BasicBlock *LoopExitBlock)
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
SmallVector< LoopT *, 4 > getLoopsInPreorder() const
Return all of the loops in the function in preorder across the loop nests, with siblings in forward p...
static bool runOnFunction(Function &F, bool PostInlining)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
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...
Analysis pass which computes a DominatorTree.
declare void exit(i32) noreturn nounwind This compiles into
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
A container for analyses that lazily runs them and caches their results.
FunctionPass class - This class is used to implement most global optimizations.
AnalysisUsage & addRequiredID(const void *ID)
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()
A vector that has set insertion semantics.
Analysis pass that exposes the LoopInfo for a function.