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