ObjCARC.cpp

        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, F.getParent()) &&
         NestingDetected;
}

/// OptimizeReturns - Look for this pattern:
///
///    %call = call i8* @something(...)
///    %2 = call i8* @objc_retain(i8* %call)
///    %3 = call i8* @objc_autorelease(i8* %2)
///    ret i8* %3
///
/// And delete the retain and autorelease.
///
/// Otherwise if it's just this:
///
///    %3 = call i8* @objc_autorelease(i8* %2)
///    ret i8* %3
///
/// convert the autorelease to autoreleaseRV.
void ObjCARCOpt::OptimizeReturns(Function &F) {
  if (!F.getReturnType()->isPointerTy())
    return;

  SmallPtrSet<Instruction *, 4> DependingInstructions;
  SmallPtrSet<const BasicBlock *, 4> Visited;
  for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
    BasicBlock *BB = FI;
    ReturnInst *Ret = dyn_cast<ReturnInst>(&BB->back());
    if (!Ret) continue;

    const Value *Arg = StripPointerCastsAndObjCCalls(Ret->getOperand(0));
    FindDependencies(NeedsPositiveRetainCount, Arg,
                     BB, Ret, DependingInstructions, Visited, PA);
    if (DependingInstructions.size() != 1)
      goto next_block;

    {
      CallInst *Autorelease =
        dyn_cast_or_null<CallInst>(*DependingInstructions.begin());
      if (!Autorelease)
        goto next_block;
      InstructionClass AutoreleaseClass =
        GetBasicInstructionClass(Autorelease);
      if (!IsAutorelease(AutoreleaseClass))
        goto next_block;
      if (GetObjCArg(Autorelease) != Arg)
        goto next_block;

      DependingInstructions.clear();
      Visited.clear();

      // Check that there is nothing that can affect the reference
      // count between the autorelease and the retain.
      FindDependencies(CanChangeRetainCount, Arg,
                       BB, Autorelease, DependingInstructions, Visited, PA);
      if (DependingInstructions.size() != 1)
        goto next_block;

      {
        CallInst *Retain =
          dyn_cast_or_null<CallInst>(*DependingInstructions.begin());

        // Check that we found a retain with the same argument.
        if (!Retain ||
            !IsRetain(GetBasicInstructionClass(Retain)) ||
            GetObjCArg(Retain) != Arg)
          goto next_block;

        DependingInstructions.clear();
        Visited.clear();

        // Convert the autorelease to an autoreleaseRV, since it's
        // returning the value.
        if (AutoreleaseClass == IC_Autorelease) {
          Autorelease->setCalledFunction(getAutoreleaseRVCallee(F.getParent()));
          AutoreleaseClass = IC_AutoreleaseRV;
        }

        // Check that there is nothing that can affect the reference
        // count between the retain and the call.
        FindDependencies(CanChangeRetainCount, Arg, BB, Retain,
                         DependingInstructions, Visited, PA);
        if (DependingInstructions.size() != 1)
          goto next_block;

        {
          CallInst *Call =
            dyn_cast_or_null<CallInst>(*DependingInstructions.begin());

          // Check that the pointer is the return value of the call.
          if (!Call || Arg != Call)
            goto next_block;

          // Check that the call is a regular call.
          InstructionClass Class = GetBasicInstructionClass(Call);
          if (Class != IC_CallOrUser && Class != IC_Call)
            goto next_block;

          // If so, we can zap the retain and autorelease.
          Changed = true;
          ++NumRets;
          EraseInstruction(Retain);
          EraseInstruction(Autorelease);
        }
      }
    }

  next_block:
    DependingInstructions.clear();
    Visited.clear();
  }
}

