LLVM  8.0.0svn
PtrState.cpp
Go to the documentation of this file.
1 //===- PtrState.cpp -------------------------------------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "PtrState.h"
11 #include "DependencyAnalysis.h"
12 #include "ObjCARC.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"
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 
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_Release:
48  return OS << "S_Release";
49  case S_MovableRelease:
50  return OS << "S_MovableRelease";
51  case S_Stop:
52  return OS << "S_Stop";
53  }
54  llvm_unreachable("Unknown sequence type.");
55 }
56 
57 //===----------------------------------------------------------------------===//
58 // Sequence
59 //===----------------------------------------------------------------------===//
60 
61 static Sequence MergeSeqs(Sequence A, Sequence B, bool TopDown) {
62  // The easy cases.
63  if (A == B)
64  return A;
65  if (A == S_None || B == S_None)
66  return S_None;
67 
68  if (A > B)
69  std::swap(A, B);
70  if (TopDown) {
71  // Choose the side which is further along in the sequence.
72  if ((A == S_Retain || A == S_CanRelease) &&
73  (B == S_CanRelease || B == S_Use))
74  return B;
75  } else {
76  // Choose the side which is further along in the sequence.
77  if ((A == S_Use || A == S_CanRelease) &&
78  (B == S_Use || B == S_Release || B == S_Stop || B == S_MovableRelease))
79  return A;
80  // If both sides are releases, choose the more conservative one.
81  if (A == S_Stop && (B == S_Release || B == S_MovableRelease))
82  return A;
83  if (A == S_Release && B == S_MovableRelease)
84  return A;
85  }
86 
87  return S_None;
88 }
89 
90 //===----------------------------------------------------------------------===//
91 // RRInfo
92 //===----------------------------------------------------------------------===//
93 
94 void RRInfo::clear() {
95  KnownSafe = false;
96  IsTailCallRelease = false;
97  ReleaseMetadata = nullptr;
98  Calls.clear();
99  ReverseInsertPts.clear();
100  CFGHazardAfflicted = false;
101 }
102 
103 bool RRInfo::Merge(const RRInfo &Other) {
104  // Conservatively merge the ReleaseMetadata information.
105  if (ReleaseMetadata != Other.ReleaseMetadata)
106  ReleaseMetadata = nullptr;
107 
108  // Conservatively merge the boolean state.
109  KnownSafe &= Other.KnownSafe;
112 
113  // Merge the call sets.
114  Calls.insert(Other.Calls.begin(), Other.Calls.end());
115 
116  // Merge the insert point sets. If there are any differences,
117  // that makes this a partial merge.
118  bool Partial = ReverseInsertPts.size() != Other.ReverseInsertPts.size();
119  for (Instruction *Inst : Other.ReverseInsertPts)
120  Partial |= ReverseInsertPts.insert(Inst).second;
121  return Partial;
122 }
123 
124 //===----------------------------------------------------------------------===//
125 // PtrState
126 //===----------------------------------------------------------------------===//
127 
129  LLVM_DEBUG(dbgs() << " Setting Known Positive.\n");
130  KnownPositiveRefCount = true;
131 }
132 
134  LLVM_DEBUG(dbgs() << " Clearing Known Positive.\n");
135  KnownPositiveRefCount = false;
136 }
137 
139  LLVM_DEBUG(dbgs() << " Old: " << GetSeq() << "; New: " << NewSeq
140  << "\n");
141  Seq = NewSeq;
142 }
143 
145  LLVM_DEBUG(dbgs() << " Resetting sequence progress.\n");
146  SetSeq(NewSeq);
147  Partial = false;
148  RRI.clear();
149 }
150 
151 void PtrState::Merge(const PtrState &Other, bool TopDown) {
152  Seq = MergeSeqs(GetSeq(), Other.GetSeq(), TopDown);
153  KnownPositiveRefCount &= Other.KnownPositiveRefCount;
154 
155  // If we're not in a sequence (anymore), drop all associated state.
156  if (Seq == S_None) {
157  Partial = false;
158  RRI.clear();
159  } else if (Partial || Other.Partial) {
160  // If we're doing a merge on a path that's previously seen a partial
161  // merge, conservatively drop the sequence, to avoid doing partial
162  // RR elimination. If the branch predicates for the two merge differ,
163  // mixing them is unsafe.
164  ClearSequenceProgress();
165  } else {
166  // Otherwise merge the other PtrState's RRInfo into our RRInfo. At this
167  // point, we know that currently we are not partial. Stash whether or not
168  // the merge operation caused us to undergo a partial merging of reverse
169  // insertion points.
170  Partial = RRI.Merge(Other.RRI);
171  }
172 }
173 
174 //===----------------------------------------------------------------------===//
175 // BottomUpPtrState
176 //===----------------------------------------------------------------------===//
177 
179  // If we see two releases in a row on the same pointer. If so, make
180  // a note, and we'll cicle back to revisit it after we've
181  // hopefully eliminated the second release, which may allow us to
182  // eliminate the first release too.
183  // Theoretically we could implement removal of nested retain+release
184  // pairs by making PtrState hold a stack of states, but this is
185  // simple and avoids adding overhead for the non-nested case.
186  bool NestingDetected = false;
187  if (GetSeq() == S_Release || GetSeq() == S_MovableRelease) {
188  LLVM_DEBUG(
189  dbgs() << " Found nested releases (i.e. a release pair)\n");
190  NestingDetected = true;
191  }
192 
195  Sequence NewSeq = ReleaseMetadata ? S_MovableRelease : S_Release;
196  ResetSequenceProgress(NewSeq);
197  SetReleaseMetadata(ReleaseMetadata);
198  SetKnownSafe(HasKnownPositiveRefCount());
199  SetTailCallRelease(cast<CallInst>(I)->isTailCall());
200  InsertCall(I);
201  SetKnownPositiveRefCount();
202  return NestingDetected;
203 }
204 
206  SetKnownPositiveRefCount();
207 
208  Sequence OldSeq = GetSeq();
209  switch (OldSeq) {
210  case S_Stop:
211  case S_Release:
212  case S_MovableRelease:
213  case S_Use:
214  // If OldSeq is not S_Use or OldSeq is S_Use and we are tracking an
215  // imprecise release, clear our reverse insertion points.
216  if (OldSeq != S_Use || IsTrackingImpreciseReleases())
217  ClearReverseInsertPts();
219  case S_CanRelease:
220  return true;
221  case S_None:
222  return false;
223  case S_Retain:
224  llvm_unreachable("bottom-up pointer in retain state!");
225  }
226  llvm_unreachable("Sequence unknown enum value");
227 }
228 
230  const Value *Ptr,
231  ProvenanceAnalysis &PA,
232  ARCInstKind Class) {
233  Sequence S = GetSeq();
234 
235  // Check for possible releases.
236  if (!CanAlterRefCount(Inst, Ptr, PA, Class))
237  return false;
238 
239  LLVM_DEBUG(dbgs() << " CanAlterRefCount: Seq: " << S << "; "
240  << *Ptr << "\n");
241  switch (S) {
242  case S_Use:
243  SetSeq(S_CanRelease);
244  return true;
245  case S_CanRelease:
246  case S_Release:
247  case S_MovableRelease:
248  case S_Stop:
249  case S_None:
250  return false;
251  case S_Retain:
252  llvm_unreachable("bottom-up pointer in retain state!");
253  }
254  llvm_unreachable("Sequence unknown enum value");
255 }
256 
258  const Value *Ptr,
259  ProvenanceAnalysis &PA,
260  ARCInstKind Class) {
261  auto SetSeqAndInsertReverseInsertPt = [&](Sequence NewSeq){
262  assert(!HasReverseInsertPts());
263  SetSeq(NewSeq);
264  // If this is an invoke instruction, we're scanning it as part of
265  // one of its successor blocks, since we can't insert code after it
266  // in its own block, and we don't want to split critical edges.
267  BasicBlock::iterator InsertAfter;
268  if (isa<InvokeInst>(Inst)) {
269  const auto IP = BB->getFirstInsertionPt();
270  InsertAfter = IP == BB->end() ? std::prev(BB->end()) : IP;
271  if (isa<CatchSwitchInst>(InsertAfter))
272  // A catchswitch must be the only non-phi instruction in its basic
273  // block, so attempting to insert an instruction into such a block would
274  // produce invalid IR.
275  SetCFGHazardAfflicted(true);
276  } else {
277  InsertAfter = std::next(Inst->getIterator());
278  }
279  InsertReverseInsertPt(&*InsertAfter);
280  };
281 
282  // Check for possible direct uses.
283  switch (GetSeq()) {
284  case S_Release:
285  case S_MovableRelease:
286  if (CanUse(Inst, Ptr, PA, Class)) {
287  LLVM_DEBUG(dbgs() << " CanUse: Seq: " << GetSeq() << "; "
288  << *Ptr << "\n");
289  SetSeqAndInsertReverseInsertPt(S_Use);
290  } else if (Seq == S_Release && IsUser(Class)) {
291  LLVM_DEBUG(dbgs() << " PreciseReleaseUse: Seq: " << GetSeq()
292  << "; " << *Ptr << "\n");
293  // Non-movable releases depend on any possible objc pointer use.
294  SetSeqAndInsertReverseInsertPt(S_Stop);
295  } else if (const auto *Call = getreturnRVOperand(*Inst, Class)) {
296  if (CanUse(Call, Ptr, PA, GetBasicARCInstKind(Call))) {
297  LLVM_DEBUG(dbgs() << " ReleaseUse: Seq: " << GetSeq() << "; "
298  << *Ptr << "\n");
299  SetSeqAndInsertReverseInsertPt(S_Stop);
300  }
301  }
302  break;
303  case S_Stop:
304  if (CanUse(Inst, Ptr, PA, Class)) {
305  LLVM_DEBUG(dbgs() << " PreciseStopUse: Seq: " << GetSeq()
306  << "; " << *Ptr << "\n");
307  SetSeq(S_Use);
308  }
309  break;
310  case S_CanRelease:
311  case S_Use:
312  case S_None:
313  break;
314  case S_Retain:
315  llvm_unreachable("bottom-up pointer in retain state!");
316  }
317 }
318 
319 //===----------------------------------------------------------------------===//
320 // TopDownPtrState
321 //===----------------------------------------------------------------------===//
322 
324  bool NestingDetected = false;
325  // Don't do retain+release tracking for ARCInstKind::RetainRV, because
326  // it's
327  // better to let it remain as the first instruction after a call.
328  if (Kind != ARCInstKind::RetainRV) {
329  // If we see two retains in a row on the same pointer. If so, make
330  // a note, and we'll cicle back to revisit it after we've
331  // hopefully eliminated the second retain, which may allow us to
332  // eliminate the first retain too.
333  // Theoretically we could implement removal of nested retain+release
334  // pairs by making PtrState hold a stack of states, but this is
335  // simple and avoids adding overhead for the non-nested case.
336  if (GetSeq() == S_Retain)
337  NestingDetected = true;
338 
339  ResetSequenceProgress(S_Retain);
340  SetKnownSafe(HasKnownPositiveRefCount());
341  InsertCall(I);
342  }
343 
344  SetKnownPositiveRefCount();
345  return NestingDetected;
346 }
347 
349  Instruction *Release) {
350  ClearKnownPositiveRefCount();
351 
352  Sequence OldSeq = GetSeq();
353 
356 
357  switch (OldSeq) {
358  case S_Retain:
359  case S_CanRelease:
360  if (OldSeq == S_Retain || ReleaseMetadata != nullptr)
361  ClearReverseInsertPts();
363  case S_Use:
364  SetReleaseMetadata(ReleaseMetadata);
365  SetTailCallRelease(cast<CallInst>(Release)->isTailCall());
366  return true;
367  case S_None:
368  return false;
369  case S_Stop:
370  case S_Release:
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  const Value *Ptr,
379  ProvenanceAnalysis &PA,
380  ARCInstKind Class) {
381  // Check for possible releases. Treat clang.arc.use as a releasing instruction
382  // to prevent sinking a retain past it.
383  if (!CanAlterRefCount(Inst, Ptr, PA, Class) &&
385  return false;
386 
387  LLVM_DEBUG(dbgs() << " CanAlterRefCount: Seq: " << GetSeq() << "; "
388  << *Ptr << "\n");
389  ClearKnownPositiveRefCount();
390  switch (GetSeq()) {
391  case S_Retain:
392  SetSeq(S_CanRelease);
393  assert(!HasReverseInsertPts());
394  InsertReverseInsertPt(Inst);
395 
396  // One call can't cause a transition from S_Retain to S_CanRelease
397  // and S_CanRelease to S_Use. If we've made the first transition,
398  // we're done.
399  return true;
400  case S_Use:
401  case S_CanRelease:
402  case S_None:
403  return false;
404  case S_Stop:
405  case S_Release:
406  case S_MovableRelease:
407  llvm_unreachable("top-down pointer in release state!");
408  }
409  llvm_unreachable("covered switch is not covered!?");
410 }
411 
413  ProvenanceAnalysis &PA,
414  ARCInstKind Class) {
415  // Check for possible direct uses.
416  switch (GetSeq()) {
417  case S_CanRelease:
418  if (!CanUse(Inst, Ptr, PA, Class))
419  return;
420  LLVM_DEBUG(dbgs() << " CanUse: Seq: " << GetSeq() << "; "
421  << *Ptr << "\n");
422  SetSeq(S_Use);
423  return;
424  case S_Retain:
425  case S_Use:
426  case S_None:
427  return;
428  case S_Stop:
429  case S_Release:
430  case S_MovableRelease:
431  llvm_unreachable("top-down pointer in release state!");
432  }
433 }
bool Merge(const RRInfo &Other)
Conservatively merge the two RRInfo.
Definition: PtrState.cpp:103
Sequence GetSeq() const
Definition: PtrState.h:151
This file declares special dependency analysis routines used in Objective C ARC Optimizations.
bool IsUser(ARCInstKind Class)
Test if the given class is a kind of user.
SmallPtrSet< Instruction *, 2 > Calls
For a top-down sequence, the set of objc_retains or objc_retainBlocks.
Definition: PtrState.h:81
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
#define LLVM_FALLTHROUGH
Definition: Compiler.h:86
bool CanUse(const Instruction *Inst, const Value *Ptr, ProvenanceAnalysis &PA, ARCInstKind Class)
Test whether the given instruction can "use" the given pointer&#39;s object in a way that requires the re...
bool HandlePotentialAlterRefCount(Instruction *Inst, const Value *Ptr, ProvenanceAnalysis &PA, ARCInstKind Class)
Definition: PtrState.cpp:229
any use of x.
Definition: PtrState.h:45
bool MatchWithRelease(ARCMDKindCache &Cache, Instruction *Release)
Return true if this set of retains can be paired with the given release.
Definition: PtrState.cpp:348
Metadata node.
Definition: Metadata.h:864
could call objc_release
SmallPtrSet< Instruction *, 2 > ReverseInsertPts
The set of optimal insert positions for moving calls in the opposite sequence.
Definition: PtrState.h:85
This class summarizes several per-pointer runtime properties which are propagated through the flow gr...
Definition: PtrState.h:102
unsigned get(ARCMDKindID ID)
This file defines common definitions/declarations used by the ObjC ARC Optimizer. ...
bool IsTailCallRelease
True of the objc_release calls are all marked with the "tail" keyword.
Definition: PtrState.h:73
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:178
objc_retainAutoreleasedReturnValue
void ClearKnownPositiveRefCount()
Definition: PtrState.cpp:133
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:217
void HandlePotentialUse(BasicBlock *BB, Instruction *Inst, const Value *Ptr, ProvenanceAnalysis &PA, ARCInstKind Class)
Definition: PtrState.cpp:257
Unidirectional information about either a retain-decrement-use-release sequence or release-use-decrem...
Definition: PtrState.h:57
raw_ostream & operator<<(raw_ostream &OS, const ARCInstKind Class)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
void HandlePotentialUse(Instruction *Inst, const Value *Ptr, ProvenanceAnalysis &PA, ARCInstKind Class)
Definition: PtrState.cpp:412
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:218
RRInfo RRI
Unidirectional information about the current sequence.
Definition: PtrState.h:115
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
bool KnownPositiveRefCount
True if the reference count is known to be incremented.
Definition: PtrState.h:105
void Merge(const PtrState &Other, bool TopDown)
Definition: PtrState.cpp:151
like S_Release, but code motion is stopped.
Definition: PtrState.h:46
self_iterator getIterator()
Definition: ilist_node.h:82
A cache of MDKinds used by various ARC optimizations.
bool MatchWithRetain()
Return true if this set of releases can be paired with a release.
Definition: PtrState.cpp:205
This file defines common analysis utilities used by the ObjC ARC Optimizer.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void ResetSequenceProgress(Sequence NewSeq)
Definition: PtrState.cpp:144
bool CFGHazardAfflicted
If this is true, we cannot perform code motion but can still remove retain/release pairs...
Definition: PtrState.h:89
ARCInstKind GetBasicARCInstKind(const Value *V)
Determine which objc runtime call instruction class V belongs to.
objc_release(x), !clang.imprecise_release.
Definition: PtrState.h:48
Iterator for intrusive lists based on ilist_node.
objc_release(x).
Definition: PtrState.h:47
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:74
bool Partial
True if we&#39;ve seen an opportunity for partial RR elimination, such as pushing calls into a CFG triang...
Definition: PtrState.h:109
iterator end()
Definition: BasicBlock.h:266
ARCInstKind
Equivalence classes of instructions in the ARC Model.
bool HandlePotentialAlterRefCount(Instruction *Inst, const Value *Ptr, ProvenanceAnalysis &PA, ARCInstKind Class)
Definition: PtrState.cpp:377
objc_retain(x).
Definition: PtrState.h:43
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:941
MDNode * ReleaseMetadata
If the Calls are objc_release calls and they all have a clang.imprecise_release tag, this is the metadata tag.
Definition: PtrState.h:77
static Sequence MergeSeqs(Sequence A, Sequence B, bool TopDown)
Definition: PtrState.cpp:61
#define I(x, y, z)
Definition: MD5.cpp:58
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
bool CanAlterRefCount(const Instruction *Inst, const Value *Ptr, ProvenanceAnalysis &PA, ARCInstKind Class)
Test whether the given instruction can result in a reference count modification (positive or negative...
void SetSeq(Sequence NewSeq)
Definition: PtrState.cpp:138
const unsigned Kind
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:73
foo(x) – x could possibly see a ref count decrement.
Definition: PtrState.h:44
bool KnownSafe
After an objc_retain, the reference count of the referenced object is known to be positive...
Definition: PtrState.h:70
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
This is similar to BasicAliasAnalysis, and it uses many of the same techniques, except it uses specia...
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:323
#define LLVM_DEBUG(X)
Definition: Debug.h:123