LLVM  16.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"
27 #include "llvm/Transforms/Utils.h"
29 
30 #define DEBUG_TYPE "unify-loop-exits"
31 
32 using namespace llvm;
33 
35  "max-booleans-in-control-flow-hub", cl::init(32), cl::Hidden,
36  cl::desc("Set the maximum number of outgoing blocks for using a boolean "
37  "value to record the exiting block in CreateControlFlowHub."));
38 
39 namespace {
40 struct UnifyLoopExitsLegacyPass : public FunctionPass {
41  static char ID;
42  UnifyLoopExitsLegacyPass() : FunctionPass(ID) {
44  }
45 
46  void getAnalysisUsage(AnalysisUsage &AU) const override {
53  }
54 
55  bool runOnFunction(Function &F) override;
56 };
57 } // namespace
58 
60 
62  return new UnifyLoopExitsLegacyPass();
63 }
64 
65 INITIALIZE_PASS_BEGIN(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 INITIALIZE_PASS_DEPENDENCY(LowerSwitchLegacyPass)
71 INITIALIZE_PASS_END(UnifyLoopExitsLegacyPass, "unify-loop-exits",
72  "Fixup each natural loop to have a single exit block",
73  false /* Only looks at CFG */, false /* Analysis Pass */)
74 
75 // The current transform introduces new control flow paths which may break the
76 // SSA requirement that every def must dominate all its uses. For example,
77 // consider a value D defined inside the loop that is used by some instruction
78 // U outside the loop. It follows that D dominates U, since the original
79 // program has valid SSA form. After merging the exits, all paths from D to U
80 // now flow through the unified exit block. In addition, there may be other
81 // paths that do not pass through D, but now reach the unified exit
82 // block. Thus, D no longer dominates U.
83 //
84 // Restore the dominance by creating a phi for each such D at the new unified
85 // loop exit. But when doing this, ignore any uses U that are in the new unified
86 // loop exit, since those were introduced specially when the block was created.
87 //
88 // The use of SSAUpdater seems like overkill for this operation. The location
89 // for creating the new PHI is well-known, and also the set of incoming blocks
90 // to the new PHI.
91 static void restoreSSA(const DominatorTree &DT, const Loop *L,
92  const SetVector<BasicBlock *> &Incoming,
93  BasicBlock *LoopExitBlock) {
94  using InstVector = SmallVector<Instruction *, 8>;
96  IIMap ExternalUsers;
97  for (auto *BB : L->blocks()) {
98  for (auto &I : *BB) {
99  for (auto &U : I.uses()) {
100  auto UserInst = cast<Instruction>(U.getUser());
101  auto UserBlock = UserInst->getParent();
102  if (UserBlock == LoopExitBlock)
103  continue;
104  if (L->contains(UserBlock))
105  continue;
106  LLVM_DEBUG(dbgs() << "added ext use for " << I.getName() << "("
107  << BB->getName() << ")"
108  << ": " << UserInst->getName() << "("
109  << UserBlock->getName() << ")"
110  << "\n");
111  ExternalUsers[&I].push_back(UserInst);
112  }
113  }
114  }
115 
116  for (auto II : ExternalUsers) {
117  // For each Def used outside the loop, create NewPhi in
118  // LoopExitBlock. NewPhi receives Def only along exiting blocks that
119  // dominate it, while the remaining values are undefined since those paths
120  // didn't exist in the original CFG.
121  auto Def = II.first;
122  LLVM_DEBUG(dbgs() << "externally used: " << Def->getName() << "\n");
123  auto NewPhi =
124  PHINode::Create(Def->getType(), Incoming.size(),
125  Def->getName() + ".moved", &LoopExitBlock->front());
126  for (auto *In : Incoming) {
127  LLVM_DEBUG(dbgs() << "predecessor " << In->getName() << ": ");
128  if (Def->getParent() == In || DT.dominates(Def, In)) {
129  LLVM_DEBUG(dbgs() << "dominated\n");
130  NewPhi->addIncoming(Def, In);
131  } else {
132  LLVM_DEBUG(dbgs() << "not dominated\n");
133  NewPhi->addIncoming(UndefValue::get(Def->getType()), In);
134  }
135  }
136 
137  LLVM_DEBUG(dbgs() << "external users:");
138  for (auto *U : II.second) {
139  LLVM_DEBUG(dbgs() << " " << U->getName());
140  U->replaceUsesOfWith(Def, NewPhi);
141  }
142  LLVM_DEBUG(dbgs() << "\n");
143  }
144 }
145 
146 static bool unifyLoopExits(DominatorTree &DT, LoopInfo &LI, Loop *L) {
147  // To unify the loop exits, we need a list of the exiting blocks as
148  // well as exit blocks. The functions for locating these lists both
149  // traverse the entire loop body. It is more efficient to first
150  // locate the exiting blocks and then examine their successors to
151  // locate the exit blocks.
152  SetVector<BasicBlock *> ExitingBlocks;
154 
155  // We need SetVectors, but the Loop API takes a vector, so we use a temporary.
157  L->getExitingBlocks(Temp);
158  for (auto *BB : Temp) {
159  ExitingBlocks.insert(BB);
160  for (auto *S : successors(BB)) {
161  auto SL = LI.getLoopFor(S);
162  // A successor is not an exit if it is directly or indirectly in the
163  // current loop.
164  if (SL == L || L->contains(SL))
165  continue;
166  Exits.insert(S);
167  }
168  }
169 
170  LLVM_DEBUG(
171  dbgs() << "Found exit blocks:";
172  for (auto Exit : Exits) {
173  dbgs() << " " << Exit->getName();
174  }
175  dbgs() << "\n";
176 
177  dbgs() << "Found exiting blocks:";
178  for (auto EB : ExitingBlocks) {
179  dbgs() << " " << EB->getName();
180  }
181  dbgs() << "\n";);
182 
183  if (Exits.size() <= 1) {
184  LLVM_DEBUG(dbgs() << "loop does not have multiple exits; nothing to do\n");
185  return false;
186  }
187 
188  SmallVector<BasicBlock *, 8> GuardBlocks;
190  auto LoopExitBlock =
191  CreateControlFlowHub(&DTU, GuardBlocks, ExitingBlocks, Exits, "loop.exit",
192  MaxBooleansInControlFlowHub.getValue());
193 
194  restoreSSA(DT, L, ExitingBlocks, LoopExitBlock);
195 
196 #if defined(EXPENSIVE_CHECKS)
198 #else
200 #endif // EXPENSIVE_CHECKS
201  L->verifyLoop();
202 
203  // The guard blocks were created outside the loop, so they need to become
204  // members of the parent loop.
205  if (auto ParentLoop = L->getParentLoop()) {
206  for (auto *G : GuardBlocks) {
207  ParentLoop->addBasicBlockToLoop(G, LI);
208  }
209  ParentLoop->verifyLoop();
210  }
211 
212 #if defined(EXPENSIVE_CHECKS)
213  LI.verify(DT);
214 #endif // EXPENSIVE_CHECKS
215 
216  return true;
217 }
218 
219 static bool runImpl(LoopInfo &LI, DominatorTree &DT) {
220 
221  bool Changed = false;
222  auto Loops = LI.getLoopsInPreorder();
223  for (auto *L : Loops) {
224  LLVM_DEBUG(dbgs() << "Loop: " << L->getHeader()->getName() << " (depth: "
225  << LI.getLoopDepth(L->getHeader()) << ")\n");
226  Changed |= unifyLoopExits(DT, LI, L);
227  }
228  return Changed;
229 }
230 
232  LLVM_DEBUG(dbgs() << "===== Unifying loop exits in function " << F.getName()
233  << "\n");
234  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
235  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
236 
237  return runImpl(LI, DT);
238 }
239 
240 namespace llvm {
241 
244  auto &LI = AM.getResult<LoopAnalysis>(F);
245  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
246 
247  if (!runImpl(LI, DT))
248  return PreservedAnalyses::all();
250  PA.preserve<LoopAnalysis>();
252  return PA;
253 }
254 } // 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:146
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
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:774
llvm::Function
Definition: Function.h:60
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:139
Loops
Hexagon Hardware Loops
Definition: HexagonHardwareLoops.cpp:374
llvm::SmallVector< Instruction *, 8 >
llvm::LoopInfoBase::verify
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
Definition: LoopInfoImpl.h:699
MapVector.h
DomTreeUpdater.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:140
to
Should compile to
Definition: README.txt:449
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1293
llvm::CreateControlFlowHub
BasicBlock * CreateControlFlowHub(DomTreeUpdater *DTU, SmallVectorImpl< BasicBlock * > &GuardBlocks, const SetVector< BasicBlock * > &Predecessors, const SetVector< BasicBlock * > &Successors, const StringRef Prefix, Optional< unsigned > MaxControlFlowBooleans=None)
Given a set of incoming and outgoing blocks, create a "hub" such that every edge from an incoming blo...
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 &)
CommandLine.h
llvm::LoopBase::getParentLoop
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Definition: LoopInfo.h:114
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
Constants.h
runImpl
static bool runImpl(LoopInfo &LI, DominatorTree &DT)
Definition: UnifyLoopExits.cpp:219
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:302
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:302
llvm::createUnifyLoopExitsPass
FunctionPass * createUnifyLoopExitsPass()
Definition: UnifyLoopExits.cpp:61
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:1713
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
llvm::cl::opt
Definition: CommandLine.h:1412
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:992
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:447
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
exits
unify loop exits
Definition: UnifyLoopExits.cpp:71
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:999
llvm::LoopInfo
Definition: LoopInfo.h:1108
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:72
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:91
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:587
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:85
llvm::UnifyLoopExitsPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: UnifyLoopExits.cpp:242
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:2740
UnifyLoopExits.h
MaxBooleansInControlFlowHub
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."))
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:279
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::cl::desc
Definition: CommandLine.h:413
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:1268