DependencyAnalysis.cpp revision dce4a407a24b04eebc6a376f8e62b41aaa7b071f
15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===- DependencyAnalysis.cpp - ObjC ARC Optimization ---------------------===// 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The LLVM Compiler Infrastructure 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This file is distributed under the University of Illinois Open Source 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// License. See LICENSE.TXT for details. 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// \file 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// This file defines special dependency analysis routines used in Objective C 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// ARC Optimizations. 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// WARNING: This file knows about certain library functions. It recognizes them 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// by name, and hardwires knowledge of their semantics. 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// WARNING: This file knows about how certain Objective-C library functions are 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// used. Naive LLVM IR transformations which would otherwise be 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// behavior-preserving may break these assumptions. 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "ObjCARC.h" 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "DependencyAnalysis.h" 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "ProvenanceAnalysis.h" 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/IR/CFG.h" 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using namespace llvm; 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using namespace llvm::objcarc; 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DEBUG_TYPE "objc-arc-dependency" 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/// Test whether the given instruction can result in a reference count 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// modification (positive or negative) for the pointer's object. 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)llvm::objcarc::CanAlterRefCount(const Instruction *Inst, const Value *Ptr, 372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ProvenanceAnalysis &PA, 382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) InstructionClass Class) { 392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) switch (Class) { 402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) case IC_Autorelease: 412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) case IC_AutoreleaseRV: 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case IC_IntrinsicUser: 432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) case IC_User: 442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // These operations never directly modify a reference count. 452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return false; 462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) default: break; 472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ImmutableCallSite CS = static_cast<const Value *>(Inst); 502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) assert(CS && "Only calls can alter reference counts!"); 512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // See if AliasAnalysis can help us with the call. 532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) AliasAnalysis::ModRefBehavior MRB = PA.getAA()->getModRefBehavior(CS); 542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (AliasAnalysis::onlyReadsMemory(MRB)) 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (AliasAnalysis::onlyAccessesArgPointees(MRB)) { 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (ImmutableCallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) I != E; ++I) { 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Value *Op = *I; 602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op)) 612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return true; 622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Assume the worst. 672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return true; 682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/// Test whether the given instruction can "use" the given pointer's object in a 712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/// way that requires the reference count to be positive. 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)llvm::objcarc::CanUse(const Instruction *Inst, const Value *Ptr, 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ProvenanceAnalysis &PA, InstructionClass Class) { 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // IC_Call operations (as opposed to IC_CallOrUser) never "use" objc pointers. 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (Class == IC_Call) 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Consider various instructions which may have pointer arguments which are 802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // not "uses". 812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (const ICmpInst *ICI = dyn_cast<ICmpInst>(Inst)) { 822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Comparing a pointer with null, or any other constant, isn't really a use, 832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // because we don't care what the pointer points to, or about the values 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // of any other dynamic reference-counted pointers. 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!IsPotentialRetainableObjPtr(ICI->getOperand(1), *PA.getAA())) 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (ImmutableCallSite CS = static_cast<const Value *>(Inst)) { 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // For calls, just check the arguments (and not the callee operand). 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (ImmutableCallSite::arg_iterator OI = CS.arg_begin(), 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) OE = CS.arg_end(); OI != OE; ++OI) { 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Value *Op = *OI; 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op)) 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Special-case stores, because we don't care about the stored value, just 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the store address. 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Value *Op = GetUnderlyingObjCPtr(SI->getPointerOperand()); 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If we can't tell what the underlying object was, assume there is a 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // dependence. 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Op, Ptr); 1035f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) } 1045f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 1055f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) // Check each operand for a match. 1065f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) for (User::const_op_iterator OI = Inst->op_begin(), OE = Inst->op_end(); 1075f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) OI != OE; ++OI) { 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Value *Op = *OI; 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op)) 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 1132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 1142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/// Test if there can be dependencies on Inst through Arg. This function only 1162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/// tests dependencies relevant for removing pairs of calls. 1172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)bool 1182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)llvm::objcarc::Depends(DependenceKind Flavor, Instruction *Inst, 1192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const Value *Arg, ProvenanceAnalysis &PA) { 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If we've reached the definition of Arg, stop. 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (Inst == Arg) 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) switch (Flavor) { 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case NeedsPositiveRetainCount: { 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) InstructionClass Class = GetInstructionClass(Inst); 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) switch (Class) { 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case IC_AutoreleasepoolPop: 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case IC_AutoreleasepoolPush: 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case IC_None: 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) default: 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return CanUse(Inst, Arg, PA, Class); 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) case AutoreleasePoolBoundary: { 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) InstructionClass Class = GetInstructionClass(Inst); 1392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) switch (Class) { 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case IC_AutoreleasepoolPop: 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case IC_AutoreleasepoolPush: 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // These mark the end and begin of an autorelease pool scope. 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) default: 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Nothing else does this. 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case CanChangeRetainCount: { 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) InstructionClass Class = GetInstructionClass(Inst); 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) switch (Class) { 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case IC_AutoreleasepoolPop: 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Conservatively assume this can decrement any count. 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case IC_AutoreleasepoolPush: 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case IC_None: 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) default: 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return CanAlterRefCount(Inst, Arg, PA, Class); 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case RetainAutoreleaseDep: 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) switch (GetBasicInstructionClass(Inst)) { 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case IC_AutoreleasepoolPop: 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case IC_AutoreleasepoolPush: 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Don't merge an objc_autorelease with an objc_retain inside a different 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // autoreleasepool scope. 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case IC_Retain: 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case IC_RetainRV: 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Check for a retain of the same pointer for merging. 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return GetObjCArg(Inst) == Arg; 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) default: 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Nothing else matters for objc_retainAutorelease formation. 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case RetainAutoreleaseRVDep: { 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) InstructionClass Class = GetBasicInstructionClass(Inst); 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) switch (Class) { 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case IC_Retain: 184868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) case IC_RetainRV: 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Check for a retain of the same pointer for merging. 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return GetObjCArg(Inst) == Arg; 1873551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) default: 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Anything that can autorelease interrupts 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // retainAutoreleaseReturnValue formation. 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return CanInterruptRV(Class); 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 192868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 193868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 1943551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) case RetainRVDep: 1953551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return CanInterruptRV(GetBasicInstructionClass(Inst)); 196868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1983551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) llvm_unreachable("Invalid dependence flavor"); 1993551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)} 2003551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 2013551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)/// Walk up the CFG from StartPos (which is in StartBB) and find local and 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// non-local dependencies on Arg. 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// TODO: Cache results? 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)llvm::objcarc::FindDependencies(DependenceKind Flavor, 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Value *Arg, 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BasicBlock *StartBB, Instruction *StartInst, 209868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) SmallPtrSet<Instruction *, 4> &DependingInsts, 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SmallPtrSet<const BasicBlock *, 4> &Visited, 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ProvenanceAnalysis &PA) { 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BasicBlock::iterator StartPos = StartInst; 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SmallVector<std::pair<BasicBlock *, BasicBlock::iterator>, 4> Worklist; 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Worklist.push_back(std::make_pair(StartBB, StartPos)); 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) do { 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::pair<BasicBlock *, BasicBlock::iterator> Pair = 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Worklist.pop_back_val(); 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BasicBlock *LocalStartBB = Pair.first; 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BasicBlock::iterator LocalStartPos = Pair.second; 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BasicBlock::iterator StartBBBegin = LocalStartBB->begin(); 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (;;) { 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (LocalStartPos == StartBBBegin) { 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pred_iterator PI(LocalStartBB), PE(LocalStartBB, false); 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (PI == PE) 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If we've reached the function entry, produce a null dependence. 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DependingInsts.insert(nullptr); 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Add the predecessors to the worklist. 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) do { 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BasicBlock *PredBB = *PI; 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (Visited.insert(PredBB)) 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Worklist.push_back(std::make_pair(PredBB, PredBB->end())); 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } while (++PI != PE); 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Instruction *Inst = --LocalStartPos; 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (Depends(Flavor, Inst, Arg, PA)) { 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DependingInsts.insert(Inst); 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } while (!Worklist.empty()); 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Determine whether the original StartBB post-dominates all of the blocks we 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // visited. If not, insert a sentinal indicating that most optimizations are 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // not safe. 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (SmallPtrSet<const BasicBlock *, 4>::const_iterator I = Visited.begin(), 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) E = Visited.end(); I != E; ++I) { 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const BasicBlock *BB = *I; 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (BB == StartBB) 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) continue; 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const TerminatorInst *TI = cast<TerminatorInst>(&BB->back()); 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (succ_const_iterator SI(TI), SE(TI, false); SI != SE; ++SI) { 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const BasicBlock *Succ = *SI; 257ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch if (Succ != StartBB && !Visited.count(Succ)) { 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DependingInsts.insert(reinterpret_cast<Instruction *>(-1)); 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)