LLVM 18.0.0git
UnifyLoopExits.cpp
Go to the documentation of this file.
1//===- UnifyLoopExits.cpp - Redirect exiting edges to one block -*- C++ -*-===//
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// For each natural loop with multiple exit blocks, this pass creates a new
10// block N such that all exiting blocks now branch to N, and then control flow
11// is redistributed to all the original exit blocks.
12//
13// Limitation: This assumes that all terminators in the CFG are direct branches
14// (the "br" instruction). The presence of any other control flow
15// such as indirectbr, switch or callbr will cause an assert.
16//
17//===----------------------------------------------------------------------===//
18
20#include "llvm/ADT/MapVector.h"
23#include "llvm/IR/Constants.h"
24#include "llvm/IR/Dominators.h"
29
30#define DEBUG_TYPE "unify-loop-exits"
31
32using namespace llvm;
33
35 "max-booleans-in-control-flow-hub", cl::init(32), cl::Hidden,
36 cl::desc("Set the maximum number of outgoing blocks for using a boolean "
37 "value to record the exiting block in CreateControlFlowHub."));
38
39namespace {
40struct UnifyLoopExitsLegacyPass : public FunctionPass {
41 static char ID;
42 UnifyLoopExitsLegacyPass() : FunctionPass(ID) {
44 }
45
46 void getAnalysisUsage(AnalysisUsage &AU) const override {
53 }
54
55 bool runOnFunction(Function &F) override;
56};
57} // namespace
58
59char UnifyLoopExitsLegacyPass::ID = 0;
60
62 return new UnifyLoopExitsLegacyPass();
63}
64
65INITIALIZE_PASS_BEGIN(UnifyLoopExitsLegacyPass, "unify-loop-exits",
66 "Fixup each natural loop to have a single exit block",
67 false /* Only looks at CFG */, false /* Analysis Pass */)
68INITIALIZE_PASS_DEPENDENCY(LowerSwitchLegacyPass)
71INITIALIZE_PASS_END(UnifyLoopExitsLegacyPass, "unify-loop-exits",
72 "Fixup each natural loop to have a single exit block",
73 false /* Only looks at CFG */, false /* Analysis Pass */)
74
75// The current transform introduces new control flow paths which may break the
76// SSA requirement that every def must dominate all its uses. For example,
77// consider a value D defined inside the loop that is used by some instruction
78// U outside the loop. It follows that D dominates U, since the original
79// program has valid SSA form. After merging the exits, all paths from D to U
80// now flow through the unified exit block. In addition, there may be other
81// paths that do not pass through D, but now reach the unified exit
82// block. Thus, D no longer dominates U.
83//
84// Restore the dominance by creating a phi for each such D at the new unified
85// loop exit. But when doing this, ignore any uses U that are in the new unified
86// loop exit, since those were introduced specially when the block was created.
87//
88// The use of SSAUpdater seems like overkill for this operation. The location
89// for creating the new PHI is well-known, and also the set of incoming blocks
90// to the new PHI.
92 const SetVector<BasicBlock *> &Incoming,
93 BasicBlock *LoopExitBlock) {
94 using InstVector = SmallVector<Instruction *, 8>;
96 IIMap ExternalUsers;
97 for (auto *BB : L->blocks()) {
98 for (auto &I : *BB) {
99 for (auto &U : I.uses()) {
100 auto UserInst = cast<Instruction>(U.getUser());
101 auto UserBlock = UserInst->getParent();
102 if (UserBlock == LoopExitBlock)
103 continue;
104 if (L->contains(UserBlock))
105 continue;
106 LLVM_DEBUG(dbgs() << "added ext use for " << I.getName() << "("
107 << BB->getName() << ")"
108 << ": " << UserInst->getName() << "("
109 << UserBlock->getName() << ")"
110 << "\n");
111 ExternalUsers[&I].push_back(UserInst);
112 }
113 }
114 }
115
116 for (const auto &II : ExternalUsers) {
117 // For each Def used outside the loop, create NewPhi in
118 // LoopExitBlock. NewPhi receives Def only along exiting blocks that
119 // dominate it, while the remaining values are undefined since those paths
120 // didn't exist in the original CFG.
121 auto Def = II.first;
122 LLVM_DEBUG(dbgs() << "externally used: " << Def->getName() << "\n");
123 auto NewPhi =
124 PHINode::Create(Def->getType(), Incoming.size(),
125 Def->getName() + ".moved", &LoopExitBlock->front());
126 for (auto *In : Incoming) {
127 LLVM_DEBUG(dbgs() << "predecessor " << In->getName() << ": ");
128 if (Def->getParent() == In || DT.dominates(Def, In)) {
129 LLVM_DEBUG(dbgs() << "dominated\n");
130 NewPhi->addIncoming(Def, In);
131 } else {
132 LLVM_DEBUG(dbgs() << "not dominated\n");
133 NewPhi->addIncoming(PoisonValue::get(Def->getType()), In);
134 }
135 }
136
137 LLVM_DEBUG(dbgs() << "external users:");
138 for (auto *U : II.second) {
139 LLVM_DEBUG(dbgs() << " " << U->getName());
140 U->replaceUsesOfWith(Def, NewPhi);
141 }
142 LLVM_DEBUG(dbgs() << "\n");
143 }
144}
145
146static bool unifyLoopExits(DominatorTree &DT, LoopInfo &LI, Loop *L) {
147 // To unify the loop exits, we need a list of the exiting blocks as
148 // well as exit blocks. The functions for locating these lists both
149 // traverse the entire loop body. It is more efficient to first
150 // locate the exiting blocks and then examine their successors to
151 // locate the exit blocks.
152 SetVector<BasicBlock *> ExitingBlocks;
154
155 // We need SetVectors, but the Loop API takes a vector, so we use a temporary.
157 L->getExitingBlocks(Temp);
158 for (auto *BB : Temp) {
159 ExitingBlocks.insert(BB);
160 for (auto *S : successors(BB)) {
161 auto SL = LI.getLoopFor(S);
162 // A successor is not an exit if it is directly or indirectly in the
163 // current loop.
164 if (SL == L || L->contains(SL))
165 continue;
166 Exits.insert(S);
167 }
168 }
169
171 dbgs() << "Found exit blocks:";
172 for (auto Exit : Exits) {
173 dbgs() << " " << Exit->getName();
174 }
175 dbgs() << "\n";
176
177 dbgs() << "Found exiting blocks:";
178 for (auto EB : ExitingBlocks) {
179 dbgs() << " " << EB->getName();
180 }
181 dbgs() << "\n";);
182
183 if (Exits.size() <= 1) {
184 LLVM_DEBUG(dbgs() << "loop does not have multiple exits; nothing to do\n");
185 return false;
186 }
187
189 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
190 auto LoopExitBlock =
191 CreateControlFlowHub(&DTU, GuardBlocks, ExitingBlocks, Exits, "loop.exit",
192 MaxBooleansInControlFlowHub.getValue());
193
194 restoreSSA(DT, L, ExitingBlocks, LoopExitBlock);
195
196#if defined(EXPENSIVE_CHECKS)
197 assert(DT.verify(DominatorTree::VerificationLevel::Full));
198#else
199 assert(DT.verify(DominatorTree::VerificationLevel::Fast));
200#endif // EXPENSIVE_CHECKS
201 L->verifyLoop();
202
203 // The guard blocks were created outside the loop, so they need to become
204 // members of the parent loop.
205 if (auto ParentLoop = L->getParentLoop()) {
206 for (auto *G : GuardBlocks) {
207 ParentLoop->addBasicBlockToLoop(G, LI);
208 }
209 ParentLoop->verifyLoop();
210 }
211
212#if defined(EXPENSIVE_CHECKS)
213 LI.verify(DT);
214#endif // EXPENSIVE_CHECKS
215
216 return true;
217}
218
219static bool runImpl(LoopInfo &LI, DominatorTree &DT) {
220
221 bool Changed = false;
222 auto Loops = LI.getLoopsInPreorder();
223 for (auto *L : Loops) {
224 LLVM_DEBUG(dbgs() << "Loop: " << L->getHeader()->getName() << " (depth: "
225 << LI.getLoopDepth(L->getHeader()) << ")\n");
226 Changed |= unifyLoopExits(DT, LI, L);
227 }
228 return Changed;
229}
230
231bool UnifyLoopExitsLegacyPass::runOnFunction(Function &F) {
232 LLVM_DEBUG(dbgs() << "===== Unifying loop exits in function " << F.getName()
233 << "\n");
234 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
235 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
236
237 return runImpl(LI, DT);
238}
239
240namespace llvm {
241
244 auto &LI = AM.getResult<LoopAnalysis>(F);
245 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
246
247 if (!runImpl(LI, DT))
248 return PreservedAnalyses::all();
252 return PA;
253}
254} // namespace llvm
aarch64 promote const
This file contains the declarations for the subclasses of Constant, which represent the different fla...
#define LLVM_DEBUG(X)
Definition: Debug.h:101
static bool runImpl(Function &F, const TargetLowering &TLI)
Hexagon Hardware Loops
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
#define G(x, y, z)
Definition: MD5.cpp:56
This file implements a map that provides insertion order iteration.
PowerPC TLS Dynamic Call Fixup
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
unify loop exits
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)
unify loop Fixup each natural loop to have a single exit block
static cl::opt< unsigned > MaxBooleansInControlFlowHub("max-booleans-in-control-flow-hub", cl::init(32), cl::Hidden, cl::desc("Set the maximum number of outgoing blocks for using a boolean " "value to record the exiting block in CreateControlFlowHub."))
static bool unifyLoopExits(DominatorTree &DT, LoopInfo &LI, Loop *L)
static bool runImpl(LoopInfo &LI, DominatorTree &DT)
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
Represent the analysis usage information of a pass.
AnalysisUsage & addRequiredID(const void *ID)
Definition: Pass.cpp:283
AnalysisUsage & addPreservedID(const void *ID)
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:314
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
virtual bool runOnFunction(Function &F)=0
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:569
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
SmallVector< LoopT *, 4 > getLoopsInPreorder() const
Return all of the loops in the function in preorder across the loop nests, with siblings in forward p...
unsigned getLoopDepth(const BlockT *BB) const
Return the loop nesting level of the specified block.
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.
Definition: LoopInfo.h:594
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:47
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:36
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 PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:98
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1743
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
A vector that has set insertion semantics.
Definition: SetVector.h:57
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:98
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:162
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto successors(const MachineBasicBlock *BB)
void initializeUnifyLoopExitsLegacyPassPass(PassRegistry &)
char & LowerSwitchID
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
FunctionPass * createUnifyLoopExitsPass()
BasicBlock * CreateControlFlowHub(DomTreeUpdater *DTU, SmallVectorImpl< BasicBlock * > &GuardBlocks, const SetVector< BasicBlock * > &Predecessors, const SetVector< BasicBlock * > &Successors, const StringRef Prefix, std::optional< unsigned > MaxControlFlowBooleans=std::nullopt)
Given a set of incoming and outgoing blocks, create a "hub" such that every edge from an incoming blo...