ObjCARC.cpp

        // Create the declaration lazily.
        LLVMContext &C = Inst->getContext();
        CallInst *NewCall =
          CallInst::Create(getReleaseCallee(F.getParent()),
                           Call->getArgOperand(0), "", Call);
        NewCall->setMetadata(ImpreciseReleaseMDKind,
                             MDNode::get(C, ArrayRef<Value *>()));
        EraseInstruction(Call);
        Inst = NewCall;
        Class = IC_Release;
      }
    }

    // For functions which can never be passed stack arguments, add
    // a tail keyword.
    if (IsAlwaysTail(Class)) {
      Changed = true;
      cast<CallInst>(Inst)->setTailCall();
    }

    // Set nounwind as needed.
    if (IsNoThrow(Class)) {
      Changed = true;
      cast<CallInst>(Inst)->setDoesNotThrow();
    }

    if (!IsNoopOnNull(Class)) {
      UsedInThisFunction |= 1 << Class;
      continue;
    }

    const Value *Arg = GetObjCArg(Inst);

    // ARC calls with null are no-ops. Delete them.
    if (isNullOrUndef(Arg)) {
      Changed = true;
      ++NumNoops;
      EraseInstruction(Inst);
      continue;
    }

    // Keep track of which of retain, release, autorelease, and retain_block
    // are actually present in this function.
    UsedInThisFunction |= 1 << Class;

    // If Arg is a PHI, and one or more incoming values to the
    // PHI are null, and the call is control-equivalent to the PHI, and there
    // are no relevant side effects between the PHI and the call, the call
    // could be pushed up to just those paths with non-null incoming values.
    // For now, don't bother splitting critical edges for this.
    SmallVector<std::pair<Instruction *, const Value *>, 4> Worklist;
    Worklist.push_back(std::make_pair(Inst, Arg));
    do {
      std::pair<Instruction *, const Value *> Pair = Worklist.pop_back_val();
      Inst = Pair.first;
      Arg = Pair.second;

      const PHINode *PN = dyn_cast<PHINode>(Arg);
      if (!PN) continue;

      // Determine if the PHI has any null operands, or any incoming
      // critical edges.
      bool HasNull = false;
      bool HasCriticalEdges = false;
      for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
        Value *Incoming =
          StripPointerCastsAndObjCCalls(PN->getIncomingValue(i));
        if (isNullOrUndef(Incoming))
          HasNull = true;
        else if (cast<TerminatorInst>(PN->getIncomingBlock(i)->back())
                   .getNumSuccessors() != 1) {
          HasCriticalEdges = true;
          break;
        }
      }
      // If we have null operands and no critical edges, optimize.
      if (!HasCriticalEdges && HasNull) {
        SmallPtrSet<Instruction *, 4> DependingInstructions;
        SmallPtrSet<const BasicBlock *, 4> Visited;

        // Check that there is nothing that cares about the reference
        // count between the call and the phi.
        FindDependencies(NeedsPositiveRetainCount, Arg,
                         Inst->getParent(), Inst,
                         DependingInstructions, Visited, PA);
        if (DependingInstructions.size() == 1 &&
            *DependingInstructions.begin() == PN) {
          Changed = true;
          ++NumPartialNoops;
          // Clone the call into each predecessor that has a non-null value.
          CallInst *CInst = cast<CallInst>(Inst);
          const Type *ParamTy = CInst->getArgOperand(0)->getType();
          for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
            Value *Incoming =
              StripPointerCastsAndObjCCalls(PN->getIncomingValue(i));
            if (!isNullOrUndef(Incoming)) {
              CallInst *Clone = cast<CallInst>(CInst->clone());
              Value *Op = PN->getIncomingValue(i);
              Instruction *InsertPos = &PN->getIncomingBlock(i)->back();
              if (Op->getType() != ParamTy)
                Op = new BitCastInst(Op, ParamTy, "", InsertPos);
              Clone->setArgOperand(0, Op);
              Clone->insertBefore(InsertPos);
              Worklist.push_back(std::make_pair(Clone, Incoming));
            }
          }
          // Erase the original call.
          EraseInstruction(CInst);
          continue;
        }
      }
    } while (!Worklist.empty());
  }
}