bool ObjCARCOpt::doInitialization(Module &M) {
  if (!EnableARCOpts)
    return false;

  Run = ModuleHasARC(M);
  if (!Run)
    return false;

  // Identify the imprecise release metadata kind.
  ImpreciseReleaseMDKind =
    M.getContext().getMDKindID("clang.imprecise_release");

  // Intuitively, objc_retain and others are nocapture, however in practice
  // they are not, because they return their argument value. And objc_release
  // calls finalizers.

  // These are initialized lazily.
  RetainRVCallee = 0;
  AutoreleaseRVCallee = 0;
  ReleaseCallee = 0;
  RetainCallee = 0;
  RetainBlockCallee = 0;
  AutoreleaseCallee = 0;

  return false;
}

bool ObjCARCOpt::runOnFunction(Function &F) {
  if (!EnableARCOpts)
    return false;

  // If nothing in the Module uses ARC, don't do anything.
  if (!Run)
    return false;

  Changed = false;

  PA.setAA(&getAnalysis<AliasAnalysis>());

  // This pass performs several distinct transformations. As a compile-time aid
  // when compiling code that isn't ObjC, skip these if the relevant ObjC
  // library functions aren't declared.

  // Preliminary optimizations. This also computs UsedInThisFunction.
  OptimizeIndividualCalls(F);

  // Optimizations for weak pointers.
  if (UsedInThisFunction & ((1 << IC_LoadWeak) |
                            (1 << IC_LoadWeakRetained) |
                            (1 << IC_StoreWeak) |
                            (1 << IC_InitWeak) |
                            (1 << IC_CopyWeak) |
                            (1 << IC_MoveWeak) |
                            (1 << IC_DestroyWeak)))
    OptimizeWeakCalls(F);

  // Optimizations for retain+release pairs.
  if (UsedInThisFunction & ((1 << IC_Retain) |
                            (1 << IC_RetainRV) |
                            (1 << IC_RetainBlock)))
    if (UsedInThisFunction & (1 << IC_Release))
      // Run OptimizeSequences until it either stops making changes or
      // no retain+release pair nesting is detected.
      while (OptimizeSequences(F)) {}

  // Optimizations if objc_autorelease is used.
  if (UsedInThisFunction &
      ((1 << IC_Autorelease) | (1 << IC_AutoreleaseRV)))
    OptimizeReturns(F);

  return Changed;
}

void ObjCARCOpt::releaseMemory() {
  PA.clear();
}

//===----------------------------------------------------------------------===//
// ARC contraction.
//===----------------------------------------------------------------------===//

// TODO: ObjCARCContract could insert PHI nodes when uses aren't
// dominated by single calls.

#include "llvm/Operator.h"
#include "llvm/InlineAsm.h"
#include "llvm/Analysis/Dominators.h"

STATISTIC(NumStoreStrongs, "Number objc_storeStrong calls formed");

namespace {
  /// ObjCARCContract - Late ARC optimizations.  These change the IR in a way
  /// that makes it difficult to be analyzed by ObjCARCOpt, so it's run late.
  class ObjCARCContract : public FunctionPass {
    bool Changed;
    AliasAnalysis *AA;
    DominatorTree *DT;
    ProvenanceAnalysis PA;

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

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

    /// RetainRVMarker - The inline asm string to insert between calls and
    /// RetainRV calls to make the optimization work on targets which need it.
    const MDString *RetainRVMarker;

    Constant *getStoreStrongCallee(Module *M);
    Constant *getRetainAutoreleaseCallee(Module *M);
    Constant *getRetainAutoreleaseRVCallee(Module *M);

    bool ContractAutorelease(Function &F, Instruction *Autorelease,
                             InstructionClass Class,
                             SmallPtrSet<Instruction *, 4>
                               &DependingInstructions,
                             SmallPtrSet<const BasicBlock *, 4>
                               &Visited);

    void ContractRelease(Instruction *Release,
                         inst_iterator &Iter);

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

  public:
    static char ID;
    ObjCARCContract() : FunctionPass(ID) {
      initializeObjCARCContractPass(*PassRegistry::getPassRegistry());
    }
  };
}

