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