1//===- ObjCARCContract.cpp - ObjC ARC Optimization ------------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9/// \file 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 12/// in Objective C. 13/// 14/// This specific file mainly deals with ``contracting'' multiple lower level 15/// operations into singular higher level operations through pattern matching. 16/// 17/// WARNING: This file knows about certain library functions. It recognizes them 18/// by name, and hardwires knowledge of their semantics. 19/// 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. 23/// 24//===----------------------------------------------------------------------===// 25 26// TODO: ObjCARCContract could insert PHI nodes when uses aren't 27// dominated by single calls. 28 29#define DEBUG_TYPE "objc-arc-contract" 30#include "ObjCARC.h" 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" 38 39using namespace llvm; 40using namespace llvm::objcarc; 41 42STATISTIC(NumPeeps, "Number of calls peephole-optimized"); 43STATISTIC(NumStoreStrongs, "Number objc_storeStrong calls formed"); 44 45namespace { 46 /// \brief Late ARC optimizations 47 /// 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 { 51 bool Changed; 52 AliasAnalysis *AA; 53 DominatorTree *DT; 54 ProvenanceAnalysis PA; 55 56 /// A flag indicating whether this optimization pass should run. 57 bool Run; 58 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. 62 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 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; 73 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 76 /// "tail". 77 SmallPtrSet<CallInst *, 8> StoreStrongCalls; 78 79 Constant *getStoreStrongCallee(Module *M); 80 Constant *getRetainAutoreleaseCallee(Module *M); 81 Constant *getRetainAutoreleaseRVCallee(Module *M); 82 83 bool ContractAutorelease(Function &F, Instruction *Autorelease, 84 InstructionClass Class, 85 SmallPtrSet<Instruction *, 4> 86 &DependingInstructions, 87 SmallPtrSet<const BasicBlock *, 4> 88 &Visited); 89 90 void ContractRelease(Instruction *Release, 91 inst_iterator &Iter); 92 93 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 94 virtual bool doInitialization(Module &M); 95 virtual bool runOnFunction(Function &F); 96 97 public: 98 static char ID; 99 ObjCARCContract() : FunctionPass(ID) { 100 initializeObjCARCContractPass(*PassRegistry::getPassRegistry()); 101 } 102 }; 103} 104 105char ObjCARCContract::ID = 0; 106INITIALIZE_PASS_BEGIN(ObjCARCContract, 107 "objc-arc-contract", "ObjC ARC contraction", false, false) 108INITIALIZE_AG_DEPENDENCY(AliasAnalysis) 109INITIALIZE_PASS_DEPENDENCY(DominatorTree) 110INITIALIZE_PASS_END(ObjCARCContract, 111 "objc-arc-contract", "ObjC ARC contraction", false, false) 112 113Pass *llvm::createObjCARCContractPass() { 114 return new ObjCARCContract(); 115} 116 117void ObjCARCContract::getAnalysisUsage(AnalysisUsage &AU) const { 118 AU.addRequired<AliasAnalysis>(); 119 AU.addRequired<DominatorTree>(); 120 AU.setPreservesCFG(); 121} 122 123Constant *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 }; 129 130 AttributeSet Attr = AttributeSet() 131 .addAttribute(M->getContext(), AttributeSet::FunctionIndex, 132 Attribute::NoUnwind) 133 .addAttribute(M->getContext(), 1, Attribute::NoCapture); 134 135 StoreStrongCallee = 136 M->getOrInsertFunction( 137 "objc_storeStrong", 138 FunctionType::get(Type::getVoidTy(C), Params, /*isVarArg=*/false), 139 Attr); 140 } 141 return StoreStrongCallee; 142} 143 144Constant *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); 155 } 156 return RetainAutoreleaseCallee; 157} 158 159Constant *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, 170 Attribute); 171 } 172 return RetainAutoreleaseRVCallee; 173} 174 175/// Merge an autorelease with a retain into a fused call. 176bool 177ObjCARCContract::ContractAutorelease(Function &F, Instruction *Autorelease, 178 InstructionClass Class, 179 SmallPtrSet<Instruction *, 4> 180 &DependingInstructions, 181 SmallPtrSet<const BasicBlock *, 4> 182 &Visited) { 183 const Value *Arg = GetObjCArg(Autorelease); 184 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); 192 else 193 FindDependencies(RetainAutoreleaseDep, Arg, 194 Autorelease->getParent(), Autorelease, 195 DependingInstructions, Visited, PA); 196 197 Visited.clear(); 198 if (DependingInstructions.size() != 1) { 199 DependingInstructions.clear(); 200 return false; 201 } 202 203 Retain = dyn_cast_or_null<CallInst>(*DependingInstructions.begin()); 204 DependingInstructions.clear(); 205 206 if (!Retain || 207 GetBasicInstructionClass(Retain) != IC_Retain || 208 GetObjCArg(Retain) != Arg) 209 return false; 210 211 Changed = true; 212 ++NumPeeps; 213 214 DEBUG(dbgs() << "ObjCARCContract::ContractAutorelease: Fusing " 215 "retain/autorelease. Erasing: " << *Autorelease << "\n" 216 " Old Retain: " 217 << *Retain << "\n"); 218 219 if (Class == IC_AutoreleaseRV) 220 Retain->setCalledFunction(getRetainAutoreleaseRVCallee(F.getParent())); 221 else 222 Retain->setCalledFunction(getRetainAutoreleaseCallee(F.getParent())); 223 224 DEBUG(dbgs() << " New Retain: " 225 << *Retain << "\n"); 226 227 EraseInstruction(Autorelease); 228 return true; 229} 230 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 234/// instructions. 235void ObjCARCContract::ContractRelease(Instruction *Release, 236 inst_iterator &Iter) { 237 LoadInst *Load = dyn_cast<LoadInst>(GetObjCArg(Release)); 238 if (!Load || !Load->isSimple()) return; 239 240 // For now, require everything to be in one basic block. 241 BasicBlock *BB = Release->getParent(); 242 if (Load->getParent() != BB) return; 243 244 // Walk down to find the store and the release, which may be in either order. 245 BasicBlock::iterator I = Load, End = BB->end(); 246 ++I; 247 AliasAnalysis::Location Loc = AA->getLocation(Load); 248 StoreInst *Store = 0; 249 bool SawRelease = false; 250 for (; !Store || !SawRelease; ++I) { 251 if (I == End) 252 return; 253 254 Instruction *Inst = I; 255 if (Inst == Release) { 256 SawRelease = true; 257 continue; 258 } 259 260 InstructionClass Class = GetBasicInstructionClass(Inst); 261 262 // Unrelated retains are harmless. 263 if (IsRetain(Class)) 264 continue; 265 266 if (Store) { 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)) 270 return; 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; 277 } 278 } 279 280 Value *New = StripPointerCastsAndObjCCalls(Store->getValueOperand()); 281 282 // Walk up to find the retain. 283 I = Store; 284 BasicBlock::iterator Begin = BB->begin(); 285 while (I != Begin && GetBasicInstructionClass(I) != IC_Retain) 286 --I; 287 Instruction *Retain = I; 288 if (GetBasicInstructionClass(Retain) != IC_Retain) return; 289 if (GetObjCArg(Retain) != New) return; 290 291 Changed = true; 292 ++NumStoreStrongs; 293 294 LLVMContext &C = Release->getContext(); 295 Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C)); 296 Type *I8XX = PointerType::getUnqual(I8X); 297 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()), 305 Args, "", Store); 306 StoreStrong->setDoesNotThrow(); 307 StoreStrong->setDebugLoc(Store->getDebugLoc()); 308 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); 313 314 if (&*Iter == Store) ++Iter; 315 Store->eraseFromParent(); 316 Release->eraseFromParent(); 317 EraseInstruction(Retain); 318 if (Load->use_empty()) 319 Load->eraseFromParent(); 320} 321 322bool ObjCARCContract::doInitialization(Module &M) { 323 // If nothing in the Module uses ARC, don't do anything. 324 Run = ModuleHasARC(M); 325 if (!Run) 326 return false; 327 328 // These are initialized lazily. 329 StoreStrongCallee = 0; 330 RetainAutoreleaseCallee = 0; 331 RetainAutoreleaseRVCallee = 0; 332 333 // Initialize RetainRVMarker. 334 RetainRVMarker = 0; 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))) 341 RetainRVMarker = S; 342 } 343 344 return false; 345} 346 347bool ObjCARCContract::runOnFunction(Function &F) { 348 if (!EnableARCOpts) 349 return false; 350 351 // If nothing in the Module uses ARC, don't do anything. 352 if (!Run) 353 return false; 354 355 Changed = false; 356 AA = &getAnalysis<AliasAnalysis>(); 357 DT = &getAnalysis<DominatorTree>(); 358 359 PA.setAA(&getAnalysis<AliasAnalysis>()); 360 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(); 368 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++; 376 377 DEBUG(dbgs() << "ObjCARCContract: Visiting: " << *Inst << "\n"); 378 379 // Only these library routines return their argument. In particular, 380 // objc_retainBlock does not necessarily return its argument. 381 InstructionClass Class = GetBasicInstructionClass(Inst); 382 switch (Class) { 383 case IC_Retain: 384 case IC_FusedRetainAutorelease: 385 case IC_FusedRetainAutoreleaseRV: 386 break; 387 case IC_Autorelease: 388 case IC_AutoreleaseRV: 389 if (ContractAutorelease(F, Inst, Class, DependingInstructions, Visited)) 390 continue; 391 break; 392 case IC_RetainRV: { 393 // If we're compiling for a target which needs a special inline-asm 394 // marker to do the retainAutoreleasedReturnValue optimization, 395 // insert it now. 396 if (!RetainRVMarker) 397 break; 398 BasicBlock::iterator BBI = Inst; 399 BasicBlock *InstParent = Inst->getParent(); 400 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. 404 do { 405 if (&*BBI == InstParent->begin()) { 406 BasicBlock *Pred = InstParent->getSinglePredecessor(); 407 if (!Pred) 408 goto decline_rv_optimization; 409 BBI = Pred->getTerminator(); 410 break; 411 } 412 --BBI; 413 } while (isNoopInstruction(BBI)); 414 415 if (&*BBI == GetObjCArg(Inst)) { 416 DEBUG(dbgs() << "ObjCARCContract: Adding inline asm marker for " 417 "retainAutoreleasedReturnValue optimization.\n"); 418 Changed = true; 419 InlineAsm *IA = 420 InlineAsm::get(FunctionType::get(Type::getVoidTy(Inst->getContext()), 421 /*isVarArg=*/false), 422 RetainRVMarker->getString(), 423 /*Constraints=*/"", /*hasSideEffects=*/true); 424 CallInst::Create(IA, "", Inst); 425 } 426 decline_rv_optimization: 427 break; 428 } 429 case IC_InitWeak: { 430 // objc_initWeak(p, null) => *p = null 431 CallInst *CI = cast<CallInst>(Inst); 432 if (isNullOrUndef(CI->getArgOperand(1))) { 433 Value *Null = 434 ConstantPointerNull::get(cast<PointerType>(CI->getType())); 435 Changed = true; 436 new StoreInst(Null, CI->getArgOperand(0), CI); 437 438 DEBUG(dbgs() << "OBJCARCContract: Old = " << *CI << "\n" 439 << " New = " << *Null << "\n"); 440 441 CI->replaceAllUsesWith(Null); 442 CI->eraseFromParent(); 443 } 444 continue; 445 } 446 case IC_Release: 447 ContractRelease(Inst, I); 448 continue; 449 case IC_User: 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; 455 continue; 456 default: 457 continue; 458 } 459 460 DEBUG(dbgs() << "ObjCARCContract: Finished List.\n\n"); 461 462 // Don't use GetObjCArg because we don't want to look through bitcasts 463 // and such; to do the replacement, the argument must have type i8*. 464 const Value *Arg = cast<CallInst>(Inst)->getArgOperand(0); 465 for (;;) { 466 // If we're compiling bugpointed code, don't get in trouble. 467 if (!isa<Instruction>(Arg) && !isa<Argument>(Arg)) 468 break; 469 // Look through the uses of the pointer. 470 for (Value::const_use_iterator UI = Arg->use_begin(), UE = Arg->use_end(); 471 UI != UE; ) { 472 Use &U = UI.getUse(); 473 unsigned OperandNo = UI.getOperandNo(); 474 ++UI; // Increment UI now, because we may unlink its element. 475 476 // If the call's return value dominates a use of the call's argument 477 // value, rewrite the use to use the return value. We check for 478 // reachability here because an unreachable call is considered to 479 // trivially dominate itself, which would lead us to rewriting its 480 // argument in terms of its return value, which would lead to 481 // infinite loops in GetObjCArg. 482 if (DT->isReachableFromEntry(U) && DT->dominates(Inst, U)) { 483 Changed = true; 484 Instruction *Replacement = Inst; 485 Type *UseTy = U.get()->getType(); 486 if (PHINode *PHI = dyn_cast<PHINode>(U.getUser())) { 487 // For PHI nodes, insert the bitcast in the predecessor block. 488 unsigned ValNo = PHINode::getIncomingValueNumForOperand(OperandNo); 489 BasicBlock *BB = PHI->getIncomingBlock(ValNo); 490 if (Replacement->getType() != UseTy) 491 Replacement = new BitCastInst(Replacement, UseTy, "", 492 &BB->back()); 493 // While we're here, rewrite all edges for this PHI, rather 494 // than just one use at a time, to minimize the number of 495 // bitcasts we emit. 496 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) 497 if (PHI->getIncomingBlock(i) == BB) { 498 // Keep the UI iterator valid. 499 if (&PHI->getOperandUse( 500 PHINode::getOperandNumForIncomingValue(i)) == 501 &UI.getUse()) 502 ++UI; 503 PHI->setIncomingValue(i, Replacement); 504 } 505 } else { 506 if (Replacement->getType() != UseTy) 507 Replacement = new BitCastInst(Replacement, UseTy, "", 508 cast<Instruction>(U.getUser())); 509 U.set(Replacement); 510 } 511 } 512 } 513 514 // If Arg is a no-op casted pointer, strip one level of casts and iterate. 515 if (const BitCastInst *BI = dyn_cast<BitCastInst>(Arg)) 516 Arg = BI->getOperand(0); 517 else if (isa<GEPOperator>(Arg) && 518 cast<GEPOperator>(Arg)->hasAllZeroIndices()) 519 Arg = cast<GEPOperator>(Arg)->getPointerOperand(); 520 else if (isa<GlobalAlias>(Arg) && 521 !cast<GlobalAlias>(Arg)->mayBeOverridden()) 522 Arg = cast<GlobalAlias>(Arg)->getAliasee(); 523 else 524 break; 525 } 526 } 527 528 // If this function has no escaping allocas or suspicious vararg usage, 529 // objc_storeStrong calls can be marked with the "tail" keyword. 530 if (TailOkForStoreStrongs) 531 for (SmallPtrSet<CallInst *, 8>::iterator I = StoreStrongCalls.begin(), 532 E = StoreStrongCalls.end(); I != E; ++I) 533 (*I)->setTailCall(); 534 StoreStrongCalls.clear(); 535 536 return Changed; 537} 538