LLVM  14.0.0git
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"
45 #include "llvm/IR/BasicBlock.h"
46 #include "llvm/IR/CFG.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/InitializePasses.h"
62 #include "llvm/Pass.h"
63 #include "llvm/Support/Casting.h"
65 #include "llvm/Support/Compiler.h"
66 #include "llvm/Support/Debug.h"
70 #include <cassert>
71 #include <iterator>
72 #include <utility>
73 
74 using namespace llvm;
75 using namespace llvm::objcarc;
76 
77 #define DEBUG_TYPE "objc-arc-opts"
78 
79 static cl::opt<unsigned> MaxPtrStates("arc-opt-max-ptr-states",
80  cl::Hidden,
81  cl::desc("Maximum number of ptr states the optimizer keeps track of"),
82  cl::init(4095));
83 
84 /// \defgroup ARCUtilities Utility declarations/definitions specific to ARC.
85 /// @{
86 
87 /// This is similar to GetRCIdentityRoot but it stops as soon
88 /// as it finds a value with multiple uses.
90  // ConstantData (like ConstantPointerNull and UndefValue) is used across
91  // modules. It's never a single-use value.
92  if (isa<ConstantData>(Arg))
93  return nullptr;
94 
95  if (Arg->hasOneUse()) {
96  if (const BitCastInst *BC = dyn_cast<BitCastInst>(Arg))
97  return FindSingleUseIdentifiedObject(BC->getOperand(0));
98  if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Arg))
99  if (GEP->hasAllZeroIndices())
100  return FindSingleUseIdentifiedObject(GEP->getPointerOperand());
103  cast<CallInst>(Arg)->getArgOperand(0));
105  return nullptr;
106  return Arg;
107  }
108 
109  // If we found an identifiable object but it has multiple uses, but they are
110  // trivial uses, we can still consider this to be a single-use value.
112  for (const User *U : Arg->users())
113  if (!U->use_empty() || GetRCIdentityRoot(U) != Arg)
114  return nullptr;
115 
116  return Arg;
117  }
118 
119  return nullptr;
120 }
121 
122 /// @}
123 ///
124 /// \defgroup ARCOpt ARC Optimization.
125 /// @{
126 
127 // TODO: On code like this:
128 //
129 // objc_retain(%x)
130 // stuff_that_cannot_release()
131 // objc_autorelease(%x)
132 // stuff_that_cannot_release()
133 // objc_retain(%x)
134 // stuff_that_cannot_release()
135 // objc_autorelease(%x)
136 //
137 // The second retain and autorelease can be deleted.
138 
139 // TODO: It should be possible to delete
140 // objc_autoreleasePoolPush and objc_autoreleasePoolPop
141 // pairs if nothing is actually autoreleased between them. Also, autorelease
142 // calls followed by objc_autoreleasePoolPop calls (perhaps in ObjC++ code
143 // after inlining) can be turned into plain release calls.
144 
145 // TODO: Critical-edge splitting. If the optimial insertion point is
146 // a critical edge, the current algorithm has to fail, because it doesn't
147 // know how to split edges. It should be possible to make the optimizer
148 // think in terms of edges, rather than blocks, and then split critical
149 // edges on demand.
150 
151 // TODO: OptimizeSequences could generalized to be Interprocedural.
152 
153 // TODO: Recognize that a bunch of other objc runtime calls have
154 // non-escaping arguments and non-releasing arguments, and may be
155 // non-autoreleasing.
156 
157 // TODO: Sink autorelease calls as far as possible. Unfortunately we
158 // usually can't sink them past other calls, which would be the main
159 // case where it would be useful.
160 
161 // TODO: The pointer returned from objc_loadWeakRetained is retained.
162 
163 // TODO: Delete release+retain pairs (rare).
164 
165 STATISTIC(NumNoops, "Number of no-op objc calls eliminated");
166 STATISTIC(NumPartialNoops, "Number of partially no-op objc calls eliminated");
167 STATISTIC(NumAutoreleases,"Number of autoreleases converted to releases");
168 STATISTIC(NumRets, "Number of return value forwarding "
169  "retain+autoreleases eliminated");
170 STATISTIC(NumRRs, "Number of retain+release paths eliminated");
171 STATISTIC(NumPeeps, "Number of calls peephole-optimized");
172 #ifndef NDEBUG
173 STATISTIC(NumRetainsBeforeOpt,
174  "Number of retains before optimization");
175 STATISTIC(NumReleasesBeforeOpt,
176  "Number of releases before optimization");
177 STATISTIC(NumRetainsAfterOpt,
178  "Number of retains after optimization");
179 STATISTIC(NumReleasesAfterOpt,
180  "Number of releases after optimization");
181 #endif
182 
183 namespace {
184 
185  /// Per-BasicBlock state.
186  class BBState {
187  /// The number of unique control paths from the entry which can reach this
188  /// block.
189  unsigned TopDownPathCount = 0;
190 
191  /// The number of unique control paths to exits from this block.
192  unsigned BottomUpPathCount = 0;
193 
194  /// The top-down traversal uses this to record information known about a
195  /// pointer at the bottom of each block.
197 
198  /// The bottom-up traversal uses this to record information known about a
199  /// pointer at the top of each block.
201 
202  /// Effective predecessors of the current block ignoring ignorable edges and
203  /// ignored backedges.
205 
206  /// Effective successors of the current block ignoring ignorable edges and
207  /// ignored backedges.
209 
210  public:
211  static const unsigned OverflowOccurredValue;
212 
213  BBState() = default;
214 
215  using top_down_ptr_iterator = decltype(PerPtrTopDown)::iterator;
216  using const_top_down_ptr_iterator = decltype(PerPtrTopDown)::const_iterator;
217 
218  top_down_ptr_iterator top_down_ptr_begin() { return PerPtrTopDown.begin(); }
219  top_down_ptr_iterator top_down_ptr_end() { return PerPtrTopDown.end(); }
220  const_top_down_ptr_iterator top_down_ptr_begin() const {
221  return PerPtrTopDown.begin();
222  }
223  const_top_down_ptr_iterator top_down_ptr_end() const {
224  return PerPtrTopDown.end();
225  }
226  bool hasTopDownPtrs() const {
227  return !PerPtrTopDown.empty();
228  }
229 
230  unsigned top_down_ptr_list_size() const {
231  return std::distance(top_down_ptr_begin(), top_down_ptr_end());
232  }
233 
234  using bottom_up_ptr_iterator = decltype(PerPtrBottomUp)::iterator;
235  using const_bottom_up_ptr_iterator =
236  decltype(PerPtrBottomUp)::const_iterator;
237 
238  bottom_up_ptr_iterator bottom_up_ptr_begin() {
239  return PerPtrBottomUp.begin();
240  }
241  bottom_up_ptr_iterator bottom_up_ptr_end() { return PerPtrBottomUp.end(); }
242  const_bottom_up_ptr_iterator bottom_up_ptr_begin() const {
243  return PerPtrBottomUp.begin();
244  }
245  const_bottom_up_ptr_iterator bottom_up_ptr_end() const {
246  return PerPtrBottomUp.end();
247  }
248  bool hasBottomUpPtrs() const {
249  return !PerPtrBottomUp.empty();
250  }
251 
252  unsigned bottom_up_ptr_list_size() const {
253  return std::distance(bottom_up_ptr_begin(), bottom_up_ptr_end());
254  }
255 
256  /// Mark this block as being an entry block, which has one path from the
257  /// entry by definition.
258  void SetAsEntry() { TopDownPathCount = 1; }
259 
260  /// Mark this block as being an exit block, which has one path to an exit by
261  /// definition.
262  void SetAsExit() { BottomUpPathCount = 1; }
263 
264  /// Attempt to find the PtrState object describing the top down state for
265  /// pointer Arg. Return a new initialized PtrState describing the top down
266  /// state for Arg if we do not find one.
267  TopDownPtrState &getPtrTopDownState(const Value *Arg) {
268  return PerPtrTopDown[Arg];
269  }
270 
271  /// Attempt to find the PtrState object describing the bottom up state for
272  /// pointer Arg. Return a new initialized PtrState describing the bottom up
273  /// state for Arg if we do not find one.
274  BottomUpPtrState &getPtrBottomUpState(const Value *Arg) {
275  return PerPtrBottomUp[Arg];
276  }
277 
278  /// Attempt to find the PtrState object describing the bottom up state for
279  /// pointer Arg.
280  bottom_up_ptr_iterator findPtrBottomUpState(const Value *Arg) {
281  return PerPtrBottomUp.find(Arg);
282  }
283 
284  void clearBottomUpPointers() {
285  PerPtrBottomUp.clear();
286  }
287 
288  void clearTopDownPointers() {
289  PerPtrTopDown.clear();
290  }
291 
292  void InitFromPred(const BBState &Other);
293  void InitFromSucc(const BBState &Other);
294  void MergePred(const BBState &Other);
295  void MergeSucc(const BBState &Other);
296 
297  /// Compute the number of possible unique paths from an entry to an exit
298  /// which pass through this block. This is only valid after both the
299  /// top-down and bottom-up traversals are complete.
300  ///
301  /// Returns true if overflow occurred. Returns false if overflow did not
302  /// occur.
303  bool GetAllPathCountWithOverflow(unsigned &PathCount) const {
304  if (TopDownPathCount == OverflowOccurredValue ||
305  BottomUpPathCount == OverflowOccurredValue)
306  return true;
307  unsigned long long Product =
308  (unsigned long long)TopDownPathCount*BottomUpPathCount;
309  // Overflow occurred if any of the upper bits of Product are set or if all
310  // the lower bits of Product are all set.
311  return (Product >> 32) ||
312  ((PathCount = Product) == OverflowOccurredValue);
313  }
314 
315  // Specialized CFG utilities.
316  using edge_iterator = SmallVectorImpl<BasicBlock *>::const_iterator;
317 
318  edge_iterator pred_begin() const { return Preds.begin(); }
319  edge_iterator pred_end() const { return Preds.end(); }
320  edge_iterator succ_begin() const { return Succs.begin(); }
321  edge_iterator succ_end() const { return Succs.end(); }
322 
323  void addSucc(BasicBlock *Succ) { Succs.push_back(Succ); }
324  void addPred(BasicBlock *Pred) { Preds.push_back(Pred); }
325 
326  bool isExit() const { return Succs.empty(); }
327  };
328 
329 } // end anonymous namespace
330 
331 const unsigned BBState::OverflowOccurredValue = 0xffffffff;
332 
333 namespace llvm {
334 
336  BBState &BBState) LLVM_ATTRIBUTE_UNUSED;
337 
338 } // end namespace llvm
339 
340 void BBState::InitFromPred(const BBState &Other) {
341  PerPtrTopDown = Other.PerPtrTopDown;
342  TopDownPathCount = Other.TopDownPathCount;
343 }
344 
345 void BBState::InitFromSucc(const BBState &Other) {
346  PerPtrBottomUp = Other.PerPtrBottomUp;
347  BottomUpPathCount = Other.BottomUpPathCount;
348 }
349 
350 /// The top-down traversal uses this to merge information about predecessors to
351 /// form the initial state for a new block.
352 void BBState::MergePred(const BBState &Other) {
353  if (TopDownPathCount == OverflowOccurredValue)
354  return;
355 
356  // Other.TopDownPathCount can be 0, in which case it is either dead or a
357  // loop backedge. Loop backedges are special.
358  TopDownPathCount += Other.TopDownPathCount;
359 
360  // In order to be consistent, we clear the top down pointers when by adding
361  // TopDownPathCount becomes OverflowOccurredValue even though "true" overflow
362  // has not occurred.
363  if (TopDownPathCount == OverflowOccurredValue) {
364  clearTopDownPointers();
365  return;
366  }
367 
368  // Check for overflow. If we have overflow, fall back to conservative
369  // behavior.
370  if (TopDownPathCount < Other.TopDownPathCount) {
371  TopDownPathCount = OverflowOccurredValue;
372  clearTopDownPointers();
373  return;
374  }
375 
376  // For each entry in the other set, if our set has an entry with the same key,
377  // merge the entries. Otherwise, copy the entry and merge it with an empty
378  // entry.
379  for (auto MI = Other.top_down_ptr_begin(), ME = Other.top_down_ptr_end();
380  MI != ME; ++MI) {
381  auto Pair = PerPtrTopDown.insert(*MI);
382  Pair.first->second.Merge(Pair.second ? TopDownPtrState() : MI->second,
383  /*TopDown=*/true);
384  }
385 
386  // For each entry in our set, if the other set doesn't have an entry with the
387  // same key, force it to merge with an empty entry.
388  for (auto MI = top_down_ptr_begin(), ME = top_down_ptr_end(); MI != ME; ++MI)
389  if (Other.PerPtrTopDown.find(MI->first) == Other.PerPtrTopDown.end())
390  MI->second.Merge(TopDownPtrState(), /*TopDown=*/true);
391 }
392 
393 /// The bottom-up traversal uses this to merge information about successors to
394 /// form the initial state for a new block.
395 void BBState::MergeSucc(const BBState &Other) {
396  if (BottomUpPathCount == OverflowOccurredValue)
397  return;
398 
399  // Other.BottomUpPathCount can be 0, in which case it is either dead or a
400  // loop backedge. Loop backedges are special.
401  BottomUpPathCount += Other.BottomUpPathCount;
402 
403  // In order to be consistent, we clear the top down pointers when by adding
404  // BottomUpPathCount becomes OverflowOccurredValue even though "true" overflow
405  // has not occurred.
406  if (BottomUpPathCount == OverflowOccurredValue) {
407  clearBottomUpPointers();
408  return;
409  }
410 
411  // Check for overflow. If we have overflow, fall back to conservative
412  // behavior.
413  if (BottomUpPathCount < Other.BottomUpPathCount) {
414  BottomUpPathCount = OverflowOccurredValue;
415  clearBottomUpPointers();
416  return;
417  }
418 
419  // For each entry in the other set, if our set has an entry with the
420  // same key, merge the entries. Otherwise, copy the entry and merge
421  // it with an empty entry.
422  for (auto MI = Other.bottom_up_ptr_begin(), ME = Other.bottom_up_ptr_end();
423  MI != ME; ++MI) {
424  auto Pair = PerPtrBottomUp.insert(*MI);
425  Pair.first->second.Merge(Pair.second ? BottomUpPtrState() : MI->second,
426  /*TopDown=*/false);
427  }
428 
429  // For each entry in our set, if the other set doesn't have an entry
430  // with the same key, force it to merge with an empty entry.
431  for (auto MI = bottom_up_ptr_begin(), ME = bottom_up_ptr_end(); MI != ME;
432  ++MI)
433  if (Other.PerPtrBottomUp.find(MI->first) == Other.PerPtrBottomUp.end())
434  MI->second.Merge(BottomUpPtrState(), /*TopDown=*/false);
435 }
436 
437 raw_ostream &llvm::operator<<(raw_ostream &OS, BBState &BBInfo) {
438  // Dump the pointers we are tracking.
439  OS << " TopDown State:\n";
440  if (!BBInfo.hasTopDownPtrs()) {
441  LLVM_DEBUG(dbgs() << " NONE!\n");
442  } else {
443  for (auto I = BBInfo.top_down_ptr_begin(), E = BBInfo.top_down_ptr_end();
444  I != E; ++I) {
445  const PtrState &P = I->second;
446  OS << " Ptr: " << *I->first
447  << "\n KnownSafe: " << (P.IsKnownSafe()?"true":"false")
448  << "\n ImpreciseRelease: "
449  << (P.IsTrackingImpreciseReleases()?"true":"false") << "\n"
450  << " HasCFGHazards: "
451  << (P.IsCFGHazardAfflicted()?"true":"false") << "\n"
452  << " KnownPositive: "
453  << (P.HasKnownPositiveRefCount()?"true":"false") << "\n"
454  << " Seq: "
455  << P.GetSeq() << "\n";
456  }
457  }
458 
459  OS << " BottomUp State:\n";
460  if (!BBInfo.hasBottomUpPtrs()) {
461  LLVM_DEBUG(dbgs() << " NONE!\n");
462  } else {
463  for (auto I = BBInfo.bottom_up_ptr_begin(), E = BBInfo.bottom_up_ptr_end();
464  I != E; ++I) {
465  const PtrState &P = I->second;
466  OS << " Ptr: " << *I->first
467  << "\n KnownSafe: " << (P.IsKnownSafe()?"true":"false")
468  << "\n ImpreciseRelease: "
469  << (P.IsTrackingImpreciseReleases()?"true":"false") << "\n"
470  << " HasCFGHazards: "
471  << (P.IsCFGHazardAfflicted()?"true":"false") << "\n"
472  << " KnownPositive: "
473  << (P.HasKnownPositiveRefCount()?"true":"false") << "\n"
474  << " Seq: "
475  << P.GetSeq() << "\n";
476  }
477  }
478 
479  return OS;
480 }
481 
482 namespace {
483 
484  /// The main ARC optimization pass.
485 class ObjCARCOpt {
486  bool Changed;
487  bool CFGChanged;
489 
490  /// A cache of references to runtime entry point constants.
492 
493  /// A cache of MDKinds that can be passed into other functions to propagate
494  /// MDKind identifiers.
495  ARCMDKindCache MDKindCache;
496 
497  BundledRetainClaimRVs *BundledInsts = nullptr;
498 
499  /// A flag indicating whether the optimization that removes or moves
500  /// retain/release pairs should be performed.
501  bool DisableRetainReleasePairing = false;
502 
503  /// Flags which determine whether each of the interesting runtime functions
504  /// is in fact used in the current function.
505  unsigned UsedInThisFunction;
506 
507  bool OptimizeRetainRVCall(Function &F, Instruction *RetainRV);
508  void OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV,
509  ARCInstKind &Class);
510  void OptimizeIndividualCalls(Function &F);
511 
512  /// Optimize an individual call, optionally passing the
513  /// GetArgRCIdentityRoot if it has already been computed.
514  void OptimizeIndividualCallImpl(
516  Instruction *Inst, ARCInstKind Class, const Value *Arg);
517 
518  /// Try to optimize an AutoreleaseRV with a RetainRV or ClaimRV. If the
519  /// optimization occurs, returns true to indicate that the caller should
520  /// assume the instructions are dead.
521  bool OptimizeInlinedAutoreleaseRVCall(
523  Instruction *Inst, const Value *&Arg, ARCInstKind Class,
524  Instruction *AutoreleaseRV, const Value *&AutoreleaseRVArg);
525 
526  void CheckForCFGHazards(const BasicBlock *BB,
528  BBState &MyStates) const;
529  bool VisitInstructionBottomUp(Instruction *Inst, BasicBlock *BB,
531  BBState &MyStates);
532  bool VisitBottomUp(BasicBlock *BB,
535  bool VisitInstructionTopDown(
536  Instruction *Inst, DenseMap<Value *, RRInfo> &Releases, BBState &MyStates,
538  &ReleaseInsertPtToRCIdentityRoots);
539  bool VisitTopDown(
541  DenseMap<Value *, RRInfo> &Releases,
543  &ReleaseInsertPtToRCIdentityRoots);
544  bool Visit(Function &F, DenseMap<const BasicBlock *, BBState> &BBStates,
546  DenseMap<Value *, RRInfo> &Releases);
547 
548  void MoveCalls(Value *Arg, RRInfo &RetainsToMove, RRInfo &ReleasesToMove,
550  DenseMap<Value *, RRInfo> &Releases,
551  SmallVectorImpl<Instruction *> &DeadInsts, Module *M);
552 
553  bool PairUpRetainsAndReleases(DenseMap<const BasicBlock *, BBState> &BBStates,
555  DenseMap<Value *, RRInfo> &Releases, Module *M,
556  Instruction *Retain,
558  RRInfo &RetainsToMove, RRInfo &ReleasesToMove,
559  Value *Arg, bool KnownSafe,
560  bool &AnyPairsCompletelyEliminated);
561 
562  bool PerformCodePlacement(DenseMap<const BasicBlock *, BBState> &BBStates,
564  DenseMap<Value *, RRInfo> &Releases, Module *M);
565 
566  void OptimizeWeakCalls(Function &F);
567 
568  bool OptimizeSequences(Function &F);
569 
570  void OptimizeReturns(Function &F);
571 
572 #ifndef NDEBUG
573  void GatherStatistics(Function &F, bool AfterOptimization = false);
574 #endif
575 
576  public:
577  void init(Module &M);
578  bool run(Function &F, AAResults &AA);
579  void releaseMemory();
580  bool hasCFGChanged() const { return CFGChanged; }
581 };
582 
583 /// The main ARC optimization pass.
584 class ObjCARCOptLegacyPass : public FunctionPass {
585 public:
586  ObjCARCOptLegacyPass() : FunctionPass(ID) {
588  }
589  void getAnalysisUsage(AnalysisUsage &AU) const override;
590  bool doInitialization(Module &M) override {
591  OCAO.init(M);
592  return false;
593  }
594  bool runOnFunction(Function &F) override {
595  return OCAO.run(F, getAnalysis<AAResultsWrapperPass>().getAAResults());
596  }
597  void releaseMemory() override { OCAO.releaseMemory(); }
598  static char ID;
599 
600 private:
601  ObjCARCOpt OCAO;
602 };
603 } // end anonymous namespace
604 
605 char ObjCARCOptLegacyPass::ID = 0;
606 
607 INITIALIZE_PASS_BEGIN(ObjCARCOptLegacyPass, "objc-arc", "ObjC ARC optimization",
608  false, false)
610 INITIALIZE_PASS_END(ObjCARCOptLegacyPass, "objc-arc", "ObjC ARC optimization",
612 
613 Pass *llvm::createObjCARCOptPass() { return new ObjCARCOptLegacyPass(); }
614 
615 void ObjCARCOptLegacyPass::getAnalysisUsage(AnalysisUsage &AU) const {
618 }
619 
620 /// Turn objc_retainAutoreleasedReturnValue into objc_retain if the operand is
621 /// not a return value.
622 bool
623 ObjCARCOpt::OptimizeRetainRVCall(Function &F, Instruction *RetainRV) {
624  // Check for the argument being from an immediately preceding call or invoke.
625  const Value *Arg = GetArgRCIdentityRoot(RetainRV);
626  if (const Instruction *Call = dyn_cast<CallBase>(Arg)) {
627  if (Call->getParent() == RetainRV->getParent()) {
629  ++I;
630  while (IsNoopInstruction(&*I))
631  ++I;
632  if (&*I == RetainRV)
633  return false;
634  } else if (const InvokeInst *II = dyn_cast<InvokeInst>(Call)) {
635  BasicBlock *RetainRVParent = RetainRV->getParent();
636  if (II->getNormalDest() == RetainRVParent) {
637  BasicBlock::const_iterator I = RetainRVParent->begin();
638  while (IsNoopInstruction(&*I))
639  ++I;
640  if (&*I == RetainRV)
641  return false;
642  }
643  }
644  }
645 
646  assert(!BundledInsts->contains(RetainRV) &&
647  "a bundled retainRV's argument should be a call");
648 
649  // Turn it to a plain objc_retain.
650  Changed = true;
651  ++NumPeeps;
652 
653  LLVM_DEBUG(dbgs() << "Transforming objc_retainAutoreleasedReturnValue => "
654  "objc_retain since the operand is not a return value.\n"
655  "Old = "
656  << *RetainRV << "\n");
657 
658  Function *NewDecl = EP.get(ARCRuntimeEntryPointKind::Retain);
659  cast<CallInst>(RetainRV)->setCalledFunction(NewDecl);
660 
661  LLVM_DEBUG(dbgs() << "New = " << *RetainRV << "\n");
662 
663  return false;
664 }
665 
666 bool ObjCARCOpt::OptimizeInlinedAutoreleaseRVCall(
668  Instruction *Inst, const Value *&Arg, ARCInstKind Class,
669  Instruction *AutoreleaseRV, const Value *&AutoreleaseRVArg) {
670  if (BundledInsts->contains(Inst))
671  return false;
672 
673  // Must be in the same basic block.
674  assert(Inst->getParent() == AutoreleaseRV->getParent());
675 
676  // Must operate on the same root.
677  Arg = GetArgRCIdentityRoot(Inst);
678  AutoreleaseRVArg = GetArgRCIdentityRoot(AutoreleaseRV);
679  if (Arg != AutoreleaseRVArg) {
680  // If there isn't an exact match, check if we have equivalent PHIs.
681  const PHINode *PN = dyn_cast<PHINode>(Arg);
682  if (!PN)
683  return false;
684 
686  getEquivalentPHIs(*PN, ArgUsers);
687  if (!llvm::is_contained(ArgUsers, AutoreleaseRVArg))
688  return false;
689  }
690 
691  // Okay, this is a match. Merge them.
692  ++NumPeeps;
693  LLVM_DEBUG(dbgs() << "Found inlined objc_autoreleaseReturnValue '"
694  << *AutoreleaseRV << "' paired with '" << *Inst << "'\n");
695 
696  // Delete the RV pair, starting with the AutoreleaseRV.
697  AutoreleaseRV->replaceAllUsesWith(
698  cast<CallInst>(AutoreleaseRV)->getArgOperand(0));
699  Changed = true;
700  EraseInstruction(AutoreleaseRV);
701  if (Class == ARCInstKind::RetainRV) {
702  // AutoreleaseRV and RetainRV cancel out. Delete the RetainRV.
703  Inst->replaceAllUsesWith(cast<CallInst>(Inst)->getArgOperand(0));
704  EraseInstruction(Inst);
705  return true;
706  }
707 
708  // ClaimRV is a frontend peephole for RetainRV + Release. Since the
709  // AutoreleaseRV and RetainRV cancel out, replace the ClaimRV with a Release.
710  assert(Class == ARCInstKind::ClaimRV);
711  Value *CallArg = cast<CallInst>(Inst)->getArgOperand(0);
713  EP.get(ARCRuntimeEntryPointKind::Release), CallArg, "", Inst);
715  "Expected ClaimRV to be safe to tail call");
716  Release->setTailCall();
718  EraseInstruction(Inst);
719 
720  // Run the normal optimizations on Release.
721  OptimizeIndividualCallImpl(F, BlockColors, Release, ARCInstKind::Release,
722  Arg);
723  return true;
724 }
725 
726 /// Turn objc_autoreleaseReturnValue into objc_autorelease if the result is not
727 /// used as a return value.
728 void ObjCARCOpt::OptimizeAutoreleaseRVCall(Function &F,
729  Instruction *AutoreleaseRV,
730  ARCInstKind &Class) {
731  // Check for a return of the pointer value.
732  const Value *Ptr = GetArgRCIdentityRoot(AutoreleaseRV);
733 
734  // If the argument is ConstantPointerNull or UndefValue, its other users
735  // aren't actually interesting to look at.
736  if (isa<ConstantData>(Ptr))
737  return;
738 
740  Users.push_back(Ptr);
741 
742  // Add PHIs that are equivalent to Ptr to Users.
743  if (const PHINode *PN = dyn_cast<PHINode>(Ptr))
744  getEquivalentPHIs(*PN, Users);
745 
746  do {
747  Ptr = Users.pop_back_val();
748  for (const User *U : Ptr->users()) {
749  if (isa<ReturnInst>(U) || GetBasicARCInstKind(U) == ARCInstKind::RetainRV)
750  return;
751  if (isa<BitCastInst>(U))
752  Users.push_back(U);
753  }
754  } while (!Users.empty());
755 
756  Changed = true;
757  ++NumPeeps;
758 
759  LLVM_DEBUG(
760  dbgs() << "Transforming objc_autoreleaseReturnValue => "
761  "objc_autorelease since its operand is not used as a return "
762  "value.\n"
763  "Old = "
764  << *AutoreleaseRV << "\n");
765 
766  CallInst *AutoreleaseRVCI = cast<CallInst>(AutoreleaseRV);
768  AutoreleaseRVCI->setCalledFunction(NewDecl);
769  AutoreleaseRVCI->setTailCall(false); // Never tail call objc_autorelease.
771 
772  LLVM_DEBUG(dbgs() << "New: " << *AutoreleaseRV << "\n");
773 }
774 
775 namespace {
776 Instruction *
777 CloneCallInstForBB(CallInst &CI, BasicBlock &BB,
778  const DenseMap<BasicBlock *, ColorVector> &BlockColors) {
780  for (unsigned I = 0, E = CI.getNumOperandBundles(); I != E; ++I) {
781  auto Bundle = CI.getOperandBundleAt(I);
782  // Funclets will be reassociated in the future.
783  if (Bundle.getTagID() == LLVMContext::OB_funclet)
784  continue;
785  OpBundles.emplace_back(Bundle);
786  }
787 
788  if (!BlockColors.empty()) {
789  const ColorVector &CV = BlockColors.find(&BB)->second;
790  assert(CV.size() == 1 && "non-unique color for block!");
791  Instruction *EHPad = CV.front()->getFirstNonPHI();
792  if (EHPad->isEHPad())
793  OpBundles.emplace_back("funclet", EHPad);
794  }
795 
796  return CallInst::Create(&CI, OpBundles);
797 }
798 }
799 
800 /// Visit each call, one at a time, and make simplifications without doing any
801 /// additional analysis.
802 void ObjCARCOpt::OptimizeIndividualCalls(Function &F) {
803  LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeIndividualCalls ==\n");
804  // Reset all the flags in preparation for recomputing them.
805  UsedInThisFunction = 0;
806 
808  if (F.hasPersonalityFn() &&
809  isScopedEHPersonality(classifyEHPersonality(F.getPersonalityFn())))
810  BlockColors = colorEHFunclets(F);
811 
812  // Store any delayed AutoreleaseRV intrinsics, so they can be easily paired
813  // with RetainRV and ClaimRV.
814  Instruction *DelayedAutoreleaseRV = nullptr;
815  const Value *DelayedAutoreleaseRVArg = nullptr;
816  auto setDelayedAutoreleaseRV = [&](Instruction *AutoreleaseRV) {
817  assert(!DelayedAutoreleaseRV || !AutoreleaseRV);
818  DelayedAutoreleaseRV = AutoreleaseRV;
819  DelayedAutoreleaseRVArg = nullptr;
820  };
821  auto optimizeDelayedAutoreleaseRV = [&]() {
822  if (!DelayedAutoreleaseRV)
823  return;
824  OptimizeIndividualCallImpl(F, BlockColors, DelayedAutoreleaseRV,
826  DelayedAutoreleaseRVArg);
827  setDelayedAutoreleaseRV(nullptr);
828  };
829  auto shouldDelayAutoreleaseRV = [&](Instruction *NonARCInst) {
830  // Nothing to delay, but we may as well skip the logic below.
831  if (!DelayedAutoreleaseRV)
832  return true;
833 
834  // If we hit the end of the basic block we're not going to find an RV-pair.
835  // Stop delaying.
836  if (NonARCInst->isTerminator())
837  return false;
838 
839  // Given the frontend rules for emitting AutoreleaseRV, RetainRV, and
840  // ClaimRV, it's probably safe to skip over even opaque function calls
841  // here since OptimizeInlinedAutoreleaseRVCall will confirm that they
842  // have the same RCIdentityRoot. However, what really matters is
843  // skipping instructions or intrinsics that the inliner could leave behind;
844  // be conservative for now and don't skip over opaque calls, which could
845  // potentially include other ARC calls.
846  auto *CB = dyn_cast<CallBase>(NonARCInst);
847  if (!CB)
848  return true;
849  return CB->getIntrinsicID() != Intrinsic::not_intrinsic;
850  };
851 
852  // Visit all objc_* calls in F.
853  for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
854  Instruction *Inst = &*I++;
855 
856  if (auto *CI = dyn_cast<CallInst>(Inst))
858  BundledInsts->insertRVCall(&*I, CI);
859  Changed = true;
860  }
861 
863 
864  // Skip this loop if this instruction isn't itself an ARC intrinsic.
865  const Value *Arg = nullptr;
866  switch (Class) {
867  default:
868  optimizeDelayedAutoreleaseRV();
869  break;
871  case ARCInstKind::User:
872  case ARCInstKind::None:
873  // This is a non-ARC instruction. If we're delaying an AutoreleaseRV,
874  // check if it's safe to skip over it; if not, optimize the AutoreleaseRV
875  // now.
876  if (!shouldDelayAutoreleaseRV(Inst))
877  optimizeDelayedAutoreleaseRV();
878  continue;
880  optimizeDelayedAutoreleaseRV();
881  setDelayedAutoreleaseRV(Inst);
882  continue;
885  if (DelayedAutoreleaseRV) {
886  // We have a potential RV pair. Check if they cancel out.
887  if (OptimizeInlinedAutoreleaseRVCall(F, BlockColors, Inst, Arg, Class,
888  DelayedAutoreleaseRV,
889  DelayedAutoreleaseRVArg)) {
890  setDelayedAutoreleaseRV(nullptr);
891  continue;
892  }
893  optimizeDelayedAutoreleaseRV();
894  }
895  break;
896  }
897 
898  OptimizeIndividualCallImpl(F, BlockColors, Inst, Class, Arg);
899  }
900 
901  // Catch the final delayed AutoreleaseRV.
902  optimizeDelayedAutoreleaseRV();
903 }
904 
905 /// This function returns true if the value is inert. An ObjC ARC runtime call
906 /// taking an inert operand can be safely deleted.
907 static bool isInertARCValue(Value *V, SmallPtrSet<Value *, 1> &VisitedPhis) {
908  V = V->stripPointerCasts();
909 
910  if (IsNullOrUndef(V))
911  return true;
912 
913  // See if this is a global attribute annotated with an 'objc_arc_inert'.
914  if (auto *GV = dyn_cast<GlobalVariable>(V))
915  if (GV->hasAttribute("objc_arc_inert"))
916  return true;
917 
918  if (auto PN = dyn_cast<PHINode>(V)) {
919  // Ignore this phi if it has already been discovered.
920  if (!VisitedPhis.insert(PN).second)
921  return true;
922  // Look through phis's operands.
923  for (Value *Opnd : PN->incoming_values())
924  if (!isInertARCValue(Opnd, VisitedPhis))
925  return false;
926  return true;
927  }
928 
929  return false;
930 }
931 
932 void ObjCARCOpt::OptimizeIndividualCallImpl(
934  Instruction *Inst, ARCInstKind Class, const Value *Arg) {
935  LLVM_DEBUG(dbgs() << "Visiting: Class: " << Class << "; " << *Inst << "\n");
936 
937  // We can delete this call if it takes an inert value.
938  SmallPtrSet<Value *, 1> VisitedPhis;
939 
940  if (BundledInsts->contains(Inst)) {
941  UsedInThisFunction |= 1 << unsigned(Class);
942  return;
943  }
944 
945  if (IsNoopOnGlobal(Class))
946  if (isInertARCValue(Inst->getOperand(0), VisitedPhis)) {
947  if (!Inst->getType()->isVoidTy())
948  Inst->replaceAllUsesWith(Inst->getOperand(0));
949  Inst->eraseFromParent();
950  Changed = true;
951  return;
952  }
953 
954  switch (Class) {
955  default:
956  break;
957 
958  // Delete no-op casts. These function calls have special semantics, but
959  // the semantics are entirely implemented via lowering in the front-end,
960  // so by the time they reach the optimizer, they are just no-op calls
961  // which return their argument.
962  //
963  // There are gray areas here, as the ability to cast reference-counted
964  // pointers to raw void* and back allows code to break ARC assumptions,
965  // however these are currently considered to be unimportant.
967  Changed = true;
968  ++NumNoops;
969  LLVM_DEBUG(dbgs() << "Erasing no-op cast: " << *Inst << "\n");
970  EraseInstruction(Inst);
971  return;
972 
973  // If the pointer-to-weak-pointer is null, it's undefined behavior.
979  CallInst *CI = cast<CallInst>(Inst);
980  if (IsNullOrUndef(CI->getArgOperand(0))) {
981  Changed = true;
982  Type *Ty = CI->getArgOperand(0)->getType();
983  new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()),
984  Constant::getNullValue(Ty), CI);
985  Value *NewValue = UndefValue::get(CI->getType());
986  LLVM_DEBUG(
987  dbgs() << "A null pointer-to-weak-pointer is undefined behavior."
988  "\nOld = "
989  << *CI << "\nNew = " << *NewValue << "\n");
990  CI->replaceAllUsesWith(NewValue);
991  CI->eraseFromParent();
992  return;
993  }
994  break;
995  }
997  case ARCInstKind::MoveWeak: {
998  CallInst *CI = cast<CallInst>(Inst);
999  if (IsNullOrUndef(CI->getArgOperand(0)) ||
1000  IsNullOrUndef(CI->getArgOperand(1))) {
1001  Changed = true;
1002  Type *Ty = CI->getArgOperand(0)->getType();
1003  new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()),
1004  Constant::getNullValue(Ty), CI);
1005 
1006  Value *NewValue = UndefValue::get(CI->getType());
1007  LLVM_DEBUG(
1008  dbgs() << "A null pointer-to-weak-pointer is undefined behavior."
1009  "\nOld = "
1010  << *CI << "\nNew = " << *NewValue << "\n");
1011 
1012  CI->replaceAllUsesWith(NewValue);
1013  CI->eraseFromParent();
1014  return;
1015  }
1016  break;
1017  }
1018  case ARCInstKind::RetainRV:
1019  if (OptimizeRetainRVCall(F, Inst))
1020  return;
1021  break;
1023  OptimizeAutoreleaseRVCall(F, Inst, Class);
1024  break;
1025  }
1026 
1027  // objc_autorelease(x) -> objc_release(x) if x is otherwise unused.
1028  if (IsAutorelease(Class) && Inst->use_empty()) {
1029  CallInst *Call = cast<CallInst>(Inst);
1030  const Value *Arg = Call->getArgOperand(0);
1032  if (Arg) {
1033  Changed = true;
1034  ++NumAutoreleases;
1035 
1036  // Create the declaration lazily.
1037  LLVMContext &C = Inst->getContext();
1038 
1040  CallInst *NewCall =
1041  CallInst::Create(Decl, Call->getArgOperand(0), "", Call);
1042  NewCall->setMetadata(MDKindCache.get(ARCMDKindID::ImpreciseRelease),
1043  MDNode::get(C, None));
1044 
1045  LLVM_DEBUG(dbgs() << "Replacing autorelease{,RV}(x) with objc_release(x) "
1046  "since x is otherwise unused.\nOld: "
1047  << *Call << "\nNew: " << *NewCall << "\n");
1048 
1049  EraseInstruction(Call);
1050  Inst = NewCall;
1052  }
1053  }
1054 
1055  // For functions which can never be passed stack arguments, add
1056  // a tail keyword.
1057  if (IsAlwaysTail(Class) && !cast<CallInst>(Inst)->isNoTailCall()) {
1058  Changed = true;
1059  LLVM_DEBUG(
1060  dbgs() << "Adding tail keyword to function since it can never be "
1061  "passed stack args: "
1062  << *Inst << "\n");
1063  cast<CallInst>(Inst)->setTailCall();
1064  }
1065 
1066  // Ensure that functions that can never have a "tail" keyword due to the
1067  // semantics of ARC truly do not do so.
1068  if (IsNeverTail(Class)) {
1069  Changed = true;
1070  LLVM_DEBUG(dbgs() << "Removing tail keyword from function: " << *Inst
1071  << "\n");
1072  cast<CallInst>(Inst)->setTailCall(false);
1073  }
1074 
1075  // Set nounwind as needed.
1076  if (IsNoThrow(Class)) {
1077  Changed = true;
1078  LLVM_DEBUG(dbgs() << "Found no throw class. Setting nounwind on: " << *Inst
1079  << "\n");
1080  cast<CallInst>(Inst)->setDoesNotThrow();
1081  }
1082 
1083  // Note: This catches instructions unrelated to ARC.
1084  if (!IsNoopOnNull(Class)) {
1085  UsedInThisFunction |= 1 << unsigned(Class);
1086  return;
1087  }
1088 
1089  // If we haven't already looked up the root, look it up now.
1090  if (!Arg)
1091  Arg = GetArgRCIdentityRoot(Inst);
1092 
1093  // ARC calls with null are no-ops. Delete them.
1094  if (IsNullOrUndef(Arg)) {
1095  Changed = true;
1096  ++NumNoops;
1097  LLVM_DEBUG(dbgs() << "ARC calls with null are no-ops. Erasing: " << *Inst
1098  << "\n");
1099  EraseInstruction(Inst);
1100  return;
1101  }
1102 
1103  // Keep track of which of retain, release, autorelease, and retain_block
1104  // are actually present in this function.
1105  UsedInThisFunction |= 1 << unsigned(Class);
1106 
1107  // If Arg is a PHI, and one or more incoming values to the
1108  // PHI are null, and the call is control-equivalent to the PHI, and there
1109  // are no relevant side effects between the PHI and the call, and the call
1110  // is not a release that doesn't have the clang.imprecise_release tag, the
1111  // call could be pushed up to just those paths with non-null incoming
1112  // values. For now, don't bother splitting critical edges for this.
1113  if (Class == ARCInstKind::Release &&
1114  !Inst->getMetadata(MDKindCache.get(ARCMDKindID::ImpreciseRelease)))
1115  return;
1116 
1118  Worklist.push_back(std::make_pair(Inst, Arg));
1119  do {
1120  std::pair<Instruction *, const Value *> Pair = Worklist.pop_back_val();
1121  Inst = Pair.first;
1122  Arg = Pair.second;
1123 
1124  const PHINode *PN = dyn_cast<PHINode>(Arg);
1125  if (!PN)
1126  continue;
1127 
1128  // Determine if the PHI has any null operands, or any incoming
1129  // critical edges.
1130  bool HasNull = false;
1131  bool HasCriticalEdges = false;
1132  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1133  Value *Incoming = GetRCIdentityRoot(PN->getIncomingValue(i));
1134  if (IsNullOrUndef(Incoming))
1135  HasNull = true;
1136  else if (PN->getIncomingBlock(i)->getTerminator()->getNumSuccessors() !=
1137  1) {
1138  HasCriticalEdges = true;
1139  break;
1140  }
1141  }
1142  // If we have null operands and no critical edges, optimize.
1143  if (HasCriticalEdges)
1144  continue;
1145  if (!HasNull)
1146  continue;
1147 
1148  Instruction *DepInst = nullptr;
1149 
1150  // Check that there is nothing that cares about the reference
1151  // count between the call and the phi.
1152  switch (Class) {
1153  case ARCInstKind::Retain:
1155  // These can always be moved up.
1156  break;
1157  case ARCInstKind::Release:
1158  // These can't be moved across things that care about the retain
1159  // count.
1161  Inst->getParent(), Inst, PA);
1162  break;
1164  // These can't be moved across autorelease pool scope boundaries.
1166  Inst->getParent(), Inst, PA);
1167  break;
1168  case ARCInstKind::ClaimRV:
1169  case ARCInstKind::RetainRV:
1171  // Don't move these; the RV optimization depends on the autoreleaseRV
1172  // being tail called, and the retainRV being immediately after a call
1173  // (which might still happen if we get lucky with codegen layout, but
1174  // it's not worth taking the chance).
1175  continue;
1176  default:
1177  llvm_unreachable("Invalid dependence flavor");
1178  }
1179 
1180  if (DepInst != PN)
1181  continue;
1182 
1183  Changed = true;
1184  ++NumPartialNoops;
1185  // Clone the call into each predecessor that has a non-null value.
1186  CallInst *CInst = cast<CallInst>(Inst);
1187  Type *ParamTy = CInst->getArgOperand(0)->getType();
1188  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1189  Value *Incoming = GetRCIdentityRoot(PN->getIncomingValue(i));
1190  if (IsNullOrUndef(Incoming))
1191  continue;
1192  Value *Op = PN->getIncomingValue(i);
1193  Instruction *InsertPos = &PN->getIncomingBlock(i)->back();
1194  CallInst *Clone = cast<CallInst>(
1195  CloneCallInstForBB(*CInst, *InsertPos->getParent(), BlockColors));
1196  if (Op->getType() != ParamTy)
1197  Op = new BitCastInst(Op, ParamTy, "", InsertPos);
1198  Clone->setArgOperand(0, Op);
1199  Clone->insertBefore(InsertPos);
1200 
1201  LLVM_DEBUG(dbgs() << "Cloning " << *CInst << "\n"
1202  "And inserting clone at "
1203  << *InsertPos << "\n");
1204  Worklist.push_back(std::make_pair(Clone, Incoming));
1205  }
1206  // Erase the original call.
1207  LLVM_DEBUG(dbgs() << "Erasing: " << *CInst << "\n");
1208  EraseInstruction(CInst);
1209  } while (!Worklist.empty());
1210 }
1211 
1212 /// If we have a top down pointer in the S_Use state, make sure that there are
1213 /// no CFG hazards by checking the states of various bottom up pointers.
1214 static void CheckForUseCFGHazard(const Sequence SuccSSeq,
1215  const bool SuccSRRIKnownSafe,
1216  TopDownPtrState &S,
1217  bool &SomeSuccHasSame,
1218  bool &AllSuccsHaveSame,
1219  bool &NotAllSeqEqualButKnownSafe,
1220  bool &ShouldContinue) {
1221  switch (SuccSSeq) {
1222  case S_CanRelease: {
1223  if (!S.IsKnownSafe() && !SuccSRRIKnownSafe) {
1224  S.ClearSequenceProgress();
1225  break;
1226  }
1227  S.SetCFGHazardAfflicted(true);
1228  ShouldContinue = true;
1229  break;
1230  }
1231  case S_Use:
1232  SomeSuccHasSame = true;
1233  break;
1234  case S_Stop:
1235  case S_MovableRelease:
1236  if (!S.IsKnownSafe() && !SuccSRRIKnownSafe)
1237  AllSuccsHaveSame = false;
1238  else
1239  NotAllSeqEqualButKnownSafe = true;
1240  break;
1241  case S_Retain:
1242  llvm_unreachable("bottom-up pointer in retain state!");
1243  case S_None:
1244  llvm_unreachable("This should have been handled earlier.");
1245  }
1246 }
1247 
1248 /// If we have a Top Down pointer in the S_CanRelease state, make sure that
1249 /// there are no CFG hazards by checking the states of various bottom up
1250 /// pointers.
1251 static void CheckForCanReleaseCFGHazard(const Sequence SuccSSeq,
1252  const bool SuccSRRIKnownSafe,
1253  TopDownPtrState &S,
1254  bool &SomeSuccHasSame,
1255  bool &AllSuccsHaveSame,
1256  bool &NotAllSeqEqualButKnownSafe) {
1257  switch (SuccSSeq) {
1258  case S_CanRelease:
1259  SomeSuccHasSame = true;
1260  break;
1261  case S_Stop:
1262  case S_MovableRelease:
1263  case S_Use:
1264  if (!S.IsKnownSafe() && !SuccSRRIKnownSafe)
1265  AllSuccsHaveSame = false;
1266  else
1267  NotAllSeqEqualButKnownSafe = true;
1268  break;
1269  case S_Retain:
1270  llvm_unreachable("bottom-up pointer in retain state!");
1271  case S_None:
1272  llvm_unreachable("This should have been handled earlier.");
1273  }
1274 }
1275 
1276 /// Check for critical edges, loop boundaries, irreducible control flow, or
1277 /// other CFG structures where moving code across the edge would result in it
1278 /// being executed more.
1279 void
1280 ObjCARCOpt::CheckForCFGHazards(const BasicBlock *BB,
1282  BBState &MyStates) const {
1283  // If any top-down local-use or possible-dec has a succ which is earlier in
1284  // the sequence, forget it.
1285  for (auto I = MyStates.top_down_ptr_begin(), E = MyStates.top_down_ptr_end();
1286  I != E; ++I) {
1287  TopDownPtrState &S = I->second;
1288  const Sequence Seq = I->second.GetSeq();
1289 
1290  // We only care about S_Retain, S_CanRelease, and S_Use.
1291  if (Seq == S_None)
1292  continue;
1293 
1294  // Make sure that if extra top down states are added in the future that this
1295  // code is updated to handle it.
1296  assert((Seq == S_Retain || Seq == S_CanRelease || Seq == S_Use) &&
1297  "Unknown top down sequence state.");
1298 
1299  const Value *Arg = I->first;
1300  bool SomeSuccHasSame = false;
1301  bool AllSuccsHaveSame = true;
1302  bool NotAllSeqEqualButKnownSafe = false;
1303 
1304  for (const BasicBlock *Succ : successors(BB)) {
1305  // If VisitBottomUp has pointer information for this successor, take
1306  // what we know about it.
1308  BBStates.find(Succ);
1309  assert(BBI != BBStates.end());
1310  const BottomUpPtrState &SuccS = BBI->second.getPtrBottomUpState(Arg);
1311  const Sequence SuccSSeq = SuccS.GetSeq();
1312 
1313  // If bottom up, the pointer is in an S_None state, clear the sequence
1314  // progress since the sequence in the bottom up state finished
1315  // suggesting a mismatch in between retains/releases. This is true for
1316  // all three cases that we are handling here: S_Retain, S_Use, and
1317  // S_CanRelease.
1318  if (SuccSSeq == S_None) {
1319  S.ClearSequenceProgress();
1320  continue;
1321  }
1322 
1323  // If we have S_Use or S_CanRelease, perform our check for cfg hazard
1324  // checks.
1325  const bool SuccSRRIKnownSafe = SuccS.IsKnownSafe();
1326 
1327  // *NOTE* We do not use Seq from above here since we are allowing for
1328  // S.GetSeq() to change while we are visiting basic blocks.
1329  switch(S.GetSeq()) {
1330  case S_Use: {
1331  bool ShouldContinue = false;
1332  CheckForUseCFGHazard(SuccSSeq, SuccSRRIKnownSafe, S, SomeSuccHasSame,
1333  AllSuccsHaveSame, NotAllSeqEqualButKnownSafe,
1334  ShouldContinue);
1335  if (ShouldContinue)
1336  continue;
1337  break;
1338  }
1339  case S_CanRelease:
1340  CheckForCanReleaseCFGHazard(SuccSSeq, SuccSRRIKnownSafe, S,
1341  SomeSuccHasSame, AllSuccsHaveSame,
1342  NotAllSeqEqualButKnownSafe);
1343  break;
1344  case S_Retain:
1345  case S_None:
1346  case S_Stop:
1347  case S_MovableRelease:
1348  break;
1349  }
1350  }
1351 
1352  // If the state at the other end of any of the successor edges
1353  // matches the current state, require all edges to match. This
1354  // guards against loops in the middle of a sequence.
1355  if (SomeSuccHasSame && !AllSuccsHaveSame) {
1356  S.ClearSequenceProgress();
1357  } else if (NotAllSeqEqualButKnownSafe) {
1358  // If we would have cleared the state foregoing the fact that we are known
1359  // safe, stop code motion. This is because whether or not it is safe to
1360  // remove RR pairs via KnownSafe is an orthogonal concept to whether we
1361  // are allowed to perform code motion.
1362  S.SetCFGHazardAfflicted(true);
1363  }
1364  }
1365 }
1366 
1367 bool ObjCARCOpt::VisitInstructionBottomUp(
1369  BBState &MyStates) {
1370  bool NestingDetected = false;
1372  const Value *Arg = nullptr;
1373 
1374  LLVM_DEBUG(dbgs() << " Class: " << Class << "\n");
1375 
1376  switch (Class) {
1377  case ARCInstKind::Release: {
1378  Arg = GetArgRCIdentityRoot(Inst);
1379 
1380  BottomUpPtrState &S = MyStates.getPtrBottomUpState(Arg);
1381  NestingDetected |= S.InitBottomUp(MDKindCache, Inst);
1382  break;
1383  }
1385  // In OptimizeIndividualCalls, we have strength reduced all optimizable
1386  // objc_retainBlocks to objc_retains. Thus at this point any
1387  // objc_retainBlocks that we see are not optimizable.
1388  break;
1389  case ARCInstKind::Retain:
1390  case ARCInstKind::RetainRV: {
1391  Arg = GetArgRCIdentityRoot(Inst);
1392  BottomUpPtrState &S = MyStates.getPtrBottomUpState(Arg);
1393  if (S.MatchWithRetain()) {
1394  // Don't do retain+release tracking for ARCInstKind::RetainRV, because
1395  // it's better to let it remain as the first instruction after a call.
1396  if (Class != ARCInstKind::RetainRV) {
1397  LLVM_DEBUG(dbgs() << " Matching with: " << *Inst << "\n");
1398  Retains[Inst] = S.GetRRInfo();
1399  }
1400  S.ClearSequenceProgress();
1401  }
1402  // A retain moving bottom up can be a use.
1403  break;
1404  }
1406  // Conservatively, clear MyStates for all known pointers.
1407  MyStates.clearBottomUpPointers();
1408  return NestingDetected;
1410  case ARCInstKind::None:
1411  // These are irrelevant.
1412  return NestingDetected;
1413  default:
1414  break;
1415  }
1416 
1417  // Consider any other possible effects of this instruction on each
1418  // pointer being tracked.
1419  for (auto MI = MyStates.bottom_up_ptr_begin(),
1420  ME = MyStates.bottom_up_ptr_end();
1421  MI != ME; ++MI) {
1422  const Value *Ptr = MI->first;
1423  if (Ptr == Arg)
1424  continue; // Handled above.
1425  BottomUpPtrState &S = MI->second;
1426 
1427  if (S.HandlePotentialAlterRefCount(Inst, Ptr, PA, Class))
1428  continue;
1429 
1430  S.HandlePotentialUse(BB, Inst, Ptr, PA, Class);
1431  }
1432 
1433  return NestingDetected;
1434 }
1435 
1436 bool ObjCARCOpt::VisitBottomUp(BasicBlock *BB,
1438  BlotMapVector<Value *, RRInfo> &Retains) {
1439  LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::VisitBottomUp ==\n");
1440 
1441  bool NestingDetected = false;
1442  BBState &MyStates = BBStates[BB];
1443 
1444  // Merge the states from each successor to compute the initial state
1445  // for the current block.
1446  BBState::edge_iterator SI(MyStates.succ_begin()),
1447  SE(MyStates.succ_end());
1448  if (SI != SE) {
1449  const BasicBlock *Succ = *SI;
1451  assert(I != BBStates.end());
1452  MyStates.InitFromSucc(I->second);
1453  ++SI;
1454  for (; SI != SE; ++SI) {
1455  Succ = *SI;
1456  I = BBStates.find(Succ);
1457  assert(I != BBStates.end());
1458  MyStates.MergeSucc(I->second);
1459  }
1460  }
1461 
1462  LLVM_DEBUG(dbgs() << "Before:\n"
1463  << BBStates[BB] << "\n"
1464  << "Performing Dataflow:\n");
1465 
1466  // Visit all the instructions, bottom-up.
1467  for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; --I) {
1468  Instruction *Inst = &*std::prev(I);
1469 
1470  // Invoke instructions are visited as part of their successors (below).
1471  if (isa<InvokeInst>(Inst))
1472  continue;
1473 
1474  LLVM_DEBUG(dbgs() << " Visiting " << *Inst << "\n");
1475 
1476  NestingDetected |= VisitInstructionBottomUp(Inst, BB, Retains, MyStates);
1477 
1478  // Bail out if the number of pointers being tracked becomes too large so
1479  // that this pass can complete in a reasonable amount of time.
1480  if (MyStates.bottom_up_ptr_list_size() > MaxPtrStates) {
1481  DisableRetainReleasePairing = true;
1482  return false;
1483  }
1484  }
1485 
1486  // If there's a predecessor with an invoke, visit the invoke as if it were
1487  // part of this block, since we can't insert code after an invoke in its own
1488  // block, and we don't want to split critical edges.
1489  for (BBState::edge_iterator PI(MyStates.pred_begin()),
1490  PE(MyStates.pred_end()); PI != PE; ++PI) {
1491  BasicBlock *Pred = *PI;
1492  if (InvokeInst *II = dyn_cast<InvokeInst>(&Pred->back()))
1493  NestingDetected |= VisitInstructionBottomUp(II, BB, Retains, MyStates);
1494  }
1495 
1496  LLVM_DEBUG(dbgs() << "\nFinal State:\n" << BBStates[BB] << "\n");
1497 
1498  return NestingDetected;
1499 }
1500 
1501 // Fill ReleaseInsertPtToRCIdentityRoots, which is a map from insertion points
1502 // to the set of RC identity roots that would be released by the release calls
1503 // moved to the insertion points.
1505  const BlotMapVector<Value *, RRInfo> &Retains,
1507  &ReleaseInsertPtToRCIdentityRoots) {
1508  for (auto &P : Retains) {
1509  // Retains is a map from an objc_retain call to a RRInfo of the RC identity
1510  // root of the call. Get the RC identity root of the objc_retain call.
1511  Instruction *Retain = cast<Instruction>(P.first);
1512  Value *Root = GetRCIdentityRoot(Retain->getOperand(0));
1513  // Collect all the insertion points of the objc_release calls that release
1514  // the RC identity root of the objc_retain call.
1515  for (const Instruction *InsertPt : P.second.ReverseInsertPts)
1516  ReleaseInsertPtToRCIdentityRoots[InsertPt].insert(Root);
1517  }
1518 }
1519 
1520 // Get the RC identity roots from an insertion point of an objc_release call.
1521 // Return nullptr if the passed instruction isn't an insertion point.
1522 static const SmallPtrSet<const Value *, 2> *
1524  const Instruction *InsertPt,
1526  &ReleaseInsertPtToRCIdentityRoots) {
1527  auto I = ReleaseInsertPtToRCIdentityRoots.find(InsertPt);
1528  if (I == ReleaseInsertPtToRCIdentityRoots.end())
1529  return nullptr;
1530  return &I->second;
1531 }
1532 
1533 bool ObjCARCOpt::VisitInstructionTopDown(
1534  Instruction *Inst, DenseMap<Value *, RRInfo> &Releases, BBState &MyStates,
1536  &ReleaseInsertPtToRCIdentityRoots) {
1537  bool NestingDetected = false;
1539  const Value *Arg = nullptr;
1540 
1541  // Make sure a call to objc_retain isn't moved past insertion points of calls
1542  // to objc_release.
1543  if (const SmallPtrSet<const Value *, 2> *Roots =
1545  Inst, ReleaseInsertPtToRCIdentityRoots))
1546  for (auto *Root : *Roots) {
1547  TopDownPtrState &S = MyStates.getPtrTopDownState(Root);
1548  // Disable code motion if the current position is S_Retain to prevent
1549  // moving the objc_retain call past objc_release calls. If it's
1550  // S_CanRelease or larger, it's not necessary to disable code motion as
1551  // the insertion points that prevent the objc_retain call from moving down
1552  // should have been set already.
1553  if (S.GetSeq() == S_Retain)
1554  S.SetCFGHazardAfflicted(true);
1555  }
1556 
1557  LLVM_DEBUG(dbgs() << " Class: " << Class << "\n");
1558 
1559  switch (Class) {
1561  // In OptimizeIndividualCalls, we have strength reduced all optimizable
1562  // objc_retainBlocks to objc_retains. Thus at this point any
1563  // objc_retainBlocks that we see are not optimizable. We need to break since
1564  // a retain can be a potential use.
1565  break;
1566  case ARCInstKind::Retain:
1567  case ARCInstKind::RetainRV: {
1568  Arg = GetArgRCIdentityRoot(Inst);
1569  TopDownPtrState &S = MyStates.getPtrTopDownState(Arg);
1570  NestingDetected |= S.InitTopDown(Class, Inst);
1571  // A retain can be a potential use; proceed to the generic checking
1572  // code below.
1573  break;
1574  }
1575  case ARCInstKind::Release: {
1576  Arg = GetArgRCIdentityRoot(Inst);
1577  TopDownPtrState &S = MyStates.getPtrTopDownState(Arg);
1578  // Try to form a tentative pair in between this release instruction and the
1579  // top down pointers that we are tracking.
1580  if (S.MatchWithRelease(MDKindCache, Inst)) {
1581  // If we succeed, copy S's RRInfo into the Release -> {Retain Set
1582  // Map}. Then we clear S.
1583  LLVM_DEBUG(dbgs() << " Matching with: " << *Inst << "\n");
1584  Releases[Inst] = S.GetRRInfo();
1585  S.ClearSequenceProgress();
1586  }
1587  break;
1588  }
1590  // Conservatively, clear MyStates for all known pointers.
1591  MyStates.clearTopDownPointers();
1592  return false;
1594  case ARCInstKind::None:
1595  // These can not be uses of
1596  return false;
1597  default:
1598  break;
1599  }
1600 
1601  // Consider any other possible effects of this instruction on each
1602  // pointer being tracked.
1603  for (auto MI = MyStates.top_down_ptr_begin(),
1604  ME = MyStates.top_down_ptr_end();
1605  MI != ME; ++MI) {
1606  const Value *Ptr = MI->first;
1607  if (Ptr == Arg)
1608  continue; // Handled above.
1609  TopDownPtrState &S = MI->second;
1610  if (S.HandlePotentialAlterRefCount(Inst, Ptr, PA, Class, *BundledInsts))
1611  continue;
1612 
1613  S.HandlePotentialUse(Inst, Ptr, PA, Class);
1614  }
1615 
1616  return NestingDetected;
1617 }
1618 
1619 bool ObjCARCOpt::VisitTopDown(
1621  DenseMap<Value *, RRInfo> &Releases,
1623  &ReleaseInsertPtToRCIdentityRoots) {
1624  LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::VisitTopDown ==\n");
1625  bool NestingDetected = false;
1626  BBState &MyStates = BBStates[BB];
1627 
1628  // Merge the states from each predecessor to compute the initial state
1629  // for the current block.
1630  BBState::edge_iterator PI(MyStates.pred_begin()),
1631  PE(MyStates.pred_end());
1632  if (PI != PE) {
1633  const BasicBlock *Pred = *PI;
1635  assert(I != BBStates.end());
1636  MyStates.InitFromPred(I->second);
1637  ++PI;
1638  for (; PI != PE; ++PI) {
1639  Pred = *PI;
1640  I = BBStates.find(Pred);
1641  assert(I != BBStates.end());
1642  MyStates.MergePred(I->second);
1643  }
1644  }
1645 
1646  // Check that BB and MyStates have the same number of predecessors. This
1647  // prevents retain calls that live outside a loop from being moved into the
1648  // loop.
1649  if (!BB->hasNPredecessors(MyStates.pred_end() - MyStates.pred_begin()))
1650  for (auto I = MyStates.top_down_ptr_begin(),
1651  E = MyStates.top_down_ptr_end();
1652  I != E; ++I)
1653  I->second.SetCFGHazardAfflicted(true);
1654 
1655  LLVM_DEBUG(dbgs() << "Before:\n"
1656  << BBStates[BB] << "\n"
1657  << "Performing Dataflow:\n");
1658 
1659  // Visit all the instructions, top-down.
1660  for (Instruction &Inst : *BB) {
1661  LLVM_DEBUG(dbgs() << " Visiting " << Inst << "\n");
1662 
1663  NestingDetected |= VisitInstructionTopDown(
1664  &Inst, Releases, MyStates, ReleaseInsertPtToRCIdentityRoots);
1665 
1666  // Bail out if the number of pointers being tracked becomes too large so
1667  // that this pass can complete in a reasonable amount of time.
1668  if (MyStates.top_down_ptr_list_size() > MaxPtrStates) {
1669  DisableRetainReleasePairing = true;
1670  return false;
1671  }
1672  }
1673 
1674  LLVM_DEBUG(dbgs() << "\nState Before Checking for CFG Hazards:\n"
1675  << BBStates[BB] << "\n\n");
1676  CheckForCFGHazards(BB, BBStates, MyStates);
1677  LLVM_DEBUG(dbgs() << "Final State:\n" << BBStates[BB] << "\n");
1678  return NestingDetected;
1679 }
1680 
1681 static void
1683  SmallVectorImpl<BasicBlock *> &PostOrder,
1684  SmallVectorImpl<BasicBlock *> &ReverseCFGPostOrder,
1685  unsigned NoObjCARCExceptionsMDKind,
1687  /// The visited set, for doing DFS walks.
1689 
1690  // Do DFS, computing the PostOrder.
1693 
1694  // Functions always have exactly one entry block, and we don't have
1695  // any other block that we treat like an entry block.
1696  BasicBlock *EntryBB = &F.getEntryBlock();
1697  BBState &MyStates = BBStates[EntryBB];
1698  MyStates.SetAsEntry();
1699  Instruction *EntryTI = EntryBB->getTerminator();
1700  SuccStack.push_back(std::make_pair(EntryBB, succ_iterator(EntryTI)));
1701  Visited.insert(EntryBB);
1702  OnStack.insert(EntryBB);
1703  do {
1704  dfs_next_succ:
1705  BasicBlock *CurrBB = SuccStack.back().first;
1706  succ_iterator SE(CurrBB->getTerminator(), false);
1707 
1708  while (SuccStack.back().second != SE) {
1709  BasicBlock *SuccBB = *SuccStack.back().second++;
1710  if (Visited.insert(SuccBB).second) {
1711  SuccStack.push_back(
1712  std::make_pair(SuccBB, succ_iterator(SuccBB->getTerminator())));
1713  BBStates[CurrBB].addSucc(SuccBB);
1714  BBState &SuccStates = BBStates[SuccBB];
1715  SuccStates.addPred(CurrBB);
1716  OnStack.insert(SuccBB);
1717  goto dfs_next_succ;
1718  }
1719 
1720  if (!OnStack.count(SuccBB)) {
1721  BBStates[CurrBB].addSucc(SuccBB);
1722  BBStates[SuccBB].addPred(CurrBB);
1723  }
1724  }
1725  OnStack.erase(CurrBB);
1726  PostOrder.push_back(CurrBB);
1727  SuccStack.pop_back();
1728  } while (!SuccStack.empty());
1729 
1730  Visited.clear();
1731 
1732  // Do reverse-CFG DFS, computing the reverse-CFG PostOrder.
1733  // Functions may have many exits, and there also blocks which we treat
1734  // as exits due to ignored edges.
1736  for (BasicBlock &ExitBB : F) {
1737  BBState &MyStates = BBStates[&ExitBB];
1738  if (!MyStates.isExit())
1739  continue;
1740 
1741  MyStates.SetAsExit();
1742 
1743  PredStack.push_back(std::make_pair(&ExitBB, MyStates.pred_begin()));
1744  Visited.insert(&ExitBB);
1745  while (!PredStack.empty()) {
1746  reverse_dfs_next_succ:
1747  BBState::edge_iterator PE = BBStates[PredStack.back().first].pred_end();
1748  while (PredStack.back().second != PE) {
1749  BasicBlock *BB = *PredStack.back().second++;
1750  if (Visited.insert(BB).second) {
1751  PredStack.push_back(std::make_pair(BB, BBStates[BB].pred_begin()));
1752  goto reverse_dfs_next_succ;
1753  }
1754  }
1755  ReverseCFGPostOrder.push_back(PredStack.pop_back_val().first);
1756  }
1757  }
1758 }
1759 
1760 // Visit the function both top-down and bottom-up.
1761 bool ObjCARCOpt::Visit(Function &F,
1764  DenseMap<Value *, RRInfo> &Releases) {
1765  // Use reverse-postorder traversals, because we magically know that loops
1766  // will be well behaved, i.e. they won't repeatedly call retain on a single
1767  // pointer without doing a release. We can't use the ReversePostOrderTraversal
1768  // class here because we want the reverse-CFG postorder to consider each
1769  // function exit point, and we want to ignore selected cycle edges.
1771  SmallVector<BasicBlock *, 16> ReverseCFGPostOrder;
1772  ComputePostOrders(F, PostOrder, ReverseCFGPostOrder,
1773  MDKindCache.get(ARCMDKindID::NoObjCARCExceptions),
1774  BBStates);
1775 
1776  // Use reverse-postorder on the reverse CFG for bottom-up.
1777  bool BottomUpNestingDetected = false;
1778  for (BasicBlock *BB : llvm::reverse(ReverseCFGPostOrder)) {
1779  BottomUpNestingDetected |= VisitBottomUp(BB, BBStates, Retains);
1780  if (DisableRetainReleasePairing)
1781  return false;
1782  }
1783 
1785  ReleaseInsertPtToRCIdentityRoots;
1786  collectReleaseInsertPts(Retains, ReleaseInsertPtToRCIdentityRoots);
1787 
1788  // Use reverse-postorder for top-down.
1789  bool TopDownNestingDetected = false;
1790  for (BasicBlock *BB : llvm::reverse(PostOrder)) {
1791  TopDownNestingDetected |=
1792  VisitTopDown(BB, BBStates, Releases, ReleaseInsertPtToRCIdentityRoots);
1793  if (DisableRetainReleasePairing)
1794  return false;
1795  }
1796 
1797  return TopDownNestingDetected && BottomUpNestingDetected;
1798 }
1799 
1800 /// Move the calls in RetainsToMove and ReleasesToMove.
1801 void ObjCARCOpt::MoveCalls(Value *Arg, RRInfo &RetainsToMove,
1802  RRInfo &ReleasesToMove,
1804  DenseMap<Value *, RRInfo> &Releases,
1805  SmallVectorImpl<Instruction *> &DeadInsts,
1806  Module *M) {
1807  Type *ArgTy = Arg->getType();
1808  Type *ParamTy = PointerType::getUnqual(Type::getInt8Ty(ArgTy->getContext()));
1809 
1810  LLVM_DEBUG(dbgs() << "== ObjCARCOpt::MoveCalls ==\n");
1811 
1812  // Insert the new retain and release calls.
1813  for (Instruction *InsertPt : ReleasesToMove.ReverseInsertPts) {
1814  Value *MyArg = ArgTy == ParamTy ? Arg :
1815  new BitCastInst(Arg, ParamTy, "", InsertPt);
1817  CallInst *Call = CallInst::Create(Decl, MyArg, "", InsertPt);
1818  Call->setDoesNotThrow();
1819  Call->setTailCall();
1820 
1821  LLVM_DEBUG(dbgs() << "Inserting new Retain: " << *Call
1822  << "\n"
1823  "At insertion point: "
1824  << *InsertPt << "\n");
1825  }
1826  for (Instruction *InsertPt : RetainsToMove.ReverseInsertPts) {
1827  Value *MyArg = ArgTy == ParamTy ? Arg :
1828  new BitCastInst(Arg, ParamTy, "", InsertPt);
1830  CallInst *Call = CallInst::Create(Decl, MyArg, "", InsertPt);
1831  // Attach a clang.imprecise_release metadata tag, if appropriate.
1832  if (MDNode *M = ReleasesToMove.ReleaseMetadata)
1833  Call->setMetadata(MDKindCache.get(ARCMDKindID::ImpreciseRelease), M);
1834  Call->setDoesNotThrow();
1835  if (ReleasesToMove.IsTailCallRelease)
1836  Call->setTailCall();
1837 
1838  LLVM_DEBUG(dbgs() << "Inserting new Release: " << *Call
1839  << "\n"
1840  "At insertion point: "
1841  << *InsertPt << "\n");
1842  }
1843 
1844  // Delete the original retain and release calls.
1845  for (Instruction *OrigRetain : RetainsToMove.Calls) {
1846  Retains.blot(OrigRetain);
1847  DeadInsts.push_back(OrigRetain);
1848  LLVM_DEBUG(dbgs() << "Deleting retain: " << *OrigRetain << "\n");
1849  }
1850  for (Instruction *OrigRelease : ReleasesToMove.Calls) {
1851  Releases.erase(OrigRelease);
1852  DeadInsts.push_back(OrigRelease);
1853  LLVM_DEBUG(dbgs() << "Deleting release: " << *OrigRelease << "\n");
1854  }
1855 }
1856 
1857 bool ObjCARCOpt::PairUpRetainsAndReleases(
1860  DenseMap<Value *, RRInfo> &Releases, Module *M,
1861  Instruction *Retain,
1862  SmallVectorImpl<Instruction *> &DeadInsts, RRInfo &RetainsToMove,
1863  RRInfo &ReleasesToMove, Value *Arg, bool KnownSafe,
1864  bool &AnyPairsCompletelyEliminated) {
1865  // If a pair happens in a region where it is known that the reference count
1866  // is already incremented, we can similarly ignore possible decrements unless
1867  // we are dealing with a retainable object with multiple provenance sources.
1868  bool KnownSafeTD = true, KnownSafeBU = true;
1869  bool CFGHazardAfflicted = false;
1870 
1871  // Connect the dots between the top-down-collected RetainsToMove and
1872  // bottom-up-collected ReleasesToMove to form sets of related calls.
1873  // This is an iterative process so that we connect multiple releases
1874  // to multiple retains if needed.
1875  unsigned OldDelta = 0;
1876  unsigned NewDelta = 0;
1877  unsigned OldCount = 0;
1878  unsigned NewCount = 0;
1879  bool FirstRelease = true;
1880  for (SmallVector<Instruction *, 4> NewRetains{Retain};;) {
1881  SmallVector<Instruction *, 4> NewReleases;
1882  for (Instruction *NewRetain : NewRetains) {
1883  auto It = Retains.find(NewRetain);
1884  assert(It != Retains.end());
1885  const RRInfo &NewRetainRRI = It->second;
1886  KnownSafeTD &= NewRetainRRI.KnownSafe;
1887  CFGHazardAfflicted |= NewRetainRRI.CFGHazardAfflicted;
1888  for (Instruction *NewRetainRelease : NewRetainRRI.Calls) {
1889  auto Jt = Releases.find(NewRetainRelease);
1890  if (Jt == Releases.end())
1891  return false;
1892  const RRInfo &NewRetainReleaseRRI = Jt->second;
1893 
1894  // If the release does not have a reference to the retain as well,
1895  // something happened which is unaccounted for. Do not do anything.
1896  //
1897  // This can happen if we catch an additive overflow during path count
1898  // merging.
1899  if (!NewRetainReleaseRRI.Calls.count(NewRetain))
1900  return false;
1901 
1902  if (ReleasesToMove.Calls.insert(NewRetainRelease).second) {
1903  // If we overflow when we compute the path count, don't remove/move
1904  // anything.
1905  const BBState &NRRBBState = BBStates[NewRetainRelease->getParent()];
1906  unsigned PathCount = BBState::OverflowOccurredValue;
1907  if (NRRBBState.GetAllPathCountWithOverflow(PathCount))
1908  return false;
1909  assert(PathCount != BBState::OverflowOccurredValue &&
1910  "PathCount at this point can not be "
1911  "OverflowOccurredValue.");
1912  OldDelta -= PathCount;
1913 
1914  // Merge the ReleaseMetadata and IsTailCallRelease values.
1915  if (FirstRelease) {
1916  ReleasesToMove.ReleaseMetadata =
1917  NewRetainReleaseRRI.ReleaseMetadata;
1918  ReleasesToMove.IsTailCallRelease =
1919  NewRetainReleaseRRI.IsTailCallRelease;
1920  FirstRelease = false;
1921  } else {
1922  if (ReleasesToMove.ReleaseMetadata !=
1923  NewRetainReleaseRRI.ReleaseMetadata)
1924  ReleasesToMove.ReleaseMetadata = nullptr;
1925  if (ReleasesToMove.IsTailCallRelease !=
1926  NewRetainReleaseRRI.IsTailCallRelease)
1927  ReleasesToMove.IsTailCallRelease = false;
1928  }
1929 
1930  // Collect the optimal insertion points.
1931  if (!KnownSafe)
1932  for (Instruction *RIP : NewRetainReleaseRRI.ReverseInsertPts) {
1933  if (ReleasesToMove.ReverseInsertPts.insert(RIP).second) {
1934  // If we overflow when we compute the path count, don't
1935  // remove/move anything.
1936  const BBState &RIPBBState = BBStates[RIP->getParent()];
1937  PathCount = BBState::OverflowOccurredValue;
1938  if (RIPBBState.GetAllPathCountWithOverflow(PathCount))
1939  return false;
1940  assert(PathCount != BBState::OverflowOccurredValue &&
1941  "PathCount at this point can not be "
1942  "OverflowOccurredValue.");
1943  NewDelta -= PathCount;
1944  }
1945  }
1946  NewReleases.push_back(NewRetainRelease);
1947  }
1948  }
1949  }
1950  NewRetains.clear();
1951  if (NewReleases.empty()) break;
1952 
1953  // Back the other way.
1954  for (Instruction *NewRelease : NewReleases) {
1955  auto It = Releases.find(NewRelease);
1956  assert(It != Releases.end());
1957  const RRInfo &NewReleaseRRI = It->second;
1958  KnownSafeBU &= NewReleaseRRI.KnownSafe;
1959  CFGHazardAfflicted |= NewReleaseRRI.CFGHazardAfflicted;
1960  for (Instruction *NewReleaseRetain : NewReleaseRRI.Calls) {
1961  auto Jt = Retains.find(NewReleaseRetain);
1962  if (Jt == Retains.end())
1963  return false;
1964  const RRInfo &NewReleaseRetainRRI = Jt->second;
1965 
1966  // If the retain does not have a reference to the release as well,
1967  // something happened which is unaccounted for. Do not do anything.
1968  //
1969  // This can happen if we catch an additive overflow during path count
1970  // merging.
1971  if (!NewReleaseRetainRRI.Calls.count(NewRelease))
1972  return false;
1973 
1974  if (RetainsToMove.Calls.insert(NewReleaseRetain).second) {
1975  // If we overflow when we compute the path count, don't remove/move
1976  // anything.
1977  const BBState &NRRBBState = BBStates[NewReleaseRetain->getParent()];
1978  unsigned PathCount = BBState::OverflowOccurredValue;
1979  if (NRRBBState.GetAllPathCountWithOverflow(PathCount))
1980  return false;
1981  assert(PathCount != BBState::OverflowOccurredValue &&
1982  "PathCount at this point can not be "
1983  "OverflowOccurredValue.");
1984  OldDelta += PathCount;
1985  OldCount += PathCount;
1986 
1987  // Collect the optimal insertion points.
1988  if (!KnownSafe)
1989  for (Instruction *RIP : NewReleaseRetainRRI.ReverseInsertPts) {
1990  if (RetainsToMove.ReverseInsertPts.insert(RIP).second) {
1991  // If we overflow when we compute the path count, don't
1992  // remove/move anything.
1993  const BBState &RIPBBState = BBStates[RIP->getParent()];
1994 
1995  PathCount = BBState::OverflowOccurredValue;
1996  if (RIPBBState.GetAllPathCountWithOverflow(PathCount))
1997  return false;
1998  assert(PathCount != BBState::OverflowOccurredValue &&
1999  "PathCount at this point can not be "
2000  "OverflowOccurredValue.");
2001  NewDelta += PathCount;
2002  NewCount += PathCount;
2003  }
2004  }
2005  NewRetains.push_back(NewReleaseRetain);
2006  }
2007  }
2008  }
2009  if (NewRetains.empty()) break;
2010  }
2011 
2012  // We can only remove pointers if we are known safe in both directions.
2013  bool UnconditionallySafe = KnownSafeTD && KnownSafeBU;
2014  if (UnconditionallySafe) {
2015  RetainsToMove.ReverseInsertPts.clear();
2016  ReleasesToMove.ReverseInsertPts.clear();
2017  NewCount = 0;
2018  } else {
2019  // Determine whether the new insertion points we computed preserve the
2020  // balance of retain and release calls through the program.
2021  // TODO: If the fully aggressive solution isn't valid, try to find a
2022  // less aggressive solution which is.
2023  if (NewDelta != 0)
2024  return false;
2025 
2026  // At this point, we are not going to remove any RR pairs, but we still are
2027  // able to move RR pairs. If one of our pointers is afflicted with
2028  // CFGHazards, we cannot perform such code motion so exit early.
2029  const bool WillPerformCodeMotion =
2030  !RetainsToMove.ReverseInsertPts.empty() ||
2031  !ReleasesToMove.ReverseInsertPts.empty();
2032  if (CFGHazardAfflicted && WillPerformCodeMotion)
2033  return false;
2034  }
2035 
2036  // Determine whether the original call points are balanced in the retain and
2037  // release calls through the program. If not, conservatively don't touch
2038  // them.
2039  // TODO: It's theoretically possible to do code motion in this case, as
2040  // long as the existing imbalances are maintained.
2041  if (OldDelta != 0)
2042  return false;
2043 
2044  Changed = true;
2045  assert(OldCount != 0 && "Unreachable code?");
2046  NumRRs += OldCount - NewCount;
2047  // Set to true if we completely removed any RR pairs.
2048  AnyPairsCompletelyEliminated = NewCount == 0;
2049 
2050  // We can move calls!
2051  return true;
2052 }
2053 
2054 /// Identify pairings between the retains and releases, and delete and/or move
2055 /// them.
2056 bool ObjCARCOpt::PerformCodePlacement(
2059  DenseMap<Value *, RRInfo> &Releases, Module *M) {
2060  LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::PerformCodePlacement ==\n");
2061 
2062  bool AnyPairsCompletelyEliminated = false;
2064 
2065  // Visit each retain.
2067  E = Retains.end();
2068  I != E; ++I) {
2069  Value *V = I->first;
2070  if (!V) continue; // blotted
2071 
2072  Instruction *Retain = cast<Instruction>(V);
2073 
2074  LLVM_DEBUG(dbgs() << "Visiting: " << *Retain << "\n");
2075 
2076  Value *Arg = GetArgRCIdentityRoot(Retain);
2077 
2078  // If the object being released is in static or stack storage, we know it's
2079  // not being managed by ObjC reference counting, so we can delete pairs
2080  // regardless of what possible decrements or uses lie between them.
2081  bool KnownSafe = isa<Constant>(Arg) || isa<AllocaInst>(Arg);
2082 
2083  // A constant pointer can't be pointing to an object on the heap. It may
2084  // be reference-counted, but it won't be deleted.
2085  if (const LoadInst *LI = dyn_cast<LoadInst>(Arg))
2086  if (const GlobalVariable *GV =
2087  dyn_cast<GlobalVariable>(
2088  GetRCIdentityRoot(LI->getPointerOperand())))
2089  if (GV->isConstant())
2090  KnownSafe = true;
2091 
2092  // Connect the dots between the top-down-collected RetainsToMove and
2093  // bottom-up-collected ReleasesToMove to form sets of related calls.
2094  RRInfo RetainsToMove, ReleasesToMove;
2095 
2096  bool PerformMoveCalls = PairUpRetainsAndReleases(
2097  BBStates, Retains, Releases, M, Retain, DeadInsts,
2098  RetainsToMove, ReleasesToMove, Arg, KnownSafe,
2099  AnyPairsCompletelyEliminated);
2100 
2101  if (PerformMoveCalls) {
2102  // Ok, everything checks out and we're all set. Let's move/delete some
2103  // code!
2104  MoveCalls(Arg, RetainsToMove, ReleasesToMove,
2105  Retains, Releases, DeadInsts, M);
2106  }
2107  }
2108 
2109  // Now that we're done moving everything, we can delete the newly dead
2110  // instructions, as we no longer need them as insert points.
2111  while (!DeadInsts.empty())
2112  EraseInstruction(DeadInsts.pop_back_val());
2113 
2114  return AnyPairsCompletelyEliminated;
2115 }
2116 
2117 /// Weak pointer optimizations.
2118 void ObjCARCOpt::OptimizeWeakCalls(Function &F) {
2119  LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeWeakCalls ==\n");
2120 
2121  // First, do memdep-style RLE and S2L optimizations. We can't use memdep
2122  // itself because it uses AliasAnalysis and we need to do provenance
2123  // queries instead.
2124  for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
2125  Instruction *Inst = &*I++;
2126 
2127  LLVM_DEBUG(dbgs() << "Visiting: " << *Inst << "\n");
2128 
2130  if (Class != ARCInstKind::LoadWeak &&
2132  continue;
2133 
2134  // Delete objc_loadWeak calls with no users.
2135  if (Class == ARCInstKind::LoadWeak && Inst->use_empty()) {
2136  Inst->eraseFromParent();
2137  Changed = true;
2138  continue;
2139  }
2140 
2141  // TODO: For now, just look for an earlier available version of this value
2142  // within the same block. Theoretically, we could do memdep-style non-local
2143  // analysis too, but that would want caching. A better approach would be to
2144  // use the technique that EarlyCSE uses.
2145  inst_iterator Current = std::prev(I);
2146  BasicBlock *CurrentBB = &*Current.getBasicBlockIterator();
2147  for (BasicBlock::iterator B = CurrentBB->begin(),
2148  J = Current.getInstructionIterator();
2149  J != B; --J) {
2150  Instruction *EarlierInst = &*std::prev(J);
2151  ARCInstKind EarlierClass = GetARCInstKind(EarlierInst);
2152  switch (EarlierClass) {
2153  case ARCInstKind::LoadWeak:
2155  // If this is loading from the same pointer, replace this load's value
2156  // with that one.
2157  CallInst *Call = cast<CallInst>(Inst);
2158  CallInst *EarlierCall = cast<CallInst>(EarlierInst);
2159  Value *Arg = Call->getArgOperand(0);
2160  Value *EarlierArg = EarlierCall->getArgOperand(0);
2161  switch (PA.getAA()->alias(Arg, EarlierArg)) {
2163  Changed = true;
2164  // If the load has a builtin retain, insert a plain retain for it.
2165  if (Class == ARCInstKind::LoadWeakRetained) {
2167  CallInst *CI = CallInst::Create(Decl, EarlierCall, "", Call);
2168  CI->setTailCall();
2169  }
2170  // Zap the fully redundant load.
2171  Call->replaceAllUsesWith(EarlierCall);
2172  Call->eraseFromParent();
2173  goto clobbered;
2174  case AliasResult::MayAlias:
2176  goto clobbered;
2177  case AliasResult::NoAlias:
2178  break;
2179  }
2180  break;
2181  }
2183  case ARCInstKind::InitWeak: {
2184  // If this is storing to the same pointer and has the same size etc.
2185  // replace this load's value with the stored value.
2186  CallInst *Call = cast<CallInst>(Inst);
2187  CallInst *EarlierCall = cast<CallInst>(EarlierInst);
2188  Value *Arg = Call->getArgOperand(0);
2189  Value *EarlierArg = EarlierCall->getArgOperand(0);
2190  switch (PA.getAA()->alias(Arg, EarlierArg)) {
2192  Changed = true;
2193  // If the load has a builtin retain, insert a plain retain for it.
2194  if (Class == ARCInstKind::LoadWeakRetained) {
2196  CallInst *CI = CallInst::Create(Decl, EarlierCall, "", Call);
2197  CI->setTailCall();
2198  }
2199  // Zap the fully redundant load.
2200  Call->replaceAllUsesWith(EarlierCall->getArgOperand(1));
2201  Call->eraseFromParent();
2202  goto clobbered;
2203  case AliasResult::MayAlias:
2205  goto clobbered;
2206  case AliasResult::NoAlias:
2207  break;
2208  }
2209  break;
2210  }
2211  case ARCInstKind::MoveWeak:
2212  case ARCInstKind::CopyWeak:
2213  // TOOD: Grab the copied value.
2214  goto clobbered;
2216  case ARCInstKind::None:
2218  case ARCInstKind::User:
2219  // Weak pointers are only modified through the weak entry points
2220  // (and arbitrary calls, which could call the weak entry points).
2221  break;
2222  default:
2223  // Anything else could modify the weak pointer.
2224  goto clobbered;
2225  }
2226  }
2227  clobbered:;
2228  }
2229 
2230  // Then, for each destroyWeak with an alloca operand, check to see if
2231  // the alloca and all its users can be zapped.
2234  if (Class != ARCInstKind::DestroyWeak)
2235  continue;
2236 
2237  CallInst *Call = cast<CallInst>(&Inst);
2238  Value *Arg = Call->getArgOperand(0);
2239  if (AllocaInst *Alloca = dyn_cast<AllocaInst>(Arg)) {
2240  for (User *U : Alloca->users()) {
2241  const Instruction *UserInst = cast<Instruction>(U);
2242  switch (GetBasicARCInstKind(UserInst)) {
2243  case ARCInstKind::InitWeak:
2246  continue;
2247  default:
2248  goto done;
2249  }
2250  }
2251  Changed = true;
2252  for (User *U : llvm::make_early_inc_range(Alloca->users())) {
2253  CallInst *UserInst = cast<CallInst>(U);
2254  switch (GetBasicARCInstKind(UserInst)) {
2255  case ARCInstKind::InitWeak:
2257  // These functions return their second argument.
2258  UserInst->replaceAllUsesWith(UserInst->getArgOperand(1));
2259  break;
2261  // No return value.
2262  break;
2263  default:
2264  llvm_unreachable("alloca really is used!");
2265  }
2266  UserInst->eraseFromParent();
2267  }
2268  Alloca->eraseFromParent();
2269  done:;
2270  }
2271  }
2272 }
2273 
2274 /// Identify program paths which execute sequences of retains and releases which
2275 /// can be eliminated.
2276 bool ObjCARCOpt::OptimizeSequences(Function &F) {
2277  // Releases, Retains - These are used to store the results of the main flow
2278  // analysis. These use Value* as the key instead of Instruction* so that the
2279  // map stays valid when we get around to rewriting code and calls get
2280  // replaced by arguments.
2281  DenseMap<Value *, RRInfo> Releases;
2283 
2284  // This is used during the traversal of the function to track the
2285  // states for each identified object at each block.
2287 
2288  // Analyze the CFG of the function, and all instructions.
2289  bool NestingDetected = Visit(F, BBStates, Retains, Releases);
2290 
2291  if (DisableRetainReleasePairing)
2292  return false;
2293 
2294  // Transform.
2295  bool AnyPairsCompletelyEliminated = PerformCodePlacement(BBStates, Retains,
2296  Releases,
2297  F.getParent());
2298 
2299  return AnyPairsCompletelyEliminated && NestingDetected;
2300 }
2301 
2302 /// Check if there is a dependent call earlier that does not have anything in
2303 /// between the Retain and the call that can affect the reference count of their
2304 /// shared pointer argument. Note that Retain need not be in BB.
2306  Instruction *Retain,
2307  ProvenanceAnalysis &PA) {
2308  auto *Call = dyn_cast_or_null<CallInst>(findSingleDependency(
2309  CanChangeRetainCount, Arg, Retain->getParent(), Retain, PA));
2310 
2311  // Check that the pointer is the return value of the call.
2312  if (!Call || Arg != Call)
2313  return nullptr;
2314 
2315  // Check that the call is a regular call.
2316  ARCInstKind Class = GetBasicARCInstKind(Call);
2317  return Class == ARCInstKind::CallOrUser || Class == ARCInstKind::Call
2318  ? Call
2319  : nullptr;
2320 }
2321 
2322 /// Find a dependent retain that precedes the given autorelease for which there
2323 /// is nothing in between the two instructions that can affect the ref count of
2324 /// Arg.
2325 static CallInst *
2327  Instruction *Autorelease,
2328  ProvenanceAnalysis &PA) {
2329  auto *Retain = dyn_cast_or_null<CallInst>(
2331 
2332  // Check that we found a retain with the same argument.
2335  return nullptr;
2336  }
2337 
2338  return Retain;
2339 }
2340 
2341 /// Look for an ``autorelease'' instruction dependent on Arg such that there are
2342 /// no instructions dependent on Arg that need a positive ref count in between
2343 /// the autorelease and the ret.
2344 static CallInst *
2346  ReturnInst *Ret,
2347  ProvenanceAnalysis &PA) {
2349  auto *Autorelease = dyn_cast_or_null<CallInst>(
2351 
2352  if (!Autorelease)
2353  return nullptr;
2354  ARCInstKind AutoreleaseClass = GetBasicARCInstKind(Autorelease);
2355  if (!IsAutorelease(AutoreleaseClass))
2356  return nullptr;
2358  return nullptr;
2359 
2360  return Autorelease;
2361 }
2362 
2363 /// Look for this pattern:
2364 /// \code
2365 /// %call = call i8* @something(...)
2366 /// %2 = call i8* @objc_retain(i8* %call)
2367 /// %3 = call i8* @objc_autorelease(i8* %2)
2368 /// ret i8* %3
2369 /// \endcode
2370 /// And delete the retain and autorelease.
2371 void ObjCARCOpt::OptimizeReturns(Function &F) {
2372  if (!F.getReturnType()->isPointerTy())
2373  return;
2374 
2375  LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeReturns ==\n");
2376 
2377  for (BasicBlock &BB: F) {
2378  ReturnInst *Ret = dyn_cast<ReturnInst>(&BB.back());
2379  if (!Ret)
2380  continue;
2381 
2382  LLVM_DEBUG(dbgs() << "Visiting: " << *Ret << "\n");
2383 
2384  const Value *Arg = GetRCIdentityRoot(Ret->getOperand(0));
2385 
2386  // Look for an ``autorelease'' instruction that is a predecessor of Ret and
2387  // dependent on Arg such that there are no instructions dependent on Arg
2388  // that need a positive ref count in between the autorelease and Ret.
2391 
2392  if (!Autorelease)
2393  continue;
2394 
2396  Arg, Autorelease->getParent(), Autorelease, PA);
2397 
2398  if (!Retain)
2399  continue;
2400 
2401  // Check that there is nothing that can affect the reference count
2402  // between the retain and the call. Note that Retain need not be in BB.
2404 
2405  // Don't remove retainRV/autoreleaseRV pairs if the call isn't a tail call.
2406  if (!Call ||
2407  (!Call->isTailCall() &&
2410  continue;
2411 
2412  // If so, we can zap the retain and autorelease.
2413  Changed = true;
2414  ++NumRets;
2415  LLVM_DEBUG(dbgs() << "Erasing: " << *Retain << "\nErasing: " << *Autorelease
2416  << "\n");
2417  BundledInsts->eraseInst(Retain);
2418  EraseInstruction(Autorelease);
2419  }
2420 }
2421 
2422 #ifndef NDEBUG
2423 void
2424 ObjCARCOpt::GatherStatistics(Function &F, bool AfterOptimization) {
2425  Statistic &NumRetains =
2426  AfterOptimization ? NumRetainsAfterOpt : NumRetainsBeforeOpt;
2427  Statistic &NumReleases =
2428  AfterOptimization ? NumReleasesAfterOpt : NumReleasesBeforeOpt;
2429 
2430  for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
2431  Instruction *Inst = &*I++;
2432  switch (GetBasicARCInstKind(Inst)) {
2433  default:
2434  break;
2435  case ARCInstKind::Retain:
2436  ++NumRetains;
2437  break;
2438  case ARCInstKind::Release:
2439  ++NumReleases;
2440  break;
2441  }
2442  }
2443 }
2444 #endif
2445 
2446 void ObjCARCOpt::init(Module &M) {
2447  if (!EnableARCOpts)
2448  return;
2449 
2450  // Intuitively, objc_retain and others are nocapture, however in practice
2451  // they are not, because they return their argument value. And objc_release
2452  // calls finalizers which can have arbitrary side effects.
2453  MDKindCache.init(&M);
2454 
2455  // Initialize our runtime entry point cache.
2456  EP.init(&M);
2457 }
2458 
2459 bool ObjCARCOpt::run(Function &F, AAResults &AA) {
2460  if (!EnableARCOpts)
2461  return false;
2462 
2463  Changed = CFGChanged = false;
2464  BundledRetainClaimRVs BRV(false);
2465  BundledInsts = &BRV;
2466 
2467  LLVM_DEBUG(dbgs() << "<<< ObjCARCOpt: Visiting Function: " << F.getName()
2468  << " >>>"
2469  "\n");
2470 
2471  std::pair<bool, bool> R = BundledInsts->insertAfterInvokes(F, nullptr);
2472  Changed |= R.first;
2473  CFGChanged |= R.second;
2474 
2475  PA.setAA(&AA);
2476 
2477 #ifndef NDEBUG
2478  if (AreStatisticsEnabled()) {
2479  GatherStatistics(F, false);
2480  }
2481 #endif
2482 
2483  // This pass performs several distinct transformations. As a compile-time aid
2484  // when compiling code that isn't ObjC, skip these if the relevant ObjC
2485  // library functions aren't declared.
2486 
2487  // Preliminary optimizations. This also computes UsedInThisFunction.
2488  OptimizeIndividualCalls(F);
2489 
2490  // Optimizations for weak pointers.
2491  if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::LoadWeak)) |
2492  (1 << unsigned(ARCInstKind::LoadWeakRetained)) |
2493  (1 << unsigned(ARCInstKind::StoreWeak)) |
2494  (1 << unsigned(ARCInstKind::InitWeak)) |
2495  (1 << unsigned(ARCInstKind::CopyWeak)) |
2496  (1 << unsigned(ARCInstKind::MoveWeak)) |
2497  (1 << unsigned(ARCInstKind::DestroyWeak))))
2498  OptimizeWeakCalls(F);
2499 
2500  // Optimizations for retain+release pairs.
2501  if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::Retain)) |
2502  (1 << unsigned(ARCInstKind::RetainRV)) |
2503  (1 << unsigned(ARCInstKind::RetainBlock))))
2504  if (UsedInThisFunction & (1 << unsigned(ARCInstKind::Release)))
2505  // Run OptimizeSequences until it either stops making changes or
2506  // no retain+release pair nesting is detected.
2507  while (OptimizeSequences(F)) {}
2508 
2509  // Optimizations if objc_autorelease is used.
2510  if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::Autorelease)) |
2511  (1 << unsigned(ARCInstKind::AutoreleaseRV))))
2512  OptimizeReturns(F);
2513 
2514  // Gather statistics after optimization.
2515 #ifndef NDEBUG
2516  if (AreStatisticsEnabled()) {
2517  GatherStatistics(F, true);
2518  }
2519 #endif
2520 
2521  LLVM_DEBUG(dbgs() << "\n");
2522 
2523  return Changed;
2524 }
2525 
2526 void ObjCARCOpt::releaseMemory() {
2527  PA.clear();
2528 }
2529 
2530 /// @}
2531 ///
2532 
2535  ObjCARCOpt OCAO;
2536  OCAO.init(*F.getParent());
2537 
2538  bool Changed = OCAO.run(F, AM.getResult<AAManager>(F));
2539  bool CFGChanged = OCAO.hasCFGChanged();
2540  if (Changed) {
2541  PreservedAnalyses PA;
2542  if (!CFGChanged)
2543  PA.preserveSet<CFGAnalyses>();
2544  return PA;
2545  }
2546  return PreservedAnalyses::all();
2547 }
llvm::objcarc::BundledRetainClaimRVs
Definition: ObjCARC.h:106
llvm::SuccIterator
Definition: CFG.h:139
llvm::objcarc::GetBasicARCInstKind
ARCInstKind GetBasicARCInstKind(const Value *V)
Determine which objc runtime call instruction class V belongs to.
Definition: ObjCARCInstKind.h:104
i
i
Definition: README.txt:29
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::CallBase::getNumOperandBundles
unsigned getNumOperandBundles() const
Return the number of operand bundles associated with this User.
Definition: InstrTypes.h:1900
llvm::objcarc::ARCInstKind::User
@ User
could "use" a pointer
llvm::AAManager
A manager for alias analyses.
Definition: AliasAnalysis.h:1233
llvm::objcarc::operator<<
raw_ostream & operator<<(raw_ostream &OS, const ARCInstKind Class)
Definition: ObjCARCInstKind.cpp:28
llvm::AliasResult::MayAlias
@ MayAlias
The two locations may or may not alias.
Definition: AliasAnalysis.h:102
llvm::AliasResult::PartialAlias
@ PartialAlias
The two locations alias, but only due to a partial overlap.
Definition: AliasAnalysis.h:104
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:103
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::objcarc::hasAttachedCallOpBundle
bool hasAttachedCallOpBundle(const CallBase *CB)
Definition: ObjCARCUtil.h:29
llvm::objcarc::Sequence
Sequence
Definition: PtrState.h:41
llvm::CallInst::setTailCall
void setTailCall(bool IsTc=true)
Definition: Instructions.h:1682
llvm::ReturnInst
Return a value (possibly void), from a function.
Definition: Instructions.h:2986
llvm::SmallPtrSetImpl::erase
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
Definition: SmallPtrSet.h:378
llvm::PHINode::incoming_values
op_range incoming_values()
Definition: Instructions.h:2719
Metadata.h
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
BlotMapVector.h
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:779
llvm::succ_end
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
InstIterator.h
llvm::Function
Definition: Function.h:61
llvm::objcarc::NeedsPositiveRetainCount
@ NeedsPositiveRetainCount
Definition: DependencyAnalysis.h:45
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
Pass.h
llvm::CallBase::setCalledFunction
void setCalledFunction(Function *Fn)
Sets the function called, including updating the function type.
Definition: InstrTypes.h:1429
arc
objc arc
Definition: ObjCARCOpts.cpp:610
llvm::BitCastInst
This class represents a no-op cast from one type to another.
Definition: Instructions.h:5200
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
Statistic.h
llvm::objcarc::S_Use
@ S_Use
any use of x.
Definition: PtrState.h:45
llvm::objcarc::ARCInstKind::RetainBlock
@ RetainBlock
objc_retainBlock
ErrorHandling.h
llvm::GlobalVariable
Definition: GlobalVariable.h:40
llvm::Instruction::insertBefore
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
Definition: Instruction.cpp:84
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::erase
bool erase(const KeyT &Val)
Definition: DenseMap.h:302
BBState::OverflowOccurredValue
static const unsigned OverflowOccurredValue
Definition: ObjCARCOpts.cpp:211
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
DenseMap.h
llvm::objcarc::IsNeverTail
bool IsNeverTail(ARCInstKind Class)
Test if the given class represents instructions which are never safe to mark with the "tail" keyword.
Definition: ObjCARCInstKind.cpp:557
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:333
llvm::objcarc::ARCInstKind::LoadWeak
@ LoadWeak
objc_loadWeak (derived)
EHPersonalities.h
llvm::TinyPtrVector::front
EltTy front() const
Definition: TinyPtrVector.h:230
llvm::objcarc::ARCInstKind::Call
@ Call
could call objc_release
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::objcarc::ARCInstKind::MoveWeak
@ MoveWeak
objc_moveWeak (derived)
llvm::MipsISD::Ret
@ Ret
Definition: MipsISelLowering.h:116
llvm::Intrinsic::not_intrinsic
@ not_intrinsic
Definition: Intrinsics.h:45
llvm::objcarc::ProvenanceAnalysis
This is similar to BasicAliasAnalysis, and it uses many of the same techniques, except it uses specia...
Definition: ProvenanceAnalysis.h:51
STLExtras.h
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
llvm::successors
succ_range successors(Instruction *I)
Definition: CFG.h:262
LLVM_ATTRIBUTE_UNUSED
#define LLVM_ATTRIBUTE_UNUSED
Definition: Compiler.h:188
llvm::objcarc::GetARCInstKind
ARCInstKind GetARCInstKind(const Value *V)
Map V to its ARCInstKind equivalence class.
Definition: ObjCARCInstKind.cpp:213
llvm::Type::getInt8Ty
static IntegerType * getInt8Ty(LLVMContext &C)
Definition: Type.cpp:201
llvm::objcarc::IsAutorelease
bool IsAutorelease(ARCInstKind Class)
Test if the given class is objc_autorelease or equivalent.
Definition: ObjCARCInstKind.cpp:381
llvm::objcarc::ARCInstKind::Autorelease
@ Autorelease
objc_autorelease
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::MDNode::get
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1208
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:198
llvm::Instruction::setMetadata
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1336
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
AliasAnalysis.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::InstIterator::getInstructionIterator
BIty & getInstructionIterator()
Definition: InstIterator.h:74
llvm::classifyEHPersonality
EHPersonality classifyEHPersonality(const Value *Pers)
See if the given exception handling personality function is one that we understand.
Definition: EHPersonalities.cpp:21
llvm::objcarc::ObjCARCAAWrapperPass
Legacy wrapper pass to provide the ObjCARCAAResult object.
Definition: ObjCARCAliasAnalysis.h:80
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:206
Instruction.h
CommandLine.h
llvm::Instruction::getNumSuccessors
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
Definition: Instruction.cpp:765
llvm::objcarc::RRInfo
Unidirectional information about either a retain-decrement-use-release sequence or release-use-decrem...
Definition: PtrState.h:56
llvm::AreStatisticsEnabled
bool AreStatisticsEnabled()
Check if statistics are enabled.
Definition: Statistic.cpp:138
optimization
objc ObjC ARC optimization
Definition: ObjCARCOpts.cpp:610
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
Constants.h
llvm::PHINode::getIncomingValue
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Definition: Instructions.h:2729
llvm::AAResults
Definition: AliasAnalysis.h:456
llvm::objcarc::ARCInstKind::InitWeak
@ InitWeak
objc_initWeak (derived)
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::objcarc::ARCRuntimeEntryPointKind::Release
@ Release
llvm::objcarc::GetArgRCIdentityRoot
Value * GetArgRCIdentityRoot(Value *Inst)
Assuming the given instruction is one of the special calls such as objc_retain or objc_release,...
Definition: ObjCARCAnalysisUtils.h:128
llvm::User
Definition: User.h:44
DependencyAnalysis.h
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::objcarc::ARCInstKind::CallOrUser
@ CallOrUser
could call objc_release and/or "use" pointers
llvm::objcarc::IsNoopOnGlobal
bool IsNoopOnGlobal(ARCInstKind Class)
Test if the given class represents instructions which do nothing if passed a global variable.
Definition: ObjCARCInstKind.cpp:486
InstrTypes.h
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:296
collectReleaseInsertPts
static void collectReleaseInsertPts(const BlotMapVector< Value *, RRInfo > &Retains, DenseMap< const Instruction *, SmallPtrSet< const Value *, 2 >> &ReleaseInsertPtToRCIdentityRoots)
Definition: ObjCARCOpts.cpp:1504
llvm::CallInst::Create
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:1518
MaxPtrStates
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))
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::ObjCARCOptPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: ObjCARCOpts.cpp:2533
llvm::objcarc::ARCInstKind::Release
@ Release
objc_release
llvm::objcarc::ARCInstKind::RetainRV
@ RetainRV
objc_retainAutoreleasedReturnValue
llvm::BlotMapVector::empty
bool empty() const
Definition: BlotMapVector.h:109
llvm::initializeObjCARCOptLegacyPassPass
void initializeObjCARCOptLegacyPassPass(PassRegistry &)
llvm::BlotMapVector::const_iterator
typename VectorTy::const_iterator const_iterator
Definition: BlotMapVector.h:48
false
Definition: StackSlotColoring.cpp:142
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::objcarc::ARCInstKind::NoopCast
@ NoopCast
objc_retainedObject, etc.
llvm::objcarc::getEquivalentPHIs
void getEquivalentPHIs(PHINodeTy &PN, VectorTy &PHIList)
Return the list of PHI nodes that are equivalent to PN.
Definition: ObjCARC.h:75
llvm::objcarc::ARCInstKind::CopyWeak
@ CopyWeak
objc_copyWeak (derived)
llvm::objcarc::RRInfo::KnownSafe
bool KnownSafe
After an objc_retain, the reference count of the referenced object is known to be positive.
Definition: PtrState.h:69
llvm::Instruction
Definition: Instruction.h:45
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::objcarc::BottomUpPtrState
Definition: PtrState.h:168
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:230
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1771
llvm::objcarc::ARCInstKind::IntrinsicUser
@ IntrinsicUser
llvm.objc.clang.arc.use
llvm::BlotMapVector::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &InsertPair)
Definition: BlotMapVector.h:67
SmallPtrSet.h
llvm::objcarc::S_None
@ S_None
Definition: PtrState.h:42
FindSingleUseIdentifiedObject
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:89
FindPredecessorRetainWithSafePath
static CallInst * FindPredecessorRetainWithSafePath(const Value *Arg, BasicBlock *BB, Instruction *Autorelease, ProvenanceAnalysis &PA)
Find a dependent retain that precedes the given autorelease for which there is nothing in between the...
Definition: ObjCARCOpts.cpp:2326
llvm::objcarc::S_Retain
@ S_Retain
objc_retain(x).
Definition: PtrState.h:43
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:153
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2725
llvm::objcarc::RRInfo::ReverseInsertPts
SmallPtrSet< Instruction *, 2 > ReverseInsertPts
The set of optimal insert positions for moving calls in the opposite sequence.
Definition: PtrState.h:84
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:345
llvm::objcarc::ARCInstKind
ARCInstKind
Definition: ObjCARCInstKind.h:28
Type.h
llvm::objcarc::IsAlwaysTail
bool IsAlwaysTail(ARCInstKind Class)
Test if the given class represents instructions which are always safe to mark with the "tail" keyword...
Definition: ObjCARCInstKind.cpp:521
llvm::Instruction::getMetadata
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:282
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
CFG.h
ARCRuntimeEntryPoints.h
llvm::InvokeInst
Invoke instruction.
Definition: Instructions.h:3749
llvm::objcarc::ARCInstKind::AutoreleasepoolPop
@ AutoreleasepoolPop
objc_autoreleasePoolPop
HasSafePathToPredecessorCall
static CallInst * HasSafePathToPredecessorCall(const Value *Arg, Instruction *Retain, ProvenanceAnalysis &PA)
Check if there is a dependent call earlier that does not have anything in between the Retain and the ...
Definition: ObjCARCOpts.cpp:2305
BasicBlock.h
llvm::cl::opt
Definition: CommandLine.h:1434
llvm::instructions
inst_range instructions(Function *F)
Definition: InstIterator.h:133
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:304
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:78
ProvenanceAnalysis.h
llvm::objcarc::ARCMDKindID::ImpreciseRelease
@ ImpreciseRelease
llvm::BlotMapVector
An associative container with fast insertion-order (deterministic) iteration over its elements.
Definition: BlotMapVector.h:22
llvm::PointerType::getUnqual
static PointerType * getUnqual(Type *ElementType)
This constructs a pointer to an object of the specified type in the default address space (address sp...
Definition: DerivedTypes.h:651
llvm::colorEHFunclets
DenseMap< BasicBlock *, ColorVector > colorEHFunclets(Function &F)
If an EH funclet personality is in use (see isFuncletEHPersonality), this will recompute which blocks...
Definition: EHPersonalities.cpp:81
llvm::objcarc::IsNoThrow
bool IsNoThrow(ARCInstKind Class)
Test if the given class represents instructions which are always safe to mark with the nounwind attri...
Definition: ObjCARCInstKind.cpp:596
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::objcarc::S_Stop
@ S_Stop
code motion is stopped.
Definition: PtrState.h:46
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
llvm::objcarc::ARCMDKindID::NoObjCARCExceptions
@ NoObjCARCExceptions
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::succ_begin
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:99
llvm::isScopedEHPersonality
bool isScopedEHPersonality(EHPersonality Pers)
Returns true if this personality uses scope-style EH IR instructions: catchswitch,...
Definition: EHPersonalities.h:80
llvm::GetElementPtrInst
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:928
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
llvm::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:576
llvm::is_contained
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1616
ObjCARCInstKind.h
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
llvm::objcarc::RRInfo::IsTailCallRelease
bool IsTailCallRelease
True of the objc_release calls are all marked with the "tail" keyword.
Definition: PtrState.h:72
isInertARCValue
static bool isInertARCValue(Value *V, SmallPtrSet< Value *, 1 > &VisitedPhis)
This function returns true if the value is inert.
Definition: ObjCARCOpts.cpp:907
llvm::objcarc::S_MovableRelease
@ S_MovableRelease
objc_release(x), !clang.imprecise_release.
Definition: PtrState.h:47
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::NVPTXISD::CallArg
@ CallArg
Definition: NVPTXISelLowering.h:40
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::objcarc::CanChangeRetainCount
@ CanChangeRetainCount
Definition: DependencyAnalysis.h:47
llvm::objcarc::EnableARCOpts
bool EnableARCOpts
A handy option to enable/disable all ARC Optimizations.
Definition: ObjCARCAnalysisUtils.cpp:23
llvm::Type::isVoidTy
bool isVoidTy() const
Return true if this is 'void'.
Definition: Type.h:138
llvm::objcarc::IsRetain
bool IsRetain(ARCInstKind Class)
Test if the given class is objc_retain or equivalent.
Definition: ObjCARCInstKind.cpp:345
ObjCARCAliasAnalysis.h
llvm::objcarc
Definition: ObjCARCAliasAnalysis.h:29
llvm::objcarc::IsObjCIdentifiedObject
bool IsObjCIdentifiedObject(const Value *V)
Return true if this value refers to a distinct and identifiable object.
Definition: ObjCARCAnalysisUtils.h:183
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::MDNode
Metadata node.
Definition: Metadata.h:906
getRCIdentityRootsFromReleaseInsertPt
static const SmallPtrSet< const Value *, 2 > * getRCIdentityRootsFromReleaseInsertPt(const Instruction *InsertPt, const DenseMap< const Instruction *, SmallPtrSet< const Value *, 2 >> &ReleaseInsertPtToRCIdentityRoots)
Definition: ObjCARCOpts.cpp:1523
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
llvm::objcarc::RRInfo::CFGHazardAfflicted
bool CFGHazardAfflicted
If this is true, we cannot perform code motion but can still remove retain/release pairs.
Definition: PtrState.h:88
llvm::objcarc::IsNoopInstruction
bool IsNoopInstruction(const Instruction *I)
Definition: ObjCARCAnalysisUtils.h:136
llvm::objcarc::ARCMDKindCache
A cache of MDKinds used by various ARC optimizations.
Definition: ObjCARCAnalysisUtils.h:226
llvm::SmallPtrSetImplBase::clear
void clear()
Definition: SmallPtrSet.h:94
FindPredecessorAutoreleaseWithSafePath
static CallInst * FindPredecessorAutoreleaseWithSafePath(const Value *Arg, BasicBlock *BB, ReturnInst *Ret, ProvenanceAnalysis &PA)
Look for an `‘autorelease’' instruction dependent on Arg such that there are no instructions dependen...
Definition: ObjCARCOpts.cpp:2345
None.h
llvm::objcarc::IsNullOrUndef
bool IsNullOrUndef(const Value *V)
Definition: ObjCARCAnalysisUtils.h:132
llvm::objcarc::PtrState::IsKnownSafe
bool IsKnownSafe() const
Definition: PtrState.h:119
llvm::TinyPtrVector::size
unsigned size() const
Definition: TinyPtrVector.h:172
llvm::CallBase::getOperandBundleAt
OperandBundleUse getOperandBundleAt(unsigned Index) const
Return the operand bundle at a specific index.
Definition: InstrTypes.h:1956
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::CFGAnalyses
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:116
llvm::objcarc::RRInfo::ReleaseMetadata
MDNode * ReleaseMetadata
If the Calls are objc_release calls and they all have a clang.imprecise_release tag,...
Definition: PtrState.h:76
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:532
llvm::AliasResult::NoAlias
@ NoAlias
The two locations do not alias at all.
Definition: AliasAnalysis.h:99
Compiler.h
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:990
llvm::AliasResult::MustAlias
@ MustAlias
The two locations precisely alias each other.
Definition: AliasAnalysis.h:106
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::TrackingStatistic
Definition: Statistic.h:49
llvm::objcarc::PtrState::GetSeq
Sequence GetSeq() const
Definition: PtrState.h:150
llvm::Type::getContext
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
Definition: Type.h:127
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:175
llvm::BasicBlock::getTerminator
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:148
llvm::objcarc::GetRCIdentityRoot
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...
Definition: ObjCARCAnalysisUtils.h:107
llvm::CallBase::setArgOperand
void setArgOperand(unsigned i, Value *v)
Definition: InstrTypes.h:1343
llvm::Value::stripPointerCasts
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition: Value.cpp:687
ObjCARCAnalysisUtils.h
llvm::objcarc::RRInfo::Calls
SmallPtrSet< Instruction *, 2 > Calls
For a top-down sequence, the set of objc_retains or objc_retainBlocks.
Definition: PtrState.h:80
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::empty
LLVM_NODISCARD bool empty() const
Definition: DenseMap.h:97
llvm::objcarc::ARCInstKind::AutoreleasepoolPush
@ AutoreleasepoolPush
objc_autoreleasePoolPush
llvm::BlotMapVector::find
iterator find(const KeyT &Key)
Definition: BlotMapVector.h:79
ObjCARCUtil.h
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
Constant.h
llvm::Constant::getNullValue
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:348
llvm::objcarc::ARCRuntimeEntryPoints
Declarations for ObjC runtime functions and constants.
Definition: ARCRuntimeEntryPoints.h:52
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end
iterator end()
Definition: DenseMap.h:83
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:321
CheckForUseCFGHazard
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...
Definition: ObjCARCOpts.cpp:1214
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
GlobalVariable.h
llvm::objcarc::ARCInstKind::StoreWeak
@ StoreWeak
objc_storeWeak (primitive)
llvm::pred_end
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:112
llvm::objcarc::TopDownPtrState
Definition: PtrState.h:189
Casting.h
Function.h
llvm::objcarc::ARCInstKind::DestroyWeak
@ DestroyWeak
objc_destroyWeak (derived)
llvm::inst_end
inst_iterator inst_end(Function *F)
Definition: InstIterator.h:132
llvm::Instruction::isEHPad
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:661
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:585
llvm::objcarc::findSingleDependency
llvm::Instruction * findSingleDependency(DependenceKind Flavor, const Value *Arg, BasicBlock *StartBB, Instruction *StartInst, ProvenanceAnalysis &PA)
Find dependent instructions.
Definition: DependencyAnalysis.cpp:263
CheckForCanReleaseCFGHazard
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...
Definition: ObjCARCOpts.cpp:1251
llvm::BlotMapVector::blot
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
llvm::tgtok::Class
@ Class
Definition: TGLexer.h:50
llvm::objcarc::EraseInstruction
static void EraseInstruction(Instruction *CI)
Erase the given instruction.
Definition: ObjCARC.h:40
llvm::BasicBlock::back
const Instruction & back() const
Definition: BasicBlock.h:310
llvm::objcarc::ARCInstKind::ClaimRV
@ ClaimRV
objc_unsafeClaimAutoreleasedReturnValue
llvm::pred_begin
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:109
llvm::objcarc::ARCRuntimeEntryPointKind::Retain
@ Retain
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
Instructions.h
llvm::PreservedAnalyses::preserveSet
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:191
llvm::objcarc::ARCInstKind::None
@ None
anything that is inert from an ARC perspective.
SmallVector.h
User.h
ObjCARC.h
PtrState.h
ComputePostOrders
static void ComputePostOrders(Function &F, SmallVectorImpl< BasicBlock * > &PostOrder, SmallVectorImpl< BasicBlock * > &ReverseCFGPostOrder, unsigned NoObjCARCExceptionsMDKind, DenseMap< const BasicBlock *, BBState > &BBStates)
Definition: ObjCARCOpts.cpp:1682
llvm::InstIterator::getBasicBlockIterator
BBIty & getBasicBlockIterator()
Definition: InstIterator.h:73
llvm::LLVMContext::OB_funclet
@ OB_funclet
Definition: LLVMContext.h:91
ObjCARCOptLegacyPass::ID
static char ID
Definition: ObjCARCOpts.cpp:598
llvm::CallBase::getArgOperand
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1338
llvm::AAResultsWrapperPass
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Definition: AliasAnalysis.h:1281
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2749
llvm::BlotMapVector::clear
void clear()
Definition: BlotMapVector.h:104
Users
iv Induction Variable Users
Definition: IVUsers.cpp:52
llvm::BlotMapVector::begin
iterator begin()
Definition: BlotMapVector.h:50
llvm::objcarc::ARCRuntimeEntryPointKind::Autorelease
@ Autorelease
llvm::PHINode
Definition: Instructions.h:2633
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
llvm::createObjCARCOptPass
Pass * createObjCARCOptPass()
Definition: ObjCARCOpts.cpp:613
DerivedTypes.h
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1475
llvm::InliningAdvisorMode::Release
@ Release
llvm::objcarc::S_CanRelease
@ S_CanRelease
foo(x) – x could possibly see a ref count decrement.
Definition: PtrState.h:44
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::succ_iterator
SuccIterator< Instruction, BasicBlock > succ_iterator
Definition: CFG.h:243
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:172
llvm::inst_begin
inst_iterator inst_begin(Function *F)
Definition: InstIterator.h:131
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
LLVMContext.h
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:62
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::cl::desc
Definition: CommandLine.h:414
llvm::InstIterator
Definition: InstIterator.h:32
raw_ostream.h
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(ObjCARCOptLegacyPass, "objc-arc", "ObjC ARC optimization", false, false) INITIALIZE_PASS_END(ObjCARCOptLegacyPass
llvm::TinyPtrVector
TinyPtrVector - This class is specialized for cases where there are normally 0 or 1 element in a vect...
Definition: TinyPtrVector.h:30
Value.h
InitializePasses.h
llvm::objcarc::PtrState
This class summarizes several per-pointer runtime properties which are propagated through the flow gr...
Definition: PtrState.h:101
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::objcarc::ARCInstKind::Retain
@ Retain
objc_retain
Debug.h
llvm::objcarc::IsForwarding
bool IsForwarding(ARCInstKind Class)
Test if the given class represents instructions which return their argument verbatim.
Definition: ObjCARCInstKind.cpp:416
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:422
llvm::objcarc::AutoreleasePoolBoundary
@ AutoreleasePoolBoundary
Definition: DependencyAnalysis.h:46
llvm::objcarc::IsNoopOnNull
bool IsNoopOnNull(ARCInstKind Class)
Test if the given class represents instructions which do nothing if passed a null pointer.
Definition: ObjCARCInstKind.cpp:451
llvm::BlotMapVector::end
iterator end()
Definition: BlotMapVector.h:51
llvm::BasicBlock::const_iterator
InstListType::const_iterator const_iterator
Definition: BasicBlock.h:91
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1172
llvm::objcarc::ARCInstKind::LoadWeakRetained
@ LoadWeakRetained
objc_loadWeakRetained (primitive)
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:908
llvm::SmallPtrSetImpl::insert
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:364
llvm::objcarc::ARCInstKind::AutoreleaseRV
@ AutoreleaseRV
objc_autoreleaseReturnValue
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37