ObjCARC.cpp

         UI != UE; ++UI) {
      const User *Ur = *UI;
      if (isa<StoreInst>(Ur)) {
        if (UI.getOperandNo() == 0)
          // The pointer is stored.
          return true;
        // The pointed is stored through.
        continue;
      }
      if (isa<CallInst>(Ur))
        // The pointer is passed as an argument, ignore this.
        continue;
      if (isa<PtrToIntInst>(P))
        // Assume the worst.
        return true;
      if (Visited.insert(Ur))
        Worklist.push_back(Ur);
    }
  } while (!Worklist.empty());

  // Everything checked out.
  return false;
}

bool ProvenanceAnalysis::relatedCheck(const Value *A, const Value *B) {
  // Skip past provenance pass-throughs.
  A = GetUnderlyingObjCPtr(A);
  B = GetUnderlyingObjCPtr(B);

  // Quick check.
  if (A == B)
    return true;

  // Ask regular AliasAnalysis, for a first approximation.
  switch (AA->alias(A, B)) {
  case AliasAnalysis::NoAlias:
    return false;
  case AliasAnalysis::MustAlias:
  case AliasAnalysis::PartialAlias:
    return true;
  case AliasAnalysis::MayAlias:
    break;
  }

  bool AIsIdentified = IsObjCIdentifiedObject(A);
  bool BIsIdentified = IsObjCIdentifiedObject(B);

  // An ObjC-Identified object can't alias a load if it is never locally stored.
  if (AIsIdentified) {
    if (BIsIdentified) {
      // If both pointers have provenance, they can be directly compared.
      if (A != B)
        return false;
    } else {
      if (isa<LoadInst>(B))
        return isStoredObjCPointer(A);
    }
  } else {
    if (BIsIdentified && isa<LoadInst>(A))
      return isStoredObjCPointer(B);
  }

   // Special handling for PHI and Select.
  if (const PHINode *PN = dyn_cast<PHINode>(A))
    return relatedPHI(PN, B);
  if (const PHINode *PN = dyn_cast<PHINode>(B))
    return relatedPHI(PN, A);
  if (const SelectInst *S = dyn_cast<SelectInst>(A))
    return relatedSelect(S, B);
  if (const SelectInst *S = dyn_cast<SelectInst>(B))
    return relatedSelect(S, A);

  // Conservative.
  return true;
}

bool ProvenanceAnalysis::related(const Value *A, const Value *B) {
  // Begin by inserting a conservative value into the map. If the insertion
  // fails, we have the answer already. If it succeeds, leave it there until we
  // compute the real answer to guard against recursive queries.
  if (A > B) std::swap(A, B);
  std::pair<CachedResultsTy::iterator, bool> Pair =
    CachedResults.insert(std::make_pair(ValuePairTy(A, B), true));
  if (!Pair.second)
    return Pair.first->second;

  bool Result = relatedCheck(A, B);
  CachedResults[ValuePairTy(A, B)] = Result;
  return Result;
}

namespace {
  // Sequence - A sequence of states that a pointer may go through in which an
  // objc_retain and objc_release are actually needed.
  enum Sequence {
    S_None,
    S_Retain,         ///< objc_retain(x)
    S_CanRelease,     ///< foo(x) -- x could possibly see a ref count decrement
    S_Use,            ///< any use of x
    S_Stop,           ///< like S_Release, but code motion is stopped
    S_Release,        ///< objc_release(x)
    S_MovableRelease  ///< objc_release(x), !clang.imprecise_release
  };
}

static Sequence MergeSeqs(Sequence A, Sequence B, bool TopDown) {
  // The easy cases.
  if (A == B)
    return A;
  if (A == S_None || B == S_None)
    return S_None;

  if (A > B) std::swap(A, B);
  if (TopDown) {
    // Choose the side which is further along in the sequence.
    if ((A == S_Retain || A == S_CanRelease) &&
        (B == S_CanRelease || B == S_Use))
      return B;
  } else {
    // Choose the side which is further along in the sequence.
    if ((A == S_Use || A == S_CanRelease) &&
        (B == S_Use || B == S_Release || B == S_Stop || B == S_MovableRelease))
      return A;
    // If both sides are releases, choose the more conservative one.
    if (A == S_Stop && (B == S_Release || B == S_MovableRelease))
      return A;
    if (A == S_Release && B == S_MovableRelease)
      return A;
  }

  return S_None;
}

