lib/Transforms/ObjCARC/ObjCARCContract.cpp

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