LLVM  mainline
ObjCARCOpts.cpp
Go to the documentation of this file.
00001 //===- ObjCARCOpts.cpp - ObjC ARC Optimization ----------------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 /// \file
00010 /// This file defines ObjC ARC optimizations. ARC stands for Automatic
00011 /// Reference Counting and is a system for managing reference counts for objects
00012 /// in Objective C.
00013 ///
00014 /// The optimizations performed include elimination of redundant, partially
00015 /// redundant, and inconsequential reference count operations, elimination of
00016 /// redundant weak pointer operations, and numerous minor simplifications.
00017 ///
00018 /// WARNING: This file knows about certain library functions. It recognizes them
00019 /// by name, and hardwires knowledge of their semantics.
00020 ///
00021 /// WARNING: This file knows about how certain Objective-C library functions are
00022 /// used. Naive LLVM IR transformations which would otherwise be
00023 /// behavior-preserving may break these assumptions.
00024 ///
00025 //===----------------------------------------------------------------------===//
00026 
00027 #include "ObjCARC.h"
00028 #include "ARCRuntimeEntryPoints.h"
00029 #include "BlotMapVector.h"
00030 #include "DependencyAnalysis.h"
00031 #include "ObjCARCAliasAnalysis.h"
00032 #include "ProvenanceAnalysis.h"
00033 #include "PtrState.h"
00034 #include "llvm/ADT/DenseMap.h"
00035 #include "llvm/ADT/DenseSet.h"
00036 #include "llvm/ADT/STLExtras.h"
00037 #include "llvm/ADT/SmallPtrSet.h"
00038 #include "llvm/ADT/Statistic.h"
00039 #include "llvm/IR/CFG.h"
00040 #include "llvm/IR/IRBuilder.h"
00041 #include "llvm/IR/LLVMContext.h"
00042 #include "llvm/Support/Debug.h"
00043 #include "llvm/Support/raw_ostream.h"
00044 
00045 using namespace llvm;
00046 using namespace llvm::objcarc;
00047 
00048 #define DEBUG_TYPE "objc-arc-opts"
00049 
00050 /// \defgroup ARCUtilities Utility declarations/definitions specific to ARC.
00051 /// @{
00052 
00053 /// \brief This is similar to GetRCIdentityRoot but it stops as soon
00054 /// as it finds a value with multiple uses.
00055 static const Value *FindSingleUseIdentifiedObject(const Value *Arg) {
00056   if (Arg->hasOneUse()) {
00057     if (const BitCastInst *BC = dyn_cast<BitCastInst>(Arg))
00058       return FindSingleUseIdentifiedObject(BC->getOperand(0));
00059     if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Arg))
00060       if (GEP->hasAllZeroIndices())
00061         return FindSingleUseIdentifiedObject(GEP->getPointerOperand());
00062     if (IsForwarding(GetBasicARCInstKind(Arg)))
00063       return FindSingleUseIdentifiedObject(
00064                cast<CallInst>(Arg)->getArgOperand(0));
00065     if (!IsObjCIdentifiedObject(Arg))
00066       return nullptr;
00067     return Arg;
00068   }
00069 
00070   // If we found an identifiable object but it has multiple uses, but they are
00071   // trivial uses, we can still consider this to be a single-use value.
00072   if (IsObjCIdentifiedObject(Arg)) {
00073     for (const User *U : Arg->users())
00074       if (!U->use_empty() || GetRCIdentityRoot(U) != Arg)
00075          return nullptr;
00076 
00077     return Arg;
00078   }
00079 
00080   return nullptr;
00081 }
00082 
00083 /// This is a wrapper around getUnderlyingObjCPtr along the lines of
00084 /// GetUnderlyingObjects except that it returns early when it sees the first
00085 /// alloca.
00086 static inline bool AreAnyUnderlyingObjectsAnAlloca(const Value *V,
00087                                                    const DataLayout &DL) {
00088   SmallPtrSet<const Value *, 4> Visited;
00089   SmallVector<const Value *, 4> Worklist;
00090   Worklist.push_back(V);
00091   do {
00092     const Value *P = Worklist.pop_back_val();
00093     P = GetUnderlyingObjCPtr(P, DL);
00094 
00095     if (isa<AllocaInst>(P))
00096       return true;
00097 
00098     if (!Visited.insert(P).second)
00099       continue;
00100 
00101     if (const SelectInst *SI = dyn_cast<const SelectInst>(P)) {
00102       Worklist.push_back(SI->getTrueValue());
00103       Worklist.push_back(SI->getFalseValue());
00104       continue;
00105     }
00106 
00107     if (const PHINode *PN = dyn_cast<const PHINode>(P)) {
00108       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
00109         Worklist.push_back(PN->getIncomingValue(i));
00110       continue;
00111     }
00112   } while (!Worklist.empty());
00113 
00114   return false;
00115 }
00116 
00117 
00118 /// @}
00119 ///
00120 /// \defgroup ARCOpt ARC Optimization.
00121 /// @{
00122 
00123 // TODO: On code like this:
00124 //
00125 // objc_retain(%x)
00126 // stuff_that_cannot_release()
00127 // objc_autorelease(%x)
00128 // stuff_that_cannot_release()
00129 // objc_retain(%x)
00130 // stuff_that_cannot_release()
00131 // objc_autorelease(%x)
00132 //
00133 // The second retain and autorelease can be deleted.
00134 
00135 // TODO: It should be possible to delete
00136 // objc_autoreleasePoolPush and objc_autoreleasePoolPop
00137 // pairs if nothing is actually autoreleased between them. Also, autorelease
00138 // calls followed by objc_autoreleasePoolPop calls (perhaps in ObjC++ code
00139 // after inlining) can be turned into plain release calls.
00140 
00141 // TODO: Critical-edge splitting. If the optimial insertion point is
00142 // a critical edge, the current algorithm has to fail, because it doesn't
00143 // know how to split edges. It should be possible to make the optimizer
00144 // think in terms of edges, rather than blocks, and then split critical
00145 // edges on demand.
00146 
00147 // TODO: OptimizeSequences could generalized to be Interprocedural.
00148 
00149 // TODO: Recognize that a bunch of other objc runtime calls have
00150 // non-escaping arguments and non-releasing arguments, and may be
00151 // non-autoreleasing.
00152 
00153 // TODO: Sink autorelease calls as far as possible. Unfortunately we
00154 // usually can't sink them past other calls, which would be the main
00155 // case where it would be useful.
00156 
00157 // TODO: The pointer returned from objc_loadWeakRetained is retained.
00158 
00159 // TODO: Delete release+retain pairs (rare).
00160 
00161 STATISTIC(NumNoops,       "Number of no-op objc calls eliminated");
00162 STATISTIC(NumPartialNoops, "Number of partially no-op objc calls eliminated");
00163 STATISTIC(NumAutoreleases,"Number of autoreleases converted to releases");
00164 STATISTIC(NumRets,        "Number of return value forwarding "
00165                           "retain+autoreleases eliminated");
00166 STATISTIC(NumRRs,         "Number of retain+release paths eliminated");
00167 STATISTIC(NumPeeps,       "Number of calls peephole-optimized");
00168 #ifndef NDEBUG
00169 STATISTIC(NumRetainsBeforeOpt,
00170           "Number of retains before optimization");
00171 STATISTIC(NumReleasesBeforeOpt,
00172           "Number of releases before optimization");
00173 STATISTIC(NumRetainsAfterOpt,
00174           "Number of retains after optimization");
00175 STATISTIC(NumReleasesAfterOpt,
00176           "Number of releases after optimization");
00177 #endif
00178 
00179 namespace {
00180   /// \brief Per-BasicBlock state.
00181   class BBState {
00182     /// The number of unique control paths from the entry which can reach this
00183     /// block.
00184     unsigned TopDownPathCount;
00185 
00186     /// The number of unique control paths to exits from this block.
00187     unsigned BottomUpPathCount;
00188 
00189     /// The top-down traversal uses this to record information known about a
00190     /// pointer at the bottom of each block.
00191     BlotMapVector<const Value *, TopDownPtrState> PerPtrTopDown;
00192 
00193     /// The bottom-up traversal uses this to record information known about a
00194     /// pointer at the top of each block.
00195     BlotMapVector<const Value *, BottomUpPtrState> PerPtrBottomUp;
00196 
00197     /// Effective predecessors of the current block ignoring ignorable edges and
00198     /// ignored backedges.
00199     SmallVector<BasicBlock *, 2> Preds;
00200 
00201     /// Effective successors of the current block ignoring ignorable edges and
00202     /// ignored backedges.
00203     SmallVector<BasicBlock *, 2> Succs;
00204 
00205   public:
00206     static const unsigned OverflowOccurredValue;
00207 
00208     BBState() : TopDownPathCount(0), BottomUpPathCount(0) { }
00209 
00210     typedef decltype(PerPtrTopDown)::iterator top_down_ptr_iterator;
00211     typedef decltype(PerPtrTopDown)::const_iterator const_top_down_ptr_iterator;
00212 
00213     top_down_ptr_iterator top_down_ptr_begin() { return PerPtrTopDown.begin(); }
00214     top_down_ptr_iterator top_down_ptr_end() { return PerPtrTopDown.end(); }
00215     const_top_down_ptr_iterator top_down_ptr_begin() const {
00216       return PerPtrTopDown.begin();
00217     }
00218     const_top_down_ptr_iterator top_down_ptr_end() const {
00219       return PerPtrTopDown.end();
00220     }
00221     bool hasTopDownPtrs() const {
00222       return !PerPtrTopDown.empty();
00223     }
00224 
00225     typedef decltype(PerPtrBottomUp)::iterator bottom_up_ptr_iterator;
00226     typedef decltype(
00227         PerPtrBottomUp)::const_iterator const_bottom_up_ptr_iterator;
00228 
00229     bottom_up_ptr_iterator bottom_up_ptr_begin() {
00230       return PerPtrBottomUp.begin();
00231     }
00232     bottom_up_ptr_iterator bottom_up_ptr_end() { return PerPtrBottomUp.end(); }
00233     const_bottom_up_ptr_iterator bottom_up_ptr_begin() const {
00234       return PerPtrBottomUp.begin();
00235     }
00236     const_bottom_up_ptr_iterator bottom_up_ptr_end() const {
00237       return PerPtrBottomUp.end();
00238     }
00239     bool hasBottomUpPtrs() const {
00240       return !PerPtrBottomUp.empty();
00241     }
00242 
00243     /// Mark this block as being an entry block, which has one path from the
00244     /// entry by definition.
00245     void SetAsEntry() { TopDownPathCount = 1; }
00246 
00247     /// Mark this block as being an exit block, which has one path to an exit by
00248     /// definition.
00249     void SetAsExit()  { BottomUpPathCount = 1; }
00250 
00251     /// Attempt to find the PtrState object describing the top down state for
00252     /// pointer Arg. Return a new initialized PtrState describing the top down
00253     /// state for Arg if we do not find one.
00254     TopDownPtrState &getPtrTopDownState(const Value *Arg) {
00255       return PerPtrTopDown[Arg];
00256     }
00257 
00258     /// Attempt to find the PtrState object describing the bottom up state for
00259     /// pointer Arg. Return a new initialized PtrState describing the bottom up
00260     /// state for Arg if we do not find one.
00261     BottomUpPtrState &getPtrBottomUpState(const Value *Arg) {
00262       return PerPtrBottomUp[Arg];
00263     }
00264 
00265     /// Attempt to find the PtrState object describing the bottom up state for
00266     /// pointer Arg.
00267     bottom_up_ptr_iterator findPtrBottomUpState(const Value *Arg) {
00268       return PerPtrBottomUp.find(Arg);
00269     }
00270 
00271     void clearBottomUpPointers() {
00272       PerPtrBottomUp.clear();
00273     }
00274 
00275     void clearTopDownPointers() {
00276       PerPtrTopDown.clear();
00277     }
00278 
00279     void InitFromPred(const BBState &Other);
00280     void InitFromSucc(const BBState &Other);
00281     void MergePred(const BBState &Other);
00282     void MergeSucc(const BBState &Other);
00283 
00284     /// Compute the number of possible unique paths from an entry to an exit
00285     /// which pass through this block. This is only valid after both the
00286     /// top-down and bottom-up traversals are complete.
00287     ///
00288     /// Returns true if overflow occurred. Returns false if overflow did not
00289     /// occur.
00290     bool GetAllPathCountWithOverflow(unsigned &PathCount) const {
00291       if (TopDownPathCount == OverflowOccurredValue ||
00292           BottomUpPathCount == OverflowOccurredValue)
00293         return true;
00294       unsigned long long Product =
00295         (unsigned long long)TopDownPathCount*BottomUpPathCount;
00296       // Overflow occurred if any of the upper bits of Product are set or if all
00297       // the lower bits of Product are all set.
00298       return (Product >> 32) ||
00299              ((PathCount = Product) == OverflowOccurredValue);
00300     }
00301 
00302     // Specialized CFG utilities.
00303     typedef SmallVectorImpl<BasicBlock *>::const_iterator edge_iterator;
00304     edge_iterator pred_begin() const { return Preds.begin(); }
00305     edge_iterator pred_end() const { return Preds.end(); }
00306     edge_iterator succ_begin() const { return Succs.begin(); }
00307     edge_iterator succ_end() const { return Succs.end(); }
00308 
00309     void addSucc(BasicBlock *Succ) { Succs.push_back(Succ); }
00310     void addPred(BasicBlock *Pred) { Preds.push_back(Pred); }
00311 
00312     bool isExit() const { return Succs.empty(); }
00313   };
00314 
00315   const unsigned BBState::OverflowOccurredValue = 0xffffffff;
00316 }
00317 
00318 namespace llvm {
00319 raw_ostream &operator<<(raw_ostream &OS,
00320                         BBState &BBState) LLVM_ATTRIBUTE_UNUSED;
00321 }
00322 
00323 void BBState::InitFromPred(const BBState &Other) {
00324   PerPtrTopDown = Other.PerPtrTopDown;
00325   TopDownPathCount = Other.TopDownPathCount;
00326 }
00327 
00328 void BBState::InitFromSucc(const BBState &Other) {
00329   PerPtrBottomUp = Other.PerPtrBottomUp;
00330   BottomUpPathCount = Other.BottomUpPathCount;
00331 }
00332 
00333 /// The top-down traversal uses this to merge information about predecessors to
00334 /// form the initial state for a new block.
00335 void BBState::MergePred(const BBState &Other) {
00336   if (TopDownPathCount == OverflowOccurredValue)
00337     return;
00338 
00339   // Other.TopDownPathCount can be 0, in which case it is either dead or a
00340   // loop backedge. Loop backedges are special.
00341   TopDownPathCount += Other.TopDownPathCount;
00342 
00343   // In order to be consistent, we clear the top down pointers when by adding
00344   // TopDownPathCount becomes OverflowOccurredValue even though "true" overflow
00345   // has not occurred.
00346   if (TopDownPathCount == OverflowOccurredValue) {
00347     clearTopDownPointers();
00348     return;
00349   }
00350 
00351   // Check for overflow. If we have overflow, fall back to conservative
00352   // behavior.
00353   if (TopDownPathCount < Other.TopDownPathCount) {
00354     TopDownPathCount = OverflowOccurredValue;
00355     clearTopDownPointers();
00356     return;
00357   }
00358 
00359   // For each entry in the other set, if our set has an entry with the same key,
00360   // merge the entries. Otherwise, copy the entry and merge it with an empty
00361   // entry.
00362   for (auto MI = Other.top_down_ptr_begin(), ME = Other.top_down_ptr_end();
00363        MI != ME; ++MI) {
00364     auto Pair = PerPtrTopDown.insert(*MI);
00365     Pair.first->second.Merge(Pair.second ? TopDownPtrState() : MI->second,
00366                              /*TopDown=*/true);
00367   }
00368 
00369   // For each entry in our set, if the other set doesn't have an entry with the
00370   // same key, force it to merge with an empty entry.
00371   for (auto MI = top_down_ptr_begin(), ME = top_down_ptr_end(); MI != ME; ++MI)
00372     if (Other.PerPtrTopDown.find(MI->first) == Other.PerPtrTopDown.end())
00373       MI->second.Merge(TopDownPtrState(), /*TopDown=*/true);
00374 }
00375 
00376 /// The bottom-up traversal uses this to merge information about successors to
00377 /// form the initial state for a new block.
00378 void BBState::MergeSucc(const BBState &Other) {
00379   if (BottomUpPathCount == OverflowOccurredValue)
00380     return;
00381 
00382   // Other.BottomUpPathCount can be 0, in which case it is either dead or a
00383   // loop backedge. Loop backedges are special.
00384   BottomUpPathCount += Other.BottomUpPathCount;
00385 
00386   // In order to be consistent, we clear the top down pointers when by adding
00387   // BottomUpPathCount becomes OverflowOccurredValue even though "true" overflow
00388   // has not occurred.
00389   if (BottomUpPathCount == OverflowOccurredValue) {
00390     clearBottomUpPointers();
00391     return;
00392   }
00393 
00394   // Check for overflow. If we have overflow, fall back to conservative
00395   // behavior.
00396   if (BottomUpPathCount < Other.BottomUpPathCount) {
00397     BottomUpPathCount = OverflowOccurredValue;
00398     clearBottomUpPointers();
00399     return;
00400   }
00401 
00402   // For each entry in the other set, if our set has an entry with the
00403   // same key, merge the entries. Otherwise, copy the entry and merge
00404   // it with an empty entry.
00405   for (auto MI = Other.bottom_up_ptr_begin(), ME = Other.bottom_up_ptr_end();
00406        MI != ME; ++MI) {
00407     auto Pair = PerPtrBottomUp.insert(*MI);
00408     Pair.first->second.Merge(Pair.second ? BottomUpPtrState() : MI->second,
00409                              /*TopDown=*/false);
00410   }
00411 
00412   // For each entry in our set, if the other set doesn't have an entry
00413   // with the same key, force it to merge with an empty entry.
00414   for (auto MI = bottom_up_ptr_begin(), ME = bottom_up_ptr_end(); MI != ME;
00415        ++MI)
00416     if (Other.PerPtrBottomUp.find(MI->first) == Other.PerPtrBottomUp.end())
00417       MI->second.Merge(BottomUpPtrState(), /*TopDown=*/false);
00418 }
00419 
00420 raw_ostream &llvm::operator<<(raw_ostream &OS, BBState &BBInfo) {
00421   // Dump the pointers we are tracking.
00422   OS << "    TopDown State:\n";
00423   if (!BBInfo.hasTopDownPtrs()) {
00424     DEBUG(llvm::dbgs() << "        NONE!\n");
00425   } else {
00426     for (auto I = BBInfo.top_down_ptr_begin(), E = BBInfo.top_down_ptr_end();
00427          I != E; ++I) {
00428       const PtrState &P = I->second;
00429       OS << "        Ptr: " << *I->first
00430          << "\n            KnownSafe:        " << (P.IsKnownSafe()?"true":"false")
00431          << "\n            ImpreciseRelease: "
00432            << (P.IsTrackingImpreciseReleases()?"true":"false") << "\n"
00433          << "            HasCFGHazards:    "
00434            << (P.IsCFGHazardAfflicted()?"true":"false") << "\n"
00435          << "            KnownPositive:    "
00436            << (P.HasKnownPositiveRefCount()?"true":"false") << "\n"
00437          << "            Seq:              "
00438          << P.GetSeq() << "\n";
00439     }
00440   }
00441 
00442   OS << "    BottomUp State:\n";
00443   if (!BBInfo.hasBottomUpPtrs()) {
00444     DEBUG(llvm::dbgs() << "        NONE!\n");
00445   } else {
00446     for (auto I = BBInfo.bottom_up_ptr_begin(), E = BBInfo.bottom_up_ptr_end();
00447          I != E; ++I) {
00448       const PtrState &P = I->second;
00449       OS << "        Ptr: " << *I->first
00450          << "\n            KnownSafe:        " << (P.IsKnownSafe()?"true":"false")
00451          << "\n            ImpreciseRelease: "
00452            << (P.IsTrackingImpreciseReleases()?"true":"false") << "\n"
00453          << "            HasCFGHazards:    "
00454            << (P.IsCFGHazardAfflicted()?"true":"false") << "\n"
00455          << "            KnownPositive:    "
00456            << (P.HasKnownPositiveRefCount()?"true":"false") << "\n"
00457          << "            Seq:              "
00458          << P.GetSeq() << "\n";
00459     }
00460   }
00461 
00462   return OS;
00463 }
00464 
00465 namespace {
00466 
00467   /// \brief The main ARC optimization pass.
00468   class ObjCARCOpt : public FunctionPass {
00469     bool Changed;
00470     ProvenanceAnalysis PA;
00471 
00472     /// A cache of references to runtime entry point constants.
00473     ARCRuntimeEntryPoints EP;
00474 
00475     /// A cache of MDKinds that can be passed into other functions to propagate
00476     /// MDKind identifiers.
00477     ARCMDKindCache MDKindCache;
00478 
00479     // This is used to track if a pointer is stored into an alloca.
00480     DenseSet<const Value *> MultiOwnersSet;
00481 
00482     /// A flag indicating whether this optimization pass should run.
00483     bool Run;
00484 
00485     /// Flags which determine whether each of the interesting runtine functions
00486     /// is in fact used in the current function.
00487     unsigned UsedInThisFunction;
00488 
00489     bool OptimizeRetainRVCall(Function &F, Instruction *RetainRV);
00490     void OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV,
00491                                    ARCInstKind &Class);
00492     void OptimizeIndividualCalls(Function &F);
00493 
00494     void CheckForCFGHazards(const BasicBlock *BB,
00495                             DenseMap<const BasicBlock *, BBState> &BBStates,
00496                             BBState &MyStates) const;
00497     bool VisitInstructionBottomUp(Instruction *Inst, BasicBlock *BB,
00498                                   BlotMapVector<Value *, RRInfo> &Retains,
00499                                   BBState &MyStates);
00500     bool VisitBottomUp(BasicBlock *BB,
00501                        DenseMap<const BasicBlock *, BBState> &BBStates,
00502                        BlotMapVector<Value *, RRInfo> &Retains);
00503     bool VisitInstructionTopDown(Instruction *Inst,
00504                                  DenseMap<Value *, RRInfo> &Releases,
00505                                  BBState &MyStates);
00506     bool VisitTopDown(BasicBlock *BB,
00507                       DenseMap<const BasicBlock *, BBState> &BBStates,
00508                       DenseMap<Value *, RRInfo> &Releases);
00509     bool Visit(Function &F, DenseMap<const BasicBlock *, BBState> &BBStates,
00510                BlotMapVector<Value *, RRInfo> &Retains,
00511                DenseMap<Value *, RRInfo> &Releases);
00512 
00513     void MoveCalls(Value *Arg, RRInfo &RetainsToMove, RRInfo &ReleasesToMove,
00514                    BlotMapVector<Value *, RRInfo> &Retains,
00515                    DenseMap<Value *, RRInfo> &Releases,
00516                    SmallVectorImpl<Instruction *> &DeadInsts, Module *M);
00517 
00518     bool
00519     PairUpRetainsAndReleases(DenseMap<const BasicBlock *, BBState> &BBStates,
00520                              BlotMapVector<Value *, RRInfo> &Retains,
00521                              DenseMap<Value *, RRInfo> &Releases, Module *M,
00522                              SmallVectorImpl<Instruction *> &NewRetains,
00523                              SmallVectorImpl<Instruction *> &NewReleases,
00524                              SmallVectorImpl<Instruction *> &DeadInsts,
00525                              RRInfo &RetainsToMove, RRInfo &ReleasesToMove,
00526                              Value *Arg, bool KnownSafe,
00527                              bool &AnyPairsCompletelyEliminated);
00528 
00529     bool PerformCodePlacement(DenseMap<const BasicBlock *, BBState> &BBStates,
00530                               BlotMapVector<Value *, RRInfo> &Retains,
00531                               DenseMap<Value *, RRInfo> &Releases, Module *M);
00532 
00533     void OptimizeWeakCalls(Function &F);
00534 
00535     bool OptimizeSequences(Function &F);
00536 
00537     void OptimizeReturns(Function &F);
00538 
00539 #ifndef NDEBUG
00540     void GatherStatistics(Function &F, bool AfterOptimization = false);
00541 #endif
00542 
00543     void getAnalysisUsage(AnalysisUsage &AU) const override;
00544     bool doInitialization(Module &M) override;
00545     bool runOnFunction(Function &F) override;
00546     void releaseMemory() override;
00547 
00548   public:
00549     static char ID;
00550     ObjCARCOpt() : FunctionPass(ID) {
00551       initializeObjCARCOptPass(*PassRegistry::getPassRegistry());
00552     }
00553   };
00554 }
00555 
00556 char ObjCARCOpt::ID = 0;
00557 INITIALIZE_PASS_BEGIN(ObjCARCOpt,
00558                       "objc-arc", "ObjC ARC optimization", false, false)
00559 INITIALIZE_PASS_DEPENDENCY(ObjCARCAliasAnalysis)
00560 INITIALIZE_PASS_END(ObjCARCOpt,
00561                     "objc-arc", "ObjC ARC optimization", false, false)
00562 
00563 Pass *llvm::createObjCARCOptPass() {
00564   return new ObjCARCOpt();
00565 }
00566 
00567 void ObjCARCOpt::getAnalysisUsage(AnalysisUsage &AU) const {
00568   AU.addRequired<ObjCARCAliasAnalysis>();
00569   AU.addRequired<AliasAnalysis>();
00570   // ARC optimization doesn't currently split critical edges.
00571   AU.setPreservesCFG();
00572 }
00573 
00574 /// Turn objc_retainAutoreleasedReturnValue into objc_retain if the operand is
00575 /// not a return value.  Or, if it can be paired with an
00576 /// objc_autoreleaseReturnValue, delete the pair and return true.
00577 bool
00578 ObjCARCOpt::OptimizeRetainRVCall(Function &F, Instruction *RetainRV) {
00579   // Check for the argument being from an immediately preceding call or invoke.
00580   const Value *Arg = GetArgRCIdentityRoot(RetainRV);
00581   ImmutableCallSite CS(Arg);
00582   if (const Instruction *Call = CS.getInstruction()) {
00583     if (Call->getParent() == RetainRV->getParent()) {
00584       BasicBlock::const_iterator I = Call;
00585       ++I;
00586       while (IsNoopInstruction(I)) ++I;
00587       if (&*I == RetainRV)
00588         return false;
00589     } else if (const InvokeInst *II = dyn_cast<InvokeInst>(Call)) {
00590       BasicBlock *RetainRVParent = RetainRV->getParent();
00591       if (II->getNormalDest() == RetainRVParent) {
00592         BasicBlock::const_iterator I = RetainRVParent->begin();
00593         while (IsNoopInstruction(I)) ++I;
00594         if (&*I == RetainRV)
00595           return false;
00596       }
00597     }
00598   }
00599 
00600   // Check for being preceded by an objc_autoreleaseReturnValue on the same
00601   // pointer. In this case, we can delete the pair.
00602   BasicBlock::iterator I = RetainRV, Begin = RetainRV->getParent()->begin();
00603   if (I != Begin) {
00604     do --I; while (I != Begin && IsNoopInstruction(I));
00605     if (GetBasicARCInstKind(I) == ARCInstKind::AutoreleaseRV &&
00606         GetArgRCIdentityRoot(I) == Arg) {
00607       Changed = true;
00608       ++NumPeeps;
00609 
00610       DEBUG(dbgs() << "Erasing autoreleaseRV,retainRV pair: " << *I << "\n"
00611                    << "Erasing " << *RetainRV << "\n");
00612 
00613       EraseInstruction(I);
00614       EraseInstruction(RetainRV);
00615       return true;
00616     }
00617   }
00618 
00619   // Turn it to a plain objc_retain.
00620   Changed = true;
00621   ++NumPeeps;
00622 
00623   DEBUG(dbgs() << "Transforming objc_retainAutoreleasedReturnValue => "
00624                   "objc_retain since the operand is not a return value.\n"
00625                   "Old = " << *RetainRV << "\n");
00626 
00627   Constant *NewDecl = EP.get(ARCRuntimeEntryPointKind::Retain);
00628   cast<CallInst>(RetainRV)->setCalledFunction(NewDecl);
00629 
00630   DEBUG(dbgs() << "New = " << *RetainRV << "\n");
00631 
00632   return false;
00633 }
00634 
00635 /// Turn objc_autoreleaseReturnValue into objc_autorelease if the result is not
00636 /// used as a return value.
00637 void ObjCARCOpt::OptimizeAutoreleaseRVCall(Function &F,
00638                                            Instruction *AutoreleaseRV,
00639                                            ARCInstKind &Class) {
00640   // Check for a return of the pointer value.
00641   const Value *Ptr = GetArgRCIdentityRoot(AutoreleaseRV);
00642   SmallVector<const Value *, 2> Users;
00643   Users.push_back(Ptr);
00644   do {
00645     Ptr = Users.pop_back_val();
00646     for (const User *U : Ptr->users()) {
00647       if (isa<ReturnInst>(U) || GetBasicARCInstKind(U) == ARCInstKind::RetainRV)
00648         return;
00649       if (isa<BitCastInst>(U))
00650         Users.push_back(U);
00651     }
00652   } while (!Users.empty());
00653 
00654   Changed = true;
00655   ++NumPeeps;
00656 
00657   DEBUG(dbgs() << "Transforming objc_autoreleaseReturnValue => "
00658                   "objc_autorelease since its operand is not used as a return "
00659                   "value.\n"
00660                   "Old = " << *AutoreleaseRV << "\n");
00661 
00662   CallInst *AutoreleaseRVCI = cast<CallInst>(AutoreleaseRV);
00663   Constant *NewDecl = EP.get(ARCRuntimeEntryPointKind::Autorelease);
00664   AutoreleaseRVCI->setCalledFunction(NewDecl);
00665   AutoreleaseRVCI->setTailCall(false); // Never tail call objc_autorelease.
00666   Class = ARCInstKind::Autorelease;
00667 
00668   DEBUG(dbgs() << "New: " << *AutoreleaseRV << "\n");
00669 
00670 }
00671 
00672 /// Visit each call, one at a time, and make simplifications without doing any
00673 /// additional analysis.
00674 void ObjCARCOpt::OptimizeIndividualCalls(Function &F) {
00675   DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeIndividualCalls ==\n");
00676   // Reset all the flags in preparation for recomputing them.
00677   UsedInThisFunction = 0;
00678 
00679   // Visit all objc_* calls in F.
00680   for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
00681     Instruction *Inst = &*I++;
00682 
00683     ARCInstKind Class = GetBasicARCInstKind(Inst);
00684 
00685     DEBUG(dbgs() << "Visiting: Class: " << Class << "; " << *Inst << "\n");
00686 
00687     switch (Class) {
00688     default: break;
00689 
00690     // Delete no-op casts. These function calls have special semantics, but
00691     // the semantics are entirely implemented via lowering in the front-end,
00692     // so by the time they reach the optimizer, they are just no-op calls
00693     // which return their argument.
00694     //
00695     // There are gray areas here, as the ability to cast reference-counted
00696     // pointers to raw void* and back allows code to break ARC assumptions,
00697     // however these are currently considered to be unimportant.
00698     case ARCInstKind::NoopCast:
00699       Changed = true;
00700       ++NumNoops;
00701       DEBUG(dbgs() << "Erasing no-op cast: " << *Inst << "\n");
00702       EraseInstruction(Inst);
00703       continue;
00704 
00705     // If the pointer-to-weak-pointer is null, it's undefined behavior.
00706     case ARCInstKind::StoreWeak:
00707     case ARCInstKind::LoadWeak:
00708     case ARCInstKind::LoadWeakRetained:
00709     case ARCInstKind::InitWeak:
00710     case ARCInstKind::DestroyWeak: {
00711       CallInst *CI = cast<CallInst>(Inst);
00712       if (IsNullOrUndef(CI->getArgOperand(0))) {
00713         Changed = true;
00714         Type *Ty = CI->getArgOperand(0)->getType();
00715         new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()),
00716                       Constant::getNullValue(Ty),
00717                       CI);
00718         llvm::Value *NewValue = UndefValue::get(CI->getType());
00719         DEBUG(dbgs() << "A null pointer-to-weak-pointer is undefined behavior."
00720                        "\nOld = " << *CI << "\nNew = " << *NewValue << "\n");
00721         CI->replaceAllUsesWith(NewValue);
00722         CI->eraseFromParent();
00723         continue;
00724       }
00725       break;
00726     }
00727     case ARCInstKind::CopyWeak:
00728     case ARCInstKind::MoveWeak: {
00729       CallInst *CI = cast<CallInst>(Inst);
00730       if (IsNullOrUndef(CI->getArgOperand(0)) ||
00731           IsNullOrUndef(CI->getArgOperand(1))) {
00732         Changed = true;
00733         Type *Ty = CI->getArgOperand(0)->getType();
00734         new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()),
00735                       Constant::getNullValue(Ty),
00736                       CI);
00737 
00738         llvm::Value *NewValue = UndefValue::get(CI->getType());
00739         DEBUG(dbgs() << "A null pointer-to-weak-pointer is undefined behavior."
00740                         "\nOld = " << *CI << "\nNew = " << *NewValue << "\n");
00741 
00742         CI->replaceAllUsesWith(NewValue);
00743         CI->eraseFromParent();
00744         continue;
00745       }
00746       break;
00747     }
00748     case ARCInstKind::RetainRV:
00749       if (OptimizeRetainRVCall(F, Inst))
00750         continue;
00751       break;
00752     case ARCInstKind::AutoreleaseRV:
00753       OptimizeAutoreleaseRVCall(F, Inst, Class);
00754       break;
00755     }
00756 
00757     // objc_autorelease(x) -> objc_release(x) if x is otherwise unused.
00758     if (IsAutorelease(Class) && Inst->use_empty()) {
00759       CallInst *Call = cast<CallInst>(Inst);
00760       const Value *Arg = Call->getArgOperand(0);
00761       Arg = FindSingleUseIdentifiedObject(Arg);
00762       if (Arg) {
00763         Changed = true;
00764         ++NumAutoreleases;
00765 
00766         // Create the declaration lazily.
00767         LLVMContext &C = Inst->getContext();
00768 
00769         Constant *Decl = EP.get(ARCRuntimeEntryPointKind::Release);
00770         CallInst *NewCall = CallInst::Create(Decl, Call->getArgOperand(0), "",
00771                                              Call);
00772         NewCall->setMetadata(MDKindCache.get(ARCMDKindID::ImpreciseRelease),
00773                              MDNode::get(C, None));
00774 
00775         DEBUG(dbgs() << "Replacing autorelease{,RV}(x) with objc_release(x) "
00776               "since x is otherwise unused.\nOld: " << *Call << "\nNew: "
00777               << *NewCall << "\n");
00778 
00779         EraseInstruction(Call);
00780         Inst = NewCall;
00781         Class = ARCInstKind::Release;
00782       }
00783     }
00784 
00785     // For functions which can never be passed stack arguments, add
00786     // a tail keyword.
00787     if (IsAlwaysTail(Class)) {
00788       Changed = true;
00789       DEBUG(dbgs() << "Adding tail keyword to function since it can never be "
00790                       "passed stack args: " << *Inst << "\n");
00791       cast<CallInst>(Inst)->setTailCall();
00792     }
00793 
00794     // Ensure that functions that can never have a "tail" keyword due to the
00795     // semantics of ARC truly do not do so.
00796     if (IsNeverTail(Class)) {
00797       Changed = true;
00798       DEBUG(dbgs() << "Removing tail keyword from function: " << *Inst <<
00799             "\n");
00800       cast<CallInst>(Inst)->setTailCall(false);
00801     }
00802 
00803     // Set nounwind as needed.
00804     if (IsNoThrow(Class)) {
00805       Changed = true;
00806       DEBUG(dbgs() << "Found no throw class. Setting nounwind on: " << *Inst
00807                    << "\n");
00808       cast<CallInst>(Inst)->setDoesNotThrow();
00809     }
00810 
00811     if (!IsNoopOnNull(Class)) {
00812       UsedInThisFunction |= 1 << unsigned(Class);
00813       continue;
00814     }
00815 
00816     const Value *Arg = GetArgRCIdentityRoot(Inst);
00817 
00818     // ARC calls with null are no-ops. Delete them.
00819     if (IsNullOrUndef(Arg)) {
00820       Changed = true;
00821       ++NumNoops;
00822       DEBUG(dbgs() << "ARC calls with  null are no-ops. Erasing: " << *Inst
00823             << "\n");
00824       EraseInstruction(Inst);
00825       continue;
00826     }
00827 
00828     // Keep track of which of retain, release, autorelease, and retain_block
00829     // are actually present in this function.
00830     UsedInThisFunction |= 1 << unsigned(Class);
00831 
00832     // If Arg is a PHI, and one or more incoming values to the
00833     // PHI are null, and the call is control-equivalent to the PHI, and there
00834     // are no relevant side effects between the PHI and the call, the call
00835     // could be pushed up to just those paths with non-null incoming values.
00836     // For now, don't bother splitting critical edges for this.
00837     SmallVector<std::pair<Instruction *, const Value *>, 4> Worklist;
00838     Worklist.push_back(std::make_pair(Inst, Arg));
00839     do {
00840       std::pair<Instruction *, const Value *> Pair = Worklist.pop_back_val();
00841       Inst = Pair.first;
00842       Arg = Pair.second;
00843 
00844       const PHINode *PN = dyn_cast<PHINode>(Arg);
00845       if (!PN) continue;
00846 
00847       // Determine if the PHI has any null operands, or any incoming
00848       // critical edges.
00849       bool HasNull = false;
00850       bool HasCriticalEdges = false;
00851       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
00852         Value *Incoming =
00853           GetRCIdentityRoot(PN->getIncomingValue(i));
00854         if (IsNullOrUndef(Incoming))
00855           HasNull = true;
00856         else if (cast<TerminatorInst>(PN->getIncomingBlock(i)->back())
00857                    .getNumSuccessors() != 1) {
00858           HasCriticalEdges = true;
00859           break;
00860         }
00861       }
00862       // If we have null operands and no critical edges, optimize.
00863       if (!HasCriticalEdges && HasNull) {
00864         SmallPtrSet<Instruction *, 4> DependingInstructions;
00865         SmallPtrSet<const BasicBlock *, 4> Visited;
00866 
00867         // Check that there is nothing that cares about the reference
00868         // count between the call and the phi.
00869         switch (Class) {
00870         case ARCInstKind::Retain:
00871         case ARCInstKind::RetainBlock:
00872           // These can always be moved up.
00873           break;
00874         case ARCInstKind::Release:
00875           // These can't be moved across things that care about the retain
00876           // count.
00877           FindDependencies(NeedsPositiveRetainCount, Arg,
00878                            Inst->getParent(), Inst,
00879                            DependingInstructions, Visited, PA);
00880           break;
00881         case ARCInstKind::Autorelease:
00882           // These can't be moved across autorelease pool scope boundaries.
00883           FindDependencies(AutoreleasePoolBoundary, Arg,
00884                            Inst->getParent(), Inst,
00885                            DependingInstructions, Visited, PA);
00886           break;
00887         case ARCInstKind::RetainRV:
00888         case ARCInstKind::AutoreleaseRV:
00889           // Don't move these; the RV optimization depends on the autoreleaseRV
00890           // being tail called, and the retainRV being immediately after a call
00891           // (which might still happen if we get lucky with codegen layout, but
00892           // it's not worth taking the chance).
00893           continue;
00894         default:
00895           llvm_unreachable("Invalid dependence flavor");
00896         }
00897 
00898         if (DependingInstructions.size() == 1 &&
00899             *DependingInstructions.begin() == PN) {
00900           Changed = true;
00901           ++NumPartialNoops;
00902           // Clone the call into each predecessor that has a non-null value.
00903           CallInst *CInst = cast<CallInst>(Inst);
00904           Type *ParamTy = CInst->getArgOperand(0)->getType();
00905           for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
00906             Value *Incoming =
00907               GetRCIdentityRoot(PN->getIncomingValue(i));
00908             if (!IsNullOrUndef(Incoming)) {
00909               CallInst *Clone = cast<CallInst>(CInst->clone());
00910               Value *Op = PN->getIncomingValue(i);
00911               Instruction *InsertPos = &PN->getIncomingBlock(i)->back();
00912               if (Op->getType() != ParamTy)
00913                 Op = new BitCastInst(Op, ParamTy, "", InsertPos);
00914               Clone->setArgOperand(0, Op);
00915               Clone->insertBefore(InsertPos);
00916 
00917               DEBUG(dbgs() << "Cloning "
00918                            << *CInst << "\n"
00919                            "And inserting clone at " << *InsertPos << "\n");
00920               Worklist.push_back(std::make_pair(Clone, Incoming));
00921             }
00922           }
00923           // Erase the original call.
00924           DEBUG(dbgs() << "Erasing: " << *CInst << "\n");
00925           EraseInstruction(CInst);
00926           continue;
00927         }
00928       }
00929     } while (!Worklist.empty());
00930   }
00931 }
00932 
00933 /// If we have a top down pointer in the S_Use state, make sure that there are
00934 /// no CFG hazards by checking the states of various bottom up pointers.
00935 static void CheckForUseCFGHazard(const Sequence SuccSSeq,
00936                                  const bool SuccSRRIKnownSafe,
00937                                  TopDownPtrState &S,
00938                                  bool &SomeSuccHasSame,
00939                                  bool &AllSuccsHaveSame,
00940                                  bool &NotAllSeqEqualButKnownSafe,
00941                                  bool &ShouldContinue) {
00942   switch (SuccSSeq) {
00943   case S_CanRelease: {
00944     if (!S.IsKnownSafe() && !SuccSRRIKnownSafe) {
00945       S.ClearSequenceProgress();
00946       break;
00947     }
00948     S.SetCFGHazardAfflicted(true);
00949     ShouldContinue = true;
00950     break;
00951   }
00952   case S_Use:
00953     SomeSuccHasSame = true;
00954     break;
00955   case S_Stop:
00956   case S_Release:
00957   case S_MovableRelease:
00958     if (!S.IsKnownSafe() && !SuccSRRIKnownSafe)
00959       AllSuccsHaveSame = false;
00960     else
00961       NotAllSeqEqualButKnownSafe = true;
00962     break;
00963   case S_Retain:
00964     llvm_unreachable("bottom-up pointer in retain state!");
00965   case S_None:
00966     llvm_unreachable("This should have been handled earlier.");
00967   }
00968 }
00969 
00970 /// If we have a Top Down pointer in the S_CanRelease state, make sure that
00971 /// there are no CFG hazards by checking the states of various bottom up
00972 /// pointers.
00973 static void CheckForCanReleaseCFGHazard(const Sequence SuccSSeq,
00974                                         const bool SuccSRRIKnownSafe,
00975                                         TopDownPtrState &S,
00976                                         bool &SomeSuccHasSame,
00977                                         bool &AllSuccsHaveSame,
00978                                         bool &NotAllSeqEqualButKnownSafe) {
00979   switch (SuccSSeq) {
00980   case S_CanRelease:
00981     SomeSuccHasSame = true;
00982     break;
00983   case S_Stop:
00984   case S_Release:
00985   case S_MovableRelease:
00986   case S_Use:
00987     if (!S.IsKnownSafe() && !SuccSRRIKnownSafe)
00988       AllSuccsHaveSame = false;
00989     else
00990       NotAllSeqEqualButKnownSafe = true;
00991     break;
00992   case S_Retain:
00993     llvm_unreachable("bottom-up pointer in retain state!");
00994   case S_None:
00995     llvm_unreachable("This should have been handled earlier.");
00996   }
00997 }
00998 
00999 /// Check for critical edges, loop boundaries, irreducible control flow, or
01000 /// other CFG structures where moving code across the edge would result in it
01001 /// being executed more.
01002 void
01003 ObjCARCOpt::CheckForCFGHazards(const BasicBlock *BB,
01004                                DenseMap<const BasicBlock *, BBState> &BBStates,
01005                                BBState &MyStates) const {
01006   // If any top-down local-use or possible-dec has a succ which is earlier in
01007   // the sequence, forget it.
01008   for (auto I = MyStates.top_down_ptr_begin(), E = MyStates.top_down_ptr_end();
01009        I != E; ++I) {
01010     TopDownPtrState &S = I->second;
01011     const Sequence Seq = I->second.GetSeq();
01012 
01013     // We only care about S_Retain, S_CanRelease, and S_Use.
01014     if (Seq == S_None)
01015       continue;
01016 
01017     // Make sure that if extra top down states are added in the future that this
01018     // code is updated to handle it.
01019     assert((Seq == S_Retain || Seq == S_CanRelease || Seq == S_Use) &&
01020            "Unknown top down sequence state.");
01021 
01022     const Value *Arg = I->first;
01023     const TerminatorInst *TI = cast<TerminatorInst>(&BB->back());
01024     bool SomeSuccHasSame = false;
01025     bool AllSuccsHaveSame = true;
01026     bool NotAllSeqEqualButKnownSafe = false;
01027 
01028     succ_const_iterator SI(TI), SE(TI, false);
01029 
01030     for (; SI != SE; ++SI) {
01031       // If VisitBottomUp has pointer information for this successor, take
01032       // what we know about it.
01033       const DenseMap<const BasicBlock *, BBState>::iterator BBI =
01034         BBStates.find(*SI);
01035       assert(BBI != BBStates.end());
01036       const BottomUpPtrState &SuccS = BBI->second.getPtrBottomUpState(Arg);
01037       const Sequence SuccSSeq = SuccS.GetSeq();
01038 
01039       // If bottom up, the pointer is in an S_None state, clear the sequence
01040       // progress since the sequence in the bottom up state finished
01041       // suggesting a mismatch in between retains/releases. This is true for
01042       // all three cases that we are handling here: S_Retain, S_Use, and
01043       // S_CanRelease.
01044       if (SuccSSeq == S_None) {
01045         S.ClearSequenceProgress();
01046         continue;
01047       }
01048 
01049       // If we have S_Use or S_CanRelease, perform our check for cfg hazard
01050       // checks.
01051       const bool SuccSRRIKnownSafe = SuccS.IsKnownSafe();
01052 
01053       // *NOTE* We do not use Seq from above here since we are allowing for
01054       // S.GetSeq() to change while we are visiting basic blocks.
01055       switch(S.GetSeq()) {
01056       case S_Use: {
01057         bool ShouldContinue = false;
01058         CheckForUseCFGHazard(SuccSSeq, SuccSRRIKnownSafe, S, SomeSuccHasSame,
01059                              AllSuccsHaveSame, NotAllSeqEqualButKnownSafe,
01060                              ShouldContinue);
01061         if (ShouldContinue)
01062           continue;
01063         break;
01064       }
01065       case S_CanRelease: {
01066         CheckForCanReleaseCFGHazard(SuccSSeq, SuccSRRIKnownSafe, S,
01067                                     SomeSuccHasSame, AllSuccsHaveSame,
01068                                     NotAllSeqEqualButKnownSafe);
01069         break;
01070       }
01071       case S_Retain:
01072       case S_None:
01073       case S_Stop:
01074       case S_Release:
01075       case S_MovableRelease:
01076         break;
01077       }
01078     }
01079 
01080     // If the state at the other end of any of the successor edges
01081     // matches the current state, require all edges to match. This
01082     // guards against loops in the middle of a sequence.
01083     if (SomeSuccHasSame && !AllSuccsHaveSame) {
01084       S.ClearSequenceProgress();
01085     } else if (NotAllSeqEqualButKnownSafe) {
01086       // If we would have cleared the state foregoing the fact that we are known
01087       // safe, stop code motion. This is because whether or not it is safe to
01088       // remove RR pairs via KnownSafe is an orthogonal concept to whether we
01089       // are allowed to perform code motion.
01090       S.SetCFGHazardAfflicted(true);
01091     }
01092   }
01093 }
01094 
01095 bool ObjCARCOpt::VisitInstructionBottomUp(
01096     Instruction *Inst, BasicBlock *BB, BlotMapVector<Value *, RRInfo> &Retains,
01097     BBState &MyStates) {
01098   bool NestingDetected = false;
01099   ARCInstKind Class = GetARCInstKind(Inst);
01100   const Value *Arg = nullptr;
01101 
01102   DEBUG(dbgs() << "        Class: " << Class << "\n");
01103 
01104   switch (Class) {
01105   case ARCInstKind::Release: {
01106     Arg = GetArgRCIdentityRoot(Inst);
01107 
01108     BottomUpPtrState &S = MyStates.getPtrBottomUpState(Arg);
01109     NestingDetected |= S.InitBottomUp(MDKindCache, Inst);
01110     break;
01111   }
01112   case ARCInstKind::RetainBlock:
01113     // In OptimizeIndividualCalls, we have strength reduced all optimizable
01114     // objc_retainBlocks to objc_retains. Thus at this point any
01115     // objc_retainBlocks that we see are not optimizable.
01116     break;
01117   case ARCInstKind::Retain:
01118   case ARCInstKind::RetainRV: {
01119     Arg = GetArgRCIdentityRoot(Inst);
01120     BottomUpPtrState &S = MyStates.getPtrBottomUpState(Arg);
01121     if (S.MatchWithRetain()) {
01122       // Don't do retain+release tracking for ARCInstKind::RetainRV, because
01123       // it's better to let it remain as the first instruction after a call.
01124       if (Class != ARCInstKind::RetainRV) {
01125         DEBUG(llvm::dbgs() << "        Matching with: " << *Inst << "\n");
01126         Retains[Inst] = S.GetRRInfo();
01127       }
01128       S.ClearSequenceProgress();
01129     }
01130     // A retain moving bottom up can be a use.
01131     break;
01132   }
01133   case ARCInstKind::AutoreleasepoolPop:
01134     // Conservatively, clear MyStates for all known pointers.
01135     MyStates.clearBottomUpPointers();
01136     return NestingDetected;
01137   case ARCInstKind::AutoreleasepoolPush:
01138   case ARCInstKind::None:
01139     // These are irrelevant.
01140     return NestingDetected;
01141   case ARCInstKind::User:
01142     // If we have a store into an alloca of a pointer we are tracking, the
01143     // pointer has multiple owners implying that we must be more conservative.
01144     //
01145     // This comes up in the context of a pointer being ``KnownSafe''. In the
01146     // presence of a block being initialized, the frontend will emit the
01147     // objc_retain on the original pointer and the release on the pointer loaded
01148     // from the alloca. The optimizer will through the provenance analysis
01149     // realize that the two are related, but since we only require KnownSafe in
01150     // one direction, will match the inner retain on the original pointer with
01151     // the guard release on the original pointer. This is fixed by ensuring that
01152     // in the presence of allocas we only unconditionally remove pointers if
01153     // both our retain and our release are KnownSafe.
01154     if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
01155       const DataLayout &DL = BB->getModule()->getDataLayout();
01156       if (AreAnyUnderlyingObjectsAnAlloca(SI->getPointerOperand(), DL)) {
01157         auto I = MyStates.findPtrBottomUpState(
01158             GetRCIdentityRoot(SI->getValueOperand()));
01159         if (I != MyStates.bottom_up_ptr_end())
01160           MultiOwnersSet.insert(I->first);
01161       }
01162     }
01163     break;
01164   default:
01165     break;
01166   }
01167 
01168   // Consider any other possible effects of this instruction on each
01169   // pointer being tracked.
01170   for (auto MI = MyStates.bottom_up_ptr_begin(),
01171             ME = MyStates.bottom_up_ptr_end();
01172        MI != ME; ++MI) {
01173     const Value *Ptr = MI->first;
01174     if (Ptr == Arg)
01175       continue; // Handled above.
01176     BottomUpPtrState &S = MI->second;
01177 
01178     if (S.HandlePotentialAlterRefCount(Inst, Ptr, PA, Class))
01179       continue;
01180 
01181     S.HandlePotentialUse(BB, Inst, Ptr, PA, Class);
01182   }
01183 
01184   return NestingDetected;
01185 }
01186 
01187 bool ObjCARCOpt::VisitBottomUp(BasicBlock *BB,
01188                                DenseMap<const BasicBlock *, BBState> &BBStates,
01189                                BlotMapVector<Value *, RRInfo> &Retains) {
01190 
01191   DEBUG(dbgs() << "\n== ObjCARCOpt::VisitBottomUp ==\n");
01192 
01193   bool NestingDetected = false;
01194   BBState &MyStates = BBStates[BB];
01195 
01196   // Merge the states from each successor to compute the initial state
01197   // for the current block.
01198   BBState::edge_iterator SI(MyStates.succ_begin()),
01199                          SE(MyStates.succ_end());
01200   if (SI != SE) {
01201     const BasicBlock *Succ = *SI;
01202     DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Succ);
01203     assert(I != BBStates.end());
01204     MyStates.InitFromSucc(I->second);
01205     ++SI;
01206     for (; SI != SE; ++SI) {
01207       Succ = *SI;
01208       I = BBStates.find(Succ);
01209       assert(I != BBStates.end());
01210       MyStates.MergeSucc(I->second);
01211     }
01212   }
01213 
01214   DEBUG(llvm::dbgs() << "Before:\n" << BBStates[BB] << "\n"
01215                      << "Performing Dataflow:\n");
01216 
01217   // Visit all the instructions, bottom-up.
01218   for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; --I) {
01219     Instruction *Inst = std::prev(I);
01220 
01221     // Invoke instructions are visited as part of their successors (below).
01222     if (isa<InvokeInst>(Inst))
01223       continue;
01224 
01225     DEBUG(dbgs() << "    Visiting " << *Inst << "\n");
01226 
01227     NestingDetected |= VisitInstructionBottomUp(Inst, BB, Retains, MyStates);
01228   }
01229 
01230   // If there's a predecessor with an invoke, visit the invoke as if it were
01231   // part of this block, since we can't insert code after an invoke in its own
01232   // block, and we don't want to split critical edges.
01233   for (BBState::edge_iterator PI(MyStates.pred_begin()),
01234        PE(MyStates.pred_end()); PI != PE; ++PI) {
01235     BasicBlock *Pred = *PI;
01236     if (InvokeInst *II = dyn_cast<InvokeInst>(&Pred->back()))
01237       NestingDetected |= VisitInstructionBottomUp(II, BB, Retains, MyStates);
01238   }
01239 
01240   DEBUG(llvm::dbgs() << "\nFinal State:\n" << BBStates[BB] << "\n");
01241 
01242   return NestingDetected;
01243 }
01244 
01245 bool
01246 ObjCARCOpt::VisitInstructionTopDown(Instruction *Inst,
01247                                     DenseMap<Value *, RRInfo> &Releases,
01248                                     BBState &MyStates) {
01249   bool NestingDetected = false;
01250   ARCInstKind Class = GetARCInstKind(Inst);
01251   const Value *Arg = nullptr;
01252 
01253   DEBUG(llvm::dbgs() << "        Class: " << Class << "\n");
01254 
01255   switch (Class) {
01256   case ARCInstKind::RetainBlock:
01257     // In OptimizeIndividualCalls, we have strength reduced all optimizable
01258     // objc_retainBlocks to objc_retains. Thus at this point any
01259     // objc_retainBlocks that we see are not optimizable. We need to break since
01260     // a retain can be a potential use.
01261     break;
01262   case ARCInstKind::Retain:
01263   case ARCInstKind::RetainRV: {
01264     Arg = GetArgRCIdentityRoot(Inst);
01265     TopDownPtrState &S = MyStates.getPtrTopDownState(Arg);
01266     NestingDetected |= S.InitTopDown(Class, Inst);
01267     // A retain can be a potential use; procede to the generic checking
01268     // code below.
01269     break;
01270   }
01271   case ARCInstKind::Release: {
01272     Arg = GetArgRCIdentityRoot(Inst);
01273     TopDownPtrState &S = MyStates.getPtrTopDownState(Arg);
01274     // Try to form a tentative pair in between this release instruction and the
01275     // top down pointers that we are tracking.
01276     if (S.MatchWithRelease(MDKindCache, Inst)) {
01277       // If we succeed, copy S's RRInfo into the Release -> {Retain Set
01278       // Map}. Then we clear S.
01279       DEBUG(llvm::dbgs() << "        Matching with: " << *Inst << "\n");
01280       Releases[Inst] = S.GetRRInfo();
01281       S.ClearSequenceProgress();
01282     }
01283     break;
01284   }
01285   case ARCInstKind::AutoreleasepoolPop:
01286     // Conservatively, clear MyStates for all known pointers.
01287     MyStates.clearTopDownPointers();
01288     return false;
01289   case ARCInstKind::AutoreleasepoolPush:
01290   case ARCInstKind::None:
01291     // These can not be uses of
01292     return false;
01293   default:
01294     break;
01295   }
01296 
01297   // Consider any other possible effects of this instruction on each
01298   // pointer being tracked.
01299   for (auto MI = MyStates.top_down_ptr_begin(),
01300             ME = MyStates.top_down_ptr_end();
01301        MI != ME; ++MI) {
01302     const Value *Ptr = MI->first;
01303     if (Ptr == Arg)
01304       continue; // Handled above.
01305     TopDownPtrState &S = MI->second;
01306     if (S.HandlePotentialAlterRefCount(Inst, Ptr, PA, Class))
01307       continue;
01308 
01309     S.HandlePotentialUse(Inst, Ptr, PA, Class);
01310   }
01311 
01312   return NestingDetected;
01313 }
01314 
01315 bool
01316 ObjCARCOpt::VisitTopDown(BasicBlock *BB,
01317                          DenseMap<const BasicBlock *, BBState> &BBStates,
01318                          DenseMap<Value *, RRInfo> &Releases) {
01319   DEBUG(dbgs() << "\n== ObjCARCOpt::VisitTopDown ==\n");
01320   bool NestingDetected = false;
01321   BBState &MyStates = BBStates[BB];
01322 
01323   // Merge the states from each predecessor to compute the initial state
01324   // for the current block.
01325   BBState::edge_iterator PI(MyStates.pred_begin()),
01326                          PE(MyStates.pred_end());
01327   if (PI != PE) {
01328     const BasicBlock *Pred = *PI;
01329     DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Pred);
01330     assert(I != BBStates.end());
01331     MyStates.InitFromPred(I->second);
01332     ++PI;
01333     for (; PI != PE; ++PI) {
01334       Pred = *PI;
01335       I = BBStates.find(Pred);
01336       assert(I != BBStates.end());
01337       MyStates.MergePred(I->second);
01338     }
01339   }
01340 
01341   DEBUG(llvm::dbgs() << "Before:\n" << BBStates[BB]  << "\n"
01342                      << "Performing Dataflow:\n");
01343 
01344   // Visit all the instructions, top-down.
01345   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
01346     Instruction *Inst = I;
01347 
01348     DEBUG(dbgs() << "    Visiting " << *Inst << "\n");
01349 
01350     NestingDetected |= VisitInstructionTopDown(Inst, Releases, MyStates);
01351   }
01352 
01353   DEBUG(llvm::dbgs() << "\nState Before Checking for CFG Hazards:\n"
01354                      << BBStates[BB] << "\n\n");
01355   CheckForCFGHazards(BB, BBStates, MyStates);
01356   DEBUG(llvm::dbgs() << "Final State:\n" << BBStates[BB] << "\n");
01357   return NestingDetected;
01358 }
01359 
01360 static void
01361 ComputePostOrders(Function &F,
01362                   SmallVectorImpl<BasicBlock *> &PostOrder,
01363                   SmallVectorImpl<BasicBlock *> &ReverseCFGPostOrder,
01364                   unsigned NoObjCARCExceptionsMDKind,
01365                   DenseMap<const BasicBlock *, BBState> &BBStates) {
01366   /// The visited set, for doing DFS walks.
01367   SmallPtrSet<BasicBlock *, 16> Visited;
01368 
01369   // Do DFS, computing the PostOrder.
01370   SmallPtrSet<BasicBlock *, 16> OnStack;
01371   SmallVector<std::pair<BasicBlock *, succ_iterator>, 16> SuccStack;
01372 
01373   // Functions always have exactly one entry block, and we don't have
01374   // any other block that we treat like an entry block.
01375   BasicBlock *EntryBB = &F.getEntryBlock();
01376   BBState &MyStates = BBStates[EntryBB];
01377   MyStates.SetAsEntry();
01378   TerminatorInst *EntryTI = cast<TerminatorInst>(&EntryBB->back());
01379   SuccStack.push_back(std::make_pair(EntryBB, succ_iterator(EntryTI)));
01380   Visited.insert(EntryBB);
01381   OnStack.insert(EntryBB);
01382   do {
01383   dfs_next_succ:
01384     BasicBlock *CurrBB = SuccStack.back().first;
01385     TerminatorInst *TI = cast<TerminatorInst>(&CurrBB->back());
01386     succ_iterator SE(TI, false);
01387 
01388     while (SuccStack.back().second != SE) {
01389       BasicBlock *SuccBB = *SuccStack.back().second++;
01390       if (Visited.insert(SuccBB).second) {
01391         TerminatorInst *TI = cast<TerminatorInst>(&SuccBB->back());
01392         SuccStack.push_back(std::make_pair(SuccBB, succ_iterator(TI)));
01393         BBStates[CurrBB].addSucc(SuccBB);
01394         BBState &SuccStates = BBStates[SuccBB];
01395         SuccStates.addPred(CurrBB);
01396         OnStack.insert(SuccBB);
01397         goto dfs_next_succ;
01398       }
01399 
01400       if (!OnStack.count(SuccBB)) {
01401         BBStates[CurrBB].addSucc(SuccBB);
01402         BBStates[SuccBB].addPred(CurrBB);
01403       }
01404     }
01405     OnStack.erase(CurrBB);
01406     PostOrder.push_back(CurrBB);
01407     SuccStack.pop_back();
01408   } while (!SuccStack.empty());
01409 
01410   Visited.clear();
01411 
01412   // Do reverse-CFG DFS, computing the reverse-CFG PostOrder.
01413   // Functions may have many exits, and there also blocks which we treat
01414   // as exits due to ignored edges.
01415   SmallVector<std::pair<BasicBlock *, BBState::edge_iterator>, 16> PredStack;
01416   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
01417     BasicBlock *ExitBB = I;
01418     BBState &MyStates = BBStates[ExitBB];
01419     if (!MyStates.isExit())
01420       continue;
01421 
01422     MyStates.SetAsExit();
01423 
01424     PredStack.push_back(std::make_pair(ExitBB, MyStates.pred_begin()));
01425     Visited.insert(ExitBB);
01426     while (!PredStack.empty()) {
01427     reverse_dfs_next_succ:
01428       BBState::edge_iterator PE = BBStates[PredStack.back().first].pred_end();
01429       while (PredStack.back().second != PE) {
01430         BasicBlock *BB = *PredStack.back().second++;
01431         if (Visited.insert(BB).second) {
01432           PredStack.push_back(std::make_pair(BB, BBStates[BB].pred_begin()));
01433           goto reverse_dfs_next_succ;
01434         }
01435       }
01436       ReverseCFGPostOrder.push_back(PredStack.pop_back_val().first);
01437     }
01438   }
01439 }
01440 
01441 // Visit the function both top-down and bottom-up.
01442 bool ObjCARCOpt::Visit(Function &F,
01443                        DenseMap<const BasicBlock *, BBState> &BBStates,
01444                        BlotMapVector<Value *, RRInfo> &Retains,
01445                        DenseMap<Value *, RRInfo> &Releases) {
01446 
01447   // Use reverse-postorder traversals, because we magically know that loops
01448   // will be well behaved, i.e. they won't repeatedly call retain on a single
01449   // pointer without doing a release. We can't use the ReversePostOrderTraversal
01450   // class here because we want the reverse-CFG postorder to consider each
01451   // function exit point, and we want to ignore selected cycle edges.
01452   SmallVector<BasicBlock *, 16> PostOrder;
01453   SmallVector<BasicBlock *, 16> ReverseCFGPostOrder;
01454   ComputePostOrders(F, PostOrder, ReverseCFGPostOrder,
01455                     MDKindCache.get(ARCMDKindID::NoObjCARCExceptions),
01456                     BBStates);
01457 
01458   // Use reverse-postorder on the reverse CFG for bottom-up.
01459   bool BottomUpNestingDetected = false;
01460   for (SmallVectorImpl<BasicBlock *>::const_reverse_iterator I =
01461        ReverseCFGPostOrder.rbegin(), E = ReverseCFGPostOrder.rend();
01462        I != E; ++I)
01463     BottomUpNestingDetected |= VisitBottomUp(*I, BBStates, Retains);
01464 
01465   // Use reverse-postorder for top-down.
01466   bool TopDownNestingDetected = false;
01467   for (SmallVectorImpl<BasicBlock *>::const_reverse_iterator I =
01468        PostOrder.rbegin(), E = PostOrder.rend();
01469        I != E; ++I)
01470     TopDownNestingDetected |= VisitTopDown(*I, BBStates, Releases);
01471 
01472   return TopDownNestingDetected && BottomUpNestingDetected;
01473 }
01474 
01475 /// Move the calls in RetainsToMove and ReleasesToMove.
01476 void ObjCARCOpt::MoveCalls(Value *Arg, RRInfo &RetainsToMove,
01477                            RRInfo &ReleasesToMove,
01478                            BlotMapVector<Value *, RRInfo> &Retains,
01479                            DenseMap<Value *, RRInfo> &Releases,
01480                            SmallVectorImpl<Instruction *> &DeadInsts,
01481                            Module *M) {
01482   Type *ArgTy = Arg->getType();
01483   Type *ParamTy = PointerType::getUnqual(Type::getInt8Ty(ArgTy->getContext()));
01484 
01485   DEBUG(dbgs() << "== ObjCARCOpt::MoveCalls ==\n");
01486 
01487   // Insert the new retain and release calls.
01488   for (Instruction *InsertPt : ReleasesToMove.ReverseInsertPts) {
01489     Value *MyArg = ArgTy == ParamTy ? Arg :
01490                    new BitCastInst(Arg, ParamTy, "", InsertPt);
01491     Constant *Decl = EP.get(ARCRuntimeEntryPointKind::Retain);
01492     CallInst *Call = CallInst::Create(Decl, MyArg, "", InsertPt);
01493     Call->setDoesNotThrow();
01494     Call->setTailCall();
01495 
01496     DEBUG(dbgs() << "Inserting new Retain: " << *Call << "\n"
01497                     "At insertion point: " << *InsertPt << "\n");
01498   }
01499   for (Instruction *InsertPt : RetainsToMove.ReverseInsertPts) {
01500     Value *MyArg = ArgTy == ParamTy ? Arg :
01501                    new BitCastInst(Arg, ParamTy, "", InsertPt);
01502     Constant *Decl = EP.get(ARCRuntimeEntryPointKind::Release);
01503     CallInst *Call = CallInst::Create(Decl, MyArg, "", InsertPt);
01504     // Attach a clang.imprecise_release metadata tag, if appropriate.
01505     if (MDNode *M = ReleasesToMove.ReleaseMetadata)
01506       Call->setMetadata(MDKindCache.get(ARCMDKindID::ImpreciseRelease), M);
01507     Call->setDoesNotThrow();
01508     if (ReleasesToMove.IsTailCallRelease)
01509       Call->setTailCall();
01510 
01511     DEBUG(dbgs() << "Inserting new Release: " << *Call << "\n"
01512                     "At insertion point: " << *InsertPt << "\n");
01513   }
01514 
01515   // Delete the original retain and release calls.
01516   for (Instruction *OrigRetain : RetainsToMove.Calls) {
01517     Retains.blot(OrigRetain);
01518     DeadInsts.push_back(OrigRetain);
01519     DEBUG(dbgs() << "Deleting retain: " << *OrigRetain << "\n");
01520   }
01521   for (Instruction *OrigRelease : ReleasesToMove.Calls) {
01522     Releases.erase(OrigRelease);
01523     DeadInsts.push_back(OrigRelease);
01524     DEBUG(dbgs() << "Deleting release: " << *OrigRelease << "\n");
01525   }
01526 
01527 }
01528 
01529 bool ObjCARCOpt::PairUpRetainsAndReleases(
01530     DenseMap<const BasicBlock *, BBState> &BBStates,
01531     BlotMapVector<Value *, RRInfo> &Retains,
01532     DenseMap<Value *, RRInfo> &Releases, Module *M,
01533     SmallVectorImpl<Instruction *> &NewRetains,
01534     SmallVectorImpl<Instruction *> &NewReleases,
01535     SmallVectorImpl<Instruction *> &DeadInsts, RRInfo &RetainsToMove,
01536     RRInfo &ReleasesToMove, Value *Arg, bool KnownSafe,
01537     bool &AnyPairsCompletelyEliminated) {
01538   // If a pair happens in a region where it is known that the reference count
01539   // is already incremented, we can similarly ignore possible decrements unless
01540   // we are dealing with a retainable object with multiple provenance sources.
01541   bool KnownSafeTD = true, KnownSafeBU = true;
01542   bool MultipleOwners = false;
01543   bool CFGHazardAfflicted = false;
01544 
01545   // Connect the dots between the top-down-collected RetainsToMove and
01546   // bottom-up-collected ReleasesToMove to form sets of related calls.
01547   // This is an iterative process so that we connect multiple releases
01548   // to multiple retains if needed.
01549   unsigned OldDelta = 0;
01550   unsigned NewDelta = 0;
01551   unsigned OldCount = 0;
01552   unsigned NewCount = 0;
01553   bool FirstRelease = true;
01554   for (;;) {
01555     for (SmallVectorImpl<Instruction *>::const_iterator
01556            NI = NewRetains.begin(), NE = NewRetains.end(); NI != NE; ++NI) {
01557       Instruction *NewRetain = *NI;
01558       auto It = Retains.find(NewRetain);
01559       assert(It != Retains.end());
01560       const RRInfo &NewRetainRRI = It->second;
01561       KnownSafeTD &= NewRetainRRI.KnownSafe;
01562       MultipleOwners =
01563         MultipleOwners || MultiOwnersSet.count(GetArgRCIdentityRoot(NewRetain));
01564       for (Instruction *NewRetainRelease : NewRetainRRI.Calls) {
01565         auto Jt = Releases.find(NewRetainRelease);
01566         if (Jt == Releases.end())
01567           return false;
01568         const RRInfo &NewRetainReleaseRRI = Jt->second;
01569 
01570         // If the release does not have a reference to the retain as well,
01571         // something happened which is unaccounted for. Do not do anything.
01572         //
01573         // This can happen if we catch an additive overflow during path count
01574         // merging.
01575         if (!NewRetainReleaseRRI.Calls.count(NewRetain))
01576           return false;
01577 
01578         if (ReleasesToMove.Calls.insert(NewRetainRelease).second) {
01579 
01580           // If we overflow when we compute the path count, don't remove/move
01581           // anything.
01582           const BBState &NRRBBState = BBStates[NewRetainRelease->getParent()];
01583           unsigned PathCount = BBState::OverflowOccurredValue;
01584           if (NRRBBState.GetAllPathCountWithOverflow(PathCount))
01585             return false;
01586           assert(PathCount != BBState::OverflowOccurredValue &&
01587                  "PathCount at this point can not be "
01588                  "OverflowOccurredValue.");
01589           OldDelta -= PathCount;
01590 
01591           // Merge the ReleaseMetadata and IsTailCallRelease values.
01592           if (FirstRelease) {
01593             ReleasesToMove.ReleaseMetadata =
01594               NewRetainReleaseRRI.ReleaseMetadata;
01595             ReleasesToMove.IsTailCallRelease =
01596               NewRetainReleaseRRI.IsTailCallRelease;
01597             FirstRelease = false;
01598           } else {
01599             if (ReleasesToMove.ReleaseMetadata !=
01600                 NewRetainReleaseRRI.ReleaseMetadata)
01601               ReleasesToMove.ReleaseMetadata = nullptr;
01602             if (ReleasesToMove.IsTailCallRelease !=
01603                 NewRetainReleaseRRI.IsTailCallRelease)
01604               ReleasesToMove.IsTailCallRelease = false;
01605           }
01606 
01607           // Collect the optimal insertion points.
01608           if (!KnownSafe)
01609             for (Instruction *RIP : NewRetainReleaseRRI.ReverseInsertPts) {
01610               if (ReleasesToMove.ReverseInsertPts.insert(RIP).second) {
01611                 // If we overflow when we compute the path count, don't
01612                 // remove/move anything.
01613                 const BBState &RIPBBState = BBStates[RIP->getParent()];
01614                 PathCount = BBState::OverflowOccurredValue;
01615                 if (RIPBBState.GetAllPathCountWithOverflow(PathCount))
01616                   return false;
01617                 assert(PathCount != BBState::OverflowOccurredValue &&
01618                        "PathCount at this point can not be "
01619                        "OverflowOccurredValue.");
01620                 NewDelta -= PathCount;
01621               }
01622             }
01623           NewReleases.push_back(NewRetainRelease);
01624         }
01625       }
01626     }
01627     NewRetains.clear();
01628     if (NewReleases.empty()) break;
01629 
01630     // Back the other way.
01631     for (SmallVectorImpl<Instruction *>::const_iterator
01632            NI = NewReleases.begin(), NE = NewReleases.end(); NI != NE; ++NI) {
01633       Instruction *NewRelease = *NI;
01634       auto It = Releases.find(NewRelease);
01635       assert(It != Releases.end());
01636       const RRInfo &NewReleaseRRI = It->second;
01637       KnownSafeBU &= NewReleaseRRI.KnownSafe;
01638       CFGHazardAfflicted |= NewReleaseRRI.CFGHazardAfflicted;
01639       for (Instruction *NewReleaseRetain : NewReleaseRRI.Calls) {
01640         auto Jt = Retains.find(NewReleaseRetain);
01641         if (Jt == Retains.end())
01642           return false;
01643         const RRInfo &NewReleaseRetainRRI = Jt->second;
01644 
01645         // If the retain does not have a reference to the release as well,
01646         // something happened which is unaccounted for. Do not do anything.
01647         //
01648         // This can happen if we catch an additive overflow during path count
01649         // merging.
01650         if (!NewReleaseRetainRRI.Calls.count(NewRelease))
01651           return false;
01652 
01653         if (RetainsToMove.Calls.insert(NewReleaseRetain).second) {
01654           // If we overflow when we compute the path count, don't remove/move
01655           // anything.
01656           const BBState &NRRBBState = BBStates[NewReleaseRetain->getParent()];
01657           unsigned PathCount = BBState::OverflowOccurredValue;
01658           if (NRRBBState.GetAllPathCountWithOverflow(PathCount))
01659             return false;
01660           assert(PathCount != BBState::OverflowOccurredValue &&
01661                  "PathCount at this point can not be "
01662                  "OverflowOccurredValue.");
01663           OldDelta += PathCount;
01664           OldCount += PathCount;
01665 
01666           // Collect the optimal insertion points.
01667           if (!KnownSafe)
01668             for (Instruction *RIP : NewReleaseRetainRRI.ReverseInsertPts) {
01669               if (RetainsToMove.ReverseInsertPts.insert(RIP).second) {
01670                 // If we overflow when we compute the path count, don't
01671                 // remove/move anything.
01672                 const BBState &RIPBBState = BBStates[RIP->getParent()];
01673 
01674                 PathCount = BBState::OverflowOccurredValue;
01675                 if (RIPBBState.GetAllPathCountWithOverflow(PathCount))
01676                   return false;
01677                 assert(PathCount != BBState::OverflowOccurredValue &&
01678                        "PathCount at this point can not be "
01679                        "OverflowOccurredValue.");
01680                 NewDelta += PathCount;
01681                 NewCount += PathCount;
01682               }
01683             }
01684           NewRetains.push_back(NewReleaseRetain);
01685         }
01686       }
01687     }
01688     NewReleases.clear();
01689     if (NewRetains.empty()) break;
01690   }
01691 
01692   // We can only remove pointers if we are known safe in both directions.
01693   bool UnconditionallySafe = KnownSafeTD && KnownSafeBU;
01694   if (UnconditionallySafe) {
01695     RetainsToMove.ReverseInsertPts.clear();
01696     ReleasesToMove.ReverseInsertPts.clear();
01697     NewCount = 0;
01698   } else {
01699     // Determine whether the new insertion points we computed preserve the
01700     // balance of retain and release calls through the program.
01701     // TODO: If the fully aggressive solution isn't valid, try to find a
01702     // less aggressive solution which is.
01703     if (NewDelta != 0)
01704       return false;
01705 
01706     // At this point, we are not going to remove any RR pairs, but we still are
01707     // able to move RR pairs. If one of our pointers is afflicted with
01708     // CFGHazards, we cannot perform such code motion so exit early.
01709     const bool WillPerformCodeMotion = RetainsToMove.ReverseInsertPts.size() ||
01710       ReleasesToMove.ReverseInsertPts.size();
01711     if (CFGHazardAfflicted && WillPerformCodeMotion)
01712       return false;
01713   }
01714 
01715   // Determine whether the original call points are balanced in the retain and
01716   // release calls through the program. If not, conservatively don't touch
01717   // them.
01718   // TODO: It's theoretically possible to do code motion in this case, as
01719   // long as the existing imbalances are maintained.
01720   if (OldDelta != 0)
01721     return false;
01722 
01723   Changed = true;
01724   assert(OldCount != 0 && "Unreachable code?");
01725   NumRRs += OldCount - NewCount;
01726   // Set to true if we completely removed any RR pairs.
01727   AnyPairsCompletelyEliminated = NewCount == 0;
01728 
01729   // We can move calls!
01730   return true;
01731 }
01732 
01733 /// Identify pairings between the retains and releases, and delete and/or move
01734 /// them.
01735 bool ObjCARCOpt::PerformCodePlacement(
01736     DenseMap<const BasicBlock *, BBState> &BBStates,
01737     BlotMapVector<Value *, RRInfo> &Retains,
01738     DenseMap<Value *, RRInfo> &Releases, Module *M) {
01739   DEBUG(dbgs() << "\n== ObjCARCOpt::PerformCodePlacement ==\n");
01740 
01741   bool AnyPairsCompletelyEliminated = false;
01742   RRInfo RetainsToMove;
01743   RRInfo ReleasesToMove;
01744   SmallVector<Instruction *, 4> NewRetains;
01745   SmallVector<Instruction *, 4> NewReleases;
01746   SmallVector<Instruction *, 8> DeadInsts;
01747 
01748   // Visit each retain.
01749   for (BlotMapVector<Value *, RRInfo>::const_iterator I = Retains.begin(),
01750                                                       E = Retains.end();
01751        I != E; ++I) {
01752     Value *V = I->first;
01753     if (!V) continue; // blotted
01754 
01755     Instruction *Retain = cast<Instruction>(V);
01756 
01757     DEBUG(dbgs() << "Visiting: " << *Retain << "\n");
01758 
01759     Value *Arg = GetArgRCIdentityRoot(Retain);
01760 
01761     // If the object being released is in static or stack storage, we know it's
01762     // not being managed by ObjC reference counting, so we can delete pairs
01763     // regardless of what possible decrements or uses lie between them.
01764     bool KnownSafe = isa<Constant>(Arg) || isa<AllocaInst>(Arg);
01765 
01766     // A constant pointer can't be pointing to an object on the heap. It may
01767     // be reference-counted, but it won't be deleted.
01768     if (const LoadInst *LI = dyn_cast<LoadInst>(Arg))
01769       if (const GlobalVariable *GV =
01770             dyn_cast<GlobalVariable>(
01771               GetRCIdentityRoot(LI->getPointerOperand())))
01772         if (GV->isConstant())
01773           KnownSafe = true;
01774 
01775     // Connect the dots between the top-down-collected RetainsToMove and
01776     // bottom-up-collected ReleasesToMove to form sets of related calls.
01777     NewRetains.push_back(Retain);
01778     bool PerformMoveCalls = PairUpRetainsAndReleases(
01779         BBStates, Retains, Releases, M, NewRetains, NewReleases, DeadInsts,
01780         RetainsToMove, ReleasesToMove, Arg, KnownSafe,
01781         AnyPairsCompletelyEliminated);
01782 
01783     if (PerformMoveCalls) {
01784       // Ok, everything checks out and we're all set. Let's move/delete some
01785       // code!
01786       MoveCalls(Arg, RetainsToMove, ReleasesToMove,
01787                 Retains, Releases, DeadInsts, M);
01788     }
01789 
01790     // Clean up state for next retain.
01791     NewReleases.clear();
01792     NewRetains.clear();
01793     RetainsToMove.clear();
01794     ReleasesToMove.clear();
01795   }
01796 
01797   // Now that we're done moving everything, we can delete the newly dead
01798   // instructions, as we no longer need them as insert points.
01799   while (!DeadInsts.empty())
01800     EraseInstruction(DeadInsts.pop_back_val());
01801 
01802   return AnyPairsCompletelyEliminated;
01803 }
01804 
01805 /// Weak pointer optimizations.
01806 void ObjCARCOpt::OptimizeWeakCalls(Function &F) {
01807   DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeWeakCalls ==\n");
01808 
01809   // First, do memdep-style RLE and S2L optimizations. We can't use memdep
01810   // itself because it uses AliasAnalysis and we need to do provenance
01811   // queries instead.
01812   for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
01813     Instruction *Inst = &*I++;
01814 
01815     DEBUG(dbgs() << "Visiting: " << *Inst << "\n");
01816 
01817     ARCInstKind Class = GetBasicARCInstKind(Inst);
01818     if (Class != ARCInstKind::LoadWeak &&
01819         Class != ARCInstKind::LoadWeakRetained)
01820       continue;
01821 
01822     // Delete objc_loadWeak calls with no users.
01823     if (Class == ARCInstKind::LoadWeak && Inst->use_empty()) {
01824       Inst->eraseFromParent();
01825       continue;
01826     }
01827 
01828     // TODO: For now, just look for an earlier available version of this value
01829     // within the same block. Theoretically, we could do memdep-style non-local
01830     // analysis too, but that would want caching. A better approach would be to
01831     // use the technique that EarlyCSE uses.
01832     inst_iterator Current = std::prev(I);
01833     BasicBlock *CurrentBB = Current.getBasicBlockIterator();
01834     for (BasicBlock::iterator B = CurrentBB->begin(),
01835                               J = Current.getInstructionIterator();
01836          J != B; --J) {
01837       Instruction *EarlierInst = &*std::prev(J);
01838       ARCInstKind EarlierClass = GetARCInstKind(EarlierInst);
01839       switch (EarlierClass) {
01840       case ARCInstKind::LoadWeak:
01841       case ARCInstKind::LoadWeakRetained: {
01842         // If this is loading from the same pointer, replace this load's value
01843         // with that one.
01844         CallInst *Call = cast<CallInst>(Inst);
01845         CallInst *EarlierCall = cast<CallInst>(EarlierInst);
01846         Value *Arg = Call->getArgOperand(0);
01847         Value *EarlierArg = EarlierCall->getArgOperand(0);
01848         switch (PA.getAA()->alias(Arg, EarlierArg)) {
01849         case AliasAnalysis::MustAlias:
01850           Changed = true;
01851           // If the load has a builtin retain, insert a plain retain for it.
01852           if (Class == ARCInstKind::LoadWeakRetained) {
01853             Constant *Decl = EP.get(ARCRuntimeEntryPointKind::Retain);
01854             CallInst *CI = CallInst::Create(Decl, EarlierCall, "", Call);
01855             CI->setTailCall();
01856           }
01857           // Zap the fully redundant load.
01858           Call->replaceAllUsesWith(EarlierCall);
01859           Call->eraseFromParent();
01860           goto clobbered;
01861         case AliasAnalysis::MayAlias:
01862         case AliasAnalysis::PartialAlias:
01863           goto clobbered;
01864         case AliasAnalysis::NoAlias:
01865           break;
01866         }
01867         break;
01868       }
01869       case ARCInstKind::StoreWeak:
01870       case ARCInstKind::InitWeak: {
01871         // If this is storing to the same pointer and has the same size etc.
01872         // replace this load's value with the stored value.
01873         CallInst *Call = cast<CallInst>(Inst);
01874         CallInst *EarlierCall = cast<CallInst>(EarlierInst);
01875         Value *Arg = Call->getArgOperand(0);
01876         Value *EarlierArg = EarlierCall->getArgOperand(0);
01877         switch (PA.getAA()->alias(Arg, EarlierArg)) {
01878         case AliasAnalysis::MustAlias:
01879           Changed = true;
01880           // If the load has a builtin retain, insert a plain retain for it.
01881           if (Class == ARCInstKind::LoadWeakRetained) {
01882             Constant *Decl = EP.get(ARCRuntimeEntryPointKind::Retain);
01883             CallInst *CI = CallInst::Create(Decl, EarlierCall, "", Call);
01884             CI->setTailCall();
01885           }
01886           // Zap the fully redundant load.
01887           Call->replaceAllUsesWith(EarlierCall->getArgOperand(1));
01888           Call->eraseFromParent();
01889           goto clobbered;
01890         case AliasAnalysis::MayAlias:
01891         case AliasAnalysis::PartialAlias:
01892           goto clobbered;
01893         case AliasAnalysis::NoAlias:
01894           break;
01895         }
01896         break;
01897       }
01898       case ARCInstKind::MoveWeak:
01899       case ARCInstKind::CopyWeak:
01900         // TOOD: Grab the copied value.
01901         goto clobbered;
01902       case ARCInstKind::AutoreleasepoolPush:
01903       case ARCInstKind::None:
01904       case ARCInstKind::IntrinsicUser:
01905       case ARCInstKind::User:
01906         // Weak pointers are only modified through the weak entry points
01907         // (and arbitrary calls, which could call the weak entry points).
01908         break;
01909       default:
01910         // Anything else could modify the weak pointer.
01911         goto clobbered;
01912       }
01913     }
01914   clobbered:;
01915   }
01916 
01917   // Then, for each destroyWeak with an alloca operand, check to see if
01918   // the alloca and all its users can be zapped.
01919   for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
01920     Instruction *Inst = &*I++;
01921     ARCInstKind Class = GetBasicARCInstKind(Inst);
01922     if (Class != ARCInstKind::DestroyWeak)
01923       continue;
01924 
01925     CallInst *Call = cast<CallInst>(Inst);
01926     Value *Arg = Call->getArgOperand(0);
01927     if (AllocaInst *Alloca = dyn_cast<AllocaInst>(Arg)) {
01928       for (User *U : Alloca->users()) {
01929         const Instruction *UserInst = cast<Instruction>(U);
01930         switch (GetBasicARCInstKind(UserInst)) {
01931         case ARCInstKind::InitWeak:
01932         case ARCInstKind::StoreWeak:
01933         case ARCInstKind::DestroyWeak:
01934           continue;
01935         default:
01936           goto done;
01937         }
01938       }
01939       Changed = true;
01940       for (auto UI = Alloca->user_begin(), UE = Alloca->user_end(); UI != UE;) {
01941         CallInst *UserInst = cast<CallInst>(*UI++);
01942         switch (GetBasicARCInstKind(UserInst)) {
01943         case ARCInstKind::InitWeak:
01944         case ARCInstKind::StoreWeak:
01945           // These functions return their second argument.
01946           UserInst->replaceAllUsesWith(UserInst->getArgOperand(1));
01947           break;
01948         case ARCInstKind::DestroyWeak:
01949           // No return value.
01950           break;
01951         default:
01952           llvm_unreachable("alloca really is used!");
01953         }
01954         UserInst->eraseFromParent();
01955       }
01956       Alloca->eraseFromParent();
01957     done:;
01958     }
01959   }
01960 }
01961 
01962 /// Identify program paths which execute sequences of retains and releases which
01963 /// can be eliminated.
01964 bool ObjCARCOpt::OptimizeSequences(Function &F) {
01965   // Releases, Retains - These are used to store the results of the main flow
01966   // analysis. These use Value* as the key instead of Instruction* so that the
01967   // map stays valid when we get around to rewriting code and calls get
01968   // replaced by arguments.
01969   DenseMap<Value *, RRInfo> Releases;
01970   BlotMapVector<Value *, RRInfo> Retains;
01971 
01972   // This is used during the traversal of the function to track the
01973   // states for each identified object at each block.
01974   DenseMap<const BasicBlock *, BBState> BBStates;
01975 
01976   // Analyze the CFG of the function, and all instructions.
01977   bool NestingDetected = Visit(F, BBStates, Retains, Releases);
01978 
01979   // Transform.
01980   bool AnyPairsCompletelyEliminated = PerformCodePlacement(BBStates, Retains,
01981                                                            Releases,
01982                                                            F.getParent());
01983 
01984   // Cleanup.
01985   MultiOwnersSet.clear();
01986 
01987   return AnyPairsCompletelyEliminated && NestingDetected;
01988 }
01989 
01990 /// Check if there is a dependent call earlier that does not have anything in
01991 /// between the Retain and the call that can affect the reference count of their
01992 /// shared pointer argument. Note that Retain need not be in BB.
01993 static bool
01994 HasSafePathToPredecessorCall(const Value *Arg, Instruction *Retain,
01995                              SmallPtrSetImpl<Instruction *> &DepInsts,
01996                              SmallPtrSetImpl<const BasicBlock *> &Visited,
01997                              ProvenanceAnalysis &PA) {
01998   FindDependencies(CanChangeRetainCount, Arg, Retain->getParent(), Retain,
01999                    DepInsts, Visited, PA);
02000   if (DepInsts.size() != 1)
02001     return false;
02002 
02003   auto *Call = dyn_cast_or_null<CallInst>(*DepInsts.begin());
02004 
02005   // Check that the pointer is the return value of the call.
02006   if (!Call || Arg != Call)
02007     return false;
02008 
02009   // Check that the call is a regular call.
02010   ARCInstKind Class = GetBasicARCInstKind(Call);
02011   if (Class != ARCInstKind::CallOrUser && Class != ARCInstKind::Call)
02012     return false;
02013 
02014   return true;
02015 }
02016 
02017 /// Find a dependent retain that precedes the given autorelease for which there
02018 /// is nothing in between the two instructions that can affect the ref count of
02019 /// Arg.
02020 static CallInst *
02021 FindPredecessorRetainWithSafePath(const Value *Arg, BasicBlock *BB,
02022                                   Instruction *Autorelease,
02023                                   SmallPtrSetImpl<Instruction *> &DepInsts,
02024                                   SmallPtrSetImpl<const BasicBlock *> &Visited,
02025                                   ProvenanceAnalysis &PA) {
02026   FindDependencies(CanChangeRetainCount, Arg,
02027                    BB, Autorelease, DepInsts, Visited, PA);
02028   if (DepInsts.size() != 1)
02029     return nullptr;
02030 
02031   auto *Retain = dyn_cast_or_null<CallInst>(*DepInsts.begin());
02032 
02033   // Check that we found a retain with the same argument.
02034   if (!Retain || !IsRetain(GetBasicARCInstKind(Retain)) ||
02035       GetArgRCIdentityRoot(Retain) != Arg) {
02036     return nullptr;
02037   }
02038 
02039   return Retain;
02040 }
02041 
02042 /// Look for an ``autorelease'' instruction dependent on Arg such that there are
02043 /// no instructions dependent on Arg that need a positive ref count in between
02044 /// the autorelease and the ret.
02045 static CallInst *
02046 FindPredecessorAutoreleaseWithSafePath(const Value *Arg, BasicBlock *BB,
02047                                        ReturnInst *Ret,
02048                                        SmallPtrSetImpl<Instruction *> &DepInsts,
02049                                        SmallPtrSetImpl<const BasicBlock *> &V,
02050                                        ProvenanceAnalysis &PA) {
02051   FindDependencies(NeedsPositiveRetainCount, Arg,
02052                    BB, Ret, DepInsts, V, PA);
02053   if (DepInsts.size() != 1)
02054     return nullptr;
02055 
02056   auto *Autorelease = dyn_cast_or_null<CallInst>(*DepInsts.begin());
02057   if (!Autorelease)
02058     return nullptr;
02059   ARCInstKind AutoreleaseClass = GetBasicARCInstKind(Autorelease);
02060   if (!IsAutorelease(AutoreleaseClass))
02061     return nullptr;
02062   if (GetArgRCIdentityRoot(Autorelease) != Arg)
02063     return nullptr;
02064 
02065   return Autorelease;
02066 }
02067 
02068 /// Look for this pattern:
02069 /// \code
02070 ///    %call = call i8* @something(...)
02071 ///    %2 = call i8* @objc_retain(i8* %call)
02072 ///    %3 = call i8* @objc_autorelease(i8* %2)
02073 ///    ret i8* %3
02074 /// \endcode
02075 /// And delete the retain and autorelease.
02076 void ObjCARCOpt::OptimizeReturns(Function &F) {
02077   if (!F.getReturnType()->isPointerTy())
02078     return;
02079 
02080   DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeReturns ==\n");
02081 
02082   SmallPtrSet<Instruction *, 4> DependingInstructions;
02083   SmallPtrSet<const BasicBlock *, 4> Visited;
02084   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
02085     BasicBlock *BB = FI;
02086     ReturnInst *Ret = dyn_cast<ReturnInst>(&BB->back());
02087 
02088     DEBUG(dbgs() << "Visiting: " << *Ret << "\n");
02089 
02090     if (!Ret)
02091       continue;
02092 
02093     const Value *Arg = GetRCIdentityRoot(Ret->getOperand(0));
02094 
02095     // Look for an ``autorelease'' instruction that is a predecessor of Ret and
02096     // dependent on Arg such that there are no instructions dependent on Arg
02097     // that need a positive ref count in between the autorelease and Ret.
02098     CallInst *Autorelease =
02099       FindPredecessorAutoreleaseWithSafePath(Arg, BB, Ret,
02100                                              DependingInstructions, Visited,
02101                                              PA);
02102     DependingInstructions.clear();
02103     Visited.clear();
02104 
02105     if (!Autorelease)
02106       continue;
02107 
02108     CallInst *Retain =
02109       FindPredecessorRetainWithSafePath(Arg, BB, Autorelease,
02110                                         DependingInstructions, Visited, PA);
02111     DependingInstructions.clear();
02112     Visited.clear();
02113 
02114     if (!Retain)
02115       continue;
02116 
02117     // Check that there is nothing that can affect the reference count
02118     // between the retain and the call.  Note that Retain need not be in BB.
02119     bool HasSafePathToCall = HasSafePathToPredecessorCall(Arg, Retain,
02120                                                           DependingInstructions,
02121                                                           Visited, PA);
02122     DependingInstructions.clear();
02123     Visited.clear();
02124 
02125     if (!HasSafePathToCall)
02126       continue;
02127 
02128     // If so, we can zap the retain and autorelease.
02129     Changed = true;
02130     ++NumRets;
02131     DEBUG(dbgs() << "Erasing: " << *Retain << "\nErasing: "
02132           << *Autorelease << "\n");
02133     EraseInstruction(Retain);
02134     EraseInstruction(Autorelease);
02135   }
02136 }
02137 
02138 #ifndef NDEBUG
02139 void
02140 ObjCARCOpt::GatherStatistics(Function &F, bool AfterOptimization) {
02141   llvm::Statistic &NumRetains =
02142     AfterOptimization? NumRetainsAfterOpt : NumRetainsBeforeOpt;
02143   llvm::Statistic &NumReleases =
02144     AfterOptimization? NumReleasesAfterOpt : NumReleasesBeforeOpt;
02145 
02146   for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
02147     Instruction *Inst = &*I++;
02148     switch (GetBasicARCInstKind(Inst)) {
02149     default:
02150       break;
02151     case ARCInstKind::Retain:
02152       ++NumRetains;
02153       break;
02154     case ARCInstKind::Release:
02155       ++NumReleases;
02156       break;
02157     }
02158   }
02159 }
02160 #endif
02161 
02162 bool ObjCARCOpt::doInitialization(Module &M) {
02163   if (!EnableARCOpts)
02164     return false;
02165 
02166   // If nothing in the Module uses ARC, don't do anything.
02167   Run = ModuleHasARC(M);
02168   if (!Run)
02169     return false;
02170 
02171   // Intuitively, objc_retain and others are nocapture, however in practice
02172   // they are not, because they return their argument value. And objc_release
02173   // calls finalizers which can have arbitrary side effects.
02174   MDKindCache.init(&M);
02175 
02176   // Initialize our runtime entry point cache.
02177   EP.init(&M);
02178 
02179   return false;
02180 }
02181 
02182 bool ObjCARCOpt::runOnFunction(Function &F) {
02183   if (!EnableARCOpts)
02184     return false;
02185 
02186   // If nothing in the Module uses ARC, don't do anything.
02187   if (!Run)
02188     return false;
02189 
02190   Changed = false;
02191 
02192   DEBUG(dbgs() << "<<< ObjCARCOpt: Visiting Function: " << F.getName() << " >>>"
02193         "\n");
02194 
02195   PA.setAA(&getAnalysis<AliasAnalysis>());
02196 
02197 #ifndef NDEBUG
02198   if (AreStatisticsEnabled()) {
02199     GatherStatistics(F, false);
02200   }
02201 #endif
02202 
02203   // This pass performs several distinct transformations. As a compile-time aid
02204   // when compiling code that isn't ObjC, skip these if the relevant ObjC
02205   // library functions aren't declared.
02206 
02207   // Preliminary optimizations. This also computes UsedInThisFunction.
02208   OptimizeIndividualCalls(F);
02209 
02210   // Optimizations for weak pointers.
02211   if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::LoadWeak)) |
02212                             (1 << unsigned(ARCInstKind::LoadWeakRetained)) |
02213                             (1 << unsigned(ARCInstKind::StoreWeak)) |
02214                             (1 << unsigned(ARCInstKind::InitWeak)) |
02215                             (1 << unsigned(ARCInstKind::CopyWeak)) |
02216                             (1 << unsigned(ARCInstKind::MoveWeak)) |
02217                             (1 << unsigned(ARCInstKind::DestroyWeak))))
02218     OptimizeWeakCalls(F);
02219 
02220   // Optimizations for retain+release pairs.
02221   if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::Retain)) |
02222                             (1 << unsigned(ARCInstKind::RetainRV)) |
02223                             (1 << unsigned(ARCInstKind::RetainBlock))))
02224     if (UsedInThisFunction & (1 << unsigned(ARCInstKind::Release)))
02225       // Run OptimizeSequences until it either stops making changes or
02226       // no retain+release pair nesting is detected.
02227       while (OptimizeSequences(F)) {}
02228 
02229   // Optimizations if objc_autorelease is used.
02230   if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::Autorelease)) |
02231                             (1 << unsigned(ARCInstKind::AutoreleaseRV))))
02232     OptimizeReturns(F);
02233 
02234   // Gather statistics after optimization.
02235 #ifndef NDEBUG
02236   if (AreStatisticsEnabled()) {
02237     GatherStatistics(F, true);
02238   }
02239 #endif
02240 
02241   DEBUG(dbgs() << "\n");
02242 
02243   return Changed;
02244 }
02245 
02246 void ObjCARCOpt::releaseMemory() {
02247   PA.clear();
02248 }
02249 
02250 /// @}
02251 ///