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