1 //===--- PtrState.cpp -----------------------------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 #include "DependencyAnalysis.h"
13 #include "llvm/Support/Debug.h"
14 #include "llvm/Support/raw_ostream.h"
17 using namespace llvm::objcarc;
19 #define DEBUG_TYPE "objc-arc-ptr-state"
21 //===----------------------------------------------------------------------===//
23 //===----------------------------------------------------------------------===//
25 raw_ostream &llvm::objcarc::operator<<(raw_ostream &OS, const Sequence S) {
28 return OS << "S_None";
30 return OS << "S_Retain";
32 return OS << "S_CanRelease";
36 return OS << "S_Release";
37 case S_MovableRelease:
38 return OS << "S_MovableRelease";
40 return OS << "S_Stop";
42 llvm_unreachable("Unknown sequence type.");
45 //===----------------------------------------------------------------------===//
47 //===----------------------------------------------------------------------===//
49 static Sequence MergeSeqs(Sequence A, Sequence B, bool TopDown) {
53 if (A == S_None || B == S_None)
59 // Choose the side which is further along in the sequence.
60 if ((A == S_Retain || A == S_CanRelease) &&
61 (B == S_CanRelease || B == S_Use))
64 // Choose the side which is further along in the sequence.
65 if ((A == S_Use || A == S_CanRelease) &&
66 (B == S_Use || B == S_Release || B == S_Stop || B == S_MovableRelease))
68 // If both sides are releases, choose the more conservative one.
69 if (A == S_Stop && (B == S_Release || B == S_MovableRelease))
71 if (A == S_Release && B == S_MovableRelease)
78 //===----------------------------------------------------------------------===//
80 //===----------------------------------------------------------------------===//
82 void RRInfo::clear() {
84 IsTailCallRelease = false;
85 ReleaseMetadata = nullptr;
87 ReverseInsertPts.clear();
88 CFGHazardAfflicted = false;
91 bool RRInfo::Merge(const RRInfo &Other) {
92 // Conservatively merge the ReleaseMetadata information.
93 if (ReleaseMetadata != Other.ReleaseMetadata)
94 ReleaseMetadata = nullptr;
96 // Conservatively merge the boolean state.
97 KnownSafe &= Other.KnownSafe;
98 IsTailCallRelease &= Other.IsTailCallRelease;
99 CFGHazardAfflicted |= Other.CFGHazardAfflicted;
101 // Merge the call sets.
102 Calls.insert(Other.Calls.begin(), Other.Calls.end());
104 // Merge the insert point sets. If there are any differences,
105 // that makes this a partial merge.
106 bool Partial = ReverseInsertPts.size() != Other.ReverseInsertPts.size();
107 for (Instruction *Inst : Other.ReverseInsertPts)
108 Partial |= ReverseInsertPts.insert(Inst).second;
112 //===----------------------------------------------------------------------===//
114 //===----------------------------------------------------------------------===//
116 void PtrState::SetKnownPositiveRefCount() {
117 DEBUG(dbgs() << " Setting Known Positive.\n");
118 KnownPositiveRefCount = true;
121 void PtrState::ClearKnownPositiveRefCount() {
122 DEBUG(dbgs() << " Clearing Known Positive.\n");
123 KnownPositiveRefCount = false;
126 void PtrState::SetSeq(Sequence NewSeq) {
127 DEBUG(dbgs() << " Old: " << GetSeq() << "; New: " << NewSeq << "\n");
131 void PtrState::ResetSequenceProgress(Sequence NewSeq) {
132 DEBUG(dbgs() << " Resetting sequence progress.\n");
138 void PtrState::Merge(const PtrState &Other, bool TopDown) {
139 Seq = MergeSeqs(GetSeq(), Other.GetSeq(), TopDown);
140 KnownPositiveRefCount &= Other.KnownPositiveRefCount;
142 // If we're not in a sequence (anymore), drop all associated state.
146 } else if (Partial || Other.Partial) {
147 // If we're doing a merge on a path that's previously seen a partial
148 // merge, conservatively drop the sequence, to avoid doing partial
149 // RR elimination. If the branch predicates for the two merge differ,
150 // mixing them is unsafe.
151 ClearSequenceProgress();
153 // Otherwise merge the other PtrState's RRInfo into our RRInfo. At this
154 // point, we know that currently we are not partial. Stash whether or not
155 // the merge operation caused us to undergo a partial merging of reverse
157 Partial = RRI.Merge(Other.RRI);
161 //===----------------------------------------------------------------------===//
163 //===----------------------------------------------------------------------===//
165 bool BottomUpPtrState::InitBottomUp(ARCMDKindCache &Cache, Instruction *I) {
166 // If we see two releases in a row on the same pointer. If so, make
167 // a note, and we'll cicle back to revisit it after we've
168 // hopefully eliminated the second release, which may allow us to
169 // eliminate the first release too.
170 // Theoretically we could implement removal of nested retain+release
171 // pairs by making PtrState hold a stack of states, but this is
172 // simple and avoids adding overhead for the non-nested case.
173 bool NestingDetected = false;
174 if (GetSeq() == S_Release || GetSeq() == S_MovableRelease) {
175 DEBUG(dbgs() << " Found nested releases (i.e. a release pair)\n");
176 NestingDetected = true;
179 MDNode *ReleaseMetadata =
180 I->getMetadata(Cache.get(ARCMDKindID::ImpreciseRelease));
181 Sequence NewSeq = ReleaseMetadata ? S_MovableRelease : S_Release;
182 ResetSequenceProgress(NewSeq);
183 SetReleaseMetadata(ReleaseMetadata);
184 SetKnownSafe(HasKnownPositiveRefCount());
185 SetTailCallRelease(cast<CallInst>(I)->isTailCall());
187 SetKnownPositiveRefCount();
188 return NestingDetected;
191 bool BottomUpPtrState::MatchWithRetain() {
192 SetKnownPositiveRefCount();
194 Sequence OldSeq = GetSeq();
198 case S_MovableRelease:
200 // If OldSeq is not S_Use or OldSeq is S_Use and we are tracking an
201 // imprecise release, clear our reverse insertion points.
202 if (OldSeq != S_Use || IsTrackingImpreciseReleases())
203 ClearReverseInsertPts();
210 llvm_unreachable("bottom-up pointer in retain state!");
212 llvm_unreachable("Sequence unknown enum value");
215 bool BottomUpPtrState::HandlePotentialAlterRefCount(Instruction *Inst,
217 ProvenanceAnalysis &PA,
219 Sequence S = GetSeq();
221 // Check for possible releases.
222 if (!CanAlterRefCount(Inst, Ptr, PA, Class))
225 DEBUG(dbgs() << " CanAlterRefCount: Seq: " << S << "; " << *Ptr
229 SetSeq(S_CanRelease);
233 case S_MovableRelease:
238 llvm_unreachable("bottom-up pointer in retain state!");
240 llvm_unreachable("Sequence unknown enum value");
243 void BottomUpPtrState::HandlePotentialUse(BasicBlock *BB, Instruction *Inst,
245 ProvenanceAnalysis &PA,
247 // Check for possible direct uses.
250 case S_MovableRelease:
251 if (CanUse(Inst, Ptr, PA, Class)) {
252 DEBUG(dbgs() << " CanUse: Seq: " << GetSeq() << "; " << *Ptr
254 assert(!HasReverseInsertPts());
255 // If this is an invoke instruction, we're scanning it as part of
256 // one of its successor blocks, since we can't insert code after it
257 // in its own block, and we don't want to split critical edges.
258 if (isa<InvokeInst>(Inst))
259 InsertReverseInsertPt(&*BB->getFirstInsertionPt());
261 InsertReverseInsertPt(&*++Inst->getIterator());
263 } else if (Seq == S_Release && IsUser(Class)) {
264 DEBUG(dbgs() << " PreciseReleaseUse: Seq: " << GetSeq() << "; "
266 // Non-movable releases depend on any possible objc pointer use.
268 assert(!HasReverseInsertPts());
269 // As above; handle invoke specially.
270 if (isa<InvokeInst>(Inst))
271 InsertReverseInsertPt(&*BB->getFirstInsertionPt());
273 InsertReverseInsertPt(&*++Inst->getIterator());
277 if (CanUse(Inst, Ptr, PA, Class)) {
278 DEBUG(dbgs() << " PreciseStopUse: Seq: " << GetSeq() << "; "
288 llvm_unreachable("bottom-up pointer in retain state!");
292 //===----------------------------------------------------------------------===//
294 //===----------------------------------------------------------------------===//
296 bool TopDownPtrState::InitTopDown(ARCInstKind Kind, Instruction *I) {
297 bool NestingDetected = false;
298 // Don't do retain+release tracking for ARCInstKind::RetainRV, because
300 // better to let it remain as the first instruction after a call.
301 if (Kind != ARCInstKind::RetainRV) {
302 // If we see two retains in a row on the same pointer. If so, make
303 // a note, and we'll cicle back to revisit it after we've
304 // hopefully eliminated the second retain, which may allow us to
305 // eliminate the first retain too.
306 // Theoretically we could implement removal of nested retain+release
307 // pairs by making PtrState hold a stack of states, but this is
308 // simple and avoids adding overhead for the non-nested case.
309 if (GetSeq() == S_Retain)
310 NestingDetected = true;
312 ResetSequenceProgress(S_Retain);
313 SetKnownSafe(HasKnownPositiveRefCount());
317 SetKnownPositiveRefCount();
318 return NestingDetected;
321 bool TopDownPtrState::MatchWithRelease(ARCMDKindCache &Cache,
322 Instruction *Release) {
323 ClearKnownPositiveRefCount();
325 Sequence OldSeq = GetSeq();
327 MDNode *ReleaseMetadata =
328 Release->getMetadata(Cache.get(ARCMDKindID::ImpreciseRelease));
333 if (OldSeq == S_Retain || ReleaseMetadata != nullptr)
334 ClearReverseInsertPts();
337 SetReleaseMetadata(ReleaseMetadata);
338 SetTailCallRelease(cast<CallInst>(Release)->isTailCall());
344 case S_MovableRelease:
345 llvm_unreachable("top-down pointer in bottom up state!");
347 llvm_unreachable("Sequence unknown enum value");
350 bool TopDownPtrState::HandlePotentialAlterRefCount(Instruction *Inst,
352 ProvenanceAnalysis &PA,
354 // Check for possible releases. Treat clang.arc.use as a releasing instruction
355 // to prevent sinking a retain past it.
356 if (!CanAlterRefCount(Inst, Ptr, PA, Class) &&
357 Class != ARCInstKind::IntrinsicUser)
360 DEBUG(dbgs() << " CanAlterRefCount: Seq: " << GetSeq() << "; " << *Ptr
362 ClearKnownPositiveRefCount();
365 SetSeq(S_CanRelease);
366 assert(!HasReverseInsertPts());
367 InsertReverseInsertPt(Inst);
369 // One call can't cause a transition from S_Retain to S_CanRelease
370 // and S_CanRelease to S_Use. If we've made the first transition,
379 case S_MovableRelease:
380 llvm_unreachable("top-down pointer in release state!");
382 llvm_unreachable("covered switch is not covered!?");
385 void TopDownPtrState::HandlePotentialUse(Instruction *Inst, const Value *Ptr,
386 ProvenanceAnalysis &PA,
388 // Check for possible direct uses.
391 if (!CanUse(Inst, Ptr, PA, Class))
393 DEBUG(dbgs() << " CanUse: Seq: " << GetSeq() << "; " << *Ptr
403 case S_MovableRelease:
404 llvm_unreachable("top-down pointer in release state!");