1 //===- PtrState.cpp -------------------------------------------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "PtrState.h"
11 #include "DependencyAnalysis.h"
12 #include "ObjCARC.h"
13 #include "llvm/Analysis/ObjCARCAnalysisUtils.h"
14 #include "llvm/Analysis/ObjCARCInstKind.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 (!CanAlterRefCount(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     InsertReverseInsertPt(&*InsertAfter);
280   };
281 
282   // Check for possible direct uses.
283   switch (GetSeq()) {
284   case S_Release:
285   case S_MovableRelease:
286     if (CanUse(Inst, Ptr, PA, Class)) {
287       LLVM_DEBUG(dbgs() << "            CanUse: Seq: " << GetSeq() << "; "
288                         << *Ptr << "\n");
289       SetSeqAndInsertReverseInsertPt(S_Use);
290     } else if (Seq == S_Release && IsUser(Class)) {
291       LLVM_DEBUG(dbgs() << "            PreciseReleaseUse: Seq: " << GetSeq()
292                         << "; " << *Ptr << "\n");
293       // Non-movable releases depend on any possible objc pointer use.
294       SetSeqAndInsertReverseInsertPt(S_Stop);
295     } else if (const auto *Call = getreturnRVOperand(*Inst, Class)) {
296       if (CanUse(Call, Ptr, PA, GetBasicARCInstKind(Call))) {
297         LLVM_DEBUG(dbgs() << "            ReleaseUse: Seq: " << GetSeq() << "; "
298                           << *Ptr << "\n");
299         SetSeqAndInsertReverseInsertPt(S_Stop);
300       }
301     }
302     break;
303   case S_Stop:
304     if (CanUse(Inst, Ptr, PA, Class)) {
305       LLVM_DEBUG(dbgs() << "            PreciseStopUse: Seq: " << GetSeq()
306                         << "; " << *Ptr << "\n");
307       SetSeq(S_Use);
308     }
309     break;
310   case S_CanRelease:
311   case S_Use:
312   case S_None:
313     break;
314   case S_Retain:
315     llvm_unreachable("bottom-up pointer in retain state!");
316   }
317 }
318 
319 //===----------------------------------------------------------------------===//
320 //                              TopDownPtrState
321 //===----------------------------------------------------------------------===//
322 
323 bool TopDownPtrState::InitTopDown(ARCInstKind Kind, Instruction *I) {
324   bool NestingDetected = false;
325   // Don't do retain+release tracking for ARCInstKind::RetainRV, because
326   // it's
327   // better to let it remain as the first instruction after a call.
328   if (Kind != ARCInstKind::RetainRV) {
329     // If we see two retains in a row on the same pointer. If so, make
330     // a note, and we'll cicle back to revisit it after we've
331     // hopefully eliminated the second retain, which may allow us to
332     // eliminate the first retain too.
333     // Theoretically we could implement removal of nested retain+release
334     // pairs by making PtrState hold a stack of states, but this is
335     // simple and avoids adding overhead for the non-nested case.
336     if (GetSeq() == S_Retain)
337       NestingDetected = true;
338 
339     ResetSequenceProgress(S_Retain);
340     SetKnownSafe(HasKnownPositiveRefCount());
341     InsertCall(I);
342   }
343 
344   SetKnownPositiveRefCount();
345   return NestingDetected;
346 }
347 
348 bool TopDownPtrState::MatchWithRelease(ARCMDKindCache &Cache,
349                                        Instruction *Release) {
350   ClearKnownPositiveRefCount();
351 
352   Sequence OldSeq = GetSeq();
353 
354   MDNode *ReleaseMetadata =
355       Release->getMetadata(Cache.get(ARCMDKindID::ImpreciseRelease));
356 
357   switch (OldSeq) {
358   case S_Retain:
359   case S_CanRelease:
360     if (OldSeq == S_Retain || ReleaseMetadata != nullptr)
361       ClearReverseInsertPts();
362     LLVM_FALLTHROUGH;
363   case S_Use:
364     SetReleaseMetadata(ReleaseMetadata);
365     SetTailCallRelease(cast<CallInst>(Release)->isTailCall());
366     return true;
367   case S_None:
368     return false;
369   case S_Stop:
370   case S_Release:
371   case S_MovableRelease:
372     llvm_unreachable("top-down pointer in bottom up state!");
373   }
374   llvm_unreachable("Sequence unknown enum value");
375 }
376 
377 bool TopDownPtrState::HandlePotentialAlterRefCount(Instruction *Inst,
378                                                    const Value *Ptr,
379                                                    ProvenanceAnalysis &PA,
380                                                    ARCInstKind Class) {
381   // Check for possible releases. Treat clang.arc.use as a releasing instruction
382   // to prevent sinking a retain past it.
383   if (!CanAlterRefCount(Inst, Ptr, PA, Class) &&
384       Class != ARCInstKind::IntrinsicUser)
385     return false;
386 
387   LLVM_DEBUG(dbgs() << "            CanAlterRefCount: Seq: " << GetSeq() << "; "
388                     << *Ptr << "\n");
389   ClearKnownPositiveRefCount();
390   switch (GetSeq()) {
391   case S_Retain:
392     SetSeq(S_CanRelease);
393     assert(!HasReverseInsertPts());
394     InsertReverseInsertPt(Inst);
395 
396     // One call can't cause a transition from S_Retain to S_CanRelease
397     // and S_CanRelease to S_Use. If we've made the first transition,
398     // we're done.
399     return true;
400   case S_Use:
401   case S_CanRelease:
402   case S_None:
403     return false;
404   case S_Stop:
405   case S_Release:
406   case S_MovableRelease:
407     llvm_unreachable("top-down pointer in release state!");
408   }
409   llvm_unreachable("covered switch is not covered!?");
410 }
411 
412 void TopDownPtrState::HandlePotentialUse(Instruction *Inst, const Value *Ptr,
413                                          ProvenanceAnalysis &PA,
414                                          ARCInstKind Class) {
415   // Check for possible direct uses.
416   switch (GetSeq()) {
417   case S_CanRelease:
418     if (!CanUse(Inst, Ptr, PA, Class))
419       return;
420     LLVM_DEBUG(dbgs() << "             CanUse: Seq: " << GetSeq() << "; "
421                       << *Ptr << "\n");
422     SetSeq(S_Use);
423     return;
424   case S_Retain:
425   case S_Use:
426   case S_None:
427     return;
428   case S_Stop:
429   case S_Release:
430   case S_MovableRelease:
431     llvm_unreachable("top-down pointer in release state!");
432   }
433 }
434