char ObjCARCContract::ID = 0;
INITIALIZE_PASS_BEGIN(ObjCARCContract,
                      "objc-arc-contract", "ObjC ARC contraction", false, false)
INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
INITIALIZE_PASS_DEPENDENCY(DominatorTree)
INITIALIZE_PASS_END(ObjCARCContract,
                    "objc-arc-contract", "ObjC ARC contraction", false, false)

Pass *llvm::createObjCARCContractPass() {
  return new ObjCARCContract();
}

void ObjCARCContract::getAnalysisUsage(AnalysisUsage &AU) const {
  AU.addRequired<AliasAnalysis>();
  AU.addRequired<DominatorTree>();
  AU.setPreservesCFG();
}

Constant *ObjCARCContract::getStoreStrongCallee(Module *M) {
  if (!StoreStrongCallee) {
    LLVMContext &C = M->getContext();
    Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
    Type *I8XX = PointerType::getUnqual(I8X);
    std::vector<Type *> Params;
    Params.push_back(I8XX);
    Params.push_back(I8X);

    AttrListPtr Attributes;
    Attributes.addAttr(~0u, Attribute::NoUnwind);
    Attributes.addAttr(1, Attribute::NoCapture);

    StoreStrongCallee =
      M->getOrInsertFunction(
        "objc_storeStrong",
        FunctionType::get(Type::getVoidTy(C), Params, /*isVarArg=*/false),
        Attributes);
  }
  return StoreStrongCallee;
}

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

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

/// ContractAutorelease - Merge an autorelease with a retain into a fused
/// call.
bool
ObjCARCContract::ContractAutorelease(Function &F, Instruction *Autorelease,
                                     InstructionClass Class,
                                     SmallPtrSet<Instruction *, 4>
                                       &DependingInstructions,
                                     SmallPtrSet<const BasicBlock *, 4>
                                       &Visited) {
  const Value *Arg = GetObjCArg(Autorelease);

  // Check that there are no instructions between the retain and the autorelease
  // (such as an autorelease_pop) which may change the count.
  CallInst *Retain = 0;
  if (Class == IC_AutoreleaseRV)
    FindDependencies(RetainAutoreleaseRVDep, Arg,
                     Autorelease->getParent(), Autorelease,
                     DependingInstructions, Visited, PA);
  else
    FindDependencies(RetainAutoreleaseDep, Arg,
                     Autorelease->getParent(), Autorelease,
                     DependingInstructions, Visited, PA);

  Visited.clear();
  if (DependingInstructions.size() != 1) {
    DependingInstructions.clear();
    return false;
  }

  Retain = dyn_cast_or_null<CallInst>(*DependingInstructions.begin());
  DependingInstructions.clear();

  if (!Retain ||
      GetBasicInstructionClass(Retain) != IC_Retain ||
      GetObjCArg(Retain) != Arg)
    return false;

  Changed = true;
  ++NumPeeps;

  if (Class == IC_AutoreleaseRV)
    Retain->setCalledFunction(getRetainAutoreleaseRVCallee(F.getParent()));
  else
    Retain->setCalledFunction(getRetainAutoreleaseCallee(F.getParent()));

  EraseInstruction(Autorelease);
  return true;
}