/// CheckForCFGHazards - Check for critical edges, loop boundaries, irreducible
/// control flow, or other CFG structures where moving code across the edge
/// would result in it being executed more.
void
ObjCARCOpt::CheckForCFGHazards(const BasicBlock *BB,
                               DenseMap<const BasicBlock *, BBState> &BBStates,
                               BBState &MyStates) const {
  // If any top-down local-use or possible-dec has a succ which is earlier in
  // the sequence, forget it.
  for (BBState::ptr_const_iterator I = MyStates.top_down_ptr_begin(),
       E = MyStates.top_down_ptr_end(); I != E; ++I)
    switch (I->second.GetSeq()) {
    default: break;
    case S_Use: {
      const Value *Arg = I->first;
      const TerminatorInst *TI = cast<TerminatorInst>(&BB->back());
      bool SomeSuccHasSame = false;
      bool AllSuccsHaveSame = true;
      for (succ_const_iterator SI(TI), SE(TI, false); SI != SE; ++SI)
        switch (BBStates[*SI].getPtrBottomUpState(Arg).GetSeq()) {
        case S_None:
        case S_CanRelease:
          MyStates.getPtrTopDownState(Arg).ClearSequenceProgress();
          SomeSuccHasSame = false;
          break;
        case S_Use:
          SomeSuccHasSame = true;
          break;
        case S_Stop:
        case S_Release:
        case S_MovableRelease:
          AllSuccsHaveSame = false;
          break;
        case S_Retain:
          llvm_unreachable("bottom-up pointer in retain state!");
        }
      // If the state at the other end of any of the successor edges
      // matches the current state, require all edges to match. This
      // guards against loops in the middle of a sequence.
      if (SomeSuccHasSame && !AllSuccsHaveSame)
        MyStates.getPtrTopDownState(Arg).ClearSequenceProgress();
    }
    case S_CanRelease: {
      const Value *Arg = I->first;
      const TerminatorInst *TI = cast<TerminatorInst>(&BB->back());
      bool SomeSuccHasSame = false;
      bool AllSuccsHaveSame = true;
      for (succ_const_iterator SI(TI), SE(TI, false); SI != SE; ++SI)
        switch (BBStates[*SI].getPtrBottomUpState(Arg).GetSeq()) {
        case S_None:
          MyStates.getPtrTopDownState(Arg).ClearSequenceProgress();
          SomeSuccHasSame = false;
          break;
        case S_CanRelease:
          SomeSuccHasSame = true;
          break;
        case S_Stop:
        case S_Release:
        case S_MovableRelease:
        case S_Use:
          AllSuccsHaveSame = false;
          break;
        case S_Retain:
          llvm_unreachable("bottom-up pointer in retain state!");
        }
      // If the state at the other end of any of the successor edges
      // matches the current state, require all edges to match. This
      // guards against loops in the middle of a sequence.
      if (SomeSuccHasSame && !AllSuccsHaveSame)
        MyStates.getPtrTopDownState(Arg).ClearSequenceProgress();
    }
    }
}

