ObjCARC.cpp

      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;

  // Note that we can't merge S_CanRelease and S_Use.
  if (A > B) std::swap(A, B);
  if (TopDown) {
    // Choose the side which is further along in the sequence.
    if (A == S_Retain && (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_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 {
    /// KnownIncremented - 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.
    bool KnownIncremented;

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

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

    /// 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() :
      KnownIncremented(false), IsRetainBlock(false), IsTailCallRelease(false),
      ReleaseMetadata(0) {}

    void clear();
  };
}

void RRInfo::clear() {
  KnownIncremented = false;
  IsRetainBlock = false;
  IsTailCallRelease = 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;

    /// 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), Seq(S_None) {}

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

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

    void ClearRefCount() {
      RefCount = 0;
    }

    bool IsKnownIncremented() const {
      return RefCount > 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);

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

  if (Seq == S_None) {
    RRI.clear();
  } else {
    // Conservatively merge the ReleaseMetadata information.
    if (RRI.ReleaseMetadata != Other.RRI.ReleaseMetadata)
      RRI.ReleaseMetadata = 0;

    RRI.KnownIncremented = RRI.KnownIncremented && Other.RRI.KnownIncremented;
    RRI.IsTailCallRelease = RRI.IsTailCallRelease && Other.RRI.IsTailCallRelease;
    RRI.Calls.insert(Other.RRI.Calls.begin(), Other.RRI.Calls.end());
    RRI.ReverseInsertPts.insert(Other.RRI.ReverseInsertPts.begin(),
                                Other.RRI.ReverseInsertPts.end());
  }
}

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() {
      PerPtrTopDown.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;
    }
  };
}

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 doens'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 doens'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;

    /// RetainFunc, RelaseFunc - Declarations for objc_retain,
    /// objc_retainBlock, and objc_release.
    Function *RetainFunc, *RetainBlockFunc, *RetainRVFunc, *ReleaseFunc;

    /// 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, *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;

    Constant *getRetainRVCallee(Module *M);
    Constant *getAutoreleaseRVCallee(Module *M);
    Constant *getReleaseCallee(Module *M);
    Constant *getRetainCallee(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);

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

    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);
    const 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);
    const 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::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);
  for (Value::const_use_iterator UI = Ptr->use_begin(), UE = Ptr->use_end();
       UI != UE; ++UI) {
    const User *I = *UI;
    if (isa<ReturnInst>(I) || GetBasicInstructionClass(I) == IC_RetainRV)
      return;
  }

  Changed = true;
  ++NumPeeps;
  cast<CallInst>(AutoreleaseRV)->
    setCalledFunction(getAutoreleaseCallee(F.getParent()));
}

/// OptimizeIndividualCalls - Visit each call, one at a time, and make
/// simplifications without doing any additional analysis.
void ObjCARCOpt::OptimizeIndividualCalls(Function &F) {
  // Reset all the flags in preparation for recomputing them.
  UsedInThisFunction = 0;

  // Visit all objc_* calls in F.
  for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
    Instruction *Inst = &*I++;
    InstructionClass Class = GetBasicInstructionClass(Inst);

    switch (Class) {
    default: break;

    // Delete no-op casts. These function calls have special semantics, but
    // the semantics are entirely implemented via lowering in the front-end,
    // so by the time they reach the optimizer, they are just no-op calls
    // which return their argument.
    //
    // There are gray areas here, as the ability to cast reference-counted
    // pointers to raw void* and back allows code to break ARC assumptions,
    // however these are currently considered to be unimportant.
    case IC_NoopCast:
      Changed = true;
      ++NumNoops;
      EraseInstruction(Inst);
      continue;

    // If the pointer-to-weak-pointer is null, it's undefined behavior.
    case IC_StoreWeak:
    case IC_LoadWeak:
    case IC_LoadWeakRetained:
    case IC_InitWeak:
    case IC_DestroyWeak: {
      CallInst *CI = cast<CallInst>(Inst);
      if (isNullOrUndef(CI->getArgOperand(0))) {
        const Type *Ty = CI->getArgOperand(0)->getType();
        new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()),
                      Constant::getNullValue(Ty),
                      CI);
        CI->replaceAllUsesWith(UndefValue::get(CI->getType()));
        CI->eraseFromParent();
        continue;
      }
      break;
    }
    case IC_CopyWeak:
    case IC_MoveWeak: {
      CallInst *CI = cast<CallInst>(Inst);
      if (isNullOrUndef(CI->getArgOperand(0)) ||
          isNullOrUndef(CI->getArgOperand(1))) {
        const Type *Ty = CI->getArgOperand(0)->getType();
        new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()),
                      Constant::getNullValue(Ty),
                      CI);
        CI->replaceAllUsesWith(UndefValue::get(CI->getType()));
        CI->eraseFromParent();
        continue;
      }
      break;
    }
    case IC_Retain:
      OptimizeRetainCall(F, Inst);
      break;
    case IC_RetainRV:
      if (OptimizeRetainRVCall(F, Inst))
        continue;
      break;
    case IC_AutoreleaseRV:
      OptimizeAutoreleaseRVCall(F, Inst);
      break;
    }

    // objc_autorelease(x) -> objc_release(x) if x is otherwise unused.
    if (IsAutorelease(Class) && Inst->use_empty()) {
      CallInst *Call = cast<CallInst>(Inst);
      const Value *Arg = Call->getArgOperand(0);
      Arg = FindSingleUseIdentifiedObject(Arg);
      if (Arg) {
        Changed = true;
        ++NumAutoreleases;