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