bool
ObjCARCOpt::VisitBottomUp(BasicBlock *BB,
                          DenseMap<const BasicBlock *, BBState> &BBStates,
                          MapVector<Value *, RRInfo> &Retains) {
  bool NestingDetected = false;
  BBState &MyStates = BBStates[BB];

  // Merge the states from each successor to compute the initial state
  // for the current block.
  const TerminatorInst *TI = cast<TerminatorInst>(&BB->back());
  succ_const_iterator SI(TI), SE(TI, false);
  if (SI == SE)
    MyStates.SetAsExit();
  else
    do {
      const BasicBlock *Succ = *SI++;
      if (Succ == BB)
        continue;
      DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Succ);
      if (I == BBStates.end())
        continue;
      MyStates.InitFromSucc(I->second);
      while (SI != SE) {
        Succ = *SI++;
        if (Succ != BB) {
          I = BBStates.find(Succ);
          if (I != BBStates.end())
            MyStates.MergeSucc(I->second);
        }
      }
      break;
    } while (SI != SE);

  // Visit all the instructions, bottom-up.
  for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; --I) {
    Instruction *Inst = llvm::prior(I);
    InstructionClass Class = GetInstructionClass(Inst);
    const Value *Arg = 0;

    switch (Class) {
    case IC_Release: {
      Arg = GetObjCArg(Inst);

      PtrState &S = MyStates.getPtrBottomUpState(Arg);

      // If we see two releases in a row on the same pointer. If so, make
      // a note, and we'll cicle back to revisit it after we've
      // hopefully eliminated the second release, which may allow us to
      // eliminate the first release too.
      // Theoretically we could implement removal of nested retain+release
      // pairs by making PtrState hold a stack of states, but this is
      // simple and avoids adding overhead for the non-nested case.
      if (S.GetSeq() == S_Release || S.GetSeq() == S_MovableRelease)
        NestingDetected = true;

      S.SetSeqToRelease(Inst->getMetadata(ImpreciseReleaseMDKind));
      S.RRI.clear();
      S.RRI.KnownIncremented = S.IsKnownIncremented();
      S.RRI.IsTailCallRelease = cast<CallInst>(Inst)->isTailCall();
      S.RRI.Calls.insert(Inst);

      S.IncrementRefCount();
      break;
    }
    case IC_RetainBlock:
    case IC_Retain:
    case IC_RetainRV: {
      Arg = GetObjCArg(Inst);

      PtrState &S = MyStates.getPtrBottomUpState(Arg);
      S.DecrementRefCount();

      switch (S.GetSeq()) {
      case S_Stop:
      case S_Release:
      case S_MovableRelease:
      case S_Use:
        S.RRI.ReverseInsertPts.clear();
        // FALL THROUGH
      case S_CanRelease:
        // Don't do retain+release tracking for IC_RetainRV, because it's
        // better to let it remain as the first instruction after a call.
        if (Class != IC_RetainRV) {
          S.RRI.IsRetainBlock = Class == IC_RetainBlock;
          Retains[Inst] = S.RRI;
        }
        S.ClearSequenceProgress();
        break;
      case S_None:
        break;
      case S_Retain:
        llvm_unreachable("bottom-up pointer in retain state!");
      }
      break;
    }
    case IC_AutoreleasepoolPop:
      // Conservatively, clear MyStates for all known pointers.
      MyStates.clearBottomUpPointers();
      continue;
    case IC_AutoreleasepoolPush:
    case IC_None:
      // These are irrelevant.
      continue;
    default:
      break;
    }

    // Consider any other possible effects of this instruction on each
    // pointer being tracked.
    for (BBState::ptr_iterator MI = MyStates.bottom_up_ptr_begin(),
         ME = MyStates.bottom_up_ptr_end(); MI != ME; ++MI) {
      const Value *Ptr = MI->first;
      if (Ptr == Arg)
        continue; // Handled above.
      PtrState &S = MI->second;
      Sequence Seq = S.GetSeq();

      // Check for possible retains and releases.
      if (CanAlterRefCount(Inst, Ptr, PA, Class)) {
        // Check for a retain (we're going bottom-up here).
        S.DecrementRefCount();

        // Check for a release.
        if (!IsRetain(Class) && Class != IC_RetainBlock)
          switch (Seq) {
          case S_Use:
            S.SetSeq(S_CanRelease);
            continue;
          case S_CanRelease:
          case S_Release:
          case S_MovableRelease:
          case S_Stop:
          case S_None:
            break;
          case S_Retain:
            llvm_unreachable("bottom-up pointer in retain state!");
          }
      }

      // Check for possible direct uses.
      switch (Seq) {
      case S_Release:
      case S_MovableRelease:
        if (CanUse(Inst, Ptr, PA, Class)) {
          S.RRI.ReverseInsertPts.clear();
          S.RRI.ReverseInsertPts.insert(Inst);
          S.SetSeq(S_Use);
        } else if (Seq == S_Release &&
                   (Class == IC_User || Class == IC_CallOrUser)) {
          // Non-movable releases depend on any possible objc pointer use.
          S.SetSeq(S_Stop);
          S.RRI.ReverseInsertPts.clear();
          S.RRI.ReverseInsertPts.insert(Inst);
        }
        break;
      case S_Stop:
        if (CanUse(Inst, Ptr, PA, Class))
          S.SetSeq(S_Use);
        break;
      case S_CanRelease:
      case S_Use:
      case S_None:
        break;
      case S_Retain:
        llvm_unreachable("bottom-up pointer in retain state!");
      }
    }
  }

  return NestingDetected;
}

