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/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/LoopPassManager.h" 28#include "llvm/Analysis/ScalarEvolution.h" 29#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" 30#include "llvm/Analysis/TargetTransformInfo.h" 31#include "llvm/IR/Dominators.h" 32#include "llvm/Transforms/Scalar.h" 33#include "llvm/Transforms/Utils/Local.h" 34#include "llvm/Transforms/Utils/LoopUtils.h" 35using namespace llvm; 36 37#define DEBUG_TYPE "loop-simplifycfg" 38 39static 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. 43 SmallVector<WeakVH, 16> Blocks(L.blocks()); 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 67PreservedAnalyses LoopSimplifyCFGPass::run(Loop &L, AnalysisManager<Loop> &AM) { 68 const auto &FAM = 69 AM.getResult<FunctionAnalysisManagerLoopProxy>(L).getManager(); 70 Function *F = L.getHeader()->getParent(); 71 72 auto *LI = FAM.getCachedResult<LoopAnalysis>(*F); 73 auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(*F); 74 assert((LI && DT) && "Analyses for LoopSimplifyCFG not available"); 75 76 if (!simplifyLoopCFG(L, *DT, *LI)) 77 return PreservedAnalyses::all(); 78 return getLoopPassPreservedAnalyses(); 79} 80 81namespace { 82class LoopSimplifyCFGLegacyPass : public LoopPass { 83public: 84 static char ID; // Pass ID, replacement for typeid 85 LoopSimplifyCFGLegacyPass() : LoopPass(ID) { 86 initializeLoopSimplifyCFGLegacyPassPass(*PassRegistry::getPassRegistry()); 87 } 88 89 bool runOnLoop(Loop *L, LPPassManager &) override { 90 if (skipLoop(L)) 91 return false; 92 93 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 94 LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 95 return simplifyLoopCFG(*L, DT, LI); 96 } 97 98 void getAnalysisUsage(AnalysisUsage &AU) const override { 99 AU.addPreserved<DependenceAnalysisWrapperPass>(); 100 getLoopAnalysisUsage(AU); 101 } 102}; 103} 104 105char LoopSimplifyCFGLegacyPass::ID = 0; 106INITIALIZE_PASS_BEGIN(LoopSimplifyCFGLegacyPass, "loop-simplifycfg", 107 "Simplify loop CFG", false, false) 108INITIALIZE_PASS_DEPENDENCY(LoopPass) 109INITIALIZE_PASS_END(LoopSimplifyCFGLegacyPass, "loop-simplifycfg", 110 "Simplify loop CFG", false, false) 111 112Pass *llvm::createLoopSimplifyCFGPass() { 113 return new LoopSimplifyCFGLegacyPass(); 114} 115