LLVM  mainline
ObjCARCContract.cpp
Go to the documentation of this file.
00001 //===- ObjCARCContract.cpp - ObjC ARC Optimization ------------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 /// \file
00010 /// This file defines late ObjC ARC optimizations. ARC stands for Automatic
00011 /// Reference Counting and is a system for managing reference counts for objects
00012 /// in Objective C.
00013 ///
00014 /// This specific file mainly deals with ``contracting'' multiple lower level
00015 /// operations into singular higher level operations through pattern matching.
00016 ///
00017 /// WARNING: This file knows about certain library functions. It recognizes them
00018 /// by name, and hardwires knowledge of their semantics.
00019 ///
00020 /// WARNING: This file knows about how certain Objective-C library functions are
00021 /// used. Naive LLVM IR transformations which would otherwise be
00022 /// behavior-preserving may break these assumptions.
00023 ///
00024 //===----------------------------------------------------------------------===//
00025 
00026 // TODO: ObjCARCContract could insert PHI nodes when uses aren't
00027 // dominated by single calls.
00028 
00029 #include "ObjCARC.h"
00030 #include "ARCRuntimeEntryPoints.h"
00031 #include "DependencyAnalysis.h"
00032 #include "ProvenanceAnalysis.h"
00033 #include "llvm/ADT/Statistic.h"
00034 #include "llvm/IR/Dominators.h"
00035 #include "llvm/IR/InlineAsm.h"
00036 #include "llvm/IR/Operator.h"
00037 #include "llvm/Support/Debug.h"
00038 #include "llvm/Support/raw_ostream.h"
00039 
00040 using namespace llvm;
00041 using namespace llvm::objcarc;
00042 
00043 #define DEBUG_TYPE "objc-arc-contract"
00044 
00045 STATISTIC(NumPeeps,       "Number of calls peephole-optimized");
00046 STATISTIC(NumStoreStrongs, "Number objc_storeStrong calls formed");
00047 
00048 //===----------------------------------------------------------------------===//
00049 //                                Declarations
00050 //===----------------------------------------------------------------------===//
00051 
00052 namespace {
00053   /// \brief Late ARC optimizations
00054   ///
00055   /// These change the IR in a way that makes it difficult to be analyzed by
00056   /// ObjCARCOpt, so it's run late.
00057   class ObjCARCContract : public FunctionPass {
00058     bool Changed;
00059     AliasAnalysis *AA;
00060     DominatorTree *DT;
00061     ProvenanceAnalysis PA;
00062     ARCRuntimeEntryPoints EP;
00063 
00064     /// A flag indicating whether this optimization pass should run.
00065     bool Run;
00066 
00067     /// The inline asm string to insert between calls and RetainRV calls to make
00068     /// the optimization work on targets which need it.
00069     const MDString *RetainRVMarker;
00070 
00071     /// The set of inserted objc_storeStrong calls. If at the end of walking the
00072     /// function we have found no alloca instructions, these calls can be marked
00073     /// "tail".
00074     SmallPtrSet<CallInst *, 8> StoreStrongCalls;
00075 
00076     /// Returns true if we eliminated Inst.
00077     bool tryToPeepholeInstruction(Function &F, Instruction *Inst,
00078                                   inst_iterator &Iter,
00079                                   SmallPtrSetImpl<Instruction *> &DepInsts,
00080                                   SmallPtrSetImpl<const BasicBlock *> &Visited,
00081                                   bool &TailOkForStoreStrong);
00082 
00083     bool optimizeRetainCall(Function &F, Instruction *Retain);
00084 
00085     bool
00086     contractAutorelease(Function &F, Instruction *Autorelease,
00087                         ARCInstKind Class,
00088                         SmallPtrSetImpl<Instruction *> &DependingInstructions,
00089                         SmallPtrSetImpl<const BasicBlock *> &Visited);
00090 
00091     void tryToContractReleaseIntoStoreStrong(Instruction *Release,
00092                                              inst_iterator &Iter);
00093 
00094     void getAnalysisUsage(AnalysisUsage &AU) const override;
00095     bool doInitialization(Module &M) override;
00096     bool runOnFunction(Function &F) override;
00097 
00098   public:
00099     static char ID;
00100     ObjCARCContract() : FunctionPass(ID) {
00101       initializeObjCARCContractPass(*PassRegistry::getPassRegistry());
00102     }
00103   };
00104 }
00105 
00106 //===----------------------------------------------------------------------===//
00107 //                               Implementation
00108 //===----------------------------------------------------------------------===//
00109 
00110 /// Turn objc_retain into objc_retainAutoreleasedReturnValue if the operand is a
00111 /// return value. We do this late so we do not disrupt the dataflow analysis in
00112 /// ObjCARCOpt.
00113 bool ObjCARCContract::optimizeRetainCall(Function &F, Instruction *Retain) {
00114   ImmutableCallSite CS(GetArgRCIdentityRoot(Retain));
00115   const Instruction *Call = CS.getInstruction();
00116   if (!Call)
00117     return false;
00118   if (Call->getParent() != Retain->getParent())
00119     return false;
00120 
00121   // Check that the call is next to the retain.
00122   BasicBlock::const_iterator I = Call;
00123   ++I;
00124   while (IsNoopInstruction(I)) ++I;
00125   if (&*I != Retain)
00126     return false;
00127 
00128   // Turn it to an objc_retainAutoreleasedReturnValue.
00129   Changed = true;
00130   ++NumPeeps;
00131 
00132   DEBUG(dbgs() << "Transforming objc_retain => "
00133                   "objc_retainAutoreleasedReturnValue since the operand is a "
00134                   "return value.\nOld: "<< *Retain << "\n");
00135 
00136   // We do not have to worry about tail calls/does not throw since
00137   // retain/retainRV have the same properties.
00138   Constant *Decl = EP.get(ARCRuntimeEntryPointKind::RetainRV);
00139   cast<CallInst>(Retain)->setCalledFunction(Decl);
00140 
00141   DEBUG(dbgs() << "New: " << *Retain << "\n");
00142   return true;
00143 }
00144 
00145 /// Merge an autorelease with a retain into a fused call.
00146 bool ObjCARCContract::contractAutorelease(
00147     Function &F, Instruction *Autorelease, ARCInstKind Class,
00148     SmallPtrSetImpl<Instruction *> &DependingInstructions,
00149     SmallPtrSetImpl<const BasicBlock *> &Visited) {
00150   const Value *Arg = GetArgRCIdentityRoot(Autorelease);
00151 
00152   // Check that there are no instructions between the retain and the autorelease
00153   // (such as an autorelease_pop) which may change the count.
00154   CallInst *Retain = nullptr;
00155   if (Class == ARCInstKind::AutoreleaseRV)
00156     FindDependencies(RetainAutoreleaseRVDep, Arg,
00157                      Autorelease->getParent(), Autorelease,
00158                      DependingInstructions, Visited, PA);
00159   else
00160     FindDependencies(RetainAutoreleaseDep, Arg,
00161                      Autorelease->getParent(), Autorelease,
00162                      DependingInstructions, Visited, PA);
00163 
00164   Visited.clear();
00165   if (DependingInstructions.size() != 1) {
00166     DependingInstructions.clear();
00167     return false;
00168   }
00169 
00170   Retain = dyn_cast_or_null<CallInst>(*DependingInstructions.begin());
00171   DependingInstructions.clear();
00172 
00173   if (!Retain || GetBasicARCInstKind(Retain) != ARCInstKind::Retain ||
00174       GetArgRCIdentityRoot(Retain) != Arg)
00175     return false;
00176 
00177   Changed = true;
00178   ++NumPeeps;
00179 
00180   DEBUG(dbgs() << "    Fusing retain/autorelease!\n"
00181                   "        Autorelease:" << *Autorelease << "\n"
00182                   "        Retain: " << *Retain << "\n");
00183 
00184   Constant *Decl = EP.get(Class == ARCInstKind::AutoreleaseRV
00185                               ? ARCRuntimeEntryPointKind::RetainAutoreleaseRV
00186                               : ARCRuntimeEntryPointKind::RetainAutorelease);
00187   Retain->setCalledFunction(Decl);
00188 
00189   DEBUG(dbgs() << "        New RetainAutorelease: " << *Retain << "\n");
00190 
00191   EraseInstruction(Autorelease);
00192   return true;
00193 }
00194 
00195 static StoreInst *findSafeStoreForStoreStrongContraction(LoadInst *Load,
00196                                                          Instruction *Release,
00197                                                          ProvenanceAnalysis &PA,
00198                                                          AliasAnalysis *AA) {
00199   StoreInst *Store = nullptr;
00200   bool SawRelease = false;
00201 
00202   // Get the location associated with Load.
00203   AliasAnalysis::Location Loc = AA->getLocation(Load);
00204 
00205   // Walk down to find the store and the release, which may be in either order.
00206   for (auto I = std::next(BasicBlock::iterator(Load)),
00207             E = Load->getParent()->end();
00208        I != E; ++I) {
00209     // If we found the store we were looking for and saw the release,
00210     // break. There is no more work to be done.
00211     if (Store && SawRelease)
00212       break;
00213 
00214     // Now we know that we have not seen either the store or the release. If I
00215     // is the the release, mark that we saw the release and continue.
00216     Instruction *Inst = &*I;
00217     if (Inst == Release) {
00218       SawRelease = true;
00219       continue;
00220     }
00221 
00222     // Otherwise, we check if Inst is a "good" store. Grab the instruction class
00223     // of Inst.
00224     ARCInstKind Class = GetBasicARCInstKind(Inst);
00225 
00226     // If Inst is an unrelated retain, we don't care about it.
00227     //
00228     // TODO: This is one area where the optimization could be made more
00229     // aggressive.
00230     if (IsRetain(Class))
00231       continue;
00232 
00233     // If we have seen the store, but not the release...
00234     if (Store) {
00235       // We need to make sure that it is safe to move the release from its
00236       // current position to the store. This implies proving that any
00237       // instruction in between Store and the Release conservatively can not use
00238       // the RCIdentityRoot of Release. If we can prove we can ignore Inst, so
00239       // continue...
00240       if (!CanUse(Inst, Load, PA, Class)) {
00241         continue;
00242       }
00243 
00244       // Otherwise, be conservative and return nullptr.
00245       return nullptr;
00246     }
00247 
00248     // Ok, now we know we have not seen a store yet. See if Inst can write to
00249     // our load location, if it can not, just ignore the instruction.
00250     if (!(AA->getModRefInfo(Inst, Loc) & AliasAnalysis::Mod))
00251       continue;
00252 
00253     Store = dyn_cast<StoreInst>(Inst);
00254 
00255     // If Inst can, then check if Inst is a simple store. If Inst is not a
00256     // store or a store that is not simple, then we have some we do not
00257     // understand writing to this memory implying we can not move the load
00258     // over the write to any subsequent store that we may find.
00259     if (!Store || !Store->isSimple())
00260       return nullptr;
00261 
00262     // Then make sure that the pointer we are storing to is Ptr. If so, we
00263     // found our Store!
00264     if (Store->getPointerOperand() == Loc.Ptr)
00265       continue;
00266 
00267     // Otherwise, we have an unknown store to some other ptr that clobbers
00268     // Loc.Ptr. Bail!
00269     return nullptr;
00270   }
00271 
00272   // If we did not find the store or did not see the release, fail.
00273   if (!Store || !SawRelease)
00274     return nullptr;
00275 
00276   // We succeeded!
00277   return Store;
00278 }
00279 
00280 static Instruction *
00281 findRetainForStoreStrongContraction(Value *New, StoreInst *Store,
00282                                     Instruction *Release,
00283                                     ProvenanceAnalysis &PA) {
00284   // Walk up from the Store to find the retain.
00285   BasicBlock::iterator I = Store;
00286   BasicBlock::iterator Begin = Store->getParent()->begin();
00287   while (I != Begin && GetBasicARCInstKind(I) != ARCInstKind::Retain) {
00288     Instruction *Inst = &*I;
00289 
00290     // It is only safe to move the retain to the store if we can prove
00291     // conservatively that nothing besides the release can decrement reference
00292     // counts in between the retain and the store.
00293     if (CanDecrementRefCount(Inst, New, PA) && Inst != Release)
00294       return nullptr;
00295     --I;
00296   }
00297   Instruction *Retain = I;
00298   if (GetBasicARCInstKind(Retain) != ARCInstKind::Retain)
00299     return nullptr;
00300   if (GetArgRCIdentityRoot(Retain) != New)
00301     return nullptr;
00302   return Retain;
00303 }
00304 
00305 /// Attempt to merge an objc_release with a store, load, and objc_retain to form
00306 /// an objc_storeStrong. An objc_storeStrong:
00307 ///
00308 ///   objc_storeStrong(i8** %old_ptr, i8* new_value)
00309 ///
00310 /// is equivalent to the following IR sequence:
00311 ///
00312 ///   ; Load old value.
00313 ///   %old_value = load i8** %old_ptr               (1)
00314 ///
00315 ///   ; Increment the new value and then release the old value. This must occur
00316 ///   ; in order in case old_value releases new_value in its destructor causing
00317 ///   ; us to potentially have a dangling ptr.
00318 ///   tail call i8* @objc_retain(i8* %new_value)    (2)
00319 ///   tail call void @objc_release(i8* %old_value)  (3)
00320 ///
00321 ///   ; Store the new_value into old_ptr
00322 ///   store i8* %new_value, i8** %old_ptr           (4)
00323 ///
00324 /// The safety of this optimization is based around the following
00325 /// considerations:
00326 ///
00327 ///  1. We are forming the store strong at the store. Thus to perform this
00328 ///     optimization it must be safe to move the retain, load, and release to
00329 ///     (4).
00330 ///  2. We need to make sure that any re-orderings of (1), (2), (3), (4) are
00331 ///     safe.
00332 void ObjCARCContract::tryToContractReleaseIntoStoreStrong(Instruction *Release,
00333                                                           inst_iterator &Iter) {
00334   // See if we are releasing something that we just loaded.
00335   auto *Load = dyn_cast<LoadInst>(GetArgRCIdentityRoot(Release));
00336   if (!Load || !Load->isSimple())
00337     return;
00338 
00339   // For now, require everything to be in one basic block.
00340   BasicBlock *BB = Release->getParent();
00341   if (Load->getParent() != BB)
00342     return;
00343 
00344   // First scan down the BB from Load, looking for a store of the RCIdentityRoot
00345   // of Load's
00346   StoreInst *Store =
00347       findSafeStoreForStoreStrongContraction(Load, Release, PA, AA);
00348   // If we fail, bail.
00349   if (!Store)
00350     return;
00351 
00352   // Then find what new_value's RCIdentity Root is.
00353   Value *New = GetRCIdentityRoot(Store->getValueOperand());
00354 
00355   // Then walk up the BB and look for a retain on New without any intervening
00356   // instructions which conservatively might decrement ref counts.
00357   Instruction *Retain =
00358       findRetainForStoreStrongContraction(New, Store, Release, PA);
00359 
00360   // If we fail, bail.
00361   if (!Retain)
00362     return;
00363 
00364   Changed = true;
00365   ++NumStoreStrongs;
00366 
00367   DEBUG(
00368       llvm::dbgs() << "    Contracting retain, release into objc_storeStrong.\n"
00369                    << "        Old:\n"
00370                    << "            Store:   " << *Store << "\n"
00371                    << "            Release: " << *Release << "\n"
00372                    << "            Retain:  " << *Retain << "\n"
00373                    << "            Load:    " << *Load << "\n");
00374 
00375   LLVMContext &C = Release->getContext();
00376   Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
00377   Type *I8XX = PointerType::getUnqual(I8X);
00378 
00379   Value *Args[] = { Load->getPointerOperand(), New };
00380   if (Args[0]->getType() != I8XX)
00381     Args[0] = new BitCastInst(Args[0], I8XX, "", Store);
00382   if (Args[1]->getType() != I8X)
00383     Args[1] = new BitCastInst(Args[1], I8X, "", Store);
00384   Constant *Decl = EP.get(ARCRuntimeEntryPointKind::StoreStrong);
00385   CallInst *StoreStrong = CallInst::Create(Decl, Args, "", Store);
00386   StoreStrong->setDoesNotThrow();
00387   StoreStrong->setDebugLoc(Store->getDebugLoc());
00388 
00389   // We can't set the tail flag yet, because we haven't yet determined
00390   // whether there are any escaping allocas. Remember this call, so that
00391   // we can set the tail flag once we know it's safe.
00392   StoreStrongCalls.insert(StoreStrong);
00393 
00394   DEBUG(llvm::dbgs() << "        New Store Strong: " << *StoreStrong << "\n");
00395 
00396   if (&*Iter == Store) ++Iter;
00397   Store->eraseFromParent();
00398   Release->eraseFromParent();
00399   EraseInstruction(Retain);
00400   if (Load->use_empty())
00401     Load->eraseFromParent();
00402 }
00403 
00404 bool ObjCARCContract::tryToPeepholeInstruction(
00405   Function &F, Instruction *Inst, inst_iterator &Iter,
00406   SmallPtrSetImpl<Instruction *> &DependingInsts,
00407   SmallPtrSetImpl<const BasicBlock *> &Visited,
00408   bool &TailOkForStoreStrongs) {
00409     // Only these library routines return their argument. In particular,
00410     // objc_retainBlock does not necessarily return its argument.
00411   ARCInstKind Class = GetBasicARCInstKind(Inst);
00412     switch (Class) {
00413     case ARCInstKind::FusedRetainAutorelease:
00414     case ARCInstKind::FusedRetainAutoreleaseRV:
00415       return false;
00416     case ARCInstKind::Autorelease:
00417     case ARCInstKind::AutoreleaseRV:
00418       return contractAutorelease(F, Inst, Class, DependingInsts, Visited);
00419     case ARCInstKind::Retain:
00420       // Attempt to convert retains to retainrvs if they are next to function
00421       // calls.
00422       if (!optimizeRetainCall(F, Inst))
00423         return false;
00424       // If we succeed in our optimization, fall through.
00425       // FALLTHROUGH
00426     case ARCInstKind::RetainRV: {
00427       // If we're compiling for a target which needs a special inline-asm
00428       // marker to do the retainAutoreleasedReturnValue optimization,
00429       // insert it now.
00430       if (!RetainRVMarker)
00431         return false;
00432       BasicBlock::iterator BBI = Inst;
00433       BasicBlock *InstParent = Inst->getParent();
00434 
00435       // Step up to see if the call immediately precedes the RetainRV call.
00436       // If it's an invoke, we have to cross a block boundary. And we have
00437       // to carefully dodge no-op instructions.
00438       do {
00439         if (&*BBI == InstParent->begin()) {
00440           BasicBlock *Pred = InstParent->getSinglePredecessor();
00441           if (!Pred)
00442             goto decline_rv_optimization;
00443           BBI = Pred->getTerminator();
00444           break;
00445         }
00446         --BBI;
00447       } while (IsNoopInstruction(BBI));
00448 
00449       if (&*BBI == GetArgRCIdentityRoot(Inst)) {
00450         DEBUG(dbgs() << "Adding inline asm marker for "
00451                         "retainAutoreleasedReturnValue optimization.\n");
00452         Changed = true;
00453         InlineAsm *IA =
00454           InlineAsm::get(FunctionType::get(Type::getVoidTy(Inst->getContext()),
00455                                            /*isVarArg=*/false),
00456                          RetainRVMarker->getString(),
00457                          /*Constraints=*/"", /*hasSideEffects=*/true);
00458         CallInst::Create(IA, "", Inst);
00459       }
00460     decline_rv_optimization:
00461       return false;
00462     }
00463     case ARCInstKind::InitWeak: {
00464       // objc_initWeak(p, null) => *p = null
00465       CallInst *CI = cast<CallInst>(Inst);
00466       if (IsNullOrUndef(CI->getArgOperand(1))) {
00467         Value *Null =
00468           ConstantPointerNull::get(cast<PointerType>(CI->getType()));
00469         Changed = true;
00470         new StoreInst(Null, CI->getArgOperand(0), CI);
00471 
00472         DEBUG(dbgs() << "OBJCARCContract: Old = " << *CI << "\n"
00473                      << "                 New = " << *Null << "\n");
00474 
00475         CI->replaceAllUsesWith(Null);
00476         CI->eraseFromParent();
00477       }
00478       return true;
00479     }
00480     case ARCInstKind::Release:
00481       // Try to form an objc store strong from our release. If we fail, there is
00482       // nothing further to do below, so continue.
00483       tryToContractReleaseIntoStoreStrong(Inst, Iter);
00484       return true;
00485     case ARCInstKind::User:
00486       // Be conservative if the function has any alloca instructions.
00487       // Technically we only care about escaping alloca instructions,
00488       // but this is sufficient to handle some interesting cases.
00489       if (isa<AllocaInst>(Inst))
00490         TailOkForStoreStrongs = false;
00491       return true;
00492     case ARCInstKind::IntrinsicUser:
00493       // Remove calls to @clang.arc.use(...).
00494       Inst->eraseFromParent();
00495       return true;
00496     default:
00497       return true;
00498     }
00499 }
00500 
00501 //===----------------------------------------------------------------------===//
00502 //                              Top Level Driver
00503 //===----------------------------------------------------------------------===//
00504 
00505 bool ObjCARCContract::runOnFunction(Function &F) {
00506   if (!EnableARCOpts)
00507     return false;
00508 
00509   // If nothing in the Module uses ARC, don't do anything.
00510   if (!Run)
00511     return false;
00512 
00513   Changed = false;
00514   AA = &getAnalysis<AliasAnalysis>();
00515   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
00516 
00517   PA.setAA(&getAnalysis<AliasAnalysis>());
00518 
00519   DEBUG(llvm::dbgs() << "**** ObjCARC Contract ****\n");
00520 
00521   // Track whether it's ok to mark objc_storeStrong calls with the "tail"
00522   // keyword. Be conservative if the function has variadic arguments.
00523   // It seems that functions which "return twice" are also unsafe for the
00524   // "tail" argument, because they are setjmp, which could need to
00525   // return to an earlier stack state.
00526   bool TailOkForStoreStrongs =
00527       !F.isVarArg() && !F.callsFunctionThatReturnsTwice();
00528 
00529   // For ObjC library calls which return their argument, replace uses of the
00530   // argument with uses of the call return value, if it dominates the use. This
00531   // reduces register pressure.
00532   SmallPtrSet<Instruction *, 4> DependingInstructions;
00533   SmallPtrSet<const BasicBlock *, 4> Visited;
00534   for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E;) {
00535     Instruction *Inst = &*I++;
00536 
00537     DEBUG(dbgs() << "Visiting: " << *Inst << "\n");
00538 
00539     // First try to peephole Inst. If there is nothing further we can do in
00540     // terms of undoing objc-arc-expand, process the next inst.
00541     if (tryToPeepholeInstruction(F, Inst, I, DependingInstructions, Visited,
00542                                  TailOkForStoreStrongs))
00543       continue;
00544 
00545     // Otherwise, try to undo objc-arc-expand.
00546 
00547     // Don't use GetArgRCIdentityRoot because we don't want to look through bitcasts
00548     // and such; to do the replacement, the argument must have type i8*.
00549     Value *Arg = cast<CallInst>(Inst)->getArgOperand(0);
00550 
00551     // TODO: Change this to a do-while.
00552     for (;;) {
00553       // If we're compiling bugpointed code, don't get in trouble.
00554       if (!isa<Instruction>(Arg) && !isa<Argument>(Arg))
00555         break;
00556       // Look through the uses of the pointer.
00557       for (Value::use_iterator UI = Arg->use_begin(), UE = Arg->use_end();
00558            UI != UE; ) {
00559         // Increment UI now, because we may unlink its element.
00560         Use &U = *UI++;
00561         unsigned OperandNo = U.getOperandNo();
00562 
00563         // If the call's return value dominates a use of the call's argument
00564         // value, rewrite the use to use the return value. We check for
00565         // reachability here because an unreachable call is considered to
00566         // trivially dominate itself, which would lead us to rewriting its
00567         // argument in terms of its return value, which would lead to
00568         // infinite loops in GetArgRCIdentityRoot.
00569         if (DT->isReachableFromEntry(U) && DT->dominates(Inst, U)) {
00570           Changed = true;
00571           Instruction *Replacement = Inst;
00572           Type *UseTy = U.get()->getType();
00573           if (PHINode *PHI = dyn_cast<PHINode>(U.getUser())) {
00574             // For PHI nodes, insert the bitcast in the predecessor block.
00575             unsigned ValNo = PHINode::getIncomingValueNumForOperand(OperandNo);
00576             BasicBlock *BB = PHI->getIncomingBlock(ValNo);
00577             if (Replacement->getType() != UseTy)
00578               Replacement = new BitCastInst(Replacement, UseTy, "",
00579                                             &BB->back());
00580             // While we're here, rewrite all edges for this PHI, rather
00581             // than just one use at a time, to minimize the number of
00582             // bitcasts we emit.
00583             for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i)
00584               if (PHI->getIncomingBlock(i) == BB) {
00585                 // Keep the UI iterator valid.
00586                 if (UI != UE &&
00587                     &PHI->getOperandUse(
00588                         PHINode::getOperandNumForIncomingValue(i)) == &*UI)
00589                   ++UI;
00590                 PHI->setIncomingValue(i, Replacement);
00591               }
00592           } else {
00593             if (Replacement->getType() != UseTy)
00594               Replacement = new BitCastInst(Replacement, UseTy, "",
00595                                             cast<Instruction>(U.getUser()));
00596             U.set(Replacement);
00597           }
00598         }
00599       }
00600 
00601       // If Arg is a no-op casted pointer, strip one level of casts and iterate.
00602       if (const BitCastInst *BI = dyn_cast<BitCastInst>(Arg))
00603         Arg = BI->getOperand(0);
00604       else if (isa<GEPOperator>(Arg) &&
00605                cast<GEPOperator>(Arg)->hasAllZeroIndices())
00606         Arg = cast<GEPOperator>(Arg)->getPointerOperand();
00607       else if (isa<GlobalAlias>(Arg) &&
00608                !cast<GlobalAlias>(Arg)->mayBeOverridden())
00609         Arg = cast<GlobalAlias>(Arg)->getAliasee();
00610       else
00611         break;
00612     }
00613   }
00614 
00615   // If this function has no escaping allocas or suspicious vararg usage,
00616   // objc_storeStrong calls can be marked with the "tail" keyword.
00617   if (TailOkForStoreStrongs)
00618     for (CallInst *CI : StoreStrongCalls)
00619       CI->setTailCall();
00620   StoreStrongCalls.clear();
00621 
00622   return Changed;
00623 }
00624 
00625 //===----------------------------------------------------------------------===//
00626 //                             Misc Pass Manager
00627 //===----------------------------------------------------------------------===//
00628 
00629 char ObjCARCContract::ID = 0;
00630 INITIALIZE_PASS_BEGIN(ObjCARCContract, "objc-arc-contract",
00631                       "ObjC ARC contraction", false, false)
00632 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
00633 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
00634 INITIALIZE_PASS_END(ObjCARCContract, "objc-arc-contract",
00635                     "ObjC ARC contraction", false, false)
00636 
00637 void ObjCARCContract::getAnalysisUsage(AnalysisUsage &AU) const {
00638   AU.addRequired<AliasAnalysis>();
00639   AU.addRequired<DominatorTreeWrapperPass>();
00640   AU.setPreservesCFG();
00641 }
00642 
00643 Pass *llvm::createObjCARCContractPass() { return new ObjCARCContract(); }
00644 
00645 bool ObjCARCContract::doInitialization(Module &M) {
00646   // If nothing in the Module uses ARC, don't do anything.
00647   Run = ModuleHasARC(M);
00648   if (!Run)
00649     return false;
00650 
00651   EP.init(&M);
00652 
00653   // Initialize RetainRVMarker.
00654   RetainRVMarker = nullptr;
00655   if (NamedMDNode *NMD =
00656           M.getNamedMetadata("clang.arc.retainAutoreleasedReturnValueMarker"))
00657     if (NMD->getNumOperands() == 1) {
00658       const MDNode *N = NMD->getOperand(0);
00659       if (N->getNumOperands() == 1)
00660         if (const MDString *S = dyn_cast<MDString>(N->getOperand(0)))
00661           RetainRVMarker = S;
00662     }
00663 
00664   return false;
00665 }