lib/Transforms/ObjCARC/PtrState.cpp

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