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