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 //===----------------------------------------------------------------------===//
10 #define DEBUG_TYPE "objc-arc-ptr-state"
11 #include "llvm/Support/Debug.h"
14 #include "DependencyAnalysis.h"
17 using namespace llvm::objcarc;
19 //===----------------------------------------------------------------------===//
21 //===----------------------------------------------------------------------===//
23 raw_ostream &llvm::objcarc::operator<<(raw_ostream &OS, const Sequence S) {
26 return OS << "S_None";
28 return OS << "S_Retain";
30 return OS << "S_CanRelease";
34 return OS << "S_Release";
35 case S_MovableRelease:
36 return OS << "S_MovableRelease";
38 return OS << "S_Stop";
40 llvm_unreachable("Unknown sequence type.");
43 //===----------------------------------------------------------------------===//
45 //===----------------------------------------------------------------------===//
47 static Sequence MergeSeqs(Sequence A, Sequence B, bool TopDown) {
51 if (A == S_None || B == S_None)
57 // Choose the side which is further along in the sequence.
58 if ((A == S_Retain || A == S_CanRelease) &&
59 (B == S_CanRelease || B == S_Use))
62 // Choose the side which is further along in the sequence.
63 if ((A == S_Use || A == S_CanRelease) &&
64 (B == S_Use || B == S_Release || B == S_Stop || B == S_MovableRelease))
66 // If both sides are releases, choose the more conservative one.
67 if (A == S_Stop && (B == S_Release || B == S_MovableRelease))
69 if (A == S_Release && B == S_MovableRelease)
76 //===----------------------------------------------------------------------===//
78 //===----------------------------------------------------------------------===//
80 void RRInfo::clear() {
82 IsTailCallRelease = false;
83 ReleaseMetadata = nullptr;
85 ReverseInsertPts.clear();
86 CFGHazardAfflicted = false;
89 bool RRInfo::Merge(const RRInfo &Other) {
90 // Conservatively merge the ReleaseMetadata information.
91 if (ReleaseMetadata != Other.ReleaseMetadata)
92 ReleaseMetadata = nullptr;
94 // Conservatively merge the boolean state.
95 KnownSafe &= Other.KnownSafe;
96 IsTailCallRelease &= Other.IsTailCallRelease;
97 CFGHazardAfflicted |= Other.CFGHazardAfflicted;
99 // Merge the call sets.
100 Calls.insert(Other.Calls.begin(), Other.Calls.end());
102 // Merge the insert point sets. If there are any differences,
103 // that makes this a partial merge.
104 bool Partial = ReverseInsertPts.size() != Other.ReverseInsertPts.size();
105 for (Instruction *Inst : Other.ReverseInsertPts)
106 Partial |= ReverseInsertPts.insert(Inst).second;
110 //===----------------------------------------------------------------------===//
112 //===----------------------------------------------------------------------===//
114 void PtrState::SetKnownPositiveRefCount() {
115 DEBUG(dbgs() << " Setting Known Positive.\n");
116 KnownPositiveRefCount = true;
119 void PtrState::ClearKnownPositiveRefCount() {
120 DEBUG(dbgs() << " Clearing Known Positive.\n");
121 KnownPositiveRefCount = false;
124 void PtrState::SetSeq(Sequence NewSeq) {
125 DEBUG(dbgs() << " Old: " << GetSeq() << "; New: " << NewSeq << "\n");
129 void PtrState::ResetSequenceProgress(Sequence NewSeq) {
130 DEBUG(dbgs() << " Resetting sequence progress.\n");
136 void PtrState::Merge(const PtrState &Other, bool TopDown) {
137 Seq = MergeSeqs(GetSeq(), Other.GetSeq(), TopDown);
138 KnownPositiveRefCount &= Other.KnownPositiveRefCount;
140 // If we're not in a sequence (anymore), drop all associated state.
144 } else if (Partial || Other.Partial) {
145 // If we're doing a merge on a path that's previously seen a partial
146 // merge, conservatively drop the sequence, to avoid doing partial
147 // RR elimination. If the branch predicates for the two merge differ,
148 // mixing them is unsafe.
149 ClearSequenceProgress();
151 // Otherwise merge the other PtrState's RRInfo into our RRInfo. At this
152 // point, we know that currently we are not partial. Stash whether or not
153 // the merge operation caused us to undergo a partial merging of reverse
155 Partial = RRI.Merge(Other.RRI);
159 //===----------------------------------------------------------------------===//
161 //===----------------------------------------------------------------------===//
163 bool BottomUpPtrState::InitBottomUp(ARCMDKindCache &Cache, Instruction *I) {
164 // If we see two releases in a row on the same pointer. If so, make
165 // a note, and we'll cicle back to revisit it after we've
166 // hopefully eliminated the second release, which may allow us to
167 // eliminate the first release too.
168 // Theoretically we could implement removal of nested retain+release
169 // pairs by making PtrState hold a stack of states, but this is
170 // simple and avoids adding overhead for the non-nested case.
171 bool NestingDetected = false;
172 if (GetSeq() == S_Release || GetSeq() == S_MovableRelease) {
173 DEBUG(dbgs() << " Found nested releases (i.e. a release pair)\n");
174 NestingDetected = true;
177 MDNode *ReleaseMetadata =
178 I->getMetadata(Cache.get(ARCMDKindID::ImpreciseRelease));
179 Sequence NewSeq = ReleaseMetadata ? S_MovableRelease : S_Release;
180 ResetSequenceProgress(NewSeq);
181 SetReleaseMetadata(ReleaseMetadata);
182 SetKnownSafe(HasKnownPositiveRefCount());
183 SetTailCallRelease(cast<CallInst>(I)->isTailCall());
185 SetKnownPositiveRefCount();
186 return NestingDetected;
189 bool BottomUpPtrState::MatchWithRetain() {
190 SetKnownPositiveRefCount();
192 Sequence OldSeq = GetSeq();
196 case S_MovableRelease:
198 // If OldSeq is not S_Use or OldSeq is S_Use and we are tracking an
199 // imprecise release, clear our reverse insertion points.
200 if (OldSeq != S_Use || IsTrackingImpreciseReleases())
201 ClearReverseInsertPts();
208 llvm_unreachable("bottom-up pointer in retain state!");
210 llvm_unreachable("Sequence unknown enum value");
213 bool BottomUpPtrState::HandlePotentialAlterRefCount(Instruction *Inst,
215 ProvenanceAnalysis &PA,
217 Sequence S = GetSeq();
219 // Check for possible releases.
220 if (!CanAlterRefCount(Inst, Ptr, PA, Class))
223 DEBUG(dbgs() << " CanAlterRefCount: Seq: " << S << "; " << *Ptr
227 SetSeq(S_CanRelease);
231 case S_MovableRelease:
236 llvm_unreachable("bottom-up pointer in retain state!");
238 llvm_unreachable("Sequence unknown enum value");
241 void BottomUpPtrState::HandlePotentialUse(BasicBlock *BB, Instruction *Inst,
243 ProvenanceAnalysis &PA,
245 // Check for possible direct uses.
248 case S_MovableRelease:
249 if (CanUse(Inst, Ptr, PA, Class)) {
250 DEBUG(dbgs() << " CanUse: Seq: " << GetSeq() << "; " << *Ptr
252 assert(!HasReverseInsertPts());
253 // If this is an invoke instruction, we're scanning it as part of
254 // one of its successor blocks, since we can't insert code after it
255 // in its own block, and we don't want to split critical edges.
256 if (isa<InvokeInst>(Inst))
257 InsertReverseInsertPt(BB->getFirstInsertionPt());
259 InsertReverseInsertPt(std::next(BasicBlock::iterator(Inst)));
261 } else if (Seq == S_Release && IsUser(Class)) {
262 DEBUG(dbgs() << " PreciseReleaseUse: Seq: " << GetSeq() << "; "
264 // Non-movable releases depend on any possible objc pointer use.
266 assert(!HasReverseInsertPts());
267 // As above; handle invoke specially.
268 if (isa<InvokeInst>(Inst))
269 InsertReverseInsertPt(BB->getFirstInsertionPt());
271 InsertReverseInsertPt(std::next(BasicBlock::iterator(Inst)));
275 if (CanUse(Inst, Ptr, PA, Class)) {
276 DEBUG(dbgs() << " PreciseStopUse: Seq: " << GetSeq() << "; "
286 llvm_unreachable("bottom-up pointer in retain state!");
290 //===----------------------------------------------------------------------===//
292 //===----------------------------------------------------------------------===//
294 bool TopDownPtrState::InitTopDown(ARCInstKind Kind, Instruction *I) {
295 bool NestingDetected = false;
296 // Don't do retain+release tracking for ARCInstKind::RetainRV, because
298 // better to let it remain as the first instruction after a call.
299 if (Kind != ARCInstKind::RetainRV) {
300 // If we see two retains in a row on the same pointer. If so, make
301 // a note, and we'll cicle back to revisit it after we've
302 // hopefully eliminated the second retain, which may allow us to
303 // eliminate the first retain too.
304 // Theoretically we could implement removal of nested retain+release
305 // pairs by making PtrState hold a stack of states, but this is
306 // simple and avoids adding overhead for the non-nested case.
307 if (GetSeq() == S_Retain)
308 NestingDetected = true;
310 ResetSequenceProgress(S_Retain);
311 SetKnownSafe(HasKnownPositiveRefCount());
315 SetKnownPositiveRefCount();
316 return NestingDetected;
319 bool TopDownPtrState::MatchWithRelease(ARCMDKindCache &Cache,
320 Instruction *Release) {
321 ClearKnownPositiveRefCount();
323 Sequence OldSeq = GetSeq();
325 MDNode *ReleaseMetadata =
326 Release->getMetadata(Cache.get(ARCMDKindID::ImpreciseRelease));
331 if (OldSeq == S_Retain || ReleaseMetadata != nullptr)
332 ClearReverseInsertPts();
335 SetReleaseMetadata(ReleaseMetadata);
336 SetTailCallRelease(cast<CallInst>(Release)->isTailCall());
342 case S_MovableRelease:
343 llvm_unreachable("top-down pointer in bottom up state!");
345 llvm_unreachable("Sequence unknown enum value");
348 bool TopDownPtrState::HandlePotentialAlterRefCount(Instruction *Inst,
350 ProvenanceAnalysis &PA,
352 // Check for possible releases.
353 if (!CanAlterRefCount(Inst, Ptr, PA, Class))
356 DEBUG(dbgs() << " CanAlterRefCount: Seq: " << GetSeq() << "; " << *Ptr
358 ClearKnownPositiveRefCount();
361 SetSeq(S_CanRelease);
362 assert(!HasReverseInsertPts());
363 InsertReverseInsertPt(Inst);
365 // One call can't cause a transition from S_Retain to S_CanRelease
366 // and S_CanRelease to S_Use. If we've made the first transition,
375 case S_MovableRelease:
376 llvm_unreachable("top-down pointer in release state!");
378 llvm_unreachable("covered switch is not covered!?");
381 void TopDownPtrState::HandlePotentialUse(Instruction *Inst, const Value *Ptr,
382 ProvenanceAnalysis &PA,
384 // Check for possible direct uses.
387 if (!CanUse(Inst, Ptr, PA, Class))
389 DEBUG(dbgs() << " CanUse: Seq: " << GetSeq() << "; " << *Ptr
399 case S_MovableRelease:
400 llvm_unreachable("top-down pointer in release state!");