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 (!CanDecrementRefCount(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 (!CanDecrementRefCount(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 } 437