LLVM 22.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) {
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) {
135 return false;
136 default:
137 return CanUse(Inst, Arg, PA, Class);
138 }
139 }
140
142 ARCInstKind Class = GetARCInstKind(Inst);
143 switch (Class) {
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) {
158 // Conservatively assume this can decrement any count.
159 return true;
162 return false;
163 default:
164 return CanAlterRefCount(Inst, Arg, PA, Class);
165 }
166 }
167
169 switch (GetBasicARCInstKind(Inst)) {
172 // Don't merge an objc_autorelease with an objc_retain inside a different
173 // autoreleasepool scope.
174 return true;
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) {
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''.
bool related(const Value *A, const Value *B)
AAResults * getAA() const
LLVM_ABI MemoryEffects getMemoryEffects(const CallBase *Call)
Return the behavior of the given call site.
LLVM Basic Block Representation.
Definition BasicBlock.h:62
iterator begin()
Instruction iterator methods.
Definition BasicBlock.h:459
InstListType::iterator iterator
Instruction iterators...
Definition BasicBlock.h:170
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:224
bool onlyReadsMemory() const
Whether this function only (at most) reads memory.
Definition ModRef.h:218
size_type size() const
Definition SmallPtrSet.h:99
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
iterator begin() const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
A Use represents the edge between a Value definition and its users.
Definition Use.h:35
op_range operands()
Definition User.h:292
LLVM Value Representation.
Definition Value.h:75
self_iterator getIterator()
Definition ilist_node.h:130
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.
@ AutoreleasepoolPop
objc_autoreleasePoolPop
@ AutoreleasepoolPush
objc_autoreleasePoolPush
@ Autorelease
objc_autorelease
@ None
anything that is inert from an ARC perspective.
@ User
could "use" a pointer
@ RetainRV
objc_retainAutoreleasedReturnValue
@ AutoreleaseRV
objc_autoreleaseReturnValue
@ Call
could call objc_release
@ IntrinsicUser
llvm.objc.clang.arc.use
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.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:649
auto successors(const MachineBasicBlock *BB)
MemoryEffectsBase< IRMemLocation > MemoryEffects
Summary of how a function affects memory in the program.
Definition ModRef.h:296
DWARFExpression::Operation Op
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:565
auto predecessors(const MachineBasicBlock *BB)
bool pred_empty(const BasicBlock *BB)
Definition CFG.h:119