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     bool IsKnownIncremented() const {
1198       return RefCount > 0;
1199     }
1200
1201     void SetSeq(Sequence NewSeq) {
1202       Seq = NewSeq;
1203     }
1204
1205     void SetSeqToRelease(MDNode *M) {
1206       if (Seq == S_None || Seq == S_Use) {
1207         Seq = M ? S_MovableRelease : S_Release;
1208         RRI.ReleaseMetadata = M;
1209       } else if (Seq != S_MovableRelease || RRI.ReleaseMetadata != M) {
1210         Seq = S_Release;
1211         RRI.ReleaseMetadata = 0;
1212       }
1213     }
1214
1215     Sequence GetSeq() const {
1216       return Seq;
1217     }
1218
1219     void ClearSequenceProgress() {
1220       Seq = S_None;
1221       RRI.clear();
1222     }
1223
1224     void Merge(const PtrState &Other, bool TopDown);
1225   };
1226 }
1227
1228 void
1229 PtrState::Merge(const PtrState &Other, bool TopDown) {
1230   Seq = MergeSeqs(Seq, Other.Seq, TopDown);
1231   RefCount = std::min(RefCount, Other.RefCount);
1232
1233   // We can't merge a plain objc_retain with an objc_retainBlock.
1234   if (RRI.IsRetainBlock != Other.RRI.IsRetainBlock)
1235     Seq = S_None;
1236
1237   if (Seq == S_None) {
1238     RRI.clear();
1239   } else {
1240     // Conservatively merge the ReleaseMetadata information.
1241     if (RRI.ReleaseMetadata != Other.RRI.ReleaseMetadata)
1242       RRI.ReleaseMetadata = 0;
1243
1244     RRI.KnownIncremented = RRI.KnownIncremented && Other.RRI.KnownIncremented;
1245     RRI.IsTailCallRelease = RRI.IsTailCallRelease && Other.RRI.IsTailCallRelease;
1246     RRI.Calls.insert(Other.RRI.Calls.begin(), Other.RRI.Calls.end());
1247     RRI.ReverseInsertPts.insert(Other.RRI.ReverseInsertPts.begin(),
1248                                 Other.RRI.ReverseInsertPts.end());
1249   }
1250 }
1251
1252 namespace {
1253   /// BBState - Per-BasicBlock state.
1254   class BBState {
1255     /// TopDownPathCount - The number of unique control paths from the entry
1256     /// which can reach this block.
1257     unsigned TopDownPathCount;
1258
1259     /// BottomUpPathCount - The number of unique control paths to exits
1260     /// from this block.
1261     unsigned BottomUpPathCount;
1262
1263     /// MapTy - A type for PerPtrTopDown and PerPtrBottomUp.
1264     typedef MapVector<const Value *, PtrState> MapTy;
1265
1266     /// PerPtrTopDown - The top-down traversal uses this to record information
1267     /// known about a pointer at the bottom of each block.
1268     MapTy PerPtrTopDown;
1269
1270     /// PerPtrBottomUp - The bottom-up traversal uses this to record information
1271     /// known about a pointer at the top of each block.
1272     MapTy PerPtrBottomUp;
1273
1274   public:
1275     BBState() : TopDownPathCount(0), BottomUpPathCount(0) {}
1276
1277     typedef MapTy::iterator ptr_iterator;
1278     typedef MapTy::const_iterator ptr_const_iterator;
1279
1280     ptr_iterator top_down_ptr_begin() { return PerPtrTopDown.begin(); }
1281     ptr_iterator top_down_ptr_end() { return PerPtrTopDown.end(); }
1282     ptr_const_iterator top_down_ptr_begin() const {
1283       return PerPtrTopDown.begin();
1284     }
1285     ptr_const_iterator top_down_ptr_end() const {
1286       return PerPtrTopDown.end();
1287     }
1288
1289     ptr_iterator bottom_up_ptr_begin() { return PerPtrBottomUp.begin(); }
1290     ptr_iterator bottom_up_ptr_end() { return PerPtrBottomUp.end(); }
1291     ptr_const_iterator bottom_up_ptr_begin() const {
1292       return PerPtrBottomUp.begin();
1293     }
1294     ptr_const_iterator bottom_up_ptr_end() const {
1295       return PerPtrBottomUp.end();
1296     }
1297
1298     /// SetAsEntry - Mark this block as being an entry block, which has one
1299     /// path from the entry by definition.
1300     void SetAsEntry() { TopDownPathCount = 1; }
1301
1302     /// SetAsExit - Mark this block as being an exit block, which has one
1303     /// path to an exit by definition.
1304     void SetAsExit()  { BottomUpPathCount = 1; }
1305
1306     PtrState &getPtrTopDownState(const Value *Arg) {
1307       return PerPtrTopDown[Arg];
1308     }
1309
1310     PtrState &getPtrBottomUpState(const Value *Arg) {
1311       return PerPtrBottomUp[Arg];
1312     }
1313
1314     void clearBottomUpPointers() {
1315       PerPtrBottomUp.clear();
1316     }
1317
1318     void clearTopDownPointers() {
1319       PerPtrTopDown.clear();
1320     }
1321
1322     void InitFromPred(const BBState &Other);
1323     void InitFromSucc(const BBState &Other);
1324     void MergePred(const BBState &Other);
1325     void MergeSucc(const BBState &Other);
1326
1327     /// GetAllPathCount - Return the number of possible unique paths from an
1328     /// entry to an exit which pass through this block. This is only valid
1329     /// after both the top-down and bottom-up traversals are complete.
1330     unsigned GetAllPathCount() const {
1331       return TopDownPathCount * BottomUpPathCount;
1332     }
1333   };
1334 }
1335
1336 void BBState::InitFromPred(const BBState &Other) {
1337   PerPtrTopDown = Other.PerPtrTopDown;
1338   TopDownPathCount = Other.TopDownPathCount;
1339 }
1340
1341 void BBState::InitFromSucc(const BBState &Other) {
1342   PerPtrBottomUp = Other.PerPtrBottomUp;
1343   BottomUpPathCount = Other.BottomUpPathCount;
1344 }
1345
1346 /// MergePred - The top-down traversal uses this to merge information about
1347 /// predecessors to form the initial state for a new block.
1348 void BBState::MergePred(const BBState &Other) {
1349   // Other.TopDownPathCount can be 0, in which case it is either dead or a
1350   // loop backedge. Loop backedges are special.
1351   TopDownPathCount += Other.TopDownPathCount;
1352
1353   // For each entry in the other set, if our set has an entry with the same key,
1354   // merge the entries. Otherwise, copy the entry and merge it with an empty
1355   // entry.
1356   for (ptr_const_iterator MI = Other.top_down_ptr_begin(),
1357        ME = Other.top_down_ptr_end(); MI != ME; ++MI) {
1358     std::pair<ptr_iterator, bool> Pair = PerPtrTopDown.insert(*MI);
1359     Pair.first->second.Merge(Pair.second ? PtrState() : MI->second,
1360                              /*TopDown=*/true);
1361   }
1362
1363   // For each entry in our set, if the other set doesn't have an entry with the
1364   // same key, force it to merge with an empty entry.
1365   for (ptr_iterator MI = top_down_ptr_begin(),
1366        ME = top_down_ptr_end(); MI != ME; ++MI)
1367     if (Other.PerPtrTopDown.find(MI->first) == Other.PerPtrTopDown.end())
1368       MI->second.Merge(PtrState(), /*TopDown=*/true);
1369 }
1370
1371 /// MergeSucc - The bottom-up traversal uses this to merge information about
1372 /// successors to form the initial state for a new block.
1373 void BBState::MergeSucc(const BBState &Other) {
1374   // Other.BottomUpPathCount can be 0, in which case it is either dead or a
1375   // loop backedge. Loop backedges are special.
1376   BottomUpPathCount += Other.BottomUpPathCount;
1377
1378   // For each entry in the other set, if our set has an entry with the
1379   // same key, merge the entries. Otherwise, copy the entry and merge
1380   // it with an empty entry.
1381   for (ptr_const_iterator MI = Other.bottom_up_ptr_begin(),
1382        ME = Other.bottom_up_ptr_end(); MI != ME; ++MI) {
1383     std::pair<ptr_iterator, bool> Pair = PerPtrBottomUp.insert(*MI);
1384     Pair.first->second.Merge(Pair.second ? PtrState() : MI->second,
1385                              /*TopDown=*/false);
1386   }
1387
1388   // For each entry in our set, if the other set doesn't have an entry
1389   // with the same key, force it to merge with an empty entry.
1390   for (ptr_iterator MI = bottom_up_ptr_begin(),
1391        ME = bottom_up_ptr_end(); MI != ME; ++MI)
1392     if (Other.PerPtrBottomUp.find(MI->first) == Other.PerPtrBottomUp.end())
1393       MI->second.Merge(PtrState(), /*TopDown=*/false);
1394 }
1395
1396 namespace {
1397   /// ObjCARCOpt - The main ARC optimization pass.
1398   class ObjCARCOpt : public FunctionPass {
1399     bool Changed;
1400     ProvenanceAnalysis PA;
1401
1402     /// Run - A flag indicating whether this optimization pass should run.
1403     bool Run;
1404
1405     /// RetainRVCallee, etc. - Declarations for ObjC runtime
1406     /// functions, for use in creating calls to them. These are initialized
1407     /// lazily to avoid cluttering up the Module with unused declarations.
1408     Constant *RetainRVCallee, *AutoreleaseRVCallee, *ReleaseCallee,
1409              *RetainCallee, *RetainBlockCallee, *AutoreleaseCallee;
1410
1411     /// UsedInThisFunciton - Flags which determine whether each of the
1412     /// interesting runtine functions is in fact used in the current function.
1413     unsigned UsedInThisFunction;
1414
1415     /// ImpreciseReleaseMDKind - The Metadata Kind for clang.imprecise_release
1416     /// metadata.
1417     unsigned ImpreciseReleaseMDKind;
1418
1419     Constant *getRetainRVCallee(Module *M);
1420     Constant *getAutoreleaseRVCallee(Module *M);
1421     Constant *getReleaseCallee(Module *M);
1422     Constant *getRetainCallee(Module *M);
1423     Constant *getRetainBlockCallee(Module *M);
1424     Constant *getAutoreleaseCallee(Module *M);
1425
1426     void OptimizeRetainCall(Function &F, Instruction *Retain);
1427     bool OptimizeRetainRVCall(Function &F, Instruction *RetainRV);
1428     void OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV);
1429     void OptimizeIndividualCalls(Function &F);
1430
1431     void CheckForCFGHazards(const BasicBlock *BB,
1432                             DenseMap<const BasicBlock *, BBState> &BBStates,
1433                             BBState &MyStates) const;
1434     bool VisitBottomUp(BasicBlock *BB,
1435                        DenseMap<const BasicBlock *, BBState> &BBStates,
1436                        MapVector<Value *, RRInfo> &Retains);
1437     bool VisitTopDown(BasicBlock *BB,
1438                       DenseMap<const BasicBlock *, BBState> &BBStates,
1439                       DenseMap<Value *, RRInfo> &Releases);
1440     bool Visit(Function &F,
1441                DenseMap<const BasicBlock *, BBState> &BBStates,
1442                MapVector<Value *, RRInfo> &Retains,
1443                DenseMap<Value *, RRInfo> &Releases);
1444
1445     void MoveCalls(Value *Arg, RRInfo &RetainsToMove, RRInfo &ReleasesToMove,
1446                    MapVector<Value *, RRInfo> &Retains,
1447                    DenseMap<Value *, RRInfo> &Releases,
1448                    SmallVectorImpl<Instruction *> &DeadInsts,
1449                    Module *M);
1450
1451     bool PerformCodePlacement(DenseMap<const BasicBlock *, BBState> &BBStates,
1452                               MapVector<Value *, RRInfo> &Retains,
1453                               DenseMap<Value *, RRInfo> &Releases,
1454                               Module *M);
1455
1456     void OptimizeWeakCalls(Function &F);
1457
1458     bool OptimizeSequences(Function &F);
1459
1460     void OptimizeReturns(Function &F);
1461
1462     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
1463     virtual bool doInitialization(Module &M);
1464     virtual bool runOnFunction(Function &F);
1465     virtual void releaseMemory();
1466
1467   public:
1468     static char ID;
1469     ObjCARCOpt() : FunctionPass(ID) {
1470       initializeObjCARCOptPass(*PassRegistry::getPassRegistry());
1471     }
1472   };
1473 }
1474
1475 char ObjCARCOpt::ID = 0;
1476 INITIALIZE_PASS_BEGIN(ObjCARCOpt,
1477                       "objc-arc", "ObjC ARC optimization", false, false)
1478 INITIALIZE_PASS_DEPENDENCY(ObjCARCAliasAnalysis)
1479 INITIALIZE_PASS_END(ObjCARCOpt,
1480                     "objc-arc", "ObjC ARC optimization", false, false)
1481
1482 Pass *llvm::createObjCARCOptPass() {
1483   return new ObjCARCOpt();
1484 }
1485
1486 void ObjCARCOpt::getAnalysisUsage(AnalysisUsage &AU) const {
1487   AU.addRequired<ObjCARCAliasAnalysis>();
1488   AU.addRequired<AliasAnalysis>();
1489   // ARC optimization doesn't currently split critical edges.
1490   AU.setPreservesCFG();
1491 }
1492
1493 Constant *ObjCARCOpt::getRetainRVCallee(Module *M) {
1494   if (!RetainRVCallee) {
1495     LLVMContext &C = M->getContext();
1496     Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
1497     std::vector<Type *> Params;
1498     Params.push_back(I8X);
1499     FunctionType *FTy =
1500       FunctionType::get(I8X, Params, /*isVarArg=*/false);
1501     AttrListPtr Attributes;
1502     Attributes.addAttr(~0u, Attribute::NoUnwind);
1503     RetainRVCallee =
1504       M->getOrInsertFunction("objc_retainAutoreleasedReturnValue", FTy,
1505                              Attributes);
1506   }
1507   return RetainRVCallee;
1508 }
1509
1510 Constant *ObjCARCOpt::getAutoreleaseRVCallee(Module *M) {
1511   if (!AutoreleaseRVCallee) {
1512     LLVMContext &C = M->getContext();
1513     Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
1514     std::vector<Type *> Params;
1515     Params.push_back(I8X);
1516     FunctionType *FTy =
1517       FunctionType::get(I8X, Params, /*isVarArg=*/false);
1518     AttrListPtr Attributes;
1519     Attributes.addAttr(~0u, Attribute::NoUnwind);
1520     AutoreleaseRVCallee =
1521       M->getOrInsertFunction("objc_autoreleaseReturnValue", FTy,
1522                              Attributes);
1523   }
1524   return AutoreleaseRVCallee;
1525 }
1526
1527 Constant *ObjCARCOpt::getReleaseCallee(Module *M) {
1528   if (!ReleaseCallee) {
1529     LLVMContext &C = M->getContext();
1530     std::vector<Type *> Params;
1531     Params.push_back(PointerType::getUnqual(Type::getInt8Ty(C)));
1532     AttrListPtr Attributes;
1533     Attributes.addAttr(~0u, Attribute::NoUnwind);
1534     ReleaseCallee =
1535       M->getOrInsertFunction(
1536         "objc_release",
1537         FunctionType::get(Type::getVoidTy(C), Params, /*isVarArg=*/false),
1538         Attributes);
1539   }
1540   return ReleaseCallee;
1541 }
1542
1543 Constant *ObjCARCOpt::getRetainCallee(Module *M) {
1544   if (!RetainCallee) {
1545     LLVMContext &C = M->getContext();
1546     std::vector<Type *> Params;
1547     Params.push_back(PointerType::getUnqual(Type::getInt8Ty(C)));
1548     AttrListPtr Attributes;
1549     Attributes.addAttr(~0u, Attribute::NoUnwind);
1550     RetainCallee =
1551       M->getOrInsertFunction(
1552         "objc_retain",
1553         FunctionType::get(Params[0], Params, /*isVarArg=*/false),
1554         Attributes);
1555   }
1556   return RetainCallee;
1557 }
1558
1559 Constant *ObjCARCOpt::getRetainBlockCallee(Module *M) {
1560   if (!RetainBlockCallee) {
1561     LLVMContext &C = M->getContext();
1562     std::vector<Type *> Params;
1563     Params.push_back(PointerType::getUnqual(Type::getInt8Ty(C)));
1564     AttrListPtr Attributes;
1565     Attributes.addAttr(~0u, Attribute::NoUnwind);
1566     RetainBlockCallee =
1567       M->getOrInsertFunction(
1568         "objc_retainBlock",
1569         FunctionType::get(Params[0], Params, /*isVarArg=*/false),
1570         Attributes);
1571   }
1572   return RetainBlockCallee;
1573 }
1574
1575 Constant *ObjCARCOpt::getAutoreleaseCallee(Module *M) {
1576   if (!AutoreleaseCallee) {
1577     LLVMContext &C = M->getContext();
1578     std::vector<Type *> Params;
1579     Params.push_back(PointerType::getUnqual(Type::getInt8Ty(C)));
1580     AttrListPtr Attributes;
1581     Attributes.addAttr(~0u, Attribute::NoUnwind);
1582     AutoreleaseCallee =
1583       M->getOrInsertFunction(
1584         "objc_autorelease",
1585         FunctionType::get(Params[0], Params, /*isVarArg=*/false),
1586         Attributes);
1587   }
1588   return AutoreleaseCallee;
1589 }
1590
1591 /// CanAlterRefCount - Test whether the given instruction can result in a
1592 /// reference count modification (positive or negative) for the pointer's
1593 /// object.
1594 static bool
1595 CanAlterRefCount(const Instruction *Inst, const Value *Ptr,
1596                  ProvenanceAnalysis &PA, InstructionClass Class) {
1597   switch (Class) {
1598   case IC_Autorelease:
1599   case IC_AutoreleaseRV:
1600   case IC_User:
1601     // These operations never directly modify a reference count.
1602     return false;
1603   default: break;
1604   }
1605
1606   ImmutableCallSite CS = static_cast<const Value *>(Inst);
1607   assert(CS && "Only calls can alter reference counts!");
1608
1609   // See if AliasAnalysis can help us with the call.
1610   AliasAnalysis::ModRefBehavior MRB = PA.getAA()->getModRefBehavior(CS);
1611   if (AliasAnalysis::onlyReadsMemory(MRB))
1612     return false;
1613   if (AliasAnalysis::onlyAccessesArgPointees(MRB)) {
1614     for (ImmutableCallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end();
1615          I != E; ++I) {
1616       const Value *Op = *I;
1617       if (IsPotentialUse(Op) && PA.related(Ptr, Op))
1618         return true;
1619     }
1620     return false;
1621   }
1622
1623   // Assume the worst.
1624   return true;
1625 }
1626
1627 /// CanUse - Test whether the given instruction can "use" the given pointer's
1628 /// object in a way that requires the reference count to be positive.
1629 static bool
1630 CanUse(const Instruction *Inst, const Value *Ptr, ProvenanceAnalysis &PA,
1631        InstructionClass Class) {
1632   // IC_Call operations (as opposed to IC_CallOrUser) never "use" objc pointers.
1633   if (Class == IC_Call)
1634     return false;
1635
1636   // Consider various instructions which may have pointer arguments which are
1637   // not "uses".
1638   if (const ICmpInst *ICI = dyn_cast<ICmpInst>(Inst)) {
1639     // Comparing a pointer with null, or any other constant, isn't really a use,
1640     // because we don't care what the pointer points to, or about the values
1641     // of any other dynamic reference-counted pointers.
1642     if (!IsPotentialUse(ICI->getOperand(1)))
1643       return false;
1644   } else if (ImmutableCallSite CS = static_cast<const Value *>(Inst)) {
1645     // For calls, just check the arguments (and not the callee operand).
1646     for (ImmutableCallSite::arg_iterator OI = CS.arg_begin(),
1647          OE = CS.arg_end(); OI != OE; ++OI) {
1648       const Value *Op = *OI;
1649       if (IsPotentialUse(Op) && PA.related(Ptr, Op))
1650         return true;
1651     }
1652     return false;
1653   } else if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
1654     // Special-case stores, because we don't care about the stored value, just
1655     // the store address.
1656     const Value *Op = GetUnderlyingObjCPtr(SI->getPointerOperand());
1657     // If we can't tell what the underlying object was, assume there is a
1658     // dependence.
1659     return IsPotentialUse(Op) && PA.related(Op, Ptr);
1660   }
1661
1662   // Check each operand for a match.
1663   for (User::const_op_iterator OI = Inst->op_begin(), OE = Inst->op_end();
1664        OI != OE; ++OI) {
1665     const Value *Op = *OI;
1666     if (IsPotentialUse(Op) && PA.related(Ptr, Op))
1667       return true;
1668   }
1669   return false;
1670 }
1671
1672 /// CanInterruptRV - Test whether the given instruction can autorelease
1673 /// any pointer or cause an autoreleasepool pop.
1674 static bool
1675 CanInterruptRV(InstructionClass Class) {
1676   switch (Class) {
1677   case IC_AutoreleasepoolPop:
1678   case IC_CallOrUser:
1679   case IC_Call:
1680   case IC_Autorelease:
1681   case IC_AutoreleaseRV:
1682   case IC_FusedRetainAutorelease:
1683   case IC_FusedRetainAutoreleaseRV:
1684     return true;
1685   default:
1686     return false;
1687   }
1688 }
1689
1690 namespace {
1691   /// DependenceKind - There are several kinds of dependence-like concepts in
1692   /// use here.
1693   enum DependenceKind {
1694     NeedsPositiveRetainCount,
1695     CanChangeRetainCount,
1696     RetainAutoreleaseDep,       ///< Blocks objc_retainAutorelease.
1697     RetainAutoreleaseRVDep,     ///< Blocks objc_retainAutoreleaseReturnValue.
1698     RetainRVDep                 ///< Blocks objc_retainAutoreleasedReturnValue.
1699   };
1700 }
1701
1702 /// Depends - Test if there can be dependencies on Inst through Arg. This
1703 /// function only tests dependencies relevant for removing pairs of calls.
1704 static bool
1705 Depends(DependenceKind Flavor, Instruction *Inst, const Value *Arg,
1706         ProvenanceAnalysis &PA) {
1707   // If we've reached the definition of Arg, stop.
1708   if (Inst == Arg)
1709     return true;
1710
1711   switch (Flavor) {
1712   case NeedsPositiveRetainCount: {
1713     InstructionClass Class = GetInstructionClass(Inst);
1714     switch (Class) {
1715     case IC_AutoreleasepoolPop:
1716     case IC_AutoreleasepoolPush:
1717     case IC_None:
1718       return false;
1719     default:
1720       return CanUse(Inst, Arg, PA, Class);
1721     }
1722   }
1723
1724   case CanChangeRetainCount: {
1725     InstructionClass Class = GetInstructionClass(Inst);
1726     switch (Class) {
1727     case IC_AutoreleasepoolPop:
1728       // Conservatively assume this can decrement any count.
1729       return true;
1730     case IC_AutoreleasepoolPush:
1731     case IC_None:
1732       return false;
1733     default:
1734       return CanAlterRefCount(Inst, Arg, PA, Class);
1735     }
1736   }
1737
1738   case RetainAutoreleaseDep:
1739     switch (GetBasicInstructionClass(Inst)) {
1740     case IC_AutoreleasepoolPop:
1741       // Don't merge an objc_autorelease with an objc_retain inside a different
1742       // autoreleasepool scope.
1743       return true;
1744     case IC_Retain:
1745     case IC_RetainRV:
1746       // Check for a retain of the same pointer for merging.
1747       return GetObjCArg(Inst) == Arg;
1748     default:
1749       // Nothing else matters for objc_retainAutorelease formation.
1750       return false;
1751     }
1752     break;
1753
1754   case RetainAutoreleaseRVDep: {
1755     InstructionClass Class = GetBasicInstructionClass(Inst);
1756     switch (Class) {
1757     case IC_Retain:
1758     case IC_RetainRV:
1759       // Check for a retain of the same pointer for merging.
1760       return GetObjCArg(Inst) == Arg;
1761     default:
1762       // Anything that can autorelease interrupts
1763       // retainAutoreleaseReturnValue formation.
1764       return CanInterruptRV(Class);
1765     }
1766     break;
1767   }
1768
1769   case RetainRVDep:
1770     return CanInterruptRV(GetBasicInstructionClass(Inst));
1771   }
1772
1773   llvm_unreachable("Invalid dependence flavor");
1774   return true;
1775 }
1776
1777 /// FindDependencies - Walk up the CFG from StartPos (which is in StartBB) and
1778 /// find local and non-local dependencies on Arg.
1779 /// TODO: Cache results?
1780 static void
1781 FindDependencies(DependenceKind Flavor,
1782                  const Value *Arg,
1783                  BasicBlock *StartBB, Instruction *StartInst,
1784                  SmallPtrSet<Instruction *, 4> &DependingInstructions,
1785                  SmallPtrSet<const BasicBlock *, 4> &Visited,
1786                  ProvenanceAnalysis &PA) {
1787   BasicBlock::iterator StartPos = StartInst;
1788
1789   SmallVector<std::pair<BasicBlock *, BasicBlock::iterator>, 4> Worklist;
1790   Worklist.push_back(std::make_pair(StartBB, StartPos));
1791   do {
1792     std::pair<BasicBlock *, BasicBlock::iterator> Pair =
1793       Worklist.pop_back_val();
1794     BasicBlock *LocalStartBB = Pair.first;
1795     BasicBlock::iterator LocalStartPos = Pair.second;
1796     BasicBlock::iterator StartBBBegin = LocalStartBB->begin();
1797     for (;;) {
1798       if (LocalStartPos == StartBBBegin) {
1799         pred_iterator PI(LocalStartBB), PE(LocalStartBB, false);
1800         if (PI == PE)
1801           // If we've reached the function entry, produce a null dependence.
1802           DependingInstructions.insert(0);
1803         else
1804           // Add the predecessors to the worklist.
1805           do {
1806             BasicBlock *PredBB = *PI;
1807             if (Visited.insert(PredBB))
1808               Worklist.push_back(std::make_pair(PredBB, PredBB->end()));
1809           } while (++PI != PE);
1810         break;
1811       }
1812
1813       Instruction *Inst = --LocalStartPos;
1814       if (Depends(Flavor, Inst, Arg, PA)) {
1815         DependingInstructions.insert(Inst);
1816         break;
1817       }
1818     }
1819   } while (!Worklist.empty());
1820
1821   // Determine whether the original StartBB post-dominates all of the blocks we
1822   // visited. If not, insert a sentinal indicating that most optimizations are
1823   // not safe.
1824   for (SmallPtrSet<const BasicBlock *, 4>::const_iterator I = Visited.begin(),
1825        E = Visited.end(); I != E; ++I) {
1826     const BasicBlock *BB = *I;
1827     if (BB == StartBB)
1828       continue;
1829     const TerminatorInst *TI = cast<TerminatorInst>(&BB->back());
1830     for (succ_const_iterator SI(TI), SE(TI, false); SI != SE; ++SI) {
1831       const BasicBlock *Succ = *SI;
1832       if (Succ != StartBB && !Visited.count(Succ)) {
1833         DependingInstructions.insert(reinterpret_cast<Instruction *>(-1));
1834         return;
1835       }
1836     }
1837   }
1838 }
1839
1840 static bool isNullOrUndef(const Value *V) {
1841   return isa<ConstantPointerNull>(V) || isa<UndefValue>(V);
1842 }
1843
1844 static bool isNoopInstruction(const Instruction *I) {
1845   return isa<BitCastInst>(I) ||
1846          (isa<GetElementPtrInst>(I) &&
1847           cast<GetElementPtrInst>(I)->hasAllZeroIndices());
1848 }
1849
1850 /// OptimizeRetainCall - Turn objc_retain into
1851 /// objc_retainAutoreleasedReturnValue if the operand is a return value.
1852 void
1853 ObjCARCOpt::OptimizeRetainCall(Function &F, Instruction *Retain) {
1854   CallSite CS(GetObjCArg(Retain));
1855   Instruction *Call = CS.getInstruction();
1856   if (!Call) return;
1857   if (Call->getParent() != Retain->getParent()) return;
1858
1859   // Check that the call is next to the retain.
1860   BasicBlock::iterator I = Call;
1861   ++I;
1862   while (isNoopInstruction(I)) ++I;
1863   if (&*I != Retain)
1864     return;
1865
1866   // Turn it to an objc_retainAutoreleasedReturnValue..
1867   Changed = true;
1868   ++NumPeeps;
1869   cast<CallInst>(Retain)->setCalledFunction(getRetainRVCallee(F.getParent()));
1870 }
1871
1872 /// OptimizeRetainRVCall - Turn objc_retainAutoreleasedReturnValue into
1873 /// objc_retain if the operand is not a return value.  Or, if it can be
1874 /// paired with an objc_autoreleaseReturnValue, delete the pair and
1875 /// return true.
1876 bool
1877 ObjCARCOpt::OptimizeRetainRVCall(Function &F, Instruction *RetainRV) {
1878   // Check for the argument being from an immediately preceding call.
1879   Value *Arg = GetObjCArg(RetainRV);
1880   CallSite CS(Arg);
1881   if (Instruction *Call = CS.getInstruction())
1882     if (Call->getParent() == RetainRV->getParent()) {
1883       BasicBlock::iterator I = Call;
1884       ++I;
1885       while (isNoopInstruction(I)) ++I;
1886       if (&*I == RetainRV)
1887         return false;
1888     }
1889
1890   // Check for being preceded by an objc_autoreleaseReturnValue on the same
1891   // pointer. In this case, we can delete the pair.
1892   BasicBlock::iterator I = RetainRV, Begin = RetainRV->getParent()->begin();
1893   if (I != Begin) {
1894     do --I; while (I != Begin && isNoopInstruction(I));
1895     if (GetBasicInstructionClass(I) == IC_AutoreleaseRV &&
1896         GetObjCArg(I) == Arg) {
1897       Changed = true;
1898       ++NumPeeps;
1899       EraseInstruction(I);
1900       EraseInstruction(RetainRV);
1901       return true;
1902     }
1903   }
1904
1905   // Turn it to a plain objc_retain.
1906   Changed = true;
1907   ++NumPeeps;
1908   cast<CallInst>(RetainRV)->setCalledFunction(getRetainCallee(F.getParent()));
1909   return false;
1910 }
1911
1912 /// OptimizeAutoreleaseRVCall - Turn objc_autoreleaseReturnValue into
1913 /// objc_autorelease if the result is not used as a return value.
1914 void
1915 ObjCARCOpt::OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV) {
1916   // Check for a return of the pointer value.
1917   const Value *Ptr = GetObjCArg(AutoreleaseRV);
1918   for (Value::const_use_iterator UI = Ptr->use_begin(), UE = Ptr->use_end();
1919        UI != UE; ++UI) {
1920     const User *I = *UI;
1921     if (isa<ReturnInst>(I) || GetBasicInstructionClass(I) == IC_RetainRV)
1922       return;
1923   }
1924
1925   Changed = true;
1926   ++NumPeeps;
1927   cast<CallInst>(AutoreleaseRV)->
1928     setCalledFunction(getAutoreleaseCallee(F.getParent()));
1929 }
1930
1931 /// OptimizeIndividualCalls - Visit each call, one at a time, and make
1932 /// simplifications without doing any additional analysis.
1933 void ObjCARCOpt::OptimizeIndividualCalls(Function &F) {
1934   // Reset all the flags in preparation for recomputing them.
1935   UsedInThisFunction = 0;
1936
1937   // Visit all objc_* calls in F.
1938   for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
1939     Instruction *Inst = &*I++;
1940     InstructionClass Class = GetBasicInstructionClass(Inst);
1941
1942     switch (Class) {
1943     default: break;
1944
1945     // Delete no-op casts. These function calls have special semantics, but
1946     // the semantics are entirely implemented via lowering in the front-end,
1947     // so by the time they reach the optimizer, they are just no-op calls
1948     // which return their argument.
1949     //
1950     // There are gray areas here, as the ability to cast reference-counted
1951     // pointers to raw void* and back allows code to break ARC assumptions,
1952     // however these are currently considered to be unimportant.
1953     case IC_NoopCast:
1954       Changed = true;
1955       ++NumNoops;
1956       EraseInstruction(Inst);
1957       continue;
1958
1959     // If the pointer-to-weak-pointer is null, it's undefined behavior.
1960     case IC_StoreWeak:
1961     case IC_LoadWeak:
1962     case IC_LoadWeakRetained:
1963     case IC_InitWeak:
1964     case IC_DestroyWeak: {
1965       CallInst *CI = cast<CallInst>(Inst);
1966       if (isNullOrUndef(CI->getArgOperand(0))) {
1967         Type *Ty = CI->getArgOperand(0)->getType();
1968         new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()),
1969                       Constant::getNullValue(Ty),
1970                       CI);
1971         CI->replaceAllUsesWith(UndefValue::get(CI->getType()));
1972         CI->eraseFromParent();
1973         continue;
1974       }
1975       break;
1976     }
1977     case IC_CopyWeak:
1978     case IC_MoveWeak: {
1979       CallInst *CI = cast<CallInst>(Inst);
1980       if (isNullOrUndef(CI->getArgOperand(0)) ||
1981           isNullOrUndef(CI->getArgOperand(1))) {
1982         Type *Ty = CI->getArgOperand(0)->getType();
1983         new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()),
1984                       Constant::getNullValue(Ty),
1985                       CI);
1986         CI->replaceAllUsesWith(UndefValue::get(CI->getType()));
1987         CI->eraseFromParent();
1988         continue;
1989       }
1990       break;
1991     }
1992     case IC_Retain:
1993       OptimizeRetainCall(F, Inst);
1994       break;
1995     case IC_RetainRV:
1996       if (OptimizeRetainRVCall(F, Inst))
1997         continue;
1998       break;
1999     case IC_AutoreleaseRV:
2000       OptimizeAutoreleaseRVCall(F, Inst);
2001       break;
2002     }
2003
2004     // objc_autorelease(x) -> objc_release(x) if x is otherwise unused.
2005     if (IsAutorelease(Class) && Inst->use_empty()) {
2006       CallInst *Call = cast<CallInst>(Inst);
2007       const Value *Arg = Call->getArgOperand(0);
2008       Arg = FindSingleUseIdentifiedObject(Arg);
2009       if (Arg) {
2010         Changed = true;
2011         ++NumAutoreleases;
2012
2013         // Create the declaration lazily.
2014         LLVMContext &C = Inst->getContext();
2015         CallInst *NewCall =
2016           CallInst::Create(getReleaseCallee(F.getParent()),
2017                            Call->getArgOperand(0), "", Call);
2018         NewCall->setMetadata(ImpreciseReleaseMDKind,
2019                              MDNode::get(C, ArrayRef<Value *>()));
2020         EraseInstruction(Call);
2021         Inst = NewCall;
2022         Class = IC_Release;
2023       }
2024     }
2025
2026     // For functions which can never be passed stack arguments, add
2027     // a tail keyword.
2028     if (IsAlwaysTail(Class)) {
2029       Changed = true;
2030       cast<CallInst>(Inst)->setTailCall();
2031     }
2032
2033     // Set nounwind as needed.
2034     if (IsNoThrow(Class)) {
2035       Changed = true;
2036       cast<CallInst>(Inst)->setDoesNotThrow();
2037     }
2038
2039     if (!IsNoopOnNull(Class)) {
2040       UsedInThisFunction |= 1 << Class;
2041       continue;
2042     }
2043
2044     const Value *Arg = GetObjCArg(Inst);
2045
2046     // ARC calls with null are no-ops. Delete them.
2047     if (isNullOrUndef(Arg)) {
2048       Changed = true;
2049       ++NumNoops;
2050       EraseInstruction(Inst);
2051       continue;
2052     }
2053
2054     // Keep track of which of retain, release, autorelease, and retain_block
2055     // are actually present in this function.
2056     UsedInThisFunction |= 1 << Class;
2057
2058     // If Arg is a PHI, and one or more incoming values to the
2059     // PHI are null, and the call is control-equivalent to the PHI, and there
2060     // are no relevant side effects between the PHI and the call, the call
2061     // could be pushed up to just those paths with non-null incoming values.
2062     // For now, don't bother splitting critical edges for this.
2063     SmallVector<std::pair<Instruction *, const Value *>, 4> Worklist;
2064     Worklist.push_back(std::make_pair(Inst, Arg));
2065     do {
2066       std::pair<Instruction *, const Value *> Pair = Worklist.pop_back_val();
2067       Inst = Pair.first;
2068       Arg = Pair.second;
2069
2070       const PHINode *PN = dyn_cast<PHINode>(Arg);
2071       if (!PN) continue;
2072
2073       // Determine if the PHI has any null operands, or any incoming
2074       // critical edges.
2075       bool HasNull = false;
2076       bool HasCriticalEdges = false;
2077       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
2078         Value *Incoming =
2079           StripPointerCastsAndObjCCalls(PN->getIncomingValue(i));
2080         if (isNullOrUndef(Incoming))
2081           HasNull = true;
2082         else if (cast<TerminatorInst>(PN->getIncomingBlock(i)->back())
2083                    .getNumSuccessors() != 1) {
2084           HasCriticalEdges = true;
2085           break;
2086         }
2087       }
2088       // If we have null operands and no critical edges, optimize.
2089       if (!HasCriticalEdges && HasNull) {
2090         SmallPtrSet<Instruction *, 4> DependingInstructions;
2091         SmallPtrSet<const BasicBlock *, 4> Visited;
2092
2093         // Check that there is nothing that cares about the reference
2094         // count between the call and the phi.
2095         FindDependencies(NeedsPositiveRetainCount, Arg,
2096                          Inst->getParent(), Inst,
2097                          DependingInstructions, Visited, PA);
2098         if (DependingInstructions.size() == 1 &&
2099             *DependingInstructions.begin() == PN) {
2100           Changed = true;
2101           ++NumPartialNoops;
2102           // Clone the call into each predecessor that has a non-null value.
2103           CallInst *CInst = cast<CallInst>(Inst);
2104           Type *ParamTy = CInst->getArgOperand(0)->getType();
2105           for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
2106             Value *Incoming =
2107               StripPointerCastsAndObjCCalls(PN->getIncomingValue(i));
2108             if (!isNullOrUndef(Incoming)) {
2109               CallInst *Clone = cast<CallInst>(CInst->clone());
2110               Value *Op = PN->getIncomingValue(i);
2111               Instruction *InsertPos = &PN->getIncomingBlock(i)->back();
2112               if (Op->getType() != ParamTy)
2113                 Op = new BitCastInst(Op, ParamTy, "", InsertPos);
2114               Clone->setArgOperand(0, Op);
2115               Clone->insertBefore(InsertPos);
2116               Worklist.push_back(std::make_pair(Clone, Incoming));
2117             }
2118           }
2119           // Erase the original call.
2120           EraseInstruction(CInst);
2121           continue;
2122         }
2123       }
2124     } while (!Worklist.empty());
2125   }
2126 }
2127
2128 /// CheckForCFGHazards - Check for critical edges, loop boundaries, irreducible
2129 /// control flow, or other CFG structures where moving code across the edge
2130 /// would result in it being executed more.
2131 void
2132 ObjCARCOpt::CheckForCFGHazards(const BasicBlock *BB,
2133                                DenseMap<const BasicBlock *, BBState> &BBStates,
2134                                BBState &MyStates) const {
2135   // If any top-down local-use or possible-dec has a succ which is earlier in
2136   // the sequence, forget it.
2137   for (BBState::ptr_const_iterator I = MyStates.top_down_ptr_begin(),
2138        E = MyStates.top_down_ptr_end(); I != E; ++I)
2139     switch (I->second.GetSeq()) {
2140     default: break;
2141     case S_Use: {
2142       const Value *Arg = I->first;
2143       const TerminatorInst *TI = cast<TerminatorInst>(&BB->back());
2144       bool SomeSuccHasSame = false;
2145       bool AllSuccsHaveSame = true;
2146       for (succ_const_iterator SI(TI), SE(TI, false); SI != SE; ++SI)
2147         switch (BBStates[*SI].getPtrBottomUpState(Arg).GetSeq()) {
2148         case S_None:
2149         case S_CanRelease:
2150           MyStates.getPtrTopDownState(Arg).ClearSequenceProgress();
2151           SomeSuccHasSame = false;
2152           break;
2153         case S_Use:
2154           SomeSuccHasSame = true;
2155           break;
2156         case S_Stop:
2157         case S_Release:
2158         case S_MovableRelease:
2159           AllSuccsHaveSame = false;
2160           break;
2161         case S_Retain:
2162           llvm_unreachable("bottom-up pointer in retain state!");
2163         }
2164       // If the state at the other end of any of the successor edges
2165       // matches the current state, require all edges to match. This
2166       // guards against loops in the middle of a sequence.
2167       if (SomeSuccHasSame && !AllSuccsHaveSame)
2168         MyStates.getPtrTopDownState(Arg).ClearSequenceProgress();
2169     }
2170     case S_CanRelease: {
2171       const Value *Arg = I->first;
2172       const TerminatorInst *TI = cast<TerminatorInst>(&BB->back());
2173       bool SomeSuccHasSame = false;
2174       bool AllSuccsHaveSame = true;
2175       for (succ_const_iterator SI(TI), SE(TI, false); SI != SE; ++SI)
2176         switch (BBStates[*SI].getPtrBottomUpState(Arg).GetSeq()) {
2177         case S_None:
2178           MyStates.getPtrTopDownState(Arg).ClearSequenceProgress();
2179           SomeSuccHasSame = false;
2180           break;
2181         case S_CanRelease:
2182           SomeSuccHasSame = true;
2183           break;
2184         case S_Stop:
2185         case S_Release:
2186         case S_MovableRelease:
2187         case S_Use:
2188           AllSuccsHaveSame = false;
2189           break;
2190         case S_Retain:
2191           llvm_unreachable("bottom-up pointer in retain state!");
2192         }
2193       // If the state at the other end of any of the successor edges
2194       // matches the current state, require all edges to match. This
2195       // guards against loops in the middle of a sequence.
2196       if (SomeSuccHasSame && !AllSuccsHaveSame)
2197         MyStates.getPtrTopDownState(Arg).ClearSequenceProgress();
2198     }
2199     }
2200 }
2201
2202 bool
2203 ObjCARCOpt::VisitBottomUp(BasicBlock *BB,
2204                           DenseMap<const BasicBlock *, BBState> &BBStates,
2205                           MapVector<Value *, RRInfo> &Retains) {
2206   bool NestingDetected = false;
2207   BBState &MyStates = BBStates[BB];
2208
2209   // Merge the states from each successor to compute the initial state
2210   // for the current block.
2211   const TerminatorInst *TI = cast<TerminatorInst>(&BB->back());
2212   succ_const_iterator SI(TI), SE(TI, false);
2213   if (SI == SE)
2214     MyStates.SetAsExit();
2215   else
2216     do {
2217       const BasicBlock *Succ = *SI++;
2218       if (Succ == BB)
2219         continue;
2220       DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Succ);
2221       if (I == BBStates.end())
2222         continue;
2223       MyStates.InitFromSucc(I->second);
2224       while (SI != SE) {
2225         Succ = *SI++;
2226         if (Succ != BB) {
2227           I = BBStates.find(Succ);
2228           if (I != BBStates.end())
2229             MyStates.MergeSucc(I->second);
2230         }
2231       }
2232       break;
2233     } while (SI != SE);
2234
2235   // Visit all the instructions, bottom-up.
2236   for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; --I) {
2237     Instruction *Inst = llvm::prior(I);
2238     InstructionClass Class = GetInstructionClass(Inst);
2239     const Value *Arg = 0;
2240
2241     switch (Class) {
2242     case IC_Release: {
2243       Arg = GetObjCArg(Inst);
2244
2245       PtrState &S = MyStates.getPtrBottomUpState(Arg);
2246
2247       // If we see two releases in a row on the same pointer. If so, make
2248       // a note, and we'll cicle back to revisit it after we've
2249       // hopefully eliminated the second release, which may allow us to
2250       // eliminate the first release too.
2251       // Theoretically we could implement removal of nested retain+release
2252       // pairs by making PtrState hold a stack of states, but this is
2253       // simple and avoids adding overhead for the non-nested case.
2254       if (S.GetSeq() == S_Release || S.GetSeq() == S_MovableRelease)
2255         NestingDetected = true;
2256
2257       S.SetSeqToRelease(Inst->getMetadata(ImpreciseReleaseMDKind));
2258       S.RRI.clear();
2259       S.RRI.KnownIncremented = S.IsKnownIncremented();
2260       S.RRI.IsTailCallRelease = cast<CallInst>(Inst)->isTailCall();
2261       S.RRI.Calls.insert(Inst);
2262
2263       S.IncrementRefCount();
2264       break;
2265     }
2266     case IC_RetainBlock:
2267     case IC_Retain:
2268     case IC_RetainRV: {
2269       Arg = GetObjCArg(Inst);
2270
2271       PtrState &S = MyStates.getPtrBottomUpState(Arg);
2272       S.DecrementRefCount();
2273
2274       switch (S.GetSeq()) {
2275       case S_Stop:
2276       case S_Release:
2277       case S_MovableRelease:
2278       case S_Use:
2279         S.RRI.ReverseInsertPts.clear();
2280         // FALL THROUGH
2281       case S_CanRelease:
2282         // Don't do retain+release tracking for IC_RetainRV, because it's
2283         // better to let it remain as the first instruction after a call.
2284         if (Class != IC_RetainRV) {
2285           S.RRI.IsRetainBlock = Class == IC_RetainBlock;
2286           Retains[Inst] = S.RRI;
2287         }
2288         S.ClearSequenceProgress();
2289         break;
2290       case S_None:
2291         break;
2292       case S_Retain:
2293         llvm_unreachable("bottom-up pointer in retain state!");
2294       }
2295       break;
2296     }
2297     case IC_AutoreleasepoolPop:
2298       // Conservatively, clear MyStates for all known pointers.
2299       MyStates.clearBottomUpPointers();
2300       continue;
2301     case IC_AutoreleasepoolPush:
2302     case IC_None:
2303       // These are irrelevant.
2304       continue;
2305     default:
2306       break;
2307     }
2308
2309     // Consider any other possible effects of this instruction on each
2310     // pointer being tracked.
2311     for (BBState::ptr_iterator MI = MyStates.bottom_up_ptr_begin(),
2312          ME = MyStates.bottom_up_ptr_end(); MI != ME; ++MI) {
2313       const Value *Ptr = MI->first;
2314       if (Ptr == Arg)
2315         continue; // Handled above.
2316       PtrState &S = MI->second;
2317       Sequence Seq = S.GetSeq();
2318
2319       // Check for possible retains and releases.
2320       if (CanAlterRefCount(Inst, Ptr, PA, Class)) {
2321         // Check for a retain (we're going bottom-up here).
2322         S.DecrementRefCount();
2323
2324         // Check for a release.
2325         if (!IsRetain(Class) && Class != IC_RetainBlock)
2326           switch (Seq) {
2327           case S_Use:
2328             S.SetSeq(S_CanRelease);
2329             continue;
2330           case S_CanRelease:
2331           case S_Release:
2332           case S_MovableRelease:
2333           case S_Stop:
2334           case S_None:
2335             break;
2336           case S_Retain:
2337             llvm_unreachable("bottom-up pointer in retain state!");
2338           }
2339       }
2340
2341       // Check for possible direct uses.
2342       switch (Seq) {
2343       case S_Release:
2344       case S_MovableRelease:
2345         if (CanUse(Inst, Ptr, PA, Class)) {
2346           S.RRI.ReverseInsertPts.clear();
2347           S.RRI.ReverseInsertPts.insert(Inst);
2348           S.SetSeq(S_Use);
2349         } else if (Seq == S_Release &&
2350                    (Class == IC_User || Class == IC_CallOrUser)) {
2351           // Non-movable releases depend on any possible objc pointer use.
2352           S.SetSeq(S_Stop);
2353           S.RRI.ReverseInsertPts.clear();
2354           S.RRI.ReverseInsertPts.insert(Inst);
2355         }
2356         break;
2357       case S_Stop:
2358         if (CanUse(Inst, Ptr, PA, Class))
2359           S.SetSeq(S_Use);
2360         break;
2361       case S_CanRelease:
2362       case S_Use:
2363       case S_None:
2364         break;
2365       case S_Retain:
2366         llvm_unreachable("bottom-up pointer in retain state!");
2367       }
2368     }
2369   }
2370
2371   return NestingDetected;
2372 }
2373
2374 bool
2375 ObjCARCOpt::VisitTopDown(BasicBlock *BB,
2376                          DenseMap<const BasicBlock *, BBState> &BBStates,
2377                          DenseMap<Value *, RRInfo> &Releases) {
2378   bool NestingDetected = false;
2379   BBState &MyStates = BBStates[BB];
2380
2381   // Merge the states from each predecessor to compute the initial state
2382   // for the current block.
2383   const_pred_iterator PI(BB), PE(BB, false);
2384   if (PI == PE)
2385     MyStates.SetAsEntry();
2386   else
2387     do {
2388       const BasicBlock *Pred = *PI++;
2389       if (Pred == BB)
2390         continue;
2391       DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Pred);
2392       if (I == BBStates.end())
2393         continue;
2394       MyStates.InitFromPred(I->second);
2395       while (PI != PE) {
2396         Pred = *PI++;
2397         if (Pred != BB) {
2398           I = BBStates.find(Pred);
2399           if (I != BBStates.end())
2400             MyStates.MergePred(I->second);
2401         }
2402       }
2403       break;
2404     } while (PI != PE);
2405
2406   // Visit all the instructions, top-down.
2407   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
2408     Instruction *Inst = I;
2409     InstructionClass Class = GetInstructionClass(Inst);
2410     const Value *Arg = 0;
2411
2412     switch (Class) {
2413     case IC_RetainBlock:
2414     case IC_Retain:
2415     case IC_RetainRV: {
2416       Arg = GetObjCArg(Inst);
2417
2418       PtrState &S = MyStates.getPtrTopDownState(Arg);
2419
2420       // Don't do retain+release tracking for IC_RetainRV, because it's
2421       // better to let it remain as the first instruction after a call.
2422       if (Class != IC_RetainRV) {
2423         // If we see two retains in a row on the same pointer. If so, make
2424         // a note, and we'll cicle back to revisit it after we've
2425         // hopefully eliminated the second retain, which may allow us to
2426         // eliminate the first retain too.
2427         // Theoretically we could implement removal of nested retain+release
2428         // pairs by making PtrState hold a stack of states, but this is
2429         // simple and avoids adding overhead for the non-nested case.
2430         if (S.GetSeq() == S_Retain)
2431           NestingDetected = true;
2432
2433         S.SetSeq(S_Retain);
2434         S.RRI.clear();
2435         S.RRI.IsRetainBlock = Class == IC_RetainBlock;
2436         S.RRI.KnownIncremented = S.IsKnownIncremented();
2437         S.RRI.Calls.insert(Inst);
2438       }
2439
2440       S.IncrementRefCount();
2441       break;
2442     }
2443     case IC_Release: {
2444       Arg = GetObjCArg(Inst);
2445
2446       PtrState &S = MyStates.getPtrTopDownState(Arg);
2447       S.DecrementRefCount();
2448
2449       switch (S.GetSeq()) {
2450       case S_Retain:
2451       case S_CanRelease:
2452         S.RRI.ReverseInsertPts.clear();
2453         // FALL THROUGH
2454       case S_Use:
2455         S.RRI.ReleaseMetadata = Inst->getMetadata(ImpreciseReleaseMDKind);
2456         S.RRI.IsTailCallRelease = cast<CallInst>(Inst)->isTailCall();
2457         Releases[Inst] = S.RRI;
2458         S.ClearSequenceProgress();
2459         break;
2460       case S_None:
2461         break;
2462       case S_Stop:
2463       case S_Release:
2464       case S_MovableRelease:
2465         llvm_unreachable("top-down pointer in release state!");
2466       }
2467       break;
2468     }
2469     case IC_AutoreleasepoolPop:
2470       // Conservatively, clear MyStates for all known pointers.
2471       MyStates.clearTopDownPointers();
2472       continue;
2473     case IC_AutoreleasepoolPush:
2474     case IC_None:
2475       // These are irrelevant.
2476       continue;
2477     default:
2478       break;
2479     }
2480
2481     // Consider any other possible effects of this instruction on each
2482     // pointer being tracked.
2483     for (BBState::ptr_iterator MI = MyStates.top_down_ptr_begin(),
2484          ME = MyStates.top_down_ptr_end(); MI != ME; ++MI) {
2485       const Value *Ptr = MI->first;
2486       if (Ptr == Arg)
2487         continue; // Handled above.
2488       PtrState &S = MI->second;
2489       Sequence Seq = S.GetSeq();
2490
2491       // Check for possible releases.
2492       if (!IsRetain(Class) && Class != IC_RetainBlock &&
2493           CanAlterRefCount(Inst, Ptr, PA, Class)) {
2494         // Check for a release.
2495         S.DecrementRefCount();
2496
2497         // Check for a release.
2498         switch (Seq) {
2499         case S_Retain:
2500           S.SetSeq(S_CanRelease);
2501           S.RRI.ReverseInsertPts.clear();
2502           S.RRI.ReverseInsertPts.insert(Inst);
2503
2504           // One call can't cause a transition from S_Retain to S_CanRelease
2505           // and S_CanRelease to S_Use. If we've made the first transition,
2506           // we're done.
2507           continue;
2508         case S_Use:
2509         case S_CanRelease:
2510         case S_None:
2511           break;
2512         case S_Stop:
2513         case S_Release:
2514         case S_MovableRelease:
2515           llvm_unreachable("top-down pointer in release state!");
2516         }
2517       }
2518
2519       // Check for possible direct uses.
2520       switch (Seq) {
2521       case S_CanRelease:
2522         if (CanUse(Inst, Ptr, PA, Class))
2523           S.SetSeq(S_Use);
2524         break;
2525       case S_Use:
2526       case S_Retain:
2527       case S_None:
2528         break;
2529       case S_Stop:
2530       case S_Release:
2531       case S_MovableRelease:
2532         llvm_unreachable("top-down pointer in release state!");
2533       }
2534     }
2535   }
2536
2537   CheckForCFGHazards(BB, BBStates, MyStates);
2538   return NestingDetected;
2539 }
2540
2541 // Visit - Visit the function both top-down and bottom-up.
2542 bool
2543 ObjCARCOpt::Visit(Function &F,
2544                   DenseMap<const BasicBlock *, BBState> &BBStates,
2545                   MapVector<Value *, RRInfo> &Retains,
2546                   DenseMap<Value *, RRInfo> &Releases) {
2547   // Use reverse-postorder on the reverse CFG for bottom-up, because we
2548   // magically know that loops will be well behaved, i.e. they won't repeatedly
2549   // call retain on a single pointer without doing a release. We can't use
2550   // ReversePostOrderTraversal here because we want to walk up from each
2551   // function exit point.
2552   SmallPtrSet<BasicBlock *, 16> Visited;
2553   SmallVector<std::pair<BasicBlock *, pred_iterator>, 16> Stack;
2554   SmallVector<BasicBlock *, 16> Order;
2555   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
2556     BasicBlock *BB = I;
2557     if (BB->getTerminator()->getNumSuccessors() == 0)
2558       Stack.push_back(std::make_pair(BB, pred_begin(BB)));
2559   }
2560   while (!Stack.empty()) {
2561     pred_iterator End = pred_end(Stack.back().first);
2562     while (Stack.back().second != End) {
2563       BasicBlock *BB = *Stack.back().second++;
2564       if (Visited.insert(BB))
2565         Stack.push_back(std::make_pair(BB, pred_begin(BB)));
2566     }
2567     Order.push_back(Stack.pop_back_val().first);
2568   }
2569   bool BottomUpNestingDetected = false;
2570   while (!Order.empty()) {
2571     BasicBlock *BB = Order.pop_back_val();
2572     BottomUpNestingDetected |= VisitBottomUp(BB, BBStates, Retains);
2573   }
2574
2575   // Use regular reverse-postorder for top-down.
2576   bool TopDownNestingDetected = false;
2577   typedef ReversePostOrderTraversal<Function *> RPOTType;
2578   RPOTType RPOT(&F);
2579   for (RPOTType::rpo_iterator I = RPOT.begin(), E = RPOT.end(); I != E; ++I) {
2580     BasicBlock *BB = *I;
2581     TopDownNestingDetected |= VisitTopDown(BB, BBStates, Releases);
2582   }
2583
2584   return TopDownNestingDetected && BottomUpNestingDetected;
2585 }
2586
2587 /// MoveCalls - Move the calls in RetainsToMove and ReleasesToMove.
2588 void ObjCARCOpt::MoveCalls(Value *Arg,
2589                            RRInfo &RetainsToMove,
2590                            RRInfo &ReleasesToMove,
2591                            MapVector<Value *, RRInfo> &Retains,
2592                            DenseMap<Value *, RRInfo> &Releases,
2593                            SmallVectorImpl<Instruction *> &DeadInsts,
2594                            Module *M) {
2595   Type *ArgTy = Arg->getType();
2596   Type *ParamTy = PointerType::getUnqual(Type::getInt8Ty(ArgTy->getContext()));
2597
2598   // Insert the new retain and release calls.
2599   for (SmallPtrSet<Instruction *, 2>::const_iterator
2600        PI = ReleasesToMove.ReverseInsertPts.begin(),
2601        PE = ReleasesToMove.ReverseInsertPts.end(); PI != PE; ++PI) {
2602     Instruction *InsertPt = *PI;
2603     Value *MyArg = ArgTy == ParamTy ? Arg :
2604                    new BitCastInst(Arg, ParamTy, "", InsertPt);
2605     CallInst *Call =
2606       CallInst::Create(RetainsToMove.IsRetainBlock ?
2607                          getRetainBlockCallee(M) : getRetainCallee(M),
2608                        MyArg, "", InsertPt);
2609     Call->setDoesNotThrow();
2610     if (!RetainsToMove.IsRetainBlock)
2611       Call->setTailCall();
2612   }
2613   for (SmallPtrSet<Instruction *, 2>::const_iterator
2614        PI = RetainsToMove.ReverseInsertPts.begin(),
2615        PE = RetainsToMove.ReverseInsertPts.end(); PI != PE; ++PI) {
2616     Instruction *LastUse = *PI;
2617     Instruction *InsertPts[] = { 0, 0, 0 };
2618     if (InvokeInst *II = dyn_cast<InvokeInst>(LastUse)) {
2619       // We can't insert code immediately after an invoke instruction, so
2620       // insert code at the beginning of both successor blocks instead.
2621       // The invoke's return value isn't available in the unwind block,
2622       // but our releases will never depend on it, because they must be
2623       // paired with retains from before the invoke.
2624       InsertPts[0] = II->getNormalDest()->getFirstNonPHI();
2625       InsertPts[1] = II->getUnwindDest()->getFirstNonPHI();
2626     } else {
2627       // Insert code immediately after the last use.
2628       InsertPts[0] = llvm::next(BasicBlock::iterator(LastUse));
2629     }
2630
2631     for (Instruction **I = InsertPts; *I; ++I) {
2632       Instruction *InsertPt = *I;
2633       Value *MyArg = ArgTy == ParamTy ? Arg :
2634                      new BitCastInst(Arg, ParamTy, "", InsertPt);
2635       CallInst *Call = CallInst::Create(getReleaseCallee(M), MyArg,
2636                                         "", InsertPt);
2637       // Attach a clang.imprecise_release metadata tag, if appropriate.
2638       if (MDNode *M = ReleasesToMove.ReleaseMetadata)
2639         Call->setMetadata(ImpreciseReleaseMDKind, M);
2640       Call->setDoesNotThrow();
2641       if (ReleasesToMove.IsTailCallRelease)
2642         Call->setTailCall();
2643     }
2644   }
2645
2646   // Delete the original retain and release calls.
2647   for (SmallPtrSet<Instruction *, 2>::const_iterator
2648        AI = RetainsToMove.Calls.begin(),
2649        AE = RetainsToMove.Calls.end(); AI != AE; ++AI) {
2650     Instruction *OrigRetain = *AI;
2651     Retains.blot(OrigRetain);
2652     DeadInsts.push_back(OrigRetain);
2653   }
2654   for (SmallPtrSet<Instruction *, 2>::const_iterator
2655        AI = ReleasesToMove.Calls.begin(),
2656        AE = ReleasesToMove.Calls.end(); AI != AE; ++AI) {
2657     Instruction *OrigRelease = *AI;
2658     Releases.erase(OrigRelease);
2659     DeadInsts.push_back(OrigRelease);
2660   }
2661 }
2662
2663 bool
2664 ObjCARCOpt::PerformCodePlacement(DenseMap<const BasicBlock *, BBState>
2665                                    &BBStates,
2666                                  MapVector<Value *, RRInfo> &Retains,
2667                                  DenseMap<Value *, RRInfo> &Releases,
2668                                  Module *M) {
2669   bool AnyPairsCompletelyEliminated = false;
2670   RRInfo RetainsToMove;
2671   RRInfo ReleasesToMove;
2672   SmallVector<Instruction *, 4> NewRetains;
2673   SmallVector<Instruction *, 4> NewReleases;
2674   SmallVector<Instruction *, 8> DeadInsts;
2675
2676   for (MapVector<Value *, RRInfo>::const_iterator I = Retains.begin(),
2677        E = Retains.end(); I != E; ) {
2678     Value *V = (I++)->first;
2679     if (!V) continue; // blotted
2680
2681     Instruction *Retain = cast<Instruction>(V);
2682     Value *Arg = GetObjCArg(Retain);
2683
2684     // If the object being released is in static or stack storage, we know it's
2685     // not being managed by ObjC reference counting, so we can delete pairs
2686     // regardless of what possible decrements or uses lie between them.
2687     bool KnownSafe = isa<Constant>(Arg) || isa<AllocaInst>(Arg);
2688
2689     // If a pair happens in a region where it is known that the reference count
2690     // is already incremented, we can similarly ignore possible decrements.
2691     bool KnownIncrementedTD = true, KnownIncrementedBU = true;
2692
2693     // Connect the dots between the top-down-collected RetainsToMove and
2694     // bottom-up-collected ReleasesToMove to form sets of related calls.
2695     // This is an iterative process so that we connect multiple releases
2696     // to multiple retains if needed.
2697     unsigned OldDelta = 0;
2698     unsigned NewDelta = 0;
2699     unsigned OldCount = 0;
2700     unsigned NewCount = 0;
2701     bool FirstRelease = true;
2702     bool FirstRetain = true;
2703     NewRetains.push_back(Retain);
2704     for (;;) {
2705       for (SmallVectorImpl<Instruction *>::const_iterator
2706            NI = NewRetains.begin(), NE = NewRetains.end(); NI != NE; ++NI) {
2707         Instruction *NewRetain = *NI;
2708         MapVector<Value *, RRInfo>::const_iterator It = Retains.find(NewRetain);
2709         assert(It != Retains.end());
2710         const RRInfo &NewRetainRRI = It->second;
2711         KnownIncrementedTD &= NewRetainRRI.KnownIncremented;
2712         for (SmallPtrSet<Instruction *, 2>::const_iterator
2713              LI = NewRetainRRI.Calls.begin(),
2714              LE = NewRetainRRI.Calls.end(); LI != LE; ++LI) {
2715           Instruction *NewRetainRelease = *LI;
2716           DenseMap<Value *, RRInfo>::const_iterator Jt =
2717             Releases.find(NewRetainRelease);
2718           if (Jt == Releases.end())
2719             goto next_retain;
2720           const RRInfo &NewRetainReleaseRRI = Jt->second;
2721           assert(NewRetainReleaseRRI.Calls.count(NewRetain));
2722           if (ReleasesToMove.Calls.insert(NewRetainRelease)) {
2723             OldDelta -=
2724               BBStates[NewRetainRelease->getParent()].GetAllPathCount();
2725
2726             // Merge the ReleaseMetadata and IsTailCallRelease values.
2727             if (FirstRelease) {
2728               ReleasesToMove.ReleaseMetadata =
2729                 NewRetainReleaseRRI.ReleaseMetadata;
2730               ReleasesToMove.IsTailCallRelease =
2731                 NewRetainReleaseRRI.IsTailCallRelease;
2732               FirstRelease = false;
2733             } else {
2734               if (ReleasesToMove.ReleaseMetadata !=
2735                     NewRetainReleaseRRI.ReleaseMetadata)
2736                 ReleasesToMove.ReleaseMetadata = 0;
2737               if (ReleasesToMove.IsTailCallRelease !=
2738                     NewRetainReleaseRRI.IsTailCallRelease)
2739                 ReleasesToMove.IsTailCallRelease = false;
2740             }
2741
2742             // Collect the optimal insertion points.
2743             if (!KnownSafe)
2744               for (SmallPtrSet<Instruction *, 2>::const_iterator
2745                    RI = NewRetainReleaseRRI.ReverseInsertPts.begin(),
2746                    RE = NewRetainReleaseRRI.ReverseInsertPts.end();
2747                    RI != RE; ++RI) {
2748                 Instruction *RIP = *RI;
2749                 if (ReleasesToMove.ReverseInsertPts.insert(RIP))
2750                   NewDelta -= BBStates[RIP->getParent()].GetAllPathCount();
2751               }
2752             NewReleases.push_back(NewRetainRelease);
2753           }
2754         }
2755       }
2756       NewRetains.clear();
2757       if (NewReleases.empty()) break;
2758
2759       // Back the other way.
2760       for (SmallVectorImpl<Instruction *>::const_iterator
2761            NI = NewReleases.begin(), NE = NewReleases.end(); NI != NE; ++NI) {
2762         Instruction *NewRelease = *NI;
2763         DenseMap<Value *, RRInfo>::const_iterator It =
2764           Releases.find(NewRelease);
2765         assert(It != Releases.end());
2766         const RRInfo &NewReleaseRRI = It->second;
2767         KnownIncrementedBU &= NewReleaseRRI.KnownIncremented;
2768         for (SmallPtrSet<Instruction *, 2>::const_iterator
2769              LI = NewReleaseRRI.Calls.begin(),
2770              LE = NewReleaseRRI.Calls.end(); LI != LE; ++LI) {
2771           Instruction *NewReleaseRetain = *LI;
2772           MapVector<Value *, RRInfo>::const_iterator Jt =
2773             Retains.find(NewReleaseRetain);
2774           if (Jt == Retains.end())
2775             goto next_retain;
2776           const RRInfo &NewReleaseRetainRRI = Jt->second;
2777           assert(NewReleaseRetainRRI.Calls.count(NewRelease));
2778           if (RetainsToMove.Calls.insert(NewReleaseRetain)) {
2779             unsigned PathCount =
2780               BBStates[NewReleaseRetain->getParent()].GetAllPathCount();
2781             OldDelta += PathCount;
2782             OldCount += PathCount;
2783
2784             // Merge the IsRetainBlock values.
2785             if (FirstRetain) {
2786               RetainsToMove.IsRetainBlock = NewReleaseRetainRRI.IsRetainBlock;
2787               FirstRetain = false;
2788             } else if (ReleasesToMove.IsRetainBlock !=
2789                        NewReleaseRetainRRI.IsRetainBlock)
2790               // It's not possible to merge the sequences if one uses
2791               // objc_retain and the other uses objc_retainBlock.
2792               goto next_retain;
2793
2794             // Collect the optimal insertion points.
2795             if (!KnownSafe)
2796               for (SmallPtrSet<Instruction *, 2>::const_iterator
2797                    RI = NewReleaseRetainRRI.ReverseInsertPts.begin(),
2798                    RE = NewReleaseRetainRRI.ReverseInsertPts.end();
2799                    RI != RE; ++RI) {
2800                 Instruction *RIP = *RI;
2801                 if (RetainsToMove.ReverseInsertPts.insert(RIP)) {
2802                   PathCount = BBStates[RIP->getParent()].GetAllPathCount();
2803                   NewDelta += PathCount;
2804                   NewCount += PathCount;
2805                 }
2806               }
2807             NewRetains.push_back(NewReleaseRetain);
2808           }
2809         }
2810       }
2811       NewReleases.clear();
2812       if (NewRetains.empty()) break;
2813     }
2814
2815     // If the pointer is known incremented, we can safely delete the pair
2816     // regardless of what's between them.
2817     if (KnownIncrementedTD || KnownIncrementedBU) {
2818       RetainsToMove.ReverseInsertPts.clear();
2819       ReleasesToMove.ReverseInsertPts.clear();
2820       NewCount = 0;
2821     }
2822
2823     // Determine whether the original call points are balanced in the retain and
2824     // release calls through the program. If not, conservatively don't touch
2825     // them.
2826     // TODO: It's theoretically possible to do code motion in this case, as
2827     // long as the existing imbalances are maintained.
2828     if (OldDelta != 0)
2829       goto next_retain;
2830
2831     // Determine whether the new insertion points we computed preserve the
2832     // balance of retain and release calls through the program.
2833     // TODO: If the fully aggressive solution isn't valid, try to find a
2834     // less aggressive solution which is.
2835     if (NewDelta != 0)
2836       goto next_retain;
2837
2838     // Ok, everything checks out and we're all set. Let's move some code!
2839     Changed = true;
2840     AnyPairsCompletelyEliminated = NewCount == 0;
2841     NumRRs += OldCount - NewCount;
2842     MoveCalls(Arg, RetainsToMove, ReleasesToMove,
2843               Retains, Releases, DeadInsts, M);
2844
2845   next_retain:
2846     NewReleases.clear();
2847     NewRetains.clear();
2848     RetainsToMove.clear();
2849     ReleasesToMove.clear();
2850   }
2851
2852   // Now that we're done moving everything, we can delete the newly dead
2853   // instructions, as we no longer need them as insert points.
2854   while (!DeadInsts.empty())
2855     EraseInstruction(DeadInsts.pop_back_val());
2856
2857   return AnyPairsCompletelyEliminated;
2858 }
2859
2860 /// OptimizeWeakCalls - Weak pointer optimizations.
2861 void ObjCARCOpt::OptimizeWeakCalls(Function &F) {
2862   // First, do memdep-style RLE and S2L optimizations. We can't use memdep
2863   // itself because it uses AliasAnalysis and we need to do provenance
2864   // queries instead.
2865   for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
2866     Instruction *Inst = &*I++;
2867     InstructionClass Class = GetBasicInstructionClass(Inst);
2868     if (Class != IC_LoadWeak && Class != IC_LoadWeakRetained)
2869       continue;
2870
2871     // Delete objc_loadWeak calls with no users.
2872     if (Class == IC_LoadWeak && Inst->use_empty()) {
2873       Inst->eraseFromParent();
2874       continue;
2875     }
2876
2877     // TODO: For now, just look for an earlier available version of this value
2878     // within the same block. Theoretically, we could do memdep-style non-local
2879     // analysis too, but that would want caching. A better approach would be to
2880     // use the technique that EarlyCSE uses.
2881     inst_iterator Current = llvm::prior(I);
2882     BasicBlock *CurrentBB = Current.getBasicBlockIterator();
2883     for (BasicBlock::iterator B = CurrentBB->begin(),
2884                               J = Current.getInstructionIterator();
2885          J != B; --J) {
2886       Instruction *EarlierInst = &*llvm::prior(J);
2887       InstructionClass EarlierClass = GetInstructionClass(EarlierInst);
2888       switch (EarlierClass) {
2889       case IC_LoadWeak:
2890       case IC_LoadWeakRetained: {
2891         // If this is loading from the same pointer, replace this load's value
2892         // with that one.
2893         CallInst *Call = cast<CallInst>(Inst);
2894         CallInst *EarlierCall = cast<CallInst>(EarlierInst);
2895         Value *Arg = Call->getArgOperand(0);
2896         Value *EarlierArg = EarlierCall->getArgOperand(0);
2897         switch (PA.getAA()->alias(Arg, EarlierArg)) {
2898         case AliasAnalysis::MustAlias:
2899           Changed = true;
2900           // If the load has a builtin retain, insert a plain retain for it.
2901           if (Class == IC_LoadWeakRetained) {
2902             CallInst *CI =
2903               CallInst::Create(getRetainCallee(F.getParent()), EarlierCall,
2904                                "", Call);
2905             CI->setTailCall();
2906           }
2907           // Zap the fully redundant load.
2908           Call->replaceAllUsesWith(EarlierCall);
2909           Call->eraseFromParent();
2910           goto clobbered;
2911         case AliasAnalysis::MayAlias:
2912         case AliasAnalysis::PartialAlias:
2913           goto clobbered;
2914         case AliasAnalysis::NoAlias:
2915           break;
2916         }
2917         break;
2918       }
2919       case IC_StoreWeak:
2920       case IC_InitWeak: {
2921         // If this is storing to the same pointer and has the same size etc.
2922         // replace this load's value with the stored value.
2923         CallInst *Call = cast<CallInst>(Inst);
2924         CallInst *EarlierCall = cast<CallInst>(EarlierInst);
2925         Value *Arg = Call->getArgOperand(0);
2926         Value *EarlierArg = EarlierCall->getArgOperand(0);
2927         switch (PA.getAA()->alias(Arg, EarlierArg)) {
2928         case AliasAnalysis::MustAlias:
2929           Changed = true;
2930           // If the load has a builtin retain, insert a plain retain for it.
2931           if (Class == IC_LoadWeakRetained) {
2932             CallInst *CI =
2933               CallInst::Create(getRetainCallee(F.getParent()), EarlierCall,
2934                                "", Call);
2935             CI->setTailCall();
2936           }
2937           // Zap the fully redundant load.
2938           Call->replaceAllUsesWith(EarlierCall->getArgOperand(1));
2939           Call->eraseFromParent();
2940           goto clobbered;
2941         case AliasAnalysis::MayAlias:
2942         case AliasAnalysis::PartialAlias:
2943           goto clobbered;
2944         case AliasAnalysis::NoAlias:
2945           break;
2946         }
2947         break;
2948       }
2949       case IC_MoveWeak:
2950       case IC_CopyWeak:
2951         // TOOD: Grab the copied value.
2952         goto clobbered;
2953       case IC_AutoreleasepoolPush:
2954       case IC_None:
2955       case IC_User:
2956         // Weak pointers are only modified through the weak entry points
2957         // (and arbitrary calls, which could call the weak entry points).
2958         break;
2959       default:
2960         // Anything else could modify the weak pointer.
2961         goto clobbered;
2962       }
2963     }
2964   clobbered:;
2965   }
2966
2967   // Then, for each destroyWeak with an alloca operand, check to see if
2968   // the alloca and all its users can be zapped.
2969   for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
2970     Instruction *Inst = &*I++;
2971     InstructionClass Class = GetBasicInstructionClass(Inst);
2972     if (Class != IC_DestroyWeak)
2973       continue;
2974
2975     CallInst *Call = cast<CallInst>(Inst);
2976     Value *Arg = Call->getArgOperand(0);
2977     if (AllocaInst *Alloca = dyn_cast<AllocaInst>(Arg)) {
2978       for (Value::use_iterator UI = Alloca->use_begin(),
2979            UE = Alloca->use_end(); UI != UE; ++UI) {
2980         Instruction *UserInst = cast<Instruction>(*UI);
2981         switch (GetBasicInstructionClass(UserInst)) {
2982         case IC_InitWeak:
2983         case IC_StoreWeak:
2984         case IC_DestroyWeak:
2985           continue;
2986         default:
2987           goto done;
2988         }
2989       }
2990       Changed = true;
2991       for (Value::use_iterator UI = Alloca->use_begin(),
2992            UE = Alloca->use_end(); UI != UE; ) {
2993         CallInst *UserInst = cast<CallInst>(*UI++);
2994         if (!UserInst->use_empty())
2995           UserInst->replaceAllUsesWith(UserInst->getOperand(1));
2996         UserInst->eraseFromParent();
2997       }
2998       Alloca->eraseFromParent();
2999     done:;
3000     }
3001   }
3002 }
3003
3004 /// OptimizeSequences - Identify program paths which execute sequences of
3005 /// retains and releases which can be eliminated.
3006 bool ObjCARCOpt::OptimizeSequences(Function &F) {
3007   /// Releases, Retains - These are used to store the results of the main flow
3008   /// analysis. These use Value* as the key instead of Instruction* so that the
3009   /// map stays valid when we get around to rewriting code and calls get
3010   /// replaced by arguments.
3011   DenseMap<Value *, RRInfo> Releases;
3012   MapVector<Value *, RRInfo> Retains;
3013
3014   /// BBStates, This is used during the traversal of the function to track the
3015   /// states for each identified object at each block.
3016   DenseMap<const BasicBlock *, BBState> BBStates;
3017
3018   // Analyze the CFG of the function, and all instructions.
3019   bool NestingDetected = Visit(F, BBStates, Retains, Releases);
3020
3021   // Transform.
3022   return PerformCodePlacement(BBStates, Retains, Releases, F.getParent()) &&
3023          NestingDetected;
3024 }
3025
3026 /// OptimizeReturns - Look for this pattern:
3027 ///
3028 ///    %call = call i8* @something(...)
3029 ///    %2 = call i8* @objc_retain(i8* %call)
3030 ///    %3 = call i8* @objc_autorelease(i8* %2)
3031 ///    ret i8* %3
3032 ///
3033 /// And delete the retain and autorelease.
3034 ///
3035 /// Otherwise if it's just this:
3036 ///
3037 ///    %3 = call i8* @objc_autorelease(i8* %2)
3038 ///    ret i8* %3
3039 ///
3040 /// convert the autorelease to autoreleaseRV.
3041 void ObjCARCOpt::OptimizeReturns(Function &F) {
3042   if (!F.getReturnType()->isPointerTy())
3043     return;
3044
3045   SmallPtrSet<Instruction *, 4> DependingInstructions;
3046   SmallPtrSet<const BasicBlock *, 4> Visited;
3047   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
3048     BasicBlock *BB = FI;
3049     ReturnInst *Ret = dyn_cast<ReturnInst>(&BB->back());
3050     if (!Ret) continue;
3051
3052     const Value *Arg = StripPointerCastsAndObjCCalls(Ret->getOperand(0));
3053     FindDependencies(NeedsPositiveRetainCount, Arg,
3054                      BB, Ret, DependingInstructions, Visited, PA);
3055     if (DependingInstructions.size() != 1)
3056       goto next_block;
3057
3058     {
3059       CallInst *Autorelease =
3060         dyn_cast_or_null<CallInst>(*DependingInstructions.begin());
3061       if (!Autorelease)
3062         goto next_block;
3063       InstructionClass AutoreleaseClass =
3064         GetBasicInstructionClass(Autorelease);
3065       if (!IsAutorelease(AutoreleaseClass))
3066         goto next_block;
3067       if (GetObjCArg(Autorelease) != Arg)
3068         goto next_block;
3069
3070       DependingInstructions.clear();
3071       Visited.clear();
3072
3073       // Check that there is nothing that can affect the reference
3074       // count between the autorelease and the retain.
3075       FindDependencies(CanChangeRetainCount, Arg,
3076                        BB, Autorelease, DependingInstructions, Visited, PA);
3077       if (DependingInstructions.size() != 1)
3078         goto next_block;
3079
3080       {
3081         CallInst *Retain =
3082           dyn_cast_or_null<CallInst>(*DependingInstructions.begin());
3083
3084         // Check that we found a retain with the same argument.
3085         if (!Retain ||
3086             !IsRetain(GetBasicInstructionClass(Retain)) ||
3087             GetObjCArg(Retain) != Arg)
3088           goto next_block;
3089
3090         DependingInstructions.clear();
3091         Visited.clear();
3092
3093         // Convert the autorelease to an autoreleaseRV, since it's
3094         // returning the value.
3095         if (AutoreleaseClass == IC_Autorelease) {
3096           Autorelease->setCalledFunction(getAutoreleaseRVCallee(F.getParent()));
3097           AutoreleaseClass = IC_AutoreleaseRV;
3098         }
3099
3100         // Check that there is nothing that can affect the reference
3101         // count between the retain and the call.
3102         FindDependencies(CanChangeRetainCount, Arg, BB, Retain,
3103                          DependingInstructions, Visited, PA);
3104         if (DependingInstructions.size() != 1)
3105           goto next_block;
3106
3107         {
3108           CallInst *Call =
3109             dyn_cast_or_null<CallInst>(*DependingInstructions.begin());
3110
3111           // Check that the pointer is the return value of the call.
3112           if (!Call || Arg != Call)
3113             goto next_block;
3114
3115           // Check that the call is a regular call.
3116           InstructionClass Class = GetBasicInstructionClass(Call);
3117           if (Class != IC_CallOrUser && Class != IC_Call)
3118             goto next_block;
3119
3120           // If so, we can zap the retain and autorelease.
3121           Changed = true;
3122           ++NumRets;
3123           EraseInstruction(Retain);
3124           EraseInstruction(Autorelease);
3125         }
3126       }
3127     }
3128
3129   next_block:
3130     DependingInstructions.clear();
3131     Visited.clear();
3132   }
3133 }
3134
3135 bool ObjCARCOpt::doInitialization(Module &M) {
3136   if (!EnableARCOpts)
3137     return false;
3138
3139   Run = ModuleHasARC(M);
3140   if (!Run)
3141     return false;
3142
3143   // Identify the imprecise release metadata kind.
3144   ImpreciseReleaseMDKind =
3145     M.getContext().getMDKindID("clang.imprecise_release");
3146
3147   // Intuitively, objc_retain and others are nocapture, however in practice
3148   // they are not, because they return their argument value. And objc_release
3149   // calls finalizers.
3150
3151   // These are initialized lazily.
3152   RetainRVCallee = 0;
3153   AutoreleaseRVCallee = 0;
3154   ReleaseCallee = 0;
3155   RetainCallee = 0;
3156   RetainBlockCallee = 0;
3157   AutoreleaseCallee = 0;
3158
3159   return false;
3160 }
3161
3162 bool ObjCARCOpt::runOnFunction(Function &F) {
3163   if (!EnableARCOpts)
3164     return false;
3165
3166   // If nothing in the Module uses ARC, don't do anything.
3167   if (!Run)
3168     return false;
3169
3170   Changed = false;
3171
3172   PA.setAA(&getAnalysis<AliasAnalysis>());
3173
3174   // This pass performs several distinct transformations. As a compile-time aid
3175   // when compiling code that isn't ObjC, skip these if the relevant ObjC
3176   // library functions aren't declared.
3177
3178   // Preliminary optimizations. This also computs UsedInThisFunction.
3179   OptimizeIndividualCalls(F);
3180
3181   // Optimizations for weak pointers.
3182   if (UsedInThisFunction & ((1 << IC_LoadWeak) |
3183                             (1 << IC_LoadWeakRetained) |
3184                             (1 << IC_StoreWeak) |
3185                             (1 << IC_InitWeak) |
3186                             (1 << IC_CopyWeak) |
3187                             (1 << IC_MoveWeak) |
3188                             (1 << IC_DestroyWeak)))
3189     OptimizeWeakCalls(F);
3190
3191   // Optimizations for retain+release pairs.
3192   if (UsedInThisFunction & ((1 << IC_Retain) |
3193                             (1 << IC_RetainRV) |
3194                             (1 << IC_RetainBlock)))
3195     if (UsedInThisFunction & (1 << IC_Release))
3196       // Run OptimizeSequences until it either stops making changes or
3197       // no retain+release pair nesting is detected.
3198       while (OptimizeSequences(F)) {}
3199
3200   // Optimizations if objc_autorelease is used.
3201   if (UsedInThisFunction &
3202       ((1 << IC_Autorelease) | (1 << IC_AutoreleaseRV)))
3203     OptimizeReturns(F);
3204
3205   return Changed;
3206 }
3207
3208 void ObjCARCOpt::releaseMemory() {
3209   PA.clear();
3210 }
3211
3212 //===----------------------------------------------------------------------===//
3213 // ARC contraction.
3214 //===----------------------------------------------------------------------===//
3215
3216 // TODO: ObjCARCContract could insert PHI nodes when uses aren't
3217 // dominated by single calls.
3218
3219 #include "llvm/Operator.h"
3220 #include "llvm/InlineAsm.h"
3221 #include "llvm/Analysis/Dominators.h"
3222
3223 STATISTIC(NumStoreStrongs, "Number objc_storeStrong calls formed");
3224
3225 namespace {
3226   /// ObjCARCContract - Late ARC optimizations.  These change the IR in a way
3227   /// that makes it difficult to be analyzed by ObjCARCOpt, so it's run late.
3228   class ObjCARCContract : public FunctionPass {
3229     bool Changed;
3230     AliasAnalysis *AA;
3231     DominatorTree *DT;
3232     ProvenanceAnalysis PA;
3233
3234     /// Run - A flag indicating whether this optimization pass should run.
3235     bool Run;
3236
3237     /// StoreStrongCallee, etc. - Declarations for ObjC runtime
3238     /// functions, for use in creating calls to them. These are initialized
3239     /// lazily to avoid cluttering up the Module with unused declarations.
3240     Constant *StoreStrongCallee,
3241              *RetainAutoreleaseCallee, *RetainAutoreleaseRVCallee;
3242
3243     /// RetainRVMarker - The inline asm string to insert between calls and
3244     /// RetainRV calls to make the optimization work on targets which need it.
3245     const MDString *RetainRVMarker;
3246
3247     Constant *getStoreStrongCallee(Module *M);
3248     Constant *getRetainAutoreleaseCallee(Module *M);
3249     Constant *getRetainAutoreleaseRVCallee(Module *M);
3250
3251     bool ContractAutorelease(Function &F, Instruction *Autorelease,
3252                              InstructionClass Class,
3253                              SmallPtrSet<Instruction *, 4>
3254                                &DependingInstructions,
3255                              SmallPtrSet<const BasicBlock *, 4>
3256                                &Visited);
3257
3258     void ContractRelease(Instruction *Release,
3259                          inst_iterator &Iter);
3260
3261     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
3262     virtual bool doInitialization(Module &M);
3263     virtual bool runOnFunction(Function &F);
3264
3265   public:
3266     static char ID;
3267     ObjCARCContract() : FunctionPass(ID) {
3268       initializeObjCARCContractPass(*PassRegistry::getPassRegistry());
3269     }
3270   };
3271 }
3272
3273 char ObjCARCContract::ID = 0;
3274 INITIALIZE_PASS_BEGIN(ObjCARCContract,
3275                       "objc-arc-contract", "ObjC ARC contraction", false, false)
3276 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
3277 INITIALIZE_PASS_DEPENDENCY(DominatorTree)
3278 INITIALIZE_PASS_END(ObjCARCContract,
3279                     "objc-arc-contract", "ObjC ARC contraction", false, false)
3280
3281 Pass *llvm::createObjCARCContractPass() {
3282   return new ObjCARCContract();
3283 }
3284
3285 void ObjCARCContract::getAnalysisUsage(AnalysisUsage &AU) const {
3286   AU.addRequired<AliasAnalysis>();
3287   AU.addRequired<DominatorTree>();
3288   AU.setPreservesCFG();
3289 }
3290
3291 Constant *ObjCARCContract::getStoreStrongCallee(Module *M) {
3292   if (!StoreStrongCallee) {
3293     LLVMContext &C = M->getContext();
3294     Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
3295     Type *I8XX = PointerType::getUnqual(I8X);
3296     std::vector<Type *> Params;
3297     Params.push_back(I8XX);
3298     Params.push_back(I8X);
3299
3300     AttrListPtr Attributes;
3301     Attributes.addAttr(~0u, Attribute::NoUnwind);
3302     Attributes.addAttr(1, Attribute::NoCapture);
3303
3304     StoreStrongCallee =
3305       M->getOrInsertFunction(
3306         "objc_storeStrong",
3307         FunctionType::get(Type::getVoidTy(C), Params, /*isVarArg=*/false),
3308         Attributes);
3309   }
3310   return StoreStrongCallee;
3311 }
3312
3313 Constant *ObjCARCContract::getRetainAutoreleaseCallee(Module *M) {
3314   if (!RetainAutoreleaseCallee) {
3315     LLVMContext &C = M->getContext();
3316     Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
3317     std::vector<Type *> Params;
3318     Params.push_back(I8X);
3319     FunctionType *FTy =
3320       FunctionType::get(I8X, Params, /*isVarArg=*/false);
3321     AttrListPtr Attributes;
3322     Attributes.addAttr(~0u, Attribute::NoUnwind);
3323     RetainAutoreleaseCallee =
3324       M->getOrInsertFunction("objc_retainAutorelease", FTy, Attributes);
3325   }
3326   return RetainAutoreleaseCallee;
3327 }
3328
3329 Constant *ObjCARCContract::getRetainAutoreleaseRVCallee(Module *M) {
3330   if (!RetainAutoreleaseRVCallee) {
3331     LLVMContext &C = M->getContext();
3332     Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
3333     std::vector<Type *> Params;
3334     Params.push_back(I8X);
3335     FunctionType *FTy =
3336       FunctionType::get(I8X, Params, /*isVarArg=*/false);
3337     AttrListPtr Attributes;
3338     Attributes.addAttr(~0u, Attribute::NoUnwind);
3339     RetainAutoreleaseRVCallee =
3340       M->getOrInsertFunction("objc_retainAutoreleaseReturnValue", FTy,
3341                              Attributes);
3342   }
3343   return RetainAutoreleaseRVCallee;
3344 }
3345
3346 /// ContractAutorelease - Merge an autorelease with a retain into a fused
3347 /// call.
3348 bool
3349 ObjCARCContract::ContractAutorelease(Function &F, Instruction *Autorelease,
3350                                      InstructionClass Class,
3351                                      SmallPtrSet<Instruction *, 4>
3352                                        &DependingInstructions,
3353                                      SmallPtrSet<const BasicBlock *, 4>
3354                                        &Visited) {
3355   const Value *Arg = GetObjCArg(Autorelease);
3356
3357   // Check that there are no instructions between the retain and the autorelease
3358   // (such as an autorelease_pop) which may change the count.
3359   CallInst *Retain = 0;
3360   if (Class == IC_AutoreleaseRV)
3361     FindDependencies(RetainAutoreleaseRVDep, Arg,
3362                      Autorelease->getParent(), Autorelease,
3363                      DependingInstructions, Visited, PA);
3364   else
3365     FindDependencies(RetainAutoreleaseDep, Arg,
3366                      Autorelease->getParent(), Autorelease,
3367                      DependingInstructions, Visited, PA);
3368
3369   Visited.clear();
3370   if (DependingInstructions.size() != 1) {
3371     DependingInstructions.clear();
3372     return false;
3373   }
3374
3375   Retain = dyn_cast_or_null<CallInst>(*DependingInstructions.begin());
3376   DependingInstructions.clear();
3377
3378   if (!Retain ||
3379       GetBasicInstructionClass(Retain) != IC_Retain ||
3380       GetObjCArg(Retain) != Arg)
3381     return false;
3382
3383   Changed = true;
3384   ++NumPeeps;
3385
3386   if (Class == IC_AutoreleaseRV)
3387     Retain->setCalledFunction(getRetainAutoreleaseRVCallee(F.getParent()));
3388   else
3389     Retain->setCalledFunction(getRetainAutoreleaseCallee(F.getParent()));
3390
3391   EraseInstruction(Autorelease);
3392   return true;
3393 }
3394
3395 /// ContractRelease - Attempt to merge an objc_release with a store, load, and
3396 /// objc_retain to form an objc_storeStrong. This can be a little tricky because
3397 /// the instructions don't always appear in order, and there may be unrelated
3398 /// intervening instructions.
3399 void ObjCARCContract::ContractRelease(Instruction *Release,
3400                                       inst_iterator &Iter) {
3401   LoadInst *Load = dyn_cast<LoadInst>(GetObjCArg(Release));
3402   if (!Load || Load->isVolatile()) return;
3403
3404   // For now, require everything to be in one basic block.
3405   BasicBlock *BB = Release->getParent();
3406   if (Load->getParent() != BB) return;
3407
3408   // Walk down to find the store.
3409   BasicBlock::iterator I = Load, End = BB->end();
3410   ++I;
3411   AliasAnalysis::Location Loc = AA->getLocation(Load);
3412   while (I != End &&
3413          (&*I == Release ||
3414           IsRetain(GetBasicInstructionClass(I)) ||
3415           !(AA->getModRefInfo(I, Loc) & AliasAnalysis::Mod)))
3416     ++I;
3417   StoreInst *Store = dyn_cast<StoreInst>(I);
3418   if (!Store || Store->isVolatile()) return;
3419   if (Store->getPointerOperand() != Loc.Ptr) return;
3420
3421   Value *New = StripPointerCastsAndObjCCalls(Store->getValueOperand());
3422
3423   // Walk up to find the retain.
3424   I = Store;
3425   BasicBlock::iterator Begin = BB->begin();
3426   while (I != Begin && GetBasicInstructionClass(I) != IC_Retain)
3427     --I;
3428   Instruction *Retain = I;
3429   if (GetBasicInstructionClass(Retain) != IC_Retain) return;
3430   if (GetObjCArg(Retain) != New) return;
3431
3432   Changed = true;
3433   ++NumStoreStrongs;
3434
3435   LLVMContext &C = Release->getContext();
3436   Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
3437   Type *I8XX = PointerType::getUnqual(I8X);
3438
3439   Value *Args[] = { Load->getPointerOperand(), New };
3440   if (Args[0]->getType() != I8XX)
3441     Args[0] = new BitCastInst(Args[0], I8XX, "", Store);
3442   if (Args[1]->getType() != I8X)
3443     Args[1] = new BitCastInst(Args[1], I8X, "", Store);
3444   CallInst *StoreStrong =
3445     CallInst::Create(getStoreStrongCallee(BB->getParent()->getParent()),
3446                      Args, "", Store);
3447   StoreStrong->setDoesNotThrow();
3448   StoreStrong->setDebugLoc(Store->getDebugLoc());
3449
3450   if (&*Iter == Store) ++Iter;
3451   Store->eraseFromParent();
3452   Release->eraseFromParent();
3453   EraseInstruction(Retain);
3454   if (Load->use_empty())
3455     Load->eraseFromParent();
3456 }
3457
3458 bool ObjCARCContract::doInitialization(Module &M) {
3459   Run = ModuleHasARC(M);
3460   if (!Run)
3461     return false;
3462
3463   // These are initialized lazily.
3464   StoreStrongCallee = 0;
3465   RetainAutoreleaseCallee = 0;
3466   RetainAutoreleaseRVCallee = 0;
3467
3468   // Initialize RetainRVMarker.
3469   RetainRVMarker = 0;
3470   if (NamedMDNode *NMD =
3471         M.getNamedMetadata("clang.arc.retainAutoreleasedReturnValueMarker"))
3472     if (NMD->getNumOperands() == 1) {
3473       const MDNode *N = NMD->getOperand(0);
3474       if (N->getNumOperands() == 1)
3475         if (const MDString *S = dyn_cast<MDString>(N->getOperand(0)))
3476           RetainRVMarker = S;
3477     }
3478
3479   return false;
3480 }
3481
3482 bool ObjCARCContract::runOnFunction(Function &F) {
3483   if (!EnableARCOpts)
3484     return false;
3485
3486   // If nothing in the Module uses ARC, don't do anything.
3487   if (!Run)
3488     return false;
3489
3490   Changed = false;
3491   AA = &getAnalysis<AliasAnalysis>();
3492   DT = &getAnalysis<DominatorTree>();
3493
3494   PA.setAA(&getAnalysis<AliasAnalysis>());
3495
3496   // For ObjC library calls which return their argument, replace uses of the
3497   // argument with uses of the call return value, if it dominates the use. This
3498   // reduces register pressure.
3499   SmallPtrSet<Instruction *, 4> DependingInstructions;
3500   SmallPtrSet<const BasicBlock *, 4> Visited;
3501   for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
3502     Instruction *Inst = &*I++;
3503
3504     // Only these library routines return their argument. In particular,
3505     // objc_retainBlock does not necessarily return its argument.
3506     InstructionClass Class = GetBasicInstructionClass(Inst);
3507     switch (Class) {
3508     case IC_Retain:
3509     case IC_FusedRetainAutorelease:
3510     case IC_FusedRetainAutoreleaseRV:
3511       break;
3512     case IC_Autorelease:
3513     case IC_AutoreleaseRV:
3514       if (ContractAutorelease(F, Inst, Class, DependingInstructions, Visited))
3515         continue;
3516       break;
3517     case IC_RetainRV: {
3518       // If we're compiling for a target which needs a special inline-asm
3519       // marker to do the retainAutoreleasedReturnValue optimization,
3520       // insert it now.
3521       if (!RetainRVMarker)
3522         break;
3523       BasicBlock::iterator BBI = Inst;
3524       --BBI;
3525       while (isNoopInstruction(BBI)) --BBI;
3526       if (&*BBI == GetObjCArg(Inst)) {
3527         InlineAsm *IA =
3528           InlineAsm::get(FunctionType::get(Type::getVoidTy(Inst->getContext()),
3529                                            /*isVarArg=*/false),
3530                          RetainRVMarker->getString(),
3531                          /*Constraints=*/"", /*hasSideEffects=*/true);
3532         CallInst::Create(IA, "", Inst);
3533       }
3534       break;
3535     }
3536     case IC_InitWeak: {
3537       // objc_initWeak(p, null) => *p = null
3538       CallInst *CI = cast<CallInst>(Inst);
3539       if (isNullOrUndef(CI->getArgOperand(1))) {
3540         Value *Null =
3541           ConstantPointerNull::get(cast<PointerType>(CI->getType()));
3542         Changed = true;
3543         new StoreInst(Null, CI->getArgOperand(0), CI);
3544         CI->replaceAllUsesWith(Null);
3545         CI->eraseFromParent();
3546       }
3547       continue;
3548     }
3549     case IC_Release:
3550       ContractRelease(Inst, I);
3551       continue;
3552     default:
3553       continue;
3554     }
3555
3556     // Don't use GetObjCArg because we don't want to look through bitcasts
3557     // and such; to do the replacement, the argument must have type i8*.
3558     const Value *Arg = cast<CallInst>(Inst)->getArgOperand(0);
3559     for (;;) {
3560       // If we're compiling bugpointed code, don't get in trouble.
3561       if (!isa<Instruction>(Arg) && !isa<Argument>(Arg))
3562         break;
3563       // Look through the uses of the pointer.
3564       for (Value::const_use_iterator UI = Arg->use_begin(), UE = Arg->use_end();
3565            UI != UE; ) {
3566         Use &U = UI.getUse();
3567         unsigned OperandNo = UI.getOperandNo();
3568         ++UI; // Increment UI now, because we may unlink its element.
3569         if (Instruction *UserInst = dyn_cast<Instruction>(U.getUser()))
3570           if (Inst != UserInst && DT->dominates(Inst, UserInst)) {
3571             Changed = true;
3572             Instruction *Replacement = Inst;
3573             Type *UseTy = U.get()->getType();
3574             if (PHINode *PHI = dyn_cast<PHINode>(UserInst)) {
3575               // For PHI nodes, insert the bitcast in the predecessor block.
3576               unsigned ValNo =
3577                 PHINode::getIncomingValueNumForOperand(OperandNo);
3578               BasicBlock *BB =
3579                 PHI->getIncomingBlock(ValNo);
3580               if (Replacement->getType() != UseTy)
3581                 Replacement = new BitCastInst(Replacement, UseTy, "",
3582                                               &BB->back());
3583               for (unsigned i = 0, e = PHI->getNumIncomingValues();
3584                    i != e; ++i)
3585                 if (PHI->getIncomingBlock(i) == BB) {
3586                   // Keep the UI iterator valid.
3587                   if (&PHI->getOperandUse(
3588                         PHINode::getOperandNumForIncomingValue(i)) ==
3589                         &UI.getUse())
3590                     ++UI;
3591                   PHI->setIncomingValue(i, Replacement);
3592                 }
3593             } else {
3594               if (Replacement->getType() != UseTy)
3595                 Replacement = new BitCastInst(Replacement, UseTy, "", UserInst);
3596               U.set(Replacement);
3597             }
3598           }
3599       }
3600
3601       // If Arg is a no-op casted pointer, strip one level of casts and
3602       // iterate.
3603       if (const BitCastInst *BI = dyn_cast<BitCastInst>(Arg))
3604         Arg = BI->getOperand(0);
3605       else if (isa<GEPOperator>(Arg) &&
3606                cast<GEPOperator>(Arg)->hasAllZeroIndices())
3607         Arg = cast<GEPOperator>(Arg)->getPointerOperand();
3608       else if (isa<GlobalAlias>(Arg) &&
3609                !cast<GlobalAlias>(Arg)->mayBeOverridden())
3610         Arg = cast<GlobalAlias>(Arg)->getAliasee();
3611       else
3612         break;
3613     }
3614   }
3615
3616   return Changed;
3617 }