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;
ObjCARCContract()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.
optimizeRetainCall(Function & F,Instruction * Retain)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.
contractAutorelease(Function & F,Instruction * Autorelease,ARCInstKind Class,SmallPtrSetImpl<Instruction * > & DependingInstructions,SmallPtrSetImpl<const BasicBlock * > & Visited)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
findSafeStoreForStoreStrongContraction(LoadInst * Load,Instruction * Release,ProvenanceAnalysis & PA,AliasAnalysis * AA)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 *
findRetainForStoreStrongContraction(Value * New,StoreInst * Store,Instruction * Release,ProvenanceAnalysis & PA)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 *
createCallInst(FunctionType * FTy,Value * Func,ArrayRef<Value * > Args,const Twine & NameStr,Instruction * InsertBefore,const DenseMap<BasicBlock *,ColorVector> & BlockColors)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 *
createCallInst(FunctionCallee Func,ArrayRef<Value * > Args,const Twine & NameStr,Instruction * InsertBefore,const DenseMap<BasicBlock *,ColorVector> & BlockColors)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.
tryToContractReleaseIntoStoreStrong(Instruction * Release,inst_iterator & Iter,const DenseMap<BasicBlock *,ColorVector> & BlockColors)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
tryToPeepholeInstruction(Function & F,Instruction * Inst,inst_iterator & Iter,SmallPtrSetImpl<Instruction * > & DependingInsts,SmallPtrSetImpl<const BasicBlock * > & Visited,bool & TailOkForStoreStrongs,const DenseMap<BasicBlock *,ColorVector> & BlockColors)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
runOnFunction(Function & F)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)
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)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
createObjCARCContractPass()769 Pass *llvm::createObjCARCContractPass() { return new ObjCARCContract(); }
770
doInitialization(Module & M)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 }
785