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