xref: /freebsd/contrib/llvm-project/llvm/lib/Transforms/ObjCARC/DependencyAnalysis.cpp (revision c66ec88fed842fbaad62c30d510644ceb7bd2d71)
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,
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 
67 bool 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.
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
130 llvm::objcarc::Depends(DependenceKind Flavor, Instruction *Inst,
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) {
137   case NeedsPositiveRetainCount: {
138     ARCInstKind Class = GetARCInstKind(Inst);
139     switch (Class) {
140     case ARCInstKind::AutoreleasepoolPop:
141     case ARCInstKind::AutoreleasepoolPush:
142     case ARCInstKind::None:
143       return false;
144     default:
145       return CanUse(Inst, Arg, PA, Class);
146     }
147   }
148 
149   case AutoreleasePoolBoundary: {
150     ARCInstKind Class = GetARCInstKind(Inst);
151     switch (Class) {
152     case ARCInstKind::AutoreleasepoolPop:
153     case ARCInstKind::AutoreleasepoolPush:
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) {
165     case ARCInstKind::AutoreleasepoolPop:
166       // Conservatively assume this can decrement any count.
167       return true;
168     case ARCInstKind::AutoreleasepoolPush:
169     case ARCInstKind::None:
170       return false;
171     default:
172       return CanAlterRefCount(Inst, Arg, PA, Class);
173     }
174   }
175 
176   case RetainAutoreleaseDep:
177     switch (GetBasicARCInstKind(Inst)) {
178     case ARCInstKind::AutoreleasepoolPop:
179     case ARCInstKind::AutoreleasepoolPush:
180       // Don't merge an objc_autorelease with an objc_retain inside a different
181       // autoreleasepool scope.
182       return true;
183     case ARCInstKind::Retain:
184     case ARCInstKind::RetainRV:
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:
196     case ARCInstKind::RetainRV:
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
218 llvm::objcarc::FindDependencies(DependenceKind Flavor,
219                                 const Value *Arg,
220                                 BasicBlock *StartBB, Instruction *StartInst,
221                                 SmallPtrSetImpl<Instruction *> &DependingInsts,
222                                 SmallPtrSetImpl<const BasicBlock *> &Visited,
223                                 ProvenanceAnalysis &PA) {
224   BasicBlock::iterator StartPos = StartInst->getIterator();
225 
226   SmallVector<std::pair<BasicBlock *, BasicBlock::iterator>, 4> Worklist;
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 }
271