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