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