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>(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, *PA.getAA()) && PA.related(Ptr, 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(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>(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())
98      if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op))
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
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(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
141  case AutoreleasePoolBoundary: {
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
154  case CanChangeRetainCount: {
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
168  case RetainAutoreleaseDep:
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
184  case RetainAutoreleaseRVDep: {
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
212  SmallPtrSet<const BasicBlock *, 4> Visited;
213  SmallVector<std::pair<BasicBlock *, BasicBlock::iterator>, 4> Worklist;
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        pred_iterator PI(LocalStartBB), PE(LocalStartBB, false);
224        if (PI == PE)
225          // Return if we've reached the function entry.
226          return false;
227        // Add the predecessors to the worklist.
228        do {
229          BasicBlock *PredBB = *PI;
230          if (Visited.insert(PredBB).second)
231            Worklist.push_back(std::make_pair(PredBB, PredBB->end()));
232        } while (++PI != PE);
233        break;
234      }
235
236      Instruction *Inst = &*--LocalStartPos;
237      if (Depends(Flavor, Inst, Arg, PA)) {
238        DependingInsts.insert(Inst);
239        break;
240      }
241    }
242  } while (!Worklist.empty());
243
244  // Determine whether the original StartBB post-dominates all of the blocks we
245  // visited. If not, insert a sentinal indicating that most optimizations are
246  // not safe.
247  for (const BasicBlock *BB : Visited) {
248    if (BB == StartBB)
249      continue;
250    for (const BasicBlock *Succ : successors(BB))
251      if (Succ != StartBB && !Visited.count(Succ))
252        return false;
253  }
254
255  return true;
256}
257
258llvm::Instruction *llvm::objcarc::findSingleDependency(DependenceKind Flavor,
259                                                       const Value *Arg,
260                                                       BasicBlock *StartBB,
261                                                       Instruction *StartInst,
262                                                       ProvenanceAnalysis &PA) {
263  SmallPtrSet<Instruction *, 4> DependingInsts;
264
265  if (!findDependencies(Flavor, Arg, StartBB, StartInst, DependingInsts, PA) ||
266      DependingInsts.size() != 1)
267    return nullptr;
268  return *DependingInsts.begin();
269}
270