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 //===----------------------------------------------------------------------===//
24 #include "DependencyAnalysis.h"
25 #include "ProvenanceAnalysis.h"
26 #include "llvm/IR/CFG.h"
29 using namespace llvm::objcarc;
31 #define DEBUG_TYPE "objc-arc-dependency"
33 /// Test whether the given instruction can result in a reference count
34 /// modification (positive or negative) for the pointer's object.
35 bool llvm::objcarc::CanAlterRefCount(const Instruction *Inst, const Value *Ptr,
36 ProvenanceAnalysis &PA,
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.
48 ImmutableCallSite CS = static_cast<const Value *>(Inst);
49 assert(CS && "Only calls can alter reference counts!");
51 // See if AliasAnalysis can help us with the call.
52 AliasAnalysis::ModRefBehavior MRB = PA.getAA()->getModRefBehavior(CS);
53 if (AliasAnalysis::onlyReadsMemory(MRB))
55 if (AliasAnalysis::onlyAccessesArgPointees(MRB)) {
56 for (ImmutableCallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end();
59 if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op))
69 bool llvm::objcarc::CanDecrementRefCount(const Instruction *Inst,
71 ProvenanceAnalysis &PA,
73 // First perform a quick check if Class can not touch ref counts.
74 if (!CanDecrementRefCount(Class))
77 // Otherwise, just use CanAlterRefCount for now.
78 return CanAlterRefCount(Inst, Ptr, PA, Class);
81 /// Test whether the given instruction can "use" the given pointer's object in a
82 /// way that requires the reference count to be positive.
83 bool llvm::objcarc::CanUse(const Instruction *Inst, const Value *Ptr,
84 ProvenanceAnalysis &PA, ARCInstKind Class) {
85 // ARCInstKind::Call operations (as opposed to
86 // ARCInstKind::CallOrUser) never "use" objc pointers.
87 if (Class == ARCInstKind::Call)
90 // Consider various instructions which may have pointer arguments which are
92 if (const ICmpInst *ICI = dyn_cast<ICmpInst>(Inst)) {
93 // Comparing a pointer with null, or any other constant, isn't really a use,
94 // because we don't care what the pointer points to, or about the values
95 // of any other dynamic reference-counted pointers.
96 if (!IsPotentialRetainableObjPtr(ICI->getOperand(1), *PA.getAA()))
98 } else if (ImmutableCallSite CS = static_cast<const Value *>(Inst)) {
99 // For calls, just check the arguments (and not the callee operand).
100 for (ImmutableCallSite::arg_iterator OI = CS.arg_begin(),
101 OE = CS.arg_end(); OI != OE; ++OI) {
102 const Value *Op = *OI;
103 if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op))
107 } else if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
108 // Special-case stores, because we don't care about the stored value, just
109 // the store address.
110 const Value *Op = GetUnderlyingObjCPtr(SI->getPointerOperand());
111 // If we can't tell what the underlying object was, assume there is a
113 return IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Op, Ptr);
116 // Check each operand for a match.
117 for (User::const_op_iterator OI = Inst->op_begin(), OE = Inst->op_end();
119 const Value *Op = *OI;
120 if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op))
126 /// Test if there can be dependencies on Inst through Arg. This function only
127 /// tests dependencies relevant for removing pairs of calls.
129 llvm::objcarc::Depends(DependenceKind Flavor, Instruction *Inst,
130 const Value *Arg, ProvenanceAnalysis &PA) {
131 // If we've reached the definition of Arg, stop.
136 case NeedsPositiveRetainCount: {
137 ARCInstKind Class = GetARCInstKind(Inst);
139 case ARCInstKind::AutoreleasepoolPop:
140 case ARCInstKind::AutoreleasepoolPush:
141 case ARCInstKind::None:
144 return CanUse(Inst, Arg, PA, Class);
148 case AutoreleasePoolBoundary: {
149 ARCInstKind Class = GetARCInstKind(Inst);
151 case ARCInstKind::AutoreleasepoolPop:
152 case ARCInstKind::AutoreleasepoolPush:
153 // These mark the end and begin of an autorelease pool scope.
156 // Nothing else does this.
161 case CanChangeRetainCount: {
162 ARCInstKind Class = GetARCInstKind(Inst);
164 case ARCInstKind::AutoreleasepoolPop:
165 // Conservatively assume this can decrement any count.
167 case ARCInstKind::AutoreleasepoolPush:
168 case ARCInstKind::None:
171 return CanAlterRefCount(Inst, Arg, PA, Class);
175 case RetainAutoreleaseDep:
176 switch (GetBasicARCInstKind(Inst)) {
177 case ARCInstKind::AutoreleasepoolPop:
178 case ARCInstKind::AutoreleasepoolPush:
179 // Don't merge an objc_autorelease with an objc_retain inside a different
180 // autoreleasepool scope.
182 case ARCInstKind::Retain:
183 case ARCInstKind::RetainRV:
184 // Check for a retain of the same pointer for merging.
185 return GetArgRCIdentityRoot(Inst) == Arg;
187 // Nothing else matters for objc_retainAutorelease formation.
191 case RetainAutoreleaseRVDep: {
192 ARCInstKind Class = GetBasicARCInstKind(Inst);
194 case ARCInstKind::Retain:
195 case ARCInstKind::RetainRV:
196 // Check for a retain of the same pointer for merging.
197 return GetArgRCIdentityRoot(Inst) == Arg;
199 // Anything that can autorelease interrupts
200 // retainAutoreleaseReturnValue formation.
201 return CanInterruptRV(Class);
206 return CanInterruptRV(GetBasicARCInstKind(Inst));
209 llvm_unreachable("Invalid dependence flavor");
212 /// Walk up the CFG from StartPos (which is in StartBB) and find local and
213 /// non-local dependencies on Arg.
215 /// TODO: Cache results?
217 llvm::objcarc::FindDependencies(DependenceKind Flavor,
219 BasicBlock *StartBB, Instruction *StartInst,
220 SmallPtrSetImpl<Instruction *> &DependingInsts,
221 SmallPtrSetImpl<const BasicBlock *> &Visited,
222 ProvenanceAnalysis &PA) {
223 BasicBlock::iterator StartPos = StartInst;
225 SmallVector<std::pair<BasicBlock *, BasicBlock::iterator>, 4> Worklist;
226 Worklist.push_back(std::make_pair(StartBB, StartPos));
228 std::pair<BasicBlock *, BasicBlock::iterator> Pair =
229 Worklist.pop_back_val();
230 BasicBlock *LocalStartBB = Pair.first;
231 BasicBlock::iterator LocalStartPos = Pair.second;
232 BasicBlock::iterator StartBBBegin = LocalStartBB->begin();
234 if (LocalStartPos == StartBBBegin) {
235 pred_iterator PI(LocalStartBB), PE(LocalStartBB, false);
237 // If we've reached the function entry, produce a null dependence.
238 DependingInsts.insert(nullptr);
240 // Add the predecessors to the worklist.
242 BasicBlock *PredBB = *PI;
243 if (Visited.insert(PredBB).second)
244 Worklist.push_back(std::make_pair(PredBB, PredBB->end()));
245 } while (++PI != PE);
249 Instruction *Inst = --LocalStartPos;
250 if (Depends(Flavor, Inst, Arg, PA)) {
251 DependingInsts.insert(Inst);
255 } while (!Worklist.empty());
257 // Determine whether the original StartBB post-dominates all of the blocks we
258 // visited. If not, insert a sentinal indicating that most optimizations are
260 for (const BasicBlock *BB : Visited) {
263 const TerminatorInst *TI = cast<TerminatorInst>(&BB->back());
264 for (succ_const_iterator SI(TI), SE(TI, false); SI != SE; ++SI) {
265 const BasicBlock *Succ = *SI;
266 if (Succ != StartBB && !Visited.count(Succ)) {
267 DependingInsts.insert(reinterpret_cast<Instruction *>(-1));