lib/Transforms/ObjCARC/ObjCARCContract.cpp

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