namespace {
  /// RRInfo - Unidirectional information about either a
  /// retain-decrement-use-release sequence or release-use-decrement-retain
  /// reverese sequence.
  struct RRInfo {
    /// KnownSafe - After an objc_retain, the reference count of the referenced
    /// object is known to be positive. Similarly, before an objc_release, the
    /// reference count of the referenced object is known to be positive. If
    /// there are retain-release pairs in code regions where the retain count
    /// is known to be positive, they can be eliminated, regardless of any side
    /// effects between them.
    ///
    /// Also, a retain+release pair nested within another retain+release
    /// pair all on the known same pointer value can be eliminated, regardless
    /// of any intervening side effects.
    ///
    /// KnownSafe is true when either of these conditions is satisfied.
    bool KnownSafe;

    /// IsRetainBlock - True if the Calls are objc_retainBlock calls (as
    /// opposed to objc_retain calls).
    bool IsRetainBlock;

    /// CopyOnEscape - True if this the Calls are objc_retainBlock calls
    /// which all have the !clang.arc.copy_on_escape metadata.
    bool CopyOnEscape;

    /// IsTailCallRelease - True of the objc_release calls are all marked
    /// with the "tail" keyword.
    bool IsTailCallRelease;

    /// Partial - True of we've seen an opportunity for partial RR elimination,
    /// such as pushing calls into a CFG triangle or into one side of a
    /// CFG diamond.
    bool Partial;

    /// ReleaseMetadata - If the Calls are objc_release calls and they all have
    /// a clang.imprecise_release tag, this is the metadata tag.
    MDNode *ReleaseMetadata;

    /// Calls - For a top-down sequence, the set of objc_retains or
    /// objc_retainBlocks. For bottom-up, the set of objc_releases.
    SmallPtrSet<Instruction *, 2> Calls;

    /// ReverseInsertPts - The set of optimal insert positions for
    /// moving calls in the opposite sequence.
    SmallPtrSet<Instruction *, 2> ReverseInsertPts;

    RRInfo() :
      KnownSafe(false), IsRetainBlock(false), CopyOnEscape(false),
      IsTailCallRelease(false), Partial(false),
      ReleaseMetadata(0) {}

    void clear();
  };
}

void RRInfo::clear() {
  KnownSafe = false;
  IsRetainBlock = false;
  CopyOnEscape = false;
  IsTailCallRelease = false;
  Partial = false;
  ReleaseMetadata = 0;
  Calls.clear();
  ReverseInsertPts.clear();
}

namespace {
  /// PtrState - This class summarizes several per-pointer runtime properties
  /// which are propogated through the flow graph.
  class PtrState {
    /// RefCount - The known minimum number of reference count increments.
    unsigned RefCount;

    /// NestCount - The known minimum level of retain+release nesting.
    unsigned NestCount;

    /// Seq - The current position in the sequence.
    Sequence Seq;

  public:
    /// RRI - Unidirectional information about the current sequence.
    /// TODO: Encapsulate this better.
    RRInfo RRI;

    PtrState() : RefCount(0), NestCount(0), Seq(S_None) {}

    void SetAtLeastOneRefCount()  {
      if (RefCount == 0) RefCount = 1;
    }

    void IncrementRefCount() {
      if (RefCount != UINT_MAX) ++RefCount;
    }

    void DecrementRefCount() {
      if (RefCount != 0) --RefCount;
    }

    bool IsKnownIncremented() const {
      return RefCount > 0;
    }

    void IncrementNestCount() {
      if (NestCount != UINT_MAX) ++NestCount;
    }

    void DecrementNestCount() {
      if (NestCount != 0) --NestCount;
    }

    bool IsKnownNested() const {
      return NestCount > 0;
    }

    void SetSeq(Sequence NewSeq) {
      Seq = NewSeq;
    }

    void SetSeqToRelease(MDNode *M) {
      if (Seq == S_None || Seq == S_Use) {
        Seq = M ? S_MovableRelease : S_Release;
        RRI.ReleaseMetadata = M;
      } else if (Seq != S_MovableRelease || RRI.ReleaseMetadata != M) {
        Seq = S_Release;
        RRI.ReleaseMetadata = 0;
      }
    }

    Sequence GetSeq() const {
      return Seq;
    }

    void ClearSequenceProgress() {
      Seq = S_None;
      RRI.clear();
    }

    void Merge(const PtrState &Other, bool TopDown);
  };
}

