LLVM  9.0.0svn
ObjCARCOpts.cpp
Go to the documentation of this file.
1 //===- ObjCARCOpts.cpp - ObjC ARC Optimization ----------------------------===//
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 /// \file
10 /// This file defines ObjC ARC optimizations. ARC stands for Automatic
11 /// Reference Counting and is a system for managing reference counts for objects
12 /// in Objective C.
13 ///
14 /// The optimizations performed include elimination of redundant, partially
15 /// redundant, and inconsequential reference count operations, elimination of
16 /// redundant weak pointer operations, and numerous minor simplifications.
17 ///
18 /// WARNING: This file knows about certain library functions. It recognizes them
19 /// by name, and hardwires knowledge of their semantics.
20 ///
21 /// WARNING: This file knows about how certain Objective-C library functions are
22 /// used. Naive LLVM IR transformations which would otherwise be
23 /// behavior-preserving may break these assumptions.
24 //
25 //===----------------------------------------------------------------------===//
26 
27 #include "ARCRuntimeEntryPoints.h"
28 #include "BlotMapVector.h"
29 #include "DependencyAnalysis.h"
30 #include "ObjCARC.h"
31 #include "ProvenanceAnalysis.h"
32 #include "PtrState.h"
33 #include "llvm/ADT/DenseMap.h"
34 #include "llvm/ADT/None.h"
35 #include "llvm/ADT/STLExtras.h"
36 #include "llvm/ADT/SmallPtrSet.h"
37 #include "llvm/ADT/SmallVector.h"
38 #include "llvm/ADT/Statistic.h"
44 #include "llvm/IR/BasicBlock.h"
45 #include "llvm/IR/CFG.h"
46 #include "llvm/IR/CallSite.h"
47 #include "llvm/IR/Constant.h"
48 #include "llvm/IR/Constants.h"
49 #include "llvm/IR/DerivedTypes.h"
50 #include "llvm/IR/Function.h"
51 #include "llvm/IR/GlobalVariable.h"
52 #include "llvm/IR/InstIterator.h"
53 #include "llvm/IR/InstrTypes.h"
54 #include "llvm/IR/Instruction.h"
55 #include "llvm/IR/Instructions.h"
56 #include "llvm/IR/LLVMContext.h"
57 #include "llvm/IR/Metadata.h"
58 #include "llvm/IR/Type.h"
59 #include "llvm/IR/User.h"
60 #include "llvm/IR/Value.h"
61 #include "llvm/Pass.h"
62 #include "llvm/Support/Casting.h"
63 #include "llvm/Support/Compiler.h"
64 #include "llvm/Support/Debug.h"
67 #include <cassert>
68 #include <iterator>
69 #include <utility>
70 
71 using namespace llvm;
72 using namespace llvm::objcarc;
73 
74 #define DEBUG_TYPE "objc-arc-opts"
75 
76 static cl::opt<unsigned> MaxPtrStates("arc-opt-max-ptr-states",
77  cl::Hidden,
78  cl::desc("Maximum number of ptr states the optimizer keeps track of"),
79  cl::init(4095));
80 
81 /// \defgroup ARCUtilities Utility declarations/definitions specific to ARC.
82 /// @{
83 
84 /// This is similar to GetRCIdentityRoot but it stops as soon
85 /// as it finds a value with multiple uses.
87  // ConstantData (like ConstantPointerNull and UndefValue) is used across
88  // modules. It's never a single-use value.
89  if (isa<ConstantData>(Arg))
90  return nullptr;
91 
92  if (Arg->hasOneUse()) {
93  if (const BitCastInst *BC = dyn_cast<BitCastInst>(Arg))
94  return FindSingleUseIdentifiedObject(BC->getOperand(0));
95  if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Arg))
96  if (GEP->hasAllZeroIndices())
97  return FindSingleUseIdentifiedObject(GEP->getPointerOperand());
100  cast<CallInst>(Arg)->getArgOperand(0));
101  if (!IsObjCIdentifiedObject(Arg))
102  return nullptr;
103  return Arg;
104  }
105 
106  // If we found an identifiable object but it has multiple uses, but they are
107  // trivial uses, we can still consider this to be a single-use value.
108  if (IsObjCIdentifiedObject(Arg)) {
109  for (const User *U : Arg->users())
110  if (!U->use_empty() || GetRCIdentityRoot(U) != Arg)
111  return nullptr;
112 
113  return Arg;
114  }
115 
116  return nullptr;
117 }
118 
119 /// @}
120 ///
121 /// \defgroup ARCOpt ARC Optimization.
122 /// @{
123 
124 // TODO: On code like this:
125 //
126 // objc_retain(%x)
127 // stuff_that_cannot_release()
128 // objc_autorelease(%x)
129 // stuff_that_cannot_release()
130 // objc_retain(%x)
131 // stuff_that_cannot_release()
132 // objc_autorelease(%x)
133 //
134 // The second retain and autorelease can be deleted.
135 
136 // TODO: It should be possible to delete
137 // objc_autoreleasePoolPush and objc_autoreleasePoolPop
138 // pairs if nothing is actually autoreleased between them. Also, autorelease
139 // calls followed by objc_autoreleasePoolPop calls (perhaps in ObjC++ code
140 // after inlining) can be turned into plain release calls.
141 
142 // TODO: Critical-edge splitting. If the optimial insertion point is
143 // a critical edge, the current algorithm has to fail, because it doesn't
144 // know how to split edges. It should be possible to make the optimizer
145 // think in terms of edges, rather than blocks, and then split critical
146 // edges on demand.
147 
148 // TODO: OptimizeSequences could generalized to be Interprocedural.
149 
150 // TODO: Recognize that a bunch of other objc runtime calls have
151 // non-escaping arguments and non-releasing arguments, and may be
152 // non-autoreleasing.
153 
154 // TODO: Sink autorelease calls as far as possible. Unfortunately we
155 // usually can't sink them past other calls, which would be the main
156 // case where it would be useful.
157 
158 // TODO: The pointer returned from objc_loadWeakRetained is retained.
159 
160 // TODO: Delete release+retain pairs (rare).
161 
162 STATISTIC(NumNoops, "Number of no-op objc calls eliminated");
163 STATISTIC(NumPartialNoops, "Number of partially no-op objc calls eliminated");
164 STATISTIC(NumAutoreleases,"Number of autoreleases converted to releases");
165 STATISTIC(NumRets, "Number of return value forwarding "
166  "retain+autoreleases eliminated");
167 STATISTIC(NumRRs, "Number of retain+release paths eliminated");
168 STATISTIC(NumPeeps, "Number of calls peephole-optimized");
169 #ifndef NDEBUG
170 STATISTIC(NumRetainsBeforeOpt,
171  "Number of retains before optimization");
172 STATISTIC(NumReleasesBeforeOpt,
173  "Number of releases before optimization");
174 STATISTIC(NumRetainsAfterOpt,
175  "Number of retains after optimization");
176 STATISTIC(NumReleasesAfterOpt,
177  "Number of releases after optimization");
178 #endif
179 
180 namespace {
181 
182  /// Per-BasicBlock state.
183  class BBState {
184  /// The number of unique control paths from the entry which can reach this
185  /// block.
186  unsigned TopDownPathCount = 0;
187 
188  /// The number of unique control paths to exits from this block.
189  unsigned BottomUpPathCount = 0;
190 
191  /// The top-down traversal uses this to record information known about a
192  /// pointer at the bottom of each block.
194 
195  /// The bottom-up traversal uses this to record information known about a
196  /// pointer at the top of each block.
198 
199  /// Effective predecessors of the current block ignoring ignorable edges and
200  /// ignored backedges.
202 
203  /// Effective successors of the current block ignoring ignorable edges and
204  /// ignored backedges.
206 
207  public:
208  static const unsigned OverflowOccurredValue;
209 
210  BBState() = default;
211 
212  using top_down_ptr_iterator = decltype(PerPtrTopDown)::iterator;
213  using const_top_down_ptr_iterator = decltype(PerPtrTopDown)::const_iterator;
214 
215  top_down_ptr_iterator top_down_ptr_begin() { return PerPtrTopDown.begin(); }
216  top_down_ptr_iterator top_down_ptr_end() { return PerPtrTopDown.end(); }
217  const_top_down_ptr_iterator top_down_ptr_begin() const {
218  return PerPtrTopDown.begin();
219  }
220  const_top_down_ptr_iterator top_down_ptr_end() const {
221  return PerPtrTopDown.end();
222  }
223  bool hasTopDownPtrs() const {
224  return !PerPtrTopDown.empty();
225  }
226 
227  unsigned top_down_ptr_list_size() const {
228  return std::distance(top_down_ptr_begin(), top_down_ptr_end());
229  }
230 
231  using bottom_up_ptr_iterator = decltype(PerPtrBottomUp)::iterator;
232  using const_bottom_up_ptr_iterator =
233  decltype(PerPtrBottomUp)::const_iterator;
234 
235  bottom_up_ptr_iterator bottom_up_ptr_begin() {
236  return PerPtrBottomUp.begin();
237  }
238  bottom_up_ptr_iterator bottom_up_ptr_end() { return PerPtrBottomUp.end(); }
239  const_bottom_up_ptr_iterator bottom_up_ptr_begin() const {
240  return PerPtrBottomUp.begin();
241  }
242  const_bottom_up_ptr_iterator bottom_up_ptr_end() const {
243  return PerPtrBottomUp.end();
244  }
245  bool hasBottomUpPtrs() const {
246  return !PerPtrBottomUp.empty();
247  }
248 
249  unsigned bottom_up_ptr_list_size() const {
250  return std::distance(bottom_up_ptr_begin(), bottom_up_ptr_end());
251  }
252 
253  /// Mark this block as being an entry block, which has one path from the
254  /// entry by definition.
255  void SetAsEntry() { TopDownPathCount = 1; }
256 
257  /// Mark this block as being an exit block, which has one path to an exit by
258  /// definition.
259  void SetAsExit() { BottomUpPathCount = 1; }
260 
261  /// Attempt to find the PtrState object describing the top down state for
262  /// pointer Arg. Return a new initialized PtrState describing the top down
263  /// state for Arg if we do not find one.
264  TopDownPtrState &getPtrTopDownState(const Value *Arg) {
265  return PerPtrTopDown[Arg];
266  }
267 
268  /// Attempt to find the PtrState object describing the bottom up state for
269  /// pointer Arg. Return a new initialized PtrState describing the bottom up
270  /// state for Arg if we do not find one.
271  BottomUpPtrState &getPtrBottomUpState(const Value *Arg) {
272  return PerPtrBottomUp[Arg];
273  }
274 
275  /// Attempt to find the PtrState object describing the bottom up state for
276  /// pointer Arg.
277  bottom_up_ptr_iterator findPtrBottomUpState(const Value *Arg) {
278  return PerPtrBottomUp.find(Arg);
279  }
280 
281  void clearBottomUpPointers() {
282  PerPtrBottomUp.clear();
283  }
284 
285  void clearTopDownPointers() {
286  PerPtrTopDown.clear();
287  }
288 
289  void InitFromPred(const BBState &Other);
290  void InitFromSucc(const BBState &Other);
291  void MergePred(const BBState &Other);
292  void MergeSucc(const BBState &Other);
293 
294  /// Compute the number of possible unique paths from an entry to an exit
295  /// which pass through this block. This is only valid after both the
296  /// top-down and bottom-up traversals are complete.
297  ///
298  /// Returns true if overflow occurred. Returns false if overflow did not
299  /// occur.
300  bool GetAllPathCountWithOverflow(unsigned &PathCount) const {
301  if (TopDownPathCount == OverflowOccurredValue ||
302  BottomUpPathCount == OverflowOccurredValue)
303  return true;
304  unsigned long long Product =
305  (unsigned long long)TopDownPathCount*BottomUpPathCount;
306  // Overflow occurred if any of the upper bits of Product are set or if all
307  // the lower bits of Product are all set.
308  return (Product >> 32) ||
309  ((PathCount = Product) == OverflowOccurredValue);
310  }
311 
312  // Specialized CFG utilities.
313  using edge_iterator = SmallVectorImpl<BasicBlock *>::const_iterator;
314 
315  edge_iterator pred_begin() const { return Preds.begin(); }
316  edge_iterator pred_end() const { return Preds.end(); }
317  edge_iterator succ_begin() const { return Succs.begin(); }
318  edge_iterator succ_end() const { return Succs.end(); }
319 
320  void addSucc(BasicBlock *Succ) { Succs.push_back(Succ); }
321  void addPred(BasicBlock *Pred) { Preds.push_back(Pred); }
322 
323  bool isExit() const { return Succs.empty(); }
324  };
325 
326 } // end anonymous namespace
327 
328 const unsigned BBState::OverflowOccurredValue = 0xffffffff;
329 
330 namespace llvm {
331 
333  BBState &BBState) LLVM_ATTRIBUTE_UNUSED;
334 
335 } // end namespace llvm
336 
337 void BBState::InitFromPred(const BBState &Other) {
338  PerPtrTopDown = Other.PerPtrTopDown;
339  TopDownPathCount = Other.TopDownPathCount;
340 }
341 
342 void BBState::InitFromSucc(const BBState &Other) {
343  PerPtrBottomUp = Other.PerPtrBottomUp;
344  BottomUpPathCount = Other.BottomUpPathCount;
345 }
346 
347 /// The top-down traversal uses this to merge information about predecessors to
348 /// form the initial state for a new block.
349 void BBState::MergePred(const BBState &Other) {
350  if (TopDownPathCount == OverflowOccurredValue)
351  return;
352 
353  // Other.TopDownPathCount can be 0, in which case it is either dead or a
354  // loop backedge. Loop backedges are special.
355  TopDownPathCount += Other.TopDownPathCount;
356 
357  // In order to be consistent, we clear the top down pointers when by adding
358  // TopDownPathCount becomes OverflowOccurredValue even though "true" overflow
359  // has not occurred.
360  if (TopDownPathCount == OverflowOccurredValue) {
361  clearTopDownPointers();
362  return;
363  }
364 
365  // Check for overflow. If we have overflow, fall back to conservative
366  // behavior.
367  if (TopDownPathCount < Other.TopDownPathCount) {
368  TopDownPathCount = OverflowOccurredValue;
369  clearTopDownPointers();
370  return;
371  }
372 
373  // For each entry in the other set, if our set has an entry with the same key,
374  // merge the entries. Otherwise, copy the entry and merge it with an empty
375  // entry.
376  for (auto MI = Other.top_down_ptr_begin(), ME = Other.top_down_ptr_end();
377  MI != ME; ++MI) {
378  auto Pair = PerPtrTopDown.insert(*MI);
379  Pair.first->second.Merge(Pair.second ? TopDownPtrState() : MI->second,
380  /*TopDown=*/true);
381  }
382 
383  // For each entry in our set, if the other set doesn't have an entry with the
384  // same key, force it to merge with an empty entry.
385  for (auto MI = top_down_ptr_begin(), ME = top_down_ptr_end(); MI != ME; ++MI)
386  if (Other.PerPtrTopDown.find(MI->first) == Other.PerPtrTopDown.end())
387  MI->second.Merge(TopDownPtrState(), /*TopDown=*/true);
388 }
389 
390 /// The bottom-up traversal uses this to merge information about successors to
391 /// form the initial state for a new block.
392 void BBState::MergeSucc(const BBState &Other) {
393  if (BottomUpPathCount == OverflowOccurredValue)
394  return;
395 
396  // Other.BottomUpPathCount can be 0, in which case it is either dead or a
397  // loop backedge. Loop backedges are special.
398  BottomUpPathCount += Other.BottomUpPathCount;
399 
400  // In order to be consistent, we clear the top down pointers when by adding
401  // BottomUpPathCount becomes OverflowOccurredValue even though "true" overflow
402  // has not occurred.
403  if (BottomUpPathCount == OverflowOccurredValue) {
404  clearBottomUpPointers();
405  return;
406  }
407 
408  // Check for overflow. If we have overflow, fall back to conservative
409  // behavior.
410  if (BottomUpPathCount < Other.BottomUpPathCount) {
411  BottomUpPathCount = OverflowOccurredValue;
412  clearBottomUpPointers();
413  return;
414  }
415 
416  // For each entry in the other set, if our set has an entry with the
417  // same key, merge the entries. Otherwise, copy the entry and merge
418  // it with an empty entry.
419  for (auto MI = Other.bottom_up_ptr_begin(), ME = Other.bottom_up_ptr_end();
420  MI != ME; ++MI) {
421  auto Pair = PerPtrBottomUp.insert(*MI);
422  Pair.first->second.Merge(Pair.second ? BottomUpPtrState() : MI->second,
423  /*TopDown=*/false);
424  }
425 
426  // For each entry in our set, if the other set doesn't have an entry
427  // with the same key, force it to merge with an empty entry.
428  for (auto MI = bottom_up_ptr_begin(), ME = bottom_up_ptr_end(); MI != ME;
429  ++MI)
430  if (Other.PerPtrBottomUp.find(MI->first) == Other.PerPtrBottomUp.end())
431  MI->second.Merge(BottomUpPtrState(), /*TopDown=*/false);
432 }
433 
434 raw_ostream &llvm::operator<<(raw_ostream &OS, BBState &BBInfo) {
435  // Dump the pointers we are tracking.
436  OS << " TopDown State:\n";
437  if (!BBInfo.hasTopDownPtrs()) {
438  LLVM_DEBUG(dbgs() << " NONE!\n");
439  } else {
440  for (auto I = BBInfo.top_down_ptr_begin(), E = BBInfo.top_down_ptr_end();
441  I != E; ++I) {
442  const PtrState &P = I->second;
443  OS << " Ptr: " << *I->first
444  << "\n KnownSafe: " << (P.IsKnownSafe()?"true":"false")
445  << "\n ImpreciseRelease: "
446  << (P.IsTrackingImpreciseReleases()?"true":"false") << "\n"
447  << " HasCFGHazards: "
448  << (P.IsCFGHazardAfflicted()?"true":"false") << "\n"
449  << " KnownPositive: "
450  << (P.HasKnownPositiveRefCount()?"true":"false") << "\n"
451  << " Seq: "
452  << P.GetSeq() << "\n";
453  }
454  }
455 
456  OS << " BottomUp State:\n";
457  if (!BBInfo.hasBottomUpPtrs()) {
458  LLVM_DEBUG(dbgs() << " NONE!\n");
459  } else {
460  for (auto I = BBInfo.bottom_up_ptr_begin(), E = BBInfo.bottom_up_ptr_end();
461  I != E; ++I) {
462  const PtrState &P = I->second;
463  OS << " Ptr: " << *I->first
464  << "\n KnownSafe: " << (P.IsKnownSafe()?"true":"false")
465  << "\n ImpreciseRelease: "
466  << (P.IsTrackingImpreciseReleases()?"true":"false") << "\n"
467  << " HasCFGHazards: "
468  << (P.IsCFGHazardAfflicted()?"true":"false") << "\n"
469  << " KnownPositive: "
470  << (P.HasKnownPositiveRefCount()?"true":"false") << "\n"
471  << " Seq: "
472  << P.GetSeq() << "\n";
473  }
474  }
475 
476  return OS;
477 }
478 
479 namespace {
480 
481  /// The main ARC optimization pass.
482  class ObjCARCOpt : public FunctionPass {
483  bool Changed;
485 
486  /// A cache of references to runtime entry point constants.
488 
489  /// A cache of MDKinds that can be passed into other functions to propagate
490  /// MDKind identifiers.
491  ARCMDKindCache MDKindCache;
492 
493  /// A flag indicating whether this optimization pass should run.
494  bool Run;
495 
496  /// A flag indicating whether the optimization that removes or moves
497  /// retain/release pairs should be performed.
498  bool DisableRetainReleasePairing = false;
499 
500  /// Flags which determine whether each of the interesting runtime functions
501  /// is in fact used in the current function.
502  unsigned UsedInThisFunction;
503 
504  bool OptimizeRetainRVCall(Function &F, Instruction *RetainRV);
505  void OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV,
506  ARCInstKind &Class);
507  void OptimizeIndividualCalls(Function &F);
508 
509  void CheckForCFGHazards(const BasicBlock *BB,
511  BBState &MyStates) const;
512  bool VisitInstructionBottomUp(Instruction *Inst, BasicBlock *BB,
514  BBState &MyStates);
515  bool VisitBottomUp(BasicBlock *BB,
518  bool VisitInstructionTopDown(Instruction *Inst,
519  DenseMap<Value *, RRInfo> &Releases,
520  BBState &MyStates);
521  bool VisitTopDown(BasicBlock *BB,
523  DenseMap<Value *, RRInfo> &Releases);
524  bool Visit(Function &F, DenseMap<const BasicBlock *, BBState> &BBStates,
526  DenseMap<Value *, RRInfo> &Releases);
527 
528  void MoveCalls(Value *Arg, RRInfo &RetainsToMove, RRInfo &ReleasesToMove,
530  DenseMap<Value *, RRInfo> &Releases,
531  SmallVectorImpl<Instruction *> &DeadInsts, Module *M);
532 
533  bool
534  PairUpRetainsAndReleases(DenseMap<const BasicBlock *, BBState> &BBStates,
536  DenseMap<Value *, RRInfo> &Releases, Module *M,
539  RRInfo &RetainsToMove, RRInfo &ReleasesToMove,
540  Value *Arg, bool KnownSafe,
541  bool &AnyPairsCompletelyEliminated);
542 
543  bool PerformCodePlacement(DenseMap<const BasicBlock *, BBState> &BBStates,
545  DenseMap<Value *, RRInfo> &Releases, Module *M);
546 
547  void OptimizeWeakCalls(Function &F);
548 
549  bool OptimizeSequences(Function &F);
550 
551  void OptimizeReturns(Function &F);
552 
553 #ifndef NDEBUG
554  void GatherStatistics(Function &F, bool AfterOptimization = false);
555 #endif
556 
557  void getAnalysisUsage(AnalysisUsage &AU) const override;
558  bool doInitialization(Module &M) override;
559  bool runOnFunction(Function &F) override;
560  void releaseMemory() override;
561 
562  public:
563  static char ID;
564 
565  ObjCARCOpt() : FunctionPass(ID) {
567  }
568  };
569 
570 } // end anonymous namespace
571 
572 char ObjCARCOpt::ID = 0;
573 
574 INITIALIZE_PASS_BEGIN(ObjCARCOpt,
575  "objc-arc", "ObjC ARC optimization", false, false)
577 INITIALIZE_PASS_END(ObjCARCOpt,
578  "objc-arc", "ObjC ARC optimization", false, false)
579 
581  return new ObjCARCOpt();
582 }
583 
584 void ObjCARCOpt::getAnalysisUsage(AnalysisUsage &AU) const {
587  // ARC optimization doesn't currently split critical edges.
588  AU.setPreservesCFG();
589 }
590 
591 /// Turn objc_retainAutoreleasedReturnValue into objc_retain if the operand is
592 /// not a return value. Or, if it can be paired with an
593 /// objc_autoreleaseReturnValue, delete the pair and return true.
594 bool
595 ObjCARCOpt::OptimizeRetainRVCall(Function &F, Instruction *RetainRV) {
596  // Check for the argument being from an immediately preceding call or invoke.
597  const Value *Arg = GetArgRCIdentityRoot(RetainRV);
598  ImmutableCallSite CS(Arg);
599  if (const Instruction *Call = CS.getInstruction()) {
600  if (Call->getParent() == RetainRV->getParent()) {
602  ++I;
603  while (IsNoopInstruction(&*I))
604  ++I;
605  if (&*I == RetainRV)
606  return false;
607  } else if (const InvokeInst *II = dyn_cast<InvokeInst>(Call)) {
608  BasicBlock *RetainRVParent = RetainRV->getParent();
609  if (II->getNormalDest() == RetainRVParent) {
610  BasicBlock::const_iterator I = RetainRVParent->begin();
611  while (IsNoopInstruction(&*I))
612  ++I;
613  if (&*I == RetainRV)
614  return false;
615  }
616  }
617  }
618 
619  // Track PHIs which are equivalent to our Arg.
620  SmallDenseSet<const Value*, 2> EquivalentArgs;
621  EquivalentArgs.insert(Arg);
622 
623  // Add PHIs that are equivalent to Arg to ArgUsers.
624  if (const PHINode *PN = dyn_cast<PHINode>(Arg)) {
626  getEquivalentPHIs(*PN, ArgUsers);
627  EquivalentArgs.insert(ArgUsers.begin(), ArgUsers.end());
628  }
629 
630  // Check for being preceded by an objc_autoreleaseReturnValue on the same
631  // pointer. In this case, we can delete the pair.
632  BasicBlock::iterator I = RetainRV->getIterator(),
633  Begin = RetainRV->getParent()->begin();
634  if (I != Begin) {
635  do
636  --I;
637  while (I != Begin && IsNoopInstruction(&*I));
639  EquivalentArgs.count(GetArgRCIdentityRoot(&*I))) {
640  Changed = true;
641  ++NumPeeps;
642 
643  LLVM_DEBUG(dbgs() << "Erasing autoreleaseRV,retainRV pair: " << *I << "\n"
644  << "Erasing " << *RetainRV << "\n");
645 
646  EraseInstruction(&*I);
647  EraseInstruction(RetainRV);
648  return true;
649  }
650  }
651 
652  // Turn it to a plain objc_retain.
653  Changed = true;
654  ++NumPeeps;
655 
656  LLVM_DEBUG(dbgs() << "Transforming objc_retainAutoreleasedReturnValue => "
657  "objc_retain since the operand is not a return value.\n"
658  "Old = "
659  << *RetainRV << "\n");
660 
661  Function *NewDecl = EP.get(ARCRuntimeEntryPointKind::Retain);
662  cast<CallInst>(RetainRV)->setCalledFunction(NewDecl);
663 
664  LLVM_DEBUG(dbgs() << "New = " << *RetainRV << "\n");
665 
666  return false;
667 }
668 
669 /// Turn objc_autoreleaseReturnValue into objc_autorelease if the result is not
670 /// used as a return value.
671 void ObjCARCOpt::OptimizeAutoreleaseRVCall(Function &F,
673  ARCInstKind &Class) {
674  // Check for a return of the pointer value.
675  const Value *Ptr = GetArgRCIdentityRoot(AutoreleaseRV);
676 
677  // If the argument is ConstantPointerNull or UndefValue, its other users
678  // aren't actually interesting to look at.
679  if (isa<ConstantData>(Ptr))
680  return;
681 
683  Users.push_back(Ptr);
684 
685  // Add PHIs that are equivalent to Ptr to Users.
686  if (const PHINode *PN = dyn_cast<PHINode>(Ptr))
687  getEquivalentPHIs(*PN, Users);
688 
689  do {
690  Ptr = Users.pop_back_val();
691  for (const User *U : Ptr->users()) {
692  if (isa<ReturnInst>(U) || GetBasicARCInstKind(U) == ARCInstKind::RetainRV)
693  return;
694  if (isa<BitCastInst>(U))
695  Users.push_back(U);
696  }
697  } while (!Users.empty());
698 
699  Changed = true;
700  ++NumPeeps;
701 
702  LLVM_DEBUG(
703  dbgs() << "Transforming objc_autoreleaseReturnValue => "
704  "objc_autorelease since its operand is not used as a return "
705  "value.\n"
706  "Old = "
707  << *AutoreleaseRV << "\n");
708 
709  CallInst *AutoreleaseRVCI = cast<CallInst>(AutoreleaseRV);
711  AutoreleaseRVCI->setCalledFunction(NewDecl);
712  AutoreleaseRVCI->setTailCall(false); // Never tail call objc_autorelease.
713  Class = ARCInstKind::Autorelease;
714 
715  LLVM_DEBUG(dbgs() << "New: " << *AutoreleaseRV << "\n");
716 }
717 
718 namespace {
719 Instruction *
720 CloneCallInstForBB(CallInst &CI, BasicBlock &BB,
721  const DenseMap<BasicBlock *, ColorVector> &BlockColors) {
723  for (unsigned I = 0, E = CI.getNumOperandBundles(); I != E; ++I) {
724  auto Bundle = CI.getOperandBundleAt(I);
725  // Funclets will be reassociated in the future.
726  if (Bundle.getTagID() == LLVMContext::OB_funclet)
727  continue;
728  OpBundles.emplace_back(Bundle);
729  }
730 
731  if (!BlockColors.empty()) {
732  const ColorVector &CV = BlockColors.find(&BB)->second;
733  assert(CV.size() == 1 && "non-unique color for block!");
734  Instruction *EHPad = CV.front()->getFirstNonPHI();
735  if (EHPad->isEHPad())
736  OpBundles.emplace_back("funclet", EHPad);
737  }
738 
739  return CallInst::Create(&CI, OpBundles);
740 }
741 }
742 
743 /// Visit each call, one at a time, and make simplifications without doing any
744 /// additional analysis.
745 void ObjCARCOpt::OptimizeIndividualCalls(Function &F) {
746  LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeIndividualCalls ==\n");
747  // Reset all the flags in preparation for recomputing them.
748  UsedInThisFunction = 0;
749 
751  if (F.hasPersonalityFn() &&
753  BlockColors = colorEHFunclets(F);
754 
755  // Visit all objc_* calls in F.
756  for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
757  Instruction *Inst = &*I++;
758 
759  ARCInstKind Class = GetBasicARCInstKind(Inst);
760 
761  LLVM_DEBUG(dbgs() << "Visiting: Class: " << Class << "; " << *Inst << "\n");
762 
763  switch (Class) {
764  default: break;
765 
766  // Delete no-op casts. These function calls have special semantics, but
767  // the semantics are entirely implemented via lowering in the front-end,
768  // so by the time they reach the optimizer, they are just no-op calls
769  // which return their argument.
770  //
771  // There are gray areas here, as the ability to cast reference-counted
772  // pointers to raw void* and back allows code to break ARC assumptions,
773  // however these are currently considered to be unimportant.
775  Changed = true;
776  ++NumNoops;
777  LLVM_DEBUG(dbgs() << "Erasing no-op cast: " << *Inst << "\n");
778  EraseInstruction(Inst);
779  continue;
780 
781  // If the pointer-to-weak-pointer is null, it's undefined behavior.
787  CallInst *CI = cast<CallInst>(Inst);
788  if (IsNullOrUndef(CI->getArgOperand(0))) {
789  Changed = true;
790  Type *Ty = CI->getArgOperand(0)->getType();
791  new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()),
793  CI);
794  Value *NewValue = UndefValue::get(CI->getType());
795  LLVM_DEBUG(
796  dbgs() << "A null pointer-to-weak-pointer is undefined behavior."
797  "\nOld = "
798  << *CI << "\nNew = " << *NewValue << "\n");
799  CI->replaceAllUsesWith(NewValue);
800  CI->eraseFromParent();
801  continue;
802  }
803  break;
804  }
806  case ARCInstKind::MoveWeak: {
807  CallInst *CI = cast<CallInst>(Inst);
808  if (IsNullOrUndef(CI->getArgOperand(0)) ||
809  IsNullOrUndef(CI->getArgOperand(1))) {
810  Changed = true;
811  Type *Ty = CI->getArgOperand(0)->getType();
812  new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()),
814  CI);
815 
816  Value *NewValue = UndefValue::get(CI->getType());
817  LLVM_DEBUG(
818  dbgs() << "A null pointer-to-weak-pointer is undefined behavior."
819  "\nOld = "
820  << *CI << "\nNew = " << *NewValue << "\n");
821 
822  CI->replaceAllUsesWith(NewValue);
823  CI->eraseFromParent();
824  continue;
825  }
826  break;
827  }
829  if (OptimizeRetainRVCall(F, Inst))
830  continue;
831  break;
833  OptimizeAutoreleaseRVCall(F, Inst, Class);
834  break;
835  }
836 
837  // objc_autorelease(x) -> objc_release(x) if x is otherwise unused.
838  if (IsAutorelease(Class) && Inst->use_empty()) {
839  CallInst *Call = cast<CallInst>(Inst);
840  const Value *Arg = Call->getArgOperand(0);
842  if (Arg) {
843  Changed = true;
844  ++NumAutoreleases;
845 
846  // Create the declaration lazily.
847  LLVMContext &C = Inst->getContext();
848 
850  CallInst *NewCall = CallInst::Create(Decl, Call->getArgOperand(0), "",
851  Call);
852  NewCall->setMetadata(MDKindCache.get(ARCMDKindID::ImpreciseRelease),
853  MDNode::get(C, None));
854 
855  LLVM_DEBUG(
856  dbgs() << "Replacing autorelease{,RV}(x) with objc_release(x) "
857  "since x is otherwise unused.\nOld: "
858  << *Call << "\nNew: " << *NewCall << "\n");
859 
860  EraseInstruction(Call);
861  Inst = NewCall;
862  Class = ARCInstKind::Release;
863  }
864  }
865 
866  // For functions which can never be passed stack arguments, add
867  // a tail keyword.
868  if (IsAlwaysTail(Class) && !cast<CallInst>(Inst)->isNoTailCall()) {
869  Changed = true;
870  LLVM_DEBUG(
871  dbgs() << "Adding tail keyword to function since it can never be "
872  "passed stack args: "
873  << *Inst << "\n");
874  cast<CallInst>(Inst)->setTailCall();
875  }
876 
877  // Ensure that functions that can never have a "tail" keyword due to the
878  // semantics of ARC truly do not do so.
879  if (IsNeverTail(Class)) {
880  Changed = true;
881  LLVM_DEBUG(dbgs() << "Removing tail keyword from function: " << *Inst
882  << "\n");
883  cast<CallInst>(Inst)->setTailCall(false);
884  }
885 
886  // Set nounwind as needed.
887  if (IsNoThrow(Class)) {
888  Changed = true;
889  LLVM_DEBUG(dbgs() << "Found no throw class. Setting nounwind on: "
890  << *Inst << "\n");
891  cast<CallInst>(Inst)->setDoesNotThrow();
892  }
893 
894  if (!IsNoopOnNull(Class)) {
895  UsedInThisFunction |= 1 << unsigned(Class);
896  continue;
897  }
898 
899  const Value *Arg = GetArgRCIdentityRoot(Inst);
900 
901  // ARC calls with null are no-ops. Delete them.
902  if (IsNullOrUndef(Arg)) {
903  Changed = true;
904  ++NumNoops;
905  LLVM_DEBUG(dbgs() << "ARC calls with null are no-ops. Erasing: " << *Inst
906  << "\n");
907  EraseInstruction(Inst);
908  continue;
909  }
910 
911  // Keep track of which of retain, release, autorelease, and retain_block
912  // are actually present in this function.
913  UsedInThisFunction |= 1 << unsigned(Class);
914 
915  // If Arg is a PHI, and one or more incoming values to the
916  // PHI are null, and the call is control-equivalent to the PHI, and there
917  // are no relevant side effects between the PHI and the call, and the call
918  // is not a release that doesn't have the clang.imprecise_release tag, the
919  // call could be pushed up to just those paths with non-null incoming
920  // values. For now, don't bother splitting critical edges for this.
921  if (Class == ARCInstKind::Release &&
922  !Inst->getMetadata(MDKindCache.get(ARCMDKindID::ImpreciseRelease)))
923  continue;
924 
926  Worklist.push_back(std::make_pair(Inst, Arg));
927  do {
928  std::pair<Instruction *, const Value *> Pair = Worklist.pop_back_val();
929  Inst = Pair.first;
930  Arg = Pair.second;
931 
932  const PHINode *PN = dyn_cast<PHINode>(Arg);
933  if (!PN) continue;
934 
935  // Determine if the PHI has any null operands, or any incoming
936  // critical edges.
937  bool HasNull = false;
938  bool HasCriticalEdges = false;
939  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
940  Value *Incoming =
942  if (IsNullOrUndef(Incoming))
943  HasNull = true;
944  else if (PN->getIncomingBlock(i)->getTerminator()->getNumSuccessors() !=
945  1) {
946  HasCriticalEdges = true;
947  break;
948  }
949  }
950  // If we have null operands and no critical edges, optimize.
951  if (!HasCriticalEdges && HasNull) {
952  SmallPtrSet<Instruction *, 4> DependingInstructions;
954 
955  // Check that there is nothing that cares about the reference
956  // count between the call and the phi.
957  switch (Class) {
958  case ARCInstKind::Retain:
960  // These can always be moved up.
961  break;
963  // These can't be moved across things that care about the retain
964  // count.
966  Inst->getParent(), Inst,
967  DependingInstructions, Visited, PA);
968  break;
970  // These can't be moved across autorelease pool scope boundaries.
972  Inst->getParent(), Inst,
973  DependingInstructions, Visited, PA);
974  break;
978  // Don't move these; the RV optimization depends on the autoreleaseRV
979  // being tail called, and the retainRV being immediately after a call
980  // (which might still happen if we get lucky with codegen layout, but
981  // it's not worth taking the chance).
982  continue;
983  default:
984  llvm_unreachable("Invalid dependence flavor");
985  }
986 
987  if (DependingInstructions.size() == 1 &&
988  *DependingInstructions.begin() == PN) {
989  Changed = true;
990  ++NumPartialNoops;
991  // Clone the call into each predecessor that has a non-null value.
992  CallInst *CInst = cast<CallInst>(Inst);
993  Type *ParamTy = CInst->getArgOperand(0)->getType();
994  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
995  Value *Incoming =
997  if (!IsNullOrUndef(Incoming)) {
998  Value *Op = PN->getIncomingValue(i);
999  Instruction *InsertPos = &PN->getIncomingBlock(i)->back();
1000  CallInst *Clone = cast<CallInst>(CloneCallInstForBB(
1001  *CInst, *InsertPos->getParent(), BlockColors));
1002  if (Op->getType() != ParamTy)
1003  Op = new BitCastInst(Op, ParamTy, "", InsertPos);
1004  Clone->setArgOperand(0, Op);
1005  Clone->insertBefore(InsertPos);
1006 
1007  LLVM_DEBUG(dbgs() << "Cloning " << *CInst
1008  << "\n"
1009  "And inserting clone at "
1010  << *InsertPos << "\n");
1011  Worklist.push_back(std::make_pair(Clone, Incoming));
1012  }
1013  }
1014  // Erase the original call.
1015  LLVM_DEBUG(dbgs() << "Erasing: " << *CInst << "\n");
1016  EraseInstruction(CInst);
1017  continue;
1018  }
1019  }
1020  } while (!Worklist.empty());
1021  }
1022 }
1023 
1024 /// If we have a top down pointer in the S_Use state, make sure that there are
1025 /// no CFG hazards by checking the states of various bottom up pointers.
1026 static void CheckForUseCFGHazard(const Sequence SuccSSeq,
1027  const bool SuccSRRIKnownSafe,
1028  TopDownPtrState &S,
1029  bool &SomeSuccHasSame,
1030  bool &AllSuccsHaveSame,
1031  bool &NotAllSeqEqualButKnownSafe,
1032  bool &ShouldContinue) {
1033  switch (SuccSSeq) {
1034  case S_CanRelease: {
1035  if (!S.IsKnownSafe() && !SuccSRRIKnownSafe) {
1037  break;
1038  }
1039  S.SetCFGHazardAfflicted(true);
1040  ShouldContinue = true;
1041  break;
1042  }
1043  case S_Use:
1044  SomeSuccHasSame = true;
1045  break;
1046  case S_Stop:
1047  case S_Release:
1048  case S_MovableRelease:
1049  if (!S.IsKnownSafe() && !SuccSRRIKnownSafe)
1050  AllSuccsHaveSame = false;
1051  else
1052  NotAllSeqEqualButKnownSafe = true;
1053  break;
1054  case S_Retain:
1055  llvm_unreachable("bottom-up pointer in retain state!");
1056  case S_None:
1057  llvm_unreachable("This should have been handled earlier.");
1058  }
1059 }
1060 
1061 /// If we have a Top Down pointer in the S_CanRelease state, make sure that
1062 /// there are no CFG hazards by checking the states of various bottom up
1063 /// pointers.
1064 static void CheckForCanReleaseCFGHazard(const Sequence SuccSSeq,
1065  const bool SuccSRRIKnownSafe,
1066  TopDownPtrState &S,
1067  bool &SomeSuccHasSame,
1068  bool &AllSuccsHaveSame,
1069  bool &NotAllSeqEqualButKnownSafe) {
1070  switch (SuccSSeq) {
1071  case S_CanRelease:
1072  SomeSuccHasSame = true;
1073  break;
1074  case S_Stop:
1075  case S_Release:
1076  case S_MovableRelease:
1077  case S_Use:
1078  if (!S.IsKnownSafe() && !SuccSRRIKnownSafe)
1079  AllSuccsHaveSame = false;
1080  else
1081  NotAllSeqEqualButKnownSafe = true;
1082  break;
1083  case S_Retain:
1084  llvm_unreachable("bottom-up pointer in retain state!");
1085  case S_None:
1086  llvm_unreachable("This should have been handled earlier.");
1087  }
1088 }
1089 
1090 /// Check for critical edges, loop boundaries, irreducible control flow, or
1091 /// other CFG structures where moving code across the edge would result in it
1092 /// being executed more.
1093 void
1094 ObjCARCOpt::CheckForCFGHazards(const BasicBlock *BB,
1096  BBState &MyStates) const {
1097  // If any top-down local-use or possible-dec has a succ which is earlier in
1098  // the sequence, forget it.
1099  for (auto I = MyStates.top_down_ptr_begin(), E = MyStates.top_down_ptr_end();
1100  I != E; ++I) {
1101  TopDownPtrState &S = I->second;
1102  const Sequence Seq = I->second.GetSeq();
1103 
1104  // We only care about S_Retain, S_CanRelease, and S_Use.
1105  if (Seq == S_None)
1106  continue;
1107 
1108  // Make sure that if extra top down states are added in the future that this
1109  // code is updated to handle it.
1110  assert((Seq == S_Retain || Seq == S_CanRelease || Seq == S_Use) &&
1111  "Unknown top down sequence state.");
1112 
1113  const Value *Arg = I->first;
1114  bool SomeSuccHasSame = false;
1115  bool AllSuccsHaveSame = true;
1116  bool NotAllSeqEqualButKnownSafe = false;
1117 
1118  for (const BasicBlock *Succ : successors(BB)) {
1119  // If VisitBottomUp has pointer information for this successor, take
1120  // what we know about it.
1122  BBStates.find(Succ);
1123  assert(BBI != BBStates.end());
1124  const BottomUpPtrState &SuccS = BBI->second.getPtrBottomUpState(Arg);
1125  const Sequence SuccSSeq = SuccS.GetSeq();
1126 
1127  // If bottom up, the pointer is in an S_None state, clear the sequence
1128  // progress since the sequence in the bottom up state finished
1129  // suggesting a mismatch in between retains/releases. This is true for
1130  // all three cases that we are handling here: S_Retain, S_Use, and
1131  // S_CanRelease.
1132  if (SuccSSeq == S_None) {
1134  continue;
1135  }
1136 
1137  // If we have S_Use or S_CanRelease, perform our check for cfg hazard
1138  // checks.
1139  const bool SuccSRRIKnownSafe = SuccS.IsKnownSafe();
1140 
1141  // *NOTE* We do not use Seq from above here since we are allowing for
1142  // S.GetSeq() to change while we are visiting basic blocks.
1143  switch(S.GetSeq()) {
1144  case S_Use: {
1145  bool ShouldContinue = false;
1146  CheckForUseCFGHazard(SuccSSeq, SuccSRRIKnownSafe, S, SomeSuccHasSame,
1147  AllSuccsHaveSame, NotAllSeqEqualButKnownSafe,
1148  ShouldContinue);
1149  if (ShouldContinue)
1150  continue;
1151  break;
1152  }
1153  case S_CanRelease:
1154  CheckForCanReleaseCFGHazard(SuccSSeq, SuccSRRIKnownSafe, S,
1155  SomeSuccHasSame, AllSuccsHaveSame,
1156  NotAllSeqEqualButKnownSafe);
1157  break;
1158  case S_Retain:
1159  case S_None:
1160  case S_Stop:
1161  case S_Release:
1162  case S_MovableRelease:
1163  break;
1164  }
1165  }
1166 
1167  // If the state at the other end of any of the successor edges
1168  // matches the current state, require all edges to match. This
1169  // guards against loops in the middle of a sequence.
1170  if (SomeSuccHasSame && !AllSuccsHaveSame) {
1172  } else if (NotAllSeqEqualButKnownSafe) {
1173  // If we would have cleared the state foregoing the fact that we are known
1174  // safe, stop code motion. This is because whether or not it is safe to
1175  // remove RR pairs via KnownSafe is an orthogonal concept to whether we
1176  // are allowed to perform code motion.
1177  S.SetCFGHazardAfflicted(true);
1178  }
1179  }
1180 }
1181 
1182 bool ObjCARCOpt::VisitInstructionBottomUp(
1184  BBState &MyStates) {
1185  bool NestingDetected = false;
1186  ARCInstKind Class = GetARCInstKind(Inst);
1187  const Value *Arg = nullptr;
1188 
1189  LLVM_DEBUG(dbgs() << " Class: " << Class << "\n");
1190 
1191  switch (Class) {
1192  case ARCInstKind::Release: {
1193  Arg = GetArgRCIdentityRoot(Inst);
1194 
1195  BottomUpPtrState &S = MyStates.getPtrBottomUpState(Arg);
1196  NestingDetected |= S.InitBottomUp(MDKindCache, Inst);
1197  break;
1198  }
1200  // In OptimizeIndividualCalls, we have strength reduced all optimizable
1201  // objc_retainBlocks to objc_retains. Thus at this point any
1202  // objc_retainBlocks that we see are not optimizable.
1203  break;
1204  case ARCInstKind::Retain:
1205  case ARCInstKind::RetainRV: {
1206  Arg = GetArgRCIdentityRoot(Inst);
1207  BottomUpPtrState &S = MyStates.getPtrBottomUpState(Arg);
1208  if (S.MatchWithRetain()) {
1209  // Don't do retain+release tracking for ARCInstKind::RetainRV, because
1210  // it's better to let it remain as the first instruction after a call.
1211  if (Class != ARCInstKind::RetainRV) {
1212  LLVM_DEBUG(dbgs() << " Matching with: " << *Inst << "\n");
1213  Retains[Inst] = S.GetRRInfo();
1214  }
1216  }
1217  // A retain moving bottom up can be a use.
1218  break;
1219  }
1221  // Conservatively, clear MyStates for all known pointers.
1222  MyStates.clearBottomUpPointers();
1223  return NestingDetected;
1225  case ARCInstKind::None:
1226  // These are irrelevant.
1227  return NestingDetected;
1228  default:
1229  break;
1230  }
1231 
1232  // Consider any other possible effects of this instruction on each
1233  // pointer being tracked.
1234  for (auto MI = MyStates.bottom_up_ptr_begin(),
1235  ME = MyStates.bottom_up_ptr_end();
1236  MI != ME; ++MI) {
1237  const Value *Ptr = MI->first;
1238  if (Ptr == Arg)
1239  continue; // Handled above.
1240  BottomUpPtrState &S = MI->second;
1241 
1242  if (S.HandlePotentialAlterRefCount(Inst, Ptr, PA, Class))
1243  continue;
1244 
1245  S.HandlePotentialUse(BB, Inst, Ptr, PA, Class);
1246  }
1247 
1248  return NestingDetected;
1249 }
1250 
1251 bool ObjCARCOpt::VisitBottomUp(BasicBlock *BB,
1253  BlotMapVector<Value *, RRInfo> &Retains) {
1254  LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::VisitBottomUp ==\n");
1255 
1256  bool NestingDetected = false;
1257  BBState &MyStates = BBStates[BB];
1258 
1259  // Merge the states from each successor to compute the initial state
1260  // for the current block.
1261  BBState::edge_iterator SI(MyStates.succ_begin()),
1262  SE(MyStates.succ_end());
1263  if (SI != SE) {
1264  const BasicBlock *Succ = *SI;
1266  assert(I != BBStates.end());
1267  MyStates.InitFromSucc(I->second);
1268  ++SI;
1269  for (; SI != SE; ++SI) {
1270  Succ = *SI;
1271  I = BBStates.find(Succ);
1272  assert(I != BBStates.end());
1273  MyStates.MergeSucc(I->second);
1274  }
1275  }
1276 
1277  LLVM_DEBUG(dbgs() << "Before:\n"
1278  << BBStates[BB] << "\n"
1279  << "Performing Dataflow:\n");
1280 
1281  // Visit all the instructions, bottom-up.
1282  for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; --I) {
1283  Instruction *Inst = &*std::prev(I);
1284 
1285  // Invoke instructions are visited as part of their successors (below).
1286  if (isa<InvokeInst>(Inst))
1287  continue;
1288 
1289  LLVM_DEBUG(dbgs() << " Visiting " << *Inst << "\n");
1290 
1291  NestingDetected |= VisitInstructionBottomUp(Inst, BB, Retains, MyStates);
1292 
1293  // Bail out if the number of pointers being tracked becomes too large so
1294  // that this pass can complete in a reasonable amount of time.
1295  if (MyStates.bottom_up_ptr_list_size() > MaxPtrStates) {
1296  DisableRetainReleasePairing = true;
1297  return false;
1298  }
1299  }
1300 
1301  // If there's a predecessor with an invoke, visit the invoke as if it were
1302  // part of this block, since we can't insert code after an invoke in its own
1303  // block, and we don't want to split critical edges.
1304  for (BBState::edge_iterator PI(MyStates.pred_begin()),
1305  PE(MyStates.pred_end()); PI != PE; ++PI) {
1306  BasicBlock *Pred = *PI;
1307  if (InvokeInst *II = dyn_cast<InvokeInst>(&Pred->back()))
1308  NestingDetected |= VisitInstructionBottomUp(II, BB, Retains, MyStates);
1309  }
1310 
1311  LLVM_DEBUG(dbgs() << "\nFinal State:\n" << BBStates[BB] << "\n");
1312 
1313  return NestingDetected;
1314 }
1315 
1316 bool
1317 ObjCARCOpt::VisitInstructionTopDown(Instruction *Inst,
1318  DenseMap<Value *, RRInfo> &Releases,
1319  BBState &MyStates) {
1320  bool NestingDetected = false;
1321  ARCInstKind Class = GetARCInstKind(Inst);
1322  const Value *Arg = nullptr;
1323 
1324  LLVM_DEBUG(dbgs() << " Class: " << Class << "\n");
1325 
1326  switch (Class) {
1328  // In OptimizeIndividualCalls, we have strength reduced all optimizable
1329  // objc_retainBlocks to objc_retains. Thus at this point any
1330  // objc_retainBlocks that we see are not optimizable. We need to break since
1331  // a retain can be a potential use.
1332  break;
1333  case ARCInstKind::Retain:
1334  case ARCInstKind::RetainRV: {
1335  Arg = GetArgRCIdentityRoot(Inst);
1336  TopDownPtrState &S = MyStates.getPtrTopDownState(Arg);
1337  NestingDetected |= S.InitTopDown(Class, Inst);
1338  // A retain can be a potential use; proceed to the generic checking
1339  // code below.
1340  break;
1341  }
1342  case ARCInstKind::Release: {
1343  Arg = GetArgRCIdentityRoot(Inst);
1344  TopDownPtrState &S = MyStates.getPtrTopDownState(Arg);
1345  // Try to form a tentative pair in between this release instruction and the
1346  // top down pointers that we are tracking.
1347  if (S.MatchWithRelease(MDKindCache, Inst)) {
1348  // If we succeed, copy S's RRInfo into the Release -> {Retain Set
1349  // Map}. Then we clear S.
1350  LLVM_DEBUG(dbgs() << " Matching with: " << *Inst << "\n");
1351  Releases[Inst] = S.GetRRInfo();
1353  }
1354  break;
1355  }
1357  // Conservatively, clear MyStates for all known pointers.
1358  MyStates.clearTopDownPointers();
1359  return false;
1361  case ARCInstKind::None:
1362  // These can not be uses of
1363  return false;
1364  default:
1365  break;
1366  }
1367 
1368  // Consider any other possible effects of this instruction on each
1369  // pointer being tracked.
1370  for (auto MI = MyStates.top_down_ptr_begin(),
1371  ME = MyStates.top_down_ptr_end();
1372  MI != ME; ++MI) {
1373  const Value *Ptr = MI->first;
1374  if (Ptr == Arg)
1375  continue; // Handled above.
1376  TopDownPtrState &S = MI->second;
1377  if (S.HandlePotentialAlterRefCount(Inst, Ptr, PA, Class))
1378  continue;
1379 
1380  S.HandlePotentialUse(Inst, Ptr, PA, Class);
1381  }
1382 
1383  return NestingDetected;
1384 }
1385 
1386 bool
1387 ObjCARCOpt::VisitTopDown(BasicBlock *BB,
1389  DenseMap<Value *, RRInfo> &Releases) {
1390  LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::VisitTopDown ==\n");
1391  bool NestingDetected = false;
1392  BBState &MyStates = BBStates[BB];
1393 
1394  // Merge the states from each predecessor to compute the initial state
1395  // for the current block.
1396  BBState::edge_iterator PI(MyStates.pred_begin()),
1397  PE(MyStates.pred_end());
1398  if (PI != PE) {
1399  const BasicBlock *Pred = *PI;
1401  assert(I != BBStates.end());
1402  MyStates.InitFromPred(I->second);
1403  ++PI;
1404  for (; PI != PE; ++PI) {
1405  Pred = *PI;
1406  I = BBStates.find(Pred);
1407  assert(I != BBStates.end());
1408  MyStates.MergePred(I->second);
1409  }
1410  }
1411 
1412  LLVM_DEBUG(dbgs() << "Before:\n"
1413  << BBStates[BB] << "\n"
1414  << "Performing Dataflow:\n");
1415 
1416  // Visit all the instructions, top-down.
1417  for (Instruction &Inst : *BB) {
1418  LLVM_DEBUG(dbgs() << " Visiting " << Inst << "\n");
1419 
1420  NestingDetected |= VisitInstructionTopDown(&Inst, Releases, MyStates);
1421 
1422  // Bail out if the number of pointers being tracked becomes too large so
1423  // that this pass can complete in a reasonable amount of time.
1424  if (MyStates.top_down_ptr_list_size() > MaxPtrStates) {
1425  DisableRetainReleasePairing = true;
1426  return false;
1427  }
1428  }
1429 
1430  LLVM_DEBUG(dbgs() << "\nState Before Checking for CFG Hazards:\n"
1431  << BBStates[BB] << "\n\n");
1432  CheckForCFGHazards(BB, BBStates, MyStates);
1433  LLVM_DEBUG(dbgs() << "Final State:\n" << BBStates[BB] << "\n");
1434  return NestingDetected;
1435 }
1436 
1437 static void
1439  SmallVectorImpl<BasicBlock *> &PostOrder,
1440  SmallVectorImpl<BasicBlock *> &ReverseCFGPostOrder,
1441  unsigned NoObjCARCExceptionsMDKind,
1443  /// The visited set, for doing DFS walks.
1445 
1446  // Do DFS, computing the PostOrder.
1449 
1450  // Functions always have exactly one entry block, and we don't have
1451  // any other block that we treat like an entry block.
1452  BasicBlock *EntryBB = &F.getEntryBlock();
1453  BBState &MyStates = BBStates[EntryBB];
1454  MyStates.SetAsEntry();
1455  Instruction *EntryTI = EntryBB->getTerminator();
1456  SuccStack.push_back(std::make_pair(EntryBB, succ_iterator(EntryTI)));
1457  Visited.insert(EntryBB);
1458  OnStack.insert(EntryBB);
1459  do {
1460  dfs_next_succ:
1461  BasicBlock *CurrBB = SuccStack.back().first;
1462  succ_iterator SE(CurrBB->getTerminator(), false);
1463 
1464  while (SuccStack.back().second != SE) {
1465  BasicBlock *SuccBB = *SuccStack.back().second++;
1466  if (Visited.insert(SuccBB).second) {
1467  SuccStack.push_back(
1468  std::make_pair(SuccBB, succ_iterator(SuccBB->getTerminator())));
1469  BBStates[CurrBB].addSucc(SuccBB);
1470  BBState &SuccStates = BBStates[SuccBB];
1471  SuccStates.addPred(CurrBB);
1472  OnStack.insert(SuccBB);
1473  goto dfs_next_succ;
1474  }
1475 
1476  if (!OnStack.count(SuccBB)) {
1477  BBStates[CurrBB].addSucc(SuccBB);
1478  BBStates[SuccBB].addPred(CurrBB);
1479  }
1480  }
1481  OnStack.erase(CurrBB);
1482  PostOrder.push_back(CurrBB);
1483  SuccStack.pop_back();
1484  } while (!SuccStack.empty());
1485 
1486  Visited.clear();
1487 
1488  // Do reverse-CFG DFS, computing the reverse-CFG PostOrder.
1489  // Functions may have many exits, and there also blocks which we treat
1490  // as exits due to ignored edges.
1492  for (BasicBlock &ExitBB : F) {
1493  BBState &MyStates = BBStates[&ExitBB];
1494  if (!MyStates.isExit())
1495  continue;
1496 
1497  MyStates.SetAsExit();
1498 
1499  PredStack.push_back(std::make_pair(&ExitBB, MyStates.pred_begin()));
1500  Visited.insert(&ExitBB);
1501  while (!PredStack.empty()) {
1502  reverse_dfs_next_succ:
1503  BBState::edge_iterator PE = BBStates[PredStack.back().first].pred_end();
1504  while (PredStack.back().second != PE) {
1505  BasicBlock *BB = *PredStack.back().second++;
1506  if (Visited.insert(BB).second) {
1507  PredStack.push_back(std::make_pair(BB, BBStates[BB].pred_begin()));
1508  goto reverse_dfs_next_succ;
1509  }
1510  }
1511  ReverseCFGPostOrder.push_back(PredStack.pop_back_val().first);
1512  }
1513  }
1514 }
1515 
1516 // Visit the function both top-down and bottom-up.
1517 bool ObjCARCOpt::Visit(Function &F,
1520  DenseMap<Value *, RRInfo> &Releases) {
1521  // Use reverse-postorder traversals, because we magically know that loops
1522  // will be well behaved, i.e. they won't repeatedly call retain on a single
1523  // pointer without doing a release. We can't use the ReversePostOrderTraversal
1524  // class here because we want the reverse-CFG postorder to consider each
1525  // function exit point, and we want to ignore selected cycle edges.
1527  SmallVector<BasicBlock *, 16> ReverseCFGPostOrder;
1528  ComputePostOrders(F, PostOrder, ReverseCFGPostOrder,
1529  MDKindCache.get(ARCMDKindID::NoObjCARCExceptions),
1530  BBStates);
1531 
1532  // Use reverse-postorder on the reverse CFG for bottom-up.
1533  bool BottomUpNestingDetected = false;
1534  for (BasicBlock *BB : llvm::reverse(ReverseCFGPostOrder)) {
1535  BottomUpNestingDetected |= VisitBottomUp(BB, BBStates, Retains);
1536  if (DisableRetainReleasePairing)
1537  return false;
1538  }
1539 
1540  // Use reverse-postorder for top-down.
1541  bool TopDownNestingDetected = false;
1542  for (BasicBlock *BB : llvm::reverse(PostOrder)) {
1543  TopDownNestingDetected |= VisitTopDown(BB, BBStates, Releases);
1544  if (DisableRetainReleasePairing)
1545  return false;
1546  }
1547 
1548  return TopDownNestingDetected && BottomUpNestingDetected;
1549 }
1550 
1551 /// Move the calls in RetainsToMove and ReleasesToMove.
1552 void ObjCARCOpt::MoveCalls(Value *Arg, RRInfo &RetainsToMove,
1553  RRInfo &ReleasesToMove,
1555  DenseMap<Value *, RRInfo> &Releases,
1556  SmallVectorImpl<Instruction *> &DeadInsts,
1557  Module *M) {
1558  Type *ArgTy = Arg->getType();
1559  Type *ParamTy = PointerType::getUnqual(Type::getInt8Ty(ArgTy->getContext()));
1560 
1561  LLVM_DEBUG(dbgs() << "== ObjCARCOpt::MoveCalls ==\n");
1562 
1563  // Insert the new retain and release calls.
1564  for (Instruction *InsertPt : ReleasesToMove.ReverseInsertPts) {
1565  Value *MyArg = ArgTy == ParamTy ? Arg :
1566  new BitCastInst(Arg, ParamTy, "", InsertPt);
1568  CallInst *Call = CallInst::Create(Decl, MyArg, "", InsertPt);
1569  Call->setDoesNotThrow();
1570  Call->setTailCall();
1571 
1572  LLVM_DEBUG(dbgs() << "Inserting new Retain: " << *Call
1573  << "\n"
1574  "At insertion point: "
1575  << *InsertPt << "\n");
1576  }
1577  for (Instruction *InsertPt : RetainsToMove.ReverseInsertPts) {
1578  Value *MyArg = ArgTy == ParamTy ? Arg :
1579  new BitCastInst(Arg, ParamTy, "", InsertPt);
1581  CallInst *Call = CallInst::Create(Decl, MyArg, "", InsertPt);
1582  // Attach a clang.imprecise_release metadata tag, if appropriate.
1583  if (MDNode *M = ReleasesToMove.ReleaseMetadata)
1584  Call->setMetadata(MDKindCache.get(ARCMDKindID::ImpreciseRelease), M);
1585  Call->setDoesNotThrow();
1586  if (ReleasesToMove.IsTailCallRelease)
1587  Call->setTailCall();
1588 
1589  LLVM_DEBUG(dbgs() << "Inserting new Release: " << *Call
1590  << "\n"
1591  "At insertion point: "
1592  << *InsertPt << "\n");
1593  }
1594 
1595  // Delete the original retain and release calls.
1596  for (Instruction *OrigRetain : RetainsToMove.Calls) {
1597  Retains.blot(OrigRetain);
1598  DeadInsts.push_back(OrigRetain);
1599  LLVM_DEBUG(dbgs() << "Deleting retain: " << *OrigRetain << "\n");
1600  }
1601  for (Instruction *OrigRelease : ReleasesToMove.Calls) {
1602  Releases.erase(OrigRelease);
1603  DeadInsts.push_back(OrigRelease);
1604  LLVM_DEBUG(dbgs() << "Deleting release: " << *OrigRelease << "\n");
1605  }
1606 }
1607 
1608 bool ObjCARCOpt::PairUpRetainsAndReleases(
1611  DenseMap<Value *, RRInfo> &Releases, Module *M,
1613  SmallVectorImpl<Instruction *> &DeadInsts, RRInfo &RetainsToMove,
1614  RRInfo &ReleasesToMove, Value *Arg, bool KnownSafe,
1615  bool &AnyPairsCompletelyEliminated) {
1616  // If a pair happens in a region where it is known that the reference count
1617  // is already incremented, we can similarly ignore possible decrements unless
1618  // we are dealing with a retainable object with multiple provenance sources.
1619  bool KnownSafeTD = true, KnownSafeBU = true;
1620  bool CFGHazardAfflicted = false;
1621 
1622  // Connect the dots between the top-down-collected RetainsToMove and
1623  // bottom-up-collected ReleasesToMove to form sets of related calls.
1624  // This is an iterative process so that we connect multiple releases
1625  // to multiple retains if needed.
1626  unsigned OldDelta = 0;
1627  unsigned NewDelta = 0;
1628  unsigned OldCount = 0;
1629  unsigned NewCount = 0;
1630  bool FirstRelease = true;
1631  for (SmallVector<Instruction *, 4> NewRetains{Retain};;) {
1632  SmallVector<Instruction *, 4> NewReleases;
1633  for (Instruction *NewRetain : NewRetains) {
1634  auto It = Retains.find(NewRetain);
1635  assert(It != Retains.end());
1636  const RRInfo &NewRetainRRI = It->second;
1637  KnownSafeTD &= NewRetainRRI.KnownSafe;
1638  CFGHazardAfflicted |= NewRetainRRI.CFGHazardAfflicted;
1639  for (Instruction *NewRetainRelease : NewRetainRRI.Calls) {
1640  auto Jt = Releases.find(NewRetainRelease);
1641  if (Jt == Releases.end())
1642  return false;
1643  const RRInfo &NewRetainReleaseRRI = Jt->second;
1644 
1645  // If the release does not have a reference to the retain as well,
1646  // something happened which is unaccounted for. Do not do anything.
1647  //
1648  // This can happen if we catch an additive overflow during path count
1649  // merging.
1650  if (!NewRetainReleaseRRI.Calls.count(NewRetain))
1651  return false;
1652 
1653  if (ReleasesToMove.Calls.insert(NewRetainRelease).second) {
1654  // If we overflow when we compute the path count, don't remove/move
1655  // anything.
1656  const BBState &NRRBBState = BBStates[NewRetainRelease->getParent()];
1657  unsigned PathCount = BBState::OverflowOccurredValue;
1658  if (NRRBBState.GetAllPathCountWithOverflow(PathCount))
1659  return false;
1660  assert(PathCount != BBState::OverflowOccurredValue &&
1661  "PathCount at this point can not be "
1662  "OverflowOccurredValue.");
1663  OldDelta -= PathCount;
1664 
1665  // Merge the ReleaseMetadata and IsTailCallRelease values.
1666  if (FirstRelease) {
1667  ReleasesToMove.ReleaseMetadata =
1668  NewRetainReleaseRRI.ReleaseMetadata;
1669  ReleasesToMove.IsTailCallRelease =
1670  NewRetainReleaseRRI.IsTailCallRelease;
1671  FirstRelease = false;
1672  } else {
1673  if (ReleasesToMove.ReleaseMetadata !=
1674  NewRetainReleaseRRI.ReleaseMetadata)
1675  ReleasesToMove.ReleaseMetadata = nullptr;
1676  if (ReleasesToMove.IsTailCallRelease !=
1677  NewRetainReleaseRRI.IsTailCallRelease)
1678  ReleasesToMove.IsTailCallRelease = false;
1679  }
1680 
1681  // Collect the optimal insertion points.
1682  if (!KnownSafe)
1683  for (Instruction *RIP : NewRetainReleaseRRI.ReverseInsertPts) {
1684  if (ReleasesToMove.ReverseInsertPts.insert(RIP).second) {
1685  // If we overflow when we compute the path count, don't
1686  // remove/move anything.
1687  const BBState &RIPBBState = BBStates[RIP->getParent()];
1688  PathCount = BBState::OverflowOccurredValue;
1689  if (RIPBBState.GetAllPathCountWithOverflow(PathCount))
1690  return false;
1691  assert(PathCount != BBState::OverflowOccurredValue &&
1692  "PathCount at this point can not be "
1693  "OverflowOccurredValue.");
1694  NewDelta -= PathCount;
1695  }
1696  }
1697  NewReleases.push_back(NewRetainRelease);
1698  }
1699  }
1700  }
1701  NewRetains.clear();
1702  if (NewReleases.empty()) break;
1703 
1704  // Back the other way.
1705  for (Instruction *NewRelease : NewReleases) {
1706  auto It = Releases.find(NewRelease);
1707  assert(It != Releases.end());
1708  const RRInfo &NewReleaseRRI = It->second;
1709  KnownSafeBU &= NewReleaseRRI.KnownSafe;
1710  CFGHazardAfflicted |= NewReleaseRRI.CFGHazardAfflicted;
1711  for (Instruction *NewReleaseRetain : NewReleaseRRI.Calls) {
1712  auto Jt = Retains.find(NewReleaseRetain);
1713  if (Jt == Retains.end())
1714  return false;
1715  const RRInfo &NewReleaseRetainRRI = Jt->second;
1716 
1717  // If the retain does not have a reference to the release as well,
1718  // something happened which is unaccounted for. Do not do anything.
1719  //
1720  // This can happen if we catch an additive overflow during path count
1721  // merging.
1722  if (!NewReleaseRetainRRI.Calls.count(NewRelease))
1723  return false;
1724 
1725  if (RetainsToMove.Calls.insert(NewReleaseRetain).second) {
1726  // If we overflow when we compute the path count, don't remove/move
1727  // anything.
1728  const BBState &NRRBBState = BBStates[NewReleaseRetain->getParent()];
1729  unsigned PathCount = BBState::OverflowOccurredValue;
1730  if (NRRBBState.GetAllPathCountWithOverflow(PathCount))
1731  return false;
1732  assert(PathCount != BBState::OverflowOccurredValue &&
1733  "PathCount at this point can not be "
1734  "OverflowOccurredValue.");
1735  OldDelta += PathCount;
1736  OldCount += PathCount;
1737 
1738  // Collect the optimal insertion points.
1739  if (!KnownSafe)
1740  for (Instruction *RIP : NewReleaseRetainRRI.ReverseInsertPts) {
1741  if (RetainsToMove.ReverseInsertPts.insert(RIP).second) {
1742  // If we overflow when we compute the path count, don't
1743  // remove/move anything.
1744  const BBState &RIPBBState = BBStates[RIP->getParent()];
1745 
1746  PathCount = BBState::OverflowOccurredValue;
1747  if (RIPBBState.GetAllPathCountWithOverflow(PathCount))
1748  return false;
1749  assert(PathCount != BBState::OverflowOccurredValue &&
1750  "PathCount at this point can not be "
1751  "OverflowOccurredValue.");
1752  NewDelta += PathCount;
1753  NewCount += PathCount;
1754  }
1755  }
1756  NewRetains.push_back(NewReleaseRetain);
1757  }
1758  }
1759  }
1760  if (NewRetains.empty()) break;
1761  }
1762 
1763  // We can only remove pointers if we are known safe in both directions.
1764  bool UnconditionallySafe = KnownSafeTD && KnownSafeBU;
1765  if (UnconditionallySafe) {
1766  RetainsToMove.ReverseInsertPts.clear();
1767  ReleasesToMove.ReverseInsertPts.clear();
1768  NewCount = 0;
1769  } else {
1770  // Determine whether the new insertion points we computed preserve the
1771  // balance of retain and release calls through the program.
1772  // TODO: If the fully aggressive solution isn't valid, try to find a
1773  // less aggressive solution which is.
1774  if (NewDelta != 0)
1775  return false;
1776 
1777  // At this point, we are not going to remove any RR pairs, but we still are
1778  // able to move RR pairs. If one of our pointers is afflicted with
1779  // CFGHazards, we cannot perform such code motion so exit early.
1780  const bool WillPerformCodeMotion =
1781  !RetainsToMove.ReverseInsertPts.empty() ||
1782  !ReleasesToMove.ReverseInsertPts.empty();
1783  if (CFGHazardAfflicted && WillPerformCodeMotion)
1784  return false;
1785  }
1786 
1787  // Determine whether the original call points are balanced in the retain and
1788  // release calls through the program. If not, conservatively don't touch
1789  // them.
1790  // TODO: It's theoretically possible to do code motion in this case, as
1791  // long as the existing imbalances are maintained.
1792  if (OldDelta != 0)
1793  return false;
1794 
1795  Changed = true;
1796  assert(OldCount != 0 && "Unreachable code?");
1797  NumRRs += OldCount - NewCount;
1798  // Set to true if we completely removed any RR pairs.
1799  AnyPairsCompletelyEliminated = NewCount == 0;
1800 
1801  // We can move calls!
1802  return true;
1803 }
1804 
1805 /// Identify pairings between the retains and releases, and delete and/or move
1806 /// them.
1807 bool ObjCARCOpt::PerformCodePlacement(
1810  DenseMap<Value *, RRInfo> &Releases, Module *M) {
1811  LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::PerformCodePlacement ==\n");
1812 
1813  bool AnyPairsCompletelyEliminated = false;
1815 
1816  // Visit each retain.
1818  E = Retains.end();
1819  I != E; ++I) {
1820  Value *V = I->first;
1821  if (!V) continue; // blotted
1822 
1823  Instruction *Retain = cast<Instruction>(V);
1824 
1825  LLVM_DEBUG(dbgs() << "Visiting: " << *Retain << "\n");
1826 
1827  Value *Arg = GetArgRCIdentityRoot(Retain);
1828 
1829  // If the object being released is in static or stack storage, we know it's
1830  // not being managed by ObjC reference counting, so we can delete pairs
1831  // regardless of what possible decrements or uses lie between them.
1832  bool KnownSafe = isa<Constant>(Arg) || isa<AllocaInst>(Arg);
1833 
1834  // A constant pointer can't be pointing to an object on the heap. It may
1835  // be reference-counted, but it won't be deleted.
1836  if (const LoadInst *LI = dyn_cast<LoadInst>(Arg))
1837  if (const GlobalVariable *GV =
1838  dyn_cast<GlobalVariable>(
1839  GetRCIdentityRoot(LI->getPointerOperand())))
1840  if (GV->isConstant())
1841  KnownSafe = true;
1842 
1843  // Connect the dots between the top-down-collected RetainsToMove and
1844  // bottom-up-collected ReleasesToMove to form sets of related calls.
1845  RRInfo RetainsToMove, ReleasesToMove;
1846 
1847  bool PerformMoveCalls = PairUpRetainsAndReleases(
1848  BBStates, Retains, Releases, M, Retain, DeadInsts,
1849  RetainsToMove, ReleasesToMove, Arg, KnownSafe,
1850  AnyPairsCompletelyEliminated);
1851 
1852  if (PerformMoveCalls) {
1853  // Ok, everything checks out and we're all set. Let's move/delete some
1854  // code!
1855  MoveCalls(Arg, RetainsToMove, ReleasesToMove,
1856  Retains, Releases, DeadInsts, M);
1857  }
1858  }
1859 
1860  // Now that we're done moving everything, we can delete the newly dead
1861  // instructions, as we no longer need them as insert points.
1862  while (!DeadInsts.empty())
1863  EraseInstruction(DeadInsts.pop_back_val());
1864 
1865  return AnyPairsCompletelyEliminated;
1866 }
1867 
1868 /// Weak pointer optimizations.
1869 void ObjCARCOpt::OptimizeWeakCalls(Function &F) {
1870  LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeWeakCalls ==\n");
1871 
1872  // First, do memdep-style RLE and S2L optimizations. We can't use memdep
1873  // itself because it uses AliasAnalysis and we need to do provenance
1874  // queries instead.
1875  for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
1876  Instruction *Inst = &*I++;
1877 
1878  LLVM_DEBUG(dbgs() << "Visiting: " << *Inst << "\n");
1879 
1880  ARCInstKind Class = GetBasicARCInstKind(Inst);
1881  if (Class != ARCInstKind::LoadWeak &&
1883  continue;
1884 
1885  // Delete objc_loadWeak calls with no users.
1886  if (Class == ARCInstKind::LoadWeak && Inst->use_empty()) {
1887  Inst->eraseFromParent();
1888  continue;
1889  }
1890 
1891  // TODO: For now, just look for an earlier available version of this value
1892  // within the same block. Theoretically, we could do memdep-style non-local
1893  // analysis too, but that would want caching. A better approach would be to
1894  // use the technique that EarlyCSE uses.
1895  inst_iterator Current = std::prev(I);
1896  BasicBlock *CurrentBB = &*Current.getBasicBlockIterator();
1897  for (BasicBlock::iterator B = CurrentBB->begin(),
1898  J = Current.getInstructionIterator();
1899  J != B; --J) {
1900  Instruction *EarlierInst = &*std::prev(J);
1901  ARCInstKind EarlierClass = GetARCInstKind(EarlierInst);
1902  switch (EarlierClass) {
1903  case ARCInstKind::LoadWeak:
1905  // If this is loading from the same pointer, replace this load's value
1906  // with that one.
1907  CallInst *Call = cast<CallInst>(Inst);
1908  CallInst *EarlierCall = cast<CallInst>(EarlierInst);
1909  Value *Arg = Call->getArgOperand(0);
1910  Value *EarlierArg = EarlierCall->getArgOperand(0);
1911  switch (PA.getAA()->alias(Arg, EarlierArg)) {
1912  case MustAlias:
1913  Changed = true;
1914  // If the load has a builtin retain, insert a plain retain for it.
1915  if (Class == ARCInstKind::LoadWeakRetained) {
1917  CallInst *CI = CallInst::Create(Decl, EarlierCall, "", Call);
1918  CI->setTailCall();
1919  }
1920  // Zap the fully redundant load.
1921  Call->replaceAllUsesWith(EarlierCall);
1922  Call->eraseFromParent();
1923  goto clobbered;
1924  case MayAlias:
1925  case PartialAlias:
1926  goto clobbered;
1927  case NoAlias:
1928  break;
1929  }
1930  break;
1931  }
1933  case ARCInstKind::InitWeak: {
1934  // If this is storing to the same pointer and has the same size etc.
1935  // replace this load's value with the stored value.
1936  CallInst *Call = cast<CallInst>(Inst);
1937  CallInst *EarlierCall = cast<CallInst>(EarlierInst);
1938  Value *Arg = Call->getArgOperand(0);
1939  Value *EarlierArg = EarlierCall->getArgOperand(0);
1940  switch (PA.getAA()->alias(Arg, EarlierArg)) {
1941  case MustAlias:
1942  Changed = true;
1943  // If the load has a builtin retain, insert a plain retain for it.
1944  if (Class == ARCInstKind::LoadWeakRetained) {
1946  CallInst *CI = CallInst::Create(Decl, EarlierCall, "", Call);
1947  CI->setTailCall();
1948  }
1949  // Zap the fully redundant load.
1950  Call->replaceAllUsesWith(EarlierCall->getArgOperand(1));
1951  Call->eraseFromParent();
1952  goto clobbered;
1953  case MayAlias:
1954  case PartialAlias:
1955  goto clobbered;
1956  case NoAlias:
1957  break;
1958  }
1959  break;
1960  }
1961  case ARCInstKind::MoveWeak:
1962  case ARCInstKind::CopyWeak:
1963  // TOOD: Grab the copied value.
1964  goto clobbered;
1966  case ARCInstKind::None:
1968  case ARCInstKind::User:
1969  // Weak pointers are only modified through the weak entry points
1970  // (and arbitrary calls, which could call the weak entry points).
1971  break;
1972  default:
1973  // Anything else could modify the weak pointer.
1974  goto clobbered;
1975  }
1976  }
1977  clobbered:;
1978  }
1979 
1980  // Then, for each destroyWeak with an alloca operand, check to see if
1981  // the alloca and all its users can be zapped.
1982  for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
1983  Instruction *Inst = &*I++;
1984  ARCInstKind Class = GetBasicARCInstKind(Inst);
1985  if (Class != ARCInstKind::DestroyWeak)
1986  continue;
1987 
1988  CallInst *Call = cast<CallInst>(Inst);
1989  Value *Arg = Call->getArgOperand(0);
1990  if (AllocaInst *Alloca = dyn_cast<AllocaInst>(Arg)) {
1991  for (User *U : Alloca->users()) {
1992  const Instruction *UserInst = cast<Instruction>(U);
1993  switch (GetBasicARCInstKind(UserInst)) {
1994  case ARCInstKind::InitWeak:
1997  continue;
1998  default:
1999  goto done;
2000  }
2001  }
2002  Changed = true;
2003  for (auto UI = Alloca->user_begin(), UE = Alloca->user_end(); UI != UE;) {
2004  CallInst *UserInst = cast<CallInst>(*UI++);
2005  switch (GetBasicARCInstKind(UserInst)) {
2006  case ARCInstKind::InitWeak:
2008  // These functions return their second argument.
2009  UserInst->replaceAllUsesWith(UserInst->getArgOperand(1));
2010  break;
2012  // No return value.
2013  break;
2014  default:
2015  llvm_unreachable("alloca really is used!");
2016  }
2017  UserInst->eraseFromParent();
2018  }
2019  Alloca->eraseFromParent();
2020  done:;
2021  }
2022  }
2023 }
2024 
2025 /// Identify program paths which execute sequences of retains and releases which
2026 /// can be eliminated.
2027 bool ObjCARCOpt::OptimizeSequences(Function &F) {
2028  // Releases, Retains - These are used to store the results of the main flow
2029  // analysis. These use Value* as the key instead of Instruction* so that the
2030  // map stays valid when we get around to rewriting code and calls get
2031  // replaced by arguments.
2032  DenseMap<Value *, RRInfo> Releases;
2034 
2035  // This is used during the traversal of the function to track the
2036  // states for each identified object at each block.
2038 
2039  // Analyze the CFG of the function, and all instructions.
2040  bool NestingDetected = Visit(F, BBStates, Retains, Releases);
2041 
2042  if (DisableRetainReleasePairing)
2043  return false;
2044 
2045  // Transform.
2046  bool AnyPairsCompletelyEliminated = PerformCodePlacement(BBStates, Retains,
2047  Releases,
2048  F.getParent());
2049 
2050  return AnyPairsCompletelyEliminated && NestingDetected;
2051 }
2052 
2053 /// Check if there is a dependent call earlier that does not have anything in
2054 /// between the Retain and the call that can affect the reference count of their
2055 /// shared pointer argument. Note that Retain need not be in BB.
2056 static bool
2060  ProvenanceAnalysis &PA) {
2062  DepInsts, Visited, PA);
2063  if (DepInsts.size() != 1)
2064  return false;
2065 
2066  auto *Call = dyn_cast_or_null<CallInst>(*DepInsts.begin());
2067 
2068  // Check that the pointer is the return value of the call.
2069  if (!Call || Arg != Call)
2070  return false;
2071 
2072  // Check that the call is a regular call.
2074  return Class == ARCInstKind::CallOrUser || Class == ARCInstKind::Call;
2075 }
2076 
2077 /// Find a dependent retain that precedes the given autorelease for which there
2078 /// is nothing in between the two instructions that can affect the ref count of
2079 /// Arg.
2080 static CallInst *
2085  ProvenanceAnalysis &PA) {
2087  BB, Autorelease, DepInsts, Visited, PA);
2088  if (DepInsts.size() != 1)
2089  return nullptr;
2090 
2091  auto *Retain = dyn_cast_or_null<CallInst>(*DepInsts.begin());
2092 
2093  // Check that we found a retain with the same argument.
2094  if (!Retain || !IsRetain(GetBasicARCInstKind(Retain)) ||
2095  GetArgRCIdentityRoot(Retain) != Arg) {
2096  return nullptr;
2097  }
2098 
2099  return Retain;
2100 }
2101 
2102 /// Look for an ``autorelease'' instruction dependent on Arg such that there are
2103 /// no instructions dependent on Arg that need a positive ref count in between
2104 /// the autorelease and the ret.
2105 static CallInst *
2107  ReturnInst *Ret,
2110  ProvenanceAnalysis &PA) {
2112  BB, Ret, DepInsts, V, PA);
2113  if (DepInsts.size() != 1)
2114  return nullptr;
2115 
2116  auto *Autorelease = dyn_cast_or_null<CallInst>(*DepInsts.begin());
2117  if (!Autorelease)
2118  return nullptr;
2119  ARCInstKind AutoreleaseClass = GetBasicARCInstKind(Autorelease);
2120  if (!IsAutorelease(AutoreleaseClass))
2121  return nullptr;
2122  if (GetArgRCIdentityRoot(Autorelease) != Arg)
2123  return nullptr;
2124 
2125  return Autorelease;
2126 }
2127 
2128 /// Look for this pattern:
2129 /// \code
2130 /// %call = call i8* @something(...)
2131 /// %2 = call i8* @objc_retain(i8* %call)
2132 /// %3 = call i8* @objc_autorelease(i8* %2)
2133 /// ret i8* %3
2134 /// \endcode
2135 /// And delete the retain and autorelease.
2136 void ObjCARCOpt::OptimizeReturns(Function &F) {
2137  if (!F.getReturnType()->isPointerTy())
2138  return;
2139 
2140  LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeReturns ==\n");
2141 
2142  SmallPtrSet<Instruction *, 4> DependingInstructions;
2144  for (BasicBlock &BB: F) {
2145  ReturnInst *Ret = dyn_cast<ReturnInst>(&BB.back());
2146  if (!Ret)
2147  continue;
2148 
2149  LLVM_DEBUG(dbgs() << "Visiting: " << *Ret << "\n");
2150 
2151  const Value *Arg = GetRCIdentityRoot(Ret->getOperand(0));
2152 
2153  // Look for an ``autorelease'' instruction that is a predecessor of Ret and
2154  // dependent on Arg such that there are no instructions dependent on Arg
2155  // that need a positive ref count in between the autorelease and Ret.
2157  Arg, &BB, Ret, DependingInstructions, Visited, PA);
2158  DependingInstructions.clear();
2159  Visited.clear();
2160 
2161  if (!Autorelease)
2162  continue;
2163 
2165  Arg, Autorelease->getParent(), Autorelease, DependingInstructions,
2166  Visited, PA);
2167  DependingInstructions.clear();
2168  Visited.clear();
2169 
2170  if (!Retain)
2171  continue;
2172 
2173  // Check that there is nothing that can affect the reference count
2174  // between the retain and the call. Note that Retain need not be in BB.
2175  bool HasSafePathToCall = HasSafePathToPredecessorCall(Arg, Retain,
2176  DependingInstructions,
2177  Visited, PA);
2178  DependingInstructions.clear();
2179  Visited.clear();
2180 
2181  if (!HasSafePathToCall)
2182  continue;
2183 
2184  // If so, we can zap the retain and autorelease.
2185  Changed = true;
2186  ++NumRets;
2187  LLVM_DEBUG(dbgs() << "Erasing: " << *Retain << "\nErasing: " << *Autorelease
2188  << "\n");
2189  EraseInstruction(Retain);
2190  EraseInstruction(Autorelease);
2191  }
2192 }
2193 
2194 #ifndef NDEBUG
2195 void
2196 ObjCARCOpt::GatherStatistics(Function &F, bool AfterOptimization) {
2197  Statistic &NumRetains =
2198  AfterOptimization ? NumRetainsAfterOpt : NumRetainsBeforeOpt;
2199  Statistic &NumReleases =
2200  AfterOptimization ? NumReleasesAfterOpt : NumReleasesBeforeOpt;
2201 
2202  for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
2203  Instruction *Inst = &*I++;
2204  switch (GetBasicARCInstKind(Inst)) {
2205  default:
2206  break;
2207  case ARCInstKind::Retain:
2208  ++NumRetains;
2209  break;
2210  case ARCInstKind::Release:
2211  ++NumReleases;
2212  break;
2213  }
2214  }
2215 }
2216 #endif
2217 
2218 bool ObjCARCOpt::doInitialization(Module &M) {
2219  if (!EnableARCOpts)
2220  return false;
2221 
2222  // If nothing in the Module uses ARC, don't do anything.
2223  Run = ModuleHasARC(M);
2224  if (!Run)
2225  return false;
2226 
2227  // Intuitively, objc_retain and others are nocapture, however in practice
2228  // they are not, because they return their argument value. And objc_release
2229  // calls finalizers which can have arbitrary side effects.
2230  MDKindCache.init(&M);
2231 
2232  // Initialize our runtime entry point cache.
2233  EP.init(&M);
2234 
2235  return false;
2236 }
2237 
2239  if (!EnableARCOpts)
2240  return false;
2241 
2242  // If nothing in the Module uses ARC, don't do anything.
2243  if (!Run)
2244  return false;
2245 
2246  Changed = false;
2247 
2248  LLVM_DEBUG(dbgs() << "<<< ObjCARCOpt: Visiting Function: " << F.getName()
2249  << " >>>"
2250  "\n");
2251 
2252  PA.setAA(&getAnalysis<AAResultsWrapperPass>().getAAResults());
2253 
2254 #ifndef NDEBUG
2255  if (AreStatisticsEnabled()) {
2256  GatherStatistics(F, false);
2257  }
2258 #endif
2259 
2260  // This pass performs several distinct transformations. As a compile-time aid
2261  // when compiling code that isn't ObjC, skip these if the relevant ObjC
2262  // library functions aren't declared.
2263 
2264  // Preliminary optimizations. This also computes UsedInThisFunction.
2265  OptimizeIndividualCalls(F);
2266 
2267  // Optimizations for weak pointers.
2268  if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::LoadWeak)) |
2269  (1 << unsigned(ARCInstKind::LoadWeakRetained)) |
2270  (1 << unsigned(ARCInstKind::StoreWeak)) |
2271  (1 << unsigned(ARCInstKind::InitWeak)) |
2272  (1 << unsigned(ARCInstKind::CopyWeak)) |
2273  (1 << unsigned(ARCInstKind::MoveWeak)) |
2274  (1 << unsigned(ARCInstKind::DestroyWeak))))
2275  OptimizeWeakCalls(F);
2276 
2277  // Optimizations for retain+release pairs.
2278  if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::Retain)) |
2279  (1 << unsigned(ARCInstKind::RetainRV)) |
2280  (1 << unsigned(ARCInstKind::RetainBlock))))
2281  if (UsedInThisFunction & (1 << unsigned(ARCInstKind::Release)))
2282  // Run OptimizeSequences until it either stops making changes or
2283  // no retain+release pair nesting is detected.
2284  while (OptimizeSequences(F)) {}
2285 
2286  // Optimizations if objc_autorelease is used.
2287  if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::Autorelease)) |
2288  (1 << unsigned(ARCInstKind::AutoreleaseRV))))
2289  OptimizeReturns(F);
2290 
2291  // Gather statistics after optimization.
2292 #ifndef NDEBUG
2293  if (AreStatisticsEnabled()) {
2294  GatherStatistics(F, true);
2295  }
2296 #endif
2297 
2298  LLVM_DEBUG(dbgs() << "\n");
2299 
2300  return Changed;
2301 }
2302 
2303 void ObjCARCOpt::releaseMemory() {
2304  PA.clear();
2305 }
2306 
2307 /// @}
2308 ///
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
uint64_t CallInst * C
Return a value (possibly void), from a function.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:67
Sequence GetSeq() const
Definition: PtrState.h:150
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:645
This file declares special dependency analysis routines used in Objective C ARC Optimizations.
ARCInstKind GetARCInstKind(const Value *V)
Map V to its ARCInstKind equivalence class.
objc_destroyWeak (derived)
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
SmallPtrSet< Instruction *, 2 > Calls
For a top-down sequence, the set of objc_retains or objc_retainBlocks.
Definition: PtrState.h:80
This file contains a class ARCRuntimeEntryPoints for use in creating/managing references to entry poi...
This class represents lattice values for constants.
Definition: AllocatorList.h:23
objc_loadWeakRetained (primitive)
typename VectorTy::const_iterator const_iterator
Definition: BlotMapVector.h:48
could call objc_release and/or "use" pointers
static char ID
EltTy front() const
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
bool IsTrackingImpreciseReleases() const
Definition: PtrState.h:129
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
bool HandlePotentialAlterRefCount(Instruction *Inst, const Value *Ptr, ProvenanceAnalysis &PA, ARCInstKind Class)
Definition: PtrState.cpp:228
objc_loadWeak (derived)
This class represents a function call, abstracting a target machine&#39;s calling convention.
objc_retainedObject, etc.
This file contains the declarations for metadata subclasses.
Value * GetArgRCIdentityRoot(Value *Inst)
Assuming the given instruction is one of the special calls such as objc_retain or objc_release...
The two locations do not alias at all.
Definition: AliasAnalysis.h:84
any use of x.
Definition: PtrState.h:44
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:709
bool MatchWithRelease(ARCMDKindCache &Cache, Instruction *Release)
Return true if this set of retains can be paired with the given release.
Definition: PtrState.cpp:347
STATISTIC(NumFunctions, "Total number of functions")
void setArgOperand(unsigned i, Value *v)
Definition: InstrTypes.h:1223
Metadata node.
Definition: Metadata.h:863
F(f)
could call objc_release
void initializeObjCARCOptPass(PassRegistry &)
An instruction for reading from memory.
Definition: Instructions.h:167
Hexagon Common GEP
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:137
iv Induction Variable Users
Definition: IVUsers.cpp:51
OperandBundleUse getOperandBundleAt(unsigned Index) const
Return the operand bundle at a specific index.
Definition: InstrTypes.h:1748
SmallPtrSet< Instruction *, 2 > ReverseInsertPts
The set of optimal insert positions for moving calls in the opposite sequence.
Definition: PtrState.h:84
TinyPtrVector - This class is specialized for cases where there are normally 0 or 1 element in a vect...
Definition: TinyPtrVector.h:30
objc_moveWeak (derived)
bool IsNoopOnNull(ARCInstKind Class)
Test if the given class represents instructions which do nothing if passed a null pointer...
bool IsForwarding(ARCInstKind Class)
Test if the given class represents instructions which return their argument verbatim.
bool IsObjCIdentifiedObject(const Value *V)
Return true if this value refers to a distinct and identifiable object.
static cl::opt< unsigned > MaxPtrStates("arc-opt-max-ptr-states", cl::Hidden, cl::desc("Maximum number of ptr states the optimizer keeps track of"), cl::init(4095))
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
Definition: Type.h:129
static Constant * getNullValue(Type *Ty)
Constructor to create a &#39;0&#39; constant of arbitrary type.
Definition: Constants.cpp:274
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:268
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1218
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
bool HasKnownPositiveRefCount() const
Definition: PtrState.h:146
objc_autoreleaseReturnValue
inst_iterator inst_begin(Function *F)
Definition: InstIterator.h:131
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
This class summarizes several per-pointer runtime properties which are propagated through the flow gr...
Definition: PtrState.h:101
ELFYAML::ELF_STO Other
Definition: ELFYAML.cpp:851
bool IsNullOrUndef(const Value *V)
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:102
This file defines common definitions/declarations used by the ObjC ARC Optimizer. ...
bool isScopedEHPersonality(EHPersonality Pers)
Returns true if this personality uses scope-style EH IR instructions: catchswitch, catchpad/ret, and cleanuppad/ret.
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
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:266
InstrTy * getInstruction() const
Definition: CallSite.h:96
objc_retainAutoreleasedReturnValue
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:244
static bool setDoesNotThrow(Function &F)
void setCalledFunction(Function *Fn)
Sets the function called, including updating the function type.
Definition: InstrTypes.h:1300
bool EnableARCOpts
A handy option to enable/disable all ARC Optimizations.
This class represents a no-op cast from one type to another.
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
An instruction for storing to memory.
Definition: Instructions.h:320
bool hasPersonalityFn() const
Check whether this function has a personality function.
Definition: Function.h:707
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:429
bool IsAlwaysTail(ARCInstKind Class)
Test if the given class represents instructions which are always safe to mark with the "tail" keyword...
unsigned getNumOperandBundles() const
Return the number of operand bundles associated with this User.
Definition: InstrTypes.h:1699
BBIty & getBasicBlockIterator()
Definition: InstIterator.h:73
bool ModuleHasARC(const Module &M)
Test if the given module looks interesting to run ARC optimization on.
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
Value * getOperand(unsigned i) const
Definition: User.h:169
Unidirectional information about either a retain-decrement-use-release sequence or release-use-decrem...
Definition: PtrState.h:56
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:105
raw_ostream & operator<<(raw_ostream &OS, const ARCInstKind Class)
const BasicBlock & getEntryBlock() const
Definition: Function.h:645
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:873
iterator find(const KeyT &Key)
Definition: BlotMapVector.h:79
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata *> MDs)
Definition: Metadata.h:1165
static bool runOnFunction(Function &F, bool PostInlining)
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
Type * getReturnType() const
Returns the type of the ret val.
Definition: Function.h:168
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
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction...
Definition: Instruction.cpp:73
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:64
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
objc_initWeak (derived)
This file contains the declarations for the subclasses of Constant, which represent the different fla...
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:223
BIty & getInstructionIterator()
Definition: InstIterator.h:74
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:370
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:112
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &InsertPair)
Definition: BlotMapVector.h:67
like S_Release, but code motion is stopped.
Definition: PtrState.h:45
EHPersonality classifyEHPersonality(const Value *Pers)
See if the given exception handling personality function is one that we understand.
Represent the analysis usage information of a pass.
const Instruction & back() const
Definition: BasicBlock.h:282
#define LLVM_ATTRIBUTE_UNUSED
Definition: Compiler.h:159
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:115
static const Value * FindSingleUseIdentifiedObject(const Value *Arg)
This is similar to GetRCIdentityRoot but it stops as soon as it finds a value with multiple uses...
Definition: ObjCARCOpts.cpp:86
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:381
self_iterator getIterator()
Definition: ilist_node.h:81
A cache of MDKinds used by various ARC optimizations.
static CallInst * FindPredecessorAutoreleaseWithSafePath(const Value *Arg, BasicBlock *BB, ReturnInst *Ret, SmallPtrSetImpl< Instruction *> &DepInsts, SmallPtrSetImpl< const BasicBlock *> &V, ProvenanceAnalysis &PA)
Look for an ``autorelease&#39;&#39; instruction dependent on Arg such that there are no instructions dependen...
objc_copyWeak (derived)
bool MatchWithRetain()
Return true if this set of releases can be paired with a release.
Definition: PtrState.cpp:204
static void CheckForCanReleaseCFGHazard(const Sequence SuccSSeq, const bool SuccSRRIKnownSafe, TopDownPtrState &S, bool &SomeSuccHasSame, bool &AllSuccsHaveSame, bool &NotAllSeqEqualButKnownSafe)
If we have a Top Down pointer in the S_CanRelease state, make sure that there are no CFG hazards by c...
void setTailCall(bool isTC=true)
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1424
This file defines common analysis utilities used by the ObjC ARC Optimizer.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
anything that is inert from an ARC perspective.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
This file declares a simple ARC-aware AliasAnalysis using special knowledge of Objective C to enhance...
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1222
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
bool IsCFGHazardAfflicted() const
Definition: PtrState.h:137
The two locations may or may not alias. This is the least precise result.
Definition: AliasAnalysis.h:86
size_type size() const
Definition: SmallPtrSet.h:92
The two locations precisely alias each other.
Definition: AliasAnalysis.h:90
static void EraseInstruction(Instruction *CI)
Erase the given instruction.
Definition: ObjCARC.h:51
Iterator for intrusive lists based on ilist_node.
objc_release(x).
Definition: PtrState.h:46
static PointerType * getUnqual(Type *ElementType)
This constructs a pointer to an object of the specified type in the generic address space (address sp...
Definition: DerivedTypes.h:513
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false...
Definition: SmallPtrSet.h:377
iterator end()
Definition: BasicBlock.h:270
This file declares a special form of Alias Analysis called ``Provenance Analysis&#39;&#39;.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:841
ARCInstKind
Equivalence classes of instructions in the ARC Model.
An associative container with fast insertion-order (deterministic) iteration over its elements...
Definition: BlotMapVector.h:22
bool IsNoThrow(ARCInstKind Class)
Test if the given class represents instructions which are always safe to mark with the nounwind attri...
objc_unsafeClaimAutoreleasedReturnValue
bool HandlePotentialAlterRefCount(Instruction *Inst, const Value *Ptr, ProvenanceAnalysis &PA, ARCInstKind Class)
Definition: PtrState.cpp:376
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:374
objc_retain(x).
Definition: PtrState.h:42
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:301
unsigned getNumIncomingValues() const
Return the number of incoming edges.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
Implements a dense probed hash-table based set with some number of buckets stored inline...
Definition: DenseSet.h:267
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
Pass * createObjCARCOptPass()
void FindDependencies(DependenceKind Flavor, const Value *Arg, BasicBlock *StartBB, Instruction *StartInst, SmallPtrSetImpl< Instruction *> &DependingInstructions, SmallPtrSetImpl< const BasicBlock *> &Visited, ProvenanceAnalysis &PA)
Walk up the CFG from StartPos (which is in StartBB) and find local and non-local dependencies on Arg...
iterator_range< user_iterator > users()
Definition: Value.h:399
could "use" a pointer
void ClearSequenceProgress()
Definition: PtrState.h:152
bool IsRetain(ARCInstKind Class)
Test if the given class is objc_retain or equivalent.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
static bool HasSafePathToPredecessorCall(const Value *Arg, Instruction *Retain, SmallPtrSetImpl< Instruction *> &DepInsts, SmallPtrSetImpl< const BasicBlock *> &Visited, ProvenanceAnalysis &PA)
Check if there is a dependent call earlier that does not have anything in between the Retain and the ...
bool empty() const
SuccIterator< Instruction, BasicBlock > succ_iterator
Definition: CFG.h:240
const RRInfo & GetRRInfo() const
Definition: PtrState.h:165
iterator begin() const
Definition: SmallPtrSet.h:396
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
Establish a view to a call site for examination.
Definition: CallSite.h:892
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
#define I(x, y, z)
Definition: MD5.cpp:58
objc_storeWeak (primitive)
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
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
static void CheckForUseCFGHazard(const Sequence SuccSSeq, const bool SuccSRRIKnownSafe, TopDownPtrState &S, bool &SomeSuccHasSame, bool &AllSuccsHaveSame, bool &NotAllSeqEqualButKnownSafe, bool &ShouldContinue)
If we have a top down pointer in the S_Use state, make sure that there are no CFG hazards by checking...
Declarations for ObjC runtime functions and constants.
void SetCFGHazardAfflicted(const bool NewValue)
Definition: PtrState.h:139
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:91
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2038
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
INITIALIZE_PASS_BEGIN(ObjCARCOpt, "objc-arc", "ObjC ARC optimization", false, false) INITIALIZE_PASS_END(ObjCARCOpt
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:565
LLVM Value Representation.
Definition: Value.h:72
Constant * getPersonalityFn() const
Get the personality function associated with this function.
Definition: Function.cpp:1306
foo(x) – x could possibly see a ref count decrement.
Definition: PtrState.h:43
Legacy wrapper pass to provide the ObjCARCAAResult object.
succ_range successors(Instruction *I)
Definition: CFG.h:259
static void ComputePostOrders(Function &F, SmallVectorImpl< BasicBlock *> &PostOrder, SmallVectorImpl< BasicBlock *> &ReverseCFGPostOrder, unsigned NoObjCARCExceptionsMDKind, DenseMap< const BasicBlock *, BBState > &BBStates)
static const unsigned OverflowOccurredValue
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
Invoke instruction.
This is similar to BasicAliasAnalysis, and it uses many of the same techniques, except it uses specia...
IRTranslator LLVM IR MI
bool hasOneUse() const
Return true if there is exactly one user of this value.
Definition: Value.h:412
const Value * GetRCIdentityRoot(const Value *V)
The RCIdentity root of a value V is a dominating value U for which retaining or releasing U is equiva...
inst_iterator inst_end(Function *F)
Definition: InstIterator.h:132
static CallInst * FindPredecessorRetainWithSafePath(const Value *Arg, BasicBlock *BB, Instruction *Autorelease, SmallPtrSetImpl< Instruction *> &DepInsts, SmallPtrSetImpl< const BasicBlock *> &Visited, ProvenanceAnalysis &PA)
Find a dependent retain that precedes the given autorelease for which there is nothing in between the...
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
The two locations alias, but only due to a partial overlap.
Definition: AliasAnalysis.h:88
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
DenseMap< BasicBlock *, ColorVector > colorEHFunclets(Function &F)
If an EH funclet personality is in use (see isFuncletEHPersonality), this will recompute which blocks...
#define LLVM_DEBUG(X)
Definition: Debug.h:122
bool IsKnownSafe() const
Definition: PtrState.h:119
void setDoesNotThrow()
Definition: InstrTypes.h:1655
static IntegerType * getInt8Ty(LLVMContext &C)
Definition: Type.cpp:173
bool AreStatisticsEnabled()
Check if statistics are enabled.
Definition: Statistic.cpp:133
bool use_empty() const
Definition: Value.h:322
unsigned size() const
bool IsNeverTail(ARCInstKind Class)
Test if the given class represents instructions which are never safe to mark with the "tail" keyword...
void blot(const KeyT &Key)
This is similar to erase, but instead of removing the element from the vector, it just zeros out the ...
Definition: BlotMapVector.h:96
void getEquivalentPHIs(PHINodeTy &PN, VectorTy &PHIList)
Return the list of PHI nodes that are equivalent to PN.
Definition: ObjCARC.h:86
bool IsNoopInstruction(const Instruction *I)
const BasicBlock * getParent() const
Definition: Instruction.h:66
an instruction to allocate memory on the stack
Definition: Instructions.h:59
bool IsAutorelease(ARCInstKind Class)
Test if the given class is objc_autorelease or equivalent.