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