LLVM  15.0.0git
FixIrreducible.cpp
Go to the documentation of this file.
1 //===- FixIrreducible.cpp - Convert irreducible control-flow into loops ---===//
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 // An irreducible SCC is one which has multiple "header" blocks, i.e., blocks
10 // with control-flow edges incident from outside the SCC. This pass converts a
11 // irreducible SCC into a natural loop by applying the following transformation:
12 //
13 // 1. Collect the set of headers H of the SCC.
14 // 2. Collect the set of predecessors P of these headers. These may be inside as
15 // well as outside the SCC.
16 // 3. Create block N and redirect every edge from set P to set H through N.
17 //
18 // This converts the SCC into a natural loop with N as the header: N is the only
19 // block with edges incident from outside the SCC, and all backedges in the SCC
20 // are incident on N, i.e., for every backedge, the head now dominates the tail.
21 //
22 // INPUT CFG: The blocks A and B form an irreducible loop with two headers.
23 //
24 // Entry
25 // / \
26 // v v
27 // A ----> B
28 // ^ /|
29 // `----' |
30 // v
31 // Exit
32 //
33 // OUTPUT CFG: Edges incident on A and B are now redirected through a
34 // new block N, forming a natural loop consisting of N, A and B.
35 //
36 // Entry
37 // |
38 // v
39 // .---> N <---.
40 // / / \ \
41 // | / \ |
42 // \ v v /
43 // `-- A B --'
44 // |
45 // v
46 // Exit
47 //
48 // The transformation is applied to every maximal SCC that is not already
49 // recognized as a loop. The pass operates on all maximal SCCs found in the
50 // function body outside of any loop, as well as those found inside each loop,
51 // including inside any newly created loops. This ensures that any SCC hidden
52 // inside a maximal SCC is also transformed.
53 //
54 // The actual transformation is handled by function CreateControlFlowHub, which
55 // takes a set of incoming blocks (the predecessors) and outgoing blocks (the
56 // headers). The function also moves every PHINode in an outgoing block to the
57 // hub. Since the hub dominates all the outgoing blocks, each such PHINode
58 // continues to dominate its uses. Since every header in an SCC has at least two
59 // predecessors, every value used in the header (or later) but defined in a
60 // predecessor (or earlier) is represented by a PHINode in a header. Hence the
61 // above handling of PHINodes is sufficient and no further processing is
62 // required to restore SSA.
63 //
64 // Limitation: The pass cannot handle switch statements and indirect
65 // branches. Both must be lowered to plain branches first.
66 //
67 //===----------------------------------------------------------------------===//
68 
70 #include "llvm/ADT/SCCIterator.h"
73 #include "llvm/InitializePasses.h"
74 #include "llvm/Pass.h"
75 #include "llvm/Transforms/Utils.h"
77 
78 #define DEBUG_TYPE "fix-irreducible"
79 
80 using namespace llvm;
81 
82 namespace {
83 struct FixIrreducible : public FunctionPass {
84  static char ID;
85  FixIrreducible() : FunctionPass(ID) {
87  }
88 
89  void getAnalysisUsage(AnalysisUsage &AU) const override {
96  }
97 
98  bool runOnFunction(Function &F) override;
99 };
100 } // namespace
101 
102 char FixIrreducible::ID = 0;
103 
104 FunctionPass *llvm::createFixIrreduciblePass() { return new FixIrreducible(); }
105 
106 INITIALIZE_PASS_BEGIN(FixIrreducible, "fix-irreducible",
107  "Convert irreducible control-flow into natural loops",
108  false /* Only looks at CFG */, false /* Analysis Pass */)
109 INITIALIZE_PASS_DEPENDENCY(LowerSwitchLegacyPass)
113  "Convert irreducible control-flow into natural loops",
114  false /* Only looks at CFG */, false /* Analysis Pass */)
115 
116 // When a new loop is created, existing children of the parent loop may now be
117 // fully inside the new loop. Reconnect these as children of the new loop.
118 static void reconnectChildLoops(LoopInfo &LI, Loop *ParentLoop, Loop *NewLoop,
119  SetVector<BasicBlock *> &Blocks,
120  SetVector<BasicBlock *> &Headers) {
121  auto &CandidateLoops = ParentLoop ? ParentLoop->getSubLoopsVector()
122  : LI.getTopLevelLoopsVector();
123  // The new loop cannot be its own child, and any candidate is a
124  // child iff its header is owned by the new loop. Move all the
125  // children to a new vector.
126  auto FirstChild = std::partition(
127  CandidateLoops.begin(), CandidateLoops.end(), [&](Loop *L) {
128  return L == NewLoop || !Blocks.contains(L->getHeader());
129  });
130  SmallVector<Loop *, 8> ChildLoops(FirstChild, CandidateLoops.end());
131  CandidateLoops.erase(FirstChild, CandidateLoops.end());
132 
133  for (Loop *Child : ChildLoops) {
134  LLVM_DEBUG(dbgs() << "child loop: " << Child->getHeader()->getName()
135  << "\n");
136  // TODO: A child loop whose header is also a header in the current
137  // SCC gets destroyed since its backedges are removed. That may
138  // not be necessary if we can retain such backedges.
139  if (Headers.count(Child->getHeader())) {
140  for (auto BB : Child->blocks()) {
141  if (LI.getLoopFor(BB) != Child)
142  continue;
143  LI.changeLoopFor(BB, NewLoop);
144  LLVM_DEBUG(dbgs() << "moved block from child: " << BB->getName()
145  << "\n");
146  }
147  std::vector<Loop *> GrandChildLoops;
148  std::swap(GrandChildLoops, Child->getSubLoopsVector());
149  for (auto GrandChildLoop : GrandChildLoops) {
150  GrandChildLoop->setParentLoop(nullptr);
151  NewLoop->addChildLoop(GrandChildLoop);
152  }
153  LI.destroy(Child);
154  LLVM_DEBUG(dbgs() << "subsumed child loop (common header)\n");
155  continue;
156  }
157 
158  Child->setParentLoop(nullptr);
159  NewLoop->addChildLoop(Child);
160  LLVM_DEBUG(dbgs() << "added child loop to new loop\n");
161  }
162 }
163 
164 // Given a set of blocks and headers in an irreducible SCC, convert it into a
165 // natural loop. Also insert this new loop at its appropriate place in the
166 // hierarchy of loops.
168  Loop *ParentLoop,
169  SetVector<BasicBlock *> &Blocks,
170  SetVector<BasicBlock *> &Headers) {
171 #ifndef NDEBUG
172  // All headers are part of the SCC
173  for (auto H : Headers) {
174  assert(Blocks.count(H));
175  }
176 #endif
177 
178  SetVector<BasicBlock *> Predecessors;
179  for (auto H : Headers) {
180  for (auto P : predecessors(H)) {
181  Predecessors.insert(P);
182  }
183  }
184 
185  LLVM_DEBUG(
186  dbgs() << "Found predecessors:";
187  for (auto P : Predecessors) {
188  dbgs() << " " << P->getName();
189  }
190  dbgs() << "\n");
191 
192  // Redirect all the backedges through a "hub" consisting of a series
193  // of guard blocks that manage the flow of control from the
194  // predecessors to the headers.
195  SmallVector<BasicBlock *, 8> GuardBlocks;
197  CreateControlFlowHub(&DTU, GuardBlocks, Predecessors, Headers, "irr");
198 #if defined(EXPENSIVE_CHECKS)
200 #else
202 #endif
203 
204  // Create a new loop from the now-transformed cycle
205  auto NewLoop = LI.AllocateLoop();
206  if (ParentLoop) {
207  ParentLoop->addChildLoop(NewLoop);
208  } else {
209  LI.addTopLevelLoop(NewLoop);
210  }
211 
212  // Add the guard blocks to the new loop. The first guard block is
213  // the head of all the backedges, and it is the first to be inserted
214  // in the loop. This ensures that it is recognized as the
215  // header. Since the new loop is already in LoopInfo, the new blocks
216  // are also propagated up the chain of parent loops.
217  for (auto G : GuardBlocks) {
218  LLVM_DEBUG(dbgs() << "added guard block: " << G->getName() << "\n");
219  NewLoop->addBasicBlockToLoop(G, LI);
220  }
221 
222  // Add the SCC blocks to the new loop.
223  for (auto BB : Blocks) {
224  NewLoop->addBlockEntry(BB);
225  if (LI.getLoopFor(BB) == ParentLoop) {
226  LLVM_DEBUG(dbgs() << "moved block from parent: " << BB->getName()
227  << "\n");
228  LI.changeLoopFor(BB, NewLoop);
229  } else {
230  LLVM_DEBUG(dbgs() << "added block from child: " << BB->getName() << "\n");
231  }
232  }
233  LLVM_DEBUG(dbgs() << "header for new loop: "
234  << NewLoop->getHeader()->getName() << "\n");
235 
236  reconnectChildLoops(LI, ParentLoop, NewLoop, Blocks, Headers);
237 
238  NewLoop->verifyLoop();
239  if (ParentLoop) {
240  ParentLoop->verifyLoop();
241  }
242 #if defined(EXPENSIVE_CHECKS)
243  LI.verify(DT);
244 #endif // EXPENSIVE_CHECKS
245 }
246 
247 namespace llvm {
248 // Enable the graph traits required for traversing a Loop body.
249 template <> struct GraphTraits<Loop> : LoopBodyTraits {};
250 } // namespace llvm
251 
252 // Overloaded wrappers to go with the function template below.
253 static BasicBlock *unwrapBlock(BasicBlock *B) { return B; }
254 static BasicBlock *unwrapBlock(LoopBodyTraits::NodeRef &N) { return N.second; }
255 
257  SetVector<BasicBlock *> &Blocks,
258  SetVector<BasicBlock *> &Headers) {
259  createNaturalLoopInternal(LI, DT, nullptr, Blocks, Headers);
260 }
261 
262 static void createNaturalLoop(LoopInfo &LI, DominatorTree &DT, Loop &L,
263  SetVector<BasicBlock *> &Blocks,
264  SetVector<BasicBlock *> &Headers) {
265  createNaturalLoopInternal(LI, DT, &L, Blocks, Headers);
266 }
267 
268 // Convert irreducible SCCs; Graph G may be a Function* or a Loop&.
269 template <class Graph>
270 static bool makeReducible(LoopInfo &LI, DominatorTree &DT, Graph &&G) {
271  bool Changed = false;
272  for (auto Scc = scc_begin(G); !Scc.isAtEnd(); ++Scc) {
273  if (Scc->size() < 2)
274  continue;
276  LLVM_DEBUG(dbgs() << "Found SCC:");
277  for (auto N : *Scc) {
278  auto BB = unwrapBlock(N);
279  LLVM_DEBUG(dbgs() << " " << BB->getName());
280  Blocks.insert(BB);
281  }
282  LLVM_DEBUG(dbgs() << "\n");
283 
284  // Minor optimization: The SCC blocks are usually discovered in an order
285  // that is the opposite of the order in which these blocks appear as branch
286  // targets. This results in a lot of condition inversions in the control
287  // flow out of the new ControlFlowHub, which can be mitigated if the orders
288  // match. So we discover the headers using the reverse of the block order.
289  SetVector<BasicBlock *> Headers;
290  LLVM_DEBUG(dbgs() << "Found headers:");
291  for (auto BB : reverse(Blocks)) {
292  for (const auto P : predecessors(BB)) {
293  // Skip unreachable predecessors.
294  if (!DT.isReachableFromEntry(P))
295  continue;
296  if (!Blocks.count(P)) {
297  LLVM_DEBUG(dbgs() << " " << BB->getName());
298  Headers.insert(BB);
299  break;
300  }
301  }
302  }
303  LLVM_DEBUG(dbgs() << "\n");
304 
305  if (Headers.size() == 1) {
306  assert(LI.isLoopHeader(Headers.front()));
307  LLVM_DEBUG(dbgs() << "Natural loop with a single header: skipped\n");
308  continue;
309  }
310  createNaturalLoop(LI, DT, G, Blocks, Headers);
311  Changed = true;
312  }
313  return Changed;
314 }
315 
317  LLVM_DEBUG(dbgs() << "===== Fix irreducible control-flow in function: "
318  << F.getName() << "\n");
319 
320  bool Changed = false;
321  SmallVector<Loop *, 8> WorkList;
322 
323  LLVM_DEBUG(dbgs() << "visiting top-level\n");
324  Changed |= makeReducible(LI, DT, &F);
325 
326  // Any SCCs reduced are now already in the list of top-level loops, so simply
327  // add them all to the worklist.
328  append_range(WorkList, LI);
329 
330  while (!WorkList.empty()) {
331  auto L = WorkList.pop_back_val();
332  LLVM_DEBUG(dbgs() << "visiting loop with header "
333  << L->getHeader()->getName() << "\n");
334  Changed |= makeReducible(LI, DT, *L);
335  // Any SCCs reduced are now already in the list of child loops, so simply
336  // add them all to the worklist.
337  WorkList.append(L->begin(), L->end());
338  }
339 
340  return Changed;
341 }
342 
344  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
345  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
346  return FixIrreducibleImpl(F, LI, DT);
347 }
348 
351  auto &LI = AM.getResult<LoopAnalysis>(F);
352  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
353  if (!FixIrreducibleImpl(F, LI, DT))
354  return PreservedAnalyses::all();
356  PA.preserve<LoopAnalysis>();
358  return PA;
359 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
SCCIterator.h
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
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
fix
arm execution domain fix
Definition: ARMTargetMachine.cpp:395
Pass.h
llvm::SetVector::size
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:77
llvm::createFixIrreduciblePass
FunctionPass * createFixIrreduciblePass()
Definition: FixIrreducible.cpp:104
llvm::SmallVector< Loop *, 8 >
llvm::LoopInfoBase::verify
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
Definition: LoopInfoImpl.h:689
DomTreeUpdater.h
llvm::FixIrreduciblePass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: FixIrreducible.cpp:349
llvm::LoopInfoBase::changeLoopFor
void changeLoopFor(BlockT *BB, LoopT *L)
Change the top-level loop that contains BB to the specified loop.
Definition: LoopInfo.h:1008
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:380
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1271
irreducible
fix irreducible
Definition: FixIrreducible.cpp:112
reconnectChildLoops
fix Convert irreducible control flow into natural static false void reconnectChildLoops(LoopInfo &LI, Loop *ParentLoop, Loop *NewLoop, SetVector< BasicBlock * > &Blocks, SetVector< BasicBlock * > &Headers)
Definition: FixIrreducible.cpp:118
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(FixIrreducible, "fix-irreducible", "Convert irreducible control-flow into natural loops", false, false) INITIALIZE_PASS_END(FixIrreducible
FixIrreducible.h
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:654
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
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::LoopBodyTraits::NodeRef
std::pair< const Loop *, BasicBlock * > NodeRef
Definition: LoopIterator.h:41
unwrapBlock
static BasicBlock * unwrapBlock(BasicBlock *B)
Definition: FixIrreducible.cpp:253
llvm::SmallVectorImpl::append
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:667
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...
llvm::LoopBase::addChildLoop
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
Definition: LoopInfo.h:395
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::LoopInfoBase::addTopLevelLoop
void addTopLevelLoop(LoopT *New)
This adds the specified loop to the collection of top-level loops.
Definition: LoopInfo.h:1027
false
Definition: StackSlotColoring.cpp:141
makeReducible
static bool makeReducible(LoopInfo &LI, DominatorTree &DT, Graph &&G)
Definition: FixIrreducible.cpp:270
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
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::initializeFixIrreduciblePass
void initializeFixIrreduciblePass(PassRegistry &)
llvm::predecessors
auto predecessors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:30
llvm::DomTreeUpdater
Definition: DomTreeUpdater.h:28
Utils.h
LoopIterator.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
llvm::LoopInfoBase::AllocateLoop
LoopT * AllocateLoop(ArgsTy &&... Args)
Definition: LoopInfo.h:934
llvm::scc_begin
scc_iterator< T > scc_begin(const T &G)
Construct the begin iterator for a deduced graph type T.
Definition: SCCIterator.h:232
into
Clang compiles this into
Definition: README.txt:504
createNaturalLoop
static void createNaturalLoop(LoopInfo &LI, DominatorTree &DT, Function *F, SetVector< BasicBlock * > &Blocks, SetVector< BasicBlock * > &Headers)
Definition: FixIrreducible.cpp:256
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:200
llvm::LoopBodyTraits
Definition: LoopIterator.h:40
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
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
llvm::DominatorTree::isReachableFromEntry
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:335
llvm::SetVector::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
llvm::LoopInfo
Definition: LoopInfo.h:1086
llvm::AnalysisUsage::addPreservedID
AnalysisUsage & addPreservedID(const void *ID)
Definition: PassAnalysisSupport.h:88
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1811
llvm::DomTreeUpdater::UpdateStrategy::Eager
@ Eager
llvm::partition
auto partition(R &&Range, UnaryPredicate P)
Provide wrappers to std::partition which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1718
llvm::LowerSwitchID
char & LowerSwitchID
Definition: LowerSwitch.cpp:577
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::LoopInfoBase::isLoopHeader
bool isLoopHeader(const BlockT *BB) const
Definition: LoopInfo.h:983
H
#define H(x, y, z)
Definition: MD5.cpp:57
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::SetVector::count
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:215
llvm::SetVector::front
const T & front() const
Return the first element of the SetVector.
Definition: SetVector.h:122
FixIrreducibleImpl
static bool FixIrreducibleImpl(Function &F, LoopInfo &LI, DominatorTree &DT)
Definition: FixIrreducible.cpp:316
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
N
#define N
llvm::DominatorTreeBase::verify
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
Definition: GenericDomTree.h:802
createNaturalLoopInternal
static void createNaturalLoopInternal(LoopInfo &LI, DominatorTree &DT, Loop *ParentLoop, SetVector< BasicBlock * > &Blocks, SetVector< BasicBlock * > &Headers)
Definition: FixIrreducible.cpp:167
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::GraphTraits
Definition: GraphTraits.h:37
loops
fix Convert irreducible control flow into natural loops
Definition: FixIrreducible.cpp:113
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