ecf8220ae95daefcb71dc704a4b0af71c0d545b9
[lldb.git] / llvm / lib / Transforms / ObjCARC / ObjCARCContract.cpp
1 //===- ObjCARCContract.cpp - ObjC ARC Optimization ------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 /// \file
9 /// This file defines late ObjC ARC optimizations. ARC stands for Automatic
10 /// Reference Counting and is a system for managing reference counts for objects
11 /// in Objective C.
12 ///
13 /// This specific file mainly deals with ``contracting'' multiple lower level
14 /// operations into singular higher level operations through pattern matching.
15 ///
16 /// WARNING: This file knows about certain library functions. It recognizes them
17 /// by name, and hardwires knowledge of their semantics.
18 ///
19 /// WARNING: This file knows about how certain Objective-C library functions are
20 /// used. Naive LLVM IR transformations which would otherwise be
21 /// behavior-preserving may break these assumptions.
22 ///
23 //===----------------------------------------------------------------------===//
24
25 // TODO: ObjCARCContract could insert PHI nodes when uses aren't
26 // dominated by single calls.
27
28 #include "ARCRuntimeEntryPoints.h"
29 #include "DependencyAnalysis.h"
30 #include "ObjCARC.h"
31 #include "ProvenanceAnalysis.h"
32 #include "llvm/ADT/Statistic.h"
33 #include "llvm/Analysis/EHPersonalities.h"
34 #include "llvm/IR/Dominators.h"
35 #include "llvm/IR/InlineAsm.h"
36 #include "llvm/IR/Operator.h"
37 #include "llvm/InitializePasses.h"
38 #include "llvm/Support/CommandLine.h"
39 #include "llvm/Support/Debug.h"
40 #include "llvm/Support/raw_ostream.h"
41
42 using namespace llvm;
43 using namespace llvm::objcarc;
44
45 #define DEBUG_TYPE "objc-arc-contract"
46
47 STATISTIC(NumPeeps,       "Number of calls peephole-optimized");
48 STATISTIC(NumStoreStrongs, "Number objc_storeStrong calls formed");
49
50 static cl::opt<unsigned> MaxBBSize("arc-contract-max-bb-size", cl::Hidden,
51     cl::desc("Maximum basic block size to discover the dominance relation of "
52              "two instructions in the same basic block"), cl::init(65535));
53
54 //===----------------------------------------------------------------------===//
55 //                                Declarations
56 //===----------------------------------------------------------------------===//
57
58 namespace {
59   /// Late ARC optimizations
60   ///
61   /// These change the IR in a way that makes it difficult to be analyzed by
62   /// ObjCARCOpt, so it's run late.
63   class ObjCARCContract : public FunctionPass {
64     bool Changed;
65     AliasAnalysis *AA;
66     DominatorTree *DT;
67     ProvenanceAnalysis PA;
68     ARCRuntimeEntryPoints EP;
69
70     /// A flag indicating whether this optimization pass should run.
71     bool Run;
72
73     /// The inline asm string to insert between calls and RetainRV calls to make
74     /// the optimization work on targets which need it.
75     const MDString *RVInstMarker;
76
77     /// The set of inserted objc_storeStrong calls. If at the end of walking the
78     /// function we have found no alloca instructions, these calls can be marked
79     /// "tail".
80     SmallPtrSet<CallInst *, 8> StoreStrongCalls;
81
82     /// Returns true if we eliminated Inst.
83     bool tryToPeepholeInstruction(
84         Function &F, Instruction *Inst, inst_iterator &Iter,
85         SmallPtrSetImpl<Instruction *> &DepInsts,
86         SmallPtrSetImpl<const BasicBlock *> &Visited,
87         bool &TailOkForStoreStrong,
88         const DenseMap<BasicBlock *, ColorVector> &BlockColors);
89
90     bool optimizeRetainCall(Function &F, Instruction *Retain);
91
92     bool
93     contractAutorelease(Function &F, Instruction *Autorelease,
94                         ARCInstKind Class,
95                         SmallPtrSetImpl<Instruction *> &DependingInstructions,
96                         SmallPtrSetImpl<const BasicBlock *> &Visited);
97
98     void tryToContractReleaseIntoStoreStrong(
99         Instruction *Release, inst_iterator &Iter,
100         const DenseMap<BasicBlock *, ColorVector> &BlockColors);
101
102     void getAnalysisUsage(AnalysisUsage &AU) const override;
103     bool doInitialization(Module &M) override;
104     bool runOnFunction(Function &F) override;
105
106   public:
107     static char ID;
108     ObjCARCContract() : FunctionPass(ID) {
109       initializeObjCARCContractPass(*PassRegistry::getPassRegistry());
110     }
111   };
112 }
113
114 //===----------------------------------------------------------------------===//
115 //                               Implementation
116 //===----------------------------------------------------------------------===//
117
118 /// Turn objc_retain into objc_retainAutoreleasedReturnValue if the operand is a
119 /// return value. We do this late so we do not disrupt the dataflow analysis in
120 /// ObjCARCOpt.
121 bool ObjCARCContract::optimizeRetainCall(Function &F, Instruction *Retain) {
122   ImmutableCallSite CS(GetArgRCIdentityRoot(Retain));
123   const Instruction *Call = CS.getInstruction();
124   if (!Call)
125     return false;
126   if (Call->getParent() != Retain->getParent())
127     return false;
128
129   // Check that the call is next to the retain.
130   BasicBlock::const_iterator I = ++Call->getIterator();
131   while (IsNoopInstruction(&*I))
132     ++I;
133   if (&*I != Retain)
134     return false;
135
136   // Turn it to an objc_retainAutoreleasedReturnValue.
137   Changed = true;
138   ++NumPeeps;
139
140   LLVM_DEBUG(
141       dbgs() << "Transforming objc_retain => "
142                 "objc_retainAutoreleasedReturnValue since the operand is a "
143                 "return value.\nOld: "
144              << *Retain << "\n");
145
146   // We do not have to worry about tail calls/does not throw since
147   // retain/retainRV have the same properties.
148   Function *Decl = EP.get(ARCRuntimeEntryPointKind::RetainRV);
149   cast<CallInst>(Retain)->setCalledFunction(Decl);
150
151   LLVM_DEBUG(dbgs() << "New: " << *Retain << "\n");
152   return true;
153 }
154
155 /// Merge an autorelease with a retain into a fused call.
156 bool ObjCARCContract::contractAutorelease(
157     Function &F, Instruction *Autorelease, ARCInstKind Class,
158     SmallPtrSetImpl<Instruction *> &DependingInstructions,
159     SmallPtrSetImpl<const BasicBlock *> &Visited) {
160   const Value *Arg = GetArgRCIdentityRoot(Autorelease);
161
162   // Check that there are no instructions between the retain and the autorelease
163   // (such as an autorelease_pop) which may change the count.
164   CallInst *Retain = nullptr;
165   if (Class == ARCInstKind::AutoreleaseRV)
166     FindDependencies(RetainAutoreleaseRVDep, Arg,
167                      Autorelease->getParent(), Autorelease,
168                      DependingInstructions, Visited, PA);
169   else
170     FindDependencies(RetainAutoreleaseDep, Arg,
171                      Autorelease->getParent(), Autorelease,
172                      DependingInstructions, Visited, PA);
173
174   Visited.clear();
175   if (DependingInstructions.size() != 1) {
176     DependingInstructions.clear();
177     return false;
178   }
179
180   Retain = dyn_cast_or_null<CallInst>(*DependingInstructions.begin());
181   DependingInstructions.clear();
182
183   if (!Retain || GetBasicARCInstKind(Retain) != ARCInstKind::Retain ||
184       GetArgRCIdentityRoot(Retain) != Arg)
185     return false;
186
187   Changed = true;
188   ++NumPeeps;
189
190   LLVM_DEBUG(dbgs() << "    Fusing retain/autorelease!\n"
191                        "        Autorelease:"
192                     << *Autorelease
193                     << "\n"
194                        "        Retain: "
195                     << *Retain << "\n");
196
197   Function *Decl = EP.get(Class == ARCInstKind::AutoreleaseRV
198                               ? ARCRuntimeEntryPointKind::RetainAutoreleaseRV
199                               : ARCRuntimeEntryPointKind::RetainAutorelease);
200   Retain->setCalledFunction(Decl);
201
202   LLVM_DEBUG(dbgs() << "        New RetainAutorelease: " << *Retain << "\n");
203
204   EraseInstruction(Autorelease);
205   return true;
206 }
207
208 static StoreInst *findSafeStoreForStoreStrongContraction(LoadInst *Load,
209                                                          Instruction *Release,
210                                                          ProvenanceAnalysis &PA,
211                                                          AliasAnalysis *AA) {
212   StoreInst *Store = nullptr;
213   bool SawRelease = false;
214
215   // Get the location associated with Load.
216   MemoryLocation Loc = MemoryLocation::get(Load);
217   auto *LocPtr = Loc.Ptr->stripPointerCasts();
218
219   // Walk down to find the store and the release, which may be in either order.
220   for (auto I = std::next(BasicBlock::iterator(Load)),
221             E = Load->getParent()->end();
222        I != E; ++I) {
223     // If we found the store we were looking for and saw the release,
224     // break. There is no more work to be done.
225     if (Store && SawRelease)
226       break;
227
228     // Now we know that we have not seen either the store or the release. If I
229     // is the release, mark that we saw the release and continue.
230     Instruction *Inst = &*I;
231     if (Inst == Release) {
232       SawRelease = true;
233       continue;
234     }
235
236     // Otherwise, we check if Inst is a "good" store. Grab the instruction class
237     // of Inst.
238     ARCInstKind Class = GetBasicARCInstKind(Inst);
239
240     // If Inst is an unrelated retain, we don't care about it.
241     //
242     // TODO: This is one area where the optimization could be made more
243     // aggressive.
244     if (IsRetain(Class))
245       continue;
246
247     // If we have seen the store, but not the release...
248     if (Store) {
249       // We need to make sure that it is safe to move the release from its
250       // current position to the store. This implies proving that any
251       // instruction in between Store and the Release conservatively can not use
252       // the RCIdentityRoot of Release. If we can prove we can ignore Inst, so
253       // continue...
254       if (!CanUse(Inst, Load, PA, Class)) {
255         continue;
256       }
257
258       // Otherwise, be conservative and return nullptr.
259       return nullptr;
260     }
261
262     // Ok, now we know we have not seen a store yet. See if Inst can write to
263     // our load location, if it can not, just ignore the instruction.
264     if (!isModSet(AA->getModRefInfo(Inst, Loc)))
265       continue;
266
267     Store = dyn_cast<StoreInst>(Inst);
268
269     // If Inst can, then check if Inst is a simple store. If Inst is not a
270     // store or a store that is not simple, then we have some we do not
271     // understand writing to this memory implying we can not move the load
272     // over the write to any subsequent store that we may find.
273     if (!Store || !Store->isSimple())
274       return nullptr;
275
276     // Then make sure that the pointer we are storing to is Ptr. If so, we
277     // found our Store!
278     if (Store->getPointerOperand()->stripPointerCasts() == LocPtr)
279       continue;
280
281     // Otherwise, we have an unknown store to some other ptr that clobbers
282     // Loc.Ptr. Bail!
283     return nullptr;
284   }
285
286   // If we did not find the store or did not see the release, fail.
287   if (!Store || !SawRelease)
288     return nullptr;
289
290   // We succeeded!
291   return Store;
292 }
293
294 static Instruction *
295 findRetainForStoreStrongContraction(Value *New, StoreInst *Store,
296                                     Instruction *Release,
297                                     ProvenanceAnalysis &PA) {
298   // Walk up from the Store to find the retain.
299   BasicBlock::iterator I = Store->getIterator();
300   BasicBlock::iterator Begin = Store->getParent()->begin();
301   while (I != Begin && GetBasicARCInstKind(&*I) != ARCInstKind::Retain) {
302     Instruction *Inst = &*I;
303
304     // It is only safe to move the retain to the store if we can prove
305     // conservatively that nothing besides the release can decrement reference
306     // counts in between the retain and the store.
307     if (CanDecrementRefCount(Inst, New, PA) && Inst != Release)
308       return nullptr;
309     --I;
310   }
311   Instruction *Retain = &*I;
312   if (GetBasicARCInstKind(Retain) != ARCInstKind::Retain)
313     return nullptr;
314   if (GetArgRCIdentityRoot(Retain) != New)
315     return nullptr;
316   return Retain;
317 }
318
319 /// Create a call instruction with the correct funclet token. Should be used
320 /// instead of calling CallInst::Create directly.
321 static CallInst *
322 createCallInst(FunctionType *FTy, Value *Func, ArrayRef<Value *> Args,
323                const Twine &NameStr, Instruction *InsertBefore,
324                const DenseMap<BasicBlock *, ColorVector> &BlockColors) {
325   SmallVector<OperandBundleDef, 1> OpBundles;
326   if (!BlockColors.empty()) {
327     const ColorVector &CV = BlockColors.find(InsertBefore->getParent())->second;
328     assert(CV.size() == 1 && "non-unique color for block!");
329     Instruction *EHPad = CV.front()->getFirstNonPHI();
330     if (EHPad->isEHPad())
331       OpBundles.emplace_back("funclet", EHPad);
332   }
333
334   return CallInst::Create(FTy, Func, Args, OpBundles, NameStr, InsertBefore);
335 }
336
337 static CallInst *
338 createCallInst(FunctionCallee Func, ArrayRef<Value *> Args, const Twine &NameStr,
339                Instruction *InsertBefore,
340                const DenseMap<BasicBlock *, ColorVector> &BlockColors) {
341   return createCallInst(Func.getFunctionType(), Func.getCallee(), Args, NameStr,
342                         InsertBefore, BlockColors);
343 }
344
345 /// Attempt to merge an objc_release with a store, load, and objc_retain to form
346 /// an objc_storeStrong. An objc_storeStrong:
347 ///
348 ///   objc_storeStrong(i8** %old_ptr, i8* new_value)
349 ///
350 /// is equivalent to the following IR sequence:
351 ///
352 ///   ; Load old value.
353 ///   %old_value = load i8** %old_ptr               (1)
354 ///
355 ///   ; Increment the new value and then release the old value. This must occur
356 ///   ; in order in case old_value releases new_value in its destructor causing
357 ///   ; us to potentially have a dangling ptr.
358 ///   tail call i8* @objc_retain(i8* %new_value)    (2)
359 ///   tail call void @objc_release(i8* %old_value)  (3)
360 ///
361 ///   ; Store the new_value into old_ptr
362 ///   store i8* %new_value, i8** %old_ptr           (4)
363 ///
364 /// The safety of this optimization is based around the following
365 /// considerations:
366 ///
367 ///  1. We are forming the store strong at the store. Thus to perform this
368 ///     optimization it must be safe to move the retain, load, and release to
369 ///     (4).
370 ///  2. We need to make sure that any re-orderings of (1), (2), (3), (4) are
371 ///     safe.
372 void ObjCARCContract::tryToContractReleaseIntoStoreStrong(
373     Instruction *Release, inst_iterator &Iter,
374     const DenseMap<BasicBlock *, ColorVector> &BlockColors) {
375   // See if we are releasing something that we just loaded.
376   auto *Load = dyn_cast<LoadInst>(GetArgRCIdentityRoot(Release));
377   if (!Load || !Load->isSimple())
378     return;
379
380   // For now, require everything to be in one basic block.
381   BasicBlock *BB = Release->getParent();
382   if (Load->getParent() != BB)
383     return;
384
385   // First scan down the BB from Load, looking for a store of the RCIdentityRoot
386   // of Load's
387   StoreInst *Store =
388       findSafeStoreForStoreStrongContraction(Load, Release, PA, AA);
389   // If we fail, bail.
390   if (!Store)
391     return;
392
393   // Then find what new_value's RCIdentity Root is.
394   Value *New = GetRCIdentityRoot(Store->getValueOperand());
395
396   // Then walk up the BB and look for a retain on New without any intervening
397   // instructions which conservatively might decrement ref counts.
398   Instruction *Retain =
399       findRetainForStoreStrongContraction(New, Store, Release, PA);
400
401   // If we fail, bail.
402   if (!Retain)
403     return;
404
405   Changed = true;
406   ++NumStoreStrongs;
407
408   LLVM_DEBUG(
409       llvm::dbgs() << "    Contracting retain, release into objc_storeStrong.\n"
410                    << "        Old:\n"
411                    << "            Store:   " << *Store << "\n"
412                    << "            Release: " << *Release << "\n"
413                    << "            Retain:  " << *Retain << "\n"
414                    << "            Load:    " << *Load << "\n");
415
416   LLVMContext &C = Release->getContext();
417   Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
418   Type *I8XX = PointerType::getUnqual(I8X);
419
420   Value *Args[] = { Load->getPointerOperand(), New };
421   if (Args[0]->getType() != I8XX)
422     Args[0] = new BitCastInst(Args[0], I8XX, "", Store);
423   if (Args[1]->getType() != I8X)
424     Args[1] = new BitCastInst(Args[1], I8X, "", Store);
425   Function *Decl = EP.get(ARCRuntimeEntryPointKind::StoreStrong);
426   CallInst *StoreStrong = createCallInst(Decl, Args, "", Store, BlockColors);
427   StoreStrong->setDoesNotThrow();
428   StoreStrong->setDebugLoc(Store->getDebugLoc());
429
430   // We can't set the tail flag yet, because we haven't yet determined
431   // whether there are any escaping allocas. Remember this call, so that
432   // we can set the tail flag once we know it's safe.
433   StoreStrongCalls.insert(StoreStrong);
434
435   LLVM_DEBUG(llvm::dbgs() << "        New Store Strong: " << *StoreStrong
436                           << "\n");
437
438   if (&*Iter == Retain) ++Iter;
439   if (&*Iter == Store) ++Iter;
440   Store->eraseFromParent();
441   Release->eraseFromParent();
442   EraseInstruction(Retain);
443   if (Load->use_empty())
444     Load->eraseFromParent();
445 }
446
447 bool ObjCARCContract::tryToPeepholeInstruction(
448     Function &F, Instruction *Inst, inst_iterator &Iter,
449     SmallPtrSetImpl<Instruction *> &DependingInsts,
450     SmallPtrSetImpl<const BasicBlock *> &Visited, bool &TailOkForStoreStrongs,
451     const DenseMap<BasicBlock *, ColorVector> &BlockColors) {
452   // Only these library routines return their argument. In particular,
453   // objc_retainBlock does not necessarily return its argument.
454   ARCInstKind Class = GetBasicARCInstKind(Inst);
455   switch (Class) {
456   case ARCInstKind::FusedRetainAutorelease:
457   case ARCInstKind::FusedRetainAutoreleaseRV:
458     return false;
459   case ARCInstKind::Autorelease:
460   case ARCInstKind::AutoreleaseRV:
461     return contractAutorelease(F, Inst, Class, DependingInsts, Visited);
462   case ARCInstKind::Retain:
463     // Attempt to convert retains to retainrvs if they are next to function
464     // calls.
465     if (!optimizeRetainCall(F, Inst))
466       return false;
467     // If we succeed in our optimization, fall through.
468     LLVM_FALLTHROUGH;
469   case ARCInstKind::RetainRV:
470   case ARCInstKind::ClaimRV: {
471     // If we're compiling for a target which needs a special inline-asm
472     // marker to do the return value optimization, insert it now.
473     if (!RVInstMarker)
474       return false;
475     BasicBlock::iterator BBI = Inst->getIterator();
476     BasicBlock *InstParent = Inst->getParent();
477
478     // Step up to see if the call immediately precedes the RV call.
479     // If it's an invoke, we have to cross a block boundary. And we have
480     // to carefully dodge no-op instructions.
481     do {
482       if (BBI == InstParent->begin()) {
483         BasicBlock *Pred = InstParent->getSinglePredecessor();
484         if (!Pred)
485           goto decline_rv_optimization;
486         BBI = Pred->getTerminator()->getIterator();
487         break;
488       }
489       --BBI;
490     } while (IsNoopInstruction(&*BBI));
491
492     if (&*BBI == GetArgRCIdentityRoot(Inst)) {
493       LLVM_DEBUG(dbgs() << "Adding inline asm marker for the return value "
494                            "optimization.\n");
495       Changed = true;
496       InlineAsm *IA =
497           InlineAsm::get(FunctionType::get(Type::getVoidTy(Inst->getContext()),
498                                            /*isVarArg=*/false),
499                          RVInstMarker->getString(),
500                          /*Constraints=*/"", /*hasSideEffects=*/true);
501
502       createCallInst(IA, None, "", Inst, BlockColors);
503     }
504   decline_rv_optimization:
505     return false;
506   }
507   case ARCInstKind::InitWeak: {
508     // objc_initWeak(p, null) => *p = null
509     CallInst *CI = cast<CallInst>(Inst);
510     if (IsNullOrUndef(CI->getArgOperand(1))) {
511       Value *Null = ConstantPointerNull::get(cast<PointerType>(CI->getType()));
512       Changed = true;
513       new StoreInst(Null, CI->getArgOperand(0), CI);
514
515       LLVM_DEBUG(dbgs() << "OBJCARCContract: Old = " << *CI << "\n"
516                         << "                 New = " << *Null << "\n");
517
518       CI->replaceAllUsesWith(Null);
519       CI->eraseFromParent();
520     }
521     return true;
522   }
523   case ARCInstKind::Release:
524     // Try to form an objc store strong from our release. If we fail, there is
525     // nothing further to do below, so continue.
526     tryToContractReleaseIntoStoreStrong(Inst, Iter, BlockColors);
527     return true;
528   case ARCInstKind::User:
529     // Be conservative if the function has any alloca instructions.
530     // Technically we only care about escaping alloca instructions,
531     // but this is sufficient to handle some interesting cases.
532     if (isa<AllocaInst>(Inst))
533       TailOkForStoreStrongs = false;
534     return true;
535   case ARCInstKind::IntrinsicUser:
536     // Remove calls to @llvm.objc.clang.arc.use(...).
537     Inst->eraseFromParent();
538     return true;
539   default:
540     return true;
541   }
542 }
543
544 //===----------------------------------------------------------------------===//
545 //                              Top Level Driver
546 //===----------------------------------------------------------------------===//
547
548 bool ObjCARCContract::runOnFunction(Function &F) {
549   if (!EnableARCOpts)
550     return false;
551
552   // If nothing in the Module uses ARC, don't do anything.
553   if (!Run)
554     return false;
555
556   Changed = false;
557   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
558   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
559
560   PA.setAA(&getAnalysis<AAResultsWrapperPass>().getAAResults());
561
562   DenseMap<BasicBlock *, ColorVector> BlockColors;
563   if (F.hasPersonalityFn() &&
564       isScopedEHPersonality(classifyEHPersonality(F.getPersonalityFn())))
565     BlockColors = colorEHFunclets(F);
566
567   LLVM_DEBUG(llvm::dbgs() << "**** ObjCARC Contract ****\n");
568
569   // Track whether it's ok to mark objc_storeStrong calls with the "tail"
570   // keyword. Be conservative if the function has variadic arguments.
571   // It seems that functions which "return twice" are also unsafe for the
572   // "tail" argument, because they are setjmp, which could need to
573   // return to an earlier stack state.
574   bool TailOkForStoreStrongs =
575       !F.isVarArg() && !F.callsFunctionThatReturnsTwice();
576
577   // For ObjC library calls which return their argument, replace uses of the
578   // argument with uses of the call return value, if it dominates the use. This
579   // reduces register pressure.
580   SmallPtrSet<Instruction *, 4> DependingInstructions;
581   SmallPtrSet<const BasicBlock *, 4> Visited;
582
583   // Cache the basic block size.
584   DenseMap<const BasicBlock *, unsigned> BBSizeMap;
585
586   // A lambda that lazily computes the size of a basic block and determines
587   // whether the size exceeds MaxBBSize.
588   auto IsLargeBB = [&](const BasicBlock *BB) {
589     unsigned BBSize;
590     auto I = BBSizeMap.find(BB);
591
592     if (I != BBSizeMap.end())
593       BBSize = I->second;
594     else
595       BBSize = BBSizeMap[BB] = BB->size();
596
597     return BBSize > MaxBBSize;
598   };
599
600   for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E;) {
601     Instruction *Inst = &*I++;
602
603     LLVM_DEBUG(dbgs() << "Visiting: " << *Inst << "\n");
604
605     // First try to peephole Inst. If there is nothing further we can do in
606     // terms of undoing objc-arc-expand, process the next inst.
607     if (tryToPeepholeInstruction(F, Inst, I, DependingInstructions, Visited,
608                                  TailOkForStoreStrongs, BlockColors))
609       continue;
610
611     // Otherwise, try to undo objc-arc-expand.
612
613     // Don't use GetArgRCIdentityRoot because we don't want to look through bitcasts
614     // and such; to do the replacement, the argument must have type i8*.
615
616     // Function for replacing uses of Arg dominated by Inst.
617     auto ReplaceArgUses = [Inst, IsLargeBB, this](Value *Arg) {
618       // If we're compiling bugpointed code, don't get in trouble.
619       if (!isa<Instruction>(Arg) && !isa<Argument>(Arg))
620         return;
621
622       // Look through the uses of the pointer.
623       for (Value::use_iterator UI = Arg->use_begin(), UE = Arg->use_end();
624            UI != UE; ) {
625         // Increment UI now, because we may unlink its element.
626         Use &U = *UI++;
627         unsigned OperandNo = U.getOperandNo();
628
629         // Don't replace the uses if Inst and the user belong to the same basic
630         // block and the size of the basic block is large. We don't want to call
631         // DominatorTree::dominate in that case. We can remove this check if we
632         // can use OrderedBasicBlock to compute the dominance relation between
633         // two instructions, but that's not currently possible since it doesn't
634         // recompute the instruction ordering when new instructions are inserted
635         // to the basic block.
636         if (Inst->getParent() == cast<Instruction>(U.getUser())->getParent() &&
637             IsLargeBB(Inst->getParent()))
638           continue;
639
640         // If the call's return value dominates a use of the call's argument
641         // value, rewrite the use to use the return value. We check for
642         // reachability here because an unreachable call is considered to
643         // trivially dominate itself, which would lead us to rewriting its
644         // argument in terms of its return value, which would lead to
645         // infinite loops in GetArgRCIdentityRoot.
646         if (!DT->isReachableFromEntry(U) || !DT->dominates(Inst, U))
647           continue;
648
649         Changed = true;
650         Instruction *Replacement = Inst;
651         Type *UseTy = U.get()->getType();
652         if (PHINode *PHI = dyn_cast<PHINode>(U.getUser())) {
653           // For PHI nodes, insert the bitcast in the predecessor block.
654           unsigned ValNo = PHINode::getIncomingValueNumForOperand(OperandNo);
655           BasicBlock *IncomingBB = PHI->getIncomingBlock(ValNo);
656           if (Replacement->getType() != UseTy) {
657             // A catchswitch is both a pad and a terminator, meaning a basic
658             // block with a catchswitch has no insertion point. Keep going up
659             // the dominator tree until we find a non-catchswitch.
660             BasicBlock *InsertBB = IncomingBB;
661             while (isa<CatchSwitchInst>(InsertBB->getFirstNonPHI())) {
662               InsertBB = DT->getNode(InsertBB)->getIDom()->getBlock();
663             }
664
665             assert(DT->dominates(Inst, &InsertBB->back()) &&
666                    "Invalid insertion point for bitcast");
667             Replacement =
668                 new BitCastInst(Replacement, UseTy, "", &InsertBB->back());
669           }
670
671           // While we're here, rewrite all edges for this PHI, rather
672           // than just one use at a time, to minimize the number of
673           // bitcasts we emit.
674           for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i)
675             if (PHI->getIncomingBlock(i) == IncomingBB) {
676               // Keep the UI iterator valid.
677               if (UI != UE &&
678                   &PHI->getOperandUse(
679                       PHINode::getOperandNumForIncomingValue(i)) == &*UI)
680                 ++UI;
681               PHI->setIncomingValue(i, Replacement);
682             }
683         } else {
684           if (Replacement->getType() != UseTy)
685             Replacement = new BitCastInst(Replacement, UseTy, "",
686                                           cast<Instruction>(U.getUser()));
687           U.set(Replacement);
688         }
689       }
690     };
691
692
693     Value *Arg = cast<CallInst>(Inst)->getArgOperand(0);
694     Value *OrigArg = Arg;
695
696     // TODO: Change this to a do-while.
697     for (;;) {
698       ReplaceArgUses(Arg);
699
700       // If Arg is a no-op casted pointer, strip one level of casts and iterate.
701       if (const BitCastInst *BI = dyn_cast<BitCastInst>(Arg))
702         Arg = BI->getOperand(0);
703       else if (isa<GEPOperator>(Arg) &&
704                cast<GEPOperator>(Arg)->hasAllZeroIndices())
705         Arg = cast<GEPOperator>(Arg)->getPointerOperand();
706       else if (isa<GlobalAlias>(Arg) &&
707                !cast<GlobalAlias>(Arg)->isInterposable())
708         Arg = cast<GlobalAlias>(Arg)->getAliasee();
709       else {
710         // If Arg is a PHI node, get PHIs that are equivalent to it and replace
711         // their uses.
712         if (PHINode *PN = dyn_cast<PHINode>(Arg)) {
713           SmallVector<Value *, 1> PHIList;
714           getEquivalentPHIs(*PN, PHIList);
715           for (Value *PHI : PHIList)
716             ReplaceArgUses(PHI);
717         }
718         break;
719       }
720     }
721
722     // Replace bitcast users of Arg that are dominated by Inst.
723     SmallVector<BitCastInst *, 2> BitCastUsers;
724
725     // Add all bitcast users of the function argument first.
726     for (User *U : OrigArg->users())
727       if (auto *BC = dyn_cast<BitCastInst>(U))
728         BitCastUsers.push_back(BC);
729
730     // Replace the bitcasts with the call return. Iterate until list is empty.
731     while (!BitCastUsers.empty()) {
732       auto *BC = BitCastUsers.pop_back_val();
733       for (User *U : BC->users())
734         if (auto *B = dyn_cast<BitCastInst>(U))
735           BitCastUsers.push_back(B);
736
737       ReplaceArgUses(BC);
738     }
739   }
740
741   // If this function has no escaping allocas or suspicious vararg usage,
742   // objc_storeStrong calls can be marked with the "tail" keyword.
743   if (TailOkForStoreStrongs)
744     for (CallInst *CI : StoreStrongCalls)
745       CI->setTailCall();
746   StoreStrongCalls.clear();
747
748   return Changed;
749 }
750
751 //===----------------------------------------------------------------------===//
752 //                             Misc Pass Manager
753 //===----------------------------------------------------------------------===//
754
755 char ObjCARCContract::ID = 0;
756 INITIALIZE_PASS_BEGIN(ObjCARCContract, "objc-arc-contract",
757                       "ObjC ARC contraction", false, false)
758 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
759 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
760 INITIALIZE_PASS_END(ObjCARCContract, "objc-arc-contract",
761                     "ObjC ARC contraction", false, false)
762
763 void ObjCARCContract::getAnalysisUsage(AnalysisUsage &AU) const {
764   AU.addRequired<AAResultsWrapperPass>();
765   AU.addRequired<DominatorTreeWrapperPass>();
766   AU.setPreservesCFG();
767 }
768
769 Pass *llvm::createObjCARCContractPass() { return new ObjCARCContract(); }
770
771 bool ObjCARCContract::doInitialization(Module &M) {
772   // If nothing in the Module uses ARC, don't do anything.
773   Run = ModuleHasARC(M);
774   if (!Run)
775     return false;
776
777   EP.init(&M);
778
779   // Initialize RVInstMarker.
780   const char *MarkerKey = "clang.arc.retainAutoreleasedReturnValueMarker";
781   RVInstMarker = dyn_cast_or_null<MDString>(M.getModuleFlag(MarkerKey));
782
783   return false;
784 }