LLVM  8.0.0svn
LoopSimplifyCFG.cpp
Go to the documentation of this file.
1 //===--------- LoopSimplifyCFG.cpp - Loop CFG Simplification Pass ---------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements the Loop SimplifyCFG Pass. This pass is responsible for
11 // basic loop CFG cleanup, primarily to assist other loop passes. If you
12 // encounter a noncanonical CFG construct that causes another loop pass to
13 // perform suboptimally, this is the place to fix it up.
14 //
15 //===----------------------------------------------------------------------===//
16 
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/ADT/Statistic.h"
25 #include "llvm/Analysis/LoopInfo.h"
26 #include "llvm/Analysis/LoopPass.h"
32 #include "llvm/IR/DomTreeUpdater.h"
33 #include "llvm/IR/Dominators.h"
34 #include "llvm/Transforms/Scalar.h"
36 #include "llvm/Transforms/Utils.h"
40 using namespace llvm;
41 
42 #define DEBUG_TYPE "loop-simplifycfg"
43 
44 static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI,
45  ScalarEvolution &SE, MemorySSAUpdater *MSSAU) {
46  bool Changed = false;
48  // Copy blocks into a temporary array to avoid iterator invalidation issues
49  // as we remove them.
51 
52  for (auto &Block : Blocks) {
53  // Attempt to merge blocks in the trivial case. Don't modify blocks which
54  // belong to other loops.
55  BasicBlock *Succ = cast_or_null<BasicBlock>(Block);
56  if (!Succ)
57  continue;
58 
59  BasicBlock *Pred = Succ->getSinglePredecessor();
60  if (!Pred || !Pred->getSingleSuccessor() || LI.getLoopFor(Pred) != &L)
61  continue;
62 
63  // Merge Succ into Pred and delete it.
64  MergeBlockIntoPredecessor(Succ, &DTU, &LI, MSSAU);
65 
66  SE.forgetTopmostLoop(&L);
67 
68  Changed = true;
69  }
70 
71  return Changed;
72 }
73 
76  LPMUpdater &) {
79  MSSAU = MemorySSAUpdater(AR.MSSA);
80  if (!simplifyLoopCFG(L, AR.DT, AR.LI, AR.SE,
81  MSSAU.hasValue() ? MSSAU.getPointer() : nullptr))
82  return PreservedAnalyses::all();
83 
85 }
86 
87 namespace {
88 class LoopSimplifyCFGLegacyPass : public LoopPass {
89 public:
90  static char ID; // Pass ID, replacement for typeid
91  LoopSimplifyCFGLegacyPass() : LoopPass(ID) {
93  }
94 
95  bool runOnLoop(Loop *L, LPPassManager &) override {
96  if (skipLoop(L))
97  return false;
98 
99  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
100  LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
101  ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
104  MemorySSA *MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
105  MSSAU = MemorySSAUpdater(MSSA);
106  if (VerifyMemorySSA)
107  MSSA->verifyMemorySSA();
108  }
109  return simplifyLoopCFG(*L, DT, LI, SE,
110  MSSAU.hasValue() ? MSSAU.getPointer() : nullptr);
111  }
112 
113  void getAnalysisUsage(AnalysisUsage &AU) const override {
117  }
120  }
121 };
122 }
123 
125 INITIALIZE_PASS_BEGIN(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
126  "Simplify loop CFG", false, false)
129 INITIALIZE_PASS_END(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
130  "Simplify loop CFG", false, false)
131 
133  return new LoopSimplifyCFGLegacyPass();
134 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI, ScalarEvolution &SE, MemorySSAUpdater *MSSAU)
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition: MemorySSA.cpp:84
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
This header provides classes for managing a pipeline of passes over loops in LLVM IR...
This is the interface for a simple mod/ref and alias analysis over globals.
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr)
Attempts to merge a block into its predecessor, if possible.
Legacy pass manager pass to access dependence information.
The main scalar evolution driver.
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:950
This is the interface for a SCEV-based alias analysis.
loop simplifycfg
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:684
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:700
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:263
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:145
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:236
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
Represent the analysis usage information of a pass.
const T * getPointer() const
Definition: Optional.h:171
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:160
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
void verifyMemorySSA() const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
Definition: MemorySSA.cpp:1701
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
Pass * createLoopSimplifyCFGPass()
loop Simplify loop CFG
void initializeLoopSimplifyCFGLegacyPassPass(PassRegistry &)
bool hasValue() const
Definition: Optional.h:183
INITIALIZE_PASS_BEGIN(LoopSimplifyCFGLegacyPass, "loop-simplifycfg", "Simplify loop CFG", false, false) INITIALIZE_PASS_END(LoopSimplifyCFGLegacyPass
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:459
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass&#39;s AnalysisUsage.
Definition: LoopUtils.cpp:128
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
This is the interface for LLVM&#39;s primary stateless and local alias analysis.
A container for analyses that lazily runs them and caches their results.
This pass exposes codegen information to IR-level passes.
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:156
void forgetTopmostLoop(const Loop *L)
cl::opt< bool > EnableMSSALoopDependency
Enables memory ssa as a dependency for loop passes.