30#define DEBUG_TYPE "unify-loop-exits"
36 cl::desc(
"Set the maximum number of outgoing blocks for using a boolean "
37 "value to record the exiting block in CreateControlFlowHub."));
59char UnifyLoopExitsLegacyPass::ID = 0;
62 return new UnifyLoopExitsLegacyPass();
66 "Fixup each natural loop to have a single exit block",
97 for (
auto *BB : L->blocks()) {
99 for (
auto &U :
I.uses()) {
100 auto UserInst = cast<Instruction>(U.getUser());
101 auto UserBlock = UserInst->getParent();
102 if (UserBlock == LoopExitBlock)
104 if (L->contains(UserBlock))
107 << BB->getName() <<
")"
108 <<
": " << UserInst->getName() <<
"("
109 << UserBlock->getName() <<
")"
111 ExternalUsers[&
I].push_back(UserInst);
116 for (
const auto &II : ExternalUsers) {
122 LLVM_DEBUG(
dbgs() <<
"externally used: " << Def->getName() <<
"\n");
125 Def->getName() +
".moved", &LoopExitBlock->front());
126 for (
auto *In : Incoming) {
128 if (Def->getParent() == In || DT.dominates(Def, In)) {
130 NewPhi->addIncoming(Def, In);
138 for (
auto *U : II.second) {
140 U->replaceUsesOfWith(Def, NewPhi);
157 L->getExitingBlocks(Temp);
158 for (
auto *BB : Temp) {
164 if (SL == L || L->contains(SL))
171 dbgs() <<
"Found exit blocks:";
172 for (
auto Exit : Exits) {
173 dbgs() <<
" " << Exit->getName();
177 dbgs() <<
"Found exiting blocks:";
178 for (
auto EB : ExitingBlocks) {
179 dbgs() <<
" " << EB->getName();
183 if (Exits.
size() <= 1) {
184 LLVM_DEBUG(
dbgs() <<
"loop does not have multiple exits; nothing to do\n");
194 restoreSSA(DT, L, ExitingBlocks, LoopExitBlock);
196#if defined(EXPENSIVE_CHECKS)
197 assert(DT.
verify(DominatorTree::VerificationLevel::Full));
199 assert(DT.
verify(DominatorTree::VerificationLevel::Fast));
205 if (
auto ParentLoop = L->getParentLoop()) {
206 for (
auto *
G : GuardBlocks) {
207 ParentLoop->addBasicBlockToLoop(
G, LI);
209 ParentLoop->verifyLoop();
212#if defined(EXPENSIVE_CHECKS)
221 bool Changed =
false;
223 for (
auto *L :
Loops) {
224 LLVM_DEBUG(
dbgs() <<
"Loop: " << L->getHeader()->getName() <<
" (depth: "
231bool UnifyLoopExitsLegacyPass::runOnFunction(
Function &
F) {
232 LLVM_DEBUG(
dbgs() <<
"===== Unifying loop exits in function " <<
F.getName()
234 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
235 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
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.
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 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.
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 & addRequiredID(const void *ID)
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.
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.
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...
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.
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="", 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...
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.
A vector that has set insertion semantics.
size_type size() const
Determine the number of elements in the SetVector.
bool insert(const value_type &X)
Insert a new element into the SetVector.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
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.
auto successors(const MachineBasicBlock *BB)
void initializeUnifyLoopExitsLegacyPassPass(PassRegistry &)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
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...