LLVM 17.0.0git
PtrState.cpp
Go to the documentation of this file.
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"
15#include "llvm/IR/BasicBlock.h"
16#include "llvm/IR/Instruction.h"
18#include "llvm/IR/Value.h"
21#include "llvm/Support/Debug.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
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";
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, 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
91 KnownSafe = false;
92 IsTailCallRelease = false;
93 ReleaseMetadata = nullptr;
94 Calls.clear();
95 ReverseInsertPts.clear();
96 CFGHazardAfflicted = false;
97}
98
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(Other.Calls.begin(), Other.Calls.end());
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// PtrState
122//===----------------------------------------------------------------------===//
123
125 LLVM_DEBUG(dbgs() << " Setting Known Positive.\n");
127}
128
130 LLVM_DEBUG(dbgs() << " Clearing Known Positive.\n");
131 KnownPositiveRefCount = false;
132}
133
135 LLVM_DEBUG(dbgs() << " Old: " << GetSeq() << "; New: " << NewSeq
136 << "\n");
137 Seq = NewSeq;
138}
139
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 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.
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.RRI);
167 }
168}
169
170//===----------------------------------------------------------------------===//
171// BottomUpPtrState
172//===----------------------------------------------------------------------===//
173
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) {
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)
195 SetReleaseMetadata(ReleaseMetadata);
197 SetTailCallRelease(cast<CallInst>(I)->isTailCall());
198 InsertCall(I);
200 return NestingDetected;
201}
202
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())
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
227 const Value *Ptr,
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:
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
254 const Value *Ptr,
256 ARCInstKind Class) {
257 auto SetSeqAndInsertReverseInsertPt = [&](Sequence NewSeq){
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>(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 basic
269 // block, so attempting to insert an instruction into such a block would
270 // produce invalid IR.
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 bundle
282 // "clang.arc.attachedcall" and the retainRV/claimRV call that uses the call
283 // result.
284 if (auto *CB = dyn_cast<CallBase>(Inst))
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// TopDownPtrState
322//===----------------------------------------------------------------------===//
323
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
342 InsertCall(I);
343 }
344
346 return NestingDetected;
347}
348
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)
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
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) &&
384 return false;
385
386 LLVM_DEBUG(dbgs() << " CanAlterRefCount: Seq: " << GetSeq() << "; "
387 << *Ptr << "\n");
389 switch (GetSeq()) {
390 case S_Retain:
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(Inst))
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
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}
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file declares special dependency analysis routines used in Objective C ARC Optimizations.
#define I(x, y, z)
Definition: MD5.cpp:58
This file defines common analysis utilities used by the ObjC ARC Optimizer.
This file defines ARC utility functions which are used by various parts of the compiler.
static Sequence MergeSeqs(Sequence A, Sequence B, bool TopDown)
Definition: PtrState.cpp:59
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
iterator end()
Definition: BasicBlock.h:316
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
Definition: BasicBlock.cpp:245
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
Metadata node.
Definition: Metadata.h:943
LLVM Value Representation.
Definition: Value.h:74
self_iterator getIterator()
Definition: ilist_node.h:82
A cache of MDKinds used by various ARC optimizations.
unsigned get(ARCMDKindID ID)
bool contains(const Instruction *I) const
See if an instruction is a bundled retainRV/claimRV call.
Definition: ObjCARC.h:124
This is similar to BasicAliasAnalysis, and it uses many of the same techniques, except it uses specia...
This class summarizes several per-pointer runtime properties which are propagated through the flow gr...
Definition: PtrState.h:101
bool KnownPositiveRefCount
True if the reference count is known to be incremented.
Definition: PtrState.h:104
unsigned char Seq
The current position in the sequence.
Definition: PtrState.h:111
void SetCFGHazardAfflicted(const bool NewValue)
Definition: PtrState.h:139
Sequence GetSeq() const
Definition: PtrState.h:150
RRInfo RRI
Unidirectional information about the current sequence.
Definition: PtrState.h:114
void ClearReverseInsertPts()
Definition: PtrState.h:161
bool HasKnownPositiveRefCount() const
Definition: PtrState.h:146
void InsertReverseInsertPt(Instruction *I)
Definition: PtrState.h:159
bool HasReverseInsertPts() const
Definition: PtrState.h:163
void SetTailCallRelease(const bool NewValue)
Definition: PtrState.h:125
void ClearKnownPositiveRefCount()
Definition: PtrState.cpp:129
void SetReleaseMetadata(MDNode *NewValue)
Definition: PtrState.h:135
void InsertCall(Instruction *I)
Definition: PtrState.h:157
void ResetSequenceProgress(Sequence NewSeq)
Definition: PtrState.cpp:140
void SetSeq(Sequence NewSeq)
Definition: PtrState.cpp:134
void SetKnownSafe(const bool NewValue)
Definition: PtrState.h:121
void Merge(const PtrState &Other, bool TopDown)
Definition: PtrState.cpp:147
void ClearSequenceProgress()
Definition: PtrState.h:152
bool Partial
True if we've seen an opportunity for partial RR elimination, such as pushing calls into a CFG triang...
Definition: PtrState.h:108
bool IsTrackingImpreciseReleases() const
Definition: PtrState.h:129
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
This file defines common definitions/declarations used by the ObjC ARC Optimizer.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
static const Instruction * getreturnRVOperand(const Instruction &Inst, ARCInstKind Class)
If Inst is a ReturnRV and its operand is a call or invoke, return the operand.
Definition: ObjCARC.h:61
raw_ostream & operator<<(raw_ostream &OS, const ARCInstKind Class)
ARCInstKind
Equivalence classes of instructions in the ARC Model.
@ RetainRV
objc_retainAutoreleasedReturnValue
@ Call
could call objc_release
@ IntrinsicUser
llvm.objc.clang.arc.use
Sequence
A sequence of states that a pointer may go through in which an objc_retain and objc_release are actua...
Definition: PtrState.h:41
@ S_CanRelease
foo(x) – x could possibly see a ref count decrement.
Definition: PtrState.h:44
@ S_Use
any use of x.
Definition: PtrState.h:45
@ S_Retain
objc_retain(x).
Definition: PtrState.h:43
@ S_Stop
code motion is stopped.
Definition: PtrState.h:46
@ S_MovableRelease
objc_release(x), !clang.imprecise_release.
Definition: PtrState.h:47
ARCInstKind GetBasicARCInstKind(const Value *V)
Determine which objc runtime call instruction class V belongs to.
bool CanDecrementRefCount(ARCInstKind Kind)
Returns false if conservatively we can prove that any instruction mapped to this kind can not decreme...
bool hasAttachedCallOpBundle(const CallBase *CB)
Definition: ObjCARCUtil.h:29
bool CanUse(const Instruction *Inst, const Value *Ptr, ProvenanceAnalysis &PA, ARCInstKind Class)
Test whether the given instruction can "use" the given pointer's object in a way that requires the re...
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
BasicBlock::iterator skipDebugIntrinsics(BasicBlock::iterator It)
Advance It while it points to a debug instruction and return the result.
Definition: BasicBlock.cpp:534
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
bool HandlePotentialAlterRefCount(Instruction *Inst, const Value *Ptr, ProvenanceAnalysis &PA, ARCInstKind Class)
Definition: PtrState.cpp:226
bool InitBottomUp(ARCMDKindCache &Cache, Instruction *I)
(Re-)Initialize this bottom up pointer returning true if we detected a pointer with nested releases.
Definition: PtrState.cpp:174
bool MatchWithRetain()
Return true if this set of releases can be paired with a release.
Definition: PtrState.cpp:203
void HandlePotentialUse(BasicBlock *BB, Instruction *Inst, const Value *Ptr, ProvenanceAnalysis &PA, ARCInstKind Class)
Definition: PtrState.cpp:253
Unidirectional information about either a retain-decrement-use-release sequence or release-use-decrem...
Definition: PtrState.h:56
bool Merge(const RRInfo &Other)
Conservatively merge the two RRInfo.
Definition: PtrState.cpp:99
bool KnownSafe
After an objc_retain, the reference count of the referenced object is known to be positive.
Definition: PtrState.h:69
SmallPtrSet< Instruction *, 2 > Calls
For a top-down sequence, the set of objc_retains or objc_retainBlocks.
Definition: PtrState.h:80
MDNode * ReleaseMetadata
If the Calls are objc_release calls and they all have a clang.imprecise_release tag,...
Definition: PtrState.h:76
bool CFGHazardAfflicted
If this is true, we cannot perform code motion but can still remove retain/release pairs.
Definition: PtrState.h:88
bool IsTailCallRelease
True of the objc_release calls are all marked with the "tail" keyword.
Definition: PtrState.h:72
SmallPtrSet< Instruction *, 2 > ReverseInsertPts
The set of optimal insert positions for moving calls in the opposite sequence.
Definition: PtrState.h:84
bool MatchWithRelease(ARCMDKindCache &Cache, Instruction *Release)
Return true if this set of retains can be paired with the given release.
Definition: PtrState.cpp:349
bool InitTopDown(ARCInstKind Kind, Instruction *I)
(Re-)Initialize this bottom up pointer returning true if we detected a pointer with nested releases.
Definition: PtrState.cpp:324
bool HandlePotentialAlterRefCount(Instruction *Inst, const Value *Ptr, ProvenanceAnalysis &PA, ARCInstKind Class, const BundledRetainClaimRVs &BundledRVs)
Definition: PtrState.cpp:377
void HandlePotentialUse(Instruction *Inst, const Value *Ptr, ProvenanceAnalysis &PA, ARCInstKind Class)
Definition: PtrState.cpp:416