LLVM  6.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  DEBUG(dbgs() << " Setting Known Positive.\n");
130  KnownPositiveRefCount = true;
131 }
132 
134  DEBUG(dbgs() << " Clearing Known Positive.\n");
135  KnownPositiveRefCount = false;
136 }
137 
139  DEBUG(dbgs() << " Old: " << GetSeq() << "; New: " << NewSeq << "\n");
140  Seq = NewSeq;
141 }
142 
144  DEBUG(dbgs() << " Resetting sequence progress.\n");
145  SetSeq(NewSeq);
146  Partial = false;
147  RRI.clear();
148 }
149 
150 void PtrState::Merge(const PtrState &Other, bool TopDown) {
151  Seq = MergeSeqs(GetSeq(), Other.GetSeq(), TopDown);
152  KnownPositiveRefCount &= Other.KnownPositiveRefCount;
153 
154  // If we're not in a sequence (anymore), drop all associated state.
155  if (Seq == S_None) {
156  Partial = false;
157  RRI.clear();
158  } else if (Partial || Other.Partial) {
159  // If we're doing a merge on a path that's previously seen a partial
160  // merge, conservatively drop the sequence, to avoid doing partial
161  // RR elimination. If the branch predicates for the two merge differ,
162  // mixing them is unsafe.
163  ClearSequenceProgress();
164  } else {
165  // Otherwise merge the other PtrState's RRInfo into our RRInfo. At this
166  // point, we know that currently we are not partial. Stash whether or not
167  // the merge operation caused us to undergo a partial merging of reverse
168  // insertion points.
169  Partial = RRI.Merge(Other.RRI);
170  }
171 }
172 
173 //===----------------------------------------------------------------------===//
174 // BottomUpPtrState
175 //===----------------------------------------------------------------------===//
176 
178  // If we see two releases in a row on the same pointer. If so, make
179  // a note, and we'll cicle back to revisit it after we've
180  // hopefully eliminated the second release, which may allow us to
181  // eliminate the first release too.
182  // Theoretically we could implement removal of nested retain+release
183  // pairs by making PtrState hold a stack of states, but this is
184  // simple and avoids adding overhead for the non-nested case.
185  bool NestingDetected = false;
186  if (GetSeq() == S_Release || GetSeq() == S_MovableRelease) {
187  DEBUG(dbgs() << " Found nested releases (i.e. a release pair)\n");
188  NestingDetected = true;
189  }
190 
193  Sequence NewSeq = ReleaseMetadata ? S_MovableRelease : S_Release;
194  ResetSequenceProgress(NewSeq);
195  SetReleaseMetadata(ReleaseMetadata);
196  SetKnownSafe(HasKnownPositiveRefCount());
197  SetTailCallRelease(cast<CallInst>(I)->isTailCall());
198  InsertCall(I);
199  SetKnownPositiveRefCount();
200  return NestingDetected;
201 }
202 
204  SetKnownPositiveRefCount();
205 
206  Sequence OldSeq = GetSeq();
207  switch (OldSeq) {
208  case S_Stop:
209  case S_Release:
210  case S_MovableRelease:
211  case S_Use:
212  // If OldSeq is not S_Use or OldSeq is S_Use and we are tracking an
213  // imprecise release, clear our reverse insertion points.
214  if (OldSeq != S_Use || IsTrackingImpreciseReleases())
215  ClearReverseInsertPts();
217  case S_CanRelease:
218  return true;
219  case S_None:
220  return false;
221  case S_Retain:
222  llvm_unreachable("bottom-up pointer in retain state!");
223  }
224  llvm_unreachable("Sequence unknown enum value");
225 }
226 
228  const Value *Ptr,
229  ProvenanceAnalysis &PA,
230  ARCInstKind Class) {
231  Sequence S = GetSeq();
232 
233  // Check for possible releases.
234  if (!CanAlterRefCount(Inst, Ptr, PA, Class))
235  return false;
236 
237  DEBUG(dbgs() << " CanAlterRefCount: Seq: " << S << "; " << *Ptr
238  << "\n");
239  switch (S) {
240  case S_Use:
241  SetSeq(S_CanRelease);
242  return true;
243  case S_CanRelease:
244  case S_Release:
245  case S_MovableRelease:
246  case S_Stop:
247  case S_None:
248  return false;
249  case S_Retain:
250  llvm_unreachable("bottom-up pointer in retain state!");
251  }
252  llvm_unreachable("Sequence unknown enum value");
253 }
254 
256  const Value *Ptr,
257  ProvenanceAnalysis &PA,
258  ARCInstKind Class) {
259  auto SetSeqAndInsertReverseInsertPt = [&](Sequence NewSeq){
260  assert(!HasReverseInsertPts());
261  SetSeq(NewSeq);
262  // If this is an invoke instruction, we're scanning it as part of
263  // one of its successor blocks, since we can't insert code after it
264  // in its own block, and we don't want to split critical edges.
265  BasicBlock::iterator InsertAfter;
266  if (isa<InvokeInst>(Inst)) {
267  const auto IP = BB->getFirstInsertionPt();
268  InsertAfter = IP == BB->end() ? std::prev(BB->end()) : IP;
269  } else {
270  InsertAfter = std::next(Inst->getIterator());
271  }
272  InsertReverseInsertPt(&*InsertAfter);
273  };
274 
275  // Check for possible direct uses.
276  switch (GetSeq()) {
277  case S_Release:
278  case S_MovableRelease:
279  if (CanUse(Inst, Ptr, PA, Class)) {
280  DEBUG(dbgs() << " CanUse: Seq: " << GetSeq() << "; " << *Ptr
281  << "\n");
282  SetSeqAndInsertReverseInsertPt(S_Use);
283  } else if (Seq == S_Release && IsUser(Class)) {
284  DEBUG(dbgs() << " PreciseReleaseUse: Seq: " << GetSeq() << "; "
285  << *Ptr << "\n");
286  // Non-movable releases depend on any possible objc pointer use.
287  SetSeqAndInsertReverseInsertPt(S_Stop);
288  } else if (const auto *Call = getreturnRVOperand(*Inst, Class)) {
289  if (CanUse(Call, Ptr, PA, GetBasicARCInstKind(Call))) {
290  DEBUG(dbgs() << " ReleaseUse: Seq: " << GetSeq() << "; "
291  << *Ptr << "\n");
292  SetSeqAndInsertReverseInsertPt(S_Stop);
293  }
294  }
295  break;
296  case S_Stop:
297  if (CanUse(Inst, Ptr, PA, Class)) {
298  DEBUG(dbgs() << " PreciseStopUse: Seq: " << GetSeq() << "; "
299  << *Ptr << "\n");
300  SetSeq(S_Use);
301  }
302  break;
303  case S_CanRelease:
304  case S_Use:
305  case S_None:
306  break;
307  case S_Retain:
308  llvm_unreachable("bottom-up pointer in retain state!");
309  }
310 }
311 
312 //===----------------------------------------------------------------------===//
313 // TopDownPtrState
314 //===----------------------------------------------------------------------===//
315 
317  bool NestingDetected = false;
318  // Don't do retain+release tracking for ARCInstKind::RetainRV, because
319  // it's
320  // better to let it remain as the first instruction after a call.
321  if (Kind != ARCInstKind::RetainRV) {
322  // If we see two retains in a row on the same pointer. If so, make
323  // a note, and we'll cicle back to revisit it after we've
324  // hopefully eliminated the second retain, which may allow us to
325  // eliminate the first retain too.
326  // Theoretically we could implement removal of nested retain+release
327  // pairs by making PtrState hold a stack of states, but this is
328  // simple and avoids adding overhead for the non-nested case.
329  if (GetSeq() == S_Retain)
330  NestingDetected = true;
331 
332  ResetSequenceProgress(S_Retain);
333  SetKnownSafe(HasKnownPositiveRefCount());
334  InsertCall(I);
335  }
336 
337  SetKnownPositiveRefCount();
338  return NestingDetected;
339 }
340 
342  Instruction *Release) {
343  ClearKnownPositiveRefCount();
344 
345  Sequence OldSeq = GetSeq();
346 
349 
350  switch (OldSeq) {
351  case S_Retain:
352  case S_CanRelease:
353  if (OldSeq == S_Retain || ReleaseMetadata != nullptr)
354  ClearReverseInsertPts();
356  case S_Use:
357  SetReleaseMetadata(ReleaseMetadata);
358  SetTailCallRelease(cast<CallInst>(Release)->isTailCall());
359  return true;
360  case S_None:
361  return false;
362  case S_Stop:
363  case S_Release:
364  case S_MovableRelease:
365  llvm_unreachable("top-down pointer in bottom up state!");
366  }
367  llvm_unreachable("Sequence unknown enum value");
368 }
369 
371  const Value *Ptr,
372  ProvenanceAnalysis &PA,
373  ARCInstKind Class) {
374  // Check for possible releases. Treat clang.arc.use as a releasing instruction
375  // to prevent sinking a retain past it.
376  if (!CanAlterRefCount(Inst, Ptr, PA, Class) &&
378  return false;
379 
380  DEBUG(dbgs() << " CanAlterRefCount: Seq: " << GetSeq() << "; " << *Ptr
381  << "\n");
382  ClearKnownPositiveRefCount();
383  switch (GetSeq()) {
384  case S_Retain:
385  SetSeq(S_CanRelease);
386  assert(!HasReverseInsertPts());
387  InsertReverseInsertPt(Inst);
388 
389  // One call can't cause a transition from S_Retain to S_CanRelease
390  // and S_CanRelease to S_Use. If we've made the first transition,
391  // we're done.
392  return true;
393  case S_Use:
394  case S_CanRelease:
395  case S_None:
396  return false;
397  case S_Stop:
398  case S_Release:
399  case S_MovableRelease:
400  llvm_unreachable("top-down pointer in release state!");
401  }
402  llvm_unreachable("covered switch is not covered!?");
403 }
404 
406  ProvenanceAnalysis &PA,
407  ARCInstKind Class) {
408  // Check for possible direct uses.
409  switch (GetSeq()) {
410  case S_CanRelease:
411  if (!CanUse(Inst, Ptr, PA, Class))
412  return;
413  DEBUG(dbgs() << " CanUse: Seq: " << GetSeq() << "; " << *Ptr
414  << "\n");
415  SetSeq(S_Use);
416  return;
417  case S_Retain:
418  case S_Use:
419  case S_None:
420  return;
421  case S_Stop:
422  case S_Release:
423  case S_MovableRelease:
424  llvm_unreachable("top-down pointer in release state!");
425  }
426 }
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
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:227
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:341
Metadata node.
Definition: Metadata.h:862
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:177
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:194
void HandlePotentialUse(BasicBlock *BB, Instruction *Inst, const Value *Ptr, ProvenanceAnalysis &PA, ARCInstKind Class)
Definition: PtrState.cpp:255
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:405
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:200
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:150
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:203
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:143
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:254
ARCInstKind
Equivalence classes of instructions in the ARC Model.
bool HandlePotentialAlterRefCount(Instruction *Inst, const Value *Ptr, ProvenanceAnalysis &PA, ARCInstKind Class)
Definition: PtrState.cpp:370
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:132
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:923
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
#define LLVM_FALLTHROUGH
LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements.
Definition: Compiler.h:235
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:44
#define DEBUG(X)
Definition: Debug.h:118
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:316