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
39using namespace llvm;
40using namespace llvm::objcarc;
41
42STATISTIC(NumPeeps,       "Number of calls peephole-optimized");
43STATISTIC(NumStoreStrongs, "Number objc_storeStrong calls formed");
44
45namespace {
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
105char ObjCARCContract::ID = 0;
106INITIALIZE_PASS_BEGIN(ObjCARCContract,
107                      "objc-arc-contract", "ObjC ARC contraction", false, false)
108INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
109INITIALIZE_PASS_DEPENDENCY(DominatorTree)
110INITIALIZE_PASS_END(ObjCARCContract,
111                    "objc-arc-contract", "ObjC ARC contraction", false, false)
112
113Pass *llvm::createObjCARCContractPass() {
114  return new ObjCARCContract();
115}
116
117void ObjCARCContract::getAnalysisUsage(AnalysisUsage &AU) const {
118  AU.addRequired<AliasAnalysis>();
119  AU.addRequired<DominatorTree>();
120  AU.setPreservesCFG();
121}
122
123Constant *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
144Constant *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
159Constant *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.
176bool
177ObjCARCContract::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.
235void 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
322bool 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
347bool 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    default:
457      continue;
458    }
459
460    DEBUG(dbgs() << "ObjCARCContract: Finished List.\n\n");
461
462    // Don't use GetObjCArg because we don't want to look through bitcasts
463    // and such; to do the replacement, the argument must have type i8*.
464    const Value *Arg = cast<CallInst>(Inst)->getArgOperand(0);
465    for (;;) {
466      // If we're compiling bugpointed code, don't get in trouble.
467      if (!isa<Instruction>(Arg) && !isa<Argument>(Arg))
468        break;
469      // Look through the uses of the pointer.
470      for (Value::const_use_iterator UI = Arg->use_begin(), UE = Arg->use_end();
471           UI != UE; ) {
472        Use &U = UI.getUse();
473        unsigned OperandNo = UI.getOperandNo();
474        ++UI; // Increment UI now, because we may unlink its element.
475
476        // If the call's return value dominates a use of the call's argument
477        // value, rewrite the use to use the return value. We check for
478        // reachability here because an unreachable call is considered to
479        // trivially dominate itself, which would lead us to rewriting its
480        // argument in terms of its return value, which would lead to
481        // infinite loops in GetObjCArg.
482        if (DT->isReachableFromEntry(U) && DT->dominates(Inst, U)) {
483          Changed = true;
484          Instruction *Replacement = Inst;
485          Type *UseTy = U.get()->getType();
486          if (PHINode *PHI = dyn_cast<PHINode>(U.getUser())) {
487            // For PHI nodes, insert the bitcast in the predecessor block.
488            unsigned ValNo = PHINode::getIncomingValueNumForOperand(OperandNo);
489            BasicBlock *BB = PHI->getIncomingBlock(ValNo);
490            if (Replacement->getType() != UseTy)
491              Replacement = new BitCastInst(Replacement, UseTy, "",
492                                            &BB->back());
493            // While we're here, rewrite all edges for this PHI, rather
494            // than just one use at a time, to minimize the number of
495            // bitcasts we emit.
496            for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i)
497              if (PHI->getIncomingBlock(i) == BB) {
498                // Keep the UI iterator valid.
499                if (&PHI->getOperandUse(
500                      PHINode::getOperandNumForIncomingValue(i)) ==
501                    &UI.getUse())
502                  ++UI;
503                PHI->setIncomingValue(i, Replacement);
504              }
505          } else {
506            if (Replacement->getType() != UseTy)
507              Replacement = new BitCastInst(Replacement, UseTy, "",
508                                            cast<Instruction>(U.getUser()));
509            U.set(Replacement);
510          }
511        }
512      }
513
514      // If Arg is a no-op casted pointer, strip one level of casts and iterate.
515      if (const BitCastInst *BI = dyn_cast<BitCastInst>(Arg))
516        Arg = BI->getOperand(0);
517      else if (isa<GEPOperator>(Arg) &&
518               cast<GEPOperator>(Arg)->hasAllZeroIndices())
519        Arg = cast<GEPOperator>(Arg)->getPointerOperand();
520      else if (isa<GlobalAlias>(Arg) &&
521               !cast<GlobalAlias>(Arg)->mayBeOverridden())
522        Arg = cast<GlobalAlias>(Arg)->getAliasee();
523      else
524        break;
525    }
526  }
527
528  // If this function has no escaping allocas or suspicious vararg usage,
529  // objc_storeStrong calls can be marked with the "tail" keyword.
530  if (TailOkForStoreStrongs)
531    for (SmallPtrSet<CallInst *, 8>::iterator I = StoreStrongCalls.begin(),
532         E = StoreStrongCalls.end(); I != E; ++I)
533      (*I)->setTailCall();
534  StoreStrongCalls.clear();
535
536  return Changed;
537}
538