LLVM 20.0.0git
DependencyAnalysis.cpp
Go to the documentation of this file.
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"
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.
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>(Inst);
49
50 // See if AliasAnalysis can help us with the call.
52 if (ME.onlyReadsMemory())
53 return false;
54 if (ME.onlyAccessesArgPointees()) {
55 for (const Value *Op : Call->args()) {
57 return true;
58 }
59 return false;
60 }
61
62 // Assume the worst.
63 return true;
64}
65
67 const Value *Ptr,
69 ARCInstKind Class) {
70 // First perform a quick check if Class can not touch ref counts.
71 if (!CanDecrementRefCount(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,
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>(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(ICI->getOperand(1), *PA.getAA()))
94 return false;
95 } else if (const auto *CS = dyn_cast<CallBase>(Inst)) {
96 // For calls, just check the arguments (and not the callee operand).
97 for (const Value *Op : CS->args())
99 return true;
100 return false;
101 } else if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
102 // Special-case stores, because we don't care about the stored value, just
103 // the store address.
104 const Value *Op = GetUnderlyingObjCPtr(SI->getPointerOperand());
105 // If we can't tell what the underlying object was, assume there is a
106 // dependence.
107 return IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Op, 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, *PA.getAA()) && PA.related(Ptr, 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
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) {
130 ARCInstKind Class = GetARCInstKind(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, Arg, PA, Class);
138 }
139 }
140
142 ARCInstKind Class = GetARCInstKind(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
155 ARCInstKind Class = GetARCInstKind(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, Arg, PA, Class);
165 }
166 }
167
169 switch (GetBasicARCInstKind(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
185 ARCInstKind Class = GetBasicARCInstKind(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
214 Worklist.push_back(std::make_pair(StartBB, 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(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(LocalStartBB))
228 if (Visited.insert(PredBB).second)
229 Worklist.push_back(std::make_pair(PredBB, PredBB->end()));
230 break;
231 }
232
233 Instruction *Inst = &*--LocalStartPos;
234 if (Depends(Flavor, Inst, Arg, PA)) {
235 DependingInsts.insert(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(Succ))
249 return false;
250 }
251
252 return true;
253}
254
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}
static bool findDependencies(DependenceKind Flavor, const Value *Arg, BasicBlock *StartBB, Instruction *StartInst, SmallPtrSetImpl< Instruction * > &DependingInsts, ProvenanceAnalysis &PA)
Walk up the CFG from StartPos (which is in StartBB) and find local and non-local dependencies on Arg.
This file declares special dependency analysis routines used in Objective C ARC Optimizations.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
This file declares a special form of Alias Analysis called Provenance Analysis''.
MemoryEffects getMemoryEffects(const CallBase *Call)
Return the behavior of the given call site.
LLVM Basic Block Representation.
Definition: BasicBlock.h:61
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:448
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:177
This class represents an Operation in the Expression.
This instruction compares its operands according to the predicate given to the constructor.
bool onlyAccessesArgPointees() const
Whether this function only (at most) accesses argument memory.
Definition: ModRef.h:201
bool onlyReadsMemory() const
Whether this function only (at most) reads memory.
Definition: ModRef.h:195
size_type size() const
Definition: SmallPtrSet.h:96
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:347
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:436
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:368
iterator begin() const
Definition: SmallPtrSet.h:456
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:503
bool empty() const
Definition: SmallVector.h:95
void push_back(const T &Elt)
Definition: SmallVector.h:427
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1210
An instruction for storing to memory.
Definition: Instructions.h:290
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
op_range operands()
Definition: User.h:242
LLVM Value Representation.
Definition: Value.h:74
self_iterator getIterator()
Definition: ilist_node.h:132
This is similar to BasicAliasAnalysis, and it uses many of the same techniques, except it uses specia...
bool related(const Value *A, const Value *B)
This file defines common definitions/declarations used by the ObjC ARC Optimizer.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
bool IsPotentialRetainableObjPtr(const Value *Op)
Test whether the given value is possible a retainable object pointer.
bool CanAlterRefCount(const Instruction *Inst, const Value *Ptr, ProvenanceAnalysis &PA, ARCInstKind Class)
Test whether the given instruction can result in a reference count modification (positive or negative...
DependenceKind
Defines different dependence kinds among various ARC constructs.
@ RetainAutoreleaseDep
Blocks objc_retainAutorelease.
@ RetainAutoreleaseRVDep
Blocks objc_retainAutoreleaseReturnValue.
ARCInstKind
Equivalence classes of instructions in the ARC Model.
@ Call
could call objc_release
llvm::Instruction * findSingleDependency(DependenceKind Flavor, const Value *Arg, BasicBlock *StartBB, Instruction *StartInst, ProvenanceAnalysis &PA)
Find dependent instructions.
ARCInstKind GetBasicARCInstKind(const Value *V)
Determine which objc runtime call instruction class V belongs to.
ARCInstKind GetARCInstKind(const Value *V)
Map V to its ARCInstKind equivalence class.
bool Depends(DependenceKind Flavor, Instruction *Inst, const Value *Arg, ProvenanceAnalysis &PA)
Test if there can be dependencies on Inst through Arg.
bool CanInterruptRV(ARCInstKind Class)
Test whether the given instruction can autorelease any pointer or cause an autoreleasepool pop.
Value * GetArgRCIdentityRoot(Value *Inst)
Assuming the given instruction is one of the special calls such as objc_retain or objc_release,...
bool CanDecrementRefCount(ARCInstKind Kind)
Returns false if conservatively we can prove that any instruction mapped to this kind can not decreme...
const Value * GetUnderlyingObjCPtr(const Value *V)
This is a wrapper around getUnderlyingObject which also knows how to look through objc_retain and obj...
bool CanUse(const Instruction *Inst, const Value *Ptr, ProvenanceAnalysis &PA, ARCInstKind Class)
Test whether the given instruction can "use" the given pointer's object in a way that requires the re...
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto successors(const MachineBasicBlock *BB)
auto predecessors(const MachineBasicBlock *BB)
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:118