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