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