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