void
PtrState::Merge(const PtrState &Other, bool TopDown) {
  Seq = MergeSeqs(Seq, Other.Seq, TopDown);
  RefCount = std::min(RefCount, Other.RefCount);
  NestCount = std::min(NestCount, Other.NestCount);

  // We can't merge a plain objc_retain with an objc_retainBlock.
  if (RRI.IsRetainBlock != Other.RRI.IsRetainBlock)
    Seq = S_None;

  // If we're not in a sequence (anymore), drop all associated state.
  if (Seq == S_None) {
    RRI.clear();
  } else if (RRI.Partial || Other.RRI.Partial) {
    // If we're doing a merge on a path that's previously seen a partial
    // merge, conservatively drop the sequence, to avoid doing partial
    // RR elimination. If the branch predicates for the two merge differ,
    // mixing them is unsafe.
    Seq = S_None;
    RRI.clear();
  } else {
    // Conservatively merge the ReleaseMetadata information.
    if (RRI.ReleaseMetadata != Other.RRI.ReleaseMetadata)
      RRI.ReleaseMetadata = 0;

    RRI.CopyOnEscape = RRI.CopyOnEscape && Other.RRI.CopyOnEscape;
    RRI.KnownSafe = RRI.KnownSafe && Other.RRI.KnownSafe;
    RRI.IsTailCallRelease = RRI.IsTailCallRelease && Other.RRI.IsTailCallRelease;
    RRI.Calls.insert(Other.RRI.Calls.begin(), Other.RRI.Calls.end());

    // Merge the insert point sets. If there are any differences,
    // that makes this a partial merge.
    RRI.Partial = RRI.ReverseInsertPts.size() !=
                  Other.RRI.ReverseInsertPts.size();
    for (SmallPtrSet<Instruction *, 2>::const_iterator
         I = Other.RRI.ReverseInsertPts.begin(),
         E = Other.RRI.ReverseInsertPts.end(); I != E; ++I)
      RRI.Partial |= RRI.ReverseInsertPts.insert(*I);
  }
}

namespace {
  /// BBState - Per-BasicBlock state.
  class BBState {
    /// TopDownPathCount - The number of unique control paths from the entry
    /// which can reach this block.
    unsigned TopDownPathCount;

    /// BottomUpPathCount - The number of unique control paths to exits
    /// from this block.
    unsigned BottomUpPathCount;

    /// MapTy - A type for PerPtrTopDown and PerPtrBottomUp.
    typedef MapVector<const Value *, PtrState> MapTy;

    /// PerPtrTopDown - The top-down traversal uses this to record information
    /// known about a pointer at the bottom of each block.
    MapTy PerPtrTopDown;

    /// PerPtrBottomUp - The bottom-up traversal uses this to record information
    /// known about a pointer at the top of each block.
    MapTy PerPtrBottomUp;

  public:
    BBState() : TopDownPathCount(0), BottomUpPathCount(0) {}

    typedef MapTy::iterator ptr_iterator;
    typedef MapTy::const_iterator ptr_const_iterator;

    ptr_iterator top_down_ptr_begin() { return PerPtrTopDown.begin(); }
    ptr_iterator top_down_ptr_end() { return PerPtrTopDown.end(); }
    ptr_const_iterator top_down_ptr_begin() const {
      return PerPtrTopDown.begin();
    }
    ptr_const_iterator top_down_ptr_end() const {
      return PerPtrTopDown.end();
    }

    ptr_iterator bottom_up_ptr_begin() { return PerPtrBottomUp.begin(); }
    ptr_iterator bottom_up_ptr_end() { return PerPtrBottomUp.end(); }
    ptr_const_iterator bottom_up_ptr_begin() const {
      return PerPtrBottomUp.begin();
    }
    ptr_const_iterator bottom_up_ptr_end() const {
      return PerPtrBottomUp.end();
    }

    /// SetAsEntry - Mark this block as being an entry block, which has one
    /// path from the entry by definition.
    void SetAsEntry() { TopDownPathCount = 1; }

    /// SetAsExit - Mark this block as being an exit block, which has one
    /// path to an exit by definition.
    void SetAsExit()  { BottomUpPathCount = 1; }

    PtrState &getPtrTopDownState(const Value *Arg) {
      return PerPtrTopDown[Arg];
    }

    PtrState &getPtrBottomUpState(const Value *Arg) {
      return PerPtrBottomUp[Arg];
    }

    void clearBottomUpPointers() {
      PerPtrBottomUp.clear();
    }

    void clearTopDownPointers() {
      PerPtrTopDown.clear();
    }

    void InitFromPred(const BBState &Other);
    void InitFromSucc(const BBState &Other);
    void MergePred(const BBState &Other);
    void MergeSucc(const BBState &Other);

    /// GetAllPathCount - Return the number of possible unique paths from an
    /// entry to an exit which pass through this block. This is only valid
    /// after both the top-down and bottom-up traversals are complete.
    unsigned GetAllPathCount() const {
      return TopDownPathCount * BottomUpPathCount;
    }

    /// IsVisitedTopDown - Test whether the block for this BBState has been
    /// visited by the top-down portion of the algorithm.
    bool isVisitedTopDown() const {
      return TopDownPathCount != 0;
    }
  };
}

