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