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;
70 /// The inline asm string to insert between calls and RetainRV calls to make
71 /// the optimization work on targets which need it.
72 const MDString *RetainRVMarker;
74 /// The set of inserted objc_storeStrong calls. If at the end of walking the
75 /// function we have found no alloca instructions, these calls can be marked
77 SmallPtrSet<CallInst *, 8> StoreStrongCalls;
79 Constant *getStoreStrongCallee(Module *M);
80 Constant *getRetainAutoreleaseCallee(Module *M);
81 Constant *getRetainAutoreleaseRVCallee(Module *M);
83 bool ContractAutorelease(Function &F, Instruction *Autorelease,
84 InstructionClass Class,
85 SmallPtrSet<Instruction *, 4>
86 &DependingInstructions,
87 SmallPtrSet<const BasicBlock *, 4>
90 void ContractRelease(Instruction *Release,
93 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
94 virtual bool doInitialization(Module &M);
95 virtual bool runOnFunction(Function &F);
99 ObjCARCContract() : FunctionPass(ID) {
100 initializeObjCARCContractPass(*PassRegistry::getPassRegistry());
105 char ObjCARCContract::ID = 0;
106 INITIALIZE_PASS_BEGIN(ObjCARCContract,
107 "objc-arc-contract", "ObjC ARC contraction", false, false)
108 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
109 INITIALIZE_PASS_DEPENDENCY(DominatorTree)
110 INITIALIZE_PASS_END(ObjCARCContract,
111 "objc-arc-contract", "ObjC ARC contraction", false, false)
113 Pass *llvm::createObjCARCContractPass() {
114 return new ObjCARCContract();
117 void ObjCARCContract::getAnalysisUsage(AnalysisUsage &AU) const {
118 AU.addRequired<AliasAnalysis>();
119 AU.addRequired<DominatorTree>();
120 AU.setPreservesCFG();
123 Constant *ObjCARCContract::getStoreStrongCallee(Module *M) {
124 if (!StoreStrongCallee) {
125 LLVMContext &C = M->getContext();
126 Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
127 Type *I8XX = PointerType::getUnqual(I8X);
128 Type *Params[] = { I8XX, I8X };
130 AttributeSet Attr = AttributeSet()
131 .addAttribute(M->getContext(), AttributeSet::FunctionIndex,
133 .addAttribute(M->getContext(), 1, Attribute::NoCapture);
136 M->getOrInsertFunction(
138 FunctionType::get(Type::getVoidTy(C), Params, /*isVarArg=*/false),
141 return StoreStrongCallee;
144 Constant *ObjCARCContract::getRetainAutoreleaseCallee(Module *M) {
145 if (!RetainAutoreleaseCallee) {
146 LLVMContext &C = M->getContext();
147 Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
148 Type *Params[] = { I8X };
149 FunctionType *FTy = FunctionType::get(I8X, Params, /*isVarArg=*/false);
150 AttributeSet Attribute =
151 AttributeSet().addAttribute(M->getContext(), AttributeSet::FunctionIndex,
152 Attribute::NoUnwind);
153 RetainAutoreleaseCallee =
154 M->getOrInsertFunction("objc_retainAutorelease", FTy, Attribute);
156 return RetainAutoreleaseCallee;
159 Constant *ObjCARCContract::getRetainAutoreleaseRVCallee(Module *M) {
160 if (!RetainAutoreleaseRVCallee) {
161 LLVMContext &C = M->getContext();
162 Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
163 Type *Params[] = { I8X };
164 FunctionType *FTy = FunctionType::get(I8X, Params, /*isVarArg=*/false);
165 AttributeSet Attribute =
166 AttributeSet().addAttribute(M->getContext(), AttributeSet::FunctionIndex,
167 Attribute::NoUnwind);
168 RetainAutoreleaseRVCallee =
169 M->getOrInsertFunction("objc_retainAutoreleaseReturnValue", FTy,
172 return RetainAutoreleaseRVCallee;
175 /// Merge an autorelease with a retain into a fused call.
177 ObjCARCContract::ContractAutorelease(Function &F, Instruction *Autorelease,
178 InstructionClass Class,
179 SmallPtrSet<Instruction *, 4>
180 &DependingInstructions,
181 SmallPtrSet<const BasicBlock *, 4>
183 const Value *Arg = GetObjCArg(Autorelease);
185 // Check that there are no instructions between the retain and the autorelease
186 // (such as an autorelease_pop) which may change the count.
187 CallInst *Retain = 0;
188 if (Class == IC_AutoreleaseRV)
189 FindDependencies(RetainAutoreleaseRVDep, Arg,
190 Autorelease->getParent(), Autorelease,
191 DependingInstructions, Visited, PA);
193 FindDependencies(RetainAutoreleaseDep, Arg,
194 Autorelease->getParent(), Autorelease,
195 DependingInstructions, Visited, PA);
198 if (DependingInstructions.size() != 1) {
199 DependingInstructions.clear();
203 Retain = dyn_cast_or_null<CallInst>(*DependingInstructions.begin());
204 DependingInstructions.clear();
207 GetBasicInstructionClass(Retain) != IC_Retain ||
208 GetObjCArg(Retain) != Arg)
214 DEBUG(dbgs() << "ObjCARCContract::ContractAutorelease: Fusing "
215 "retain/autorelease. Erasing: " << *Autorelease << "\n"
219 if (Class == IC_AutoreleaseRV)
220 Retain->setCalledFunction(getRetainAutoreleaseRVCallee(F.getParent()));
222 Retain->setCalledFunction(getRetainAutoreleaseCallee(F.getParent()));
224 DEBUG(dbgs() << " New Retain: "
227 EraseInstruction(Autorelease);
231 /// Attempt to merge an objc_release with a store, load, and objc_retain to form
232 /// an objc_storeStrong. This can be a little tricky because the instructions
233 /// don't always appear in order, and there may be unrelated intervening
235 void ObjCARCContract::ContractRelease(Instruction *Release,
236 inst_iterator &Iter) {
237 LoadInst *Load = dyn_cast<LoadInst>(GetObjCArg(Release));
238 if (!Load || !Load->isSimple()) return;
240 // For now, require everything to be in one basic block.
241 BasicBlock *BB = Release->getParent();
242 if (Load->getParent() != BB) return;
244 // Walk down to find the store and the release, which may be in either order.
245 BasicBlock::iterator I = Load, End = BB->end();
247 AliasAnalysis::Location Loc = AA->getLocation(Load);
248 StoreInst *Store = 0;
249 bool SawRelease = false;
250 for (; !Store || !SawRelease; ++I) {
254 Instruction *Inst = I;
255 if (Inst == Release) {
260 InstructionClass Class = GetBasicInstructionClass(Inst);
262 // Unrelated retains are harmless.
267 // The store is the point where we're going to put the objc_storeStrong,
268 // so make sure there are no uses after it.
269 if (CanUse(Inst, Load, PA, Class))
271 } else if (AA->getModRefInfo(Inst, Loc) & AliasAnalysis::Mod) {
272 // We are moving the load down to the store, so check for anything
273 // else which writes to the memory between the load and the store.
274 Store = dyn_cast<StoreInst>(Inst);
275 if (!Store || !Store->isSimple()) return;
276 if (Store->getPointerOperand() != Loc.Ptr) return;
280 Value *New = StripPointerCastsAndObjCCalls(Store->getValueOperand());
282 // Walk up to find the retain.
284 BasicBlock::iterator Begin = BB->begin();
285 while (I != Begin && GetBasicInstructionClass(I) != IC_Retain)
287 Instruction *Retain = I;
288 if (GetBasicInstructionClass(Retain) != IC_Retain) return;
289 if (GetObjCArg(Retain) != New) return;
294 LLVMContext &C = Release->getContext();
295 Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
296 Type *I8XX = PointerType::getUnqual(I8X);
298 Value *Args[] = { Load->getPointerOperand(), New };
299 if (Args[0]->getType() != I8XX)
300 Args[0] = new BitCastInst(Args[0], I8XX, "", Store);
301 if (Args[1]->getType() != I8X)
302 Args[1] = new BitCastInst(Args[1], I8X, "", Store);
303 CallInst *StoreStrong =
304 CallInst::Create(getStoreStrongCallee(BB->getParent()->getParent()),
306 StoreStrong->setDoesNotThrow();
307 StoreStrong->setDebugLoc(Store->getDebugLoc());
309 // We can't set the tail flag yet, because we haven't yet determined
310 // whether there are any escaping allocas. Remember this call, so that
311 // we can set the tail flag once we know it's safe.
312 StoreStrongCalls.insert(StoreStrong);
314 if (&*Iter == Store) ++Iter;
315 Store->eraseFromParent();
316 Release->eraseFromParent();
317 EraseInstruction(Retain);
318 if (Load->use_empty())
319 Load->eraseFromParent();
322 bool ObjCARCContract::doInitialization(Module &M) {
323 // If nothing in the Module uses ARC, don't do anything.
324 Run = ModuleHasARC(M);
328 // These are initialized lazily.
329 StoreStrongCallee = 0;
330 RetainAutoreleaseCallee = 0;
331 RetainAutoreleaseRVCallee = 0;
333 // Initialize RetainRVMarker.
335 if (NamedMDNode *NMD =
336 M.getNamedMetadata("clang.arc.retainAutoreleasedReturnValueMarker"))
337 if (NMD->getNumOperands() == 1) {
338 const MDNode *N = NMD->getOperand(0);
339 if (N->getNumOperands() == 1)
340 if (const MDString *S = dyn_cast<MDString>(N->getOperand(0)))
347 bool ObjCARCContract::runOnFunction(Function &F) {
351 // If nothing in the Module uses ARC, don't do anything.
356 AA = &getAnalysis<AliasAnalysis>();
357 DT = &getAnalysis<DominatorTree>();
359 PA.setAA(&getAnalysis<AliasAnalysis>());
361 // Track whether it's ok to mark objc_storeStrong calls with the "tail"
362 // keyword. Be conservative if the function has variadic arguments.
363 // It seems that functions which "return twice" are also unsafe for the
364 // "tail" argument, because they are setjmp, which could need to
365 // return to an earlier stack state.
366 bool TailOkForStoreStrongs = !F.isVarArg() &&
367 !F.callsFunctionThatReturnsTwice();
369 // For ObjC library calls which return their argument, replace uses of the
370 // argument with uses of the call return value, if it dominates the use. This
371 // reduces register pressure.
372 SmallPtrSet<Instruction *, 4> DependingInstructions;
373 SmallPtrSet<const BasicBlock *, 4> Visited;
374 for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
375 Instruction *Inst = &*I++;
377 DEBUG(dbgs() << "ObjCARCContract: Visiting: " << *Inst << "\n");
379 // Only these library routines return their argument. In particular,
380 // objc_retainBlock does not necessarily return its argument.
381 InstructionClass Class = GetBasicInstructionClass(Inst);
384 case IC_FusedRetainAutorelease:
385 case IC_FusedRetainAutoreleaseRV:
388 case IC_AutoreleaseRV:
389 if (ContractAutorelease(F, Inst, Class, DependingInstructions, Visited))
393 // If we're compiling for a target which needs a special inline-asm
394 // marker to do the retainAutoreleasedReturnValue optimization,
398 BasicBlock::iterator BBI = Inst;
399 BasicBlock *InstParent = Inst->getParent();
401 // Step up to see if the call immediately precedes the RetainRV call.
402 // If it's an invoke, we have to cross a block boundary. And we have
403 // to carefully dodge no-op instructions.
405 if (&*BBI == InstParent->begin()) {
406 BasicBlock *Pred = InstParent->getSinglePredecessor();
408 goto decline_rv_optimization;
409 BBI = Pred->getTerminator();
413 } while (IsNoopInstruction(BBI));
415 if (&*BBI == GetObjCArg(Inst)) {
416 DEBUG(dbgs() << "ObjCARCContract: Adding inline asm marker for "
417 "retainAutoreleasedReturnValue optimization.\n");
420 InlineAsm::get(FunctionType::get(Type::getVoidTy(Inst->getContext()),
422 RetainRVMarker->getString(),
423 /*Constraints=*/"", /*hasSideEffects=*/true);
424 CallInst::Create(IA, "", Inst);
426 decline_rv_optimization:
430 // objc_initWeak(p, null) => *p = null
431 CallInst *CI = cast<CallInst>(Inst);
432 if (IsNullOrUndef(CI->getArgOperand(1))) {
434 ConstantPointerNull::get(cast<PointerType>(CI->getType()));
436 new StoreInst(Null, CI->getArgOperand(0), CI);
438 DEBUG(dbgs() << "OBJCARCContract: Old = " << *CI << "\n"
439 << " New = " << *Null << "\n");
441 CI->replaceAllUsesWith(Null);
442 CI->eraseFromParent();
447 ContractRelease(Inst, I);
450 // Be conservative if the function has any alloca instructions.
451 // Technically we only care about escaping alloca instructions,
452 // but this is sufficient to handle some interesting cases.
453 if (isa<AllocaInst>(Inst))
454 TailOkForStoreStrongs = false;
456 case IC_IntrinsicUser:
457 // Remove calls to @clang.arc.use(...).
458 Inst->eraseFromParent();
464 DEBUG(dbgs() << "ObjCARCContract: Finished List.\n\n");
466 // Don't use GetObjCArg because we don't want to look through bitcasts
467 // and such; to do the replacement, the argument must have type i8*.
468 const Value *Arg = cast<CallInst>(Inst)->getArgOperand(0);
470 // If we're compiling bugpointed code, don't get in trouble.
471 if (!isa<Instruction>(Arg) && !isa<Argument>(Arg))
473 // Look through the uses of the pointer.
474 for (Value::const_use_iterator UI = Arg->use_begin(), UE = Arg->use_end();
476 Use &U = UI.getUse();
477 unsigned OperandNo = UI.getOperandNo();
478 ++UI; // Increment UI now, because we may unlink its element.
480 // If the call's return value dominates a use of the call's argument
481 // value, rewrite the use to use the return value. We check for
482 // reachability here because an unreachable call is considered to
483 // trivially dominate itself, which would lead us to rewriting its
484 // argument in terms of its return value, which would lead to
485 // infinite loops in GetObjCArg.
486 if (DT->isReachableFromEntry(U) && DT->dominates(Inst, U)) {
488 Instruction *Replacement = Inst;
489 Type *UseTy = U.get()->getType();
490 if (PHINode *PHI = dyn_cast<PHINode>(U.getUser())) {
491 // For PHI nodes, insert the bitcast in the predecessor block.
492 unsigned ValNo = PHINode::getIncomingValueNumForOperand(OperandNo);
493 BasicBlock *BB = PHI->getIncomingBlock(ValNo);
494 if (Replacement->getType() != UseTy)
495 Replacement = new BitCastInst(Replacement, UseTy, "",
497 // While we're here, rewrite all edges for this PHI, rather
498 // than just one use at a time, to minimize the number of
500 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i)
501 if (PHI->getIncomingBlock(i) == BB) {
502 // Keep the UI iterator valid.
503 if (&PHI->getOperandUse(
504 PHINode::getOperandNumForIncomingValue(i)) ==
507 PHI->setIncomingValue(i, Replacement);
510 if (Replacement->getType() != UseTy)
511 Replacement = new BitCastInst(Replacement, UseTy, "",
512 cast<Instruction>(U.getUser()));
518 // If Arg is a no-op casted pointer, strip one level of casts and iterate.
519 if (const BitCastInst *BI = dyn_cast<BitCastInst>(Arg))
520 Arg = BI->getOperand(0);
521 else if (isa<GEPOperator>(Arg) &&
522 cast<GEPOperator>(Arg)->hasAllZeroIndices())
523 Arg = cast<GEPOperator>(Arg)->getPointerOperand();
524 else if (isa<GlobalAlias>(Arg) &&
525 !cast<GlobalAlias>(Arg)->mayBeOverridden())
526 Arg = cast<GlobalAlias>(Arg)->getAliasee();
532 // If this function has no escaping allocas or suspicious vararg usage,
533 // objc_storeStrong calls can be marked with the "tail" keyword.
534 if (TailOkForStoreStrongs)
535 for (SmallPtrSet<CallInst *, 8>::iterator I = StoreStrongCalls.begin(),
536 E = StoreStrongCalls.end(); I != E; ++I)
538 StoreStrongCalls.clear();