lib/Transforms/ObjCARC/PtrState.cpp

   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 #define DEBUG_TYPE "objc-arc-ptr-state"
  11 #include "llvm/Support/Debug.h"
  12 #include "PtrState.h"
  13 #include "ObjCARC.h"
  14
  15 using namespace llvm;
  16 using namespace llvm::objcarc;
  17
  18 raw_ostream &llvm::objcarc::operator<<(raw_ostream &OS, const Sequence S) {
  19   switch (S) {
  20   case S_None:
  21     return OS << "S_None";
  22   case S_Retain:
  23     return OS << "S_Retain";
  24   case S_CanRelease:
  25     return OS << "S_CanRelease";
  26   case S_Use:
  27     return OS << "S_Use";
  28   case S_Release:
  29     return OS << "S_Release";
  30   case S_MovableRelease:
  31     return OS << "S_MovableRelease";
  32   case S_Stop:
  33     return OS << "S_Stop";
  34   }
  35   llvm_unreachable("Unknown sequence type.");
  36 }
  37
  38 static Sequence MergeSeqs(Sequence A, Sequence B, bool TopDown) {
  39   // The easy cases.
  40   if (A == B)
  41     return A;
  42   if (A == S_None || B == S_None)
  43     return S_None;
  44
  45   if (A > B)
  46     std::swap(A, B);
  47   if (TopDown) {
  48     // Choose the side which is further along in the sequence.
  49     if ((A == S_Retain || A == S_CanRelease) &&
  50         (B == S_CanRelease || B == S_Use))
  51       return B;
  52   } else {
  53     // Choose the side which is further along in the sequence.
  54     if ((A == S_Use || A == S_CanRelease) &&
  55         (B == S_Use || B == S_Release || B == S_Stop || B == S_MovableRelease))
  56       return A;
  57     // If both sides are releases, choose the more conservative one.
  58     if (A == S_Stop && (B == S_Release || B == S_MovableRelease))
  59       return A;
  60     if (A == S_Release && B == S_MovableRelease)
  61       return A;
  62   }
  63
  64   return S_None;
  65 }
  66
  67 void RRInfo::clear() {
  68   KnownSafe = false;
  69   IsTailCallRelease = false;
  70   ReleaseMetadata = nullptr;
  71   Calls.clear();
  72   ReverseInsertPts.clear();
  73   CFGHazardAfflicted = false;
  74 }
  75
  76 bool RRInfo::Merge(const RRInfo &Other) {
  77   // Conservatively merge the ReleaseMetadata information.
  78   if (ReleaseMetadata != Other.ReleaseMetadata)
  79     ReleaseMetadata = nullptr;
  80
  81   // Conservatively merge the boolean state.
  82   KnownSafe &= Other.KnownSafe;
  83   IsTailCallRelease &= Other.IsTailCallRelease;
  84   CFGHazardAfflicted |= Other.CFGHazardAfflicted;
  85
  86   // Merge the call sets.
  87   Calls.insert(Other.Calls.begin(), Other.Calls.end());
  88
  89   // Merge the insert point sets. If there are any differences,
  90   // that makes this a partial merge.
  91   bool Partial = ReverseInsertPts.size() != Other.ReverseInsertPts.size();
  92   for (Instruction *Inst : Other.ReverseInsertPts)
  93     Partial |= ReverseInsertPts.insert(Inst).second;
  94   return Partial;
  95 }
  96
  97 void PtrState::SetKnownPositiveRefCount() {
  98   DEBUG(dbgs() << "Setting Known Positive.\n");
  99   KnownPositiveRefCount = true;
 100 }
 101
 102 void PtrState::ClearKnownPositiveRefCount() {
 103   DEBUG(dbgs() << "Clearing Known Positive.\n");
 104   KnownPositiveRefCount = false;
 105 }
 106
 107 void PtrState::SetSeq(Sequence NewSeq) {
 108   DEBUG(dbgs() << "Old: " << Seq << "; New: " << NewSeq << "\n");
 109   Seq = NewSeq;
 110 }
 111
 112 void PtrState::ResetSequenceProgress(Sequence NewSeq) {
 113   DEBUG(dbgs() << "Resetting sequence progress.\n");
 114   SetSeq(NewSeq);
 115   Partial = false;
 116   RRI.clear();
 117 }
 118
 119 void PtrState::Merge(const PtrState &Other, bool TopDown) {
 120   Seq = MergeSeqs(GetSeq(), Other.GetSeq(), TopDown);
 121   KnownPositiveRefCount &= Other.KnownPositiveRefCount;
 122
 123   // If we're not in a sequence (anymore), drop all associated state.
 124   if (Seq == S_None) {
 125     Partial = false;
 126     RRI.clear();
 127   } else if (Partial || Other.Partial) {
 128     // If we're doing a merge on a path that's previously seen a partial
 129     // merge, conservatively drop the sequence, to avoid doing partial
 130     // RR elimination. If the branch predicates for the two merge differ,
 131     // mixing them is unsafe.
 132     ClearSequenceProgress();
 133   } else {
 134     // Otherwise merge the other PtrState's RRInfo into our RRInfo. At this
 135     // point, we know that currently we are not partial. Stash whether or not
 136     // the merge operation caused us to undergo a partial merging of reverse
 137     // insertion points.
 138     Partial = RRI.Merge(Other.RRI);
 139   }
 140 }
 141
 142 bool BottomUpPtrState::InitBottomUp(ARCMDKindCache &Cache, Instruction *I) {
 143   // If we see two releases in a row on the same pointer. If so, make
 144   // a note, and we'll cicle back to revisit it after we've
 145   // hopefully eliminated the second release, which may allow us to
 146   // eliminate the first release too.
 147   // Theoretically we could implement removal of nested retain+release
 148   // pairs by making PtrState hold a stack of states, but this is
 149   // simple and avoids adding overhead for the non-nested case.
 150   bool NestingDetected = false;
 151   if (GetSeq() == S_Release || GetSeq() == S_MovableRelease) {
 152     DEBUG(dbgs() << "Found nested releases (i.e. a release pair)\n");
 153     NestingDetected = true;
 154   }
 155
 156   MDNode *ReleaseMetadata = I->getMetadata(Cache.ImpreciseReleaseMDKind);
 157   Sequence NewSeq = ReleaseMetadata ? S_MovableRelease : S_Release;
 158   ResetSequenceProgress(NewSeq);
 159   SetReleaseMetadata(ReleaseMetadata);
 160   SetKnownSafe(HasKnownPositiveRefCount());
 161   SetTailCallRelease(cast<CallInst>(I)->isTailCall());
 162   InsertCall(I);
 163   SetKnownPositiveRefCount();
 164   return NestingDetected;
 165 }
 166
 167 bool BottomUpPtrState::MatchWithRetain() {
 168   SetKnownPositiveRefCount();
 169
 170   Sequence OldSeq = GetSeq();
 171   switch (OldSeq) {
 172   case S_Stop:
 173   case S_Release:
 174   case S_MovableRelease:
 175   case S_Use:
 176     // If OldSeq is not S_Use or OldSeq is S_Use and we are tracking an
 177     // imprecise release, clear our reverse insertion points.
 178     if (OldSeq != S_Use || IsTrackingImpreciseReleases())
 179       ClearReverseInsertPts();
 180   // FALL THROUGH
 181   case S_CanRelease:
 182     return true;
 183   case S_None:
 184     return false;
 185   case S_Retain:
 186     llvm_unreachable("bottom-up pointer in retain state!");
 187   }
 188 }
 189
 190 bool TopDownPtrState::InitTopDown(ARCInstKind Kind, Instruction *I) {
 191   bool NestingDetected = false;
 192   // Don't do retain+release tracking for ARCInstKind::RetainRV, because
 193   // it's
 194   // better to let it remain as the first instruction after a call.
 195   if (Kind != ARCInstKind::RetainRV) {
 196     // If we see two retains in a row on the same pointer. If so, make
 197     // a note, and we'll cicle back to revisit it after we've
 198     // hopefully eliminated the second retain, which may allow us to
 199     // eliminate the first retain too.
 200     // Theoretically we could implement removal of nested retain+release
 201     // pairs by making PtrState hold a stack of states, but this is
 202     // simple and avoids adding overhead for the non-nested case.
 203     if (GetSeq() == S_Retain)
 204       NestingDetected = true;
 205
 206     ResetSequenceProgress(S_Retain);
 207     SetKnownSafe(HasKnownPositiveRefCount());
 208     InsertCall(I);
 209   }
 210
 211   SetKnownPositiveRefCount();
 212   return NestingDetected;
 213 }
 214
 215 bool TopDownPtrState::MatchWithRelease(ARCMDKindCache &Cache,
 216                                        Instruction *Release) {
 217   ClearKnownPositiveRefCount();
 218
 219   Sequence OldSeq = GetSeq();
 220
 221   MDNode *ReleaseMetadata = Release->getMetadata(Cache.ImpreciseReleaseMDKind);
 222
 223   switch (OldSeq) {
 224   case S_Retain:
 225   case S_CanRelease:
 226     if (OldSeq == S_Retain || ReleaseMetadata != nullptr)
 227       ClearReverseInsertPts();
 228   // FALL THROUGH
 229   case S_Use:
 230     SetReleaseMetadata(ReleaseMetadata);
 231     SetTailCallRelease(cast<CallInst>(Release)->isTailCall());
 232     return true;
 233   case S_None:
 234     return false;
 235   case S_Stop:
 236   case S_Release:
 237   case S_MovableRelease:
 238     llvm_unreachable("top-down pointer in bottom up state!");
 239   }
 240 }