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   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 
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 (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.
121 bool
122 llvm::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?
206 static 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 
258 llvm::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