LLVM  6.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  ImmutableCallSite CS(Inst);
49  assert(CS && "Only calls can alter reference counts!");
50 
51  // See if AliasAnalysis can help us with the call.
54  return false;
56  const DataLayout &DL = Inst->getModule()->getDataLayout();
58  I != E; ++I) {
59  const Value *Op = *I;
60  if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) &&
61  PA.related(Ptr, Op, DL))
62  return true;
63  }
64  return false;
65  }
66 
67  // Assume the worst.
68  return true;
69 }
70 
72  const Value *Ptr,
74  ARCInstKind Class) {
75  // First perform a quick check if Class can not touch ref counts.
76  if (!CanDecrementRefCount(Class))
77  return false;
78 
79  // Otherwise, just use CanAlterRefCount for now.
80  return CanAlterRefCount(Inst, Ptr, PA, Class);
81 }
82 
83 /// Test whether the given instruction can "use" the given pointer's object in a
84 /// way that requires the reference count to be positive.
85 bool llvm::objcarc::CanUse(const Instruction *Inst, const Value *Ptr,
86  ProvenanceAnalysis &PA, ARCInstKind Class) {
87  // ARCInstKind::Call operations (as opposed to
88  // ARCInstKind::CallOrUser) never "use" objc pointers.
89  if (Class == ARCInstKind::Call)
90  return false;
91 
92  const DataLayout &DL = Inst->getModule()->getDataLayout();
93 
94  // Consider various instructions which may have pointer arguments which are
95  // not "uses".
96  if (const ICmpInst *ICI = dyn_cast<ICmpInst>(Inst)) {
97  // Comparing a pointer with null, or any other constant, isn't really a use,
98  // because we don't care what the pointer points to, or about the values
99  // of any other dynamic reference-counted pointers.
100  if (!IsPotentialRetainableObjPtr(ICI->getOperand(1), *PA.getAA()))
101  return false;
102  } else if (auto CS = ImmutableCallSite(Inst)) {
103  // For calls, just check the arguments (and not the callee operand).
104  for (ImmutableCallSite::arg_iterator OI = CS.arg_begin(),
105  OE = CS.arg_end(); OI != OE; ++OI) {
106  const Value *Op = *OI;
107  if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) &&
108  PA.related(Ptr, Op, DL))
109  return true;
110  }
111  return false;
112  } else if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
113  // Special-case stores, because we don't care about the stored value, just
114  // the store address.
115  const Value *Op = GetUnderlyingObjCPtr(SI->getPointerOperand(), DL);
116  // If we can't tell what the underlying object was, assume there is a
117  // dependence.
118  return IsPotentialRetainableObjPtr(Op, *PA.getAA()) &&
119  PA.related(Op, Ptr, DL);
120  }
121 
122  // Check each operand for a match.
123  for (User::const_op_iterator OI = Inst->op_begin(), OE = Inst->op_end();
124  OI != OE; ++OI) {
125  const Value *Op = *OI;
126  if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op, DL))
127  return true;
128  }
129  return false;
130 }
131 
132 /// Test if there can be dependencies on Inst through Arg. This function only
133 /// tests dependencies relevant for removing pairs of calls.
134 bool
136  const Value *Arg, ProvenanceAnalysis &PA) {
137  // If we've reached the definition of Arg, stop.
138  if (Inst == Arg)
139  return true;
140 
141  switch (Flavor) {
143  ARCInstKind Class = GetARCInstKind(Inst);
144  switch (Class) {
147  case ARCInstKind::None:
148  return false;
149  default:
150  return CanUse(Inst, Arg, PA, Class);
151  }
152  }
153 
155  ARCInstKind Class = GetARCInstKind(Inst);
156  switch (Class) {
159  // These mark the end and begin of an autorelease pool scope.
160  return true;
161  default:
162  // Nothing else does this.
163  return false;
164  }
165  }
166 
167  case CanChangeRetainCount: {
168  ARCInstKind Class = GetARCInstKind(Inst);
169  switch (Class) {
171  // Conservatively assume this can decrement any count.
172  return true;
174  case ARCInstKind::None:
175  return false;
176  default:
177  return CanAlterRefCount(Inst, Arg, PA, Class);
178  }
179  }
180 
182  switch (GetBasicARCInstKind(Inst)) {
185  // Don't merge an objc_autorelease with an objc_retain inside a different
186  // autoreleasepool scope.
187  return true;
188  case ARCInstKind::Retain:
190  // Check for a retain of the same pointer for merging.
191  return GetArgRCIdentityRoot(Inst) == Arg;
192  default:
193  // Nothing else matters for objc_retainAutorelease formation.
194  return false;
195  }
196 
197  case RetainAutoreleaseRVDep: {
198  ARCInstKind Class = GetBasicARCInstKind(Inst);
199  switch (Class) {
200  case ARCInstKind::Retain:
202  // Check for a retain of the same pointer for merging.
203  return GetArgRCIdentityRoot(Inst) == Arg;
204  default:
205  // Anything that can autorelease interrupts
206  // retainAutoreleaseReturnValue formation.
207  return CanInterruptRV(Class);
208  }
209  }
210 
211  case RetainRVDep:
212  return CanInterruptRV(GetBasicARCInstKind(Inst));
213  }
214 
215  llvm_unreachable("Invalid dependence flavor");
216 }
217 
218 /// Walk up the CFG from StartPos (which is in StartBB) and find local and
219 /// non-local dependencies on Arg.
220 ///
221 /// TODO: Cache results?
222 void
224  const Value *Arg,
225  BasicBlock *StartBB, Instruction *StartInst,
226  SmallPtrSetImpl<Instruction *> &DependingInsts,
228  ProvenanceAnalysis &PA) {
229  BasicBlock::iterator StartPos = StartInst->getIterator();
230 
232  Worklist.push_back(std::make_pair(StartBB, StartPos));
233  do {
234  std::pair<BasicBlock *, BasicBlock::iterator> Pair =
235  Worklist.pop_back_val();
236  BasicBlock *LocalStartBB = Pair.first;
237  BasicBlock::iterator LocalStartPos = Pair.second;
238  BasicBlock::iterator StartBBBegin = LocalStartBB->begin();
239  for (;;) {
240  if (LocalStartPos == StartBBBegin) {
241  pred_iterator PI(LocalStartBB), PE(LocalStartBB, false);
242  if (PI == PE)
243  // If we've reached the function entry, produce a null dependence.
244  DependingInsts.insert(nullptr);
245  else
246  // Add the predecessors to the worklist.
247  do {
248  BasicBlock *PredBB = *PI;
249  if (Visited.insert(PredBB).second)
250  Worklist.push_back(std::make_pair(PredBB, PredBB->end()));
251  } while (++PI != PE);
252  break;
253  }
254 
255  Instruction *Inst = &*--LocalStartPos;
256  if (Depends(Flavor, Inst, Arg, PA)) {
257  DependingInsts.insert(Inst);
258  break;
259  }
260  }
261  } while (!Worklist.empty());
262 
263  // Determine whether the original StartBB post-dominates all of the blocks we
264  // visited. If not, insert a sentinal indicating that most optimizations are
265  // not safe.
266  for (const BasicBlock *BB : Visited) {
267  if (BB == StartBB)
268  continue;
269  const TerminatorInst *TI = cast<TerminatorInst>(&BB->back());
270  for (succ_const_iterator SI(TI), SE(TI, false); SI != SE; ++SI) {
271  const BasicBlock *Succ = *SI;
272  if (Succ != StartBB && !Visited.count(Succ)) {
273  DependingInsts.insert(reinterpret_cast<Instruction *>(-1));
274  return;
275  }
276  }
277  }
278 }
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:109
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.
Compute iterated dominance frontiers using a linear time algorithm.
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...
bool onlyReadsMemory(ImmutableCallSite CS)
Checks if the specified call is known to only read from non-volatile memory (or not access memory at ...
could call objc_release
op_iterator op_begin()
Definition: User.h:214
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:252
objc_autoreleaseReturnValue
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:361
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
IterTy arg_end() const
Definition: CallSite.h:575
This file defines common definitions/declarations used by the ObjC ARC Optimizer. ...
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:306
Subclasses of this class are all able to terminate a basic block.
Definition: InstrTypes.h:54
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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
FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS)
Return the behavior of the given call site.
op_iterator op_end()
Definition: User.h:216
This instruction compares its operands according to the predicate given to the constructor.
self_iterator getIterator()
Definition: ilist_node.h:82
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:254
IterTy arg_begin() const
Definition: CallSite.h:571
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:864
ARCInstKind
Equivalence classes of instructions in the ARC Model.
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:385
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:57
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
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:61
Establish a view to a call site for examination.
Definition: CallSite.h:713
Blocks objc_retainAutoreleaseReturnValue.
#define I(x, y, z)
Definition: MD5.cpp:58
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...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:73
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.