AliasAnalysis.cpp revision 81e480463d8bb57776d03cebfd083762909023f1
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" 2981e480463d8bb57776d03cebfd083762909023f1Nick Lewycky#include "llvm/Analysis/CFG.h" 303a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier#include "llvm/Analysis/Dominators.h" 313a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier#include "llvm/Analysis/ValueTracking.h" 320b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/BasicBlock.h" 330b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DataLayout.h" 340b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 350b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 360b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/IntrinsicInst.h" 370b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/LLVMContext.h" 380b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Type.h" 39d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Pass.h" 408e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer#include "llvm/Target/TargetLibraryInfo.h" 41992860c44ed8d8b82c6b7fde6645123772965c65Chris Lattnerusing namespace llvm; 42d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 4353ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// Register the AliasAnalysis interface, providing a nice name to refer to. 44081c34b725980f995be9080eaec24cd3dfaaf065Owen AndersonINITIALIZE_ANALYSIS_GROUP(AliasAnalysis, "Alias Analysis", NoAA) 451997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar AliasAnalysis::ID = 0; 4653ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 475a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner//===----------------------------------------------------------------------===// 485a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner// Default chaining methods 495a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner//===----------------------------------------------------------------------===// 505a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner 515a24d70d99cc76be190ed6ebe37d09585046ddc3Chris LattnerAliasAnalysis::AliasResult 52b2143b6247901ae4eca2192ee134564c4f5f7853Dan GohmanAliasAnalysis::alias(const Location &LocA, const Location &LocB) { 535a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 54b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman return AA->alias(LocA, LocB); 555a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner} 565a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner 57a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohmanbool AliasAnalysis::pointsToConstantMemory(const Location &Loc, 58a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman bool OrLocal) { 595a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 60a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman return AA->pointsToConstantMemory(Loc, OrLocal); 615a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner} 625a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner 635a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattnervoid AliasAnalysis::deleteValue(Value *V) { 645a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 655a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner AA->deleteValue(V); 665a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner} 675a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner 685a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattnervoid AliasAnalysis::copyValue(Value *From, Value *To) { 695a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 705a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner AA->copyValue(From, To); 715a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner} 725a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner 73ab6acc6ecdc4585a55059e36d81481d1c26d3ff9Owen Andersonvoid AliasAnalysis::addEscapingUse(Use &U) { 74ab6acc6ecdc4585a55059e36d81481d1c26d3ff9Owen Anderson assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 75ab6acc6ecdc4585a55059e36d81481d1c26d3ff9Owen Anderson AA->addEscapingUse(U); 76ab6acc6ecdc4585a55059e36d81481d1c26d3ff9Owen Anderson} 77ab6acc6ecdc4585a55059e36d81481d1c26d3ff9Owen Anderson 78ab6acc6ecdc4585a55059e36d81481d1c26d3ff9Owen Anderson 795a24d70d99cc76be190ed6ebe37d09585046ddc3Chris LattnerAliasAnalysis::ModRefResult 806ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanAliasAnalysis::getModRefInfo(ImmutableCallSite CS, 81b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman const Location &Loc) { 82852dda46251f50286b6d83425f39e20a5c7592e9Dan Gohman assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 836ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 846ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman ModRefBehavior MRB = getModRefBehavior(CS); 856ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (MRB == DoesNotAccessMemory) 866ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return NoModRef; 876ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 886ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman ModRefResult Mask = ModRef; 89c07661c1fa7fd646c1e904f2327ca7f0105fb322Dan Gohman if (onlyReadsMemory(MRB)) 906ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman Mask = Ref; 91c07661c1fa7fd646c1e904f2327ca7f0105fb322Dan Gohman 9268a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman if (onlyAccessesArgPointees(MRB)) { 936ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman bool doesAlias = false; 94bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman if (doesAccessArgPointees(MRB)) { 95bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman MDNode *CSTag = CS.getInstruction()->getMetadata(LLVMContext::MD_tbaa); 9668a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman for (ImmutableCallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end(); 97bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman AI != AE; ++AI) { 98bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman const Value *Arg = *AI; 99bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman if (!Arg->getType()->isPointerTy()) 100bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman continue; 101bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman Location CSLoc(Arg, UnknownSize, CSTag); 102bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman if (!isNoAlias(CSLoc, Loc)) { 10368a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman doesAlias = true; 10468a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman break; 10568a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman } 106bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman } 107bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman } 1086ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (!doesAlias) 1096ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return NoModRef; 1106ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman } 1116ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 112b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman // If Loc is a constant memory location, the call definitely could not 1136ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // modify the memory location. 114b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if ((Mask & Mod) && pointsToConstantMemory(Loc)) 1156ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman Mask = ModRefResult(Mask & ~Mod); 1166ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 117e46a3881fc74652b23c3b31ee487e0ca9a6a268aDan Gohman // If this is the end of the chain, don't forward. 1186ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (!AA) return Mask; 1196ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1206ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // Otherwise, fall back to the next AA in the chain. But we can merge 1216ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // in any mask we've managed to compute. 122b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman return ModRefResult(AA->getModRefInfo(CS, Loc) & Mask); 1236ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman} 1246ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1256ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanAliasAnalysis::ModRefResult 12679fca6fea87be7221843031870bbf2c9ae1fc555Dan GohmanAliasAnalysis::getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2) { 127852dda46251f50286b6d83425f39e20a5c7592e9Dan Gohman assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 1286ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1296ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // If CS1 or CS2 are readnone, they don't interact. 1306ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman ModRefBehavior CS1B = getModRefBehavior(CS1); 1316ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (CS1B == DoesNotAccessMemory) return NoModRef; 1326ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1336ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman ModRefBehavior CS2B = getModRefBehavior(CS2); 1346ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (CS2B == DoesNotAccessMemory) return NoModRef; 1356ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1366ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // If they both only read from memory, there is no dependence. 137c07661c1fa7fd646c1e904f2327ca7f0105fb322Dan Gohman if (onlyReadsMemory(CS1B) && onlyReadsMemory(CS2B)) 1386ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return NoModRef; 1396ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1406ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman AliasAnalysis::ModRefResult Mask = ModRef; 1416ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1426ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // If CS1 only reads memory, the only dependence on CS2 can be 1436ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // from CS1 reading memory written by CS2. 144c07661c1fa7fd646c1e904f2327ca7f0105fb322Dan Gohman if (onlyReadsMemory(CS1B)) 1456ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman Mask = ModRefResult(Mask & Ref); 1466ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1476ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // If CS2 only access memory through arguments, accumulate the mod/ref 1486ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // information from CS1's references to the memory referenced by 1496ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // CS2's arguments. 15068a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman if (onlyAccessesArgPointees(CS2B)) { 1516ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman AliasAnalysis::ModRefResult R = NoModRef; 152bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman if (doesAccessArgPointees(CS2B)) { 153bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman MDNode *CS2Tag = CS2.getInstruction()->getMetadata(LLVMContext::MD_tbaa); 15468a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman for (ImmutableCallSite::arg_iterator 15568a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman I = CS2.arg_begin(), E = CS2.arg_end(); I != E; ++I) { 156bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman const Value *Arg = *I; 157bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman if (!Arg->getType()->isPointerTy()) 158bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman continue; 159bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman Location CS2Loc(Arg, UnknownSize, CS2Tag); 160bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman R = ModRefResult((R | getModRefInfo(CS1, CS2Loc)) & Mask); 16168a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman if (R == Mask) 16268a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman break; 16368a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman } 164bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman } 1656ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return R; 1666ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman } 1676ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1686ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // If CS1 only accesses memory through arguments, check if CS2 references 1696ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // any of the memory referenced by CS1's arguments. If not, return NoModRef. 17068a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman if (onlyAccessesArgPointees(CS1B)) { 1716ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman AliasAnalysis::ModRefResult R = NoModRef; 172bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman if (doesAccessArgPointees(CS1B)) { 173bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman MDNode *CS1Tag = CS1.getInstruction()->getMetadata(LLVMContext::MD_tbaa); 17468a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman for (ImmutableCallSite::arg_iterator 175bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman I = CS1.arg_begin(), E = CS1.arg_end(); I != E; ++I) { 176bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman const Value *Arg = *I; 177bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman if (!Arg->getType()->isPointerTy()) 178bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman continue; 179bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman Location CS1Loc(Arg, UnknownSize, CS1Tag); 180bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman if (getModRefInfo(CS2, CS1Loc) != NoModRef) { 18168a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman R = Mask; 18268a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman break; 18368a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman } 184bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman } 185bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman } 1866ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (R == NoModRef) 1876ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return R; 1886ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman } 1896ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 190e46a3881fc74652b23c3b31ee487e0ca9a6a268aDan Gohman // If this is the end of the chain, don't forward. 1916ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (!AA) return Mask; 1926ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1936ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // Otherwise, fall back to the next AA in the chain. But we can merge 1946ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // in any mask we've managed to compute. 1956ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return ModRefResult(AA->getModRefInfo(CS1, CS2) & Mask); 1966ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman} 1976ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1986ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanAliasAnalysis::ModRefBehavior 1996ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanAliasAnalysis::getModRefBehavior(ImmutableCallSite CS) { 200852dda46251f50286b6d83425f39e20a5c7592e9Dan Gohman assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 2016ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 2026ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman ModRefBehavior Min = UnknownModRefBehavior; 2036ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 2046ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // Call back into the alias analysis with the other form of getModRefBehavior 2056ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // to see if it can give a better response. 2066ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (const Function *F = CS.getCalledFunction()) 2076ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman Min = getModRefBehavior(F); 2086ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 209e46a3881fc74652b23c3b31ee487e0ca9a6a268aDan Gohman // If this is the end of the chain, don't forward. 2106ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (!AA) return Min; 2116ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 2126ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // Otherwise, fall back to the next AA in the chain. But we can merge 2136ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // in any result we've managed to compute. 21442c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman return ModRefBehavior(AA->getModRefBehavior(CS) & Min); 2156ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman} 2166ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 2176ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanAliasAnalysis::ModRefBehavior 2186ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanAliasAnalysis::getModRefBehavior(const Function *F) { 2195a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 2206ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return AA->getModRefBehavior(F); 2215a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner} 2225a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner 2235a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner//===----------------------------------------------------------------------===// 2245a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner// AliasAnalysis non-virtual helper method implementation 2255a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner//===----------------------------------------------------------------------===// 2265a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner 2276d8eb156e6be727570b300bac7712f745a318c7dDan GohmanAliasAnalysis::Location AliasAnalysis::getLocation(const LoadInst *LI) { 2286d8eb156e6be727570b300bac7712f745a318c7dDan Gohman return Location(LI->getPointerOperand(), 2296d8eb156e6be727570b300bac7712f745a318c7dDan Gohman getTypeStoreSize(LI->getType()), 2306d8eb156e6be727570b300bac7712f745a318c7dDan Gohman LI->getMetadata(LLVMContext::MD_tbaa)); 2316d8eb156e6be727570b300bac7712f745a318c7dDan Gohman} 2326d8eb156e6be727570b300bac7712f745a318c7dDan Gohman 2336d8eb156e6be727570b300bac7712f745a318c7dDan GohmanAliasAnalysis::Location AliasAnalysis::getLocation(const StoreInst *SI) { 2346d8eb156e6be727570b300bac7712f745a318c7dDan Gohman return Location(SI->getPointerOperand(), 2356d8eb156e6be727570b300bac7712f745a318c7dDan Gohman getTypeStoreSize(SI->getValueOperand()->getType()), 2366d8eb156e6be727570b300bac7712f745a318c7dDan Gohman SI->getMetadata(LLVMContext::MD_tbaa)); 2376d8eb156e6be727570b300bac7712f745a318c7dDan Gohman} 2386d8eb156e6be727570b300bac7712f745a318c7dDan Gohman 2396d8eb156e6be727570b300bac7712f745a318c7dDan GohmanAliasAnalysis::Location AliasAnalysis::getLocation(const VAArgInst *VI) { 2406d8eb156e6be727570b300bac7712f745a318c7dDan Gohman return Location(VI->getPointerOperand(), 2416d8eb156e6be727570b300bac7712f745a318c7dDan Gohman UnknownSize, 2426d8eb156e6be727570b300bac7712f745a318c7dDan Gohman VI->getMetadata(LLVMContext::MD_tbaa)); 2436d8eb156e6be727570b300bac7712f745a318c7dDan Gohman} 2446d8eb156e6be727570b300bac7712f745a318c7dDan Gohman 24546cb5afdcd031c371c78201fb34291d9d48b2ee4Eli FriedmanAliasAnalysis::Location 24646cb5afdcd031c371c78201fb34291d9d48b2ee4Eli FriedmanAliasAnalysis::getLocation(const AtomicCmpXchgInst *CXI) { 24746cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman return Location(CXI->getPointerOperand(), 24846cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman getTypeStoreSize(CXI->getCompareOperand()->getType()), 24946cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman CXI->getMetadata(LLVMContext::MD_tbaa)); 25046cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman} 25146cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman 25246cb5afdcd031c371c78201fb34291d9d48b2ee4Eli FriedmanAliasAnalysis::Location 25346cb5afdcd031c371c78201fb34291d9d48b2ee4Eli FriedmanAliasAnalysis::getLocation(const AtomicRMWInst *RMWI) { 25446cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman return Location(RMWI->getPointerOperand(), 25546cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman getTypeStoreSize(RMWI->getValOperand()->getType()), 25646cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman RMWI->getMetadata(LLVMContext::MD_tbaa)); 25746cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman} 258e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner 259e90c5cb747631b315350e7ee7424048c7778bdf9Chris LattnerAliasAnalysis::Location 260e90c5cb747631b315350e7ee7424048c7778bdf9Chris LattnerAliasAnalysis::getLocationForSource(const MemTransferInst *MTI) { 261e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner uint64_t Size = UnknownSize; 262e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner if (ConstantInt *C = dyn_cast<ConstantInt>(MTI->getLength())) 263e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner Size = C->getValue().getZExtValue(); 264e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner 265387f28aff41bae6a81311279b203a1281eaa443aDan Gohman // memcpy/memmove can have TBAA tags. For memcpy, they apply 266387f28aff41bae6a81311279b203a1281eaa443aDan Gohman // to both the source and the destination. 267387f28aff41bae6a81311279b203a1281eaa443aDan Gohman MDNode *TBAATag = MTI->getMetadata(LLVMContext::MD_tbaa); 268387f28aff41bae6a81311279b203a1281eaa443aDan Gohman 269387f28aff41bae6a81311279b203a1281eaa443aDan Gohman return Location(MTI->getRawSource(), Size, TBAATag); 270e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner} 271e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner 272e90c5cb747631b315350e7ee7424048c7778bdf9Chris LattnerAliasAnalysis::Location 2739dc9e81aa7412b329bbaf51a589a81475214802bChris LattnerAliasAnalysis::getLocationForDest(const MemIntrinsic *MTI) { 274e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner uint64_t Size = UnknownSize; 275e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner if (ConstantInt *C = dyn_cast<ConstantInt>(MTI->getLength())) 276e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner Size = C->getValue().getZExtValue(); 277387f28aff41bae6a81311279b203a1281eaa443aDan Gohman 278387f28aff41bae6a81311279b203a1281eaa443aDan Gohman // memcpy/memmove can have TBAA tags. For memcpy, they apply 279387f28aff41bae6a81311279b203a1281eaa443aDan Gohman // to both the source and the destination. 280387f28aff41bae6a81311279b203a1281eaa443aDan Gohman MDNode *TBAATag = MTI->getMetadata(LLVMContext::MD_tbaa); 281e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner 282387f28aff41bae6a81311279b203a1281eaa443aDan Gohman return Location(MTI->getRawDest(), Size, TBAATag); 283e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner} 284e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner 285e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner 286e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner 28714ac877e0a898ab46eeba1b0b72b8e5a9918179fChris LattnerAliasAnalysis::ModRefResult 288b2143b6247901ae4eca2192ee134564c4f5f7853Dan GohmanAliasAnalysis::getModRefInfo(const LoadInst *L, const Location &Loc) { 289667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman // Be conservative in the face of volatile/atomic. 290667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman if (!L->isUnordered()) 291b9db52dcbcf4279270eab972f3d560b4e5654260Dan Gohman return ModRef; 292b9db52dcbcf4279270eab972f3d560b4e5654260Dan Gohman 29314a498a48677eb1eaddd8329330df073224f9575Dan Gohman // If the load address doesn't alias the given address, it doesn't read 29414a498a48677eb1eaddd8329330df073224f9575Dan Gohman // or write the specified memory. 2956d8eb156e6be727570b300bac7712f745a318c7dDan Gohman if (!alias(getLocation(L), Loc)) 29614a498a48677eb1eaddd8329330df073224f9575Dan Gohman return NoModRef; 29714a498a48677eb1eaddd8329330df073224f9575Dan Gohman 29814a498a48677eb1eaddd8329330df073224f9575Dan Gohman // Otherwise, a load just reads. 29914a498a48677eb1eaddd8329330df073224f9575Dan Gohman return Ref; 30014ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner} 30153ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 30214ac877e0a898ab46eeba1b0b72b8e5a9918179fChris LattnerAliasAnalysis::ModRefResult 303b2143b6247901ae4eca2192ee134564c4f5f7853Dan GohmanAliasAnalysis::getModRefInfo(const StoreInst *S, const Location &Loc) { 304667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman // Be conservative in the face of volatile/atomic. 305667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman if (!S->isUnordered()) 306b9db52dcbcf4279270eab972f3d560b4e5654260Dan Gohman return ModRef; 307b9db52dcbcf4279270eab972f3d560b4e5654260Dan Gohman 3089b8639c9bd98ae08d0fe3630e2d3421a9277564aDan Gohman // If the store address cannot alias the pointer in question, then the 3099b8639c9bd98ae08d0fe3630e2d3421a9277564aDan Gohman // specified memory cannot be modified by the store. 3106d8eb156e6be727570b300bac7712f745a318c7dDan Gohman if (!alias(getLocation(S), Loc)) 311f4d904d7e326c9cbed497ca681b6270170fd2020Chris Lattner return NoModRef; 312f4d904d7e326c9cbed497ca681b6270170fd2020Chris Lattner 313f4d904d7e326c9cbed497ca681b6270170fd2020Chris Lattner // If the pointer is a pointer to constant memory, then it could not have been 314f4d904d7e326c9cbed497ca681b6270170fd2020Chris Lattner // modified by this store. 315b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if (pointsToConstantMemory(Loc)) 31614a498a48677eb1eaddd8329330df073224f9575Dan Gohman return NoModRef; 31714a498a48677eb1eaddd8329330df073224f9575Dan Gohman 31814a498a48677eb1eaddd8329330df073224f9575Dan Gohman // Otherwise, a store just writes. 31914a498a48677eb1eaddd8329330df073224f9575Dan Gohman return Mod; 32053ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner} 32153ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 322e26a7b5e21a49543a727b1b2524a934e73c89772Dan GohmanAliasAnalysis::ModRefResult 323b2143b6247901ae4eca2192ee134564c4f5f7853Dan GohmanAliasAnalysis::getModRefInfo(const VAArgInst *V, const Location &Loc) { 324e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman // If the va_arg address cannot alias the pointer in question, then the 325e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman // specified memory cannot be accessed by the va_arg. 3266d8eb156e6be727570b300bac7712f745a318c7dDan Gohman if (!alias(getLocation(V), Loc)) 327e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman return NoModRef; 328e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman 329e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman // If the pointer is a pointer to constant memory, then it could not have been 330e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman // modified by this va_arg. 331b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if (pointsToConstantMemory(Loc)) 332e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman return NoModRef; 333e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman 334e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman // Otherwise, a va_arg reads and writes. 335e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman return ModRef; 336e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman} 337e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman 33846cb5afdcd031c371c78201fb34291d9d48b2ee4Eli FriedmanAliasAnalysis::ModRefResult 33946cb5afdcd031c371c78201fb34291d9d48b2ee4Eli FriedmanAliasAnalysis::getModRefInfo(const AtomicCmpXchgInst *CX, const Location &Loc) { 34046cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman // Acquire/Release cmpxchg has properties that matter for arbitrary addresses. 34146cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman if (CX->getOrdering() > Monotonic) 34246cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman return ModRef; 34346cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman 34446cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman // If the cmpxchg address does not alias the location, it does not access it. 34546cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman if (!alias(getLocation(CX), Loc)) 34646cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman return NoModRef; 34746cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman 34846cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman return ModRef; 34946cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman} 35046cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman 35146cb5afdcd031c371c78201fb34291d9d48b2ee4Eli FriedmanAliasAnalysis::ModRefResult 35246cb5afdcd031c371c78201fb34291d9d48b2ee4Eli FriedmanAliasAnalysis::getModRefInfo(const AtomicRMWInst *RMW, const Location &Loc) { 35346cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman // Acquire/Release atomicrmw has properties that matter for arbitrary addresses. 35446cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman if (RMW->getOrdering() > Monotonic) 35546cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman return ModRef; 35646cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman 35746cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman // If the atomicrmw address does not alias the location, it does not access it. 35846cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman if (!alias(getLocation(RMW), Loc)) 35946cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman return NoModRef; 36046cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman 36146cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman return ModRef; 36246cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman} 36346cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman 3643a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosiernamespace { 3653a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier /// Only find pointer captures which happen before the given instruction. Uses 3663a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier /// the dominator tree to determine whether one instruction is before another. 367c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren /// Only support the case where the Value is defined in the same basic block 368c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren /// as the given instruction and the use. 3693a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier struct CapturesBefore : public CaptureTracker { 3703a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier CapturesBefore(const Instruction *I, DominatorTree *DT) 3713a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier : BeforeHere(I), DT(DT), Captured(false) {} 3723a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier 3733a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier void tooManyUses() { Captured = true; } 3743a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier 3753a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier bool shouldExplore(Use *U) { 3763a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier Instruction *I = cast<Instruction>(U->getUser()); 3773a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier BasicBlock *BB = I->getParent(); 378c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren // We explore this usage only if the usage can reach "BeforeHere". 379c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren // If use is not reachable from entry, there is no need to explore. 380c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren if (BeforeHere != I && !DT->isReachableFromEntry(BB)) 381c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren return false; 382c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren // If the value is defined in the same basic block as use and BeforeHere, 383c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren // there is no need to explore the use if BeforeHere dominates use. 384c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren // Check whether there is a path from I to BeforeHere. 385c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren if (BeforeHere != I && DT->dominates(BeforeHere, I) && 38681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky !isPotentiallyReachable(I, BeforeHere, DT)) 3873a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier return false; 3883a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier return true; 3893a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier } 3903a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier 3913a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier bool captured(Use *U) { 3923a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier Instruction *I = cast<Instruction>(U->getUser()); 3933a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier BasicBlock *BB = I->getParent(); 394c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren // Same logic as in shouldExplore. 395c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren if (BeforeHere != I && !DT->isReachableFromEntry(BB)) 396c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren return false; 397c55bd47105ef8e362cfb2a2c97ee3e23145aca4dManman Ren if (BeforeHere != I && DT->dominates(BeforeHere, I) && 39881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky !isPotentiallyReachable(I, BeforeHere, DT)) 3993a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier return false; 4003a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier Captured = true; 4013a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier return true; 4023a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier } 4033a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier 4043a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier const Instruction *BeforeHere; 4053a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier DominatorTree *DT; 4063a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier 4073a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier bool Captured; 4083a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier }; 4093a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier} 4103a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier 4113a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier// FIXME: this is really just shoring-up a deficiency in alias analysis. 4123a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier// BasicAA isn't willing to spend linear time determining whether an alloca 4133a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier// was captured before or after this particular call, while we are. However, 4143a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier// with a smarter AA in place, this test is just wasting compile time. 4153a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad RosierAliasAnalysis::ModRefResult 4163a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad RosierAliasAnalysis::callCapturesBefore(const Instruction *I, 4173a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier const AliasAnalysis::Location &MemLoc, 4183a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier DominatorTree *DT) { 4193a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier if (!DT || !TD) return AliasAnalysis::ModRef; 4203a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier 4213a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier const Value *Object = GetUnderlyingObject(MemLoc.Ptr, TD); 4223a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier if (!isIdentifiedObject(Object) || isa<GlobalValue>(Object) || 4233a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier isa<Constant>(Object)) 4243a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier return AliasAnalysis::ModRef; 4253a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier 4263a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier ImmutableCallSite CS(I); 4273a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier if (!CS.getInstruction() || CS.getInstruction() == Object) 4283a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier return AliasAnalysis::ModRef; 4293a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier 4303a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier CapturesBefore CB(I, DT); 4313a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier llvm::PointerMayBeCaptured(Object, &CB); 4323a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier if (CB.Captured) 4333a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier return AliasAnalysis::ModRef; 4343a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier 4353a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier unsigned ArgNo = 0; 43637ade2b8015d86e73c62ab48a2ce5f0ce10de708Nick Lewycky AliasAnalysis::ModRefResult R = AliasAnalysis::NoModRef; 4373a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier for (ImmutableCallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 4383a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier CI != CE; ++CI, ++ArgNo) { 4393a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier // Only look at the no-capture or byval pointer arguments. If this 4403a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier // pointer were passed to arguments that were neither of these, then it 4413a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier // couldn't be no-capture. 4423a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier if (!(*CI)->getType()->isPointerTy() || 4433a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier (!CS.doesNotCapture(ArgNo) && !CS.isByValArgument(ArgNo))) 4443a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier continue; 4453a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier 4463a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier // If this is a no-capture pointer argument, see if we can tell that it 4473a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier // is impossible to alias the pointer we're checking. If not, we have to 4483a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier // assume that the call could touch the pointer, even though it doesn't 4493a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier // escape. 45037ade2b8015d86e73c62ab48a2ce5f0ce10de708Nick Lewycky if (isNoAlias(AliasAnalysis::Location(*CI), 45137ade2b8015d86e73c62ab48a2ce5f0ce10de708Nick Lewycky AliasAnalysis::Location(Object))) 45237ade2b8015d86e73c62ab48a2ce5f0ce10de708Nick Lewycky continue; 45337ade2b8015d86e73c62ab48a2ce5f0ce10de708Nick Lewycky if (CS.doesNotAccessMemory(ArgNo)) 45437ade2b8015d86e73c62ab48a2ce5f0ce10de708Nick Lewycky continue; 45537ade2b8015d86e73c62ab48a2ce5f0ce10de708Nick Lewycky if (CS.onlyReadsMemory(ArgNo)) { 45637ade2b8015d86e73c62ab48a2ce5f0ce10de708Nick Lewycky R = AliasAnalysis::Ref; 45737ade2b8015d86e73c62ab48a2ce5f0ce10de708Nick Lewycky continue; 4583a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier } 45937ade2b8015d86e73c62ab48a2ce5f0ce10de708Nick Lewycky return AliasAnalysis::ModRef; 4603a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier } 46137ade2b8015d86e73c62ab48a2ce5f0ce10de708Nick Lewycky return R; 4623a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier} 46346cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman 46453ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// AliasAnalysis destructor: DO NOT move this to the header file for 46553ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// AliasAnalysis or else clients of the AliasAnalysis class may not depend on 46653ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// the AliasAnalysis.o file in the current .a file, causing alias analysis 46753ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// support to not be included in the tool correctly! 46853ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// 46953ad0edd361c724df623c082a8a37eaf762d1703Chris LattnerAliasAnalysis::~AliasAnalysis() {} 47053ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 4715a56bf631eef695b04bbd306b53d6094f7616b5eDan Gohman/// InitializeAliasAnalysis - Subclasses must call this method to initialize the 47214ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner/// AliasAnalysis interface before any other methods are called. 473f9355f636b6a7d59993081766dd0481bd08f545dChris Lattner/// 47414ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattnervoid AliasAnalysis::InitializeAliasAnalysis(Pass *P) { 4753574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow TD = P->getAnalysisIfAvailable<DataLayout>(); 4768e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer TLI = P->getAnalysisIfAvailable<TargetLibraryInfo>(); 4775a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner AA = &P->getAnalysis<AliasAnalysis>(); 47814ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner} 47953ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 48014ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner// getAnalysisUsage - All alias analysis implementations should invoke this 481fc2a3ed0c9e32cf7edaf5030fa0972b916cc5f0bDan Gohman// directly (using AliasAnalysis::getAnalysisUsage(AU)). 48214ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattnervoid AliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 4835a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner AU.addRequired<AliasAnalysis>(); // All AA's chain 48414ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner} 48553ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 4863574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow/// getTypeStoreSize - Return the DataLayout store size for the given type, 487fc2a3ed0c9e32cf7edaf5030fa0972b916cc5f0bDan Gohman/// if known, or a conservative value otherwise. 488fc2a3ed0c9e32cf7edaf5030fa0972b916cc5f0bDan Gohman/// 489db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattneruint64_t AliasAnalysis::getTypeStoreSize(Type *Ty) { 490f3a925dc7a14ade42da442b49c304c064954c1d4Dan Gohman return TD ? TD->getTypeStoreSize(Ty) : UnknownSize; 491fc2a3ed0c9e32cf7edaf5030fa0972b916cc5f0bDan Gohman} 492fc2a3ed0c9e32cf7edaf5030fa0972b916cc5f0bDan Gohman 49314ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner/// canBasicBlockModify - Return true if it is possible for execution of the 49414ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner/// specified basic block to modify the value pointed to by Ptr. 49514ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner/// 49614ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattnerbool AliasAnalysis::canBasicBlockModify(const BasicBlock &BB, 497b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman const Location &Loc) { 498b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman return canInstructionRangeModify(BB.front(), BB.back(), Loc); 49953ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner} 50053ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 501f9355f636b6a7d59993081766dd0481bd08f545dChris Lattner/// canInstructionRangeModify - Return true if it is possible for the execution 502f9355f636b6a7d59993081766dd0481bd08f545dChris Lattner/// of the specified instructions to modify the value pointed to by Ptr. The 503f9355f636b6a7d59993081766dd0481bd08f545dChris Lattner/// instructions to consider are all of the instructions in the range of [I1,I2] 504f9355f636b6a7d59993081766dd0481bd08f545dChris Lattner/// INCLUSIVE. I1 and I2 must be in the same basic block. 505f9355f636b6a7d59993081766dd0481bd08f545dChris Lattner/// 50653ad0edd361c724df623c082a8a37eaf762d1703Chris Lattnerbool AliasAnalysis::canInstructionRangeModify(const Instruction &I1, 50753ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner const Instruction &I2, 508b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman const Location &Loc) { 50953ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner assert(I1.getParent() == I2.getParent() && 51053ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner "Instructions not in same basic block!"); 51179fca6fea87be7221843031870bbf2c9ae1fc555Dan Gohman BasicBlock::const_iterator I = &I1; 51279fca6fea87be7221843031870bbf2c9ae1fc555Dan Gohman BasicBlock::const_iterator E = &I2; 51353ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner ++E; // Convert from inclusive to exclusive range. 51453ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 51514ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner for (; I != E; ++I) // Check every instruction in range 516b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if (getModRefInfo(I, Loc) & Mod) 51753ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner return true; 51853ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner return false; 51953ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner} 52053ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 521a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman/// isNoAliasCall - Return true if this pointer is returned by a noalias 522a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman/// function. 523a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohmanbool llvm::isNoAliasCall(const Value *V) { 524a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman if (isa<CallInst>(V) || isa<InvokeInst>(V)) 52579fca6fea87be7221843031870bbf2c9ae1fc555Dan Gohman return ImmutableCallSite(cast<Instruction>(V)) 526034b94b17006f51722886b0f2283fb6fb19aca1fBill Wendling .paramHasAttr(0, Attribute::NoAlias); 527a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman return false; 528a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman} 529a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman 5309f5de6dadcdb9922ad8c8135a29e4abccec11671Michael Kuperstein/// isNoAliasArgument - Return true if this is an argument with the noalias 5319f5de6dadcdb9922ad8c8135a29e4abccec11671Michael Kuperstein/// attribute. 5329f5de6dadcdb9922ad8c8135a29e4abccec11671Michael Kupersteinbool llvm::isNoAliasArgument(const Value *V) 5339f5de6dadcdb9922ad8c8135a29e4abccec11671Michael Kuperstein{ 5349f5de6dadcdb9922ad8c8135a29e4abccec11671Michael Kuperstein if (const Argument *A = dyn_cast<Argument>(V)) 5359f5de6dadcdb9922ad8c8135a29e4abccec11671Michael Kuperstein return A->hasNoAliasAttr(); 5369f5de6dadcdb9922ad8c8135a29e4abccec11671Michael Kuperstein return false; 5379f5de6dadcdb9922ad8c8135a29e4abccec11671Michael Kuperstein} 5389f5de6dadcdb9922ad8c8135a29e4abccec11671Michael Kuperstein 539a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman/// isIdentifiedObject - Return true if this pointer refers to a distinct and 540a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman/// identifiable object. This returns true for: 5415753a4a0033da4add45f2e9930a4e1159d92a869Dan Gohman/// Global Variables and Functions (but not Global Aliases) 542a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman/// Allocas and Mallocs 5439e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman/// ByVal and NoAlias Arguments 5449e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman/// NoAlias returns 545a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman/// 5469e86f4364b912ae743490ba01d6989acfd12c046Dan Gohmanbool llvm::isIdentifiedObject(const Value *V) { 5476be2bd516a3022721480f8fee6986617baf0944fDan Gohman if (isa<AllocaInst>(V)) 5485753a4a0033da4add45f2e9930a4e1159d92a869Dan Gohman return true; 5495753a4a0033da4add45f2e9930a4e1159d92a869Dan Gohman if (isa<GlobalValue>(V) && !isa<GlobalAlias>(V)) 550a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman return true; 5519e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman if (isNoAliasCall(V)) 5529e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman return true; 5539e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman if (const Argument *A = dyn_cast<Argument>(V)) 5549e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman return A->hasNoAliasAttr() || A->hasByValAttr(); 555a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman return false; 556a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman} 557