1 //===------ SimplifyInstructions.cpp - Remove redundant instructions ------===// 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 is a utility pass used for testing the InstructionSimplify analysis. 11 // The analysis is applied to every instruction, and if it simplifies then the 12 // instruction is replaced by the simplification. If you are looking for a pass 13 // that performs serious instruction folding, use the instcombine pass instead. 14 // 15 //===----------------------------------------------------------------------===// 16 17 #include "llvm/Transforms/Utils/SimplifyInstructions.h" 18 #include "llvm/ADT/DepthFirstIterator.h" 19 #include "llvm/ADT/SmallPtrSet.h" 20 #include "llvm/ADT/Statistic.h" 21 #include "llvm/Analysis/AssumptionCache.h" 22 #include "llvm/Analysis/InstructionSimplify.h" 23 #include "llvm/Analysis/TargetLibraryInfo.h" 24 #include "llvm/IR/DataLayout.h" 25 #include "llvm/IR/Dominators.h" 26 #include "llvm/IR/Function.h" 27 #include "llvm/IR/Type.h" 28 #include "llvm/Pass.h" 29 #include "llvm/Transforms/Utils/Local.h" 30 #include "llvm/Transforms/Scalar.h" 31 using namespace llvm; 32 33 #define DEBUG_TYPE "instsimplify" 34 35 STATISTIC(NumSimplified, "Number of redundant instructions removed"); 36 37 static bool runImpl(Function &F, const DominatorTree *DT, const TargetLibraryInfo *TLI, 38 AssumptionCache *AC) { 39 const DataLayout &DL = F.getParent()->getDataLayout(); 40 SmallPtrSet<const Instruction*, 8> S1, S2, *ToSimplify = &S1, *Next = &S2; 41 bool Changed = false; 42 43 do { 44 for (BasicBlock *BB : depth_first(&F.getEntryBlock())) 45 // Here be subtlety: the iterator must be incremented before the loop 46 // body (not sure why), so a range-for loop won't work here. 47 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) { 48 Instruction *I = &*BI++; 49 // The first time through the loop ToSimplify is empty and we try to 50 // simplify all instructions. On later iterations ToSimplify is not 51 // empty and we only bother simplifying instructions that are in it. 52 if (!ToSimplify->empty() && !ToSimplify->count(I)) 53 continue; 54 // Don't waste time simplifying unused instructions. 55 if (!I->use_empty()) 56 if (Value *V = SimplifyInstruction(I, DL, TLI, DT, AC)) { 57 // Mark all uses for resimplification next time round the loop. 58 for (User *U : I->users()) 59 Next->insert(cast<Instruction>(U)); 60 I->replaceAllUsesWith(V); 61 ++NumSimplified; 62 Changed = true; 63 } 64 bool res = RecursivelyDeleteTriviallyDeadInstructions(I, TLI); 65 if (res) { 66 // RecursivelyDeleteTriviallyDeadInstruction can remove 67 // more than one instruction, so simply incrementing the 68 // iterator does not work. When instructions get deleted 69 // re-iterate instead. 70 BI = BB->begin(); BE = BB->end(); 71 Changed |= res; 72 } 73 } 74 75 // Place the list of instructions to simplify on the next loop iteration 76 // into ToSimplify. 77 std::swap(ToSimplify, Next); 78 Next->clear(); 79 } while (!ToSimplify->empty()); 80 81 return Changed; 82 } 83 84 namespace { 85 struct InstSimplifier : public FunctionPass { 86 static char ID; // Pass identification, replacement for typeid 87 InstSimplifier() : FunctionPass(ID) { 88 initializeInstSimplifierPass(*PassRegistry::getPassRegistry()); 89 } 90 91 void getAnalysisUsage(AnalysisUsage &AU) const override { 92 AU.setPreservesCFG(); 93 AU.addRequired<AssumptionCacheTracker>(); 94 AU.addRequired<TargetLibraryInfoWrapperPass>(); 95 } 96 97 /// runOnFunction - Remove instructions that simplify. 98 bool runOnFunction(Function &F) override { 99 if (skipFunction(F)) 100 return false; 101 102 const DominatorTreeWrapperPass *DTWP = 103 getAnalysisIfAvailable<DominatorTreeWrapperPass>(); 104 const DominatorTree *DT = DTWP ? &DTWP->getDomTree() : nullptr; 105 const TargetLibraryInfo *TLI = 106 &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(); 107 AssumptionCache *AC = 108 &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); 109 return runImpl(F, DT, TLI, AC); 110 } 111 }; 112 } 113 114 char InstSimplifier::ID = 0; 115 INITIALIZE_PASS_BEGIN(InstSimplifier, "instsimplify", 116 "Remove redundant instructions", false, false) 117 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 118 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) 119 INITIALIZE_PASS_END(InstSimplifier, "instsimplify", 120 "Remove redundant instructions", false, false) 121 char &llvm::InstructionSimplifierID = InstSimplifier::ID; 122 123 // Public interface to the simplify instructions pass. 124 FunctionPass *llvm::createInstructionSimplifierPass() { 125 return new InstSimplifier(); 126 } 127 128 PreservedAnalyses InstSimplifierPass::run(Function &F, 129 AnalysisManager<Function> &AM) { 130 auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(F); 131 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F); 132 auto &AC = AM.getResult<AssumptionAnalysis>(F); 133 bool Changed = runImpl(F, DT, &TLI, &AC); 134 if (!Changed) 135 return PreservedAnalyses::all(); 136 // FIXME: This should also 'preserve the CFG'. 137 return PreservedAnalyses::none(); 138 } 139