void BBState::InitFromPred(const BBState &Other) {
  PerPtrTopDown = Other.PerPtrTopDown;
  TopDownPathCount = Other.TopDownPathCount;
}

void BBState::InitFromSucc(const BBState &Other) {
  PerPtrBottomUp = Other.PerPtrBottomUp;
  BottomUpPathCount = Other.BottomUpPathCount;
}

/// MergePred - The top-down traversal uses this to merge information about
/// predecessors to form the initial state for a new block.
void BBState::MergePred(const BBState &Other) {
  // Other.TopDownPathCount can be 0, in which case it is either dead or a
  // loop backedge. Loop backedges are special.
  TopDownPathCount += Other.TopDownPathCount;

  // For each entry in the other set, if our set has an entry with the same key,
  // merge the entries. Otherwise, copy the entry and merge it with an empty
  // entry.
  for (ptr_const_iterator MI = Other.top_down_ptr_begin(),
       ME = Other.top_down_ptr_end(); MI != ME; ++MI) {
    std::pair<ptr_iterator, bool> Pair = PerPtrTopDown.insert(*MI);
    Pair.first->second.Merge(Pair.second ? PtrState() : MI->second,
                             /*TopDown=*/true);
  }

  // For each entry in our set, if the other set doesn't have an entry with the
  // same key, force it to merge with an empty entry.
  for (ptr_iterator MI = top_down_ptr_begin(),
       ME = top_down_ptr_end(); MI != ME; ++MI)
    if (Other.PerPtrTopDown.find(MI->first) == Other.PerPtrTopDown.end())
      MI->second.Merge(PtrState(), /*TopDown=*/true);
}

/// MergeSucc - The bottom-up traversal uses this to merge information about
/// successors to form the initial state for a new block.
void BBState::MergeSucc(const BBState &Other) {
  // Other.BottomUpPathCount can be 0, in which case it is either dead or a
  // loop backedge. Loop backedges are special.
  BottomUpPathCount += Other.BottomUpPathCount;

  // For each entry in the other set, if our set has an entry with the
  // same key, merge the entries. Otherwise, copy the entry and merge
  // it with an empty entry.
  for (ptr_const_iterator MI = Other.bottom_up_ptr_begin(),
       ME = Other.bottom_up_ptr_end(); MI != ME; ++MI) {
    std::pair<ptr_iterator, bool> Pair = PerPtrBottomUp.insert(*MI);
    Pair.first->second.Merge(Pair.second ? PtrState() : MI->second,
                             /*TopDown=*/false);
  }

  // For each entry in our set, if the other set doesn't have an entry
  // with the same key, force it to merge with an empty entry.
  for (ptr_iterator MI = bottom_up_ptr_begin(),
       ME = bottom_up_ptr_end(); MI != ME; ++MI)
    if (Other.PerPtrBottomUp.find(MI->first) == Other.PerPtrBottomUp.end())
      MI->second.Merge(PtrState(), /*TopDown=*/false);
}

namespace {
  /// ObjCARCOpt - The main ARC optimization pass.
  class ObjCARCOpt : public FunctionPass {
    bool Changed;
    ProvenanceAnalysis PA;

    /// Run - A flag indicating whether this optimization pass should run.
    bool Run;

    /// RetainRVCallee, etc. - Declarations for ObjC runtime
    /// functions, for use in creating calls to them. These are initialized
    /// lazily to avoid cluttering up the Module with unused declarations.
    Constant *RetainRVCallee, *AutoreleaseRVCallee, *ReleaseCallee,
             *RetainCallee, *RetainBlockCallee, *AutoreleaseCallee;

    /// UsedInThisFunciton - Flags which determine whether each of the
    /// interesting runtine functions is in fact used in the current function.
    unsigned UsedInThisFunction;

    /// ImpreciseReleaseMDKind - The Metadata Kind for clang.imprecise_release
    /// metadata.
    unsigned ImpreciseReleaseMDKind;

    /// CopyOnEscape - The Metadata Kind for clang.arc.copy_on_escape
    /// metadata.
    unsigned CopyOnEscapeMDKind;

    Constant *getRetainRVCallee(Module *M);
    Constant *getAutoreleaseRVCallee(Module *M);
    Constant *getReleaseCallee(Module *M);
    Constant *getRetainCallee(Module *M);
    Constant *getRetainBlockCallee(Module *M);
    Constant *getAutoreleaseCallee(Module *M);

    void OptimizeRetainCall(Function &F, Instruction *Retain);
    bool OptimizeRetainRVCall(Function &F, Instruction *RetainRV);
    void OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV);
    void OptimizeIndividualCalls(Function &F);

