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