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 
17 #include "llvm/Transforms/Scalar.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/ADT/Statistic.h"
20 #include "llvm/Analysis/AliasAnalysis.h"
21 #include "llvm/Analysis/BasicAliasAnalysis.h"
22 #include "llvm/Analysis/AssumptionCache.h"
23 #include "llvm/Analysis/DependenceAnalysis.h"
24 #include "llvm/Analysis/GlobalsModRef.h"
25 #include "llvm/Analysis/LoopInfo.h"
26 #include "llvm/Analysis/LoopPass.h"
27 #include "llvm/Analysis/ScalarEvolution.h"
28 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
29 #include "llvm/Analysis/TargetTransformInfo.h"
30 #include "llvm/IR/Dominators.h"
31 #include "llvm/Transforms/Utils/Local.h"
32 #include "llvm/Transforms/Utils/LoopUtils.h"
33 using namespace llvm;
34 
35 #define DEBUG_TYPE "loop-simplifycfg"
36 
37 namespace {
38 class LoopSimplifyCFG : public LoopPass {
39 public:
40   static char ID; // Pass ID, replacement for typeid
41   LoopSimplifyCFG() : LoopPass(ID) {
42     initializeLoopSimplifyCFGPass(*PassRegistry::getPassRegistry());
43   }
44 
45   bool runOnLoop(Loop *L, LPPassManager &) override;
46 
47   void getAnalysisUsage(AnalysisUsage &AU) const override {
48     AU.addPreserved<DependenceAnalysis>();
49     getLoopAnalysisUsage(AU);
50   }
51 };
52 }
53 
54 char LoopSimplifyCFG::ID = 0;
55 INITIALIZE_PASS_BEGIN(LoopSimplifyCFG, "loop-simplifycfg", "Simplify loop CFG",
56                       false, false)
57 INITIALIZE_PASS_DEPENDENCY(LoopPass)
58 INITIALIZE_PASS_END(LoopSimplifyCFG, "loop-simplifycfg", "Simplify loop CFG",
59                     false, false)
60 
61 Pass *llvm::createLoopSimplifyCFGPass() { return new LoopSimplifyCFG(); }
62 
63 static bool simplifyLoopCFG(Loop *L, DominatorTree *DT, LoopInfo *LI) {
64   bool Changed = false;
65   // Copy blocks into a temporary array to avoid iterator invalidation issues
66   // as we remove them.
67   SmallVector<WeakVH, 16> Blocks(L->blocks());
68 
69   for (auto &Block : Blocks) {
70     // Attempt to merge blocks in the trivial case. Don't modify blocks which
71     // belong to other loops.
72     BasicBlock *Succ = cast_or_null<BasicBlock>(Block);
73     if (!Succ)
74       continue;
75 
76     BasicBlock *Pred = Succ->getSinglePredecessor();
77     if (!Pred || !Pred->getSingleSuccessor() || LI->getLoopFor(Pred) != L)
78       continue;
79 
80     // Pred is going to disappear, so we need to update the loop info.
81     if (L->getHeader() == Pred)
82       L->moveToHeader(Succ);
83     LI->removeBlock(Pred);
84     MergeBasicBlockIntoOnlyPred(Succ, DT);
85     Changed = true;
86   }
87 
88   return Changed;
89 }
90 
91 /// runOnLoop - Perform basic CFG simplifications to assist other loop passes.
92 /// For now, this only attempts to merge blocks in the trivial case.
93 bool LoopSimplifyCFG::runOnLoop(Loop *L, LPPassManager &) {
94   if (skipOptnoneFunction(L))
95     return false;
96 
97   DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
98   LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
99   return simplifyLoopCFG(L, DT, LI);
100 }
101