LLVM  9.0.0svn
PtrState.cpp
Go to the documentation of this file.
1 //===- PtrState.cpp -------------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #include "PtrState.h"
10 #include "DependencyAnalysis.h"
11 #include "ObjCARC.h"
14 #include "llvm/IR/BasicBlock.h"
15 #include "llvm/IR/Instruction.h"
16 #include "llvm/IR/Instructions.h"
17 #include "llvm/IR/Value.h"
18 #include "llvm/Support/Casting.h"
19 #include "llvm/Support/Compiler.h"
20 #include "llvm/Support/Debug.h"
23 #include <cassert>
24 #include <iterator>
25 #include <utility>
26 
27 using namespace llvm;
28 using namespace llvm::objcarc;
29 
30 #define DEBUG_TYPE "objc-arc-ptr-state"
31 
32 //===----------------------------------------------------------------------===//
33 // Utility
34 //===----------------------------------------------------------------------===//
35 
37  switch (S) {
38  case S_None:
39  return OS << "S_None";
40  case S_Retain:
41  return OS << "S_Retain";
42  case S_CanRelease:
43  return OS << "S_CanRelease";
44  case S_Use:
45  return OS << "S_Use";
46  case S_Release:
47  return OS << "S_Release";
48  case S_MovableRelease:
49  return OS << "S_MovableRelease";
50  case S_Stop:
51  return OS << "S_Stop";
52  }
53  llvm_unreachable("Unknown sequence type.");
54 }
55 
56 //===----------------------------------------------------------------------===//
57 // Sequence
58 //===----------------------------------------------------------------------===//
59 
60 static Sequence MergeSeqs(Sequence A, Sequence B, bool TopDown) {
61  // The easy cases.
62  if (A == B)
63  return A;
64  if (A == S_None || B == S_None)
65  return S_None;
66 
67  if (A > B)
68  std::swap(A, B);
69  if (TopDown) {
70  // Choose the side which is further along in the sequence.
71  if ((A == S_Retain || A == S_CanRelease) &&
72  (B == S_CanRelease || B == S_Use))
73  return B;
74  } else {
75  // Choose the side which is further along in the sequence.
76  if ((A == S_Use || A == S_CanRelease) &&
77  (B == S_Use || B == S_Release || B == S_Stop || B == S_MovableRelease))
78  return A;
79  // If both sides are releases, choose the more conservative one.
80  if (A == S_Stop && (B == S_Release || B == S_MovableRelease))
81  return A;
82  if (A == S_Release && B == S_MovableRelease)
83  return A;
84  }
85 
86  return S_None;
87 }
88 
89 //===----------------------------------------------------------------------===//
90 // RRInfo
91 //===----------------------------------------------------------------------===//
92 
93 void RRInfo::clear() {
94  KnownSafe = false;
95  IsTailCallRelease = false;
96  ReleaseMetadata = nullptr;
97  Calls.clear();
98  ReverseInsertPts.clear();
99  CFGHazardAfflicted = false;
100 }
101 
102 bool RRInfo::Merge(const RRInfo &Other) {
103  // Conservatively merge the ReleaseMetadata information.
104  if (ReleaseMetadata != Other.ReleaseMetadata)
105  ReleaseMetadata = nullptr;
106 
107  // Conservatively merge the boolean state.
108  KnownSafe &= Other.KnownSafe;
111 
112  // Merge the call sets.
113  Calls.insert(Other.Calls.begin(), Other.Calls.end());
114 
115  // Merge the insert point sets. If there are any differences,
116  // that makes this a partial merge.
117  bool Partial = ReverseInsertPts.size() != Other.ReverseInsertPts.size();
118  for (Instruction *Inst : Other.ReverseInsertPts)
119  Partial |= ReverseInsertPts.insert(Inst).second;
120  return Partial;
121 }
122 
123 //===----------------------------------------------------------------------===//
124 // PtrState
125 //===----------------------------------------------------------------------===//
126 
128  LLVM_DEBUG(dbgs() << " Setting Known Positive.\n");
129  KnownPositiveRefCount = true;
130 }
131 
133  LLVM_DEBUG(dbgs() << " Clearing Known Positive.\n");
134  KnownPositiveRefCount = false;
135 }
136 
138  LLVM_DEBUG(dbgs() << " Old: " << GetSeq() << "; New: " << NewSeq
139  << "\n");
140  Seq = NewSeq;
141 }
142 
144  LLVM_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  LLVM_DEBUG(
188  dbgs() << " Found nested releases (i.e. a release pair)\n");
189  NestingDetected = true;
190  }
191 
194  Sequence NewSeq = ReleaseMetadata ? S_MovableRelease : S_Release;
195  ResetSequenceProgress(NewSeq);
196  SetReleaseMetadata(ReleaseMetadata);
197  SetKnownSafe(HasKnownPositiveRefCount());
198  SetTailCallRelease(cast<CallInst>(I)->isTailCall());
199  InsertCall(I);
200  SetKnownPositiveRefCount();
201  return NestingDetected;
202 }
203 
205  SetKnownPositiveRefCount();
206 
207  Sequence OldSeq = GetSeq();
208  switch (OldSeq) {
209  case S_Stop:
210  case S_Release:
211  case S_MovableRelease:
212  case S_Use:
213  // If OldSeq is not S_Use or OldSeq is S_Use and we are tracking an
214  // imprecise release, clear our reverse insertion points.
215  if (OldSeq != S_Use || IsTrackingImpreciseReleases())
216  ClearReverseInsertPts();
218  case S_CanRelease:
219  return true;
220  case S_None:
221  return false;
222  case S_Retain:
223  llvm_unreachable("bottom-up pointer in retain state!");
224  }
225  llvm_unreachable("Sequence unknown enum value");
226 }
227 
229  const Value *Ptr,
230  ProvenanceAnalysis &PA,
231  ARCInstKind Class) {
232  Sequence S = GetSeq();
233 
234  // Check for possible releases.
235  if (!CanAlterRefCount(Inst, Ptr, PA, Class))
236  return false;
237 
238  LLVM_DEBUG(dbgs() << " CanAlterRefCount: Seq: " << S << "; "
239  << *Ptr << "\n");
240  switch (S) {
241  case S_Use:
242  SetSeq(S_CanRelease);
243  return true;
244  case S_CanRelease:
245  case S_Release:
246  case S_MovableRelease:
247  case S_Stop:
248  case S_None:
249  return false;
250  case S_Retain:
251  llvm_unreachable("bottom-up pointer in retain state!");
252  }
253  llvm_unreachable("Sequence unknown enum value");
254 }
255 
257  const Value *Ptr,
258  ProvenanceAnalysis &PA,
259  ARCInstKind Class) {
260  auto SetSeqAndInsertReverseInsertPt = [&](Sequence NewSeq){
261  assert(!HasReverseInsertPts());
262  SetSeq(NewSeq);
263  // If this is an invoke instruction, we're scanning it as part of
264  // one of its successor blocks, since we can't insert code after it
265  // in its own block, and we don't want to split critical edges.
266  BasicBlock::iterator InsertAfter;
267  if (isa<InvokeInst>(Inst)) {
268  const auto IP = BB->getFirstInsertionPt();
269  InsertAfter = IP == BB->end() ? std::prev(BB->end()) : IP;
270  if (isa<CatchSwitchInst>(InsertAfter))
271  // A catchswitch must be the only non-phi instruction in its basic
272  // block, so attempting to insert an instruction into such a block would
273  // produce invalid IR.
274  SetCFGHazardAfflicted(true);
275  } else {
276  InsertAfter = std::next(Inst->getIterator());
277  }
278  InsertReverseInsertPt(&*InsertAfter);
279  };
280 
281  // Check for possible direct uses.
282  switch (GetSeq()) {
283  case S_Release:
284  case S_MovableRelease:
285  if (CanUse(Inst, Ptr, PA, Class)) {
286  LLVM_DEBUG(dbgs() << " CanUse: Seq: " << GetSeq() << "; "
287  << *Ptr << "\n");
288  SetSeqAndInsertReverseInsertPt(S_Use);
289  } else if (Seq == S_Release && IsUser(Class)) {
290  LLVM_DEBUG(dbgs() << " PreciseReleaseUse: Seq: " << GetSeq()
291  << "; " << *Ptr << "\n");
292  // Non-movable releases depend on any possible objc pointer use.
293  SetSeqAndInsertReverseInsertPt(S_Stop);
294  } else if (const auto *Call = getreturnRVOperand(*Inst, Class)) {
295  if (CanUse(Call, Ptr, PA, GetBasicARCInstKind(Call))) {
296  LLVM_DEBUG(dbgs() << " ReleaseUse: Seq: " << GetSeq() << "; "
297  << *Ptr << "\n");
298  SetSeqAndInsertReverseInsertPt(S_Stop);
299  }
300  }
301  break;
302  case S_Stop:
303  if (CanUse(Inst, Ptr, PA, Class)) {
304  LLVM_DEBUG(dbgs() << " PreciseStopUse: Seq: " << GetSeq()
305  << "; " << *Ptr << "\n");
306  SetSeq(S_Use);
307  }
308  break;
309  case S_CanRelease:
310  case S_Use:
311  case S_None:
312  break;
313  case S_Retain:
314  llvm_unreachable("bottom-up pointer in retain state!");
315  }
316 }
317 
318 //===----------------------------------------------------------------------===//
319 // TopDownPtrState
320 //===----------------------------------------------------------------------===//
321 
323  bool NestingDetected = false;
324  // Don't do retain+release tracking for ARCInstKind::RetainRV, because
325  // it's
326  // better to let it remain as the first instruction after a call.
327  if (Kind != ARCInstKind::RetainRV) {
328  // If we see two retains in a row on the same pointer. If so, make
329  // a note, and we'll cicle back to revisit it after we've
330  // hopefully eliminated the second retain, which may allow us to
331  // eliminate the first retain too.
332  // Theoretically we could implement removal of nested retain+release
333  // pairs by making PtrState hold a stack of states, but this is
334  // simple and avoids adding overhead for the non-nested case.
335  if (GetSeq() == S_Retain)
336  NestingDetected = true;
337 
338  ResetSequenceProgress(S_Retain);
339  SetKnownSafe(HasKnownPositiveRefCount());
340  InsertCall(I);
341  }
342 
343  SetKnownPositiveRefCount();
344  return NestingDetected;
345 }
346 
348  Instruction *Release) {
349  ClearKnownPositiveRefCount();
350 
351  Sequence OldSeq = GetSeq();
352 
355 
356  switch (OldSeq) {
357  case S_Retain:
358  case S_CanRelease:
359  if (OldSeq == S_Retain || ReleaseMetadata != nullptr)
360  ClearReverseInsertPts();
362  case S_Use:
363  SetReleaseMetadata(ReleaseMetadata);
364  SetTailCallRelease(cast<CallInst>(Release)->isTailCall());
365  return true;
366  case S_None:
367  return false;
368  case S_Stop:
369  case S_Release:
370  case S_MovableRelease:
371  llvm_unreachable("top-down pointer in bottom up state!");
372  }
373  llvm_unreachable("Sequence unknown enum value");
374 }
375 
377  const Value *Ptr,
378  ProvenanceAnalysis &PA,
379  ARCInstKind Class) {
380  // Check for possible releases. Treat clang.arc.use as a releasing instruction
381  // to prevent sinking a retain past it.
382  if (!CanAlterRefCount(Inst, Ptr, PA, Class) &&
384  return false;
385 
386  LLVM_DEBUG(dbgs() << " CanAlterRefCount: Seq: " << GetSeq() << "; "
387  << *Ptr << "\n");
388  ClearKnownPositiveRefCount();
389  switch (GetSeq()) {
390  case S_Retain:
391  SetSeq(S_CanRelease);
392  assert(!HasReverseInsertPts());
393  InsertReverseInsertPt(Inst);
394 
395  // One call can't cause a transition from S_Retain to S_CanRelease
396  // and S_CanRelease to S_Use. If we've made the first transition,
397  // we're done.
398  return true;
399  case S_Use:
400  case S_CanRelease:
401  case S_None:
402  return false;
403  case S_Stop:
404  case S_Release:
405  case S_MovableRelease:
406  llvm_unreachable("top-down pointer in release state!");
407  }
408  llvm_unreachable("covered switch is not covered!?");
409 }
410 
412  ProvenanceAnalysis &PA,
413  ARCInstKind Class) {
414  // Check for possible direct uses.
415  switch (GetSeq()) {
416  case S_CanRelease:
417  if (!CanUse(Inst, Ptr, PA, Class))
418  return;
419  LLVM_DEBUG(dbgs() << " CanUse: Seq: " << GetSeq() << "; "
420  << *Ptr << "\n");
421  SetSeq(S_Use);
422  return;
423  case S_Retain:
424  case S_Use:
425  case S_None:
426  return;
427  case S_Stop:
428  case S_Release:
429  case S_MovableRelease:
430  llvm_unreachable("top-down pointer in release state!");
431  }
432 }
bool Merge(const RRInfo &Other)
Conservatively merge the two RRInfo.
Definition: PtrState.cpp:102
Sequence GetSeq() const
Definition: PtrState.h:150
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:80
This class represents lattice values for constants.
Definition: AllocatorList.h:23
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:228
any use of x.
Definition: PtrState.h:44
bool MatchWithRelease(ARCMDKindCache &Cache, Instruction *Release)
Return true if this set of retains can be paired with the given release.
Definition: PtrState.cpp:347
Metadata node.
Definition: Metadata.h:863
could call objc_release
SmallPtrSet< Instruction *, 2 > ReverseInsertPts
The set of optimal insert positions for moving calls in the opposite sequence.
Definition: PtrState.h:84
This class summarizes several per-pointer runtime properties which are propagated through the flow gr...
Definition: PtrState.h:101
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:72
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:132
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:234
void HandlePotentialUse(BasicBlock *BB, Instruction *Inst, const Value *Ptr, ProvenanceAnalysis &PA, ARCInstKind Class)
Definition: PtrState.cpp:256
Unidirectional information about either a retain-decrement-use-release sequence or release-use-decrem...
Definition: PtrState.h:56
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:411
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:216
RRInfo RRI
Unidirectional information about the current sequence.
Definition: PtrState.h:114
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
bool KnownPositiveRefCount
True if the reference count is known to be incremented.
Definition: PtrState.h:104
void Merge(const PtrState &Other, bool TopDown)
Definition: PtrState.cpp:150
like S_Release, but code motion is stopped.
Definition: PtrState.h:45
self_iterator getIterator()
Definition: ilist_node.h:81
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:204
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:88
ARCInstKind GetBasicARCInstKind(const Value *V)
Determine which objc runtime call instruction class V belongs to.
objc_release(x), !clang.imprecise_release.
Definition: PtrState.h:47
Iterator for intrusive lists based on ilist_node.
objc_release(x).
Definition: PtrState.h:46
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:73
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:108
iterator end()
Definition: BasicBlock.h:270
ARCInstKind
Equivalence classes of instructions in the ARC Model.
bool HandlePotentialAlterRefCount(Instruction *Inst, const Value *Ptr, ProvenanceAnalysis &PA, ARCInstKind Class)
Definition: PtrState.cpp:376
objc_retain(x).
Definition: PtrState.h:42
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:940
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:76
static Sequence MergeSeqs(Sequence A, Sequence B, bool TopDown)
Definition: PtrState.cpp:60
#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:40
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:137
const unsigned Kind
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:72
foo(x) – x could possibly see a ref count decrement.
Definition: PtrState.h:43
#define LLVM_FALLTHROUGH
LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements.
Definition: Compiler.h:250
bool KnownSafe
After an objc_retain, the reference count of the referenced object is known to be positive...
Definition: PtrState.h:69
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
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:322
#define LLVM_DEBUG(X)
Definition: Debug.h:122