LLVM  10.0.0svn
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"
25 #include "llvm/IR/CFG.h"
26 
27 using namespace llvm;
28 using namespace llvm::objcarc;
29 
30 #define DEBUG_TYPE "objc-arc-dependency"
31 
32 /// Test whether the given instruction can result in a reference count
33 /// modification (positive or negative) for the pointer's object.
34 bool llvm::objcarc::CanAlterRefCount(const Instruction *Inst, const Value *Ptr,
36  ARCInstKind Class) {
37  switch (Class) {
41  case ARCInstKind::User:
42  // These operations never directly modify a reference count.
43  return false;
44  default: break;
45  }
46 
47  const auto *Call = cast<CallBase>(Inst);
48 
49  // See if AliasAnalysis can help us with the call.
52  return false;
54  const DataLayout &DL = Inst->getModule()->getDataLayout();
55  for (const Value *Op : Call->args()) {
56  if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) &&
57  PA.related(Ptr, Op, DL))
58  return true;
59  }
60  return false;
61  }
62 
63  // Assume the worst.
64  return true;
65 }
66 
68  const Value *Ptr,
70  ARCInstKind Class) {
71  // First perform a quick check if Class can not touch ref counts.
72  if (!CanDecrementRefCount(Class))
73  return false;
74 
75  // Otherwise, just use CanAlterRefCount for now.
76  return CanAlterRefCount(Inst, Ptr, PA, Class);
77 }
78 
79 /// Test whether the given instruction can "use" the given pointer's object in a
80 /// way that requires the reference count to be positive.
81 bool llvm::objcarc::CanUse(const Instruction *Inst, const Value *Ptr,
82  ProvenanceAnalysis &PA, ARCInstKind Class) {
83  // ARCInstKind::Call operations (as opposed to
84  // ARCInstKind::CallOrUser) never "use" objc pointers.
85  if (Class == ARCInstKind::Call)
86  return false;
87 
88  const DataLayout &DL = Inst->getModule()->getDataLayout();
89 
90  // Consider various instructions which may have pointer arguments which are
91  // not "uses".
92  if (const ICmpInst *ICI = dyn_cast<ICmpInst>(Inst)) {
93  // Comparing a pointer with null, or any other constant, isn't really a use,
94  // because we don't care what the pointer points to, or about the values
95  // of any other dynamic reference-counted pointers.
96  if (!IsPotentialRetainableObjPtr(ICI->getOperand(1), *PA.getAA()))
97  return false;
98  } else if (auto CS = ImmutableCallSite(Inst)) {
99  // For calls, just check the arguments (and not the callee operand).
100  for (ImmutableCallSite::arg_iterator OI = CS.arg_begin(),
101  OE = CS.arg_end(); OI != OE; ++OI) {
102  const Value *Op = *OI;
103  if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) &&
104  PA.related(Ptr, Op, DL))
105  return true;
106  }
107  return false;
108  } else if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
109  // Special-case stores, because we don't care about the stored value, just
110  // the store address.
111  const Value *Op = GetUnderlyingObjCPtr(SI->getPointerOperand(), DL);
112  // If we can't tell what the underlying object was, assume there is a
113  // dependence.
114  return IsPotentialRetainableObjPtr(Op, *PA.getAA()) &&
115  PA.related(Op, Ptr, DL);
116  }
117 
118  // Check each operand for a match.
119  for (User::const_op_iterator OI = Inst->op_begin(), OE = Inst->op_end();
120  OI != OE; ++OI) {
121  const Value *Op = *OI;
122  if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op, DL))
123  return true;
124  }
125  return false;
126 }
127 
128 /// Test if there can be dependencies on Inst through Arg. This function only
129 /// tests dependencies relevant for removing pairs of calls.
130 bool
132  const Value *Arg, ProvenanceAnalysis &PA) {
133  // If we've reached the definition of Arg, stop.
134  if (Inst == Arg)
135  return true;
136 
137  switch (Flavor) {
139  ARCInstKind Class = GetARCInstKind(Inst);
140  switch (Class) {
143  case ARCInstKind::None:
144  return false;
145  default:
146  return CanUse(Inst, Arg, PA, Class);
147  }
148  }
149 
151  ARCInstKind Class = GetARCInstKind(Inst);
152  switch (Class) {
155  // These mark the end and begin of an autorelease pool scope.
156  return true;
157  default:
158  // Nothing else does this.
159  return false;
160  }
161  }
162 
163  case CanChangeRetainCount: {
164  ARCInstKind Class = GetARCInstKind(Inst);
165  switch (Class) {
167  // Conservatively assume this can decrement any count.
168  return true;
170  case ARCInstKind::None:
171  return false;
172  default:
173  return CanAlterRefCount(Inst, Arg, PA, Class);
174  }
175  }
176 
178  switch (GetBasicARCInstKind(Inst)) {
181  // Don't merge an objc_autorelease with an objc_retain inside a different
182  // autoreleasepool scope.
183  return true;
184  case ARCInstKind::Retain:
186  // Check for a retain of the same pointer for merging.
187  return GetArgRCIdentityRoot(Inst) == Arg;
188  default:
189  // Nothing else matters for objc_retainAutorelease formation.
190  return false;
191  }
192 
193  case RetainAutoreleaseRVDep: {
194  ARCInstKind Class = GetBasicARCInstKind(Inst);
195  switch (Class) {
196  case ARCInstKind::Retain:
198  // Check for a retain of the same pointer for merging.
199  return GetArgRCIdentityRoot(Inst) == Arg;
200  default:
201  // Anything that can autorelease interrupts
202  // retainAutoreleaseReturnValue formation.
203  return CanInterruptRV(Class);
204  }
205  }
206 
207  case RetainRVDep:
208  return CanInterruptRV(GetBasicARCInstKind(Inst));
209  }
210 
211  llvm_unreachable("Invalid dependence flavor");
212 }
213 
214 /// Walk up the CFG from StartPos (which is in StartBB) and find local and
215 /// non-local dependencies on Arg.
216 ///
217 /// TODO: Cache results?
218 void
220  const Value *Arg,
221  BasicBlock *StartBB, Instruction *StartInst,
222  SmallPtrSetImpl<Instruction *> &DependingInsts,
224  ProvenanceAnalysis &PA) {
225  BasicBlock::iterator StartPos = StartInst->getIterator();
226 
228  Worklist.push_back(std::make_pair(StartBB, StartPos));
229  do {
230  std::pair<BasicBlock *, BasicBlock::iterator> Pair =
231  Worklist.pop_back_val();
232  BasicBlock *LocalStartBB = Pair.first;
233  BasicBlock::iterator LocalStartPos = Pair.second;
234  BasicBlock::iterator StartBBBegin = LocalStartBB->begin();
235  for (;;) {
236  if (LocalStartPos == StartBBBegin) {
237  pred_iterator PI(LocalStartBB), PE(LocalStartBB, false);
238  if (PI == PE)
239  // If we've reached the function entry, produce a null dependence.
240  DependingInsts.insert(nullptr);
241  else
242  // Add the predecessors to the worklist.
243  do {
244  BasicBlock *PredBB = *PI;
245  if (Visited.insert(PredBB).second)
246  Worklist.push_back(std::make_pair(PredBB, PredBB->end()));
247  } while (++PI != PE);
248  break;
249  }
250 
251  Instruction *Inst = &*--LocalStartPos;
252  if (Depends(Flavor, Inst, Arg, PA)) {
253  DependingInsts.insert(Inst);
254  break;
255  }
256  }
257  } while (!Worklist.empty());
258 
259  // Determine whether the original StartBB post-dominates all of the blocks we
260  // visited. If not, insert a sentinal indicating that most optimizations are
261  // not safe.
262  for (const BasicBlock *BB : Visited) {
263  if (BB == StartBB)
264  continue;
265  for (const BasicBlock *Succ : successors(BB))
266  if (Succ != StartBB && !Visited.count(Succ)) {
267  DependingInsts.insert(reinterpret_cast<Instruction *>(-1));
268  return;
269  }
270  }
271 }
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:112
This file declares special dependency analysis routines used in Objective C ARC Optimizations.
ARCInstKind GetARCInstKind(const Value *V)
Map V to its ARCInstKind equivalence class.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
bool CanUse(const Instruction *Inst, const Value *Ptr, ProvenanceAnalysis &PA, ARCInstKind Class)
Test whether the given instruction can "use" the given pointer&#39;s object in a way that requires the re...
Blocks objc_retainAutorelease.
Value * GetArgRCIdentityRoot(Value *Inst)
Assuming the given instruction is one of the special calls such as objc_retain or objc_release...
could call objc_release
op_iterator op_begin()
Definition: User.h:229
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:273
objc_autoreleaseReturnValue
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:369
bool Depends(DependenceKind Flavor, Instruction *Inst, const Value *Arg, ProvenanceAnalysis &PA)
Test if there can be dependencies on Inst through Arg.
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
This file defines common definitions/declarations used by the ObjC ARC Optimizer. ...
FunctionModRefBehavior getModRefBehavior(const CallBase *Call)
Return the behavior of the given call site.
objc_retainAutoreleasedReturnValue
bool IsPotentialRetainableObjPtr(const Value *Op)
Test whether the given value is possible a retainable object pointer.
FunctionModRefBehavior
Summary of how a function affects memory in the program.
An instruction for storing to memory.
Definition: Instructions.h:325
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
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:370
op_iterator op_end()
Definition: User.h:231
This instruction compares its operands according to the predicate given to the constructor.
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
self_iterator getIterator()
Definition: ilist_node.h:81
bool onlyReadsMemory(const CallBase *Call)
Checks if the specified call is known to only read from non-volatile memory (or not access memory at ...
anything that is inert from an ARC perspective.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
ARCInstKind GetBasicARCInstKind(const Value *V)
Determine which objc runtime call instruction class V belongs to.
bool CanDecrementRefCount(ARCInstKind Kind)
Returns false if conservatively we can prove that any instruction mapped to this kind can not decreme...
DependenceKind
Defines different dependence kinds among various ARC constructs.
Iterator for intrusive lists based on ilist_node.
iterator end()
Definition: BasicBlock.h:275
This file declares a special form of Alias Analysis called ``Provenance Analysis&#39;&#39;.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
ARCInstKind
Equivalence classes of instructions in the ARC Model.
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:374
bool related(const Value *A, const Value *B, const DataLayout &DL)
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:55
void FindDependencies(DependenceKind Flavor, const Value *Arg, BasicBlock *StartBB, Instruction *StartInst, SmallPtrSetImpl< Instruction *> &DependingInstructions, SmallPtrSetImpl< const BasicBlock *> &Visited, ProvenanceAnalysis &PA)
Walk up the CFG from StartPos (which is in StartBB) and find local and non-local dependencies on Arg...
could "use" a pointer
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
static bool onlyAccessesArgPointees(FunctionModRefBehavior MRB)
Checks if functions with the specified behavior are known to read and write at most from objects poin...
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
Establish a view to a call site for examination.
Definition: CallSite.h:906
Blocks objc_retainAutoreleaseReturnValue.
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...
const Value * GetUnderlyingObjCPtr(const Value *V, const DataLayout &DL)
This is a wrapper around getUnderlyingObject which also knows how to look through objc_retain and obj...
LLVM Value Representation.
Definition: Value.h:73
succ_range successors(Instruction *I)
Definition: CFG.h:259
This is similar to BasicAliasAnalysis, and it uses many of the same techniques, except it uses specia...
bool CanInterruptRV(ARCInstKind Class)
Test whether the given instruction can autorelease any pointer or cause an autoreleasepool pop...
Blocks objc_retainAutoreleasedReturnValue.