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