1 //===- DependencyAnalysis.cpp - ObjC ARC Optimization ---------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 /// This file defines special dependency analysis routines used in Objective C
12 /// ARC Optimizations.
14 /// WARNING: This file knows about certain library functions. It recognizes them
15 /// by name, and hardwires knowledge of their semantics.
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.
21 //===----------------------------------------------------------------------===//
23 #define DEBUG_TYPE "objc-arc-dependency"
25 #include "DependencyAnalysis.h"
26 #include "ProvenanceAnalysis.h"
27 #include "llvm/Support/CFG.h"
30 using namespace llvm::objcarc;
32 /// Test whether the given instruction can result in a reference count
33 /// modification (positive or negative) for the pointer's object.
35 llvm::objcarc::CanAlterRefCount(const Instruction *Inst, const Value *Ptr,
36 ProvenanceAnalysis &PA,
37 InstructionClass Class) {
40 case IC_AutoreleaseRV:
42 // These operations never directly modify a reference count.
47 ImmutableCallSite CS = static_cast<const Value *>(Inst);
48 assert(CS && "Only calls can alter reference counts!");
50 // See if AliasAnalysis can help us with the call.
51 AliasAnalysis::ModRefBehavior MRB = PA.getAA()->getModRefBehavior(CS);
52 if (AliasAnalysis::onlyReadsMemory(MRB))
54 if (AliasAnalysis::onlyAccessesArgPointees(MRB)) {
55 for (ImmutableCallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end();
58 if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op))
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.
71 llvm::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.
77 // Consider various instructions which may have pointer arguments which are
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()))
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))
94 } else if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
95 // Special-case stores, because we don't care about the stored value, just
97 const Value *Op = GetUnderlyingObjCPtr(SI->getPointerOperand());
98 // If we can't tell what the underlying object was, assume there is a
100 return IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Op, Ptr);
103 // Check each operand for a match.
104 for (User::const_op_iterator OI = Inst->op_begin(), OE = Inst->op_end();
106 const Value *Op = *OI;
107 if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op))
113 /// Test if there can be dependencies on Inst through Arg. This function only
114 /// tests dependencies relevant for removing pairs of calls.
116 llvm::objcarc::Depends(DependenceKind Flavor, Instruction *Inst,
117 const Value *Arg, ProvenanceAnalysis &PA) {
118 // If we've reached the definition of Arg, stop.
123 case NeedsPositiveRetainCount: {
124 InstructionClass Class = GetInstructionClass(Inst);
126 case IC_AutoreleasepoolPop:
127 case IC_AutoreleasepoolPush:
131 return CanUse(Inst, Arg, PA, Class);
135 case AutoreleasePoolBoundary: {
136 InstructionClass Class = GetInstructionClass(Inst);
138 case IC_AutoreleasepoolPop:
139 case IC_AutoreleasepoolPush:
140 // These mark the end and begin of an autorelease pool scope.
143 // Nothing else does this.
148 case CanChangeRetainCount: {
149 InstructionClass Class = GetInstructionClass(Inst);
151 case IC_AutoreleasepoolPop:
152 // Conservatively assume this can decrement any count.
154 case IC_AutoreleasepoolPush:
158 return CanAlterRefCount(Inst, Arg, PA, Class);
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.
171 // Check for a retain of the same pointer for merging.
172 return GetObjCArg(Inst) == Arg;
174 // Nothing else matters for objc_retainAutorelease formation.
178 case RetainAutoreleaseRVDep: {
179 InstructionClass Class = GetBasicInstructionClass(Inst);
183 // Check for a retain of the same pointer for merging.
184 return GetObjCArg(Inst) == Arg;
186 // Anything that can autorelease interrupts
187 // retainAutoreleaseReturnValue formation.
188 return CanInterruptRV(Class);
193 return CanInterruptRV(GetBasicInstructionClass(Inst));
196 llvm_unreachable("Invalid dependence flavor");
199 /// Walk up the CFG from StartPos (which is in StartBB) and find local and
200 /// non-local dependencies on Arg.
202 /// TODO: Cache results?
204 llvm::objcarc::FindDependencies(DependenceKind Flavor,
206 BasicBlock *StartBB, Instruction *StartInst,
207 SmallPtrSet<Instruction *, 4> &DependingInsts,
208 SmallPtrSet<const BasicBlock *, 4> &Visited,
209 ProvenanceAnalysis &PA) {
210 BasicBlock::iterator StartPos = StartInst;
212 SmallVector<std::pair<BasicBlock *, BasicBlock::iterator>, 4> Worklist;
213 Worklist.push_back(std::make_pair(StartBB, StartPos));
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();
221 if (LocalStartPos == StartBBBegin) {
222 pred_iterator PI(LocalStartBB), PE(LocalStartBB, false);
224 // If we've reached the function entry, produce a null dependence.
225 DependingInsts.insert(0);
227 // Add the predecessors to the worklist.
229 BasicBlock *PredBB = *PI;
230 if (Visited.insert(PredBB))
231 Worklist.push_back(std::make_pair(PredBB, PredBB->end()));
232 } while (++PI != PE);
236 Instruction *Inst = --LocalStartPos;
237 if (Depends(Flavor, Inst, Arg, PA)) {
238 DependingInsts.insert(Inst);
242 } while (!Worklist.empty());
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
247 for (SmallPtrSet<const BasicBlock *, 4>::const_iterator I = Visited.begin(),
248 E = Visited.end(); I != E; ++I) {
249 const BasicBlock *BB = *I;
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));