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