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/SmallPtrSet.h" 11 #include "llvm/ADT/Statistic.h" 12 #include "llvm/Analysis/AssumptionCache.h" 13 #include "llvm/Analysis/InstructionSimplify.h" 14 #include "llvm/Analysis/OptimizationRemarkEmitter.h" 15 #include "llvm/Analysis/TargetLibraryInfo.h" 16 #include "llvm/IR/Dominators.h" 17 #include "llvm/IR/Function.h" 18 #include "llvm/InitializePasses.h" 19 #include "llvm/Pass.h" 20 #include "llvm/Transforms/Scalar.h" 21 #include "llvm/Transforms/Utils/Local.h" 22 23 using namespace llvm; 24 25 #define DEBUG_TYPE "instsimplify" 26 27 STATISTIC(NumSimplified, "Number of redundant instructions removed"); 28 29 static bool runImpl(Function &F, const SimplifyQuery &SQ, 30 OptimizationRemarkEmitter *ORE) { 31 SmallPtrSet<const Instruction *, 8> S1, S2, *ToSimplify = &S1, *Next = &S2; 32 bool Changed = false; 33 34 do { 35 for (BasicBlock &BB : F) { 36 // Unreachable code can take on strange forms that we are not prepared to 37 // handle. For example, an instruction may have itself as an operand. 38 if (!SQ.DT->isReachableFromEntry(&BB)) 39 continue; 40 41 SmallVector<WeakTrackingVH, 8> DeadInstsInBB; 42 for (Instruction &I : BB) { 43 // The first time through the loop, ToSimplify is empty and we try to 44 // simplify all instructions. On later iterations, ToSimplify is not 45 // empty and we only bother simplifying instructions that are in it. 46 if (!ToSimplify->empty() && !ToSimplify->count(&I)) 47 continue; 48 49 // Don't waste time simplifying dead/unused instructions. 50 if (isInstructionTriviallyDead(&I)) { 51 DeadInstsInBB.push_back(&I); 52 Changed = true; 53 } else if (!I.use_empty()) { 54 if (Value *V = simplifyInstruction(&I, SQ, ORE)) { 55 // Mark all uses for resimplification next time round the loop. 56 for (User *U : I.users()) 57 Next->insert(cast<Instruction>(U)); 58 I.replaceAllUsesWith(V); 59 ++NumSimplified; 60 Changed = true; 61 // A call can get simplified, but it may not be trivially dead. 62 if (isInstructionTriviallyDead(&I)) 63 DeadInstsInBB.push_back(&I); 64 } 65 } 66 } 67 RecursivelyDeleteTriviallyDeadInstructions(DeadInstsInBB, SQ.TLI); 68 } 69 70 // Place the list of instructions to simplify on the next loop iteration 71 // into ToSimplify. 72 std::swap(ToSimplify, Next); 73 Next->clear(); 74 } while (!ToSimplify->empty()); 75 76 return Changed; 77 } 78 79 namespace { 80 struct InstSimplifyLegacyPass : public FunctionPass { 81 static char ID; // Pass identification, replacement for typeid 82 InstSimplifyLegacyPass() : FunctionPass(ID) { 83 initializeInstSimplifyLegacyPassPass(*PassRegistry::getPassRegistry()); 84 } 85 86 void getAnalysisUsage(AnalysisUsage &AU) const override { 87 AU.setPreservesCFG(); 88 AU.addRequired<DominatorTreeWrapperPass>(); 89 AU.addRequired<AssumptionCacheTracker>(); 90 AU.addRequired<TargetLibraryInfoWrapperPass>(); 91 AU.addRequired<OptimizationRemarkEmitterWrapperPass>(); 92 } 93 94 /// Remove instructions that simplify. 95 bool runOnFunction(Function &F) override { 96 if (skipFunction(F)) 97 return false; 98 99 const DominatorTree *DT = 100 &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 101 const TargetLibraryInfo *TLI = 102 &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F); 103 AssumptionCache *AC = 104 &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); 105 OptimizationRemarkEmitter *ORE = 106 &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE(); 107 const DataLayout &DL = F.getParent()->getDataLayout(); 108 const SimplifyQuery SQ(DL, TLI, DT, AC); 109 return runImpl(F, SQ, ORE); 110 } 111 }; 112 } // namespace 113 114 char InstSimplifyLegacyPass::ID = 0; 115 INITIALIZE_PASS_BEGIN(InstSimplifyLegacyPass, "instsimplify", 116 "Remove redundant instructions", false, false) 117 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 118 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 119 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) 120 INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass) 121 INITIALIZE_PASS_END(InstSimplifyLegacyPass, "instsimplify", 122 "Remove redundant instructions", false, false) 123 124 // Public interface to the simplify instructions pass. 125 FunctionPass *llvm::createInstSimplifyLegacyPass() { 126 return new InstSimplifyLegacyPass(); 127 } 128 129 PreservedAnalyses InstSimplifyPass::run(Function &F, 130 FunctionAnalysisManager &AM) { 131 auto &DT = AM.getResult<DominatorTreeAnalysis>(F); 132 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F); 133 auto &AC = AM.getResult<AssumptionAnalysis>(F); 134 auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F); 135 const DataLayout &DL = F.getParent()->getDataLayout(); 136 const SimplifyQuery SQ(DL, &TLI, &DT, &AC); 137 bool Changed = runImpl(F, SQ, &ORE); 138 if (!Changed) 139 return PreservedAnalyses::all(); 140 141 PreservedAnalyses PA; 142 PA.preserveSet<CFGAnalyses>(); 143 return PA; 144 } 145