LLVM  6.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"
35 using namespace llvm;
36 
37 #define DEBUG_TYPE "loop-simplifycfg"
38 
39 static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI) {
40  bool Changed = false;
41  // Copy blocks into a temporary array to avoid iterator invalidation issues
42  // as we remove them.
44 
45  for (auto &Block : Blocks) {
46  // Attempt to merge blocks in the trivial case. Don't modify blocks which
47  // belong to other loops.
48  BasicBlock *Succ = cast_or_null<BasicBlock>(Block);
49  if (!Succ)
50  continue;
51 
52  BasicBlock *Pred = Succ->getSinglePredecessor();
53  if (!Pred || !Pred->getSingleSuccessor() || LI.getLoopFor(Pred) != &L)
54  continue;
55 
56  // Pred is going to disappear, so we need to update the loop info.
57  if (L.getHeader() == Pred)
58  L.moveToHeader(Succ);
59  LI.removeBlock(Pred);
60  MergeBasicBlockIntoOnlyPred(Succ, &DT);
61  Changed = true;
62  }
63 
64  return Changed;
65 }
66 
69  LPMUpdater &) {
70  if (!simplifyLoopCFG(L, AR.DT, AR.LI))
71  return PreservedAnalyses::all();
72 
74 }
75 
76 namespace {
77 class LoopSimplifyCFGLegacyPass : public LoopPass {
78 public:
79  static char ID; // Pass ID, replacement for typeid
80  LoopSimplifyCFGLegacyPass() : LoopPass(ID) {
82  }
83 
84  bool runOnLoop(Loop *L, LPPassManager &) override {
85  if (skipLoop(L))
86  return false;
87 
88  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
89  LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
90  return simplifyLoopCFG(*L, DT, LI);
91  }
92 
93  void getAnalysisUsage(AnalysisUsage &AU) const override {
96  }
97 };
98 }
99 
101 INITIALIZE_PASS_BEGIN(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
102  "Simplify loop CFG", false, false)
104 INITIALIZE_PASS_END(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
105  "Simplify loop CFG", false, false)
106 
108  return new LoopSimplifyCFGLegacyPass();
109 }
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.
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.
void moveToHeader(BlockT *BB)
This method is used to move BB (which must be part of this loop) to be the loop header of the loop (t...
Definition: LoopInfo.h:359
void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, DominatorTree *DT=nullptr)
BB is a block with one predecessor and its predecessor is known to have one successor (BB!)...
Definition: Local.cpp:615
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:678
BlockT * getHeader() const
Definition: LoopInfo.h:100
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:244
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:140
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:217
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:864
Pass * createLoopSimplifyCFGPass()
loop Simplify loop CFG
void initializeLoopSimplifyCFGLegacyPassPass(PassRegistry &)
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:439
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass&#39;s AnalysisUsage.
Definition: LoopUtils.cpp:1023
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
void removeBlock(BlockT *BB)
This method completely removes BB from all data structures, including all of the Loop objects it is n...
Definition: LoopInfo.h:737
static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI)