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