LLVM  14.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"
21 #include "llvm/Analysis/LoopInfo.h"
22 #include "llvm/IR/Dominators.h"
23 #include "llvm/InitializePasses.h"
24 #include "llvm/Transforms/Utils.h"
26 
27 #define DEBUG_TYPE "unify-loop-exits"
28 
29 using namespace llvm;
30 
31 namespace {
32 struct UnifyLoopExitsLegacyPass : public FunctionPass {
33  static char ID;
34  UnifyLoopExitsLegacyPass() : FunctionPass(ID) {
36  }
37 
38  void getAnalysisUsage(AnalysisUsage &AU) const override {
45  }
46 
47  bool runOnFunction(Function &F) override;
48 };
49 } // namespace
50 
52 
54  return new UnifyLoopExitsLegacyPass();
55 }
56 
57 INITIALIZE_PASS_BEGIN(UnifyLoopExitsLegacyPass, "unify-loop-exits",
58  "Fixup each natural loop to have a single exit block",
59  false /* Only looks at CFG */, false /* Analysis Pass */)
60 INITIALIZE_PASS_DEPENDENCY(LowerSwitchLegacyPass)
63 INITIALIZE_PASS_END(UnifyLoopExitsLegacyPass, "unify-loop-exits",
64  "Fixup each natural loop to have a single exit block",
65  false /* Only looks at CFG */, false /* Analysis Pass */)
66 
67 // The current transform introduces new control flow paths which may break the
68 // SSA requirement that every def must dominate all its uses. For example,
69 // consider a value D defined inside the loop that is used by some instruction
70 // U outside the loop. It follows that D dominates U, since the original
71 // program has valid SSA form. After merging the exits, all paths from D to U
72 // now flow through the unified exit block. In addition, there may be other
73 // paths that do not pass through D, but now reach the unified exit
74 // block. Thus, D no longer dominates U.
75 //
76 // Restore the dominance by creating a phi for each such D at the new unified
77 // loop exit. But when doing this, ignore any uses U that are in the new unified
78 // loop exit, since those were introduced specially when the block was created.
79 //
80 // The use of SSAUpdater seems like overkill for this operation. The location
81 // for creating the new PHI is well-known, and also the set of incoming blocks
82 // to the new PHI.
83 static void restoreSSA(const DominatorTree &DT, const Loop *L,
84  const SetVector<BasicBlock *> &Incoming,
85  BasicBlock *LoopExitBlock) {
86  using InstVector = SmallVector<Instruction *, 8>;
88  IIMap ExternalUsers;
89  for (auto BB : L->blocks()) {
90  for (auto &I : *BB) {
91  for (auto &U : I.uses()) {
92  auto UserInst = cast<Instruction>(U.getUser());
93  auto UserBlock = UserInst->getParent();
94  if (UserBlock == LoopExitBlock)
95  continue;
96  if (L->contains(UserBlock))
97  continue;
98  LLVM_DEBUG(dbgs() << "added ext use for " << I.getName() << "("
99  << BB->getName() << ")"
100  << ": " << UserInst->getName() << "("
101  << UserBlock->getName() << ")"
102  << "\n");
103  ExternalUsers[&I].push_back(UserInst);
104  }
105  }
106  }
107 
108  for (auto II : ExternalUsers) {
109  // For each Def used outside the loop, create NewPhi in
110  // LoopExitBlock. NewPhi receives Def only along exiting blocks that
111  // dominate it, while the remaining values are undefined since those paths
112  // didn't exist in the original CFG.
113  auto Def = II.first;
114  LLVM_DEBUG(dbgs() << "externally used: " << Def->getName() << "\n");
115  auto NewPhi = PHINode::Create(Def->getType(), Incoming.size(),
116  Def->getName() + ".moved",
117  LoopExitBlock->getTerminator());
118  for (auto In : Incoming) {
119  LLVM_DEBUG(dbgs() << "predecessor " << In->getName() << ": ");
120  if (Def->getParent() == In || DT.dominates(Def, In)) {
121  LLVM_DEBUG(dbgs() << "dominated\n");
122  NewPhi->addIncoming(Def, In);
123  } else {
124  LLVM_DEBUG(dbgs() << "not dominated\n");
125  NewPhi->addIncoming(UndefValue::get(Def->getType()), In);
126  }
127  }
128 
129  LLVM_DEBUG(dbgs() << "external users:");
130  for (auto U : II.second) {
131  LLVM_DEBUG(dbgs() << " " << U->getName());
132  U->replaceUsesOfWith(Def, NewPhi);
133  }
134  LLVM_DEBUG(dbgs() << "\n");
135  }
136 }
137 
138 static bool unifyLoopExits(DominatorTree &DT, LoopInfo &LI, Loop *L) {
139  // To unify the loop exits, we need a list of the exiting blocks as
140  // well as exit blocks. The functions for locating these lists both
141  // traverse the entire loop body. It is more efficient to first
142  // locate the exiting blocks and then examine their successors to
143  // locate the exit blocks.
144  SetVector<BasicBlock *> ExitingBlocks;
146 
147  // We need SetVectors, but the Loop API takes a vector, so we use a temporary.
149  L->getExitingBlocks(Temp);
150  for (auto BB : Temp) {
151  ExitingBlocks.insert(BB);
152  for (auto S : successors(BB)) {
153  auto SL = LI.getLoopFor(S);
154  // A successor is not an exit if it is directly or indirectly in the
155  // current loop.
156  if (SL == L || L->contains(SL))
157  continue;
158  Exits.insert(S);
159  }
160  }
161 
162  LLVM_DEBUG(
163  dbgs() << "Found exit blocks:";
164  for (auto Exit : Exits) {
165  dbgs() << " " << Exit->getName();
166  }
167  dbgs() << "\n";
168 
169  dbgs() << "Found exiting blocks:";
170  for (auto EB : ExitingBlocks) {
171  dbgs() << " " << EB->getName();
172  }
173  dbgs() << "\n";);
174 
175  if (Exits.size() <= 1) {
176  LLVM_DEBUG(dbgs() << "loop does not have multiple exits; nothing to do\n");
177  return false;
178  }
179 
180  SmallVector<BasicBlock *, 8> GuardBlocks;
182  auto LoopExitBlock = CreateControlFlowHub(&DTU, GuardBlocks, ExitingBlocks,
183  Exits, "loop.exit");
184 
185  restoreSSA(DT, L, ExitingBlocks, LoopExitBlock);
186 
187 #if defined(EXPENSIVE_CHECKS)
189 #else
191 #endif // EXPENSIVE_CHECKS
192  L->verifyLoop();
193 
194  // The guard blocks were created outside the loop, so they need to become
195  // members of the parent loop.
196  if (auto ParentLoop = L->getParentLoop()) {
197  for (auto G : GuardBlocks) {
198  ParentLoop->addBasicBlockToLoop(G, LI);
199  }
200  ParentLoop->verifyLoop();
201  }
202 
203 #if defined(EXPENSIVE_CHECKS)
204  LI.verify(DT);
205 #endif // EXPENSIVE_CHECKS
206 
207  return true;
208 }
209 
210 static bool runImpl(LoopInfo &LI, DominatorTree &DT) {
211 
212  bool Changed = false;
213  auto Loops = LI.getLoopsInPreorder();
214  for (auto L : Loops) {
215  LLVM_DEBUG(dbgs() << "Loop: " << L->getHeader()->getName() << " (depth: "
216  << LI.getLoopDepth(L->getHeader()) << ")\n");
217  Changed |= unifyLoopExits(DT, LI, L);
218  }
219  return Changed;
220 }
221 
223  LLVM_DEBUG(dbgs() << "===== Unifying loop exits in function " << F.getName()
224  << "\n");
225  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
226  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
227 
228  return runImpl(LI, DT);
229 }
230 
231 namespace llvm {
232 
235  auto &LI = AM.getResult<LoopAnalysis>(F);
236  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
237 
238  if (!runImpl(LI, DT))
239  return PreservedAnalyses::all();
241  PA.preserve<LoopAnalysis>();
243  return PA;
244 }
245 } // namespace llvm
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
unifyLoopExits
static bool unifyLoopExits(DominatorTree &DT, LoopInfo &LI, Loop *L)
Definition: UnifyLoopExits.cpp:138
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
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:783
llvm::Function
Definition: Function.h:62
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:690
MapVector.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
to
Should compile to
Definition: README.txt:449
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1268
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
succ_range successors(Instruction *I)
Definition: CFG.h:262
llvm::Sched::Fast
@ Fast
Definition: TargetLowering.h:105
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:56
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:58
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
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:210
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
false
Definition: StackSlotColoring.cpp:142
llvm::LoopBase::verifyLoop
void verifyLoop() const
Verify loop structure.
Definition: LoopInfoImpl.h:286
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:287
llvm::createUnifyLoopExitsPass
FunctionPass * createUnifyLoopExitsPass()
Definition: UnifyLoopExits.cpp:53
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:34
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1796
llvm::DomTreeUpdater
Definition: DomTreeUpdater.h:28
Utils.h
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:202
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:176
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:967
I
#define I(x, y, z)
Definition: MD5.cpp:59
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
exits
unify loop exits
Definition: UnifyLoopExits.cpp:63
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:974
llvm::LoopInfo
Definition: LoopInfo.h:1083
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:64
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:83
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:570
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:578
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::UnifyLoopExitsPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: UnifyLoopExits.cpp:233
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
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:2690
UnifyLoopExits.h
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
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:44
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
llvm::AnalysisUsage::addRequiredID
AnalysisUsage & addRequiredID(const void *ID)
Definition: Pass.cpp:267
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:1243
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38