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 : F) { 37 SmallVector<Instruction *, 8> DeadInstsInBB; 38 for (Instruction &I : BB) { 39 // The first time through the loop, ToSimplify is empty and we try to 40 // simplify all instructions. On later iterations, ToSimplify is not 41 // empty and we only bother simplifying instructions that are in it. 42 if (!ToSimplify->empty() && !ToSimplify->count(&I)) 43 continue; 44 45 // Don't waste time simplifying dead/unused instructions. 46 if (isInstructionTriviallyDead(&I)) { 47 DeadInstsInBB.push_back(&I); 48 Changed = true; 49 } else if (!I.use_empty()) { 50 if (Value *V = SimplifyInstruction(&I, SQ, ORE)) { 51 // Mark all uses for resimplification next time round the loop. 52 for (User *U : I.users()) 53 Next->insert(cast<Instruction>(U)); 54 I.replaceAllUsesWith(V); 55 ++NumSimplified; 56 Changed = true; 57 // A call can get simplified, but it may not be trivially dead. 58 if (isInstructionTriviallyDead(&I)) 59 DeadInstsInBB.push_back(&I); 60 } 61 } 62 } 63 RecursivelyDeleteTriviallyDeadInstructions(DeadInstsInBB, SQ.TLI); 64 } 65 66 // Place the list of instructions to simplify on the next loop iteration 67 // into ToSimplify. 68 std::swap(ToSimplify, Next); 69 Next->clear(); 70 } while (!ToSimplify->empty()); 71 72 return Changed; 73 } 74 75 namespace { 76 struct InstSimplifyLegacyPass : public FunctionPass { 77 static char ID; // Pass identification, replacement for typeid 78 InstSimplifyLegacyPass() : FunctionPass(ID) { 79 initializeInstSimplifyLegacyPassPass(*PassRegistry::getPassRegistry()); 80 } 81 82 void getAnalysisUsage(AnalysisUsage &AU) const override { 83 AU.setPreservesCFG(); 84 AU.addRequired<DominatorTreeWrapperPass>(); 85 AU.addRequired<AssumptionCacheTracker>(); 86 AU.addRequired<TargetLibraryInfoWrapperPass>(); 87 AU.addRequired<OptimizationRemarkEmitterWrapperPass>(); 88 } 89 90 /// runOnFunction - Remove instructions that simplify. 91 bool runOnFunction(Function &F) override { 92 if (skipFunction(F)) 93 return false; 94 95 const DominatorTree *DT = 96 &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 97 const TargetLibraryInfo *TLI = 98 &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(); 99 AssumptionCache *AC = 100 &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); 101 OptimizationRemarkEmitter *ORE = 102 &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE(); 103 const DataLayout &DL = F.getParent()->getDataLayout(); 104 const SimplifyQuery SQ(DL, TLI, DT, AC); 105 return runImpl(F, SQ, ORE); 106 } 107 }; 108 } // namespace 109 110 char InstSimplifyLegacyPass::ID = 0; 111 INITIALIZE_PASS_BEGIN(InstSimplifyLegacyPass, "instsimplify", 112 "Remove redundant instructions", false, false) 113 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 114 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 115 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) 116 INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass) 117 INITIALIZE_PASS_END(InstSimplifyLegacyPass, "instsimplify", 118 "Remove redundant instructions", false, false) 119 120 // Public interface to the simplify instructions pass. 121 FunctionPass *llvm::createInstSimplifyLegacyPass() { 122 return new InstSimplifyLegacyPass(); 123 } 124 125 PreservedAnalyses InstSimplifyPass::run(Function &F, 126 FunctionAnalysisManager &AM) { 127 auto &DT = AM.getResult<DominatorTreeAnalysis>(F); 128 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F); 129 auto &AC = AM.getResult<AssumptionAnalysis>(F); 130 auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F); 131 const DataLayout &DL = F.getParent()->getDataLayout(); 132 const SimplifyQuery SQ(DL, &TLI, &DT, &AC); 133 bool Changed = runImpl(F, SQ, &ORE); 134 if (!Changed) 135 return PreservedAnalyses::all(); 136 137 PreservedAnalyses PA; 138 PA.preserveSet<CFGAnalyses>(); 139 return PA; 140 } 141