bool
ObjCARCOpt::VisitTopDown(BasicBlock *BB,
                         DenseMap<const BasicBlock *, BBState> &BBStates,
                         DenseMap<Value *, RRInfo> &Releases) {
  bool NestingDetected = false;
  BBState &MyStates = BBStates[BB];

  // Merge the states from each predecessor to compute the initial state
  // for the current block.
  const_pred_iterator PI(BB), PE(BB, false);
  if (PI == PE)
    MyStates.SetAsEntry();
  else
    do {
      const BasicBlock *Pred = *PI++;
      if (Pred == BB)
        continue;
      DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Pred);
      if (I == BBStates.end())
        continue;
      MyStates.InitFromPred(I->second);
      while (PI != PE) {
        Pred = *PI++;
        if (Pred != BB) {
          I = BBStates.find(Pred);
          if (I != BBStates.end())
            MyStates.MergePred(I->second);
        }
      }
      break;
    } while (PI != PE);

  // Visit all the instructions, top-down.
  for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
    Instruction *Inst = I;
    InstructionClass Class = GetInstructionClass(Inst);
    const Value *Arg = 0;

    switch (Class) {
    case IC_RetainBlock:
    case IC_Retain:
    case IC_RetainRV: {
      Arg = GetObjCArg(Inst);

      PtrState &S = MyStates.getPtrTopDownState(Arg);

      // Don't do retain+release tracking for IC_RetainRV, because it's
      // better to let it remain as the first instruction after a call.
      if (Class != IC_RetainRV) {
        // If we see two retains in a row on the same pointer. If so, make
        // a note, and we'll cicle back to revisit it after we've
        // hopefully eliminated the second retain, which may allow us to
        // eliminate the first retain too.
        // Theoretically we could implement removal of nested retain+release
        // pairs by making PtrState hold a stack of states, but this is
        // simple and avoids adding overhead for the non-nested case.
        if (S.GetSeq() == S_Retain)
          NestingDetected = true;

        S.SetSeq(S_Retain);
        S.RRI.clear();
        S.RRI.IsRetainBlock = Class == IC_RetainBlock;
        S.RRI.KnownIncremented = S.IsKnownIncremented();
        S.RRI.Calls.insert(Inst);
      }

      S.IncrementRefCount();
      break;
    }
    case IC_Release: {
      Arg = GetObjCArg(Inst);

      PtrState &S = MyStates.getPtrTopDownState(Arg);
      S.DecrementRefCount();

      switch (S.GetSeq()) {
      case S_Retain:
      case S_CanRelease:
        S.RRI.ReverseInsertPts.clear();
        // FALL THROUGH
      case S_Use:
        S.RRI.ReleaseMetadata = Inst->getMetadata(ImpreciseReleaseMDKind);
        S.RRI.IsTailCallRelease = cast<CallInst>(Inst)->isTailCall();
        Releases[Inst] = S.RRI;
        S.ClearSequenceProgress();
        break;
      case S_None:
        break;
      case S_Stop:
      case S_Release:
      case S_MovableRelease:
        llvm_unreachable("top-down pointer in release state!");
      }
      break;
    }
    case IC_AutoreleasepoolPop:
      // Conservatively, clear MyStates for all known pointers.
      MyStates.clearTopDownPointers();
      continue;
    case IC_AutoreleasepoolPush:
    case IC_None:
      // These are irrelevant.
      continue;
    default:
      break;
    }

    // Consider any other possible effects of this instruction on each
    // pointer being tracked.
    for (BBState::ptr_iterator MI = MyStates.top_down_ptr_begin(),
         ME = MyStates.top_down_ptr_end(); MI != ME; ++MI) {
      const Value *Ptr = MI->first;
      if (Ptr == Arg)
        continue; // Handled above.
      PtrState &S = MI->second;
      Sequence Seq = S.GetSeq();

      // Check for possible releases.
      if (!IsRetain(Class) && Class != IC_RetainBlock &&
          CanAlterRefCount(Inst, Ptr, PA, Class)) {
        // Check for a release.
        S.DecrementRefCount();

        // Check for a release.
        switch (Seq) {
        case S_Retain:
          S.SetSeq(S_CanRelease);
          S.RRI.ReverseInsertPts.clear();
          S.RRI.ReverseInsertPts.insert(Inst);

          // One call can't cause a transition from S_Retain to S_CanRelease
          // and S_CanRelease to S_Use. If we've made the first transition,
          // we're done.
          continue;
        case S_Use:
        case S_CanRelease:
        case S_None:
          break;
        case S_Stop:
        case S_Release:
        case S_MovableRelease:
          llvm_unreachable("top-down pointer in release state!");
        }
      }

      // Check for possible direct uses.
      switch (Seq) {
      case S_CanRelease:
        if (CanUse(Inst, Ptr, PA, Class))
          S.SetSeq(S_Use);
        break;
      case S_Use:
      case S_Retain:
      case S_None:
        break;
      case S_Stop:
      case S_Release:
      case S_MovableRelease:
        llvm_unreachable("top-down pointer in release state!");
      }
    }
  }

  CheckForCFGHazards(BB, BBStates, MyStates);
  return NestingDetected;
}

// Visit - Visit the function both top-down and bottom-up.
bool
ObjCARCOpt::Visit(Function &F,
                  DenseMap<const BasicBlock *, BBState> &BBStates,
                  MapVector<Value *, RRInfo> &Retains,
                  DenseMap<Value *, RRInfo> &Releases) {
  // Use postorder for bottom-up, and reverse-postorder for top-down, because we
  // magically know that loops will be well behaved, i.e. they won't repeatedly
  // call retain on a single pointer without doing a release.
  bool BottomUpNestingDetected = false;
  SmallVector<BasicBlock *, 8> PostOrder;
  for (po_iterator<Function *> I = po_begin(&F), E = po_end(&F); I != E; ++I) {
    BasicBlock *BB = *I;
    PostOrder.push_back(BB);

    BottomUpNestingDetected |= VisitBottomUp(BB, BBStates, Retains);
  }

  // Iterate through the post-order in reverse order, achieving a
  // reverse-postorder traversal. We don't use the ReversePostOrderTraversal
  // class here because it works by computing its own full postorder iteration,
  // recording the sequence, and playing it back in reverse. Since we're already
  // doing a full iteration above, we can just record the sequence manually and
  // avoid the cost of having ReversePostOrderTraversal compute it.
  bool TopDownNestingDetected = false;
  for (SmallVectorImpl<BasicBlock *>::const_reverse_iterator
       RI = PostOrder.rbegin(), RE = PostOrder.rend(); RI != RE; ++RI)
    TopDownNestingDetected |= VisitTopDown(*RI, BBStates, Releases);

  return TopDownNestingDetected && BottomUpNestingDetected;
}

