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
28 using namespace llvm;
29 using namespace llvm::objcarc;
30
31 #define DEBUG_TYPE "objc-arc-ptr-state"
32
33 //===----------------------------------------------------------------------===//
34 // Utility
35 //===----------------------------------------------------------------------===//
36
operator <<(raw_ostream & OS,const Sequence S)37 raw_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
MergeSeqs(Sequence A,Sequence B,bool TopDown)59 static 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
clear()90 void RRInfo::clear() {
91 KnownSafe = false;
92 IsTailCallRelease = false;
93 ReleaseMetadata = nullptr;
94 Calls.clear();
95 ReverseInsertPts.clear();
96 CFGHazardAfflicted = false;
97 }
98
Merge(const RRInfo & Other)99 bool 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(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
SetKnownPositiveRefCount()124 void PtrState::SetKnownPositiveRefCount() {
125 LLVM_DEBUG(dbgs() << " Setting Known Positive.\n");
126 KnownPositiveRefCount = true;
127 }
128
ClearKnownPositiveRefCount()129 void PtrState::ClearKnownPositiveRefCount() {
130 LLVM_DEBUG(dbgs() << " Clearing Known Positive.\n");
131 KnownPositiveRefCount = false;
132 }
133
SetSeq(Sequence NewSeq)134 void PtrState::SetSeq(Sequence NewSeq) {
135 LLVM_DEBUG(dbgs() << " Old: " << GetSeq() << "; New: " << NewSeq
136 << "\n");
137 Seq = NewSeq;
138 }
139
ResetSequenceProgress(Sequence NewSeq)140 void PtrState::ResetSequenceProgress(Sequence NewSeq) {
141 LLVM_DEBUG(dbgs() << " Resetting sequence progress.\n");
142 SetSeq(NewSeq);
143 Partial = false;
144 RRI.clear();
145 }
146
Merge(const PtrState & Other,bool TopDown)147 void 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.
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.RRI);
167 }
168 }
169
170 //===----------------------------------------------------------------------===//
171 // BottomUpPtrState
172 //===----------------------------------------------------------------------===//
173
InitBottomUp(ARCMDKindCache & Cache,Instruction * I)174 bool 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(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
MatchWithRetain()203 bool 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
HandlePotentialAlterRefCount(Instruction * Inst,const Value * Ptr,ProvenanceAnalysis & PA,ARCInstKind Class)226 bool 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
HandlePotentialUse(BasicBlock * BB,Instruction * Inst,const Value * Ptr,ProvenanceAnalysis & PA,ARCInstKind Class)253 void 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>(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.
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 bundle
282 // "clang.arc.attachedcall" and the retainRV/claimRV call that uses the call
283 // 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 // TopDownPtrState
322 //===----------------------------------------------------------------------===//
323
InitTopDown(ARCInstKind Kind,Instruction * I)324 bool 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(S_Retain);
341 SetKnownSafe(HasKnownPositiveRefCount());
342 InsertCall(I);
343 }
344
345 SetKnownPositiveRefCount();
346 return NestingDetected;
347 }
348
MatchWithRelease(ARCMDKindCache & Cache,Instruction * Release)349 bool 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
HandlePotentialAlterRefCount(Instruction * Inst,const Value * Ptr,ProvenanceAnalysis & PA,ARCInstKind Class,const BundledRetainClaimRVs & BundledRVs)377 bool 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(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(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
HandlePotentialUse(Instruction * Inst,const Value * Ptr,ProvenanceAnalysis & PA,ARCInstKind Class)416 void 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