    void CheckForCFGHazards(const BasicBlock *BB,
                            DenseMap<const BasicBlock *, BBState> &BBStates,
                            BBState &MyStates) const;
    bool VisitBottomUp(BasicBlock *BB,
                       DenseMap<const BasicBlock *, BBState> &BBStates,
                       MapVector<Value *, RRInfo> &Retains);
    bool VisitTopDown(BasicBlock *BB,
                      DenseMap<const BasicBlock *, BBState> &BBStates,
                      DenseMap<Value *, RRInfo> &Releases);
    bool Visit(Function &F,
               DenseMap<const BasicBlock *, BBState> &BBStates,
               MapVector<Value *, RRInfo> &Retains,
               DenseMap<Value *, RRInfo> &Releases);

    void MoveCalls(Value *Arg, RRInfo &RetainsToMove, RRInfo &ReleasesToMove,
                   MapVector<Value *, RRInfo> &Retains,
                   DenseMap<Value *, RRInfo> &Releases,
                   SmallVectorImpl<Instruction *> &DeadInsts,
                   Module *M);

    bool PerformCodePlacement(DenseMap<const BasicBlock *, BBState> &BBStates,
                              MapVector<Value *, RRInfo> &Retains,
                              DenseMap<Value *, RRInfo> &Releases,
                              Module *M);

    void OptimizeWeakCalls(Function &F);

    bool OptimizeSequences(Function &F);

    void OptimizeReturns(Function &F);

    virtual void getAnalysisUsage(AnalysisUsage &AU) const;
    virtual bool doInitialization(Module &M);
    virtual bool runOnFunction(Function &F);
    virtual void releaseMemory();

  public:
    static char ID;
    ObjCARCOpt() : FunctionPass(ID) {
      initializeObjCARCOptPass(*PassRegistry::getPassRegistry());
    }
  };
}

char ObjCARCOpt::ID = 0;
INITIALIZE_PASS_BEGIN(ObjCARCOpt,
                      "objc-arc", "ObjC ARC optimization", false, false)
INITIALIZE_PASS_DEPENDENCY(ObjCARCAliasAnalysis)
INITIALIZE_PASS_END(ObjCARCOpt,
                    "objc-arc", "ObjC ARC optimization", false, false)

Pass *llvm::createObjCARCOptPass() {
  return new ObjCARCOpt();
}

void ObjCARCOpt::getAnalysisUsage(AnalysisUsage &AU) const {
  AU.addRequired<ObjCARCAliasAnalysis>();
  AU.addRequired<AliasAnalysis>();
  // ARC optimization doesn't currently split critical edges.
  AU.setPreservesCFG();
}

Constant *ObjCARCOpt::getRetainRVCallee(Module *M) {
  if (!RetainRVCallee) {
    LLVMContext &C = M->getContext();
    Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
    std::vector<Type *> Params;
    Params.push_back(I8X);
    FunctionType *FTy =
      FunctionType::get(I8X, Params, /*isVarArg=*/false);
    AttrListPtr Attributes;
    Attributes.addAttr(~0u, Attribute::NoUnwind);
    RetainRVCallee =
      M->getOrInsertFunction("objc_retainAutoreleasedReturnValue", FTy,
                             Attributes);
  }
  return RetainRVCallee;
}

Constant *ObjCARCOpt::getAutoreleaseRVCallee(Module *M) {
  if (!AutoreleaseRVCallee) {
    LLVMContext &C = M->getContext();
    Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
    std::vector<Type *> Params;
    Params.push_back(I8X);
    FunctionType *FTy =
      FunctionType::get(I8X, Params, /*isVarArg=*/false);
    AttrListPtr Attributes;
    Attributes.addAttr(~0u, Attribute::NoUnwind);
    AutoreleaseRVCallee =
      M->getOrInsertFunction("objc_autoreleaseReturnValue", FTy,
                             Attributes);
  }
  return AutoreleaseRVCallee;
}

Constant *ObjCARCOpt::getReleaseCallee(Module *M) {
  if (!ReleaseCallee) {
    LLVMContext &C = M->getContext();
    std::vector<Type *> Params;
    Params.push_back(PointerType::getUnqual(Type::getInt8Ty(C)));
    AttrListPtr Attributes;
    Attributes.addAttr(~0u, Attribute::NoUnwind);
    ReleaseCallee =
      M->getOrInsertFunction(
        "objc_release",
        FunctionType::get(Type::getVoidTy(C), Params, /*isVarArg=*/false),
        Attributes);
  }
  return ReleaseCallee;
}

