1283625Sdim//===--- PtrState.cpp -----------------------------------------------------===// 2283625Sdim// 3283625Sdim// The LLVM Compiler Infrastructure 4283625Sdim// 5283625Sdim// This file is distributed under the University of Illinois Open Source 6283625Sdim// License. See LICENSE.TXT for details. 7283625Sdim// 8283625Sdim//===----------------------------------------------------------------------===// 9283625Sdim 10283625Sdim#include "PtrState.h" 11283625Sdim#include "DependencyAnalysis.h" 12283625Sdim#include "ObjCARC.h" 13283625Sdim#include "llvm/Support/Debug.h" 14283625Sdim#include "llvm/Support/raw_ostream.h" 15283625Sdim 16283625Sdimusing namespace llvm; 17283625Sdimusing namespace llvm::objcarc; 18283625Sdim 19283625Sdim#define DEBUG_TYPE "objc-arc-ptr-state" 20283625Sdim 21283625Sdim//===----------------------------------------------------------------------===// 22283625Sdim// Utility 23283625Sdim//===----------------------------------------------------------------------===// 24283625Sdim 25283625Sdimraw_ostream &llvm::objcarc::operator<<(raw_ostream &OS, const Sequence S) { 26283625Sdim switch (S) { 27283625Sdim case S_None: 28283625Sdim return OS << "S_None"; 29283625Sdim case S_Retain: 30283625Sdim return OS << "S_Retain"; 31283625Sdim case S_CanRelease: 32283625Sdim return OS << "S_CanRelease"; 33283625Sdim case S_Use: 34283625Sdim return OS << "S_Use"; 35283625Sdim case S_Release: 36283625Sdim return OS << "S_Release"; 37283625Sdim case S_MovableRelease: 38283625Sdim return OS << "S_MovableRelease"; 39283625Sdim case S_Stop: 40283625Sdim return OS << "S_Stop"; 41283625Sdim } 42283625Sdim llvm_unreachable("Unknown sequence type."); 43283625Sdim} 44283625Sdim 45283625Sdim//===----------------------------------------------------------------------===// 46283625Sdim// Sequence 47283625Sdim//===----------------------------------------------------------------------===// 48283625Sdim 49283625Sdimstatic Sequence MergeSeqs(Sequence A, Sequence B, bool TopDown) { 50283625Sdim // The easy cases. 51283625Sdim if (A == B) 52283625Sdim return A; 53283625Sdim if (A == S_None || B == S_None) 54283625Sdim return S_None; 55283625Sdim 56283625Sdim if (A > B) 57283625Sdim std::swap(A, B); 58283625Sdim if (TopDown) { 59283625Sdim // Choose the side which is further along in the sequence. 60283625Sdim if ((A == S_Retain || A == S_CanRelease) && 61283625Sdim (B == S_CanRelease || B == S_Use)) 62283625Sdim return B; 63283625Sdim } else { 64283625Sdim // Choose the side which is further along in the sequence. 65283625Sdim if ((A == S_Use || A == S_CanRelease) && 66283625Sdim (B == S_Use || B == S_Release || B == S_Stop || B == S_MovableRelease)) 67283625Sdim return A; 68283625Sdim // If both sides are releases, choose the more conservative one. 69283625Sdim if (A == S_Stop && (B == S_Release || B == S_MovableRelease)) 70283625Sdim return A; 71283625Sdim if (A == S_Release && B == S_MovableRelease) 72283625Sdim return A; 73283625Sdim } 74283625Sdim 75283625Sdim return S_None; 76283625Sdim} 77283625Sdim 78283625Sdim//===----------------------------------------------------------------------===// 79283625Sdim// RRInfo 80283625Sdim//===----------------------------------------------------------------------===// 81283625Sdim 82283625Sdimvoid RRInfo::clear() { 83283625Sdim KnownSafe = false; 84283625Sdim IsTailCallRelease = false; 85283625Sdim ReleaseMetadata = nullptr; 86283625Sdim Calls.clear(); 87283625Sdim ReverseInsertPts.clear(); 88283625Sdim CFGHazardAfflicted = false; 89283625Sdim} 90283625Sdim 91283625Sdimbool RRInfo::Merge(const RRInfo &Other) { 92283625Sdim // Conservatively merge the ReleaseMetadata information. 93283625Sdim if (ReleaseMetadata != Other.ReleaseMetadata) 94283625Sdim ReleaseMetadata = nullptr; 95283625Sdim 96283625Sdim // Conservatively merge the boolean state. 97283625Sdim KnownSafe &= Other.KnownSafe; 98283625Sdim IsTailCallRelease &= Other.IsTailCallRelease; 99283625Sdim CFGHazardAfflicted |= Other.CFGHazardAfflicted; 100283625Sdim 101283625Sdim // Merge the call sets. 102283625Sdim Calls.insert(Other.Calls.begin(), Other.Calls.end()); 103283625Sdim 104283625Sdim // Merge the insert point sets. If there are any differences, 105283625Sdim // that makes this a partial merge. 106283625Sdim bool Partial = ReverseInsertPts.size() != Other.ReverseInsertPts.size(); 107283625Sdim for (Instruction *Inst : Other.ReverseInsertPts) 108283625Sdim Partial |= ReverseInsertPts.insert(Inst).second; 109283625Sdim return Partial; 110283625Sdim} 111283625Sdim 112283625Sdim//===----------------------------------------------------------------------===// 113283625Sdim// PtrState 114283625Sdim//===----------------------------------------------------------------------===// 115283625Sdim 116283625Sdimvoid PtrState::SetKnownPositiveRefCount() { 117283625Sdim DEBUG(dbgs() << " Setting Known Positive.\n"); 118283625Sdim KnownPositiveRefCount = true; 119283625Sdim} 120283625Sdim 121283625Sdimvoid PtrState::ClearKnownPositiveRefCount() { 122283625Sdim DEBUG(dbgs() << " Clearing Known Positive.\n"); 123283625Sdim KnownPositiveRefCount = false; 124283625Sdim} 125283625Sdim 126283625Sdimvoid PtrState::SetSeq(Sequence NewSeq) { 127283625Sdim DEBUG(dbgs() << " Old: " << GetSeq() << "; New: " << NewSeq << "\n"); 128283625Sdim Seq = NewSeq; 129283625Sdim} 130283625Sdim 131283625Sdimvoid PtrState::ResetSequenceProgress(Sequence NewSeq) { 132283625Sdim DEBUG(dbgs() << " Resetting sequence progress.\n"); 133283625Sdim SetSeq(NewSeq); 134283625Sdim Partial = false; 135283625Sdim RRI.clear(); 136283625Sdim} 137283625Sdim 138283625Sdimvoid PtrState::Merge(const PtrState &Other, bool TopDown) { 139283625Sdim Seq = MergeSeqs(GetSeq(), Other.GetSeq(), TopDown); 140283625Sdim KnownPositiveRefCount &= Other.KnownPositiveRefCount; 141283625Sdim 142283625Sdim // If we're not in a sequence (anymore), drop all associated state. 143283625Sdim if (Seq == S_None) { 144283625Sdim Partial = false; 145283625Sdim RRI.clear(); 146283625Sdim } else if (Partial || Other.Partial) { 147283625Sdim // If we're doing a merge on a path that's previously seen a partial 148283625Sdim // merge, conservatively drop the sequence, to avoid doing partial 149283625Sdim // RR elimination. If the branch predicates for the two merge differ, 150283625Sdim // mixing them is unsafe. 151283625Sdim ClearSequenceProgress(); 152283625Sdim } else { 153283625Sdim // Otherwise merge the other PtrState's RRInfo into our RRInfo. At this 154283625Sdim // point, we know that currently we are not partial. Stash whether or not 155283625Sdim // the merge operation caused us to undergo a partial merging of reverse 156283625Sdim // insertion points. 157283625Sdim Partial = RRI.Merge(Other.RRI); 158283625Sdim } 159283625Sdim} 160283625Sdim 161283625Sdim//===----------------------------------------------------------------------===// 162283625Sdim// BottomUpPtrState 163283625Sdim//===----------------------------------------------------------------------===// 164283625Sdim 165283625Sdimbool BottomUpPtrState::InitBottomUp(ARCMDKindCache &Cache, Instruction *I) { 166283625Sdim // If we see two releases in a row on the same pointer. If so, make 167283625Sdim // a note, and we'll cicle back to revisit it after we've 168283625Sdim // hopefully eliminated the second release, which may allow us to 169283625Sdim // eliminate the first release too. 170283625Sdim // Theoretically we could implement removal of nested retain+release 171283625Sdim // pairs by making PtrState hold a stack of states, but this is 172283625Sdim // simple and avoids adding overhead for the non-nested case. 173283625Sdim bool NestingDetected = false; 174283625Sdim if (GetSeq() == S_Release || GetSeq() == S_MovableRelease) { 175283625Sdim DEBUG(dbgs() << " Found nested releases (i.e. a release pair)\n"); 176283625Sdim NestingDetected = true; 177283625Sdim } 178283625Sdim 179283625Sdim MDNode *ReleaseMetadata = 180283625Sdim I->getMetadata(Cache.get(ARCMDKindID::ImpreciseRelease)); 181283625Sdim Sequence NewSeq = ReleaseMetadata ? S_MovableRelease : S_Release; 182283625Sdim ResetSequenceProgress(NewSeq); 183283625Sdim SetReleaseMetadata(ReleaseMetadata); 184283625Sdim SetKnownSafe(HasKnownPositiveRefCount()); 185283625Sdim SetTailCallRelease(cast<CallInst>(I)->isTailCall()); 186283625Sdim InsertCall(I); 187283625Sdim SetKnownPositiveRefCount(); 188283625Sdim return NestingDetected; 189283625Sdim} 190283625Sdim 191283625Sdimbool BottomUpPtrState::MatchWithRetain() { 192283625Sdim SetKnownPositiveRefCount(); 193283625Sdim 194283625Sdim Sequence OldSeq = GetSeq(); 195283625Sdim switch (OldSeq) { 196283625Sdim case S_Stop: 197283625Sdim case S_Release: 198283625Sdim case S_MovableRelease: 199283625Sdim case S_Use: 200283625Sdim // If OldSeq is not S_Use or OldSeq is S_Use and we are tracking an 201283625Sdim // imprecise release, clear our reverse insertion points. 202283625Sdim if (OldSeq != S_Use || IsTrackingImpreciseReleases()) 203283625Sdim ClearReverseInsertPts(); 204283625Sdim // FALL THROUGH 205283625Sdim case S_CanRelease: 206283625Sdim return true; 207283625Sdim case S_None: 208283625Sdim return false; 209283625Sdim case S_Retain: 210283625Sdim llvm_unreachable("bottom-up pointer in retain state!"); 211283625Sdim } 212283625Sdim llvm_unreachable("Sequence unknown enum value"); 213283625Sdim} 214283625Sdim 215283625Sdimbool BottomUpPtrState::HandlePotentialAlterRefCount(Instruction *Inst, 216283625Sdim const Value *Ptr, 217283625Sdim ProvenanceAnalysis &PA, 218283625Sdim ARCInstKind Class) { 219283625Sdim Sequence S = GetSeq(); 220283625Sdim 221283625Sdim // Check for possible releases. 222283625Sdim if (!CanAlterRefCount(Inst, Ptr, PA, Class)) 223283625Sdim return false; 224283625Sdim 225283625Sdim DEBUG(dbgs() << " CanAlterRefCount: Seq: " << S << "; " << *Ptr 226283625Sdim << "\n"); 227283625Sdim switch (S) { 228283625Sdim case S_Use: 229283625Sdim SetSeq(S_CanRelease); 230283625Sdim return true; 231283625Sdim case S_CanRelease: 232283625Sdim case S_Release: 233283625Sdim case S_MovableRelease: 234283625Sdim case S_Stop: 235283625Sdim case S_None: 236283625Sdim return false; 237283625Sdim case S_Retain: 238283625Sdim llvm_unreachable("bottom-up pointer in retain state!"); 239283625Sdim } 240283625Sdim llvm_unreachable("Sequence unknown enum value"); 241283625Sdim} 242283625Sdim 243283625Sdimvoid BottomUpPtrState::HandlePotentialUse(BasicBlock *BB, Instruction *Inst, 244283625Sdim const Value *Ptr, 245283625Sdim ProvenanceAnalysis &PA, 246283625Sdim ARCInstKind Class) { 247283625Sdim // Check for possible direct uses. 248283625Sdim switch (GetSeq()) { 249283625Sdim case S_Release: 250283625Sdim case S_MovableRelease: 251283625Sdim if (CanUse(Inst, Ptr, PA, Class)) { 252283625Sdim DEBUG(dbgs() << " CanUse: Seq: " << GetSeq() << "; " << *Ptr 253283625Sdim << "\n"); 254283625Sdim assert(!HasReverseInsertPts()); 255283625Sdim // If this is an invoke instruction, we're scanning it as part of 256283625Sdim // one of its successor blocks, since we can't insert code after it 257283625Sdim // in its own block, and we don't want to split critical edges. 258283625Sdim if (isa<InvokeInst>(Inst)) 259296417Sdim InsertReverseInsertPt(&*BB->getFirstInsertionPt()); 260283625Sdim else 261296417Sdim InsertReverseInsertPt(&*++Inst->getIterator()); 262283625Sdim SetSeq(S_Use); 263283625Sdim } else if (Seq == S_Release && IsUser(Class)) { 264283625Sdim DEBUG(dbgs() << " PreciseReleaseUse: Seq: " << GetSeq() << "; " 265283625Sdim << *Ptr << "\n"); 266283625Sdim // Non-movable releases depend on any possible objc pointer use. 267283625Sdim SetSeq(S_Stop); 268283625Sdim assert(!HasReverseInsertPts()); 269283625Sdim // As above; handle invoke specially. 270283625Sdim if (isa<InvokeInst>(Inst)) 271296417Sdim InsertReverseInsertPt(&*BB->getFirstInsertionPt()); 272283625Sdim else 273296417Sdim InsertReverseInsertPt(&*++Inst->getIterator()); 274283625Sdim } 275283625Sdim break; 276283625Sdim case S_Stop: 277283625Sdim if (CanUse(Inst, Ptr, PA, Class)) { 278283625Sdim DEBUG(dbgs() << " PreciseStopUse: Seq: " << GetSeq() << "; " 279283625Sdim << *Ptr << "\n"); 280283625Sdim SetSeq(S_Use); 281283625Sdim } 282283625Sdim break; 283283625Sdim case S_CanRelease: 284283625Sdim case S_Use: 285283625Sdim case S_None: 286283625Sdim break; 287283625Sdim case S_Retain: 288283625Sdim llvm_unreachable("bottom-up pointer in retain state!"); 289283625Sdim } 290283625Sdim} 291283625Sdim 292283625Sdim//===----------------------------------------------------------------------===// 293283625Sdim// TopDownPtrState 294283625Sdim//===----------------------------------------------------------------------===// 295283625Sdim 296283625Sdimbool TopDownPtrState::InitTopDown(ARCInstKind Kind, Instruction *I) { 297283625Sdim bool NestingDetected = false; 298283625Sdim // Don't do retain+release tracking for ARCInstKind::RetainRV, because 299283625Sdim // it's 300283625Sdim // better to let it remain as the first instruction after a call. 301283625Sdim if (Kind != ARCInstKind::RetainRV) { 302283625Sdim // If we see two retains in a row on the same pointer. If so, make 303283625Sdim // a note, and we'll cicle back to revisit it after we've 304283625Sdim // hopefully eliminated the second retain, which may allow us to 305283625Sdim // eliminate the first retain too. 306283625Sdim // Theoretically we could implement removal of nested retain+release 307283625Sdim // pairs by making PtrState hold a stack of states, but this is 308283625Sdim // simple and avoids adding overhead for the non-nested case. 309283625Sdim if (GetSeq() == S_Retain) 310283625Sdim NestingDetected = true; 311283625Sdim 312283625Sdim ResetSequenceProgress(S_Retain); 313283625Sdim SetKnownSafe(HasKnownPositiveRefCount()); 314283625Sdim InsertCall(I); 315283625Sdim } 316283625Sdim 317283625Sdim SetKnownPositiveRefCount(); 318283625Sdim return NestingDetected; 319283625Sdim} 320283625Sdim 321283625Sdimbool TopDownPtrState::MatchWithRelease(ARCMDKindCache &Cache, 322283625Sdim Instruction *Release) { 323283625Sdim ClearKnownPositiveRefCount(); 324283625Sdim 325283625Sdim Sequence OldSeq = GetSeq(); 326283625Sdim 327283625Sdim MDNode *ReleaseMetadata = 328283625Sdim Release->getMetadata(Cache.get(ARCMDKindID::ImpreciseRelease)); 329283625Sdim 330283625Sdim switch (OldSeq) { 331283625Sdim case S_Retain: 332283625Sdim case S_CanRelease: 333283625Sdim if (OldSeq == S_Retain || ReleaseMetadata != nullptr) 334283625Sdim ClearReverseInsertPts(); 335283625Sdim // FALL THROUGH 336283625Sdim case S_Use: 337283625Sdim SetReleaseMetadata(ReleaseMetadata); 338283625Sdim SetTailCallRelease(cast<CallInst>(Release)->isTailCall()); 339283625Sdim return true; 340283625Sdim case S_None: 341283625Sdim return false; 342283625Sdim case S_Stop: 343283625Sdim case S_Release: 344283625Sdim case S_MovableRelease: 345283625Sdim llvm_unreachable("top-down pointer in bottom up state!"); 346283625Sdim } 347283625Sdim llvm_unreachable("Sequence unknown enum value"); 348283625Sdim} 349283625Sdim 350283625Sdimbool TopDownPtrState::HandlePotentialAlterRefCount(Instruction *Inst, 351283625Sdim const Value *Ptr, 352283625Sdim ProvenanceAnalysis &PA, 353283625Sdim ARCInstKind Class) { 354283625Sdim // Check for possible releases. 355283625Sdim if (!CanAlterRefCount(Inst, Ptr, PA, Class)) 356283625Sdim return false; 357283625Sdim 358283625Sdim DEBUG(dbgs() << " CanAlterRefCount: Seq: " << GetSeq() << "; " << *Ptr 359283625Sdim << "\n"); 360283625Sdim ClearKnownPositiveRefCount(); 361283625Sdim switch (GetSeq()) { 362283625Sdim case S_Retain: 363283625Sdim SetSeq(S_CanRelease); 364283625Sdim assert(!HasReverseInsertPts()); 365283625Sdim InsertReverseInsertPt(Inst); 366283625Sdim 367283625Sdim // One call can't cause a transition from S_Retain to S_CanRelease 368283625Sdim // and S_CanRelease to S_Use. If we've made the first transition, 369283625Sdim // we're done. 370283625Sdim return true; 371283625Sdim case S_Use: 372283625Sdim case S_CanRelease: 373283625Sdim case S_None: 374283625Sdim return false; 375283625Sdim case S_Stop: 376283625Sdim case S_Release: 377283625Sdim case S_MovableRelease: 378283625Sdim llvm_unreachable("top-down pointer in release state!"); 379283625Sdim } 380283625Sdim llvm_unreachable("covered switch is not covered!?"); 381283625Sdim} 382283625Sdim 383283625Sdimvoid TopDownPtrState::HandlePotentialUse(Instruction *Inst, const Value *Ptr, 384283625Sdim ProvenanceAnalysis &PA, 385283625Sdim ARCInstKind Class) { 386283625Sdim // Check for possible direct uses. 387283625Sdim switch (GetSeq()) { 388283625Sdim case S_CanRelease: 389283625Sdim if (!CanUse(Inst, Ptr, PA, Class)) 390283625Sdim return; 391283625Sdim DEBUG(dbgs() << " CanUse: Seq: " << GetSeq() << "; " << *Ptr 392283625Sdim << "\n"); 393283625Sdim SetSeq(S_Use); 394283625Sdim return; 395283625Sdim case S_Retain: 396283625Sdim case S_Use: 397283625Sdim case S_None: 398283625Sdim return; 399283625Sdim case S_Stop: 400283625Sdim case S_Release: 401283625Sdim case S_MovableRelease: 402283625Sdim llvm_unreachable("top-down pointer in release state!"); 403283625Sdim } 404283625Sdim} 405