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#include "ObjCARC.h" 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" 38 39using namespace llvm; 40using namespace llvm::objcarc; 41 42#define DEBUG_TYPE "objc-arc-contract" 43 44STATISTIC(NumPeeps, "Number of calls peephole-optimized"); 45STATISTIC(NumStoreStrongs, "Number objc_storeStrong calls formed"); 46 47namespace { 48 /// \brief Late ARC optimizations 49 /// 50 /// These change the IR in a way that makes it difficult to be analyzed by 51 /// ObjCARCOpt, so it's run late. 52 class ObjCARCContract : public FunctionPass { 53 bool Changed; 54 AliasAnalysis *AA; 55 DominatorTree *DT; 56 ProvenanceAnalysis PA; 57 ARCRuntimeEntryPoints EP; 58 59 /// A flag indicating whether this optimization pass should run. 60 bool Run; 61 62 /// The inline asm string to insert between calls and RetainRV calls to make 63 /// the optimization work on targets which need it. 64 const MDString *RetainRVMarker; 65 66 /// The set of inserted objc_storeStrong calls. If at the end of walking the 67 /// function we have found no alloca instructions, these calls can be marked 68 /// "tail". 69 SmallPtrSet<CallInst *, 8> StoreStrongCalls; 70 71 bool OptimizeRetainCall(Function &F, Instruction *Retain); 72 73 bool ContractAutorelease(Function &F, Instruction *Autorelease, 74 InstructionClass Class, 75 SmallPtrSet<Instruction *, 4> 76 &DependingInstructions, 77 SmallPtrSet<const BasicBlock *, 4> 78 &Visited); 79 80 void ContractRelease(Instruction *Release, 81 inst_iterator &Iter); 82 83 void getAnalysisUsage(AnalysisUsage &AU) const override; 84 bool doInitialization(Module &M) override; 85 bool runOnFunction(Function &F) override; 86 87 public: 88 static char ID; 89 ObjCARCContract() : FunctionPass(ID) { 90 initializeObjCARCContractPass(*PassRegistry::getPassRegistry()); 91 } 92 }; 93} 94 95char ObjCARCContract::ID = 0; 96INITIALIZE_PASS_BEGIN(ObjCARCContract, 97 "objc-arc-contract", "ObjC ARC contraction", false, false) 98INITIALIZE_AG_DEPENDENCY(AliasAnalysis) 99INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 100INITIALIZE_PASS_END(ObjCARCContract, 101 "objc-arc-contract", "ObjC ARC contraction", false, false) 102 103Pass *llvm::createObjCARCContractPass() { 104 return new ObjCARCContract(); 105} 106 107void ObjCARCContract::getAnalysisUsage(AnalysisUsage &AU) const { 108 AU.addRequired<AliasAnalysis>(); 109 AU.addRequired<DominatorTreeWrapperPass>(); 110 AU.setPreservesCFG(); 111} 112 113/// Turn objc_retain into objc_retainAutoreleasedReturnValue if the operand is a 114/// return value. We do this late so we do not disrupt the dataflow analysis in 115/// ObjCARCOpt. 116bool 117ObjCARCContract::OptimizeRetainCall(Function &F, Instruction *Retain) { 118 ImmutableCallSite CS(GetObjCArg(Retain)); 119 const Instruction *Call = CS.getInstruction(); 120 if (!Call) 121 return false; 122 if (Call->getParent() != Retain->getParent()) 123 return false; 124 125 // Check that the call is next to the retain. 126 BasicBlock::const_iterator I = Call; 127 ++I; 128 while (IsNoopInstruction(I)) ++I; 129 if (&*I != Retain) 130 return false; 131 132 // Turn it to an objc_retainAutoreleasedReturnValue. 133 Changed = true; 134 ++NumPeeps; 135 136 DEBUG(dbgs() << "Transforming objc_retain => " 137 "objc_retainAutoreleasedReturnValue since the operand is a " 138 "return value.\nOld: "<< *Retain << "\n"); 139 140 // We do not have to worry about tail calls/does not throw since 141 // retain/retainRV have the same properties. 142 Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_RetainRV); 143 cast<CallInst>(Retain)->setCalledFunction(Decl); 144 145 DEBUG(dbgs() << "New: " << *Retain << "\n"); 146 return true; 147} 148 149/// Merge an autorelease with a retain into a fused call. 150bool 151ObjCARCContract::ContractAutorelease(Function &F, Instruction *Autorelease, 152 InstructionClass Class, 153 SmallPtrSet<Instruction *, 4> 154 &DependingInstructions, 155 SmallPtrSet<const BasicBlock *, 4> 156 &Visited) { 157 const Value *Arg = GetObjCArg(Autorelease); 158 159 // Check that there are no instructions between the retain and the autorelease 160 // (such as an autorelease_pop) which may change the count. 161 CallInst *Retain = nullptr; 162 if (Class == IC_AutoreleaseRV) 163 FindDependencies(RetainAutoreleaseRVDep, Arg, 164 Autorelease->getParent(), Autorelease, 165 DependingInstructions, Visited, PA); 166 else 167 FindDependencies(RetainAutoreleaseDep, Arg, 168 Autorelease->getParent(), Autorelease, 169 DependingInstructions, Visited, PA); 170 171 Visited.clear(); 172 if (DependingInstructions.size() != 1) { 173 DependingInstructions.clear(); 174 return false; 175 } 176 177 Retain = dyn_cast_or_null<CallInst>(*DependingInstructions.begin()); 178 DependingInstructions.clear(); 179 180 if (!Retain || 181 GetBasicInstructionClass(Retain) != IC_Retain || 182 GetObjCArg(Retain) != Arg) 183 return false; 184 185 Changed = true; 186 ++NumPeeps; 187 188 DEBUG(dbgs() << "ObjCARCContract::ContractAutorelease: Fusing " 189 "retain/autorelease. Erasing: " << *Autorelease << "\n" 190 " Old Retain: " 191 << *Retain << "\n"); 192 193 Constant *Decl = EP.get(Class == IC_AutoreleaseRV ? 194 ARCRuntimeEntryPoints::EPT_RetainAutoreleaseRV : 195 ARCRuntimeEntryPoints::EPT_RetainAutorelease); 196 Retain->setCalledFunction(Decl); 197 198 DEBUG(dbgs() << " New Retain: " 199 << *Retain << "\n"); 200 201 EraseInstruction(Autorelease); 202 return true; 203} 204 205/// Attempt to merge an objc_release with a store, load, and objc_retain to form 206/// an objc_storeStrong. This can be a little tricky because the instructions 207/// don't always appear in order, and there may be unrelated intervening 208/// instructions. 209void ObjCARCContract::ContractRelease(Instruction *Release, 210 inst_iterator &Iter) { 211 LoadInst *Load = dyn_cast<LoadInst>(GetObjCArg(Release)); 212 if (!Load || !Load->isSimple()) return; 213 214 // For now, require everything to be in one basic block. 215 BasicBlock *BB = Release->getParent(); 216 if (Load->getParent() != BB) return; 217 218 // Walk down to find the store and the release, which may be in either order. 219 BasicBlock::iterator I = Load, End = BB->end(); 220 ++I; 221 AliasAnalysis::Location Loc = AA->getLocation(Load); 222 StoreInst *Store = nullptr; 223 bool SawRelease = false; 224 for (; !Store || !SawRelease; ++I) { 225 if (I == End) 226 return; 227 228 Instruction *Inst = I; 229 if (Inst == Release) { 230 SawRelease = true; 231 continue; 232 } 233 234 InstructionClass Class = GetBasicInstructionClass(Inst); 235 236 // Unrelated retains are harmless. 237 if (IsRetain(Class)) 238 continue; 239 240 if (Store) { 241 // The store is the point where we're going to put the objc_storeStrong, 242 // so make sure there are no uses after it. 243 if (CanUse(Inst, Load, PA, Class)) 244 return; 245 } else if (AA->getModRefInfo(Inst, Loc) & AliasAnalysis::Mod) { 246 // We are moving the load down to the store, so check for anything 247 // else which writes to the memory between the load and the store. 248 Store = dyn_cast<StoreInst>(Inst); 249 if (!Store || !Store->isSimple()) return; 250 if (Store->getPointerOperand() != Loc.Ptr) return; 251 } 252 } 253 254 Value *New = StripPointerCastsAndObjCCalls(Store->getValueOperand()); 255 256 // Walk up to find the retain. 257 I = Store; 258 BasicBlock::iterator Begin = BB->begin(); 259 while (I != Begin && GetBasicInstructionClass(I) != IC_Retain) 260 --I; 261 Instruction *Retain = I; 262 if (GetBasicInstructionClass(Retain) != IC_Retain) return; 263 if (GetObjCArg(Retain) != New) return; 264 265 Changed = true; 266 ++NumStoreStrongs; 267 268 LLVMContext &C = Release->getContext(); 269 Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C)); 270 Type *I8XX = PointerType::getUnqual(I8X); 271 272 Value *Args[] = { Load->getPointerOperand(), New }; 273 if (Args[0]->getType() != I8XX) 274 Args[0] = new BitCastInst(Args[0], I8XX, "", Store); 275 if (Args[1]->getType() != I8X) 276 Args[1] = new BitCastInst(Args[1], I8X, "", Store); 277 Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_StoreStrong); 278 CallInst *StoreStrong = CallInst::Create(Decl, Args, "", Store); 279 StoreStrong->setDoesNotThrow(); 280 StoreStrong->setDebugLoc(Store->getDebugLoc()); 281 282 // We can't set the tail flag yet, because we haven't yet determined 283 // whether there are any escaping allocas. Remember this call, so that 284 // we can set the tail flag once we know it's safe. 285 StoreStrongCalls.insert(StoreStrong); 286 287 if (&*Iter == Store) ++Iter; 288 Store->eraseFromParent(); 289 Release->eraseFromParent(); 290 EraseInstruction(Retain); 291 if (Load->use_empty()) 292 Load->eraseFromParent(); 293} 294 295bool ObjCARCContract::doInitialization(Module &M) { 296 // If nothing in the Module uses ARC, don't do anything. 297 Run = ModuleHasARC(M); 298 if (!Run) 299 return false; 300 301 EP.Initialize(&M); 302 303 // Initialize RetainRVMarker. 304 RetainRVMarker = nullptr; 305 if (NamedMDNode *NMD = 306 M.getNamedMetadata("clang.arc.retainAutoreleasedReturnValueMarker")) 307 if (NMD->getNumOperands() == 1) { 308 const MDNode *N = NMD->getOperand(0); 309 if (N->getNumOperands() == 1) 310 if (const MDString *S = dyn_cast<MDString>(N->getOperand(0))) 311 RetainRVMarker = S; 312 } 313 314 return false; 315} 316 317bool ObjCARCContract::runOnFunction(Function &F) { 318 if (!EnableARCOpts) 319 return false; 320 321 // If nothing in the Module uses ARC, don't do anything. 322 if (!Run) 323 return false; 324 325 Changed = false; 326 AA = &getAnalysis<AliasAnalysis>(); 327 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 328 329 PA.setAA(&getAnalysis<AliasAnalysis>()); 330 331 // Track whether it's ok to mark objc_storeStrong calls with the "tail" 332 // keyword. Be conservative if the function has variadic arguments. 333 // It seems that functions which "return twice" are also unsafe for the 334 // "tail" argument, because they are setjmp, which could need to 335 // return to an earlier stack state. 336 bool TailOkForStoreStrongs = !F.isVarArg() && 337 !F.callsFunctionThatReturnsTwice(); 338 339 // For ObjC library calls which return their argument, replace uses of the 340 // argument with uses of the call return value, if it dominates the use. This 341 // reduces register pressure. 342 SmallPtrSet<Instruction *, 4> DependingInstructions; 343 SmallPtrSet<const BasicBlock *, 4> Visited; 344 for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) { 345 Instruction *Inst = &*I++; 346 347 DEBUG(dbgs() << "ObjCARCContract: Visiting: " << *Inst << "\n"); 348 349 // Only these library routines return their argument. In particular, 350 // objc_retainBlock does not necessarily return its argument. 351 InstructionClass Class = GetBasicInstructionClass(Inst); 352 switch (Class) { 353 case IC_FusedRetainAutorelease: 354 case IC_FusedRetainAutoreleaseRV: 355 break; 356 case IC_Autorelease: 357 case IC_AutoreleaseRV: 358 if (ContractAutorelease(F, Inst, Class, DependingInstructions, Visited)) 359 continue; 360 break; 361 case IC_Retain: 362 // Attempt to convert retains to retainrvs if they are next to function 363 // calls. 364 if (!OptimizeRetainCall(F, Inst)) 365 break; 366 // If we succeed in our optimization, fall through. 367 // FALLTHROUGH 368 case IC_RetainRV: { 369 // If we're compiling for a target which needs a special inline-asm 370 // marker to do the retainAutoreleasedReturnValue optimization, 371 // insert it now. 372 if (!RetainRVMarker) 373 break; 374 BasicBlock::iterator BBI = Inst; 375 BasicBlock *InstParent = Inst->getParent(); 376 377 // Step up to see if the call immediately precedes the RetainRV call. 378 // If it's an invoke, we have to cross a block boundary. And we have 379 // to carefully dodge no-op instructions. 380 do { 381 if (&*BBI == InstParent->begin()) { 382 BasicBlock *Pred = InstParent->getSinglePredecessor(); 383 if (!Pred) 384 goto decline_rv_optimization; 385 BBI = Pred->getTerminator(); 386 break; 387 } 388 --BBI; 389 } while (IsNoopInstruction(BBI)); 390 391 if (&*BBI == GetObjCArg(Inst)) { 392 DEBUG(dbgs() << "ObjCARCContract: Adding inline asm marker for " 393 "retainAutoreleasedReturnValue optimization.\n"); 394 Changed = true; 395 InlineAsm *IA = 396 InlineAsm::get(FunctionType::get(Type::getVoidTy(Inst->getContext()), 397 /*isVarArg=*/false), 398 RetainRVMarker->getString(), 399 /*Constraints=*/"", /*hasSideEffects=*/true); 400 CallInst::Create(IA, "", Inst); 401 } 402 decline_rv_optimization: 403 break; 404 } 405 case IC_InitWeak: { 406 // objc_initWeak(p, null) => *p = null 407 CallInst *CI = cast<CallInst>(Inst); 408 if (IsNullOrUndef(CI->getArgOperand(1))) { 409 Value *Null = 410 ConstantPointerNull::get(cast<PointerType>(CI->getType())); 411 Changed = true; 412 new StoreInst(Null, CI->getArgOperand(0), CI); 413 414 DEBUG(dbgs() << "OBJCARCContract: Old = " << *CI << "\n" 415 << " New = " << *Null << "\n"); 416 417 CI->replaceAllUsesWith(Null); 418 CI->eraseFromParent(); 419 } 420 continue; 421 } 422 case IC_Release: 423 ContractRelease(Inst, I); 424 continue; 425 case IC_User: 426 // Be conservative if the function has any alloca instructions. 427 // Technically we only care about escaping alloca instructions, 428 // but this is sufficient to handle some interesting cases. 429 if (isa<AllocaInst>(Inst)) 430 TailOkForStoreStrongs = false; 431 continue; 432 case IC_IntrinsicUser: 433 // Remove calls to @clang.arc.use(...). 434 Inst->eraseFromParent(); 435 continue; 436 default: 437 continue; 438 } 439 440 DEBUG(dbgs() << "ObjCARCContract: Finished List.\n\n"); 441 442 // Don't use GetObjCArg because we don't want to look through bitcasts 443 // and such; to do the replacement, the argument must have type i8*. 444 Value *Arg = cast<CallInst>(Inst)->getArgOperand(0); 445 for (;;) { 446 // If we're compiling bugpointed code, don't get in trouble. 447 if (!isa<Instruction>(Arg) && !isa<Argument>(Arg)) 448 break; 449 // Look through the uses of the pointer. 450 for (Value::use_iterator UI = Arg->use_begin(), UE = Arg->use_end(); 451 UI != UE; ) { 452 // Increment UI now, because we may unlink its element. 453 Use &U = *UI++; 454 unsigned OperandNo = U.getOperandNo(); 455 456 // If the call's return value dominates a use of the call's argument 457 // value, rewrite the use to use the return value. We check for 458 // reachability here because an unreachable call is considered to 459 // trivially dominate itself, which would lead us to rewriting its 460 // argument in terms of its return value, which would lead to 461 // infinite loops in GetObjCArg. 462 if (DT->isReachableFromEntry(U) && DT->dominates(Inst, U)) { 463 Changed = true; 464 Instruction *Replacement = Inst; 465 Type *UseTy = U.get()->getType(); 466 if (PHINode *PHI = dyn_cast<PHINode>(U.getUser())) { 467 // For PHI nodes, insert the bitcast in the predecessor block. 468 unsigned ValNo = PHINode::getIncomingValueNumForOperand(OperandNo); 469 BasicBlock *BB = PHI->getIncomingBlock(ValNo); 470 if (Replacement->getType() != UseTy) 471 Replacement = new BitCastInst(Replacement, UseTy, "", 472 &BB->back()); 473 // While we're here, rewrite all edges for this PHI, rather 474 // than just one use at a time, to minimize the number of 475 // bitcasts we emit. 476 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) 477 if (PHI->getIncomingBlock(i) == BB) { 478 // Keep the UI iterator valid. 479 if (UI != UE && 480 &PHI->getOperandUse( 481 PHINode::getOperandNumForIncomingValue(i)) == &*UI) 482 ++UI; 483 PHI->setIncomingValue(i, Replacement); 484 } 485 } else { 486 if (Replacement->getType() != UseTy) 487 Replacement = new BitCastInst(Replacement, UseTy, "", 488 cast<Instruction>(U.getUser())); 489 U.set(Replacement); 490 } 491 } 492 } 493 494 // If Arg is a no-op casted pointer, strip one level of casts and iterate. 495 if (const BitCastInst *BI = dyn_cast<BitCastInst>(Arg)) 496 Arg = BI->getOperand(0); 497 else if (isa<GEPOperator>(Arg) && 498 cast<GEPOperator>(Arg)->hasAllZeroIndices()) 499 Arg = cast<GEPOperator>(Arg)->getPointerOperand(); 500 else if (isa<GlobalAlias>(Arg) && 501 !cast<GlobalAlias>(Arg)->mayBeOverridden()) 502 Arg = cast<GlobalAlias>(Arg)->getAliasee(); 503 else 504 break; 505 } 506 } 507 508 // If this function has no escaping allocas or suspicious vararg usage, 509 // objc_storeStrong calls can be marked with the "tail" keyword. 510 if (TailOkForStoreStrongs) 511 for (SmallPtrSet<CallInst *, 8>::iterator I = StoreStrongCalls.begin(), 512 E = StoreStrongCalls.end(); I != E; ++I) 513 (*I)->setTailCall(); 514 StoreStrongCalls.clear(); 515 516 return Changed; 517} 518