DependencyAnalysis.cpp revision 3a57c37964adfbbf83b4b309a2ceda43ba6d8231
13a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman//===- DependencyAnalysis.cpp - ObjC ARC Optimization ---------------------===// 23a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman// 33a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman// The LLVM Compiler Infrastructure 43a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman// 53a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman// This file is distributed under the University of Illinois Open Source 63a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman// License. See LICENSE.TXT for details. 73a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman// 83a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman//===----------------------------------------------------------------------===// 93a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman/// \file 103a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman/// 113a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman/// This file defines special dependency analysis routines used in Objective C 123a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman/// ARC Optimizations. 133a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman/// 143a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman/// WARNING: This file knows about certain library functions. It recognizes them 153a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman/// by name, and hardwires knowledge of their semantics. 163a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman/// 173a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman/// WARNING: This file knows about how certain Objective-C library functions are 183a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman/// used. Naive LLVM IR transformations which would otherwise be 193a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman/// behavior-preserving may break these assumptions. 203a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman/// 213a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman//===----------------------------------------------------------------------===// 223a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman 233a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman#define DEBUG_TYPE "objc-arc-dependency" 243a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman#include "ObjCARC.h" 253a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman#include "ProvenanceAnalysis.h" 263a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman#include "DependencyAnalysis.h" 273a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman 283a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman#include "llvm/Support/CFG.h" 293a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman 303a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesmanusing namespace llvm; 313a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesmanusing namespace llvm::objcarc; 323a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman 333a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman/// Test whether the given instruction can result in a reference count 343a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman/// modification (positive or negative) for the pointer's object. 353a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesmanbool 363a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesmanllvm::objcarc::CanAlterRefCount(const Instruction *Inst, const Value *Ptr, 373a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman ProvenanceAnalysis &PA, 383a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman InstructionClass Class) { 393a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman switch (Class) { 403a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman case IC_Autorelease: 413a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman case IC_AutoreleaseRV: 423a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman case IC_User: 433a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman // These operations never directly modify a reference count. 443a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman return false; 453a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman default: break; 463a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman } 473a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman 483a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman ImmutableCallSite CS = static_cast<const Value *>(Inst); 493a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman assert(CS && "Only calls can alter reference counts!"); 503a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman 513a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman // See if AliasAnalysis can help us with the call. 523a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman AliasAnalysis::ModRefBehavior MRB = PA.getAA()->getModRefBehavior(CS); 533a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman if (AliasAnalysis::onlyReadsMemory(MRB)) 543a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman return false; 553a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman if (AliasAnalysis::onlyAccessesArgPointees(MRB)) { 563a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman for (ImmutableCallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); 573a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman I != E; ++I) { 583a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman const Value *Op = *I; 593a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op)) 603a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman return true; 613a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman } 623a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman return false; 633a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman } 643a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman 653a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman // Assume the worst. 663a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman return true; 673a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman} 683a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman 693a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman/// Test whether the given instruction can "use" the given pointer's object in a 703a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman/// way that requires the reference count to be positive. 713a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesmanbool 723a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesmanllvm::objcarc::CanUse(const Instruction *Inst, const Value *Ptr, 733a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman ProvenanceAnalysis &PA, InstructionClass Class) { 743a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman // IC_Call operations (as opposed to IC_CallOrUser) never "use" objc pointers. 753a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman if (Class == IC_Call) 763a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman return false; 773a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman 783a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman // Consider various instructions which may have pointer arguments which are 793a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman // not "uses". 803a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman if (const ICmpInst *ICI = dyn_cast<ICmpInst>(Inst)) { 813a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman // Comparing a pointer with null, or any other constant, isn't really a use, 823a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman // because we don't care what the pointer points to, or about the values 833a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman // of any other dynamic reference-counted pointers. 843a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman if (!IsPotentialRetainableObjPtr(ICI->getOperand(1), *PA.getAA())) 853a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman return false; 863a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman } else if (ImmutableCallSite CS = static_cast<const Value *>(Inst)) { 873a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman // For calls, just check the arguments (and not the callee operand). 883a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman for (ImmutableCallSite::arg_iterator OI = CS.arg_begin(), 893a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman OE = CS.arg_end(); OI != OE; ++OI) { 903a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman const Value *Op = *OI; 913a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op)) 923a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman return true; 933a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman } 943a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman return false; 953a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman } else if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 963a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman // Special-case stores, because we don't care about the stored value, just 973a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman // the store address. 983a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman const Value *Op = GetUnderlyingObjCPtr(SI->getPointerOperand()); 993a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman // If we can't tell what the underlying object was, assume there is a 1003a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman // dependence. 1013a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman return IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Op, Ptr); 1023a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman } 1033a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman 1043a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman // Check each operand for a match. 1053a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman for (User::const_op_iterator OI = Inst->op_begin(), OE = Inst->op_end(); 1063a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman OI != OE; ++OI) { 1073a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman const Value *Op = *OI; 1083a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op)) 1093a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman return true; 1103a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman } 1113a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman return false; 1123a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman} 1133a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman 1143a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman/// Test if there can be dependencies on Inst through Arg. This function only 1153a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman/// tests dependencies relevant for removing pairs of calls. 1163a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesmanbool 1173a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesmanllvm::objcarc::Depends(DependenceKind Flavor, Instruction *Inst, 1183a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman const Value *Arg, ProvenanceAnalysis &PA) { 1193a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman // If we've reached the definition of Arg, stop. 1203a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman if (Inst == Arg) 1213a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman return true; 1223a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman 1233a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman switch (Flavor) { 1243a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman case NeedsPositiveRetainCount: { 1253a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman InstructionClass Class = GetInstructionClass(Inst); 1263a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman switch (Class) { 1273a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman case IC_AutoreleasepoolPop: 1283a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman case IC_AutoreleasepoolPush: 1293a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman case IC_None: 1303a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman return false; 1313a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman default: 1323a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman return CanUse(Inst, Arg, PA, Class); 1333a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman } 1343a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman } 1353a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman 1363a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman case AutoreleasePoolBoundary: { 1373a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman InstructionClass Class = GetInstructionClass(Inst); 1383a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman switch (Class) { 1393a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman case IC_AutoreleasepoolPop: 1403a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman case IC_AutoreleasepoolPush: 1413a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman // These mark the end and begin of an autorelease pool scope. 1423a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman return true; 1433a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman default: 1443a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman // Nothing else does this. 1453a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman return false; 1463a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman } 1473a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman } 1483a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman 1493a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman case CanChangeRetainCount: { 1503a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman InstructionClass Class = GetInstructionClass(Inst); 1513a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman switch (Class) { 1523a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman case IC_AutoreleasepoolPop: 1533a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman // Conservatively assume this can decrement any count. 1543a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman return true; 1553a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman case IC_AutoreleasepoolPush: 1563a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman case IC_None: 1573a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman return false; 1583a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman default: 1593a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman return CanAlterRefCount(Inst, Arg, PA, Class); 1603a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman } 1613a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman } 1623a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman 1633a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman case RetainAutoreleaseDep: 1643a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman switch (GetBasicInstructionClass(Inst)) { 1653a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman case IC_AutoreleasepoolPop: 1663a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman case IC_AutoreleasepoolPush: 1673a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman // Don't merge an objc_autorelease with an objc_retain inside a different 1683a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman // autoreleasepool scope. 1693a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman return true; 1703a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman case IC_Retain: 1713a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman case IC_RetainRV: 1723a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman // Check for a retain of the same pointer for merging. 1733a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman return GetObjCArg(Inst) == Arg; 1743a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman default: 1753a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman // Nothing else matters for objc_retainAutorelease formation. 1763a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman return false; 1773a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman } 1783a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman 1793a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman case RetainAutoreleaseRVDep: { 1803a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman InstructionClass Class = GetBasicInstructionClass(Inst); 1813a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman switch (Class) { 1823a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman case IC_Retain: 1833a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman case IC_RetainRV: 1843a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman // Check for a retain of the same pointer for merging. 1853a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman return GetObjCArg(Inst) == Arg; 1863a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman default: 1873a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman // Anything that can autorelease interrupts 1883a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman // retainAutoreleaseReturnValue formation. 1893a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman return CanInterruptRV(Class); 1903a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman } 1913a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman } 1923a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman 1933a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman case RetainRVDep: 1943a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman return CanInterruptRV(GetBasicInstructionClass(Inst)); 1953a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman } 1963a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman 1973a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman llvm_unreachable("Invalid dependence flavor"); 1983a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman} 1993a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman 2003a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman/// Walk up the CFG from StartPos (which is in StartBB) and find local and 2013a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman/// non-local dependencies on Arg. 2023a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman/// 2033a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman/// TODO: Cache results? 2043a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesmanvoid 2053a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesmanllvm::objcarc::FindDependencies(DependenceKind Flavor, 2063a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman const Value *Arg, 2073a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman BasicBlock *StartBB, Instruction *StartInst, 2083a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman SmallPtrSet<Instruction *, 4> &DependingInsts, 2093a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman SmallPtrSet<const BasicBlock *, 4> &Visited, 2103a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman ProvenanceAnalysis &PA) { 2113a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman BasicBlock::iterator StartPos = StartInst; 2123a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman 2133a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman SmallVector<std::pair<BasicBlock *, BasicBlock::iterator>, 4> Worklist; 2143a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman Worklist.push_back(std::make_pair(StartBB, StartPos)); 2153a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman do { 2163a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman std::pair<BasicBlock *, BasicBlock::iterator> Pair = 2173a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman Worklist.pop_back_val(); 2183a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman BasicBlock *LocalStartBB = Pair.first; 2193a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman BasicBlock::iterator LocalStartPos = Pair.second; 2203a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman BasicBlock::iterator StartBBBegin = LocalStartBB->begin(); 2213a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman for (;;) { 2223a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman if (LocalStartPos == StartBBBegin) { 2233a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman pred_iterator PI(LocalStartBB), PE(LocalStartBB, false); 2243a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman if (PI == PE) 2253a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman // If we've reached the function entry, produce a null dependence. 2263a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman DependingInsts.insert(0); 2273a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman else 2283a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman // Add the predecessors to the worklist. 2293a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman do { 2303a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman BasicBlock *PredBB = *PI; 2313a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman if (Visited.insert(PredBB)) 2323a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman Worklist.push_back(std::make_pair(PredBB, PredBB->end())); 2333a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman } while (++PI != PE); 2343a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman break; 2353a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman } 2363a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman 2373a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman Instruction *Inst = --LocalStartPos; 2383a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman if (Depends(Flavor, Inst, Arg, PA)) { 2393a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman DependingInsts.insert(Inst); 2403a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman break; 2413a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman } 2423a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman } 2433a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman } while (!Worklist.empty()); 2443a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman 2453a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman // Determine whether the original StartBB post-dominates all of the blocks we 2463a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman // visited. If not, insert a sentinal indicating that most optimizations are 2473a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman // not safe. 2483a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman for (SmallPtrSet<const BasicBlock *, 4>::const_iterator I = Visited.begin(), 2493a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman E = Visited.end(); I != E; ++I) { 2503a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman const BasicBlock *BB = *I; 2513a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman if (BB == StartBB) 2523a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman continue; 2533a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman const TerminatorInst *TI = cast<TerminatorInst>(&BB->back()); 2543a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman for (succ_const_iterator SI(TI), SE(TI, false); SI != SE; ++SI) { 2553a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman const BasicBlock *Succ = *SI; 2563a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman if (Succ != StartBB && !Visited.count(Succ)) { 2573a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman DependingInsts.insert(reinterpret_cast<Instruction *>(-1)); 2583a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman return; 2593a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman } 2603a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman } 2613a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman } 2623a57c37964adfbbf83b4b309a2ceda43ba6d8231Michael Gottesman} 263