LLVM API Documentation

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 #define DEBUG_TYPE "objc-arc-contract"
00030 #include "ObjCARC.h"
00031 #include "ARCRuntimeEntryPoints.h"
00032 #include "DependencyAnalysis.h"
00033 #include "ProvenanceAnalysis.h"
00034 #include "llvm/ADT/Statistic.h"
00035 #include "llvm/IR/Dominators.h"
00036 #include "llvm/IR/InlineAsm.h"
00037 #include "llvm/IR/Operator.h"
00038 #include "llvm/Support/Debug.h"
00039 
00040 using namespace llvm;
00041 using namespace llvm::objcarc;
00042 
00043 STATISTIC(NumPeeps,       "Number of calls peephole-optimized");
00044 STATISTIC(NumStoreStrongs, "Number objc_storeStrong calls formed");
00045 
00046 namespace {
00047   /// \brief Late ARC optimizations
00048   ///
00049   /// These change the IR in a way that makes it difficult to be analyzed by
00050   /// ObjCARCOpt, so it's run late.
00051   class ObjCARCContract : public FunctionPass {
00052     bool Changed;
00053     AliasAnalysis *AA;
00054     DominatorTree *DT;
00055     ProvenanceAnalysis PA;
00056     ARCRuntimeEntryPoints EP;
00057 
00058     /// A flag indicating whether this optimization pass should run.
00059     bool Run;
00060 
00061     /// The inline asm string to insert between calls and RetainRV calls to make
00062     /// the optimization work on targets which need it.
00063     const MDString *RetainRVMarker;
00064 
00065     /// The set of inserted objc_storeStrong calls. If at the end of walking the
00066     /// function we have found no alloca instructions, these calls can be marked
00067     /// "tail".
00068     SmallPtrSet<CallInst *, 8> StoreStrongCalls;
00069 
00070     bool OptimizeRetainCall(Function &F, Instruction *Retain);
00071 
00072     bool ContractAutorelease(Function &F, Instruction *Autorelease,
00073                              InstructionClass Class,
00074                              SmallPtrSet<Instruction *, 4>
00075                                &DependingInstructions,
00076                              SmallPtrSet<const BasicBlock *, 4>
00077                                &Visited);
00078 
00079     void ContractRelease(Instruction *Release,
00080                          inst_iterator &Iter);
00081 
00082     void getAnalysisUsage(AnalysisUsage &AU) const override;
00083     bool doInitialization(Module &M) override;
00084     bool runOnFunction(Function &F) override;
00085 
00086   public:
00087     static char ID;
00088     ObjCARCContract() : FunctionPass(ID) {
00089       initializeObjCARCContractPass(*PassRegistry::getPassRegistry());
00090     }
00091   };
00092 }
00093 
00094 char ObjCARCContract::ID = 0;
00095 INITIALIZE_PASS_BEGIN(ObjCARCContract,
00096                       "objc-arc-contract", "ObjC ARC contraction", false, false)
00097 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
00098 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
00099 INITIALIZE_PASS_END(ObjCARCContract,
00100                     "objc-arc-contract", "ObjC ARC contraction", false, false)
00101 
00102 Pass *llvm::createObjCARCContractPass() {
00103   return new ObjCARCContract();
00104 }
00105 
00106 void ObjCARCContract::getAnalysisUsage(AnalysisUsage &AU) const {
00107   AU.addRequired<AliasAnalysis>();
00108   AU.addRequired<DominatorTreeWrapperPass>();
00109   AU.setPreservesCFG();
00110 }
00111 
00112 /// Turn objc_retain into objc_retainAutoreleasedReturnValue if the operand is a
00113 /// return value. We do this late so we do not disrupt the dataflow analysis in
00114 /// ObjCARCOpt.
00115 bool
00116 ObjCARCContract::OptimizeRetainCall(Function &F, Instruction *Retain) {
00117   ImmutableCallSite CS(GetObjCArg(Retain));
00118   const Instruction *Call = CS.getInstruction();
00119   if (!Call)
00120     return false;
00121   if (Call->getParent() != Retain->getParent())
00122     return false;
00123 
00124   // Check that the call is next to the retain.
00125   BasicBlock::const_iterator I = Call;
00126   ++I;
00127   while (IsNoopInstruction(I)) ++I;
00128   if (&*I != Retain)
00129     return false;
00130 
00131   // Turn it to an objc_retainAutoreleasedReturnValue.
00132   Changed = true;
00133   ++NumPeeps;
00134 
00135   DEBUG(dbgs() << "Transforming objc_retain => "
00136                   "objc_retainAutoreleasedReturnValue since the operand is a "
00137                   "return value.\nOld: "<< *Retain << "\n");
00138 
00139   // We do not have to worry about tail calls/does not throw since
00140   // retain/retainRV have the same properties.
00141   Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_RetainRV);
00142   cast<CallInst>(Retain)->setCalledFunction(Decl);
00143 
00144   DEBUG(dbgs() << "New: " << *Retain << "\n");
00145   return true;
00146 }
00147 
00148 /// Merge an autorelease with a retain into a fused call.
00149 bool
00150 ObjCARCContract::ContractAutorelease(Function &F, Instruction *Autorelease,
00151                                      InstructionClass Class,
00152                                      SmallPtrSet<Instruction *, 4>
00153                                        &DependingInstructions,
00154                                      SmallPtrSet<const BasicBlock *, 4>
00155                                        &Visited) {
00156   const Value *Arg = GetObjCArg(Autorelease);
00157 
00158   // Check that there are no instructions between the retain and the autorelease
00159   // (such as an autorelease_pop) which may change the count.
00160   CallInst *Retain = 0;
00161   if (Class == IC_AutoreleaseRV)
00162     FindDependencies(RetainAutoreleaseRVDep, Arg,
00163                      Autorelease->getParent(), Autorelease,
00164                      DependingInstructions, Visited, PA);
00165   else
00166     FindDependencies(RetainAutoreleaseDep, Arg,
00167                      Autorelease->getParent(), Autorelease,
00168                      DependingInstructions, Visited, PA);
00169 
00170   Visited.clear();
00171   if (DependingInstructions.size() != 1) {
00172     DependingInstructions.clear();
00173     return false;
00174   }
00175 
00176   Retain = dyn_cast_or_null<CallInst>(*DependingInstructions.begin());
00177   DependingInstructions.clear();
00178 
00179   if (!Retain ||
00180       GetBasicInstructionClass(Retain) != IC_Retain ||
00181       GetObjCArg(Retain) != Arg)
00182     return false;
00183 
00184   Changed = true;
00185   ++NumPeeps;
00186 
00187   DEBUG(dbgs() << "ObjCARCContract::ContractAutorelease: Fusing "
00188                   "retain/autorelease. Erasing: " << *Autorelease << "\n"
00189                   "                                      Old Retain: "
00190                << *Retain << "\n");
00191 
00192   Constant *Decl = EP.get(Class == IC_AutoreleaseRV ?
00193                           ARCRuntimeEntryPoints::EPT_RetainAutoreleaseRV :
00194                           ARCRuntimeEntryPoints::EPT_RetainAutorelease);
00195   Retain->setCalledFunction(Decl);
00196 
00197   DEBUG(dbgs() << "                                      New Retain: "
00198                << *Retain << "\n");
00199 
00200   EraseInstruction(Autorelease);
00201   return true;
00202 }
00203 
00204 /// Attempt to merge an objc_release with a store, load, and objc_retain to form
00205 /// an objc_storeStrong. This can be a little tricky because the instructions
00206 /// don't always appear in order, and there may be unrelated intervening
00207 /// instructions.
00208 void ObjCARCContract::ContractRelease(Instruction *Release,
00209                                       inst_iterator &Iter) {
00210   LoadInst *Load = dyn_cast<LoadInst>(GetObjCArg(Release));
00211   if (!Load || !Load->isSimple()) return;
00212 
00213   // For now, require everything to be in one basic block.
00214   BasicBlock *BB = Release->getParent();
00215   if (Load->getParent() != BB) return;
00216 
00217   // Walk down to find the store and the release, which may be in either order.
00218   BasicBlock::iterator I = Load, End = BB->end();
00219   ++I;
00220   AliasAnalysis::Location Loc = AA->getLocation(Load);
00221   StoreInst *Store = 0;
00222   bool SawRelease = false;
00223   for (; !Store || !SawRelease; ++I) {
00224     if (I == End)
00225       return;
00226 
00227     Instruction *Inst = I;
00228     if (Inst == Release) {
00229       SawRelease = true;
00230       continue;
00231     }
00232 
00233     InstructionClass Class = GetBasicInstructionClass(Inst);
00234 
00235     // Unrelated retains are harmless.
00236     if (IsRetain(Class))
00237       continue;
00238 
00239     if (Store) {
00240       // The store is the point where we're going to put the objc_storeStrong,
00241       // so make sure there are no uses after it.
00242       if (CanUse(Inst, Load, PA, Class))
00243         return;
00244     } else if (AA->getModRefInfo(Inst, Loc) & AliasAnalysis::Mod) {
00245       // We are moving the load down to the store, so check for anything
00246       // else which writes to the memory between the load and the store.
00247       Store = dyn_cast<StoreInst>(Inst);
00248       if (!Store || !Store->isSimple()) return;
00249       if (Store->getPointerOperand() != Loc.Ptr) return;
00250     }
00251   }
00252 
00253   Value *New = StripPointerCastsAndObjCCalls(Store->getValueOperand());
00254 
00255   // Walk up to find the retain.
00256   I = Store;
00257   BasicBlock::iterator Begin = BB->begin();
00258   while (I != Begin && GetBasicInstructionClass(I) != IC_Retain)
00259     --I;
00260   Instruction *Retain = I;
00261   if (GetBasicInstructionClass(Retain) != IC_Retain) return;
00262   if (GetObjCArg(Retain) != New) return;
00263 
00264   Changed = true;
00265   ++NumStoreStrongs;
00266 
00267   LLVMContext &C = Release->getContext();
00268   Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
00269   Type *I8XX = PointerType::getUnqual(I8X);
00270 
00271   Value *Args[] = { Load->getPointerOperand(), New };
00272   if (Args[0]->getType() != I8XX)
00273     Args[0] = new BitCastInst(Args[0], I8XX, "", Store);
00274   if (Args[1]->getType() != I8X)
00275     Args[1] = new BitCastInst(Args[1], I8X, "", Store);
00276   Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_StoreStrong);
00277   CallInst *StoreStrong = CallInst::Create(Decl, Args, "", Store);
00278   StoreStrong->setDoesNotThrow();
00279   StoreStrong->setDebugLoc(Store->getDebugLoc());
00280 
00281   // We can't set the tail flag yet, because we haven't yet determined
00282   // whether there are any escaping allocas. Remember this call, so that
00283   // we can set the tail flag once we know it's safe.
00284   StoreStrongCalls.insert(StoreStrong);
00285 
00286   if (&*Iter == Store) ++Iter;
00287   Store->eraseFromParent();
00288   Release->eraseFromParent();
00289   EraseInstruction(Retain);
00290   if (Load->use_empty())
00291     Load->eraseFromParent();
00292 }
00293 
00294 bool ObjCARCContract::doInitialization(Module &M) {
00295   // If nothing in the Module uses ARC, don't do anything.
00296   Run = ModuleHasARC(M);
00297   if (!Run)
00298     return false;
00299 
00300   EP.Initialize(&M);
00301 
00302   // Initialize RetainRVMarker.
00303   RetainRVMarker = 0;
00304   if (NamedMDNode *NMD =
00305         M.getNamedMetadata("clang.arc.retainAutoreleasedReturnValueMarker"))
00306     if (NMD->getNumOperands() == 1) {
00307       const MDNode *N = NMD->getOperand(0);
00308       if (N->getNumOperands() == 1)
00309         if (const MDString *S = dyn_cast<MDString>(N->getOperand(0)))
00310           RetainRVMarker = S;
00311     }
00312 
00313   return false;
00314 }
00315 
00316 bool ObjCARCContract::runOnFunction(Function &F) {
00317   if (!EnableARCOpts)
00318     return false;
00319 
00320   // If nothing in the Module uses ARC, don't do anything.
00321   if (!Run)
00322     return false;
00323 
00324   Changed = false;
00325   AA = &getAnalysis<AliasAnalysis>();
00326   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
00327 
00328   PA.setAA(&getAnalysis<AliasAnalysis>());
00329 
00330   // Track whether it's ok to mark objc_storeStrong calls with the "tail"
00331   // keyword. Be conservative if the function has variadic arguments.
00332   // It seems that functions which "return twice" are also unsafe for the
00333   // "tail" argument, because they are setjmp, which could need to
00334   // return to an earlier stack state.
00335   bool TailOkForStoreStrongs = !F.isVarArg() &&
00336                                !F.callsFunctionThatReturnsTwice();
00337 
00338   // For ObjC library calls which return their argument, replace uses of the
00339   // argument with uses of the call return value, if it dominates the use. This
00340   // reduces register pressure.
00341   SmallPtrSet<Instruction *, 4> DependingInstructions;
00342   SmallPtrSet<const BasicBlock *, 4> Visited;
00343   for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
00344     Instruction *Inst = &*I++;
00345 
00346     DEBUG(dbgs() << "ObjCARCContract: Visiting: " << *Inst << "\n");
00347 
00348     // Only these library routines return their argument. In particular,
00349     // objc_retainBlock does not necessarily return its argument.
00350     InstructionClass Class = GetBasicInstructionClass(Inst);
00351     switch (Class) {
00352     case IC_FusedRetainAutorelease:
00353     case IC_FusedRetainAutoreleaseRV:
00354       break;
00355     case IC_Autorelease:
00356     case IC_AutoreleaseRV:
00357       if (ContractAutorelease(F, Inst, Class, DependingInstructions, Visited))
00358         continue;
00359       break;
00360     case IC_Retain:
00361       // Attempt to convert retains to retainrvs if they are next to function
00362       // calls.
00363       if (!OptimizeRetainCall(F, Inst))
00364         break;
00365       // If we succeed in our optimization, fall through.
00366       // FALLTHROUGH
00367     case IC_RetainRV: {
00368       // If we're compiling for a target which needs a special inline-asm
00369       // marker to do the retainAutoreleasedReturnValue optimization,
00370       // insert it now.
00371       if (!RetainRVMarker)
00372         break;
00373       BasicBlock::iterator BBI = Inst;
00374       BasicBlock *InstParent = Inst->getParent();
00375 
00376       // Step up to see if the call immediately precedes the RetainRV call.
00377       // If it's an invoke, we have to cross a block boundary. And we have
00378       // to carefully dodge no-op instructions.
00379       do {
00380         if (&*BBI == InstParent->begin()) {
00381           BasicBlock *Pred = InstParent->getSinglePredecessor();
00382           if (!Pred)
00383             goto decline_rv_optimization;
00384           BBI = Pred->getTerminator();
00385           break;
00386         }
00387         --BBI;
00388       } while (IsNoopInstruction(BBI));
00389 
00390       if (&*BBI == GetObjCArg(Inst)) {
00391         DEBUG(dbgs() << "ObjCARCContract: Adding inline asm marker for "
00392                         "retainAutoreleasedReturnValue optimization.\n");
00393         Changed = true;
00394         InlineAsm *IA =
00395           InlineAsm::get(FunctionType::get(Type::getVoidTy(Inst->getContext()),
00396                                            /*isVarArg=*/false),
00397                          RetainRVMarker->getString(),
00398                          /*Constraints=*/"", /*hasSideEffects=*/true);
00399         CallInst::Create(IA, "", Inst);
00400       }
00401     decline_rv_optimization:
00402       break;
00403     }
00404     case IC_InitWeak: {
00405       // objc_initWeak(p, null) => *p = null
00406       CallInst *CI = cast<CallInst>(Inst);
00407       if (IsNullOrUndef(CI->getArgOperand(1))) {
00408         Value *Null =
00409           ConstantPointerNull::get(cast<PointerType>(CI->getType()));
00410         Changed = true;
00411         new StoreInst(Null, CI->getArgOperand(0), CI);
00412 
00413         DEBUG(dbgs() << "OBJCARCContract: Old = " << *CI << "\n"
00414                      << "                 New = " << *Null << "\n");
00415 
00416         CI->replaceAllUsesWith(Null);
00417         CI->eraseFromParent();
00418       }
00419       continue;
00420     }
00421     case IC_Release:
00422       ContractRelease(Inst, I);
00423       continue;
00424     case IC_User:
00425       // Be conservative if the function has any alloca instructions.
00426       // Technically we only care about escaping alloca instructions,
00427       // but this is sufficient to handle some interesting cases.
00428       if (isa<AllocaInst>(Inst))
00429         TailOkForStoreStrongs = false;
00430       continue;
00431     case IC_IntrinsicUser:
00432       // Remove calls to @clang.arc.use(...).
00433       Inst->eraseFromParent();
00434       continue;
00435     default:
00436       continue;
00437     }
00438 
00439     DEBUG(dbgs() << "ObjCARCContract: Finished List.\n\n");
00440 
00441     // Don't use GetObjCArg because we don't want to look through bitcasts
00442     // and such; to do the replacement, the argument must have type i8*.
00443     Value *Arg = cast<CallInst>(Inst)->getArgOperand(0);
00444     for (;;) {
00445       // If we're compiling bugpointed code, don't get in trouble.
00446       if (!isa<Instruction>(Arg) && !isa<Argument>(Arg))
00447         break;
00448       // Look through the uses of the pointer.
00449       for (Value::use_iterator UI = Arg->use_begin(), UE = Arg->use_end();
00450            UI != UE; ) {
00451         // Increment UI now, because we may unlink its element.
00452         Use &U = *UI++;
00453         unsigned OperandNo = U.getOperandNo();
00454 
00455         // If the call's return value dominates a use of the call's argument
00456         // value, rewrite the use to use the return value. We check for
00457         // reachability here because an unreachable call is considered to
00458         // trivially dominate itself, which would lead us to rewriting its
00459         // argument in terms of its return value, which would lead to
00460         // infinite loops in GetObjCArg.
00461         if (DT->isReachableFromEntry(U) && DT->dominates(Inst, U)) {
00462           Changed = true;
00463           Instruction *Replacement = Inst;
00464           Type *UseTy = U.get()->getType();
00465           if (PHINode *PHI = dyn_cast<PHINode>(U.getUser())) {
00466             // For PHI nodes, insert the bitcast in the predecessor block.
00467             unsigned ValNo = PHINode::getIncomingValueNumForOperand(OperandNo);
00468             BasicBlock *BB = PHI->getIncomingBlock(ValNo);
00469             if (Replacement->getType() != UseTy)
00470               Replacement = new BitCastInst(Replacement, UseTy, "",
00471                                             &BB->back());
00472             // While we're here, rewrite all edges for this PHI, rather
00473             // than just one use at a time, to minimize the number of
00474             // bitcasts we emit.
00475             for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i)
00476               if (PHI->getIncomingBlock(i) == BB) {
00477                 // Keep the UI iterator valid.
00478                 if (UI != UE &&
00479                     &PHI->getOperandUse(
00480                         PHINode::getOperandNumForIncomingValue(i)) == &*UI)
00481                   ++UI;
00482                 PHI->setIncomingValue(i, Replacement);
00483               }
00484           } else {
00485             if (Replacement->getType() != UseTy)
00486               Replacement = new BitCastInst(Replacement, UseTy, "",
00487                                             cast<Instruction>(U.getUser()));
00488             U.set(Replacement);
00489           }
00490         }
00491       }
00492 
00493       // If Arg is a no-op casted pointer, strip one level of casts and iterate.
00494       if (const BitCastInst *BI = dyn_cast<BitCastInst>(Arg))
00495         Arg = BI->getOperand(0);
00496       else if (isa<GEPOperator>(Arg) &&
00497                cast<GEPOperator>(Arg)->hasAllZeroIndices())
00498         Arg = cast<GEPOperator>(Arg)->getPointerOperand();
00499       else if (isa<GlobalAlias>(Arg) &&
00500                !cast<GlobalAlias>(Arg)->mayBeOverridden())
00501         Arg = cast<GlobalAlias>(Arg)->getAliasee();
00502       else
00503         break;
00504     }
00505   }
00506 
00507   // If this function has no escaping allocas or suspicious vararg usage,
00508   // objc_storeStrong calls can be marked with the "tail" keyword.
00509   if (TailOkForStoreStrongs)
00510     for (SmallPtrSet<CallInst *, 8>::iterator I = StoreStrongCalls.begin(),
00511          E = StoreStrongCalls.end(); I != E; ++I)
00512       (*I)->setTailCall();
00513   StoreStrongCalls.clear();
00514 
00515   return Changed;
00516 }