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