LLVM  12.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"
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,
36  ARCInstKind Class) {
37  switch (Class) {
41  case ARCInstKind::User:
42  // These operations never directly modify a reference count.
43  return false;
44  default: break;
45  }
46 
47  const auto *Call = cast<CallBase>(Inst);
48 
49  // See if AliasAnalysis can help us with the call.
52  return false;
54  const DataLayout &DL = Inst->getModule()->getDataLayout();
55  for (const Value *Op : Call->args()) {
56  if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) &&
57  PA.related(Ptr, Op, DL))
58  return true;
59  }
60  return false;
61  }
62 
63  // Assume the worst.
64  return true;
65 }
66 
68  const Value *Ptr,
70  ARCInstKind Class) {
71  // First perform a quick check if Class can not touch ref counts.
72  if (!CanDecrementRefCount(Class))
73  return false;
74 
75  // Otherwise, just use CanAlterRefCount for now.
76  return CanAlterRefCount(Inst, Ptr, PA, Class);
77 }
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  ProvenanceAnalysis &PA, ARCInstKind Class) {
83  // ARCInstKind::Call operations (as opposed to
84  // ARCInstKind::CallOrUser) never "use" objc pointers.
85  if (Class == ARCInstKind::Call)
86  return false;
87 
88  const DataLayout &DL = Inst->getModule()->getDataLayout();
89 
90  // Consider various instructions which may have pointer arguments which are
91  // not "uses".
92  if (const ICmpInst *ICI = dyn_cast<ICmpInst>(Inst)) {
93  // Comparing a pointer with null, or any other constant, isn't really a use,
94  // because we don't care what the pointer points to, or about the values
95  // of any other dynamic reference-counted pointers.
96  if (!IsPotentialRetainableObjPtr(ICI->getOperand(1), *PA.getAA()))
97  return false;
98  } else if (const auto *CS = dyn_cast<CallBase>(Inst)) {
99  // For calls, just check the arguments (and not the callee operand).
100  for (auto OI = CS->arg_begin(), OE = CS->arg_end(); OI != OE; ++OI) {
101  const Value *Op = *OI;
102  if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) &&
103  PA.related(Ptr, Op, DL))
104  return true;
105  }
106  return false;
107  } else if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
108  // Special-case stores, because we don't care about the stored value, just
109  // the store address.
110  const Value *Op = GetUnderlyingObjCPtr(SI->getPointerOperand(), DL);
111  // If we can't tell what the underlying object was, assume there is a
112  // dependence.
113  return IsPotentialRetainableObjPtr(Op, *PA.getAA()) &&
114  PA.related(Op, Ptr, DL);
115  }
116 
117  // Check each operand for a match.
118  for (User::const_op_iterator OI = Inst->op_begin(), OE = Inst->op_end();
119  OI != OE; ++OI) {
120  const Value *Op = *OI;
121  if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op, DL))
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.
129 bool
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) {
138  ARCInstKind Class = GetARCInstKind(Inst);
139  switch (Class) {
142  case ARCInstKind::None:
143  return false;
144  default:
145  return CanUse(Inst, Arg, PA, Class);
146  }
147  }
148 
150  ARCInstKind Class = GetARCInstKind(Inst);
151  switch (Class) {
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(Inst);
164  switch (Class) {
166  // Conservatively assume this can decrement any count.
167  return true;
169  case ARCInstKind::None:
170  return false;
171  default:
172  return CanAlterRefCount(Inst, Arg, PA, Class);
173  }
174  }
175 
177  switch (GetBasicARCInstKind(Inst)) {
180  // Don't merge an objc_autorelease with an objc_retain inside a different
181  // autoreleasepool scope.
182  return true;
183  case ARCInstKind::Retain:
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(Inst);
194  switch (Class) {
195  case ARCInstKind::Retain:
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  case RetainRVDep:
207  return CanInterruptRV(GetBasicARCInstKind(Inst));
208  }
209 
210  llvm_unreachable("Invalid dependence flavor");
211 }
212 
213 /// Walk up the CFG from StartPos (which is in StartBB) and find local and
214 /// non-local dependencies on Arg.
215 ///
216 /// TODO: Cache results?
217 void
219  const Value *Arg,
220  BasicBlock *StartBB, Instruction *StartInst,
221  SmallPtrSetImpl<Instruction *> &DependingInsts,
223  ProvenanceAnalysis &PA) {
224  BasicBlock::iterator StartPos = StartInst->getIterator();
225 
227  Worklist.push_back(std::make_pair(StartBB, StartPos));
228  do {
229  std::pair<BasicBlock *, BasicBlock::iterator> Pair =
230  Worklist.pop_back_val();
231  BasicBlock *LocalStartBB = Pair.first;
232  BasicBlock::iterator LocalStartPos = Pair.second;
233  BasicBlock::iterator StartBBBegin = LocalStartBB->begin();
234  for (;;) {
235  if (LocalStartPos == StartBBBegin) {
236  pred_iterator PI(LocalStartBB), PE(LocalStartBB, false);
237  if (PI == PE)
238  // If we've reached the function entry, produce a null dependence.
239  DependingInsts.insert(nullptr);
240  else
241  // Add the predecessors to the worklist.
242  do {
243  BasicBlock *PredBB = *PI;
244  if (Visited.insert(PredBB).second)
245  Worklist.push_back(std::make_pair(PredBB, PredBB->end()));
246  } while (++PI != PE);
247  break;
248  }
249 
250  Instruction *Inst = &*--LocalStartPos;
251  if (Depends(Flavor, Inst, Arg, PA)) {
252  DependingInsts.insert(Inst);
253  break;
254  }
255  }
256  } while (!Worklist.empty());
257 
258  // Determine whether the original StartBB post-dominates all of the blocks we
259  // visited. If not, insert a sentinal indicating that most optimizations are
260  // not safe.
261  for (const BasicBlock *BB : Visited) {
262  if (BB == StartBB)
263  continue;
264  for (const BasicBlock *Succ : successors(BB))
265  if (Succ != StartBB && !Visited.count(Succ)) {
266  DependingInsts.insert(reinterpret_cast<Instruction *>(-1));
267  return;
268  }
269  }
270 }
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
This file declares special dependency analysis routines used in Objective C ARC Optimizations.
ARCInstKind GetARCInstKind(const Value *V)
Map V to its ARCInstKind equivalence class.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
bool CanUse(const Instruction *Inst, const Value *Ptr, ProvenanceAnalysis &PA, ARCInstKind Class)
Test whether the given instruction can "use" the given pointer&#39;s object in a way that requires the re...
Blocks objc_retainAutorelease.
Value * GetArgRCIdentityRoot(Value *Inst)
Assuming the given instruction is one of the special calls such as objc_retain or objc_release...
could call objc_release
op_iterator op_begin()
Definition: User.h:234
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:289
objc_autoreleaseReturnValue
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:397
bool Depends(DependenceKind Flavor, Instruction *Inst, const Value *Arg, ProvenanceAnalysis &PA)
Test if there can be dependencies on Inst through Arg.
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
This file defines common definitions/declarations used by the ObjC ARC Optimizer. ...
FunctionModRefBehavior getModRefBehavior(const CallBase *Call)
Return the behavior of the given call site.
objc_retainAutoreleasedReturnValue
bool IsPotentialRetainableObjPtr(const Value *Op)
Test whether the given value is possible a retainable object pointer.
FunctionModRefBehavior
Summary of how a function affects memory in the program.
An instruction for storing to memory.
Definition: Instructions.h:302
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
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:364
op_iterator op_end()
Definition: User.h:236
This instruction compares its operands according to the predicate given to the constructor.
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
self_iterator getIterator()
Definition: ilist_node.h:81
bool onlyReadsMemory(const CallBase *Call)
Checks if the specified call is known to only read from non-volatile memory (or not access memory at ...
anything that is inert from an ARC perspective.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
ARCInstKind GetBasicARCInstKind(const Value *V)
Determine which objc runtime call instruction class V belongs to.
bool CanDecrementRefCount(ARCInstKind Kind)
Returns false if conservatively we can prove that any instruction mapped to this kind can not decreme...
DependenceKind
Defines different dependence kinds among various ARC constructs.
Iterator for intrusive lists based on ilist_node.
iterator end()
Definition: BasicBlock.h:291
This file declares a special form of Alias Analysis called ``Provenance Analysis&#39;&#39;.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:883
ARCInstKind
Equivalence classes of instructions in the ARC Model.
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:420
bool related(const Value *A, const Value *B, const DataLayout &DL)
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:68
void FindDependencies(DependenceKind Flavor, const Value *Arg, BasicBlock *StartBB, Instruction *StartInst, SmallPtrSetImpl< Instruction *> &DependingInstructions, SmallPtrSetImpl< const BasicBlock *> &Visited, ProvenanceAnalysis &PA)
Walk up the CFG from StartPos (which is in StartBB) and find local and non-local dependencies on Arg...
could "use" a pointer
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
static bool onlyAccessesArgPointees(FunctionModRefBehavior MRB)
Checks if functions with the specified behavior are known to read and write at most from objects poin...
Blocks objc_retainAutoreleaseReturnValue.
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...
const Value * GetUnderlyingObjCPtr(const Value *V, const DataLayout &DL)
This is a wrapper around getUnderlyingObject which also knows how to look through objc_retain and obj...
LLVM Value Representation.
Definition: Value.h:74
succ_range successors(Instruction *I)
Definition: CFG.h:260
This is similar to BasicAliasAnalysis, and it uses many of the same techniques, except it uses specia...
bool CanInterruptRV(ARCInstKind Class)
Test whether the given instruction can autorelease any pointer or cause an autoreleasepool pop...
Blocks objc_retainAutoreleasedReturnValue.
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL