1 //===- InstSimplifyPass.cpp -----------------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "llvm/Transforms/Scalar/InstSimplifyPass.h" 10 #include "llvm/ADT/DepthFirstIterator.h" 11 #include "llvm/ADT/SmallPtrSet.h" 12 #include "llvm/ADT/Statistic.h" 13 #include "llvm/Analysis/AssumptionCache.h" 14 #include "llvm/Analysis/InstructionSimplify.h" 15 #include "llvm/Analysis/OptimizationRemarkEmitter.h" 16 #include "llvm/Analysis/TargetLibraryInfo.h" 17 #include "llvm/IR/DataLayout.h" 18 #include "llvm/IR/Dominators.h" 19 #include "llvm/IR/Function.h" 20 #include "llvm/IR/Type.h" 21 #include "llvm/Pass.h" 22 #include "llvm/Transforms/Utils.h" 23 #include "llvm/Transforms/Utils/Local.h" 24 using namespace llvm; 25 26 #define DEBUG_TYPE "instsimplify" 27 28 STATISTIC(NumSimplified, "Number of redundant instructions removed"); 29 30 static bool runImpl(Function &F, const SimplifyQuery &SQ, 31 OptimizationRemarkEmitter *ORE) { 32 SmallPtrSet<const Instruction *, 8> S1, S2, *ToSimplify = &S1, *Next = &S2; 33 bool Changed = false; 34 35 do { 36 for (BasicBlock *BB : depth_first(&F.getEntryBlock())) { 37 // Here be subtlety: the iterator must be incremented before the loop 38 // body (not sure why), so a range-for loop won't work here. 39 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) { 40 Instruction *I = &*BI++; 41 // The first time through the loop ToSimplify is empty and we try to 42 // simplify all instructions. On later iterations ToSimplify is not 43 // empty and we only bother simplifying instructions that are in it. 44 if (!ToSimplify->empty() && !ToSimplify->count(I)) 45 continue; 46 47 // Don't waste time simplifying unused instructions. 48 if (!I->use_empty()) { 49 if (Value *V = SimplifyInstruction(I, SQ, ORE)) { 50 // Mark all uses for resimplification next time round the loop. 51 for (User *U : I->users()) 52 Next->insert(cast<Instruction>(U)); 53 I->replaceAllUsesWith(V); 54 ++NumSimplified; 55 Changed = true; 56 } 57 } 58 if (RecursivelyDeleteTriviallyDeadInstructions(I, SQ.TLI)) { 59 // RecursivelyDeleteTriviallyDeadInstruction can remove more than one 60 // instruction, so simply incrementing the iterator does not work. 61 // When instructions get deleted re-iterate instead. 62 BI = BB->begin(); 63 BE = BB->end(); 64 Changed = true; 65 } 66 } 67 } 68 69 // Place the list of instructions to simplify on the next loop iteration 70 // into ToSimplify. 71 std::swap(ToSimplify, Next); 72 Next->clear(); 73 } while (!ToSimplify->empty()); 74 75 return Changed; 76 } 77 78 namespace { 79 struct InstSimplifyLegacyPass : public FunctionPass { 80 static char ID; // Pass identification, replacement for typeid 81 InstSimplifyLegacyPass() : FunctionPass(ID) { 82 initializeInstSimplifyLegacyPassPass(*PassRegistry::getPassRegistry()); 83 } 84 85 void getAnalysisUsage(AnalysisUsage &AU) const override { 86 AU.setPreservesCFG(); 87 AU.addRequired<DominatorTreeWrapperPass>(); 88 AU.addRequired<AssumptionCacheTracker>(); 89 AU.addRequired<TargetLibraryInfoWrapperPass>(); 90 AU.addRequired<OptimizationRemarkEmitterWrapperPass>(); 91 } 92 93 /// runOnFunction - Remove instructions that simplify. 94 bool runOnFunction(Function &F) override { 95 if (skipFunction(F)) 96 return false; 97 98 const DominatorTree *DT = 99 &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 100 const TargetLibraryInfo *TLI = 101 &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(); 102 AssumptionCache *AC = 103 &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); 104 OptimizationRemarkEmitter *ORE = 105 &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE(); 106 const DataLayout &DL = F.getParent()->getDataLayout(); 107 const SimplifyQuery SQ(DL, TLI, DT, AC); 108 return runImpl(F, SQ, ORE); 109 } 110 }; 111 } // namespace 112 113 char InstSimplifyLegacyPass::ID = 0; 114 INITIALIZE_PASS_BEGIN(InstSimplifyLegacyPass, "instsimplify", 115 "Remove redundant instructions", false, false) 116 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 117 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 118 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) 119 INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass) 120 INITIALIZE_PASS_END(InstSimplifyLegacyPass, "instsimplify", 121 "Remove redundant instructions", false, false) 122 123 // Public interface to the simplify instructions pass. 124 FunctionPass *llvm::createInstSimplifyLegacyPass() { 125 return new InstSimplifyLegacyPass(); 126 } 127 128 PreservedAnalyses InstSimplifyPass::run(Function &F, 129 FunctionAnalysisManager &AM) { 130 auto &DT = AM.getResult<DominatorTreeAnalysis>(F); 131 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F); 132 auto &AC = AM.getResult<AssumptionAnalysis>(F); 133 auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F); 134 const DataLayout &DL = F.getParent()->getDataLayout(); 135 const SimplifyQuery SQ(DL, &TLI, &DT, &AC); 136 bool Changed = runImpl(F, SQ, &ORE); 137 if (!Changed) 138 return PreservedAnalyses::all(); 139 140 PreservedAnalyses PA; 141 PA.preserveSet<CFGAnalyses>(); 142 return PA; 143 } 144