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  // Some of the ARC calls can be deleted if their arguments are global
764  // variables that are inert in ARC.
765  if (IsNoopOnGlobal(Class)) {
766  Value *Opnd = Inst->getOperand(0);
767  if (auto *GV = dyn_cast<GlobalVariable>(Opnd->stripPointerCasts()))
768  if (GV->hasAttribute("objc_arc_inert")) {
769  if (!Inst->getType()->isVoidTy())
770  Inst->replaceAllUsesWith(Opnd);
771  Inst->eraseFromParent();
772  continue;
773  }
774  }
775 
776  switch (Class) {
777  default: break;
778 
779  // Delete no-op casts. These function calls have special semantics, but
780  // the semantics are entirely implemented via lowering in the front-end,
781  // so by the time they reach the optimizer, they are just no-op calls
782  // which return their argument.
783  //
784  // There are gray areas here, as the ability to cast reference-counted
785  // pointers to raw void* and back allows code to break ARC assumptions,
786  // however these are currently considered to be unimportant.
788  Changed = true;
789  ++NumNoops;
790  LLVM_DEBUG(dbgs() << "Erasing no-op cast: " << *Inst << "\n");
791  EraseInstruction(Inst);
792  continue;
793 
794  // If the pointer-to-weak-pointer is null, it's undefined behavior.
800  CallInst *CI = cast<CallInst>(Inst);
801  if (IsNullOrUndef(CI->getArgOperand(0))) {
802  Changed = true;
803  Type *Ty = CI->getArgOperand(0)->getType();
804  new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()),
806  CI);
807  Value *NewValue = UndefValue::get(CI->getType());
808  LLVM_DEBUG(
809  dbgs() << "A null pointer-to-weak-pointer is undefined behavior."
810  "\nOld = "
811  << *CI << "\nNew = " << *NewValue << "\n");
812  CI->replaceAllUsesWith(NewValue);
813  CI->eraseFromParent();
814  continue;
815  }
816  break;
817  }
819  case ARCInstKind::MoveWeak: {
820  CallInst *CI = cast<CallInst>(Inst);
821  if (IsNullOrUndef(CI->getArgOperand(0)) ||
822  IsNullOrUndef(CI->getArgOperand(1))) {
823  Changed = true;
824  Type *Ty = CI->getArgOperand(0)->getType();
825  new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()),
827  CI);
828 
829  Value *NewValue = UndefValue::get(CI->getType());
830  LLVM_DEBUG(
831  dbgs() << "A null pointer-to-weak-pointer is undefined behavior."
832  "\nOld = "
833  << *CI << "\nNew = " << *NewValue << "\n");
834 
835  CI->replaceAllUsesWith(NewValue);
836  CI->eraseFromParent();
837  continue;
838  }
839  break;
840  }
842  if (OptimizeRetainRVCall(F, Inst))
843  continue;
844  break;
846  OptimizeAutoreleaseRVCall(F, Inst, Class);
847  break;
848  }
849 
850  // objc_autorelease(x) -> objc_release(x) if x is otherwise unused.
851  if (IsAutorelease(Class) && Inst->use_empty()) {
852  CallInst *Call = cast<CallInst>(Inst);
853  const Value *Arg = Call->getArgOperand(0);
855  if (Arg) {
856  Changed = true;
857  ++NumAutoreleases;
858 
859  // Create the declaration lazily.
860  LLVMContext &C = Inst->getContext();
861 
863  CallInst *NewCall = CallInst::Create(Decl, Call->getArgOperand(0), "",
864  Call);
865  NewCall->setMetadata(MDKindCache.get(ARCMDKindID::ImpreciseRelease),
866  MDNode::get(C, None));
867 
868  LLVM_DEBUG(
869  dbgs() << "Replacing autorelease{,RV}(x) with objc_release(x) "
870  "since x is otherwise unused.\nOld: "
871  << *Call << "\nNew: " << *NewCall << "\n");
872 
873  EraseInstruction(Call);
874  Inst = NewCall;
875  Class = ARCInstKind::Release;
876  }
877  }
878 
879  // For functions which can never be passed stack arguments, add
880  // a tail keyword.
881  if (IsAlwaysTail(Class) && !cast<CallInst>(Inst)->isNoTailCall()) {
882  Changed = true;
883  LLVM_DEBUG(
884  dbgs() << "Adding tail keyword to function since it can never be "
885  "passed stack args: "
886  << *Inst << "\n");
887  cast<CallInst>(Inst)->setTailCall();
888  }
889 
890  // Ensure that functions that can never have a "tail" keyword due to the
891  // semantics of ARC truly do not do so.
892  if (IsNeverTail(Class)) {
893  Changed = true;
894  LLVM_DEBUG(dbgs() << "Removing tail keyword from function: " << *Inst
895  << "\n");
896  cast<CallInst>(Inst)->setTailCall(false);
897  }
898 
899  // Set nounwind as needed.
900  if (IsNoThrow(Class)) {
901  Changed = true;
902  LLVM_DEBUG(dbgs() << "Found no throw class. Setting nounwind on: "
903  << *Inst << "\n");
904  cast<CallInst>(Inst)->setDoesNotThrow();
905  }
906 
907  if (!IsNoopOnNull(Class)) {
908  UsedInThisFunction |= 1 << unsigned(Class);
909  continue;
910  }
911 
912  const Value *Arg = GetArgRCIdentityRoot(Inst);
913 
914  // ARC calls with null are no-ops. Delete them.
915  if (IsNullOrUndef(Arg)) {
916  Changed = true;
917  ++NumNoops;
918  LLVM_DEBUG(dbgs() << "ARC calls with null are no-ops. Erasing: " << *Inst
919  << "\n");
920  EraseInstruction(Inst);
921  continue;
922  }
923 
924  // Keep track of which of retain, release, autorelease, and retain_block
925  // are actually present in this function.
926  UsedInThisFunction |= 1 << unsigned(Class);
927 
928  // If Arg is a PHI, and one or more incoming values to the
929  // PHI are null, and the call is control-equivalent to the PHI, and there
930  // are no relevant side effects between the PHI and the call, and the call
931  // is not a release that doesn't have the clang.imprecise_release tag, the
932  // call could be pushed up to just those paths with non-null incoming
933  // values. For now, don't bother splitting critical edges for this.
934  if (Class == ARCInstKind::Release &&
935  !Inst->getMetadata(MDKindCache.get(ARCMDKindID::ImpreciseRelease)))
936  continue;
937 
939  Worklist.push_back(std::make_pair(Inst, Arg));
940  do {
941  std::pair<Instruction *, const Value *> Pair = Worklist.pop_back_val();
942  Inst = Pair.first;
943  Arg = Pair.second;
944 
945  const PHINode *PN = dyn_cast<PHINode>(Arg);
946  if (!PN) continue;
947 
948  // Determine if the PHI has any null operands, or any incoming
949  // critical edges.
950  bool HasNull = false;
951  bool HasCriticalEdges = false;
952  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
953  Value *Incoming =
955  if (IsNullOrUndef(Incoming))
956  HasNull = true;
957  else if (PN->getIncomingBlock(i)->getTerminator()->getNumSuccessors() !=
958  1) {
959  HasCriticalEdges = true;
960  break;
961  }
962  }
963  // If we have null operands and no critical edges, optimize.
964  if (!HasCriticalEdges && HasNull) {
965  SmallPtrSet<Instruction *, 4> DependingInstructions;
967 
968  // Check that there is nothing that cares about the reference
969  // count between the call and the phi.
970  switch (Class) {
971  case ARCInstKind::Retain:
973  // These can always be moved up.
974  break;
976  // These can't be moved across things that care about the retain
977  // count.
979  Inst->getParent(), Inst,
980  DependingInstructions, Visited, PA);
981  break;
983  // These can't be moved across autorelease pool scope boundaries.
985  Inst->getParent(), Inst,
986  DependingInstructions, Visited, PA);
987  break;
991  // Don't move these; the RV optimization depends on the autoreleaseRV
992  // being tail called, and the retainRV being immediately after a call
993  // (which might still happen if we get lucky with codegen layout, but
994  // it's not worth taking the chance).
995  continue;
996  default:
997  llvm_unreachable("Invalid dependence flavor");
998  }
999 
1000  if (DependingInstructions.size() == 1 &&
1001  *DependingInstructions.begin() == PN) {
1002  Changed = true;
1003  ++NumPartialNoops;
1004  // Clone the call into each predecessor that has a non-null value.
1005  CallInst *CInst = cast<CallInst>(Inst);
1006  Type *ParamTy = CInst->getArgOperand(0)->getType();
1007  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1008  Value *Incoming =
1010  if (!IsNullOrUndef(Incoming)) {
1011  Value *Op = PN->getIncomingValue(i);
1012  Instruction *InsertPos = &PN->getIncomingBlock(i)->back();
1013  CallInst *Clone = cast<CallInst>(CloneCallInstForBB(
1014  *CInst, *InsertPos->getParent(), BlockColors));
1015  if (Op->getType() != ParamTy)
1016  Op = new BitCastInst(Op, ParamTy, "", InsertPos);
1017  Clone->setArgOperand(0, Op);
1018  Clone->insertBefore(InsertPos);
1019 
1020  LLVM_DEBUG(dbgs() << "Cloning " << *CInst
1021  << "\n"
1022  "And inserting clone at "
1023  << *InsertPos << "\n");
1024  Worklist.push_back(std::make_pair(Clone, Incoming));
1025  }
1026  }
1027  // Erase the original call.
1028  LLVM_DEBUG(dbgs() << "Erasing: " << *CInst << "\n");
1029  EraseInstruction(CInst);
1030  continue;
1031  }
1032  }
1033  } while (!Worklist.empty());
1034  }
1035 }
1036 
1037 /// If we have a top down pointer in the S_Use state, make sure that there are
1038 /// no CFG hazards by checking the states of various bottom up pointers.
1039 static void CheckForUseCFGHazard(const Sequence SuccSSeq,
1040  const bool SuccSRRIKnownSafe,
1041  TopDownPtrState &S,
1042  bool &SomeSuccHasSame,
1043  bool &AllSuccsHaveSame,
1044  bool &NotAllSeqEqualButKnownSafe,
1045  bool &ShouldContinue) {
1046  switch (SuccSSeq) {
1047  case S_CanRelease: {
1048  if (!S.IsKnownSafe() && !SuccSRRIKnownSafe) {
1050  break;
1051  }
1052  S.SetCFGHazardAfflicted(true);
1053  ShouldContinue = true;
1054  break;
1055  }
1056  case S_Use:
1057  SomeSuccHasSame = true;
1058  break;
1059  case S_Stop:
1060  case S_Release:
1061  case S_MovableRelease:
1062  if (!S.IsKnownSafe() && !SuccSRRIKnownSafe)
1063  AllSuccsHaveSame = false;
1064  else
1065  NotAllSeqEqualButKnownSafe = true;
1066  break;
1067  case S_Retain:
1068  llvm_unreachable("bottom-up pointer in retain state!");
1069  case S_None:
1070  llvm_unreachable("This should have been handled earlier.");
1071  }
1072 }
1073 
1074 /// If we have a Top Down pointer in the S_CanRelease state, make sure that
1075 /// there are no CFG hazards by checking the states of various bottom up
1076 /// pointers.
1077 static void CheckForCanReleaseCFGHazard(const Sequence SuccSSeq,
1078  const bool SuccSRRIKnownSafe,
1079  TopDownPtrState &S,
1080  bool &SomeSuccHasSame,
1081  bool &AllSuccsHaveSame,
1082  bool &NotAllSeqEqualButKnownSafe) {
1083  switch (SuccSSeq) {
1084  case S_CanRelease:
1085  SomeSuccHasSame = true;
1086  break;
1087  case S_Stop:
1088  case S_Release:
1089  case S_MovableRelease:
1090  case S_Use:
1091  if (!S.IsKnownSafe() && !SuccSRRIKnownSafe)
1092  AllSuccsHaveSame = false;
1093  else
1094  NotAllSeqEqualButKnownSafe = true;
1095  break;
1096  case S_Retain:
1097  llvm_unreachable("bottom-up pointer in retain state!");
1098  case S_None:
1099  llvm_unreachable("This should have been handled earlier.");
1100  }
1101 }
1102 
1103 /// Check for critical edges, loop boundaries, irreducible control flow, or
1104 /// other CFG structures where moving code across the edge would result in it
1105 /// being executed more.
1106 void
1107 ObjCARCOpt::CheckForCFGHazards(const BasicBlock *BB,
1109  BBState &MyStates) const {
1110  // If any top-down local-use or possible-dec has a succ which is earlier in
1111  // the sequence, forget it.
1112  for (auto I = MyStates.top_down_ptr_begin(), E = MyStates.top_down_ptr_end();
1113  I != E; ++I) {
1114  TopDownPtrState &S = I->second;
1115  const Sequence Seq = I->second.GetSeq();
1116 
1117  // We only care about S_Retain, S_CanRelease, and S_Use.
1118  if (Seq == S_None)
1119  continue;
1120 
1121  // Make sure that if extra top down states are added in the future that this
1122  // code is updated to handle it.
1123  assert((Seq == S_Retain || Seq == S_CanRelease || Seq == S_Use) &&
1124  "Unknown top down sequence state.");
1125 
1126  const Value *Arg = I->first;
1127  bool SomeSuccHasSame = false;
1128  bool AllSuccsHaveSame = true;
1129  bool NotAllSeqEqualButKnownSafe = false;
1130 
1131  for (const BasicBlock *Succ : successors(BB)) {
1132  // If VisitBottomUp has pointer information for this successor, take
1133  // what we know about it.
1135  BBStates.find(Succ);
1136  assert(BBI != BBStates.end());
1137  const BottomUpPtrState &SuccS = BBI->second.getPtrBottomUpState(Arg);
1138  const Sequence SuccSSeq = SuccS.GetSeq();
1139 
1140  // If bottom up, the pointer is in an S_None state, clear the sequence
1141  // progress since the sequence in the bottom up state finished
1142  // suggesting a mismatch in between retains/releases. This is true for
1143  // all three cases that we are handling here: S_Retain, S_Use, and
1144  // S_CanRelease.
1145  if (SuccSSeq == S_None) {
1147  continue;
1148  }
1149 
1150  // If we have S_Use or S_CanRelease, perform our check for cfg hazard
1151  // checks.
1152  const bool SuccSRRIKnownSafe = SuccS.IsKnownSafe();
1153 
1154  // *NOTE* We do not use Seq from above here since we are allowing for
1155  // S.GetSeq() to change while we are visiting basic blocks.
1156  switch(S.GetSeq()) {
1157  case S_Use: {
1158  bool ShouldContinue = false;
1159  CheckForUseCFGHazard(SuccSSeq, SuccSRRIKnownSafe, S, SomeSuccHasSame,
1160  AllSuccsHaveSame, NotAllSeqEqualButKnownSafe,
1161  ShouldContinue);
1162  if (ShouldContinue)
1163  continue;
1164  break;
1165  }
1166  case S_CanRelease:
1167  CheckForCanReleaseCFGHazard(SuccSSeq, SuccSRRIKnownSafe, S,
1168  SomeSuccHasSame, AllSuccsHaveSame,
1169  NotAllSeqEqualButKnownSafe);
1170  break;
1171  case S_Retain:
1172  case S_None:
1173  case S_Stop:
1174  case S_Release:
1175  case S_MovableRelease:
1176  break;
1177  }
1178  }
1179 
1180  // If the state at the other end of any of the successor edges
1181  // matches the current state, require all edges to match. This
1182  // guards against loops in the middle of a sequence.
1183  if (SomeSuccHasSame && !AllSuccsHaveSame) {
1185  } else if (NotAllSeqEqualButKnownSafe) {
1186  // If we would have cleared the state foregoing the fact that we are known
1187  // safe, stop code motion. This is because whether or not it is safe to
1188  // remove RR pairs via KnownSafe is an orthogonal concept to whether we
1189  // are allowed to perform code motion.
1190  S.SetCFGHazardAfflicted(true);
1191  }
1192  }
1193 }
1194 
1195 bool ObjCARCOpt::VisitInstructionBottomUp(
1197  BBState &MyStates) {
1198  bool NestingDetected = false;
1199  ARCInstKind Class = GetARCInstKind(Inst);
1200  const Value *Arg = nullptr;
1201 
1202  LLVM_DEBUG(dbgs() << " Class: " << Class << "\n");
1203 
1204  switch (Class) {
1205  case ARCInstKind::Release: {
1206  Arg = GetArgRCIdentityRoot(Inst);
1207 
1208  BottomUpPtrState &S = MyStates.getPtrBottomUpState(Arg);
1209  NestingDetected |= S.InitBottomUp(MDKindCache, Inst);
1210  break;
1211  }
1213  // In OptimizeIndividualCalls, we have strength reduced all optimizable
1214  // objc_retainBlocks to objc_retains. Thus at this point any
1215  // objc_retainBlocks that we see are not optimizable.
1216  break;
1217  case ARCInstKind::Retain:
1218  case ARCInstKind::RetainRV: {
1219  Arg = GetArgRCIdentityRoot(Inst);
1220  BottomUpPtrState &S = MyStates.getPtrBottomUpState(Arg);
1221  if (S.MatchWithRetain()) {
1222  // Don't do retain+release tracking for ARCInstKind::RetainRV, because
1223  // it's better to let it remain as the first instruction after a call.
1224  if (Class != ARCInstKind::RetainRV) {
1225  LLVM_DEBUG(dbgs() << " Matching with: " << *Inst << "\n");
1226  Retains[Inst] = S.GetRRInfo();
1227  }
1229  }
1230  // A retain moving bottom up can be a use.
1231  break;
1232  }
1234  // Conservatively, clear MyStates for all known pointers.
1235  MyStates.clearBottomUpPointers();
1236  return NestingDetected;
1238  case ARCInstKind::None:
1239  // These are irrelevant.
1240  return NestingDetected;
1241  default:
1242  break;
1243  }
1244 
1245  // Consider any other possible effects of this instruction on each
1246  // pointer being tracked.
1247  for (auto MI = MyStates.bottom_up_ptr_begin(),
1248  ME = MyStates.bottom_up_ptr_end();
1249  MI != ME; ++MI) {
1250  const Value *Ptr = MI->first;
1251  if (Ptr == Arg)
1252  continue; // Handled above.
1253  BottomUpPtrState &S = MI->second;
1254 
1255  if (S.HandlePotentialAlterRefCount(Inst, Ptr, PA, Class))
1256  continue;
1257 
1258  S.HandlePotentialUse(BB, Inst, Ptr, PA, Class);
1259  }
1260 
1261  return NestingDetected;
1262 }
1263 
1264 bool ObjCARCOpt::VisitBottomUp(BasicBlock *BB,
1266  BlotMapVector<Value *, RRInfo> &Retains) {
1267  LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::VisitBottomUp ==\n");
1268 
1269  bool NestingDetected = false;
1270  BBState &MyStates = BBStates[BB];
1271 
1272  // Merge the states from each successor to compute the initial state
1273  // for the current block.
1274  BBState::edge_iterator SI(MyStates.succ_begin()),
1275  SE(MyStates.succ_end());
1276  if (SI != SE) {
1277  const BasicBlock *Succ = *SI;
1279  assert(I != BBStates.end());
1280  MyStates.InitFromSucc(I->second);
1281  ++SI;
1282  for (; SI != SE; ++SI) {
1283  Succ = *SI;
1284  I = BBStates.find(Succ);
1285  assert(I != BBStates.end());
1286  MyStates.MergeSucc(I->second);
1287  }
1288  }
1289 
1290  LLVM_DEBUG(dbgs() << "Before:\n"
1291  << BBStates[BB] << "\n"
1292  << "Performing Dataflow:\n");
1293 
1294  // Visit all the instructions, bottom-up.
1295  for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; --I) {
1296  Instruction *Inst = &*std::prev(I);
1297 
1298  // Invoke instructions are visited as part of their successors (below).
1299  if (isa<InvokeInst>(Inst))
1300  continue;
1301 
1302  LLVM_DEBUG(dbgs() << " Visiting " << *Inst << "\n");
1303 
1304  NestingDetected |= VisitInstructionBottomUp(Inst, BB, Retains, MyStates);
1305 
1306  // Bail out if the number of pointers being tracked becomes too large so
1307  // that this pass can complete in a reasonable amount of time.
1308  if (MyStates.bottom_up_ptr_list_size() > MaxPtrStates) {
1309  DisableRetainReleasePairing = true;
1310  return false;
1311  }
1312  }
1313 
1314  // If there's a predecessor with an invoke, visit the invoke as if it were
1315  // part of this block, since we can't insert code after an invoke in its own
1316  // block, and we don't want to split critical edges.
1317  for (BBState::edge_iterator PI(MyStates.pred_begin()),
1318  PE(MyStates.pred_end()); PI != PE; ++PI) {
1319  BasicBlock *Pred = *PI;
1320  if (InvokeInst *II = dyn_cast<InvokeInst>(&Pred->back()))
1321  NestingDetected |= VisitInstructionBottomUp(II, BB, Retains, MyStates);
1322  }
1323 
1324  LLVM_DEBUG(dbgs() << "\nFinal State:\n" << BBStates[BB] << "\n");
1325 
1326  return NestingDetected;
1327 }
1328 
1329 bool
1330 ObjCARCOpt::VisitInstructionTopDown(Instruction *Inst,
1331  DenseMap<Value *, RRInfo> &Releases,
1332  BBState &MyStates) {
1333  bool NestingDetected = false;
1334  ARCInstKind Class = GetARCInstKind(Inst);
1335  const Value *Arg = nullptr;
1336 
1337  LLVM_DEBUG(dbgs() << " Class: " << Class << "\n");
1338 
1339  switch (Class) {
1341  // In OptimizeIndividualCalls, we have strength reduced all optimizable
1342  // objc_retainBlocks to objc_retains. Thus at this point any
1343  // objc_retainBlocks that we see are not optimizable. We need to break since
1344  // a retain can be a potential use.
1345  break;
1346  case ARCInstKind::Retain:
1347  case ARCInstKind::RetainRV: {
1348  Arg = GetArgRCIdentityRoot(Inst);
1349  TopDownPtrState &S = MyStates.getPtrTopDownState(Arg);
1350  NestingDetected |= S.InitTopDown(Class, Inst);
1351  // A retain can be a potential use; proceed to the generic checking
1352  // code below.
1353  break;
1354  }
1355  case ARCInstKind::Release: {
1356  Arg = GetArgRCIdentityRoot(Inst);
1357  TopDownPtrState &S = MyStates.getPtrTopDownState(Arg);
1358  // Try to form a tentative pair in between this release instruction and the
1359  // top down pointers that we are tracking.
1360  if (S.MatchWithRelease(MDKindCache, Inst)) {
1361  // If we succeed, copy S's RRInfo into the Release -> {Retain Set
1362  // Map}. Then we clear S.
1363  LLVM_DEBUG(dbgs() << " Matching with: " << *Inst << "\n");
1364  Releases[Inst] = S.GetRRInfo();
1366  }
1367  break;
1368  }
1370  // Conservatively, clear MyStates for all known pointers.
1371  MyStates.clearTopDownPointers();
1372  return false;
1374  case ARCInstKind::None:
1375  // These can not be uses of
1376  return false;
1377  default:
1378  break;
1379  }
1380 
1381  // Consider any other possible effects of this instruction on each
1382  // pointer being tracked.
1383  for (auto MI = MyStates.top_down_ptr_begin(),
1384  ME = MyStates.top_down_ptr_end();
1385  MI != ME; ++MI) {
1386  const Value *Ptr = MI->first;
1387  if (Ptr == Arg)
1388  continue; // Handled above.
1389  TopDownPtrState &S = MI->second;
1390  if (S.HandlePotentialAlterRefCount(Inst, Ptr, PA, Class))
1391  continue;
1392 
1393  S.HandlePotentialUse(Inst, Ptr, PA, Class);
1394  }
1395 
1396  return NestingDetected;
1397 }
1398 
1399 bool
1400 ObjCARCOpt::VisitTopDown(BasicBlock *BB,
1402  DenseMap<Value *, RRInfo> &Releases) {
1403  LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::VisitTopDown ==\n");
1404  bool NestingDetected = false;
1405  BBState &MyStates = BBStates[BB];
1406 
1407  // Merge the states from each predecessor to compute the initial state
1408  // for the current block.
1409  BBState::edge_iterator PI(MyStates.pred_begin()),
1410  PE(MyStates.pred_end());
1411  if (PI != PE) {
1412  const BasicBlock *Pred = *PI;
1414  assert(I != BBStates.end());
1415  MyStates.InitFromPred(I->second);
1416  ++PI;
1417  for (; PI != PE; ++PI) {
1418  Pred = *PI;
1419  I = BBStates.find(Pred);
1420  assert(I != BBStates.end());
1421  MyStates.MergePred(I->second);
1422  }
1423  }
1424 
1425  LLVM_DEBUG(dbgs() << "Before:\n"
1426  << BBStates[BB] << "\n"
1427  << "Performing Dataflow:\n");
1428 
1429  // Visit all the instructions, top-down.
1430  for (Instruction &Inst : *BB) {
1431  LLVM_DEBUG(dbgs() << " Visiting " << Inst << "\n");
1432 
1433  NestingDetected |= VisitInstructionTopDown(&Inst, Releases, MyStates);
1434 
1435  // Bail out if the number of pointers being tracked becomes too large so
1436  // that this pass can complete in a reasonable amount of time.
1437  if (MyStates.top_down_ptr_list_size() > MaxPtrStates) {
1438  DisableRetainReleasePairing = true;
1439  return false;
1440  }
1441  }
1442 
1443  LLVM_DEBUG(dbgs() << "\nState Before Checking for CFG Hazards:\n"
1444  << BBStates[BB] << "\n\n");
1445  CheckForCFGHazards(BB, BBStates, MyStates);
1446  LLVM_DEBUG(dbgs() << "Final State:\n" << BBStates[BB] << "\n");
1447  return NestingDetected;
1448 }
1449 
1450 static void
1452  SmallVectorImpl<BasicBlock *> &PostOrder,
1453  SmallVectorImpl<BasicBlock *> &ReverseCFGPostOrder,
1454  unsigned NoObjCARCExceptionsMDKind,
1456  /// The visited set, for doing DFS walks.
1458 
1459  // Do DFS, computing the PostOrder.
1462 
1463  // Functions always have exactly one entry block, and we don't have
1464  // any other block that we treat like an entry block.
1465  BasicBlock *EntryBB = &F.getEntryBlock();
1466  BBState &MyStates = BBStates[EntryBB];
1467  MyStates.SetAsEntry();
1468  Instruction *EntryTI = EntryBB->getTerminator();
1469  SuccStack.push_back(std::make_pair(EntryBB, succ_iterator(EntryTI)));
1470  Visited.insert(EntryBB);
1471  OnStack.insert(EntryBB);
1472  do {
1473  dfs_next_succ:
1474  BasicBlock *CurrBB = SuccStack.back().first;
1475  succ_iterator SE(CurrBB->getTerminator(), false);
1476 
1477  while (SuccStack.back().second != SE) {
1478  BasicBlock *SuccBB = *SuccStack.back().second++;
1479  if (Visited.insert(SuccBB).second) {
1480  SuccStack.push_back(
1481  std::make_pair(SuccBB, succ_iterator(SuccBB->getTerminator())));
1482  BBStates[CurrBB].addSucc(SuccBB);
1483  BBState &SuccStates = BBStates[SuccBB];
1484  SuccStates.addPred(CurrBB);
1485  OnStack.insert(SuccBB);
1486  goto dfs_next_succ;
1487  }
1488 
1489  if (!OnStack.count(SuccBB)) {
1490  BBStates[CurrBB].addSucc(SuccBB);
1491  BBStates[SuccBB].addPred(CurrBB);
1492  }
1493  }
1494  OnStack.erase(CurrBB);
1495  PostOrder.push_back(CurrBB);
1496  SuccStack.pop_back();
1497  } while (!SuccStack.empty());
1498 
1499  Visited.clear();
1500 
1501  // Do reverse-CFG DFS, computing the reverse-CFG PostOrder.
1502  // Functions may have many exits, and there also blocks which we treat
1503  // as exits due to ignored edges.
1505  for (BasicBlock &ExitBB : F) {
1506  BBState &MyStates = BBStates[&ExitBB];
1507  if (!MyStates.isExit())
1508  continue;
1509 
1510  MyStates.SetAsExit();
1511 
1512  PredStack.push_back(std::make_pair(&ExitBB, MyStates.pred_begin()));
1513  Visited.insert(&ExitBB);
1514  while (!PredStack.empty()) {
1515  reverse_dfs_next_succ:
1516  BBState::edge_iterator PE = BBStates[PredStack.back().first].pred_end();
1517  while (PredStack.back().second != PE) {
1518  BasicBlock *BB = *PredStack.back().second++;
1519  if (Visited.insert(BB).second) {
1520  PredStack.push_back(std::make_pair(BB, BBStates[BB].pred_begin()));
1521  goto reverse_dfs_next_succ;
1522  }
1523  }
1524  ReverseCFGPostOrder.push_back(PredStack.pop_back_val().first);
1525  }
1526  }
1527 }
1528 
1529 // Visit the function both top-down and bottom-up.
1530 bool ObjCARCOpt::Visit(Function &F,
1533  DenseMap<Value *, RRInfo> &Releases) {
1534  // Use reverse-postorder traversals, because we magically know that loops
1535  // will be well behaved, i.e. they won't repeatedly call retain on a single
1536  // pointer without doing a release. We can't use the ReversePostOrderTraversal
1537  // class here because we want the reverse-CFG postorder to consider each
1538  // function exit point, and we want to ignore selected cycle edges.
1540  SmallVector<BasicBlock *, 16> ReverseCFGPostOrder;
1541  ComputePostOrders(F, PostOrder, ReverseCFGPostOrder,
1542  MDKindCache.get(ARCMDKindID::NoObjCARCExceptions),
1543  BBStates);
1544 
1545  // Use reverse-postorder on the reverse CFG for bottom-up.
1546  bool BottomUpNestingDetected = false;
1547  for (BasicBlock *BB : llvm::reverse(ReverseCFGPostOrder)) {
1548  BottomUpNestingDetected |= VisitBottomUp(BB, BBStates, Retains);
1549  if (DisableRetainReleasePairing)
1550  return false;
1551  }
1552 
1553  // Use reverse-postorder for top-down.
1554  bool TopDownNestingDetected = false;
1555  for (BasicBlock *BB : llvm::reverse(PostOrder)) {
1556  TopDownNestingDetected |= VisitTopDown(BB, BBStates, Releases);
1557  if (DisableRetainReleasePairing)
1558  return false;
1559  }
1560 
1561  return TopDownNestingDetected && BottomUpNestingDetected;
1562 }
1563 
1564 /// Move the calls in RetainsToMove and ReleasesToMove.
1565 void ObjCARCOpt::MoveCalls(Value *Arg, RRInfo &RetainsToMove,
1566  RRInfo &ReleasesToMove,
1568  DenseMap<Value *, RRInfo> &Releases,
1569  SmallVectorImpl<Instruction *> &DeadInsts,
1570  Module *M) {
1571  Type *ArgTy = Arg->getType();
1572  Type *ParamTy = PointerType::getUnqual(Type::getInt8Ty(ArgTy->getContext()));
1573 
1574  LLVM_DEBUG(dbgs() << "== ObjCARCOpt::MoveCalls ==\n");
1575 
1576  // Insert the new retain and release calls.
1577  for (Instruction *InsertPt : ReleasesToMove.ReverseInsertPts) {
1578  Value *MyArg = ArgTy == ParamTy ? Arg :
1579  new BitCastInst(Arg, ParamTy, "", InsertPt);
1581  CallInst *Call = CallInst::Create(Decl, MyArg, "", InsertPt);
1582  Call->setDoesNotThrow();
1583  Call->setTailCall();
1584 
1585  LLVM_DEBUG(dbgs() << "Inserting new Retain: " << *Call
1586  << "\n"
1587  "At insertion point: "
1588  << *InsertPt << "\n");
1589  }
1590  for (Instruction *InsertPt : RetainsToMove.ReverseInsertPts) {
1591  Value *MyArg = ArgTy == ParamTy ? Arg :
1592  new BitCastInst(Arg, ParamTy, "", InsertPt);
1594  CallInst *Call = CallInst::Create(Decl, MyArg, "", InsertPt);
1595  // Attach a clang.imprecise_release metadata tag, if appropriate.
1596  if (MDNode *M = ReleasesToMove.ReleaseMetadata)
1597  Call->setMetadata(MDKindCache.get(ARCMDKindID::ImpreciseRelease), M);
1598  Call->setDoesNotThrow();
1599  if (ReleasesToMove.IsTailCallRelease)
1600  Call->setTailCall();
1601 
1602  LLVM_DEBUG(dbgs() << "Inserting new Release: " << *Call
1603  << "\n"
1604  "At insertion point: "
1605  << *InsertPt << "\n");
1606  }
1607 
1608  // Delete the original retain and release calls.
1609  for (Instruction *OrigRetain : RetainsToMove.Calls) {
1610  Retains.blot(OrigRetain);
1611  DeadInsts.push_back(OrigRetain);
1612  LLVM_DEBUG(dbgs() << "Deleting retain: " << *OrigRetain << "\n");
1613  }
1614  for (Instruction *OrigRelease : ReleasesToMove.Calls) {
1615  Releases.erase(OrigRelease);
1616  DeadInsts.push_back(OrigRelease);
1617  LLVM_DEBUG(dbgs() << "Deleting release: " << *OrigRelease << "\n");
1618  }
1619 }
1620 
1621 bool ObjCARCOpt::PairUpRetainsAndReleases(
1624  DenseMap<Value *, RRInfo> &Releases, Module *M,
1626  SmallVectorImpl<Instruction *> &DeadInsts, RRInfo &RetainsToMove,
1627  RRInfo &ReleasesToMove, Value *Arg, bool KnownSafe,
1628  bool &AnyPairsCompletelyEliminated) {
1629  // If a pair happens in a region where it is known that the reference count
1630  // is already incremented, we can similarly ignore possible decrements unless
1631  // we are dealing with a retainable object with multiple provenance sources.
1632  bool KnownSafeTD = true, KnownSafeBU = true;
1633  bool CFGHazardAfflicted = false;
1634 
1635  // Connect the dots between the top-down-collected RetainsToMove and
1636  // bottom-up-collected ReleasesToMove to form sets of related calls.
1637  // This is an iterative process so that we connect multiple releases
1638  // to multiple retains if needed.
1639  unsigned OldDelta = 0;
1640  unsigned NewDelta = 0;
1641  unsigned OldCount = 0;
1642  unsigned NewCount = 0;
1643  bool FirstRelease = true;
1644  for (SmallVector<Instruction *, 4> NewRetains{Retain};;) {
1645  SmallVector<Instruction *, 4> NewReleases;
1646  for (Instruction *NewRetain : NewRetains) {
1647  auto It = Retains.find(NewRetain);
1648  assert(It != Retains.end());
1649  const RRInfo &NewRetainRRI = It->second;
1650  KnownSafeTD &= NewRetainRRI.KnownSafe;
1651  CFGHazardAfflicted |= NewRetainRRI.CFGHazardAfflicted;
1652  for (Instruction *NewRetainRelease : NewRetainRRI.Calls) {
1653  auto Jt = Releases.find(NewRetainRelease);
1654  if (Jt == Releases.end())
1655  return false;
1656  const RRInfo &NewRetainReleaseRRI = Jt->second;
1657 
1658  // If the release does not have a reference to the retain as well,
1659  // something happened which is unaccounted for. Do not do anything.
1660  //
1661  // This can happen if we catch an additive overflow during path count
1662  // merging.
1663  if (!NewRetainReleaseRRI.Calls.count(NewRetain))
1664  return false;
1665 
1666  if (ReleasesToMove.Calls.insert(NewRetainRelease).second) {
1667  // If we overflow when we compute the path count, don't remove/move
1668  // anything.
1669  const BBState &NRRBBState = BBStates[NewRetainRelease->getParent()];
1670  unsigned PathCount = BBState::OverflowOccurredValue;
1671  if (NRRBBState.GetAllPathCountWithOverflow(PathCount))
1672  return false;
1673  assert(PathCount != BBState::OverflowOccurredValue &&
1674  "PathCount at this point can not be "
1675  "OverflowOccurredValue.");
1676  OldDelta -= PathCount;
1677 
1678  // Merge the ReleaseMetadata and IsTailCallRelease values.
1679  if (FirstRelease) {
1680  ReleasesToMove.ReleaseMetadata =
1681  NewRetainReleaseRRI.ReleaseMetadata;
1682  ReleasesToMove.IsTailCallRelease =
1683  NewRetainReleaseRRI.IsTailCallRelease;
1684  FirstRelease = false;
1685  } else {
1686  if (ReleasesToMove.ReleaseMetadata !=
1687  NewRetainReleaseRRI.ReleaseMetadata)
1688  ReleasesToMove.ReleaseMetadata = nullptr;
1689  if (ReleasesToMove.IsTailCallRelease !=
1690  NewRetainReleaseRRI.IsTailCallRelease)
1691  ReleasesToMove.IsTailCallRelease = false;
1692  }
1693 
1694  // Collect the optimal insertion points.
1695  if (!KnownSafe)
1696  for (Instruction *RIP : NewRetainReleaseRRI.ReverseInsertPts) {
1697  if (ReleasesToMove.ReverseInsertPts.insert(RIP).second) {
1698  // If we overflow when we compute the path count, don't
1699  // remove/move anything.
1700  const BBState &RIPBBState = BBStates[RIP->getParent()];
1701  PathCount = BBState::OverflowOccurredValue;
1702  if (RIPBBState.GetAllPathCountWithOverflow(PathCount))
1703  return false;
1704  assert(PathCount != BBState::OverflowOccurredValue &&
1705  "PathCount at this point can not be "
1706  "OverflowOccurredValue.");
1707  NewDelta -= PathCount;
1708  }
1709  }
1710  NewReleases.push_back(NewRetainRelease);
1711  }
1712  }
1713  }
1714  NewRetains.clear();
1715  if (NewReleases.empty()) break;
1716 
1717  // Back the other way.
1718  for (Instruction *NewRelease : NewReleases) {
1719  auto It = Releases.find(NewRelease);
1720  assert(It != Releases.end());
1721  const RRInfo &NewReleaseRRI = It->second;
1722  KnownSafeBU &= NewReleaseRRI.KnownSafe;
1723  CFGHazardAfflicted |= NewReleaseRRI.CFGHazardAfflicted;
1724  for (Instruction *NewReleaseRetain : NewReleaseRRI.Calls) {
1725  auto Jt = Retains.find(NewReleaseRetain);
1726  if (Jt == Retains.end())
1727  return false;
1728  const RRInfo &NewReleaseRetainRRI = Jt->second;
1729 
1730  // If the retain does not have a reference to the release as well,
1731  // something happened which is unaccounted for. Do not do anything.
1732  //
1733  // This can happen if we catch an additive overflow during path count
1734  // merging.
1735  if (!NewReleaseRetainRRI.Calls.count(NewRelease))
1736  return false;
1737 
1738  if (RetainsToMove.Calls.insert(NewReleaseRetain).second) {
1739  // If we overflow when we compute the path count, don't remove/move
1740  // anything.
1741  const BBState &NRRBBState = BBStates[NewReleaseRetain->getParent()];
1742  unsigned PathCount = BBState::OverflowOccurredValue;
1743  if (NRRBBState.GetAllPathCountWithOverflow(PathCount))
1744  return false;
1745  assert(PathCount != BBState::OverflowOccurredValue &&
1746  "PathCount at this point can not be "
1747  "OverflowOccurredValue.");
1748  OldDelta += PathCount;
1749  OldCount += PathCount;
1750 
1751  // Collect the optimal insertion points.
1752  if (!KnownSafe)
1753  for (Instruction *RIP : NewReleaseRetainRRI.ReverseInsertPts) {
1754  if (RetainsToMove.ReverseInsertPts.insert(RIP).second) {
1755  // If we overflow when we compute the path count, don't
1756  // remove/move anything.
1757  const BBState &RIPBBState = BBStates[RIP->getParent()];
1758 
1759  PathCount = BBState::OverflowOccurredValue;
1760  if (RIPBBState.GetAllPathCountWithOverflow(PathCount))
1761  return false;
1762  assert(PathCount != BBState::OverflowOccurredValue &&
1763  "PathCount at this point can not be "
1764  "OverflowOccurredValue.");
1765  NewDelta += PathCount;
1766  NewCount += PathCount;
1767  }
1768  }
1769  NewRetains.push_back(NewReleaseRetain);
1770  }
1771  }
1772  }
1773  if (NewRetains.empty()) break;
1774  }
1775 
1776  // We can only remove pointers if we are known safe in both directions.
1777  bool UnconditionallySafe = KnownSafeTD && KnownSafeBU;
1778  if (UnconditionallySafe) {
1779  RetainsToMove.ReverseInsertPts.clear();
1780  ReleasesToMove.ReverseInsertPts.clear();
1781  NewCount = 0;
1782  } else {
1783  // Determine whether the new insertion points we computed preserve the
1784  // balance of retain and release calls through the program.
1785  // TODO: If the fully aggressive solution isn't valid, try to find a
1786  // less aggressive solution which is.
1787  if (NewDelta != 0)
1788  return false;
1789 
1790  // At this point, we are not going to remove any RR pairs, but we still are
1791  // able to move RR pairs. If one of our pointers is afflicted with
1792  // CFGHazards, we cannot perform such code motion so exit early.
1793  const bool WillPerformCodeMotion =
1794  !RetainsToMove.ReverseInsertPts.empty() ||
1795  !ReleasesToMove.ReverseInsertPts.empty();
1796  if (CFGHazardAfflicted && WillPerformCodeMotion)
1797  return false;
1798  }
1799 
1800  // Determine whether the original call points are balanced in the retain and
1801  // release calls through the program. If not, conservatively don't touch
1802  // them.
1803  // TODO: It's theoretically possible to do code motion in this case, as
1804  // long as the existing imbalances are maintained.
1805  if (OldDelta != 0)
1806  return false;
1807 
1808  Changed = true;
1809  assert(OldCount != 0 && "Unreachable code?");
1810  NumRRs += OldCount - NewCount;
1811  // Set to true if we completely removed any RR pairs.
1812  AnyPairsCompletelyEliminated = NewCount == 0;
1813 
1814  // We can move calls!
1815  return true;
1816 }
1817 
1818 /// Identify pairings between the retains and releases, and delete and/or move
1819 /// them.
1820 bool ObjCARCOpt::PerformCodePlacement(
1823  DenseMap<Value *, RRInfo> &Releases, Module *M) {
1824  LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::PerformCodePlacement ==\n");
1825 
1826  bool AnyPairsCompletelyEliminated = false;
1828 
1829  // Visit each retain.
1831  E = Retains.end();
1832  I != E; ++I) {
1833  Value *V = I->first;
1834  if (!V) continue; // blotted
1835 
1836  Instruction *Retain = cast<Instruction>(V);
1837 
1838  LLVM_DEBUG(dbgs() << "Visiting: " << *Retain << "\n");
1839 
1840  Value *Arg = GetArgRCIdentityRoot(Retain);
1841 
1842  // If the object being released is in static or stack storage, we know it's
1843  // not being managed by ObjC reference counting, so we can delete pairs
1844  // regardless of what possible decrements or uses lie between them.
1845  bool KnownSafe = isa<Constant>(Arg) || isa<AllocaInst>(Arg);
1846 
1847  // A constant pointer can't be pointing to an object on the heap. It may
1848  // be reference-counted, but it won't be deleted.
1849  if (const LoadInst *LI = dyn_cast<LoadInst>(Arg))
1850  if (const GlobalVariable *GV =
1851  dyn_cast<GlobalVariable>(
1852  GetRCIdentityRoot(LI->getPointerOperand())))
1853  if (GV->isConstant())
1854  KnownSafe = true;
1855 
1856  // Connect the dots between the top-down-collected RetainsToMove and
1857  // bottom-up-collected ReleasesToMove to form sets of related calls.
1858  RRInfo RetainsToMove, ReleasesToMove;
1859 
1860  bool PerformMoveCalls = PairUpRetainsAndReleases(
1861  BBStates, Retains, Releases, M, Retain, DeadInsts,
1862  RetainsToMove, ReleasesToMove, Arg, KnownSafe,
1863  AnyPairsCompletelyEliminated);
1864 
1865  if (PerformMoveCalls) {
1866  // Ok, everything checks out and we're all set. Let's move/delete some
1867  // code!
1868  MoveCalls(Arg, RetainsToMove, ReleasesToMove,
1869  Retains, Releases, DeadInsts, M);
1870  }
1871  }
1872 
1873  // Now that we're done moving everything, we can delete the newly dead
1874  // instructions, as we no longer need them as insert points.
1875  while (!DeadInsts.empty())
1876  EraseInstruction(DeadInsts.pop_back_val());
1877 
1878  return AnyPairsCompletelyEliminated;
1879 }
1880 
1881 /// Weak pointer optimizations.
1882 void ObjCARCOpt::OptimizeWeakCalls(Function &F) {
1883  LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeWeakCalls ==\n");
1884 
1885  // First, do memdep-style RLE and S2L optimizations. We can't use memdep
1886  // itself because it uses AliasAnalysis and we need to do provenance
1887  // queries instead.
1888  for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
1889  Instruction *Inst = &*I++;
1890 
1891  LLVM_DEBUG(dbgs() << "Visiting: " << *Inst << "\n");
1892 
1893  ARCInstKind Class = GetBasicARCInstKind(Inst);
1894  if (Class != ARCInstKind::LoadWeak &&
1896  continue;
1897 
1898  // Delete objc_loadWeak calls with no users.
1899  if (Class == ARCInstKind::LoadWeak && Inst->use_empty()) {
1900  Inst->eraseFromParent();
1901  continue;
1902  }
1903 
1904  // TODO: For now, just look for an earlier available version of this value
1905  // within the same block. Theoretically, we could do memdep-style non-local
1906  // analysis too, but that would want caching. A better approach would be to
1907  // use the technique that EarlyCSE uses.
1908  inst_iterator Current = std::prev(I);
1909  BasicBlock *CurrentBB = &*Current.getBasicBlockIterator();
1910  for (BasicBlock::iterator B = CurrentBB->begin(),
1911  J = Current.getInstructionIterator();
1912  J != B; --J) {
1913  Instruction *EarlierInst = &*std::prev(J);
1914  ARCInstKind EarlierClass = GetARCInstKind(EarlierInst);
1915  switch (EarlierClass) {
1916  case ARCInstKind::LoadWeak:
1918  // If this is loading from the same pointer, replace this load's value
1919  // with that one.
1920  CallInst *Call = cast<CallInst>(Inst);
1921  CallInst *EarlierCall = cast<CallInst>(EarlierInst);
1922  Value *Arg = Call->getArgOperand(0);
1923  Value *EarlierArg = EarlierCall->getArgOperand(0);
1924  switch (PA.getAA()->alias(Arg, EarlierArg)) {
1925  case MustAlias:
1926  Changed = true;
1927  // If the load has a builtin retain, insert a plain retain for it.
1928  if (Class == ARCInstKind::LoadWeakRetained) {
1930  CallInst *CI = CallInst::Create(Decl, EarlierCall, "", Call);
1931  CI->setTailCall();
1932  }
1933  // Zap the fully redundant load.
1934  Call->replaceAllUsesWith(EarlierCall);
1935  Call->eraseFromParent();
1936  goto clobbered;
1937  case MayAlias:
1938  case PartialAlias:
1939  goto clobbered;
1940  case NoAlias:
1941  break;
1942  }
1943  break;
1944  }
1946  case ARCInstKind::InitWeak: {
1947  // If this is storing to the same pointer and has the same size etc.
1948  // replace this load's value with the stored value.
1949  CallInst *Call = cast<CallInst>(Inst);
1950  CallInst *EarlierCall = cast<CallInst>(EarlierInst);
1951  Value *Arg = Call->getArgOperand(0);
1952  Value *EarlierArg = EarlierCall->getArgOperand(0);
1953  switch (PA.getAA()->alias(Arg, EarlierArg)) {
1954  case MustAlias:
1955  Changed = true;
1956  // If the load has a builtin retain, insert a plain retain for it.
1957  if (Class == ARCInstKind::LoadWeakRetained) {
1959  CallInst *CI = CallInst::Create(Decl, EarlierCall, "", Call);
1960  CI->setTailCall();
1961  }
1962  // Zap the fully redundant load.
1963  Call->replaceAllUsesWith(EarlierCall->getArgOperand(1));
1964  Call->eraseFromParent();
1965  goto clobbered;
1966  case MayAlias:
1967  case PartialAlias:
1968  goto clobbered;
1969  case NoAlias:
1970  break;
1971  }
1972  break;
1973  }
1974  case ARCInstKind::MoveWeak:
1975  case ARCInstKind::CopyWeak:
1976  // TOOD: Grab the copied value.
1977  goto clobbered;
1979  case ARCInstKind::None:
1981  case ARCInstKind::User:
1982  // Weak pointers are only modified through the weak entry points
1983  // (and arbitrary calls, which could call the weak entry points).
1984  break;
1985  default:
1986  // Anything else could modify the weak pointer.
1987  goto clobbered;
1988  }
1989  }
1990  clobbered:;
1991  }
1992 
1993  // Then, for each destroyWeak with an alloca operand, check to see if
1994  // the alloca and all its users can be zapped.
1995  for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
1996  Instruction *Inst = &*I++;
1997  ARCInstKind Class = GetBasicARCInstKind(Inst);
1998  if (Class != ARCInstKind::DestroyWeak)
1999  continue;
2000 
2001  CallInst *Call = cast<CallInst>(Inst);
2002  Value *Arg = Call->getArgOperand(0);
2003  if (AllocaInst *Alloca = dyn_cast<AllocaInst>(Arg)) {
2004  for (User *U : Alloca->users()) {
2005  const Instruction *UserInst = cast<Instruction>(U);
2006  switch (GetBasicARCInstKind(UserInst)) {
2007  case ARCInstKind::InitWeak:
2010  continue;
2011  default:
2012  goto done;
2013  }
2014  }
2015  Changed = true;
2016  for (auto UI = Alloca->user_begin(), UE = Alloca->user_end(); UI != UE;) {
2017  CallInst *UserInst = cast<CallInst>(*UI++);
2018  switch (GetBasicARCInstKind(UserInst)) {
2019  case ARCInstKind::InitWeak:
2021  // These functions return their second argument.
2022  UserInst->replaceAllUsesWith(UserInst->getArgOperand(1));
2023  break;
2025  // No return value.
2026  break;
2027  default:
2028  llvm_unreachable("alloca really is used!");
2029  }
2030  UserInst->eraseFromParent();
2031  }
2032  Alloca->eraseFromParent();
2033  done:;
2034  }
2035  }
2036 }
2037 
2038 /// Identify program paths which execute sequences of retains and releases which
2039 /// can be eliminated.
2040 bool ObjCARCOpt::OptimizeSequences(Function &F) {
2041  // Releases, Retains - These are used to store the results of the main flow
2042  // analysis. These use Value* as the key instead of Instruction* so that the
2043  // map stays valid when we get around to rewriting code and calls get
2044  // replaced by arguments.
2045  DenseMap<Value *, RRInfo> Releases;
2047 
2048  // This is used during the traversal of the function to track the
2049  // states for each identified object at each block.
2051 
2052  // Analyze the CFG of the function, and all instructions.
2053  bool NestingDetected = Visit(F, BBStates, Retains, Releases);
2054 
2055  if (DisableRetainReleasePairing)
2056  return false;
2057 
2058  // Transform.
2059  bool AnyPairsCompletelyEliminated = PerformCodePlacement(BBStates, Retains,
2060  Releases,
2061  F.getParent());
2062 
2063  return AnyPairsCompletelyEliminated && NestingDetected;
2064 }
2065 
2066 /// Check if there is a dependent call earlier that does not have anything in
2067 /// between the Retain and the call that can affect the reference count of their
2068 /// shared pointer argument. Note that Retain need not be in BB.
2069 static bool
2073  ProvenanceAnalysis &PA) {
2075  DepInsts, Visited, PA);
2076  if (DepInsts.size() != 1)
2077  return false;
2078 
2079  auto *Call = dyn_cast_or_null<CallInst>(*DepInsts.begin());
2080 
2081  // Check that the pointer is the return value of the call.
2082  if (!Call || Arg != Call)
2083  return false;
2084 
2085  // Check that the call is a regular call.
2087  return Class == ARCInstKind::CallOrUser || Class == ARCInstKind::Call;
2088 }
2089 
2090 /// Find a dependent retain that precedes the given autorelease for which there
2091 /// is nothing in between the two instructions that can affect the ref count of
2092 /// Arg.
2093 static CallInst *
2098  ProvenanceAnalysis &PA) {
2100  BB, Autorelease, DepInsts, Visited, PA);
2101  if (DepInsts.size() != 1)
2102  return nullptr;
2103 
2104  auto *Retain = dyn_cast_or_null<CallInst>(*DepInsts.begin());
2105 
2106  // Check that we found a retain with the same argument.
2107  if (!Retain || !IsRetain(GetBasicARCInstKind(Retain)) ||
2108  GetArgRCIdentityRoot(Retain) != Arg) {
2109  return nullptr;
2110  }
2111 
2112  return Retain;
2113 }
2114 
2115 /// Look for an ``autorelease'' instruction dependent on Arg such that there are
2116 /// no instructions dependent on Arg that need a positive ref count in between
2117 /// the autorelease and the ret.
2118 static CallInst *
2120  ReturnInst *Ret,
2123  ProvenanceAnalysis &PA) {
2125  BB, Ret, DepInsts, V, PA);
2126  if (DepInsts.size() != 1)
2127  return nullptr;
2128 
2129  auto *Autorelease = dyn_cast_or_null<CallInst>(*DepInsts.begin());
2130  if (!Autorelease)
2131  return nullptr;
2132  ARCInstKind AutoreleaseClass = GetBasicARCInstKind(Autorelease);
2133  if (!IsAutorelease(AutoreleaseClass))
2134  return nullptr;
2135  if (GetArgRCIdentityRoot(Autorelease) != Arg)
2136  return nullptr;
2137 
2138  return Autorelease;
2139 }
2140 
2141 /// Look for this pattern:
2142 /// \code
2143 /// %call = call i8* @something(...)
2144 /// %2 = call i8* @objc_retain(i8* %call)
2145 /// %3 = call i8* @objc_autorelease(i8* %2)
2146 /// ret i8* %3
2147 /// \endcode
2148 /// And delete the retain and autorelease.
2149 void ObjCARCOpt::OptimizeReturns(Function &F) {
2150  if (!F.getReturnType()->isPointerTy())
2151  return;
2152 
2153  LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeReturns ==\n");
2154 
2155  SmallPtrSet<Instruction *, 4> DependingInstructions;
2157  for (BasicBlock &BB: F) {
2158  ReturnInst *Ret = dyn_cast<ReturnInst>(&BB.back());
2159  if (!Ret)
2160  continue;
2161 
2162  LLVM_DEBUG(dbgs() << "Visiting: " << *Ret << "\n");
2163 
2164  const Value *Arg = GetRCIdentityRoot(Ret->getOperand(0));
2165 
2166  // Look for an ``autorelease'' instruction that is a predecessor of Ret and
2167  // dependent on Arg such that there are no instructions dependent on Arg
2168  // that need a positive ref count in between the autorelease and Ret.
2170  Arg, &BB, Ret, DependingInstructions, Visited, PA);
2171  DependingInstructions.clear();
2172  Visited.clear();
2173 
2174  if (!Autorelease)
2175  continue;
2176 
2178  Arg, Autorelease->getParent(), Autorelease, DependingInstructions,
2179  Visited, PA);
2180  DependingInstructions.clear();
2181  Visited.clear();
2182 
2183  if (!Retain)
2184  continue;
2185 
2186  // Check that there is nothing that can affect the reference count
2187  // between the retain and the call. Note that Retain need not be in BB.
2188  bool HasSafePathToCall = HasSafePathToPredecessorCall(Arg, Retain,
2189  DependingInstructions,
2190  Visited, PA);
2191  DependingInstructions.clear();
2192  Visited.clear();
2193 
2194  if (!HasSafePathToCall)
2195  continue;
2196 
2197  // If so, we can zap the retain and autorelease.
2198  Changed = true;
2199  ++NumRets;
2200  LLVM_DEBUG(dbgs() << "Erasing: " << *Retain << "\nErasing: " << *Autorelease
2201  << "\n");
2202  EraseInstruction(Retain);
2203  EraseInstruction(Autorelease);
2204  }
2205 }
2206 
2207 #ifndef NDEBUG
2208 void
2209 ObjCARCOpt::GatherStatistics(Function &F, bool AfterOptimization) {
2210  Statistic &NumRetains =
2211  AfterOptimization ? NumRetainsAfterOpt : NumRetainsBeforeOpt;
2212  Statistic &NumReleases =
2213  AfterOptimization ? NumReleasesAfterOpt : NumReleasesBeforeOpt;
2214 
2215  for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
2216  Instruction *Inst = &*I++;
2217  switch (GetBasicARCInstKind(Inst)) {
2218  default:
2219  break;
2220  case ARCInstKind::Retain:
2221  ++NumRetains;
2222  break;
2223  case ARCInstKind::Release:
2224  ++NumReleases;
2225  break;
2226  }
2227  }
2228 }
2229 #endif
2230 
2231 bool ObjCARCOpt::doInitialization(Module &M) {
2232  if (!EnableARCOpts)
2233  return false;
2234 
2235  // If nothing in the Module uses ARC, don't do anything.
2236  Run = ModuleHasARC(M);
2237  if (!Run)
2238  return false;
2239 
2240  // Intuitively, objc_retain and others are nocapture, however in practice
2241  // they are not, because they return their argument value. And objc_release
2242  // calls finalizers which can have arbitrary side effects.
2243  MDKindCache.init(&M);
2244 
2245  // Initialize our runtime entry point cache.
2246  EP.init(&M);
2247 
2248  return false;
2249 }
2250 
2252  if (!EnableARCOpts)
2253  return false;
2254 
2255  // If nothing in the Module uses ARC, don't do anything.
2256  if (!Run)
2257  return false;
2258 
2259  Changed = false;
2260 
2261  LLVM_DEBUG(dbgs() << "<<< ObjCARCOpt: Visiting Function: " << F.getName()
2262  << " >>>"
2263  "\n");
2264 
2265  PA.setAA(&getAnalysis<AAResultsWrapperPass>().getAAResults());
2266 
2267 #ifndef NDEBUG
2268  if (AreStatisticsEnabled()) {
2269  GatherStatistics(F, false);
2270  }
2271 #endif
2272 
2273  // This pass performs several distinct transformations. As a compile-time aid
2274  // when compiling code that isn't ObjC, skip these if the relevant ObjC
2275  // library functions aren't declared.
2276 
2277  // Preliminary optimizations. This also computes UsedInThisFunction.
2278  OptimizeIndividualCalls(F);
2279 
2280  // Optimizations for weak pointers.
2281  if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::LoadWeak)) |
2282  (1 << unsigned(ARCInstKind::LoadWeakRetained)) |
2283  (1 << unsigned(ARCInstKind::StoreWeak)) |
2284  (1 << unsigned(ARCInstKind::InitWeak)) |
2285  (1 << unsigned(ARCInstKind::CopyWeak)) |
2286  (1 << unsigned(ARCInstKind::MoveWeak)) |
2287  (1 << unsigned(ARCInstKind::DestroyWeak))))
2288  OptimizeWeakCalls(F);
2289 
2290  // Optimizations for retain+release pairs.
2291  if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::Retain)) |
2292  (1 << unsigned(ARCInstKind::RetainRV)) |
2293  (1 << unsigned(ARCInstKind::RetainBlock))))
2294  if (UsedInThisFunction & (1 << unsigned(ARCInstKind::Release)))
2295  // Run OptimizeSequences until it either stops making changes or
2296  // no retain+release pair nesting is detected.
2297  while (OptimizeSequences(F)) {}
2298 
2299  // Optimizations if objc_autorelease is used.
2300  if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::Autorelease)) |
2301  (1 << unsigned(ARCInstKind::AutoreleaseRV))))
2302  OptimizeReturns(F);
2303 
2304  // Gather statistics after optimization.
2305 #ifndef NDEBUG
2306  if (AreStatisticsEnabled()) {
2307  GatherStatistics(F, true);
2308  }
2309 #endif
2310 
2311  LLVM_DEBUG(dbgs() << "\n");
2312 
2313  return Changed;
2314 }
2315 
2316 void ObjCARCOpt::releaseMemory() {
2317  PA.clear();
2318 }
2319 
2320 /// @}
2321 ///
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:641
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:732
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:1246
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:1777
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:1241
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
bool IsNoopOnGlobal(ARCInstKind Class)
Test if the given class represents instructions which do nothing if passed a global variable...
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:877
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:273
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:1323
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:726
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:1728
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)
bool isVoidTy() const
Return true if this is &#39;void&#39;.
Definition: Type.h:140
const BasicBlock & getEntryBlock() const
Definition: Function.h:664
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:875
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
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs, address space casts, and aliases.
Definition: Value.cpp:535
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:559
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:837
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:897
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:575
LLVM Value Representation.
Definition: Value.h:72
Constant * getPersonalityFn() const
Get the personality function associated with this function.
Definition: Function.cpp:1384
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:1684
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.