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.
29 #define DEBUG_TYPE "objc-arc-contract"
31 #include "DependencyAnalysis.h"
32 #include "ProvenanceAnalysis.h"
33 #include "llvm/ADT/Statistic.h"
34 #include "llvm/Analysis/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 STATISTIC(NumPeeps, "Number of calls peephole-optimized");
43 STATISTIC(NumStoreStrongs, "Number objc_storeStrong calls formed");
46 /// \brief Late ARC optimizations
48 /// These change the IR in a way that makes it difficult to be analyzed by
49 /// ObjCARCOpt, so it's run late.
50 class ObjCARCContract : public FunctionPass {
54 ProvenanceAnalysis PA;
56 /// A flag indicating whether this optimization pass should run.
59 /// Declarations for ObjC runtime functions, for use in creating calls to
60 /// them. These are initialized lazily to avoid cluttering up the Module
61 /// with unused declarations.
63 /// Declaration for objc_storeStrong().
64 Constant *StoreStrongCallee;
65 /// Declaration for objc_retainAutorelease().
66 Constant *RetainAutoreleaseCallee;
67 /// Declaration for objc_retainAutoreleaseReturnValue().
68 Constant *RetainAutoreleaseRVCallee;
69 /// Declaration for objc_retainAutoreleasedReturnValue().
70 Constant *RetainRVCallee;
72 /// The inline asm string to insert between calls and RetainRV calls to make
73 /// the optimization work on targets which need it.
74 const MDString *RetainRVMarker;
76 /// The set of inserted objc_storeStrong calls. If at the end of walking the
77 /// function we have found no alloca instructions, these calls can be marked
79 SmallPtrSet<CallInst *, 8> StoreStrongCalls;
81 Constant *getStoreStrongCallee(Module *M);
82 Constant *getRetainRVCallee(Module *M);
83 Constant *getRetainAutoreleaseCallee(Module *M);
84 Constant *getRetainAutoreleaseRVCallee(Module *M);
86 bool OptimizeRetainCall(Function &F, Instruction *Retain);
88 bool ContractAutorelease(Function &F, Instruction *Autorelease,
89 InstructionClass Class,
90 SmallPtrSet<Instruction *, 4>
91 &DependingInstructions,
92 SmallPtrSet<const BasicBlock *, 4>
95 void ContractRelease(Instruction *Release,
98 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
99 virtual bool doInitialization(Module &M);
100 virtual bool runOnFunction(Function &F);
104 ObjCARCContract() : FunctionPass(ID) {
105 initializeObjCARCContractPass(*PassRegistry::getPassRegistry());
110 char ObjCARCContract::ID = 0;
111 INITIALIZE_PASS_BEGIN(ObjCARCContract,
112 "objc-arc-contract", "ObjC ARC contraction", false, false)
113 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
114 INITIALIZE_PASS_DEPENDENCY(DominatorTree)
115 INITIALIZE_PASS_END(ObjCARCContract,
116 "objc-arc-contract", "ObjC ARC contraction", false, false)
118 Pass *llvm::createObjCARCContractPass() {
119 return new ObjCARCContract();
122 void ObjCARCContract::getAnalysisUsage(AnalysisUsage &AU) const {
123 AU.addRequired<AliasAnalysis>();
124 AU.addRequired<DominatorTree>();
125 AU.setPreservesCFG();
128 Constant *ObjCARCContract::getStoreStrongCallee(Module *M) {
129 if (!StoreStrongCallee) {
130 LLVMContext &C = M->getContext();
131 Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
132 Type *I8XX = PointerType::getUnqual(I8X);
133 Type *Params[] = { I8XX, I8X };
135 AttributeSet Attr = AttributeSet()
136 .addAttribute(M->getContext(), AttributeSet::FunctionIndex,
138 .addAttribute(M->getContext(), 1, Attribute::NoCapture);
141 M->getOrInsertFunction(
143 FunctionType::get(Type::getVoidTy(C), Params, /*isVarArg=*/false),
146 return StoreStrongCallee;
149 Constant *ObjCARCContract::getRetainAutoreleaseCallee(Module *M) {
150 if (!RetainAutoreleaseCallee) {
151 LLVMContext &C = M->getContext();
152 Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
153 Type *Params[] = { I8X };
154 FunctionType *FTy = FunctionType::get(I8X, Params, /*isVarArg=*/false);
155 AttributeSet Attribute =
156 AttributeSet().addAttribute(M->getContext(), AttributeSet::FunctionIndex,
157 Attribute::NoUnwind);
158 RetainAutoreleaseCallee =
159 M->getOrInsertFunction("objc_retainAutorelease", FTy, Attribute);
161 return RetainAutoreleaseCallee;
164 Constant *ObjCARCContract::getRetainAutoreleaseRVCallee(Module *M) {
165 if (!RetainAutoreleaseRVCallee) {
166 LLVMContext &C = M->getContext();
167 Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
168 Type *Params[] = { I8X };
169 FunctionType *FTy = FunctionType::get(I8X, Params, /*isVarArg=*/false);
170 AttributeSet Attribute =
171 AttributeSet().addAttribute(M->getContext(), AttributeSet::FunctionIndex,
172 Attribute::NoUnwind);
173 RetainAutoreleaseRVCallee =
174 M->getOrInsertFunction("objc_retainAutoreleaseReturnValue", FTy,
177 return RetainAutoreleaseRVCallee;
180 Constant *ObjCARCContract::getRetainRVCallee(Module *M) {
181 if (!RetainRVCallee) {
182 LLVMContext &C = M->getContext();
183 Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
184 Type *Params[] = { I8X };
185 FunctionType *FTy = FunctionType::get(I8X, Params, /*isVarArg=*/false);
186 AttributeSet Attribute =
187 AttributeSet().addAttribute(M->getContext(), AttributeSet::FunctionIndex,
188 Attribute::NoUnwind);
190 M->getOrInsertFunction("objc_retainAutoreleasedReturnValue", FTy,
193 return RetainRVCallee;
196 /// Turn objc_retain into objc_retainAutoreleasedReturnValue if the operand is a
197 /// return value. We do this late so we do not disrupt the dataflow analysis in
200 ObjCARCContract::OptimizeRetainCall(Function &F, Instruction *Retain) {
201 ImmutableCallSite CS(GetObjCArg(Retain));
202 const Instruction *Call = CS.getInstruction();
205 if (Call->getParent() != Retain->getParent())
208 // Check that the call is next to the retain.
209 BasicBlock::const_iterator I = Call;
211 while (IsNoopInstruction(I)) ++I;
215 // Turn it to an objc_retainAutoreleasedReturnValue.
219 DEBUG(dbgs() << "Transforming objc_retain => "
220 "objc_retainAutoreleasedReturnValue since the operand is a "
221 "return value.\nOld: "<< *Retain << "\n");
223 // We do not have to worry about tail calls/does not throw since
224 // retain/retainRV have the same properties.
225 cast<CallInst>(Retain)->setCalledFunction(getRetainRVCallee(F.getParent()));
227 DEBUG(dbgs() << "New: " << *Retain << "\n");
231 /// Merge an autorelease with a retain into a fused call.
233 ObjCARCContract::ContractAutorelease(Function &F, Instruction *Autorelease,
234 InstructionClass Class,
235 SmallPtrSet<Instruction *, 4>
236 &DependingInstructions,
237 SmallPtrSet<const BasicBlock *, 4>
239 const Value *Arg = GetObjCArg(Autorelease);
241 // Check that there are no instructions between the retain and the autorelease
242 // (such as an autorelease_pop) which may change the count.
243 CallInst *Retain = 0;
244 if (Class == IC_AutoreleaseRV)
245 FindDependencies(RetainAutoreleaseRVDep, Arg,
246 Autorelease->getParent(), Autorelease,
247 DependingInstructions, Visited, PA);
249 FindDependencies(RetainAutoreleaseDep, Arg,
250 Autorelease->getParent(), Autorelease,
251 DependingInstructions, Visited, PA);
254 if (DependingInstructions.size() != 1) {
255 DependingInstructions.clear();
259 Retain = dyn_cast_or_null<CallInst>(*DependingInstructions.begin());
260 DependingInstructions.clear();
263 GetBasicInstructionClass(Retain) != IC_Retain ||
264 GetObjCArg(Retain) != Arg)
270 DEBUG(dbgs() << "ObjCARCContract::ContractAutorelease: Fusing "
271 "retain/autorelease. Erasing: " << *Autorelease << "\n"
275 if (Class == IC_AutoreleaseRV)
276 Retain->setCalledFunction(getRetainAutoreleaseRVCallee(F.getParent()));
278 Retain->setCalledFunction(getRetainAutoreleaseCallee(F.getParent()));
280 DEBUG(dbgs() << " New Retain: "
283 EraseInstruction(Autorelease);
287 /// Attempt to merge an objc_release with a store, load, and objc_retain to form
288 /// an objc_storeStrong. This can be a little tricky because the instructions
289 /// don't always appear in order, and there may be unrelated intervening
291 void ObjCARCContract::ContractRelease(Instruction *Release,
292 inst_iterator &Iter) {
293 LoadInst *Load = dyn_cast<LoadInst>(GetObjCArg(Release));
294 if (!Load || !Load->isSimple()) return;
296 // For now, require everything to be in one basic block.
297 BasicBlock *BB = Release->getParent();
298 if (Load->getParent() != BB) return;
300 // Walk down to find the store and the release, which may be in either order.
301 BasicBlock::iterator I = Load, End = BB->end();
303 AliasAnalysis::Location Loc = AA->getLocation(Load);
304 StoreInst *Store = 0;
305 bool SawRelease = false;
306 for (; !Store || !SawRelease; ++I) {
310 Instruction *Inst = I;
311 if (Inst == Release) {
316 InstructionClass Class = GetBasicInstructionClass(Inst);
318 // Unrelated retains are harmless.
323 // The store is the point where we're going to put the objc_storeStrong,
324 // so make sure there are no uses after it.
325 if (CanUse(Inst, Load, PA, Class))
327 } else if (AA->getModRefInfo(Inst, Loc) & AliasAnalysis::Mod) {
328 // We are moving the load down to the store, so check for anything
329 // else which writes to the memory between the load and the store.
330 Store = dyn_cast<StoreInst>(Inst);
331 if (!Store || !Store->isSimple()) return;
332 if (Store->getPointerOperand() != Loc.Ptr) return;
336 Value *New = StripPointerCastsAndObjCCalls(Store->getValueOperand());
338 // Walk up to find the retain.
340 BasicBlock::iterator Begin = BB->begin();
341 while (I != Begin && GetBasicInstructionClass(I) != IC_Retain)
343 Instruction *Retain = I;
344 if (GetBasicInstructionClass(Retain) != IC_Retain) return;
345 if (GetObjCArg(Retain) != New) return;
350 LLVMContext &C = Release->getContext();
351 Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
352 Type *I8XX = PointerType::getUnqual(I8X);
354 Value *Args[] = { Load->getPointerOperand(), New };
355 if (Args[0]->getType() != I8XX)
356 Args[0] = new BitCastInst(Args[0], I8XX, "", Store);
357 if (Args[1]->getType() != I8X)
358 Args[1] = new BitCastInst(Args[1], I8X, "", Store);
359 CallInst *StoreStrong =
360 CallInst::Create(getStoreStrongCallee(BB->getParent()->getParent()),
362 StoreStrong->setDoesNotThrow();
363 StoreStrong->setDebugLoc(Store->getDebugLoc());
365 // We can't set the tail flag yet, because we haven't yet determined
366 // whether there are any escaping allocas. Remember this call, so that
367 // we can set the tail flag once we know it's safe.
368 StoreStrongCalls.insert(StoreStrong);
370 if (&*Iter == Store) ++Iter;
371 Store->eraseFromParent();
372 Release->eraseFromParent();
373 EraseInstruction(Retain);
374 if (Load->use_empty())
375 Load->eraseFromParent();
378 bool ObjCARCContract::doInitialization(Module &M) {
379 // If nothing in the Module uses ARC, don't do anything.
380 Run = ModuleHasARC(M);
384 // These are initialized lazily.
385 StoreStrongCallee = 0;
386 RetainAutoreleaseCallee = 0;
387 RetainAutoreleaseRVCallee = 0;
390 // Initialize RetainRVMarker.
392 if (NamedMDNode *NMD =
393 M.getNamedMetadata("clang.arc.retainAutoreleasedReturnValueMarker"))
394 if (NMD->getNumOperands() == 1) {
395 const MDNode *N = NMD->getOperand(0);
396 if (N->getNumOperands() == 1)
397 if (const MDString *S = dyn_cast<MDString>(N->getOperand(0)))
404 bool ObjCARCContract::runOnFunction(Function &F) {
408 // If nothing in the Module uses ARC, don't do anything.
413 AA = &getAnalysis<AliasAnalysis>();
414 DT = &getAnalysis<DominatorTree>();
416 PA.setAA(&getAnalysis<AliasAnalysis>());
418 // Track whether it's ok to mark objc_storeStrong calls with the "tail"
419 // keyword. Be conservative if the function has variadic arguments.
420 // It seems that functions which "return twice" are also unsafe for the
421 // "tail" argument, because they are setjmp, which could need to
422 // return to an earlier stack state.
423 bool TailOkForStoreStrongs = !F.isVarArg() &&
424 !F.callsFunctionThatReturnsTwice();
426 // For ObjC library calls which return their argument, replace uses of the
427 // argument with uses of the call return value, if it dominates the use. This
428 // reduces register pressure.
429 SmallPtrSet<Instruction *, 4> DependingInstructions;
430 SmallPtrSet<const BasicBlock *, 4> Visited;
431 for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
432 Instruction *Inst = &*I++;
434 DEBUG(dbgs() << "ObjCARCContract: Visiting: " << *Inst << "\n");
436 // Only these library routines return their argument. In particular,
437 // objc_retainBlock does not necessarily return its argument.
438 InstructionClass Class = GetBasicInstructionClass(Inst);
440 case IC_FusedRetainAutorelease:
441 case IC_FusedRetainAutoreleaseRV:
444 case IC_AutoreleaseRV:
445 if (ContractAutorelease(F, Inst, Class, DependingInstructions, Visited))
449 // Attempt to convert retains to retainrvs if they are next to function
451 if (!OptimizeRetainCall(F, Inst))
453 // If we succeed in our optimization, fall through.
456 // If we're compiling for a target which needs a special inline-asm
457 // marker to do the retainAutoreleasedReturnValue optimization,
461 BasicBlock::iterator BBI = Inst;
462 BasicBlock *InstParent = Inst->getParent();
464 // Step up to see if the call immediately precedes the RetainRV call.
465 // If it's an invoke, we have to cross a block boundary. And we have
466 // to carefully dodge no-op instructions.
468 if (&*BBI == InstParent->begin()) {
469 BasicBlock *Pred = InstParent->getSinglePredecessor();
471 goto decline_rv_optimization;
472 BBI = Pred->getTerminator();
476 } while (IsNoopInstruction(BBI));
478 if (&*BBI == GetObjCArg(Inst)) {
479 DEBUG(dbgs() << "ObjCARCContract: Adding inline asm marker for "
480 "retainAutoreleasedReturnValue optimization.\n");
483 InlineAsm::get(FunctionType::get(Type::getVoidTy(Inst->getContext()),
485 RetainRVMarker->getString(),
486 /*Constraints=*/"", /*hasSideEffects=*/true);
487 CallInst::Create(IA, "", Inst);
489 decline_rv_optimization:
493 // objc_initWeak(p, null) => *p = null
494 CallInst *CI = cast<CallInst>(Inst);
495 if (IsNullOrUndef(CI->getArgOperand(1))) {
497 ConstantPointerNull::get(cast<PointerType>(CI->getType()));
499 new StoreInst(Null, CI->getArgOperand(0), CI);
501 DEBUG(dbgs() << "OBJCARCContract: Old = " << *CI << "\n"
502 << " New = " << *Null << "\n");
504 CI->replaceAllUsesWith(Null);
505 CI->eraseFromParent();
510 ContractRelease(Inst, I);
513 // Be conservative if the function has any alloca instructions.
514 // Technically we only care about escaping alloca instructions,
515 // but this is sufficient to handle some interesting cases.
516 if (isa<AllocaInst>(Inst))
517 TailOkForStoreStrongs = false;
519 case IC_IntrinsicUser:
520 // Remove calls to @clang.arc.use(...).
521 Inst->eraseFromParent();
527 DEBUG(dbgs() << "ObjCARCContract: Finished List.\n\n");
529 // Don't use GetObjCArg because we don't want to look through bitcasts
530 // and such; to do the replacement, the argument must have type i8*.
531 const Value *Arg = cast<CallInst>(Inst)->getArgOperand(0);
533 // If we're compiling bugpointed code, don't get in trouble.
534 if (!isa<Instruction>(Arg) && !isa<Argument>(Arg))
536 // Look through the uses of the pointer.
537 for (Value::const_use_iterator UI = Arg->use_begin(), UE = Arg->use_end();
539 Use &U = UI.getUse();
540 unsigned OperandNo = UI.getOperandNo();
541 ++UI; // Increment UI now, because we may unlink its element.
543 // If the call's return value dominates a use of the call's argument
544 // value, rewrite the use to use the return value. We check for
545 // reachability here because an unreachable call is considered to
546 // trivially dominate itself, which would lead us to rewriting its
547 // argument in terms of its return value, which would lead to
548 // infinite loops in GetObjCArg.
549 if (DT->isReachableFromEntry(U) && DT->dominates(Inst, U)) {
551 Instruction *Replacement = Inst;
552 Type *UseTy = U.get()->getType();
553 if (PHINode *PHI = dyn_cast<PHINode>(U.getUser())) {
554 // For PHI nodes, insert the bitcast in the predecessor block.
555 unsigned ValNo = PHINode::getIncomingValueNumForOperand(OperandNo);
556 BasicBlock *BB = PHI->getIncomingBlock(ValNo);
557 if (Replacement->getType() != UseTy)
558 Replacement = new BitCastInst(Replacement, UseTy, "",
560 // While we're here, rewrite all edges for this PHI, rather
561 // than just one use at a time, to minimize the number of
563 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i)
564 if (PHI->getIncomingBlock(i) == BB) {
565 // Keep the UI iterator valid.
566 if (&PHI->getOperandUse(
567 PHINode::getOperandNumForIncomingValue(i)) ==
570 PHI->setIncomingValue(i, Replacement);
573 if (Replacement->getType() != UseTy)
574 Replacement = new BitCastInst(Replacement, UseTy, "",
575 cast<Instruction>(U.getUser()));
581 // If Arg is a no-op casted pointer, strip one level of casts and iterate.
582 if (const BitCastInst *BI = dyn_cast<BitCastInst>(Arg))
583 Arg = BI->getOperand(0);
584 else if (isa<GEPOperator>(Arg) &&
585 cast<GEPOperator>(Arg)->hasAllZeroIndices())
586 Arg = cast<GEPOperator>(Arg)->getPointerOperand();
587 else if (isa<GlobalAlias>(Arg) &&
588 !cast<GlobalAlias>(Arg)->mayBeOverridden())
589 Arg = cast<GlobalAlias>(Arg)->getAliasee();
595 // If this function has no escaping allocas or suspicious vararg usage,
596 // objc_storeStrong calls can be marked with the "tail" keyword.
597 if (TailOkForStoreStrongs)
598 for (SmallPtrSet<CallInst *, 8>::iterator I = StoreStrongCalls.begin(),
599 E = StoreStrongCalls.end(); I != E; ++I)
601 StoreStrongCalls.clear();