LLVM  7.0.0svn
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 //===----------------------------------------------------------------------===//
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/ADT/Statistic.h"
25 #include "llvm/Analysis/LoopInfo.h"
26 #include "llvm/Analysis/LoopPass.h"
31 #include "llvm/IR/Dominators.h"
32 #include "llvm/Transforms/Scalar.h"
34 #include "llvm/Transforms/Utils.h"
36 using namespace llvm;
38 #define DEBUG_TYPE "loop-simplifycfg"
40 static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI) {
41  bool Changed = false;
42  // Copy blocks into a temporary array to avoid iterator invalidation issues
43  // as we remove them.
46  for (auto &Block : Blocks) {
47  // Attempt to merge blocks in the trivial case. Don't modify blocks which
48  // belong to other loops.
49  BasicBlock *Succ = cast_or_null<BasicBlock>(Block);
50  if (!Succ)
51  continue;
53  BasicBlock *Pred = Succ->getSinglePredecessor();
54  if (!Pred || !Pred->getSingleSuccessor() || LI.getLoopFor(Pred) != &L)
55  continue;
57  // Pred is going to disappear, so we need to update the loop info.
58  if (L.getHeader() == Pred)
59  L.moveToHeader(Succ);
60  LI.removeBlock(Pred);
61  MergeBasicBlockIntoOnlyPred(Succ, &DT);
62  Changed = true;
63  }
65  return Changed;
66 }
70  LPMUpdater &) {
71  if (!simplifyLoopCFG(L, AR.DT, AR.LI))
72  return PreservedAnalyses::all();
75 }
77 namespace {
78 class LoopSimplifyCFGLegacyPass : public LoopPass {
79 public:
80  static char ID; // Pass ID, replacement for typeid
81  LoopSimplifyCFGLegacyPass() : LoopPass(ID) {
83  }
85  bool runOnLoop(Loop *L, LPPassManager &) override {
86  if (skipLoop(L))
87  return false;
89  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
90  LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
91  return simplifyLoopCFG(*L, DT, LI);
92  }
94  void getAnalysisUsage(AnalysisUsage &AU) const override {
97  }
98 };
99 }
102 INITIALIZE_PASS_BEGIN(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
103  "Simplify loop CFG", false, false)
105 INITIALIZE_PASS_END(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
106  "Simplify loop CFG", false, false)
109  return new LoopSimplifyCFGLegacyPass();
110 }
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
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Definition: PassSupport.h:51
This is the interface for a SCEV-based alias analysis.
void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, DominatorTree *DT=nullptr, DeferredDominance *DDT=nullptr)
BB is a block with one predecessor and its predecessor is known to have one successor (BB!)...
Definition: Local.cpp:643
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: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:862
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:1223
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)