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