Home | History | Annotate | Download | only in ObjCARC 
      1 //===- ObjCARCContract.cpp - ObjC ARC Optimization ------------------------===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 /// \file
     10 /// This file defines late ObjC ARC optimizations. ARC stands for Automatic
     11 /// Reference Counting and is a system for managing reference counts for objects
     12 /// in Objective C.
     13 ///
     14 /// This specific file mainly deals with ``contracting'' multiple lower level
     15 /// operations into singular higher level operations through pattern matching.
     16 ///
     17 /// WARNING: This file knows about certain library functions. It recognizes them
     18 /// by name, and hardwires knowledge of their semantics.
     19 ///
     20 /// WARNING: This file knows about how certain Objective-C library functions are
     21 /// used. Naive LLVM IR transformations which would otherwise be
     22 /// behavior-preserving may break these assumptions.
     23 ///
     24 //===----------------------------------------------------------------------===//
     25 
     26 // TODO: ObjCARCContract could insert PHI nodes when uses aren't
     27 // dominated by single calls.
     28 
     29 #define DEBUG_TYPE "objc-arc-contract"
     30 #include "ObjCARC.h"
     31 #include "ARCRuntimeEntryPoints.h"
     32 #include "DependencyAnalysis.h"
     33 #include "ProvenanceAnalysis.h"
     34 #include "llvm/ADT/Statistic.h"
     35 #include "llvm/Analysis/Dominators.h"
     36 #include "llvm/IR/InlineAsm.h"
     37 #include "llvm/IR/Operator.h"
     38 #include "llvm/Support/Debug.h"
     39 
     40 using namespace llvm;
     41 using namespace llvm::objcarc;
     42 
     43 STATISTIC(NumPeeps,       "Number of calls peephole-optimized");
     44 STATISTIC(NumStoreStrongs, "Number objc_storeStrong calls formed");
     45 
     46 namespace {
     47   /// \brief Late ARC optimizations
     48   ///
     49   /// These change the IR in a way that makes it difficult to be analyzed by
     50   /// ObjCARCOpt, so it's run late.
     51   class ObjCARCContract : public FunctionPass {
     52     bool Changed;
     53     AliasAnalysis *AA;
     54     DominatorTree *DT;
     55     ProvenanceAnalysis PA;
     56     ARCRuntimeEntryPoints EP;
     57 
     58     /// A flag indicating whether this optimization pass should run.
     59     bool Run;
     60 
     61     /// The inline asm string to insert between calls and RetainRV calls to make
     62     /// the optimization work on targets which need it.
     63     const MDString *RetainRVMarker;
     64 
     65     /// The set of inserted objc_storeStrong calls. If at the end of walking the
     66     /// function we have found no alloca instructions, these calls can be marked
     67     /// "tail".
     68     SmallPtrSet<CallInst *, 8> StoreStrongCalls;
     69 
     70     bool OptimizeRetainCall(Function &F, Instruction *Retain);
     71 
     72     bool ContractAutorelease(Function &F, Instruction *Autorelease,
     73                              InstructionClass Class,
     74                              SmallPtrSet<Instruction *, 4>
     75                                &DependingInstructions,
     76                              SmallPtrSet<const BasicBlock *, 4>
     77                                &Visited);
     78 
     79     void ContractRelease(Instruction *Release,
     80                          inst_iterator &Iter);
     81 
     82     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
     83     virtual bool doInitialization(Module &M);
     84     virtual bool runOnFunction(Function &F);
     85 
     86   public:
     87     static char ID;
     88     ObjCARCContract() : FunctionPass(ID) {
     89       initializeObjCARCContractPass(*PassRegistry::getPassRegistry());
     90     }
     91   };
     92 }
     93 
     94 char ObjCARCContract::ID = 0;
     95 INITIALIZE_PASS_BEGIN(ObjCARCContract,
     96                       "objc-arc-contract", "ObjC ARC contraction", false, false)
     97 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
     98 INITIALIZE_PASS_DEPENDENCY(DominatorTree)
     99 INITIALIZE_PASS_END(ObjCARCContract,
    100                     "objc-arc-contract", "ObjC ARC contraction", false, false)
    101 
    102 Pass *llvm::createObjCARCContractPass() {
    103   return new ObjCARCContract();
    104 }
    105 
    106 void ObjCARCContract::getAnalysisUsage(AnalysisUsage &AU) const {
    107   AU.addRequired<AliasAnalysis>();
    108   AU.addRequired<DominatorTree>();
    109   AU.setPreservesCFG();
    110 }
    111 
    112 /// Turn objc_retain into objc_retainAutoreleasedReturnValue if the operand is a
    113 /// return value. We do this late so we do not disrupt the dataflow analysis in
    114 /// ObjCARCOpt.
    115 bool
    116 ObjCARCContract::OptimizeRetainCall(Function &F, Instruction *Retain) {
    117   ImmutableCallSite CS(GetObjCArg(Retain));
    118   const Instruction *Call = CS.getInstruction();
    119   if (!Call)
    120     return false;
    121   if (Call->getParent() != Retain->getParent())
    122     return false;
    123 
    124   // Check that the call is next to the retain.
    125   BasicBlock::const_iterator I = Call;
    126   ++I;
    127   while (IsNoopInstruction(I)) ++I;
    128   if (&*I != Retain)
    129     return false;
    130 
    131   // Turn it to an objc_retainAutoreleasedReturnValue.
    132   Changed = true;
    133   ++NumPeeps;
    134 
    135   DEBUG(dbgs() << "Transforming objc_retain => "
    136                   "objc_retainAutoreleasedReturnValue since the operand is a "
    137                   "return value.\nOld: "<< *Retain << "\n");
    138 
    139   // We do not have to worry about tail calls/does not throw since
    140   // retain/retainRV have the same properties.
    141   Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_RetainRV);
    142   cast<CallInst>(Retain)->setCalledFunction(Decl);
    143 
    144   DEBUG(dbgs() << "New: " << *Retain << "\n");
    145   return true;
    146 }
    147 
    148 /// Merge an autorelease with a retain into a fused call.
    149 bool
    150 ObjCARCContract::ContractAutorelease(Function &F, Instruction *Autorelease,
    151                                      InstructionClass Class,
    152                                      SmallPtrSet<Instruction *, 4>
    153                                        &DependingInstructions,
    154                                      SmallPtrSet<const BasicBlock *, 4>
    155                                        &Visited) {
    156   const Value *Arg = GetObjCArg(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 = 0;
    161   if (Class == IC_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 ||
    180       GetBasicInstructionClass(Retain) != IC_Retain ||
    181       GetObjCArg(Retain) != Arg)
    182     return false;
    183 
    184   Changed = true;
    185   ++NumPeeps;
    186 
    187   DEBUG(dbgs() << "ObjCARCContract::ContractAutorelease: Fusing "
    188                   "retain/autorelease. Erasing: " << *Autorelease << "\n"
    189                   "                                      Old Retain: "
    190                << *Retain << "\n");
    191 
    192   Constant *Decl = EP.get(Class == IC_AutoreleaseRV ?
    193                           ARCRuntimeEntryPoints::EPT_RetainAutoreleaseRV :
    194                           ARCRuntimeEntryPoints::EPT_RetainAutorelease);
    195   Retain->setCalledFunction(Decl);
    196 
    197   DEBUG(dbgs() << "                                      New Retain: "
    198                << *Retain << "\n");
    199 
    200   EraseInstruction(Autorelease);
    201   return true;
    202 }
    203 
    204 /// Attempt to merge an objc_release with a store, load, and objc_retain to form
    205 /// an objc_storeStrong. This can be a little tricky because the instructions
    206 /// don't always appear in order, and there may be unrelated intervening
    207 /// instructions.
    208 void ObjCARCContract::ContractRelease(Instruction *Release,
    209                                       inst_iterator &Iter) {
    210   LoadInst *Load = dyn_cast<LoadInst>(GetObjCArg(Release));
    211   if (!Load || !Load->isSimple()) return;
    212 
    213   // For now, require everything to be in one basic block.
    214   BasicBlock *BB = Release->getParent();
    215   if (Load->getParent() != BB) return;
    216 
    217   // Walk down to find the store and the release, which may be in either order.
    218   BasicBlock::iterator I = Load, End = BB->end();
    219   ++I;
    220   AliasAnalysis::Location Loc = AA->getLocation(Load);
    221   StoreInst *Store = 0;
    222   bool SawRelease = false;
    223   for (; !Store || !SawRelease; ++I) {
    224     if (I == End)
    225       return;
    226 
    227     Instruction *Inst = I;
    228     if (Inst == Release) {
    229       SawRelease = true;
    230       continue;
    231     }
    232 
    233     InstructionClass Class = GetBasicInstructionClass(Inst);
    234 
    235     // Unrelated retains are harmless.
    236     if (IsRetain(Class))
    237       continue;
    238 
    239     if (Store) {
    240       // The store is the point where we're going to put the objc_storeStrong,
    241       // so make sure there are no uses after it.
    242       if (CanUse(Inst, Load, PA, Class))
    243         return;
    244     } else if (AA->getModRefInfo(Inst, Loc) & AliasAnalysis::Mod) {
    245       // We are moving the load down to the store, so check for anything
    246       // else which writes to the memory between the load and the store.
    247       Store = dyn_cast<StoreInst>(Inst);
    248       if (!Store || !Store->isSimple()) return;
    249       if (Store->getPointerOperand() != Loc.Ptr) return;
    250     }
    251   }
    252 
    253   Value *New = StripPointerCastsAndObjCCalls(Store->getValueOperand());
    254 
    255   // Walk up to find the retain.
    256   I = Store;
    257   BasicBlock::iterator Begin = BB->begin();
    258   while (I != Begin && GetBasicInstructionClass(I) != IC_Retain)
    259     --I;
    260   Instruction *Retain = I;
    261   if (GetBasicInstructionClass(Retain) != IC_Retain) return;
    262   if (GetObjCArg(Retain) != New) return;
    263 
    264   Changed = true;
    265   ++NumStoreStrongs;
    266 
    267   LLVMContext &C = Release->getContext();
    268   Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
    269   Type *I8XX = PointerType::getUnqual(I8X);
    270 
    271   Value *Args[] = { Load->getPointerOperand(), New };
    272   if (Args[0]->getType() != I8XX)
    273     Args[0] = new BitCastInst(Args[0], I8XX, "", Store);
    274   if (Args[1]->getType() != I8X)
    275     Args[1] = new BitCastInst(Args[1], I8X, "", Store);
    276   Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_StoreStrong);
    277   CallInst *StoreStrong = CallInst::Create(Decl, Args, "", Store);
    278   StoreStrong->setDoesNotThrow();
    279   StoreStrong->setDebugLoc(Store->getDebugLoc());
    280 
    281   // We can't set the tail flag yet, because we haven't yet determined
    282   // whether there are any escaping allocas. Remember this call, so that
    283   // we can set the tail flag once we know it's safe.
    284   StoreStrongCalls.insert(StoreStrong);
    285 
    286   if (&*Iter == Store) ++Iter;
    287   Store->eraseFromParent();
    288   Release->eraseFromParent();
    289   EraseInstruction(Retain);
    290   if (Load->use_empty())
    291     Load->eraseFromParent();
    292 }
    293 
    294 bool ObjCARCContract::doInitialization(Module &M) {
    295   // If nothing in the Module uses ARC, don't do anything.
    296   Run = ModuleHasARC(M);
    297   if (!Run)
    298     return false;
    299 
    300   EP.Initialize(&M);
    301 
    302   // Initialize RetainRVMarker.
    303   RetainRVMarker = 0;
    304   if (NamedMDNode *NMD =
    305         M.getNamedMetadata("clang.arc.retainAutoreleasedReturnValueMarker"))
    306     if (NMD->getNumOperands() == 1) {
    307       const MDNode *N = NMD->getOperand(0);
    308       if (N->getNumOperands() == 1)
    309         if (const MDString *S = dyn_cast<MDString>(N->getOperand(0)))
    310           RetainRVMarker = S;
    311     }
    312 
    313   return false;
    314 }
    315 
    316 bool ObjCARCContract::runOnFunction(Function &F) {
    317   if (!EnableARCOpts)
    318     return false;
    319 
    320   // If nothing in the Module uses ARC, don't do anything.
    321   if (!Run)
    322     return false;
    323 
    324   Changed = false;
    325   AA = &getAnalysis<AliasAnalysis>();
    326   DT = &getAnalysis<DominatorTree>();
    327 
    328   PA.setAA(&getAnalysis<AliasAnalysis>());
    329 
    330   // Track whether it's ok to mark objc_storeStrong calls with the "tail"
    331   // keyword. Be conservative if the function has variadic arguments.
    332   // It seems that functions which "return twice" are also unsafe for the
    333   // "tail" argument, because they are setjmp, which could need to
    334   // return to an earlier stack state.
    335   bool TailOkForStoreStrongs = !F.isVarArg() &&
    336                                !F.callsFunctionThatReturnsTwice();
    337 
    338   // For ObjC library calls which return their argument, replace uses of the
    339   // argument with uses of the call return value, if it dominates the use. This
    340   // reduces register pressure.
    341   SmallPtrSet<Instruction *, 4> DependingInstructions;
    342   SmallPtrSet<const BasicBlock *, 4> Visited;
    343   for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
    344     Instruction *Inst = &*I++;
    345 
    346     DEBUG(dbgs() << "ObjCARCContract: Visiting: " << *Inst << "\n");
    347 
    348     // Only these library routines return their argument. In particular,
    349     // objc_retainBlock does not necessarily return its argument.
    350     InstructionClass Class = GetBasicInstructionClass(Inst);
    351     switch (Class) {
    352     case IC_FusedRetainAutorelease:
    353     case IC_FusedRetainAutoreleaseRV:
    354       break;
    355     case IC_Autorelease:
    356     case IC_AutoreleaseRV:
    357       if (ContractAutorelease(F, Inst, Class, DependingInstructions, Visited))
    358         continue;
    359       break;
    360     case IC_Retain:
    361       // Attempt to convert retains to retainrvs if they are next to function
    362       // calls.
    363       if (!OptimizeRetainCall(F, Inst))
    364         break;
    365       // If we succeed in our optimization, fall through.
    366       // FALLTHROUGH
    367     case IC_RetainRV: {
    368       // If we're compiling for a target which needs a special inline-asm
    369       // marker to do the retainAutoreleasedReturnValue optimization,
    370       // insert it now.
    371       if (!RetainRVMarker)
    372         break;
    373       BasicBlock::iterator BBI = Inst;
    374       BasicBlock *InstParent = Inst->getParent();
    375 
    376       // Step up to see if the call immediately precedes the RetainRV call.
    377       // If it's an invoke, we have to cross a block boundary. And we have
    378       // to carefully dodge no-op instructions.
    379       do {
    380         if (&*BBI == InstParent->begin()) {
    381           BasicBlock *Pred = InstParent->getSinglePredecessor();
    382           if (!Pred)
    383             goto decline_rv_optimization;
    384           BBI = Pred->getTerminator();
    385           break;
    386         }
    387         --BBI;
    388       } while (IsNoopInstruction(BBI));
    389 
    390       if (&*BBI == GetObjCArg(Inst)) {
    391         DEBUG(dbgs() << "ObjCARCContract: Adding inline asm marker for "
    392                         "retainAutoreleasedReturnValue optimization.\n");
    393         Changed = true;
    394         InlineAsm *IA =
    395           InlineAsm::get(FunctionType::get(Type::getVoidTy(Inst->getContext()),
    396                                            /*isVarArg=*/false),
    397                          RetainRVMarker->getString(),
    398                          /*Constraints=*/"", /*hasSideEffects=*/true);
    399         CallInst::Create(IA, "", Inst);
    400       }
    401     decline_rv_optimization:
    402       break;
    403     }
    404     case IC_InitWeak: {
    405       // objc_initWeak(p, null) => *p = null
    406       CallInst *CI = cast<CallInst>(Inst);
    407       if (IsNullOrUndef(CI->getArgOperand(1))) {
    408         Value *Null =
    409           ConstantPointerNull::get(cast<PointerType>(CI->getType()));
    410         Changed = true;
    411         new StoreInst(Null, CI->getArgOperand(0), CI);
    412 
    413         DEBUG(dbgs() << "OBJCARCContract: Old = " << *CI << "\n"
    414                      << "                 New = " << *Null << "\n");
    415 
    416         CI->replaceAllUsesWith(Null);
    417         CI->eraseFromParent();
    418       }
    419       continue;
    420     }
    421     case IC_Release:
    422       ContractRelease(Inst, I);
    423       continue;
    424     case IC_User:
    425       // Be conservative if the function has any alloca instructions.
    426       // Technically we only care about escaping alloca instructions,
    427       // but this is sufficient to handle some interesting cases.
    428       if (isa<AllocaInst>(Inst))
    429         TailOkForStoreStrongs = false;
    430       continue;
    431     case IC_IntrinsicUser:
    432       // Remove calls to @clang.arc.use(...).
    433       Inst->eraseFromParent();
    434       continue;
    435     default:
    436       continue;
    437     }
    438 
    439     DEBUG(dbgs() << "ObjCARCContract: Finished List.\n\n");
    440 
    441     // Don't use GetObjCArg because we don't want to look through bitcasts
    442     // and such; to do the replacement, the argument must have type i8*.
    443     const Value *Arg = cast<CallInst>(Inst)->getArgOperand(0);
    444     for (;;) {
    445       // If we're compiling bugpointed code, don't get in trouble.
    446       if (!isa<Instruction>(Arg) && !isa<Argument>(Arg))
    447         break;
    448       // Look through the uses of the pointer.
    449       for (Value::const_use_iterator UI = Arg->use_begin(), UE = Arg->use_end();
    450            UI != UE; ) {
    451         Use &U = UI.getUse();
    452         unsigned OperandNo = UI.getOperandNo();
    453         ++UI; // Increment UI now, because we may unlink its element.
    454 
    455         // If the call's return value dominates a use of the call's argument
    456         // value, rewrite the use to use the return value. We check for
    457         // reachability here because an unreachable call is considered to
    458         // trivially dominate itself, which would lead us to rewriting its
    459         // argument in terms of its return value, which would lead to
    460         // infinite loops in GetObjCArg.
    461         if (DT->isReachableFromEntry(U) && DT->dominates(Inst, U)) {
    462           Changed = true;
    463           Instruction *Replacement = Inst;
    464           Type *UseTy = U.get()->getType();
    465           if (PHINode *PHI = dyn_cast<PHINode>(U.getUser())) {
    466             // For PHI nodes, insert the bitcast in the predecessor block.
    467             unsigned ValNo = PHINode::getIncomingValueNumForOperand(OperandNo);
    468             BasicBlock *BB = PHI->getIncomingBlock(ValNo);
    469             if (Replacement->getType() != UseTy)
    470               Replacement = new BitCastInst(Replacement, UseTy, "",
    471                                             &BB->back());
    472             // While we're here, rewrite all edges for this PHI, rather
    473             // than just one use at a time, to minimize the number of
    474             // bitcasts we emit.
    475             for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i)
    476               if (PHI->getIncomingBlock(i) == BB) {
    477                 // Keep the UI iterator valid.
    478                 if (&PHI->getOperandUse(
    479                       PHINode::getOperandNumForIncomingValue(i)) ==
    480                     &UI.getUse())
    481                   ++UI;
    482                 PHI->setIncomingValue(i, Replacement);
    483               }
    484           } else {
    485             if (Replacement->getType() != UseTy)
    486               Replacement = new BitCastInst(Replacement, UseTy, "",
    487                                             cast<Instruction>(U.getUser()));
    488             U.set(Replacement);
    489           }
    490         }
    491       }
    492 
    493       // If Arg is a no-op casted pointer, strip one level of casts and iterate.
    494       if (const BitCastInst *BI = dyn_cast<BitCastInst>(Arg))
    495         Arg = BI->getOperand(0);
    496       else if (isa<GEPOperator>(Arg) &&
    497                cast<GEPOperator>(Arg)->hasAllZeroIndices())
    498         Arg = cast<GEPOperator>(Arg)->getPointerOperand();
    499       else if (isa<GlobalAlias>(Arg) &&
    500                !cast<GlobalAlias>(Arg)->mayBeOverridden())
    501         Arg = cast<GlobalAlias>(Arg)->getAliasee();
    502       else
    503         break;
    504     }
    505   }
    506 
    507   // If this function has no escaping allocas or suspicious vararg usage,
    508   // objc_storeStrong calls can be marked with the "tail" keyword.
    509   if (TailOkForStoreStrongs)
    510     for (SmallPtrSet<CallInst *, 8>::iterator I = StoreStrongCalls.begin(),
    511          E = StoreStrongCalls.end(); I != E; ++I)
    512       (*I)->setTailCall();
    513   StoreStrongCalls.clear();
    514 
    515   return Changed;
    516 }
    517