LLVM  14.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  case RetainRVDep:
199  return CanInterruptRV(GetBasicARCInstKind(Inst));
200  }
201 
202  llvm_unreachable("Invalid dependence flavor");
203 }
204 
205 /// Walk up the CFG from StartPos (which is in StartBB) and find local and
206 /// non-local dependencies on Arg.
207 ///
208 /// TODO: Cache results?
209 static bool findDependencies(DependenceKind Flavor, const Value *Arg,
210  BasicBlock *StartBB, Instruction *StartInst,
211  SmallPtrSetImpl<Instruction *> &DependingInsts,
212  ProvenanceAnalysis &PA) {
213  BasicBlock::iterator StartPos = StartInst->getIterator();
214 
217  Worklist.push_back(std::make_pair(StartBB, StartPos));
218  do {
219  std::pair<BasicBlock *, BasicBlock::iterator> Pair =
220  Worklist.pop_back_val();
221  BasicBlock *LocalStartBB = Pair.first;
222  BasicBlock::iterator LocalStartPos = Pair.second;
223  BasicBlock::iterator StartBBBegin = LocalStartBB->begin();
224  for (;;) {
225  if (LocalStartPos == StartBBBegin) {
226  pred_iterator PI(LocalStartBB), PE(LocalStartBB, false);
227  if (PI == PE)
228  // Return if we've reached the function entry.
229  return false;
230  // Add the predecessors to the worklist.
231  do {
232  BasicBlock *PredBB = *PI;
233  if (Visited.insert(PredBB).second)
234  Worklist.push_back(std::make_pair(PredBB, PredBB->end()));
235  } while (++PI != PE);
236  break;
237  }
238 
239  Instruction *Inst = &*--LocalStartPos;
240  if (Depends(Flavor, Inst, Arg, PA)) {
241  DependingInsts.insert(Inst);
242  break;
243  }
244  }
245  } while (!Worklist.empty());
246 
247  // Determine whether the original StartBB post-dominates all of the blocks we
248  // visited. If not, insert a sentinal indicating that most optimizations are
249  // not safe.
250  for (const BasicBlock *BB : Visited) {
251  if (BB == StartBB)
252  continue;
253  for (const BasicBlock *Succ : successors(BB))
254  if (Succ != StartBB && !Visited.count(Succ))
255  return false;
256  }
257 
258  return true;
259 }
260 
262  const Value *Arg,
263  BasicBlock *StartBB,
264  Instruction *StartInst,
265  ProvenanceAnalysis &PA) {
266  SmallPtrSet<Instruction *, 4> DependingInsts;
267 
268  if (!findDependencies(Flavor, Arg, StartBB, StartInst, DependingInsts, PA) ||
269  DependingInsts.size() != 1)
270  return nullptr;
271  return *DependingInsts.begin();
272 }
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
This is an optimization pass for GlobalISel generic memory operations.
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:689
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::successors
auto successors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:31
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::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:206
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:657
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:296
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:209
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:304
ProvenanceAnalysis.h
llvm::ICmpInst
This instruction compares its operands according to the predicate given to the constructor.
Definition: Instructions.h:1185
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: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:134
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:263
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:423
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:325
llvm::objcarc::findSingleDependency
llvm::Instruction * findSingleDependency(DependenceKind Flavor, const Value *Arg, BasicBlock *StartBB, Instruction *StartInst, ProvenanceAnalysis &PA)
Find dependent instructions.
Definition: DependencyAnalysis.cpp:261
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: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:73