ObjCARC.cpp revision 8b11fdd8bb78840937ceebdfe44397dd8d2697fd
1//===- ObjCARC.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// 10// This file defines ObjC ARC optimizations. ARC stands for 11// Automatic Reference Counting and is a system for managing reference counts 12// for objects in Objective C. 13// 14// The optimizations performed include elimination of redundant, partially 15// redundant, and inconsequential reference count operations, elimination of 16// redundant weak pointer operations, pattern-matching and replacement of 17// low-level operations into higher-level operations, and numerous minor 18// simplifications. 19// 20// This file also defines a simple ARC-aware AliasAnalysis. 21// 22// WARNING: This file knows about certain library functions. It recognizes them 23// by name, and hardwires knowedge of their semantics. 24// 25// WARNING: This file knows about how certain Objective-C library functions are 26// used. Naive LLVM IR transformations which would otherwise be 27// behavior-preserving may break these assumptions. 28// 29//===----------------------------------------------------------------------===// 30 31#define DEBUG_TYPE "objc-arc" 32#include "llvm/Function.h" 33#include "llvm/Intrinsics.h" 34#include "llvm/GlobalVariable.h" 35#include "llvm/DerivedTypes.h" 36#include "llvm/Module.h" 37#include "llvm/Analysis/ValueTracking.h" 38#include "llvm/Transforms/Utils/Local.h" 39#include "llvm/Support/CallSite.h" 40#include "llvm/Support/CommandLine.h" 41#include "llvm/ADT/StringSwitch.h" 42#include "llvm/ADT/DenseMap.h" 43#include "llvm/ADT/STLExtras.h" 44using namespace llvm; 45 46// A handy option to enable/disable all optimizations in this file. 47static cl::opt<bool> EnableARCOpts("enable-objc-arc-opts", cl::init(true)); 48 49//===----------------------------------------------------------------------===// 50// Misc. Utilities 51//===----------------------------------------------------------------------===// 52 53namespace { 54 /// MapVector - An associative container with fast insertion-order 55 /// (deterministic) iteration over its elements. Plus the special 56 /// blot operation. 57 template<class KeyT, class ValueT> 58 class MapVector { 59 /// Map - Map keys to indices in Vector. 60 typedef DenseMap<KeyT, size_t> MapTy; 61 MapTy Map; 62 63 /// Vector - Keys and values. 64 typedef std::vector<std::pair<KeyT, ValueT> > VectorTy; 65 VectorTy Vector; 66 67 public: 68 typedef typename VectorTy::iterator iterator; 69 typedef typename VectorTy::const_iterator const_iterator; 70 iterator begin() { return Vector.begin(); } 71 iterator end() { return Vector.end(); } 72 const_iterator begin() const { return Vector.begin(); } 73 const_iterator end() const { return Vector.end(); } 74 75#ifdef XDEBUG 76 ~MapVector() { 77 assert(Vector.size() >= Map.size()); // May differ due to blotting. 78 for (typename MapTy::const_iterator I = Map.begin(), E = Map.end(); 79 I != E; ++I) { 80 assert(I->second < Vector.size()); 81 assert(Vector[I->second].first == I->first); 82 } 83 for (typename VectorTy::const_iterator I = Vector.begin(), 84 E = Vector.end(); I != E; ++I) 85 assert(!I->first || 86 (Map.count(I->first) && 87 Map[I->first] == size_t(I - Vector.begin()))); 88 } 89#endif 90 91 ValueT &operator[](const KeyT &Arg) { 92 std::pair<typename MapTy::iterator, bool> Pair = 93 Map.insert(std::make_pair(Arg, size_t(0))); 94 if (Pair.second) { 95 size_t Num = Vector.size(); 96 Pair.first->second = Num; 97 Vector.push_back(std::make_pair(Arg, ValueT())); 98 return Vector[Num].second; 99 } 100 return Vector[Pair.first->second].second; 101 } 102 103 std::pair<iterator, bool> 104 insert(const std::pair<KeyT, ValueT> &InsertPair) { 105 std::pair<typename MapTy::iterator, bool> Pair = 106 Map.insert(std::make_pair(InsertPair.first, size_t(0))); 107 if (Pair.second) { 108 size_t Num = Vector.size(); 109 Pair.first->second = Num; 110 Vector.push_back(InsertPair); 111 return std::make_pair(Vector.begin() + Num, true); 112 } 113 return std::make_pair(Vector.begin() + Pair.first->second, false); 114 } 115 116 const_iterator find(const KeyT &Key) const { 117 typename MapTy::const_iterator It = Map.find(Key); 118 if (It == Map.end()) return Vector.end(); 119 return Vector.begin() + It->second; 120 } 121 122 /// blot - This is similar to erase, but instead of removing the element 123 /// from the vector, it just zeros out the key in the vector. This leaves 124 /// iterators intact, but clients must be prepared for zeroed-out keys when 125 /// iterating. 126 void blot(const KeyT &Key) { 127 typename MapTy::iterator It = Map.find(Key); 128 if (It == Map.end()) return; 129 Vector[It->second].first = KeyT(); 130 Map.erase(It); 131 } 132 133 void clear() { 134 Map.clear(); 135 Vector.clear(); 136 } 137 }; 138} 139 140//===----------------------------------------------------------------------===// 141// ARC Utilities. 142//===----------------------------------------------------------------------===// 143 144namespace { 145 /// InstructionClass - A simple classification for instructions. 146 enum InstructionClass { 147 IC_Retain, ///< objc_retain 148 IC_RetainRV, ///< objc_retainAutoreleasedReturnValue 149 IC_RetainBlock, ///< objc_retainBlock 150 IC_Release, ///< objc_release 151 IC_Autorelease, ///< objc_autorelease 152 IC_AutoreleaseRV, ///< objc_autoreleaseReturnValue 153 IC_AutoreleasepoolPush, ///< objc_autoreleasePoolPush 154 IC_AutoreleasepoolPop, ///< objc_autoreleasePoolPop 155 IC_NoopCast, ///< objc_retainedObject, etc. 156 IC_FusedRetainAutorelease, ///< objc_retainAutorelease 157 IC_FusedRetainAutoreleaseRV, ///< objc_retainAutoreleaseReturnValue 158 IC_LoadWeakRetained, ///< objc_loadWeakRetained (primitive) 159 IC_StoreWeak, ///< objc_storeWeak (primitive) 160 IC_InitWeak, ///< objc_initWeak (derived) 161 IC_LoadWeak, ///< objc_loadWeak (derived) 162 IC_MoveWeak, ///< objc_moveWeak (derived) 163 IC_CopyWeak, ///< objc_copyWeak (derived) 164 IC_DestroyWeak, ///< objc_destroyWeak (derived) 165 IC_CallOrUser, ///< could call objc_release and/or "use" pointers 166 IC_Call, ///< could call objc_release 167 IC_User, ///< could "use" a pointer 168 IC_None ///< anything else 169 }; 170} 171 172/// IsPotentialUse - Test whether the given value is possible a 173/// reference-counted pointer. 174static bool IsPotentialUse(const Value *Op) { 175 // Pointers to static or stack storage are not reference-counted pointers. 176 if (isa<Constant>(Op) || isa<AllocaInst>(Op)) 177 return false; 178 // Special arguments are not reference-counted. 179 if (const Argument *Arg = dyn_cast<Argument>(Op)) 180 if (Arg->hasByValAttr() || 181 Arg->hasNestAttr() || 182 Arg->hasStructRetAttr()) 183 return false; 184 // Only consider values with pointer types. 185 // It seemes intuitive to exclude function pointer types as well, since 186 // functions are never reference-counted, however clang occasionally 187 // bitcasts reference-counted pointers to function-pointer type 188 // temporarily. 189 PointerType *Ty = dyn_cast<PointerType>(Op->getType()); 190 if (!Ty) 191 return false; 192 // Conservatively assume anything else is a potential use. 193 return true; 194} 195 196/// GetCallSiteClass - Helper for GetInstructionClass. Determines what kind 197/// of construct CS is. 198static InstructionClass GetCallSiteClass(ImmutableCallSite CS) { 199 for (ImmutableCallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); 200 I != E; ++I) 201 if (IsPotentialUse(*I)) 202 return CS.onlyReadsMemory() ? IC_User : IC_CallOrUser; 203 204 return CS.onlyReadsMemory() ? IC_None : IC_Call; 205} 206 207/// GetFunctionClass - Determine if F is one of the special known Functions. 208/// If it isn't, return IC_CallOrUser. 209static InstructionClass GetFunctionClass(const Function *F) { 210 Function::const_arg_iterator AI = F->arg_begin(), AE = F->arg_end(); 211 212 // No arguments. 213 if (AI == AE) 214 return StringSwitch<InstructionClass>(F->getName()) 215 .Case("objc_autoreleasePoolPush", IC_AutoreleasepoolPush) 216 .Default(IC_CallOrUser); 217 218 // One argument. 219 const Argument *A0 = AI++; 220 if (AI == AE) 221 // Argument is a pointer. 222 if (PointerType *PTy = dyn_cast<PointerType>(A0->getType())) { 223 Type *ETy = PTy->getElementType(); 224 // Argument is i8*. 225 if (ETy->isIntegerTy(8)) 226 return StringSwitch<InstructionClass>(F->getName()) 227 .Case("objc_retain", IC_Retain) 228 .Case("objc_retainAutoreleasedReturnValue", IC_RetainRV) 229 .Case("objc_retainBlock", IC_RetainBlock) 230 .Case("objc_release", IC_Release) 231 .Case("objc_autorelease", IC_Autorelease) 232 .Case("objc_autoreleaseReturnValue", IC_AutoreleaseRV) 233 .Case("objc_autoreleasePoolPop", IC_AutoreleasepoolPop) 234 .Case("objc_retainedObject", IC_NoopCast) 235 .Case("objc_unretainedObject", IC_NoopCast) 236 .Case("objc_unretainedPointer", IC_NoopCast) 237 .Case("objc_retain_autorelease", IC_FusedRetainAutorelease) 238 .Case("objc_retainAutorelease", IC_FusedRetainAutorelease) 239 .Case("objc_retainAutoreleaseReturnValue",IC_FusedRetainAutoreleaseRV) 240 .Default(IC_CallOrUser); 241 242 // Argument is i8** 243 if (PointerType *Pte = dyn_cast<PointerType>(ETy)) 244 if (Pte->getElementType()->isIntegerTy(8)) 245 return StringSwitch<InstructionClass>(F->getName()) 246 .Case("objc_loadWeakRetained", IC_LoadWeakRetained) 247 .Case("objc_loadWeak", IC_LoadWeak) 248 .Case("objc_destroyWeak", IC_DestroyWeak) 249 .Default(IC_CallOrUser); 250 } 251 252 // Two arguments, first is i8**. 253 const Argument *A1 = AI++; 254 if (AI == AE) 255 if (PointerType *PTy = dyn_cast<PointerType>(A0->getType())) 256 if (PointerType *Pte = dyn_cast<PointerType>(PTy->getElementType())) 257 if (Pte->getElementType()->isIntegerTy(8)) 258 if (PointerType *PTy1 = dyn_cast<PointerType>(A1->getType())) { 259 Type *ETy1 = PTy1->getElementType(); 260 // Second argument is i8* 261 if (ETy1->isIntegerTy(8)) 262 return StringSwitch<InstructionClass>(F->getName()) 263 .Case("objc_storeWeak", IC_StoreWeak) 264 .Case("objc_initWeak", IC_InitWeak) 265 .Default(IC_CallOrUser); 266 // Second argument is i8**. 267 if (PointerType *Pte1 = dyn_cast<PointerType>(ETy1)) 268 if (Pte1->getElementType()->isIntegerTy(8)) 269 return StringSwitch<InstructionClass>(F->getName()) 270 .Case("objc_moveWeak", IC_MoveWeak) 271 .Case("objc_copyWeak", IC_CopyWeak) 272 .Default(IC_CallOrUser); 273 } 274 275 // Anything else. 276 return IC_CallOrUser; 277} 278 279/// GetInstructionClass - Determine what kind of construct V is. 280static InstructionClass GetInstructionClass(const Value *V) { 281 if (const Instruction *I = dyn_cast<Instruction>(V)) { 282 // Any instruction other than bitcast and gep with a pointer operand have a 283 // use of an objc pointer. Bitcasts, GEPs, Selects, PHIs transfer a pointer 284 // to a subsequent use, rather than using it themselves, in this sense. 285 // As a short cut, several other opcodes are known to have no pointer 286 // operands of interest. And ret is never followed by a release, so it's 287 // not interesting to examine. 288 switch (I->getOpcode()) { 289 case Instruction::Call: { 290 const CallInst *CI = cast<CallInst>(I); 291 // Check for calls to special functions. 292 if (const Function *F = CI->getCalledFunction()) { 293 InstructionClass Class = GetFunctionClass(F); 294 if (Class != IC_CallOrUser) 295 return Class; 296 297 // None of the intrinsic functions do objc_release. For intrinsics, the 298 // only question is whether or not they may be users. 299 switch (F->getIntrinsicID()) { 300 case 0: break; 301 case Intrinsic::bswap: case Intrinsic::ctpop: 302 case Intrinsic::ctlz: case Intrinsic::cttz: 303 case Intrinsic::returnaddress: case Intrinsic::frameaddress: 304 case Intrinsic::stacksave: case Intrinsic::stackrestore: 305 case Intrinsic::vastart: case Intrinsic::vacopy: case Intrinsic::vaend: 306 // Don't let dbg info affect our results. 307 case Intrinsic::dbg_declare: case Intrinsic::dbg_value: 308 // Short cut: Some intrinsics obviously don't use ObjC pointers. 309 return IC_None; 310 default: 311 for (Function::const_arg_iterator AI = F->arg_begin(), 312 AE = F->arg_end(); AI != AE; ++AI) 313 if (IsPotentialUse(AI)) 314 return IC_User; 315 return IC_None; 316 } 317 } 318 return GetCallSiteClass(CI); 319 } 320 case Instruction::Invoke: 321 return GetCallSiteClass(cast<InvokeInst>(I)); 322 case Instruction::BitCast: 323 case Instruction::GetElementPtr: 324 case Instruction::Select: case Instruction::PHI: 325 case Instruction::Ret: case Instruction::Br: 326 case Instruction::Switch: case Instruction::IndirectBr: 327 case Instruction::Alloca: case Instruction::VAArg: 328 case Instruction::Add: case Instruction::FAdd: 329 case Instruction::Sub: case Instruction::FSub: 330 case Instruction::Mul: case Instruction::FMul: 331 case Instruction::SDiv: case Instruction::UDiv: case Instruction::FDiv: 332 case Instruction::SRem: case Instruction::URem: case Instruction::FRem: 333 case Instruction::Shl: case Instruction::LShr: case Instruction::AShr: 334 case Instruction::And: case Instruction::Or: case Instruction::Xor: 335 case Instruction::SExt: case Instruction::ZExt: case Instruction::Trunc: 336 case Instruction::IntToPtr: case Instruction::FCmp: 337 case Instruction::FPTrunc: case Instruction::FPExt: 338 case Instruction::FPToUI: case Instruction::FPToSI: 339 case Instruction::UIToFP: case Instruction::SIToFP: 340 case Instruction::InsertElement: case Instruction::ExtractElement: 341 case Instruction::ShuffleVector: 342 case Instruction::ExtractValue: 343 break; 344 case Instruction::ICmp: 345 // Comparing a pointer with null, or any other constant, isn't an 346 // interesting use, because we don't care what the pointer points to, or 347 // about the values of any other dynamic reference-counted pointers. 348 if (IsPotentialUse(I->getOperand(1))) 349 return IC_User; 350 break; 351 default: 352 // For anything else, check all the operands. 353 // Note that this includes both operands of a Store: while the first 354 // operand isn't actually being dereferenced, it is being stored to 355 // memory where we can no longer track who might read it and dereference 356 // it, so we have to consider it potentially used. 357 for (User::const_op_iterator OI = I->op_begin(), OE = I->op_end(); 358 OI != OE; ++OI) 359 if (IsPotentialUse(*OI)) 360 return IC_User; 361 } 362 } 363 364 // Otherwise, it's totally inert for ARC purposes. 365 return IC_None; 366} 367 368/// GetBasicInstructionClass - Determine what kind of construct V is. This is 369/// similar to GetInstructionClass except that it only detects objc runtine 370/// calls. This allows it to be faster. 371static InstructionClass GetBasicInstructionClass(const Value *V) { 372 if (const CallInst *CI = dyn_cast<CallInst>(V)) { 373 if (const Function *F = CI->getCalledFunction()) 374 return GetFunctionClass(F); 375 // Otherwise, be conservative. 376 return IC_CallOrUser; 377 } 378 379 // Otherwise, be conservative. 380 return isa<InvokeInst>(V) ? IC_CallOrUser : IC_User; 381} 382 383/// IsRetain - Test if the the given class is objc_retain or 384/// equivalent. 385static bool IsRetain(InstructionClass Class) { 386 return Class == IC_Retain || 387 Class == IC_RetainRV; 388} 389 390/// IsAutorelease - Test if the the given class is objc_autorelease or 391/// equivalent. 392static bool IsAutorelease(InstructionClass Class) { 393 return Class == IC_Autorelease || 394 Class == IC_AutoreleaseRV; 395} 396 397/// IsForwarding - Test if the given class represents instructions which return 398/// their argument verbatim. 399static bool IsForwarding(InstructionClass Class) { 400 // objc_retainBlock technically doesn't always return its argument 401 // verbatim, but it doesn't matter for our purposes here. 402 return Class == IC_Retain || 403 Class == IC_RetainRV || 404 Class == IC_Autorelease || 405 Class == IC_AutoreleaseRV || 406 Class == IC_RetainBlock || 407 Class == IC_NoopCast; 408} 409 410/// IsNoopOnNull - Test if the given class represents instructions which do 411/// nothing if passed a null pointer. 412static bool IsNoopOnNull(InstructionClass Class) { 413 return Class == IC_Retain || 414 Class == IC_RetainRV || 415 Class == IC_Release || 416 Class == IC_Autorelease || 417 Class == IC_AutoreleaseRV || 418 Class == IC_RetainBlock; 419} 420 421/// IsAlwaysTail - Test if the given class represents instructions which are 422/// always safe to mark with the "tail" keyword. 423static bool IsAlwaysTail(InstructionClass Class) { 424 // IC_RetainBlock may be given a stack argument. 425 return Class == IC_Retain || 426 Class == IC_RetainRV || 427 Class == IC_Autorelease || 428 Class == IC_AutoreleaseRV; 429} 430 431/// IsNoThrow - Test if the given class represents instructions which are always 432/// safe to mark with the nounwind attribute.. 433static bool IsNoThrow(InstructionClass Class) { 434 // objc_retainBlock is not nounwind because it calls user copy constructors 435 // which could theoretically throw. 436 return Class == IC_Retain || 437 Class == IC_RetainRV || 438 Class == IC_Release || 439 Class == IC_Autorelease || 440 Class == IC_AutoreleaseRV || 441 Class == IC_AutoreleasepoolPush || 442 Class == IC_AutoreleasepoolPop; 443} 444 445/// EraseInstruction - Erase the given instruction. ObjC calls return their 446/// argument verbatim, so if it's such a call and the return value has users, 447/// replace them with the argument value. 448static void EraseInstruction(Instruction *CI) { 449 Value *OldArg = cast<CallInst>(CI)->getArgOperand(0); 450 451 bool Unused = CI->use_empty(); 452 453 if (!Unused) { 454 // Replace the return value with the argument. 455 assert(IsForwarding(GetBasicInstructionClass(CI)) && 456 "Can't delete non-forwarding instruction with users!"); 457 CI->replaceAllUsesWith(OldArg); 458 } 459 460 CI->eraseFromParent(); 461 462 if (Unused) 463 RecursivelyDeleteTriviallyDeadInstructions(OldArg); 464} 465 466/// GetUnderlyingObjCPtr - This is a wrapper around getUnderlyingObject which 467/// also knows how to look through objc_retain and objc_autorelease calls, which 468/// we know to return their argument verbatim. 469static const Value *GetUnderlyingObjCPtr(const Value *V) { 470 for (;;) { 471 V = GetUnderlyingObject(V); 472 if (!IsForwarding(GetBasicInstructionClass(V))) 473 break; 474 V = cast<CallInst>(V)->getArgOperand(0); 475 } 476 477 return V; 478} 479 480/// StripPointerCastsAndObjCCalls - This is a wrapper around 481/// Value::stripPointerCasts which also knows how to look through objc_retain 482/// and objc_autorelease calls, which we know to return their argument verbatim. 483static const Value *StripPointerCastsAndObjCCalls(const Value *V) { 484 for (;;) { 485 V = V->stripPointerCasts(); 486 if (!IsForwarding(GetBasicInstructionClass(V))) 487 break; 488 V = cast<CallInst>(V)->getArgOperand(0); 489 } 490 return V; 491} 492 493/// StripPointerCastsAndObjCCalls - This is a wrapper around 494/// Value::stripPointerCasts which also knows how to look through objc_retain 495/// and objc_autorelease calls, which we know to return their argument verbatim. 496static Value *StripPointerCastsAndObjCCalls(Value *V) { 497 for (;;) { 498 V = V->stripPointerCasts(); 499 if (!IsForwarding(GetBasicInstructionClass(V))) 500 break; 501 V = cast<CallInst>(V)->getArgOperand(0); 502 } 503 return V; 504} 505 506/// GetObjCArg - Assuming the given instruction is one of the special calls such 507/// as objc_retain or objc_release, return the argument value, stripped of no-op 508/// casts and forwarding calls. 509static Value *GetObjCArg(Value *Inst) { 510 return StripPointerCastsAndObjCCalls(cast<CallInst>(Inst)->getArgOperand(0)); 511} 512 513/// IsObjCIdentifiedObject - This is similar to AliasAnalysis' 514/// isObjCIdentifiedObject, except that it uses special knowledge of 515/// ObjC conventions... 516static bool IsObjCIdentifiedObject(const Value *V) { 517 // Assume that call results and arguments have their own "provenance". 518 // Constants (including GlobalVariables) and Allocas are never 519 // reference-counted. 520 if (isa<CallInst>(V) || isa<InvokeInst>(V) || 521 isa<Argument>(V) || isa<Constant>(V) || 522 isa<AllocaInst>(V)) 523 return true; 524 525 if (const LoadInst *LI = dyn_cast<LoadInst>(V)) { 526 const Value *Pointer = 527 StripPointerCastsAndObjCCalls(LI->getPointerOperand()); 528 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(Pointer)) { 529 // A constant pointer can't be pointing to an object on the heap. It may 530 // be reference-counted, but it won't be deleted. 531 if (GV->isConstant()) 532 return true; 533 StringRef Name = GV->getName(); 534 // These special variables are known to hold values which are not 535 // reference-counted pointers. 536 if (Name.startswith("\01L_OBJC_SELECTOR_REFERENCES_") || 537 Name.startswith("\01L_OBJC_CLASSLIST_REFERENCES_") || 538 Name.startswith("\01L_OBJC_CLASSLIST_SUP_REFS_$_") || 539 Name.startswith("\01L_OBJC_METH_VAR_NAME_") || 540 Name.startswith("\01l_objc_msgSend_fixup_")) 541 return true; 542 } 543 } 544 545 return false; 546} 547 548/// FindSingleUseIdentifiedObject - This is similar to 549/// StripPointerCastsAndObjCCalls but it stops as soon as it finds a value 550/// with multiple uses. 551static const Value *FindSingleUseIdentifiedObject(const Value *Arg) { 552 if (Arg->hasOneUse()) { 553 if (const BitCastInst *BC = dyn_cast<BitCastInst>(Arg)) 554 return FindSingleUseIdentifiedObject(BC->getOperand(0)); 555 if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Arg)) 556 if (GEP->hasAllZeroIndices()) 557 return FindSingleUseIdentifiedObject(GEP->getPointerOperand()); 558 if (IsForwarding(GetBasicInstructionClass(Arg))) 559 return FindSingleUseIdentifiedObject( 560 cast<CallInst>(Arg)->getArgOperand(0)); 561 if (!IsObjCIdentifiedObject(Arg)) 562 return 0; 563 return Arg; 564 } 565 566 // If we found an identifiable object but it has multiple uses, but they 567 // are trivial uses, we can still consider this to be a single-use 568 // value. 569 if (IsObjCIdentifiedObject(Arg)) { 570 for (Value::const_use_iterator UI = Arg->use_begin(), UE = Arg->use_end(); 571 UI != UE; ++UI) { 572 const User *U = *UI; 573 if (!U->use_empty() || StripPointerCastsAndObjCCalls(U) != Arg) 574 return 0; 575 } 576 577 return Arg; 578 } 579 580 return 0; 581} 582 583/// ModuleHasARC - Test if the given module looks interesting to run ARC 584/// optimization on. 585static bool ModuleHasARC(const Module &M) { 586 return 587 M.getNamedValue("objc_retain") || 588 M.getNamedValue("objc_release") || 589 M.getNamedValue("objc_autorelease") || 590 M.getNamedValue("objc_retainAutoreleasedReturnValue") || 591 M.getNamedValue("objc_retainBlock") || 592 M.getNamedValue("objc_autoreleaseReturnValue") || 593 M.getNamedValue("objc_autoreleasePoolPush") || 594 M.getNamedValue("objc_loadWeakRetained") || 595 M.getNamedValue("objc_loadWeak") || 596 M.getNamedValue("objc_destroyWeak") || 597 M.getNamedValue("objc_storeWeak") || 598 M.getNamedValue("objc_initWeak") || 599 M.getNamedValue("objc_moveWeak") || 600 M.getNamedValue("objc_copyWeak") || 601 M.getNamedValue("objc_retainedObject") || 602 M.getNamedValue("objc_unretainedObject") || 603 M.getNamedValue("objc_unretainedPointer"); 604} 605 606/// DoesObjCBlockEscape - Test whether the given pointer, which is an 607/// Objective C block pointer, does not "escape". This differs from regular 608/// escape analysis in that a use as an argument to a call is not considered 609/// an escape. 610static bool DoesObjCBlockEscape(const Value *BlockPtr) { 611 // Walk the def-use chains. 612 SmallVector<const Value *, 4> Worklist; 613 Worklist.push_back(BlockPtr); 614 do { 615 const Value *V = Worklist.pop_back_val(); 616 for (Value::const_use_iterator UI = V->use_begin(), UE = V->use_end(); 617 UI != UE; ++UI) { 618 const User *UUser = *UI; 619 // Special - Use by a call (callee or argument) is not considered 620 // to be an escape. 621 if (isa<CallInst>(UUser) || isa<InvokeInst>(UUser)) 622 continue; 623 // Use by an instruction which copies the value is an escape if the 624 // result is an escape. 625 if (isa<BitCastInst>(UUser) || isa<GetElementPtrInst>(UUser) || 626 isa<PHINode>(UUser) || isa<SelectInst>(UUser)) { 627 Worklist.push_back(UUser); 628 continue; 629 } 630 // Use by a load is not an escape. 631 if (isa<LoadInst>(UUser)) 632 continue; 633 // Use by a store is not an escape if the use is the address. 634 if (const StoreInst *SI = dyn_cast<StoreInst>(UUser)) 635 if (V != SI->getValueOperand()) 636 continue; 637 // Otherwise, conservatively assume an escape. 638 return true; 639 } 640 } while (!Worklist.empty()); 641 642 // No escapes found. 643 return false; 644} 645 646//===----------------------------------------------------------------------===// 647// ARC AliasAnalysis. 648//===----------------------------------------------------------------------===// 649 650#include "llvm/Pass.h" 651#include "llvm/Analysis/AliasAnalysis.h" 652#include "llvm/Analysis/Passes.h" 653 654namespace { 655 /// ObjCARCAliasAnalysis - This is a simple alias analysis 656 /// implementation that uses knowledge of ARC constructs to answer queries. 657 /// 658 /// TODO: This class could be generalized to know about other ObjC-specific 659 /// tricks. Such as knowing that ivars in the non-fragile ABI are non-aliasing 660 /// even though their offsets are dynamic. 661 class ObjCARCAliasAnalysis : public ImmutablePass, 662 public AliasAnalysis { 663 public: 664 static char ID; // Class identification, replacement for typeinfo 665 ObjCARCAliasAnalysis() : ImmutablePass(ID) { 666 initializeObjCARCAliasAnalysisPass(*PassRegistry::getPassRegistry()); 667 } 668 669 private: 670 virtual void initializePass() { 671 InitializeAliasAnalysis(this); 672 } 673 674 /// getAdjustedAnalysisPointer - This method is used when a pass implements 675 /// an analysis interface through multiple inheritance. If needed, it 676 /// should override this to adjust the this pointer as needed for the 677 /// specified pass info. 678 virtual void *getAdjustedAnalysisPointer(const void *PI) { 679 if (PI == &AliasAnalysis::ID) 680 return (AliasAnalysis*)this; 681 return this; 682 } 683 684 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 685 virtual AliasResult alias(const Location &LocA, const Location &LocB); 686 virtual bool pointsToConstantMemory(const Location &Loc, bool OrLocal); 687 virtual ModRefBehavior getModRefBehavior(ImmutableCallSite CS); 688 virtual ModRefBehavior getModRefBehavior(const Function *F); 689 virtual ModRefResult getModRefInfo(ImmutableCallSite CS, 690 const Location &Loc); 691 virtual ModRefResult getModRefInfo(ImmutableCallSite CS1, 692 ImmutableCallSite CS2); 693 }; 694} // End of anonymous namespace 695 696// Register this pass... 697char ObjCARCAliasAnalysis::ID = 0; 698INITIALIZE_AG_PASS(ObjCARCAliasAnalysis, AliasAnalysis, "objc-arc-aa", 699 "ObjC-ARC-Based Alias Analysis", false, true, false) 700 701ImmutablePass *llvm::createObjCARCAliasAnalysisPass() { 702 return new ObjCARCAliasAnalysis(); 703} 704 705void 706ObjCARCAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 707 AU.setPreservesAll(); 708 AliasAnalysis::getAnalysisUsage(AU); 709} 710 711AliasAnalysis::AliasResult 712ObjCARCAliasAnalysis::alias(const Location &LocA, const Location &LocB) { 713 if (!EnableARCOpts) 714 return AliasAnalysis::alias(LocA, LocB); 715 716 // First, strip off no-ops, including ObjC-specific no-ops, and try making a 717 // precise alias query. 718 const Value *SA = StripPointerCastsAndObjCCalls(LocA.Ptr); 719 const Value *SB = StripPointerCastsAndObjCCalls(LocB.Ptr); 720 AliasResult Result = 721 AliasAnalysis::alias(Location(SA, LocA.Size, LocA.TBAATag), 722 Location(SB, LocB.Size, LocB.TBAATag)); 723 if (Result != MayAlias) 724 return Result; 725 726 // If that failed, climb to the underlying object, including climbing through 727 // ObjC-specific no-ops, and try making an imprecise alias query. 728 const Value *UA = GetUnderlyingObjCPtr(SA); 729 const Value *UB = GetUnderlyingObjCPtr(SB); 730 if (UA != SA || UB != SB) { 731 Result = AliasAnalysis::alias(Location(UA), Location(UB)); 732 // We can't use MustAlias or PartialAlias results here because 733 // GetUnderlyingObjCPtr may return an offsetted pointer value. 734 if (Result == NoAlias) 735 return NoAlias; 736 } 737 738 // If that failed, fail. We don't need to chain here, since that's covered 739 // by the earlier precise query. 740 return MayAlias; 741} 742 743bool 744ObjCARCAliasAnalysis::pointsToConstantMemory(const Location &Loc, 745 bool OrLocal) { 746 if (!EnableARCOpts) 747 return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 748 749 // First, strip off no-ops, including ObjC-specific no-ops, and try making 750 // a precise alias query. 751 const Value *S = StripPointerCastsAndObjCCalls(Loc.Ptr); 752 if (AliasAnalysis::pointsToConstantMemory(Location(S, Loc.Size, Loc.TBAATag), 753 OrLocal)) 754 return true; 755 756 // If that failed, climb to the underlying object, including climbing through 757 // ObjC-specific no-ops, and try making an imprecise alias query. 758 const Value *U = GetUnderlyingObjCPtr(S); 759 if (U != S) 760 return AliasAnalysis::pointsToConstantMemory(Location(U), OrLocal); 761 762 // If that failed, fail. We don't need to chain here, since that's covered 763 // by the earlier precise query. 764 return false; 765} 766 767AliasAnalysis::ModRefBehavior 768ObjCARCAliasAnalysis::getModRefBehavior(ImmutableCallSite CS) { 769 // We have nothing to do. Just chain to the next AliasAnalysis. 770 return AliasAnalysis::getModRefBehavior(CS); 771} 772 773AliasAnalysis::ModRefBehavior 774ObjCARCAliasAnalysis::getModRefBehavior(const Function *F) { 775 if (!EnableARCOpts) 776 return AliasAnalysis::getModRefBehavior(F); 777 778 switch (GetFunctionClass(F)) { 779 case IC_NoopCast: 780 return DoesNotAccessMemory; 781 default: 782 break; 783 } 784 785 return AliasAnalysis::getModRefBehavior(F); 786} 787 788AliasAnalysis::ModRefResult 789ObjCARCAliasAnalysis::getModRefInfo(ImmutableCallSite CS, const Location &Loc) { 790 if (!EnableARCOpts) 791 return AliasAnalysis::getModRefInfo(CS, Loc); 792 793 switch (GetBasicInstructionClass(CS.getInstruction())) { 794 case IC_Retain: 795 case IC_RetainRV: 796 case IC_Autorelease: 797 case IC_AutoreleaseRV: 798 case IC_NoopCast: 799 case IC_AutoreleasepoolPush: 800 case IC_FusedRetainAutorelease: 801 case IC_FusedRetainAutoreleaseRV: 802 // These functions don't access any memory visible to the compiler. 803 // Note that this doesn't include objc_retainBlock, becuase it updates 804 // pointers when it copies block data. 805 return NoModRef; 806 default: 807 break; 808 } 809 810 return AliasAnalysis::getModRefInfo(CS, Loc); 811} 812 813AliasAnalysis::ModRefResult 814ObjCARCAliasAnalysis::getModRefInfo(ImmutableCallSite CS1, 815 ImmutableCallSite CS2) { 816 // TODO: Theoretically we could check for dependencies between objc_* calls 817 // and OnlyAccessesArgumentPointees calls or other well-behaved calls. 818 return AliasAnalysis::getModRefInfo(CS1, CS2); 819} 820 821//===----------------------------------------------------------------------===// 822// ARC expansion. 823//===----------------------------------------------------------------------===// 824 825#include "llvm/Support/InstIterator.h" 826#include "llvm/Transforms/Scalar.h" 827 828namespace { 829 /// ObjCARCExpand - Early ARC transformations. 830 class ObjCARCExpand : public FunctionPass { 831 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 832 virtual bool doInitialization(Module &M); 833 virtual bool runOnFunction(Function &F); 834 835 /// Run - A flag indicating whether this optimization pass should run. 836 bool Run; 837 838 public: 839 static char ID; 840 ObjCARCExpand() : FunctionPass(ID) { 841 initializeObjCARCExpandPass(*PassRegistry::getPassRegistry()); 842 } 843 }; 844} 845 846char ObjCARCExpand::ID = 0; 847INITIALIZE_PASS(ObjCARCExpand, 848 "objc-arc-expand", "ObjC ARC expansion", false, false) 849 850Pass *llvm::createObjCARCExpandPass() { 851 return new ObjCARCExpand(); 852} 853 854void ObjCARCExpand::getAnalysisUsage(AnalysisUsage &AU) const { 855 AU.setPreservesCFG(); 856} 857 858bool ObjCARCExpand::doInitialization(Module &M) { 859 Run = ModuleHasARC(M); 860 return false; 861} 862 863bool ObjCARCExpand::runOnFunction(Function &F) { 864 if (!EnableARCOpts) 865 return false; 866 867 // If nothing in the Module uses ARC, don't do anything. 868 if (!Run) 869 return false; 870 871 bool Changed = false; 872 873 for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ++I) { 874 Instruction *Inst = &*I; 875 876 switch (GetBasicInstructionClass(Inst)) { 877 case IC_Retain: 878 case IC_RetainRV: 879 case IC_Autorelease: 880 case IC_AutoreleaseRV: 881 case IC_FusedRetainAutorelease: 882 case IC_FusedRetainAutoreleaseRV: 883 // These calls return their argument verbatim, as a low-level 884 // optimization. However, this makes high-level optimizations 885 // harder. Undo any uses of this optimization that the front-end 886 // emitted here. We'll redo them in a later pass. 887 Changed = true; 888 Inst->replaceAllUsesWith(cast<CallInst>(Inst)->getArgOperand(0)); 889 break; 890 default: 891 break; 892 } 893 } 894 895 return Changed; 896} 897 898//===----------------------------------------------------------------------===// 899// ARC autorelease pool elimination. 900//===----------------------------------------------------------------------===// 901 902#include "llvm/Constants.h" 903 904namespace { 905 /// ObjCARCAPElim - Autorelease pool elimination. 906 class ObjCARCAPElim : public ModulePass { 907 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 908 virtual bool runOnModule(Module &M); 909 910 bool MayAutorelease(CallSite CS, unsigned Depth = 0); 911 bool OptimizeBB(BasicBlock *BB); 912 913 public: 914 static char ID; 915 ObjCARCAPElim() : ModulePass(ID) { 916 initializeObjCARCAPElimPass(*PassRegistry::getPassRegistry()); 917 } 918 }; 919} 920 921char ObjCARCAPElim::ID = 0; 922INITIALIZE_PASS(ObjCARCAPElim, 923 "objc-arc-apelim", 924 "ObjC ARC autorelease pool elimination", 925 false, false) 926 927Pass *llvm::createObjCARCAPElimPass() { 928 return new ObjCARCAPElim(); 929} 930 931void ObjCARCAPElim::getAnalysisUsage(AnalysisUsage &AU) const { 932 AU.setPreservesCFG(); 933} 934 935/// MayAutorelease - Interprocedurally determine if calls made by the 936/// given call site can possibly produce autoreleases. 937bool ObjCARCAPElim::MayAutorelease(CallSite CS, unsigned Depth) { 938 if (Function *Callee = CS.getCalledFunction()) { 939 if (Callee->isDeclaration() || Callee->mayBeOverridden()) 940 return true; 941 for (Function::iterator I = Callee->begin(), E = Callee->end(); 942 I != E; ++I) { 943 BasicBlock *BB = I; 944 for (BasicBlock::iterator J = BB->begin(), F = BB->end(); J != F; ++J) 945 if (CallSite JCS = CallSite(J)) 946 // This recursion depth limit is arbitrary. It's just great 947 // enough to cover known interesting testcases. 948 if (Depth < 3 && 949 !JCS.onlyReadsMemory() && 950 MayAutorelease(JCS, Depth + 1)) 951 return true; 952 } 953 return false; 954 } 955 956 return true; 957} 958 959bool ObjCARCAPElim::OptimizeBB(BasicBlock *BB) { 960 bool Changed = false; 961 962 Instruction *Push = 0; 963 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) { 964 Instruction *Inst = I++; 965 switch (GetBasicInstructionClass(Inst)) { 966 case IC_AutoreleasepoolPush: 967 Push = Inst; 968 break; 969 case IC_AutoreleasepoolPop: 970 // If this pop matches a push and nothing in between can autorelease, 971 // zap the pair. 972 if (Push && cast<CallInst>(Inst)->getArgOperand(0) == Push) { 973 Changed = true; 974 Inst->eraseFromParent(); 975 Push->eraseFromParent(); 976 } 977 Push = 0; 978 break; 979 case IC_CallOrUser: 980 if (MayAutorelease(CallSite(Inst))) 981 Push = 0; 982 break; 983 default: 984 break; 985 } 986 } 987 988 return Changed; 989} 990 991bool ObjCARCAPElim::runOnModule(Module &M) { 992 if (!EnableARCOpts) 993 return false; 994 995 // If nothing in the Module uses ARC, don't do anything. 996 if (!ModuleHasARC(M)) 997 return false; 998 999 // Find the llvm.global_ctors variable, as the first step in 1000 // identifying the global constructors. 1001 GlobalVariable *GV = M.getGlobalVariable("llvm.global_ctors"); 1002 if (!GV) 1003 return false; 1004 1005 assert(GV->hasDefinitiveInitializer() && 1006 "llvm.global_ctors is uncooperative!"); 1007 1008 bool Changed = false; 1009 1010 // Dig the constructor functions out of GV's initializer. 1011 ConstantArray *Init = cast<ConstantArray>(GV->getInitializer()); 1012 for (User::op_iterator OI = Init->op_begin(), OE = Init->op_end(); 1013 OI != OE; ++OI) { 1014 Value *Op = *OI; 1015 // llvm.global_ctors is an array of pairs where the second members 1016 // are constructor functions. 1017 Function *F = cast<Function>(cast<ConstantStruct>(Op)->getOperand(1)); 1018 // Only look at function definitions. 1019 if (F->isDeclaration()) 1020 continue; 1021 // Only look at functions with one basic block. 1022 if (llvm::next(F->begin()) != F->end()) 1023 continue; 1024 // Ok, a single-block constructor function definition. Try to optimize it. 1025 Changed |= OptimizeBB(F->begin()); 1026 } 1027 1028 return Changed; 1029} 1030 1031//===----------------------------------------------------------------------===// 1032// ARC optimization. 1033//===----------------------------------------------------------------------===// 1034 1035// TODO: On code like this: 1036// 1037// objc_retain(%x) 1038// stuff_that_cannot_release() 1039// objc_autorelease(%x) 1040// stuff_that_cannot_release() 1041// objc_retain(%x) 1042// stuff_that_cannot_release() 1043// objc_autorelease(%x) 1044// 1045// The second retain and autorelease can be deleted. 1046 1047// TODO: It should be possible to delete 1048// objc_autoreleasePoolPush and objc_autoreleasePoolPop 1049// pairs if nothing is actually autoreleased between them. Also, autorelease 1050// calls followed by objc_autoreleasePoolPop calls (perhaps in ObjC++ code 1051// after inlining) can be turned into plain release calls. 1052 1053// TODO: Critical-edge splitting. If the optimial insertion point is 1054// a critical edge, the current algorithm has to fail, because it doesn't 1055// know how to split edges. It should be possible to make the optimizer 1056// think in terms of edges, rather than blocks, and then split critical 1057// edges on demand. 1058 1059// TODO: OptimizeSequences could generalized to be Interprocedural. 1060 1061// TODO: Recognize that a bunch of other objc runtime calls have 1062// non-escaping arguments and non-releasing arguments, and may be 1063// non-autoreleasing. 1064 1065// TODO: Sink autorelease calls as far as possible. Unfortunately we 1066// usually can't sink them past other calls, which would be the main 1067// case where it would be useful. 1068 1069// TODO: The pointer returned from objc_loadWeakRetained is retained. 1070 1071// TODO: Delete release+retain pairs (rare). 1072 1073#include "llvm/GlobalAlias.h" 1074#include "llvm/Constants.h" 1075#include "llvm/LLVMContext.h" 1076#include "llvm/Support/ErrorHandling.h" 1077#include "llvm/Support/CFG.h" 1078#include "llvm/ADT/Statistic.h" 1079#include "llvm/ADT/SmallPtrSet.h" 1080#include "llvm/ADT/DenseSet.h" 1081 1082STATISTIC(NumNoops, "Number of no-op objc calls eliminated"); 1083STATISTIC(NumPartialNoops, "Number of partially no-op objc calls eliminated"); 1084STATISTIC(NumAutoreleases,"Number of autoreleases converted to releases"); 1085STATISTIC(NumRets, "Number of return value forwarding " 1086 "retain+autoreleaes eliminated"); 1087STATISTIC(NumRRs, "Number of retain+release paths eliminated"); 1088STATISTIC(NumPeeps, "Number of calls peephole-optimized"); 1089 1090namespace { 1091 /// ProvenanceAnalysis - This is similar to BasicAliasAnalysis, and it 1092 /// uses many of the same techniques, except it uses special ObjC-specific 1093 /// reasoning about pointer relationships. 1094 class ProvenanceAnalysis { 1095 AliasAnalysis *AA; 1096 1097 typedef std::pair<const Value *, const Value *> ValuePairTy; 1098 typedef DenseMap<ValuePairTy, bool> CachedResultsTy; 1099 CachedResultsTy CachedResults; 1100 1101 bool relatedCheck(const Value *A, const Value *B); 1102 bool relatedSelect(const SelectInst *A, const Value *B); 1103 bool relatedPHI(const PHINode *A, const Value *B); 1104 1105 // Do not implement. 1106 void operator=(const ProvenanceAnalysis &); 1107 ProvenanceAnalysis(const ProvenanceAnalysis &); 1108 1109 public: 1110 ProvenanceAnalysis() {} 1111 1112 void setAA(AliasAnalysis *aa) { AA = aa; } 1113 1114 AliasAnalysis *getAA() const { return AA; } 1115 1116 bool related(const Value *A, const Value *B); 1117 1118 void clear() { 1119 CachedResults.clear(); 1120 } 1121 }; 1122} 1123 1124bool ProvenanceAnalysis::relatedSelect(const SelectInst *A, const Value *B) { 1125 // If the values are Selects with the same condition, we can do a more precise 1126 // check: just check for relations between the values on corresponding arms. 1127 if (const SelectInst *SB = dyn_cast<SelectInst>(B)) 1128 if (A->getCondition() == SB->getCondition()) { 1129 if (related(A->getTrueValue(), SB->getTrueValue())) 1130 return true; 1131 if (related(A->getFalseValue(), SB->getFalseValue())) 1132 return true; 1133 return false; 1134 } 1135 1136 // Check both arms of the Select node individually. 1137 if (related(A->getTrueValue(), B)) 1138 return true; 1139 if (related(A->getFalseValue(), B)) 1140 return true; 1141 1142 // The arms both checked out. 1143 return false; 1144} 1145 1146bool ProvenanceAnalysis::relatedPHI(const PHINode *A, const Value *B) { 1147 // If the values are PHIs in the same block, we can do a more precise as well 1148 // as efficient check: just check for relations between the values on 1149 // corresponding edges. 1150 if (const PHINode *PNB = dyn_cast<PHINode>(B)) 1151 if (PNB->getParent() == A->getParent()) { 1152 for (unsigned i = 0, e = A->getNumIncomingValues(); i != e; ++i) 1153 if (related(A->getIncomingValue(i), 1154 PNB->getIncomingValueForBlock(A->getIncomingBlock(i)))) 1155 return true; 1156 return false; 1157 } 1158 1159 // Check each unique source of the PHI node against B. 1160 SmallPtrSet<const Value *, 4> UniqueSrc; 1161 for (unsigned i = 0, e = A->getNumIncomingValues(); i != e; ++i) { 1162 const Value *PV1 = A->getIncomingValue(i); 1163 if (UniqueSrc.insert(PV1) && related(PV1, B)) 1164 return true; 1165 } 1166 1167 // All of the arms checked out. 1168 return false; 1169} 1170 1171/// isStoredObjCPointer - Test if the value of P, or any value covered by its 1172/// provenance, is ever stored within the function (not counting callees). 1173static bool isStoredObjCPointer(const Value *P) { 1174 SmallPtrSet<const Value *, 8> Visited; 1175 SmallVector<const Value *, 8> Worklist; 1176 Worklist.push_back(P); 1177 Visited.insert(P); 1178 do { 1179 P = Worklist.pop_back_val(); 1180 for (Value::const_use_iterator UI = P->use_begin(), UE = P->use_end(); 1181 UI != UE; ++UI) { 1182 const User *Ur = *UI; 1183 if (isa<StoreInst>(Ur)) { 1184 if (UI.getOperandNo() == 0) 1185 // The pointer is stored. 1186 return true; 1187 // The pointed is stored through. 1188 continue; 1189 } 1190 if (isa<CallInst>(Ur)) 1191 // The pointer is passed as an argument, ignore this. 1192 continue; 1193 if (isa<PtrToIntInst>(P)) 1194 // Assume the worst. 1195 return true; 1196 if (Visited.insert(Ur)) 1197 Worklist.push_back(Ur); 1198 } 1199 } while (!Worklist.empty()); 1200 1201 // Everything checked out. 1202 return false; 1203} 1204 1205bool ProvenanceAnalysis::relatedCheck(const Value *A, const Value *B) { 1206 // Skip past provenance pass-throughs. 1207 A = GetUnderlyingObjCPtr(A); 1208 B = GetUnderlyingObjCPtr(B); 1209 1210 // Quick check. 1211 if (A == B) 1212 return true; 1213 1214 // Ask regular AliasAnalysis, for a first approximation. 1215 switch (AA->alias(A, B)) { 1216 case AliasAnalysis::NoAlias: 1217 return false; 1218 case AliasAnalysis::MustAlias: 1219 case AliasAnalysis::PartialAlias: 1220 return true; 1221 case AliasAnalysis::MayAlias: 1222 break; 1223 } 1224 1225 bool AIsIdentified = IsObjCIdentifiedObject(A); 1226 bool BIsIdentified = IsObjCIdentifiedObject(B); 1227 1228 // An ObjC-Identified object can't alias a load if it is never locally stored. 1229 if (AIsIdentified) { 1230 if (BIsIdentified) { 1231 // If both pointers have provenance, they can be directly compared. 1232 if (A != B) 1233 return false; 1234 } else { 1235 if (isa<LoadInst>(B)) 1236 return isStoredObjCPointer(A); 1237 } 1238 } else { 1239 if (BIsIdentified && isa<LoadInst>(A)) 1240 return isStoredObjCPointer(B); 1241 } 1242 1243 // Special handling for PHI and Select. 1244 if (const PHINode *PN = dyn_cast<PHINode>(A)) 1245 return relatedPHI(PN, B); 1246 if (const PHINode *PN = dyn_cast<PHINode>(B)) 1247 return relatedPHI(PN, A); 1248 if (const SelectInst *S = dyn_cast<SelectInst>(A)) 1249 return relatedSelect(S, B); 1250 if (const SelectInst *S = dyn_cast<SelectInst>(B)) 1251 return relatedSelect(S, A); 1252 1253 // Conservative. 1254 return true; 1255} 1256 1257bool ProvenanceAnalysis::related(const Value *A, const Value *B) { 1258 // Begin by inserting a conservative value into the map. If the insertion 1259 // fails, we have the answer already. If it succeeds, leave it there until we 1260 // compute the real answer to guard against recursive queries. 1261 if (A > B) std::swap(A, B); 1262 std::pair<CachedResultsTy::iterator, bool> Pair = 1263 CachedResults.insert(std::make_pair(ValuePairTy(A, B), true)); 1264 if (!Pair.second) 1265 return Pair.first->second; 1266 1267 bool Result = relatedCheck(A, B); 1268 CachedResults[ValuePairTy(A, B)] = Result; 1269 return Result; 1270} 1271 1272namespace { 1273 // Sequence - A sequence of states that a pointer may go through in which an 1274 // objc_retain and objc_release are actually needed. 1275 enum Sequence { 1276 S_None, 1277 S_Retain, ///< objc_retain(x) 1278 S_CanRelease, ///< foo(x) -- x could possibly see a ref count decrement 1279 S_Use, ///< any use of x 1280 S_Stop, ///< like S_Release, but code motion is stopped 1281 S_Release, ///< objc_release(x) 1282 S_MovableRelease ///< objc_release(x), !clang.imprecise_release 1283 }; 1284} 1285 1286static Sequence MergeSeqs(Sequence A, Sequence B, bool TopDown) { 1287 // The easy cases. 1288 if (A == B) 1289 return A; 1290 if (A == S_None || B == S_None) 1291 return S_None; 1292 1293 if (A > B) std::swap(A, B); 1294 if (TopDown) { 1295 // Choose the side which is further along in the sequence. 1296 if ((A == S_Retain || A == S_CanRelease) && 1297 (B == S_CanRelease || B == S_Use)) 1298 return B; 1299 } else { 1300 // Choose the side which is further along in the sequence. 1301 if ((A == S_Use || A == S_CanRelease) && 1302 (B == S_Use || B == S_Release || B == S_Stop || B == S_MovableRelease)) 1303 return A; 1304 // If both sides are releases, choose the more conservative one. 1305 if (A == S_Stop && (B == S_Release || B == S_MovableRelease)) 1306 return A; 1307 if (A == S_Release && B == S_MovableRelease) 1308 return A; 1309 } 1310 1311 return S_None; 1312} 1313 1314namespace { 1315 /// RRInfo - Unidirectional information about either a 1316 /// retain-decrement-use-release sequence or release-use-decrement-retain 1317 /// reverese sequence. 1318 struct RRInfo { 1319 /// KnownSafe - After an objc_retain, the reference count of the referenced 1320 /// object is known to be positive. Similarly, before an objc_release, the 1321 /// reference count of the referenced object is known to be positive. If 1322 /// there are retain-release pairs in code regions where the retain count 1323 /// is known to be positive, they can be eliminated, regardless of any side 1324 /// effects between them. 1325 /// 1326 /// Also, a retain+release pair nested within another retain+release 1327 /// pair all on the known same pointer value can be eliminated, regardless 1328 /// of any intervening side effects. 1329 /// 1330 /// KnownSafe is true when either of these conditions is satisfied. 1331 bool KnownSafe; 1332 1333 /// IsRetainBlock - True if the Calls are objc_retainBlock calls (as 1334 /// opposed to objc_retain calls). 1335 bool IsRetainBlock; 1336 1337 /// IsTailCallRelease - True of the objc_release calls are all marked 1338 /// with the "tail" keyword. 1339 bool IsTailCallRelease; 1340 1341 /// Partial - True of we've seen an opportunity for partial RR elimination, 1342 /// such as pushing calls into a CFG triangle or into one side of a 1343 /// CFG diamond. 1344 /// TODO: Consider moving this to PtrState. 1345 bool Partial; 1346 1347 /// ReleaseMetadata - If the Calls are objc_release calls and they all have 1348 /// a clang.imprecise_release tag, this is the metadata tag. 1349 MDNode *ReleaseMetadata; 1350 1351 /// Calls - For a top-down sequence, the set of objc_retains or 1352 /// objc_retainBlocks. For bottom-up, the set of objc_releases. 1353 SmallPtrSet<Instruction *, 2> Calls; 1354 1355 /// ReverseInsertPts - The set of optimal insert positions for 1356 /// moving calls in the opposite sequence. 1357 SmallPtrSet<Instruction *, 2> ReverseInsertPts; 1358 1359 RRInfo() : 1360 KnownSafe(false), IsRetainBlock(false), 1361 IsTailCallRelease(false), Partial(false), 1362 ReleaseMetadata(0) {} 1363 1364 void clear(); 1365 }; 1366} 1367 1368void RRInfo::clear() { 1369 KnownSafe = false; 1370 IsRetainBlock = false; 1371 IsTailCallRelease = false; 1372 Partial = false; 1373 ReleaseMetadata = 0; 1374 Calls.clear(); 1375 ReverseInsertPts.clear(); 1376} 1377 1378namespace { 1379 /// PtrState - This class summarizes several per-pointer runtime properties 1380 /// which are propogated through the flow graph. 1381 class PtrState { 1382 /// RefCount - The known minimum number of reference count increments. 1383 unsigned RefCount; 1384 1385 /// NestCount - The known minimum level of retain+release nesting. 1386 unsigned NestCount; 1387 1388 /// Seq - The current position in the sequence. 1389 Sequence Seq; 1390 1391 public: 1392 /// RRI - Unidirectional information about the current sequence. 1393 /// TODO: Encapsulate this better. 1394 RRInfo RRI; 1395 1396 PtrState() : RefCount(0), NestCount(0), Seq(S_None) {} 1397 1398 void SetAtLeastOneRefCount() { 1399 if (RefCount == 0) RefCount = 1; 1400 } 1401 1402 void IncrementRefCount() { 1403 if (RefCount != UINT_MAX) ++RefCount; 1404 } 1405 1406 void DecrementRefCount() { 1407 if (RefCount != 0) --RefCount; 1408 } 1409 1410 bool IsKnownIncremented() const { 1411 return RefCount > 0; 1412 } 1413 1414 void IncrementNestCount() { 1415 if (NestCount != UINT_MAX) ++NestCount; 1416 } 1417 1418 void DecrementNestCount() { 1419 if (NestCount != 0) --NestCount; 1420 } 1421 1422 bool IsKnownNested() const { 1423 return NestCount > 0; 1424 } 1425 1426 void SetSeq(Sequence NewSeq) { 1427 Seq = NewSeq; 1428 } 1429 1430 Sequence GetSeq() const { 1431 return Seq; 1432 } 1433 1434 void ClearSequenceProgress() { 1435 Seq = S_None; 1436 RRI.clear(); 1437 } 1438 1439 void Merge(const PtrState &Other, bool TopDown); 1440 }; 1441} 1442 1443void 1444PtrState::Merge(const PtrState &Other, bool TopDown) { 1445 Seq = MergeSeqs(Seq, Other.Seq, TopDown); 1446 RefCount = std::min(RefCount, Other.RefCount); 1447 NestCount = std::min(NestCount, Other.NestCount); 1448 1449 // We can't merge a plain objc_retain with an objc_retainBlock. 1450 if (RRI.IsRetainBlock != Other.RRI.IsRetainBlock) 1451 Seq = S_None; 1452 1453 // If we're not in a sequence (anymore), drop all associated state. 1454 if (Seq == S_None) { 1455 RRI.clear(); 1456 } else if (RRI.Partial || Other.RRI.Partial) { 1457 // If we're doing a merge on a path that's previously seen a partial 1458 // merge, conservatively drop the sequence, to avoid doing partial 1459 // RR elimination. If the branch predicates for the two merge differ, 1460 // mixing them is unsafe. 1461 Seq = S_None; 1462 RRI.clear(); 1463 } else { 1464 // Conservatively merge the ReleaseMetadata information. 1465 if (RRI.ReleaseMetadata != Other.RRI.ReleaseMetadata) 1466 RRI.ReleaseMetadata = 0; 1467 1468 RRI.KnownSafe = RRI.KnownSafe && Other.RRI.KnownSafe; 1469 RRI.IsTailCallRelease = RRI.IsTailCallRelease && Other.RRI.IsTailCallRelease; 1470 RRI.Calls.insert(Other.RRI.Calls.begin(), Other.RRI.Calls.end()); 1471 1472 // Merge the insert point sets. If there are any differences, 1473 // that makes this a partial merge. 1474 RRI.Partial = RRI.ReverseInsertPts.size() != 1475 Other.RRI.ReverseInsertPts.size(); 1476 for (SmallPtrSet<Instruction *, 2>::const_iterator 1477 I = Other.RRI.ReverseInsertPts.begin(), 1478 E = Other.RRI.ReverseInsertPts.end(); I != E; ++I) 1479 RRI.Partial |= RRI.ReverseInsertPts.insert(*I); 1480 } 1481} 1482 1483namespace { 1484 /// BBState - Per-BasicBlock state. 1485 class BBState { 1486 /// TopDownPathCount - The number of unique control paths from the entry 1487 /// which can reach this block. 1488 unsigned TopDownPathCount; 1489 1490 /// BottomUpPathCount - The number of unique control paths to exits 1491 /// from this block. 1492 unsigned BottomUpPathCount; 1493 1494 /// MapTy - A type for PerPtrTopDown and PerPtrBottomUp. 1495 typedef MapVector<const Value *, PtrState> MapTy; 1496 1497 /// PerPtrTopDown - The top-down traversal uses this to record information 1498 /// known about a pointer at the bottom of each block. 1499 MapTy PerPtrTopDown; 1500 1501 /// PerPtrBottomUp - The bottom-up traversal uses this to record information 1502 /// known about a pointer at the top of each block. 1503 MapTy PerPtrBottomUp; 1504 1505 public: 1506 BBState() : TopDownPathCount(0), BottomUpPathCount(0) {} 1507 1508 typedef MapTy::iterator ptr_iterator; 1509 typedef MapTy::const_iterator ptr_const_iterator; 1510 1511 ptr_iterator top_down_ptr_begin() { return PerPtrTopDown.begin(); } 1512 ptr_iterator top_down_ptr_end() { return PerPtrTopDown.end(); } 1513 ptr_const_iterator top_down_ptr_begin() const { 1514 return PerPtrTopDown.begin(); 1515 } 1516 ptr_const_iterator top_down_ptr_end() const { 1517 return PerPtrTopDown.end(); 1518 } 1519 1520 ptr_iterator bottom_up_ptr_begin() { return PerPtrBottomUp.begin(); } 1521 ptr_iterator bottom_up_ptr_end() { return PerPtrBottomUp.end(); } 1522 ptr_const_iterator bottom_up_ptr_begin() const { 1523 return PerPtrBottomUp.begin(); 1524 } 1525 ptr_const_iterator bottom_up_ptr_end() const { 1526 return PerPtrBottomUp.end(); 1527 } 1528 1529 /// SetAsEntry - Mark this block as being an entry block, which has one 1530 /// path from the entry by definition. 1531 void SetAsEntry() { TopDownPathCount = 1; } 1532 1533 /// SetAsExit - Mark this block as being an exit block, which has one 1534 /// path to an exit by definition. 1535 void SetAsExit() { BottomUpPathCount = 1; } 1536 1537 PtrState &getPtrTopDownState(const Value *Arg) { 1538 return PerPtrTopDown[Arg]; 1539 } 1540 1541 PtrState &getPtrBottomUpState(const Value *Arg) { 1542 return PerPtrBottomUp[Arg]; 1543 } 1544 1545 void clearBottomUpPointers() { 1546 PerPtrBottomUp.clear(); 1547 } 1548 1549 void clearTopDownPointers() { 1550 PerPtrTopDown.clear(); 1551 } 1552 1553 void InitFromPred(const BBState &Other); 1554 void InitFromSucc(const BBState &Other); 1555 void MergePred(const BBState &Other); 1556 void MergeSucc(const BBState &Other); 1557 1558 /// GetAllPathCount - Return the number of possible unique paths from an 1559 /// entry to an exit which pass through this block. This is only valid 1560 /// after both the top-down and bottom-up traversals are complete. 1561 unsigned GetAllPathCount() const { 1562 return TopDownPathCount * BottomUpPathCount; 1563 } 1564 1565 /// IsVisitedTopDown - Test whether the block for this BBState has been 1566 /// visited by the top-down portion of the algorithm. 1567 bool isVisitedTopDown() const { 1568 return TopDownPathCount != 0; 1569 } 1570 }; 1571} 1572 1573void BBState::InitFromPred(const BBState &Other) { 1574 PerPtrTopDown = Other.PerPtrTopDown; 1575 TopDownPathCount = Other.TopDownPathCount; 1576} 1577 1578void BBState::InitFromSucc(const BBState &Other) { 1579 PerPtrBottomUp = Other.PerPtrBottomUp; 1580 BottomUpPathCount = Other.BottomUpPathCount; 1581} 1582 1583/// MergePred - The top-down traversal uses this to merge information about 1584/// predecessors to form the initial state for a new block. 1585void BBState::MergePred(const BBState &Other) { 1586 // Other.TopDownPathCount can be 0, in which case it is either dead or a 1587 // loop backedge. Loop backedges are special. 1588 TopDownPathCount += Other.TopDownPathCount; 1589 1590 // For each entry in the other set, if our set has an entry with the same key, 1591 // merge the entries. Otherwise, copy the entry and merge it with an empty 1592 // entry. 1593 for (ptr_const_iterator MI = Other.top_down_ptr_begin(), 1594 ME = Other.top_down_ptr_end(); MI != ME; ++MI) { 1595 std::pair<ptr_iterator, bool> Pair = PerPtrTopDown.insert(*MI); 1596 Pair.first->second.Merge(Pair.second ? PtrState() : MI->second, 1597 /*TopDown=*/true); 1598 } 1599 1600 // For each entry in our set, if the other set doesn't have an entry with the 1601 // same key, force it to merge with an empty entry. 1602 for (ptr_iterator MI = top_down_ptr_begin(), 1603 ME = top_down_ptr_end(); MI != ME; ++MI) 1604 if (Other.PerPtrTopDown.find(MI->first) == Other.PerPtrTopDown.end()) 1605 MI->second.Merge(PtrState(), /*TopDown=*/true); 1606} 1607 1608/// MergeSucc - The bottom-up traversal uses this to merge information about 1609/// successors to form the initial state for a new block. 1610void BBState::MergeSucc(const BBState &Other) { 1611 // Other.BottomUpPathCount can be 0, in which case it is either dead or a 1612 // loop backedge. Loop backedges are special. 1613 BottomUpPathCount += Other.BottomUpPathCount; 1614 1615 // For each entry in the other set, if our set has an entry with the 1616 // same key, merge the entries. Otherwise, copy the entry and merge 1617 // it with an empty entry. 1618 for (ptr_const_iterator MI = Other.bottom_up_ptr_begin(), 1619 ME = Other.bottom_up_ptr_end(); MI != ME; ++MI) { 1620 std::pair<ptr_iterator, bool> Pair = PerPtrBottomUp.insert(*MI); 1621 Pair.first->second.Merge(Pair.second ? PtrState() : MI->second, 1622 /*TopDown=*/false); 1623 } 1624 1625 // For each entry in our set, if the other set doesn't have an entry 1626 // with the same key, force it to merge with an empty entry. 1627 for (ptr_iterator MI = bottom_up_ptr_begin(), 1628 ME = bottom_up_ptr_end(); MI != ME; ++MI) 1629 if (Other.PerPtrBottomUp.find(MI->first) == Other.PerPtrBottomUp.end()) 1630 MI->second.Merge(PtrState(), /*TopDown=*/false); 1631} 1632 1633namespace { 1634 /// ObjCARCOpt - The main ARC optimization pass. 1635 class ObjCARCOpt : public FunctionPass { 1636 bool Changed; 1637 ProvenanceAnalysis PA; 1638 1639 /// Run - A flag indicating whether this optimization pass should run. 1640 bool Run; 1641 1642 /// RetainRVCallee, etc. - Declarations for ObjC runtime 1643 /// functions, for use in creating calls to them. These are initialized 1644 /// lazily to avoid cluttering up the Module with unused declarations. 1645 Constant *RetainRVCallee, *AutoreleaseRVCallee, *ReleaseCallee, 1646 *RetainCallee, *RetainBlockCallee, *AutoreleaseCallee; 1647 1648 /// UsedInThisFunciton - Flags which determine whether each of the 1649 /// interesting runtine functions is in fact used in the current function. 1650 unsigned UsedInThisFunction; 1651 1652 /// ImpreciseReleaseMDKind - The Metadata Kind for clang.imprecise_release 1653 /// metadata. 1654 unsigned ImpreciseReleaseMDKind; 1655 1656 /// CopyOnEscapeMDKind - The Metadata Kind for clang.arc.copy_on_escape 1657 /// metadata. 1658 unsigned CopyOnEscapeMDKind; 1659 1660 /// NoObjCARCExceptionsMDKind - The Metadata Kind for 1661 /// clang.arc.no_objc_arc_exceptions metadata. 1662 unsigned NoObjCARCExceptionsMDKind; 1663 1664 Constant *getRetainRVCallee(Module *M); 1665 Constant *getAutoreleaseRVCallee(Module *M); 1666 Constant *getReleaseCallee(Module *M); 1667 Constant *getRetainCallee(Module *M); 1668 Constant *getRetainBlockCallee(Module *M); 1669 Constant *getAutoreleaseCallee(Module *M); 1670 1671 bool IsRetainBlockOptimizable(const Instruction *Inst); 1672 1673 void OptimizeRetainCall(Function &F, Instruction *Retain); 1674 bool OptimizeRetainRVCall(Function &F, Instruction *RetainRV); 1675 void OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV); 1676 void OptimizeIndividualCalls(Function &F); 1677 1678 void CheckForCFGHazards(const BasicBlock *BB, 1679 DenseMap<const BasicBlock *, BBState> &BBStates, 1680 BBState &MyStates) const; 1681 bool VisitBottomUp(BasicBlock *BB, 1682 DenseMap<const BasicBlock *, BBState> &BBStates, 1683 MapVector<Value *, RRInfo> &Retains); 1684 bool VisitTopDown(BasicBlock *BB, 1685 DenseMap<const BasicBlock *, BBState> &BBStates, 1686 DenseMap<Value *, RRInfo> &Releases); 1687 bool Visit(Function &F, 1688 DenseMap<const BasicBlock *, BBState> &BBStates, 1689 MapVector<Value *, RRInfo> &Retains, 1690 DenseMap<Value *, RRInfo> &Releases); 1691 1692 void MoveCalls(Value *Arg, RRInfo &RetainsToMove, RRInfo &ReleasesToMove, 1693 MapVector<Value *, RRInfo> &Retains, 1694 DenseMap<Value *, RRInfo> &Releases, 1695 SmallVectorImpl<Instruction *> &DeadInsts, 1696 Module *M); 1697 1698 bool PerformCodePlacement(DenseMap<const BasicBlock *, BBState> &BBStates, 1699 MapVector<Value *, RRInfo> &Retains, 1700 DenseMap<Value *, RRInfo> &Releases, 1701 Module *M); 1702 1703 void OptimizeWeakCalls(Function &F); 1704 1705 bool OptimizeSequences(Function &F); 1706 1707 void OptimizeReturns(Function &F); 1708 1709 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 1710 virtual bool doInitialization(Module &M); 1711 virtual bool runOnFunction(Function &F); 1712 virtual void releaseMemory(); 1713 1714 public: 1715 static char ID; 1716 ObjCARCOpt() : FunctionPass(ID) { 1717 initializeObjCARCOptPass(*PassRegistry::getPassRegistry()); 1718 } 1719 }; 1720} 1721 1722char ObjCARCOpt::ID = 0; 1723INITIALIZE_PASS_BEGIN(ObjCARCOpt, 1724 "objc-arc", "ObjC ARC optimization", false, false) 1725INITIALIZE_PASS_DEPENDENCY(ObjCARCAliasAnalysis) 1726INITIALIZE_PASS_END(ObjCARCOpt, 1727 "objc-arc", "ObjC ARC optimization", false, false) 1728 1729Pass *llvm::createObjCARCOptPass() { 1730 return new ObjCARCOpt(); 1731} 1732 1733void ObjCARCOpt::getAnalysisUsage(AnalysisUsage &AU) const { 1734 AU.addRequired<ObjCARCAliasAnalysis>(); 1735 AU.addRequired<AliasAnalysis>(); 1736 // ARC optimization doesn't currently split critical edges. 1737 AU.setPreservesCFG(); 1738} 1739 1740bool ObjCARCOpt::IsRetainBlockOptimizable(const Instruction *Inst) { 1741 // Without the magic metadata tag, we have to assume this might be an 1742 // objc_retainBlock call inserted to convert a block pointer to an id, 1743 // in which case it really is needed. 1744 if (!Inst->getMetadata(CopyOnEscapeMDKind)) 1745 return false; 1746 1747 // If the pointer "escapes" (not including being used in a call), 1748 // the copy may be needed. 1749 if (DoesObjCBlockEscape(Inst)) 1750 return false; 1751 1752 // Otherwise, it's not needed. 1753 return true; 1754} 1755 1756Constant *ObjCARCOpt::getRetainRVCallee(Module *M) { 1757 if (!RetainRVCallee) { 1758 LLVMContext &C = M->getContext(); 1759 Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C)); 1760 std::vector<Type *> Params; 1761 Params.push_back(I8X); 1762 FunctionType *FTy = 1763 FunctionType::get(I8X, Params, /*isVarArg=*/false); 1764 AttrListPtr Attributes; 1765 Attributes.addAttr(~0u, Attribute::NoUnwind); 1766 RetainRVCallee = 1767 M->getOrInsertFunction("objc_retainAutoreleasedReturnValue", FTy, 1768 Attributes); 1769 } 1770 return RetainRVCallee; 1771} 1772 1773Constant *ObjCARCOpt::getAutoreleaseRVCallee(Module *M) { 1774 if (!AutoreleaseRVCallee) { 1775 LLVMContext &C = M->getContext(); 1776 Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C)); 1777 std::vector<Type *> Params; 1778 Params.push_back(I8X); 1779 FunctionType *FTy = 1780 FunctionType::get(I8X, Params, /*isVarArg=*/false); 1781 AttrListPtr Attributes; 1782 Attributes.addAttr(~0u, Attribute::NoUnwind); 1783 AutoreleaseRVCallee = 1784 M->getOrInsertFunction("objc_autoreleaseReturnValue", FTy, 1785 Attributes); 1786 } 1787 return AutoreleaseRVCallee; 1788} 1789 1790Constant *ObjCARCOpt::getReleaseCallee(Module *M) { 1791 if (!ReleaseCallee) { 1792 LLVMContext &C = M->getContext(); 1793 std::vector<Type *> Params; 1794 Params.push_back(PointerType::getUnqual(Type::getInt8Ty(C))); 1795 AttrListPtr Attributes; 1796 Attributes.addAttr(~0u, Attribute::NoUnwind); 1797 ReleaseCallee = 1798 M->getOrInsertFunction( 1799 "objc_release", 1800 FunctionType::get(Type::getVoidTy(C), Params, /*isVarArg=*/false), 1801 Attributes); 1802 } 1803 return ReleaseCallee; 1804} 1805 1806Constant *ObjCARCOpt::getRetainCallee(Module *M) { 1807 if (!RetainCallee) { 1808 LLVMContext &C = M->getContext(); 1809 std::vector<Type *> Params; 1810 Params.push_back(PointerType::getUnqual(Type::getInt8Ty(C))); 1811 AttrListPtr Attributes; 1812 Attributes.addAttr(~0u, Attribute::NoUnwind); 1813 RetainCallee = 1814 M->getOrInsertFunction( 1815 "objc_retain", 1816 FunctionType::get(Params[0], Params, /*isVarArg=*/false), 1817 Attributes); 1818 } 1819 return RetainCallee; 1820} 1821 1822Constant *ObjCARCOpt::getRetainBlockCallee(Module *M) { 1823 if (!RetainBlockCallee) { 1824 LLVMContext &C = M->getContext(); 1825 std::vector<Type *> Params; 1826 Params.push_back(PointerType::getUnqual(Type::getInt8Ty(C))); 1827 AttrListPtr Attributes; 1828 // objc_retainBlock is not nounwind because it calls user copy constructors 1829 // which could theoretically throw. 1830 RetainBlockCallee = 1831 M->getOrInsertFunction( 1832 "objc_retainBlock", 1833 FunctionType::get(Params[0], Params, /*isVarArg=*/false), 1834 Attributes); 1835 } 1836 return RetainBlockCallee; 1837} 1838 1839Constant *ObjCARCOpt::getAutoreleaseCallee(Module *M) { 1840 if (!AutoreleaseCallee) { 1841 LLVMContext &C = M->getContext(); 1842 std::vector<Type *> Params; 1843 Params.push_back(PointerType::getUnqual(Type::getInt8Ty(C))); 1844 AttrListPtr Attributes; 1845 Attributes.addAttr(~0u, Attribute::NoUnwind); 1846 AutoreleaseCallee = 1847 M->getOrInsertFunction( 1848 "objc_autorelease", 1849 FunctionType::get(Params[0], Params, /*isVarArg=*/false), 1850 Attributes); 1851 } 1852 return AutoreleaseCallee; 1853} 1854 1855/// CanAlterRefCount - Test whether the given instruction can result in a 1856/// reference count modification (positive or negative) for the pointer's 1857/// object. 1858static bool 1859CanAlterRefCount(const Instruction *Inst, const Value *Ptr, 1860 ProvenanceAnalysis &PA, InstructionClass Class) { 1861 switch (Class) { 1862 case IC_Autorelease: 1863 case IC_AutoreleaseRV: 1864 case IC_User: 1865 // These operations never directly modify a reference count. 1866 return false; 1867 default: break; 1868 } 1869 1870 ImmutableCallSite CS = static_cast<const Value *>(Inst); 1871 assert(CS && "Only calls can alter reference counts!"); 1872 1873 // See if AliasAnalysis can help us with the call. 1874 AliasAnalysis::ModRefBehavior MRB = PA.getAA()->getModRefBehavior(CS); 1875 if (AliasAnalysis::onlyReadsMemory(MRB)) 1876 return false; 1877 if (AliasAnalysis::onlyAccessesArgPointees(MRB)) { 1878 for (ImmutableCallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); 1879 I != E; ++I) { 1880 const Value *Op = *I; 1881 if (IsPotentialUse(Op) && PA.related(Ptr, Op)) 1882 return true; 1883 } 1884 return false; 1885 } 1886 1887 // Assume the worst. 1888 return true; 1889} 1890 1891/// CanUse - Test whether the given instruction can "use" the given pointer's 1892/// object in a way that requires the reference count to be positive. 1893static bool 1894CanUse(const Instruction *Inst, const Value *Ptr, ProvenanceAnalysis &PA, 1895 InstructionClass Class) { 1896 // IC_Call operations (as opposed to IC_CallOrUser) never "use" objc pointers. 1897 if (Class == IC_Call) 1898 return false; 1899 1900 // Consider various instructions which may have pointer arguments which are 1901 // not "uses". 1902 if (const ICmpInst *ICI = dyn_cast<ICmpInst>(Inst)) { 1903 // Comparing a pointer with null, or any other constant, isn't really a use, 1904 // because we don't care what the pointer points to, or about the values 1905 // of any other dynamic reference-counted pointers. 1906 if (!IsPotentialUse(ICI->getOperand(1))) 1907 return false; 1908 } else if (ImmutableCallSite CS = static_cast<const Value *>(Inst)) { 1909 // For calls, just check the arguments (and not the callee operand). 1910 for (ImmutableCallSite::arg_iterator OI = CS.arg_begin(), 1911 OE = CS.arg_end(); OI != OE; ++OI) { 1912 const Value *Op = *OI; 1913 if (IsPotentialUse(Op) && PA.related(Ptr, Op)) 1914 return true; 1915 } 1916 return false; 1917 } else if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 1918 // Special-case stores, because we don't care about the stored value, just 1919 // the store address. 1920 const Value *Op = GetUnderlyingObjCPtr(SI->getPointerOperand()); 1921 // If we can't tell what the underlying object was, assume there is a 1922 // dependence. 1923 return IsPotentialUse(Op) && PA.related(Op, Ptr); 1924 } 1925 1926 // Check each operand for a match. 1927 for (User::const_op_iterator OI = Inst->op_begin(), OE = Inst->op_end(); 1928 OI != OE; ++OI) { 1929 const Value *Op = *OI; 1930 if (IsPotentialUse(Op) && PA.related(Ptr, Op)) 1931 return true; 1932 } 1933 return false; 1934} 1935 1936/// CanInterruptRV - Test whether the given instruction can autorelease 1937/// any pointer or cause an autoreleasepool pop. 1938static bool 1939CanInterruptRV(InstructionClass Class) { 1940 switch (Class) { 1941 case IC_AutoreleasepoolPop: 1942 case IC_CallOrUser: 1943 case IC_Call: 1944 case IC_Autorelease: 1945 case IC_AutoreleaseRV: 1946 case IC_FusedRetainAutorelease: 1947 case IC_FusedRetainAutoreleaseRV: 1948 return true; 1949 default: 1950 return false; 1951 } 1952} 1953 1954namespace { 1955 /// DependenceKind - There are several kinds of dependence-like concepts in 1956 /// use here. 1957 enum DependenceKind { 1958 NeedsPositiveRetainCount, 1959 CanChangeRetainCount, 1960 RetainAutoreleaseDep, ///< Blocks objc_retainAutorelease. 1961 RetainAutoreleaseRVDep, ///< Blocks objc_retainAutoreleaseReturnValue. 1962 RetainRVDep ///< Blocks objc_retainAutoreleasedReturnValue. 1963 }; 1964} 1965 1966/// Depends - Test if there can be dependencies on Inst through Arg. This 1967/// function only tests dependencies relevant for removing pairs of calls. 1968static bool 1969Depends(DependenceKind Flavor, Instruction *Inst, const Value *Arg, 1970 ProvenanceAnalysis &PA) { 1971 // If we've reached the definition of Arg, stop. 1972 if (Inst == Arg) 1973 return true; 1974 1975 switch (Flavor) { 1976 case NeedsPositiveRetainCount: { 1977 InstructionClass Class = GetInstructionClass(Inst); 1978 switch (Class) { 1979 case IC_AutoreleasepoolPop: 1980 case IC_AutoreleasepoolPush: 1981 case IC_None: 1982 return false; 1983 default: 1984 return CanUse(Inst, Arg, PA, Class); 1985 } 1986 } 1987 1988 case CanChangeRetainCount: { 1989 InstructionClass Class = GetInstructionClass(Inst); 1990 switch (Class) { 1991 case IC_AutoreleasepoolPop: 1992 // Conservatively assume this can decrement any count. 1993 return true; 1994 case IC_AutoreleasepoolPush: 1995 case IC_None: 1996 return false; 1997 default: 1998 return CanAlterRefCount(Inst, Arg, PA, Class); 1999 } 2000 } 2001 2002 case RetainAutoreleaseDep: 2003 switch (GetBasicInstructionClass(Inst)) { 2004 case IC_AutoreleasepoolPop: 2005 // Don't merge an objc_autorelease with an objc_retain inside a different 2006 // autoreleasepool scope. 2007 return true; 2008 case IC_Retain: 2009 case IC_RetainRV: 2010 // Check for a retain of the same pointer for merging. 2011 return GetObjCArg(Inst) == Arg; 2012 default: 2013 // Nothing else matters for objc_retainAutorelease formation. 2014 return false; 2015 } 2016 2017 case RetainAutoreleaseRVDep: { 2018 InstructionClass Class = GetBasicInstructionClass(Inst); 2019 switch (Class) { 2020 case IC_Retain: 2021 case IC_RetainRV: 2022 // Check for a retain of the same pointer for merging. 2023 return GetObjCArg(Inst) == Arg; 2024 default: 2025 // Anything that can autorelease interrupts 2026 // retainAutoreleaseReturnValue formation. 2027 return CanInterruptRV(Class); 2028 } 2029 } 2030 2031 case RetainRVDep: 2032 return CanInterruptRV(GetBasicInstructionClass(Inst)); 2033 } 2034 2035 llvm_unreachable("Invalid dependence flavor"); 2036} 2037 2038/// FindDependencies - Walk up the CFG from StartPos (which is in StartBB) and 2039/// find local and non-local dependencies on Arg. 2040/// TODO: Cache results? 2041static void 2042FindDependencies(DependenceKind Flavor, 2043 const Value *Arg, 2044 BasicBlock *StartBB, Instruction *StartInst, 2045 SmallPtrSet<Instruction *, 4> &DependingInstructions, 2046 SmallPtrSet<const BasicBlock *, 4> &Visited, 2047 ProvenanceAnalysis &PA) { 2048 BasicBlock::iterator StartPos = StartInst; 2049 2050 SmallVector<std::pair<BasicBlock *, BasicBlock::iterator>, 4> Worklist; 2051 Worklist.push_back(std::make_pair(StartBB, StartPos)); 2052 do { 2053 std::pair<BasicBlock *, BasicBlock::iterator> Pair = 2054 Worklist.pop_back_val(); 2055 BasicBlock *LocalStartBB = Pair.first; 2056 BasicBlock::iterator LocalStartPos = Pair.second; 2057 BasicBlock::iterator StartBBBegin = LocalStartBB->begin(); 2058 for (;;) { 2059 if (LocalStartPos == StartBBBegin) { 2060 pred_iterator PI(LocalStartBB), PE(LocalStartBB, false); 2061 if (PI == PE) 2062 // If we've reached the function entry, produce a null dependence. 2063 DependingInstructions.insert(0); 2064 else 2065 // Add the predecessors to the worklist. 2066 do { 2067 BasicBlock *PredBB = *PI; 2068 if (Visited.insert(PredBB)) 2069 Worklist.push_back(std::make_pair(PredBB, PredBB->end())); 2070 } while (++PI != PE); 2071 break; 2072 } 2073 2074 Instruction *Inst = --LocalStartPos; 2075 if (Depends(Flavor, Inst, Arg, PA)) { 2076 DependingInstructions.insert(Inst); 2077 break; 2078 } 2079 } 2080 } while (!Worklist.empty()); 2081 2082 // Determine whether the original StartBB post-dominates all of the blocks we 2083 // visited. If not, insert a sentinal indicating that most optimizations are 2084 // not safe. 2085 for (SmallPtrSet<const BasicBlock *, 4>::const_iterator I = Visited.begin(), 2086 E = Visited.end(); I != E; ++I) { 2087 const BasicBlock *BB = *I; 2088 if (BB == StartBB) 2089 continue; 2090 const TerminatorInst *TI = cast<TerminatorInst>(&BB->back()); 2091 for (succ_const_iterator SI(TI), SE(TI, false); SI != SE; ++SI) { 2092 const BasicBlock *Succ = *SI; 2093 if (Succ != StartBB && !Visited.count(Succ)) { 2094 DependingInstructions.insert(reinterpret_cast<Instruction *>(-1)); 2095 return; 2096 } 2097 } 2098 } 2099} 2100 2101static bool isNullOrUndef(const Value *V) { 2102 return isa<ConstantPointerNull>(V) || isa<UndefValue>(V); 2103} 2104 2105static bool isNoopInstruction(const Instruction *I) { 2106 return isa<BitCastInst>(I) || 2107 (isa<GetElementPtrInst>(I) && 2108 cast<GetElementPtrInst>(I)->hasAllZeroIndices()); 2109} 2110 2111/// OptimizeRetainCall - Turn objc_retain into 2112/// objc_retainAutoreleasedReturnValue if the operand is a return value. 2113void 2114ObjCARCOpt::OptimizeRetainCall(Function &F, Instruction *Retain) { 2115 CallSite CS(GetObjCArg(Retain)); 2116 Instruction *Call = CS.getInstruction(); 2117 if (!Call) return; 2118 if (Call->getParent() != Retain->getParent()) return; 2119 2120 // Check that the call is next to the retain. 2121 BasicBlock::iterator I = Call; 2122 ++I; 2123 while (isNoopInstruction(I)) ++I; 2124 if (&*I != Retain) 2125 return; 2126 2127 // Turn it to an objc_retainAutoreleasedReturnValue.. 2128 Changed = true; 2129 ++NumPeeps; 2130 cast<CallInst>(Retain)->setCalledFunction(getRetainRVCallee(F.getParent())); 2131} 2132 2133/// OptimizeRetainRVCall - Turn objc_retainAutoreleasedReturnValue into 2134/// objc_retain if the operand is not a return value. Or, if it can be 2135/// paired with an objc_autoreleaseReturnValue, delete the pair and 2136/// return true. 2137bool 2138ObjCARCOpt::OptimizeRetainRVCall(Function &F, Instruction *RetainRV) { 2139 // Check for the argument being from an immediately preceding call. 2140 Value *Arg = GetObjCArg(RetainRV); 2141 CallSite CS(Arg); 2142 if (Instruction *Call = CS.getInstruction()) 2143 if (Call->getParent() == RetainRV->getParent()) { 2144 BasicBlock::iterator I = Call; 2145 ++I; 2146 while (isNoopInstruction(I)) ++I; 2147 if (&*I == RetainRV) 2148 return false; 2149 } 2150 2151 // Check for being preceded by an objc_autoreleaseReturnValue on the same 2152 // pointer. In this case, we can delete the pair. 2153 BasicBlock::iterator I = RetainRV, Begin = RetainRV->getParent()->begin(); 2154 if (I != Begin) { 2155 do --I; while (I != Begin && isNoopInstruction(I)); 2156 if (GetBasicInstructionClass(I) == IC_AutoreleaseRV && 2157 GetObjCArg(I) == Arg) { 2158 Changed = true; 2159 ++NumPeeps; 2160 EraseInstruction(I); 2161 EraseInstruction(RetainRV); 2162 return true; 2163 } 2164 } 2165 2166 // Turn it to a plain objc_retain. 2167 Changed = true; 2168 ++NumPeeps; 2169 cast<CallInst>(RetainRV)->setCalledFunction(getRetainCallee(F.getParent())); 2170 return false; 2171} 2172 2173/// OptimizeAutoreleaseRVCall - Turn objc_autoreleaseReturnValue into 2174/// objc_autorelease if the result is not used as a return value. 2175void 2176ObjCARCOpt::OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV) { 2177 // Check for a return of the pointer value. 2178 const Value *Ptr = GetObjCArg(AutoreleaseRV); 2179 SmallVector<const Value *, 2> Users; 2180 Users.push_back(Ptr); 2181 do { 2182 Ptr = Users.pop_back_val(); 2183 for (Value::const_use_iterator UI = Ptr->use_begin(), UE = Ptr->use_end(); 2184 UI != UE; ++UI) { 2185 const User *I = *UI; 2186 if (isa<ReturnInst>(I) || GetBasicInstructionClass(I) == IC_RetainRV) 2187 return; 2188 if (isa<BitCastInst>(I)) 2189 Users.push_back(I); 2190 } 2191 } while (!Users.empty()); 2192 2193 Changed = true; 2194 ++NumPeeps; 2195 cast<CallInst>(AutoreleaseRV)-> 2196 setCalledFunction(getAutoreleaseCallee(F.getParent())); 2197} 2198 2199/// OptimizeIndividualCalls - Visit each call, one at a time, and make 2200/// simplifications without doing any additional analysis. 2201void ObjCARCOpt::OptimizeIndividualCalls(Function &F) { 2202 // Reset all the flags in preparation for recomputing them. 2203 UsedInThisFunction = 0; 2204 2205 // Visit all objc_* calls in F. 2206 for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) { 2207 Instruction *Inst = &*I++; 2208 InstructionClass Class = GetBasicInstructionClass(Inst); 2209 2210 switch (Class) { 2211 default: break; 2212 2213 // Delete no-op casts. These function calls have special semantics, but 2214 // the semantics are entirely implemented via lowering in the front-end, 2215 // so by the time they reach the optimizer, they are just no-op calls 2216 // which return their argument. 2217 // 2218 // There are gray areas here, as the ability to cast reference-counted 2219 // pointers to raw void* and back allows code to break ARC assumptions, 2220 // however these are currently considered to be unimportant. 2221 case IC_NoopCast: 2222 Changed = true; 2223 ++NumNoops; 2224 EraseInstruction(Inst); 2225 continue; 2226 2227 // If the pointer-to-weak-pointer is null, it's undefined behavior. 2228 case IC_StoreWeak: 2229 case IC_LoadWeak: 2230 case IC_LoadWeakRetained: 2231 case IC_InitWeak: 2232 case IC_DestroyWeak: { 2233 CallInst *CI = cast<CallInst>(Inst); 2234 if (isNullOrUndef(CI->getArgOperand(0))) { 2235 Type *Ty = CI->getArgOperand(0)->getType(); 2236 new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()), 2237 Constant::getNullValue(Ty), 2238 CI); 2239 CI->replaceAllUsesWith(UndefValue::get(CI->getType())); 2240 CI->eraseFromParent(); 2241 continue; 2242 } 2243 break; 2244 } 2245 case IC_CopyWeak: 2246 case IC_MoveWeak: { 2247 CallInst *CI = cast<CallInst>(Inst); 2248 if (isNullOrUndef(CI->getArgOperand(0)) || 2249 isNullOrUndef(CI->getArgOperand(1))) { 2250 Type *Ty = CI->getArgOperand(0)->getType(); 2251 new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()), 2252 Constant::getNullValue(Ty), 2253 CI); 2254 CI->replaceAllUsesWith(UndefValue::get(CI->getType())); 2255 CI->eraseFromParent(); 2256 continue; 2257 } 2258 break; 2259 } 2260 case IC_Retain: 2261 OptimizeRetainCall(F, Inst); 2262 break; 2263 case IC_RetainRV: 2264 if (OptimizeRetainRVCall(F, Inst)) 2265 continue; 2266 break; 2267 case IC_AutoreleaseRV: 2268 OptimizeAutoreleaseRVCall(F, Inst); 2269 break; 2270 } 2271 2272 // objc_autorelease(x) -> objc_release(x) if x is otherwise unused. 2273 if (IsAutorelease(Class) && Inst->use_empty()) { 2274 CallInst *Call = cast<CallInst>(Inst); 2275 const Value *Arg = Call->getArgOperand(0); 2276 Arg = FindSingleUseIdentifiedObject(Arg); 2277 if (Arg) { 2278 Changed = true; 2279 ++NumAutoreleases; 2280 2281 // Create the declaration lazily. 2282 LLVMContext &C = Inst->getContext(); 2283 CallInst *NewCall = 2284 CallInst::Create(getReleaseCallee(F.getParent()), 2285 Call->getArgOperand(0), "", Call); 2286 NewCall->setMetadata(ImpreciseReleaseMDKind, 2287 MDNode::get(C, ArrayRef<Value *>())); 2288 EraseInstruction(Call); 2289 Inst = NewCall; 2290 Class = IC_Release; 2291 } 2292 } 2293 2294 // For functions which can never be passed stack arguments, add 2295 // a tail keyword. 2296 if (IsAlwaysTail(Class)) { 2297 Changed = true; 2298 cast<CallInst>(Inst)->setTailCall(); 2299 } 2300 2301 // Set nounwind as needed. 2302 if (IsNoThrow(Class)) { 2303 Changed = true; 2304 cast<CallInst>(Inst)->setDoesNotThrow(); 2305 } 2306 2307 if (!IsNoopOnNull(Class)) { 2308 UsedInThisFunction |= 1 << Class; 2309 continue; 2310 } 2311 2312 const Value *Arg = GetObjCArg(Inst); 2313 2314 // ARC calls with null are no-ops. Delete them. 2315 if (isNullOrUndef(Arg)) { 2316 Changed = true; 2317 ++NumNoops; 2318 EraseInstruction(Inst); 2319 continue; 2320 } 2321 2322 // Keep track of which of retain, release, autorelease, and retain_block 2323 // are actually present in this function. 2324 UsedInThisFunction |= 1 << Class; 2325 2326 // If Arg is a PHI, and one or more incoming values to the 2327 // PHI are null, and the call is control-equivalent to the PHI, and there 2328 // are no relevant side effects between the PHI and the call, the call 2329 // could be pushed up to just those paths with non-null incoming values. 2330 // For now, don't bother splitting critical edges for this. 2331 SmallVector<std::pair<Instruction *, const Value *>, 4> Worklist; 2332 Worklist.push_back(std::make_pair(Inst, Arg)); 2333 do { 2334 std::pair<Instruction *, const Value *> Pair = Worklist.pop_back_val(); 2335 Inst = Pair.first; 2336 Arg = Pair.second; 2337 2338 const PHINode *PN = dyn_cast<PHINode>(Arg); 2339 if (!PN) continue; 2340 2341 // Determine if the PHI has any null operands, or any incoming 2342 // critical edges. 2343 bool HasNull = false; 2344 bool HasCriticalEdges = false; 2345 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 2346 Value *Incoming = 2347 StripPointerCastsAndObjCCalls(PN->getIncomingValue(i)); 2348 if (isNullOrUndef(Incoming)) 2349 HasNull = true; 2350 else if (cast<TerminatorInst>(PN->getIncomingBlock(i)->back()) 2351 .getNumSuccessors() != 1) { 2352 HasCriticalEdges = true; 2353 break; 2354 } 2355 } 2356 // If we have null operands and no critical edges, optimize. 2357 if (!HasCriticalEdges && HasNull) { 2358 SmallPtrSet<Instruction *, 4> DependingInstructions; 2359 SmallPtrSet<const BasicBlock *, 4> Visited; 2360 2361 // Check that there is nothing that cares about the reference 2362 // count between the call and the phi. 2363 FindDependencies(NeedsPositiveRetainCount, Arg, 2364 Inst->getParent(), Inst, 2365 DependingInstructions, Visited, PA); 2366 if (DependingInstructions.size() == 1 && 2367 *DependingInstructions.begin() == PN) { 2368 Changed = true; 2369 ++NumPartialNoops; 2370 // Clone the call into each predecessor that has a non-null value. 2371 CallInst *CInst = cast<CallInst>(Inst); 2372 Type *ParamTy = CInst->getArgOperand(0)->getType(); 2373 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 2374 Value *Incoming = 2375 StripPointerCastsAndObjCCalls(PN->getIncomingValue(i)); 2376 if (!isNullOrUndef(Incoming)) { 2377 CallInst *Clone = cast<CallInst>(CInst->clone()); 2378 Value *Op = PN->getIncomingValue(i); 2379 Instruction *InsertPos = &PN->getIncomingBlock(i)->back(); 2380 if (Op->getType() != ParamTy) 2381 Op = new BitCastInst(Op, ParamTy, "", InsertPos); 2382 Clone->setArgOperand(0, Op); 2383 Clone->insertBefore(InsertPos); 2384 Worklist.push_back(std::make_pair(Clone, Incoming)); 2385 } 2386 } 2387 // Erase the original call. 2388 EraseInstruction(CInst); 2389 continue; 2390 } 2391 } 2392 } while (!Worklist.empty()); 2393 } 2394} 2395 2396/// CheckForCFGHazards - Check for critical edges, loop boundaries, irreducible 2397/// control flow, or other CFG structures where moving code across the edge 2398/// would result in it being executed more. 2399void 2400ObjCARCOpt::CheckForCFGHazards(const BasicBlock *BB, 2401 DenseMap<const BasicBlock *, BBState> &BBStates, 2402 BBState &MyStates) const { 2403 // If any top-down local-use or possible-dec has a succ which is earlier in 2404 // the sequence, forget it. 2405 for (BBState::ptr_iterator I = MyStates.top_down_ptr_begin(), 2406 E = MyStates.top_down_ptr_end(); I != E; ++I) 2407 switch (I->second.GetSeq()) { 2408 default: break; 2409 case S_Use: { 2410 const Value *Arg = I->first; 2411 const TerminatorInst *TI = cast<TerminatorInst>(&BB->back()); 2412 bool SomeSuccHasSame = false; 2413 bool AllSuccsHaveSame = true; 2414 PtrState &S = I->second; 2415 succ_const_iterator SI(TI), SE(TI, false); 2416 2417 // If the terminator is an invoke marked with the 2418 // clang.arc.no_objc_arc_exceptions metadata, the unwind edge can be 2419 // ignored, for ARC purposes. 2420 if (isa<InvokeInst>(TI) && TI->getMetadata(NoObjCARCExceptionsMDKind)) 2421 --SE; 2422 2423 for (; SI != SE; ++SI) { 2424 Sequence SuccSSeq = S_None; 2425 bool SuccSRRIKnownSafe = false; 2426 // If VisitBottomUp has visited this successor, take what we know about it. 2427 DenseMap<const BasicBlock *, BBState>::iterator BBI = BBStates.find(*SI); 2428 if (BBI != BBStates.end()) { 2429 const PtrState &SuccS = BBI->second.getPtrBottomUpState(Arg); 2430 SuccSSeq = SuccS.GetSeq(); 2431 SuccSRRIKnownSafe = SuccS.RRI.KnownSafe; 2432 } 2433 switch (SuccSSeq) { 2434 case S_None: 2435 case S_CanRelease: { 2436 if (!S.RRI.KnownSafe && !SuccSRRIKnownSafe) { 2437 S.ClearSequenceProgress(); 2438 break; 2439 } 2440 continue; 2441 } 2442 case S_Use: 2443 SomeSuccHasSame = true; 2444 break; 2445 case S_Stop: 2446 case S_Release: 2447 case S_MovableRelease: 2448 if (!S.RRI.KnownSafe && !SuccSRRIKnownSafe) 2449 AllSuccsHaveSame = false; 2450 break; 2451 case S_Retain: 2452 llvm_unreachable("bottom-up pointer in retain state!"); 2453 } 2454 } 2455 // If the state at the other end of any of the successor edges 2456 // matches the current state, require all edges to match. This 2457 // guards against loops in the middle of a sequence. 2458 if (SomeSuccHasSame && !AllSuccsHaveSame) 2459 S.ClearSequenceProgress(); 2460 break; 2461 } 2462 case S_CanRelease: { 2463 const Value *Arg = I->first; 2464 const TerminatorInst *TI = cast<TerminatorInst>(&BB->back()); 2465 bool SomeSuccHasSame = false; 2466 bool AllSuccsHaveSame = true; 2467 PtrState &S = I->second; 2468 succ_const_iterator SI(TI), SE(TI, false); 2469 2470 // If the terminator is an invoke marked with the 2471 // clang.arc.no_objc_arc_exceptions metadata, the unwind edge can be 2472 // ignored, for ARC purposes. 2473 if (isa<InvokeInst>(TI) && TI->getMetadata(NoObjCARCExceptionsMDKind)) 2474 --SE; 2475 2476 for (; SI != SE; ++SI) { 2477 Sequence SuccSSeq = S_None; 2478 bool SuccSRRIKnownSafe = false; 2479 // If VisitBottomUp has visited this successor, take what we know about it. 2480 DenseMap<const BasicBlock *, BBState>::iterator BBI = BBStates.find(*SI); 2481 if (BBI != BBStates.end()) { 2482 const PtrState &SuccS = BBI->second.getPtrBottomUpState(Arg); 2483 SuccSSeq = SuccS.GetSeq(); 2484 SuccSRRIKnownSafe = SuccS.RRI.KnownSafe; 2485 } 2486 switch (SuccSSeq) { 2487 case S_None: { 2488 if (!S.RRI.KnownSafe && !SuccSRRIKnownSafe) { 2489 S.ClearSequenceProgress(); 2490 break; 2491 } 2492 continue; 2493 } 2494 case S_CanRelease: 2495 SomeSuccHasSame = true; 2496 break; 2497 case S_Stop: 2498 case S_Release: 2499 case S_MovableRelease: 2500 case S_Use: 2501 if (!S.RRI.KnownSafe && !SuccSRRIKnownSafe) 2502 AllSuccsHaveSame = false; 2503 break; 2504 case S_Retain: 2505 llvm_unreachable("bottom-up pointer in retain state!"); 2506 } 2507 } 2508 // If the state at the other end of any of the successor edges 2509 // matches the current state, require all edges to match. This 2510 // guards against loops in the middle of a sequence. 2511 if (SomeSuccHasSame && !AllSuccsHaveSame) 2512 S.ClearSequenceProgress(); 2513 break; 2514 } 2515 } 2516} 2517 2518bool 2519ObjCARCOpt::VisitBottomUp(BasicBlock *BB, 2520 DenseMap<const BasicBlock *, BBState> &BBStates, 2521 MapVector<Value *, RRInfo> &Retains) { 2522 bool NestingDetected = false; 2523 BBState &MyStates = BBStates[BB]; 2524 2525 // Merge the states from each successor to compute the initial state 2526 // for the current block. 2527 const TerminatorInst *TI = cast<TerminatorInst>(&BB->back()); 2528 succ_const_iterator SI(TI), SE(TI, false); 2529 if (SI == SE) 2530 MyStates.SetAsExit(); 2531 else { 2532 // If the terminator is an invoke marked with the 2533 // clang.arc.no_objc_arc_exceptions metadata, the unwind edge can be 2534 // ignored, for ARC purposes. 2535 if (isa<InvokeInst>(TI) && TI->getMetadata(NoObjCARCExceptionsMDKind)) 2536 --SE; 2537 2538 do { 2539 const BasicBlock *Succ = *SI++; 2540 if (Succ == BB) 2541 continue; 2542 DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Succ); 2543 // If we haven't seen this node yet, then we've found a CFG cycle. 2544 // Be optimistic here; it's CheckForCFGHazards' job detect trouble. 2545 if (I == BBStates.end()) 2546 continue; 2547 MyStates.InitFromSucc(I->second); 2548 while (SI != SE) { 2549 Succ = *SI++; 2550 if (Succ != BB) { 2551 I = BBStates.find(Succ); 2552 if (I != BBStates.end()) 2553 MyStates.MergeSucc(I->second); 2554 } 2555 } 2556 break; 2557 } while (SI != SE); 2558 } 2559 2560 // Visit all the instructions, bottom-up. 2561 for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; --I) { 2562 Instruction *Inst = llvm::prior(I); 2563 InstructionClass Class = GetInstructionClass(Inst); 2564 const Value *Arg = 0; 2565 2566 switch (Class) { 2567 case IC_Release: { 2568 Arg = GetObjCArg(Inst); 2569 2570 PtrState &S = MyStates.getPtrBottomUpState(Arg); 2571 2572 // If we see two releases in a row on the same pointer. If so, make 2573 // a note, and we'll cicle back to revisit it after we've 2574 // hopefully eliminated the second release, which may allow us to 2575 // eliminate the first release too. 2576 // Theoretically we could implement removal of nested retain+release 2577 // pairs by making PtrState hold a stack of states, but this is 2578 // simple and avoids adding overhead for the non-nested case. 2579 if (S.GetSeq() == S_Release || S.GetSeq() == S_MovableRelease) 2580 NestingDetected = true; 2581 2582 S.RRI.clear(); 2583 2584 MDNode *ReleaseMetadata = Inst->getMetadata(ImpreciseReleaseMDKind); 2585 S.SetSeq(ReleaseMetadata ? S_MovableRelease : S_Release); 2586 S.RRI.ReleaseMetadata = ReleaseMetadata; 2587 S.RRI.KnownSafe = S.IsKnownNested() || S.IsKnownIncremented(); 2588 S.RRI.IsTailCallRelease = cast<CallInst>(Inst)->isTailCall(); 2589 S.RRI.Calls.insert(Inst); 2590 2591 S.IncrementRefCount(); 2592 S.IncrementNestCount(); 2593 break; 2594 } 2595 case IC_RetainBlock: 2596 // An objc_retainBlock call with just a use may need to be kept, 2597 // because it may be copying a block from the stack to the heap. 2598 if (!IsRetainBlockOptimizable(Inst)) 2599 break; 2600 // FALLTHROUGH 2601 case IC_Retain: 2602 case IC_RetainRV: { 2603 Arg = GetObjCArg(Inst); 2604 2605 PtrState &S = MyStates.getPtrBottomUpState(Arg); 2606 S.DecrementRefCount(); 2607 S.SetAtLeastOneRefCount(); 2608 S.DecrementNestCount(); 2609 2610 switch (S.GetSeq()) { 2611 case S_Stop: 2612 case S_Release: 2613 case S_MovableRelease: 2614 case S_Use: 2615 S.RRI.ReverseInsertPts.clear(); 2616 // FALL THROUGH 2617 case S_CanRelease: 2618 // Don't do retain+release tracking for IC_RetainRV, because it's 2619 // better to let it remain as the first instruction after a call. 2620 if (Class != IC_RetainRV) { 2621 S.RRI.IsRetainBlock = Class == IC_RetainBlock; 2622 Retains[Inst] = S.RRI; 2623 } 2624 S.ClearSequenceProgress(); 2625 break; 2626 case S_None: 2627 break; 2628 case S_Retain: 2629 llvm_unreachable("bottom-up pointer in retain state!"); 2630 } 2631 continue; 2632 } 2633 case IC_AutoreleasepoolPop: 2634 // Conservatively, clear MyStates for all known pointers. 2635 MyStates.clearBottomUpPointers(); 2636 continue; 2637 case IC_AutoreleasepoolPush: 2638 case IC_None: 2639 // These are irrelevant. 2640 continue; 2641 default: 2642 break; 2643 } 2644 2645 // Consider any other possible effects of this instruction on each 2646 // pointer being tracked. 2647 for (BBState::ptr_iterator MI = MyStates.bottom_up_ptr_begin(), 2648 ME = MyStates.bottom_up_ptr_end(); MI != ME; ++MI) { 2649 const Value *Ptr = MI->first; 2650 if (Ptr == Arg) 2651 continue; // Handled above. 2652 PtrState &S = MI->second; 2653 Sequence Seq = S.GetSeq(); 2654 2655 // Check for possible releases. 2656 if (CanAlterRefCount(Inst, Ptr, PA, Class)) { 2657 S.DecrementRefCount(); 2658 switch (Seq) { 2659 case S_Use: 2660 S.SetSeq(S_CanRelease); 2661 continue; 2662 case S_CanRelease: 2663 case S_Release: 2664 case S_MovableRelease: 2665 case S_Stop: 2666 case S_None: 2667 break; 2668 case S_Retain: 2669 llvm_unreachable("bottom-up pointer in retain state!"); 2670 } 2671 } 2672 2673 // Check for possible direct uses. 2674 switch (Seq) { 2675 case S_Release: 2676 case S_MovableRelease: 2677 if (CanUse(Inst, Ptr, PA, Class)) { 2678 assert(S.RRI.ReverseInsertPts.empty()); 2679 S.RRI.ReverseInsertPts.insert(Inst); 2680 S.SetSeq(S_Use); 2681 } else if (Seq == S_Release && 2682 (Class == IC_User || Class == IC_CallOrUser)) { 2683 // Non-movable releases depend on any possible objc pointer use. 2684 S.SetSeq(S_Stop); 2685 assert(S.RRI.ReverseInsertPts.empty()); 2686 S.RRI.ReverseInsertPts.insert(Inst); 2687 } 2688 break; 2689 case S_Stop: 2690 if (CanUse(Inst, Ptr, PA, Class)) 2691 S.SetSeq(S_Use); 2692 break; 2693 case S_CanRelease: 2694 case S_Use: 2695 case S_None: 2696 break; 2697 case S_Retain: 2698 llvm_unreachable("bottom-up pointer in retain state!"); 2699 } 2700 } 2701 } 2702 2703 return NestingDetected; 2704} 2705 2706bool 2707ObjCARCOpt::VisitTopDown(BasicBlock *BB, 2708 DenseMap<const BasicBlock *, BBState> &BBStates, 2709 DenseMap<Value *, RRInfo> &Releases) { 2710 bool NestingDetected = false; 2711 BBState &MyStates = BBStates[BB]; 2712 2713 // Merge the states from each predecessor to compute the initial state 2714 // for the current block. 2715 const_pred_iterator PI(BB), PE(BB, false); 2716 if (PI == PE) 2717 MyStates.SetAsEntry(); 2718 else 2719 do { 2720 unsigned OperandNo = PI.getOperandNo(); 2721 const Use &Us = PI.getUse(); 2722 ++PI; 2723 2724 // Skip invoke unwind edges on invoke instructions marked with 2725 // clang.arc.no_objc_arc_exceptions. 2726 if (const InvokeInst *II = dyn_cast<InvokeInst>(Us.getUser())) 2727 if (OperandNo == II->getNumArgOperands() + 2 && 2728 II->getMetadata(NoObjCARCExceptionsMDKind)) 2729 continue; 2730 2731 const BasicBlock *Pred = cast<TerminatorInst>(Us.getUser())->getParent(); 2732 if (Pred == BB) 2733 continue; 2734 DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Pred); 2735 // If we haven't seen this node yet, then we've found a CFG cycle. 2736 // Be optimistic here; it's CheckForCFGHazards' job detect trouble. 2737 if (I == BBStates.end() || !I->second.isVisitedTopDown()) 2738 continue; 2739 MyStates.InitFromPred(I->second); 2740 while (PI != PE) { 2741 Pred = *PI++; 2742 if (Pred != BB) { 2743 I = BBStates.find(Pred); 2744 if (I != BBStates.end() && I->second.isVisitedTopDown()) 2745 MyStates.MergePred(I->second); 2746 } 2747 } 2748 break; 2749 } while (PI != PE); 2750 2751 // Visit all the instructions, top-down. 2752 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { 2753 Instruction *Inst = I; 2754 InstructionClass Class = GetInstructionClass(Inst); 2755 const Value *Arg = 0; 2756 2757 switch (Class) { 2758 case IC_RetainBlock: 2759 // An objc_retainBlock call with just a use may need to be kept, 2760 // because it may be copying a block from the stack to the heap. 2761 if (!IsRetainBlockOptimizable(Inst)) 2762 break; 2763 // FALLTHROUGH 2764 case IC_Retain: 2765 case IC_RetainRV: { 2766 Arg = GetObjCArg(Inst); 2767 2768 PtrState &S = MyStates.getPtrTopDownState(Arg); 2769 2770 // Don't do retain+release tracking for IC_RetainRV, because it's 2771 // better to let it remain as the first instruction after a call. 2772 if (Class != IC_RetainRV) { 2773 // If we see two retains in a row on the same pointer. If so, make 2774 // a note, and we'll cicle back to revisit it after we've 2775 // hopefully eliminated the second retain, which may allow us to 2776 // eliminate the first retain too. 2777 // Theoretically we could implement removal of nested retain+release 2778 // pairs by making PtrState hold a stack of states, but this is 2779 // simple and avoids adding overhead for the non-nested case. 2780 if (S.GetSeq() == S_Retain) 2781 NestingDetected = true; 2782 2783 S.SetSeq(S_Retain); 2784 S.RRI.clear(); 2785 S.RRI.IsRetainBlock = Class == IC_RetainBlock; 2786 // Don't check S.IsKnownIncremented() here because it's not 2787 // sufficient. 2788 S.RRI.KnownSafe = S.IsKnownNested(); 2789 S.RRI.Calls.insert(Inst); 2790 } 2791 2792 S.SetAtLeastOneRefCount(); 2793 S.IncrementRefCount(); 2794 S.IncrementNestCount(); 2795 continue; 2796 } 2797 case IC_Release: { 2798 Arg = GetObjCArg(Inst); 2799 2800 PtrState &S = MyStates.getPtrTopDownState(Arg); 2801 S.DecrementRefCount(); 2802 S.DecrementNestCount(); 2803 2804 switch (S.GetSeq()) { 2805 case S_Retain: 2806 case S_CanRelease: 2807 S.RRI.ReverseInsertPts.clear(); 2808 // FALL THROUGH 2809 case S_Use: 2810 S.RRI.ReleaseMetadata = Inst->getMetadata(ImpreciseReleaseMDKind); 2811 S.RRI.IsTailCallRelease = cast<CallInst>(Inst)->isTailCall(); 2812 Releases[Inst] = S.RRI; 2813 S.ClearSequenceProgress(); 2814 break; 2815 case S_None: 2816 break; 2817 case S_Stop: 2818 case S_Release: 2819 case S_MovableRelease: 2820 llvm_unreachable("top-down pointer in release state!"); 2821 } 2822 break; 2823 } 2824 case IC_AutoreleasepoolPop: 2825 // Conservatively, clear MyStates for all known pointers. 2826 MyStates.clearTopDownPointers(); 2827 continue; 2828 case IC_AutoreleasepoolPush: 2829 case IC_None: 2830 // These are irrelevant. 2831 continue; 2832 default: 2833 break; 2834 } 2835 2836 // Consider any other possible effects of this instruction on each 2837 // pointer being tracked. 2838 for (BBState::ptr_iterator MI = MyStates.top_down_ptr_begin(), 2839 ME = MyStates.top_down_ptr_end(); MI != ME; ++MI) { 2840 const Value *Ptr = MI->first; 2841 if (Ptr == Arg) 2842 continue; // Handled above. 2843 PtrState &S = MI->second; 2844 Sequence Seq = S.GetSeq(); 2845 2846 // Check for possible releases. 2847 if (CanAlterRefCount(Inst, Ptr, PA, Class)) { 2848 S.DecrementRefCount(); 2849 switch (Seq) { 2850 case S_Retain: 2851 S.SetSeq(S_CanRelease); 2852 assert(S.RRI.ReverseInsertPts.empty()); 2853 S.RRI.ReverseInsertPts.insert(Inst); 2854 2855 // One call can't cause a transition from S_Retain to S_CanRelease 2856 // and S_CanRelease to S_Use. If we've made the first transition, 2857 // we're done. 2858 continue; 2859 case S_Use: 2860 case S_CanRelease: 2861 case S_None: 2862 break; 2863 case S_Stop: 2864 case S_Release: 2865 case S_MovableRelease: 2866 llvm_unreachable("top-down pointer in release state!"); 2867 } 2868 } 2869 2870 // Check for possible direct uses. 2871 switch (Seq) { 2872 case S_CanRelease: 2873 if (CanUse(Inst, Ptr, PA, Class)) 2874 S.SetSeq(S_Use); 2875 break; 2876 case S_Retain: 2877 case S_Use: 2878 case S_None: 2879 break; 2880 case S_Stop: 2881 case S_Release: 2882 case S_MovableRelease: 2883 llvm_unreachable("top-down pointer in release state!"); 2884 } 2885 } 2886 } 2887 2888 CheckForCFGHazards(BB, BBStates, MyStates); 2889 return NestingDetected; 2890} 2891 2892static void 2893ComputePostOrders(Function &F, 2894 SmallVectorImpl<BasicBlock *> &PostOrder, 2895 SmallVectorImpl<BasicBlock *> &ReverseCFGPostOrder) { 2896 /// Backedges - Backedges detected in the DFS. These edges will be 2897 /// ignored in the reverse-CFG DFS, so that loops with multiple exits will be 2898 /// traversed in the desired order. 2899 DenseSet<std::pair<BasicBlock *, BasicBlock *> > Backedges; 2900 2901 /// Visited - The visited set, for doing DFS walks. 2902 SmallPtrSet<BasicBlock *, 16> Visited; 2903 2904 // Do DFS, computing the PostOrder. 2905 SmallPtrSet<BasicBlock *, 16> OnStack; 2906 SmallVector<std::pair<BasicBlock *, succ_iterator>, 16> SuccStack; 2907 BasicBlock *EntryBB = &F.getEntryBlock(); 2908 SuccStack.push_back(std::make_pair(EntryBB, succ_begin(EntryBB))); 2909 Visited.insert(EntryBB); 2910 OnStack.insert(EntryBB); 2911 do { 2912 dfs_next_succ: 2913 TerminatorInst *TI = cast<TerminatorInst>(&SuccStack.back().first->back()); 2914 succ_iterator End = succ_iterator(TI, true); 2915 while (SuccStack.back().second != End) { 2916 BasicBlock *BB = *SuccStack.back().second++; 2917 if (Visited.insert(BB)) { 2918 SuccStack.push_back(std::make_pair(BB, succ_begin(BB))); 2919 OnStack.insert(BB); 2920 goto dfs_next_succ; 2921 } 2922 if (OnStack.count(BB)) 2923 Backedges.insert(std::make_pair(SuccStack.back().first, BB)); 2924 } 2925 OnStack.erase(SuccStack.back().first); 2926 PostOrder.push_back(SuccStack.pop_back_val().first); 2927 } while (!SuccStack.empty()); 2928 2929 Visited.clear(); 2930 2931 // Compute the exits, which are the starting points for reverse-CFG DFS. 2932 // This includes blocks where all the successors are backedges that 2933 // we're skipping. 2934 SmallVector<BasicBlock *, 4> Exits; 2935 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) { 2936 BasicBlock *BB = I; 2937 TerminatorInst *TI = cast<TerminatorInst>(&BB->back()); 2938 for (succ_iterator SI(TI), SE(TI, true); SI != SE; ++SI) 2939 if (!Backedges.count(std::make_pair(BB, *SI))) 2940 goto HasNonBackedgeSucc; 2941 Exits.push_back(BB); 2942 HasNonBackedgeSucc:; 2943 } 2944 2945 // Do reverse-CFG DFS, computing the reverse-CFG PostOrder. 2946 SmallVector<std::pair<BasicBlock *, pred_iterator>, 16> PredStack; 2947 for (SmallVectorImpl<BasicBlock *>::iterator I = Exits.begin(), E = Exits.end(); 2948 I != E; ++I) { 2949 BasicBlock *ExitBB = *I; 2950 PredStack.push_back(std::make_pair(ExitBB, pred_begin(ExitBB))); 2951 Visited.insert(ExitBB); 2952 while (!PredStack.empty()) { 2953 reverse_dfs_next_succ: 2954 pred_iterator End = pred_end(PredStack.back().first); 2955 while (PredStack.back().second != End) { 2956 BasicBlock *BB = *PredStack.back().second++; 2957 // Skip backedges detected in the forward-CFG DFS. 2958 if (Backedges.count(std::make_pair(BB, PredStack.back().first))) 2959 continue; 2960 if (Visited.insert(BB)) { 2961 PredStack.push_back(std::make_pair(BB, pred_begin(BB))); 2962 goto reverse_dfs_next_succ; 2963 } 2964 } 2965 ReverseCFGPostOrder.push_back(PredStack.pop_back_val().first); 2966 } 2967 } 2968} 2969 2970// Visit - Visit the function both top-down and bottom-up. 2971bool 2972ObjCARCOpt::Visit(Function &F, 2973 DenseMap<const BasicBlock *, BBState> &BBStates, 2974 MapVector<Value *, RRInfo> &Retains, 2975 DenseMap<Value *, RRInfo> &Releases) { 2976 2977 // Use reverse-postorder traversals, because we magically know that loops 2978 // will be well behaved, i.e. they won't repeatedly call retain on a single 2979 // pointer without doing a release. We can't use the ReversePostOrderTraversal 2980 // class here because we want the reverse-CFG postorder to consider each 2981 // function exit point, and we want to ignore selected cycle edges. 2982 SmallVector<BasicBlock *, 16> PostOrder; 2983 SmallVector<BasicBlock *, 16> ReverseCFGPostOrder; 2984 ComputePostOrders(F, PostOrder, ReverseCFGPostOrder); 2985 2986 // Use reverse-postorder on the reverse CFG for bottom-up. 2987 bool BottomUpNestingDetected = false; 2988 for (SmallVectorImpl<BasicBlock *>::const_reverse_iterator I = 2989 ReverseCFGPostOrder.rbegin(), E = ReverseCFGPostOrder.rend(); 2990 I != E; ++I) 2991 BottomUpNestingDetected |= VisitBottomUp(*I, BBStates, Retains); 2992 2993 // Use reverse-postorder for top-down. 2994 bool TopDownNestingDetected = false; 2995 for (SmallVectorImpl<BasicBlock *>::const_reverse_iterator I = 2996 PostOrder.rbegin(), E = PostOrder.rend(); 2997 I != E; ++I) 2998 TopDownNestingDetected |= VisitTopDown(*I, BBStates, Releases); 2999 3000 return TopDownNestingDetected && BottomUpNestingDetected; 3001} 3002 3003/// MoveCalls - Move the calls in RetainsToMove and ReleasesToMove. 3004void ObjCARCOpt::MoveCalls(Value *Arg, 3005 RRInfo &RetainsToMove, 3006 RRInfo &ReleasesToMove, 3007 MapVector<Value *, RRInfo> &Retains, 3008 DenseMap<Value *, RRInfo> &Releases, 3009 SmallVectorImpl<Instruction *> &DeadInsts, 3010 Module *M) { 3011 Type *ArgTy = Arg->getType(); 3012 Type *ParamTy = PointerType::getUnqual(Type::getInt8Ty(ArgTy->getContext())); 3013 3014 // Insert the new retain and release calls. 3015 for (SmallPtrSet<Instruction *, 2>::const_iterator 3016 PI = ReleasesToMove.ReverseInsertPts.begin(), 3017 PE = ReleasesToMove.ReverseInsertPts.end(); PI != PE; ++PI) { 3018 Instruction *InsertPt = *PI; 3019 Value *MyArg = ArgTy == ParamTy ? Arg : 3020 new BitCastInst(Arg, ParamTy, "", InsertPt); 3021 CallInst *Call = 3022 CallInst::Create(RetainsToMove.IsRetainBlock ? 3023 getRetainBlockCallee(M) : getRetainCallee(M), 3024 MyArg, "", InsertPt); 3025 Call->setDoesNotThrow(); 3026 if (RetainsToMove.IsRetainBlock) 3027 Call->setMetadata(CopyOnEscapeMDKind, 3028 MDNode::get(M->getContext(), ArrayRef<Value *>())); 3029 else 3030 Call->setTailCall(); 3031 } 3032 for (SmallPtrSet<Instruction *, 2>::const_iterator 3033 PI = RetainsToMove.ReverseInsertPts.begin(), 3034 PE = RetainsToMove.ReverseInsertPts.end(); PI != PE; ++PI) { 3035 Instruction *LastUse = *PI; 3036 Instruction *InsertPts[] = { 0, 0, 0 }; 3037 if (InvokeInst *II = dyn_cast<InvokeInst>(LastUse)) { 3038 // We can't insert code immediately after an invoke instruction, so 3039 // insert code at the beginning of both successor blocks instead. 3040 // The invoke's return value isn't available in the unwind block, 3041 // but our releases will never depend on it, because they must be 3042 // paired with retains from before the invoke. 3043 InsertPts[0] = II->getNormalDest()->getFirstInsertionPt(); 3044 if (!II->getMetadata(NoObjCARCExceptionsMDKind)) 3045 InsertPts[1] = II->getUnwindDest()->getFirstInsertionPt(); 3046 } else { 3047 // Insert code immediately after the last use. 3048 InsertPts[0] = llvm::next(BasicBlock::iterator(LastUse)); 3049 } 3050 3051 for (Instruction **I = InsertPts; *I; ++I) { 3052 Instruction *InsertPt = *I; 3053 Value *MyArg = ArgTy == ParamTy ? Arg : 3054 new BitCastInst(Arg, ParamTy, "", InsertPt); 3055 CallInst *Call = CallInst::Create(getReleaseCallee(M), MyArg, 3056 "", InsertPt); 3057 // Attach a clang.imprecise_release metadata tag, if appropriate. 3058 if (MDNode *M = ReleasesToMove.ReleaseMetadata) 3059 Call->setMetadata(ImpreciseReleaseMDKind, M); 3060 Call->setDoesNotThrow(); 3061 if (ReleasesToMove.IsTailCallRelease) 3062 Call->setTailCall(); 3063 } 3064 } 3065 3066 // Delete the original retain and release calls. 3067 for (SmallPtrSet<Instruction *, 2>::const_iterator 3068 AI = RetainsToMove.Calls.begin(), 3069 AE = RetainsToMove.Calls.end(); AI != AE; ++AI) { 3070 Instruction *OrigRetain = *AI; 3071 Retains.blot(OrigRetain); 3072 DeadInsts.push_back(OrigRetain); 3073 } 3074 for (SmallPtrSet<Instruction *, 2>::const_iterator 3075 AI = ReleasesToMove.Calls.begin(), 3076 AE = ReleasesToMove.Calls.end(); AI != AE; ++AI) { 3077 Instruction *OrigRelease = *AI; 3078 Releases.erase(OrigRelease); 3079 DeadInsts.push_back(OrigRelease); 3080 } 3081} 3082 3083bool 3084ObjCARCOpt::PerformCodePlacement(DenseMap<const BasicBlock *, BBState> 3085 &BBStates, 3086 MapVector<Value *, RRInfo> &Retains, 3087 DenseMap<Value *, RRInfo> &Releases, 3088 Module *M) { 3089 bool AnyPairsCompletelyEliminated = false; 3090 RRInfo RetainsToMove; 3091 RRInfo ReleasesToMove; 3092 SmallVector<Instruction *, 4> NewRetains; 3093 SmallVector<Instruction *, 4> NewReleases; 3094 SmallVector<Instruction *, 8> DeadInsts; 3095 3096 for (MapVector<Value *, RRInfo>::const_iterator I = Retains.begin(), 3097 E = Retains.end(); I != E; ++I) { 3098 Value *V = I->first; 3099 if (!V) continue; // blotted 3100 3101 Instruction *Retain = cast<Instruction>(V); 3102 Value *Arg = GetObjCArg(Retain); 3103 3104 // If the object being released is in static or stack storage, we know it's 3105 // not being managed by ObjC reference counting, so we can delete pairs 3106 // regardless of what possible decrements or uses lie between them. 3107 bool KnownSafe = isa<Constant>(Arg) || isa<AllocaInst>(Arg); 3108 3109 // A constant pointer can't be pointing to an object on the heap. It may 3110 // be reference-counted, but it won't be deleted. 3111 if (const LoadInst *LI = dyn_cast<LoadInst>(Arg)) 3112 if (const GlobalVariable *GV = 3113 dyn_cast<GlobalVariable>( 3114 StripPointerCastsAndObjCCalls(LI->getPointerOperand()))) 3115 if (GV->isConstant()) 3116 KnownSafe = true; 3117 3118 // If a pair happens in a region where it is known that the reference count 3119 // is already incremented, we can similarly ignore possible decrements. 3120 bool KnownSafeTD = true, KnownSafeBU = true; 3121 3122 // Connect the dots between the top-down-collected RetainsToMove and 3123 // bottom-up-collected ReleasesToMove to form sets of related calls. 3124 // This is an iterative process so that we connect multiple releases 3125 // to multiple retains if needed. 3126 unsigned OldDelta = 0; 3127 unsigned NewDelta = 0; 3128 unsigned OldCount = 0; 3129 unsigned NewCount = 0; 3130 bool FirstRelease = true; 3131 bool FirstRetain = true; 3132 NewRetains.push_back(Retain); 3133 for (;;) { 3134 for (SmallVectorImpl<Instruction *>::const_iterator 3135 NI = NewRetains.begin(), NE = NewRetains.end(); NI != NE; ++NI) { 3136 Instruction *NewRetain = *NI; 3137 MapVector<Value *, RRInfo>::const_iterator It = Retains.find(NewRetain); 3138 assert(It != Retains.end()); 3139 const RRInfo &NewRetainRRI = It->second; 3140 KnownSafeTD &= NewRetainRRI.KnownSafe; 3141 for (SmallPtrSet<Instruction *, 2>::const_iterator 3142 LI = NewRetainRRI.Calls.begin(), 3143 LE = NewRetainRRI.Calls.end(); LI != LE; ++LI) { 3144 Instruction *NewRetainRelease = *LI; 3145 DenseMap<Value *, RRInfo>::const_iterator Jt = 3146 Releases.find(NewRetainRelease); 3147 if (Jt == Releases.end()) 3148 goto next_retain; 3149 const RRInfo &NewRetainReleaseRRI = Jt->second; 3150 assert(NewRetainReleaseRRI.Calls.count(NewRetain)); 3151 if (ReleasesToMove.Calls.insert(NewRetainRelease)) { 3152 OldDelta -= 3153 BBStates[NewRetainRelease->getParent()].GetAllPathCount(); 3154 3155 // Merge the ReleaseMetadata and IsTailCallRelease values. 3156 if (FirstRelease) { 3157 ReleasesToMove.ReleaseMetadata = 3158 NewRetainReleaseRRI.ReleaseMetadata; 3159 ReleasesToMove.IsTailCallRelease = 3160 NewRetainReleaseRRI.IsTailCallRelease; 3161 FirstRelease = false; 3162 } else { 3163 if (ReleasesToMove.ReleaseMetadata != 3164 NewRetainReleaseRRI.ReleaseMetadata) 3165 ReleasesToMove.ReleaseMetadata = 0; 3166 if (ReleasesToMove.IsTailCallRelease != 3167 NewRetainReleaseRRI.IsTailCallRelease) 3168 ReleasesToMove.IsTailCallRelease = false; 3169 } 3170 3171 // Collect the optimal insertion points. 3172 if (!KnownSafe) 3173 for (SmallPtrSet<Instruction *, 2>::const_iterator 3174 RI = NewRetainReleaseRRI.ReverseInsertPts.begin(), 3175 RE = NewRetainReleaseRRI.ReverseInsertPts.end(); 3176 RI != RE; ++RI) { 3177 Instruction *RIP = *RI; 3178 if (ReleasesToMove.ReverseInsertPts.insert(RIP)) 3179 NewDelta -= BBStates[RIP->getParent()].GetAllPathCount(); 3180 } 3181 NewReleases.push_back(NewRetainRelease); 3182 } 3183 } 3184 } 3185 NewRetains.clear(); 3186 if (NewReleases.empty()) break; 3187 3188 // Back the other way. 3189 for (SmallVectorImpl<Instruction *>::const_iterator 3190 NI = NewReleases.begin(), NE = NewReleases.end(); NI != NE; ++NI) { 3191 Instruction *NewRelease = *NI; 3192 DenseMap<Value *, RRInfo>::const_iterator It = 3193 Releases.find(NewRelease); 3194 assert(It != Releases.end()); 3195 const RRInfo &NewReleaseRRI = It->second; 3196 KnownSafeBU &= NewReleaseRRI.KnownSafe; 3197 for (SmallPtrSet<Instruction *, 2>::const_iterator 3198 LI = NewReleaseRRI.Calls.begin(), 3199 LE = NewReleaseRRI.Calls.end(); LI != LE; ++LI) { 3200 Instruction *NewReleaseRetain = *LI; 3201 MapVector<Value *, RRInfo>::const_iterator Jt = 3202 Retains.find(NewReleaseRetain); 3203 if (Jt == Retains.end()) 3204 goto next_retain; 3205 const RRInfo &NewReleaseRetainRRI = Jt->second; 3206 assert(NewReleaseRetainRRI.Calls.count(NewRelease)); 3207 if (RetainsToMove.Calls.insert(NewReleaseRetain)) { 3208 unsigned PathCount = 3209 BBStates[NewReleaseRetain->getParent()].GetAllPathCount(); 3210 OldDelta += PathCount; 3211 OldCount += PathCount; 3212 3213 // Merge the IsRetainBlock values. 3214 if (FirstRetain) { 3215 RetainsToMove.IsRetainBlock = NewReleaseRetainRRI.IsRetainBlock; 3216 FirstRetain = false; 3217 } else if (ReleasesToMove.IsRetainBlock != 3218 NewReleaseRetainRRI.IsRetainBlock) 3219 // It's not possible to merge the sequences if one uses 3220 // objc_retain and the other uses objc_retainBlock. 3221 goto next_retain; 3222 3223 // Collect the optimal insertion points. 3224 if (!KnownSafe) 3225 for (SmallPtrSet<Instruction *, 2>::const_iterator 3226 RI = NewReleaseRetainRRI.ReverseInsertPts.begin(), 3227 RE = NewReleaseRetainRRI.ReverseInsertPts.end(); 3228 RI != RE; ++RI) { 3229 Instruction *RIP = *RI; 3230 if (RetainsToMove.ReverseInsertPts.insert(RIP)) { 3231 PathCount = BBStates[RIP->getParent()].GetAllPathCount(); 3232 NewDelta += PathCount; 3233 NewCount += PathCount; 3234 } 3235 } 3236 NewRetains.push_back(NewReleaseRetain); 3237 } 3238 } 3239 } 3240 NewReleases.clear(); 3241 if (NewRetains.empty()) break; 3242 } 3243 3244 // If the pointer is known incremented or nested, we can safely delete the 3245 // pair regardless of what's between them. 3246 if (KnownSafeTD || KnownSafeBU) { 3247 RetainsToMove.ReverseInsertPts.clear(); 3248 ReleasesToMove.ReverseInsertPts.clear(); 3249 NewCount = 0; 3250 } else { 3251 // Determine whether the new insertion points we computed preserve the 3252 // balance of retain and release calls through the program. 3253 // TODO: If the fully aggressive solution isn't valid, try to find a 3254 // less aggressive solution which is. 3255 if (NewDelta != 0) 3256 goto next_retain; 3257 } 3258 3259 // Determine whether the original call points are balanced in the retain and 3260 // release calls through the program. If not, conservatively don't touch 3261 // them. 3262 // TODO: It's theoretically possible to do code motion in this case, as 3263 // long as the existing imbalances are maintained. 3264 if (OldDelta != 0) 3265 goto next_retain; 3266 3267 // Ok, everything checks out and we're all set. Let's move some code! 3268 Changed = true; 3269 AnyPairsCompletelyEliminated = NewCount == 0; 3270 NumRRs += OldCount - NewCount; 3271 MoveCalls(Arg, RetainsToMove, ReleasesToMove, 3272 Retains, Releases, DeadInsts, M); 3273 3274 next_retain: 3275 NewReleases.clear(); 3276 NewRetains.clear(); 3277 RetainsToMove.clear(); 3278 ReleasesToMove.clear(); 3279 } 3280 3281 // Now that we're done moving everything, we can delete the newly dead 3282 // instructions, as we no longer need them as insert points. 3283 while (!DeadInsts.empty()) 3284 EraseInstruction(DeadInsts.pop_back_val()); 3285 3286 return AnyPairsCompletelyEliminated; 3287} 3288 3289/// OptimizeWeakCalls - Weak pointer optimizations. 3290void ObjCARCOpt::OptimizeWeakCalls(Function &F) { 3291 // First, do memdep-style RLE and S2L optimizations. We can't use memdep 3292 // itself because it uses AliasAnalysis and we need to do provenance 3293 // queries instead. 3294 for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) { 3295 Instruction *Inst = &*I++; 3296 InstructionClass Class = GetBasicInstructionClass(Inst); 3297 if (Class != IC_LoadWeak && Class != IC_LoadWeakRetained) 3298 continue; 3299 3300 // Delete objc_loadWeak calls with no users. 3301 if (Class == IC_LoadWeak && Inst->use_empty()) { 3302 Inst->eraseFromParent(); 3303 continue; 3304 } 3305 3306 // TODO: For now, just look for an earlier available version of this value 3307 // within the same block. Theoretically, we could do memdep-style non-local 3308 // analysis too, but that would want caching. A better approach would be to 3309 // use the technique that EarlyCSE uses. 3310 inst_iterator Current = llvm::prior(I); 3311 BasicBlock *CurrentBB = Current.getBasicBlockIterator(); 3312 for (BasicBlock::iterator B = CurrentBB->begin(), 3313 J = Current.getInstructionIterator(); 3314 J != B; --J) { 3315 Instruction *EarlierInst = &*llvm::prior(J); 3316 InstructionClass EarlierClass = GetInstructionClass(EarlierInst); 3317 switch (EarlierClass) { 3318 case IC_LoadWeak: 3319 case IC_LoadWeakRetained: { 3320 // If this is loading from the same pointer, replace this load's value 3321 // with that one. 3322 CallInst *Call = cast<CallInst>(Inst); 3323 CallInst *EarlierCall = cast<CallInst>(EarlierInst); 3324 Value *Arg = Call->getArgOperand(0); 3325 Value *EarlierArg = EarlierCall->getArgOperand(0); 3326 switch (PA.getAA()->alias(Arg, EarlierArg)) { 3327 case AliasAnalysis::MustAlias: 3328 Changed = true; 3329 // If the load has a builtin retain, insert a plain retain for it. 3330 if (Class == IC_LoadWeakRetained) { 3331 CallInst *CI = 3332 CallInst::Create(getRetainCallee(F.getParent()), EarlierCall, 3333 "", Call); 3334 CI->setTailCall(); 3335 } 3336 // Zap the fully redundant load. 3337 Call->replaceAllUsesWith(EarlierCall); 3338 Call->eraseFromParent(); 3339 goto clobbered; 3340 case AliasAnalysis::MayAlias: 3341 case AliasAnalysis::PartialAlias: 3342 goto clobbered; 3343 case AliasAnalysis::NoAlias: 3344 break; 3345 } 3346 break; 3347 } 3348 case IC_StoreWeak: 3349 case IC_InitWeak: { 3350 // If this is storing to the same pointer and has the same size etc. 3351 // replace this load's value with the stored value. 3352 CallInst *Call = cast<CallInst>(Inst); 3353 CallInst *EarlierCall = cast<CallInst>(EarlierInst); 3354 Value *Arg = Call->getArgOperand(0); 3355 Value *EarlierArg = EarlierCall->getArgOperand(0); 3356 switch (PA.getAA()->alias(Arg, EarlierArg)) { 3357 case AliasAnalysis::MustAlias: 3358 Changed = true; 3359 // If the load has a builtin retain, insert a plain retain for it. 3360 if (Class == IC_LoadWeakRetained) { 3361 CallInst *CI = 3362 CallInst::Create(getRetainCallee(F.getParent()), EarlierCall, 3363 "", Call); 3364 CI->setTailCall(); 3365 } 3366 // Zap the fully redundant load. 3367 Call->replaceAllUsesWith(EarlierCall->getArgOperand(1)); 3368 Call->eraseFromParent(); 3369 goto clobbered; 3370 case AliasAnalysis::MayAlias: 3371 case AliasAnalysis::PartialAlias: 3372 goto clobbered; 3373 case AliasAnalysis::NoAlias: 3374 break; 3375 } 3376 break; 3377 } 3378 case IC_MoveWeak: 3379 case IC_CopyWeak: 3380 // TOOD: Grab the copied value. 3381 goto clobbered; 3382 case IC_AutoreleasepoolPush: 3383 case IC_None: 3384 case IC_User: 3385 // Weak pointers are only modified through the weak entry points 3386 // (and arbitrary calls, which could call the weak entry points). 3387 break; 3388 default: 3389 // Anything else could modify the weak pointer. 3390 goto clobbered; 3391 } 3392 } 3393 clobbered:; 3394 } 3395 3396 // Then, for each destroyWeak with an alloca operand, check to see if 3397 // the alloca and all its users can be zapped. 3398 for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) { 3399 Instruction *Inst = &*I++; 3400 InstructionClass Class = GetBasicInstructionClass(Inst); 3401 if (Class != IC_DestroyWeak) 3402 continue; 3403 3404 CallInst *Call = cast<CallInst>(Inst); 3405 Value *Arg = Call->getArgOperand(0); 3406 if (AllocaInst *Alloca = dyn_cast<AllocaInst>(Arg)) { 3407 for (Value::use_iterator UI = Alloca->use_begin(), 3408 UE = Alloca->use_end(); UI != UE; ++UI) { 3409 Instruction *UserInst = cast<Instruction>(*UI); 3410 switch (GetBasicInstructionClass(UserInst)) { 3411 case IC_InitWeak: 3412 case IC_StoreWeak: 3413 case IC_DestroyWeak: 3414 continue; 3415 default: 3416 goto done; 3417 } 3418 } 3419 Changed = true; 3420 for (Value::use_iterator UI = Alloca->use_begin(), 3421 UE = Alloca->use_end(); UI != UE; ) { 3422 CallInst *UserInst = cast<CallInst>(*UI++); 3423 if (!UserInst->use_empty()) 3424 UserInst->replaceAllUsesWith(UserInst->getArgOperand(0)); 3425 UserInst->eraseFromParent(); 3426 } 3427 Alloca->eraseFromParent(); 3428 done:; 3429 } 3430 } 3431} 3432 3433/// OptimizeSequences - Identify program paths which execute sequences of 3434/// retains and releases which can be eliminated. 3435bool ObjCARCOpt::OptimizeSequences(Function &F) { 3436 /// Releases, Retains - These are used to store the results of the main flow 3437 /// analysis. These use Value* as the key instead of Instruction* so that the 3438 /// map stays valid when we get around to rewriting code and calls get 3439 /// replaced by arguments. 3440 DenseMap<Value *, RRInfo> Releases; 3441 MapVector<Value *, RRInfo> Retains; 3442 3443 /// BBStates, This is used during the traversal of the function to track the 3444 /// states for each identified object at each block. 3445 DenseMap<const BasicBlock *, BBState> BBStates; 3446 3447 // Analyze the CFG of the function, and all instructions. 3448 bool NestingDetected = Visit(F, BBStates, Retains, Releases); 3449 3450 // Transform. 3451 return PerformCodePlacement(BBStates, Retains, Releases, F.getParent()) && 3452 NestingDetected; 3453} 3454 3455/// OptimizeReturns - Look for this pattern: 3456/// 3457/// %call = call i8* @something(...) 3458/// %2 = call i8* @objc_retain(i8* %call) 3459/// %3 = call i8* @objc_autorelease(i8* %2) 3460/// ret i8* %3 3461/// 3462/// And delete the retain and autorelease. 3463/// 3464/// Otherwise if it's just this: 3465/// 3466/// %3 = call i8* @objc_autorelease(i8* %2) 3467/// ret i8* %3 3468/// 3469/// convert the autorelease to autoreleaseRV. 3470void ObjCARCOpt::OptimizeReturns(Function &F) { 3471 if (!F.getReturnType()->isPointerTy()) 3472 return; 3473 3474 SmallPtrSet<Instruction *, 4> DependingInstructions; 3475 SmallPtrSet<const BasicBlock *, 4> Visited; 3476 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) { 3477 BasicBlock *BB = FI; 3478 ReturnInst *Ret = dyn_cast<ReturnInst>(&BB->back()); 3479 if (!Ret) continue; 3480 3481 const Value *Arg = StripPointerCastsAndObjCCalls(Ret->getOperand(0)); 3482 FindDependencies(NeedsPositiveRetainCount, Arg, 3483 BB, Ret, DependingInstructions, Visited, PA); 3484 if (DependingInstructions.size() != 1) 3485 goto next_block; 3486 3487 { 3488 CallInst *Autorelease = 3489 dyn_cast_or_null<CallInst>(*DependingInstructions.begin()); 3490 if (!Autorelease) 3491 goto next_block; 3492 InstructionClass AutoreleaseClass = 3493 GetBasicInstructionClass(Autorelease); 3494 if (!IsAutorelease(AutoreleaseClass)) 3495 goto next_block; 3496 if (GetObjCArg(Autorelease) != Arg) 3497 goto next_block; 3498 3499 DependingInstructions.clear(); 3500 Visited.clear(); 3501 3502 // Check that there is nothing that can affect the reference 3503 // count between the autorelease and the retain. 3504 FindDependencies(CanChangeRetainCount, Arg, 3505 BB, Autorelease, DependingInstructions, Visited, PA); 3506 if (DependingInstructions.size() != 1) 3507 goto next_block; 3508 3509 { 3510 CallInst *Retain = 3511 dyn_cast_or_null<CallInst>(*DependingInstructions.begin()); 3512 3513 // Check that we found a retain with the same argument. 3514 if (!Retain || 3515 !IsRetain(GetBasicInstructionClass(Retain)) || 3516 GetObjCArg(Retain) != Arg) 3517 goto next_block; 3518 3519 DependingInstructions.clear(); 3520 Visited.clear(); 3521 3522 // Convert the autorelease to an autoreleaseRV, since it's 3523 // returning the value. 3524 if (AutoreleaseClass == IC_Autorelease) { 3525 Autorelease->setCalledFunction(getAutoreleaseRVCallee(F.getParent())); 3526 AutoreleaseClass = IC_AutoreleaseRV; 3527 } 3528 3529 // Check that there is nothing that can affect the reference 3530 // count between the retain and the call. 3531 // Note that Retain need not be in BB. 3532 FindDependencies(CanChangeRetainCount, Arg, Retain->getParent(), Retain, 3533 DependingInstructions, Visited, PA); 3534 if (DependingInstructions.size() != 1) 3535 goto next_block; 3536 3537 { 3538 CallInst *Call = 3539 dyn_cast_or_null<CallInst>(*DependingInstructions.begin()); 3540 3541 // Check that the pointer is the return value of the call. 3542 if (!Call || Arg != Call) 3543 goto next_block; 3544 3545 // Check that the call is a regular call. 3546 InstructionClass Class = GetBasicInstructionClass(Call); 3547 if (Class != IC_CallOrUser && Class != IC_Call) 3548 goto next_block; 3549 3550 // If so, we can zap the retain and autorelease. 3551 Changed = true; 3552 ++NumRets; 3553 EraseInstruction(Retain); 3554 EraseInstruction(Autorelease); 3555 } 3556 } 3557 } 3558 3559 next_block: 3560 DependingInstructions.clear(); 3561 Visited.clear(); 3562 } 3563} 3564 3565bool ObjCARCOpt::doInitialization(Module &M) { 3566 if (!EnableARCOpts) 3567 return false; 3568 3569 Run = ModuleHasARC(M); 3570 if (!Run) 3571 return false; 3572 3573 // Identify the imprecise release metadata kind. 3574 ImpreciseReleaseMDKind = 3575 M.getContext().getMDKindID("clang.imprecise_release"); 3576 CopyOnEscapeMDKind = 3577 M.getContext().getMDKindID("clang.arc.copy_on_escape"); 3578 NoObjCARCExceptionsMDKind = 3579 M.getContext().getMDKindID("clang.arc.no_objc_arc_exceptions"); 3580 3581 // Intuitively, objc_retain and others are nocapture, however in practice 3582 // they are not, because they return their argument value. And objc_release 3583 // calls finalizers. 3584 3585 // These are initialized lazily. 3586 RetainRVCallee = 0; 3587 AutoreleaseRVCallee = 0; 3588 ReleaseCallee = 0; 3589 RetainCallee = 0; 3590 RetainBlockCallee = 0; 3591 AutoreleaseCallee = 0; 3592 3593 return false; 3594} 3595 3596bool ObjCARCOpt::runOnFunction(Function &F) { 3597 if (!EnableARCOpts) 3598 return false; 3599 3600 // If nothing in the Module uses ARC, don't do anything. 3601 if (!Run) 3602 return false; 3603 3604 Changed = false; 3605 3606 PA.setAA(&getAnalysis<AliasAnalysis>()); 3607 3608 // This pass performs several distinct transformations. As a compile-time aid 3609 // when compiling code that isn't ObjC, skip these if the relevant ObjC 3610 // library functions aren't declared. 3611 3612 // Preliminary optimizations. This also computs UsedInThisFunction. 3613 OptimizeIndividualCalls(F); 3614 3615 // Optimizations for weak pointers. 3616 if (UsedInThisFunction & ((1 << IC_LoadWeak) | 3617 (1 << IC_LoadWeakRetained) | 3618 (1 << IC_StoreWeak) | 3619 (1 << IC_InitWeak) | 3620 (1 << IC_CopyWeak) | 3621 (1 << IC_MoveWeak) | 3622 (1 << IC_DestroyWeak))) 3623 OptimizeWeakCalls(F); 3624 3625 // Optimizations for retain+release pairs. 3626 if (UsedInThisFunction & ((1 << IC_Retain) | 3627 (1 << IC_RetainRV) | 3628 (1 << IC_RetainBlock))) 3629 if (UsedInThisFunction & (1 << IC_Release)) 3630 // Run OptimizeSequences until it either stops making changes or 3631 // no retain+release pair nesting is detected. 3632 while (OptimizeSequences(F)) {} 3633 3634 // Optimizations if objc_autorelease is used. 3635 if (UsedInThisFunction & 3636 ((1 << IC_Autorelease) | (1 << IC_AutoreleaseRV))) 3637 OptimizeReturns(F); 3638 3639 return Changed; 3640} 3641 3642void ObjCARCOpt::releaseMemory() { 3643 PA.clear(); 3644} 3645 3646//===----------------------------------------------------------------------===// 3647// ARC contraction. 3648//===----------------------------------------------------------------------===// 3649 3650// TODO: ObjCARCContract could insert PHI nodes when uses aren't 3651// dominated by single calls. 3652 3653#include "llvm/Operator.h" 3654#include "llvm/InlineAsm.h" 3655#include "llvm/Analysis/Dominators.h" 3656 3657STATISTIC(NumStoreStrongs, "Number objc_storeStrong calls formed"); 3658 3659namespace { 3660 /// ObjCARCContract - Late ARC optimizations. These change the IR in a way 3661 /// that makes it difficult to be analyzed by ObjCARCOpt, so it's run late. 3662 class ObjCARCContract : public FunctionPass { 3663 bool Changed; 3664 AliasAnalysis *AA; 3665 DominatorTree *DT; 3666 ProvenanceAnalysis PA; 3667 3668 /// Run - A flag indicating whether this optimization pass should run. 3669 bool Run; 3670 3671 /// StoreStrongCallee, etc. - Declarations for ObjC runtime 3672 /// functions, for use in creating calls to them. These are initialized 3673 /// lazily to avoid cluttering up the Module with unused declarations. 3674 Constant *StoreStrongCallee, 3675 *RetainAutoreleaseCallee, *RetainAutoreleaseRVCallee; 3676 3677 /// RetainRVMarker - The inline asm string to insert between calls and 3678 /// RetainRV calls to make the optimization work on targets which need it. 3679 const MDString *RetainRVMarker; 3680 3681 /// StoreStrongCalls - The set of inserted objc_storeStrong calls. If 3682 /// at the end of walking the function we have found no alloca 3683 /// instructions, these calls can be marked "tail". 3684 DenseSet<CallInst *> StoreStrongCalls; 3685 3686 Constant *getStoreStrongCallee(Module *M); 3687 Constant *getRetainAutoreleaseCallee(Module *M); 3688 Constant *getRetainAutoreleaseRVCallee(Module *M); 3689 3690 bool ContractAutorelease(Function &F, Instruction *Autorelease, 3691 InstructionClass Class, 3692 SmallPtrSet<Instruction *, 4> 3693 &DependingInstructions, 3694 SmallPtrSet<const BasicBlock *, 4> 3695 &Visited); 3696 3697 void ContractRelease(Instruction *Release, 3698 inst_iterator &Iter); 3699 3700 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 3701 virtual bool doInitialization(Module &M); 3702 virtual bool runOnFunction(Function &F); 3703 3704 public: 3705 static char ID; 3706 ObjCARCContract() : FunctionPass(ID) { 3707 initializeObjCARCContractPass(*PassRegistry::getPassRegistry()); 3708 } 3709 }; 3710} 3711 3712char ObjCARCContract::ID = 0; 3713INITIALIZE_PASS_BEGIN(ObjCARCContract, 3714 "objc-arc-contract", "ObjC ARC contraction", false, false) 3715INITIALIZE_AG_DEPENDENCY(AliasAnalysis) 3716INITIALIZE_PASS_DEPENDENCY(DominatorTree) 3717INITIALIZE_PASS_END(ObjCARCContract, 3718 "objc-arc-contract", "ObjC ARC contraction", false, false) 3719 3720Pass *llvm::createObjCARCContractPass() { 3721 return new ObjCARCContract(); 3722} 3723 3724void ObjCARCContract::getAnalysisUsage(AnalysisUsage &AU) const { 3725 AU.addRequired<AliasAnalysis>(); 3726 AU.addRequired<DominatorTree>(); 3727 AU.setPreservesCFG(); 3728} 3729 3730Constant *ObjCARCContract::getStoreStrongCallee(Module *M) { 3731 if (!StoreStrongCallee) { 3732 LLVMContext &C = M->getContext(); 3733 Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C)); 3734 Type *I8XX = PointerType::getUnqual(I8X); 3735 std::vector<Type *> Params; 3736 Params.push_back(I8XX); 3737 Params.push_back(I8X); 3738 3739 AttrListPtr Attributes; 3740 Attributes.addAttr(~0u, Attribute::NoUnwind); 3741 Attributes.addAttr(1, Attribute::NoCapture); 3742 3743 StoreStrongCallee = 3744 M->getOrInsertFunction( 3745 "objc_storeStrong", 3746 FunctionType::get(Type::getVoidTy(C), Params, /*isVarArg=*/false), 3747 Attributes); 3748 } 3749 return StoreStrongCallee; 3750} 3751 3752Constant *ObjCARCContract::getRetainAutoreleaseCallee(Module *M) { 3753 if (!RetainAutoreleaseCallee) { 3754 LLVMContext &C = M->getContext(); 3755 Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C)); 3756 std::vector<Type *> Params; 3757 Params.push_back(I8X); 3758 FunctionType *FTy = 3759 FunctionType::get(I8X, Params, /*isVarArg=*/false); 3760 AttrListPtr Attributes; 3761 Attributes.addAttr(~0u, Attribute::NoUnwind); 3762 RetainAutoreleaseCallee = 3763 M->getOrInsertFunction("objc_retainAutorelease", FTy, Attributes); 3764 } 3765 return RetainAutoreleaseCallee; 3766} 3767 3768Constant *ObjCARCContract::getRetainAutoreleaseRVCallee(Module *M) { 3769 if (!RetainAutoreleaseRVCallee) { 3770 LLVMContext &C = M->getContext(); 3771 Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C)); 3772 std::vector<Type *> Params; 3773 Params.push_back(I8X); 3774 FunctionType *FTy = 3775 FunctionType::get(I8X, Params, /*isVarArg=*/false); 3776 AttrListPtr Attributes; 3777 Attributes.addAttr(~0u, Attribute::NoUnwind); 3778 RetainAutoreleaseRVCallee = 3779 M->getOrInsertFunction("objc_retainAutoreleaseReturnValue", FTy, 3780 Attributes); 3781 } 3782 return RetainAutoreleaseRVCallee; 3783} 3784 3785/// ContractAutorelease - Merge an autorelease with a retain into a fused 3786/// call. 3787bool 3788ObjCARCContract::ContractAutorelease(Function &F, Instruction *Autorelease, 3789 InstructionClass Class, 3790 SmallPtrSet<Instruction *, 4> 3791 &DependingInstructions, 3792 SmallPtrSet<const BasicBlock *, 4> 3793 &Visited) { 3794 const Value *Arg = GetObjCArg(Autorelease); 3795 3796 // Check that there are no instructions between the retain and the autorelease 3797 // (such as an autorelease_pop) which may change the count. 3798 CallInst *Retain = 0; 3799 if (Class == IC_AutoreleaseRV) 3800 FindDependencies(RetainAutoreleaseRVDep, Arg, 3801 Autorelease->getParent(), Autorelease, 3802 DependingInstructions, Visited, PA); 3803 else 3804 FindDependencies(RetainAutoreleaseDep, Arg, 3805 Autorelease->getParent(), Autorelease, 3806 DependingInstructions, Visited, PA); 3807 3808 Visited.clear(); 3809 if (DependingInstructions.size() != 1) { 3810 DependingInstructions.clear(); 3811 return false; 3812 } 3813 3814 Retain = dyn_cast_or_null<CallInst>(*DependingInstructions.begin()); 3815 DependingInstructions.clear(); 3816 3817 if (!Retain || 3818 GetBasicInstructionClass(Retain) != IC_Retain || 3819 GetObjCArg(Retain) != Arg) 3820 return false; 3821 3822 Changed = true; 3823 ++NumPeeps; 3824 3825 if (Class == IC_AutoreleaseRV) 3826 Retain->setCalledFunction(getRetainAutoreleaseRVCallee(F.getParent())); 3827 else 3828 Retain->setCalledFunction(getRetainAutoreleaseCallee(F.getParent())); 3829 3830 EraseInstruction(Autorelease); 3831 return true; 3832} 3833 3834/// ContractRelease - Attempt to merge an objc_release with a store, load, and 3835/// objc_retain to form an objc_storeStrong. This can be a little tricky because 3836/// the instructions don't always appear in order, and there may be unrelated 3837/// intervening instructions. 3838void ObjCARCContract::ContractRelease(Instruction *Release, 3839 inst_iterator &Iter) { 3840 LoadInst *Load = dyn_cast<LoadInst>(GetObjCArg(Release)); 3841 if (!Load || !Load->isSimple()) return; 3842 3843 // For now, require everything to be in one basic block. 3844 BasicBlock *BB = Release->getParent(); 3845 if (Load->getParent() != BB) return; 3846 3847 // Walk down to find the store. 3848 BasicBlock::iterator I = Load, End = BB->end(); 3849 ++I; 3850 AliasAnalysis::Location Loc = AA->getLocation(Load); 3851 while (I != End && 3852 (&*I == Release || 3853 IsRetain(GetBasicInstructionClass(I)) || 3854 !(AA->getModRefInfo(I, Loc) & AliasAnalysis::Mod))) 3855 ++I; 3856 StoreInst *Store = dyn_cast<StoreInst>(I); 3857 if (!Store || !Store->isSimple()) return; 3858 if (Store->getPointerOperand() != Loc.Ptr) return; 3859 3860 Value *New = StripPointerCastsAndObjCCalls(Store->getValueOperand()); 3861 3862 // Walk up to find the retain. 3863 I = Store; 3864 BasicBlock::iterator Begin = BB->begin(); 3865 while (I != Begin && GetBasicInstructionClass(I) != IC_Retain) 3866 --I; 3867 Instruction *Retain = I; 3868 if (GetBasicInstructionClass(Retain) != IC_Retain) return; 3869 if (GetObjCArg(Retain) != New) return; 3870 3871 Changed = true; 3872 ++NumStoreStrongs; 3873 3874 LLVMContext &C = Release->getContext(); 3875 Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C)); 3876 Type *I8XX = PointerType::getUnqual(I8X); 3877 3878 Value *Args[] = { Load->getPointerOperand(), New }; 3879 if (Args[0]->getType() != I8XX) 3880 Args[0] = new BitCastInst(Args[0], I8XX, "", Store); 3881 if (Args[1]->getType() != I8X) 3882 Args[1] = new BitCastInst(Args[1], I8X, "", Store); 3883 CallInst *StoreStrong = 3884 CallInst::Create(getStoreStrongCallee(BB->getParent()->getParent()), 3885 Args, "", Store); 3886 StoreStrong->setDoesNotThrow(); 3887 StoreStrong->setDebugLoc(Store->getDebugLoc()); 3888 3889 // We can't set the tail flag yet, because we haven't yet determined 3890 // whether there are any escaping allocas. Remember this call, so that 3891 // we can set the tail flag once we know it's safe. 3892 StoreStrongCalls.insert(StoreStrong); 3893 3894 if (&*Iter == Store) ++Iter; 3895 Store->eraseFromParent(); 3896 Release->eraseFromParent(); 3897 EraseInstruction(Retain); 3898 if (Load->use_empty()) 3899 Load->eraseFromParent(); 3900} 3901 3902bool ObjCARCContract::doInitialization(Module &M) { 3903 Run = ModuleHasARC(M); 3904 if (!Run) 3905 return false; 3906 3907 // These are initialized lazily. 3908 StoreStrongCallee = 0; 3909 RetainAutoreleaseCallee = 0; 3910 RetainAutoreleaseRVCallee = 0; 3911 3912 // Initialize RetainRVMarker. 3913 RetainRVMarker = 0; 3914 if (NamedMDNode *NMD = 3915 M.getNamedMetadata("clang.arc.retainAutoreleasedReturnValueMarker")) 3916 if (NMD->getNumOperands() == 1) { 3917 const MDNode *N = NMD->getOperand(0); 3918 if (N->getNumOperands() == 1) 3919 if (const MDString *S = dyn_cast<MDString>(N->getOperand(0))) 3920 RetainRVMarker = S; 3921 } 3922 3923 return false; 3924} 3925 3926bool ObjCARCContract::runOnFunction(Function &F) { 3927 if (!EnableARCOpts) 3928 return false; 3929 3930 // If nothing in the Module uses ARC, don't do anything. 3931 if (!Run) 3932 return false; 3933 3934 Changed = false; 3935 AA = &getAnalysis<AliasAnalysis>(); 3936 DT = &getAnalysis<DominatorTree>(); 3937 3938 PA.setAA(&getAnalysis<AliasAnalysis>()); 3939 3940 // Track whether it's ok to mark objc_storeStrong calls with the "tail" 3941 // keyword. Be conservative if the function has variadic arguments. 3942 // It seems that functions which "return twice" are also unsafe for the 3943 // "tail" argument, because they are setjmp, which could need to 3944 // return to an earlier stack state. 3945 bool TailOkForStoreStrongs = !F.isVarArg() && !F.callsFunctionThatReturnsTwice(); 3946 3947 // For ObjC library calls which return their argument, replace uses of the 3948 // argument with uses of the call return value, if it dominates the use. This 3949 // reduces register pressure. 3950 SmallPtrSet<Instruction *, 4> DependingInstructions; 3951 SmallPtrSet<const BasicBlock *, 4> Visited; 3952 for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) { 3953 Instruction *Inst = &*I++; 3954 3955 // Only these library routines return their argument. In particular, 3956 // objc_retainBlock does not necessarily return its argument. 3957 InstructionClass Class = GetBasicInstructionClass(Inst); 3958 switch (Class) { 3959 case IC_Retain: 3960 case IC_FusedRetainAutorelease: 3961 case IC_FusedRetainAutoreleaseRV: 3962 break; 3963 case IC_Autorelease: 3964 case IC_AutoreleaseRV: 3965 if (ContractAutorelease(F, Inst, Class, DependingInstructions, Visited)) 3966 continue; 3967 break; 3968 case IC_RetainRV: { 3969 // If we're compiling for a target which needs a special inline-asm 3970 // marker to do the retainAutoreleasedReturnValue optimization, 3971 // insert it now. 3972 if (!RetainRVMarker) 3973 break; 3974 BasicBlock::iterator BBI = Inst; 3975 --BBI; 3976 while (isNoopInstruction(BBI)) --BBI; 3977 if (&*BBI == GetObjCArg(Inst)) { 3978 InlineAsm *IA = 3979 InlineAsm::get(FunctionType::get(Type::getVoidTy(Inst->getContext()), 3980 /*isVarArg=*/false), 3981 RetainRVMarker->getString(), 3982 /*Constraints=*/"", /*hasSideEffects=*/true); 3983 CallInst::Create(IA, "", Inst); 3984 } 3985 break; 3986 } 3987 case IC_InitWeak: { 3988 // objc_initWeak(p, null) => *p = null 3989 CallInst *CI = cast<CallInst>(Inst); 3990 if (isNullOrUndef(CI->getArgOperand(1))) { 3991 Value *Null = 3992 ConstantPointerNull::get(cast<PointerType>(CI->getType())); 3993 Changed = true; 3994 new StoreInst(Null, CI->getArgOperand(0), CI); 3995 CI->replaceAllUsesWith(Null); 3996 CI->eraseFromParent(); 3997 } 3998 continue; 3999 } 4000 case IC_Release: 4001 ContractRelease(Inst, I); 4002 continue; 4003 case IC_User: 4004 // Be conservative if the function has any alloca instructions. 4005 // Technically we only care about escaping alloca instructions, 4006 // but this is sufficient to handle some interesting cases. 4007 if (isa<AllocaInst>(Inst)) 4008 TailOkForStoreStrongs = false; 4009 continue; 4010 default: 4011 continue; 4012 } 4013 4014 // Don't use GetObjCArg because we don't want to look through bitcasts 4015 // and such; to do the replacement, the argument must have type i8*. 4016 const Value *Arg = cast<CallInst>(Inst)->getArgOperand(0); 4017 for (;;) { 4018 // If we're compiling bugpointed code, don't get in trouble. 4019 if (!isa<Instruction>(Arg) && !isa<Argument>(Arg)) 4020 break; 4021 // Look through the uses of the pointer. 4022 for (Value::const_use_iterator UI = Arg->use_begin(), UE = Arg->use_end(); 4023 UI != UE; ) { 4024 Use &U = UI.getUse(); 4025 unsigned OperandNo = UI.getOperandNo(); 4026 ++UI; // Increment UI now, because we may unlink its element. 4027 if (Instruction *UserInst = dyn_cast<Instruction>(U.getUser())) 4028 if (Inst != UserInst && DT->dominates(Inst, UserInst)) { 4029 Changed = true; 4030 Instruction *Replacement = Inst; 4031 Type *UseTy = U.get()->getType(); 4032 if (PHINode *PHI = dyn_cast<PHINode>(UserInst)) { 4033 // For PHI nodes, insert the bitcast in the predecessor block. 4034 unsigned ValNo = 4035 PHINode::getIncomingValueNumForOperand(OperandNo); 4036 BasicBlock *BB = 4037 PHI->getIncomingBlock(ValNo); 4038 if (Replacement->getType() != UseTy) 4039 Replacement = new BitCastInst(Replacement, UseTy, "", 4040 &BB->back()); 4041 for (unsigned i = 0, e = PHI->getNumIncomingValues(); 4042 i != e; ++i) 4043 if (PHI->getIncomingBlock(i) == BB) { 4044 // Keep the UI iterator valid. 4045 if (&PHI->getOperandUse( 4046 PHINode::getOperandNumForIncomingValue(i)) == 4047 &UI.getUse()) 4048 ++UI; 4049 PHI->setIncomingValue(i, Replacement); 4050 } 4051 } else { 4052 if (Replacement->getType() != UseTy) 4053 Replacement = new BitCastInst(Replacement, UseTy, "", UserInst); 4054 U.set(Replacement); 4055 } 4056 } 4057 } 4058 4059 // If Arg is a no-op casted pointer, strip one level of casts and 4060 // iterate. 4061 if (const BitCastInst *BI = dyn_cast<BitCastInst>(Arg)) 4062 Arg = BI->getOperand(0); 4063 else if (isa<GEPOperator>(Arg) && 4064 cast<GEPOperator>(Arg)->hasAllZeroIndices()) 4065 Arg = cast<GEPOperator>(Arg)->getPointerOperand(); 4066 else if (isa<GlobalAlias>(Arg) && 4067 !cast<GlobalAlias>(Arg)->mayBeOverridden()) 4068 Arg = cast<GlobalAlias>(Arg)->getAliasee(); 4069 else 4070 break; 4071 } 4072 } 4073 4074 // If this function has no escaping allocas or suspicious vararg usage, 4075 // objc_storeStrong calls can be marked with the "tail" keyword. 4076 if (TailOkForStoreStrongs) 4077 for (DenseSet<CallInst *>::iterator I = StoreStrongCalls.begin(), 4078 E = StoreStrongCalls.end(); I != E; ++I) 4079 (*I)->setTailCall(); 4080 StoreStrongCalls.clear(); 4081 4082 return Changed; 4083} 4084