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: " << Seq << "; 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 Seq = GetSeq();
 218
 219   // Check for possible releases.
 220   if (!CanAlterRefCount(Inst, Ptr, PA, Class))
 221     return false;
 222
 223   DEBUG(dbgs() << "CanAlterRefCount: Seq: " << Seq << "; " << *Ptr << "\n");
 224   switch (Seq) {
 225   case S_Use:
 226     SetSeq(S_CanRelease);
 227     return true;
 228   case S_CanRelease:
 229   case S_Release:
 230   case S_MovableRelease:
 231   case S_Stop:
 232   case S_None:
 233     return false;
 234   case S_Retain:
 235     llvm_unreachable("bottom-up pointer in retain state!");
 236   }
 237   llvm_unreachable("Sequence unknown enum value");
 238 }
 239
 240 void BottomUpPtrState::HandlePotentialUse(BasicBlock *BB, Instruction *Inst,
 241                                           const Value *Ptr,
 242                                           ProvenanceAnalysis &PA,
 243                                           ARCInstKind Class) {
 244   // Check for possible direct uses.
 245   switch (GetSeq()) {
 246   case S_Release:
 247   case S_MovableRelease:
 248     if (CanUse(Inst, Ptr, PA, Class)) {
 249       DEBUG(dbgs() << "CanUse: Seq: " << Seq << "; " << *Ptr << "\n");
 250       assert(!HasReverseInsertPts());
 251       // If this is an invoke instruction, we're scanning it as part of
 252       // one of its successor blocks, since we can't insert code after it
 253       // in its own block, and we don't want to split critical edges.
 254       if (isa<InvokeInst>(Inst))
 255         InsertReverseInsertPt(BB->getFirstInsertionPt());
 256       else
 257         InsertReverseInsertPt(std::next(BasicBlock::iterator(Inst)));
 258       SetSeq(S_Use);
 259     } else if (Seq == S_Release && IsUser(Class)) {
 260       DEBUG(dbgs() << "PreciseReleaseUse: Seq: " << Seq << "; " << *Ptr
 261                    << "\n");
 262       // Non-movable releases depend on any possible objc pointer use.
 263       SetSeq(S_Stop);
 264       assert(!HasReverseInsertPts());
 265       // As above; handle invoke specially.
 266       if (isa<InvokeInst>(Inst))
 267         InsertReverseInsertPt(BB->getFirstInsertionPt());
 268       else
 269         InsertReverseInsertPt(std::next(BasicBlock::iterator(Inst)));
 270     }
 271     break;
 272   case S_Stop:
 273     if (CanUse(Inst, Ptr, PA, Class)) {
 274       DEBUG(dbgs() << "PreciseStopUse: Seq: " << Seq << "; " << *Ptr << "\n");
 275       SetSeq(S_Use);
 276     }
 277     break;
 278   case S_CanRelease:
 279   case S_Use:
 280   case S_None:
 281     break;
 282   case S_Retain:
 283     llvm_unreachable("bottom-up pointer in retain state!");
 284   }
 285 }
 286
 287 //===----------------------------------------------------------------------===//
 288 //                              TopDownPtrState
 289 //===----------------------------------------------------------------------===//
 290
 291 bool TopDownPtrState::InitTopDown(ARCInstKind Kind, Instruction *I) {
 292   bool NestingDetected = false;
 293   // Don't do retain+release tracking for ARCInstKind::RetainRV, because
 294   // it's
 295   // better to let it remain as the first instruction after a call.
 296   if (Kind != ARCInstKind::RetainRV) {
 297     // If we see two retains in a row on the same pointer. If so, make
 298     // a note, and we'll cicle back to revisit it after we've
 299     // hopefully eliminated the second retain, which may allow us to
 300     // eliminate the first retain too.
 301     // Theoretically we could implement removal of nested retain+release
 302     // pairs by making PtrState hold a stack of states, but this is
 303     // simple and avoids adding overhead for the non-nested case.
 304     if (GetSeq() == S_Retain)
 305       NestingDetected = true;
 306
 307     ResetSequenceProgress(S_Retain);
 308     SetKnownSafe(HasKnownPositiveRefCount());
 309     InsertCall(I);
 310   }
 311
 312   SetKnownPositiveRefCount();
 313   return NestingDetected;
 314 }
 315
 316 bool TopDownPtrState::MatchWithRelease(ARCMDKindCache &Cache,
 317                                        Instruction *Release) {
 318   ClearKnownPositiveRefCount();
 319
 320   Sequence OldSeq = GetSeq();
 321
 322   MDNode *ReleaseMetadata =
 323       Release->getMetadata(Cache.get(ARCMDKindID::ImpreciseRelease));
 324
 325   switch (OldSeq) {
 326   case S_Retain:
 327   case S_CanRelease:
 328     if (OldSeq == S_Retain || ReleaseMetadata != nullptr)
 329       ClearReverseInsertPts();
 330   // FALL THROUGH
 331   case S_Use:
 332     SetReleaseMetadata(ReleaseMetadata);
 333     SetTailCallRelease(cast<CallInst>(Release)->isTailCall());
 334     return true;
 335   case S_None:
 336     return false;
 337   case S_Stop:
 338   case S_Release:
 339   case S_MovableRelease:
 340     llvm_unreachable("top-down pointer in bottom up state!");
 341   }
 342   llvm_unreachable("Sequence unknown enum value");
 343 }
 344
 345 bool TopDownPtrState::HandlePotentialAlterRefCount(Instruction *Inst,
 346                                                    const Value *Ptr,
 347                                                    ProvenanceAnalysis &PA,
 348                                                    ARCInstKind Class) {
 349   // Check for possible releases.
 350   if (!CanAlterRefCount(Inst, Ptr, PA, Class))
 351     return false;
 352
 353   DEBUG(dbgs() << "CanAlterRefCount: Seq: " << Seq << "; " << *Ptr << "\n");
 354   ClearKnownPositiveRefCount();
 355   switch (Seq) {
 356   case S_Retain:
 357     SetSeq(S_CanRelease);
 358     assert(!HasReverseInsertPts());
 359     InsertReverseInsertPt(Inst);
 360
 361     // One call can't cause a transition from S_Retain to S_CanRelease
 362     // and S_CanRelease to S_Use. If we've made the first transition,
 363     // we're done.
 364     return true;
 365   case S_Use:
 366   case S_CanRelease:
 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 release state!");
 373   }
 374   llvm_unreachable("covered switch is not covered!?");
 375 }
 376
 377 void TopDownPtrState::HandlePotentialUse(Instruction *Inst, const Value *Ptr,
 378                                          ProvenanceAnalysis &PA,
 379                                          ARCInstKind Class) {
 380   // Check for possible direct uses.
 381   switch (GetSeq()) {
 382   case S_CanRelease:
 383     if (!CanUse(Inst, Ptr, PA, Class))
 384       return;
 385     DEBUG(dbgs() << "CanUse: Seq: " << Seq << "; " << *Ptr << "\n");
 386     SetSeq(S_Use);
 387     return;
 388   case S_Retain:
 389   case S_Use:
 390   case S_None:
 391     return;
 392   case S_Stop:
 393   case S_Release:
 394   case S_MovableRelease:
 395     llvm_unreachable("top-down pointer in release state!");
 396   }
 397 }