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#define DEBUG_TYPE "objc-arc-dependency"
24#include "ObjCARC.h"
25#include "DependencyAnalysis.h"
26#include "ProvenanceAnalysis.h"
27#include "llvm/Support/CFG.h"
28
29using namespace llvm;
30using namespace llvm::objcarc;
31
32/// Test whether the given instruction can result in a reference count
33/// modification (positive or negative) for the pointer's object.
34bool
35llvm::objcarc::CanAlterRefCount(const Instruction *Inst, const Value *Ptr,
36                                ProvenanceAnalysis &PA,
37                                InstructionClass Class) {
38  switch (Class) {
39  case IC_Autorelease:
40  case IC_AutoreleaseRV:
41  case IC_User:
42    // These operations never directly modify a reference count.
43    return false;
44  default: break;
45  }
46
47  ImmutableCallSite CS = static_cast<const Value *>(Inst);
48  assert(CS && "Only calls can alter reference counts!");
49
50  // See if AliasAnalysis can help us with the call.
51  AliasAnalysis::ModRefBehavior MRB = PA.getAA()->getModRefBehavior(CS);
52  if (AliasAnalysis::onlyReadsMemory(MRB))
53    return false;
54  if (AliasAnalysis::onlyAccessesArgPointees(MRB)) {
55    for (ImmutableCallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end();
56         I != E; ++I) {
57      const Value *Op = *I;
58      if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op))
59        return true;
60    }
61    return false;
62  }
63
64  // Assume the worst.
65  return true;
66}
67
68/// Test whether the given instruction can "use" the given pointer's object in a
69/// way that requires the reference count to be positive.
70bool
71llvm::objcarc::CanUse(const Instruction *Inst, const Value *Ptr,
72                      ProvenanceAnalysis &PA, InstructionClass Class) {
73  // IC_Call operations (as opposed to IC_CallOrUser) never "use" objc pointers.
74  if (Class == IC_Call)
75    return false;
76
77  // Consider various instructions which may have pointer arguments which are
78  // not "uses".
79  if (const ICmpInst *ICI = dyn_cast<ICmpInst>(Inst)) {
80    // Comparing a pointer with null, or any other constant, isn't really a use,
81    // because we don't care what the pointer points to, or about the values
82    // of any other dynamic reference-counted pointers.
83    if (!IsPotentialRetainableObjPtr(ICI->getOperand(1), *PA.getAA()))
84      return false;
85  } else if (ImmutableCallSite CS = static_cast<const Value *>(Inst)) {
86    // For calls, just check the arguments (and not the callee operand).
87    for (ImmutableCallSite::arg_iterator OI = CS.arg_begin(),
88         OE = CS.arg_end(); OI != OE; ++OI) {
89      const Value *Op = *OI;
90      if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op))
91        return true;
92    }
93    return false;
94  } else if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
95    // Special-case stores, because we don't care about the stored value, just
96    // the store address.
97    const Value *Op = GetUnderlyingObjCPtr(SI->getPointerOperand());
98    // If we can't tell what the underlying object was, assume there is a
99    // dependence.
100    return IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Op, Ptr);
101  }
102
103  // Check each operand for a match.
104  for (User::const_op_iterator OI = Inst->op_begin(), OE = Inst->op_end();
105       OI != OE; ++OI) {
106    const Value *Op = *OI;
107    if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op))
108      return true;
109  }
110  return false;
111}
112
113/// Test if there can be dependencies on Inst through Arg. This function only
114/// tests dependencies relevant for removing pairs of calls.
115bool
116llvm::objcarc::Depends(DependenceKind Flavor, Instruction *Inst,
117                       const Value *Arg, ProvenanceAnalysis &PA) {
118  // If we've reached the definition of Arg, stop.
119  if (Inst == Arg)
120    return true;
121
122  switch (Flavor) {
123  case NeedsPositiveRetainCount: {
124    InstructionClass Class = GetInstructionClass(Inst);
125    switch (Class) {
126    case IC_AutoreleasepoolPop:
127    case IC_AutoreleasepoolPush:
128    case IC_None:
129      return false;
130    default:
131      return CanUse(Inst, Arg, PA, Class);
132    }
133  }
134
135  case AutoreleasePoolBoundary: {
136    InstructionClass Class = GetInstructionClass(Inst);
137    switch (Class) {
138    case IC_AutoreleasepoolPop:
139    case IC_AutoreleasepoolPush:
140      // These mark the end and begin of an autorelease pool scope.
141      return true;
142    default:
143      // Nothing else does this.
144      return false;
145    }
146  }
147
148  case CanChangeRetainCount: {
149    InstructionClass Class = GetInstructionClass(Inst);
150    switch (Class) {
151    case IC_AutoreleasepoolPop:
152      // Conservatively assume this can decrement any count.
153      return true;
154    case IC_AutoreleasepoolPush:
155    case IC_None:
156      return false;
157    default:
158      return CanAlterRefCount(Inst, Arg, PA, Class);
159    }
160  }
161
162  case RetainAutoreleaseDep:
163    switch (GetBasicInstructionClass(Inst)) {
164    case IC_AutoreleasepoolPop:
165    case IC_AutoreleasepoolPush:
166      // Don't merge an objc_autorelease with an objc_retain inside a different
167      // autoreleasepool scope.
168      return true;
169    case IC_Retain:
170    case IC_RetainRV:
171      // Check for a retain of the same pointer for merging.
172      return GetObjCArg(Inst) == Arg;
173    default:
174      // Nothing else matters for objc_retainAutorelease formation.
175      return false;
176    }
177
178  case RetainAutoreleaseRVDep: {
179    InstructionClass Class = GetBasicInstructionClass(Inst);
180    switch (Class) {
181    case IC_Retain:
182    case IC_RetainRV:
183      // Check for a retain of the same pointer for merging.
184      return GetObjCArg(Inst) == Arg;
185    default:
186      // Anything that can autorelease interrupts
187      // retainAutoreleaseReturnValue formation.
188      return CanInterruptRV(Class);
189    }
190  }
191
192  case RetainRVDep:
193    return CanInterruptRV(GetBasicInstructionClass(Inst));
194  }
195
196  llvm_unreachable("Invalid dependence flavor");
197}
198
199/// Walk up the CFG from StartPos (which is in StartBB) and find local and
200/// non-local dependencies on Arg.
201///
202/// TODO: Cache results?
203void
204llvm::objcarc::FindDependencies(DependenceKind Flavor,
205                                const Value *Arg,
206                                BasicBlock *StartBB, Instruction *StartInst,
207                                SmallPtrSet<Instruction *, 4> &DependingInsts,
208                                SmallPtrSet<const BasicBlock *, 4> &Visited,
209                                ProvenanceAnalysis &PA) {
210  BasicBlock::iterator StartPos = StartInst;
211
212  SmallVector<std::pair<BasicBlock *, BasicBlock::iterator>, 4> Worklist;
213  Worklist.push_back(std::make_pair(StartBB, StartPos));
214  do {
215    std::pair<BasicBlock *, BasicBlock::iterator> Pair =
216      Worklist.pop_back_val();
217    BasicBlock *LocalStartBB = Pair.first;
218    BasicBlock::iterator LocalStartPos = Pair.second;
219    BasicBlock::iterator StartBBBegin = LocalStartBB->begin();
220    for (;;) {
221      if (LocalStartPos == StartBBBegin) {
222        pred_iterator PI(LocalStartBB), PE(LocalStartBB, false);
223        if (PI == PE)
224          // If we've reached the function entry, produce a null dependence.
225          DependingInsts.insert(0);
226        else
227          // Add the predecessors to the worklist.
228          do {
229            BasicBlock *PredBB = *PI;
230            if (Visited.insert(PredBB))
231              Worklist.push_back(std::make_pair(PredBB, PredBB->end()));
232          } while (++PI != PE);
233        break;
234      }
235
236      Instruction *Inst = --LocalStartPos;
237      if (Depends(Flavor, Inst, Arg, PA)) {
238        DependingInsts.insert(Inst);
239        break;
240      }
241    }
242  } while (!Worklist.empty());
243
244  // Determine whether the original StartBB post-dominates all of the blocks we
245  // visited. If not, insert a sentinal indicating that most optimizations are
246  // not safe.
247  for (SmallPtrSet<const BasicBlock *, 4>::const_iterator I = Visited.begin(),
248       E = Visited.end(); I != E; ++I) {
249    const BasicBlock *BB = *I;
250    if (BB == StartBB)
251      continue;
252    const TerminatorInst *TI = cast<TerminatorInst>(&BB->back());
253    for (succ_const_iterator SI(TI), SE(TI, false); SI != SE; ++SI) {
254      const BasicBlock *Succ = *SI;
255      if (Succ != StartBB && !Visited.count(Succ)) {
256        DependingInsts.insert(reinterpret_cast<Instruction *>(-1));
257        return;
258      }
259    }
260  }
261}
262