llvm/lib/Transforms/ObjCARC/ObjCARCContract.cpp

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