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
27using namespace llvm;
28using 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.
34bool llvm::objcarc::CanAlterRefCount(const Instruction *Inst, const Value *Ptr,
35                                     ProvenanceAnalysis &PA,
36                                     ARCInstKind Class) {
37  switch (Class) {
38  case ARCInstKind::Autorelease:
39  case ARCInstKind::AutoreleaseRV:
40  case ARCInstKind::IntrinsicUser:
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.
50  FunctionModRefBehavior MRB = PA.getAA()->getModRefBehavior(Call);
51  if (AliasAnalysis::onlyReadsMemory(MRB))
52    return false;
53  if (AliasAnalysis::onlyAccessesArgPointees(MRB)) {
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
67bool llvm::objcarc::CanDecrementRefCount(const Instruction *Inst,
68                                         const Value *Ptr,
69                                         ProvenanceAnalysis &PA,
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.
81bool 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 (auto CS = ImmutableCallSite(Inst)) {
99    // For calls, just check the arguments (and not the callee operand).
100    for (ImmutableCallSite::arg_iterator OI = CS.arg_begin(),
101         OE = CS.arg_end(); OI != OE; ++OI) {
102      const Value *Op = *OI;
103      if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) &&
104          PA.related(Ptr, Op, DL))
105        return true;
106    }
107    return false;
108  } else if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
109    // Special-case stores, because we don't care about the stored value, just
110    // the store address.
111    const Value *Op = GetUnderlyingObjCPtr(SI->getPointerOperand(), DL);
112    // If we can't tell what the underlying object was, assume there is a
113    // dependence.
114    return IsPotentialRetainableObjPtr(Op, *PA.getAA()) &&
115           PA.related(Op, Ptr, DL);
116  }
117
118  // Check each operand for a match.
119  for (User::const_op_iterator OI = Inst->op_begin(), OE = Inst->op_end();
120       OI != OE; ++OI) {
121    const Value *Op = *OI;
122    if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op, DL))
123      return true;
124  }
125  return false;
126}
127
128/// Test if there can be dependencies on Inst through Arg. This function only
129/// tests dependencies relevant for removing pairs of calls.
130bool
131llvm::objcarc::Depends(DependenceKind Flavor, Instruction *Inst,
132                       const Value *Arg, ProvenanceAnalysis &PA) {
133  // If we've reached the definition of Arg, stop.
134  if (Inst == Arg)
135    return true;
136
137  switch (Flavor) {
138  case NeedsPositiveRetainCount: {
139    ARCInstKind Class = GetARCInstKind(Inst);
140    switch (Class) {
141    case ARCInstKind::AutoreleasepoolPop:
142    case ARCInstKind::AutoreleasepoolPush:
143    case ARCInstKind::None:
144      return false;
145    default:
146      return CanUse(Inst, Arg, PA, Class);
147    }
148  }
149
150  case AutoreleasePoolBoundary: {
151    ARCInstKind Class = GetARCInstKind(Inst);
152    switch (Class) {
153    case ARCInstKind::AutoreleasepoolPop:
154    case ARCInstKind::AutoreleasepoolPush:
155      // These mark the end and begin of an autorelease pool scope.
156      return true;
157    default:
158      // Nothing else does this.
159      return false;
160    }
161  }
162
163  case CanChangeRetainCount: {
164    ARCInstKind Class = GetARCInstKind(Inst);
165    switch (Class) {
166    case ARCInstKind::AutoreleasepoolPop:
167      // Conservatively assume this can decrement any count.
168      return true;
169    case ARCInstKind::AutoreleasepoolPush:
170    case ARCInstKind::None:
171      return false;
172    default:
173      return CanAlterRefCount(Inst, Arg, PA, Class);
174    }
175  }
176
177  case RetainAutoreleaseDep:
178    switch (GetBasicARCInstKind(Inst)) {
179    case ARCInstKind::AutoreleasepoolPop:
180    case ARCInstKind::AutoreleasepoolPush:
181      // Don't merge an objc_autorelease with an objc_retain inside a different
182      // autoreleasepool scope.
183      return true;
184    case ARCInstKind::Retain:
185    case ARCInstKind::RetainRV:
186      // Check for a retain of the same pointer for merging.
187      return GetArgRCIdentityRoot(Inst) == Arg;
188    default:
189      // Nothing else matters for objc_retainAutorelease formation.
190      return false;
191    }
192
193  case RetainAutoreleaseRVDep: {
194    ARCInstKind Class = GetBasicARCInstKind(Inst);
195    switch (Class) {
196    case ARCInstKind::Retain:
197    case ARCInstKind::RetainRV:
198      // Check for a retain of the same pointer for merging.
199      return GetArgRCIdentityRoot(Inst) == Arg;
200    default:
201      // Anything that can autorelease interrupts
202      // retainAutoreleaseReturnValue formation.
203      return CanInterruptRV(Class);
204    }
205  }
206
207  case RetainRVDep:
208    return CanInterruptRV(GetBasicARCInstKind(Inst));
209  }
210
211  llvm_unreachable("Invalid dependence flavor");
212}
213
214/// Walk up the CFG from StartPos (which is in StartBB) and find local and
215/// non-local dependencies on Arg.
216///
217/// TODO: Cache results?
218void
219llvm::objcarc::FindDependencies(DependenceKind Flavor,
220                                const Value *Arg,
221                                BasicBlock *StartBB, Instruction *StartInst,
222                                SmallPtrSetImpl<Instruction *> &DependingInsts,
223                                SmallPtrSetImpl<const BasicBlock *> &Visited,
224                                ProvenanceAnalysis &PA) {
225  BasicBlock::iterator StartPos = StartInst->getIterator();
226
227  SmallVector<std::pair<BasicBlock *, BasicBlock::iterator>, 4> Worklist;
228  Worklist.push_back(std::make_pair(StartBB, StartPos));
229  do {
230    std::pair<BasicBlock *, BasicBlock::iterator> Pair =
231      Worklist.pop_back_val();
232    BasicBlock *LocalStartBB = Pair.first;
233    BasicBlock::iterator LocalStartPos = Pair.second;
234    BasicBlock::iterator StartBBBegin = LocalStartBB->begin();
235    for (;;) {
236      if (LocalStartPos == StartBBBegin) {
237        pred_iterator PI(LocalStartBB), PE(LocalStartBB, false);
238        if (PI == PE)
239          // If we've reached the function entry, produce a null dependence.
240          DependingInsts.insert(nullptr);
241        else
242          // Add the predecessors to the worklist.
243          do {
244            BasicBlock *PredBB = *PI;
245            if (Visited.insert(PredBB).second)
246              Worklist.push_back(std::make_pair(PredBB, PredBB->end()));
247          } while (++PI != PE);
248        break;
249      }
250
251      Instruction *Inst = &*--LocalStartPos;
252      if (Depends(Flavor, Inst, Arg, PA)) {
253        DependingInsts.insert(Inst);
254        break;
255      }
256    }
257  } while (!Worklist.empty());
258
259  // Determine whether the original StartBB post-dominates all of the blocks we
260  // visited. If not, insert a sentinal indicating that most optimizations are
261  // not safe.
262  for (const BasicBlock *BB : Visited) {
263    if (BB == StartBB)
264      continue;
265    for (const BasicBlock *Succ : successors(BB))
266      if (Succ != StartBB && !Visited.count(Succ)) {
267        DependingInsts.insert(reinterpret_cast<Instruction *>(-1));
268        return;
269      }
270  }
271}
272