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 } 433