Constant *ObjCARCOpt::getRetainCallee(Module *M) {
  if (!RetainCallee) {
    LLVMContext &C = M->getContext();
    std::vector<Type *> Params;
    Params.push_back(PointerType::getUnqual(Type::getInt8Ty(C)));
    AttrListPtr Attributes;
    Attributes.addAttr(~0u, Attribute::NoUnwind);
    RetainCallee =
      M->getOrInsertFunction(
        "objc_retain",
        FunctionType::get(Params[0], Params, /*isVarArg=*/false),
        Attributes);
  }
  return RetainCallee;
}

Constant *ObjCARCOpt::getRetainBlockCallee(Module *M) {
  if (!RetainBlockCallee) {
    LLVMContext &C = M->getContext();
    std::vector<Type *> Params;
    Params.push_back(PointerType::getUnqual(Type::getInt8Ty(C)));
    AttrListPtr Attributes;
    // objc_retainBlock is not nounwind because it calls user copy constructors
    // which could theoretically throw.
    RetainBlockCallee =
      M->getOrInsertFunction(
        "objc_retainBlock",
        FunctionType::get(Params[0], Params, /*isVarArg=*/false),
        Attributes);
  }
  return RetainBlockCallee;
}

Constant *ObjCARCOpt::getAutoreleaseCallee(Module *M) {
  if (!AutoreleaseCallee) {
    LLVMContext &C = M->getContext();
    std::vector<Type *> Params;
    Params.push_back(PointerType::getUnqual(Type::getInt8Ty(C)));
    AttrListPtr Attributes;
    Attributes.addAttr(~0u, Attribute::NoUnwind);
    AutoreleaseCallee =
      M->getOrInsertFunction(
        "objc_autorelease",
        FunctionType::get(Params[0], Params, /*isVarArg=*/false),
        Attributes);
  }
  return AutoreleaseCallee;
}

/// CanAlterRefCount - Test whether the given instruction can result in a
/// reference count modification (positive or negative) for the pointer's
/// object.
static bool
CanAlterRefCount(const Instruction *Inst, const Value *Ptr,
                 ProvenanceAnalysis &PA, InstructionClass Class) {
  switch (Class) {
  case IC_Autorelease:
  case IC_AutoreleaseRV:
  case IC_User:
    // These operations never directly modify a reference count.
    return false;
  default: break;
  }

  ImmutableCallSite CS = static_cast<const Value *>(Inst);
  assert(CS && "Only calls can alter reference counts!");

  // See if AliasAnalysis can help us with the call.
  AliasAnalysis::ModRefBehavior MRB = PA.getAA()->getModRefBehavior(CS);
  if (AliasAnalysis::onlyReadsMemory(MRB))
    return false;
  if (AliasAnalysis::onlyAccessesArgPointees(MRB)) {
    for (ImmutableCallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end();
         I != E; ++I) {
      const Value *Op = *I;
      if (IsPotentialUse(Op) && PA.related(Ptr, Op))
        return true;
    }
    return false;
  }

  // Assume the worst.
  return true;
}

/// CanUse - Test whether the given instruction can "use" the given pointer's
/// object in a way that requires the reference count to be positive.
static bool
CanUse(const Instruction *Inst, const Value *Ptr, ProvenanceAnalysis &PA,
       InstructionClass Class) {
  // IC_Call operations (as opposed to IC_CallOrUser) never "use" objc pointers.
  if (Class == IC_Call)
    return false;

  // Consider various instructions which may have pointer arguments which are
  // not "uses".
  if (const ICmpInst *ICI = dyn_cast<ICmpInst>(Inst)) {
    // Comparing a pointer with null, or any other constant, isn't really a use,
    // because we don't care what the pointer points to, or about the values
    // of any other dynamic reference-counted pointers.
    if (!IsPotentialUse(ICI->getOperand(1)))
      return false;
  } else if (ImmutableCallSite CS = static_cast<const Value *>(Inst)) {
    // For calls, just check the arguments (and not the callee operand).
    for (ImmutableCallSite::arg_iterator OI = CS.arg_begin(),
         OE = CS.arg_end(); OI != OE; ++OI) {
      const Value *Op = *OI;
      if (IsPotentialUse(Op) && PA.related(Ptr, Op))
        return true;
    }
    return false;
  } else if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
    // Special-case stores, because we don't care about the stored value, just
    // the store address.
    const Value *Op = GetUnderlyingObjCPtr(SI->getPointerOperand());
    // If we can't tell what the underlying object was, assume there is a
    // dependence.
    return IsPotentialUse(Op) && PA.related(Op, Ptr);
  }

  // Check each operand for a match.
  for (User::const_op_iterator OI = Inst->op_begin(), OE = Inst->op_end();
       OI != OE; ++OI) {
    const Value *Op = *OI;
    if (IsPotentialUse(Op) && PA.related(Ptr, Op))
      return true;
  }
  return false;
}

