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