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