/// ContractRelease - Attempt to merge an objc_release with a store, load, and
/// objc_retain to form an objc_storeStrong. This can be a little tricky because
/// the instructions don't always appear in order, and there may be unrelated
/// intervening instructions.
void ObjCARCContract::ContractRelease(Instruction *Release,
                                      inst_iterator &Iter) {
  LoadInst *Load = dyn_cast<LoadInst>(GetObjCArg(Release));
  if (!Load || !Load->isSimple()) return;

  // For now, require everything to be in one basic block.
  BasicBlock *BB = Release->getParent();
  if (Load->getParent() != BB) return;

  // Walk down to find the store.
  BasicBlock::iterator I = Load, End = BB->end();
  ++I;
  AliasAnalysis::Location Loc = AA->getLocation(Load);
  while (I != End &&
         (&*I == Release ||
          IsRetain(GetBasicInstructionClass(I)) ||
          !(AA->getModRefInfo(I, Loc) & AliasAnalysis::Mod)))
    ++I;
  StoreInst *Store = dyn_cast<StoreInst>(I);
  if (!Store || !Store->isSimple()) return;
  if (Store->getPointerOperand() != Loc.Ptr) return;

  Value *New = StripPointerCastsAndObjCCalls(Store->getValueOperand());

  // Walk up to find the retain.
  I = Store;
  BasicBlock::iterator Begin = BB->begin();
  while (I != Begin && GetBasicInstructionClass(I) != IC_Retain)
    --I;
  Instruction *Retain = I;
  if (GetBasicInstructionClass(Retain) != IC_Retain) return;
  if (GetObjCArg(Retain) != New) return;

  Changed = true;
  ++NumStoreStrongs;

  LLVMContext &C = Release->getContext();
  Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
  Type *I8XX = PointerType::getUnqual(I8X);

  Value *Args[] = { Load->getPointerOperand(), New };
  if (Args[0]->getType() != I8XX)
    Args[0] = new BitCastInst(Args[0], I8XX, "", Store);
  if (Args[1]->getType() != I8X)
    Args[1] = new BitCastInst(Args[1], I8X, "", Store);
  CallInst *StoreStrong =
    CallInst::Create(getStoreStrongCallee(BB->getParent()->getParent()),
                     Args, "", Store);
  StoreStrong->setDoesNotThrow();
  StoreStrong->setDebugLoc(Store->getDebugLoc());

  if (&*Iter == Store) ++Iter;
  Store->eraseFromParent();
  Release->eraseFromParent();
  EraseInstruction(Retain);
  if (Load->use_empty())
    Load->eraseFromParent();
}

bool ObjCARCContract::doInitialization(Module &M) {
  Run = ModuleHasARC(M);
  if (!Run)
    return false;

  // These are initialized lazily.
  StoreStrongCallee = 0;
  RetainAutoreleaseCallee = 0;
  RetainAutoreleaseRVCallee = 0;

  // Initialize RetainRVMarker.
  RetainRVMarker = 0;
  if (NamedMDNode *NMD =
        M.getNamedMetadata("clang.arc.retainAutoreleasedReturnValueMarker"))
    if (NMD->getNumOperands() == 1) {
      const MDNode *N = NMD->getOperand(0);
      if (N->getNumOperands() == 1)
        if (const MDString *S = dyn_cast<MDString>(N->getOperand(0)))
          RetainRVMarker = S;
    }

  return false;
}

