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