1 //===- ObjCARCContract.cpp - ObjC ARC Optimization ------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 /// This file defines late ObjC ARC optimizations. ARC stands for Automatic
11 /// Reference Counting and is a system for managing reference counts for objects
14 /// This specific file mainly deals with ``contracting'' multiple lower level
15 /// operations into singular higher level operations through pattern matching.
17 /// WARNING: This file knows about certain library functions. It recognizes them
18 /// by name, and hardwires knowledge of their semantics.
20 /// WARNING: This file knows about how certain Objective-C library functions are
21 /// used. Naive LLVM IR transformations which would otherwise be
22 /// behavior-preserving may break these assumptions.
24 //===----------------------------------------------------------------------===//
26 // TODO: ObjCARCContract could insert PHI nodes when uses aren't
27 // dominated by single calls.
30 #include "ARCRuntimeEntryPoints.h"
31 #include "DependencyAnalysis.h"
32 #include "ProvenanceAnalysis.h"
33 #include "llvm/ADT/Statistic.h"
34 #include "llvm/IR/Dominators.h"
35 #include "llvm/IR/InlineAsm.h"
36 #include "llvm/IR/Operator.h"
37 #include "llvm/Support/Debug.h"
40 using namespace llvm::objcarc;
42 #define DEBUG_TYPE "objc-arc-contract"
44 STATISTIC(NumPeeps, "Number of calls peephole-optimized");
45 STATISTIC(NumStoreStrongs, "Number objc_storeStrong calls formed");
47 //===----------------------------------------------------------------------===//
49 //===----------------------------------------------------------------------===//
52 /// \brief Late ARC optimizations
54 /// These change the IR in a way that makes it difficult to be analyzed by
55 /// ObjCARCOpt, so it's run late.
56 class ObjCARCContract : public FunctionPass {
60 ProvenanceAnalysis PA;
61 ARCRuntimeEntryPoints EP;
63 /// A flag indicating whether this optimization pass should run.
66 /// The inline asm string to insert between calls and RetainRV calls to make
67 /// the optimization work on targets which need it.
68 const MDString *RetainRVMarker;
70 /// The set of inserted objc_storeStrong calls. If at the end of walking the
71 /// function we have found no alloca instructions, these calls can be marked
73 SmallPtrSet<CallInst *, 8> StoreStrongCalls;
75 /// Returns true if we eliminated Inst.
76 bool tryToPeepholeInstruction(Function &F, Instruction *Inst,
78 SmallPtrSetImpl<Instruction *> &DepInsts,
79 SmallPtrSetImpl<const BasicBlock *> &Visited,
80 bool &TailOkForStoreStrong);
82 bool optimizeRetainCall(Function &F, Instruction *Retain);
85 contractAutorelease(Function &F, Instruction *Autorelease,
87 SmallPtrSetImpl<Instruction *> &DependingInstructions,
88 SmallPtrSetImpl<const BasicBlock *> &Visited);
90 void tryToContractReleaseIntoStoreStrong(Instruction *Release,
93 void getAnalysisUsage(AnalysisUsage &AU) const override;
94 bool doInitialization(Module &M) override;
95 bool runOnFunction(Function &F) override;
99 ObjCARCContract() : FunctionPass(ID) {
100 initializeObjCARCContractPass(*PassRegistry::getPassRegistry());
105 //===----------------------------------------------------------------------===//
107 //===----------------------------------------------------------------------===//
109 /// Turn objc_retain into objc_retainAutoreleasedReturnValue if the operand is a
110 /// return value. We do this late so we do not disrupt the dataflow analysis in
112 bool ObjCARCContract::optimizeRetainCall(Function &F, Instruction *Retain) {
113 ImmutableCallSite CS(GetArgRCIdentityRoot(Retain));
114 const Instruction *Call = CS.getInstruction();
117 if (Call->getParent() != Retain->getParent())
120 // Check that the call is next to the retain.
121 BasicBlock::const_iterator I = Call;
123 while (IsNoopInstruction(I)) ++I;
127 // Turn it to an objc_retainAutoreleasedReturnValue.
131 DEBUG(dbgs() << "Transforming objc_retain => "
132 "objc_retainAutoreleasedReturnValue since the operand is a "
133 "return value.\nOld: "<< *Retain << "\n");
135 // We do not have to worry about tail calls/does not throw since
136 // retain/retainRV have the same properties.
137 Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_RetainRV);
138 cast<CallInst>(Retain)->setCalledFunction(Decl);
140 DEBUG(dbgs() << "New: " << *Retain << "\n");
144 /// Merge an autorelease with a retain into a fused call.
145 bool ObjCARCContract::contractAutorelease(
146 Function &F, Instruction *Autorelease, ARCInstKind Class,
147 SmallPtrSetImpl<Instruction *> &DependingInstructions,
148 SmallPtrSetImpl<const BasicBlock *> &Visited) {
149 const Value *Arg = GetArgRCIdentityRoot(Autorelease);
151 // Check that there are no instructions between the retain and the autorelease
152 // (such as an autorelease_pop) which may change the count.
153 CallInst *Retain = nullptr;
154 if (Class == ARCInstKind::AutoreleaseRV)
155 FindDependencies(RetainAutoreleaseRVDep, Arg,
156 Autorelease->getParent(), Autorelease,
157 DependingInstructions, Visited, PA);
159 FindDependencies(RetainAutoreleaseDep, Arg,
160 Autorelease->getParent(), Autorelease,
161 DependingInstructions, Visited, PA);
164 if (DependingInstructions.size() != 1) {
165 DependingInstructions.clear();
169 Retain = dyn_cast_or_null<CallInst>(*DependingInstructions.begin());
170 DependingInstructions.clear();
172 if (!Retain || GetBasicARCInstKind(Retain) != ARCInstKind::Retain ||
173 GetArgRCIdentityRoot(Retain) != Arg)
179 DEBUG(dbgs() << " Fusing retain/autorelease!\n"
180 " Autorelease:" << *Autorelease << "\n"
181 " Retain: " << *Retain << "\n");
183 Constant *Decl = EP.get(Class == ARCInstKind::AutoreleaseRV
184 ? ARCRuntimeEntryPoints::EPT_RetainAutoreleaseRV
185 : ARCRuntimeEntryPoints::EPT_RetainAutorelease);
186 Retain->setCalledFunction(Decl);
188 DEBUG(dbgs() << " New RetainAutorelease: " << *Retain << "\n");
190 EraseInstruction(Autorelease);
194 static StoreInst *findSafeStoreForStoreStrongContraction(LoadInst *Load,
195 Instruction *Release,
196 ProvenanceAnalysis &PA,
198 StoreInst *Store = nullptr;
199 bool SawRelease = false;
201 // Get the location associated with Load.
202 AliasAnalysis::Location Loc = AA->getLocation(Load);
204 // Walk down to find the store and the release, which may be in either order.
205 for (auto I = std::next(BasicBlock::iterator(Load)),
206 E = Load->getParent()->end();
208 // If we found the store we were looking for and saw the release,
209 // break. There is no more work to be done.
210 if (Store && SawRelease)
213 // Now we know that we have not seen either the store or the release. If I
214 // is the the release, mark that we saw the release and continue.
215 Instruction *Inst = &*I;
216 if (Inst == Release) {
221 // Otherwise, we check if Inst is a "good" store. Grab the instruction class
223 ARCInstKind Class = GetBasicARCInstKind(Inst);
225 // If Inst is an unrelated retain, we don't care about it.
227 // TODO: This is one area where the optimization could be made more
232 // If we have seen the store, but not the release...
234 // We need to make sure that it is safe to move the release from its
235 // current position to the store. This implies proving that any
236 // instruction in between Store and the Release conservatively can not use
237 // the RCIdentityRoot of Release. If we can prove we can ignore Inst, so
239 if (!CanUse(Inst, Load, PA, Class)) {
243 // Otherwise, be conservative and return nullptr.
247 // Ok, now we know we have not seen a store yet. See if Inst can write to
248 // our load location, if it can not, just ignore the instruction.
249 if (!(AA->getModRefInfo(Inst, Loc) & AliasAnalysis::Mod))
252 Store = dyn_cast<StoreInst>(Inst);
254 // If Inst can, then check if Inst is a simple store. If Inst is not a
255 // store or a store that is not simple, then we have some we do not
256 // understand writing to this memory implying we can not move the load
257 // over the write to any subsequent store that we may find.
258 if (!Store || !Store->isSimple())
261 // Then make sure that the pointer we are storing to is Ptr. If so, we
263 if (Store->getPointerOperand() == Loc.Ptr)
266 // Otherwise, we have an unknown store to some other ptr that clobbers
271 // If we did not find the store or did not see the release, fail.
272 if (!Store || !SawRelease)
280 findRetainForStoreStrongContraction(Value *New, StoreInst *Store,
281 Instruction *Release,
282 ProvenanceAnalysis &PA) {
283 // Walk up from the Store to find the retain.
284 BasicBlock::iterator I = Store;
285 BasicBlock::iterator Begin = Store->getParent()->begin();
286 while (I != Begin && GetBasicARCInstKind(I) != ARCInstKind::Retain) {
287 Instruction *Inst = &*I;
289 // It is only safe to move the retain to the store if we can prove
290 // conservatively that nothing besides the release can decrement reference
291 // counts in between the retain and the store.
292 if (CanDecrementRefCount(Inst, New, PA) && Inst != Release)
296 Instruction *Retain = I;
297 if (GetBasicARCInstKind(Retain) != ARCInstKind::Retain)
299 if (GetArgRCIdentityRoot(Retain) != New)
304 /// Attempt to merge an objc_release with a store, load, and objc_retain to form
305 /// an objc_storeStrong. An objc_storeStrong:
307 /// objc_storeStrong(i8** %old_ptr, i8* new_value)
309 /// is equivalent to the following IR sequence:
311 /// ; Load old value.
312 /// %old_value = load i8** %old_ptr (1)
314 /// ; Increment the new value and then release the old value. This must occur
315 /// ; in order in case old_value releases new_value in its destructor causing
316 /// ; us to potentially have a dangling ptr.
317 /// tail call i8* @objc_retain(i8* %new_value) (2)
318 /// tail call void @objc_release(i8* %old_value) (3)
320 /// ; Store the new_value into old_ptr
321 /// store i8* %new_value, i8** %old_ptr (4)
323 /// The safety of this optimization is based around the following
326 /// 1. We are forming the store strong at the store. Thus to perform this
327 /// optimization it must be safe to move the retain, load, and release to
329 /// 2. We need to make sure that any re-orderings of (1), (2), (3), (4) are
331 void ObjCARCContract::tryToContractReleaseIntoStoreStrong(Instruction *Release,
332 inst_iterator &Iter) {
333 // See if we are releasing something that we just loaded.
334 auto *Load = dyn_cast<LoadInst>(GetArgRCIdentityRoot(Release));
335 if (!Load || !Load->isSimple())
338 // For now, require everything to be in one basic block.
339 BasicBlock *BB = Release->getParent();
340 if (Load->getParent() != BB)
343 // First scan down the BB from Load, looking for a store of the RCIdentityRoot
346 findSafeStoreForStoreStrongContraction(Load, Release, PA, AA);
351 // Then find what new_value's RCIdentity Root is.
352 Value *New = GetRCIdentityRoot(Store->getValueOperand());
354 // Then walk up the BB and look for a retain on New without any intervening
355 // instructions which conservatively might decrement ref counts.
356 Instruction *Retain =
357 findRetainForStoreStrongContraction(New, Store, Release, PA);
367 llvm::dbgs() << " Contracting retain, release into objc_storeStrong.\n"
369 << " Store: " << *Store << "\n"
370 << " Release: " << *Release << "\n"
371 << " Retain: " << *Retain << "\n"
372 << " Load: " << *Load << "\n");
374 LLVMContext &C = Release->getContext();
375 Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
376 Type *I8XX = PointerType::getUnqual(I8X);
378 Value *Args[] = { Load->getPointerOperand(), New };
379 if (Args[0]->getType() != I8XX)
380 Args[0] = new BitCastInst(Args[0], I8XX, "", Store);
381 if (Args[1]->getType() != I8X)
382 Args[1] = new BitCastInst(Args[1], I8X, "", Store);
383 Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_StoreStrong);
384 CallInst *StoreStrong = CallInst::Create(Decl, Args, "", Store);
385 StoreStrong->setDoesNotThrow();
386 StoreStrong->setDebugLoc(Store->getDebugLoc());
388 // We can't set the tail flag yet, because we haven't yet determined
389 // whether there are any escaping allocas. Remember this call, so that
390 // we can set the tail flag once we know it's safe.
391 StoreStrongCalls.insert(StoreStrong);
393 DEBUG(llvm::dbgs() << " New Store Strong: " << *StoreStrong << "\n");
395 if (&*Iter == Store) ++Iter;
396 Store->eraseFromParent();
397 Release->eraseFromParent();
398 EraseInstruction(Retain);
399 if (Load->use_empty())
400 Load->eraseFromParent();
403 bool ObjCARCContract::tryToPeepholeInstruction(
404 Function &F, Instruction *Inst, inst_iterator &Iter,
405 SmallPtrSetImpl<Instruction *> &DependingInsts,
406 SmallPtrSetImpl<const BasicBlock *> &Visited,
407 bool &TailOkForStoreStrongs) {
408 // Only these library routines return their argument. In particular,
409 // objc_retainBlock does not necessarily return its argument.
410 ARCInstKind Class = GetBasicARCInstKind(Inst);
412 case ARCInstKind::FusedRetainAutorelease:
413 case ARCInstKind::FusedRetainAutoreleaseRV:
415 case ARCInstKind::Autorelease:
416 case ARCInstKind::AutoreleaseRV:
417 return contractAutorelease(F, Inst, Class, DependingInsts, Visited);
418 case ARCInstKind::Retain:
419 // Attempt to convert retains to retainrvs if they are next to function
421 if (!optimizeRetainCall(F, Inst))
423 // If we succeed in our optimization, fall through.
425 case ARCInstKind::RetainRV: {
426 // If we're compiling for a target which needs a special inline-asm
427 // marker to do the retainAutoreleasedReturnValue optimization,
431 BasicBlock::iterator BBI = Inst;
432 BasicBlock *InstParent = Inst->getParent();
434 // Step up to see if the call immediately precedes the RetainRV call.
435 // If it's an invoke, we have to cross a block boundary. And we have
436 // to carefully dodge no-op instructions.
438 if (&*BBI == InstParent->begin()) {
439 BasicBlock *Pred = InstParent->getSinglePredecessor();
441 goto decline_rv_optimization;
442 BBI = Pred->getTerminator();
446 } while (IsNoopInstruction(BBI));
448 if (&*BBI == GetArgRCIdentityRoot(Inst)) {
449 DEBUG(dbgs() << "Adding inline asm marker for "
450 "retainAutoreleasedReturnValue optimization.\n");
453 InlineAsm::get(FunctionType::get(Type::getVoidTy(Inst->getContext()),
455 RetainRVMarker->getString(),
456 /*Constraints=*/"", /*hasSideEffects=*/true);
457 CallInst::Create(IA, "", Inst);
459 decline_rv_optimization:
462 case ARCInstKind::InitWeak: {
463 // objc_initWeak(p, null) => *p = null
464 CallInst *CI = cast<CallInst>(Inst);
465 if (IsNullOrUndef(CI->getArgOperand(1))) {
467 ConstantPointerNull::get(cast<PointerType>(CI->getType()));
469 new StoreInst(Null, CI->getArgOperand(0), CI);
471 DEBUG(dbgs() << "OBJCARCContract: Old = " << *CI << "\n"
472 << " New = " << *Null << "\n");
474 CI->replaceAllUsesWith(Null);
475 CI->eraseFromParent();
479 case ARCInstKind::Release:
480 // Try to form an objc store strong from our release. If we fail, there is
481 // nothing further to do below, so continue.
482 tryToContractReleaseIntoStoreStrong(Inst, Iter);
484 case ARCInstKind::User:
485 // Be conservative if the function has any alloca instructions.
486 // Technically we only care about escaping alloca instructions,
487 // but this is sufficient to handle some interesting cases.
488 if (isa<AllocaInst>(Inst))
489 TailOkForStoreStrongs = false;
491 case ARCInstKind::IntrinsicUser:
492 // Remove calls to @clang.arc.use(...).
493 Inst->eraseFromParent();
500 //===----------------------------------------------------------------------===//
502 //===----------------------------------------------------------------------===//
504 bool ObjCARCContract::runOnFunction(Function &F) {
508 // If nothing in the Module uses ARC, don't do anything.
513 AA = &getAnalysis<AliasAnalysis>();
514 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
516 PA.setAA(&getAnalysis<AliasAnalysis>());
518 DEBUG(llvm::dbgs() << "**** ObjCARC Contract ****\n");
520 // Track whether it's ok to mark objc_storeStrong calls with the "tail"
521 // keyword. Be conservative if the function has variadic arguments.
522 // It seems that functions which "return twice" are also unsafe for the
523 // "tail" argument, because they are setjmp, which could need to
524 // return to an earlier stack state.
525 bool TailOkForStoreStrongs =
526 !F.isVarArg() && !F.callsFunctionThatReturnsTwice();
528 // For ObjC library calls which return their argument, replace uses of the
529 // argument with uses of the call return value, if it dominates the use. This
530 // reduces register pressure.
531 SmallPtrSet<Instruction *, 4> DependingInstructions;
532 SmallPtrSet<const BasicBlock *, 4> Visited;
533 for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E;) {
534 Instruction *Inst = &*I++;
536 DEBUG(dbgs() << "Visiting: " << *Inst << "\n");
538 // First try to peephole Inst. If there is nothing further we can do in
539 // terms of undoing objc-arc-expand, process the next inst.
540 if (tryToPeepholeInstruction(F, Inst, I, DependingInstructions, Visited,
541 TailOkForStoreStrongs))
544 // Otherwise, try to undo objc-arc-expand.
546 // Don't use GetArgRCIdentityRoot because we don't want to look through bitcasts
547 // and such; to do the replacement, the argument must have type i8*.
548 Value *Arg = cast<CallInst>(Inst)->getArgOperand(0);
550 // TODO: Change this to a do-while.
552 // If we're compiling bugpointed code, don't get in trouble.
553 if (!isa<Instruction>(Arg) && !isa<Argument>(Arg))
555 // Look through the uses of the pointer.
556 for (Value::use_iterator UI = Arg->use_begin(), UE = Arg->use_end();
558 // Increment UI now, because we may unlink its element.
560 unsigned OperandNo = U.getOperandNo();
562 // If the call's return value dominates a use of the call's argument
563 // value, rewrite the use to use the return value. We check for
564 // reachability here because an unreachable call is considered to
565 // trivially dominate itself, which would lead us to rewriting its
566 // argument in terms of its return value, which would lead to
567 // infinite loops in GetArgRCIdentityRoot.
568 if (DT->isReachableFromEntry(U) && DT->dominates(Inst, U)) {
570 Instruction *Replacement = Inst;
571 Type *UseTy = U.get()->getType();
572 if (PHINode *PHI = dyn_cast<PHINode>(U.getUser())) {
573 // For PHI nodes, insert the bitcast in the predecessor block.
574 unsigned ValNo = PHINode::getIncomingValueNumForOperand(OperandNo);
575 BasicBlock *BB = PHI->getIncomingBlock(ValNo);
576 if (Replacement->getType() != UseTy)
577 Replacement = new BitCastInst(Replacement, UseTy, "",
579 // While we're here, rewrite all edges for this PHI, rather
580 // than just one use at a time, to minimize the number of
582 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i)
583 if (PHI->getIncomingBlock(i) == BB) {
584 // Keep the UI iterator valid.
587 PHINode::getOperandNumForIncomingValue(i)) == &*UI)
589 PHI->setIncomingValue(i, Replacement);
592 if (Replacement->getType() != UseTy)
593 Replacement = new BitCastInst(Replacement, UseTy, "",
594 cast<Instruction>(U.getUser()));
600 // If Arg is a no-op casted pointer, strip one level of casts and iterate.
601 if (const BitCastInst *BI = dyn_cast<BitCastInst>(Arg))
602 Arg = BI->getOperand(0);
603 else if (isa<GEPOperator>(Arg) &&
604 cast<GEPOperator>(Arg)->hasAllZeroIndices())
605 Arg = cast<GEPOperator>(Arg)->getPointerOperand();
606 else if (isa<GlobalAlias>(Arg) &&
607 !cast<GlobalAlias>(Arg)->mayBeOverridden())
608 Arg = cast<GlobalAlias>(Arg)->getAliasee();
614 // If this function has no escaping allocas or suspicious vararg usage,
615 // objc_storeStrong calls can be marked with the "tail" keyword.
616 if (TailOkForStoreStrongs)
617 for (CallInst *CI : StoreStrongCalls)
619 StoreStrongCalls.clear();
624 //===----------------------------------------------------------------------===//
626 //===----------------------------------------------------------------------===//
628 char ObjCARCContract::ID = 0;
629 INITIALIZE_PASS_BEGIN(ObjCARCContract, "objc-arc-contract",
630 "ObjC ARC contraction", false, false)
631 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
632 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
633 INITIALIZE_PASS_END(ObjCARCContract, "objc-arc-contract",
634 "ObjC ARC contraction", false, false)
636 void ObjCARCContract::getAnalysisUsage(AnalysisUsage &AU) const {
637 AU.addRequired<AliasAnalysis>();
638 AU.addRequired<DominatorTreeWrapperPass>();
639 AU.setPreservesCFG();
642 Pass *llvm::createObjCARCContractPass() { return new ObjCARCContract(); }
644 bool ObjCARCContract::doInitialization(Module &M) {
645 // If nothing in the Module uses ARC, don't do anything.
646 Run = ModuleHasARC(M);
652 // Initialize RetainRVMarker.
653 RetainRVMarker = nullptr;
654 if (NamedMDNode *NMD =
655 M.getNamedMetadata("clang.arc.retainAutoreleasedReturnValueMarker"))
656 if (NMD->getNumOperands() == 1) {
657 const MDNode *N = NMD->getOperand(0);
658 if (N->getNumOperands() == 1)
659 if (const MDString *S = dyn_cast<MDString>(N->getOperand(0)))