/// MoveCalls - Move the calls in RetainsToMove and ReleasesToMove.
void ObjCARCOpt::MoveCalls(Value *Arg,
                           RRInfo &RetainsToMove,
                           RRInfo &ReleasesToMove,
                           MapVector<Value *, RRInfo> &Retains,
                           DenseMap<Value *, RRInfo> &Releases,
                           SmallVectorImpl<Instruction *> &DeadInsts) {
  const Type *ArgTy = Arg->getType();
  const Type *ParamTy =
    (RetainRVFunc ? RetainRVFunc :
     RetainFunc ? RetainFunc :
     RetainBlockFunc)->arg_begin()->getType();

  // Insert the new retain and release calls.
  for (SmallPtrSet<Instruction *, 2>::const_iterator
       PI = ReleasesToMove.ReverseInsertPts.begin(),
       PE = ReleasesToMove.ReverseInsertPts.end(); PI != PE; ++PI) {
    Instruction *InsertPt = *PI;
    Value *MyArg = ArgTy == ParamTy ? Arg :
                   new BitCastInst(Arg, ParamTy, "", InsertPt);
    CallInst *Call =
      CallInst::Create(RetainsToMove.IsRetainBlock ?
                         RetainBlockFunc : RetainFunc,
                       MyArg, "", InsertPt);
    Call->setDoesNotThrow();
    if (!RetainsToMove.IsRetainBlock)
      Call->setTailCall();
  }
  for (SmallPtrSet<Instruction *, 2>::const_iterator
       PI = RetainsToMove.ReverseInsertPts.begin(),
       PE = RetainsToMove.ReverseInsertPts.end(); PI != PE; ++PI) {
    Instruction *LastUse = *PI;
    Instruction *InsertPts[] = { 0, 0, 0 };
    if (InvokeInst *II = dyn_cast<InvokeInst>(LastUse)) {
      // We can't insert code immediately after an invoke instruction, so
      // insert code at the beginning of both successor blocks instead.
      // The invoke's return value isn't available in the unwind block,
      // but our releases will never depend on it, because they must be
      // paired with retains from before the invoke.
      InsertPts[0] = II->getNormalDest()->getFirstNonPHI();
      InsertPts[1] = II->getUnwindDest()->getFirstNonPHI();
    } else {
      // Insert code immediately after the last use.
      InsertPts[0] = llvm::next(BasicBlock::iterator(LastUse));
    }

    for (Instruction **I = InsertPts; *I; ++I) {
      Instruction *InsertPt = *I;
      Value *MyArg = ArgTy == ParamTy ? Arg :
                     new BitCastInst(Arg, ParamTy, "", InsertPt);
      CallInst *Call = CallInst::Create(ReleaseFunc, MyArg, "", InsertPt);
      // Attach a clang.imprecise_release metadata tag, if appropriate.
      if (MDNode *M = ReleasesToMove.ReleaseMetadata)
        Call->setMetadata(ImpreciseReleaseMDKind, M);
      Call->setDoesNotThrow();
      if (ReleasesToMove.IsTailCallRelease)
        Call->setTailCall();
    }
  }

  // Delete the original retain and release calls.
  for (SmallPtrSet<Instruction *, 2>::const_iterator
       AI = RetainsToMove.Calls.begin(),
       AE = RetainsToMove.Calls.end(); AI != AE; ++AI) {
    Instruction *OrigRetain = *AI;
    Retains.blot(OrigRetain);
    DeadInsts.push_back(OrigRetain);
  }
  for (SmallPtrSet<Instruction *, 2>::const_iterator
       AI = ReleasesToMove.Calls.begin(),
       AE = ReleasesToMove.Calls.end(); AI != AE; ++AI) {
    Instruction *OrigRelease = *AI;
    Releases.erase(OrigRelease);
    DeadInsts.push_back(OrigRelease);
  }
}

