/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Transforms/ObjCARC/DependencyAnalysis.cpp
Line | Count | Source (jump to first uncovered line) |
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 "DependencyAnalysis.h" |
24 | | #include "ObjCARC.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 llvm::objcarc::CanAlterRefCount(const Instruction *Inst, const Value *Ptr, |
36 | | ProvenanceAnalysis &PA, |
37 | 3.11k | ARCInstKind Class) { |
38 | 3.11k | switch (Class) { |
39 | 1.05k | case ARCInstKind::Autorelease: |
40 | 1.05k | case ARCInstKind::AutoreleaseRV: |
41 | 1.05k | case ARCInstKind::IntrinsicUser: |
42 | 1.05k | case ARCInstKind::User: |
43 | 1.05k | // These operations never directly modify a reference count. |
44 | 1.05k | return false; |
45 | 2.05k | default: break; |
46 | 2.05k | } |
47 | 2.05k | |
48 | 2.05k | ImmutableCallSite CS(Inst); |
49 | 2.05k | assert(CS && "Only calls can alter reference counts!"); |
50 | 2.05k | |
51 | 2.05k | // See if AliasAnalysis can help us with the call. |
52 | 2.05k | FunctionModRefBehavior MRB = PA.getAA()->getModRefBehavior(CS); |
53 | 2.05k | if (AliasAnalysis::onlyReadsMemory(MRB)) |
54 | 0 | return false; |
55 | 2.05k | if (2.05k AliasAnalysis::onlyAccessesArgPointees(MRB)2.05k ) { |
56 | 0 | const DataLayout &DL = Inst->getModule()->getDataLayout(); |
57 | 0 | for (ImmutableCallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); |
58 | 0 | I != E0 ; ++I0 ) { |
59 | 0 | const Value *Op = *I; |
60 | 0 | if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && |
61 | 0 | PA.related(Ptr, Op, DL)) |
62 | 0 | return true; |
63 | 0 | } |
64 | 0 | return false; |
65 | 2.05k | } |
66 | 2.05k | |
67 | 2.05k | // Assume the worst. |
68 | 2.05k | return true; |
69 | 2.05k | } |
70 | | |
71 | | bool llvm::objcarc::CanDecrementRefCount(const Instruction *Inst, |
72 | | const Value *Ptr, |
73 | | ProvenanceAnalysis &PA, |
74 | 35 | ARCInstKind Class) { |
75 | 35 | // First perform a quick check if Class can not touch ref counts. |
76 | 35 | if (!CanDecrementRefCount(Class)) |
77 | 28 | return false; |
78 | 7 | |
79 | 7 | // Otherwise, just use CanAlterRefCount for now. |
80 | 7 | return CanAlterRefCount(Inst, Ptr, PA, Class); |
81 | 7 | } |
82 | | |
83 | | /// Test whether the given instruction can "use" the given pointer's object in a |
84 | | /// way that requires the reference count to be positive. |
85 | | bool llvm::objcarc::CanUse(const Instruction *Inst, const Value *Ptr, |
86 | 796 | ProvenanceAnalysis &PA, ARCInstKind Class) { |
87 | 796 | // ARCInstKind::Call operations (as opposed to |
88 | 796 | // ARCInstKind::CallOrUser) never "use" objc pointers. |
89 | 796 | if (Class == ARCInstKind::Call) |
90 | 48 | return false; |
91 | 748 | |
92 | 748 | const DataLayout &DL = Inst->getModule()->getDataLayout(); |
93 | 748 | |
94 | 748 | // Consider various instructions which may have pointer arguments which are |
95 | 748 | // not "uses". |
96 | 748 | if (const ICmpInst *ICI748 = dyn_cast<ICmpInst>(Inst)) { |
97 | 8 | // Comparing a pointer with null, or any other constant, isn't really a use, |
98 | 8 | // because we don't care what the pointer points to, or about the values |
99 | 8 | // of any other dynamic reference-counted pointers. |
100 | 8 | if (!IsPotentialRetainableObjPtr(ICI->getOperand(1), *PA.getAA())) |
101 | 0 | return false; |
102 | 740 | } else if (auto 740 CS740 = ImmutableCallSite(Inst)) { |
103 | 538 | // For calls, just check the arguments (and not the callee operand). |
104 | 538 | for (ImmutableCallSite::arg_iterator OI = CS.arg_begin(), |
105 | 1.08k | OE = CS.arg_end(); OI != OE1.08k ; ++OI548 ) { |
106 | 821 | const Value *Op = *OI; |
107 | 821 | if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && |
108 | 701 | PA.related(Ptr, Op, DL)) |
109 | 273 | return true; |
110 | 821 | } |
111 | 265 | return false; |
112 | 202 | } else if (const StoreInst *202 SI202 = dyn_cast<StoreInst>(Inst)) { |
113 | 106 | // Special-case stores, because we don't care about the stored value, just |
114 | 106 | // the store address. |
115 | 106 | const Value *Op = GetUnderlyingObjCPtr(SI->getPointerOperand(), DL); |
116 | 106 | // If we can't tell what the underlying object was, assume there is a |
117 | 106 | // dependence. |
118 | 106 | return IsPotentialRetainableObjPtr(Op, *PA.getAA()) && |
119 | 82 | PA.related(Op, Ptr, DL); |
120 | 740 | } |
121 | 104 | |
122 | 104 | // Check each operand for a match. |
123 | 104 | for (User::const_op_iterator OI = Inst->op_begin(), OE = Inst->op_end(); |
124 | 186 | OI != OE186 ; ++OI82 ) { |
125 | 104 | const Value *Op = *OI; |
126 | 104 | if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && 104 PA.related(Ptr, Op, DL)104 ) |
127 | 22 | return true; |
128 | 104 | } |
129 | 82 | return false; |
130 | 796 | } |
131 | | |
132 | | /// Test if there can be dependencies on Inst through Arg. This function only |
133 | | /// tests dependencies relevant for removing pairs of calls. |
134 | | bool |
135 | | llvm::objcarc::Depends(DependenceKind Flavor, Instruction *Inst, |
136 | 140 | const Value *Arg, ProvenanceAnalysis &PA) { |
137 | 140 | // If we've reached the definition of Arg, stop. |
138 | 140 | if (Inst == Arg) |
139 | 15 | return true; |
140 | 125 | |
141 | 125 | switch (Flavor) { |
142 | 36 | case NeedsPositiveRetainCount: { |
143 | 36 | ARCInstKind Class = GetARCInstKind(Inst); |
144 | 36 | switch (Class) { |
145 | 6 | case ARCInstKind::AutoreleasepoolPop: |
146 | 6 | case ARCInstKind::AutoreleasepoolPush: |
147 | 6 | case ARCInstKind::None: |
148 | 6 | return false; |
149 | 30 | default: |
150 | 30 | return CanUse(Inst, Arg, PA, Class); |
151 | 0 | } |
152 | 0 | } |
153 | 0 |
|
154 | 8 | case AutoreleasePoolBoundary: { |
155 | 8 | ARCInstKind Class = GetARCInstKind(Inst); |
156 | 8 | switch (Class) { |
157 | 1 | case ARCInstKind::AutoreleasepoolPop: |
158 | 1 | case ARCInstKind::AutoreleasepoolPush: |
159 | 1 | // These mark the end and begin of an autorelease pool scope. |
160 | 1 | return true; |
161 | 7 | default: |
162 | 7 | // Nothing else does this. |
163 | 7 | return false; |
164 | 0 | } |
165 | 0 | } |
166 | 0 |
|
167 | 26 | case CanChangeRetainCount: { |
168 | 26 | ARCInstKind Class = GetARCInstKind(Inst); |
169 | 26 | switch (Class) { |
170 | 1 | case ARCInstKind::AutoreleasepoolPop: |
171 | 1 | // Conservatively assume this can decrement any count. |
172 | 1 | return true; |
173 | 8 | case ARCInstKind::AutoreleasepoolPush: |
174 | 8 | case ARCInstKind::None: |
175 | 8 | return false; |
176 | 17 | default: |
177 | 17 | return CanAlterRefCount(Inst, Arg, PA, Class); |
178 | 0 | } |
179 | 0 | } |
180 | 0 |
|
181 | 49 | case RetainAutoreleaseDep: |
182 | 49 | switch (GetBasicARCInstKind(Inst)) { |
183 | 0 | case ARCInstKind::AutoreleasepoolPop: |
184 | 0 | case ARCInstKind::AutoreleasepoolPush: |
185 | 0 | // Don't merge an objc_autorelease with an objc_retain inside a different |
186 | 0 | // autoreleasepool scope. |
187 | 0 | return true; |
188 | 7 | case ARCInstKind::Retain: |
189 | 7 | case ARCInstKind::RetainRV: |
190 | 7 | // Check for a retain of the same pointer for merging. |
191 | 7 | return GetArgRCIdentityRoot(Inst) == Arg; |
192 | 42 | default: |
193 | 42 | // Nothing else matters for objc_retainAutorelease formation. |
194 | 42 | return false; |
195 | 0 | } |
196 | 0 |
|
197 | 6 | case RetainAutoreleaseRVDep: { |
198 | 6 | ARCInstKind Class = GetBasicARCInstKind(Inst); |
199 | 6 | switch (Class) { |
200 | 3 | case ARCInstKind::Retain: |
201 | 3 | case ARCInstKind::RetainRV: |
202 | 3 | // Check for a retain of the same pointer for merging. |
203 | 3 | return GetArgRCIdentityRoot(Inst) == Arg; |
204 | 3 | default: |
205 | 3 | // Anything that can autorelease interrupts |
206 | 3 | // retainAutoreleaseReturnValue formation. |
207 | 3 | return CanInterruptRV(Class); |
208 | 0 | } |
209 | 0 | } |
210 | 0 |
|
211 | 0 | case RetainRVDep: |
212 | 0 | return CanInterruptRV(GetBasicARCInstKind(Inst)); |
213 | 0 | } |
214 | 0 |
|
215 | 0 | llvm_unreachable0 ("Invalid dependence flavor"); |
216 | 0 | } |
217 | | |
218 | | /// Walk up the CFG from StartPos (which is in StartBB) and find local and |
219 | | /// non-local dependencies on Arg. |
220 | | /// |
221 | | /// TODO: Cache results? |
222 | | void |
223 | | llvm::objcarc::FindDependencies(DependenceKind Flavor, |
224 | | const Value *Arg, |
225 | | BasicBlock *StartBB, Instruction *StartInst, |
226 | | SmallPtrSetImpl<Instruction *> &DependingInsts, |
227 | | SmallPtrSetImpl<const BasicBlock *> &Visited, |
228 | 83 | ProvenanceAnalysis &PA) { |
229 | 83 | BasicBlock::iterator StartPos = StartInst->getIterator(); |
230 | 83 | |
231 | 83 | SmallVector<std::pair<BasicBlock *, BasicBlock::iterator>, 4> Worklist; |
232 | 83 | Worklist.push_back(std::make_pair(StartBB, StartPos)); |
233 | 92 | do { |
234 | 92 | std::pair<BasicBlock *, BasicBlock::iterator> Pair = |
235 | 92 | Worklist.pop_back_val(); |
236 | 92 | BasicBlock *LocalStartBB = Pair.first; |
237 | 92 | BasicBlock::iterator LocalStartPos = Pair.second; |
238 | 92 | BasicBlock::iterator StartBBBegin = LocalStartBB->begin(); |
239 | 161 | for (;;) { |
240 | 161 | if (LocalStartPos == StartBBBegin161 ) { |
241 | 21 | pred_iterator PI(LocalStartBB), PE(LocalStartBB, false); |
242 | 21 | if (PI == PE) |
243 | 21 | // If we've reached the function entry, produce a null dependence. |
244 | 12 | DependingInsts.insert(nullptr); |
245 | 21 | else |
246 | 21 | // Add the predecessors to the worklist. |
247 | 9 | do 9 { |
248 | 14 | BasicBlock *PredBB = *PI; |
249 | 14 | if (Visited.insert(PredBB).second) |
250 | 9 | Worklist.push_back(std::make_pair(PredBB, PredBB->end())); |
251 | 14 | } while (++PI != PE); |
252 | 21 | break; |
253 | 21 | } |
254 | 140 | |
255 | 140 | Instruction *Inst = &*--LocalStartPos; |
256 | 140 | if (Depends(Flavor, Inst, Arg, PA)140 ) { |
257 | 71 | DependingInsts.insert(Inst); |
258 | 71 | break; |
259 | 71 | } |
260 | 92 | } |
261 | 92 | } while (!Worklist.empty()); |
262 | 83 | |
263 | 83 | // Determine whether the original StartBB post-dominates all of the blocks we |
264 | 83 | // visited. If not, insert a sentinal indicating that most optimizations are |
265 | 83 | // not safe. |
266 | 9 | for (const BasicBlock *BB : Visited) { |
267 | 9 | if (BB == StartBB) |
268 | 0 | continue; |
269 | 9 | const TerminatorInst *TI = cast<TerminatorInst>(&BB->back()); |
270 | 23 | for (succ_const_iterator SI(TI), SE(TI, false); SI != SE23 ; ++SI14 ) { |
271 | 15 | const BasicBlock *Succ = *SI; |
272 | 15 | if (Succ != StartBB && 15 !Visited.count(Succ)6 ) { |
273 | 1 | DependingInsts.insert(reinterpret_cast<Instruction *>(-1)); |
274 | 1 | return; |
275 | 1 | } |
276 | 15 | } |
277 | 9 | } |
278 | 83 | } |