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/LoopSimplifyCFG.h" 18 #include "llvm/ADT/SmallVector.h" 19 #include "llvm/ADT/Statistic.h" 20 #include "llvm/Analysis/AliasAnalysis.h" 21 #include "llvm/Analysis/AssumptionCache.h" 22 #include "llvm/Analysis/BasicAliasAnalysis.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/Scalar.h" 32 #include "llvm/Transforms/Scalar/LoopPassManager.h" 33 #include "llvm/Transforms/Utils.h" 34 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 35 #include "llvm/Transforms/Utils/Local.h" 36 #include "llvm/Transforms/Utils/LoopUtils.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. 46 SmallVector<WeakTrackingVH, 16> Blocks(L.blocks()); 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 69 PreservedAnalyses LoopSimplifyCFGPass::run(Loop &L, LoopAnalysisManager &AM, 70 LoopStandardAnalysisResults &AR, 71 LPMUpdater &) { 72 if (!simplifyLoopCFG(L, AR.DT, AR.LI, AR.SE)) 73 return PreservedAnalyses::all(); 74 75 return getLoopPassPreservedAnalyses(); 76 } 77 78 namespace { 79 class LoopSimplifyCFGLegacyPass : public LoopPass { 80 public: 81 static char ID; // Pass ID, replacement for typeid 82 LoopSimplifyCFGLegacyPass() : LoopPass(ID) { 83 initializeLoopSimplifyCFGLegacyPassPass(*PassRegistry::getPassRegistry()); 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 { 97 AU.addPreserved<DependenceAnalysisWrapperPass>(); 98 getLoopAnalysisUsage(AU); 99 } 100 }; 101 } 102 103 char LoopSimplifyCFGLegacyPass::ID = 0; 104 INITIALIZE_PASS_BEGIN(LoopSimplifyCFGLegacyPass, "loop-simplifycfg", 105 "Simplify loop CFG", false, false) 106 INITIALIZE_PASS_DEPENDENCY(LoopPass) 107 INITIALIZE_PASS_END(LoopSimplifyCFGLegacyPass, "loop-simplifycfg", 108 "Simplify loop CFG", false, false) 109 110 Pass *llvm::createLoopSimplifyCFGPass() { 111 return new LoopSimplifyCFGLegacyPass(); 112 } 113