437 lines · 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-exception6//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/Analysis/ObjCARCUtil.h"15#include "llvm/IR/BasicBlock.h"16#include "llvm/IR/Instruction.h"17#include "llvm/IR/Instructions.h"18#include "llvm/IR/Value.h"19#include "llvm/Support/Casting.h"20#include "llvm/Support/Compiler.h"21#include "llvm/Support/Debug.h"22#include "llvm/Support/ErrorHandling.h"23#include "llvm/Support/raw_ostream.h"24#include <cassert>25#include <iterator>26#include <utility>27 28using namespace llvm;29using namespace llvm::objcarc;30 31#define DEBUG_TYPE "objc-arc-ptr-state"32 33//===----------------------------------------------------------------------===//34// Utility35//===----------------------------------------------------------------------===//36 37raw_ostream &llvm::objcarc::operator<<(raw_ostream &OS, const Sequence S) {38 switch (S) {39 case S_None:40 return OS << "S_None";41 case S_Retain:42 return OS << "S_Retain";43 case S_CanRelease:44 return OS << "S_CanRelease";45 case S_Use:46 return OS << "S_Use";47 case S_MovableRelease:48 return OS << "S_MovableRelease";49 case S_Stop:50 return OS << "S_Stop";51 }52 llvm_unreachable("Unknown sequence type.");53}54 55//===----------------------------------------------------------------------===//56// Sequence57//===----------------------------------------------------------------------===//58 59static Sequence MergeSeqs(Sequence A, Sequence B, bool TopDown) {60 // The easy cases.61 if (A == B)62 return A;63 if (A == S_None || B == S_None)64 return S_None;65 66 if (A > B)67 std::swap(A, B);68 if (TopDown) {69 // Choose the side which is further along in the sequence.70 if ((A == S_Retain || A == S_CanRelease) &&71 (B == S_CanRelease || B == S_Use))72 return B;73 } else {74 // Choose the side which is further along in the sequence.75 if ((A == S_Use || A == S_CanRelease) &&76 (B == S_Use || B == S_Stop || B == S_MovableRelease))77 return A;78 // If both sides are releases, choose the more conservative one.79 if (A == S_Stop && B == S_MovableRelease)80 return A;81 }82 83 return S_None;84}85 86//===----------------------------------------------------------------------===//87// RRInfo88//===----------------------------------------------------------------------===//89 90void RRInfo::clear() {91 KnownSafe = false;92 IsTailCallRelease = false;93 ReleaseMetadata = nullptr;94 Calls.clear();95 ReverseInsertPts.clear();96 CFGHazardAfflicted = false;97}98 99bool RRInfo::Merge(const RRInfo &Other) {100 // Conservatively merge the ReleaseMetadata information.101 if (ReleaseMetadata != Other.ReleaseMetadata)102 ReleaseMetadata = nullptr;103 104 // Conservatively merge the boolean state.105 KnownSafe &= Other.KnownSafe;106 IsTailCallRelease &= Other.IsTailCallRelease;107 CFGHazardAfflicted |= Other.CFGHazardAfflicted;108 109 // Merge the call sets.110 Calls.insert_range(Other.Calls);111 112 // Merge the insert point sets. If there are any differences,113 // that makes this a partial merge.114 bool Partial = ReverseInsertPts.size() != Other.ReverseInsertPts.size();115 for (Instruction *Inst : Other.ReverseInsertPts)116 Partial |= ReverseInsertPts.insert(Inst).second;117 return Partial;118}119 120//===----------------------------------------------------------------------===//121// PtrState122//===----------------------------------------------------------------------===//123 124void PtrState::SetKnownPositiveRefCount() {125 LLVM_DEBUG(dbgs() << " Setting Known Positive.\n");126 KnownPositiveRefCount = true;127}128 129void PtrState::ClearKnownPositiveRefCount() {130 LLVM_DEBUG(dbgs() << " Clearing Known Positive.\n");131 KnownPositiveRefCount = false;132}133 134void PtrState::SetSeq(Sequence NewSeq) {135 LLVM_DEBUG(dbgs() << " Old: " << GetSeq() << "; New: " << NewSeq136 << "\n");137 Seq = NewSeq;138}139 140void PtrState::ResetSequenceProgress(Sequence NewSeq) {141 LLVM_DEBUG(dbgs() << " Resetting sequence progress.\n");142 SetSeq(NewSeq);143 Partial = false;144 RRI.clear();145}146 147void PtrState::Merge(const PtrState &Other, bool TopDown) {148 Seq = MergeSeqs(GetSeq(), Other.GetSeq(), TopDown);149 KnownPositiveRefCount &= Other.KnownPositiveRefCount;150 151 // If we're not in a sequence (anymore), drop all associated state.152 if (Seq == S_None) {153 Partial = false;154 RRI.clear();155 } else if (Partial || Other.Partial) {156 // If we're doing a merge on a path that's previously seen a partial157 // merge, conservatively drop the sequence, to avoid doing partial158 // RR elimination. If the branch predicates for the two merge differ,159 // mixing them is unsafe.160 ClearSequenceProgress();161 } else {162 // Otherwise merge the other PtrState's RRInfo into our RRInfo. At this163 // point, we know that currently we are not partial. Stash whether or not164 // the merge operation caused us to undergo a partial merging of reverse165 // insertion points.166 Partial = RRI.Merge(Other.RRI);167 }168}169 170//===----------------------------------------------------------------------===//171// BottomUpPtrState172//===----------------------------------------------------------------------===//173 174bool BottomUpPtrState::InitBottomUp(ARCMDKindCache &Cache, Instruction *I) {175 // If we see two releases in a row on the same pointer. If so, make176 // a note, and we'll cicle back to revisit it after we've177 // hopefully eliminated the second release, which may allow us to178 // eliminate the first release too.179 // Theoretically we could implement removal of nested retain+release180 // pairs by making PtrState hold a stack of states, but this is181 // simple and avoids adding overhead for the non-nested case.182 bool NestingDetected = false;183 if (GetSeq() == S_MovableRelease) {184 LLVM_DEBUG(185 dbgs() << " Found nested releases (i.e. a release pair)\n");186 NestingDetected = true;187 }188 189 MDNode *ReleaseMetadata =190 I->getMetadata(Cache.get(ARCMDKindID::ImpreciseRelease));191 Sequence NewSeq = ReleaseMetadata ? S_MovableRelease : S_Stop;192 ResetSequenceProgress(NewSeq);193 if (NewSeq == S_Stop)194 InsertReverseInsertPt(I);195 SetReleaseMetadata(ReleaseMetadata);196 SetKnownSafe(HasKnownPositiveRefCount());197 SetTailCallRelease(cast<CallInst>(I)->isTailCall());198 InsertCall(I);199 SetKnownPositiveRefCount();200 return NestingDetected;201}202 203bool BottomUpPtrState::MatchWithRetain() {204 SetKnownPositiveRefCount();205 206 Sequence OldSeq = GetSeq();207 switch (OldSeq) {208 case S_Stop:209 case S_MovableRelease:210 case S_Use:211 // If OldSeq is not S_Use or OldSeq is S_Use and we are tracking an212 // imprecise release, clear our reverse insertion points.213 if (OldSeq != S_Use || IsTrackingImpreciseReleases())214 ClearReverseInsertPts();215 [[fallthrough]];216 case S_CanRelease:217 return true;218 case S_None:219 return false;220 case S_Retain:221 llvm_unreachable("bottom-up pointer in retain state!");222 }223 llvm_unreachable("Sequence unknown enum value");224}225 226bool BottomUpPtrState::HandlePotentialAlterRefCount(Instruction *Inst,227 const Value *Ptr,228 ProvenanceAnalysis &PA,229 ARCInstKind Class) {230 Sequence S = GetSeq();231 232 // Check for possible releases.233 if (!CanDecrementRefCount(Inst, Ptr, PA, Class))234 return false;235 236 LLVM_DEBUG(dbgs() << " CanAlterRefCount: Seq: " << S << "; "237 << *Ptr << "\n");238 switch (S) {239 case S_Use:240 SetSeq(S_CanRelease);241 return true;242 case S_CanRelease:243 case S_MovableRelease:244 case S_Stop:245 case S_None:246 return false;247 case S_Retain:248 llvm_unreachable("bottom-up pointer in retain state!");249 }250 llvm_unreachable("Sequence unknown enum value");251}252 253void BottomUpPtrState::HandlePotentialUse(BasicBlock *BB, Instruction *Inst,254 const Value *Ptr,255 ProvenanceAnalysis &PA,256 ARCInstKind Class) {257 auto SetSeqAndInsertReverseInsertPt = [&](Sequence NewSeq){258 assert(!HasReverseInsertPts());259 SetSeq(NewSeq);260 // If this is an invoke instruction, we're scanning it as part of261 // one of its successor blocks, since we can't insert code after it262 // in its own block, and we don't want to split critical edges.263 BasicBlock::iterator InsertAfter;264 if (isa<InvokeInst>(Inst)) {265 const auto IP = BB->getFirstInsertionPt();266 InsertAfter = IP == BB->end() ? std::prev(BB->end()) : IP;267 if (isa<CatchSwitchInst>(InsertAfter))268 // A catchswitch must be the only non-phi instruction in its basic269 // block, so attempting to insert an instruction into such a block would270 // produce invalid IR.271 SetCFGHazardAfflicted(true);272 } else {273 InsertAfter = std::next(Inst->getIterator());274 }275 276 if (InsertAfter != BB->end())277 InsertAfter = skipDebugIntrinsics(InsertAfter);278 279 InsertReverseInsertPt(&*InsertAfter);280 281 // Don't insert anything between a call/invoke with operand bundle282 // "clang.arc.attachedcall" and the retainRV/claimRV call that uses the call283 // result.284 if (auto *CB = dyn_cast<CallBase>(Inst))285 if (objcarc::hasAttachedCallOpBundle(CB))286 SetCFGHazardAfflicted(true);287 };288 289 // Check for possible direct uses.290 switch (GetSeq()) {291 case S_MovableRelease:292 if (CanUse(Inst, Ptr, PA, Class)) {293 LLVM_DEBUG(dbgs() << " CanUse: Seq: " << GetSeq() << "; "294 << *Ptr << "\n");295 SetSeqAndInsertReverseInsertPt(S_Use);296 } else if (const auto *Call = getreturnRVOperand(*Inst, Class)) {297 if (CanUse(Call, Ptr, PA, GetBasicARCInstKind(Call))) {298 LLVM_DEBUG(dbgs() << " ReleaseUse: Seq: " << GetSeq() << "; "299 << *Ptr << "\n");300 SetSeqAndInsertReverseInsertPt(S_Stop);301 }302 }303 break;304 case S_Stop:305 if (CanUse(Inst, Ptr, PA, Class)) {306 LLVM_DEBUG(dbgs() << " PreciseStopUse: Seq: " << GetSeq()307 << "; " << *Ptr << "\n");308 SetSeq(S_Use);309 }310 break;311 case S_CanRelease:312 case S_Use:313 case S_None:314 break;315 case S_Retain:316 llvm_unreachable("bottom-up pointer in retain state!");317 }318}319 320//===----------------------------------------------------------------------===//321// TopDownPtrState322//===----------------------------------------------------------------------===//323 324bool TopDownPtrState::InitTopDown(ARCInstKind Kind, Instruction *I) {325 bool NestingDetected = false;326 // Don't do retain+release tracking for ARCInstKind::RetainRV, because327 // it's328 // better to let it remain as the first instruction after a call.329 if (Kind != ARCInstKind::RetainRV) {330 // If we see two retains in a row on the same pointer. If so, make331 // a note, and we'll cicle back to revisit it after we've332 // hopefully eliminated the second retain, which may allow us to333 // eliminate the first retain too.334 // Theoretically we could implement removal of nested retain+release335 // pairs by making PtrState hold a stack of states, but this is336 // simple and avoids adding overhead for the non-nested case.337 if (GetSeq() == S_Retain)338 NestingDetected = true;339 340 ResetSequenceProgress(S_Retain);341 SetKnownSafe(HasKnownPositiveRefCount());342 InsertCall(I);343 }344 345 SetKnownPositiveRefCount();346 return NestingDetected;347}348 349bool TopDownPtrState::MatchWithRelease(ARCMDKindCache &Cache,350 Instruction *Release) {351 ClearKnownPositiveRefCount();352 353 Sequence OldSeq = GetSeq();354 355 MDNode *ReleaseMetadata =356 Release->getMetadata(Cache.get(ARCMDKindID::ImpreciseRelease));357 358 switch (OldSeq) {359 case S_Retain:360 case S_CanRelease:361 if (OldSeq == S_Retain || ReleaseMetadata != nullptr)362 ClearReverseInsertPts();363 [[fallthrough]];364 case S_Use:365 SetReleaseMetadata(ReleaseMetadata);366 SetTailCallRelease(cast<CallInst>(Release)->isTailCall());367 return true;368 case S_None:369 return false;370 case S_Stop:371 case S_MovableRelease:372 llvm_unreachable("top-down pointer in bottom up state!");373 }374 llvm_unreachable("Sequence unknown enum value");375}376 377bool TopDownPtrState::HandlePotentialAlterRefCount(378 Instruction *Inst, const Value *Ptr, ProvenanceAnalysis &PA,379 ARCInstKind Class, const BundledRetainClaimRVs &BundledRVs) {380 // Check for possible releases. Treat clang.arc.use as a releasing instruction381 // to prevent sinking a retain past it.382 if (!CanDecrementRefCount(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 // Don't insert anything between a call/invoke with operand bundle396 // "clang.arc.attachedcall" and the retainRV/claimRV call that uses the call397 // result.398 if (BundledRVs.contains(Inst))399 SetCFGHazardAfflicted(true);400 401 // One call can't cause a transition from S_Retain to S_CanRelease402 // and S_CanRelease to S_Use. If we've made the first transition,403 // we're done.404 return true;405 case S_Use:406 case S_CanRelease:407 case S_None:408 return false;409 case S_Stop:410 case S_MovableRelease:411 llvm_unreachable("top-down pointer in release state!");412 }413 llvm_unreachable("covered switch is not covered!?");414}415 416void TopDownPtrState::HandlePotentialUse(Instruction *Inst, const Value *Ptr,417 ProvenanceAnalysis &PA,418 ARCInstKind Class) {419 // Check for possible direct uses.420 switch (GetSeq()) {421 case S_CanRelease:422 if (!CanUse(Inst, Ptr, PA, Class))423 return;424 LLVM_DEBUG(dbgs() << " CanUse: Seq: " << GetSeq() << "; "425 << *Ptr << "\n");426 SetSeq(S_Use);427 return;428 case S_Retain:429 case S_Use:430 case S_None:431 return;432 case S_Stop:433 case S_MovableRelease:434 llvm_unreachable("top-down pointer in release state!");435 }436}437