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/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// Utility
35//===----------------------------------------------------------------------===//
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// Sequence
57//===----------------------------------------------------------------------===//
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&: A, b&: 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// RRInfo
88//===----------------------------------------------------------------------===//
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(R: 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(Ptr: Inst).second;
117 return Partial;
118}
119
120//===----------------------------------------------------------------------===//
121// PtrState
122//===----------------------------------------------------------------------===//
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: " << NewSeq
136 << "\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(A: GetSeq(), B: 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 partial
157 // merge, conservatively drop the sequence, to avoid doing partial
158 // 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 this
163 // point, we know that currently we are not partial. Stash whether or not
164 // the merge operation caused us to undergo a partial merging of reverse
165 // insertion points.
166 Partial = RRI.Merge(Other: Other.RRI);
167 }
168}
169
170//===----------------------------------------------------------------------===//
171// BottomUpPtrState
172//===----------------------------------------------------------------------===//
173
174bool BottomUpPtrState::InitBottomUp(ARCMDKindCache &Cache, Instruction *I) {
175 // If we see two releases in a row on the same pointer. If so, make
176 // a note, and we'll cicle back to revisit it after we've
177 // hopefully eliminated the second release, which may allow us to
178 // eliminate the first release too.
179 // Theoretically we could implement removal of nested retain+release
180 // pairs by making PtrState hold a stack of states, but this is
181 // 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(KindID: Cache.get(ID: 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>(Val: 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 an
212 // 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 of
261 // one of its successor blocks, since we can't insert code after it
262 // in its own block, and we don't want to split critical edges.
263 BasicBlock::iterator InsertAfter;
264 if (isa<InvokeInst>(Val: Inst)) {
265 const auto IP = BB->getFirstInsertionPt();
266 InsertAfter = IP == BB->end() ? std::prev(x: BB->end()) : IP;
267 if (isa<CatchSwitchInst>(Val: InsertAfter))
268 // A catchswitch must be the only non-phi instruction in its basic
269 // block, so attempting to insert an instruction into such a block would
270 // produce invalid IR.
271 SetCFGHazardAfflicted(true);
272 } else {
273 InsertAfter = std::next(x: Inst->getIterator());
274 }
275
276 InsertReverseInsertPt(I: &*InsertAfter);
277
278 // Don't insert anything between a call/invoke with operand bundle
279 // "clang.arc.attachedcall" and the retainRV/claimRV call that uses the call
280 // result.
281 if (auto *CB = dyn_cast<CallBase>(Val: Inst))
282 if (objcarc::hasAttachedCallOpBundle(CB))
283 SetCFGHazardAfflicted(true);
284 };
285
286 // Check for possible direct uses.
287 switch (GetSeq()) {
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 (const auto *Call = getreturnRVOperand(Inst: *Inst, Class)) {
294 if (CanUse(Inst: Call, Ptr, PA, Class: GetBasicARCInstKind(V: Call))) {
295 LLVM_DEBUG(dbgs() << " ReleaseUse: Seq: " << GetSeq() << "; "
296 << *Ptr << "\n");
297 SetSeqAndInsertReverseInsertPt(S_Stop);
298 }
299 }
300 break;
301 case S_Stop:
302 if (CanUse(Inst, Ptr, PA, Class)) {
303 LLVM_DEBUG(dbgs() << " PreciseStopUse: Seq: " << GetSeq()
304 << "; " << *Ptr << "\n");
305 SetSeq(S_Use);
306 }
307 break;
308 case S_CanRelease:
309 case S_Use:
310 case S_None:
311 break;
312 case S_Retain:
313 llvm_unreachable("bottom-up pointer in retain state!");
314 }
315}
316
317//===----------------------------------------------------------------------===//
318// TopDownPtrState
319//===----------------------------------------------------------------------===//
320
321bool TopDownPtrState::InitTopDown(ARCInstKind Kind, Instruction *I) {
322 bool NestingDetected = false;
323 // Don't do retain+release tracking for ARCInstKind::RetainRV, because
324 // it's
325 // better to let it remain as the first instruction after a call.
326 if (Kind != ARCInstKind::RetainRV) {
327 // If we see two retains in a row on the same pointer. If so, make
328 // a note, and we'll cicle back to revisit it after we've
329 // hopefully eliminated the second retain, which may allow us to
330 // eliminate the first retain too.
331 // Theoretically we could implement removal of nested retain+release
332 // pairs by making PtrState hold a stack of states, but this is
333 // simple and avoids adding overhead for the non-nested case.
334 if (GetSeq() == S_Retain)
335 NestingDetected = true;
336
337 ResetSequenceProgress(NewSeq: S_Retain);
338 SetKnownSafe(HasKnownPositiveRefCount());
339 InsertCall(I);
340 }
341
342 SetKnownPositiveRefCount();
343 return NestingDetected;
344}
345
346bool TopDownPtrState::MatchWithRelease(ARCMDKindCache &Cache,
347 Instruction *Release) {
348 ClearKnownPositiveRefCount();
349
350 Sequence OldSeq = GetSeq();
351
352 MDNode *ReleaseMetadata =
353 Release->getMetadata(KindID: Cache.get(ID: ARCMDKindID::ImpreciseRelease));
354
355 switch (OldSeq) {
356 case S_Retain:
357 case S_CanRelease:
358 if (OldSeq == S_Retain || ReleaseMetadata != nullptr)
359 ClearReverseInsertPts();
360 [[fallthrough]];
361 case S_Use:
362 SetReleaseMetadata(ReleaseMetadata);
363 SetTailCallRelease(cast<CallInst>(Val: Release)->isTailCall());
364 return true;
365 case S_None:
366 return false;
367 case S_Stop:
368 case S_MovableRelease:
369 llvm_unreachable("top-down pointer in bottom up state!");
370 }
371 llvm_unreachable("Sequence unknown enum value");
372}
373
374bool TopDownPtrState::HandlePotentialAlterRefCount(
375 Instruction *Inst, const Value *Ptr, ProvenanceAnalysis &PA,
376 ARCInstKind Class, const BundledRetainClaimRVs &BundledRVs) {
377 // Check for possible releases. Treat clang.arc.use as a releasing instruction
378 // to prevent sinking a retain past it.
379 if (!CanDecrementRefCount(Inst, Ptr, PA, Class) &&
380 Class != ARCInstKind::IntrinsicUser)
381 return false;
382
383 LLVM_DEBUG(dbgs() << " CanAlterRefCount: Seq: " << GetSeq() << "; "
384 << *Ptr << "\n");
385 ClearKnownPositiveRefCount();
386 switch (GetSeq()) {
387 case S_Retain:
388 SetSeq(S_CanRelease);
389 assert(!HasReverseInsertPts());
390 InsertReverseInsertPt(I: Inst);
391
392 // Don't insert anything between a call/invoke with operand bundle
393 // "clang.arc.attachedcall" and the retainRV/claimRV call that uses the call
394 // result.
395 if (BundledRVs.contains(I: Inst))
396 SetCFGHazardAfflicted(true);
397
398 // One call can't cause a transition from S_Retain to S_CanRelease
399 // and S_CanRelease to S_Use. If we've made the first transition,
400 // we're done.
401 return true;
402 case S_Use:
403 case S_CanRelease:
404 case S_None:
405 return false;
406 case S_Stop:
407 case S_MovableRelease:
408 llvm_unreachable("top-down pointer in release state!");
409 }
410 llvm_unreachable("covered switch is not covered!?");
411}
412
413void TopDownPtrState::HandlePotentialUse(Instruction *Inst, const Value *Ptr,
414 ProvenanceAnalysis &PA,
415 ARCInstKind Class) {
416 // Check for possible direct uses.
417 switch (GetSeq()) {
418 case S_CanRelease:
419 if (!CanUse(Inst, Ptr, PA, Class))
420 return;
421 LLVM_DEBUG(dbgs() << " CanUse: Seq: " << GetSeq() << "; "
422 << *Ptr << "\n");
423 SetSeq(S_Use);
424 return;
425 case S_Retain:
426 case S_Use:
427 case S_None:
428 return;
429 case S_Stop:
430 case S_MovableRelease:
431 llvm_unreachable("top-down pointer in release state!");
432 }
433}
434