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 if (InsertAfter != BB->end())
277 InsertAfter = skipDebugIntrinsics(It: InsertAfter);
278
279 InsertReverseInsertPt(I: &*InsertAfter);
280
281 // Don't insert anything between a call/invoke with operand bundle
282 // "clang.arc.attachedcall" and the retainRV/claimRV call that uses the call
283 // result.
284 if (auto *CB = dyn_cast<CallBase>(Val: 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: *Inst, Class)) {
297 if (CanUse(Inst: Call, Ptr, PA, Class: GetBasicARCInstKind(V: 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// TopDownPtrState
322//===----------------------------------------------------------------------===//
323
324bool TopDownPtrState::InitTopDown(ARCInstKind Kind, Instruction *I) {
325 bool NestingDetected = false;
326 // Don't do retain+release tracking for ARCInstKind::RetainRV, because
327 // it's
328 // 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, make
331 // a note, and we'll cicle back to revisit it after we've
332 // hopefully eliminated the second retain, which may allow us to
333 // eliminate the first retain too.
334 // Theoretically we could implement removal of nested retain+release
335 // pairs by making PtrState hold a stack of states, but this is
336 // simple and avoids adding overhead for the non-nested case.
337 if (GetSeq() == S_Retain)
338 NestingDetected = true;
339
340 ResetSequenceProgress(NewSeq: 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(KindID: Cache.get(ID: 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>(Val: 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 instruction
381 // 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(I: Inst);
394
395 // Don't insert anything between a call/invoke with operand bundle
396 // "clang.arc.attachedcall" and the retainRV/claimRV call that uses the call
397 // result.
398 if (BundledRVs.contains(I: Inst))
399 SetCFGHazardAfflicted(true);
400
401 // One call can't cause a transition from S_Retain to S_CanRelease
402 // 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