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