bool ObjCARCContract::runOnFunction(Function &F) {
  if (!EnableARCOpts)
    return false;

  // If nothing in the Module uses ARC, don't do anything.
  if (!Run)
    return false;

  Changed = false;
  AA = &getAnalysis<AliasAnalysis>();
  DT = &getAnalysis<DominatorTree>();

  PA.setAA(&getAnalysis<AliasAnalysis>());

  // For ObjC library calls which return their argument, replace uses of the
  // argument with uses of the call return value, if it dominates the use. This
  // reduces register pressure.
  SmallPtrSet<Instruction *, 4> DependingInstructions;
  SmallPtrSet<const BasicBlock *, 4> Visited;
  for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
    Instruction *Inst = &*I++;

    // Only these library routines return their argument. In particular,
    // objc_retainBlock does not necessarily return its argument.
    InstructionClass Class = GetBasicInstructionClass(Inst);
    switch (Class) {
    case IC_Retain:
    case IC_FusedRetainAutorelease:
    case IC_FusedRetainAutoreleaseRV:
      break;
    case IC_Autorelease:
    case IC_AutoreleaseRV:
      if (ContractAutorelease(F, Inst, Class, DependingInstructions, Visited))
        continue;
      break;
    case IC_RetainRV: {
      // If we're compiling for a target which needs a special inline-asm
      // marker to do the retainAutoreleasedReturnValue optimization,
      // insert it now.
      if (!RetainRVMarker)
        break;
      BasicBlock::iterator BBI = Inst;
      --BBI;
      while (isNoopInstruction(BBI)) --BBI;
      if (&*BBI == GetObjCArg(Inst)) {
        InlineAsm *IA =
          InlineAsm::get(FunctionType::get(Type::getVoidTy(Inst->getContext()),
                                           /*isVarArg=*/false),
                         RetainRVMarker->getString(),
                         /*Constraints=*/"", /*hasSideEffects=*/true);
        CallInst::Create(IA, "", Inst);
      }
      break;
    }
    case IC_InitWeak: {
      // objc_initWeak(p, null) => *p = null
      CallInst *CI = cast<CallInst>(Inst);
      if (isNullOrUndef(CI->getArgOperand(1))) {
        Value *Null =
          ConstantPointerNull::get(cast<PointerType>(CI->getType()));
        Changed = true;
        new StoreInst(Null, CI->getArgOperand(0), CI);
        CI->replaceAllUsesWith(Null);
        CI->eraseFromParent();
      }
      continue;
    }
    case IC_Release:
      ContractRelease(Inst, I);
      continue;
    default:
      continue;
    }

    // Don't use GetObjCArg because we don't want to look through bitcasts
    // and such; to do the replacement, the argument must have type i8*.
    const Value *Arg = cast<CallInst>(Inst)->getArgOperand(0);
    for (;;) {
      // If we're compiling bugpointed code, don't get in trouble.
      if (!isa<Instruction>(Arg) && !isa<Argument>(Arg))
        break;
      // Look through the uses of the pointer.
      for (Value::const_use_iterator UI = Arg->use_begin(), UE = Arg->use_end();
           UI != UE; ) {
        Use &U = UI.getUse();
        unsigned OperandNo = UI.getOperandNo();
        ++UI; // Increment UI now, because we may unlink its element.
        if (Instruction *UserInst = dyn_cast<Instruction>(U.getUser()))
          if (Inst != UserInst && DT->dominates(Inst, UserInst)) {
            Changed = true;
            Instruction *Replacement = Inst;
            Type *UseTy = U.get()->getType();
            if (PHINode *PHI = dyn_cast<PHINode>(UserInst)) {
              // For PHI nodes, insert the bitcast in the predecessor block.
              unsigned ValNo =
                PHINode::getIncomingValueNumForOperand(OperandNo);
              BasicBlock *BB =
                PHI->getIncomingBlock(ValNo);
              if (Replacement->getType() != UseTy)
                Replacement = new BitCastInst(Replacement, UseTy, "",
                                              &BB->back());
              for (unsigned i = 0, e = PHI->getNumIncomingValues();
                   i != e; ++i)
                if (PHI->getIncomingBlock(i) == BB) {
                  // Keep the UI iterator valid.
                  if (&PHI->getOperandUse(
                        PHINode::getOperandNumForIncomingValue(i)) ==
                        &UI.getUse())
                    ++UI;
                  PHI->setIncomingValue(i, Replacement);
                }
            } else {
              if (Replacement->getType() != UseTy)
                Replacement = new BitCastInst(Replacement, UseTy, "", UserInst);
              U.set(Replacement);
            }
          }
      }

      // If Arg is a no-op casted pointer, strip one level of casts and
      // iterate.
      if (const BitCastInst *BI = dyn_cast<BitCastInst>(Arg))
        Arg = BI->getOperand(0);
      else if (isa<GEPOperator>(Arg) &&
               cast<GEPOperator>(Arg)->hasAllZeroIndices())
        Arg = cast<GEPOperator>(Arg)->getPointerOperand();
      else if (isa<GlobalAlias>(Arg) &&
               !cast<GlobalAlias>(Arg)->mayBeOverridden())
        Arg = cast<GlobalAlias>(Arg)->getAliasee();
      else
        break;
    }
  }

  return Changed;
}