LLVM  15.0.0git
DependencyAnalysis.cpp
Go to the documentation of this file.
1 //===- DependencyAnalysis.cpp - ObjC ARC Optimization ---------------------===//
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 /// \file
9 ///
10 /// This file defines special dependency analysis routines used in Objective C
11 /// ARC Optimizations.
12 ///
13 /// WARNING: This file knows about certain library functions. It recognizes them
14 /// by name, and hardwires knowledge of their semantics.
15 ///
16 /// WARNING: This file knows about how certain Objective-C library functions are
17 /// used. Naive LLVM IR transformations which would otherwise be
18 /// behavior-preserving may break these assumptions.
19 ///
20 //===----------------------------------------------------------------------===//
21 
22 #include "DependencyAnalysis.h"
23 #include "ObjCARC.h"
24 #include "ProvenanceAnalysis.h"
26 #include "llvm/IR/CFG.h"
27 
28 using namespace llvm;
29 using namespace llvm::objcarc;
30 
31 #define DEBUG_TYPE "objc-arc-dependency"
32 
33 /// Test whether the given instruction can result in a reference count
34 /// modification (positive or negative) for the pointer's object.
35 bool llvm::objcarc::CanAlterRefCount(const Instruction *Inst, const Value *Ptr,
37  ARCInstKind Class) {
38  switch (Class) {
42  case ARCInstKind::User:
43  // These operations never directly modify a reference count.
44  return false;
45  default: break;
46  }
47 
48  const auto *Call = cast<CallBase>(Inst);
49 
50  // See if AliasAnalysis can help us with the call.
53  return false;
55  for (const Value *Op : Call->args()) {
56  if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op))
57  return true;
58  }
59  return false;
60  }
61 
62  // Assume the worst.
63  return true;
64 }
65 
67  const Value *Ptr,
69  ARCInstKind Class) {
70  // First perform a quick check if Class can not touch ref counts.
71  if (!CanDecrementRefCount(Class))
72  return false;
73 
74  // Otherwise, just use CanAlterRefCount for now.
75  return CanAlterRefCount(Inst, Ptr, PA, Class);
76 }
77 
78 /// Test whether the given instruction can "use" the given pointer's object in a
79 /// way that requires the reference count to be positive.
80 bool llvm::objcarc::CanUse(const Instruction *Inst, const Value *Ptr,
81  ProvenanceAnalysis &PA, ARCInstKind Class) {
82  // ARCInstKind::Call operations (as opposed to
83  // ARCInstKind::CallOrUser) never "use" objc pointers.
84  if (Class == ARCInstKind::Call)
85  return false;
86 
87  // Consider various instructions which may have pointer arguments which are
88  // not "uses".
89  if (const ICmpInst *ICI = dyn_cast<ICmpInst>(Inst)) {
90  // Comparing a pointer with null, or any other constant, isn't really a use,
91  // because we don't care what the pointer points to, or about the values
92  // of any other dynamic reference-counted pointers.
93  if (!IsPotentialRetainableObjPtr(ICI->getOperand(1), *PA.getAA()))
94  return false;
95  } else if (const auto *CS = dyn_cast<CallBase>(Inst)) {
96  // For calls, just check the arguments (and not the callee operand).
97  for (const Value *Op : CS->args())
98  if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op))
99  return true;
100  return false;
101  } else if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
102  // Special-case stores, because we don't care about the stored value, just
103  // the store address.
104  const Value *Op = GetUnderlyingObjCPtr(SI->getPointerOperand());
105  // If we can't tell what the underlying object was, assume there is a
106  // dependence.
107  return IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Op, Ptr);
108  }
109 
110  // Check each operand for a match.
111  for (const Use &U : Inst->operands()) {
112  const Value *Op = U;
113  if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op))
114  return true;
115  }
116  return false;
117 }
118 
119 /// Test if there can be dependencies on Inst through Arg. This function only
120 /// tests dependencies relevant for removing pairs of calls.
121 bool
123  const Value *Arg, ProvenanceAnalysis &PA) {
124  // If we've reached the definition of Arg, stop.
125  if (Inst == Arg)
126  return true;
127 
128  switch (Flavor) {
130  ARCInstKind Class = GetARCInstKind(Inst);
131  switch (Class) {
134  case ARCInstKind::None:
135  return false;
136  default:
137  return CanUse(Inst, Arg, PA, Class);
138  }
139  }
140 
142  ARCInstKind Class = GetARCInstKind(Inst);
143  switch (Class) {
146  // These mark the end and begin of an autorelease pool scope.
147  return true;
148  default:
149  // Nothing else does this.
150  return false;
151  }
152  }
153 
154  case CanChangeRetainCount: {
155  ARCInstKind Class = GetARCInstKind(Inst);
156  switch (Class) {
158  // Conservatively assume this can decrement any count.
159  return true;
161  case ARCInstKind::None:
162  return false;
163  default:
164  return CanAlterRefCount(Inst, Arg, PA, Class);
165  }
166  }
167 
169  switch (GetBasicARCInstKind(Inst)) {
172  // Don't merge an objc_autorelease with an objc_retain inside a different
173  // autoreleasepool scope.
174  return true;
175  case ARCInstKind::Retain:
177  // Check for a retain of the same pointer for merging.
178  return GetArgRCIdentityRoot(Inst) == Arg;
179  default:
180  // Nothing else matters for objc_retainAutorelease formation.
181  return false;
182  }
183 
184  case RetainAutoreleaseRVDep: {
185  ARCInstKind Class = GetBasicARCInstKind(Inst);
186  switch (Class) {
187  case ARCInstKind::Retain:
189  // Check for a retain of the same pointer for merging.
190  return GetArgRCIdentityRoot(Inst) == Arg;
191  default:
192  // Anything that can autorelease interrupts
193  // retainAutoreleaseReturnValue formation.
194  return CanInterruptRV(Class);
195  }
196  }
197  }
198 
199  llvm_unreachable("Invalid dependence flavor");
200 }
201 
202 /// Walk up the CFG from StartPos (which is in StartBB) and find local and
203 /// non-local dependencies on Arg.
204 ///
205 /// TODO: Cache results?
206 static bool findDependencies(DependenceKind Flavor, const Value *Arg,
207  BasicBlock *StartBB, Instruction *StartInst,
208  SmallPtrSetImpl<Instruction *> &DependingInsts,
209  ProvenanceAnalysis &PA) {
210  BasicBlock::iterator StartPos = StartInst->getIterator();
211 
214  Worklist.push_back(std::make_pair(StartBB, StartPos));
215  do {
216  std::pair<BasicBlock *, BasicBlock::iterator> Pair =
217  Worklist.pop_back_val();
218  BasicBlock *LocalStartBB = Pair.first;
219  BasicBlock::iterator LocalStartPos = Pair.second;
220  BasicBlock::iterator StartBBBegin = LocalStartBB->begin();
221  for (;;) {
222  if (LocalStartPos == StartBBBegin) {
223  pred_iterator PI(LocalStartBB), PE(LocalStartBB, false);
224  if (PI == PE)
225  // Return if we've reached the function entry.
226  return false;
227  // Add the predecessors to the worklist.
228  do {
229  BasicBlock *PredBB = *PI;
230  if (Visited.insert(PredBB).second)
231  Worklist.push_back(std::make_pair(PredBB, PredBB->end()));
232  } while (++PI != PE);
233  break;
234  }
235 
236  Instruction *Inst = &*--LocalStartPos;
237  if (Depends(Flavor, Inst, Arg, PA)) {
238  DependingInsts.insert(Inst);
239  break;
240  }
241  }
242  } while (!Worklist.empty());
243 
244  // Determine whether the original StartBB post-dominates all of the blocks we
245  // visited. If not, insert a sentinal indicating that most optimizations are
246  // not safe.
247  for (const BasicBlock *BB : Visited) {
248  if (BB == StartBB)
249  continue;
250  for (const BasicBlock *Succ : successors(BB))
251  if (Succ != StartBB && !Visited.count(Succ))
252  return false;
253  }
254 
255  return true;
256 }
257 
259  const Value *Arg,
260  BasicBlock *StartBB,
261  Instruction *StartInst,
262  ProvenanceAnalysis &PA) {
263  SmallPtrSet<Instruction *, 4> DependingInsts;
264 
265  if (!findDependencies(Flavor, Arg, StartBB, StartInst, DependingInsts, PA) ||
266  DependingInsts.size() != 1)
267  return nullptr;
268  return *DependingInsts.begin();
269 }
llvm::objcarc::GetBasicARCInstKind
ARCInstKind GetBasicARCInstKind(const Value *V)
Determine which objc runtime call instruction class V belongs to.
Definition: ObjCARCInstKind.h:104
llvm::objcarc::ARCInstKind::User
@ User
could "use" a pointer
llvm::BasicBlock::end
iterator end()
Definition: BasicBlock.h:299
llvm::objcarc::CanUse
bool CanUse(const Instruction *Inst, const Value *Ptr, ProvenanceAnalysis &PA, ARCInstKind Class)
Test whether the given instruction can "use" the given pointer's object in a way that requires the re...
Definition: DependencyAnalysis.cpp:80
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::User::operands
op_range operands()
Definition: User.h:242
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
llvm::objcarc::NeedsPositiveRetainCount
@ NeedsPositiveRetainCount
Definition: DependencyAnalysis.h:45
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::objcarc::RetainAutoreleaseDep
@ RetainAutoreleaseDep
Blocks objc_retainAutorelease.
Definition: DependencyAnalysis.h:48
llvm::AAResults::onlyAccessesArgPointees
static bool onlyAccessesArgPointees(FunctionModRefBehavior MRB)
Checks if functions with the specified behavior are known to read and write at most from objects poin...
Definition: AliasAnalysis.h:692
llvm::objcarc::ARCInstKind::Call
@ Call
could call objc_release
ObjCARC.h
llvm::SmallPtrSet< const BasicBlock *, 4 >
llvm::successors
auto successors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:29
llvm::objcarc::ProvenanceAnalysis
This is similar to BasicAliasAnalysis, and it uses many of the same techniques, except it uses specia...
Definition: ProvenanceAnalysis.h:50
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:654
llvm::objcarc::GetARCInstKind
ARCInstKind GetARCInstKind(const Value *V)
Map V to its ARCInstKind equivalence class.
Definition: ObjCARCInstKind.cpp:213
llvm::objcarc::ARCInstKind::Autorelease
@ Autorelease
objc_autorelease
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
AliasAnalysis.h
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:186
llvm::objcarc::CanInterruptRV
bool CanInterruptRV(ARCInstKind Class)
Test whether the given instruction can autorelease any pointer or cause an autoreleasepool pop.
Definition: ObjCARCInstKind.cpp:634
llvm::AAResults::onlyReadsMemory
bool onlyReadsMemory(const CallBase *Call)
Checks if the specified call is known to only read from non-volatile memory (or not access memory at ...
Definition: AliasAnalysis.h:660
llvm::objcarc::IsPotentialRetainableObjPtr
bool IsPotentialRetainableObjPtr(const Value *Op)
Test whether the given value is possible a retainable object pointer.
Definition: ObjCARCAnalysisUtils.h:146
llvm::objcarc::GetArgRCIdentityRoot
Value * GetArgRCIdentityRoot(Value *Inst)
Assuming the given instruction is one of the special calls such as objc_retain or objc_release,...
Definition: ObjCARCAnalysisUtils.h:131
DependencyAnalysis.h
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:297
llvm::objcarc::ARCInstKind::RetainRV
@ RetainRV
objc_retainAutoreleasedReturnValue
llvm::Instruction
Definition: Instruction.h:42
llvm::objcarc::ARCInstKind::IntrinsicUser
@ IntrinsicUser
llvm.objc.clang.arc.use
llvm::objcarc::DependenceKind
DependenceKind
Definition: DependencyAnalysis.h:44
findDependencies
static bool findDependencies(DependenceKind Flavor, const Value *Arg, BasicBlock *StartBB, Instruction *StartInst, SmallPtrSetImpl< Instruction * > &DependingInsts, ProvenanceAnalysis &PA)
Walk up the CFG from StartPos (which is in StartBB) and find local and non-local dependencies on Arg.
Definition: DependencyAnalysis.cpp:206
llvm::objcarc::ARCInstKind
ARCInstKind
Definition: ObjCARCInstKind.h:28
CFG.h
llvm::objcarc::ARCInstKind::AutoreleasepoolPop
@ AutoreleasepoolPop
objc_autoreleasePoolPop
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:305
ProvenanceAnalysis.h
llvm::ICmpInst
This instruction compares its operands according to the predicate given to the constructor.
Definition: Instructions.h:1186
llvm::SmallPtrSetImpl::begin
iterator begin() const
Definition: SmallPtrSet.h:403
llvm::objcarc::Depends
bool Depends(DependenceKind Flavor, Instruction *Inst, const Value *Arg, ProvenanceAnalysis &PA)
Test if there can be dependencies on Inst through Arg.
Definition: DependencyAnalysis.cpp:122
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::objcarc::CanChangeRetainCount
@ CanChangeRetainCount
Definition: DependencyAnalysis.h:47
llvm::objcarc
Definition: ObjCARCAliasAnalysis.h:29
llvm::objcarc::RetainAutoreleaseRVDep
@ RetainAutoreleaseRVDep
Blocks objc_retainAutoreleaseReturnValue.
Definition: DependencyAnalysis.h:49
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::objcarc::GetUnderlyingObjCPtr
const Value * GetUnderlyingObjCPtr(const Value *V)
This is a wrapper around getUnderlyingObject which also knows how to look through objc_retain and obj...
Definition: ObjCARCAnalysisUtils.h:69
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:82
llvm::FunctionModRefBehavior
FunctionModRefBehavior
Summary of how a function affects memory in the program.
Definition: AliasAnalysis.h:262
llvm::PredIterator
Definition: CFG.h:42
llvm::AAResults::getModRefBehavior
FunctionModRefBehavior getModRefBehavior(const CallBase *Call)
Return the behavior of the given call site.
Definition: AliasAnalysis.cpp:422
llvm::SmallPtrSetImplBase::size
size_type size() const
Definition: SmallPtrSet.h:93
llvm::objcarc::ARCInstKind::AutoreleasepoolPush
@ AutoreleasepoolPush
objc_autoreleasePoolPush
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:341
llvm::objcarc::findSingleDependency
llvm::Instruction * findSingleDependency(DependenceKind Flavor, const Value *Arg, BasicBlock *StartBB, Instruction *StartInst, ProvenanceAnalysis &PA)
Find dependent instructions.
Definition: DependencyAnalysis.cpp:258
llvm::objcarc::CanDecrementRefCount
bool CanDecrementRefCount(ARCInstKind Kind)
Returns false if conservatively we can prove that any instruction mapped to this kind can not decreme...
Definition: ObjCARCInstKind.cpp:667
llvm::objcarc::ARCInstKind::None
@ None
anything that is inert from an ARC perspective.
llvm::objcarc::CanAlterRefCount
bool CanAlterRefCount(const Instruction *Inst, const Value *Ptr, ProvenanceAnalysis &PA, ARCInstKind Class)
Test whether the given instruction can result in a reference count modification (positive or negative...
Definition: DependencyAnalysis.cpp:35
llvm::SmallPtrSetImpl< Instruction * >
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::objcarc::ProvenanceAnalysis::related
bool related(const Value *A, const Value *B)
Definition: ProvenanceAnalysis.cpp:159
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::objcarc::ARCInstKind::Retain
@ Retain
objc_retain
llvm::objcarc::AutoreleasePoolBoundary
@ AutoreleasePoolBoundary
Definition: DependencyAnalysis.h:46
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
llvm::objcarc::ARCInstKind::AutoreleaseRV
@ AutoreleaseRV
objc_autoreleaseReturnValue
llvm::objcarc::ProvenanceAnalysis::getAA
AAResults * getAA() const
Definition: ProvenanceAnalysis.h:72