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/Analysis/AliasAnalysis.h"
26#include "llvm/IR/CFG.h"
27
28using namespace llvm;
29using 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.
35bool llvm::objcarc::CanAlterRefCount(const Instruction *Inst, const Value *Ptr,
36 ProvenanceAnalysis &PA,
37 ARCInstKind Class) {
38 switch (Class) {
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.
44 return false;
45 default: break;
46 }
47
48 const auto *Call = cast<CallBase>(Val: Inst);
49
50 // See if AliasAnalysis can help us with the call.
51 MemoryEffects ME = PA.getAA()->getMemoryEffects(Call);
52 if (ME.onlyReadsMemory())
53 return false;
54 if (ME.onlyAccessesArgPointees()) {
55 for (const Value *Op : Call->args()) {
56 if (IsPotentialRetainableObjPtr(Op, AA&: *PA.getAA()) && PA.related(A: Ptr, B: Op))
57 return true;
58 }
59 return false;
60 }
61
62 // Assume the worst.
63 return true;
64}
65
66bool llvm::objcarc::CanDecrementRefCount(const Instruction *Inst,
67 const Value *Ptr,
68 ProvenanceAnalysis &PA,
69 ARCInstKind Class) {
70 // Atomic stores, RMW, and CmpXchg may make a pointer visible to another
71 // thread, which could release it. Treat such instructions as potentially
72 // decrementing refcounts.
73 if (const auto *SI = dyn_cast<StoreInst>(Val: Inst); SI && SI->isAtomic())
74 return true;
75 if (isa<AtomicRMWInst>(Val: Inst) || isa<AtomicCmpXchgInst>(Val: Inst))
76 return true;
77
78 // Perform a quick check if Class can not touch ref counts.
79 if (!CanDecrementRefCount(Kind: Class))
80 return false;
81
82 // Otherwise, just use CanAlterRefCount for now.
83 return CanAlterRefCount(Inst, Ptr, PA, Class);
84}
85
86/// Test whether the given instruction can "use" the given pointer's object in a
87/// way that requires the reference count to be positive.
88bool llvm::objcarc::CanUse(const Instruction *Inst, const Value *Ptr,
89 ProvenanceAnalysis &PA, ARCInstKind Class) {
90 // ARCInstKind::Call operations (as opposed to
91 // ARCInstKind::CallOrUser) never "use" objc pointers.
92 if (Class == ARCInstKind::Call)
93 return false;
94
95 // Consider various instructions which may have pointer arguments which are
96 // not "uses".
97 if (const ICmpInst *ICI = dyn_cast<ICmpInst>(Val: Inst)) {
98 // Comparing a pointer with null, or any other constant, isn't really a use,
99 // because we don't care what the pointer points to, or about the values
100 // of any other dynamic reference-counted pointers.
101 if (!IsPotentialRetainableObjPtr(Op: ICI->getOperand(i_nocapture: 1), AA&: *PA.getAA()))
102 return false;
103 } else if (const auto *CS = dyn_cast<CallBase>(Val: Inst)) {
104 // For calls, just check the arguments (and not the callee operand).
105 for (const Value *Op : CS->args())
106 if (IsPotentialRetainableObjPtr(Op, AA&: *PA.getAA()) && PA.related(A: Ptr, B: Op))
107 return true;
108 return false;
109 } else if (const StoreInst *SI = dyn_cast<StoreInst>(Val: Inst)) {
110 // Special-case stores, because we don't care about the stored value, just
111 // the store address.
112 const Value *Op = GetUnderlyingObjCPtr(V: SI->getPointerOperand());
113 // If we can't tell what the underlying object was, assume there is a
114 // dependence.
115 return IsPotentialRetainableObjPtr(Op, AA&: *PA.getAA()) && PA.related(A: Op, B: Ptr);
116 }
117
118 // Check each operand for a match.
119 for (const Use &U : Inst->operands()) {
120 const Value *Op = U;
121 if (IsPotentialRetainableObjPtr(Op, AA&: *PA.getAA()) && PA.related(A: Ptr, B: Op))
122 return true;
123 }
124 return false;
125}
126
127/// Test if there can be dependencies on Inst through Arg. This function only
128/// tests dependencies relevant for removing pairs of calls.
129bool
130llvm::objcarc::Depends(DependenceKind Flavor, Instruction *Inst,
131 const Value *Arg, ProvenanceAnalysis &PA) {
132 // If we've reached the definition of Arg, stop.
133 if (Inst == Arg)
134 return true;
135
136 switch (Flavor) {
137 case NeedsPositiveRetainCount: {
138 ARCInstKind Class = GetARCInstKind(V: Inst);
139 switch (Class) {
140 case ARCInstKind::AutoreleasepoolPop:
141 case ARCInstKind::AutoreleasepoolPush:
142 case ARCInstKind::None:
143 return false;
144 default:
145 return CanUse(Inst, Ptr: Arg, PA, Class);
146 }
147 }
148
149 case AutoreleasePoolBoundary: {
150 ARCInstKind Class = GetARCInstKind(V: Inst);
151 switch (Class) {
152 case ARCInstKind::AutoreleasepoolPop:
153 case ARCInstKind::AutoreleasepoolPush:
154 // These mark the end and begin of an autorelease pool scope.
155 return true;
156 default:
157 // Nothing else does this.
158 return false;
159 }
160 }
161
162 case CanChangeRetainCount: {
163 ARCInstKind Class = GetARCInstKind(V: Inst);
164 switch (Class) {
165 case ARCInstKind::AutoreleasepoolPop:
166 // Conservatively assume this can decrement any count.
167 return true;
168 case ARCInstKind::AutoreleasepoolPush:
169 case ARCInstKind::None:
170 return false;
171 default:
172 return CanAlterRefCount(Inst, Ptr: Arg, PA, Class);
173 }
174 }
175
176 case RetainAutoreleaseDep:
177 switch (GetBasicARCInstKind(V: Inst)) {
178 case ARCInstKind::AutoreleasepoolPop:
179 case ARCInstKind::AutoreleasepoolPush:
180 // Don't merge an objc_autorelease with an objc_retain inside a different
181 // autoreleasepool scope.
182 return true;
183 case ARCInstKind::Retain:
184 case ARCInstKind::RetainRV:
185 // Check for a retain of the same pointer for merging.
186 return GetArgRCIdentityRoot(Inst) == Arg;
187 default:
188 // Nothing else matters for objc_retainAutorelease formation.
189 return false;
190 }
191
192 case RetainAutoreleaseRVDep: {
193 ARCInstKind Class = GetBasicARCInstKind(V: Inst);
194 switch (Class) {
195 case ARCInstKind::Retain:
196 case ARCInstKind::RetainRV:
197 // Check for a retain of the same pointer for merging.
198 return GetArgRCIdentityRoot(Inst) == Arg;
199 default:
200 // Anything that can autorelease interrupts
201 // retainAutoreleaseReturnValue formation.
202 return CanInterruptRV(Class);
203 }
204 }
205 }
206
207 llvm_unreachable("Invalid dependence flavor");
208}
209
210/// Walk up the CFG from StartPos (which is in StartBB) and find local and
211/// non-local dependencies on Arg.
212///
213/// TODO: Cache results?
214static bool findDependencies(DependenceKind Flavor, const Value *Arg,
215 BasicBlock *StartBB, Instruction *StartInst,
216 SmallPtrSetImpl<Instruction *> &DependingInsts,
217 ProvenanceAnalysis &PA) {
218 BasicBlock::iterator StartPos = StartInst->getIterator();
219
220 SmallPtrSet<const BasicBlock *, 4> Visited;
221 SmallVector<std::pair<BasicBlock *, BasicBlock::iterator>, 4> Worklist;
222 Worklist.push_back(Elt: std::make_pair(x&: StartBB, y&: StartPos));
223 do {
224 std::pair<BasicBlock *, BasicBlock::iterator> Pair =
225 Worklist.pop_back_val();
226 BasicBlock *LocalStartBB = Pair.first;
227 BasicBlock::iterator LocalStartPos = Pair.second;
228 BasicBlock::iterator StartBBBegin = LocalStartBB->begin();
229 for (;;) {
230 if (LocalStartPos == StartBBBegin) {
231 if (pred_empty(BB: LocalStartBB))
232 // Return if we've reached the function entry.
233 return false;
234 // Add the predecessors to the worklist.
235 for (BasicBlock *PredBB : predecessors(BB: LocalStartBB))
236 if (Visited.insert(Ptr: PredBB).second)
237 Worklist.push_back(Elt: std::make_pair(x&: PredBB, y: PredBB->end()));
238 break;
239 }
240
241 Instruction *Inst = &*--LocalStartPos;
242 if (Depends(Flavor, Inst, Arg, PA)) {
243 DependingInsts.insert(Ptr: Inst);
244 break;
245 }
246 }
247 } while (!Worklist.empty());
248
249 // Determine whether the original StartBB post-dominates all of the blocks we
250 // visited. If not, insert a sentinel indicating that most optimizations are
251 // not safe.
252 for (const BasicBlock *BB : Visited) {
253 if (BB == StartBB)
254 continue;
255 for (const BasicBlock *Succ : successors(BB))
256 if (Succ != StartBB && !Visited.count(Ptr: Succ))
257 return false;
258 }
259
260 return true;
261}
262
263llvm::Instruction *llvm::objcarc::findSingleDependency(DependenceKind Flavor,
264 const Value *Arg,
265 BasicBlock *StartBB,
266 Instruction *StartInst,
267 ProvenanceAnalysis &PA) {
268 SmallPtrSet<Instruction *, 4> DependingInsts;
269
270 if (!findDependencies(Flavor, Arg, StartBB, StartInst, DependingInsts, PA) ||
271 DependingInsts.size() != 1)
272 return nullptr;
273 return *DependingInsts.begin();
274}
275