1 //===- LoopInstSimplify.cpp - Loop Instruction 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 pass performs lightweight instruction simplification on loop bodies. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #define DEBUG_TYPE "loop-instsimplify" 15 #include "llvm/Analysis/Dominators.h" 16 #include "llvm/Analysis/InstructionSimplify.h" 17 #include "llvm/Analysis/LoopInfo.h" 18 #include "llvm/Analysis/LoopPass.h" 19 #include "llvm/Support/Debug.h" 20 #include "llvm/Target/TargetData.h" 21 #include "llvm/Transforms/Scalar.h" 22 #include "llvm/Transforms/Utils/Local.h" 23 #include "llvm/ADT/Statistic.h" 24 using namespace llvm; 25 26 STATISTIC(NumSimplified, "Number of redundant instructions simplified"); 27 28 namespace { 29 class LoopInstSimplify : public LoopPass { 30 public: 31 static char ID; // Pass ID, replacement for typeid 32 LoopInstSimplify() : LoopPass(ID) { 33 initializeLoopInstSimplifyPass(*PassRegistry::getPassRegistry()); 34 } 35 36 bool runOnLoop(Loop*, LPPassManager&); 37 38 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 39 AU.setPreservesCFG(); 40 AU.addRequired<LoopInfo>(); 41 AU.addRequiredID(LoopSimplifyID); 42 AU.addPreservedID(LCSSAID); 43 } 44 }; 45 } 46 47 char LoopInstSimplify::ID = 0; 48 INITIALIZE_PASS_BEGIN(LoopInstSimplify, "loop-instsimplify", 49 "Simplify instructions in loops", false, false) 50 INITIALIZE_PASS_DEPENDENCY(DominatorTree) 51 INITIALIZE_PASS_DEPENDENCY(LoopInfo) 52 INITIALIZE_PASS_DEPENDENCY(LCSSA) 53 INITIALIZE_PASS_END(LoopInstSimplify, "loop-instsimplify", 54 "Simplify instructions in loops", false, false) 55 56 Pass* llvm::createLoopInstSimplifyPass() { 57 return new LoopInstSimplify(); 58 } 59 60 bool LoopInstSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { 61 DominatorTree *DT = getAnalysisIfAvailable<DominatorTree>(); 62 LoopInfo *LI = &getAnalysis<LoopInfo>(); 63 const TargetData *TD = getAnalysisIfAvailable<TargetData>(); 64 65 SmallVector<BasicBlock*, 8> ExitBlocks; 66 L->getUniqueExitBlocks(ExitBlocks); 67 array_pod_sort(ExitBlocks.begin(), ExitBlocks.end()); 68 69 SmallPtrSet<const Instruction*, 8> S1, S2, *ToSimplify = &S1, *Next = &S2; 70 71 SmallVector<BasicBlock*, 16> VisitStack; 72 SmallPtrSet<BasicBlock*, 32> Visited; 73 74 bool Changed = false; 75 bool LocalChanged; 76 do { 77 LocalChanged = false; 78 79 VisitStack.clear(); 80 Visited.clear(); 81 82 VisitStack.push_back(L->getHeader()); 83 84 while (!VisitStack.empty()) { 85 BasicBlock *BB = VisitStack.back(); 86 VisitStack.pop_back(); 87 88 // Simplify instructions in the current basic block. 89 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) { 90 Instruction *I = BI++; 91 92 // The first time through the loop ToSimplify is empty and we try to 93 // simplify all instructions. On later iterations ToSimplify is not 94 // empty and we only bother simplifying instructions that are in it. 95 if (!ToSimplify->empty() && !ToSimplify->count(I)) 96 continue; 97 98 // Don't bother simplifying unused instructions. 99 if (!I->use_empty()) { 100 Value *V = SimplifyInstruction(I, TD, DT); 101 if (V && LI->replacementPreservesLCSSAForm(I, V)) { 102 // Mark all uses for resimplification next time round the loop. 103 for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); 104 UI != UE; ++UI) 105 Next->insert(cast<Instruction>(*UI)); 106 107 I->replaceAllUsesWith(V); 108 LocalChanged = true; 109 ++NumSimplified; 110 } 111 } 112 LocalChanged |= RecursivelyDeleteTriviallyDeadInstructions(I); 113 } 114 115 // Add all successors to the worklist, except for loop exit blocks. 116 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; 117 ++SI) { 118 BasicBlock *SuccBB = *SI; 119 bool IsExitBlock = std::binary_search(ExitBlocks.begin(), 120 ExitBlocks.end(), SuccBB); 121 if (!IsExitBlock && Visited.insert(SuccBB)) 122 VisitStack.push_back(SuccBB); 123 } 124 } 125 126 // Place the list of instructions to simplify on the next loop iteration 127 // into ToSimplify. 128 std::swap(ToSimplify, Next); 129 Next->clear(); 130 131 Changed |= LocalChanged; 132 } while (LocalChanged); 133 134 return Changed; 135 } 136