Use range based for loops to avoid needing to re-mention SmallPtrSet size.
[oota-llvm.git] / 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 namespace {
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                              SmallPtrSetImpl<Instruction *>
76                                &DependingInstructions,
77                              SmallPtrSetImpl<const BasicBlock *>
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
95 char ObjCARCContract::ID = 0;
96 INITIALIZE_PASS_BEGIN(ObjCARCContract,
97                       "objc-arc-contract", "ObjC ARC contraction", false, false)
98 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
99 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
100 INITIALIZE_PASS_END(ObjCARCContract,
101                     "objc-arc-contract", "ObjC ARC contraction", false, false)
102
103 Pass *llvm::createObjCARCContractPass() {
104   return new ObjCARCContract();
105 }
106
107 void 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.
116 bool
117 ObjCARCContract::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.
150 bool
151 ObjCARCContract::ContractAutorelease(Function &F, Instruction *Autorelease,
152                                      InstructionClass Class,
153                                      SmallPtrSetImpl<Instruction *>
154                                        &DependingInstructions,
155                                      SmallPtrSetImpl<const BasicBlock *>
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.
209 void 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
295 bool 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
317 bool 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 (CallInst *CI : StoreStrongCalls)
512       CI->setTailCall();
513   StoreStrongCalls.clear();
514
515   return Changed;
516 }