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: " << Seq << "; 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 Seq = GetSeq();
219 // Check for possible releases.
220 if (!CanAlterRefCount(Inst, Ptr, PA, Class))
223 DEBUG(dbgs() << "CanAlterRefCount: Seq: " << Seq << "; " << *Ptr << "\n");
226 SetSeq(S_CanRelease);
230 case S_MovableRelease:
235 llvm_unreachable("bottom-up pointer in retain state!");
237 llvm_unreachable("Sequence unknown enum value");
240 void BottomUpPtrState::HandlePotentialUse(BasicBlock *BB, Instruction *Inst,
242 ProvenanceAnalysis &PA,
244 // Check for possible direct uses.
247 case S_MovableRelease:
248 if (CanUse(Inst, Ptr, PA, Class)) {
249 DEBUG(dbgs() << "CanUse: Seq: " << Seq << "; " << *Ptr << "\n");
250 assert(!HasReverseInsertPts());
251 // If this is an invoke instruction, we're scanning it as part of
252 // one of its successor blocks, since we can't insert code after it
253 // in its own block, and we don't want to split critical edges.
254 if (isa<InvokeInst>(Inst))
255 InsertReverseInsertPt(BB->getFirstInsertionPt());
257 InsertReverseInsertPt(std::next(BasicBlock::iterator(Inst)));
259 } else if (Seq == S_Release && IsUser(Class)) {
260 DEBUG(dbgs() << "PreciseReleaseUse: Seq: " << Seq << "; " << *Ptr
262 // Non-movable releases depend on any possible objc pointer use.
264 assert(!HasReverseInsertPts());
265 // As above; handle invoke specially.
266 if (isa<InvokeInst>(Inst))
267 InsertReverseInsertPt(BB->getFirstInsertionPt());
269 InsertReverseInsertPt(std::next(BasicBlock::iterator(Inst)));
273 if (CanUse(Inst, Ptr, PA, Class)) {
274 DEBUG(dbgs() << "PreciseStopUse: Seq: " << Seq << "; " << *Ptr << "\n");
283 llvm_unreachable("bottom-up pointer in retain state!");
287 //===----------------------------------------------------------------------===//
289 //===----------------------------------------------------------------------===//
291 bool TopDownPtrState::InitTopDown(ARCInstKind Kind, Instruction *I) {
292 bool NestingDetected = false;
293 // Don't do retain+release tracking for ARCInstKind::RetainRV, because
295 // better to let it remain as the first instruction after a call.
296 if (Kind != ARCInstKind::RetainRV) {
297 // If we see two retains in a row on the same pointer. If so, make
298 // a note, and we'll cicle back to revisit it after we've
299 // hopefully eliminated the second retain, which may allow us to
300 // eliminate the first retain too.
301 // Theoretically we could implement removal of nested retain+release
302 // pairs by making PtrState hold a stack of states, but this is
303 // simple and avoids adding overhead for the non-nested case.
304 if (GetSeq() == S_Retain)
305 NestingDetected = true;
307 ResetSequenceProgress(S_Retain);
308 SetKnownSafe(HasKnownPositiveRefCount());
312 SetKnownPositiveRefCount();
313 return NestingDetected;
316 bool TopDownPtrState::MatchWithRelease(ARCMDKindCache &Cache,
317 Instruction *Release) {
318 ClearKnownPositiveRefCount();
320 Sequence OldSeq = GetSeq();
322 MDNode *ReleaseMetadata =
323 Release->getMetadata(Cache.get(ARCMDKindID::ImpreciseRelease));
328 if (OldSeq == S_Retain || ReleaseMetadata != nullptr)
329 ClearReverseInsertPts();
332 SetReleaseMetadata(ReleaseMetadata);
333 SetTailCallRelease(cast<CallInst>(Release)->isTailCall());
339 case S_MovableRelease:
340 llvm_unreachable("top-down pointer in bottom up state!");
342 llvm_unreachable("Sequence unknown enum value");
345 bool TopDownPtrState::HandlePotentialAlterRefCount(Instruction *Inst,
347 ProvenanceAnalysis &PA,
349 // Check for possible releases.
350 if (!CanAlterRefCount(Inst, Ptr, PA, Class))
353 DEBUG(dbgs() << "CanAlterRefCount: Seq: " << Seq << "; " << *Ptr << "\n");
354 ClearKnownPositiveRefCount();
357 SetSeq(S_CanRelease);
358 assert(!HasReverseInsertPts());
359 InsertReverseInsertPt(Inst);
361 // One call can't cause a transition from S_Retain to S_CanRelease
362 // and S_CanRelease to S_Use. If we've made the first transition,
371 case S_MovableRelease:
372 llvm_unreachable("top-down pointer in release state!");
374 llvm_unreachable("covered switch is not covered!?");
377 void TopDownPtrState::HandlePotentialUse(Instruction *Inst, const Value *Ptr,
378 ProvenanceAnalysis &PA,
380 // Check for possible direct uses.
383 if (!CanUse(Inst, Ptr, PA, Class))
385 DEBUG(dbgs() << "CanUse: Seq: " << Seq << "; " << *Ptr << "\n");
394 case S_MovableRelease:
395 llvm_unreachable("top-down pointer in release state!");