LLVM  14.0.0git
InstSimplifyPass.cpp
Go to the documentation of this file.
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 
11 #include "llvm/ADT/SmallPtrSet.h"
12 #include "llvm/ADT/Statistic.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"
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,
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.
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.
67  DeadInstsInBB.push_back(&I);
68  }
69  }
70  }
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) {
88  }
89 
90  void getAnalysisUsage(AnalysisUsage &AU) const override {
91  AU.setPreservesCFG();
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);
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 
119 INITIALIZE_PASS_BEGIN(InstSimplifyLegacyPass, "instsimplify",
120  "Remove redundant instructions", false, false)
125 INITIALIZE_PASS_END(InstSimplifyLegacyPass, "instsimplify",
126  "Remove redundant instructions", false, false)
127 
128 // Public interface to the simplify instructions pass.
130  return new InstSimplifyLegacyPass();
131 }
132 
135  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
136  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
137  auto &AC = AM.getResult<AssumptionAnalysis>(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 
146  PA.preserveSet<CFGAnalyses>();
147  return PA;
148 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::RecursivelyDeleteTriviallyDeadInstructions
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
Definition: Local.cpp:511
AssumptionCache.h
instsimplify
instsimplify
Definition: InstSimplifyPass.cpp:125
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:112
llvm::SimplifyQuery
Definition: InstructionSimplify.h:94
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:769
Scalar.h
llvm::Function
Definition: Function.h:61
Pass.h
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
Statistic.h
llvm::initializeInstSimplifyLegacyPassPass
void initializeInstSimplifyLegacyPassPass(PassRegistry &)
Local.h
OptimizationRemarkEmitter.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
DepthFirstIterator.h
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::User
Definition: User.h:44
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
TargetLibraryInfo.h
false
Definition: StackSlotColoring.cpp:142
llvm::Instruction
Definition: Instruction.h:45
llvm::SimplifyInstruction
Value * SimplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
Definition: InstructionSimplify.cpp:6243
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:281
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
SmallPtrSet.h
Utils.h
Type.h
InstSimplifyPass.h
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::instructions
inst_range instructions(Function *F)
Definition: InstIterator.h:133
llvm::TargetLibraryInfoWrapperPass
Definition: TargetLibraryInfo.h:463
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(InstSimplifyLegacyPass, "instsimplify", "Remove redundant instructions", false, false) INITIALIZE_PASS_END(InstSimplifyLegacyPass
llvm::AssumptionAnalysis
A function analysis which provides an AssumptionCache.
Definition: AssumptionCache.h:169
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::InstSimplifyPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: InstSimplifyPass.cpp:133
llvm::SimplifyQuery::TLI
const TargetLibraryInfo * TLI
Definition: InstructionSimplify.h:96
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::SimplifyQuery::DT
const DominatorTree * DT
Definition: InstructionSimplify.h:97
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:840
llvm::DominatorTree::isReachableFromEntry
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:328
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
llvm::AssumptionCacheTracker
An immutable pass that tracks lazily created AssumptionCache objects.
Definition: AssumptionCache.h:200
llvm::isInstructionTriviallyDead
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction has no side ef...
Definition: Local.cpp:398
llvm::OptimizationRemarkEmitter
The optimization diagnostic interface.
Definition: OptimizationRemarkEmitter.h:33
DataLayout.h
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:253
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:41
llvm::CFGAnalyses
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:116
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::OptimizationRemarkEmitterWrapperPass
OptimizationRemarkEmitter legacy analysis pass.
Definition: OptimizationRemarkEmitter.h:146
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
Function.h
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:219
llvm::createInstSimplifyLegacyPass
FunctionPass * createInstSimplifyLegacyPass()
Definition: InstSimplifyPass.cpp:129
runImpl
static bool runImpl(Function &F, const SimplifyQuery &SQ, OptimizationRemarkEmitter *ORE)
Definition: InstSimplifyPass.cpp:33
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
llvm::PreservedAnalyses::preserveSet
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:191
Dominators.h
llvm::SmallPtrSetImplBase::empty
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:91
InstructionSimplify.h
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
InitializePasses.h
llvm::OptimizationRemarkEmitterAnalysis
Definition: OptimizationRemarkEmitter.h:164
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::TargetLibraryAnalysis
Analysis pass providing the TargetLibraryInfo.
Definition: TargetLibraryInfo.h:438
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38
llvm::SmallVectorImpl::insert
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:773