LLVM  15.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"
22 #include "llvm/Analysis/LoopInfo.h"
23 #include "llvm/IR/Constants.h"
24 #include "llvm/IR/Dominators.h"
25 #include "llvm/InitializePasses.h"
26 #include "llvm/Transforms/Utils.h"
28 
29 #define DEBUG_TYPE "unify-loop-exits"
30 
31 using namespace llvm;
32 
33 namespace {
34 struct UnifyLoopExitsLegacyPass : public FunctionPass {
35  static char ID;
36  UnifyLoopExitsLegacyPass() : FunctionPass(ID) {
38  }
39 
40  void getAnalysisUsage(AnalysisUsage &AU) const override {
47  }
48 
49  bool runOnFunction(Function &F) override;
50 };
51 } // namespace
52 
54 
56  return new UnifyLoopExitsLegacyPass();
57 }
58 
59 INITIALIZE_PASS_BEGIN(UnifyLoopExitsLegacyPass, "unify-loop-exits",
60  "Fixup each natural loop to have a single exit block",
61  false /* Only looks at CFG */, false /* Analysis Pass */)
62 INITIALIZE_PASS_DEPENDENCY(LowerSwitchLegacyPass)
65 INITIALIZE_PASS_END(UnifyLoopExitsLegacyPass, "unify-loop-exits",
66  "Fixup each natural loop to have a single exit block",
67  false /* Only looks at CFG */, false /* Analysis Pass */)
68 
69 // The current transform introduces new control flow paths which may break the
70 // SSA requirement that every def must dominate all its uses. For example,
71 // consider a value D defined inside the loop that is used by some instruction
72 // U outside the loop. It follows that D dominates U, since the original
73 // program has valid SSA form. After merging the exits, all paths from D to U
74 // now flow through the unified exit block. In addition, there may be other
75 // paths that do not pass through D, but now reach the unified exit
76 // block. Thus, D no longer dominates U.
77 //
78 // Restore the dominance by creating a phi for each such D at the new unified
79 // loop exit. But when doing this, ignore any uses U that are in the new unified
80 // loop exit, since those were introduced specially when the block was created.
81 //
82 // The use of SSAUpdater seems like overkill for this operation. The location
83 // for creating the new PHI is well-known, and also the set of incoming blocks
84 // to the new PHI.
85 static void restoreSSA(const DominatorTree &DT, const Loop *L,
86  const SetVector<BasicBlock *> &Incoming,
87  BasicBlock *LoopExitBlock) {
88  using InstVector = SmallVector<Instruction *, 8>;
90  IIMap ExternalUsers;
91  for (auto BB : L->blocks()) {
92  for (auto &I : *BB) {
93  for (auto &U : I.uses()) {
94  auto UserInst = cast<Instruction>(U.getUser());
95  auto UserBlock = UserInst->getParent();
96  if (UserBlock == LoopExitBlock)
97  continue;
98  if (L->contains(UserBlock))
99  continue;
100  LLVM_DEBUG(dbgs() << "added ext use for " << I.getName() << "("
101  << BB->getName() << ")"
102  << ": " << UserInst->getName() << "("
103  << UserBlock->getName() << ")"
104  << "\n");
105  ExternalUsers[&I].push_back(UserInst);
106  }
107  }
108  }
109 
110  for (auto II : ExternalUsers) {
111  // For each Def used outside the loop, create NewPhi in
112  // LoopExitBlock. NewPhi receives Def only along exiting blocks that
113  // dominate it, while the remaining values are undefined since those paths
114  // didn't exist in the original CFG.
115  auto Def = II.first;
116  LLVM_DEBUG(dbgs() << "externally used: " << Def->getName() << "\n");
117  auto NewPhi = PHINode::Create(Def->getType(), Incoming.size(),
118  Def->getName() + ".moved",
119  LoopExitBlock->getTerminator());
120  for (auto In : Incoming) {
121  LLVM_DEBUG(dbgs() << "predecessor " << In->getName() << ": ");
122  if (Def->getParent() == In || DT.dominates(Def, In)) {
123  LLVM_DEBUG(dbgs() << "dominated\n");
124  NewPhi->addIncoming(Def, In);
125  } else {
126  LLVM_DEBUG(dbgs() << "not dominated\n");
127  NewPhi->addIncoming(UndefValue::get(Def->getType()), In);
128  }
129  }
130 
131  LLVM_DEBUG(dbgs() << "external users:");
132  for (auto U : II.second) {
133  LLVM_DEBUG(dbgs() << " " << U->getName());
134  U->replaceUsesOfWith(Def, NewPhi);
135  }
136  LLVM_DEBUG(dbgs() << "\n");
137  }
138 }
139 
140 static bool unifyLoopExits(DominatorTree &DT, LoopInfo &LI, Loop *L) {
141  // To unify the loop exits, we need a list of the exiting blocks as
142  // well as exit blocks. The functions for locating these lists both
143  // traverse the entire loop body. It is more efficient to first
144  // locate the exiting blocks and then examine their successors to
145  // locate the exit blocks.
146  SetVector<BasicBlock *> ExitingBlocks;
148 
149  // We need SetVectors, but the Loop API takes a vector, so we use a temporary.
151  L->getExitingBlocks(Temp);
152  for (auto BB : Temp) {
153  ExitingBlocks.insert(BB);
154  for (auto S : successors(BB)) {
155  auto SL = LI.getLoopFor(S);
156  // A successor is not an exit if it is directly or indirectly in the
157  // current loop.
158  if (SL == L || L->contains(SL))
159  continue;
160  Exits.insert(S);
161  }
162  }
163 
164  LLVM_DEBUG(
165  dbgs() << "Found exit blocks:";
166  for (auto Exit : Exits) {
167  dbgs() << " " << Exit->getName();
168  }
169  dbgs() << "\n";
170 
171  dbgs() << "Found exiting blocks:";
172  for (auto EB : ExitingBlocks) {
173  dbgs() << " " << EB->getName();
174  }
175  dbgs() << "\n";);
176 
177  if (Exits.size() <= 1) {
178  LLVM_DEBUG(dbgs() << "loop does not have multiple exits; nothing to do\n");
179  return false;
180  }
181 
182  SmallVector<BasicBlock *, 8> GuardBlocks;
184  auto LoopExitBlock = CreateControlFlowHub(&DTU, GuardBlocks, ExitingBlocks,
185  Exits, "loop.exit");
186 
187  restoreSSA(DT, L, ExitingBlocks, LoopExitBlock);
188 
189 #if defined(EXPENSIVE_CHECKS)
191 #else
193 #endif // EXPENSIVE_CHECKS
194  L->verifyLoop();
195 
196  // The guard blocks were created outside the loop, so they need to become
197  // members of the parent loop.
198  if (auto ParentLoop = L->getParentLoop()) {
199  for (auto G : GuardBlocks) {
200  ParentLoop->addBasicBlockToLoop(G, LI);
201  }
202  ParentLoop->verifyLoop();
203  }
204 
205 #if defined(EXPENSIVE_CHECKS)
206  LI.verify(DT);
207 #endif // EXPENSIVE_CHECKS
208 
209  return true;
210 }
211 
212 static bool runImpl(LoopInfo &LI, DominatorTree &DT) {
213 
214  bool Changed = false;
215  auto Loops = LI.getLoopsInPreorder();
216  for (auto L : Loops) {
217  LLVM_DEBUG(dbgs() << "Loop: " << L->getHeader()->getName() << " (depth: "
218  << LI.getLoopDepth(L->getHeader()) << ")\n");
219  Changed |= unifyLoopExits(DT, LI, L);
220  }
221  return Changed;
222 }
223 
225  LLVM_DEBUG(dbgs() << "===== Unifying loop exits in function " << F.getName()
226  << "\n");
227  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
228  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
229 
230  return runImpl(LI, DT);
231 }
232 
233 namespace llvm {
234 
237  auto &LI = AM.getResult<LoopAnalysis>(F);
238  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
239 
240  if (!runImpl(LI, DT))
241  return PreservedAnalyses::all();
243  PA.preserve<LoopAnalysis>();
245  return PA;
246 }
247 } // namespace llvm
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
unifyLoopExits
static bool unifyLoopExits(DominatorTree &DT, LoopInfo &LI, Loop *L)
Definition: UnifyLoopExits.cpp:140
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(UnifyLoopExitsLegacyPass, "unify-loop-exits", "Fixup each natural loop to have a single exit block", false, false) INITIALIZE_PASS_END(UnifyLoopExitsLegacyPass
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:780
llvm::Function
Definition: Function.h:60
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:122
Loops
Hexagon Hardware Loops
Definition: HexagonHardwareLoops.cpp:372
llvm::SmallVector< Instruction *, 8 >
llvm::LoopInfoBase::verify
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
Definition: LoopInfoImpl.h:689
MapVector.h
DomTreeUpdater.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
to
Should compile to
Definition: README.txt:449
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1271
llvm::MapVector
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:37
llvm::successors
auto successors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:29
llvm::Sched::Fast
@ Fast
Definition: TargetLowering.h:104
llvm::JumpTable::Full
@ Full
Definition: TargetOptions.h:50
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
loop
Analysis the ScalarEvolution expression for r is< loop > Outside the loop
Definition: README.txt:8
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
a
=0.0 ? 0.0 :(a > 0.0 ? 1.0 :-1.0) a
Definition: README.txt:489
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::initializeUnifyLoopExitsLegacyPassPass
void initializeUnifyLoopExitsLegacyPassPass(PassRegistry &)
llvm::LoopBase::getParentLoop
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Definition: LoopInfo.h:113
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
Constants.h
llvm::CreateControlFlowHub
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...
runImpl
static bool runImpl(LoopInfo &LI, DominatorTree &DT)
Definition: UnifyLoopExits.cpp:212
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
false
Definition: StackSlotColoring.cpp:141
llvm::LoopBase::verifyLoop
void verifyLoop() const
Verify loop structure.
Definition: LoopInfoImpl.h:285
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:302
llvm::createUnifyLoopExitsPass
FunctionPass * createUnifyLoopExitsPass()
Definition: UnifyLoopExits.cpp:55
llvm::LoopBase::getExitingBlocks
void getExitingBlocks(SmallVectorImpl< BlockT * > &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
Definition: LoopInfoImpl.h:33
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1769
llvm::DomTreeUpdater
Definition: DomTreeUpdater.h:28
Utils.h
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
LoopInfo.h
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:200
llvm::tgtok::In
@ In
Definition: TGLexer.h:51
const
aarch64 promote const
Definition: AArch64PromoteConstant.cpp:232
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:970
I
#define I(x, y, z)
Definition: MD5.cpp:58
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
exits
unify loop exits
Definition: UnifyLoopExits.cpp:65
llvm::SetVector::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
llvm::LoopInfoBase::getLoopDepth
unsigned getLoopDepth(const BlockT *BB) const
Return the loop nesting level of the specified block.
Definition: LoopInfo.h:977
llvm::LoopInfo
Definition: LoopInfo.h:1086
llvm::AnalysisUsage::addPreservedID
AnalysisUsage & addPreservedID(const void *ID)
Definition: PassAnalysisSupport.h:88
block
unify loop Fixup each natural loop to have a single exit block
Definition: UnifyLoopExits.cpp:66
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
restoreSSA
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)
Definition: UnifyLoopExits.cpp:85
S
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
Definition: README.txt:210
llvm::DomTreeUpdater::UpdateStrategy::Eager
@ Eager
llvm::LowerSwitchID
char & LowerSwitchID
Definition: LowerSwitch.cpp:577
llvm::LoopInfoBase::getLoopsInPreorder
SmallVector< LoopT *, 4 > getLoopsInPreorder() const
Return all of the loops in the function in preorder across the loop nests, with siblings in forward p...
Definition: LoopInfoImpl.h:577
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::UnifyLoopExitsPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: UnifyLoopExits.cpp:235
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::PHINode::Create
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...
Definition: Instructions.h:2706
UnifyLoopExits.h
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
exit
declare void exit(i32) noreturn nounwind This compiles into
Definition: README.txt:1072
Dominators.h
llvm::DominatorTreeBase::verify
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
Definition: GenericDomTree.h:802
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
llvm::AnalysisUsage::addRequiredID
AnalysisUsage & addRequiredID(const void *ID)
Definition: Pass.cpp:277
BB
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
Definition: README.txt:39
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::SetVector
A vector that has set insertion semantics.
Definition: SetVector.h:40
BasicBlockUtils.h
InitializePasses.h
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1246
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37