bool
ObjCARCOpt::PerformCodePlacement(DenseMap<const BasicBlock *, BBState>
                                   &BBStates,
                                 MapVector<Value *, RRInfo> &Retains,
                                 DenseMap<Value *, RRInfo> &Releases) {
  bool AnyPairsCompletelyEliminated = false;
  RRInfo RetainsToMove;
  RRInfo ReleasesToMove;
  SmallVector<Instruction *, 4> NewRetains;
  SmallVector<Instruction *, 4> NewReleases;
  SmallVector<Instruction *, 8> DeadInsts;

  for (MapVector<Value *, RRInfo>::const_iterator I = Retains.begin(),
       E = Retains.end(); I != E; ) {
    Value *V = (I++)->first;
    if (!V) continue; // blotted

    Instruction *Retain = cast<Instruction>(V);
    Value *Arg = GetObjCArg(Retain);

    // If the object being released is in static or stack storage, we know it's
    // not being managed by ObjC reference counting, so we can delete pairs
    // regardless of what possible decrements or uses lie between them.
    bool KnownSafe = isa<Constant>(Arg) || isa<AllocaInst>(Arg);

    // If a pair happens in a region where it is known that the reference count
    // is already incremented, we can similarly ignore possible decrements.
    bool KnownIncrementedTD = true, KnownIncrementedBU = true;

    // Connect the dots between the top-down-collected RetainsToMove and
    // bottom-up-collected ReleasesToMove to form sets of related calls.
    // This is an iterative process so that we connect multiple releases
    // to multiple retains if needed.
    unsigned OldDelta = 0;
    unsigned NewDelta = 0;
    unsigned OldCount = 0;
    unsigned NewCount = 0;
    bool FirstRelease = true;
    bool FirstRetain = true;
    NewRetains.push_back(Retain);
    for (;;) {
      for (SmallVectorImpl<Instruction *>::const_iterator
           NI = NewRetains.begin(), NE = NewRetains.end(); NI != NE; ++NI) {
        Instruction *NewRetain = *NI;
        MapVector<Value *, RRInfo>::const_iterator It = Retains.find(NewRetain);
        assert(It != Retains.end());
        const RRInfo &NewRetainRRI = It->second;
        KnownIncrementedTD &= NewRetainRRI.KnownIncremented;
        for (SmallPtrSet<Instruction *, 2>::const_iterator
             LI = NewRetainRRI.Calls.begin(),
             LE = NewRetainRRI.Calls.end(); LI != LE; ++LI) {
          Instruction *NewRetainRelease = *LI;
          DenseMap<Value *, RRInfo>::const_iterator Jt =
            Releases.find(NewRetainRelease);
          if (Jt == Releases.end())
            goto next_retain;
          const RRInfo &NewRetainReleaseRRI = Jt->second;
          assert(NewRetainReleaseRRI.Calls.count(NewRetain));
          if (ReleasesToMove.Calls.insert(NewRetainRelease)) {
            OldDelta -=
              BBStates[NewRetainRelease->getParent()].GetAllPathCount();

            // Merge the ReleaseMetadata and IsTailCallRelease values.
            if (FirstRelease) {
              ReleasesToMove.ReleaseMetadata =
                NewRetainReleaseRRI.ReleaseMetadata;
              ReleasesToMove.IsTailCallRelease =
                NewRetainReleaseRRI.IsTailCallRelease;
              FirstRelease = false;
            } else {
              if (ReleasesToMove.ReleaseMetadata !=
                    NewRetainReleaseRRI.ReleaseMetadata)
                ReleasesToMove.ReleaseMetadata = 0;
              if (ReleasesToMove.IsTailCallRelease !=
                    NewRetainReleaseRRI.IsTailCallRelease)
                ReleasesToMove.IsTailCallRelease = false;
            }

            // Collect the optimal insertion points.
            if (!KnownSafe)
              for (SmallPtrSet<Instruction *, 2>::const_iterator
                   RI = NewRetainReleaseRRI.ReverseInsertPts.begin(),
                   RE = NewRetainReleaseRRI.ReverseInsertPts.end();
                   RI != RE; ++RI) {
                Instruction *RIP = *RI;
                if (ReleasesToMove.ReverseInsertPts.insert(RIP))
                  NewDelta -= BBStates[RIP->getParent()].GetAllPathCount();
              }
            NewReleases.push_back(NewRetainRelease);
          }
        }
      }
      NewRetains.clear();
      if (NewReleases.empty()) break;

      // Back the other way.
      for (SmallVectorImpl<Instruction *>::const_iterator
           NI = NewReleases.begin(), NE = NewReleases.end(); NI != NE; ++NI) {
        Instruction *NewRelease = *NI;
        DenseMap<Value *, RRInfo>::const_iterator It =
          Releases.find(NewRelease);
        assert(It != Releases.end());
        const RRInfo &NewReleaseRRI = It->second;
        KnownIncrementedBU &= NewReleaseRRI.KnownIncremented;
        for (SmallPtrSet<Instruction *, 2>::const_iterator
             LI = NewReleaseRRI.Calls.begin(),
             LE = NewReleaseRRI.Calls.end(); LI != LE; ++LI) {
          Instruction *NewReleaseRetain = *LI;
          MapVector<Value *, RRInfo>::const_iterator Jt =
            Retains.find(NewReleaseRetain);
          if (Jt == Retains.end())
            goto next_retain;
          const RRInfo &NewReleaseRetainRRI = Jt->second;
          assert(NewReleaseRetainRRI.Calls.count(NewRelease));
          if (RetainsToMove.Calls.insert(NewReleaseRetain)) {
            unsigned PathCount =
              BBStates[NewReleaseRetain->getParent()].GetAllPathCount();
            OldDelta += PathCount;
            OldCount += PathCount;

            // Merge the IsRetainBlock values.
            if (FirstRetain) {
              RetainsToMove.IsRetainBlock = NewReleaseRetainRRI.IsRetainBlock;
              FirstRetain = false;
            } else if (ReleasesToMove.IsRetainBlock !=
                       NewReleaseRetainRRI.IsRetainBlock)
              // It's not possible to merge the sequences if one uses
              // objc_retain and the other uses objc_retainBlock.
              goto next_retain;

            // Collect the optimal insertion points.
            if (!KnownSafe)
              for (SmallPtrSet<Instruction *, 2>::const_iterator
                   RI = NewReleaseRetainRRI.ReverseInsertPts.begin(),
                   RE = NewReleaseRetainRRI.ReverseInsertPts.end();
                   RI != RE; ++RI) {
                Instruction *RIP = *RI;
                if (RetainsToMove.ReverseInsertPts.insert(RIP)) {
                  PathCount = BBStates[RIP->getParent()].GetAllPathCount();
                  NewDelta += PathCount;
                  NewCount += PathCount;
                }
              }
            NewRetains.push_back(NewReleaseRetain);
          }
        }
      }
      NewReleases.clear();
      if (NewRetains.empty()) break;
    }

    // If the pointer is known incremented, we can safely delete the pair
    // regardless of what's between them.
    if (KnownIncrementedTD || KnownIncrementedBU) {
      RetainsToMove.ReverseInsertPts.clear();
      ReleasesToMove.ReverseInsertPts.clear();
      NewCount = 0;
    }

    // Determine whether the original call points are balanced in the retain and
    // release calls through the program. If not, conservatively don't touch
    // them.
    // TODO: It's theoretically possible to do code motion in this case, as
    // long as the existing imbalances are maintained.
    if (OldDelta != 0)
      goto next_retain;

    // Determine whether the new insertion points we computed preserve the
    // balance of retain and release calls through the program.
    // TODO: If the fully aggressive solution isn't valid, try to find a
    // less aggressive solution which is.
    if (NewDelta != 0)
      goto next_retain;

    // Ok, everything checks out and we're all set. Let's move some code!
    Changed = true;
    AnyPairsCompletelyEliminated = NewCount == 0;
    NumRRs += OldCount - NewCount;
    MoveCalls(Arg, RetainsToMove, ReleasesToMove, Retains, Releases, DeadInsts);

  next_retain:
    NewReleases.clear();
    NewRetains.clear();
    RetainsToMove.clear();
    ReleasesToMove.clear();
  }

  // Now that we're done moving everything, we can delete the newly dead
  // instructions, as we no longer need them as insert points.
  while (!DeadInsts.empty())
    EraseInstruction(DeadInsts.pop_back_val());

  return AnyPairsCompletelyEliminated;
}

