lib/Transforms/Scalar/ObjCARC.cpp

   1 //===- ObjCARC.cpp - ObjC ARC Optimization --------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines ObjC ARC optimizations. ARC stands for
  11 // Automatic Reference Counting and is a system for managing reference counts
  12 // for objects in Objective C.
  13 //
  14 // The optimizations performed include elimination of redundant, partially
  15 // redundant, and inconsequential reference count operations, elimination of
  16 // redundant weak pointer operations, pattern-matching and replacement of
  17 // low-level operations into higher-level operations, and numerous minor
  18 // simplifications.
  19 //
  20 // This file also defines a simple ARC-aware AliasAnalysis.
  21 //
  22 // WARNING: This file knows about certain library functions. It recognizes them
  23 // by name, and hardwires knowedge of their semantics.
  24 //
  25 // WARNING: This file knows about how certain Objective-C library functions are
  26 // used. Naive LLVM IR transformations which would otherwise be
  27 // behavior-preserving may break these assumptions.
  28 //
  29 //===----------------------------------------------------------------------===//
  30
  31 #define DEBUG_TYPE "objc-arc"
  32 #include "llvm/Function.h"
  33 #include "llvm/Intrinsics.h"
  34 #include "llvm/GlobalVariable.h"
  35 #include "llvm/DerivedTypes.h"
  36 #include "llvm/Module.h"
  37 #include "llvm/Analysis/ValueTracking.h"
  38 #include "llvm/Transforms/Utils/Local.h"
  39 #include "llvm/Support/CallSite.h"
  40 #include "llvm/Support/CommandLine.h"
  41 #include "llvm/ADT/StringSwitch.h"
  42 #include "llvm/ADT/DenseMap.h"
  43 #include "llvm/ADT/STLExtras.h"
  44 using namespace llvm;
  45
  46 // A handy option to enable/disable all optimizations in this file.
  47 static cl::opt<bool> EnableARCOpts("enable-objc-arc-opts", cl::init(true));
  48
  49 //===----------------------------------------------------------------------===//
  50 // Misc. Utilities
  51 //===----------------------------------------------------------------------===//
  52
  53 namespace {
  54   /// MapVector - An associative container with fast insertion-order
  55   /// (deterministic) iteration over its elements. Plus the special
  56   /// blot operation.
  57   template<class KeyT, class ValueT>
  58   class MapVector {
  59     /// Map - Map keys to indices in Vector.
  60     typedef DenseMap<KeyT, size_t> MapTy;
  61     MapTy Map;
  62
  63     /// Vector - Keys and values.
  64     typedef std::vector<std::pair<KeyT, ValueT> > VectorTy;
  65     VectorTy Vector;
  66
  67   public:
  68     typedef typename VectorTy::iterator iterator;
  69     typedef typename VectorTy::const_iterator const_iterator;
  70     iterator begin() { return Vector.begin(); }
  71     iterator end() { return Vector.end(); }
  72     const_iterator begin() const { return Vector.begin(); }
  73     const_iterator end() const { return Vector.end(); }
  74
  75 #ifdef XDEBUG
  76     ~MapVector() {
  77       assert(Vector.size() >= Map.size()); // May differ due to blotting.
  78       for (typename MapTy::const_iterator I = Map.begin(), E = Map.end();
  79            I != E; ++I) {
  80         assert(I->second < Vector.size());
  81         assert(Vector[I->second].first == I->first);
  82       }
  83       for (typename VectorTy::const_iterator I = Vector.begin(),
  84            E = Vector.end(); I != E; ++I)
  85         assert(!I->first ||
  86                (Map.count(I->first) &&
  87                 Map[I->first] == size_t(I - Vector.begin())));
  88     }
  89 #endif
  90
  91     ValueT &operator[](KeyT Arg) {
  92       std::pair<typename MapTy::iterator, bool> Pair =
  93         Map.insert(std::make_pair(Arg, size_t(0)));
  94       if (Pair.second) {
  95         Pair.first->second = Vector.size();
  96         Vector.push_back(std::make_pair(Arg, ValueT()));
  97         return Vector.back().second;
  98       }
  99       return Vector[Pair.first->second].second;
 100     }
 101
 102     std::pair<iterator, bool>
 103     insert(const std::pair<KeyT, ValueT> &InsertPair) {
 104       std::pair<typename MapTy::iterator, bool> Pair =
 105         Map.insert(std::make_pair(InsertPair.first, size_t(0)));
 106       if (Pair.second) {
 107         Pair.first->second = Vector.size();
 108         Vector.push_back(InsertPair);
 109         return std::make_pair(llvm::prior(Vector.end()), true);
 110       }
 111       return std::make_pair(Vector.begin() + Pair.first->second, false);
 112     }
 113
 114     const_iterator find(KeyT Key) const {
 115       typename MapTy::const_iterator It = Map.find(Key);
 116       if (It == Map.end()) return Vector.end();
 117       return Vector.begin() + It->second;
 118     }
 119
 120     /// blot - This is similar to erase, but instead of removing the element
 121     /// from the vector, it just zeros out the key in the vector. This leaves
 122     /// iterators intact, but clients must be prepared for zeroed-out keys when
 123     /// iterating.
 124     void blot(KeyT Key) {
 125       typename MapTy::iterator It = Map.find(Key);
 126       if (It == Map.end()) return;
 127       Vector[It->second].first = KeyT();
 128       Map.erase(It);
 129     }
 130
 131     void clear() {
 132       Map.clear();
 133       Vector.clear();
 134     }
 135   };
 136 }
 137
 138 //===----------------------------------------------------------------------===//
 139 // ARC Utilities.
 140 //===----------------------------------------------------------------------===//
 141
 142 namespace {
 143   /// InstructionClass - A simple classification for instructions.
 144   enum InstructionClass {
 145     IC_Retain,              ///< objc_retain
 146     IC_RetainRV,            ///< objc_retainAutoreleasedReturnValue
 147     IC_RetainBlock,         ///< objc_retainBlock
 148     IC_Release,             ///< objc_release
 149     IC_Autorelease,         ///< objc_autorelease
 150     IC_AutoreleaseRV,       ///< objc_autoreleaseReturnValue
 151     IC_AutoreleasepoolPush, ///< objc_autoreleasePoolPush
 152     IC_AutoreleasepoolPop,  ///< objc_autoreleasePoolPop
 153     IC_NoopCast,            ///< objc_retainedObject, etc.
 154     IC_FusedRetainAutorelease, ///< objc_retainAutorelease
 155     IC_FusedRetainAutoreleaseRV, ///< objc_retainAutoreleaseReturnValue
 156     IC_LoadWeakRetained,    ///< objc_loadWeakRetained (primitive)
 157     IC_StoreWeak,           ///< objc_storeWeak (primitive)
 158     IC_InitWeak,            ///< objc_initWeak (derived)
 159     IC_LoadWeak,            ///< objc_loadWeak (derived)
 160     IC_MoveWeak,            ///< objc_moveWeak (derived)
 161     IC_CopyWeak,            ///< objc_copyWeak (derived)
 162     IC_DestroyWeak,         ///< objc_destroyWeak (derived)
 163     IC_CallOrUser,          ///< could call objc_release and/or "use" pointers
 164     IC_Call,                ///< could call objc_release
 165     IC_User,                ///< could "use" a pointer
 166     IC_None                 ///< anything else
 167   };
 168 }
 169
 170 /// IsPotentialUse - Test whether the given value is possible a
 171 /// reference-counted pointer.
 172 static bool IsPotentialUse(const Value *Op) {
 173   // Pointers to static or stack storage are not reference-counted pointers.
 174   if (isa<Constant>(Op) || isa<AllocaInst>(Op))
 175     return false;
 176   // Special arguments are not reference-counted.
 177   if (const Argument *Arg = dyn_cast<Argument>(Op))
 178     if (Arg->hasByValAttr() ||
 179         Arg->hasNestAttr() ||
 180         Arg->hasStructRetAttr())
 181       return false;
 182   // Only consider values with pointer types, and not function pointers.
 183   PointerType *Ty = dyn_cast<PointerType>(Op->getType());
 184   if (!Ty || isa<FunctionType>(Ty->getElementType()))
 185     return false;
 186   // Conservatively assume anything else is a potential use.
 187   return true;
 188 }
 189
 190 /// GetCallSiteClass - Helper for GetInstructionClass. Determines what kind
 191 /// of construct CS is.
 192 static InstructionClass GetCallSiteClass(ImmutableCallSite CS) {
 193   for (ImmutableCallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end();
 194        I != E; ++I)
 195     if (IsPotentialUse(*I))
 196       return CS.onlyReadsMemory() ? IC_User : IC_CallOrUser;
 197
 198   return CS.onlyReadsMemory() ? IC_None : IC_Call;
 199 }
 200
 201 /// GetFunctionClass - Determine if F is one of the special known Functions.
 202 /// If it isn't, return IC_CallOrUser.
 203 static InstructionClass GetFunctionClass(const Function *F) {
 204   Function::const_arg_iterator AI = F->arg_begin(), AE = F->arg_end();
 205
 206   // No arguments.
 207   if (AI == AE)
 208     return StringSwitch<InstructionClass>(F->getName())
 209       .Case("objc_autoreleasePoolPush",  IC_AutoreleasepoolPush)
 210       .Default(IC_CallOrUser);
 211
 212   // One argument.
 213   const Argument *A0 = AI++;
 214   if (AI == AE)
 215     // Argument is a pointer.
 216     if (PointerType *PTy = dyn_cast<PointerType>(A0->getType())) {
 217       Type *ETy = PTy->getElementType();
 218       // Argument is i8*.
 219       if (ETy->isIntegerTy(8))
 220         return StringSwitch<InstructionClass>(F->getName())
 221           .Case("objc_retain",                IC_Retain)
 222           .Case("objc_retainAutoreleasedReturnValue", IC_RetainRV)
 223           .Case("objc_retainBlock",           IC_RetainBlock)
 224           .Case("objc_release",               IC_Release)
 225           .Case("objc_autorelease",           IC_Autorelease)
 226           .Case("objc_autoreleaseReturnValue", IC_AutoreleaseRV)
 227           .Case("objc_autoreleasePoolPop",    IC_AutoreleasepoolPop)
 228           .Case("objc_retainedObject",        IC_NoopCast)
 229           .Case("objc_unretainedObject",      IC_NoopCast)
 230           .Case("objc_unretainedPointer",     IC_NoopCast)
 231           .Case("objc_retain_autorelease",    IC_FusedRetainAutorelease)
 232           .Case("objc_retainAutorelease",     IC_FusedRetainAutorelease)
 233           .Case("objc_retainAutoreleaseReturnValue",IC_FusedRetainAutoreleaseRV)
 234           .Default(IC_CallOrUser);
 235
 236       // Argument is i8**
 237       if (PointerType *Pte = dyn_cast<PointerType>(ETy))
 238         if (Pte->getElementType()->isIntegerTy(8))
 239           return StringSwitch<InstructionClass>(F->getName())
 240             .Case("objc_loadWeakRetained",      IC_LoadWeakRetained)
 241             .Case("objc_loadWeak",              IC_LoadWeak)
 242             .Case("objc_destroyWeak",           IC_DestroyWeak)
 243             .Default(IC_CallOrUser);
 244     }
 245
 246   // Two arguments, first is i8**.
 247   const Argument *A1 = AI++;
 248   if (AI == AE)
 249     if (PointerType *PTy = dyn_cast<PointerType>(A0->getType()))
 250       if (PointerType *Pte = dyn_cast<PointerType>(PTy->getElementType()))
 251         if (Pte->getElementType()->isIntegerTy(8))
 252           if (PointerType *PTy1 = dyn_cast<PointerType>(A1->getType())) {
 253             Type *ETy1 = PTy1->getElementType();
 254             // Second argument is i8*
 255             if (ETy1->isIntegerTy(8))
 256               return StringSwitch<InstructionClass>(F->getName())
 257                      .Case("objc_storeWeak",             IC_StoreWeak)
 258                      .Case("objc_initWeak",              IC_InitWeak)
 259                      .Default(IC_CallOrUser);
 260             // Second argument is i8**.
 261             if (PointerType *Pte1 = dyn_cast<PointerType>(ETy1))
 262               if (Pte1->getElementType()->isIntegerTy(8))
 263                 return StringSwitch<InstructionClass>(F->getName())
 264                        .Case("objc_moveWeak",              IC_MoveWeak)
 265                        .Case("objc_copyWeak",              IC_CopyWeak)
 266                        .Default(IC_CallOrUser);
 267           }
 268
 269   // Anything else.
 270   return IC_CallOrUser;
 271 }
 272
 273 /// GetInstructionClass - Determine what kind of construct V is.
 274 static InstructionClass GetInstructionClass(const Value *V) {
 275   if (const Instruction *I = dyn_cast<Instruction>(V)) {
 276     // Any instruction other than bitcast and gep with a pointer operand have a
 277     // use of an objc pointer. Bitcasts, GEPs, Selects, PHIs transfer a pointer
 278     // to a subsequent use, rather than using it themselves, in this sense.
 279     // As a short cut, several other opcodes are known to have no pointer
 280     // operands of interest. And ret is never followed by a release, so it's
 281     // not interesting to examine.
 282     switch (I->getOpcode()) {
 283     case Instruction::Call: {
 284       const CallInst *CI = cast<CallInst>(I);
 285       // Check for calls to special functions.
 286       if (const Function *F = CI->getCalledFunction()) {
 287         InstructionClass Class = GetFunctionClass(F);
 288         if (Class != IC_CallOrUser)
 289           return Class;
 290
 291         // None of the intrinsic functions do objc_release. For intrinsics, the
 292         // only question is whether or not they may be users.
 293         switch (F->getIntrinsicID()) {
 294         case 0: break;
 295         case Intrinsic::bswap: case Intrinsic::ctpop:
 296         case Intrinsic::ctlz: case Intrinsic::cttz:
 297         case Intrinsic::returnaddress: case Intrinsic::frameaddress:
 298         case Intrinsic::stacksave: case Intrinsic::stackrestore:
 299         case Intrinsic::vastart: case Intrinsic::vacopy: case Intrinsic::vaend:
 300         // Don't let dbg info affect our results.
 301         case Intrinsic::dbg_declare: case Intrinsic::dbg_value:
 302           // Short cut: Some intrinsics obviously don't use ObjC pointers.
 303           return IC_None;
 304         default:
 305           for (Function::const_arg_iterator AI = F->arg_begin(),
 306                AE = F->arg_end(); AI != AE; ++AI)
 307             if (IsPotentialUse(AI))
 308               return IC_User;
 309           return IC_None;
 310         }
 311       }
 312       return GetCallSiteClass(CI);
 313     }
 314     case Instruction::Invoke:
 315       return GetCallSiteClass(cast<InvokeInst>(I));
 316     case Instruction::BitCast:
 317     case Instruction::GetElementPtr:
 318     case Instruction::Select: case Instruction::PHI:
 319     case Instruction::Ret: case Instruction::Br:
 320     case Instruction::Switch: case Instruction::IndirectBr:
 321     case Instruction::Alloca: case Instruction::VAArg:
 322     case Instruction::Add: case Instruction::FAdd:
 323     case Instruction::Sub: case Instruction::FSub:
 324     case Instruction::Mul: case Instruction::FMul:
 325     case Instruction::SDiv: case Instruction::UDiv: case Instruction::FDiv:
 326     case Instruction::SRem: case Instruction::URem: case Instruction::FRem:
 327     case Instruction::Shl: case Instruction::LShr: case Instruction::AShr:
 328     case Instruction::And: case Instruction::Or: case Instruction::Xor:
 329     case Instruction::SExt: case Instruction::ZExt: case Instruction::Trunc:
 330     case Instruction::IntToPtr: case Instruction::FCmp:
 331     case Instruction::FPTrunc: case Instruction::FPExt:
 332     case Instruction::FPToUI: case Instruction::FPToSI:
 333     case Instruction::UIToFP: case Instruction::SIToFP:
 334     case Instruction::InsertElement: case Instruction::ExtractElement:
 335     case Instruction::ShuffleVector:
 336     case Instruction::ExtractValue:
 337       break;
 338     case Instruction::ICmp:
 339       // Comparing a pointer with null, or any other constant, isn't an
 340       // interesting use, because we don't care what the pointer points to, or
 341       // about the values of any other dynamic reference-counted pointers.
 342       if (IsPotentialUse(I->getOperand(1)))
 343         return IC_User;
 344       break;
 345     default:
 346       // For anything else, check all the operands.
 347       for (User::const_op_iterator OI = I->op_begin(), OE = I->op_end();
 348            OI != OE; ++OI)
 349         if (IsPotentialUse(*OI))
 350           return IC_User;
 351     }
 352   }
 353
 354   // Otherwise, it's totally inert for ARC purposes.
 355   return IC_None;
 356 }
 357
 358 /// GetBasicInstructionClass - Determine what kind of construct V is. This is
 359 /// similar to GetInstructionClass except that it only detects objc runtine
 360 /// calls. This allows it to be faster.
 361 static InstructionClass GetBasicInstructionClass(const Value *V) {
 362   if (const CallInst *CI = dyn_cast<CallInst>(V)) {
 363     if (const Function *F = CI->getCalledFunction())
 364       return GetFunctionClass(F);
 365     // Otherwise, be conservative.
 366     return IC_CallOrUser;
 367   }
 368
 369   // Otherwise, be conservative.
 370   return IC_User;
 371 }
 372
 373 /// IsRetain - Test if the the given class is objc_retain or
 374 /// equivalent.
 375 static bool IsRetain(InstructionClass Class) {
 376   return Class == IC_Retain ||
 377          Class == IC_RetainRV;
 378 }
 379
 380 /// IsAutorelease - Test if the the given class is objc_autorelease or
 381 /// equivalent.
 382 static bool IsAutorelease(InstructionClass Class) {
 383   return Class == IC_Autorelease ||
 384          Class == IC_AutoreleaseRV;
 385 }
 386
 387 /// IsForwarding - Test if the given class represents instructions which return
 388 /// their argument verbatim.
 389 static bool IsForwarding(InstructionClass Class) {
 390   // objc_retainBlock technically doesn't always return its argument
 391   // verbatim, but it doesn't matter for our purposes here.
 392   return Class == IC_Retain ||
 393          Class == IC_RetainRV ||
 394          Class == IC_Autorelease ||
 395          Class == IC_AutoreleaseRV ||
 396          Class == IC_RetainBlock ||
 397          Class == IC_NoopCast;
 398 }
 399
 400 /// IsNoopOnNull - Test if the given class represents instructions which do
 401 /// nothing if passed a null pointer.
 402 static bool IsNoopOnNull(InstructionClass Class) {
 403   return Class == IC_Retain ||
 404          Class == IC_RetainRV ||
 405          Class == IC_Release ||
 406          Class == IC_Autorelease ||
 407          Class == IC_AutoreleaseRV ||
 408          Class == IC_RetainBlock;
 409 }
 410
 411 /// IsAlwaysTail - Test if the given class represents instructions which are
 412 /// always safe to mark with the "tail" keyword.
 413 static bool IsAlwaysTail(InstructionClass Class) {
 414   // IC_RetainBlock may be given a stack argument.
 415   return Class == IC_Retain ||
 416          Class == IC_RetainRV ||
 417          Class == IC_Autorelease ||
 418          Class == IC_AutoreleaseRV;
 419 }
 420
 421 /// IsNoThrow - Test if the given class represents instructions which are always
 422 /// safe to mark with the nounwind attribute..
 423 static bool IsNoThrow(InstructionClass Class) {
 424   return Class == IC_Retain ||
 425          Class == IC_RetainRV ||
 426          Class == IC_RetainBlock ||
 427          Class == IC_Release ||
 428          Class == IC_Autorelease ||
 429          Class == IC_AutoreleaseRV ||
 430          Class == IC_AutoreleasepoolPush ||
 431          Class == IC_AutoreleasepoolPop;
 432 }
 433
 434 /// EraseInstruction - Erase the given instruction. ObjC calls return their
 435 /// argument verbatim, so if it's such a call and the return value has users,
 436 /// replace them with the argument value.
 437 static void EraseInstruction(Instruction *CI) {
 438   Value *OldArg = cast<CallInst>(CI)->getArgOperand(0);
 439
 440   bool Unused = CI->use_empty();
 441
 442   if (!Unused) {
 443     // Replace the return value with the argument.
 444     assert(IsForwarding(GetBasicInstructionClass(CI)) &&
 445            "Can't delete non-forwarding instruction with users!");
 446     CI->replaceAllUsesWith(OldArg);
 447   }
 448
 449   CI->eraseFromParent();
 450
 451   if (Unused)
 452     RecursivelyDeleteTriviallyDeadInstructions(OldArg);
 453 }
 454
 455 /// GetUnderlyingObjCPtr - This is a wrapper around getUnderlyingObject which
 456 /// also knows how to look through objc_retain and objc_autorelease calls, which
 457 /// we know to return their argument verbatim.
 458 static const Value *GetUnderlyingObjCPtr(const Value *V) {
 459   for (;;) {
 460     V = GetUnderlyingObject(V);
 461     if (!IsForwarding(GetBasicInstructionClass(V)))
 462       break;
 463     V = cast<CallInst>(V)->getArgOperand(0);
 464   }
 465
 466   return V;
 467 }
 468
 469 /// StripPointerCastsAndObjCCalls - This is a wrapper around
 470 /// Value::stripPointerCasts which also knows how to look through objc_retain
 471 /// and objc_autorelease calls, which we know to return their argument verbatim.
 472 static const Value *StripPointerCastsAndObjCCalls(const Value *V) {
 473   for (;;) {
 474     V = V->stripPointerCasts();
 475     if (!IsForwarding(GetBasicInstructionClass(V)))
 476       break;
 477     V = cast<CallInst>(V)->getArgOperand(0);
 478   }
 479   return V;
 480 }
 481
 482 /// StripPointerCastsAndObjCCalls - This is a wrapper around
 483 /// Value::stripPointerCasts which also knows how to look through objc_retain
 484 /// and objc_autorelease calls, which we know to return their argument verbatim.
 485 static Value *StripPointerCastsAndObjCCalls(Value *V) {
 486   for (;;) {
 487     V = V->stripPointerCasts();
 488     if (!IsForwarding(GetBasicInstructionClass(V)))
 489       break;
 490     V = cast<CallInst>(V)->getArgOperand(0);
 491   }
 492   return V;
 493 }
 494
 495 /// GetObjCArg - Assuming the given instruction is one of the special calls such
 496 /// as objc_retain or objc_release, return the argument value, stripped of no-op
 497 /// casts and forwarding calls.
 498 static Value *GetObjCArg(Value *Inst) {
 499   return StripPointerCastsAndObjCCalls(cast<CallInst>(Inst)->getArgOperand(0));
 500 }
 501
 502 /// IsObjCIdentifiedObject - This is similar to AliasAnalysis'
 503 /// isObjCIdentifiedObject, except that it uses special knowledge of
 504 /// ObjC conventions...
 505 static bool IsObjCIdentifiedObject(const Value *V) {
 506   // Assume that call results and arguments have their own "provenance".
 507   // Constants (including GlobalVariables) and Allocas are never
 508   // reference-counted.
 509   if (isa<CallInst>(V) || isa<InvokeInst>(V) ||
 510       isa<Argument>(V) || isa<Constant>(V) ||
 511       isa<AllocaInst>(V))
 512     return true;
 513
 514   if (const LoadInst *LI = dyn_cast<LoadInst>(V)) {
 515     const Value *Pointer =
 516       StripPointerCastsAndObjCCalls(LI->getPointerOperand());
 517     if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(Pointer)) {
 518       StringRef Name = GV->getName();
 519       // These special variables are known to hold values which are not
 520       // reference-counted pointers.
 521       if (Name.startswith("\01L_OBJC_SELECTOR_REFERENCES_") ||
 522           Name.startswith("\01L_OBJC_CLASSLIST_REFERENCES_") ||
 523           Name.startswith("\01L_OBJC_CLASSLIST_SUP_REFS_$_") ||
 524           Name.startswith("\01L_OBJC_METH_VAR_NAME_") ||
 525           Name.startswith("\01l_objc_msgSend_fixup_"))
 526         return true;
 527     }
 528   }
 529
 530   return false;
 531 }
 532
 533 /// FindSingleUseIdentifiedObject - This is similar to
 534 /// StripPointerCastsAndObjCCalls but it stops as soon as it finds a value
 535 /// with multiple uses.
 536 static const Value *FindSingleUseIdentifiedObject(const Value *Arg) {
 537   if (Arg->hasOneUse()) {
 538     if (const BitCastInst *BC = dyn_cast<BitCastInst>(Arg))
 539       return FindSingleUseIdentifiedObject(BC->getOperand(0));
 540     if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Arg))
 541       if (GEP->hasAllZeroIndices())
 542         return FindSingleUseIdentifiedObject(GEP->getPointerOperand());
 543     if (IsForwarding(GetBasicInstructionClass(Arg)))
 544       return FindSingleUseIdentifiedObject(
 545                cast<CallInst>(Arg)->getArgOperand(0));
 546     if (!IsObjCIdentifiedObject(Arg))
 547       return 0;
 548     return Arg;
 549   }
 550
 551   // If we found an identifiable object but it has multiple uses, but they
 552   // are trivial uses, we can still consider this to be a single-use
 553   // value.
 554   if (IsObjCIdentifiedObject(Arg)) {
 555     for (Value::const_use_iterator UI = Arg->use_begin(), UE = Arg->use_end();
 556          UI != UE; ++UI) {
 557       const User *U = *UI;
 558       if (!U->use_empty() || StripPointerCastsAndObjCCalls(U) != Arg)
 559          return 0;
 560     }
 561
 562     return Arg;
 563   }
 564
 565   return 0;
 566 }
 567
 568 /// ModuleHasARC - Test if the given module looks interesting to run ARC
 569 /// optimization on.
 570 static bool ModuleHasARC(const Module &M) {
 571   return
 572     M.getNamedValue("objc_retain") ||
 573     M.getNamedValue("objc_release") ||
 574     M.getNamedValue("objc_autorelease") ||
 575     M.getNamedValue("objc_retainAutoreleasedReturnValue") ||
 576     M.getNamedValue("objc_retainBlock") ||
 577     M.getNamedValue("objc_autoreleaseReturnValue") ||
 578     M.getNamedValue("objc_autoreleasePoolPush") ||
 579     M.getNamedValue("objc_loadWeakRetained") ||
 580     M.getNamedValue("objc_loadWeak") ||
 581     M.getNamedValue("objc_destroyWeak") ||
 582     M.getNamedValue("objc_storeWeak") ||
 583     M.getNamedValue("objc_initWeak") ||
 584     M.getNamedValue("objc_moveWeak") ||
 585     M.getNamedValue("objc_copyWeak") ||
 586     M.getNamedValue("objc_retainedObject") ||
 587     M.getNamedValue("objc_unretainedObject") ||
 588     M.getNamedValue("objc_unretainedPointer");
 589 }
 590
 591 //===----------------------------------------------------------------------===//
 592 // ARC AliasAnalysis.
 593 //===----------------------------------------------------------------------===//
 594
 595 #include "llvm/Pass.h"
 596 #include "llvm/Analysis/AliasAnalysis.h"
 597 #include "llvm/Analysis/Passes.h"
 598
 599 namespace {
 600   /// ObjCARCAliasAnalysis - This is a simple alias analysis
 601   /// implementation that uses knowledge of ARC constructs to answer queries.
 602   ///
 603   /// TODO: This class could be generalized to know about other ObjC-specific
 604   /// tricks. Such as knowing that ivars in the non-fragile ABI are non-aliasing
 605   /// even though their offsets are dynamic.
 606   class ObjCARCAliasAnalysis : public ImmutablePass,
 607                                public AliasAnalysis {
 608   public:
 609     static char ID; // Class identification, replacement for typeinfo
 610     ObjCARCAliasAnalysis() : ImmutablePass(ID) {
 611       initializeObjCARCAliasAnalysisPass(*PassRegistry::getPassRegistry());
 612     }
 613
 614   private:
 615     virtual void initializePass() {
 616       InitializeAliasAnalysis(this);
 617     }
 618
 619     /// getAdjustedAnalysisPointer - This method is used when a pass implements
 620     /// an analysis interface through multiple inheritance.  If needed, it
 621     /// should override this to adjust the this pointer as needed for the
 622     /// specified pass info.
 623     virtual void *getAdjustedAnalysisPointer(const void *PI) {
 624       if (PI == &AliasAnalysis::ID)
 625         return (AliasAnalysis*)this;
 626       return this;
 627     }
 628
 629     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
 630     virtual AliasResult alias(const Location &LocA, const Location &LocB);
 631     virtual bool pointsToConstantMemory(const Location &Loc, bool OrLocal);
 632     virtual ModRefBehavior getModRefBehavior(ImmutableCallSite CS);
 633     virtual ModRefBehavior getModRefBehavior(const Function *F);
 634     virtual ModRefResult getModRefInfo(ImmutableCallSite CS,
 635                                        const Location &Loc);
 636     virtual ModRefResult getModRefInfo(ImmutableCallSite CS1,
 637                                        ImmutableCallSite CS2);
 638   };
 639 }  // End of anonymous namespace
 640
 641 // Register this pass...
 642 char ObjCARCAliasAnalysis::ID = 0;
 643 INITIALIZE_AG_PASS(ObjCARCAliasAnalysis, AliasAnalysis, "objc-arc-aa",
 644                    "ObjC-ARC-Based Alias Analysis", false, true, false)
 645
 646 ImmutablePass *llvm::createObjCARCAliasAnalysisPass() {
 647   return new ObjCARCAliasAnalysis();
 648 }
 649
 650 void
 651 ObjCARCAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
 652   AU.setPreservesAll();
 653   AliasAnalysis::getAnalysisUsage(AU);
 654 }
 655
 656 AliasAnalysis::AliasResult
 657 ObjCARCAliasAnalysis::alias(const Location &LocA, const Location &LocB) {
 658   if (!EnableARCOpts)
 659     return AliasAnalysis::alias(LocA, LocB);
 660
 661   // First, strip off no-ops, including ObjC-specific no-ops, and try making a
 662   // precise alias query.
 663   const Value *SA = StripPointerCastsAndObjCCalls(LocA.Ptr);
 664   const Value *SB = StripPointerCastsAndObjCCalls(LocB.Ptr);
 665   AliasResult Result =
 666     AliasAnalysis::alias(Location(SA, LocA.Size, LocA.TBAATag),
 667                          Location(SB, LocB.Size, LocB.TBAATag));
 668   if (Result != MayAlias)
 669     return Result;
 670
 671   // If that failed, climb to the underlying object, including climbing through
 672   // ObjC-specific no-ops, and try making an imprecise alias query.
 673   const Value *UA = GetUnderlyingObjCPtr(SA);
 674   const Value *UB = GetUnderlyingObjCPtr(SB);
 675   if (UA != SA || UB != SB) {
 676     Result = AliasAnalysis::alias(Location(UA), Location(UB));
 677     // We can't use MustAlias or PartialAlias results here because
 678     // GetUnderlyingObjCPtr may return an offsetted pointer value.
 679     if (Result == NoAlias)
 680       return NoAlias;
 681   }
 682
 683   // If that failed, fail. We don't need to chain here, since that's covered
 684   // by the earlier precise query.
 685   return MayAlias;
 686 }
 687
 688 bool
 689 ObjCARCAliasAnalysis::pointsToConstantMemory(const Location &Loc,
 690                                              bool OrLocal) {
 691   if (!EnableARCOpts)
 692     return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal);
 693
 694   // First, strip off no-ops, including ObjC-specific no-ops, and try making
 695   // a precise alias query.
 696   const Value *S = StripPointerCastsAndObjCCalls(Loc.Ptr);
 697   if (AliasAnalysis::pointsToConstantMemory(Location(S, Loc.Size, Loc.TBAATag),
 698                                             OrLocal))
 699     return true;
 700
 701   // If that failed, climb to the underlying object, including climbing through
 702   // ObjC-specific no-ops, and try making an imprecise alias query.
 703   const Value *U = GetUnderlyingObjCPtr(S);
 704   if (U != S)
 705     return AliasAnalysis::pointsToConstantMemory(Location(U), OrLocal);
 706
 707   // If that failed, fail. We don't need to chain here, since that's covered
 708   // by the earlier precise query.
 709   return false;
 710 }
 711
 712 AliasAnalysis::ModRefBehavior
 713 ObjCARCAliasAnalysis::getModRefBehavior(ImmutableCallSite CS) {
 714   // We have nothing to do. Just chain to the next AliasAnalysis.
 715   return AliasAnalysis::getModRefBehavior(CS);
 716 }
 717
 718 AliasAnalysis::ModRefBehavior
 719 ObjCARCAliasAnalysis::getModRefBehavior(const Function *F) {
 720   if (!EnableARCOpts)
 721     return AliasAnalysis::getModRefBehavior(F);
 722
 723   switch (GetFunctionClass(F)) {
 724   case IC_NoopCast:
 725     return DoesNotAccessMemory;
 726   default:
 727     break;
 728   }
 729
 730   return AliasAnalysis::getModRefBehavior(F);
 731 }
 732
 733 AliasAnalysis::ModRefResult
 734 ObjCARCAliasAnalysis::getModRefInfo(ImmutableCallSite CS, const Location &Loc) {
 735   if (!EnableARCOpts)
 736     return AliasAnalysis::getModRefInfo(CS, Loc);
 737
 738   switch (GetBasicInstructionClass(CS.getInstruction())) {
 739   case IC_Retain:
 740   case IC_RetainRV:
 741   case IC_RetainBlock:
 742   case IC_Autorelease:
 743   case IC_AutoreleaseRV:
 744   case IC_NoopCast:
 745   case IC_AutoreleasepoolPush:
 746   case IC_FusedRetainAutorelease:
 747   case IC_FusedRetainAutoreleaseRV:
 748     // These functions don't access any memory visible to the compiler.
 749     return NoModRef;
 750   default:
 751     break;
 752   }
 753
 754   return AliasAnalysis::getModRefInfo(CS, Loc);
 755 }
 756
 757 AliasAnalysis::ModRefResult
 758 ObjCARCAliasAnalysis::getModRefInfo(ImmutableCallSite CS1,
 759                                     ImmutableCallSite CS2) {
 760   // TODO: Theoretically we could check for dependencies between objc_* calls
 761   // and OnlyAccessesArgumentPointees calls or other well-behaved calls.
 762   return AliasAnalysis::getModRefInfo(CS1, CS2);
 763 }
 764
 765 //===----------------------------------------------------------------------===//
 766 // ARC expansion.
 767 //===----------------------------------------------------------------------===//
 768
 769 #include "llvm/Support/InstIterator.h"
 770 #include "llvm/Transforms/Scalar.h"
 771
 772 namespace {
 773   /// ObjCARCExpand - Early ARC transformations.
 774   class ObjCARCExpand : public FunctionPass {
 775     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
 776     virtual bool doInitialization(Module &M);
 777     virtual bool runOnFunction(Function &F);
 778
 779     /// Run - A flag indicating whether this optimization pass should run.
 780     bool Run;
 781
 782   public:
 783     static char ID;
 784     ObjCARCExpand() : FunctionPass(ID) {
 785       initializeObjCARCExpandPass(*PassRegistry::getPassRegistry());
 786     }
 787   };
 788 }
 789
 790 char ObjCARCExpand::ID = 0;
 791 INITIALIZE_PASS(ObjCARCExpand,
 792                 "objc-arc-expand", "ObjC ARC expansion", false, false)
 793
 794 Pass *llvm::createObjCARCExpandPass() {
 795   return new ObjCARCExpand();
 796 }
 797
 798 void ObjCARCExpand::getAnalysisUsage(AnalysisUsage &AU) const {
 799   AU.setPreservesCFG();
 800 }
 801
 802 bool ObjCARCExpand::doInitialization(Module &M) {
 803   Run = ModuleHasARC(M);
 804   return false;
 805 }
 806
 807 bool ObjCARCExpand::runOnFunction(Function &F) {
 808   if (!EnableARCOpts)
 809     return false;
 810
 811   // If nothing in the Module uses ARC, don't do anything.
 812   if (!Run)
 813     return false;
 814
 815   bool Changed = false;
 816
 817   for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ++I) {
 818     Instruction *Inst = &*I;
 819
 820     switch (GetBasicInstructionClass(Inst)) {
 821     case IC_Retain:
 822     case IC_RetainRV:
 823     case IC_Autorelease:
 824     case IC_AutoreleaseRV:
 825     case IC_FusedRetainAutorelease:
 826     case IC_FusedRetainAutoreleaseRV:
 827       // These calls return their argument verbatim, as a low-level
 828       // optimization. However, this makes high-level optimizations
 829       // harder. Undo any uses of this optimization that the front-end
 830       // emitted here. We'll redo them in a later pass.
 831       Changed = true;
 832       Inst->replaceAllUsesWith(cast<CallInst>(Inst)->getArgOperand(0));
 833       break;
 834     default:
 835       break;
 836     }
 837   }
 838
 839   return Changed;
 840 }
 841
 842 //===----------------------------------------------------------------------===//
 843 // ARC optimization.
 844 //===----------------------------------------------------------------------===//
 845
 846 // TODO: On code like this:
 847 //
 848 // objc_retain(%x)
 849 // stuff_that_cannot_release()
 850 // objc_autorelease(%x)
 851 // stuff_that_cannot_release()
 852 // objc_retain(%x)
 853 // stuff_that_cannot_release()
 854 // objc_autorelease(%x)
 855 //
 856 // The second retain and autorelease can be deleted.
 857
 858 // TODO: It should be possible to delete
 859 // objc_autoreleasePoolPush and objc_autoreleasePoolPop
 860 // pairs if nothing is actually autoreleased between them. Also, autorelease
 861 // calls followed by objc_autoreleasePoolPop calls (perhaps in ObjC++ code
 862 // after inlining) can be turned into plain release calls.
 863
 864 // TODO: Critical-edge splitting. If the optimial insertion point is
 865 // a critical edge, the current algorithm has to fail, because it doesn't
 866 // know how to split edges. It should be possible to make the optimizer
 867 // think in terms of edges, rather than blocks, and then split critical
 868 // edges on demand.
 869
 870 // TODO: OptimizeSequences could generalized to be Interprocedural.
 871
 872 // TODO: Recognize that a bunch of other objc runtime calls have
 873 // non-escaping arguments and non-releasing arguments, and may be
 874 // non-autoreleasing.
 875
 876 // TODO: Sink autorelease calls as far as possible. Unfortunately we
 877 // usually can't sink them past other calls, which would be the main
 878 // case where it would be useful.
 879
 880 /// TODO: The pointer returned from objc_loadWeakRetained is retained.
 881
 882 #include "llvm/GlobalAlias.h"
 883 #include "llvm/Constants.h"
 884 #include "llvm/LLVMContext.h"
 885 #include "llvm/Support/ErrorHandling.h"
 886 #include "llvm/Support/CFG.h"
 887 #include "llvm/ADT/PostOrderIterator.h"
 888 #include "llvm/ADT/Statistic.h"
 889
 890 STATISTIC(NumNoops,       "Number of no-op objc calls eliminated");
 891 STATISTIC(NumPartialNoops, "Number of partially no-op objc calls eliminated");
 892 STATISTIC(NumAutoreleases,"Number of autoreleases converted to releases");
 893 STATISTIC(NumRets,        "Number of return value forwarding "
 894                           "retain+autoreleaes eliminated");
 895 STATISTIC(NumRRs,         "Number of retain+release paths eliminated");
 896 STATISTIC(NumPeeps,       "Number of calls peephole-optimized");
 897
 898 namespace {
 899   /// ProvenanceAnalysis - This is similar to BasicAliasAnalysis, and it
 900   /// uses many of the same techniques, except it uses special ObjC-specific
 901   /// reasoning about pointer relationships.
 902   class ProvenanceAnalysis {
 903     AliasAnalysis *AA;
 904
 905     typedef std::pair<const Value *, const Value *> ValuePairTy;
 906     typedef DenseMap<ValuePairTy, bool> CachedResultsTy;
 907     CachedResultsTy CachedResults;
 908
 909     bool relatedCheck(const Value *A, const Value *B);
 910     bool relatedSelect(const SelectInst *A, const Value *B);
 911     bool relatedPHI(const PHINode *A, const Value *B);
 912
 913     // Do not implement.
 914     void operator=(const ProvenanceAnalysis &);
 915     ProvenanceAnalysis(const ProvenanceAnalysis &);
 916
 917   public:
 918     ProvenanceAnalysis() {}
 919
 920     void setAA(AliasAnalysis *aa) { AA = aa; }
 921
 922     AliasAnalysis *getAA() const { return AA; }
 923
 924     bool related(const Value *A, const Value *B);
 925
 926     void clear() {
 927       CachedResults.clear();
 928     }
 929   };
 930 }
 931
 932 bool ProvenanceAnalysis::relatedSelect(const SelectInst *A, const Value *B) {
 933   // If the values are Selects with the same condition, we can do a more precise
 934   // check: just check for relations between the values on corresponding arms.
 935   if (const SelectInst *SB = dyn_cast<SelectInst>(B))
 936     if (A->getCondition() == SB->getCondition()) {
 937       if (related(A->getTrueValue(), SB->getTrueValue()))
 938         return true;
 939       if (related(A->getFalseValue(), SB->getFalseValue()))
 940         return true;
 941       return false;
 942     }
 943
 944   // Check both arms of the Select node individually.
 945   if (related(A->getTrueValue(), B))
 946     return true;
 947   if (related(A->getFalseValue(), B))
 948     return true;
 949
 950   // The arms both checked out.
 951   return false;
 952 }
 953
 954 bool ProvenanceAnalysis::relatedPHI(const PHINode *A, const Value *B) {
 955   // If the values are PHIs in the same block, we can do a more precise as well
 956   // as efficient check: just check for relations between the values on
 957   // corresponding edges.
 958   if (const PHINode *PNB = dyn_cast<PHINode>(B))
 959     if (PNB->getParent() == A->getParent()) {
 960       for (unsigned i = 0, e = A->getNumIncomingValues(); i != e; ++i)
 961         if (related(A->getIncomingValue(i),
 962                     PNB->getIncomingValueForBlock(A->getIncomingBlock(i))))
 963           return true;
 964       return false;
 965     }
 966
 967   // Check each unique source of the PHI node against B.
 968   SmallPtrSet<const Value *, 4> UniqueSrc;
 969   for (unsigned i = 0, e = A->getNumIncomingValues(); i != e; ++i) {
 970     const Value *PV1 = A->getIncomingValue(i);
 971     if (UniqueSrc.insert(PV1) && related(PV1, B))
 972       return true;
 973   }
 974
 975   // All of the arms checked out.
 976   return false;
 977 }
 978
 979 /// isStoredObjCPointer - Test if the value of P, or any value covered by its
 980 /// provenance, is ever stored within the function (not counting callees).
 981 static bool isStoredObjCPointer(const Value *P) {
 982   SmallPtrSet<const Value *, 8> Visited;
 983   SmallVector<const Value *, 8> Worklist;
 984   Worklist.push_back(P);
 985   Visited.insert(P);
 986   do {
 987     P = Worklist.pop_back_val();
 988     for (Value::const_use_iterator UI = P->use_begin(), UE = P->use_end();
 989          UI != UE; ++UI) {
 990       const User *Ur = *UI;
 991       if (isa<StoreInst>(Ur)) {
 992         if (UI.getOperandNo() == 0)
 993           // The pointer is stored.
 994           return true;
 995         // The pointed is stored through.
 996         continue;
 997       }
 998       if (isa<CallInst>(Ur))
 999         // The pointer is passed as an argument, ignore this.
1000         continue;
1001       if (isa<PtrToIntInst>(P))
1002         // Assume the worst.
1003         return true;
1004       if (Visited.insert(Ur))
1005         Worklist.push_back(Ur);
1006     }
1007   } while (!Worklist.empty());
1008
1009   // Everything checked out.
1010   return false;
1011 }
1012
1013 bool ProvenanceAnalysis::relatedCheck(const Value *A, const Value *B) {
1014   // Skip past provenance pass-throughs.
1015   A = GetUnderlyingObjCPtr(A);
1016   B = GetUnderlyingObjCPtr(B);
1017
1018   // Quick check.
1019   if (A == B)
1020     return true;
1021
1022   // Ask regular AliasAnalysis, for a first approximation.
1023   switch (AA->alias(A, B)) {
1024   case AliasAnalysis::NoAlias:
1025     return false;
1026   case AliasAnalysis::MustAlias:
1027   case AliasAnalysis::PartialAlias:
1028     return true;
1029   case AliasAnalysis::MayAlias:
1030     break;
1031   }
1032
1033   bool AIsIdentified = IsObjCIdentifiedObject(A);
1034   bool BIsIdentified = IsObjCIdentifiedObject(B);
1035
1036   // An ObjC-Identified object can't alias a load if it is never locally stored.
1037   if (AIsIdentified) {
1038     if (BIsIdentified) {
1039       // If both pointers have provenance, they can be directly compared.
1040       if (A != B)
1041         return false;
1042     } else {
1043       if (isa<LoadInst>(B))
1044         return isStoredObjCPointer(A);
1045     }
1046   } else {
1047     if (BIsIdentified && isa<LoadInst>(A))
1048       return isStoredObjCPointer(B);
1049   }
1050
1051    // Special handling for PHI and Select.
1052   if (const PHINode *PN = dyn_cast<PHINode>(A))
1053     return relatedPHI(PN, B);
1054   if (const PHINode *PN = dyn_cast<PHINode>(B))
1055     return relatedPHI(PN, A);
1056   if (const SelectInst *S = dyn_cast<SelectInst>(A))
1057     return relatedSelect(S, B);
1058   if (const SelectInst *S = dyn_cast<SelectInst>(B))
1059     return relatedSelect(S, A);
1060
1061   // Conservative.
1062   return true;
1063 }
1064
1065 bool ProvenanceAnalysis::related(const Value *A, const Value *B) {
1066   // Begin by inserting a conservative value into the map. If the insertion
1067   // fails, we have the answer already. If it succeeds, leave it there until we
1068   // compute the real answer to guard against recursive queries.
1069   if (A > B) std::swap(A, B);
1070   std::pair<CachedResultsTy::iterator, bool> Pair =
1071     CachedResults.insert(std::make_pair(ValuePairTy(A, B), true));
1072   if (!Pair.second)
1073     return Pair.first->second;
1074
1075   bool Result = relatedCheck(A, B);
1076   CachedResults[ValuePairTy(A, B)] = Result;
1077   return Result;
1078 }
1079
1080 namespace {
1081   // Sequence - A sequence of states that a pointer may go through in which an
1082   // objc_retain and objc_release are actually needed.
1083   enum Sequence {
1084     S_None,
1085     S_Retain,         ///< objc_retain(x)
1086     S_CanRelease,     ///< foo(x) -- x could possibly see a ref count decrement
1087     S_Use,            ///< any use of x
1088     S_Stop,           ///< like S_Release, but code motion is stopped
1089     S_Release,        ///< objc_release(x)
1090     S_MovableRelease  ///< objc_release(x), !clang.imprecise_release
1091   };
1092 }
1093
1094 static Sequence MergeSeqs(Sequence A, Sequence B, bool TopDown) {
1095   // The easy cases.
1096   if (A == B)
1097     return A;
1098   if (A == S_None || B == S_None)
1099     return S_None;
1100
1101   // Note that we can't merge S_CanRelease and S_Use.
1102   if (A > B) std::swap(A, B);
1103   if (TopDown) {
1104     // Choose the side which is further along in the sequence.
1105     if (A == S_Retain && (B == S_CanRelease || B == S_Use))
1106       return B;
1107   } else {
1108     // Choose the side which is further along in the sequence.
1109     if ((A == S_Use || A == S_CanRelease) &&
1110         (B == S_Release || B == S_Stop || B == S_MovableRelease))
1111       return A;
1112     // If both sides are releases, choose the more conservative one.
1113     if (A == S_Stop && (B == S_Release || B == S_MovableRelease))
1114       return A;
1115     if (A == S_Release && B == S_MovableRelease)
1116       return A;
1117   }
1118
1119   return S_None;
1120 }
1121
1122 namespace {
1123   /// RRInfo - Unidirectional information about either a
1124   /// retain-decrement-use-release sequence or release-use-decrement-retain
1125   /// reverese sequence.
1126   struct RRInfo {
1127     /// KnownIncremented - After an objc_retain, the reference count of the
1128     /// referenced object is known to be positive. Similarly, before an
1129     /// objc_release, the reference count of the referenced object is known to
1130     /// be positive. If there are retain-release pairs in code regions where the
1131     /// retain count is known to be positive, they can be eliminated, regardless
1132     /// of any side effects between them.
1133     bool KnownIncremented;
1134
1135     /// IsRetainBlock - True if the Calls are objc_retainBlock calls (as
1136     /// opposed to objc_retain calls).
1137     bool IsRetainBlock;
1138
1139     /// IsTailCallRelease - True of the objc_release calls are all marked
1140     /// with the "tail" keyword.
1141     bool IsTailCallRelease;
1142
1143     /// ReleaseMetadata - If the Calls are objc_release calls and they all have
1144     /// a clang.imprecise_release tag, this is the metadata tag.
1145     MDNode *ReleaseMetadata;
1146
1147     /// Calls - For a top-down sequence, the set of objc_retains or
1148     /// objc_retainBlocks. For bottom-up, the set of objc_releases.
1149     SmallPtrSet<Instruction *, 2> Calls;
1150
1151     /// ReverseInsertPts - The set of optimal insert positions for
1152     /// moving calls in the opposite sequence.
1153     SmallPtrSet<Instruction *, 2> ReverseInsertPts;
1154
1155     RRInfo() :
1156       KnownIncremented(false), IsRetainBlock(false), IsTailCallRelease(false),
1157       ReleaseMetadata(0) {}
1158
1159     void clear();
1160   };
1161 }
1162
1163 void RRInfo::clear() {
1164   KnownIncremented = false;
1165   IsRetainBlock = false;
1166   IsTailCallRelease = false;
1167   ReleaseMetadata = 0;
1168   Calls.clear();
1169   ReverseInsertPts.clear();
1170 }
1171
1172 namespace {
1173   /// PtrState - This class summarizes several per-pointer runtime properties
1174   /// which are propogated through the flow graph.
1175   class PtrState {
1176     /// RefCount - The known minimum number of reference count increments.
1177     unsigned RefCount;
1178
1179     /// Seq - The current position in the sequence.
1180     Sequence Seq;
1181
1182   public:
1183     /// RRI - Unidirectional information about the current sequence.
1184     /// TODO: Encapsulate this better.
1185     RRInfo RRI;
1186
1187     PtrState() : RefCount(0), Seq(S_None) {}
1188
1189     void IncrementRefCount() {
1190       if (RefCount != UINT_MAX) ++RefCount;
1191     }
1192
1193     void DecrementRefCount() {
1194       if (RefCount != 0) --RefCount;
1195     }
1196
1197     void ClearRefCount() {
1198       RefCount = 0;
1199     }
1200
1201     bool IsKnownIncremented() const {
1202       return RefCount > 0;
1203     }
1204
1205     void SetSeq(Sequence NewSeq) {
1206       Seq = NewSeq;
1207     }
1208
1209     void SetSeqToRelease(MDNode *M) {
1210       if (Seq == S_None || Seq == S_Use) {
1211         Seq = M ? S_MovableRelease : S_Release;
1212         RRI.ReleaseMetadata = M;
1213       } else if (Seq != S_MovableRelease || RRI.ReleaseMetadata != M) {
1214         Seq = S_Release;
1215         RRI.ReleaseMetadata = 0;
1216       }
1217     }
1218
1219     Sequence GetSeq() const {
1220       return Seq;
1221     }
1222
1223     void ClearSequenceProgress() {
1224       Seq = S_None;
1225       RRI.clear();
1226     }
1227
1228     void Merge(const PtrState &Other, bool TopDown);
1229   };
1230 }
1231
1232 void
1233 PtrState::Merge(const PtrState &Other, bool TopDown) {
1234   Seq = MergeSeqs(Seq, Other.Seq, TopDown);
1235   RefCount = std::min(RefCount, Other.RefCount);
1236
1237   // We can't merge a plain objc_retain with an objc_retainBlock.
1238   if (RRI.IsRetainBlock != Other.RRI.IsRetainBlock)
1239     Seq = S_None;
1240
1241   if (Seq == S_None) {
1242     RRI.clear();
1243   } else {
1244     // Conservatively merge the ReleaseMetadata information.
1245     if (RRI.ReleaseMetadata != Other.RRI.ReleaseMetadata)
1246       RRI.ReleaseMetadata = 0;
1247
1248     RRI.KnownIncremented = RRI.KnownIncremented && Other.RRI.KnownIncremented;
1249     RRI.IsTailCallRelease = RRI.IsTailCallRelease && Other.RRI.IsTailCallRelease;
1250     RRI.Calls.insert(Other.RRI.Calls.begin(), Other.RRI.Calls.end());
1251     RRI.ReverseInsertPts.insert(Other.RRI.ReverseInsertPts.begin(),
1252                                 Other.RRI.ReverseInsertPts.end());
1253   }
1254 }
1255
1256 namespace {
1257   /// BBState - Per-BasicBlock state.
1258   class BBState {
1259     /// TopDownPathCount - The number of unique control paths from the entry
1260     /// which can reach this block.
1261     unsigned TopDownPathCount;
1262
1263     /// BottomUpPathCount - The number of unique control paths to exits
1264     /// from this block.
1265     unsigned BottomUpPathCount;
1266
1267     /// MapTy - A type for PerPtrTopDown and PerPtrBottomUp.
1268     typedef MapVector<const Value *, PtrState> MapTy;
1269
1270     /// PerPtrTopDown - The top-down traversal uses this to record information
1271     /// known about a pointer at the bottom of each block.
1272     MapTy PerPtrTopDown;
1273
1274     /// PerPtrBottomUp - The bottom-up traversal uses this to record information
1275     /// known about a pointer at the top of each block.
1276     MapTy PerPtrBottomUp;
1277
1278   public:
1279     BBState() : TopDownPathCount(0), BottomUpPathCount(0) {}
1280
1281     typedef MapTy::iterator ptr_iterator;
1282     typedef MapTy::const_iterator ptr_const_iterator;
1283
1284     ptr_iterator top_down_ptr_begin() { return PerPtrTopDown.begin(); }
1285     ptr_iterator top_down_ptr_end() { return PerPtrTopDown.end(); }
1286     ptr_const_iterator top_down_ptr_begin() const {
1287       return PerPtrTopDown.begin();
1288     }
1289     ptr_const_iterator top_down_ptr_end() const {
1290       return PerPtrTopDown.end();
1291     }
1292
1293     ptr_iterator bottom_up_ptr_begin() { return PerPtrBottomUp.begin(); }
1294     ptr_iterator bottom_up_ptr_end() { return PerPtrBottomUp.end(); }
1295     ptr_const_iterator bottom_up_ptr_begin() const {
1296       return PerPtrBottomUp.begin();
1297     }
1298     ptr_const_iterator bottom_up_ptr_end() const {
1299       return PerPtrBottomUp.end();
1300     }
1301
1302     /// SetAsEntry - Mark this block as being an entry block, which has one
1303     /// path from the entry by definition.
1304     void SetAsEntry() { TopDownPathCount = 1; }
1305
1306     /// SetAsExit - Mark this block as being an exit block, which has one
1307     /// path to an exit by definition.
1308     void SetAsExit()  { BottomUpPathCount = 1; }
1309
1310     PtrState &getPtrTopDownState(const Value *Arg) {
1311       return PerPtrTopDown[Arg];
1312     }
1313
1314     PtrState &getPtrBottomUpState(const Value *Arg) {
1315       return PerPtrBottomUp[Arg];
1316     }
1317
1318     void clearBottomUpPointers() {
1319       PerPtrTopDown.clear();
1320     }
1321
1322     void clearTopDownPointers() {
1323       PerPtrTopDown.clear();
1324     }
1325
1326     void InitFromPred(const BBState &Other);
1327     void InitFromSucc(const BBState &Other);
1328     void MergePred(const BBState &Other);
1329     void MergeSucc(const BBState &Other);
1330
1331     /// GetAllPathCount - Return the number of possible unique paths from an
1332     /// entry to an exit which pass through this block. This is only valid
1333     /// after both the top-down and bottom-up traversals are complete.
1334     unsigned GetAllPathCount() const {
1335       return TopDownPathCount * BottomUpPathCount;
1336     }
1337   };
1338 }
1339
1340 void BBState::InitFromPred(const BBState &Other) {
1341   PerPtrTopDown = Other.PerPtrTopDown;
1342   TopDownPathCount = Other.TopDownPathCount;
1343 }
1344
1345 void BBState::InitFromSucc(const BBState &Other) {
1346   PerPtrBottomUp = Other.PerPtrBottomUp;
1347   BottomUpPathCount = Other.BottomUpPathCount;
1348 }
1349
1350 /// MergePred - The top-down traversal uses this to merge information about
1351 /// predecessors to form the initial state for a new block.
1352 void BBState::MergePred(const BBState &Other) {
1353   // Other.TopDownPathCount can be 0, in which case it is either dead or a
1354   // loop backedge. Loop backedges are special.
1355   TopDownPathCount += Other.TopDownPathCount;
1356
1357   // For each entry in the other set, if our set has an entry with the same key,
1358   // merge the entries. Otherwise, copy the entry and merge it with an empty
1359   // entry.
1360   for (ptr_const_iterator MI = Other.top_down_ptr_begin(),
1361        ME = Other.top_down_ptr_end(); MI != ME; ++MI) {
1362     std::pair<ptr_iterator, bool> Pair = PerPtrTopDown.insert(*MI);
1363     Pair.first->second.Merge(Pair.second ? PtrState() : MI->second,
1364                              /*TopDown=*/true);
1365   }
1366
1367   // For each entry in our set, if the other set doens't have an entry with the
1368   // same key, force it to merge with an empty entry.
1369   for (ptr_iterator MI = top_down_ptr_begin(),
1370        ME = top_down_ptr_end(); MI != ME; ++MI)
1371     if (Other.PerPtrTopDown.find(MI->first) == Other.PerPtrTopDown.end())
1372       MI->second.Merge(PtrState(), /*TopDown=*/true);
1373 }
1374
1375 /// MergeSucc - The bottom-up traversal uses this to merge information about
1376 /// successors to form the initial state for a new block.
1377 void BBState::MergeSucc(const BBState &Other) {
1378   // Other.BottomUpPathCount can be 0, in which case it is either dead or a
1379   // loop backedge. Loop backedges are special.
1380   BottomUpPathCount += Other.BottomUpPathCount;
1381
1382   // For each entry in the other set, if our set has an entry with the
1383   // same key, merge the entries. Otherwise, copy the entry and merge
1384   // it with an empty entry.
1385   for (ptr_const_iterator MI = Other.bottom_up_ptr_begin(),
1386        ME = Other.bottom_up_ptr_end(); MI != ME; ++MI) {
1387     std::pair<ptr_iterator, bool> Pair = PerPtrBottomUp.insert(*MI);
1388     Pair.first->second.Merge(Pair.second ? PtrState() : MI->second,
1389                              /*TopDown=*/false);
1390   }
1391
1392   // For each entry in our set, if the other set doens't have an entry
1393   // with the same key, force it to merge with an empty entry.
1394   for (ptr_iterator MI = bottom_up_ptr_begin(),
1395        ME = bottom_up_ptr_end(); MI != ME; ++MI)
1396     if (Other.PerPtrBottomUp.find(MI->first) == Other.PerPtrBottomUp.end())
1397       MI->second.Merge(PtrState(), /*TopDown=*/false);
1398 }
1399
1400 namespace {
1401   /// ObjCARCOpt - The main ARC optimization pass.
1402   class ObjCARCOpt : public FunctionPass {
1403     bool Changed;
1404     ProvenanceAnalysis PA;
1405
1406     /// Run - A flag indicating whether this optimization pass should run.
1407     bool Run;
1408
1409     /// RetainRVCallee, etc. - Declarations for ObjC runtime
1410     /// functions, for use in creating calls to them. These are initialized
1411     /// lazily to avoid cluttering up the Module with unused declarations.
1412     Constant *RetainRVCallee, *AutoreleaseRVCallee, *ReleaseCallee,
1413              *RetainCallee, *RetainBlockCallee, *AutoreleaseCallee;
1414
1415     /// UsedInThisFunciton - Flags which determine whether each of the
1416     /// interesting runtine functions is in fact used in the current function.
1417     unsigned UsedInThisFunction;
1418
1419     /// ImpreciseReleaseMDKind - The Metadata Kind for clang.imprecise_release
1420     /// metadata.
1421     unsigned ImpreciseReleaseMDKind;
1422
1423     Constant *getRetainRVCallee(Module *M);
1424     Constant *getAutoreleaseRVCallee(Module *M);
1425     Constant *getReleaseCallee(Module *M);
1426     Constant *getRetainCallee(Module *M);
1427     Constant *getRetainBlockCallee(Module *M);
1428     Constant *getAutoreleaseCallee(Module *M);
1429
1430     void OptimizeRetainCall(Function &F, Instruction *Retain);
1431     bool OptimizeRetainRVCall(Function &F, Instruction *RetainRV);
1432     void OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV);
1433     void OptimizeIndividualCalls(Function &F);
1434
1435     void CheckForCFGHazards(const BasicBlock *BB,
1436                             DenseMap<const BasicBlock *, BBState> &BBStates,
1437                             BBState &MyStates) const;
1438     bool VisitBottomUp(BasicBlock *BB,
1439                        DenseMap<const BasicBlock *, BBState> &BBStates,
1440                        MapVector<Value *, RRInfo> &Retains);
1441     bool VisitTopDown(BasicBlock *BB,
1442                       DenseMap<const BasicBlock *, BBState> &BBStates,
1443                       DenseMap<Value *, RRInfo> &Releases);
1444     bool Visit(Function &F,
1445                DenseMap<const BasicBlock *, BBState> &BBStates,
1446                MapVector<Value *, RRInfo> &Retains,
1447                DenseMap<Value *, RRInfo> &Releases);
1448
1449     void MoveCalls(Value *Arg, RRInfo &RetainsToMove, RRInfo &ReleasesToMove,
1450                    MapVector<Value *, RRInfo> &Retains,
1451                    DenseMap<Value *, RRInfo> &Releases,
1452                    SmallVectorImpl<Instruction *> &DeadInsts,
1453                    Module *M);
1454
1455     bool PerformCodePlacement(DenseMap<const BasicBlock *, BBState> &BBStates,
1456                               MapVector<Value *, RRInfo> &Retains,
1457                               DenseMap<Value *, RRInfo> &Releases,
1458                               Module *M);
1459
1460     void OptimizeWeakCalls(Function &F);
1461
1462     bool OptimizeSequences(Function &F);
1463
1464     void OptimizeReturns(Function &F);
1465
1466     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
1467     virtual bool doInitialization(Module &M);
1468     virtual bool runOnFunction(Function &F);
1469     virtual void releaseMemory();
1470
1471   public:
1472     static char ID;
1473     ObjCARCOpt() : FunctionPass(ID) {
1474       initializeObjCARCOptPass(*PassRegistry::getPassRegistry());
1475     }
1476   };
1477 }
1478
1479 char ObjCARCOpt::ID = 0;
1480 INITIALIZE_PASS_BEGIN(ObjCARCOpt,
1481                       "objc-arc", "ObjC ARC optimization", false, false)
1482 INITIALIZE_PASS_DEPENDENCY(ObjCARCAliasAnalysis)
1483 INITIALIZE_PASS_END(ObjCARCOpt,
1484                     "objc-arc", "ObjC ARC optimization", false, false)
1485
1486 Pass *llvm::createObjCARCOptPass() {
1487   return new ObjCARCOpt();
1488 }
1489
1490 void ObjCARCOpt::getAnalysisUsage(AnalysisUsage &AU) const {
1491   AU.addRequired<ObjCARCAliasAnalysis>();
1492   AU.addRequired<AliasAnalysis>();
1493   // ARC optimization doesn't currently split critical edges.
1494   AU.setPreservesCFG();
1495 }
1496
1497 Constant *ObjCARCOpt::getRetainRVCallee(Module *M) {
1498   if (!RetainRVCallee) {
1499     LLVMContext &C = M->getContext();
1500     Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
1501     std::vector<Type *> Params;
1502     Params.push_back(I8X);
1503     FunctionType *FTy =
1504       FunctionType::get(I8X, Params, /*isVarArg=*/false);
1505     AttrListPtr Attributes;
1506     Attributes.addAttr(~0u, Attribute::NoUnwind);
1507     RetainRVCallee =
1508       M->getOrInsertFunction("objc_retainAutoreleasedReturnValue", FTy,
1509                              Attributes);
1510   }
1511   return RetainRVCallee;
1512 }
1513
1514 Constant *ObjCARCOpt::getAutoreleaseRVCallee(Module *M) {
1515   if (!AutoreleaseRVCallee) {
1516     LLVMContext &C = M->getContext();
1517     Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
1518     std::vector<Type *> Params;
1519     Params.push_back(I8X);
1520     FunctionType *FTy =
1521       FunctionType::get(I8X, Params, /*isVarArg=*/false);
1522     AttrListPtr Attributes;
1523     Attributes.addAttr(~0u, Attribute::NoUnwind);
1524     AutoreleaseRVCallee =
1525       M->getOrInsertFunction("objc_autoreleaseReturnValue", FTy,
1526                              Attributes);
1527   }
1528   return AutoreleaseRVCallee;
1529 }
1530
1531 Constant *ObjCARCOpt::getReleaseCallee(Module *M) {
1532   if (!ReleaseCallee) {
1533     LLVMContext &C = M->getContext();
1534     std::vector<Type *> Params;
1535     Params.push_back(PointerType::getUnqual(Type::getInt8Ty(C)));
1536     AttrListPtr Attributes;
1537     Attributes.addAttr(~0u, Attribute::NoUnwind);
1538     ReleaseCallee =
1539       M->getOrInsertFunction(
1540         "objc_release",
1541         FunctionType::get(Type::getVoidTy(C), Params, /*isVarArg=*/false),
1542         Attributes);
1543   }
1544   return ReleaseCallee;
1545 }
1546
1547 Constant *ObjCARCOpt::getRetainCallee(Module *M) {
1548   if (!RetainCallee) {
1549     LLVMContext &C = M->getContext();
1550     std::vector<Type *> Params;
1551     Params.push_back(PointerType::getUnqual(Type::getInt8Ty(C)));
1552     AttrListPtr Attributes;
1553     Attributes.addAttr(~0u, Attribute::NoUnwind);
1554     RetainCallee =
1555       M->getOrInsertFunction(
1556         "objc_retain",
1557         FunctionType::get(Params[0], Params, /*isVarArg=*/false),
1558         Attributes);
1559   }
1560   return RetainCallee;
1561 }
1562
1563 Constant *ObjCARCOpt::getRetainBlockCallee(Module *M) {
1564   if (!RetainBlockCallee) {
1565     LLVMContext &C = M->getContext();
1566     std::vector<Type *> Params;
1567     Params.push_back(PointerType::getUnqual(Type::getInt8Ty(C)));
1568     AttrListPtr Attributes;
1569     Attributes.addAttr(~0u, Attribute::NoUnwind);
1570     RetainBlockCallee =
1571       M->getOrInsertFunction(
1572         "objc_retainBlock",
1573         FunctionType::get(Params[0], Params, /*isVarArg=*/false),
1574         Attributes);
1575   }
1576   return RetainBlockCallee;
1577 }
1578
1579 Constant *ObjCARCOpt::getAutoreleaseCallee(Module *M) {
1580   if (!AutoreleaseCallee) {
1581     LLVMContext &C = M->getContext();
1582     std::vector<Type *> Params;
1583     Params.push_back(PointerType::getUnqual(Type::getInt8Ty(C)));
1584     AttrListPtr Attributes;
1585     Attributes.addAttr(~0u, Attribute::NoUnwind);
1586     AutoreleaseCallee =
1587       M->getOrInsertFunction(
1588         "objc_autorelease",
1589         FunctionType::get(Params[0], Params, /*isVarArg=*/false),
1590         Attributes);
1591   }
1592   return AutoreleaseCallee;
1593 }
1594
1595 /// CanAlterRefCount - Test whether the given instruction can result in a
1596 /// reference count modification (positive or negative) for the pointer's
1597 /// object.
1598 static bool
1599 CanAlterRefCount(const Instruction *Inst, const Value *Ptr,
1600                  ProvenanceAnalysis &PA, InstructionClass Class) {
1601   switch (Class) {
1602   case IC_Autorelease:
1603   case IC_AutoreleaseRV:
1604   case IC_User:
1605     // These operations never directly modify a reference count.
1606     return false;
1607   default: break;
1608   }
1609
1610   ImmutableCallSite CS = static_cast<const Value *>(Inst);
1611   assert(CS && "Only calls can alter reference counts!");
1612
1613   // See if AliasAnalysis can help us with the call.
1614   AliasAnalysis::ModRefBehavior MRB = PA.getAA()->getModRefBehavior(CS);
1615   if (AliasAnalysis::onlyReadsMemory(MRB))
1616     return false;
1617   if (AliasAnalysis::onlyAccessesArgPointees(MRB)) {
1618     for (ImmutableCallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end();
1619          I != E; ++I) {
1620       const Value *Op = *I;
1621       if (IsPotentialUse(Op) && PA.related(Ptr, Op))
1622         return true;
1623     }
1624     return false;
1625   }
1626
1627   // Assume the worst.
1628   return true;
1629 }
1630
1631 /// CanUse - Test whether the given instruction can "use" the given pointer's
1632 /// object in a way that requires the reference count to be positive.
1633 static bool
1634 CanUse(const Instruction *Inst, const Value *Ptr, ProvenanceAnalysis &PA,
1635        InstructionClass Class) {
1636   // IC_Call operations (as opposed to IC_CallOrUser) never "use" objc pointers.
1637   if (Class == IC_Call)
1638     return false;
1639
1640   // Consider various instructions which may have pointer arguments which are
1641   // not "uses".
1642   if (const ICmpInst *ICI = dyn_cast<ICmpInst>(Inst)) {
1643     // Comparing a pointer with null, or any other constant, isn't really a use,
1644     // because we don't care what the pointer points to, or about the values
1645     // of any other dynamic reference-counted pointers.
1646     if (!IsPotentialUse(ICI->getOperand(1)))
1647       return false;
1648   } else if (ImmutableCallSite CS = static_cast<const Value *>(Inst)) {
1649     // For calls, just check the arguments (and not the callee operand).
1650     for (ImmutableCallSite::arg_iterator OI = CS.arg_begin(),
1651          OE = CS.arg_end(); OI != OE; ++OI) {
1652       const Value *Op = *OI;
1653       if (IsPotentialUse(Op) && PA.related(Ptr, Op))
1654         return true;
1655     }
1656     return false;
1657   } else if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
1658     // Special-case stores, because we don't care about the stored value, just
1659     // the store address.
1660     const Value *Op = GetUnderlyingObjCPtr(SI->getPointerOperand());
1661     // If we can't tell what the underlying object was, assume there is a
1662     // dependence.
1663     return IsPotentialUse(Op) && PA.related(Op, Ptr);
1664   }
1665
1666   // Check each operand for a match.
1667   for (User::const_op_iterator OI = Inst->op_begin(), OE = Inst->op_end();
1668        OI != OE; ++OI) {
1669     const Value *Op = *OI;
1670     if (IsPotentialUse(Op) && PA.related(Ptr, Op))
1671       return true;
1672   }
1673   return false;
1674 }
1675
1676 /// CanInterruptRV - Test whether the given instruction can autorelease
1677 /// any pointer or cause an autoreleasepool pop.
1678 static bool
1679 CanInterruptRV(InstructionClass Class) {
1680   switch (Class) {
1681   case IC_AutoreleasepoolPop:
1682   case IC_CallOrUser:
1683   case IC_Call:
1684   case IC_Autorelease:
1685   case IC_AutoreleaseRV:
1686   case IC_FusedRetainAutorelease:
1687   case IC_FusedRetainAutoreleaseRV:
1688     return true;
1689   default:
1690     return false;
1691   }
1692 }
1693
1694 namespace {
1695   /// DependenceKind - There are several kinds of dependence-like concepts in
1696   /// use here.
1697   enum DependenceKind {
1698     NeedsPositiveRetainCount,
1699     CanChangeRetainCount,
1700     RetainAutoreleaseDep,       ///< Blocks objc_retainAutorelease.
1701     RetainAutoreleaseRVDep,     ///< Blocks objc_retainAutoreleaseReturnValue.
1702     RetainRVDep                 ///< Blocks objc_retainAutoreleasedReturnValue.
1703   };
1704 }
1705
1706 /// Depends - Test if there can be dependencies on Inst through Arg. This
1707 /// function only tests dependencies relevant for removing pairs of calls.
1708 static bool
1709 Depends(DependenceKind Flavor, Instruction *Inst, const Value *Arg,
1710         ProvenanceAnalysis &PA) {
1711   // If we've reached the definition of Arg, stop.
1712   if (Inst == Arg)
1713     return true;
1714
1715   switch (Flavor) {
1716   case NeedsPositiveRetainCount: {
1717     InstructionClass Class = GetInstructionClass(Inst);
1718     switch (Class) {
1719     case IC_AutoreleasepoolPop:
1720     case IC_AutoreleasepoolPush:
1721     case IC_None:
1722       return false;
1723     default:
1724       return CanUse(Inst, Arg, PA, Class);
1725     }
1726   }
1727
1728   case CanChangeRetainCount: {
1729     InstructionClass Class = GetInstructionClass(Inst);
1730     switch (Class) {
1731     case IC_AutoreleasepoolPop:
1732       // Conservatively assume this can decrement any count.
1733       return true;
1734     case IC_AutoreleasepoolPush:
1735     case IC_None:
1736       return false;
1737     default:
1738       return CanAlterRefCount(Inst, Arg, PA, Class);
1739     }
1740   }
1741
1742   case RetainAutoreleaseDep:
1743     switch (GetBasicInstructionClass(Inst)) {
1744     case IC_AutoreleasepoolPop:
1745       // Don't merge an objc_autorelease with an objc_retain inside a different
1746       // autoreleasepool scope.
1747       return true;
1748     case IC_Retain:
1749     case IC_RetainRV:
1750       // Check for a retain of the same pointer for merging.
1751       return GetObjCArg(Inst) == Arg;
1752     default:
1753       // Nothing else matters for objc_retainAutorelease formation.
1754       return false;
1755     }
1756     break;
1757
1758   case RetainAutoreleaseRVDep: {
1759     InstructionClass Class = GetBasicInstructionClass(Inst);
1760     switch (Class) {
1761     case IC_Retain:
1762     case IC_RetainRV:
1763       // Check for a retain of the same pointer for merging.
1764       return GetObjCArg(Inst) == Arg;
1765     default:
1766       // Anything that can autorelease interrupts
1767       // retainAutoreleaseReturnValue formation.
1768       return CanInterruptRV(Class);
1769     }
1770     break;
1771   }
1772
1773   case RetainRVDep:
1774     return CanInterruptRV(GetBasicInstructionClass(Inst));
1775   }
1776
1777   llvm_unreachable("Invalid dependence flavor");
1778   return true;
1779 }
1780
1781 /// FindDependencies - Walk up the CFG from StartPos (which is in StartBB) and
1782 /// find local and non-local dependencies on Arg.
1783 /// TODO: Cache results?
1784 static void
1785 FindDependencies(DependenceKind Flavor,
1786                  const Value *Arg,
1787                  BasicBlock *StartBB, Instruction *StartInst,
1788                  SmallPtrSet<Instruction *, 4> &DependingInstructions,
1789                  SmallPtrSet<const BasicBlock *, 4> &Visited,
1790                  ProvenanceAnalysis &PA) {
1791   BasicBlock::iterator StartPos = StartInst;
1792
1793   SmallVector<std::pair<BasicBlock *, BasicBlock::iterator>, 4> Worklist;
1794   Worklist.push_back(std::make_pair(StartBB, StartPos));
1795   do {
1796     std::pair<BasicBlock *, BasicBlock::iterator> Pair =
1797       Worklist.pop_back_val();
1798     BasicBlock *LocalStartBB = Pair.first;
1799     BasicBlock::iterator LocalStartPos = Pair.second;
1800     BasicBlock::iterator StartBBBegin = LocalStartBB->begin();
1801     for (;;) {
1802       if (LocalStartPos == StartBBBegin) {
1803         pred_iterator PI(LocalStartBB), PE(LocalStartBB, false);
1804         if (PI == PE)
1805           // If we've reached the function entry, produce a null dependence.
1806           DependingInstructions.insert(0);
1807         else
1808           // Add the predecessors to the worklist.
1809           do {
1810             BasicBlock *PredBB = *PI;
1811             if (Visited.insert(PredBB))
1812               Worklist.push_back(std::make_pair(PredBB, PredBB->end()));
1813           } while (++PI != PE);
1814         break;
1815       }
1816
1817       Instruction *Inst = --LocalStartPos;
1818       if (Depends(Flavor, Inst, Arg, PA)) {
1819         DependingInstructions.insert(Inst);
1820         break;
1821       }
1822     }
1823   } while (!Worklist.empty());
1824
1825   // Determine whether the original StartBB post-dominates all of the blocks we
1826   // visited. If not, insert a sentinal indicating that most optimizations are
1827   // not safe.
1828   for (SmallPtrSet<const BasicBlock *, 4>::const_iterator I = Visited.begin(),
1829        E = Visited.end(); I != E; ++I) {
1830     const BasicBlock *BB = *I;
1831     if (BB == StartBB)
1832       continue;
1833     const TerminatorInst *TI = cast<TerminatorInst>(&BB->back());
1834     for (succ_const_iterator SI(TI), SE(TI, false); SI != SE; ++SI) {
1835       const BasicBlock *Succ = *SI;
1836       if (Succ != StartBB && !Visited.count(Succ)) {
1837         DependingInstructions.insert(reinterpret_cast<Instruction *>(-1));
1838         return;
1839       }
1840     }
1841   }
1842 }
1843
1844 static bool isNullOrUndef(const Value *V) {
1845   return isa<ConstantPointerNull>(V) || isa<UndefValue>(V);
1846 }
1847
1848 static bool isNoopInstruction(const Instruction *I) {
1849   return isa<BitCastInst>(I) ||
1850          (isa<GetElementPtrInst>(I) &&
1851           cast<GetElementPtrInst>(I)->hasAllZeroIndices());
1852 }
1853
1854 /// OptimizeRetainCall - Turn objc_retain into
1855 /// objc_retainAutoreleasedReturnValue if the operand is a return value.
1856 void
1857 ObjCARCOpt::OptimizeRetainCall(Function &F, Instruction *Retain) {
1858   CallSite CS(GetObjCArg(Retain));
1859   Instruction *Call = CS.getInstruction();
1860   if (!Call) return;
1861   if (Call->getParent() != Retain->getParent()) return;
1862
1863   // Check that the call is next to the retain.
1864   BasicBlock::iterator I = Call;
1865   ++I;
1866   while (isNoopInstruction(I)) ++I;
1867   if (&*I != Retain)
1868     return;
1869
1870   // Turn it to an objc_retainAutoreleasedReturnValue..
1871   Changed = true;
1872   ++NumPeeps;
1873   cast<CallInst>(Retain)->setCalledFunction(getRetainRVCallee(F.getParent()));
1874 }
1875
1876 /// OptimizeRetainRVCall - Turn objc_retainAutoreleasedReturnValue into
1877 /// objc_retain if the operand is not a return value.  Or, if it can be
1878 /// paired with an objc_autoreleaseReturnValue, delete the pair and
1879 /// return true.
1880 bool
1881 ObjCARCOpt::OptimizeRetainRVCall(Function &F, Instruction *RetainRV) {
1882   // Check for the argument being from an immediately preceding call.
1883   Value *Arg = GetObjCArg(RetainRV);
1884   CallSite CS(Arg);
1885   if (Instruction *Call = CS.getInstruction())
1886     if (Call->getParent() == RetainRV->getParent()) {
1887       BasicBlock::iterator I = Call;
1888       ++I;
1889       while (isNoopInstruction(I)) ++I;
1890       if (&*I == RetainRV)
1891         return false;
1892     }
1893
1894   // Check for being preceded by an objc_autoreleaseReturnValue on the same
1895   // pointer. In this case, we can delete the pair.
1896   BasicBlock::iterator I = RetainRV, Begin = RetainRV->getParent()->begin();
1897   if (I != Begin) {
1898     do --I; while (I != Begin && isNoopInstruction(I));
1899     if (GetBasicInstructionClass(I) == IC_AutoreleaseRV &&
1900         GetObjCArg(I) == Arg) {
1901       Changed = true;
1902       ++NumPeeps;
1903       EraseInstruction(I);
1904       EraseInstruction(RetainRV);
1905       return true;
1906     }
1907   }
1908
1909   // Turn it to a plain objc_retain.
1910   Changed = true;
1911   ++NumPeeps;
1912   cast<CallInst>(RetainRV)->setCalledFunction(getRetainCallee(F.getParent()));
1913   return false;
1914 }
1915
1916 /// OptimizeAutoreleaseRVCall - Turn objc_autoreleaseReturnValue into
1917 /// objc_autorelease if the result is not used as a return value.
1918 void
1919 ObjCARCOpt::OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV) {
1920   // Check for a return of the pointer value.
1921   const Value *Ptr = GetObjCArg(AutoreleaseRV);
1922   for (Value::const_use_iterator UI = Ptr->use_begin(), UE = Ptr->use_end();
1923        UI != UE; ++UI) {
1924     const User *I = *UI;
1925     if (isa<ReturnInst>(I) || GetBasicInstructionClass(I) == IC_RetainRV)
1926       return;
1927   }
1928
1929   Changed = true;
1930   ++NumPeeps;
1931   cast<CallInst>(AutoreleaseRV)->
1932     setCalledFunction(getAutoreleaseCallee(F.getParent()));
1933 }
1934
1935 /// OptimizeIndividualCalls - Visit each call, one at a time, and make
1936 /// simplifications without doing any additional analysis.
1937 void ObjCARCOpt::OptimizeIndividualCalls(Function &F) {
1938   // Reset all the flags in preparation for recomputing them.
1939   UsedInThisFunction = 0;
1940
1941   // Visit all objc_* calls in F.
1942   for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
1943     Instruction *Inst = &*I++;
1944     InstructionClass Class = GetBasicInstructionClass(Inst);
1945
1946     switch (Class) {
1947     default: break;
1948
1949     // Delete no-op casts. These function calls have special semantics, but
1950     // the semantics are entirely implemented via lowering in the front-end,
1951     // so by the time they reach the optimizer, they are just no-op calls
1952     // which return their argument.
1953     //
1954     // There are gray areas here, as the ability to cast reference-counted
1955     // pointers to raw void* and back allows code to break ARC assumptions,
1956     // however these are currently considered to be unimportant.
1957     case IC_NoopCast:
1958       Changed = true;
1959       ++NumNoops;
1960       EraseInstruction(Inst);
1961       continue;
1962
1963     // If the pointer-to-weak-pointer is null, it's undefined behavior.
1964     case IC_StoreWeak:
1965     case IC_LoadWeak:
1966     case IC_LoadWeakRetained:
1967     case IC_InitWeak:
1968     case IC_DestroyWeak: {
1969       CallInst *CI = cast<CallInst>(Inst);
1970       if (isNullOrUndef(CI->getArgOperand(0))) {
1971         Type *Ty = CI->getArgOperand(0)->getType();
1972         new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()),
1973                       Constant::getNullValue(Ty),
1974                       CI);
1975         CI->replaceAllUsesWith(UndefValue::get(CI->getType()));
1976         CI->eraseFromParent();
1977         continue;
1978       }
1979       break;
1980     }
1981     case IC_CopyWeak:
1982     case IC_MoveWeak: {
1983       CallInst *CI = cast<CallInst>(Inst);
1984       if (isNullOrUndef(CI->getArgOperand(0)) ||
1985           isNullOrUndef(CI->getArgOperand(1))) {
1986         Type *Ty = CI->getArgOperand(0)->getType();
1987         new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()),
1988                       Constant::getNullValue(Ty),
1989                       CI);
1990         CI->replaceAllUsesWith(UndefValue::get(CI->getType()));
1991         CI->eraseFromParent();
1992         continue;
1993       }
1994       break;
1995     }
1996     case IC_Retain:
1997       OptimizeRetainCall(F, Inst);
1998       break;
1999     case IC_RetainRV:
2000       if (OptimizeRetainRVCall(F, Inst))
2001         continue;
2002       break;
2003     case IC_AutoreleaseRV:
2004       OptimizeAutoreleaseRVCall(F, Inst);
2005       break;
2006     }
2007
2008     // objc_autorelease(x) -> objc_release(x) if x is otherwise unused.
2009     if (IsAutorelease(Class) && Inst->use_empty()) {
2010       CallInst *Call = cast<CallInst>(Inst);
2011       const Value *Arg = Call->getArgOperand(0);
2012       Arg = FindSingleUseIdentifiedObject(Arg);
2013       if (Arg) {
2014         Changed = true;
2015         ++NumAutoreleases;
2016
2017         // Create the declaration lazily.
2018         LLVMContext &C = Inst->getContext();
2019         CallInst *NewCall =
2020           CallInst::Create(getReleaseCallee(F.getParent()),
2021                            Call->getArgOperand(0), "", Call);
2022         NewCall->setMetadata(ImpreciseReleaseMDKind,
2023                              MDNode::get(C, ArrayRef<Value *>()));
2024         EraseInstruction(Call);
2025         Inst = NewCall;
2026         Class = IC_Release;
2027       }
2028     }
2029
2030     // For functions which can never be passed stack arguments, add
2031     // a tail keyword.
2032     if (IsAlwaysTail(Class)) {
2033       Changed = true;
2034       cast<CallInst>(Inst)->setTailCall();
2035     }
2036
2037     // Set nounwind as needed.
2038     if (IsNoThrow(Class)) {
2039       Changed = true;
2040       cast<CallInst>(Inst)->setDoesNotThrow();
2041     }
2042
2043     if (!IsNoopOnNull(Class)) {
2044       UsedInThisFunction |= 1 << Class;
2045       continue;
2046     }
2047
2048     const Value *Arg = GetObjCArg(Inst);
2049
2050     // ARC calls with null are no-ops. Delete them.
2051     if (isNullOrUndef(Arg)) {
2052       Changed = true;
2053       ++NumNoops;
2054       EraseInstruction(Inst);
2055       continue;
2056     }
2057
2058     // Keep track of which of retain, release, autorelease, and retain_block
2059     // are actually present in this function.
2060     UsedInThisFunction |= 1 << Class;
2061
2062     // If Arg is a PHI, and one or more incoming values to the
2063     // PHI are null, and the call is control-equivalent to the PHI, and there
2064     // are no relevant side effects between the PHI and the call, the call
2065     // could be pushed up to just those paths with non-null incoming values.
2066     // For now, don't bother splitting critical edges for this.
2067     SmallVector<std::pair<Instruction *, const Value *>, 4> Worklist;
2068     Worklist.push_back(std::make_pair(Inst, Arg));
2069     do {
2070       std::pair<Instruction *, const Value *> Pair = Worklist.pop_back_val();
2071       Inst = Pair.first;
2072       Arg = Pair.second;
2073
2074       const PHINode *PN = dyn_cast<PHINode>(Arg);
2075       if (!PN) continue;
2076
2077       // Determine if the PHI has any null operands, or any incoming
2078       // critical edges.
2079       bool HasNull = false;
2080       bool HasCriticalEdges = false;
2081       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
2082         Value *Incoming =
2083           StripPointerCastsAndObjCCalls(PN->getIncomingValue(i));
2084         if (isNullOrUndef(Incoming))
2085           HasNull = true;
2086         else if (cast<TerminatorInst>(PN->getIncomingBlock(i)->back())
2087                    .getNumSuccessors() != 1) {
2088           HasCriticalEdges = true;
2089           break;
2090         }
2091       }
2092       // If we have null operands and no critical edges, optimize.
2093       if (!HasCriticalEdges && HasNull) {
2094         SmallPtrSet<Instruction *, 4> DependingInstructions;
2095         SmallPtrSet<const BasicBlock *, 4> Visited;
2096
2097         // Check that there is nothing that cares about the reference
2098         // count between the call and the phi.
2099         FindDependencies(NeedsPositiveRetainCount, Arg,
2100                          Inst->getParent(), Inst,
2101                          DependingInstructions, Visited, PA);
2102         if (DependingInstructions.size() == 1 &&
2103             *DependingInstructions.begin() == PN) {
2104           Changed = true;
2105           ++NumPartialNoops;
2106           // Clone the call into each predecessor that has a non-null value.
2107           CallInst *CInst = cast<CallInst>(Inst);
2108           Type *ParamTy = CInst->getArgOperand(0)->getType();
2109           for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
2110             Value *Incoming =
2111               StripPointerCastsAndObjCCalls(PN->getIncomingValue(i));
2112             if (!isNullOrUndef(Incoming)) {
2113               CallInst *Clone = cast<CallInst>(CInst->clone());
2114               Value *Op = PN->getIncomingValue(i);
2115               Instruction *InsertPos = &PN->getIncomingBlock(i)->back();
2116               if (Op->getType() != ParamTy)
2117                 Op = new BitCastInst(Op, ParamTy, "", InsertPos);
2118               Clone->setArgOperand(0, Op);
2119               Clone->insertBefore(InsertPos);
2120               Worklist.push_back(std::make_pair(Clone, Incoming));
2121             }
2122           }
2123           // Erase the original call.
2124           EraseInstruction(CInst);
2125           continue;
2126         }
2127       }
2128     } while (!Worklist.empty());
2129   }
2130 }
2131
2132 /// CheckForCFGHazards - Check for critical edges, loop boundaries, irreducible
2133 /// control flow, or other CFG structures where moving code across the edge
2134 /// would result in it being executed more.
2135 void
2136 ObjCARCOpt::CheckForCFGHazards(const BasicBlock *BB,
2137                                DenseMap<const BasicBlock *, BBState> &BBStates,
2138                                BBState &MyStates) const {
2139   // If any top-down local-use or possible-dec has a succ which is earlier in
2140   // the sequence, forget it.
2141   for (BBState::ptr_const_iterator I = MyStates.top_down_ptr_begin(),
2142        E = MyStates.top_down_ptr_end(); I != E; ++I)
2143     switch (I->second.GetSeq()) {
2144     default: break;
2145     case S_Use: {
2146       const Value *Arg = I->first;
2147       const TerminatorInst *TI = cast<TerminatorInst>(&BB->back());
2148       bool SomeSuccHasSame = false;
2149       bool AllSuccsHaveSame = true;
2150       for (succ_const_iterator SI(TI), SE(TI, false); SI != SE; ++SI)
2151         switch (BBStates[*SI].getPtrBottomUpState(Arg).GetSeq()) {
2152         case S_None:
2153         case S_CanRelease:
2154           MyStates.getPtrTopDownState(Arg).ClearSequenceProgress();
2155           SomeSuccHasSame = false;
2156           break;
2157         case S_Use:
2158           SomeSuccHasSame = true;
2159           break;
2160         case S_Stop:
2161         case S_Release:
2162         case S_MovableRelease:
2163           AllSuccsHaveSame = false;
2164           break;
2165         case S_Retain:
2166           llvm_unreachable("bottom-up pointer in retain state!");
2167         }
2168       // If the state at the other end of any of the successor edges
2169       // matches the current state, require all edges to match. This
2170       // guards against loops in the middle of a sequence.
2171       if (SomeSuccHasSame && !AllSuccsHaveSame)
2172         MyStates.getPtrTopDownState(Arg).ClearSequenceProgress();
2173     }
2174     case S_CanRelease: {
2175       const Value *Arg = I->first;
2176       const TerminatorInst *TI = cast<TerminatorInst>(&BB->back());
2177       bool SomeSuccHasSame = false;
2178       bool AllSuccsHaveSame = true;
2179       for (succ_const_iterator SI(TI), SE(TI, false); SI != SE; ++SI)
2180         switch (BBStates[*SI].getPtrBottomUpState(Arg).GetSeq()) {
2181         case S_None:
2182           MyStates.getPtrTopDownState(Arg).ClearSequenceProgress();
2183           SomeSuccHasSame = false;
2184           break;
2185         case S_CanRelease:
2186           SomeSuccHasSame = true;
2187           break;
2188         case S_Stop:
2189         case S_Release:
2190         case S_MovableRelease:
2191         case S_Use:
2192           AllSuccsHaveSame = false;
2193           break;
2194         case S_Retain:
2195           llvm_unreachable("bottom-up pointer in retain state!");
2196         }
2197       // If the state at the other end of any of the successor edges
2198       // matches the current state, require all edges to match. This
2199       // guards against loops in the middle of a sequence.
2200       if (SomeSuccHasSame && !AllSuccsHaveSame)
2201         MyStates.getPtrTopDownState(Arg).ClearSequenceProgress();
2202     }
2203     }
2204 }
2205
2206 bool
2207 ObjCARCOpt::VisitBottomUp(BasicBlock *BB,
2208                           DenseMap<const BasicBlock *, BBState> &BBStates,
2209                           MapVector<Value *, RRInfo> &Retains) {
2210   bool NestingDetected = false;
2211   BBState &MyStates = BBStates[BB];
2212
2213   // Merge the states from each successor to compute the initial state
2214   // for the current block.
2215   const TerminatorInst *TI = cast<TerminatorInst>(&BB->back());
2216   succ_const_iterator SI(TI), SE(TI, false);
2217   if (SI == SE)
2218     MyStates.SetAsExit();
2219   else
2220     do {
2221       const BasicBlock *Succ = *SI++;
2222       if (Succ == BB)
2223         continue;
2224       DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Succ);
2225       if (I == BBStates.end())
2226         continue;
2227       MyStates.InitFromSucc(I->second);
2228       while (SI != SE) {
2229         Succ = *SI++;
2230         if (Succ != BB) {
2231           I = BBStates.find(Succ);
2232           if (I != BBStates.end())
2233             MyStates.MergeSucc(I->second);
2234         }
2235       }
2236       break;
2237     } while (SI != SE);
2238
2239   // Visit all the instructions, bottom-up.
2240   for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; --I) {
2241     Instruction *Inst = llvm::prior(I);
2242     InstructionClass Class = GetInstructionClass(Inst);
2243     const Value *Arg = 0;
2244
2245     switch (Class) {
2246     case IC_Release: {
2247       Arg = GetObjCArg(Inst);
2248
2249       PtrState &S = MyStates.getPtrBottomUpState(Arg);
2250
2251       // If we see two releases in a row on the same pointer. If so, make
2252       // a note, and we'll cicle back to revisit it after we've
2253       // hopefully eliminated the second release, which may allow us to
2254       // eliminate the first release too.
2255       // Theoretically we could implement removal of nested retain+release
2256       // pairs by making PtrState hold a stack of states, but this is
2257       // simple and avoids adding overhead for the non-nested case.
2258       if (S.GetSeq() == S_Release || S.GetSeq() == S_MovableRelease)
2259         NestingDetected = true;
2260
2261       S.SetSeqToRelease(Inst->getMetadata(ImpreciseReleaseMDKind));
2262       S.RRI.clear();
2263       S.RRI.KnownIncremented = S.IsKnownIncremented();
2264       S.RRI.IsTailCallRelease = cast<CallInst>(Inst)->isTailCall();
2265       S.RRI.Calls.insert(Inst);
2266
2267       S.IncrementRefCount();
2268       break;
2269     }
2270     case IC_RetainBlock:
2271     case IC_Retain:
2272     case IC_RetainRV: {
2273       Arg = GetObjCArg(Inst);
2274
2275       PtrState &S = MyStates.getPtrBottomUpState(Arg);
2276       S.DecrementRefCount();
2277
2278       switch (S.GetSeq()) {
2279       case S_Stop:
2280       case S_Release:
2281       case S_MovableRelease:
2282       case S_Use:
2283         S.RRI.ReverseInsertPts.clear();
2284         // FALL THROUGH
2285       case S_CanRelease:
2286         // Don't do retain+release tracking for IC_RetainRV, because it's
2287         // better to let it remain as the first instruction after a call.
2288         if (Class != IC_RetainRV) {
2289           S.RRI.IsRetainBlock = Class == IC_RetainBlock;
2290           Retains[Inst] = S.RRI;
2291         }
2292         S.ClearSequenceProgress();
2293         break;
2294       case S_None:
2295         break;
2296       case S_Retain:
2297         llvm_unreachable("bottom-up pointer in retain state!");
2298       }
2299       break;
2300     }
2301     case IC_AutoreleasepoolPop:
2302       // Conservatively, clear MyStates for all known pointers.
2303       MyStates.clearBottomUpPointers();
2304       continue;
2305     case IC_AutoreleasepoolPush:
2306     case IC_None:
2307       // These are irrelevant.
2308       continue;
2309     default:
2310       break;
2311     }
2312
2313     // Consider any other possible effects of this instruction on each
2314     // pointer being tracked.
2315     for (BBState::ptr_iterator MI = MyStates.bottom_up_ptr_begin(),
2316          ME = MyStates.bottom_up_ptr_end(); MI != ME; ++MI) {
2317       const Value *Ptr = MI->first;
2318       if (Ptr == Arg)
2319         continue; // Handled above.
2320       PtrState &S = MI->second;
2321       Sequence Seq = S.GetSeq();
2322
2323       // Check for possible retains and releases.
2324       if (CanAlterRefCount(Inst, Ptr, PA, Class)) {
2325         // Check for a retain (we're going bottom-up here).
2326         S.DecrementRefCount();
2327
2328         // Check for a release.
2329         if (!IsRetain(Class) && Class != IC_RetainBlock)
2330           switch (Seq) {
2331           case S_Use:
2332             S.SetSeq(S_CanRelease);
2333             continue;
2334           case S_CanRelease:
2335           case S_Release:
2336           case S_MovableRelease:
2337           case S_Stop:
2338           case S_None:
2339             break;
2340           case S_Retain:
2341             llvm_unreachable("bottom-up pointer in retain state!");
2342           }
2343       }
2344
2345       // Check for possible direct uses.
2346       switch (Seq) {
2347       case S_Release:
2348       case S_MovableRelease:
2349         if (CanUse(Inst, Ptr, PA, Class)) {
2350           S.RRI.ReverseInsertPts.clear();
2351           S.RRI.ReverseInsertPts.insert(Inst);
2352           S.SetSeq(S_Use);
2353         } else if (Seq == S_Release &&
2354                    (Class == IC_User || Class == IC_CallOrUser)) {
2355           // Non-movable releases depend on any possible objc pointer use.
2356           S.SetSeq(S_Stop);
2357           S.RRI.ReverseInsertPts.clear();
2358           S.RRI.ReverseInsertPts.insert(Inst);
2359         }
2360         break;
2361       case S_Stop:
2362         if (CanUse(Inst, Ptr, PA, Class))
2363           S.SetSeq(S_Use);
2364         break;
2365       case S_CanRelease:
2366       case S_Use:
2367       case S_None:
2368         break;
2369       case S_Retain:
2370         llvm_unreachable("bottom-up pointer in retain state!");
2371       }
2372     }
2373   }
2374
2375   return NestingDetected;
2376 }
2377
2378 bool
2379 ObjCARCOpt::VisitTopDown(BasicBlock *BB,
2380                          DenseMap<const BasicBlock *, BBState> &BBStates,
2381                          DenseMap<Value *, RRInfo> &Releases) {
2382   bool NestingDetected = false;
2383   BBState &MyStates = BBStates[BB];
2384
2385   // Merge the states from each predecessor to compute the initial state
2386   // for the current block.
2387   const_pred_iterator PI(BB), PE(BB, false);
2388   if (PI == PE)
2389     MyStates.SetAsEntry();
2390   else
2391     do {
2392       const BasicBlock *Pred = *PI++;
2393       if (Pred == BB)
2394         continue;
2395       DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Pred);
2396       if (I == BBStates.end())
2397         continue;
2398       MyStates.InitFromPred(I->second);
2399       while (PI != PE) {
2400         Pred = *PI++;
2401         if (Pred != BB) {
2402           I = BBStates.find(Pred);
2403           if (I != BBStates.end())
2404             MyStates.MergePred(I->second);
2405         }
2406       }
2407       break;
2408     } while (PI != PE);
2409
2410   // Visit all the instructions, top-down.
2411   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
2412     Instruction *Inst = I;
2413     InstructionClass Class = GetInstructionClass(Inst);
2414     const Value *Arg = 0;
2415
2416     switch (Class) {
2417     case IC_RetainBlock:
2418     case IC_Retain:
2419     case IC_RetainRV: {
2420       Arg = GetObjCArg(Inst);
2421
2422       PtrState &S = MyStates.getPtrTopDownState(Arg);
2423
2424       // Don't do retain+release tracking for IC_RetainRV, because it's
2425       // better to let it remain as the first instruction after a call.
2426       if (Class != IC_RetainRV) {
2427         // If we see two retains in a row on the same pointer. If so, make
2428         // a note, and we'll cicle back to revisit it after we've
2429         // hopefully eliminated the second retain, which may allow us to
2430         // eliminate the first retain too.
2431         // Theoretically we could implement removal of nested retain+release
2432         // pairs by making PtrState hold a stack of states, but this is
2433         // simple and avoids adding overhead for the non-nested case.
2434         if (S.GetSeq() == S_Retain)
2435           NestingDetected = true;
2436
2437         S.SetSeq(S_Retain);
2438         S.RRI.clear();
2439         S.RRI.IsRetainBlock = Class == IC_RetainBlock;
2440         S.RRI.KnownIncremented = S.IsKnownIncremented();
2441         S.RRI.Calls.insert(Inst);
2442       }
2443
2444       S.IncrementRefCount();
2445       break;
2446     }
2447     case IC_Release: {
2448       Arg = GetObjCArg(Inst);
2449
2450       PtrState &S = MyStates.getPtrTopDownState(Arg);
2451       S.DecrementRefCount();
2452
2453       switch (S.GetSeq()) {
2454       case S_Retain:
2455       case S_CanRelease:
2456         S.RRI.ReverseInsertPts.clear();
2457         // FALL THROUGH
2458       case S_Use:
2459         S.RRI.ReleaseMetadata = Inst->getMetadata(ImpreciseReleaseMDKind);
2460         S.RRI.IsTailCallRelease = cast<CallInst>(Inst)->isTailCall();
2461         Releases[Inst] = S.RRI;
2462         S.ClearSequenceProgress();
2463         break;
2464       case S_None:
2465         break;
2466       case S_Stop:
2467       case S_Release:
2468       case S_MovableRelease:
2469         llvm_unreachable("top-down pointer in release state!");
2470       }
2471       break;
2472     }
2473     case IC_AutoreleasepoolPop:
2474       // Conservatively, clear MyStates for all known pointers.
2475       MyStates.clearTopDownPointers();
2476       continue;
2477     case IC_AutoreleasepoolPush:
2478     case IC_None:
2479       // These are irrelevant.
2480       continue;
2481     default:
2482       break;
2483     }
2484
2485     // Consider any other possible effects of this instruction on each
2486     // pointer being tracked.
2487     for (BBState::ptr_iterator MI = MyStates.top_down_ptr_begin(),
2488          ME = MyStates.top_down_ptr_end(); MI != ME; ++MI) {
2489       const Value *Ptr = MI->first;
2490       if (Ptr == Arg)
2491         continue; // Handled above.
2492       PtrState &S = MI->second;
2493       Sequence Seq = S.GetSeq();
2494
2495       // Check for possible releases.
2496       if (!IsRetain(Class) && Class != IC_RetainBlock &&
2497           CanAlterRefCount(Inst, Ptr, PA, Class)) {
2498         // Check for a release.
2499         S.DecrementRefCount();
2500
2501         // Check for a release.
2502         switch (Seq) {
2503         case S_Retain:
2504           S.SetSeq(S_CanRelease);
2505           S.RRI.ReverseInsertPts.clear();
2506           S.RRI.ReverseInsertPts.insert(Inst);
2507
2508           // One call can't cause a transition from S_Retain to S_CanRelease
2509           // and S_CanRelease to S_Use. If we've made the first transition,
2510           // we're done.
2511           continue;
2512         case S_Use:
2513         case S_CanRelease:
2514         case S_None:
2515           break;
2516         case S_Stop:
2517         case S_Release:
2518         case S_MovableRelease:
2519           llvm_unreachable("top-down pointer in release state!");
2520         }
2521       }
2522
2523       // Check for possible direct uses.
2524       switch (Seq) {
2525       case S_CanRelease:
2526         if (CanUse(Inst, Ptr, PA, Class))
2527           S.SetSeq(S_Use);
2528         break;
2529       case S_Use:
2530       case S_Retain:
2531       case S_None:
2532         break;
2533       case S_Stop:
2534       case S_Release:
2535       case S_MovableRelease:
2536         llvm_unreachable("top-down pointer in release state!");
2537       }
2538     }
2539   }
2540
2541   CheckForCFGHazards(BB, BBStates, MyStates);
2542   return NestingDetected;
2543 }
2544
2545 // Visit - Visit the function both top-down and bottom-up.
2546 bool
2547 ObjCARCOpt::Visit(Function &F,
2548                   DenseMap<const BasicBlock *, BBState> &BBStates,
2549                   MapVector<Value *, RRInfo> &Retains,
2550                   DenseMap<Value *, RRInfo> &Releases) {
2551   // Use postorder for bottom-up, and reverse-postorder for top-down, because we
2552   // magically know that loops will be well behaved, i.e. they won't repeatedly
2553   // call retain on a single pointer without doing a release.
2554   bool BottomUpNestingDetected = false;
2555   SmallVector<BasicBlock *, 8> PostOrder;
2556   for (po_iterator<Function *> I = po_begin(&F), E = po_end(&F); I != E; ++I) {
2557     BasicBlock *BB = *I;
2558     PostOrder.push_back(BB);
2559
2560     BottomUpNestingDetected |= VisitBottomUp(BB, BBStates, Retains);
2561   }
2562
2563   // Iterate through the post-order in reverse order, achieving a
2564   // reverse-postorder traversal. We don't use the ReversePostOrderTraversal
2565   // class here because it works by computing its own full postorder iteration,
2566   // recording the sequence, and playing it back in reverse. Since we're already
2567   // doing a full iteration above, we can just record the sequence manually and
2568   // avoid the cost of having ReversePostOrderTraversal compute it.
2569   bool TopDownNestingDetected = false;
2570   for (SmallVectorImpl<BasicBlock *>::const_reverse_iterator
2571        RI = PostOrder.rbegin(), RE = PostOrder.rend(); RI != RE; ++RI)
2572     TopDownNestingDetected |= VisitTopDown(*RI, BBStates, Releases);
2573
2574   return TopDownNestingDetected && BottomUpNestingDetected;
2575 }
2576
2577 /// MoveCalls - Move the calls in RetainsToMove and ReleasesToMove.
2578 void ObjCARCOpt::MoveCalls(Value *Arg,
2579                            RRInfo &RetainsToMove,
2580                            RRInfo &ReleasesToMove,
2581                            MapVector<Value *, RRInfo> &Retains,
2582                            DenseMap<Value *, RRInfo> &Releases,
2583                            SmallVectorImpl<Instruction *> &DeadInsts,
2584                            Module *M) {
2585   Type *ArgTy = Arg->getType();
2586   Type *ParamTy = PointerType::getUnqual(Type::getInt8Ty(ArgTy->getContext()));
2587
2588   // Insert the new retain and release calls.
2589   for (SmallPtrSet<Instruction *, 2>::const_iterator
2590        PI = ReleasesToMove.ReverseInsertPts.begin(),
2591        PE = ReleasesToMove.ReverseInsertPts.end(); PI != PE; ++PI) {
2592     Instruction *InsertPt = *PI;
2593     Value *MyArg = ArgTy == ParamTy ? Arg :
2594                    new BitCastInst(Arg, ParamTy, "", InsertPt);
2595     CallInst *Call =
2596       CallInst::Create(RetainsToMove.IsRetainBlock ?
2597                          getRetainBlockCallee(M) : getRetainCallee(M),
2598                        MyArg, "", InsertPt);
2599     Call->setDoesNotThrow();
2600     if (!RetainsToMove.IsRetainBlock)
2601       Call->setTailCall();
2602   }
2603   for (SmallPtrSet<Instruction *, 2>::const_iterator
2604        PI = RetainsToMove.ReverseInsertPts.begin(),
2605        PE = RetainsToMove.ReverseInsertPts.end(); PI != PE; ++PI) {
2606     Instruction *LastUse = *PI;
2607     Instruction *InsertPts[] = { 0, 0, 0 };
2608     if (InvokeInst *II = dyn_cast<InvokeInst>(LastUse)) {
2609       // We can't insert code immediately after an invoke instruction, so
2610       // insert code at the beginning of both successor blocks instead.
2611       // The invoke's return value isn't available in the unwind block,
2612       // but our releases will never depend on it, because they must be
2613       // paired with retains from before the invoke.
2614       InsertPts[0] = II->getNormalDest()->getFirstNonPHI();
2615       InsertPts[1] = II->getUnwindDest()->getFirstNonPHI();
2616     } else {
2617       // Insert code immediately after the last use.
2618       InsertPts[0] = llvm::next(BasicBlock::iterator(LastUse));
2619     }
2620
2621     for (Instruction **I = InsertPts; *I; ++I) {
2622       Instruction *InsertPt = *I;
2623       Value *MyArg = ArgTy == ParamTy ? Arg :
2624                      new BitCastInst(Arg, ParamTy, "", InsertPt);
2625       CallInst *Call = CallInst::Create(getReleaseCallee(M), MyArg,
2626                                         "", InsertPt);
2627       // Attach a clang.imprecise_release metadata tag, if appropriate.
2628       if (MDNode *M = ReleasesToMove.ReleaseMetadata)
2629         Call->setMetadata(ImpreciseReleaseMDKind, M);
2630       Call->setDoesNotThrow();
2631       if (ReleasesToMove.IsTailCallRelease)
2632         Call->setTailCall();
2633     }
2634   }
2635
2636   // Delete the original retain and release calls.
2637   for (SmallPtrSet<Instruction *, 2>::const_iterator
2638        AI = RetainsToMove.Calls.begin(),
2639        AE = RetainsToMove.Calls.end(); AI != AE; ++AI) {
2640     Instruction *OrigRetain = *AI;
2641     Retains.blot(OrigRetain);
2642     DeadInsts.push_back(OrigRetain);
2643   }
2644   for (SmallPtrSet<Instruction *, 2>::const_iterator
2645        AI = ReleasesToMove.Calls.begin(),
2646        AE = ReleasesToMove.Calls.end(); AI != AE; ++AI) {
2647     Instruction *OrigRelease = *AI;
2648     Releases.erase(OrigRelease);
2649     DeadInsts.push_back(OrigRelease);
2650   }
2651 }
2652
2653 bool
2654 ObjCARCOpt::PerformCodePlacement(DenseMap<const BasicBlock *, BBState>
2655                                    &BBStates,
2656                                  MapVector<Value *, RRInfo> &Retains,
2657                                  DenseMap<Value *, RRInfo> &Releases,
2658                                  Module *M) {
2659   bool AnyPairsCompletelyEliminated = false;
2660   RRInfo RetainsToMove;
2661   RRInfo ReleasesToMove;
2662   SmallVector<Instruction *, 4> NewRetains;
2663   SmallVector<Instruction *, 4> NewReleases;
2664   SmallVector<Instruction *, 8> DeadInsts;
2665
2666   for (MapVector<Value *, RRInfo>::const_iterator I = Retains.begin(),
2667        E = Retains.end(); I != E; ) {
2668     Value *V = (I++)->first;
2669     if (!V) continue; // blotted
2670
2671     Instruction *Retain = cast<Instruction>(V);
2672     Value *Arg = GetObjCArg(Retain);
2673
2674     // If the object being released is in static or stack storage, we know it's
2675     // not being managed by ObjC reference counting, so we can delete pairs
2676     // regardless of what possible decrements or uses lie between them.
2677     bool KnownSafe = isa<Constant>(Arg) || isa<AllocaInst>(Arg);
2678
2679     // If a pair happens in a region where it is known that the reference count
2680     // is already incremented, we can similarly ignore possible decrements.
2681     bool KnownIncrementedTD = true, KnownIncrementedBU = true;
2682
2683     // Connect the dots between the top-down-collected RetainsToMove and
2684     // bottom-up-collected ReleasesToMove to form sets of related calls.
2685     // This is an iterative process so that we connect multiple releases
2686     // to multiple retains if needed.
2687     unsigned OldDelta = 0;
2688     unsigned NewDelta = 0;
2689     unsigned OldCount = 0;
2690     unsigned NewCount = 0;
2691     bool FirstRelease = true;
2692     bool FirstRetain = true;
2693     NewRetains.push_back(Retain);
2694     for (;;) {
2695       for (SmallVectorImpl<Instruction *>::const_iterator
2696            NI = NewRetains.begin(), NE = NewRetains.end(); NI != NE; ++NI) {
2697         Instruction *NewRetain = *NI;
2698         MapVector<Value *, RRInfo>::const_iterator It = Retains.find(NewRetain);
2699         assert(It != Retains.end());
2700         const RRInfo &NewRetainRRI = It->second;
2701         KnownIncrementedTD &= NewRetainRRI.KnownIncremented;
2702         for (SmallPtrSet<Instruction *, 2>::const_iterator
2703              LI = NewRetainRRI.Calls.begin(),
2704              LE = NewRetainRRI.Calls.end(); LI != LE; ++LI) {
2705           Instruction *NewRetainRelease = *LI;
2706           DenseMap<Value *, RRInfo>::const_iterator Jt =
2707             Releases.find(NewRetainRelease);
2708           if (Jt == Releases.end())
2709             goto next_retain;
2710           const RRInfo &NewRetainReleaseRRI = Jt->second;
2711           assert(NewRetainReleaseRRI.Calls.count(NewRetain));
2712           if (ReleasesToMove.Calls.insert(NewRetainRelease)) {
2713             OldDelta -=
2714               BBStates[NewRetainRelease->getParent()].GetAllPathCount();
2715
2716             // Merge the ReleaseMetadata and IsTailCallRelease values.
2717             if (FirstRelease) {
2718               ReleasesToMove.ReleaseMetadata =
2719                 NewRetainReleaseRRI.ReleaseMetadata;
2720               ReleasesToMove.IsTailCallRelease =
2721                 NewRetainReleaseRRI.IsTailCallRelease;
2722               FirstRelease = false;
2723             } else {
2724               if (ReleasesToMove.ReleaseMetadata !=
2725                     NewRetainReleaseRRI.ReleaseMetadata)
2726                 ReleasesToMove.ReleaseMetadata = 0;
2727               if (ReleasesToMove.IsTailCallRelease !=
2728                     NewRetainReleaseRRI.IsTailCallRelease)
2729                 ReleasesToMove.IsTailCallRelease = false;
2730             }
2731
2732             // Collect the optimal insertion points.
2733             if (!KnownSafe)
2734               for (SmallPtrSet<Instruction *, 2>::const_iterator
2735                    RI = NewRetainReleaseRRI.ReverseInsertPts.begin(),
2736                    RE = NewRetainReleaseRRI.ReverseInsertPts.end();
2737                    RI != RE; ++RI) {
2738                 Instruction *RIP = *RI;
2739                 if (ReleasesToMove.ReverseInsertPts.insert(RIP))
2740                   NewDelta -= BBStates[RIP->getParent()].GetAllPathCount();
2741               }
2742             NewReleases.push_back(NewRetainRelease);
2743           }
2744         }
2745       }
2746       NewRetains.clear();
2747       if (NewReleases.empty()) break;
2748
2749       // Back the other way.
2750       for (SmallVectorImpl<Instruction *>::const_iterator
2751            NI = NewReleases.begin(), NE = NewReleases.end(); NI != NE; ++NI) {
2752         Instruction *NewRelease = *NI;
2753         DenseMap<Value *, RRInfo>::const_iterator It =
2754           Releases.find(NewRelease);
2755         assert(It != Releases.end());
2756         const RRInfo &NewReleaseRRI = It->second;
2757         KnownIncrementedBU &= NewReleaseRRI.KnownIncremented;
2758         for (SmallPtrSet<Instruction *, 2>::const_iterator
2759              LI = NewReleaseRRI.Calls.begin(),
2760              LE = NewReleaseRRI.Calls.end(); LI != LE; ++LI) {
2761           Instruction *NewReleaseRetain = *LI;
2762           MapVector<Value *, RRInfo>::const_iterator Jt =
2763             Retains.find(NewReleaseRetain);
2764           if (Jt == Retains.end())
2765             goto next_retain;
2766           const RRInfo &NewReleaseRetainRRI = Jt->second;
2767           assert(NewReleaseRetainRRI.Calls.count(NewRelease));
2768           if (RetainsToMove.Calls.insert(NewReleaseRetain)) {
2769             unsigned PathCount =
2770               BBStates[NewReleaseRetain->getParent()].GetAllPathCount();
2771             OldDelta += PathCount;
2772             OldCount += PathCount;
2773
2774             // Merge the IsRetainBlock values.
2775             if (FirstRetain) {
2776               RetainsToMove.IsRetainBlock = NewReleaseRetainRRI.IsRetainBlock;
2777               FirstRetain = false;
2778             } else if (ReleasesToMove.IsRetainBlock !=
2779                        NewReleaseRetainRRI.IsRetainBlock)
2780               // It's not possible to merge the sequences if one uses
2781               // objc_retain and the other uses objc_retainBlock.
2782               goto next_retain;
2783
2784             // Collect the optimal insertion points.
2785             if (!KnownSafe)
2786               for (SmallPtrSet<Instruction *, 2>::const_iterator
2787                    RI = NewReleaseRetainRRI.ReverseInsertPts.begin(),
2788                    RE = NewReleaseRetainRRI.ReverseInsertPts.end();
2789                    RI != RE; ++RI) {
2790                 Instruction *RIP = *RI;
2791                 if (RetainsToMove.ReverseInsertPts.insert(RIP)) {
2792                   PathCount = BBStates[RIP->getParent()].GetAllPathCount();
2793                   NewDelta += PathCount;
2794                   NewCount += PathCount;
2795                 }
2796               }
2797             NewRetains.push_back(NewReleaseRetain);
2798           }
2799         }
2800       }
2801       NewReleases.clear();
2802       if (NewRetains.empty()) break;
2803     }
2804
2805     // If the pointer is known incremented, we can safely delete the pair
2806     // regardless of what's between them.
2807     if (KnownIncrementedTD || KnownIncrementedBU) {
2808       RetainsToMove.ReverseInsertPts.clear();
2809       ReleasesToMove.ReverseInsertPts.clear();
2810       NewCount = 0;
2811     }
2812
2813     // Determine whether the original call points are balanced in the retain and
2814     // release calls through the program. If not, conservatively don't touch
2815     // them.
2816     // TODO: It's theoretically possible to do code motion in this case, as
2817     // long as the existing imbalances are maintained.
2818     if (OldDelta != 0)
2819       goto next_retain;
2820
2821     // Determine whether the new insertion points we computed preserve the
2822     // balance of retain and release calls through the program.
2823     // TODO: If the fully aggressive solution isn't valid, try to find a
2824     // less aggressive solution which is.
2825     if (NewDelta != 0)
2826       goto next_retain;
2827
2828     // Ok, everything checks out and we're all set. Let's move some code!
2829     Changed = true;
2830     AnyPairsCompletelyEliminated = NewCount == 0;
2831     NumRRs += OldCount - NewCount;
2832     MoveCalls(Arg, RetainsToMove, ReleasesToMove,
2833               Retains, Releases, DeadInsts, M);
2834
2835   next_retain:
2836     NewReleases.clear();
2837     NewRetains.clear();
2838     RetainsToMove.clear();
2839     ReleasesToMove.clear();
2840   }
2841
2842   // Now that we're done moving everything, we can delete the newly dead
2843   // instructions, as we no longer need them as insert points.
2844   while (!DeadInsts.empty())
2845     EraseInstruction(DeadInsts.pop_back_val());
2846
2847   return AnyPairsCompletelyEliminated;
2848 }
2849
2850 /// OptimizeWeakCalls - Weak pointer optimizations.
2851 void ObjCARCOpt::OptimizeWeakCalls(Function &F) {
2852   // First, do memdep-style RLE and S2L optimizations. We can't use memdep
2853   // itself because it uses AliasAnalysis and we need to do provenance
2854   // queries instead.
2855   for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
2856     Instruction *Inst = &*I++;
2857     InstructionClass Class = GetBasicInstructionClass(Inst);
2858     if (Class != IC_LoadWeak && Class != IC_LoadWeakRetained)
2859       continue;
2860
2861     // Delete objc_loadWeak calls with no users.
2862     if (Class == IC_LoadWeak && Inst->use_empty()) {
2863       Inst->eraseFromParent();
2864       continue;
2865     }
2866
2867     // TODO: For now, just look for an earlier available version of this value
2868     // within the same block. Theoretically, we could do memdep-style non-local
2869     // analysis too, but that would want caching. A better approach would be to
2870     // use the technique that EarlyCSE uses.
2871     inst_iterator Current = llvm::prior(I);
2872     BasicBlock *CurrentBB = Current.getBasicBlockIterator();
2873     for (BasicBlock::iterator B = CurrentBB->begin(),
2874                               J = Current.getInstructionIterator();
2875          J != B; --J) {
2876       Instruction *EarlierInst = &*llvm::prior(J);
2877       InstructionClass EarlierClass = GetInstructionClass(EarlierInst);
2878       switch (EarlierClass) {
2879       case IC_LoadWeak:
2880       case IC_LoadWeakRetained: {
2881         // If this is loading from the same pointer, replace this load's value
2882         // with that one.
2883         CallInst *Call = cast<CallInst>(Inst);
2884         CallInst *EarlierCall = cast<CallInst>(EarlierInst);
2885         Value *Arg = Call->getArgOperand(0);
2886         Value *EarlierArg = EarlierCall->getArgOperand(0);
2887         switch (PA.getAA()->alias(Arg, EarlierArg)) {
2888         case AliasAnalysis::MustAlias:
2889           Changed = true;
2890           // If the load has a builtin retain, insert a plain retain for it.
2891           if (Class == IC_LoadWeakRetained) {
2892             CallInst *CI =
2893               CallInst::Create(getRetainCallee(F.getParent()), EarlierCall,
2894                                "", Call);
2895             CI->setTailCall();
2896           }
2897           // Zap the fully redundant load.
2898           Call->replaceAllUsesWith(EarlierCall);
2899           Call->eraseFromParent();
2900           goto clobbered;
2901         case AliasAnalysis::MayAlias:
2902         case AliasAnalysis::PartialAlias:
2903           goto clobbered;
2904         case AliasAnalysis::NoAlias:
2905           break;
2906         }
2907         break;
2908       }
2909       case IC_StoreWeak:
2910       case IC_InitWeak: {
2911         // If this is storing to the same pointer and has the same size etc.
2912         // replace this load's value with the stored value.
2913         CallInst *Call = cast<CallInst>(Inst);
2914         CallInst *EarlierCall = cast<CallInst>(EarlierInst);
2915         Value *Arg = Call->getArgOperand(0);
2916         Value *EarlierArg = EarlierCall->getArgOperand(0);
2917         switch (PA.getAA()->alias(Arg, EarlierArg)) {
2918         case AliasAnalysis::MustAlias:
2919           Changed = true;
2920           // If the load has a builtin retain, insert a plain retain for it.
2921           if (Class == IC_LoadWeakRetained) {
2922             CallInst *CI =
2923               CallInst::Create(getRetainCallee(F.getParent()), EarlierCall,
2924                                "", Call);
2925             CI->setTailCall();
2926           }
2927           // Zap the fully redundant load.
2928           Call->replaceAllUsesWith(EarlierCall->getArgOperand(1));
2929           Call->eraseFromParent();
2930           goto clobbered;
2931         case AliasAnalysis::MayAlias:
2932         case AliasAnalysis::PartialAlias:
2933           goto clobbered;
2934         case AliasAnalysis::NoAlias:
2935           break;
2936         }
2937         break;
2938       }
2939       case IC_MoveWeak:
2940       case IC_CopyWeak:
2941         // TOOD: Grab the copied value.
2942         goto clobbered;
2943       case IC_AutoreleasepoolPush:
2944       case IC_None:
2945       case IC_User:
2946         // Weak pointers are only modified through the weak entry points
2947         // (and arbitrary calls, which could call the weak entry points).
2948         break;
2949       default:
2950         // Anything else could modify the weak pointer.
2951         goto clobbered;
2952       }
2953     }
2954   clobbered:;
2955   }
2956
2957   // Then, for each destroyWeak with an alloca operand, check to see if
2958   // the alloca and all its users can be zapped.
2959   for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
2960     Instruction *Inst = &*I++;
2961     InstructionClass Class = GetBasicInstructionClass(Inst);
2962     if (Class != IC_DestroyWeak)
2963       continue;
2964
2965     CallInst *Call = cast<CallInst>(Inst);
2966     Value *Arg = Call->getArgOperand(0);
2967     if (AllocaInst *Alloca = dyn_cast<AllocaInst>(Arg)) {
2968       for (Value::use_iterator UI = Alloca->use_begin(),
2969            UE = Alloca->use_end(); UI != UE; ++UI) {
2970         Instruction *UserInst = cast<Instruction>(*UI);
2971         switch (GetBasicInstructionClass(UserInst)) {
2972         case IC_InitWeak:
2973         case IC_StoreWeak:
2974         case IC_DestroyWeak:
2975           continue;
2976         default:
2977           goto done;
2978         }
2979       }
2980       Changed = true;
2981       for (Value::use_iterator UI = Alloca->use_begin(),
2982            UE = Alloca->use_end(); UI != UE; ) {
2983         CallInst *UserInst = cast<CallInst>(*UI++);
2984         if (!UserInst->use_empty())
2985           UserInst->replaceAllUsesWith(UserInst->getOperand(1));
2986         UserInst->eraseFromParent();
2987       }
2988       Alloca->eraseFromParent();
2989     done:;
2990     }
2991   }
2992 }
2993
2994 /// OptimizeSequences - Identify program paths which execute sequences of
2995 /// retains and releases which can be eliminated.
2996 bool ObjCARCOpt::OptimizeSequences(Function &F) {
2997   /// Releases, Retains - These are used to store the results of the main flow
2998   /// analysis. These use Value* as the key instead of Instruction* so that the
2999   /// map stays valid when we get around to rewriting code and calls get
3000   /// replaced by arguments.
3001   DenseMap<Value *, RRInfo> Releases;
3002   MapVector<Value *, RRInfo> Retains;
3003
3004   /// BBStates, This is used during the traversal of the function to track the
3005   /// states for each identified object at each block.
3006   DenseMap<const BasicBlock *, BBState> BBStates;
3007
3008   // Analyze the CFG of the function, and all instructions.
3009   bool NestingDetected = Visit(F, BBStates, Retains, Releases);
3010
3011   // Transform.
3012   return PerformCodePlacement(BBStates, Retains, Releases, F.getParent()) &&
3013          NestingDetected;
3014 }
3015
3016 /// OptimizeReturns - Look for this pattern:
3017 ///
3018 ///    %call = call i8* @something(...)
3019 ///    %2 = call i8* @objc_retain(i8* %call)
3020 ///    %3 = call i8* @objc_autorelease(i8* %2)
3021 ///    ret i8* %3
3022 ///
3023 /// And delete the retain and autorelease.
3024 ///
3025 /// Otherwise if it's just this:
3026 ///
3027 ///    %3 = call i8* @objc_autorelease(i8* %2)
3028 ///    ret i8* %3
3029 ///
3030 /// convert the autorelease to autoreleaseRV.
3031 void ObjCARCOpt::OptimizeReturns(Function &F) {
3032   if (!F.getReturnType()->isPointerTy())
3033     return;
3034
3035   SmallPtrSet<Instruction *, 4> DependingInstructions;
3036   SmallPtrSet<const BasicBlock *, 4> Visited;
3037   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
3038     BasicBlock *BB = FI;
3039     ReturnInst *Ret = dyn_cast<ReturnInst>(&BB->back());
3040     if (!Ret) continue;
3041
3042     const Value *Arg = StripPointerCastsAndObjCCalls(Ret->getOperand(0));
3043     FindDependencies(NeedsPositiveRetainCount, Arg,
3044                      BB, Ret, DependingInstructions, Visited, PA);
3045     if (DependingInstructions.size() != 1)
3046       goto next_block;
3047
3048     {
3049       CallInst *Autorelease =
3050         dyn_cast_or_null<CallInst>(*DependingInstructions.begin());
3051       if (!Autorelease)
3052         goto next_block;
3053       InstructionClass AutoreleaseClass =
3054         GetBasicInstructionClass(Autorelease);
3055       if (!IsAutorelease(AutoreleaseClass))
3056         goto next_block;
3057       if (GetObjCArg(Autorelease) != Arg)
3058         goto next_block;
3059
3060       DependingInstructions.clear();
3061       Visited.clear();
3062
3063       // Check that there is nothing that can affect the reference
3064       // count between the autorelease and the retain.
3065       FindDependencies(CanChangeRetainCount, Arg,
3066                        BB, Autorelease, DependingInstructions, Visited, PA);
3067       if (DependingInstructions.size() != 1)
3068         goto next_block;
3069
3070       {
3071         CallInst *Retain =
3072           dyn_cast_or_null<CallInst>(*DependingInstructions.begin());
3073
3074         // Check that we found a retain with the same argument.
3075         if (!Retain ||
3076             !IsRetain(GetBasicInstructionClass(Retain)) ||
3077             GetObjCArg(Retain) != Arg)
3078           goto next_block;
3079
3080         DependingInstructions.clear();
3081         Visited.clear();
3082
3083         // Convert the autorelease to an autoreleaseRV, since it's
3084         // returning the value.
3085         if (AutoreleaseClass == IC_Autorelease) {
3086           Autorelease->setCalledFunction(getAutoreleaseRVCallee(F.getParent()));
3087           AutoreleaseClass = IC_AutoreleaseRV;
3088         }
3089
3090         // Check that there is nothing that can affect the reference
3091         // count between the retain and the call.
3092         FindDependencies(CanChangeRetainCount, Arg, BB, Retain,
3093                          DependingInstructions, Visited, PA);
3094         if (DependingInstructions.size() != 1)
3095           goto next_block;
3096
3097         {
3098           CallInst *Call =
3099             dyn_cast_or_null<CallInst>(*DependingInstructions.begin());
3100
3101           // Check that the pointer is the return value of the call.
3102           if (!Call || Arg != Call)
3103             goto next_block;
3104
3105           // Check that the call is a regular call.
3106           InstructionClass Class = GetBasicInstructionClass(Call);
3107           if (Class != IC_CallOrUser && Class != IC_Call)
3108             goto next_block;
3109
3110           // If so, we can zap the retain and autorelease.
3111           Changed = true;
3112           ++NumRets;
3113           EraseInstruction(Retain);
3114           EraseInstruction(Autorelease);
3115         }
3116       }
3117     }
3118
3119   next_block:
3120     DependingInstructions.clear();
3121     Visited.clear();
3122   }
3123 }
3124
3125 bool ObjCARCOpt::doInitialization(Module &M) {
3126   if (!EnableARCOpts)
3127     return false;
3128
3129   Run = ModuleHasARC(M);
3130   if (!Run)
3131     return false;
3132
3133   // Identify the imprecise release metadata kind.
3134   ImpreciseReleaseMDKind =
3135     M.getContext().getMDKindID("clang.imprecise_release");
3136
3137   // Intuitively, objc_retain and others are nocapture, however in practice
3138   // they are not, because they return their argument value. And objc_release
3139   // calls finalizers.
3140
3141   // These are initialized lazily.
3142   RetainRVCallee = 0;
3143   AutoreleaseRVCallee = 0;
3144   ReleaseCallee = 0;
3145   RetainCallee = 0;
3146   RetainBlockCallee = 0;
3147   AutoreleaseCallee = 0;
3148
3149   return false;
3150 }
3151
3152 bool ObjCARCOpt::runOnFunction(Function &F) {
3153   if (!EnableARCOpts)
3154     return false;
3155
3156   // If nothing in the Module uses ARC, don't do anything.
3157   if (!Run)
3158     return false;
3159
3160   Changed = false;
3161
3162   PA.setAA(&getAnalysis<AliasAnalysis>());
3163
3164   // This pass performs several distinct transformations. As a compile-time aid
3165   // when compiling code that isn't ObjC, skip these if the relevant ObjC
3166   // library functions aren't declared.
3167
3168   // Preliminary optimizations. This also computs UsedInThisFunction.
3169   OptimizeIndividualCalls(F);
3170
3171   // Optimizations for weak pointers.
3172   if (UsedInThisFunction & ((1 << IC_LoadWeak) |
3173                             (1 << IC_LoadWeakRetained) |
3174                             (1 << IC_StoreWeak) |
3175                             (1 << IC_InitWeak) |
3176                             (1 << IC_CopyWeak) |
3177                             (1 << IC_MoveWeak) |
3178                             (1 << IC_DestroyWeak)))
3179     OptimizeWeakCalls(F);
3180
3181   // Optimizations for retain+release pairs.
3182   if (UsedInThisFunction & ((1 << IC_Retain) |
3183                             (1 << IC_RetainRV) |
3184                             (1 << IC_RetainBlock)))
3185     if (UsedInThisFunction & (1 << IC_Release))
3186       // Run OptimizeSequences until it either stops making changes or
3187       // no retain+release pair nesting is detected.
3188       while (OptimizeSequences(F)) {}
3189
3190   // Optimizations if objc_autorelease is used.
3191   if (UsedInThisFunction &
3192       ((1 << IC_Autorelease) | (1 << IC_AutoreleaseRV)))
3193     OptimizeReturns(F);
3194
3195   return Changed;
3196 }
3197
3198 void ObjCARCOpt::releaseMemory() {
3199   PA.clear();
3200 }
3201
3202 //===----------------------------------------------------------------------===//
3203 // ARC contraction.
3204 //===----------------------------------------------------------------------===//
3205
3206 // TODO: ObjCARCContract could insert PHI nodes when uses aren't
3207 // dominated by single calls.
3208
3209 #include "llvm/Operator.h"
3210 #include "llvm/InlineAsm.h"
3211 #include "llvm/Analysis/Dominators.h"
3212
3213 STATISTIC(NumStoreStrongs, "Number objc_storeStrong calls formed");
3214
3215 namespace {
3216   /// ObjCARCContract - Late ARC optimizations.  These change the IR in a way
3217   /// that makes it difficult to be analyzed by ObjCARCOpt, so it's run late.
3218   class ObjCARCContract : public FunctionPass {
3219     bool Changed;
3220     AliasAnalysis *AA;
3221     DominatorTree *DT;
3222     ProvenanceAnalysis PA;
3223
3224     /// Run - A flag indicating whether this optimization pass should run.
3225     bool Run;
3226
3227     /// StoreStrongCallee, etc. - Declarations for ObjC runtime
3228     /// functions, for use in creating calls to them. These are initialized
3229     /// lazily to avoid cluttering up the Module with unused declarations.
3230     Constant *StoreStrongCallee,
3231              *RetainAutoreleaseCallee, *RetainAutoreleaseRVCallee;
3232
3233     /// RetainRVMarker - The inline asm string to insert between calls and
3234     /// RetainRV calls to make the optimization work on targets which need it.
3235     const MDString *RetainRVMarker;
3236
3237     Constant *getStoreStrongCallee(Module *M);
3238     Constant *getRetainAutoreleaseCallee(Module *M);
3239     Constant *getRetainAutoreleaseRVCallee(Module *M);
3240
3241     bool ContractAutorelease(Function &F, Instruction *Autorelease,
3242                              InstructionClass Class,
3243                              SmallPtrSet<Instruction *, 4>
3244                                &DependingInstructions,
3245                              SmallPtrSet<const BasicBlock *, 4>
3246                                &Visited);
3247
3248     void ContractRelease(Instruction *Release,
3249                          inst_iterator &Iter);
3250
3251     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
3252     virtual bool doInitialization(Module &M);
3253     virtual bool runOnFunction(Function &F);
3254
3255   public:
3256     static char ID;
3257     ObjCARCContract() : FunctionPass(ID) {
3258       initializeObjCARCContractPass(*PassRegistry::getPassRegistry());
3259     }
3260   };
3261 }
3262
3263 char ObjCARCContract::ID = 0;
3264 INITIALIZE_PASS_BEGIN(ObjCARCContract,
3265                       "objc-arc-contract", "ObjC ARC contraction", false, false)
3266 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
3267 INITIALIZE_PASS_DEPENDENCY(DominatorTree)
3268 INITIALIZE_PASS_END(ObjCARCContract,
3269                     "objc-arc-contract", "ObjC ARC contraction", false, false)
3270
3271 Pass *llvm::createObjCARCContractPass() {
3272   return new ObjCARCContract();
3273 }
3274
3275 void ObjCARCContract::getAnalysisUsage(AnalysisUsage &AU) const {
3276   AU.addRequired<AliasAnalysis>();
3277   AU.addRequired<DominatorTree>();
3278   AU.setPreservesCFG();
3279 }
3280
3281 Constant *ObjCARCContract::getStoreStrongCallee(Module *M) {
3282   if (!StoreStrongCallee) {
3283     LLVMContext &C = M->getContext();
3284     Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
3285     Type *I8XX = PointerType::getUnqual(I8X);
3286     std::vector<Type *> Params;
3287     Params.push_back(I8XX);
3288     Params.push_back(I8X);
3289
3290     AttrListPtr Attributes;
3291     Attributes.addAttr(~0u, Attribute::NoUnwind);
3292     Attributes.addAttr(1, Attribute::NoCapture);
3293
3294     StoreStrongCallee =
3295       M->getOrInsertFunction(
3296         "objc_storeStrong",
3297         FunctionType::get(Type::getVoidTy(C), Params, /*isVarArg=*/false),
3298         Attributes);
3299   }
3300   return StoreStrongCallee;
3301 }
3302
3303 Constant *ObjCARCContract::getRetainAutoreleaseCallee(Module *M) {
3304   if (!RetainAutoreleaseCallee) {
3305     LLVMContext &C = M->getContext();
3306     Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
3307     std::vector<Type *> Params;
3308     Params.push_back(I8X);
3309     FunctionType *FTy =
3310       FunctionType::get(I8X, Params, /*isVarArg=*/false);
3311     AttrListPtr Attributes;
3312     Attributes.addAttr(~0u, Attribute::NoUnwind);
3313     RetainAutoreleaseCallee =
3314       M->getOrInsertFunction("objc_retainAutorelease", FTy, Attributes);
3315   }
3316   return RetainAutoreleaseCallee;
3317 }
3318
3319 Constant *ObjCARCContract::getRetainAutoreleaseRVCallee(Module *M) {
3320   if (!RetainAutoreleaseRVCallee) {
3321     LLVMContext &C = M->getContext();
3322     Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
3323     std::vector<Type *> Params;
3324     Params.push_back(I8X);
3325     FunctionType *FTy =
3326       FunctionType::get(I8X, Params, /*isVarArg=*/false);
3327     AttrListPtr Attributes;
3328     Attributes.addAttr(~0u, Attribute::NoUnwind);
3329     RetainAutoreleaseRVCallee =
3330       M->getOrInsertFunction("objc_retainAutoreleaseReturnValue", FTy,
3331                              Attributes);
3332   }
3333   return RetainAutoreleaseRVCallee;
3334 }
3335
3336 /// ContractAutorelease - Merge an autorelease with a retain into a fused
3337 /// call.
3338 bool
3339 ObjCARCContract::ContractAutorelease(Function &F, Instruction *Autorelease,
3340                                      InstructionClass Class,
3341                                      SmallPtrSet<Instruction *, 4>
3342                                        &DependingInstructions,
3343                                      SmallPtrSet<const BasicBlock *, 4>
3344                                        &Visited) {
3345   const Value *Arg = GetObjCArg(Autorelease);
3346
3347   // Check that there are no instructions between the retain and the autorelease
3348   // (such as an autorelease_pop) which may change the count.
3349   CallInst *Retain = 0;
3350   if (Class == IC_AutoreleaseRV)
3351     FindDependencies(RetainAutoreleaseRVDep, Arg,
3352                      Autorelease->getParent(), Autorelease,
3353                      DependingInstructions, Visited, PA);
3354   else
3355     FindDependencies(RetainAutoreleaseDep, Arg,
3356                      Autorelease->getParent(), Autorelease,
3357                      DependingInstructions, Visited, PA);
3358
3359   Visited.clear();
3360   if (DependingInstructions.size() != 1) {
3361     DependingInstructions.clear();
3362     return false;
3363   }
3364
3365   Retain = dyn_cast_or_null<CallInst>(*DependingInstructions.begin());
3366   DependingInstructions.clear();
3367
3368   if (!Retain ||
3369       GetBasicInstructionClass(Retain) != IC_Retain ||
3370       GetObjCArg(Retain) != Arg)
3371     return false;
3372
3373   Changed = true;
3374   ++NumPeeps;
3375
3376   if (Class == IC_AutoreleaseRV)
3377     Retain->setCalledFunction(getRetainAutoreleaseRVCallee(F.getParent()));
3378   else
3379     Retain->setCalledFunction(getRetainAutoreleaseCallee(F.getParent()));
3380
3381   EraseInstruction(Autorelease);
3382   return true;
3383 }
3384
3385 /// ContractRelease - Attempt to merge an objc_release with a store, load, and
3386 /// objc_retain to form an objc_storeStrong. This can be a little tricky because
3387 /// the instructions don't always appear in order, and there may be unrelated
3388 /// intervening instructions.
3389 void ObjCARCContract::ContractRelease(Instruction *Release,
3390                                       inst_iterator &Iter) {
3391   LoadInst *Load = dyn_cast<LoadInst>(GetObjCArg(Release));
3392   if (!Load || Load->isVolatile()) return;
3393
3394   // For now, require everything to be in one basic block.
3395   BasicBlock *BB = Release->getParent();
3396   if (Load->getParent() != BB) return;
3397
3398   // Walk down to find the store.
3399   BasicBlock::iterator I = Load, End = BB->end();
3400   ++I;
3401   AliasAnalysis::Location Loc = AA->getLocation(Load);
3402   while (I != End &&
3403          (&*I == Release ||
3404           IsRetain(GetBasicInstructionClass(I)) ||
3405           !(AA->getModRefInfo(I, Loc) & AliasAnalysis::Mod)))
3406     ++I;
3407   StoreInst *Store = dyn_cast<StoreInst>(I);
3408   if (!Store || Store->isVolatile()) return;
3409   if (Store->getPointerOperand() != Loc.Ptr) return;
3410
3411   Value *New = StripPointerCastsAndObjCCalls(Store->getValueOperand());
3412
3413   // Walk up to find the retain.
3414   I = Store;
3415   BasicBlock::iterator Begin = BB->begin();
3416   while (I != Begin && GetBasicInstructionClass(I) != IC_Retain)
3417     --I;
3418   Instruction *Retain = I;
3419   if (GetBasicInstructionClass(Retain) != IC_Retain) return;
3420   if (GetObjCArg(Retain) != New) return;
3421
3422   Changed = true;
3423   ++NumStoreStrongs;
3424
3425   LLVMContext &C = Release->getContext();
3426   Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
3427   Type *I8XX = PointerType::getUnqual(I8X);
3428
3429   Value *Args[] = { Load->getPointerOperand(), New };
3430   if (Args[0]->getType() != I8XX)
3431     Args[0] = new BitCastInst(Args[0], I8XX, "", Store);
3432   if (Args[1]->getType() != I8X)
3433     Args[1] = new BitCastInst(Args[1], I8X, "", Store);
3434   CallInst *StoreStrong =
3435     CallInst::Create(getStoreStrongCallee(BB->getParent()->getParent()),
3436                      Args, "", Store);
3437   StoreStrong->setDoesNotThrow();
3438   StoreStrong->setDebugLoc(Store->getDebugLoc());
3439
3440   if (&*Iter == Store) ++Iter;
3441   Store->eraseFromParent();
3442   Release->eraseFromParent();
3443   EraseInstruction(Retain);
3444   if (Load->use_empty())
3445     Load->eraseFromParent();
3446 }
3447
3448 bool ObjCARCContract::doInitialization(Module &M) {
3449   Run = ModuleHasARC(M);
3450   if (!Run)
3451     return false;
3452
3453   // These are initialized lazily.
3454   StoreStrongCallee = 0;
3455   RetainAutoreleaseCallee = 0;
3456   RetainAutoreleaseRVCallee = 0;
3457
3458   // Initialize RetainRVMarker.
3459   RetainRVMarker = 0;
3460   if (NamedMDNode *NMD =
3461         M.getNamedMetadata("clang.arc.retainAutoreleasedReturnValueMarker"))
3462     if (NMD->getNumOperands() == 1) {
3463       const MDNode *N = NMD->getOperand(0);
3464       if (N->getNumOperands() == 1)
3465         if (const MDString *S = dyn_cast<MDString>(N->getOperand(0)))
3466           RetainRVMarker = S;
3467     }
3468
3469   return false;
3470 }
3471
3472 bool ObjCARCContract::runOnFunction(Function &F) {
3473   if (!EnableARCOpts)
3474     return false;
3475
3476   // If nothing in the Module uses ARC, don't do anything.
3477   if (!Run)
3478     return false;
3479
3480   Changed = false;
3481   AA = &getAnalysis<AliasAnalysis>();
3482   DT = &getAnalysis<DominatorTree>();
3483
3484   PA.setAA(&getAnalysis<AliasAnalysis>());
3485
3486   // For ObjC library calls which return their argument, replace uses of the
3487   // argument with uses of the call return value, if it dominates the use. This
3488   // reduces register pressure.
3489   SmallPtrSet<Instruction *, 4> DependingInstructions;
3490   SmallPtrSet<const BasicBlock *, 4> Visited;
3491   for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
3492     Instruction *Inst = &*I++;
3493
3494     // Only these library routines return their argument. In particular,
3495     // objc_retainBlock does not necessarily return its argument.
3496     InstructionClass Class = GetBasicInstructionClass(Inst);
3497     switch (Class) {
3498     case IC_Retain:
3499     case IC_FusedRetainAutorelease:
3500     case IC_FusedRetainAutoreleaseRV:
3501       break;
3502     case IC_Autorelease:
3503     case IC_AutoreleaseRV:
3504       if (ContractAutorelease(F, Inst, Class, DependingInstructions, Visited))
3505         continue;
3506       break;
3507     case IC_RetainRV: {
3508       // If we're compiling for a target which needs a special inline-asm
3509       // marker to do the retainAutoreleasedReturnValue optimization,
3510       // insert it now.
3511       if (!RetainRVMarker)
3512         break;
3513       BasicBlock::iterator BBI = Inst;
3514       --BBI;
3515       while (isNoopInstruction(BBI)) --BBI;
3516       if (&*BBI == GetObjCArg(Inst)) {
3517         InlineAsm *IA =
3518           InlineAsm::get(FunctionType::get(Type::getVoidTy(Inst->getContext()),
3519                                            /*isVarArg=*/false),
3520                          RetainRVMarker->getString(),
3521                          /*Constraints=*/"", /*hasSideEffects=*/true);
3522         CallInst::Create(IA, "", Inst);
3523       }
3524       break;
3525     }
3526     case IC_InitWeak: {
3527       // objc_initWeak(p, null) => *p = null
3528       CallInst *CI = cast<CallInst>(Inst);
3529       if (isNullOrUndef(CI->getArgOperand(1))) {
3530         Value *Null =
3531           ConstantPointerNull::get(cast<PointerType>(CI->getType()));
3532         Changed = true;
3533         new StoreInst(Null, CI->getArgOperand(0), CI);
3534         CI->replaceAllUsesWith(Null);
3535         CI->eraseFromParent();
3536       }
3537       continue;
3538     }
3539     case IC_Release:
3540       ContractRelease(Inst, I);
3541       continue;
3542     default:
3543       continue;
3544     }
3545
3546     // Don't use GetObjCArg because we don't want to look through bitcasts
3547     // and such; to do the replacement, the argument must have type i8*.
3548     const Value *Arg = cast<CallInst>(Inst)->getArgOperand(0);
3549     for (;;) {
3550       // If we're compiling bugpointed code, don't get in trouble.
3551       if (!isa<Instruction>(Arg) && !isa<Argument>(Arg))
3552         break;
3553       // Look through the uses of the pointer.
3554       for (Value::const_use_iterator UI = Arg->use_begin(), UE = Arg->use_end();
3555            UI != UE; ) {
3556         Use &U = UI.getUse();
3557         unsigned OperandNo = UI.getOperandNo();
3558         ++UI; // Increment UI now, because we may unlink its element.
3559         if (Instruction *UserInst = dyn_cast<Instruction>(U.getUser()))
3560           if (Inst != UserInst && DT->dominates(Inst, UserInst)) {
3561             Changed = true;
3562             Instruction *Replacement = Inst;
3563             Type *UseTy = U.get()->getType();
3564             if (PHINode *PHI = dyn_cast<PHINode>(UserInst)) {
3565               // For PHI nodes, insert the bitcast in the predecessor block.
3566               unsigned ValNo =
3567                 PHINode::getIncomingValueNumForOperand(OperandNo);
3568               BasicBlock *BB =
3569                 PHI->getIncomingBlock(ValNo);
3570               if (Replacement->getType() != UseTy)
3571                 Replacement = new BitCastInst(Replacement, UseTy, "",
3572                                               &BB->back());
3573               for (unsigned i = 0, e = PHI->getNumIncomingValues();
3574                    i != e; ++i)
3575                 if (PHI->getIncomingBlock(i) == BB) {
3576                   // Keep the UI iterator valid.
3577                   if (&PHI->getOperandUse(
3578                         PHINode::getOperandNumForIncomingValue(i)) ==
3579                         &UI.getUse())
3580                     ++UI;
3581                   PHI->setIncomingValue(i, Replacement);
3582                 }
3583             } else {
3584               if (Replacement->getType() != UseTy)
3585                 Replacement = new BitCastInst(Replacement, UseTy, "", UserInst);
3586               U.set(Replacement);
3587             }
3588           }
3589       }
3590
3591       // If Arg is a no-op casted pointer, strip one level of casts and
3592       // iterate.
3593       if (const BitCastInst *BI = dyn_cast<BitCastInst>(Arg))
3594         Arg = BI->getOperand(0);
3595       else if (isa<GEPOperator>(Arg) &&
3596                cast<GEPOperator>(Arg)->hasAllZeroIndices())
3597         Arg = cast<GEPOperator>(Arg)->getPointerOperand();
3598       else if (isa<GlobalAlias>(Arg) &&
3599                !cast<GlobalAlias>(Arg)->mayBeOverridden())
3600         Arg = cast<GlobalAlias>(Arg)->getAliasee();
3601       else
3602         break;
3603     }
3604   }
3605
3606   return Changed;
3607 }