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  // Record the exit blocks that branch to the same block.
150 
151  // We need SetVectors, but the Loop API takes a vector, so we use a temporary.
153  L->getExitingBlocks(Temp);
154  for (auto BB : Temp) {
155  ExitingBlocks.insert(BB);
156  for (auto S : successors(BB)) {
157  auto SL = LI.getLoopFor(S);
158  // A successor is not an exit if it is directly or indirectly in the
159  // current loop.
160  if (SL == L || L->contains(SL))
161  continue;
162  Exits.insert(S);
163  // The typical case for reducing the number of guard blocks occurs when
164  // the exit block has a single predecessor and successor.
165  if (S->getSinglePredecessor())
166  if (auto *Succ = S->getSingleSuccessor())
167  CommonSuccs[Succ].insert(S);
168  }
169  }
170 
171  LLVM_DEBUG(
172  dbgs() << "Found exit blocks:";
173  for (auto Exit : Exits) {
174  dbgs() << " " << Exit->getName();
175  }
176  dbgs() << "\n";
177 
178  dbgs() << "Found exiting blocks:";
179  for (auto EB : ExitingBlocks) {
180  dbgs() << " " << EB->getName();
181  }
182  dbgs() << "\n";
183 
184  dbgs() << "Exit blocks with a common successor:\n";
185  for (auto CS : CommonSuccs) {
186  dbgs() << " Succ " << CS.first->getName() << ", exits:";
187  for (auto Exit : CS.second)
188  dbgs() << " " << Exit->getName();
189  dbgs() << "\n";
190  });
191 
192  if (Exits.size() <= 1) {
193  LLVM_DEBUG(dbgs() << "loop does not have multiple exits; nothing to do\n");
194  return false;
195  }
196 
197  // When multiple exit blocks branch to the same block, change the control
198  // flow hub to after the exit blocks rather than before. This reduces the
199  // number of guard blocks needed after the loop.
200  for (auto CS : CommonSuccs) {
201  auto CB = CS.first;
202  auto Preds = CS.second;
203  if (Exits.contains(CB))
204  continue;
205  if (Preds.size() < 2 || Preds.size() == Exits.size())
206  continue;
207  for (auto Exit : Preds) {
208  Exits.remove(Exit);
209  ExitingBlocks.remove(Exit->getSinglePredecessor());
210  ExitingBlocks.insert(Exit);
211  }
212  Exits.insert(CB);
213  }
214 
215  SmallVector<BasicBlock *, 8> GuardBlocks;
217  auto LoopExitBlock = CreateControlFlowHub(&DTU, GuardBlocks, ExitingBlocks,
218  Exits, "loop.exit");
219 
220  restoreSSA(DT, L, ExitingBlocks, LoopExitBlock);
221 
222 #if defined(EXPENSIVE_CHECKS)
224 #else
226 #endif // EXPENSIVE_CHECKS
227  L->verifyLoop();
228 
229  // The guard blocks were created outside the loop, so they need to become
230  // members of the parent loop.
231  if (auto ParentLoop = L->getParentLoop()) {
232  for (auto G : GuardBlocks) {
233  ParentLoop->addBasicBlockToLoop(G, LI);
234  // Ensure the guard block predecessors are in a valid loop. After the
235  // change to the control flow hub for common successors, a guard block
236  // predecessor may not be in a loop or may be in an outer loop.
237  for (auto Pred : predecessors(G)) {
238  auto PredLoop = LI.getLoopFor(Pred);
239  if (!ParentLoop->contains(PredLoop)) {
240  if (PredLoop)
241  LI.removeBlock(Pred);
242  ParentLoop->addBasicBlockToLoop(Pred, LI);
243  }
244  }
245  }
246  ParentLoop->verifyLoop();
247  }
248 
249 #if defined(EXPENSIVE_CHECKS)
250  LI.verify(DT);
251 #endif // EXPENSIVE_CHECKS
252 
253  return true;
254 }
255 
256 static bool runImpl(LoopInfo &LI, DominatorTree &DT) {
257 
258  bool Changed = false;
259  auto Loops = LI.getLoopsInPreorder();
260  for (auto L : Loops) {
261  LLVM_DEBUG(dbgs() << "Loop: " << L->getHeader()->getName() << " (depth: "
262  << LI.getLoopDepth(L->getHeader()) << ")\n");
263  Changed |= unifyLoopExits(DT, LI, L);
264  }
265  return Changed;
266 }
267 
269  LLVM_DEBUG(dbgs() << "===== Unifying loop exits in function " << F.getName()
270  << "\n");
271  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
272  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
273 
274  return runImpl(LI, DT);
275 }
276 
277 namespace llvm {
278 
281  auto &LI = AM.getResult<LoopAnalysis>(F);
282  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
283 
284  if (!runImpl(LI, DT))
285  return PreservedAnalyses::all();
287  PA.preserve<LoopAnalysis>();
289  return PA;
290 }
291 } // 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:546
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:138
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:687
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::LoopInfoBase::removeBlock
void removeBlock(BlockT *BB)
This method completely removes BB from all data structures, including all of the Loop objects it is n...
Definition: LoopInfo.h:1051
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1287
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:256
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::predecessors
auto predecessors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:30
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:1768
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:986
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:993
llvm::LoopInfo
Definition: LoopInfo.h:1102
llvm::MapVector::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: MapVector.h:118
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:575
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::UnifyLoopExitsPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: UnifyLoopExits.cpp:279
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:2693
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:1262
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38