ObjCARCContract.cpp revision 7a7102d17f979918042bc040e27288d64a6bea5f 
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
35using namespace llvm;
36using namespace llvm::objcarc;
37
38STATISTIC(NumPeeps,       "Number of calls peephole-optimized");
39STATISTIC(NumStoreStrongs, "Number objc_storeStrong calls formed");
40
41namespace {
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
101char ObjCARCContract::ID = 0;
102INITIALIZE_PASS_BEGIN(ObjCARCContract,
103                      "objc-arc-contract", "ObjC ARC contraction", false, false)
104INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
105INITIALIZE_PASS_DEPENDENCY(DominatorTree)
106INITIALIZE_PASS_END(ObjCARCContract,
107                    "objc-arc-contract", "ObjC ARC contraction", false, false)
108
109Pass *llvm::createObjCARCContractPass() {
110  return new ObjCARCContract();
111}
112
113void ObjCARCContract::getAnalysisUsage(AnalysisUsage &AU) const {
114  AU.addRequired<AliasAnalysis>();
115  AU.addRequired<DominatorTree>();
116  AU.setPreservesCFG();
117}
118
119Constant *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
140Constant *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
155Constant *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.
172bool
173ObjCARCContract::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.
231void 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
318bool 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
343bool 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///
537