contrib/llvm/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     InsertReverseInsertPt(&*InsertAfter);
 279   };
 280
 281   // Check for possible direct uses.
 282   switch (GetSeq()) {
 283   case S_Release:
 284   case S_MovableRelease:
 285     if (CanUse(Inst, Ptr, PA, Class)) {
 286       LLVM_DEBUG(dbgs() << "            CanUse: Seq: " << GetSeq() << "; "
 287                         << *Ptr << "\n");
 288       SetSeqAndInsertReverseInsertPt(S_Use);
 289     } else if (Seq == S_Release && IsUser(Class)) {
 290       LLVM_DEBUG(dbgs() << "            PreciseReleaseUse: Seq: " << GetSeq()
 291                         << "; " << *Ptr << "\n");
 292       // Non-movable releases depend on any possible objc pointer use.
 293       SetSeqAndInsertReverseInsertPt(S_Stop);
 294     } else if (const auto *Call = getreturnRVOperand(*Inst, Class)) {
 295       if (CanUse(Call, Ptr, PA, GetBasicARCInstKind(Call))) {
 296         LLVM_DEBUG(dbgs() << "            ReleaseUse: Seq: " << GetSeq() << "; "
 297                           << *Ptr << "\n");
 298         SetSeqAndInsertReverseInsertPt(S_Stop);
 299       }
 300     }
 301     break;
 302   case S_Stop:
 303     if (CanUse(Inst, Ptr, PA, Class)) {
 304       LLVM_DEBUG(dbgs() << "            PreciseStopUse: Seq: " << GetSeq()
 305                         << "; " << *Ptr << "\n");
 306       SetSeq(S_Use);
 307     }
 308     break;
 309   case S_CanRelease:
 310   case S_Use:
 311   case S_None:
 312     break;
 313   case S_Retain:
 314     llvm_unreachable("bottom-up pointer in retain state!");
 315   }
 316 }
 317
 318 //===----------------------------------------------------------------------===//
 319 //                              TopDownPtrState
 320 //===----------------------------------------------------------------------===//
 321
 322 bool TopDownPtrState::InitTopDown(ARCInstKind Kind, Instruction *I) {
 323   bool NestingDetected = false;
 324   // Don't do retain+release tracking for ARCInstKind::RetainRV, because
 325   // it's
 326   // better to let it remain as the first instruction after a call.
 327   if (Kind != ARCInstKind::RetainRV) {
 328     // If we see two retains in a row on the same pointer. If so, make
 329     // a note, and we'll cicle back to revisit it after we've
 330     // hopefully eliminated the second retain, which may allow us to
 331     // eliminate the first retain too.
 332     // Theoretically we could implement removal of nested retain+release
 333     // pairs by making PtrState hold a stack of states, but this is
 334     // simple and avoids adding overhead for the non-nested case.
 335     if (GetSeq() == S_Retain)
 336       NestingDetected = true;
 337
 338     ResetSequenceProgress(S_Retain);
 339     SetKnownSafe(HasKnownPositiveRefCount());
 340     InsertCall(I);
 341   }
 342
 343   SetKnownPositiveRefCount();
 344   return NestingDetected;
 345 }
 346
 347 bool TopDownPtrState::MatchWithRelease(ARCMDKindCache &Cache,
 348                                        Instruction *Release) {
 349   ClearKnownPositiveRefCount();
 350
 351   Sequence OldSeq = GetSeq();
 352
 353   MDNode *ReleaseMetadata =
 354       Release->getMetadata(Cache.get(ARCMDKindID::ImpreciseRelease));
 355
 356   switch (OldSeq) {
 357   case S_Retain:
 358   case S_CanRelease:
 359     if (OldSeq == S_Retain || ReleaseMetadata != nullptr)
 360       ClearReverseInsertPts();
 361     LLVM_FALLTHROUGH;
 362   case S_Use:
 363     SetReleaseMetadata(ReleaseMetadata);
 364     SetTailCallRelease(cast<CallInst>(Release)->isTailCall());
 365     return true;
 366   case S_None:
 367     return false;
 368   case S_Stop:
 369   case S_Release:
 370   case S_MovableRelease:
 371     llvm_unreachable("top-down pointer in bottom up state!");
 372   }
 373   llvm_unreachable("Sequence unknown enum value");
 374 }
 375
 376 bool TopDownPtrState::HandlePotentialAlterRefCount(Instruction *Inst,
 377                                                    const Value *Ptr,
 378                                                    ProvenanceAnalysis &PA,
 379                                                    ARCInstKind Class) {
 380   // Check for possible releases. Treat clang.arc.use as a releasing instruction
 381   // to prevent sinking a retain past it.
 382   if (!CanAlterRefCount(Inst, Ptr, PA, Class) &&
 383       Class != ARCInstKind::IntrinsicUser)
 384     return false;
 385
 386   LLVM_DEBUG(dbgs() << "            CanAlterRefCount: Seq: " << GetSeq() << "; "
 387                     << *Ptr << "\n");
 388   ClearKnownPositiveRefCount();
 389   switch (GetSeq()) {
 390   case S_Retain:
 391     SetSeq(S_CanRelease);
 392     assert(!HasReverseInsertPts());
 393     InsertReverseInsertPt(Inst);
 394
 395     // One call can't cause a transition from S_Retain to S_CanRelease
 396     // and S_CanRelease to S_Use. If we've made the first transition,
 397     // we're done.
 398     return true;
 399   case S_Use:
 400   case S_CanRelease:
 401   case S_None:
 402     return false;
 403   case S_Stop:
 404   case S_Release:
 405   case S_MovableRelease:
 406     llvm_unreachable("top-down pointer in release state!");
 407   }
 408   llvm_unreachable("covered switch is not covered!?");
 409 }
 410
 411 void TopDownPtrState::HandlePotentialUse(Instruction *Inst, const Value *Ptr,
 412                                          ProvenanceAnalysis &PA,
 413                                          ARCInstKind Class) {
 414   // Check for possible direct uses.
 415   switch (GetSeq()) {
 416   case S_CanRelease:
 417     if (!CanUse(Inst, Ptr, PA, Class))
 418       return;
 419     LLVM_DEBUG(dbgs() << "             CanUse: Seq: " << GetSeq() << "; "
 420                       << *Ptr << "\n");
 421     SetSeq(S_Use);
 422     return;
 423   case S_Retain:
 424   case S_Use:
 425   case S_None:
 426     return;
 427   case S_Stop:
 428   case S_Release:
 429   case S_MovableRelease:
 430     llvm_unreachable("top-down pointer in release state!");
 431   }
 432 }