/// CanInterruptRV - Test whether the given instruction can autorelease
/// any pointer or cause an autoreleasepool pop.
static bool
CanInterruptRV(InstructionClass Class) {
  switch (Class) {
  case IC_AutoreleasepoolPop:
  case IC_CallOrUser:
  case IC_Call:
  case IC_Autorelease:
  case IC_AutoreleaseRV:
  case IC_FusedRetainAutorelease:
  case IC_FusedRetainAutoreleaseRV:
    return true;
  default:
    return false;
  }
}

namespace {
  /// DependenceKind - There are several kinds of dependence-like concepts in
  /// use here.
  enum DependenceKind {
    NeedsPositiveRetainCount,
    CanChangeRetainCount,
    RetainAutoreleaseDep,       ///< Blocks objc_retainAutorelease.
    RetainAutoreleaseRVDep,     ///< Blocks objc_retainAutoreleaseReturnValue.
    RetainRVDep                 ///< Blocks objc_retainAutoreleasedReturnValue.
  };
}

/// Depends - Test if there can be dependencies on Inst through Arg. This
/// function only tests dependencies relevant for removing pairs of calls.
static bool
Depends(DependenceKind Flavor, Instruction *Inst, const Value *Arg,
        ProvenanceAnalysis &PA) {
  // If we've reached the definition of Arg, stop.
  if (Inst == Arg)
    return true;

  switch (Flavor) {
  case NeedsPositiveRetainCount: {
    InstructionClass Class = GetInstructionClass(Inst);
    switch (Class) {
    case IC_AutoreleasepoolPop:
    case IC_AutoreleasepoolPush:
    case IC_None:
      return false;
    default:
      return CanUse(Inst, Arg, PA, Class);
    }
  }

  case CanChangeRetainCount: {
    InstructionClass Class = GetInstructionClass(Inst);
    switch (Class) {
    case IC_AutoreleasepoolPop:
      // Conservatively assume this can decrement any count.
      return true;
    case IC_AutoreleasepoolPush:
    case IC_None:
      return false;
    default:
      return CanAlterRefCount(Inst, Arg, PA, Class);
    }
  }

  case RetainAutoreleaseDep:
    switch (GetBasicInstructionClass(Inst)) {
    case IC_AutoreleasepoolPop:
      // Don't merge an objc_autorelease with an objc_retain inside a different
      // autoreleasepool scope.
      return true;
    case IC_Retain:
    case IC_RetainRV:
      // Check for a retain of the same pointer for merging.
      return GetObjCArg(Inst) == Arg;
    default:
      // Nothing else matters for objc_retainAutorelease formation.
      return false;
    }
    break;

  case RetainAutoreleaseRVDep: {
    InstructionClass Class = GetBasicInstructionClass(Inst);
    switch (Class) {
    case IC_Retain:
    case IC_RetainRV:
      // Check for a retain of the same pointer for merging.
      return GetObjCArg(Inst) == Arg;
    default:
      // Anything that can autorelease interrupts
      // retainAutoreleaseReturnValue formation.
      return CanInterruptRV(Class);
    }
    break;
  }

  case RetainRVDep:
    return CanInterruptRV(GetBasicInstructionClass(Inst));
  }

  llvm_unreachable("Invalid dependence flavor");
  return true;
}

