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