ObjCARC.cpp

      const User *I = *UI;
      if (isa<ReturnInst>(I) || GetBasicInstructionClass(I) == IC_RetainRV)
        return;
      if (isa<BitCastInst>(I))
        Users.push_back(I);
    }
  } while (!Users.empty());

  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))) {
        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))) {
        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;

        // 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);
          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;
      PtrState &S = MyStates.getPtrTopDownState(Arg);
      for (succ_const_iterator SI(TI), SE(TI, false); SI != SE; ++SI) {
        PtrState &SuccS = BBStates[*SI].getPtrBottomUpState(Arg);
        switch (SuccS.GetSeq()) {
        case S_None:
        case S_CanRelease: {
          if (!S.RRI.KnownSafe && !SuccS.RRI.KnownSafe)
            S.ClearSequenceProgress();
          continue;
        }
        case S_Use:
          SomeSuccHasSame = true;
          break;
        case S_Stop:
        case S_Release:
        case S_MovableRelease:
          if (!S.RRI.KnownSafe && !SuccS.RRI.KnownSafe)
            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)
        S.ClearSequenceProgress();
    }
    case S_CanRelease: {
      const Value *Arg = I->first;
      const TerminatorInst *TI = cast<TerminatorInst>(&BB->back());
      bool SomeSuccHasSame = false;
      bool AllSuccsHaveSame = true;
      PtrState &S = MyStates.getPtrTopDownState(Arg);
      for (succ_const_iterator SI(TI), SE(TI, false); SI != SE; ++SI) {
        PtrState &SuccS = BBStates[*SI].getPtrBottomUpState(Arg);
        switch (SuccS.GetSeq()) {
        case S_None: {
          if (!S.RRI.KnownSafe && !SuccS.RRI.KnownSafe)
            S.ClearSequenceProgress();
          continue;
        }
        case S_CanRelease:
          SomeSuccHasSame = true;
          break;
        case S_Stop:
        case S_Release:
        case S_MovableRelease:
        case S_Use:
          if (!S.RRI.KnownSafe && !SuccS.RRI.KnownSafe)
            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)
        S.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 we haven't seen this node yet, then we've found a CFG cycle.
      // Be optimistic here; it's CheckForCFGHazards' job detect trouble.
      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.KnownSafe = S.IsKnownNested() || S.IsKnownIncremented();
      S.RRI.IsTailCallRelease = cast<CallInst>(Inst)->isTailCall();
      S.RRI.Calls.insert(Inst);

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

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

      // An non-copy-on-escape objc_retainBlock call with just a use still
      // needs to be kept, because it may be copying a block from the stack
      // to the heap.
      if (Class == IC_RetainBlock &&
          !Inst->getMetadata(CopyOnEscapeMDKind) &&
          S.GetSeq() == S_Use)
        S.SetSeq(S_CanRelease);

      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;
          if (S.RRI.IsRetainBlock)
            S.RRI.CopyOnEscape = !!Inst->getMetadata(CopyOnEscapeMDKind);
          Retains[Inst] = S.RRI;
        }
        S.ClearSequenceProgress();
        break;
      case S_None:
        break;
      case S_Retain:
        llvm_unreachable("bottom-up pointer in retain state!");
      }
      continue;
    }
    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 releases.
      if (CanAlterRefCount(Inst, Ptr, PA, Class)) {
        S.DecrementRefCount();
        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)) {
          assert(S.RRI.ReverseInsertPts.empty());
          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);
          assert(S.RRI.ReverseInsertPts.empty());
          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);
      assert(I != BBStates.end());
      // If we haven't seen this node yet, then we've found a CFG cycle.
      // Be optimistic here; it's CheckForCFGHazards' job detect trouble.
      if (!I->second.isVisitedTopDown())
        continue;
      MyStates.InitFromPred(I->second);
      while (PI != PE) {
        Pred = *PI++;
        if (Pred != BB) {
          I = BBStates.find(Pred);
          assert(I != BBStates.end());
          if (I->second.isVisitedTopDown())
            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;
        if (S.RRI.IsRetainBlock)
          S.RRI.CopyOnEscape = !!Inst->getMetadata(CopyOnEscapeMDKind);
        // Don't check S.IsKnownIncremented() here because it's not
        // sufficient.
        S.RRI.KnownSafe = S.IsKnownNested();
        S.RRI.Calls.insert(Inst);
      }

      S.SetAtLeastOneRefCount();
      S.IncrementRefCount();
      S.IncrementNestCount();
      continue;
    }
    case IC_Release: {
      Arg = GetObjCArg(Inst);

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

      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 (CanAlterRefCount(Inst, Ptr, PA, Class)) {
        S.DecrementRefCount();
        switch (Seq) {
        case S_Retain:
          S.SetSeq(S_CanRelease);
          assert(S.RRI.ReverseInsertPts.empty());
          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_Retain:
        // A non-copy-on-scape objc_retainBlock call may be responsible for
        // copying the block data from the stack to the heap. Model this by
        // moving it straight from S_Retain to S_Use.
        if (S.RRI.IsRetainBlock &&
            !S.RRI.CopyOnEscape &&
            CanUse(Inst, Ptr, PA, Class)) {
          assert(S.RRI.ReverseInsertPts.empty());
          S.RRI.ReverseInsertPts.insert(Inst);
          S.SetSeq(S_Use);
        }
        break;
      case S_Use:
      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 reverse-postorder on the reverse CFG for bottom-up, 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. We can't use
  // ReversePostOrderTraversal here because we want to walk up from each
  // function exit point.
  SmallPtrSet<BasicBlock *, 16> Visited;
  SmallVector<std::pair<BasicBlock *, pred_iterator>, 16> Stack;
  SmallVector<BasicBlock *, 16> Order;
  for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
    BasicBlock *BB = I;
    if (BB->getTerminator()->getNumSuccessors() == 0)
      Stack.push_back(std::make_pair(BB, pred_begin(BB)));
  }
  while (!Stack.empty()) {
    pred_iterator End = pred_end(Stack.back().first);
    while (Stack.back().second != End) {
      BasicBlock *BB = *Stack.back().second++;
      if (Visited.insert(BB))
        Stack.push_back(std::make_pair(BB, pred_begin(BB)));
    }
    Order.push_back(Stack.pop_back_val().first);
  }
  bool BottomUpNestingDetected = false;
  for (SmallVectorImpl<BasicBlock *>::const_reverse_iterator I =
         Order.rbegin(), E = Order.rend(); I != E; ++I) {
    BasicBlock *BB = *I;
    BottomUpNestingDetected |= VisitBottomUp(BB, BBStates, Retains);
  }

  // Use regular reverse-postorder for top-down.
  bool TopDownNestingDetected = false;
  typedef ReversePostOrderTraversal<Function *> RPOTType;
  RPOTType RPOT(&F);
  for (RPOTType::rpo_iterator I = RPOT.begin(), E = RPOT.end(); I != E; ++I) {
    BasicBlock *BB = *I;
    TopDownNestingDetected |= VisitTopDown(BB, 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,
                           Module *M) {
  Type *ArgTy = Arg->getType();
  Type *ParamTy = PointerType::getUnqual(Type::getInt8Ty(ArgTy->getContext()));

  // 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 ?
                         getRetainBlockCallee(M) : getRetainCallee(M),
                       MyArg, "", InsertPt);
    Call->setDoesNotThrow();
    if (RetainsToMove.CopyOnEscape)
      Call->setMetadata(CopyOnEscapeMDKind,
                        MDNode::get(M->getContext(), ArrayRef<Value *>()));
    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()->getFirstInsertionPt();
      InsertPts[1] = II->getUnwindDest()->getFirstInsertionPt();
    } 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(getReleaseCallee(M), 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,
                                 Module *M) {
  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; ++I) {
    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 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);
   
    // Same for stack storage, unless this is a non-copy-on-escape
    // objc_retainBlock call, which is responsible for copying the block data
    // from the stack to the heap.
    if ((!I->second.IsRetainBlock || I->second.CopyOnEscape) &&
        isa<AllocaInst>(Arg))
      KnownSafe = true;

    // A constant pointer can't be pointing to an object on the heap. It may
    // be reference-counted, but it won't be deleted.
    if (const LoadInst *LI = dyn_cast<LoadInst>(Arg))
      if (const GlobalVariable *GV =
            dyn_cast<GlobalVariable>(
              StripPointerCastsAndObjCCalls(LI->getPointerOperand())))
        if (GV->isConstant())
          KnownSafe = true;

    // 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 KnownSafeTD = true, KnownSafeBU = 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;
        KnownSafeTD &= NewRetainRRI.KnownSafe;
        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;
        KnownSafeBU &= NewReleaseRRI.KnownSafe;
        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;
              RetainsToMove.CopyOnEscape = NewReleaseRetainRRI.CopyOnEscape;
              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;

            // Merge the CopyOnEscape values.
            RetainsToMove.CopyOnEscape &= NewReleaseRetainRRI.CopyOnEscape;

            // 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 or nested, we can safely delete the
    // pair regardless of what's between them.
    if (KnownSafeTD || KnownSafeBU) {
      RetainsToMove.ReverseInsertPts.clear();
      ReleasesToMove.ReverseInsertPts.clear();
      NewCount = 0;
    } else {
      // 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;
    }

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

    // 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, M);

  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.