1//===- UnifyLoopExits.cpp - Redirect exiting edges to one block -*- C++ -*-===// 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 7//===----------------------------------------------------------------------===// 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. 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. 17//===----------------------------------------------------------------------===// 31#define DEBUG_TYPE "unify-loop-exits" 37cl::desc(
"Set the maximum number of outgoing blocks for using a boolean " 38"value to record the exiting block in the ControlFlowHub."));
58char UnifyLoopExitsLegacyPass::ID = 0;
61returnnew UnifyLoopExitsLegacyPass();
65"Fixup each natural loop to have a single exit block",
66false/* Only looks at CFG */,
false/* Analysis Pass */)
73// The current transform introduces new control flow paths which may break the 74// SSA requirement that every def must dominate all its uses. For example, 75// consider a value D defined inside the loop that is used by some instruction 76// U outside the loop. It follows that D dominates U, since the original 77// program has valid SSA form. After merging the exits, all paths from D to U 78// now flow through the unified exit block. In addition, there may be other 79// paths that do not pass through D, but now reach the unified exit 80// block. Thus, D no longer dominates U. 82// Restore the dominance by creating a phi for each such D at the new unified 83// loop exit. But when doing this, ignore any uses U that are in the new unified 84// loop exit, since those were introduced specially when the block was created. 86// The use of SSAUpdater seems like overkill for this operation. The location 87// for creating the new PHI is well-known, and also the set of incoming blocks 95for (
auto *BB : L->blocks()) {
97for (
auto &U :
I.uses()) {
98auto UserInst = cast<Instruction>(U.getUser());
99auto UserBlock = UserInst->getParent();
100if (UserBlock == LoopExitBlock)
102if (L->contains(UserBlock))
105 << BB->getName() <<
")" 106 <<
": " << UserInst->getName() <<
"(" 107 << UserBlock->getName() <<
")" 109 ExternalUsers[&
I].push_back(UserInst);
114for (
constauto &
II : ExternalUsers) {
115// For each Def used outside the loop, create NewPhi in 116// LoopExitBlock. NewPhi receives Def only along exiting blocks that 117// dominate it, while the remaining values are undefined since those paths 118// didn't exist in the original CFG. 123 Def->getName() +
".moved", LoopExitBlock->begin());
126if (Def->getParent() == In || DT.
dominates(Def, In)) {
128 NewPhi->addIncoming(Def, In);
136for (
auto *U :
II.second) {
138 U->replaceUsesOfWith(Def, NewPhi);
145// To unify the loop exits, we need a list of the exiting blocks as 146// well as exit blocks. The functions for locating these lists both 147// traverse the entire loop body. It is more efficient to first 148// locate the exiting blocks and then examine their successors to 149// locate the exit blocks. 151 L->getExitingBlocks(ExitingBlocks);
153// Redirect exiting edges through a control flow hub. 155for (
auto *BB : ExitingBlocks) {
156auto *Branch = cast<BranchInst>(BB->getTerminator());
158 Succ0 = L->contains(Succ0) ? nullptr : Succ0;
161 Branch->isUnconditional() ? nullptr : Branch->getSuccessor(1);
162 Succ1 = L->contains(Succ1) ? nullptr : Succ1;
165LLVM_DEBUG(
dbgs() <<
"Added exiting branch: " << BB->getName() <<
" -> {" 166 << (Succ0 ? Succ0->
getName() :
"<none>") <<
", " 167 << (Succ1 ? Succ1->
getName() :
"<none>") <<
"}\n");
175restoreSSA(DT, L, ExitingBlocks, LoopExitBlock);
177#if defined(EXPENSIVE_CHECKS) 178assert(DT.
verify(DominatorTree::VerificationLevel::Full));
180assert(DT.
verify(DominatorTree::VerificationLevel::Fast));
181#endif// EXPENSIVE_CHECKS 184// The guard blocks were created outside the loop, so they need to become 185// members of the parent loop. 186if (
auto ParentLoop = L->getParentLoop()) {
187for (
auto *
G : GuardBlocks) {
188 ParentLoop->addBasicBlockToLoop(
G, LI);
190 ParentLoop->verifyLoop();
193#if defined(EXPENSIVE_CHECKS) 195#endif// EXPENSIVE_CHECKS 204for (
auto *L :
Loops) {
211bool UnifyLoopExitsLegacyPass::runOnFunction(
Function &
F) {
212LLVM_DEBUG(
dbgs() <<
"===== Unifying loop exits in function " <<
F.getName()
214auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
215auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
226LLVM_DEBUG(
dbgs() <<
"===== Unifying loop exits in function " <<
F.getName()
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static bool runImpl(Function &F, const TargetLowering &TLI)
This file implements a map that provides insertion order iteration.
uint64_t IntrinsicInst * II
PowerPC TLS Dynamic Call Fixup
#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())
unify loop Fixup each natural loop to have a single exit block
static bool unifyLoopExits(DominatorTree &DT, LoopInfo &LI, Loop *L)
unify loop Fixup each natural loop to have a single exit static false void restoreSSA(const DominatorTree &DT, const Loop *L, SmallVectorImpl< BasicBlock * > &Incoming, BasicBlock *LoopExitBlock)
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 the ControlFlowHub."))
static bool runImpl(LoopInfo &LI, DominatorTree &DT)
A container for analyses that lazily runs them and caches their results.
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 & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
LLVM Basic Block Representation.
Analysis pass which computes a DominatorTree.
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
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.
Analysis pass that exposes the LoopInfo for a function.
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...
The legacy pass manager's analysis pass to compute loop information.
Represents a single loop in the control flow graph.
This class implements a map that also provides access to all stored values in a deterministic order.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition 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...
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
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 preserve()
Mark an analysis as preserved.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
StringRef getName() const
Return a constant reference to the value's name.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
bool hasOnlySimpleTerminator(const Function &F)
void initializeUnifyLoopExitsLegacyPassPass(PassRegistry &)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
FunctionPass * createUnifyLoopExitsPass()
Given a set of branch descriptors [BB, Succ0, Succ1], create a "hub" such that the control flow from ...
BasicBlock * finalize(DomTreeUpdater *DTU, SmallVectorImpl< BasicBlock * > &GuardBlocks, const StringRef Prefix, std::optional< unsigned > MaxControlFlowBooleans=std::nullopt)
void addBranch(BasicBlock *BB, BasicBlock *Succ0, BasicBlock *Succ1)
Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...
