LLVM  7.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"
30 #include "llvm/IR/Dominators.h"
31 #include "llvm/Transforms/Scalar.h"
33 #include "llvm/Transforms/Utils.h"
37 using namespace llvm;
38 
39 #define DEBUG_TYPE "loop-simplifycfg"
40 
41 static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI,
42  ScalarEvolution &SE) {
43  bool Changed = false;
44  // Copy blocks into a temporary array to avoid iterator invalidation issues
45  // as we remove them.
47 
48  for (auto &Block : Blocks) {
49  // Attempt to merge blocks in the trivial case. Don't modify blocks which
50  // belong to other loops.
51  BasicBlock *Succ = cast_or_null<BasicBlock>(Block);
52  if (!Succ)
53  continue;
54 
55  BasicBlock *Pred = Succ->getSinglePredecessor();
56  if (!Pred || !Pred->getSingleSuccessor() || LI.getLoopFor(Pred) != &L)
57  continue;
58 
59  // Merge Succ into Pred and delete it.
60  MergeBlockIntoPredecessor(Succ, &DT, &LI);
61 
62  SE.forgetLoop(&L);
63  Changed = true;
64  }
65 
66  return Changed;
67 }
68 
71  LPMUpdater &) {
72  if (!simplifyLoopCFG(L, AR.DT, AR.LI, AR.SE))
73  return PreservedAnalyses::all();
74 
76 }
77 
78 namespace {
79 class LoopSimplifyCFGLegacyPass : public LoopPass {
80 public:
81  static char ID; // Pass ID, replacement for typeid
82  LoopSimplifyCFGLegacyPass() : LoopPass(ID) {
84  }
85 
86  bool runOnLoop(Loop *L, LPPassManager &) override {
87  if (skipLoop(L))
88  return false;
89 
90  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
91  LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
92  ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
93  return simplifyLoopCFG(*L, DT, LI, SE);
94  }
95 
96  void getAnalysisUsage(AnalysisUsage &AU) const override {
99  }
100 };
101 }
102 
104 INITIALIZE_PASS_BEGIN(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
105  "Simplify loop CFG", false, false)
107 INITIALIZE_PASS_END(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
108  "Simplify loop CFG", false, false)
109 
111  return new LoopSimplifyCFGLegacyPass();
112 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
bool MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemoryDependenceResults *MemDep=nullptr, DeferredDominance *DDT=nullptr)
Attempts to merge a block into its predecessor, if possible.
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.
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.
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...
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
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
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:262
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:142
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:235
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
Represent the analysis usage information of a pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
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...
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:861
Pass * createLoopSimplifyCFGPass()
loop Simplify loop CFG
void initializeLoopSimplifyCFGLegacyPassPass(PassRegistry &)
void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
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:1226
static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI, ScalarEvolution &SE)
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
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