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
16using namespace llvm;
17using namespace llvm::objcarc;
18
19#define DEBUG_TYPE "objc-arc-ptr-state"
20
21//===----------------------------------------------------------------------===//
22//                                  Utility
23//===----------------------------------------------------------------------===//
24
25raw_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
49static 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
82void RRInfo::clear() {
83  KnownSafe = false;
84  IsTailCallRelease = false;
85  ReleaseMetadata = nullptr;
86  Calls.clear();
87  ReverseInsertPts.clear();
88  CFGHazardAfflicted = false;
89}
90
91bool 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
116void PtrState::SetKnownPositiveRefCount() {
117  DEBUG(dbgs() << "        Setting Known Positive.\n");
118  KnownPositiveRefCount = true;
119}
120
121void PtrState::ClearKnownPositiveRefCount() {
122  DEBUG(dbgs() << "        Clearing Known Positive.\n");
123  KnownPositiveRefCount = false;
124}
125
126void PtrState::SetSeq(Sequence NewSeq) {
127  DEBUG(dbgs() << "            Old: " << GetSeq() << "; New: " << NewSeq << "\n");
128  Seq = NewSeq;
129}
130
131void PtrState::ResetSequenceProgress(Sequence NewSeq) {
132  DEBUG(dbgs() << "        Resetting sequence progress.\n");
133  SetSeq(NewSeq);
134  Partial = false;
135  RRI.clear();
136}
137
138void 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
165bool 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
191bool 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
215bool 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
243void 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
296bool 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
321bool 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
350bool 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
383void 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