LLVM  13.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 (auto OI = CS->arg_begin(), OE = CS->arg_end(); OI != OE; ++OI) {
98  const Value *Op = *OI;
99  if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op))
100  return true;
101  }
102  return false;
103  } else if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
104  // Special-case stores, because we don't care about the stored value, just
105  // the store address.
106  const Value *Op = GetUnderlyingObjCPtr(SI->getPointerOperand());
107  // If we can't tell what the underlying object was, assume there is a
108  // dependence.
109  return IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Op, Ptr);
110  }
111 
112  // Check each operand for a match.
113  for (const Use &U : Inst->operands()) {
114  const Value *Op = U;
115  if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op))
116  return true;
117  }
118  return false;
119 }
120 
121 /// Test if there can be dependencies on Inst through Arg. This function only
122 /// tests dependencies relevant for removing pairs of calls.
123 bool
125  const Value *Arg, ProvenanceAnalysis &PA) {
126  // If we've reached the definition of Arg, stop.
127  if (Inst == Arg)
128  return true;
129 
130  switch (Flavor) {
132  ARCInstKind Class = GetARCInstKind(Inst);
133  switch (Class) {
136  case ARCInstKind::None:
137  return false;
138  default:
139  return CanUse(Inst, Arg, PA, Class);
140  }
141  }
142 
144  ARCInstKind Class = GetARCInstKind(Inst);
145  switch (Class) {
148  // These mark the end and begin of an autorelease pool scope.
149  return true;
150  default:
151  // Nothing else does this.
152  return false;
153  }
154  }
155 
156  case CanChangeRetainCount: {
157  ARCInstKind Class = GetARCInstKind(Inst);
158  switch (Class) {
160  // Conservatively assume this can decrement any count.
161  return true;
163  case ARCInstKind::None:
164  return false;
165  default:
166  return CanAlterRefCount(Inst, Arg, PA, Class);
167  }
168  }
169 
171  switch (GetBasicARCInstKind(Inst)) {
174  // Don't merge an objc_autorelease with an objc_retain inside a different
175  // autoreleasepool scope.
176  return true;
177  case ARCInstKind::Retain:
179  // Check for a retain of the same pointer for merging.
180  return GetArgRCIdentityRoot(Inst) == Arg;
181  default:
182  // Nothing else matters for objc_retainAutorelease formation.
183  return false;
184  }
185 
186  case RetainAutoreleaseRVDep: {
187  ARCInstKind Class = GetBasicARCInstKind(Inst);
188  switch (Class) {
189  case ARCInstKind::Retain:
191  // Check for a retain of the same pointer for merging.
192  return GetArgRCIdentityRoot(Inst) == Arg;
193  default:
194  // Anything that can autorelease interrupts
195  // retainAutoreleaseReturnValue formation.
196  return CanInterruptRV(Class);
197  }
198  }
199 
200  case RetainRVDep:
201  return CanInterruptRV(GetBasicARCInstKind(Inst));
202  }
203 
204  llvm_unreachable("Invalid dependence flavor");
205 }
206 
207 /// Walk up the CFG from StartPos (which is in StartBB) and find local and
208 /// non-local dependencies on Arg.
209 ///
210 /// TODO: Cache results?
211 static bool findDependencies(DependenceKind Flavor, const Value *Arg,
212  BasicBlock *StartBB, Instruction *StartInst,
213  SmallPtrSetImpl<Instruction *> &DependingInsts,
214  ProvenanceAnalysis &PA) {
215  BasicBlock::iterator StartPos = StartInst->getIterator();
216 
219  Worklist.push_back(std::make_pair(StartBB, StartPos));
220  do {
221  std::pair<BasicBlock *, BasicBlock::iterator> Pair =
222  Worklist.pop_back_val();
223  BasicBlock *LocalStartBB = Pair.first;
224  BasicBlock::iterator LocalStartPos = Pair.second;
225  BasicBlock::iterator StartBBBegin = LocalStartBB->begin();
226  for (;;) {
227  if (LocalStartPos == StartBBBegin) {
228  pred_iterator PI(LocalStartBB), PE(LocalStartBB, false);
229  if (PI == PE)
230  // Return if we've reached the function entry.
231  return false;
232  // Add the predecessors to the worklist.
233  do {
234  BasicBlock *PredBB = *PI;
235  if (Visited.insert(PredBB).second)
236  Worklist.push_back(std::make_pair(PredBB, PredBB->end()));
237  } while (++PI != PE);
238  break;
239  }
240 
241  Instruction *Inst = &*--LocalStartPos;
242  if (Depends(Flavor, Inst, Arg, PA)) {
243  DependingInsts.insert(Inst);
244  break;
245  }
246  }
247  } while (!Worklist.empty());
248 
249  // Determine whether the original StartBB post-dominates all of the blocks we
250  // visited. If not, insert a sentinal indicating that most optimizations are
251  // not safe.
252  for (const BasicBlock *BB : Visited) {
253  if (BB == StartBB)
254  continue;
255  for (const BasicBlock *Succ : successors(BB))
256  if (Succ != StartBB && !Visited.count(Succ))
257  return false;
258  }
259 
260  return true;
261 }
262 
264  const Value *Arg,
265  BasicBlock *StartBB,
266  Instruction *StartInst,
267  ProvenanceAnalysis &PA) {
268  SmallPtrSet<Instruction *, 4> DependingInsts;
269 
270  if (!findDependencies(Flavor, Arg, StartBB, StartInst, DependingInsts, PA) ||
271  DependingInsts.size() != 1)
272  return nullptr;
273  return *DependingInsts.begin();
274 }
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:298
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
Definition: AllocatorList.h:23
llvm::User::operands
op_range operands()
Definition: User.h:242
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
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:1168
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:637
llvm::objcarc::RetainRVDep
@ RetainRVDep
Blocks objc_retainAutoreleasedReturnValue.
Definition: DependencyAnalysis.h:50
llvm::objcarc::ARCInstKind::Call
@ Call
could call objc_release
ObjCARC.h
llvm::SmallPtrSet< const BasicBlock *, 4 >
llvm::objcarc::ProvenanceAnalysis
This is similar to BasicAliasAnalysis, and it uses many of the same techniques, except it uses specia...
Definition: ProvenanceAnalysis.h:51
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
llvm::successors
succ_range successors(Instruction *I)
Definition: CFG.h:262
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:58
AliasAnalysis.h
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:205
llvm::objcarc::CanInterruptRV
bool CanInterruptRV(ARCInstKind Class)
Test whether the given instruction can autorelease any pointer or cause an autoreleasepool pop.
Definition: ObjCARCInstKind.cpp:635
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:605
llvm::objcarc::IsPotentialRetainableObjPtr
bool IsPotentialRetainableObjPtr(const Value *Op)
Test whether the given value is possible a retainable object pointer.
Definition: ObjCARCAnalysisUtils.h:143
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:128
DependencyAnalysis.h
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:296
SI
@ SI
Definition: SIInstrInfo.cpp:7342
llvm::objcarc::ARCInstKind::RetainRV
@ RetainRV
objc_retainAutoreleasedReturnValue
llvm::Instruction
Definition: Instruction.h:45
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:211
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:303
ProvenanceAnalysis.h
llvm::ICmpInst
This instruction compares its operands according to the predicate given to the constructor.
Definition: Instructions.h:1178
llvm::SmallPtrSetImpl::begin
iterator begin() const
Definition: SmallPtrSet.h:402
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:124
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:136
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:81
llvm::FunctionModRefBehavior
FunctionModRefBehavior
Summary of how a function affects memory in the program.
Definition: AliasAnalysis.h:262
llvm::PredIterator
Definition: CFG.h:43
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:92
llvm::objcarc::ARCInstKind::AutoreleasepoolPush
@ AutoreleasepoolPush
objc_autoreleasePoolPush
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:314
llvm::objcarc::findSingleDependency
llvm::Instruction * findSingleDependency(DependenceKind Flavor, const Value *Arg, BasicBlock *StartBB, Instruction *StartInst, ProvenanceAnalysis &PA)
Find dependent instructions.
Definition: DependencyAnalysis.cpp:263
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:668
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:75
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:44
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:364
llvm::objcarc::ARCInstKind::AutoreleaseRV
@ AutoreleaseRV
objc_autoreleaseReturnValue
llvm::objcarc::ProvenanceAnalysis::getAA
AAResults * getAA() const
Definition: ProvenanceAnalysis.h:72