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