lib/Transforms/ObjCARC/ObjCARCContract.cpp

   1 //===- ObjCARCContract.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 /// \file
  10 /// This file defines late ObjC ARC optimizations. ARC stands for Automatic
  11 /// Reference Counting and is a system for managing reference counts for objects
  12 /// in Objective C.
  13 ///
  14 /// This specific file mainly deals with ``contracting'' multiple lower level
  15 /// operations into singular higher level operations through pattern matching.
  16 ///
  17 /// WARNING: This file knows about certain library functions. It recognizes them
  18 /// by name, and hardwires knowledge of their semantics.
  19 ///
  20 /// WARNING: This file knows about how certain Objective-C library functions are
  21 /// used. Naive LLVM IR transformations which would otherwise be
  22 /// behavior-preserving may break these assumptions.
  23 ///
  24 //===----------------------------------------------------------------------===//
  25
  26 // TODO: ObjCARCContract could insert PHI nodes when uses aren't
  27 // dominated by single calls.
  28
  29 #include "ObjCARC.h"
  30 #include "ARCRuntimeEntryPoints.h"
  31 #include "DependencyAnalysis.h"
  32 #include "ProvenanceAnalysis.h"
  33 #include "llvm/ADT/Statistic.h"
  34 #include "llvm/IR/Dominators.h"
  35 #include "llvm/IR/InlineAsm.h"
  36 #include "llvm/IR/Operator.h"
  37 #include "llvm/Support/Debug.h"
  38
  39 using namespace llvm;
  40 using namespace llvm::objcarc;
  41
  42 #define DEBUG_TYPE "objc-arc-contract"
  43
  44 STATISTIC(NumPeeps,       "Number of calls peephole-optimized");
  45 STATISTIC(NumStoreStrongs, "Number objc_storeStrong calls formed");
  46
  47 //===----------------------------------------------------------------------===//
  48 //                                Declarations
  49 //===----------------------------------------------------------------------===//
  50
  51 namespace {
  52   /// \brief Late ARC optimizations
  53   ///
  54   /// These change the IR in a way that makes it difficult to be analyzed by
  55   /// ObjCARCOpt, so it's run late.
  56   class ObjCARCContract : public FunctionPass {
  57     bool Changed;
  58     AliasAnalysis *AA;
  59     DominatorTree *DT;
  60     ProvenanceAnalysis PA;
  61     ARCRuntimeEntryPoints EP;
  62
  63     /// A flag indicating whether this optimization pass should run.
  64     bool Run;
  65
  66     /// The inline asm string to insert between calls and RetainRV calls to make
  67     /// the optimization work on targets which need it.
  68     const MDString *RetainRVMarker;
  69
  70     /// The set of inserted objc_storeStrong calls. If at the end of walking the
  71     /// function we have found no alloca instructions, these calls can be marked
  72     /// "tail".
  73     SmallPtrSet<CallInst *, 8> StoreStrongCalls;
  74
  75     /// Returns true if we eliminated Inst.
  76     bool tryToPeepholeInstruction(Function &F, Instruction *Inst,
  77                                   inst_iterator &Iter,
  78                                   SmallPtrSetImpl<Instruction *> &DepInsts,
  79                                   SmallPtrSetImpl<const BasicBlock *> &Visited,
  80                                   bool &TailOkForStoreStrong);
  81
  82     bool optimizeRetainCall(Function &F, Instruction *Retain);
  83
  84     bool
  85     contractAutorelease(Function &F, Instruction *Autorelease,
  86                         ARCInstKind Class,
  87                         SmallPtrSetImpl<Instruction *> &DependingInstructions,
  88                         SmallPtrSetImpl<const BasicBlock *> &Visited);
  89
  90     void tryToContractReleaseIntoStoreStrong(Instruction *Release,
  91                                              inst_iterator &Iter);
  92
  93     void getAnalysisUsage(AnalysisUsage &AU) const override;
  94     bool doInitialization(Module &M) override;
  95     bool runOnFunction(Function &F) override;
  96
  97   public:
  98     static char ID;
  99     ObjCARCContract() : FunctionPass(ID) {
 100       initializeObjCARCContractPass(*PassRegistry::getPassRegistry());
 101     }
 102   };
 103 }
 104
 105 //===----------------------------------------------------------------------===//
 106 //                               Implementation
 107 //===----------------------------------------------------------------------===//
 108
 109 /// Turn objc_retain into objc_retainAutoreleasedReturnValue if the operand is a
 110 /// return value. We do this late so we do not disrupt the dataflow analysis in
 111 /// ObjCARCOpt.
 112 bool ObjCARCContract::optimizeRetainCall(Function &F, Instruction *Retain) {
 113   ImmutableCallSite CS(GetArgRCIdentityRoot(Retain));
 114   const Instruction *Call = CS.getInstruction();
 115   if (!Call)
 116     return false;
 117   if (Call->getParent() != Retain->getParent())
 118     return false;
 119
 120   // Check that the call is next to the retain.
 121   BasicBlock::const_iterator I = Call;
 122   ++I;
 123   while (IsNoopInstruction(I)) ++I;
 124   if (&*I != Retain)
 125     return false;
 126
 127   // Turn it to an objc_retainAutoreleasedReturnValue.
 128   Changed = true;
 129   ++NumPeeps;
 130
 131   DEBUG(dbgs() << "Transforming objc_retain => "
 132                   "objc_retainAutoreleasedReturnValue since the operand is a "
 133                   "return value.\nOld: "<< *Retain << "\n");
 134
 135   // We do not have to worry about tail calls/does not throw since
 136   // retain/retainRV have the same properties.
 137   Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_RetainRV);
 138   cast<CallInst>(Retain)->setCalledFunction(Decl);
 139
 140   DEBUG(dbgs() << "New: " << *Retain << "\n");
 141   return true;
 142 }
 143
 144 /// Merge an autorelease with a retain into a fused call.
 145 bool ObjCARCContract::contractAutorelease(
 146     Function &F, Instruction *Autorelease, ARCInstKind Class,
 147     SmallPtrSetImpl<Instruction *> &DependingInstructions,
 148     SmallPtrSetImpl<const BasicBlock *> &Visited) {
 149   const Value *Arg = GetArgRCIdentityRoot(Autorelease);
 150
 151   // Check that there are no instructions between the retain and the autorelease
 152   // (such as an autorelease_pop) which may change the count.
 153   CallInst *Retain = nullptr;
 154   if (Class == ARCInstKind::AutoreleaseRV)
 155     FindDependencies(RetainAutoreleaseRVDep, Arg,
 156                      Autorelease->getParent(), Autorelease,
 157                      DependingInstructions, Visited, PA);
 158   else
 159     FindDependencies(RetainAutoreleaseDep, Arg,
 160                      Autorelease->getParent(), Autorelease,
 161                      DependingInstructions, Visited, PA);
 162
 163   Visited.clear();
 164   if (DependingInstructions.size() != 1) {
 165     DependingInstructions.clear();
 166     return false;
 167   }
 168
 169   Retain = dyn_cast_or_null<CallInst>(*DependingInstructions.begin());
 170   DependingInstructions.clear();
 171
 172   if (!Retain || GetBasicARCInstKind(Retain) != ARCInstKind::Retain ||
 173       GetArgRCIdentityRoot(Retain) != Arg)
 174     return false;
 175
 176   Changed = true;
 177   ++NumPeeps;
 178
 179   DEBUG(dbgs() << "    Fusing retain/autorelease!\n"
 180                   "        Autorelease:" << *Autorelease << "\n"
 181                   "        Retain: " << *Retain << "\n");
 182
 183   Constant *Decl = EP.get(Class == ARCInstKind::AutoreleaseRV
 184                               ? ARCRuntimeEntryPoints::EPT_RetainAutoreleaseRV
 185                               : ARCRuntimeEntryPoints::EPT_RetainAutorelease);
 186   Retain->setCalledFunction(Decl);
 187
 188   DEBUG(dbgs() << "        New RetainAutorelease: " << *Retain << "\n");
 189
 190   EraseInstruction(Autorelease);
 191   return true;
 192 }
 193
 194 static StoreInst *findSafeStoreForStoreStrongContraction(LoadInst *Load,
 195                                                          Instruction *Release,
 196                                                          ProvenanceAnalysis &PA,
 197                                                          AliasAnalysis *AA) {
 198   StoreInst *Store = nullptr;
 199   bool SawRelease = false;
 200
 201   // Get the location associated with Load.
 202   AliasAnalysis::Location Loc = AA->getLocation(Load);
 203
 204   // Walk down to find the store and the release, which may be in either order.
 205   for (auto I = std::next(BasicBlock::iterator(Load)),
 206             E = Load->getParent()->end();
 207        I != E; ++I) {
 208     // If we found the store we were looking for and saw the release,
 209     // break. There is no more work to be done.
 210     if (Store && SawRelease)
 211       break;
 212
 213     // Now we know that we have not seen either the store or the release. If I
 214     // is the the release, mark that we saw the release and continue.
 215     Instruction *Inst = &*I;
 216     if (Inst == Release) {
 217       SawRelease = true;
 218       continue;
 219     }
 220
 221     // Otherwise, we check if Inst is a "good" store. Grab the instruction class
 222     // of Inst.
 223     ARCInstKind Class = GetBasicARCInstKind(Inst);
 224
 225     // If Inst is an unrelated retain, we don't care about it.
 226     //
 227     // TODO: This is one area where the optimization could be made more
 228     // aggressive.
 229     if (IsRetain(Class))
 230       continue;
 231
 232     // If we have seen the store, but not the release...
 233     if (Store) {
 234       // We need to make sure that it is safe to move the release from its
 235       // current position to the store. This implies proving that any
 236       // instruction in between Store and the Release conservatively can not use
 237       // the RCIdentityRoot of Release. If we can prove we can ignore Inst, so
 238       // continue...
 239       if (!CanUse(Inst, Load, PA, Class)) {
 240         continue;
 241       }
 242
 243       // Otherwise, be conservative and return nullptr.
 244       return nullptr;
 245     }
 246
 247     // Ok, now we know we have not seen a store yet. See if Inst can write to
 248     // our load location, if it can not, just ignore the instruction.
 249     if (!(AA->getModRefInfo(Inst, Loc) & AliasAnalysis::Mod))
 250       continue;
 251
 252     Store = dyn_cast<StoreInst>(Inst);
 253
 254     // If Inst can, then check if Inst is a simple store. If Inst is not a
 255     // store or a store that is not simple, then we have some we do not
 256     // understand writing to this memory implying we can not move the load
 257     // over the write to any subsequent store that we may find.
 258     if (!Store || !Store->isSimple())
 259       return nullptr;
 260
 261     // Then make sure that the pointer we are storing to is Ptr. If so, we
 262     // found our Store!
 263     if (Store->getPointerOperand() == Loc.Ptr)
 264       continue;
 265
 266     // Otherwise, we have an unknown store to some other ptr that clobbers
 267     // Loc.Ptr. Bail!
 268     return nullptr;
 269   }
 270
 271   // If we did not find the store or did not see the release, fail.
 272   if (!Store || !SawRelease)
 273     return nullptr;
 274
 275   // We succeeded!
 276   return Store;
 277 }
 278
 279 static Instruction *
 280 findRetainForStoreStrongContraction(Value *New, StoreInst *Store,
 281                                     Instruction *Release,
 282                                     ProvenanceAnalysis &PA) {
 283   // Walk up from the Store to find the retain.
 284   BasicBlock::iterator I = Store;
 285   BasicBlock::iterator Begin = Store->getParent()->begin();
 286   while (I != Begin && GetBasicARCInstKind(I) != ARCInstKind::Retain) {
 287     Instruction *Inst = &*I;
 288
 289     // It is only safe to move the retain to the store if we can prove
 290     // conservatively that nothing besides the release can decrement reference
 291     // counts in between the retain and the store.
 292     if (CanDecrementRefCount(Inst, New, PA) && Inst != Release)
 293       return nullptr;
 294     --I;
 295   }
 296   Instruction *Retain = I;
 297   if (GetBasicARCInstKind(Retain) != ARCInstKind::Retain)
 298     return nullptr;
 299   if (GetArgRCIdentityRoot(Retain) != New)
 300     return nullptr;
 301   return Retain;
 302 }
 303
 304 /// Attempt to merge an objc_release with a store, load, and objc_retain to form
 305 /// an objc_storeStrong. An objc_storeStrong:
 306 ///
 307 ///   objc_storeStrong(i8** %old_ptr, i8* new_value)
 308 ///
 309 /// is equivalent to the following IR sequence:
 310 ///
 311 ///   ; Load old value.
 312 ///   %old_value = load i8** %old_ptr               (1)
 313 ///
 314 ///   ; Increment the new value and then release the old value. This must occur
 315 ///   ; in order in case old_value releases new_value in its destructor causing
 316 ///   ; us to potentially have a dangling ptr.
 317 ///   tail call i8* @objc_retain(i8* %new_value)    (2)
 318 ///   tail call void @objc_release(i8* %old_value)  (3)
 319 ///
 320 ///   ; Store the new_value into old_ptr
 321 ///   store i8* %new_value, i8** %old_ptr           (4)
 322 ///
 323 /// The safety of this optimization is based around the following
 324 /// considerations:
 325 ///
 326 ///  1. We are forming the store strong at the store. Thus to perform this
 327 ///     optimization it must be safe to move the retain, load, and release to
 328 ///     (4).
 329 ///  2. We need to make sure that any re-orderings of (1), (2), (3), (4) are
 330 ///     safe.
 331 void ObjCARCContract::tryToContractReleaseIntoStoreStrong(Instruction *Release,
 332                                                           inst_iterator &Iter) {
 333   // See if we are releasing something that we just loaded.
 334   auto *Load = dyn_cast<LoadInst>(GetArgRCIdentityRoot(Release));
 335   if (!Load || !Load->isSimple())
 336     return;
 337
 338   // For now, require everything to be in one basic block.
 339   BasicBlock *BB = Release->getParent();
 340   if (Load->getParent() != BB)
 341     return;
 342
 343   // First scan down the BB from Load, looking for a store of the RCIdentityRoot
 344   // of Load's
 345   StoreInst *Store =
 346       findSafeStoreForStoreStrongContraction(Load, Release, PA, AA);
 347   // If we fail, bail.
 348   if (!Store)
 349     return;
 350
 351   // Then find what new_value's RCIdentity Root is.
 352   Value *New = GetRCIdentityRoot(Store->getValueOperand());
 353
 354   // Then walk up the BB and look for a retain on New without any intervening
 355   // instructions which conservatively might decrement ref counts.
 356   Instruction *Retain =
 357       findRetainForStoreStrongContraction(New, Store, Release, PA);
 358
 359   // If we fail, bail.
 360   if (!Retain)
 361     return;
 362
 363   Changed = true;
 364   ++NumStoreStrongs;
 365
 366   DEBUG(
 367       llvm::dbgs() << "    Contracting retain, release into objc_storeStrong.\n"
 368                    << "        Old:\n"
 369                    << "            Store:   " << *Store << "\n"
 370                    << "            Release: " << *Release << "\n"
 371                    << "            Retain:  " << *Retain << "\n"
 372                    << "            Load:    " << *Load << "\n");
 373
 374   LLVMContext &C = Release->getContext();
 375   Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
 376   Type *I8XX = PointerType::getUnqual(I8X);
 377
 378   Value *Args[] = { Load->getPointerOperand(), New };
 379   if (Args[0]->getType() != I8XX)
 380     Args[0] = new BitCastInst(Args[0], I8XX, "", Store);
 381   if (Args[1]->getType() != I8X)
 382     Args[1] = new BitCastInst(Args[1], I8X, "", Store);
 383   Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_StoreStrong);
 384   CallInst *StoreStrong = CallInst::Create(Decl, Args, "", Store);
 385   StoreStrong->setDoesNotThrow();
 386   StoreStrong->setDebugLoc(Store->getDebugLoc());
 387
 388   // We can't set the tail flag yet, because we haven't yet determined
 389   // whether there are any escaping allocas. Remember this call, so that
 390   // we can set the tail flag once we know it's safe.
 391   StoreStrongCalls.insert(StoreStrong);
 392
 393   DEBUG(llvm::dbgs() << "        New Store Strong: " << *StoreStrong << "\n");
 394
 395   if (&*Iter == Store) ++Iter;
 396   Store->eraseFromParent();
 397   Release->eraseFromParent();
 398   EraseInstruction(Retain);
 399   if (Load->use_empty())
 400     Load->eraseFromParent();
 401 }
 402
 403 bool ObjCARCContract::tryToPeepholeInstruction(
 404   Function &F, Instruction *Inst, inst_iterator &Iter,
 405   SmallPtrSetImpl<Instruction *> &DependingInsts,
 406   SmallPtrSetImpl<const BasicBlock *> &Visited,
 407   bool &TailOkForStoreStrongs) {
 408     // Only these library routines return their argument. In particular,
 409     // objc_retainBlock does not necessarily return its argument.
 410   ARCInstKind Class = GetBasicARCInstKind(Inst);
 411     switch (Class) {
 412     case ARCInstKind::FusedRetainAutorelease:
 413     case ARCInstKind::FusedRetainAutoreleaseRV:
 414       return false;
 415     case ARCInstKind::Autorelease:
 416     case ARCInstKind::AutoreleaseRV:
 417       return contractAutorelease(F, Inst, Class, DependingInsts, Visited);
 418     case ARCInstKind::Retain:
 419       // Attempt to convert retains to retainrvs if they are next to function
 420       // calls.
 421       if (!optimizeRetainCall(F, Inst))
 422         return false;
 423       // If we succeed in our optimization, fall through.
 424       // FALLTHROUGH
 425     case ARCInstKind::RetainRV: {
 426       // If we're compiling for a target which needs a special inline-asm
 427       // marker to do the retainAutoreleasedReturnValue optimization,
 428       // insert it now.
 429       if (!RetainRVMarker)
 430         return false;
 431       BasicBlock::iterator BBI = Inst;
 432       BasicBlock *InstParent = Inst->getParent();
 433
 434       // Step up to see if the call immediately precedes the RetainRV call.
 435       // If it's an invoke, we have to cross a block boundary. And we have
 436       // to carefully dodge no-op instructions.
 437       do {
 438         if (&*BBI == InstParent->begin()) {
 439           BasicBlock *Pred = InstParent->getSinglePredecessor();
 440           if (!Pred)
 441             goto decline_rv_optimization;
 442           BBI = Pred->getTerminator();
 443           break;
 444         }
 445         --BBI;
 446       } while (IsNoopInstruction(BBI));
 447
 448       if (&*BBI == GetArgRCIdentityRoot(Inst)) {
 449         DEBUG(dbgs() << "Adding inline asm marker for "
 450                         "retainAutoreleasedReturnValue optimization.\n");
 451         Changed = true;
 452         InlineAsm *IA =
 453           InlineAsm::get(FunctionType::get(Type::getVoidTy(Inst->getContext()),
 454                                            /*isVarArg=*/false),
 455                          RetainRVMarker->getString(),
 456                          /*Constraints=*/"", /*hasSideEffects=*/true);
 457         CallInst::Create(IA, "", Inst);
 458       }
 459     decline_rv_optimization:
 460       return false;
 461     }
 462     case ARCInstKind::InitWeak: {
 463       // objc_initWeak(p, null) => *p = null
 464       CallInst *CI = cast<CallInst>(Inst);
 465       if (IsNullOrUndef(CI->getArgOperand(1))) {
 466         Value *Null =
 467           ConstantPointerNull::get(cast<PointerType>(CI->getType()));
 468         Changed = true;
 469         new StoreInst(Null, CI->getArgOperand(0), CI);
 470
 471         DEBUG(dbgs() << "OBJCARCContract: Old = " << *CI << "\n"
 472                      << "                 New = " << *Null << "\n");
 473
 474         CI->replaceAllUsesWith(Null);
 475         CI->eraseFromParent();
 476       }
 477       return true;
 478     }
 479     case ARCInstKind::Release:
 480       // Try to form an objc store strong from our release. If we fail, there is
 481       // nothing further to do below, so continue.
 482       tryToContractReleaseIntoStoreStrong(Inst, Iter);
 483       return true;
 484     case ARCInstKind::User:
 485       // Be conservative if the function has any alloca instructions.
 486       // Technically we only care about escaping alloca instructions,
 487       // but this is sufficient to handle some interesting cases.
 488       if (isa<AllocaInst>(Inst))
 489         TailOkForStoreStrongs = false;
 490       return true;
 491     case ARCInstKind::IntrinsicUser:
 492       // Remove calls to @clang.arc.use(...).
 493       Inst->eraseFromParent();
 494       return true;
 495     default:
 496       return true;
 497     }
 498 }
 499
 500 //===----------------------------------------------------------------------===//
 501 //                              Top Level Driver
 502 //===----------------------------------------------------------------------===//
 503
 504 bool ObjCARCContract::runOnFunction(Function &F) {
 505   if (!EnableARCOpts)
 506     return false;
 507
 508   // If nothing in the Module uses ARC, don't do anything.
 509   if (!Run)
 510     return false;
 511
 512   Changed = false;
 513   AA = &getAnalysis<AliasAnalysis>();
 514   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 515
 516   PA.setAA(&getAnalysis<AliasAnalysis>());
 517
 518   DEBUG(llvm::dbgs() << "**** ObjCARC Contract ****\n");
 519
 520   // Track whether it's ok to mark objc_storeStrong calls with the "tail"
 521   // keyword. Be conservative if the function has variadic arguments.
 522   // It seems that functions which "return twice" are also unsafe for the
 523   // "tail" argument, because they are setjmp, which could need to
 524   // return to an earlier stack state.
 525   bool TailOkForStoreStrongs =
 526       !F.isVarArg() && !F.callsFunctionThatReturnsTwice();
 527
 528   // For ObjC library calls which return their argument, replace uses of the
 529   // argument with uses of the call return value, if it dominates the use. This
 530   // reduces register pressure.
 531   SmallPtrSet<Instruction *, 4> DependingInstructions;
 532   SmallPtrSet<const BasicBlock *, 4> Visited;
 533   for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E;) {
 534     Instruction *Inst = &*I++;
 535
 536     DEBUG(dbgs() << "Visiting: " << *Inst << "\n");
 537
 538     // First try to peephole Inst. If there is nothing further we can do in
 539     // terms of undoing objc-arc-expand, process the next inst.
 540     if (tryToPeepholeInstruction(F, Inst, I, DependingInstructions, Visited,
 541                                  TailOkForStoreStrongs))
 542       continue;
 543
 544     // Otherwise, try to undo objc-arc-expand.
 545
 546     // Don't use GetArgRCIdentityRoot because we don't want to look through bitcasts
 547     // and such; to do the replacement, the argument must have type i8*.
 548     Value *Arg = cast<CallInst>(Inst)->getArgOperand(0);
 549
 550     // TODO: Change this to a do-while.
 551     for (;;) {
 552       // If we're compiling bugpointed code, don't get in trouble.
 553       if (!isa<Instruction>(Arg) && !isa<Argument>(Arg))
 554         break;
 555       // Look through the uses of the pointer.
 556       for (Value::use_iterator UI = Arg->use_begin(), UE = Arg->use_end();
 557            UI != UE; ) {
 558         // Increment UI now, because we may unlink its element.
 559         Use &U = *UI++;
 560         unsigned OperandNo = U.getOperandNo();
 561
 562         // If the call's return value dominates a use of the call's argument
 563         // value, rewrite the use to use the return value. We check for
 564         // reachability here because an unreachable call is considered to
 565         // trivially dominate itself, which would lead us to rewriting its
 566         // argument in terms of its return value, which would lead to
 567         // infinite loops in GetArgRCIdentityRoot.
 568         if (DT->isReachableFromEntry(U) && DT->dominates(Inst, U)) {
 569           Changed = true;
 570           Instruction *Replacement = Inst;
 571           Type *UseTy = U.get()->getType();
 572           if (PHINode *PHI = dyn_cast<PHINode>(U.getUser())) {
 573             // For PHI nodes, insert the bitcast in the predecessor block.
 574             unsigned ValNo = PHINode::getIncomingValueNumForOperand(OperandNo);
 575             BasicBlock *BB = PHI->getIncomingBlock(ValNo);
 576             if (Replacement->getType() != UseTy)
 577               Replacement = new BitCastInst(Replacement, UseTy, "",
 578                                             &BB->back());
 579             // While we're here, rewrite all edges for this PHI, rather
 580             // than just one use at a time, to minimize the number of
 581             // bitcasts we emit.
 582             for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i)
 583               if (PHI->getIncomingBlock(i) == BB) {
 584                 // Keep the UI iterator valid.
 585                 if (UI != UE &&
 586                     &PHI->getOperandUse(
 587                         PHINode::getOperandNumForIncomingValue(i)) == &*UI)
 588                   ++UI;
 589                 PHI->setIncomingValue(i, Replacement);
 590               }
 591           } else {
 592             if (Replacement->getType() != UseTy)
 593               Replacement = new BitCastInst(Replacement, UseTy, "",
 594                                             cast<Instruction>(U.getUser()));
 595             U.set(Replacement);
 596           }
 597         }
 598       }
 599
 600       // If Arg is a no-op casted pointer, strip one level of casts and iterate.
 601       if (const BitCastInst *BI = dyn_cast<BitCastInst>(Arg))
 602         Arg = BI->getOperand(0);
 603       else if (isa<GEPOperator>(Arg) &&
 604                cast<GEPOperator>(Arg)->hasAllZeroIndices())
 605         Arg = cast<GEPOperator>(Arg)->getPointerOperand();
 606       else if (isa<GlobalAlias>(Arg) &&
 607                !cast<GlobalAlias>(Arg)->mayBeOverridden())
 608         Arg = cast<GlobalAlias>(Arg)->getAliasee();
 609       else
 610         break;
 611     }
 612   }
 613
 614   // If this function has no escaping allocas or suspicious vararg usage,
 615   // objc_storeStrong calls can be marked with the "tail" keyword.
 616   if (TailOkForStoreStrongs)
 617     for (CallInst *CI : StoreStrongCalls)
 618       CI->setTailCall();
 619   StoreStrongCalls.clear();
 620
 621   return Changed;
 622 }
 623
 624 //===----------------------------------------------------------------------===//
 625 //                             Misc Pass Manager
 626 //===----------------------------------------------------------------------===//
 627
 628 char ObjCARCContract::ID = 0;
 629 INITIALIZE_PASS_BEGIN(ObjCARCContract, "objc-arc-contract",
 630                       "ObjC ARC contraction", false, false)
 631 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
 632 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 633 INITIALIZE_PASS_END(ObjCARCContract, "objc-arc-contract",
 634                     "ObjC ARC contraction", false, false)
 635
 636 void ObjCARCContract::getAnalysisUsage(AnalysisUsage &AU) const {
 637   AU.addRequired<AliasAnalysis>();
 638   AU.addRequired<DominatorTreeWrapperPass>();
 639   AU.setPreservesCFG();
 640 }
 641
 642 Pass *llvm::createObjCARCContractPass() { return new ObjCARCContract(); }
 643
 644 bool ObjCARCContract::doInitialization(Module &M) {
 645   // If nothing in the Module uses ARC, don't do anything.
 646   Run = ModuleHasARC(M);
 647   if (!Run)
 648     return false;
 649
 650   EP.Initialize(&M);
 651
 652   // Initialize RetainRVMarker.
 653   RetainRVMarker = nullptr;
 654   if (NamedMDNode *NMD =
 655           M.getNamedMetadata("clang.arc.retainAutoreleasedReturnValueMarker"))
 656     if (NMD->getNumOperands() == 1) {
 657       const MDNode *N = NMD->getOperand(0);
 658       if (N->getNumOperands() == 1)
 659         if (const MDString *S = dyn_cast<MDString>(N->getOperand(0)))
 660           RetainRVMarker = S;
 661     }
 662
 663   return false;
 664 }