/// FindDependencies - Walk up the CFG from StartPos (which is in StartBB) and
/// find local and non-local dependencies on Arg.
/// TODO: Cache results?
static void
FindDependencies(DependenceKind Flavor,
                 const Value *Arg,
                 BasicBlock *StartBB, Instruction *StartInst,
                 SmallPtrSet<Instruction *, 4> &DependingInstructions,
                 SmallPtrSet<const BasicBlock *, 4> &Visited,
                 ProvenanceAnalysis &PA) {
  BasicBlock::iterator StartPos = StartInst;

  SmallVector<std::pair<BasicBlock *, BasicBlock::iterator>, 4> Worklist;
  Worklist.push_back(std::make_pair(StartBB, StartPos));
  do {
    std::pair<BasicBlock *, BasicBlock::iterator> Pair =
      Worklist.pop_back_val();
    BasicBlock *LocalStartBB = Pair.first;
    BasicBlock::iterator LocalStartPos = Pair.second;
    BasicBlock::iterator StartBBBegin = LocalStartBB->begin();
    for (;;) {
      if (LocalStartPos == StartBBBegin) {
        pred_iterator PI(LocalStartBB), PE(LocalStartBB, false);
        if (PI == PE)
          // If we've reached the function entry, produce a null dependence.
          DependingInstructions.insert(0);
        else
          // Add the predecessors to the worklist.
          do {
            BasicBlock *PredBB = *PI;
            if (Visited.insert(PredBB))
              Worklist.push_back(std::make_pair(PredBB, PredBB->end()));
          } while (++PI != PE);
        break;
      }

      Instruction *Inst = --LocalStartPos;
      if (Depends(Flavor, Inst, Arg, PA)) {
        DependingInstructions.insert(Inst);
        break;
      }
    }
  } while (!Worklist.empty());

  // Determine whether the original StartBB post-dominates all of the blocks we
  // visited. If not, insert a sentinal indicating that most optimizations are
  // not safe.
  for (SmallPtrSet<const BasicBlock *, 4>::const_iterator I = Visited.begin(),
       E = Visited.end(); I != E; ++I) {
    const BasicBlock *BB = *I;
    if (BB == StartBB)
      continue;
    const TerminatorInst *TI = cast<TerminatorInst>(&BB->back());
    for (succ_const_iterator SI(TI), SE(TI, false); SI != SE; ++SI) {
      const BasicBlock *Succ = *SI;
      if (Succ != StartBB && !Visited.count(Succ)) {
        DependingInstructions.insert(reinterpret_cast<Instruction *>(-1));
        return;
      }
    }
  }
}

static bool isNullOrUndef(const Value *V) {
  return isa<ConstantPointerNull>(V) || isa<UndefValue>(V);
}

static bool isNoopInstruction(const Instruction *I) {
  return isa<BitCastInst>(I) ||
         (isa<GetElementPtrInst>(I) &&
          cast<GetElementPtrInst>(I)->hasAllZeroIndices());
}

/// OptimizeRetainCall - Turn objc_retain into
/// objc_retainAutoreleasedReturnValue if the operand is a return value.
void
ObjCARCOpt::OptimizeRetainCall(Function &F, Instruction *Retain) {
  CallSite CS(GetObjCArg(Retain));
  Instruction *Call = CS.getInstruction();
  if (!Call) return;
  if (Call->getParent() != Retain->getParent()) return;

  // Check that the call is next to the retain.
  BasicBlock::iterator I = Call;
  ++I;
  while (isNoopInstruction(I)) ++I;
  if (&*I != Retain)
    return;

  // Turn it to an objc_retainAutoreleasedReturnValue..
  Changed = true;
  ++NumPeeps;
  cast<CallInst>(Retain)->setCalledFunction(getRetainRVCallee(F.getParent()));
}

/// OptimizeRetainRVCall - Turn objc_retainAutoreleasedReturnValue into
/// objc_retain if the operand is not a return value.  Or, if it can be
/// paired with an objc_autoreleaseReturnValue, delete the pair and
/// return true.
bool
ObjCARCOpt::OptimizeRetainRVCall(Function &F, Instruction *RetainRV) {
  // Check for the argument being from an immediately preceding call.
  Value *Arg = GetObjCArg(RetainRV);
  CallSite CS(Arg);
  if (Instruction *Call = CS.getInstruction())
    if (Call->getParent() == RetainRV->getParent()) {
      BasicBlock::iterator I = Call;
      ++I;
      while (isNoopInstruction(I)) ++I;
      if (&*I == RetainRV)
        return false;
    }

  // Check for being preceded by an objc_autoreleaseReturnValue on the same
  // pointer. In this case, we can delete the pair.
  BasicBlock::iterator I = RetainRV, Begin = RetainRV->getParent()->begin();
  if (I != Begin) {
    do --I; while (I != Begin && isNoopInstruction(I));
    if (GetBasicInstructionClass(I) == IC_AutoreleaseRV &&
        GetObjCArg(I) == Arg) {
      Changed = true;
      ++NumPeeps;
      EraseInstruction(I);
      EraseInstruction(RetainRV);
      return true;
    }
  }

  // Turn it to a plain objc_retain.
  Changed = true;
  ++NumPeeps;
  cast<CallInst>(RetainRV)->setCalledFunction(getRetainCallee(F.getParent()));
  return false;
}

/// OptimizeAutoreleaseRVCall - Turn objc_autoreleaseReturnValue into
/// objc_autorelease if the result is not used as a return value.
void
ObjCARCOpt::OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV) {
  // Check for a return of the pointer value.
  const Value *Ptr = GetObjCArg(AutoreleaseRV);
  SmallVector<const Value *, 2> Users;
  Users.push_back(Ptr);
  do {
    Ptr = Users.pop_back_val();
    for (Value::const_use_iterator UI = Ptr->use_begin(), UE = Ptr->use_end();
         UI != UE; ++UI) {