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