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 "ObjCARC.h"
24#include "DependencyAnalysis.h"
25#include "ProvenanceAnalysis.h"
26#include "llvm/IR/CFG.h"
27
28using namespace llvm;
29using 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.
35bool llvm::objcarc::CanAlterRefCount(const Instruction *Inst, const Value *Ptr,
36                                     ProvenanceAnalysis &PA,
37                                     ARCInstKind Class) {
38  switch (Class) {
39  case ARCInstKind::Autorelease:
40  case ARCInstKind::AutoreleaseRV:
41  case ARCInstKind::IntrinsicUser:
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.
52  FunctionModRefBehavior MRB = PA.getAA()->getModRefBehavior(CS);
53  if (AliasAnalysis::onlyReadsMemory(MRB))
54    return false;
55  if (AliasAnalysis::onlyAccessesArgPointees(MRB)) {
56    const DataLayout &DL = Inst->getModule()->getDataLayout();
57    for (ImmutableCallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end();
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
71bool llvm::objcarc::CanDecrementRefCount(const Instruction *Inst,
72                                         const Value *Ptr,
73                                         ProvenanceAnalysis &PA,
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.
85bool 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.
134bool
135llvm::objcarc::Depends(DependenceKind Flavor, Instruction *Inst,
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) {
142  case NeedsPositiveRetainCount: {
143    ARCInstKind Class = GetARCInstKind(Inst);
144    switch (Class) {
145    case ARCInstKind::AutoreleasepoolPop:
146    case ARCInstKind::AutoreleasepoolPush:
147    case ARCInstKind::None:
148      return false;
149    default:
150      return CanUse(Inst, Arg, PA, Class);
151    }
152  }
153
154  case AutoreleasePoolBoundary: {
155    ARCInstKind Class = GetARCInstKind(Inst);
156    switch (Class) {
157    case ARCInstKind::AutoreleasepoolPop:
158    case ARCInstKind::AutoreleasepoolPush:
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) {
170    case ARCInstKind::AutoreleasepoolPop:
171      // Conservatively assume this can decrement any count.
172      return true;
173    case ARCInstKind::AutoreleasepoolPush:
174    case ARCInstKind::None:
175      return false;
176    default:
177      return CanAlterRefCount(Inst, Arg, PA, Class);
178    }
179  }
180
181  case RetainAutoreleaseDep:
182    switch (GetBasicARCInstKind(Inst)) {
183    case ARCInstKind::AutoreleasepoolPop:
184    case ARCInstKind::AutoreleasepoolPush:
185      // Don't merge an objc_autorelease with an objc_retain inside a different
186      // autoreleasepool scope.
187      return true;
188    case ARCInstKind::Retain:
189    case ARCInstKind::RetainRV:
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:
201    case ARCInstKind::RetainRV:
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?
222void
223llvm::objcarc::FindDependencies(DependenceKind Flavor,
224                                const Value *Arg,
225                                BasicBlock *StartBB, Instruction *StartInst,
226                                SmallPtrSetImpl<Instruction *> &DependingInsts,
227                                SmallPtrSetImpl<const BasicBlock *> &Visited,
228                                ProvenanceAnalysis &PA) {
229  BasicBlock::iterator StartPos = StartInst->getIterator();
230
231  SmallVector<std::pair<BasicBlock *, BasicBlock::iterator>, 4> Worklist;
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}
279