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