AliasAnalysis.cpp revision e46a3881fc74652b23c3b31ee487e0ca9a6a268a
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" 286df60a9effe4d20a48cfd9d105c0ab3c5dc3e690Reid Spencer#include "llvm/Pass.h" 2953ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner#include "llvm/BasicBlock.h" 30dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands#include "llvm/Function.h" 31cd89525434810af74d2d3f882f0e0ac5c677e341Owen Anderson#include "llvm/IntrinsicInst.h" 3247b14a4a6a455c7be169cfd312fcbe796f0ad426Misha Brukman#include "llvm/Instructions.h" 33b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman#include "llvm/LLVMContext.h" 345b3a4553c1da7e417a240379e2f510c77532c5c1Chris Lattner#include "llvm/Type.h" 3514ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner#include "llvm/Target/TargetData.h" 36992860c44ed8d8b82c6b7fde6645123772965c65Chris Lattnerusing namespace llvm; 37d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 3853ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// Register the AliasAnalysis interface, providing a nice name to refer to. 39081c34b725980f995be9080eaec24cd3dfaaf065Owen AndersonINITIALIZE_ANALYSIS_GROUP(AliasAnalysis, "Alias Analysis", NoAA) 401997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar AliasAnalysis::ID = 0; 4153ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 425a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner//===----------------------------------------------------------------------===// 435a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner// Default chaining methods 445a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner//===----------------------------------------------------------------------===// 455a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner 465a24d70d99cc76be190ed6ebe37d09585046ddc3Chris LattnerAliasAnalysis::AliasResult 47b2143b6247901ae4eca2192ee134564c4f5f7853Dan GohmanAliasAnalysis::alias(const Location &LocA, const Location &LocB) { 485a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 49b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman return AA->alias(LocA, LocB); 505a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner} 515a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner 52b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohmanbool AliasAnalysis::pointsToConstantMemory(const Location &Loc) { 535a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 54b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman return AA->pointsToConstantMemory(Loc); 555a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner} 565a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner 575a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattnervoid AliasAnalysis::deleteValue(Value *V) { 585a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 595a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner AA->deleteValue(V); 605a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner} 615a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner 625a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattnervoid AliasAnalysis::copyValue(Value *From, Value *To) { 635a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 645a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner AA->copyValue(From, To); 655a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner} 665a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner 675a24d70d99cc76be190ed6ebe37d09585046ddc3Chris LattnerAliasAnalysis::ModRefResult 686ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanAliasAnalysis::getModRefInfo(ImmutableCallSite CS, 69b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman const Location &Loc) { 70852dda46251f50286b6d83425f39e20a5c7592e9Dan Gohman assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 716ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 726ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman ModRefBehavior MRB = getModRefBehavior(CS); 736ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (MRB == DoesNotAccessMemory) 746ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return NoModRef; 756ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 766ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman ModRefResult Mask = ModRef; 776ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (MRB == OnlyReadsMemory) 786ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman Mask = Ref; 796ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman else if (MRB == AliasAnalysis::AccessesArguments) { 806ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman bool doesAlias = false; 816ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman for (ImmutableCallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end(); 826ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman AI != AE; ++AI) 83b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if (!isNoAlias(Location(*AI), Loc)) { 846ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman doesAlias = true; 856ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman break; 866ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman } 876ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 886ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (!doesAlias) 896ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return NoModRef; 906ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman } 916ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 92b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman // If Loc is a constant memory location, the call definitely could not 936ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // modify the memory location. 94b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if ((Mask & Mod) && pointsToConstantMemory(Loc)) 956ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman Mask = ModRefResult(Mask & ~Mod); 966ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 97e46a3881fc74652b23c3b31ee487e0ca9a6a268aDan Gohman // If this is the end of the chain, don't forward. 986ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (!AA) return Mask; 996ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1006ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // Otherwise, fall back to the next AA in the chain. But we can merge 1016ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // in any mask we've managed to compute. 102b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman return ModRefResult(AA->getModRefInfo(CS, Loc) & Mask); 1036ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman} 1046ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1056ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanAliasAnalysis::ModRefResult 10679fca6fea87be7221843031870bbf2c9ae1fc555Dan GohmanAliasAnalysis::getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2) { 107852dda46251f50286b6d83425f39e20a5c7592e9Dan Gohman assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 1086ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1096ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // If CS1 or CS2 are readnone, they don't interact. 1106ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman ModRefBehavior CS1B = getModRefBehavior(CS1); 1116ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (CS1B == DoesNotAccessMemory) return NoModRef; 1126ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1136ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman ModRefBehavior CS2B = getModRefBehavior(CS2); 1146ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (CS2B == DoesNotAccessMemory) return NoModRef; 1156ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1166ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // If they both only read from memory, there is no dependence. 1176ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (CS1B == OnlyReadsMemory && CS2B == OnlyReadsMemory) 1186ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return NoModRef; 1196ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1206ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman AliasAnalysis::ModRefResult Mask = ModRef; 1216ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1226ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // If CS1 only reads memory, the only dependence on CS2 can be 1236ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // from CS1 reading memory written by CS2. 1246ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (CS1B == OnlyReadsMemory) 1256ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman Mask = ModRefResult(Mask & Ref); 1266ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1276ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // If CS2 only access memory through arguments, accumulate the mod/ref 1286ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // information from CS1's references to the memory referenced by 1296ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // CS2's arguments. 1306ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (CS2B == AccessesArguments) { 1316ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman AliasAnalysis::ModRefResult R = NoModRef; 1326ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman for (ImmutableCallSite::arg_iterator 1336ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman I = CS2.arg_begin(), E = CS2.arg_end(); I != E; ++I) { 1346ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman R = ModRefResult((R | getModRefInfo(CS1, *I, UnknownSize)) & Mask); 1356ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (R == Mask) 1366ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman break; 1376ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman } 1386ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return R; 1396ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman } 1406ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1416ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // If CS1 only accesses memory through arguments, check if CS2 references 1426ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // any of the memory referenced by CS1's arguments. If not, return NoModRef. 1436ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (CS1B == AccessesArguments) { 1446ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman AliasAnalysis::ModRefResult R = NoModRef; 1456ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman for (ImmutableCallSite::arg_iterator 1466ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman I = CS1.arg_begin(), E = CS1.arg_end(); I != E; ++I) 1476ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (getModRefInfo(CS2, *I, UnknownSize) != NoModRef) { 1486ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman R = Mask; 1496ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman break; 1506ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman } 1516ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (R == NoModRef) 1526ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return R; 1536ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman } 1546ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 155e46a3881fc74652b23c3b31ee487e0ca9a6a268aDan Gohman // If this is the end of the chain, don't forward. 1566ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (!AA) return Mask; 1576ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1586ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // Otherwise, fall back to the next AA in the chain. But we can merge 1596ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // in any mask we've managed to compute. 1606ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return ModRefResult(AA->getModRefInfo(CS1, CS2) & Mask); 1616ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman} 1626ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1636ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanAliasAnalysis::ModRefBehavior 1646ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanAliasAnalysis::getModRefBehavior(ImmutableCallSite CS) { 165852dda46251f50286b6d83425f39e20a5c7592e9Dan Gohman assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 1666ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1676ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman ModRefBehavior Min = UnknownModRefBehavior; 1686ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1696ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // Call back into the alias analysis with the other form of getModRefBehavior 1706ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // to see if it can give a better response. 1716ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (const Function *F = CS.getCalledFunction()) 1726ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman Min = getModRefBehavior(F); 1736ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 174e46a3881fc74652b23c3b31ee487e0ca9a6a268aDan Gohman // If this is the end of the chain, don't forward. 1756ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (!AA) return Min; 1766ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1776ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // Otherwise, fall back to the next AA in the chain. But we can merge 1786ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // in any result we've managed to compute. 1796ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return std::min(AA->getModRefBehavior(CS), Min); 1806ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman} 1816ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1826ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanAliasAnalysis::ModRefBehavior 1836ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanAliasAnalysis::getModRefBehavior(const Function *F) { 1845a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 1856ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return AA->getModRefBehavior(F); 1865a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner} 1875a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner 1885a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner//===----------------------------------------------------------------------===// 1895a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner// AliasAnalysis non-virtual helper method implementation 1905a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner//===----------------------------------------------------------------------===// 1915a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner 19214ac877e0a898ab46eeba1b0b72b8e5a9918179fChris LattnerAliasAnalysis::ModRefResult 193b2143b6247901ae4eca2192ee134564c4f5f7853Dan GohmanAliasAnalysis::getModRefInfo(const LoadInst *L, const Location &Loc) { 194b9db52dcbcf4279270eab972f3d560b4e5654260Dan Gohman // Be conservative in the face of volatile. 195b9db52dcbcf4279270eab972f3d560b4e5654260Dan Gohman if (L->isVolatile()) 196b9db52dcbcf4279270eab972f3d560b4e5654260Dan Gohman return ModRef; 197b9db52dcbcf4279270eab972f3d560b4e5654260Dan Gohman 19814a498a48677eb1eaddd8329330df073224f9575Dan Gohman // If the load address doesn't alias the given address, it doesn't read 19914a498a48677eb1eaddd8329330df073224f9575Dan Gohman // or write the specified memory. 200b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if (!alias(Location(L->getOperand(0), 201b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman getTypeStoreSize(L->getType()), 202b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman L->getMetadata(LLVMContext::MD_tbaa)), 203b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman Loc)) 20414a498a48677eb1eaddd8329330df073224f9575Dan Gohman return NoModRef; 20514a498a48677eb1eaddd8329330df073224f9575Dan Gohman 20614a498a48677eb1eaddd8329330df073224f9575Dan Gohman // Otherwise, a load just reads. 20714a498a48677eb1eaddd8329330df073224f9575Dan Gohman return Ref; 20814ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner} 20953ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 21014ac877e0a898ab46eeba1b0b72b8e5a9918179fChris LattnerAliasAnalysis::ModRefResult 211b2143b6247901ae4eca2192ee134564c4f5f7853Dan GohmanAliasAnalysis::getModRefInfo(const StoreInst *S, const Location &Loc) { 212b9db52dcbcf4279270eab972f3d560b4e5654260Dan Gohman // Be conservative in the face of volatile. 213b9db52dcbcf4279270eab972f3d560b4e5654260Dan Gohman if (S->isVolatile()) 214b9db52dcbcf4279270eab972f3d560b4e5654260Dan Gohman return ModRef; 215b9db52dcbcf4279270eab972f3d560b4e5654260Dan Gohman 2169b8639c9bd98ae08d0fe3630e2d3421a9277564aDan Gohman // If the store address cannot alias the pointer in question, then the 2179b8639c9bd98ae08d0fe3630e2d3421a9277564aDan Gohman // specified memory cannot be modified by the store. 218b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if (!alias(Location(S->getOperand(1), 219b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman getTypeStoreSize(S->getOperand(0)->getType()), 220b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman S->getMetadata(LLVMContext::MD_tbaa)), 221b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman Loc)) 222f4d904d7e326c9cbed497ca681b6270170fd2020Chris Lattner return NoModRef; 223f4d904d7e326c9cbed497ca681b6270170fd2020Chris Lattner 224f4d904d7e326c9cbed497ca681b6270170fd2020Chris Lattner // If the pointer is a pointer to constant memory, then it could not have been 225f4d904d7e326c9cbed497ca681b6270170fd2020Chris Lattner // modified by this store. 226b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if (pointsToConstantMemory(Loc)) 22714a498a48677eb1eaddd8329330df073224f9575Dan Gohman return NoModRef; 22814a498a48677eb1eaddd8329330df073224f9575Dan Gohman 22914a498a48677eb1eaddd8329330df073224f9575Dan Gohman // Otherwise, a store just writes. 23014a498a48677eb1eaddd8329330df073224f9575Dan Gohman return Mod; 23153ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner} 23253ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 233e26a7b5e21a49543a727b1b2524a934e73c89772Dan GohmanAliasAnalysis::ModRefResult 234b2143b6247901ae4eca2192ee134564c4f5f7853Dan GohmanAliasAnalysis::getModRefInfo(const VAArgInst *V, const Location &Loc) { 235e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman // If the va_arg address cannot alias the pointer in question, then the 236e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman // specified memory cannot be accessed by the va_arg. 237b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if (!alias(Location(V->getOperand(0), 238b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman UnknownSize, 239b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman V->getMetadata(LLVMContext::MD_tbaa)), 240b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman Loc)) 241e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman return NoModRef; 242e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman 243e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman // If the pointer is a pointer to constant memory, then it could not have been 244e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman // modified by this va_arg. 245b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if (pointsToConstantMemory(Loc)) 246e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman return NoModRef; 247e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman 248e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman // Otherwise, a va_arg reads and writes. 249e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman return ModRef; 250e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman} 251e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman 252dff6710717b159f089c76a07eda074eb6347eb92Duncan SandsAliasAnalysis::ModRefBehavior 25379fca6fea87be7221843031870bbf2c9ae1fc555Dan GohmanAliasAnalysis::getIntrinsicModRefBehavior(unsigned iid) { 254d869b3847f1dee78e1e4e1ed3cb41bd3ab0a079cDuncan Sands#define GET_INTRINSIC_MODREF_BEHAVIOR 255d869b3847f1dee78e1e4e1ed3cb41bd3ab0a079cDuncan Sands#include "llvm/Intrinsics.gen" 256d869b3847f1dee78e1e4e1ed3cb41bd3ab0a079cDuncan Sands#undef GET_INTRINSIC_MODREF_BEHAVIOR 257dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands} 258dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands 25953ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// AliasAnalysis destructor: DO NOT move this to the header file for 26053ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// AliasAnalysis or else clients of the AliasAnalysis class may not depend on 26153ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// the AliasAnalysis.o file in the current .a file, causing alias analysis 26253ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// support to not be included in the tool correctly! 26353ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// 26453ad0edd361c724df623c082a8a37eaf762d1703Chris LattnerAliasAnalysis::~AliasAnalysis() {} 26553ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 2665a56bf631eef695b04bbd306b53d6094f7616b5eDan Gohman/// InitializeAliasAnalysis - Subclasses must call this method to initialize the 26714ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner/// AliasAnalysis interface before any other methods are called. 268f9355f636b6a7d59993081766dd0481bd08f545dChris Lattner/// 26914ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattnervoid AliasAnalysis::InitializeAliasAnalysis(Pass *P) { 270fc2a3ed0c9e32cf7edaf5030fa0972b916cc5f0bDan Gohman TD = P->getAnalysisIfAvailable<TargetData>(); 2715a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner AA = &P->getAnalysis<AliasAnalysis>(); 27214ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner} 27353ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 27414ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner// getAnalysisUsage - All alias analysis implementations should invoke this 275fc2a3ed0c9e32cf7edaf5030fa0972b916cc5f0bDan Gohman// directly (using AliasAnalysis::getAnalysisUsage(AU)). 27614ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattnervoid AliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 2775a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner AU.addRequired<AliasAnalysis>(); // All AA's chain 27814ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner} 27953ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 280fc2a3ed0c9e32cf7edaf5030fa0972b916cc5f0bDan Gohman/// getTypeStoreSize - Return the TargetData store size for the given type, 281fc2a3ed0c9e32cf7edaf5030fa0972b916cc5f0bDan Gohman/// if known, or a conservative value otherwise. 282fc2a3ed0c9e32cf7edaf5030fa0972b916cc5f0bDan Gohman/// 2833da848bbda62b25c12335998aaa44ab361f0bf15Dan Gohmanuint64_t AliasAnalysis::getTypeStoreSize(const Type *Ty) { 284f3a925dc7a14ade42da442b49c304c064954c1d4Dan Gohman return TD ? TD->getTypeStoreSize(Ty) : UnknownSize; 285fc2a3ed0c9e32cf7edaf5030fa0972b916cc5f0bDan Gohman} 286fc2a3ed0c9e32cf7edaf5030fa0972b916cc5f0bDan Gohman 28714ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner/// canBasicBlockModify - Return true if it is possible for execution of the 28814ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner/// specified basic block to modify the value pointed to by Ptr. 28914ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner/// 29014ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattnerbool AliasAnalysis::canBasicBlockModify(const BasicBlock &BB, 291b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman const Location &Loc) { 292b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman return canInstructionRangeModify(BB.front(), BB.back(), Loc); 29353ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner} 29453ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 295f9355f636b6a7d59993081766dd0481bd08f545dChris Lattner/// canInstructionRangeModify - Return true if it is possible for the execution 296f9355f636b6a7d59993081766dd0481bd08f545dChris Lattner/// of the specified instructions to modify the value pointed to by Ptr. The 297f9355f636b6a7d59993081766dd0481bd08f545dChris Lattner/// instructions to consider are all of the instructions in the range of [I1,I2] 298f9355f636b6a7d59993081766dd0481bd08f545dChris Lattner/// INCLUSIVE. I1 and I2 must be in the same basic block. 299f9355f636b6a7d59993081766dd0481bd08f545dChris Lattner/// 30053ad0edd361c724df623c082a8a37eaf762d1703Chris Lattnerbool AliasAnalysis::canInstructionRangeModify(const Instruction &I1, 30153ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner const Instruction &I2, 302b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman const Location &Loc) { 30353ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner assert(I1.getParent() == I2.getParent() && 30453ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner "Instructions not in same basic block!"); 30579fca6fea87be7221843031870bbf2c9ae1fc555Dan Gohman BasicBlock::const_iterator I = &I1; 30679fca6fea87be7221843031870bbf2c9ae1fc555Dan Gohman BasicBlock::const_iterator E = &I2; 30753ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner ++E; // Convert from inclusive to exclusive range. 30853ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 30914ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner for (; I != E; ++I) // Check every instruction in range 310b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if (getModRefInfo(I, Loc) & Mod) 31153ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner return true; 31253ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner return false; 31353ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner} 31453ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 315a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman/// isNoAliasCall - Return true if this pointer is returned by a noalias 316a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman/// function. 317a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohmanbool llvm::isNoAliasCall(const Value *V) { 318a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman if (isa<CallInst>(V) || isa<InvokeInst>(V)) 31979fca6fea87be7221843031870bbf2c9ae1fc555Dan Gohman return ImmutableCallSite(cast<Instruction>(V)) 320a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman .paramHasAttr(0, Attribute::NoAlias); 321a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman return false; 322a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman} 323a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman 324a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman/// isIdentifiedObject - Return true if this pointer refers to a distinct and 325a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman/// identifiable object. This returns true for: 3265753a4a0033da4add45f2e9930a4e1159d92a869Dan Gohman/// Global Variables and Functions (but not Global Aliases) 327a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman/// Allocas and Mallocs 3289e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman/// ByVal and NoAlias Arguments 3299e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman/// NoAlias returns 330a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman/// 3319e86f4364b912ae743490ba01d6989acfd12c046Dan Gohmanbool llvm::isIdentifiedObject(const Value *V) { 3326be2bd516a3022721480f8fee6986617baf0944fDan Gohman if (isa<AllocaInst>(V)) 3335753a4a0033da4add45f2e9930a4e1159d92a869Dan Gohman return true; 3345753a4a0033da4add45f2e9930a4e1159d92a869Dan Gohman if (isa<GlobalValue>(V) && !isa<GlobalAlias>(V)) 335a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman return true; 3369e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman if (isNoAliasCall(V)) 3379e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman return true; 3389e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman if (const Argument *A = dyn_cast<Argument>(V)) 3399e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman return A->hasNoAliasAttr() || A->hasByValAttr(); 340a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman return false; 341a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman} 342