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 #include "ObjCARC.h"
  30 #include "ARCRuntimeEntryPoints.h"
  31 #include "DependencyAnalysis.h"
  32 #include "ProvenanceAnalysis.h"
  33 #include "llvm/ADT/Statistic.h"
  34 #include "llvm/IR/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 #define DEBUG_TYPE "objc-arc-contract"
  43
  44 STATISTIC(NumPeeps,       "Number of calls peephole-optimized");
  45 STATISTIC(NumStoreStrongs, "Number objc_storeStrong calls formed");
  46
  47 //===----------------------------------------------------------------------===//
  48 //                                Declarations
  49 //===----------------------------------------------------------------------===//
  50
  51 namespace {
  52   /// \brief Late ARC optimizations
  53   ///
  54   /// These change the IR in a way that makes it difficult to be analyzed by
  55   /// ObjCARCOpt, so it's run late.
  56   class ObjCARCContract : public FunctionPass {
  57     bool Changed;
  58     AliasAnalysis *AA;
  59     DominatorTree *DT;
  60     ProvenanceAnalysis PA;
  61     ARCRuntimeEntryPoints EP;
  62
  63     /// A flag indicating whether this optimization pass should run.
  64     bool Run;
  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     /// Returns true if we eliminated Inst.
  76     bool tryToPeepholeInstruction(Function &F, Instruction *Inst,
  77                                   inst_iterator &Iter,
  78                                   SmallPtrSetImpl<Instruction *> &DepInsts,
  79                                   SmallPtrSetImpl<const BasicBlock *> &Visited,
  80                                   bool &TailOkForStoreStrong);
  81
  82     bool optimizeRetainCall(Function &F, Instruction *Retain);
  83
  84     bool
  85     contractAutorelease(Function &F, Instruction *Autorelease,
  86                         InstructionClass Class,
  87                         SmallPtrSetImpl<Instruction *> &DependingInstructions,
  88                         SmallPtrSetImpl<const BasicBlock *> &Visited);
  89
  90     void tryToContractReleaseIntoStoreStrong(Instruction *Release,
  91                                              inst_iterator &Iter);
  92
  93     void getAnalysisUsage(AnalysisUsage &AU) const override;
  94     bool doInitialization(Module &M) override;
  95     bool runOnFunction(Function &F) override;
  96
  97   public:
  98     static char ID;
  99     ObjCARCContract() : FunctionPass(ID) {
 100       initializeObjCARCContractPass(*PassRegistry::getPassRegistry());
 101     }
 102   };
 103 }
 104
 105 //===----------------------------------------------------------------------===//
 106 //                               Implementation
 107 //===----------------------------------------------------------------------===//
 108
 109 /// Turn objc_retain into objc_retainAutoreleasedReturnValue if the operand is a
 110 /// return value. We do this late so we do not disrupt the dataflow analysis in
 111 /// ObjCARCOpt.
 112 bool ObjCARCContract::optimizeRetainCall(Function &F, Instruction *Retain) {
 113   ImmutableCallSite CS(GetArgRCIdentityRoot(Retain));
 114   const Instruction *Call = CS.getInstruction();
 115   if (!Call)
 116     return false;
 117   if (Call->getParent() != Retain->getParent())
 118     return false;
 119
 120   // Check that the call is next to the retain.
 121   BasicBlock::const_iterator I = Call;
 122   ++I;
 123   while (IsNoopInstruction(I)) ++I;
 124   if (&*I != Retain)
 125     return false;
 126
 127   // Turn it to an objc_retainAutoreleasedReturnValue.
 128   Changed = true;
 129   ++NumPeeps;
 130
 131   DEBUG(dbgs() << "Transforming objc_retain => "
 132                   "objc_retainAutoreleasedReturnValue since the operand is a "
 133                   "return value.\nOld: "<< *Retain << "\n");
 134
 135   // We do not have to worry about tail calls/does not throw since
 136   // retain/retainRV have the same properties.
 137   Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_RetainRV);
 138   cast<CallInst>(Retain)->setCalledFunction(Decl);
 139
 140   DEBUG(dbgs() << "New: " << *Retain << "\n");
 141   return true;
 142 }
 143
 144 /// Merge an autorelease with a retain into a fused call.
 145 bool ObjCARCContract::contractAutorelease(
 146     Function &F, Instruction *Autorelease, InstructionClass Class,
 147     SmallPtrSetImpl<Instruction *> &DependingInstructions,
 148     SmallPtrSetImpl<const BasicBlock *> &Visited) {
 149   const Value *Arg = GetArgRCIdentityRoot(Autorelease);
 150
 151   // Check that there are no instructions between the retain and the autorelease
 152   // (such as an autorelease_pop) which may change the count.
 153   CallInst *Retain = nullptr;
 154   if (Class == IC_AutoreleaseRV)
 155     FindDependencies(RetainAutoreleaseRVDep, Arg,
 156                      Autorelease->getParent(), Autorelease,
 157                      DependingInstructions, Visited, PA);
 158   else
 159     FindDependencies(RetainAutoreleaseDep, Arg,
 160                      Autorelease->getParent(), Autorelease,
 161                      DependingInstructions, Visited, PA);
 162
 163   Visited.clear();
 164   if (DependingInstructions.size() != 1) {
 165     DependingInstructions.clear();
 166     return false;
 167   }
 168
 169   Retain = dyn_cast_or_null<CallInst>(*DependingInstructions.begin());
 170   DependingInstructions.clear();
 171
 172   if (!Retain ||
 173       GetBasicInstructionClass(Retain) != IC_Retain ||
 174       GetArgRCIdentityRoot(Retain) != Arg)
 175     return false;
 176
 177   Changed = true;
 178   ++NumPeeps;
 179
 180   DEBUG(dbgs() << "    Fusing retain/autorelease!\n"
 181                   "        Autorelease:" << *Autorelease << "\n"
 182                   "        Retain: " << *Retain << "\n");
 183
 184   Constant *Decl = EP.get(Class == IC_AutoreleaseRV ?
 185                           ARCRuntimeEntryPoints::EPT_RetainAutoreleaseRV :
 186                           ARCRuntimeEntryPoints::EPT_RetainAutorelease);
 187   Retain->setCalledFunction(Decl);
 188
 189   DEBUG(dbgs() << "        New RetainAutorelease: " << *Retain << "\n");
 190
 191   EraseInstruction(Autorelease);
 192   return true;
 193 }
 194
 195 /// Attempt to merge an objc_release with a store, load, and objc_retain to form
 196 /// an objc_storeStrong. This can be a little tricky because the instructions
 197 /// don't always appear in order, and there may be unrelated intervening
 198 /// instructions.
 199 void
 200 ObjCARCContract::
 201 tryToContractReleaseIntoStoreStrong(Instruction *Release, inst_iterator &Iter) {
 202   LoadInst *Load = dyn_cast<LoadInst>(GetArgRCIdentityRoot(Release));
 203   if (!Load || !Load->isSimple()) return;
 204
 205   // For now, require everything to be in one basic block.
 206   BasicBlock *BB = Release->getParent();
 207   if (Load->getParent() != BB) return;
 208
 209   // Walk down to find the store and the release, which may be in either order.
 210   BasicBlock::iterator I = Load, End = BB->end();
 211   ++I;
 212   AliasAnalysis::Location Loc = AA->getLocation(Load);
 213   StoreInst *Store = nullptr;
 214   bool SawRelease = false;
 215   for (; !Store || !SawRelease; ++I) {
 216     if (I == End)
 217       return;
 218
 219     Instruction *Inst = I;
 220     if (Inst == Release) {
 221       SawRelease = true;
 222       continue;
 223     }
 224
 225     InstructionClass Class = GetBasicInstructionClass(Inst);
 226
 227     // Unrelated retains are harmless.
 228     if (IsRetain(Class))
 229       continue;
 230
 231     if (Store) {
 232       // The store is the point where we're going to put the objc_storeStrong,
 233       // so make sure there are no uses after it.
 234       if (CanUse(Inst, Load, PA, Class))
 235         return;
 236     } else if (AA->getModRefInfo(Inst, Loc) & AliasAnalysis::Mod) {
 237       // We are moving the load down to the store, so check for anything
 238       // else which writes to the memory between the load and the store.
 239       Store = dyn_cast<StoreInst>(Inst);
 240       if (!Store || !Store->isSimple()) return;
 241       if (Store->getPointerOperand() != Loc.Ptr) return;
 242     }
 243   }
 244
 245   Value *New = GetRCIdentityRoot(Store->getValueOperand());
 246
 247   // Walk up to find the retain.
 248   I = Store;
 249   BasicBlock::iterator Begin = BB->begin();
 250   while (I != Begin && GetBasicInstructionClass(I) != IC_Retain)
 251     --I;
 252   Instruction *Retain = I;
 253   if (GetBasicInstructionClass(Retain) != IC_Retain) return;
 254   if (GetArgRCIdentityRoot(Retain) != New) return;
 255
 256   Changed = true;
 257   ++NumStoreStrongs;
 258
 259   DEBUG(
 260       llvm::dbgs() << "    Contracting retain, release into objc_storeStrong.\n"
 261                    << "        Old:\n"
 262                    << "            Store:   " << *Store << "\n"
 263                    << "            Release: " << *Release << "\n"
 264                    << "            Retain:  " << *Retain << "\n"
 265                    << "            Load:    " << *Load << "\n");
 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   DEBUG(llvm::dbgs() << "        New Store Strong: " << *StoreStrong << "\n");
 287
 288   if (&*Iter == Store) ++Iter;
 289   Store->eraseFromParent();
 290   Release->eraseFromParent();
 291   EraseInstruction(Retain);
 292   if (Load->use_empty())
 293     Load->eraseFromParent();
 294 }
 295
 296 bool ObjCARCContract::tryToPeepholeInstruction(
 297   Function &F, Instruction *Inst, inst_iterator &Iter,
 298   SmallPtrSetImpl<Instruction *> &DependingInsts,
 299   SmallPtrSetImpl<const BasicBlock *> &Visited,
 300   bool &TailOkForStoreStrongs) {
 301     // Only these library routines return their argument. In particular,
 302     // objc_retainBlock does not necessarily return its argument.
 303     InstructionClass Class = GetBasicInstructionClass(Inst);
 304     switch (Class) {
 305     case IC_FusedRetainAutorelease:
 306     case IC_FusedRetainAutoreleaseRV:
 307       return false;
 308     case IC_Autorelease:
 309     case IC_AutoreleaseRV:
 310       return contractAutorelease(F, Inst, Class, DependingInsts, Visited);
 311     case IC_Retain:
 312       // Attempt to convert retains to retainrvs if they are next to function
 313       // calls.
 314       if (!optimizeRetainCall(F, Inst))
 315         return false;
 316       // If we succeed in our optimization, fall through.
 317       // FALLTHROUGH
 318     case IC_RetainRV: {
 319       // If we're compiling for a target which needs a special inline-asm
 320       // marker to do the retainAutoreleasedReturnValue optimization,
 321       // insert it now.
 322       if (!RetainRVMarker)
 323         return false;
 324       BasicBlock::iterator BBI = Inst;
 325       BasicBlock *InstParent = Inst->getParent();
 326
 327       // Step up to see if the call immediately precedes the RetainRV call.
 328       // If it's an invoke, we have to cross a block boundary. And we have
 329       // to carefully dodge no-op instructions.
 330       do {
 331         if (&*BBI == InstParent->begin()) {
 332           BasicBlock *Pred = InstParent->getSinglePredecessor();
 333           if (!Pred)
 334             goto decline_rv_optimization;
 335           BBI = Pred->getTerminator();
 336           break;
 337         }
 338         --BBI;
 339       } while (IsNoopInstruction(BBI));
 340
 341       if (&*BBI == GetArgRCIdentityRoot(Inst)) {
 342         DEBUG(dbgs() << "Adding inline asm marker for "
 343                         "retainAutoreleasedReturnValue optimization.\n");
 344         Changed = true;
 345         InlineAsm *IA =
 346           InlineAsm::get(FunctionType::get(Type::getVoidTy(Inst->getContext()),
 347                                            /*isVarArg=*/false),
 348                          RetainRVMarker->getString(),
 349                          /*Constraints=*/"", /*hasSideEffects=*/true);
 350         CallInst::Create(IA, "", Inst);
 351       }
 352     decline_rv_optimization:
 353       return false;
 354     }
 355     case IC_InitWeak: {
 356       // objc_initWeak(p, null) => *p = null
 357       CallInst *CI = cast<CallInst>(Inst);
 358       if (IsNullOrUndef(CI->getArgOperand(1))) {
 359         Value *Null =
 360           ConstantPointerNull::get(cast<PointerType>(CI->getType()));
 361         Changed = true;
 362         new StoreInst(Null, CI->getArgOperand(0), CI);
 363
 364         DEBUG(dbgs() << "OBJCARCContract: Old = " << *CI << "\n"
 365                      << "                 New = " << *Null << "\n");
 366
 367         CI->replaceAllUsesWith(Null);
 368         CI->eraseFromParent();
 369       }
 370       return true;
 371     }
 372     case IC_Release:
 373       // Try to form an objc store strong from our release. If we fail, there is
 374       // nothing further to do below, so continue.
 375       tryToContractReleaseIntoStoreStrong(Inst, Iter);
 376       return true;
 377     case IC_User:
 378       // Be conservative if the function has any alloca instructions.
 379       // Technically we only care about escaping alloca instructions,
 380       // but this is sufficient to handle some interesting cases.
 381       if (isa<AllocaInst>(Inst))
 382         TailOkForStoreStrongs = false;
 383       return true;
 384     case IC_IntrinsicUser:
 385       // Remove calls to @clang.arc.use(...).
 386       Inst->eraseFromParent();
 387       return true;
 388     default:
 389       return true;
 390     }
 391 }
 392
 393 //===----------------------------------------------------------------------===//
 394 //                              Top Level Driver
 395 //===----------------------------------------------------------------------===//
 396
 397 bool ObjCARCContract::runOnFunction(Function &F) {
 398   if (!EnableARCOpts)
 399     return false;
 400
 401   // If nothing in the Module uses ARC, don't do anything.
 402   if (!Run)
 403     return false;
 404
 405   Changed = false;
 406   AA = &getAnalysis<AliasAnalysis>();
 407   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 408
 409   PA.setAA(&getAnalysis<AliasAnalysis>());
 410
 411   DEBUG(llvm::dbgs() << "**** ObjCARC Contract ****\n");
 412
 413   // Track whether it's ok to mark objc_storeStrong calls with the "tail"
 414   // keyword. Be conservative if the function has variadic arguments.
 415   // It seems that functions which "return twice" are also unsafe for the
 416   // "tail" argument, because they are setjmp, which could need to
 417   // return to an earlier stack state.
 418   bool TailOkForStoreStrongs =
 419       !F.isVarArg() && !F.callsFunctionThatReturnsTwice();
 420
 421   // For ObjC library calls which return their argument, replace uses of the
 422   // argument with uses of the call return value, if it dominates the use. This
 423   // reduces register pressure.
 424   SmallPtrSet<Instruction *, 4> DependingInstructions;
 425   SmallPtrSet<const BasicBlock *, 4> Visited;
 426   for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E;) {
 427     Instruction *Inst = &*I++;
 428
 429     DEBUG(dbgs() << "Visiting: " << *Inst << "\n");
 430
 431     // First try to peephole Inst. If there is nothing further we can do in
 432     // terms of undoing objc-arc-expand, process the next inst.
 433     if (tryToPeepholeInstruction(F, Inst, I, DependingInstructions, Visited,
 434                                  TailOkForStoreStrongs))
 435       continue;
 436
 437     // Otherwise, try to undo objc-arc-expand.
 438
 439     // Don't use GetArgRCIdentityRoot because we don't want to look through bitcasts
 440     // and such; to do the replacement, the argument must have type i8*.
 441     Value *Arg = cast<CallInst>(Inst)->getArgOperand(0);
 442
 443     // TODO: Change this to a do-while.
 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::use_iterator UI = Arg->use_begin(), UE = Arg->use_end();
 450            UI != UE; ) {
 451         // Increment UI now, because we may unlink its element.
 452         Use &U = *UI++;
 453         unsigned OperandNo = U.getOperandNo();
 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 GetArgRCIdentityRoot.
 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 (UI != UE &&
 479                     &PHI->getOperandUse(
 480                         PHINode::getOperandNumForIncomingValue(i)) == &*UI)
 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 (CallInst *CI : StoreStrongCalls)
 511       CI->setTailCall();
 512   StoreStrongCalls.clear();
 513
 514   return Changed;
 515 }
 516
 517 //===----------------------------------------------------------------------===//
 518 //                             Misc Pass Manager
 519 //===----------------------------------------------------------------------===//
 520
 521 char ObjCARCContract::ID = 0;
 522 INITIALIZE_PASS_BEGIN(ObjCARCContract, "objc-arc-contract",
 523                       "ObjC ARC contraction", false, false)
 524 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
 525 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 526 INITIALIZE_PASS_END(ObjCARCContract, "objc-arc-contract",
 527                     "ObjC ARC contraction", false, false)
 528
 529 void ObjCARCContract::getAnalysisUsage(AnalysisUsage &AU) const {
 530   AU.addRequired<AliasAnalysis>();
 531   AU.addRequired<DominatorTreeWrapperPass>();
 532   AU.setPreservesCFG();
 533 }
 534
 535 Pass *llvm::createObjCARCContractPass() { return new ObjCARCContract(); }
 536
 537 bool ObjCARCContract::doInitialization(Module &M) {
 538   // If nothing in the Module uses ARC, don't do anything.
 539   Run = ModuleHasARC(M);
 540   if (!Run)
 541     return false;
 542
 543   EP.Initialize(&M);
 544
 545   // Initialize RetainRVMarker.
 546   RetainRVMarker = nullptr;
 547   if (NamedMDNode *NMD =
 548           M.getNamedMetadata("clang.arc.retainAutoreleasedReturnValueMarker"))
 549     if (NMD->getNumOperands() == 1) {
 550       const MDNode *N = NMD->getOperand(0);
 551       if (N->getNumOperands() == 1)
 552         if (const MDString *S = dyn_cast<MDString>(N->getOperand(0)))
 553           RetainRVMarker = S;
 554     }
 555
 556   return false;
 557 }