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 #include "llvm/Transforms/Scalar.h" 15 #include "llvm/ADT/STLExtras.h" 16 #include "llvm/ADT/Statistic.h" 17 #include "llvm/Analysis/AssumptionCache.h" 18 #include "llvm/Analysis/InstructionSimplify.h" 19 #include "llvm/Analysis/LoopInfo.h" 20 #include "llvm/Analysis/LoopPass.h" 21 #include "llvm/Analysis/ScalarEvolution.h" 22 #include "llvm/IR/DataLayout.h" 23 #include "llvm/IR/Dominators.h" 24 #include "llvm/IR/Instructions.h" 25 #include "llvm/Support/Debug.h" 26 #include "llvm/Analysis/TargetLibraryInfo.h" 27 #include "llvm/Transforms/Utils/Local.h" 28 using namespace llvm; 29 30 #define DEBUG_TYPE "loop-instsimplify" 31 32 STATISTIC(NumSimplified, "Number of redundant instructions simplified"); 33 34 namespace { 35 class LoopInstSimplify : public LoopPass { 36 public: 37 static char ID; // Pass ID, replacement for typeid 38 LoopInstSimplify() : LoopPass(ID) { 39 initializeLoopInstSimplifyPass(*PassRegistry::getPassRegistry()); 40 } 41 42 bool runOnLoop(Loop*, LPPassManager&) override; 43 44 void getAnalysisUsage(AnalysisUsage &AU) const override { 45 AU.setPreservesCFG(); 46 AU.addRequired<AssumptionCacheTracker>(); 47 AU.addRequired<LoopInfoWrapperPass>(); 48 AU.addRequiredID(LoopSimplifyID); 49 AU.addPreservedID(LoopSimplifyID); 50 AU.addPreservedID(LCSSAID); 51 AU.addPreserved<ScalarEvolutionWrapperPass>(); 52 AU.addRequired<TargetLibraryInfoWrapperPass>(); 53 } 54 }; 55 } 56 57 char LoopInstSimplify::ID = 0; 58 INITIALIZE_PASS_BEGIN(LoopInstSimplify, "loop-instsimplify", 59 "Simplify instructions in loops", false, false) 60 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 61 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) 62 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 63 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) 64 INITIALIZE_PASS_DEPENDENCY(LCSSA) 65 INITIALIZE_PASS_END(LoopInstSimplify, "loop-instsimplify", 66 "Simplify instructions in loops", false, false) 67 68 Pass *llvm::createLoopInstSimplifyPass() { 69 return new LoopInstSimplify(); 70 } 71 72 bool LoopInstSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { 73 if (skipOptnoneFunction(L)) 74 return false; 75 76 DominatorTreeWrapperPass *DTWP = 77 getAnalysisIfAvailable<DominatorTreeWrapperPass>(); 78 DominatorTree *DT = DTWP ? &DTWP->getDomTree() : nullptr; 79 LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 80 const TargetLibraryInfo *TLI = 81 &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(); 82 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache( 83 *L->getHeader()->getParent()); 84 85 SmallVector<BasicBlock*, 8> ExitBlocks; 86 L->getUniqueExitBlocks(ExitBlocks); 87 array_pod_sort(ExitBlocks.begin(), ExitBlocks.end()); 88 89 SmallPtrSet<const Instruction*, 8> S1, S2, *ToSimplify = &S1, *Next = &S2; 90 91 // The bit we are stealing from the pointer represents whether this basic 92 // block is the header of a subloop, in which case we only process its phis. 93 typedef PointerIntPair<BasicBlock*, 1> WorklistItem; 94 SmallVector<WorklistItem, 16> VisitStack; 95 SmallPtrSet<BasicBlock*, 32> Visited; 96 97 bool Changed = false; 98 bool LocalChanged; 99 do { 100 LocalChanged = false; 101 102 VisitStack.clear(); 103 Visited.clear(); 104 105 VisitStack.push_back(WorklistItem(L->getHeader(), false)); 106 107 while (!VisitStack.empty()) { 108 WorklistItem Item = VisitStack.pop_back_val(); 109 BasicBlock *BB = Item.getPointer(); 110 bool IsSubloopHeader = Item.getInt(); 111 const DataLayout &DL = L->getHeader()->getModule()->getDataLayout(); 112 113 // Simplify instructions in the current basic block. 114 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) { 115 Instruction *I = &*BI++; 116 117 // The first time through the loop ToSimplify is empty and we try to 118 // simplify all instructions. On later iterations ToSimplify is not 119 // empty and we only bother simplifying instructions that are in it. 120 if (!ToSimplify->empty() && !ToSimplify->count(I)) 121 continue; 122 123 // Don't bother simplifying unused instructions. 124 if (!I->use_empty()) { 125 Value *V = SimplifyInstruction(I, DL, TLI, DT, &AC); 126 if (V && LI->replacementPreservesLCSSAForm(I, V)) { 127 // Mark all uses for resimplification next time round the loop. 128 for (User *U : I->users()) 129 Next->insert(cast<Instruction>(U)); 130 131 I->replaceAllUsesWith(V); 132 LocalChanged = true; 133 ++NumSimplified; 134 } 135 } 136 bool res = RecursivelyDeleteTriviallyDeadInstructions(I, TLI); 137 if (res) { 138 // RecursivelyDeleteTriviallyDeadInstruction can remove 139 // more than one instruction, so simply incrementing the 140 // iterator does not work. When instructions get deleted 141 // re-iterate instead. 142 BI = BB->begin(); BE = BB->end(); 143 LocalChanged |= res; 144 } 145 146 if (IsSubloopHeader && !isa<PHINode>(I)) 147 break; 148 } 149 150 // Add all successors to the worklist, except for loop exit blocks and the 151 // bodies of subloops. We visit the headers of loops so that we can process 152 // their phis, but we contract the rest of the subloop body and only follow 153 // edges leading back to the original loop. 154 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; 155 ++SI) { 156 BasicBlock *SuccBB = *SI; 157 if (!Visited.insert(SuccBB).second) 158 continue; 159 160 const Loop *SuccLoop = LI->getLoopFor(SuccBB); 161 if (SuccLoop && SuccLoop->getHeader() == SuccBB 162 && L->contains(SuccLoop)) { 163 VisitStack.push_back(WorklistItem(SuccBB, true)); 164 165 SmallVector<BasicBlock*, 8> SubLoopExitBlocks; 166 SuccLoop->getExitBlocks(SubLoopExitBlocks); 167 168 for (unsigned i = 0; i < SubLoopExitBlocks.size(); ++i) { 169 BasicBlock *ExitBB = SubLoopExitBlocks[i]; 170 if (LI->getLoopFor(ExitBB) == L && Visited.insert(ExitBB).second) 171 VisitStack.push_back(WorklistItem(ExitBB, false)); 172 } 173 174 continue; 175 } 176 177 bool IsExitBlock = std::binary_search(ExitBlocks.begin(), 178 ExitBlocks.end(), SuccBB); 179 if (IsExitBlock) 180 continue; 181 182 VisitStack.push_back(WorklistItem(SuccBB, false)); 183 } 184 } 185 186 // Place the list of instructions to simplify on the next loop iteration 187 // into ToSimplify. 188 std::swap(ToSimplify, Next); 189 Next->clear(); 190 191 Changed |= LocalChanged; 192 } while (LocalChanged); 193 194 return Changed; 195 } 196