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