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 "ProvenanceAnalysis.h"
00032 #include "PtrState.h"
00033 #include "llvm/ADT/DenseMap.h"
00034 #include "llvm/ADT/DenseSet.h"
00035 #include "llvm/ADT/STLExtras.h"
00036 #include "llvm/ADT/SmallPtrSet.h"
00037 #include "llvm/ADT/Statistic.h"
00038 #include "llvm/Analysis/ObjCARCAliasAnalysis.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 (Value *IncValue : PN->incoming_values())
00109         Worklist.push_back(IncValue);
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 runtime 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(ObjCARCAAWrapperPass)
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<ObjCARCAAWrapperPass>();
00569   AU.addRequired<AAResultsWrapperPass>();
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))
00587         ++I;
00588       if (&*I == RetainRV)
00589         return false;
00590     } else if (const InvokeInst *II = dyn_cast<InvokeInst>(Call)) {
00591       BasicBlock *RetainRVParent = RetainRV->getParent();
00592       if (II->getNormalDest() == RetainRVParent) {
00593         BasicBlock::const_iterator I = RetainRVParent->begin();
00594         while (IsNoopInstruction(&*I))
00595           ++I;
00596         if (&*I == RetainRV)
00597           return false;
00598       }
00599     }
00600   }
00601 
00602   // Check for being preceded by an objc_autoreleaseReturnValue on the same
00603   // pointer. In this case, we can delete the pair.
00604   BasicBlock::iterator I = RetainRV->getIterator(),
00605                        Begin = RetainRV->getParent()->begin();
00606   if (I != Begin) {
00607     do
00608       --I;
00609     while (I != Begin && IsNoopInstruction(&*I));
00610     if (GetBasicARCInstKind(&*I) == ARCInstKind::AutoreleaseRV &&
00611         GetArgRCIdentityRoot(&*I) == Arg) {
00612       Changed = true;
00613       ++NumPeeps;
00614 
00615       DEBUG(dbgs() << "Erasing autoreleaseRV,retainRV pair: " << *I << "\n"
00616                    << "Erasing " << *RetainRV << "\n");
00617 
00618       EraseInstruction(&*I);
00619       EraseInstruction(RetainRV);
00620       return true;
00621     }
00622   }
00623 
00624   // Turn it to a plain objc_retain.
00625   Changed = true;
00626   ++NumPeeps;
00627 
00628   DEBUG(dbgs() << "Transforming objc_retainAutoreleasedReturnValue => "
00629                   "objc_retain since the operand is not a return value.\n"
00630                   "Old = " << *RetainRV << "\n");
00631 
00632   Constant *NewDecl = EP.get(ARCRuntimeEntryPointKind::Retain);
00633   cast<CallInst>(RetainRV)->setCalledFunction(NewDecl);
00634 
00635   DEBUG(dbgs() << "New = " << *RetainRV << "\n");
00636 
00637   return false;
00638 }
00639 
00640 /// Turn objc_autoreleaseReturnValue into objc_autorelease if the result is not
00641 /// used as a return value.
00642 void ObjCARCOpt::OptimizeAutoreleaseRVCall(Function &F,
00643                                            Instruction *AutoreleaseRV,
00644                                            ARCInstKind &Class) {
00645   // Check for a return of the pointer value.
00646   const Value *Ptr = GetArgRCIdentityRoot(AutoreleaseRV);
00647   SmallVector<const Value *, 2> Users;
00648   Users.push_back(Ptr);
00649   do {
00650     Ptr = Users.pop_back_val();
00651     for (const User *U : Ptr->users()) {
00652       if (isa<ReturnInst>(U) || GetBasicARCInstKind(U) == ARCInstKind::RetainRV)
00653         return;
00654       if (isa<BitCastInst>(U))
00655         Users.push_back(U);
00656     }
00657   } while (!Users.empty());
00658 
00659   Changed = true;
00660   ++NumPeeps;
00661 
00662   DEBUG(dbgs() << "Transforming objc_autoreleaseReturnValue => "
00663                   "objc_autorelease since its operand is not used as a return "
00664                   "value.\n"
00665                   "Old = " << *AutoreleaseRV << "\n");
00666 
00667   CallInst *AutoreleaseRVCI = cast<CallInst>(AutoreleaseRV);
00668   Constant *NewDecl = EP.get(ARCRuntimeEntryPointKind::Autorelease);
00669   AutoreleaseRVCI->setCalledFunction(NewDecl);
00670   AutoreleaseRVCI->setTailCall(false); // Never tail call objc_autorelease.
00671   Class = ARCInstKind::Autorelease;
00672 
00673   DEBUG(dbgs() << "New: " << *AutoreleaseRV << "\n");
00674 
00675 }
00676 
00677 /// Visit each call, one at a time, and make simplifications without doing any
00678 /// additional analysis.
00679 void ObjCARCOpt::OptimizeIndividualCalls(Function &F) {
00680   DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeIndividualCalls ==\n");
00681   // Reset all the flags in preparation for recomputing them.
00682   UsedInThisFunction = 0;
00683 
00684   // Visit all objc_* calls in F.
00685   for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
00686     Instruction *Inst = &*I++;
00687 
00688     ARCInstKind Class = GetBasicARCInstKind(Inst);
00689 
00690     DEBUG(dbgs() << "Visiting: Class: " << Class << "; " << *Inst << "\n");
00691 
00692     switch (Class) {
00693     default: break;
00694 
00695     // Delete no-op casts. These function calls have special semantics, but
00696     // the semantics are entirely implemented via lowering in the front-end,
00697     // so by the time they reach the optimizer, they are just no-op calls
00698     // which return their argument.
00699     //
00700     // There are gray areas here, as the ability to cast reference-counted
00701     // pointers to raw void* and back allows code to break ARC assumptions,
00702     // however these are currently considered to be unimportant.
00703     case ARCInstKind::NoopCast:
00704       Changed = true;
00705       ++NumNoops;
00706       DEBUG(dbgs() << "Erasing no-op cast: " << *Inst << "\n");
00707       EraseInstruction(Inst);
00708       continue;
00709 
00710     // If the pointer-to-weak-pointer is null, it's undefined behavior.
00711     case ARCInstKind::StoreWeak:
00712     case ARCInstKind::LoadWeak:
00713     case ARCInstKind::LoadWeakRetained:
00714     case ARCInstKind::InitWeak:
00715     case ARCInstKind::DestroyWeak: {
00716       CallInst *CI = cast<CallInst>(Inst);
00717       if (IsNullOrUndef(CI->getArgOperand(0))) {
00718         Changed = true;
00719         Type *Ty = CI->getArgOperand(0)->getType();
00720         new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()),
00721                       Constant::getNullValue(Ty),
00722                       CI);
00723         llvm::Value *NewValue = UndefValue::get(CI->getType());
00724         DEBUG(dbgs() << "A null pointer-to-weak-pointer is undefined behavior."
00725                        "\nOld = " << *CI << "\nNew = " << *NewValue << "\n");
00726         CI->replaceAllUsesWith(NewValue);
00727         CI->eraseFromParent();
00728         continue;
00729       }
00730       break;
00731     }
00732     case ARCInstKind::CopyWeak:
00733     case ARCInstKind::MoveWeak: {
00734       CallInst *CI = cast<CallInst>(Inst);
00735       if (IsNullOrUndef(CI->getArgOperand(0)) ||
00736           IsNullOrUndef(CI->getArgOperand(1))) {
00737         Changed = true;
00738         Type *Ty = CI->getArgOperand(0)->getType();
00739         new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()),
00740                       Constant::getNullValue(Ty),
00741                       CI);
00742 
00743         llvm::Value *NewValue = UndefValue::get(CI->getType());
00744         DEBUG(dbgs() << "A null pointer-to-weak-pointer is undefined behavior."
00745                         "\nOld = " << *CI << "\nNew = " << *NewValue << "\n");
00746 
00747         CI->replaceAllUsesWith(NewValue);
00748         CI->eraseFromParent();
00749         continue;
00750       }
00751       break;
00752     }
00753     case ARCInstKind::RetainRV:
00754       if (OptimizeRetainRVCall(F, Inst))
00755         continue;
00756       break;
00757     case ARCInstKind::AutoreleaseRV:
00758       OptimizeAutoreleaseRVCall(F, Inst, Class);
00759       break;
00760     }
00761 
00762     // objc_autorelease(x) -> objc_release(x) if x is otherwise unused.
00763     if (IsAutorelease(Class) && Inst->use_empty()) {
00764       CallInst *Call = cast<CallInst>(Inst);
00765       const Value *Arg = Call->getArgOperand(0);
00766       Arg = FindSingleUseIdentifiedObject(Arg);
00767       if (Arg) {
00768         Changed = true;
00769         ++NumAutoreleases;
00770 
00771         // Create the declaration lazily.
00772         LLVMContext &C = Inst->getContext();
00773 
00774         Constant *Decl = EP.get(ARCRuntimeEntryPointKind::Release);
00775         CallInst *NewCall = CallInst::Create(Decl, Call->getArgOperand(0), "",
00776                                              Call);
00777         NewCall->setMetadata(MDKindCache.get(ARCMDKindID::ImpreciseRelease),
00778                              MDNode::get(C, None));
00779 
00780         DEBUG(dbgs() << "Replacing autorelease{,RV}(x) with objc_release(x) "
00781               "since x is otherwise unused.\nOld: " << *Call << "\nNew: "
00782               << *NewCall << "\n");
00783 
00784         EraseInstruction(Call);
00785         Inst = NewCall;
00786         Class = ARCInstKind::Release;
00787       }
00788     }
00789 
00790     // For functions which can never be passed stack arguments, add
00791     // a tail keyword.
00792     if (IsAlwaysTail(Class)) {
00793       Changed = true;
00794       DEBUG(dbgs() << "Adding tail keyword to function since it can never be "
00795                       "passed stack args: " << *Inst << "\n");
00796       cast<CallInst>(Inst)->setTailCall();
00797     }
00798 
00799     // Ensure that functions that can never have a "tail" keyword due to the
00800     // semantics of ARC truly do not do so.
00801     if (IsNeverTail(Class)) {
00802       Changed = true;
00803       DEBUG(dbgs() << "Removing tail keyword from function: " << *Inst <<
00804             "\n");
00805       cast<CallInst>(Inst)->setTailCall(false);
00806     }
00807 
00808     // Set nounwind as needed.
00809     if (IsNoThrow(Class)) {
00810       Changed = true;
00811       DEBUG(dbgs() << "Found no throw class. Setting nounwind on: " << *Inst
00812                    << "\n");
00813       cast<CallInst>(Inst)->setDoesNotThrow();
00814     }
00815 
00816     if (!IsNoopOnNull(Class)) {
00817       UsedInThisFunction |= 1 << unsigned(Class);
00818       continue;
00819     }
00820 
00821     const Value *Arg = GetArgRCIdentityRoot(Inst);
00822 
00823     // ARC calls with null are no-ops. Delete them.
00824     if (IsNullOrUndef(Arg)) {
00825       Changed = true;
00826       ++NumNoops;
00827       DEBUG(dbgs() << "ARC calls with  null are no-ops. Erasing: " << *Inst
00828             << "\n");
00829       EraseInstruction(Inst);
00830       continue;
00831     }
00832 
00833     // Keep track of which of retain, release, autorelease, and retain_block
00834     // are actually present in this function.
00835     UsedInThisFunction |= 1 << unsigned(Class);
00836 
00837     // If Arg is a PHI, and one or more incoming values to the
00838     // PHI are null, and the call is control-equivalent to the PHI, and there
00839     // are no relevant side effects between the PHI and the call, the call
00840     // could be pushed up to just those paths with non-null incoming values.
00841     // For now, don't bother splitting critical edges for this.
00842     SmallVector<std::pair<Instruction *, const Value *>, 4> Worklist;
00843     Worklist.push_back(std::make_pair(Inst, Arg));
00844     do {
00845       std::pair<Instruction *, const Value *> Pair = Worklist.pop_back_val();
00846       Inst = Pair.first;
00847       Arg = Pair.second;
00848 
00849       const PHINode *PN = dyn_cast<PHINode>(Arg);
00850       if (!PN) continue;
00851 
00852       // Determine if the PHI has any null operands, or any incoming
00853       // critical edges.
00854       bool HasNull = false;
00855       bool HasCriticalEdges = false;
00856       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
00857         Value *Incoming =
00858           GetRCIdentityRoot(PN->getIncomingValue(i));
00859         if (IsNullOrUndef(Incoming))
00860           HasNull = true;
00861         else if (cast<TerminatorInst>(PN->getIncomingBlock(i)->back())
00862                    .getNumSuccessors() != 1) {
00863           HasCriticalEdges = true;
00864           break;
00865         }
00866       }
00867       // If we have null operands and no critical edges, optimize.
00868       if (!HasCriticalEdges && HasNull) {
00869         SmallPtrSet<Instruction *, 4> DependingInstructions;
00870         SmallPtrSet<const BasicBlock *, 4> Visited;
00871 
00872         // Check that there is nothing that cares about the reference
00873         // count between the call and the phi.
00874         switch (Class) {
00875         case ARCInstKind::Retain:
00876         case ARCInstKind::RetainBlock:
00877           // These can always be moved up.
00878           break;
00879         case ARCInstKind::Release:
00880           // These can't be moved across things that care about the retain
00881           // count.
00882           FindDependencies(NeedsPositiveRetainCount, Arg,
00883                            Inst->getParent(), Inst,
00884                            DependingInstructions, Visited, PA);
00885           break;
00886         case ARCInstKind::Autorelease:
00887           // These can't be moved across autorelease pool scope boundaries.
00888           FindDependencies(AutoreleasePoolBoundary, Arg,
00889                            Inst->getParent(), Inst,
00890                            DependingInstructions, Visited, PA);
00891           break;
00892         case ARCInstKind::RetainRV:
00893         case ARCInstKind::AutoreleaseRV:
00894           // Don't move these; the RV optimization depends on the autoreleaseRV
00895           // being tail called, and the retainRV being immediately after a call
00896           // (which might still happen if we get lucky with codegen layout, but
00897           // it's not worth taking the chance).
00898           continue;
00899         default:
00900           llvm_unreachable("Invalid dependence flavor");
00901         }
00902 
00903         if (DependingInstructions.size() == 1 &&
00904             *DependingInstructions.begin() == PN) {
00905           Changed = true;
00906           ++NumPartialNoops;
00907           // Clone the call into each predecessor that has a non-null value.
00908           CallInst *CInst = cast<CallInst>(Inst);
00909           Type *ParamTy = CInst->getArgOperand(0)->getType();
00910           for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
00911             Value *Incoming =
00912               GetRCIdentityRoot(PN->getIncomingValue(i));
00913             if (!IsNullOrUndef(Incoming)) {
00914               CallInst *Clone = cast<CallInst>(CInst->clone());
00915               Value *Op = PN->getIncomingValue(i);
00916               Instruction *InsertPos = &PN->getIncomingBlock(i)->back();
00917               if (Op->getType() != ParamTy)
00918                 Op = new BitCastInst(Op, ParamTy, "", InsertPos);
00919               Clone->setArgOperand(0, Op);
00920               Clone->insertBefore(InsertPos);
00921 
00922               DEBUG(dbgs() << "Cloning "
00923                            << *CInst << "\n"
00924                            "And inserting clone at " << *InsertPos << "\n");
00925               Worklist.push_back(std::make_pair(Clone, Incoming));
00926             }
00927           }
00928           // Erase the original call.
00929           DEBUG(dbgs() << "Erasing: " << *CInst << "\n");
00930           EraseInstruction(CInst);
00931           continue;
00932         }
00933       }
00934     } while (!Worklist.empty());
00935   }
00936 }
00937 
00938 /// If we have a top down pointer in the S_Use state, make sure that there are
00939 /// no CFG hazards by checking the states of various bottom up pointers.
00940 static void CheckForUseCFGHazard(const Sequence SuccSSeq,
00941                                  const bool SuccSRRIKnownSafe,
00942                                  TopDownPtrState &S,
00943                                  bool &SomeSuccHasSame,
00944                                  bool &AllSuccsHaveSame,
00945                                  bool &NotAllSeqEqualButKnownSafe,
00946                                  bool &ShouldContinue) {
00947   switch (SuccSSeq) {
00948   case S_CanRelease: {
00949     if (!S.IsKnownSafe() && !SuccSRRIKnownSafe) {
00950       S.ClearSequenceProgress();
00951       break;
00952     }
00953     S.SetCFGHazardAfflicted(true);
00954     ShouldContinue = true;
00955     break;
00956   }
00957   case S_Use:
00958     SomeSuccHasSame = true;
00959     break;
00960   case S_Stop:
00961   case S_Release:
00962   case S_MovableRelease:
00963     if (!S.IsKnownSafe() && !SuccSRRIKnownSafe)
00964       AllSuccsHaveSame = false;
00965     else
00966       NotAllSeqEqualButKnownSafe = true;
00967     break;
00968   case S_Retain:
00969     llvm_unreachable("bottom-up pointer in retain state!");
00970   case S_None:
00971     llvm_unreachable("This should have been handled earlier.");
00972   }
00973 }
00974 
00975 /// If we have a Top Down pointer in the S_CanRelease state, make sure that
00976 /// there are no CFG hazards by checking the states of various bottom up
00977 /// pointers.
00978 static void CheckForCanReleaseCFGHazard(const Sequence SuccSSeq,
00979                                         const bool SuccSRRIKnownSafe,
00980                                         TopDownPtrState &S,
00981                                         bool &SomeSuccHasSame,
00982                                         bool &AllSuccsHaveSame,
00983                                         bool &NotAllSeqEqualButKnownSafe) {
00984   switch (SuccSSeq) {
00985   case S_CanRelease:
00986     SomeSuccHasSame = true;
00987     break;
00988   case S_Stop:
00989   case S_Release:
00990   case S_MovableRelease:
00991   case S_Use:
00992     if (!S.IsKnownSafe() && !SuccSRRIKnownSafe)
00993       AllSuccsHaveSame = false;
00994     else
00995       NotAllSeqEqualButKnownSafe = true;
00996     break;
00997   case S_Retain:
00998     llvm_unreachable("bottom-up pointer in retain state!");
00999   case S_None:
01000     llvm_unreachable("This should have been handled earlier.");
01001   }
01002 }
01003 
01004 /// Check for critical edges, loop boundaries, irreducible control flow, or
01005 /// other CFG structures where moving code across the edge would result in it
01006 /// being executed more.
01007 void
01008 ObjCARCOpt::CheckForCFGHazards(const BasicBlock *BB,
01009                                DenseMap<const BasicBlock *, BBState> &BBStates,
01010                                BBState &MyStates) const {
01011   // If any top-down local-use or possible-dec has a succ which is earlier in
01012   // the sequence, forget it.
01013   for (auto I = MyStates.top_down_ptr_begin(), E = MyStates.top_down_ptr_end();
01014        I != E; ++I) {
01015     TopDownPtrState &S = I->second;
01016     const Sequence Seq = I->second.GetSeq();
01017 
01018     // We only care about S_Retain, S_CanRelease, and S_Use.
01019     if (Seq == S_None)
01020       continue;
01021 
01022     // Make sure that if extra top down states are added in the future that this
01023     // code is updated to handle it.
01024     assert((Seq == S_Retain || Seq == S_CanRelease || Seq == S_Use) &&
01025            "Unknown top down sequence state.");
01026 
01027     const Value *Arg = I->first;
01028     const TerminatorInst *TI = cast<TerminatorInst>(&BB->back());
01029     bool SomeSuccHasSame = false;
01030     bool AllSuccsHaveSame = true;
01031     bool NotAllSeqEqualButKnownSafe = false;
01032 
01033     succ_const_iterator SI(TI), SE(TI, false);
01034 
01035     for (; SI != SE; ++SI) {
01036       // If VisitBottomUp has pointer information for this successor, take
01037       // what we know about it.
01038       const DenseMap<const BasicBlock *, BBState>::iterator BBI =
01039         BBStates.find(*SI);
01040       assert(BBI != BBStates.end());
01041       const BottomUpPtrState &SuccS = BBI->second.getPtrBottomUpState(Arg);
01042       const Sequence SuccSSeq = SuccS.GetSeq();
01043 
01044       // If bottom up, the pointer is in an S_None state, clear the sequence
01045       // progress since the sequence in the bottom up state finished
01046       // suggesting a mismatch in between retains/releases. This is true for
01047       // all three cases that we are handling here: S_Retain, S_Use, and
01048       // S_CanRelease.
01049       if (SuccSSeq == S_None) {
01050         S.ClearSequenceProgress();
01051         continue;
01052       }
01053 
01054       // If we have S_Use or S_CanRelease, perform our check for cfg hazard
01055       // checks.
01056       const bool SuccSRRIKnownSafe = SuccS.IsKnownSafe();
01057 
01058       // *NOTE* We do not use Seq from above here since we are allowing for
01059       // S.GetSeq() to change while we are visiting basic blocks.
01060       switch(S.GetSeq()) {
01061       case S_Use: {
01062         bool ShouldContinue = false;
01063         CheckForUseCFGHazard(SuccSSeq, SuccSRRIKnownSafe, S, SomeSuccHasSame,
01064                              AllSuccsHaveSame, NotAllSeqEqualButKnownSafe,
01065                              ShouldContinue);
01066         if (ShouldContinue)
01067           continue;
01068         break;
01069       }
01070       case S_CanRelease: {
01071         CheckForCanReleaseCFGHazard(SuccSSeq, SuccSRRIKnownSafe, S,
01072                                     SomeSuccHasSame, AllSuccsHaveSame,
01073                                     NotAllSeqEqualButKnownSafe);
01074         break;
01075       }
01076       case S_Retain:
01077       case S_None:
01078       case S_Stop:
01079       case S_Release:
01080       case S_MovableRelease:
01081         break;
01082       }
01083     }
01084 
01085     // If the state at the other end of any of the successor edges
01086     // matches the current state, require all edges to match. This
01087     // guards against loops in the middle of a sequence.
01088     if (SomeSuccHasSame && !AllSuccsHaveSame) {
01089       S.ClearSequenceProgress();
01090     } else if (NotAllSeqEqualButKnownSafe) {
01091       // If we would have cleared the state foregoing the fact that we are known
01092       // safe, stop code motion. This is because whether or not it is safe to
01093       // remove RR pairs via KnownSafe is an orthogonal concept to whether we
01094       // are allowed to perform code motion.
01095       S.SetCFGHazardAfflicted(true);
01096     }
01097   }
01098 }
01099 
01100 bool ObjCARCOpt::VisitInstructionBottomUp(
01101     Instruction *Inst, BasicBlock *BB, BlotMapVector<Value *, RRInfo> &Retains,
01102     BBState &MyStates) {
01103   bool NestingDetected = false;
01104   ARCInstKind Class = GetARCInstKind(Inst);
01105   const Value *Arg = nullptr;
01106 
01107   DEBUG(dbgs() << "        Class: " << Class << "\n");
01108 
01109   switch (Class) {
01110   case ARCInstKind::Release: {
01111     Arg = GetArgRCIdentityRoot(Inst);
01112 
01113     BottomUpPtrState &S = MyStates.getPtrBottomUpState(Arg);
01114     NestingDetected |= S.InitBottomUp(MDKindCache, Inst);
01115     break;
01116   }
01117   case ARCInstKind::RetainBlock:
01118     // In OptimizeIndividualCalls, we have strength reduced all optimizable
01119     // objc_retainBlocks to objc_retains. Thus at this point any
01120     // objc_retainBlocks that we see are not optimizable.
01121     break;
01122   case ARCInstKind::Retain:
01123   case ARCInstKind::RetainRV: {
01124     Arg = GetArgRCIdentityRoot(Inst);
01125     BottomUpPtrState &S = MyStates.getPtrBottomUpState(Arg);
01126     if (S.MatchWithRetain()) {
01127       // Don't do retain+release tracking for ARCInstKind::RetainRV, because
01128       // it's better to let it remain as the first instruction after a call.
01129       if (Class != ARCInstKind::RetainRV) {
01130         DEBUG(llvm::dbgs() << "        Matching with: " << *Inst << "\n");
01131         Retains[Inst] = S.GetRRInfo();
01132       }
01133       S.ClearSequenceProgress();
01134     }
01135     // A retain moving bottom up can be a use.
01136     break;
01137   }
01138   case ARCInstKind::AutoreleasepoolPop:
01139     // Conservatively, clear MyStates for all known pointers.
01140     MyStates.clearBottomUpPointers();
01141     return NestingDetected;
01142   case ARCInstKind::AutoreleasepoolPush:
01143   case ARCInstKind::None:
01144     // These are irrelevant.
01145     return NestingDetected;
01146   case ARCInstKind::User:
01147     // If we have a store into an alloca of a pointer we are tracking, the
01148     // pointer has multiple owners implying that we must be more conservative.
01149     //
01150     // This comes up in the context of a pointer being ``KnownSafe''. In the
01151     // presence of a block being initialized, the frontend will emit the
01152     // objc_retain on the original pointer and the release on the pointer loaded
01153     // from the alloca. The optimizer will through the provenance analysis
01154     // realize that the two are related, but since we only require KnownSafe in
01155     // one direction, will match the inner retain on the original pointer with
01156     // the guard release on the original pointer. This is fixed by ensuring that
01157     // in the presence of allocas we only unconditionally remove pointers if
01158     // both our retain and our release are KnownSafe.
01159     if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
01160       const DataLayout &DL = BB->getModule()->getDataLayout();
01161       if (AreAnyUnderlyingObjectsAnAlloca(SI->getPointerOperand(), DL)) {
01162         auto I = MyStates.findPtrBottomUpState(
01163             GetRCIdentityRoot(SI->getValueOperand()));
01164         if (I != MyStates.bottom_up_ptr_end())
01165           MultiOwnersSet.insert(I->first);
01166       }
01167     }
01168     break;
01169   default:
01170     break;
01171   }
01172 
01173   // Consider any other possible effects of this instruction on each
01174   // pointer being tracked.
01175   for (auto MI = MyStates.bottom_up_ptr_begin(),
01176             ME = MyStates.bottom_up_ptr_end();
01177        MI != ME; ++MI) {
01178     const Value *Ptr = MI->first;
01179     if (Ptr == Arg)
01180       continue; // Handled above.
01181     BottomUpPtrState &S = MI->second;
01182 
01183     if (S.HandlePotentialAlterRefCount(Inst, Ptr, PA, Class))
01184       continue;
01185 
01186     S.HandlePotentialUse(BB, Inst, Ptr, PA, Class);
01187   }
01188 
01189   return NestingDetected;
01190 }
01191 
01192 bool ObjCARCOpt::VisitBottomUp(BasicBlock *BB,
01193                                DenseMap<const BasicBlock *, BBState> &BBStates,
01194                                BlotMapVector<Value *, RRInfo> &Retains) {
01195 
01196   DEBUG(dbgs() << "\n== ObjCARCOpt::VisitBottomUp ==\n");
01197 
01198   bool NestingDetected = false;
01199   BBState &MyStates = BBStates[BB];
01200 
01201   // Merge the states from each successor to compute the initial state
01202   // for the current block.
01203   BBState::edge_iterator SI(MyStates.succ_begin()),
01204                          SE(MyStates.succ_end());
01205   if (SI != SE) {
01206     const BasicBlock *Succ = *SI;
01207     DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Succ);
01208     assert(I != BBStates.end());
01209     MyStates.InitFromSucc(I->second);
01210     ++SI;
01211     for (; SI != SE; ++SI) {
01212       Succ = *SI;
01213       I = BBStates.find(Succ);
01214       assert(I != BBStates.end());
01215       MyStates.MergeSucc(I->second);
01216     }
01217   }
01218 
01219   DEBUG(llvm::dbgs() << "Before:\n" << BBStates[BB] << "\n"
01220                      << "Performing Dataflow:\n");
01221 
01222   // Visit all the instructions, bottom-up.
01223   for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; --I) {
01224     Instruction *Inst = &*std::prev(I);
01225 
01226     // Invoke instructions are visited as part of their successors (below).
01227     if (isa<InvokeInst>(Inst))
01228       continue;
01229 
01230     DEBUG(dbgs() << "    Visiting " << *Inst << "\n");
01231 
01232     NestingDetected |= VisitInstructionBottomUp(Inst, BB, Retains, MyStates);
01233   }
01234 
01235   // If there's a predecessor with an invoke, visit the invoke as if it were
01236   // part of this block, since we can't insert code after an invoke in its own
01237   // block, and we don't want to split critical edges.
01238   for (BBState::edge_iterator PI(MyStates.pred_begin()),
01239        PE(MyStates.pred_end()); PI != PE; ++PI) {
01240     BasicBlock *Pred = *PI;
01241     if (InvokeInst *II = dyn_cast<InvokeInst>(&Pred->back()))
01242       NestingDetected |= VisitInstructionBottomUp(II, BB, Retains, MyStates);
01243   }
01244 
01245   DEBUG(llvm::dbgs() << "\nFinal State:\n" << BBStates[BB] << "\n");
01246 
01247   return NestingDetected;
01248 }
01249 
01250 bool
01251 ObjCARCOpt::VisitInstructionTopDown(Instruction *Inst,
01252                                     DenseMap<Value *, RRInfo> &Releases,
01253                                     BBState &MyStates) {
01254   bool NestingDetected = false;
01255   ARCInstKind Class = GetARCInstKind(Inst);
01256   const Value *Arg = nullptr;
01257 
01258   DEBUG(llvm::dbgs() << "        Class: " << Class << "\n");
01259 
01260   switch (Class) {
01261   case ARCInstKind::RetainBlock:
01262     // In OptimizeIndividualCalls, we have strength reduced all optimizable
01263     // objc_retainBlocks to objc_retains. Thus at this point any
01264     // objc_retainBlocks that we see are not optimizable. We need to break since
01265     // a retain can be a potential use.
01266     break;
01267   case ARCInstKind::Retain:
01268   case ARCInstKind::RetainRV: {
01269     Arg = GetArgRCIdentityRoot(Inst);
01270     TopDownPtrState &S = MyStates.getPtrTopDownState(Arg);
01271     NestingDetected |= S.InitTopDown(Class, Inst);
01272     // A retain can be a potential use; proceed to the generic checking
01273     // code below.
01274     break;
01275   }
01276   case ARCInstKind::Release: {
01277     Arg = GetArgRCIdentityRoot(Inst);
01278     TopDownPtrState &S = MyStates.getPtrTopDownState(Arg);
01279     // Try to form a tentative pair in between this release instruction and the
01280     // top down pointers that we are tracking.
01281     if (S.MatchWithRelease(MDKindCache, Inst)) {
01282       // If we succeed, copy S's RRInfo into the Release -> {Retain Set
01283       // Map}. Then we clear S.
01284       DEBUG(llvm::dbgs() << "        Matching with: " << *Inst << "\n");
01285       Releases[Inst] = S.GetRRInfo();
01286       S.ClearSequenceProgress();
01287     }
01288     break;
01289   }
01290   case ARCInstKind::AutoreleasepoolPop:
01291     // Conservatively, clear MyStates for all known pointers.
01292     MyStates.clearTopDownPointers();
01293     return false;
01294   case ARCInstKind::AutoreleasepoolPush:
01295   case ARCInstKind::None:
01296     // These can not be uses of
01297     return false;
01298   default:
01299     break;
01300   }
01301 
01302   // Consider any other possible effects of this instruction on each
01303   // pointer being tracked.
01304   for (auto MI = MyStates.top_down_ptr_begin(),
01305             ME = MyStates.top_down_ptr_end();
01306        MI != ME; ++MI) {
01307     const Value *Ptr = MI->first;
01308     if (Ptr == Arg)
01309       continue; // Handled above.
01310     TopDownPtrState &S = MI->second;
01311     if (S.HandlePotentialAlterRefCount(Inst, Ptr, PA, Class))
01312       continue;
01313 
01314     S.HandlePotentialUse(Inst, Ptr, PA, Class);
01315   }
01316 
01317   return NestingDetected;
01318 }
01319 
01320 bool
01321 ObjCARCOpt::VisitTopDown(BasicBlock *BB,
01322                          DenseMap<const BasicBlock *, BBState> &BBStates,
01323                          DenseMap<Value *, RRInfo> &Releases) {
01324   DEBUG(dbgs() << "\n== ObjCARCOpt::VisitTopDown ==\n");
01325   bool NestingDetected = false;
01326   BBState &MyStates = BBStates[BB];
01327 
01328   // Merge the states from each predecessor to compute the initial state
01329   // for the current block.
01330   BBState::edge_iterator PI(MyStates.pred_begin()),
01331                          PE(MyStates.pred_end());
01332   if (PI != PE) {
01333     const BasicBlock *Pred = *PI;
01334     DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Pred);
01335     assert(I != BBStates.end());
01336     MyStates.InitFromPred(I->second);
01337     ++PI;
01338     for (; PI != PE; ++PI) {
01339       Pred = *PI;
01340       I = BBStates.find(Pred);
01341       assert(I != BBStates.end());
01342       MyStates.MergePred(I->second);
01343     }
01344   }
01345 
01346   DEBUG(llvm::dbgs() << "Before:\n" << BBStates[BB]  << "\n"
01347                      << "Performing Dataflow:\n");
01348 
01349   // Visit all the instructions, top-down.
01350   for (Instruction &Inst : *BB) {
01351     DEBUG(dbgs() << "    Visiting " << Inst << "\n");
01352 
01353     NestingDetected |= VisitInstructionTopDown(&Inst, Releases, MyStates);
01354   }
01355 
01356   DEBUG(llvm::dbgs() << "\nState Before Checking for CFG Hazards:\n"
01357                      << BBStates[BB] << "\n\n");
01358   CheckForCFGHazards(BB, BBStates, MyStates);
01359   DEBUG(llvm::dbgs() << "Final State:\n" << BBStates[BB] << "\n");
01360   return NestingDetected;
01361 }
01362 
01363 static void
01364 ComputePostOrders(Function &F,
01365                   SmallVectorImpl<BasicBlock *> &PostOrder,
01366                   SmallVectorImpl<BasicBlock *> &ReverseCFGPostOrder,
01367                   unsigned NoObjCARCExceptionsMDKind,
01368                   DenseMap<const BasicBlock *, BBState> &BBStates) {
01369   /// The visited set, for doing DFS walks.
01370   SmallPtrSet<BasicBlock *, 16> Visited;
01371 
01372   // Do DFS, computing the PostOrder.
01373   SmallPtrSet<BasicBlock *, 16> OnStack;
01374   SmallVector<std::pair<BasicBlock *, succ_iterator>, 16> SuccStack;
01375 
01376   // Functions always have exactly one entry block, and we don't have
01377   // any other block that we treat like an entry block.
01378   BasicBlock *EntryBB = &F.getEntryBlock();
01379   BBState &MyStates = BBStates[EntryBB];
01380   MyStates.SetAsEntry();
01381   TerminatorInst *EntryTI = cast<TerminatorInst>(&EntryBB->back());
01382   SuccStack.push_back(std::make_pair(EntryBB, succ_iterator(EntryTI)));
01383   Visited.insert(EntryBB);
01384   OnStack.insert(EntryBB);
01385   do {
01386   dfs_next_succ:
01387     BasicBlock *CurrBB = SuccStack.back().first;
01388     TerminatorInst *TI = cast<TerminatorInst>(&CurrBB->back());
01389     succ_iterator SE(TI, false);
01390 
01391     while (SuccStack.back().second != SE) {
01392       BasicBlock *SuccBB = *SuccStack.back().second++;
01393       if (Visited.insert(SuccBB).second) {
01394         TerminatorInst *TI = cast<TerminatorInst>(&SuccBB->back());
01395         SuccStack.push_back(std::make_pair(SuccBB, succ_iterator(TI)));
01396         BBStates[CurrBB].addSucc(SuccBB);
01397         BBState &SuccStates = BBStates[SuccBB];
01398         SuccStates.addPred(CurrBB);
01399         OnStack.insert(SuccBB);
01400         goto dfs_next_succ;
01401       }
01402 
01403       if (!OnStack.count(SuccBB)) {
01404         BBStates[CurrBB].addSucc(SuccBB);
01405         BBStates[SuccBB].addPred(CurrBB);
01406       }
01407     }
01408     OnStack.erase(CurrBB);
01409     PostOrder.push_back(CurrBB);
01410     SuccStack.pop_back();
01411   } while (!SuccStack.empty());
01412 
01413   Visited.clear();
01414 
01415   // Do reverse-CFG DFS, computing the reverse-CFG PostOrder.
01416   // Functions may have many exits, and there also blocks which we treat
01417   // as exits due to ignored edges.
01418   SmallVector<std::pair<BasicBlock *, BBState::edge_iterator>, 16> PredStack;
01419   for (BasicBlock &ExitBB : F) {
01420     BBState &MyStates = BBStates[&ExitBB];
01421     if (!MyStates.isExit())
01422       continue;
01423 
01424     MyStates.SetAsExit();
01425 
01426     PredStack.push_back(std::make_pair(&ExitBB, MyStates.pred_begin()));
01427     Visited.insert(&ExitBB);
01428     while (!PredStack.empty()) {
01429     reverse_dfs_next_succ:
01430       BBState::edge_iterator PE = BBStates[PredStack.back().first].pred_end();
01431       while (PredStack.back().second != PE) {
01432         BasicBlock *BB = *PredStack.back().second++;
01433         if (Visited.insert(BB).second) {
01434           PredStack.push_back(std::make_pair(BB, BBStates[BB].pred_begin()));
01435           goto reverse_dfs_next_succ;
01436         }
01437       }
01438       ReverseCFGPostOrder.push_back(PredStack.pop_back_val().first);
01439     }
01440   }
01441 }
01442 
01443 // Visit the function both top-down and bottom-up.
01444 bool ObjCARCOpt::Visit(Function &F,
01445                        DenseMap<const BasicBlock *, BBState> &BBStates,
01446                        BlotMapVector<Value *, RRInfo> &Retains,
01447                        DenseMap<Value *, RRInfo> &Releases) {
01448 
01449   // Use reverse-postorder traversals, because we magically know that loops
01450   // will be well behaved, i.e. they won't repeatedly call retain on a single
01451   // pointer without doing a release. We can't use the ReversePostOrderTraversal
01452   // class here because we want the reverse-CFG postorder to consider each
01453   // function exit point, and we want to ignore selected cycle edges.
01454   SmallVector<BasicBlock *, 16> PostOrder;
01455   SmallVector<BasicBlock *, 16> ReverseCFGPostOrder;
01456   ComputePostOrders(F, PostOrder, ReverseCFGPostOrder,
01457                     MDKindCache.get(ARCMDKindID::NoObjCARCExceptions),
01458                     BBStates);
01459 
01460   // Use reverse-postorder on the reverse CFG for bottom-up.
01461   bool BottomUpNestingDetected = false;
01462   for (SmallVectorImpl<BasicBlock *>::const_reverse_iterator I =
01463        ReverseCFGPostOrder.rbegin(), E = ReverseCFGPostOrder.rend();
01464        I != E; ++I)
01465     BottomUpNestingDetected |= VisitBottomUp(*I, BBStates, Retains);
01466 
01467   // Use reverse-postorder for top-down.
01468   bool TopDownNestingDetected = false;
01469   for (SmallVectorImpl<BasicBlock *>::const_reverse_iterator I =
01470        PostOrder.rbegin(), E = PostOrder.rend();
01471        I != E; ++I)
01472     TopDownNestingDetected |= VisitTopDown(*I, BBStates, Releases);
01473 
01474   return TopDownNestingDetected && BottomUpNestingDetected;
01475 }
01476 
01477 /// Move the calls in RetainsToMove and ReleasesToMove.
01478 void ObjCARCOpt::MoveCalls(Value *Arg, RRInfo &RetainsToMove,
01479                            RRInfo &ReleasesToMove,
01480                            BlotMapVector<Value *, RRInfo> &Retains,
01481                            DenseMap<Value *, RRInfo> &Releases,
01482                            SmallVectorImpl<Instruction *> &DeadInsts,
01483                            Module *M) {
01484   Type *ArgTy = Arg->getType();
01485   Type *ParamTy = PointerType::getUnqual(Type::getInt8Ty(ArgTy->getContext()));
01486 
01487   DEBUG(dbgs() << "== ObjCARCOpt::MoveCalls ==\n");
01488 
01489   // Insert the new retain and release calls.
01490   for (Instruction *InsertPt : ReleasesToMove.ReverseInsertPts) {
01491     Value *MyArg = ArgTy == ParamTy ? Arg :
01492                    new BitCastInst(Arg, ParamTy, "", InsertPt);
01493     Constant *Decl = EP.get(ARCRuntimeEntryPointKind::Retain);
01494     CallInst *Call = CallInst::Create(Decl, MyArg, "", InsertPt);
01495     Call->setDoesNotThrow();
01496     Call->setTailCall();
01497 
01498     DEBUG(dbgs() << "Inserting new Retain: " << *Call << "\n"
01499                     "At insertion point: " << *InsertPt << "\n");
01500   }
01501   for (Instruction *InsertPt : RetainsToMove.ReverseInsertPts) {
01502     Value *MyArg = ArgTy == ParamTy ? Arg :
01503                    new BitCastInst(Arg, ParamTy, "", InsertPt);
01504     Constant *Decl = EP.get(ARCRuntimeEntryPointKind::Release);
01505     CallInst *Call = CallInst::Create(Decl, MyArg, "", InsertPt);
01506     // Attach a clang.imprecise_release metadata tag, if appropriate.
01507     if (MDNode *M = ReleasesToMove.ReleaseMetadata)
01508       Call->setMetadata(MDKindCache.get(ARCMDKindID::ImpreciseRelease), M);
01509     Call->setDoesNotThrow();
01510     if (ReleasesToMove.IsTailCallRelease)
01511       Call->setTailCall();
01512 
01513     DEBUG(dbgs() << "Inserting new Release: " << *Call << "\n"
01514                     "At insertion point: " << *InsertPt << "\n");
01515   }
01516 
01517   // Delete the original retain and release calls.
01518   for (Instruction *OrigRetain : RetainsToMove.Calls) {
01519     Retains.blot(OrigRetain);
01520     DeadInsts.push_back(OrigRetain);
01521     DEBUG(dbgs() << "Deleting retain: " << *OrigRetain << "\n");
01522   }
01523   for (Instruction *OrigRelease : ReleasesToMove.Calls) {
01524     Releases.erase(OrigRelease);
01525     DeadInsts.push_back(OrigRelease);
01526     DEBUG(dbgs() << "Deleting release: " << *OrigRelease << "\n");
01527   }
01528 
01529 }
01530 
01531 bool ObjCARCOpt::PairUpRetainsAndReleases(
01532     DenseMap<const BasicBlock *, BBState> &BBStates,
01533     BlotMapVector<Value *, RRInfo> &Retains,
01534     DenseMap<Value *, RRInfo> &Releases, Module *M,
01535     SmallVectorImpl<Instruction *> &NewRetains,
01536     SmallVectorImpl<Instruction *> &NewReleases,
01537     SmallVectorImpl<Instruction *> &DeadInsts, RRInfo &RetainsToMove,
01538     RRInfo &ReleasesToMove, Value *Arg, bool KnownSafe,
01539     bool &AnyPairsCompletelyEliminated) {
01540   // If a pair happens in a region where it is known that the reference count
01541   // is already incremented, we can similarly ignore possible decrements unless
01542   // we are dealing with a retainable object with multiple provenance sources.
01543   bool KnownSafeTD = true, KnownSafeBU = true;
01544   bool MultipleOwners = false;
01545   bool CFGHazardAfflicted = false;
01546 
01547   // Connect the dots between the top-down-collected RetainsToMove and
01548   // bottom-up-collected ReleasesToMove to form sets of related calls.
01549   // This is an iterative process so that we connect multiple releases
01550   // to multiple retains if needed.
01551   unsigned OldDelta = 0;
01552   unsigned NewDelta = 0;
01553   unsigned OldCount = 0;
01554   unsigned NewCount = 0;
01555   bool FirstRelease = true;
01556   for (;;) {
01557     for (SmallVectorImpl<Instruction *>::const_iterator
01558            NI = NewRetains.begin(), NE = NewRetains.end(); NI != NE; ++NI) {
01559       Instruction *NewRetain = *NI;
01560       auto It = Retains.find(NewRetain);
01561       assert(It != Retains.end());
01562       const RRInfo &NewRetainRRI = It->second;
01563       KnownSafeTD &= NewRetainRRI.KnownSafe;
01564       MultipleOwners =
01565         MultipleOwners || MultiOwnersSet.count(GetArgRCIdentityRoot(NewRetain));
01566       for (Instruction *NewRetainRelease : NewRetainRRI.Calls) {
01567         auto Jt = Releases.find(NewRetainRelease);
01568         if (Jt == Releases.end())
01569           return false;
01570         const RRInfo &NewRetainReleaseRRI = Jt->second;
01571 
01572         // If the release does not have a reference to the retain as well,
01573         // something happened which is unaccounted for. Do not do anything.
01574         //
01575         // This can happen if we catch an additive overflow during path count
01576         // merging.
01577         if (!NewRetainReleaseRRI.Calls.count(NewRetain))
01578           return false;
01579 
01580         if (ReleasesToMove.Calls.insert(NewRetainRelease).second) {
01581 
01582           // If we overflow when we compute the path count, don't remove/move
01583           // anything.
01584           const BBState &NRRBBState = BBStates[NewRetainRelease->getParent()];
01585           unsigned PathCount = BBState::OverflowOccurredValue;
01586           if (NRRBBState.GetAllPathCountWithOverflow(PathCount))
01587             return false;
01588           assert(PathCount != BBState::OverflowOccurredValue &&
01589                  "PathCount at this point can not be "
01590                  "OverflowOccurredValue.");
01591           OldDelta -= PathCount;
01592 
01593           // Merge the ReleaseMetadata and IsTailCallRelease values.
01594           if (FirstRelease) {
01595             ReleasesToMove.ReleaseMetadata =
01596               NewRetainReleaseRRI.ReleaseMetadata;
01597             ReleasesToMove.IsTailCallRelease =
01598               NewRetainReleaseRRI.IsTailCallRelease;
01599             FirstRelease = false;
01600           } else {
01601             if (ReleasesToMove.ReleaseMetadata !=
01602                 NewRetainReleaseRRI.ReleaseMetadata)
01603               ReleasesToMove.ReleaseMetadata = nullptr;
01604             if (ReleasesToMove.IsTailCallRelease !=
01605                 NewRetainReleaseRRI.IsTailCallRelease)
01606               ReleasesToMove.IsTailCallRelease = false;
01607           }
01608 
01609           // Collect the optimal insertion points.
01610           if (!KnownSafe)
01611             for (Instruction *RIP : NewRetainReleaseRRI.ReverseInsertPts) {
01612               if (ReleasesToMove.ReverseInsertPts.insert(RIP).second) {
01613                 // If we overflow when we compute the path count, don't
01614                 // remove/move anything.
01615                 const BBState &RIPBBState = BBStates[RIP->getParent()];
01616                 PathCount = BBState::OverflowOccurredValue;
01617                 if (RIPBBState.GetAllPathCountWithOverflow(PathCount))
01618                   return false;
01619                 assert(PathCount != BBState::OverflowOccurredValue &&
01620                        "PathCount at this point can not be "
01621                        "OverflowOccurredValue.");
01622                 NewDelta -= PathCount;
01623               }
01624             }
01625           NewReleases.push_back(NewRetainRelease);
01626         }
01627       }
01628     }
01629     NewRetains.clear();
01630     if (NewReleases.empty()) break;
01631 
01632     // Back the other way.
01633     for (SmallVectorImpl<Instruction *>::const_iterator
01634            NI = NewReleases.begin(), NE = NewReleases.end(); NI != NE; ++NI) {
01635       Instruction *NewRelease = *NI;
01636       auto It = Releases.find(NewRelease);
01637       assert(It != Releases.end());
01638       const RRInfo &NewReleaseRRI = It->second;
01639       KnownSafeBU &= NewReleaseRRI.KnownSafe;
01640       CFGHazardAfflicted |= NewReleaseRRI.CFGHazardAfflicted;
01641       for (Instruction *NewReleaseRetain : NewReleaseRRI.Calls) {
01642         auto Jt = Retains.find(NewReleaseRetain);
01643         if (Jt == Retains.end())
01644           return false;
01645         const RRInfo &NewReleaseRetainRRI = Jt->second;
01646 
01647         // If the retain does not have a reference to the release as well,
01648         // something happened which is unaccounted for. Do not do anything.
01649         //
01650         // This can happen if we catch an additive overflow during path count
01651         // merging.
01652         if (!NewReleaseRetainRRI.Calls.count(NewRelease))
01653           return false;
01654 
01655         if (RetainsToMove.Calls.insert(NewReleaseRetain).second) {
01656           // If we overflow when we compute the path count, don't remove/move
01657           // anything.
01658           const BBState &NRRBBState = BBStates[NewReleaseRetain->getParent()];
01659           unsigned PathCount = BBState::OverflowOccurredValue;
01660           if (NRRBBState.GetAllPathCountWithOverflow(PathCount))
01661             return false;
01662           assert(PathCount != BBState::OverflowOccurredValue &&
01663                  "PathCount at this point can not be "
01664                  "OverflowOccurredValue.");
01665           OldDelta += PathCount;
01666           OldCount += PathCount;
01667 
01668           // Collect the optimal insertion points.
01669           if (!KnownSafe)
01670             for (Instruction *RIP : NewReleaseRetainRRI.ReverseInsertPts) {
01671               if (RetainsToMove.ReverseInsertPts.insert(RIP).second) {
01672                 // If we overflow when we compute the path count, don't
01673                 // remove/move anything.
01674                 const BBState &RIPBBState = BBStates[RIP->getParent()];
01675 
01676                 PathCount = BBState::OverflowOccurredValue;
01677                 if (RIPBBState.GetAllPathCountWithOverflow(PathCount))
01678                   return false;
01679                 assert(PathCount != BBState::OverflowOccurredValue &&
01680                        "PathCount at this point can not be "
01681                        "OverflowOccurredValue.");
01682                 NewDelta += PathCount;
01683                 NewCount += PathCount;
01684               }
01685             }
01686           NewRetains.push_back(NewReleaseRetain);
01687         }
01688       }
01689     }
01690     NewReleases.clear();
01691     if (NewRetains.empty()) break;
01692   }
01693 
01694   // We can only remove pointers if we are known safe in both directions.
01695   bool UnconditionallySafe = KnownSafeTD && KnownSafeBU;
01696   if (UnconditionallySafe) {
01697     RetainsToMove.ReverseInsertPts.clear();
01698     ReleasesToMove.ReverseInsertPts.clear();
01699     NewCount = 0;
01700   } else {
01701     // Determine whether the new insertion points we computed preserve the
01702     // balance of retain and release calls through the program.
01703     // TODO: If the fully aggressive solution isn't valid, try to find a
01704     // less aggressive solution which is.
01705     if (NewDelta != 0)
01706       return false;
01707 
01708     // At this point, we are not going to remove any RR pairs, but we still are
01709     // able to move RR pairs. If one of our pointers is afflicted with
01710     // CFGHazards, we cannot perform such code motion so exit early.
01711     const bool WillPerformCodeMotion = RetainsToMove.ReverseInsertPts.size() ||
01712       ReleasesToMove.ReverseInsertPts.size();
01713     if (CFGHazardAfflicted && WillPerformCodeMotion)
01714       return false;
01715   }
01716 
01717   // Determine whether the original call points are balanced in the retain and
01718   // release calls through the program. If not, conservatively don't touch
01719   // them.
01720   // TODO: It's theoretically possible to do code motion in this case, as
01721   // long as the existing imbalances are maintained.
01722   if (OldDelta != 0)
01723     return false;
01724 
01725   Changed = true;
01726   assert(OldCount != 0 && "Unreachable code?");
01727   NumRRs += OldCount - NewCount;
01728   // Set to true if we completely removed any RR pairs.
01729   AnyPairsCompletelyEliminated = NewCount == 0;
01730 
01731   // We can move calls!
01732   return true;
01733 }
01734 
01735 /// Identify pairings between the retains and releases, and delete and/or move
01736 /// them.
01737 bool ObjCARCOpt::PerformCodePlacement(
01738     DenseMap<const BasicBlock *, BBState> &BBStates,
01739     BlotMapVector<Value *, RRInfo> &Retains,
01740     DenseMap<Value *, RRInfo> &Releases, Module *M) {
01741   DEBUG(dbgs() << "\n== ObjCARCOpt::PerformCodePlacement ==\n");
01742 
01743   bool AnyPairsCompletelyEliminated = false;
01744   RRInfo RetainsToMove;
01745   RRInfo ReleasesToMove;
01746   SmallVector<Instruction *, 4> NewRetains;
01747   SmallVector<Instruction *, 4> NewReleases;
01748   SmallVector<Instruction *, 8> DeadInsts;
01749 
01750   // Visit each retain.
01751   for (BlotMapVector<Value *, RRInfo>::const_iterator I = Retains.begin(),
01752                                                       E = Retains.end();
01753        I != E; ++I) {
01754     Value *V = I->first;
01755     if (!V) continue; // blotted
01756 
01757     Instruction *Retain = cast<Instruction>(V);
01758 
01759     DEBUG(dbgs() << "Visiting: " << *Retain << "\n");
01760 
01761     Value *Arg = GetArgRCIdentityRoot(Retain);
01762 
01763     // If the object being released is in static or stack storage, we know it's
01764     // not being managed by ObjC reference counting, so we can delete pairs
01765     // regardless of what possible decrements or uses lie between them.
01766     bool KnownSafe = isa<Constant>(Arg) || isa<AllocaInst>(Arg);
01767 
01768     // A constant pointer can't be pointing to an object on the heap. It may
01769     // be reference-counted, but it won't be deleted.
01770     if (const LoadInst *LI = dyn_cast<LoadInst>(Arg))
01771       if (const GlobalVariable *GV =
01772             dyn_cast<GlobalVariable>(
01773               GetRCIdentityRoot(LI->getPointerOperand())))
01774         if (GV->isConstant())
01775           KnownSafe = true;
01776 
01777     // Connect the dots between the top-down-collected RetainsToMove and
01778     // bottom-up-collected ReleasesToMove to form sets of related calls.
01779     NewRetains.push_back(Retain);
01780     bool PerformMoveCalls = PairUpRetainsAndReleases(
01781         BBStates, Retains, Releases, M, NewRetains, NewReleases, DeadInsts,
01782         RetainsToMove, ReleasesToMove, Arg, KnownSafe,
01783         AnyPairsCompletelyEliminated);
01784 
01785     if (PerformMoveCalls) {
01786       // Ok, everything checks out and we're all set. Let's move/delete some
01787       // code!
01788       MoveCalls(Arg, RetainsToMove, ReleasesToMove,
01789                 Retains, Releases, DeadInsts, M);
01790     }
01791 
01792     // Clean up state for next retain.
01793     NewReleases.clear();
01794     NewRetains.clear();
01795     RetainsToMove.clear();
01796     ReleasesToMove.clear();
01797   }
01798 
01799   // Now that we're done moving everything, we can delete the newly dead
01800   // instructions, as we no longer need them as insert points.
01801   while (!DeadInsts.empty())
01802     EraseInstruction(DeadInsts.pop_back_val());
01803 
01804   return AnyPairsCompletelyEliminated;
01805 }
01806 
01807 /// Weak pointer optimizations.
01808 void ObjCARCOpt::OptimizeWeakCalls(Function &F) {
01809   DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeWeakCalls ==\n");
01810 
01811   // First, do memdep-style RLE and S2L optimizations. We can't use memdep
01812   // itself because it uses AliasAnalysis and we need to do provenance
01813   // queries instead.
01814   for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
01815     Instruction *Inst = &*I++;
01816 
01817     DEBUG(dbgs() << "Visiting: " << *Inst << "\n");
01818 
01819     ARCInstKind Class = GetBasicARCInstKind(Inst);
01820     if (Class != ARCInstKind::LoadWeak &&
01821         Class != ARCInstKind::LoadWeakRetained)
01822       continue;
01823 
01824     // Delete objc_loadWeak calls with no users.
01825     if (Class == ARCInstKind::LoadWeak && Inst->use_empty()) {
01826       Inst->eraseFromParent();
01827       continue;
01828     }
01829 
01830     // TODO: For now, just look for an earlier available version of this value
01831     // within the same block. Theoretically, we could do memdep-style non-local
01832     // analysis too, but that would want caching. A better approach would be to
01833     // use the technique that EarlyCSE uses.
01834     inst_iterator Current = std::prev(I);
01835     BasicBlock *CurrentBB = &*Current.getBasicBlockIterator();
01836     for (BasicBlock::iterator B = CurrentBB->begin(),
01837                               J = Current.getInstructionIterator();
01838          J != B; --J) {
01839       Instruction *EarlierInst = &*std::prev(J);
01840       ARCInstKind EarlierClass = GetARCInstKind(EarlierInst);
01841       switch (EarlierClass) {
01842       case ARCInstKind::LoadWeak:
01843       case ARCInstKind::LoadWeakRetained: {
01844         // If this is loading from the same pointer, replace this load's value
01845         // with that one.
01846         CallInst *Call = cast<CallInst>(Inst);
01847         CallInst *EarlierCall = cast<CallInst>(EarlierInst);
01848         Value *Arg = Call->getArgOperand(0);
01849         Value *EarlierArg = EarlierCall->getArgOperand(0);
01850         switch (PA.getAA()->alias(Arg, EarlierArg)) {
01851         case MustAlias:
01852           Changed = true;
01853           // If the load has a builtin retain, insert a plain retain for it.
01854           if (Class == ARCInstKind::LoadWeakRetained) {
01855             Constant *Decl = EP.get(ARCRuntimeEntryPointKind::Retain);
01856             CallInst *CI = CallInst::Create(Decl, EarlierCall, "", Call);
01857             CI->setTailCall();
01858           }
01859           // Zap the fully redundant load.
01860           Call->replaceAllUsesWith(EarlierCall);
01861           Call->eraseFromParent();
01862           goto clobbered;
01863         case MayAlias:
01864         case PartialAlias:
01865           goto clobbered;
01866         case NoAlias:
01867           break;
01868         }
01869         break;
01870       }
01871       case ARCInstKind::StoreWeak:
01872       case ARCInstKind::InitWeak: {
01873         // If this is storing to the same pointer and has the same size etc.
01874         // replace this load's value with the stored value.
01875         CallInst *Call = cast<CallInst>(Inst);
01876         CallInst *EarlierCall = cast<CallInst>(EarlierInst);
01877         Value *Arg = Call->getArgOperand(0);
01878         Value *EarlierArg = EarlierCall->getArgOperand(0);
01879         switch (PA.getAA()->alias(Arg, EarlierArg)) {
01880         case MustAlias:
01881           Changed = true;
01882           // If the load has a builtin retain, insert a plain retain for it.
01883           if (Class == ARCInstKind::LoadWeakRetained) {
01884             Constant *Decl = EP.get(ARCRuntimeEntryPointKind::Retain);
01885             CallInst *CI = CallInst::Create(Decl, EarlierCall, "", Call);
01886             CI->setTailCall();
01887           }
01888           // Zap the fully redundant load.
01889           Call->replaceAllUsesWith(EarlierCall->getArgOperand(1));
01890           Call->eraseFromParent();
01891           goto clobbered;
01892         case MayAlias:
01893         case PartialAlias:
01894           goto clobbered;
01895         case NoAlias:
01896           break;
01897         }
01898         break;
01899       }
01900       case ARCInstKind::MoveWeak:
01901       case ARCInstKind::CopyWeak:
01902         // TOOD: Grab the copied value.
01903         goto clobbered;
01904       case ARCInstKind::AutoreleasepoolPush:
01905       case ARCInstKind::None:
01906       case ARCInstKind::IntrinsicUser:
01907       case ARCInstKind::User:
01908         // Weak pointers are only modified through the weak entry points
01909         // (and arbitrary calls, which could call the weak entry points).
01910         break;
01911       default:
01912         // Anything else could modify the weak pointer.
01913         goto clobbered;
01914       }
01915     }
01916   clobbered:;
01917   }
01918 
01919   // Then, for each destroyWeak with an alloca operand, check to see if
01920   // the alloca and all its users can be zapped.
01921   for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
01922     Instruction *Inst = &*I++;
01923     ARCInstKind Class = GetBasicARCInstKind(Inst);
01924     if (Class != ARCInstKind::DestroyWeak)
01925       continue;
01926 
01927     CallInst *Call = cast<CallInst>(Inst);
01928     Value *Arg = Call->getArgOperand(0);
01929     if (AllocaInst *Alloca = dyn_cast<AllocaInst>(Arg)) {
01930       for (User *U : Alloca->users()) {
01931         const Instruction *UserInst = cast<Instruction>(U);
01932         switch (GetBasicARCInstKind(UserInst)) {
01933         case ARCInstKind::InitWeak:
01934         case ARCInstKind::StoreWeak:
01935         case ARCInstKind::DestroyWeak:
01936           continue;
01937         default:
01938           goto done;
01939         }
01940       }
01941       Changed = true;
01942       for (auto UI = Alloca->user_begin(), UE = Alloca->user_end(); UI != UE;) {
01943         CallInst *UserInst = cast<CallInst>(*UI++);
01944         switch (GetBasicARCInstKind(UserInst)) {
01945         case ARCInstKind::InitWeak:
01946         case ARCInstKind::StoreWeak:
01947           // These functions return their second argument.
01948           UserInst->replaceAllUsesWith(UserInst->getArgOperand(1));
01949           break;
01950         case ARCInstKind::DestroyWeak:
01951           // No return value.
01952           break;
01953         default:
01954           llvm_unreachable("alloca really is used!");
01955         }
01956         UserInst->eraseFromParent();
01957       }
01958       Alloca->eraseFromParent();
01959     done:;
01960     }
01961   }
01962 }
01963 
01964 /// Identify program paths which execute sequences of retains and releases which
01965 /// can be eliminated.
01966 bool ObjCARCOpt::OptimizeSequences(Function &F) {
01967   // Releases, Retains - These are used to store the results of the main flow
01968   // analysis. These use Value* as the key instead of Instruction* so that the
01969   // map stays valid when we get around to rewriting code and calls get
01970   // replaced by arguments.
01971   DenseMap<Value *, RRInfo> Releases;
01972   BlotMapVector<Value *, RRInfo> Retains;
01973 
01974   // This is used during the traversal of the function to track the
01975   // states for each identified object at each block.
01976   DenseMap<const BasicBlock *, BBState> BBStates;
01977 
01978   // Analyze the CFG of the function, and all instructions.
01979   bool NestingDetected = Visit(F, BBStates, Retains, Releases);
01980 
01981   // Transform.
01982   bool AnyPairsCompletelyEliminated = PerformCodePlacement(BBStates, Retains,
01983                                                            Releases,
01984                                                            F.getParent());
01985 
01986   // Cleanup.
01987   MultiOwnersSet.clear();
01988 
01989   return AnyPairsCompletelyEliminated && NestingDetected;
01990 }
01991 
01992 /// Check if there is a dependent call earlier that does not have anything in
01993 /// between the Retain and the call that can affect the reference count of their
01994 /// shared pointer argument. Note that Retain need not be in BB.
01995 static bool
01996 HasSafePathToPredecessorCall(const Value *Arg, Instruction *Retain,
01997                              SmallPtrSetImpl<Instruction *> &DepInsts,
01998                              SmallPtrSetImpl<const BasicBlock *> &Visited,
01999                              ProvenanceAnalysis &PA) {
02000   FindDependencies(CanChangeRetainCount, Arg, Retain->getParent(), Retain,
02001                    DepInsts, Visited, PA);
02002   if (DepInsts.size() != 1)
02003     return false;
02004 
02005   auto *Call = dyn_cast_or_null<CallInst>(*DepInsts.begin());
02006 
02007   // Check that the pointer is the return value of the call.
02008   if (!Call || Arg != Call)
02009     return false;
02010 
02011   // Check that the call is a regular call.
02012   ARCInstKind Class = GetBasicARCInstKind(Call);
02013   return Class == ARCInstKind::CallOrUser || Class == ARCInstKind::Call;
02014 }
02015 
02016 /// Find a dependent retain that precedes the given autorelease for which there
02017 /// is nothing in between the two instructions that can affect the ref count of
02018 /// Arg.
02019 static CallInst *
02020 FindPredecessorRetainWithSafePath(const Value *Arg, BasicBlock *BB,
02021                                   Instruction *Autorelease,
02022                                   SmallPtrSetImpl<Instruction *> &DepInsts,
02023                                   SmallPtrSetImpl<const BasicBlock *> &Visited,
02024                                   ProvenanceAnalysis &PA) {
02025   FindDependencies(CanChangeRetainCount, Arg,
02026                    BB, Autorelease, DepInsts, Visited, PA);
02027   if (DepInsts.size() != 1)
02028     return nullptr;
02029 
02030   auto *Retain = dyn_cast_or_null<CallInst>(*DepInsts.begin());
02031 
02032   // Check that we found a retain with the same argument.
02033   if (!Retain || !IsRetain(GetBasicARCInstKind(Retain)) ||
02034       GetArgRCIdentityRoot(Retain) != Arg) {
02035     return nullptr;
02036   }
02037 
02038   return Retain;
02039 }
02040 
02041 /// Look for an ``autorelease'' instruction dependent on Arg such that there are
02042 /// no instructions dependent on Arg that need a positive ref count in between
02043 /// the autorelease and the ret.
02044 static CallInst *
02045 FindPredecessorAutoreleaseWithSafePath(const Value *Arg, BasicBlock *BB,
02046                                        ReturnInst *Ret,
02047                                        SmallPtrSetImpl<Instruction *> &DepInsts,
02048                                        SmallPtrSetImpl<const BasicBlock *> &V,
02049                                        ProvenanceAnalysis &PA) {
02050   FindDependencies(NeedsPositiveRetainCount, Arg,
02051                    BB, Ret, DepInsts, V, PA);
02052   if (DepInsts.size() != 1)
02053     return nullptr;
02054 
02055   auto *Autorelease = dyn_cast_or_null<CallInst>(*DepInsts.begin());
02056   if (!Autorelease)
02057     return nullptr;
02058   ARCInstKind AutoreleaseClass = GetBasicARCInstKind(Autorelease);
02059   if (!IsAutorelease(AutoreleaseClass))
02060     return nullptr;
02061   if (GetArgRCIdentityRoot(Autorelease) != Arg)
02062     return nullptr;
02063 
02064   return Autorelease;
02065 }
02066 
02067 /// Look for this pattern:
02068 /// \code
02069 ///    %call = call i8* @something(...)
02070 ///    %2 = call i8* @objc_retain(i8* %call)
02071 ///    %3 = call i8* @objc_autorelease(i8* %2)
02072 ///    ret i8* %3
02073 /// \endcode
02074 /// And delete the retain and autorelease.
02075 void ObjCARCOpt::OptimizeReturns(Function &F) {
02076   if (!F.getReturnType()->isPointerTy())
02077     return;
02078 
02079   DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeReturns ==\n");
02080 
02081   SmallPtrSet<Instruction *, 4> DependingInstructions;
02082   SmallPtrSet<const BasicBlock *, 4> Visited;
02083   for (BasicBlock &BB: F) {
02084     ReturnInst *Ret = dyn_cast<ReturnInst>(&BB.back());
02085 
02086     DEBUG(dbgs() << "Visiting: " << *Ret << "\n");
02087 
02088     if (!Ret)
02089       continue;
02090 
02091     const Value *Arg = GetRCIdentityRoot(Ret->getOperand(0));
02092 
02093     // Look for an ``autorelease'' instruction that is a predecessor of Ret and
02094     // dependent on Arg such that there are no instructions dependent on Arg
02095     // that need a positive ref count in between the autorelease and Ret.
02096     CallInst *Autorelease = FindPredecessorAutoreleaseWithSafePath(
02097         Arg, &BB, Ret, DependingInstructions, Visited, PA);
02098     DependingInstructions.clear();
02099     Visited.clear();
02100 
02101     if (!Autorelease)
02102       continue;
02103 
02104     CallInst *Retain = FindPredecessorRetainWithSafePath(
02105         Arg, &BB, Autorelease, DependingInstructions, Visited, PA);
02106     DependingInstructions.clear();
02107     Visited.clear();
02108 
02109     if (!Retain)
02110       continue;
02111 
02112     // Check that there is nothing that can affect the reference count
02113     // between the retain and the call.  Note that Retain need not be in BB.
02114     bool HasSafePathToCall = HasSafePathToPredecessorCall(Arg, Retain,
02115                                                           DependingInstructions,
02116                                                           Visited, PA);
02117     DependingInstructions.clear();
02118     Visited.clear();
02119 
02120     if (!HasSafePathToCall)
02121       continue;
02122 
02123     // If so, we can zap the retain and autorelease.
02124     Changed = true;
02125     ++NumRets;
02126     DEBUG(dbgs() << "Erasing: " << *Retain << "\nErasing: "
02127           << *Autorelease << "\n");
02128     EraseInstruction(Retain);
02129     EraseInstruction(Autorelease);
02130   }
02131 }
02132 
02133 #ifndef NDEBUG
02134 void
02135 ObjCARCOpt::GatherStatistics(Function &F, bool AfterOptimization) {
02136   llvm::Statistic &NumRetains =
02137     AfterOptimization? NumRetainsAfterOpt : NumRetainsBeforeOpt;
02138   llvm::Statistic &NumReleases =
02139     AfterOptimization? NumReleasesAfterOpt : NumReleasesBeforeOpt;
02140 
02141   for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
02142     Instruction *Inst = &*I++;
02143     switch (GetBasicARCInstKind(Inst)) {
02144     default:
02145       break;
02146     case ARCInstKind::Retain:
02147       ++NumRetains;
02148       break;
02149     case ARCInstKind::Release:
02150       ++NumReleases;
02151       break;
02152     }
02153   }
02154 }
02155 #endif
02156 
02157 bool ObjCARCOpt::doInitialization(Module &M) {
02158   if (!EnableARCOpts)
02159     return false;
02160 
02161   // If nothing in the Module uses ARC, don't do anything.
02162   Run = ModuleHasARC(M);
02163   if (!Run)
02164     return false;
02165 
02166   // Intuitively, objc_retain and others are nocapture, however in practice
02167   // they are not, because they return their argument value. And objc_release
02168   // calls finalizers which can have arbitrary side effects.
02169   MDKindCache.init(&M);
02170 
02171   // Initialize our runtime entry point cache.
02172   EP.init(&M);
02173 
02174   return false;
02175 }
02176 
02177 bool ObjCARCOpt::runOnFunction(Function &F) {
02178   if (!EnableARCOpts)
02179     return false;
02180 
02181   // If nothing in the Module uses ARC, don't do anything.
02182   if (!Run)
02183     return false;
02184 
02185   Changed = false;
02186 
02187   DEBUG(dbgs() << "<<< ObjCARCOpt: Visiting Function: " << F.getName() << " >>>"
02188         "\n");
02189 
02190   PA.setAA(&getAnalysis<AAResultsWrapperPass>().getAAResults());
02191 
02192 #ifndef NDEBUG
02193   if (AreStatisticsEnabled()) {
02194     GatherStatistics(F, false);
02195   }
02196 #endif
02197 
02198   // This pass performs several distinct transformations. As a compile-time aid
02199   // when compiling code that isn't ObjC, skip these if the relevant ObjC
02200   // library functions aren't declared.
02201 
02202   // Preliminary optimizations. This also computes UsedInThisFunction.
02203   OptimizeIndividualCalls(F);
02204 
02205   // Optimizations for weak pointers.
02206   if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::LoadWeak)) |
02207                             (1 << unsigned(ARCInstKind::LoadWeakRetained)) |
02208                             (1 << unsigned(ARCInstKind::StoreWeak)) |
02209                             (1 << unsigned(ARCInstKind::InitWeak)) |
02210                             (1 << unsigned(ARCInstKind::CopyWeak)) |
02211                             (1 << unsigned(ARCInstKind::MoveWeak)) |
02212                             (1 << unsigned(ARCInstKind::DestroyWeak))))
02213     OptimizeWeakCalls(F);
02214 
02215   // Optimizations for retain+release pairs.
02216   if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::Retain)) |
02217                             (1 << unsigned(ARCInstKind::RetainRV)) |
02218                             (1 << unsigned(ARCInstKind::RetainBlock))))
02219     if (UsedInThisFunction & (1 << unsigned(ARCInstKind::Release)))
02220       // Run OptimizeSequences until it either stops making changes or
02221       // no retain+release pair nesting is detected.
02222       while (OptimizeSequences(F)) {}
02223 
02224   // Optimizations if objc_autorelease is used.
02225   if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::Autorelease)) |
02226                             (1 << unsigned(ARCInstKind::AutoreleaseRV))))
02227     OptimizeReturns(F);
02228 
02229   // Gather statistics after optimization.
02230 #ifndef NDEBUG
02231   if (AreStatisticsEnabled()) {
02232     GatherStatistics(F, true);
02233   }
02234 #endif
02235 
02236   DEBUG(dbgs() << "\n");
02237 
02238   return Changed;
02239 }
02240 
02241 void ObjCARCOpt::releaseMemory() {
02242   PA.clear();
02243 }
02244 
02245 /// @}
02246 ///