1 //===- PtrState.cpp -------------------------------------------------------===//
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 
9 #include "PtrState.h"
10 #include "DependencyAnalysis.h"
11 #include "ObjCARC.h"
12 #include "llvm/Analysis/ObjCARCAnalysisUtils.h"
13 #include "llvm/Analysis/ObjCARCInstKind.h"
14 #include "llvm/Analysis/ObjCARCUtil.h"
15 #include "llvm/IR/BasicBlock.h"
16 #include "llvm/IR/Instruction.h"
17 #include "llvm/IR/Instructions.h"
18 #include "llvm/IR/Value.h"
19 #include "llvm/Support/Casting.h"
20 #include "llvm/Support/Compiler.h"
21 #include "llvm/Support/Debug.h"
22 #include "llvm/Support/ErrorHandling.h"
23 #include "llvm/Support/raw_ostream.h"
24 #include <cassert>
25 #include <iterator>
26 #include <utility>
27 
28 using namespace llvm;
29 using namespace llvm::objcarc;
30 
31 #define DEBUG_TYPE "objc-arc-ptr-state"
32 
33 //===----------------------------------------------------------------------===//
34 //                                  Utility
35 //===----------------------------------------------------------------------===//
36 
37 raw_ostream &llvm::objcarc::operator<<(raw_ostream &OS, const Sequence S) {
38   switch (S) {
39   case S_None:
40     return OS << "S_None";
41   case S_Retain:
42     return OS << "S_Retain";
43   case S_CanRelease:
44     return OS << "S_CanRelease";
45   case S_Use:
46     return OS << "S_Use";
47   case S_Release:
48     return OS << "S_Release";
49   case S_MovableRelease:
50     return OS << "S_MovableRelease";
51   case S_Stop:
52     return OS << "S_Stop";
53   }
54   llvm_unreachable("Unknown sequence type.");
55 }
56 
57 //===----------------------------------------------------------------------===//
58 //                                  Sequence
59 //===----------------------------------------------------------------------===//
60 
61 static Sequence MergeSeqs(Sequence A, Sequence B, bool TopDown) {
62   // The easy cases.
63   if (A == B)
64     return A;
65   if (A == S_None || B == S_None)
66     return S_None;
67 
68   if (A > B)
69     std::swap(A, B);
70   if (TopDown) {
71     // Choose the side which is further along in the sequence.
72     if ((A == S_Retain || A == S_CanRelease) &&
73         (B == S_CanRelease || B == S_Use))
74       return B;
75   } else {
76     // Choose the side which is further along in the sequence.
77     if ((A == S_Use || A == S_CanRelease) &&
78         (B == S_Use || B == S_Release || B == S_Stop || B == S_MovableRelease))
79       return A;
80     // If both sides are releases, choose the more conservative one.
81     if (A == S_Stop && (B == S_Release || B == S_MovableRelease))
82       return A;
83     if (A == S_Release && B == S_MovableRelease)
84       return A;
85   }
86 
87   return S_None;
88 }
89 
90 //===----------------------------------------------------------------------===//
91 //                                   RRInfo
92 //===----------------------------------------------------------------------===//
93 
94 void RRInfo::clear() {
95   KnownSafe = false;
96   IsTailCallRelease = false;
97   ReleaseMetadata = nullptr;
98   Calls.clear();
99   ReverseInsertPts.clear();
100   CFGHazardAfflicted = false;
101 }
102 
103 bool RRInfo::Merge(const RRInfo &Other) {
104   // Conservatively merge the ReleaseMetadata information.
105   if (ReleaseMetadata != Other.ReleaseMetadata)
106     ReleaseMetadata = nullptr;
107 
108   // Conservatively merge the boolean state.
109   KnownSafe &= Other.KnownSafe;
110   IsTailCallRelease &= Other.IsTailCallRelease;
111   CFGHazardAfflicted |= Other.CFGHazardAfflicted;
112 
113   // Merge the call sets.
114   Calls.insert(Other.Calls.begin(), Other.Calls.end());
115 
116   // Merge the insert point sets. If there are any differences,
117   // that makes this a partial merge.
118   bool Partial = ReverseInsertPts.size() != Other.ReverseInsertPts.size();
119   for (Instruction *Inst : Other.ReverseInsertPts)
120     Partial |= ReverseInsertPts.insert(Inst).second;
121   return Partial;
122 }
123 
124 //===----------------------------------------------------------------------===//
125 //                                  PtrState
126 //===----------------------------------------------------------------------===//
127 
128 void PtrState::SetKnownPositiveRefCount() {
129   LLVM_DEBUG(dbgs() << "        Setting Known Positive.\n");
130   KnownPositiveRefCount = true;
131 }
132 
133 void PtrState::ClearKnownPositiveRefCount() {
134   LLVM_DEBUG(dbgs() << "        Clearing Known Positive.\n");
135   KnownPositiveRefCount = false;
136 }
137 
138 void PtrState::SetSeq(Sequence NewSeq) {
139   LLVM_DEBUG(dbgs() << "            Old: " << GetSeq() << "; New: " << NewSeq
140                     << "\n");
141   Seq = NewSeq;
142 }
143 
144 void PtrState::ResetSequenceProgress(Sequence NewSeq) {
145   LLVM_DEBUG(dbgs() << "        Resetting sequence progress.\n");
146   SetSeq(NewSeq);
147   Partial = false;
148   RRI.clear();
149 }
150 
151 void PtrState::Merge(const PtrState &Other, bool TopDown) {
152   Seq = MergeSeqs(GetSeq(), Other.GetSeq(), TopDown);
153   KnownPositiveRefCount &= Other.KnownPositiveRefCount;
154 
155   // If we're not in a sequence (anymore), drop all associated state.
156   if (Seq == S_None) {
157     Partial = false;
158     RRI.clear();
159   } else if (Partial || Other.Partial) {
160     // If we're doing a merge on a path that's previously seen a partial
161     // merge, conservatively drop the sequence, to avoid doing partial
162     // RR elimination. If the branch predicates for the two merge differ,
163     // mixing them is unsafe.
164     ClearSequenceProgress();
165   } else {
166     // Otherwise merge the other PtrState's RRInfo into our RRInfo. At this
167     // point, we know that currently we are not partial. Stash whether or not
168     // the merge operation caused us to undergo a partial merging of reverse
169     // insertion points.
170     Partial = RRI.Merge(Other.RRI);
171   }
172 }
173 
174 //===----------------------------------------------------------------------===//
175 //                              BottomUpPtrState
176 //===----------------------------------------------------------------------===//
177 
178 bool BottomUpPtrState::InitBottomUp(ARCMDKindCache &Cache, Instruction *I) {
179   // If we see two releases in a row on the same pointer. If so, make
180   // a note, and we'll cicle back to revisit it after we've
181   // hopefully eliminated the second release, which may allow us to
182   // eliminate the first release too.
183   // Theoretically we could implement removal of nested retain+release
184   // pairs by making PtrState hold a stack of states, but this is
185   // simple and avoids adding overhead for the non-nested case.
186   bool NestingDetected = false;
187   if (GetSeq() == S_Release || GetSeq() == S_MovableRelease) {
188     LLVM_DEBUG(
189         dbgs() << "        Found nested releases (i.e. a release pair)\n");
190     NestingDetected = true;
191   }
192 
193   MDNode *ReleaseMetadata =
194       I->getMetadata(Cache.get(ARCMDKindID::ImpreciseRelease));
195   Sequence NewSeq = ReleaseMetadata ? S_MovableRelease : S_Release;
196   ResetSequenceProgress(NewSeq);
197   SetReleaseMetadata(ReleaseMetadata);
198   SetKnownSafe(HasKnownPositiveRefCount());
199   SetTailCallRelease(cast<CallInst>(I)->isTailCall());
200   InsertCall(I);
201   SetKnownPositiveRefCount();
202   return NestingDetected;
203 }
204 
205 bool BottomUpPtrState::MatchWithRetain() {
206   SetKnownPositiveRefCount();
207 
208   Sequence OldSeq = GetSeq();
209   switch (OldSeq) {
210   case S_Stop:
211   case S_Release:
212   case S_MovableRelease:
213   case S_Use:
214     // If OldSeq is not S_Use or OldSeq is S_Use and we are tracking an
215     // imprecise release, clear our reverse insertion points.
216     if (OldSeq != S_Use || IsTrackingImpreciseReleases())
217       ClearReverseInsertPts();
218     LLVM_FALLTHROUGH;
219   case S_CanRelease:
220     return true;
221   case S_None:
222     return false;
223   case S_Retain:
224     llvm_unreachable("bottom-up pointer in retain state!");
225   }
226   llvm_unreachable("Sequence unknown enum value");
227 }
228 
229 bool BottomUpPtrState::HandlePotentialAlterRefCount(Instruction *Inst,
230                                                     const Value *Ptr,
231                                                     ProvenanceAnalysis &PA,
232                                                     ARCInstKind Class) {
233   Sequence S = GetSeq();
234 
235   // Check for possible releases.
236   if (!CanDecrementRefCount(Inst, Ptr, PA, Class))
237     return false;
238 
239   LLVM_DEBUG(dbgs() << "            CanAlterRefCount: Seq: " << S << "; "
240                     << *Ptr << "\n");
241   switch (S) {
242   case S_Use:
243     SetSeq(S_CanRelease);
244     return true;
245   case S_CanRelease:
246   case S_Release:
247   case S_MovableRelease:
248   case S_Stop:
249   case S_None:
250     return false;
251   case S_Retain:
252     llvm_unreachable("bottom-up pointer in retain state!");
253   }
254   llvm_unreachable("Sequence unknown enum value");
255 }
256 
257 void BottomUpPtrState::HandlePotentialUse(BasicBlock *BB, Instruction *Inst,
258                                           const Value *Ptr,
259                                           ProvenanceAnalysis &PA,
260                                           ARCInstKind Class) {
261   auto SetSeqAndInsertReverseInsertPt = [&](Sequence NewSeq){
262     assert(!HasReverseInsertPts());
263     SetSeq(NewSeq);
264     // If this is an invoke instruction, we're scanning it as part of
265     // one of its successor blocks, since we can't insert code after it
266     // in its own block, and we don't want to split critical edges.
267     BasicBlock::iterator InsertAfter;
268     if (isa<InvokeInst>(Inst)) {
269       const auto IP = BB->getFirstInsertionPt();
270       InsertAfter = IP == BB->end() ? std::prev(BB->end()) : IP;
271       if (isa<CatchSwitchInst>(InsertAfter))
272         // A catchswitch must be the only non-phi instruction in its basic
273         // block, so attempting to insert an instruction into such a block would
274         // produce invalid IR.
275         SetCFGHazardAfflicted(true);
276     } else {
277       InsertAfter = std::next(Inst->getIterator());
278     }
279 
280     if (InsertAfter != BB->end())
281       InsertAfter = skipDebugIntrinsics(InsertAfter);
282 
283     InsertReverseInsertPt(&*InsertAfter);
284 
285     // Don't insert anything between a call/invoke with operand bundle
286     // "clang.arc.rv" and the retainRV/claimRV call that uses the call result.
287     if (auto *CB = dyn_cast<CallBase>(Inst))
288       if (objcarc::hasRVOpBundle(CB))
289         SetCFGHazardAfflicted(true);
290   };
291 
292   // Check for possible direct uses.
293   switch (GetSeq()) {
294   case S_Release:
295   case S_MovableRelease:
296     if (CanUse(Inst, Ptr, PA, Class)) {
297       LLVM_DEBUG(dbgs() << "            CanUse: Seq: " << GetSeq() << "; "
298                         << *Ptr << "\n");
299       SetSeqAndInsertReverseInsertPt(S_Use);
300     } else if (Seq == S_Release && IsUser(Class)) {
301       LLVM_DEBUG(dbgs() << "            PreciseReleaseUse: Seq: " << GetSeq()
302                         << "; " << *Ptr << "\n");
303       // Non-movable releases depend on any possible objc pointer use.
304       SetSeqAndInsertReverseInsertPt(S_Stop);
305     } else if (const auto *Call = getreturnRVOperand(*Inst, Class)) {
306       if (CanUse(Call, Ptr, PA, GetBasicARCInstKind(Call))) {
307         LLVM_DEBUG(dbgs() << "            ReleaseUse: Seq: " << GetSeq() << "; "
308                           << *Ptr << "\n");
309         SetSeqAndInsertReverseInsertPt(S_Stop);
310       }
311     }
312     break;
313   case S_Stop:
314     if (CanUse(Inst, Ptr, PA, Class)) {
315       LLVM_DEBUG(dbgs() << "            PreciseStopUse: Seq: " << GetSeq()
316                         << "; " << *Ptr << "\n");
317       SetSeq(S_Use);
318     }
319     break;
320   case S_CanRelease:
321   case S_Use:
322   case S_None:
323     break;
324   case S_Retain:
325     llvm_unreachable("bottom-up pointer in retain state!");
326   }
327 }
328 
329 //===----------------------------------------------------------------------===//
330 //                              TopDownPtrState
331 //===----------------------------------------------------------------------===//
332 
333 bool TopDownPtrState::InitTopDown(ARCInstKind Kind, Instruction *I) {
334   bool NestingDetected = false;
335   // Don't do retain+release tracking for ARCInstKind::RetainRV, because
336   // it's
337   // better to let it remain as the first instruction after a call.
338   if (Kind != ARCInstKind::RetainRV) {
339     // If we see two retains in a row on the same pointer. If so, make
340     // a note, and we'll cicle back to revisit it after we've
341     // hopefully eliminated the second retain, which may allow us to
342     // eliminate the first retain too.
343     // Theoretically we could implement removal of nested retain+release
344     // pairs by making PtrState hold a stack of states, but this is
345     // simple and avoids adding overhead for the non-nested case.
346     if (GetSeq() == S_Retain)
347       NestingDetected = true;
348 
349     ResetSequenceProgress(S_Retain);
350     SetKnownSafe(HasKnownPositiveRefCount());
351     InsertCall(I);
352   }
353 
354   SetKnownPositiveRefCount();
355   return NestingDetected;
356 }
357 
358 bool TopDownPtrState::MatchWithRelease(ARCMDKindCache &Cache,
359                                        Instruction *Release) {
360   ClearKnownPositiveRefCount();
361 
362   Sequence OldSeq = GetSeq();
363 
364   MDNode *ReleaseMetadata =
365       Release->getMetadata(Cache.get(ARCMDKindID::ImpreciseRelease));
366 
367   switch (OldSeq) {
368   case S_Retain:
369   case S_CanRelease:
370     if (OldSeq == S_Retain || ReleaseMetadata != nullptr)
371       ClearReverseInsertPts();
372     LLVM_FALLTHROUGH;
373   case S_Use:
374     SetReleaseMetadata(ReleaseMetadata);
375     SetTailCallRelease(cast<CallInst>(Release)->isTailCall());
376     return true;
377   case S_None:
378     return false;
379   case S_Stop:
380   case S_Release:
381   case S_MovableRelease:
382     llvm_unreachable("top-down pointer in bottom up state!");
383   }
384   llvm_unreachable("Sequence unknown enum value");
385 }
386 
387 bool TopDownPtrState::HandlePotentialAlterRefCount(
388     Instruction *Inst, const Value *Ptr, ProvenanceAnalysis &PA,
389     ARCInstKind Class, const BundledRetainClaimRVs &BundledRVs) {
390   // Check for possible releases. Treat clang.arc.use as a releasing instruction
391   // to prevent sinking a retain past it.
392   if (!CanDecrementRefCount(Inst, Ptr, PA, Class) &&
393       Class != ARCInstKind::IntrinsicUser)
394     return false;
395 
396   LLVM_DEBUG(dbgs() << "            CanAlterRefCount: Seq: " << GetSeq() << "; "
397                     << *Ptr << "\n");
398   ClearKnownPositiveRefCount();
399   switch (GetSeq()) {
400   case S_Retain:
401     SetSeq(S_CanRelease);
402     assert(!HasReverseInsertPts());
403     InsertReverseInsertPt(Inst);
404 
405     // Don't insert anything between a call/invoke with operand bundle
406     // "clang.arc.rv" and the retainRV/claimRV call that uses the call result.
407     if (BundledRVs.contains(Inst))
408       SetCFGHazardAfflicted(true);
409 
410     // One call can't cause a transition from S_Retain to S_CanRelease
411     // and S_CanRelease to S_Use. If we've made the first transition,
412     // we're done.
413     return true;
414   case S_Use:
415   case S_CanRelease:
416   case S_None:
417     return false;
418   case S_Stop:
419   case S_Release:
420   case S_MovableRelease:
421     llvm_unreachable("top-down pointer in release state!");
422   }
423   llvm_unreachable("covered switch is not covered!?");
424 }
425 
426 void TopDownPtrState::HandlePotentialUse(Instruction *Inst, const Value *Ptr,
427                                          ProvenanceAnalysis &PA,
428                                          ARCInstKind Class) {
429   // Check for possible direct uses.
430   switch (GetSeq()) {
431   case S_CanRelease:
432     if (!CanUse(Inst, Ptr, PA, Class))
433       return;
434     LLVM_DEBUG(dbgs() << "             CanUse: Seq: " << GetSeq() << "; "
435                       << *Ptr << "\n");
436     SetSeq(S_Use);
437     return;
438   case S_Retain:
439   case S_Use:
440   case S_None:
441     return;
442   case S_Stop:
443   case S_Release:
444   case S_MovableRelease:
445     llvm_unreachable("top-down pointer in release state!");
446   }
447 }
448