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
28 using namespace llvm;
29 using 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.
35 bool
CanAlterRefCount(const Instruction * Inst,const Value * Ptr,ProvenanceAnalysis & PA,InstructionClass Class)36 llvm::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.
72 bool
CanUse(const Instruction * Inst,const Value * Ptr,ProvenanceAnalysis & PA,InstructionClass Class)73 llvm::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.
117 bool
Depends(DependenceKind Flavor,Instruction * Inst,const Value * Arg,ProvenanceAnalysis & PA)118 llvm::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?
205 void
FindDependencies(DependenceKind Flavor,const Value * Arg,BasicBlock * StartBB,Instruction * StartInst,SmallPtrSetImpl<Instruction * > & DependingInsts,SmallPtrSetImpl<const BasicBlock * > & Visited,ProvenanceAnalysis & PA)206 llvm::objcarc::FindDependencies(DependenceKind Flavor,
207 const Value *Arg,
208 BasicBlock *StartBB, Instruction *StartInst,
209 SmallPtrSetImpl<Instruction *> &DependingInsts,
210 SmallPtrSetImpl<const BasicBlock *> &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).second)
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 (const BasicBlock *BB : Visited) {
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