AliasAnalysis.cpp revision 9f5de6dadcdb9922ad8c8135a29e4abccec11671
153ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner//===- AliasAnalysis.cpp - Generic Alias Analysis Interface Implementation -==// 22b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 72b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 953ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// 1053ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// This file implements the generic AliasAnalysis interface which is used as the 1153ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// common interface used by all clients and implementations of alias analysis. 1253ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// 1353ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// This file also implements the default version of the AliasAnalysis interface 1453ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// that is to be used when no other implementation is specified. This does some 1553ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// simple tests that detect obvious cases: two different global pointers cannot 1653ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// alias, a global cannot alias a malloc, two different mallocs cannot alias, 1753ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// etc. 1853ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// 1953ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// This alias analysis implementation really isn't very good for anything, but 2053ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// it is very fast, and makes a nice clean default implementation. Because it 2153ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// handles lots of little corner cases, other, more complex, alias analysis 2253ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// implementations may choose to rely on this pass to resolve these simple and 2353ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// easy cases. 2453ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// 2553ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner//===----------------------------------------------------------------------===// 2653ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 27d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner#include "llvm/Analysis/AliasAnalysis.h" 283a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier#include "llvm/Analysis/CaptureTracking.h" 293a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier#include "llvm/Analysis/Dominators.h" 303a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier#include "llvm/Analysis/ValueTracking.h" 310b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/BasicBlock.h" 320b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DataLayout.h" 330b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 340b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 350b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/IntrinsicInst.h" 360b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/LLVMContext.h" 370b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Type.h" 38d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Pass.h" 398e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer#include "llvm/Target/TargetLibraryInfo.h" 40992860c44ed8d8b82c6b7fde6645123772965c65Chris Lattnerusing namespace llvm; 41d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 4253ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// Register the AliasAnalysis interface, providing a nice name to refer to. 43081c34b725980f995be9080eaec24cd3dfaaf065Owen AndersonINITIALIZE_ANALYSIS_GROUP(AliasAnalysis, "Alias Analysis", NoAA) 441997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar AliasAnalysis::ID = 0; 4553ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 465a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner//===----------------------------------------------------------------------===// 475a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner// Default chaining methods 485a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner//===----------------------------------------------------------------------===// 495a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner 505a24d70d99cc76be190ed6ebe37d09585046ddc3Chris LattnerAliasAnalysis::AliasResult 51b2143b6247901ae4eca2192ee134564c4f5f7853Dan GohmanAliasAnalysis::alias(const Location &LocA, const Location &LocB) { 525a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 53b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman return AA->alias(LocA, LocB); 545a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner} 555a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner 56a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohmanbool AliasAnalysis::pointsToConstantMemory(const Location &Loc, 57a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman bool OrLocal) { 585a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 59a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman return AA->pointsToConstantMemory(Loc, OrLocal); 605a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner} 615a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner 625a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattnervoid AliasAnalysis::deleteValue(Value *V) { 635a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 645a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner AA->deleteValue(V); 655a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner} 665a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner 675a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattnervoid AliasAnalysis::copyValue(Value *From, Value *To) { 685a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 695a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner AA->copyValue(From, To); 705a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner} 715a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner 72ab6acc6ecdc4585a55059e36d81481d1c26d3ff9Owen Andersonvoid AliasAnalysis::addEscapingUse(Use &U) { 73ab6acc6ecdc4585a55059e36d81481d1c26d3ff9Owen Anderson assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 74ab6acc6ecdc4585a55059e36d81481d1c26d3ff9Owen Anderson AA->addEscapingUse(U); 75ab6acc6ecdc4585a55059e36d81481d1c26d3ff9Owen Anderson} 76ab6acc6ecdc4585a55059e36d81481d1c26d3ff9Owen Anderson 77ab6acc6ecdc4585a55059e36d81481d1c26d3ff9Owen Anderson 785a24d70d99cc76be190ed6ebe37d09585046ddc3Chris LattnerAliasAnalysis::ModRefResult 796ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanAliasAnalysis::getModRefInfo(ImmutableCallSite CS, 80b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman const Location &Loc) { 81852dda46251f50286b6d83425f39e20a5c7592e9Dan Gohman assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 826ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 836ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman ModRefBehavior MRB = getModRefBehavior(CS); 846ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (MRB == DoesNotAccessMemory) 856ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return NoModRef; 866ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 876ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman ModRefResult Mask = ModRef; 88c07661c1fa7fd646c1e904f2327ca7f0105fb322Dan Gohman if (onlyReadsMemory(MRB)) 896ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman Mask = Ref; 90c07661c1fa7fd646c1e904f2327ca7f0105fb322Dan Gohman 9168a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman if (onlyAccessesArgPointees(MRB)) { 926ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman bool doesAlias = false; 93bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman if (doesAccessArgPointees(MRB)) { 94bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman MDNode *CSTag = CS.getInstruction()->getMetadata(LLVMContext::MD_tbaa); 9568a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman for (ImmutableCallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end(); 96bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman AI != AE; ++AI) { 97bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman const Value *Arg = *AI; 98bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman if (!Arg->getType()->isPointerTy()) 99bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman continue; 100bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman Location CSLoc(Arg, UnknownSize, CSTag); 101bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman if (!isNoAlias(CSLoc, Loc)) { 10268a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman doesAlias = true; 10368a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman break; 10468a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman } 105bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman } 106bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman } 1076ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (!doesAlias) 1086ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return NoModRef; 1096ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman } 1106ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 111b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman // If Loc is a constant memory location, the call definitely could not 1126ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // modify the memory location. 113b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if ((Mask & Mod) && pointsToConstantMemory(Loc)) 1146ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman Mask = ModRefResult(Mask & ~Mod); 1156ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 116e46a3881fc74652b23c3b31ee487e0ca9a6a268aDan Gohman // If this is the end of the chain, don't forward. 1176ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (!AA) return Mask; 1186ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1196ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // Otherwise, fall back to the next AA in the chain. But we can merge 1206ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // in any mask we've managed to compute. 121b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman return ModRefResult(AA->getModRefInfo(CS, Loc) & Mask); 1226ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman} 1236ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1246ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanAliasAnalysis::ModRefResult 12579fca6fea87be7221843031870bbf2c9ae1fc555Dan GohmanAliasAnalysis::getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2) { 126852dda46251f50286b6d83425f39e20a5c7592e9Dan Gohman assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 1276ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1286ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // If CS1 or CS2 are readnone, they don't interact. 1296ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman ModRefBehavior CS1B = getModRefBehavior(CS1); 1306ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (CS1B == DoesNotAccessMemory) return NoModRef; 1316ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1326ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman ModRefBehavior CS2B = getModRefBehavior(CS2); 1336ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (CS2B == DoesNotAccessMemory) return NoModRef; 1346ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1356ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // If they both only read from memory, there is no dependence. 136c07661c1fa7fd646c1e904f2327ca7f0105fb322Dan Gohman if (onlyReadsMemory(CS1B) && onlyReadsMemory(CS2B)) 1376ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return NoModRef; 1386ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1396ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman AliasAnalysis::ModRefResult Mask = ModRef; 1406ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1416ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // If CS1 only reads memory, the only dependence on CS2 can be 1426ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // from CS1 reading memory written by CS2. 143c07661c1fa7fd646c1e904f2327ca7f0105fb322Dan Gohman if (onlyReadsMemory(CS1B)) 1446ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman Mask = ModRefResult(Mask & Ref); 1456ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1466ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // If CS2 only access memory through arguments, accumulate the mod/ref 1476ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // information from CS1's references to the memory referenced by 1486ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // CS2's arguments. 14968a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman if (onlyAccessesArgPointees(CS2B)) { 1506ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman AliasAnalysis::ModRefResult R = NoModRef; 151bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman if (doesAccessArgPointees(CS2B)) { 152bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman MDNode *CS2Tag = CS2.getInstruction()->getMetadata(LLVMContext::MD_tbaa); 15368a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman for (ImmutableCallSite::arg_iterator 15468a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman I = CS2.arg_begin(), E = CS2.arg_end(); I != E; ++I) { 155bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman const Value *Arg = *I; 156bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman if (!Arg->getType()->isPointerTy()) 157bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman continue; 158bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman Location CS2Loc(Arg, UnknownSize, CS2Tag); 159bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman R = ModRefResult((R | getModRefInfo(CS1, CS2Loc)) & Mask); 16068a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman if (R == Mask) 16168a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman break; 16268a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman } 163bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman } 1646ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return R; 1656ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman } 1666ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1676ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // If CS1 only accesses memory through arguments, check if CS2 references 1686ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // any of the memory referenced by CS1's arguments. If not, return NoModRef. 16968a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman if (onlyAccessesArgPointees(CS1B)) { 1706ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman AliasAnalysis::ModRefResult R = NoModRef; 171bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman if (doesAccessArgPointees(CS1B)) { 172bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman MDNode *CS1Tag = CS1.getInstruction()->getMetadata(LLVMContext::MD_tbaa); 17368a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman for (ImmutableCallSite::arg_iterator 174bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman I = CS1.arg_begin(), E = CS1.arg_end(); I != E; ++I) { 175bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman const Value *Arg = *I; 176bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman if (!Arg->getType()->isPointerTy()) 177bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman continue; 178bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman Location CS1Loc(Arg, UnknownSize, CS1Tag); 179bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman if (getModRefInfo(CS2, CS1Loc) != NoModRef) { 18068a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman R = Mask; 18168a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman break; 18268a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman } 183bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman } 184bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman } 1856ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (R == NoModRef) 1866ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return R; 1876ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman } 1886ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 189e46a3881fc74652b23c3b31ee487e0ca9a6a268aDan Gohman // If this is the end of the chain, don't forward. 1906ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (!AA) return Mask; 1916ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1926ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // Otherwise, fall back to the next AA in the chain. But we can merge 1936ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // in any mask we've managed to compute. 1946ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return ModRefResult(AA->getModRefInfo(CS1, CS2) & Mask); 1956ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman} 1966ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1976ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanAliasAnalysis::ModRefBehavior 1986ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanAliasAnalysis::getModRefBehavior(ImmutableCallSite CS) { 199852dda46251f50286b6d83425f39e20a5c7592e9Dan Gohman assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 2006ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 2016ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman ModRefBehavior Min = UnknownModRefBehavior; 2026ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 2036ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // Call back into the alias analysis with the other form of getModRefBehavior 2046ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // to see if it can give a better response. 2056ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (const Function *F = CS.getCalledFunction()) 2066ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman Min = getModRefBehavior(F); 2076ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 208e46a3881fc74652b23c3b31ee487e0ca9a6a268aDan Gohman // If this is the end of the chain, don't forward. 2096ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (!AA) return Min; 2106ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 2116ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // Otherwise, fall back to the next AA in the chain. But we can merge 2126ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // in any result we've managed to compute. 21342c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman return ModRefBehavior(AA->getModRefBehavior(CS) & Min); 2146ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman} 2156ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 2166ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanAliasAnalysis::ModRefBehavior 2176ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanAliasAnalysis::getModRefBehavior(const Function *F) { 2185a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 2196ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return AA->getModRefBehavior(F); 2205a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner} 2215a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner 2225a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner//===----------------------------------------------------------------------===// 2235a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner// AliasAnalysis non-virtual helper method implementation 2245a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner//===----------------------------------------------------------------------===// 2255a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner 2266d8eb156e6be727570b300bac7712f745a318c7dDan GohmanAliasAnalysis::Location AliasAnalysis::getLocation(const LoadInst *LI) { 2276d8eb156e6be727570b300bac7712f745a318c7dDan Gohman return Location(LI->getPointerOperand(), 2286d8eb156e6be727570b300bac7712f745a318c7dDan Gohman getTypeStoreSize(LI->getType()), 2296d8eb156e6be727570b300bac7712f745a318c7dDan Gohman LI->getMetadata(LLVMContext::MD_tbaa)); 2306d8eb156e6be727570b300bac7712f745a318c7dDan Gohman} 2316d8eb156e6be727570b300bac7712f745a318c7dDan Gohman 2326d8eb156e6be727570b300bac7712f745a318c7dDan GohmanAliasAnalysis::Location AliasAnalysis::getLocation(const StoreInst *SI) { 2336d8eb156e6be727570b300bac7712f745a318c7dDan Gohman return Location(SI->getPointerOperand(), 2346d8eb156e6be727570b300bac7712f745a318c7dDan Gohman getTypeStoreSize(SI->getValueOperand()->getType()), 2356d8eb156e6be727570b300bac7712f745a318c7dDan Gohman SI->getMetadata(LLVMContext::MD_tbaa)); 2366d8eb156e6be727570b300bac7712f745a318c7dDan Gohman} 2376d8eb156e6be727570b300bac7712f745a318c7dDan Gohman 2386d8eb156e6be727570b300bac7712f745a318c7dDan GohmanAliasAnalysis::Location AliasAnalysis::getLocation(const VAArgInst *VI) { 2396d8eb156e6be727570b300bac7712f745a318c7dDan Gohman return Location(VI->getPointerOperand(), 2406d8eb156e6be727570b300bac7712f745a318c7dDan Gohman UnknownSize, 2416d8eb156e6be727570b300bac7712f745a318c7dDan Gohman VI->getMetadata(LLVMContext::MD_tbaa)); 2426d8eb156e6be727570b300bac7712f745a318c7dDan Gohman} 2436d8eb156e6be727570b300bac7712f745a318c7dDan Gohman 24446cb5afdcd031c371c78201fb34291d9d48b2ee4Eli FriedmanAliasAnalysis::Location 24546cb5afdcd031c371c78201fb34291d9d48b2ee4Eli FriedmanAliasAnalysis::getLocation(const AtomicCmpXchgInst *CXI) { 24646cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman return Location(CXI->getPointerOperand(), 24746cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman getTypeStoreSize(CXI->getCompareOperand()->getType()), 24846cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman CXI->getMetadata(LLVMContext::MD_tbaa)); 24946cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman} 25046cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman 25146cb5afdcd031c371c78201fb34291d9d48b2ee4Eli FriedmanAliasAnalysis::Location 25246cb5afdcd031c371c78201fb34291d9d48b2ee4Eli FriedmanAliasAnalysis::getLocation(const AtomicRMWInst *RMWI) { 25346cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman return Location(RMWI->getPointerOperand(), 25446cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman getTypeStoreSize(RMWI->getValOperand()->getType()), 25546cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman RMWI->getMetadata(LLVMContext::MD_tbaa)); 25646cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman} 257e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner 258e90c5cb747631b315350e7ee7424048c7778bdf9Chris LattnerAliasAnalysis::Location 259e90c5cb747631b315350e7ee7424048c7778bdf9Chris LattnerAliasAnalysis::getLocationForSource(const MemTransferInst *MTI) { 260e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner uint64_t Size = UnknownSize; 261e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner if (ConstantInt *C = dyn_cast<ConstantInt>(MTI->getLength())) 262e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner Size = C->getValue().getZExtValue(); 263e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner 264387f28aff41bae6a81311279b203a1281eaa443aDan Gohman // memcpy/memmove can have TBAA tags. For memcpy, they apply 265387f28aff41bae6a81311279b203a1281eaa443aDan Gohman // to both the source and the destination. 266387f28aff41bae6a81311279b203a1281eaa443aDan Gohman MDNode *TBAATag = MTI->getMetadata(LLVMContext::MD_tbaa); 267387f28aff41bae6a81311279b203a1281eaa443aDan Gohman 268387f28aff41bae6a81311279b203a1281eaa443aDan Gohman return Location(MTI->getRawSource(), Size, TBAATag); 269e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner} 270e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner 271e90c5cb747631b315350e7ee7424048c7778bdf9Chris LattnerAliasAnalysis::Location 2729dc9e81aa7412b329bbaf51a589a81475214802bChris LattnerAliasAnalysis::getLocationForDest(const MemIntrinsic *MTI) { 273e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner uint64_t Size = UnknownSize; 274e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner if (ConstantInt *C = dyn_cast<ConstantInt>(MTI->getLength())) 275e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner Size = C->getValue().getZExtValue(); 276387f28aff41bae6a81311279b203a1281eaa443aDan Gohman 277387f28aff41bae6a81311279b203a1281eaa443aDan Gohman // memcpy/memmove can have TBAA tags. For memcpy, they apply 278387f28aff41bae6a81311279b203a1281eaa443aDan Gohman // to both the source and the destination. 279387f28aff41bae6a81311279b203a1281eaa443aDan Gohman MDNode *TBAATag = MTI->getMetadata(LLVMContext::MD_tbaa); 280e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner 281387f28aff41bae6a81311279b203a1281eaa443aDan Gohman return Location(MTI->getRawDest(), Size, TBAATag); 282e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner} 283e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner 284e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner 285e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner 28614ac877e0a898ab46eeba1b0b72b8e5a9918179fChris LattnerAliasAnalysis::ModRefResult 287b2143b6247901ae4eca2192ee134564c4f5f7853Dan GohmanAliasAnalysis::getModRefInfo(const LoadInst *L, const Location &Loc) { 288667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman // Be conservative in the face of volatile/atomic. 289667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman if (!L->isUnordered()) 290b9db52dcbcf4279270eab972f3d560b4e5654260Dan Gohman return ModRef; 291b9db52dcbcf4279270eab972f3d560b4e5654260Dan Gohman 29214a498a48677eb1eaddd8329330df073224f9575Dan Gohman // If the load address doesn't alias the given address, it doesn't read 29314a498a48677eb1eaddd8329330df073224f9575Dan Gohman // or write the specified memory. 2946d8eb156e6be727570b300bac7712f745a318c7dDan Gohman if (!alias(getLocation(L), Loc)) 29514a498a48677eb1eaddd8329330df073224f9575Dan Gohman return NoModRef; 29614a498a48677eb1eaddd8329330df073224f9575Dan Gohman 29714a498a48677eb1eaddd8329330df073224f9575Dan Gohman // Otherwise, a load just reads. 29814a498a48677eb1eaddd8329330df073224f9575Dan Gohman return Ref; 29914ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner} 30053ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 30114ac877e0a898ab46eeba1b0b72b8e5a9918179fChris LattnerAliasAnalysis::ModRefResult 302b2143b6247901ae4eca2192ee134564c4f5f7853Dan GohmanAliasAnalysis::getModRefInfo(const StoreInst *S, const Location &Loc) { 303667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman // Be conservative in the face of volatile/atomic. 304667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman if (!S->isUnordered()) 305b9db52dcbcf4279270eab972f3d560b4e5654260Dan Gohman return ModRef; 306b9db52dcbcf4279270eab972f3d560b4e5654260Dan Gohman 3079b8639c9bd98ae08d0fe3630e2d3421a9277564aDan Gohman // If the store address cannot alias the pointer in question, then the 3089b8639c9bd98ae08d0fe3630e2d3421a9277564aDan Gohman // specified memory cannot be modified by the store. 3096d8eb156e6be727570b300bac7712f745a318c7dDan Gohman if (!alias(getLocation(S), Loc)) 310f4d904d7e326c9cbed497ca681b6270170fd2020Chris Lattner return NoModRef; 311f4d904d7e326c9cbed497ca681b6270170fd2020Chris Lattner 312f4d904d7e326c9cbed497ca681b6270170fd2020Chris Lattner // If the pointer is a pointer to constant memory, then it could not have been 313f4d904d7e326c9cbed497ca681b6270170fd2020Chris Lattner // modified by this store. 314b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if (pointsToConstantMemory(Loc)) 31514a498a48677eb1eaddd8329330df073224f9575Dan Gohman return NoModRef; 31614a498a48677eb1eaddd8329330df073224f9575Dan Gohman 31714a498a48677eb1eaddd8329330df073224f9575Dan Gohman // Otherwise, a store just writes. 31814a498a48677eb1eaddd8329330df073224f9575Dan Gohman return Mod; 31953ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner} 32053ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 321e26a7b5e21a49543a727b1b2524a934e73c89772Dan GohmanAliasAnalysis::ModRefResult 322b2143b6247901ae4eca2192ee134564c4f5f7853Dan GohmanAliasAnalysis::getModRefInfo(const VAArgInst *V, const Location &Loc) { 323e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman // If the va_arg address cannot alias the pointer in question, then the 324e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman // specified memory cannot be accessed by the va_arg. 3256d8eb156e6be727570b300bac7712f745a318c7dDan Gohman if (!alias(getLocation(V), Loc)) 326e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman return NoModRef; 327e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman 328e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman // If the pointer is a pointer to constant memory, then it could not have been 329e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman // modified by this va_arg. 330b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if (pointsToConstantMemory(Loc)) 331e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman return NoModRef; 332e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman 333e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman // Otherwise, a va_arg reads and writes. 334e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman return ModRef; 335e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman} 336e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman 33746cb5afdcd031c371c78201fb34291d9d48b2ee4Eli FriedmanAliasAnalysis::ModRefResult 33846cb5afdcd031c371c78201fb34291d9d48b2ee4Eli FriedmanAliasAnalysis::getModRefInfo(const AtomicCmpXchgInst *CX, const Location &Loc) { 33946cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman // Acquire/Release cmpxchg has properties that matter for arbitrary addresses. 34046cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman if (CX->getOrdering() > Monotonic) 34146cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman return ModRef; 34246cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman 34346cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman // If the cmpxchg address does not alias the location, it does not access it. 34446cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman if (!alias(getLocation(CX), Loc)) 34546cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman return NoModRef; 34646cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman 34746cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman return ModRef; 34846cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman} 34946cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman 35046cb5afdcd031c371c78201fb34291d9d48b2ee4Eli FriedmanAliasAnalysis::ModRefResult 35146cb5afdcd031c371c78201fb34291d9d48b2ee4Eli FriedmanAliasAnalysis::getModRefInfo(const AtomicRMWInst *RMW, const Location &Loc) { 35246cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman // Acquire/Release atomicrmw has properties that matter for arbitrary addresses. 35346cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman if (RMW->getOrdering() > Monotonic) 35446cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman return ModRef; 35546cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman 35646cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman // If the atomicrmw address does not alias the location, it does not access it. 35746cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman if (!alias(getLocation(RMW), Loc)) 35846cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman return NoModRef; 35946cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman 36046cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman return ModRef; 36146cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman} 36246cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman 3633a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosiernamespace { 364c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren // Conservatively return true. Return false, if there is a single path 365c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren // starting from "From" and the path does not reach "To". 366c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren static bool hasPath(const BasicBlock *From, const BasicBlock *To) { 367c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren const unsigned MaxCheck = 5; 368c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren const BasicBlock *Current = From; 369c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren for (unsigned I = 0; I < MaxCheck; I++) { 370c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren unsigned NumSuccs = Current->getTerminator()->getNumSuccessors(); 371c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren if (NumSuccs > 1) 372c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren return true; 373c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren if (NumSuccs == 0) 374c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren return false; 375c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren Current = Current->getTerminator()->getSuccessor(0); 376c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren if (Current == To) 377c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren return true; 378c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren } 379c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren return true; 380c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren } 381c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren 3823a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier /// Only find pointer captures which happen before the given instruction. Uses 3833a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier /// the dominator tree to determine whether one instruction is before another. 384c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren /// Only support the case where the Value is defined in the same basic block 385c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren /// as the given instruction and the use. 3863a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier struct CapturesBefore : public CaptureTracker { 3873a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier CapturesBefore(const Instruction *I, DominatorTree *DT) 3883a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier : BeforeHere(I), DT(DT), Captured(false) {} 3893a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier 3903a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier void tooManyUses() { Captured = true; } 3913a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier 3923a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier bool shouldExplore(Use *U) { 3933a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier Instruction *I = cast<Instruction>(U->getUser()); 3943a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier BasicBlock *BB = I->getParent(); 395c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren // We explore this usage only if the usage can reach "BeforeHere". 396c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren // If use is not reachable from entry, there is no need to explore. 397c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren if (BeforeHere != I && !DT->isReachableFromEntry(BB)) 398c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren return false; 399c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren // If the value is defined in the same basic block as use and BeforeHere, 400c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren // there is no need to explore the use if BeforeHere dominates use. 401c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren // Check whether there is a path from I to BeforeHere. 402c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren if (BeforeHere != I && DT->dominates(BeforeHere, I) && 403c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren !hasPath(BB, BeforeHere->getParent())) 4043a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier return false; 4053a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier return true; 4063a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier } 4073a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier 4083a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier bool captured(Use *U) { 4093a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier Instruction *I = cast<Instruction>(U->getUser()); 4103a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier BasicBlock *BB = I->getParent(); 411c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren // Same logic as in shouldExplore. 412c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren if (BeforeHere != I && !DT->isReachableFromEntry(BB)) 413c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren return false; 414c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren if (BeforeHere != I && DT->dominates(BeforeHere, I) && 415c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren !hasPath(BB, BeforeHere->getParent())) 4163a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier return false; 4173a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier Captured = true; 4183a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier return true; 4193a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier } 4203a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier 4213a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier const Instruction *BeforeHere; 4223a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier DominatorTree *DT; 4233a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier 4243a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier bool Captured; 4253a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier }; 4263a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier} 4273a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier 4283a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier// FIXME: this is really just shoring-up a deficiency in alias analysis. 4293a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier// BasicAA isn't willing to spend linear time determining whether an alloca 4303a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier// was captured before or after this particular call, while we are. However, 4313a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier// with a smarter AA in place, this test is just wasting compile time. 4323a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad RosierAliasAnalysis::ModRefResult 4333a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad RosierAliasAnalysis::callCapturesBefore(const Instruction *I, 4343a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier const AliasAnalysis::Location &MemLoc, 4353a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier DominatorTree *DT) { 4363a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier if (!DT || !TD) return AliasAnalysis::ModRef; 4373a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier 4383a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier const Value *Object = GetUnderlyingObject(MemLoc.Ptr, TD); 4393a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier if (!isIdentifiedObject(Object) || isa<GlobalValue>(Object) || 4403a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier isa<Constant>(Object)) 4413a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier return AliasAnalysis::ModRef; 4423a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier 4433a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier ImmutableCallSite CS(I); 4443a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier if (!CS.getInstruction() || CS.getInstruction() == Object) 4453a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier return AliasAnalysis::ModRef; 4463a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier 4473a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier CapturesBefore CB(I, DT); 4483a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier llvm::PointerMayBeCaptured(Object, &CB); 4493a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier if (CB.Captured) 4503a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier return AliasAnalysis::ModRef; 4513a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier 4523a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier unsigned ArgNo = 0; 4533a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier for (ImmutableCallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 4543a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier CI != CE; ++CI, ++ArgNo) { 4553a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier // Only look at the no-capture or byval pointer arguments. If this 4563a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier // pointer were passed to arguments that were neither of these, then it 4573a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier // couldn't be no-capture. 4583a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier if (!(*CI)->getType()->isPointerTy() || 4593a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier (!CS.doesNotCapture(ArgNo) && !CS.isByValArgument(ArgNo))) 4603a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier continue; 4613a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier 4623a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier // If this is a no-capture pointer argument, see if we can tell that it 4633a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier // is impossible to alias the pointer we're checking. If not, we have to 4643a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier // assume that the call could touch the pointer, even though it doesn't 4653a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier // escape. 4663a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier if (!isNoAlias(AliasAnalysis::Location(*CI), 4673a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier AliasAnalysis::Location(Object))) { 4683a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier return AliasAnalysis::ModRef; 4693a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier } 4703a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier } 4713a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier return AliasAnalysis::NoModRef; 4723a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier} 47346cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman 47453ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// AliasAnalysis destructor: DO NOT move this to the header file for 47553ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// AliasAnalysis or else clients of the AliasAnalysis class may not depend on 47653ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// the AliasAnalysis.o file in the current .a file, causing alias analysis 47753ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// support to not be included in the tool correctly! 47853ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// 47953ad0edd361c724df623c082a8a37eaf762d1703Chris LattnerAliasAnalysis::~AliasAnalysis() {} 48053ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 4815a56bf631eef695b04bbd306b53d6094f7616b5eDan Gohman/// InitializeAliasAnalysis - Subclasses must call this method to initialize the 48214ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner/// AliasAnalysis interface before any other methods are called. 483f9355f636b6a7d59993081766dd0481bd08f545dChris Lattner/// 48414ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattnervoid AliasAnalysis::InitializeAliasAnalysis(Pass *P) { 4853574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow TD = P->getAnalysisIfAvailable<DataLayout>(); 4868e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer TLI = P->getAnalysisIfAvailable<TargetLibraryInfo>(); 4875a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner AA = &P->getAnalysis<AliasAnalysis>(); 48814ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner} 48953ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 49014ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner// getAnalysisUsage - All alias analysis implementations should invoke this 491fc2a3ed0c9e32cf7edaf5030fa0972b916cc5f0bDan Gohman// directly (using AliasAnalysis::getAnalysisUsage(AU)). 49214ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattnervoid AliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 4935a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner AU.addRequired<AliasAnalysis>(); // All AA's chain 49414ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner} 49553ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 4963574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow/// getTypeStoreSize - Return the DataLayout store size for the given type, 497fc2a3ed0c9e32cf7edaf5030fa0972b916cc5f0bDan Gohman/// if known, or a conservative value otherwise. 498fc2a3ed0c9e32cf7edaf5030fa0972b916cc5f0bDan Gohman/// 499db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattneruint64_t AliasAnalysis::getTypeStoreSize(Type *Ty) { 500f3a925dc7a14ade42da442b49c304c064954c1d4Dan Gohman return TD ? TD->getTypeStoreSize(Ty) : UnknownSize; 501fc2a3ed0c9e32cf7edaf5030fa0972b916cc5f0bDan Gohman} 502fc2a3ed0c9e32cf7edaf5030fa0972b916cc5f0bDan Gohman 50314ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner/// canBasicBlockModify - Return true if it is possible for execution of the 50414ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner/// specified basic block to modify the value pointed to by Ptr. 50514ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner/// 50614ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattnerbool AliasAnalysis::canBasicBlockModify(const BasicBlock &BB, 507b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman const Location &Loc) { 508b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman return canInstructionRangeModify(BB.front(), BB.back(), Loc); 50953ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner} 51053ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 511f9355f636b6a7d59993081766dd0481bd08f545dChris Lattner/// canInstructionRangeModify - Return true if it is possible for the execution 512f9355f636b6a7d59993081766dd0481bd08f545dChris Lattner/// of the specified instructions to modify the value pointed to by Ptr. The 513f9355f636b6a7d59993081766dd0481bd08f545dChris Lattner/// instructions to consider are all of the instructions in the range of [I1,I2] 514f9355f636b6a7d59993081766dd0481bd08f545dChris Lattner/// INCLUSIVE. I1 and I2 must be in the same basic block. 515f9355f636b6a7d59993081766dd0481bd08f545dChris Lattner/// 51653ad0edd361c724df623c082a8a37eaf762d1703Chris Lattnerbool AliasAnalysis::canInstructionRangeModify(const Instruction &I1, 51753ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner const Instruction &I2, 518b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman const Location &Loc) { 51953ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner assert(I1.getParent() == I2.getParent() && 52053ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner "Instructions not in same basic block!"); 52179fca6fea87be7221843031870bbf2c9ae1fc555Dan Gohman BasicBlock::const_iterator I = &I1; 52279fca6fea87be7221843031870bbf2c9ae1fc555Dan Gohman BasicBlock::const_iterator E = &I2; 52353ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner ++E; // Convert from inclusive to exclusive range. 52453ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 52514ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner for (; I != E; ++I) // Check every instruction in range 526b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if (getModRefInfo(I, Loc) & Mod) 52753ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner return true; 52853ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner return false; 52953ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner} 53053ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 531a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman/// isNoAliasCall - Return true if this pointer is returned by a noalias 532a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman/// function. 533a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohmanbool llvm::isNoAliasCall(const Value *V) { 534a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman if (isa<CallInst>(V) || isa<InvokeInst>(V)) 53579fca6fea87be7221843031870bbf2c9ae1fc555Dan Gohman return ImmutableCallSite(cast<Instruction>(V)) 536034b94b17006f51722886b0f2283fb6fb19aca1fBill Wendling .paramHasAttr(0, Attribute::NoAlias); 537a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman return false; 538a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman} 539a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman 5409f5de6dadcdb9922ad8c8135a29e4abccec11671Michael Kuperstein/// isNoAliasArgument - Return true if this is an argument with the noalias 5419f5de6dadcdb9922ad8c8135a29e4abccec11671Michael Kuperstein/// attribute. 5429f5de6dadcdb9922ad8c8135a29e4abccec11671Michael Kupersteinbool llvm::isNoAliasArgument(const Value *V) 5439f5de6dadcdb9922ad8c8135a29e4abccec11671Michael Kuperstein{ 5449f5de6dadcdb9922ad8c8135a29e4abccec11671Michael Kuperstein if (const Argument *A = dyn_cast<Argument>(V)) 5459f5de6dadcdb9922ad8c8135a29e4abccec11671Michael Kuperstein return A->hasNoAliasAttr(); 5469f5de6dadcdb9922ad8c8135a29e4abccec11671Michael Kuperstein return false; 5479f5de6dadcdb9922ad8c8135a29e4abccec11671Michael Kuperstein} 5489f5de6dadcdb9922ad8c8135a29e4abccec11671Michael Kuperstein 549a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman/// isIdentifiedObject - Return true if this pointer refers to a distinct and 550a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman/// identifiable object. This returns true for: 5515753a4a0033da4add45f2e9930a4e1159d92a869Dan Gohman/// Global Variables and Functions (but not Global Aliases) 552a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman/// Allocas and Mallocs 5539e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman/// ByVal and NoAlias Arguments 5549e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman/// NoAlias returns 555a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman/// 5569e86f4364b912ae743490ba01d6989acfd12c046Dan Gohmanbool llvm::isIdentifiedObject(const Value *V) { 5576be2bd516a3022721480f8fee6986617baf0944fDan Gohman if (isa<AllocaInst>(V)) 5585753a4a0033da4add45f2e9930a4e1159d92a869Dan Gohman return true; 5595753a4a0033da4add45f2e9930a4e1159d92a869Dan Gohman if (isa<GlobalValue>(V) && !isa<GlobalAlias>(V)) 560a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman return true; 5619e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman if (isNoAliasCall(V)) 5629e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman return true; 5639e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman if (const Argument *A = dyn_cast<Argument>(V)) 5649e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman return A->hasNoAliasAttr() || A->hasByValAttr(); 565a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman return false; 566a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman} 567