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