/// OptimizeWeakCalls - Weak pointer optimizations.
void ObjCARCOpt::OptimizeWeakCalls(Function &F) {
  // First, do memdep-style RLE and S2L optimizations. We can't use memdep
  // itself because it uses AliasAnalysis and we need to do provenance
  // queries instead.
  for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
    Instruction *Inst = &*I++;
    InstructionClass Class = GetBasicInstructionClass(Inst);
    if (Class != IC_LoadWeak && Class != IC_LoadWeakRetained)
      continue;

    // Delete objc_loadWeak calls with no users.
    if (Class == IC_LoadWeak && Inst->use_empty()) {
      Inst->eraseFromParent();
      continue;
    }

    // TODO: For now, just look for an earlier available version of this value
    // within the same block. Theoretically, we could do memdep-style non-local
    // analysis too, but that would want caching. A better approach would be to
    // use the technique that EarlyCSE uses.
    inst_iterator Current = llvm::prior(I);
    BasicBlock *CurrentBB = Current.getBasicBlockIterator();
    for (BasicBlock::iterator B = CurrentBB->begin(),
                              J = Current.getInstructionIterator();
         J != B; --J) {
      Instruction *EarlierInst = &*llvm::prior(J);
      InstructionClass EarlierClass = GetInstructionClass(EarlierInst);
      switch (EarlierClass) {
      case IC_LoadWeak:
      case IC_LoadWeakRetained: {
        // If this is loading from the same pointer, replace this load's value
        // with that one.
        CallInst *Call = cast<CallInst>(Inst);
        CallInst *EarlierCall = cast<CallInst>(EarlierInst);
        Value *Arg = Call->getArgOperand(0);
        Value *EarlierArg = EarlierCall->getArgOperand(0);
        switch (PA.getAA()->alias(Arg, EarlierArg)) {
        case AliasAnalysis::MustAlias:
          Changed = true;
          // If the load has a builtin retain, insert a plain retain for it.
          if (Class == IC_LoadWeakRetained) {
            CallInst *CI =
              CallInst::Create(getRetainCallee(F.getParent()), EarlierCall,
                               "", Call);
            CI->setTailCall();
          }
          // Zap the fully redundant load.
          Call->replaceAllUsesWith(EarlierCall);
          Call->eraseFromParent();
          goto clobbered;
        case AliasAnalysis::MayAlias:
        case AliasAnalysis::PartialAlias:
          goto clobbered;
        case AliasAnalysis::NoAlias:
          break;
        }
        break;
      }
      case IC_StoreWeak:
      case IC_InitWeak: {
        // If this is storing to the same pointer and has the same size etc.
        // replace this load's value with the stored value.
        CallInst *Call = cast<CallInst>(Inst);
        CallInst *EarlierCall = cast<CallInst>(EarlierInst);
        Value *Arg = Call->getArgOperand(0);
        Value *EarlierArg = EarlierCall->getArgOperand(0);
        switch (PA.getAA()->alias(Arg, EarlierArg)) {
        case AliasAnalysis::MustAlias:
          Changed = true;
          // If the load has a builtin retain, insert a plain retain for it.
          if (Class == IC_LoadWeakRetained) {
            CallInst *CI =
              CallInst::Create(getRetainCallee(F.getParent()), EarlierCall,
                               "", Call);
            CI->setTailCall();
          }
          // Zap the fully redundant load.
          Call->replaceAllUsesWith(EarlierCall->getArgOperand(1));
          Call->eraseFromParent();
          goto clobbered;
        case AliasAnalysis::MayAlias:
        case AliasAnalysis::PartialAlias:
          goto clobbered;
        case AliasAnalysis::NoAlias:
          break;
        }
        break;
      }
      case IC_MoveWeak:
      case IC_CopyWeak:
        // TOOD: Grab the copied value.
        goto clobbered;
      case IC_AutoreleasepoolPush:
      case IC_None:
      case IC_User:
        // Weak pointers are only modified through the weak entry points
        // (and arbitrary calls, which could call the weak entry points).
        break;
      default:
        // Anything else could modify the weak pointer.
        goto clobbered;
      }
    }
  clobbered:;
  }

  // Then, for each destroyWeak with an alloca operand, check to see if
  // the alloca and all its users can be zapped.
  for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
    Instruction *Inst = &*I++;
    InstructionClass Class = GetBasicInstructionClass(Inst);
    if (Class != IC_DestroyWeak)
      continue;

    CallInst *Call = cast<CallInst>(Inst);
    Value *Arg = Call->getArgOperand(0);
    if (AllocaInst *Alloca = dyn_cast<AllocaInst>(Arg)) {
      for (Value::use_iterator UI = Alloca->use_begin(),
           UE = Alloca->use_end(); UI != UE; ++UI) {
        Instruction *UserInst = cast<Instruction>(*UI);
        switch (GetBasicInstructionClass(UserInst)) {
        case IC_InitWeak:
        case IC_StoreWeak:
        case IC_DestroyWeak:
          continue;
        default:
          goto done;
        }
      }
      Changed = true;
      for (Value::use_iterator UI = Alloca->use_begin(),
           UE = Alloca->use_end(); UI != UE; ) {
        CallInst *UserInst = cast<CallInst>(*UI++);
        if (!UserInst->use_empty())
          UserInst->replaceAllUsesWith(UserInst->getOperand(1));
        UserInst->eraseFromParent();
      }
      Alloca->eraseFromParent();
    done:;
    }
  }
}

/// OptimizeSequences - Identify program paths which execute sequences of
/// retains and releases which can be eliminated.
bool ObjCARCOpt::OptimizeSequences(Function &F) {
  /// Releases, Retains - These are used to store the results of the main flow
  /// analysis. These use Value* as the key instead of Instruction* so that the
  /// map stays valid when we get around to rewriting code and calls get
  /// replaced by arguments.
  DenseMap<Value *, RRInfo> Releases;
  MapVector<Value *, RRInfo> Retains;

  /// BBStates, This is used during the traversal of the function to track the
  /// states for each identified object at each block.
  DenseMap<const BasicBlock *, BBState> BBStates;

  // Analyze the CFG of the function, and all instructions.
  bool NestingDetected = Visit(F, BBStates, Retains, Releases);

  // Transform.
  return PerformCodePlacement(BBStates, Retains, Releases) && NestingDetected;
}

/// OptimizeReturns - Look for this pattern:
///