LLVM  9.0.0svn
DependencyAnalysis.cpp
Go to the documentation of this file.
1 //===- DependencyAnalysis.cpp - ObjC ARC Optimization ---------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 /// \file
10 ///
11 /// This file defines special dependency analysis routines used in Objective C
12 /// ARC Optimizations.
13 ///
14 /// WARNING: This file knows about certain library functions. It recognizes them
15 /// by name, and hardwires knowledge of their semantics.
16 ///
17 /// WARNING: This file knows about how certain Objective-C library functions are
18 /// used. Naive LLVM IR transformations which would otherwise be
19 /// behavior-preserving may break these assumptions.
20 ///
21 //===----------------------------------------------------------------------===//
22 
23 #include "DependencyAnalysis.h"
24 #include "ObjCARC.h"
25 #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  const DataLayout &DL = Inst->getModule()->getDataLayout();
56  for (const Value *Op : Call->args()) {
57  if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) &&
58  PA.related(Ptr, Op, DL))
59  return true;
60  }
61  return false;
62  }
63 
64  // Assume the worst.
65  return true;
66 }
67 
69  const Value *Ptr,
71  ARCInstKind Class) {
72  // First perform a quick check if Class can not touch ref counts.
73  if (!CanDecrementRefCount(Class))
74  return false;
75 
76  // Otherwise, just use CanAlterRefCount for now.
77  return CanAlterRefCount(Inst, Ptr, PA, Class);
78 }
79 
80 /// Test whether the given instruction can "use" the given pointer's object in a
81 /// way that requires the reference count to be positive.
82 bool llvm::objcarc::CanUse(const Instruction *Inst, const Value *Ptr,
83  ProvenanceAnalysis &PA, ARCInstKind Class) {
84  // ARCInstKind::Call operations (as opposed to
85  // ARCInstKind::CallOrUser) never "use" objc pointers.
86  if (Class == ARCInstKind::Call)
87  return false;
88 
89  const DataLayout &DL = Inst->getModule()->getDataLayout();
90 
91  // Consider various instructions which may have pointer arguments which are
92  // not "uses".
93  if (const ICmpInst *ICI = dyn_cast<ICmpInst>(Inst)) {
94  // Comparing a pointer with null, or any other constant, isn't really a use,
95  // because we don't care what the pointer points to, or about the values
96  // of any other dynamic reference-counted pointers.
97  if (!IsPotentialRetainableObjPtr(ICI->getOperand(1), *PA.getAA()))
98  return false;
99  } else if (auto CS = ImmutableCallSite(Inst)) {
100  // For calls, just check the arguments (and not the callee operand).
101  for (ImmutableCallSite::arg_iterator OI = CS.arg_begin(),
102  OE = CS.arg_end(); OI != OE; ++OI) {
103  const Value *Op = *OI;
104  if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) &&
105  PA.related(Ptr, Op, DL))
106  return true;
107  }
108  return false;
109  } else if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
110  // Special-case stores, because we don't care about the stored value, just
111  // the store address.
112  const Value *Op = GetUnderlyingObjCPtr(SI->getPointerOperand(), DL);
113  // If we can't tell what the underlying object was, assume there is a
114  // dependence.
115  return IsPotentialRetainableObjPtr(Op, *PA.getAA()) &&
116  PA.related(Op, Ptr, DL);
117  }
118 
119  // Check each operand for a match.
120  for (User::const_op_iterator OI = Inst->op_begin(), OE = Inst->op_end();
121  OI != OE; ++OI) {
122  const Value *Op = *OI;
123  if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op, DL))
124  return true;
125  }
126  return false;
127 }
128 
129 /// Test if there can be dependencies on Inst through Arg. This function only
130 /// tests dependencies relevant for removing pairs of calls.
131 bool
133  const Value *Arg, ProvenanceAnalysis &PA) {
134  // If we've reached the definition of Arg, stop.
135  if (Inst == Arg)
136  return true;
137 
138  switch (Flavor) {
140  ARCInstKind Class = GetARCInstKind(Inst);
141  switch (Class) {
144  case ARCInstKind::None:
145  return false;
146  default:
147  return CanUse(Inst, Arg, PA, Class);
148  }
149  }
150 
152  ARCInstKind Class = GetARCInstKind(Inst);
153  switch (Class) {
156  // These mark the end and begin of an autorelease pool scope.
157  return true;
158  default:
159  // Nothing else does this.
160  return false;
161  }
162  }
163 
164  case CanChangeRetainCount: {
165  ARCInstKind Class = GetARCInstKind(Inst);
166  switch (Class) {
168  // Conservatively assume this can decrement any count.
169  return true;
171  case ARCInstKind::None:
172  return false;
173  default:
174  return CanAlterRefCount(Inst, Arg, PA, Class);
175  }
176  }
177 
179  switch (GetBasicARCInstKind(Inst)) {
182  // Don't merge an objc_autorelease with an objc_retain inside a different
183  // autoreleasepool scope.
184  return true;
185  case ARCInstKind::Retain:
187  // Check for a retain of the same pointer for merging.
188  return GetArgRCIdentityRoot(Inst) == Arg;
189  default:
190  // Nothing else matters for objc_retainAutorelease formation.
191  return false;
192  }
193 
194  case RetainAutoreleaseRVDep: {
195  ARCInstKind Class = GetBasicARCInstKind(Inst);
196  switch (Class) {
197  case ARCInstKind::Retain:
199  // Check for a retain of the same pointer for merging.
200  return GetArgRCIdentityRoot(Inst) == Arg;
201  default:
202  // Anything that can autorelease interrupts
203  // retainAutoreleaseReturnValue formation.
204  return CanInterruptRV(Class);
205  }
206  }
207 
208  case RetainRVDep:
209  return CanInterruptRV(GetBasicARCInstKind(Inst));
210  }
211 
212  llvm_unreachable("Invalid dependence flavor");
213 }
214 
215 /// Walk up the CFG from StartPos (which is in StartBB) and find local and
216 /// non-local dependencies on Arg.
217 ///
218 /// TODO: Cache results?
219 void
221  const Value *Arg,
222  BasicBlock *StartBB, Instruction *StartInst,
223  SmallPtrSetImpl<Instruction *> &DependingInsts,
225  ProvenanceAnalysis &PA) {
226  BasicBlock::iterator StartPos = StartInst->getIterator();
227 
229  Worklist.push_back(std::make_pair(StartBB, StartPos));
230  do {
231  std::pair<BasicBlock *, BasicBlock::iterator> Pair =
232  Worklist.pop_back_val();
233  BasicBlock *LocalStartBB = Pair.first;
234  BasicBlock::iterator LocalStartPos = Pair.second;
235  BasicBlock::iterator StartBBBegin = LocalStartBB->begin();
236  for (;;) {
237  if (LocalStartPos == StartBBBegin) {
238  pred_iterator PI(LocalStartBB), PE(LocalStartBB, false);
239  if (PI == PE)
240  // If we've reached the function entry, produce a null dependence.
241  DependingInsts.insert(nullptr);
242  else
243  // Add the predecessors to the worklist.
244  do {
245  BasicBlock *PredBB = *PI;
246  if (Visited.insert(PredBB).second)
247  Worklist.push_back(std::make_pair(PredBB, PredBB->end()));
248  } while (++PI != PE);
249  break;
250  }
251 
252  Instruction *Inst = &*--LocalStartPos;
253  if (Depends(Flavor, Inst, Arg, PA)) {
254  DependingInsts.insert(Inst);
255  break;
256  }
257  }
258  } while (!Worklist.empty());
259 
260  // Determine whether the original StartBB post-dominates all of the blocks we
261  // visited. If not, insert a sentinal indicating that most optimizations are
262  // not safe.
263  for (const BasicBlock *BB : Visited) {
264  if (BB == StartBB)
265  continue;
266  for (const BasicBlock *Succ : successors(BB))
267  if (Succ != StartBB && !Visited.count(Succ)) {
268  DependingInsts.insert(reinterpret_cast<Instruction *>(-1));
269  return;
270  }
271  }
272 }
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
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:24
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:230
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:269
objc_autoreleaseReturnValue
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:371
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:56
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:321
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
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:371
op_iterator op_end()
Definition: User.h:232
This instruction compares its operands according to the predicate given to the constructor.
self_iterator getIterator()
Definition: ilist_node.h:82
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:271
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:847
ARCInstKind
Equivalence classes of instructions in the ARC Model.
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:381
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:56
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...
amdgpu Simplify well known AMD library false Value Value * 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:56
Establish a view to a call site for examination.
Definition: CallSite.h:887
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:264
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.