AliasAnalysis.cpp revision b2143b6247901ae4eca2192ee134564c4f5f7853
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. 39844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterAnalysisGroup<AliasAnalysis> Z("Alias Analysis"); 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) { 706ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // Don't assert AA because BasicAA calls us in order to make use of the 716ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // logic here. 726ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 736ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman ModRefBehavior MRB = getModRefBehavior(CS); 746ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (MRB == DoesNotAccessMemory) 756ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return NoModRef; 766ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 776ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman ModRefResult Mask = ModRef; 786ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (MRB == OnlyReadsMemory) 796ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman Mask = Ref; 806ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman else if (MRB == AliasAnalysis::AccessesArguments) { 816ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman bool doesAlias = false; 826ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman for (ImmutableCallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end(); 836ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman AI != AE; ++AI) 84b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if (!isNoAlias(Location(*AI), Loc)) { 856ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman doesAlias = true; 866ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman break; 876ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman } 886ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 896ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (!doesAlias) 906ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return NoModRef; 916ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman } 926ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 93b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman // If Loc is a constant memory location, the call definitely could not 946ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // modify the memory location. 95b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if ((Mask & Mod) && pointsToConstantMemory(Loc)) 966ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman Mask = ModRefResult(Mask & ~Mod); 976ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 986ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // If this is BasicAA, don't forward. 996ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (!AA) return Mask; 1006ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1016ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // Otherwise, fall back to the next AA in the chain. But we can merge 1026ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // in any mask we've managed to compute. 103b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman return ModRefResult(AA->getModRefInfo(CS, Loc) & Mask); 1046ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman} 1056ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1066ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanAliasAnalysis::ModRefResult 10779fca6fea87be7221843031870bbf2c9ae1fc555Dan GohmanAliasAnalysis::getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2) { 1086ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // Don't assert AA because BasicAA calls us in order to make use of the 1096ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // logic here. 1106ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1116ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // If CS1 or CS2 are readnone, they don't interact. 1126ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman ModRefBehavior CS1B = getModRefBehavior(CS1); 1136ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (CS1B == DoesNotAccessMemory) return NoModRef; 1146ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1156ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman ModRefBehavior CS2B = getModRefBehavior(CS2); 1166ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (CS2B == DoesNotAccessMemory) return NoModRef; 1176ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1186ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // If they both only read from memory, there is no dependence. 1196ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (CS1B == OnlyReadsMemory && CS2B == OnlyReadsMemory) 1206ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return NoModRef; 1216ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1226ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman AliasAnalysis::ModRefResult Mask = ModRef; 1236ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1246ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // If CS1 only reads memory, the only dependence on CS2 can be 1256ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // from CS1 reading memory written by CS2. 1266ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (CS1B == OnlyReadsMemory) 1276ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman Mask = ModRefResult(Mask & Ref); 1286ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1296ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // If CS2 only access memory through arguments, accumulate the mod/ref 1306ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // information from CS1's references to the memory referenced by 1316ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // CS2's arguments. 1326ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (CS2B == AccessesArguments) { 1336ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman AliasAnalysis::ModRefResult R = NoModRef; 1346ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman for (ImmutableCallSite::arg_iterator 1356ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman I = CS2.arg_begin(), E = CS2.arg_end(); I != E; ++I) { 1366ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman R = ModRefResult((R | getModRefInfo(CS1, *I, UnknownSize)) & Mask); 1376ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (R == Mask) 1386ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman break; 1396ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman } 1406ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return R; 1416ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman } 1426ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1436ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // If CS1 only accesses memory through arguments, check if CS2 references 1446ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // any of the memory referenced by CS1's arguments. If not, return NoModRef. 1456ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (CS1B == AccessesArguments) { 1466ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman AliasAnalysis::ModRefResult R = NoModRef; 1476ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman for (ImmutableCallSite::arg_iterator 1486ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman I = CS1.arg_begin(), E = CS1.arg_end(); I != E; ++I) 1496ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (getModRefInfo(CS2, *I, UnknownSize) != NoModRef) { 1506ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman R = Mask; 1516ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman break; 1526ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman } 1536ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (R == NoModRef) 1546ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return R; 1556ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman } 1566ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1576ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // If this is BasicAA, don't forward. 1586ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (!AA) return Mask; 1596ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1606ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // Otherwise, fall back to the next AA in the chain. But we can merge 1616ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // in any mask we've managed to compute. 1626ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return ModRefResult(AA->getModRefInfo(CS1, CS2) & Mask); 1636ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman} 1646ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1656ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanAliasAnalysis::ModRefBehavior 1666ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanAliasAnalysis::getModRefBehavior(ImmutableCallSite CS) { 1676ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // Don't assert AA because BasicAA calls us in order to make use of the 1686ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // logic here. 1696ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1706ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman ModRefBehavior Min = UnknownModRefBehavior; 1716ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1726ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // Call back into the alias analysis with the other form of getModRefBehavior 1736ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // to see if it can give a better response. 1746ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (const Function *F = CS.getCalledFunction()) 1756ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman Min = getModRefBehavior(F); 1766ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1776ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // If this is BasicAA, don't forward. 1786ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (!AA) return Min; 1796ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1806ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // Otherwise, fall back to the next AA in the chain. But we can merge 1816ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // in any result we've managed to compute. 1826ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return std::min(AA->getModRefBehavior(CS), Min); 1836ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman} 1846ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1856ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanAliasAnalysis::ModRefBehavior 1866ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanAliasAnalysis::getModRefBehavior(const Function *F) { 1875a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 1886ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return AA->getModRefBehavior(F); 1895a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner} 1905a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner 1915a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner//===----------------------------------------------------------------------===// 1925a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner// AliasAnalysis non-virtual helper method implementation 1935a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner//===----------------------------------------------------------------------===// 1945a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner 19514ac877e0a898ab46eeba1b0b72b8e5a9918179fChris LattnerAliasAnalysis::ModRefResult 196b2143b6247901ae4eca2192ee134564c4f5f7853Dan GohmanAliasAnalysis::getModRefInfo(const LoadInst *L, const Location &Loc) { 197b9db52dcbcf4279270eab972f3d560b4e5654260Dan Gohman // Be conservative in the face of volatile. 198b9db52dcbcf4279270eab972f3d560b4e5654260Dan Gohman if (L->isVolatile()) 199b9db52dcbcf4279270eab972f3d560b4e5654260Dan Gohman return ModRef; 200b9db52dcbcf4279270eab972f3d560b4e5654260Dan Gohman 20114a498a48677eb1eaddd8329330df073224f9575Dan Gohman // If the load address doesn't alias the given address, it doesn't read 20214a498a48677eb1eaddd8329330df073224f9575Dan Gohman // or write the specified memory. 203b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if (!alias(Location(L->getOperand(0), 204b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman getTypeStoreSize(L->getType()), 205b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman L->getMetadata(LLVMContext::MD_tbaa)), 206b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman Loc)) 20714a498a48677eb1eaddd8329330df073224f9575Dan Gohman return NoModRef; 20814a498a48677eb1eaddd8329330df073224f9575Dan Gohman 20914a498a48677eb1eaddd8329330df073224f9575Dan Gohman // Otherwise, a load just reads. 21014a498a48677eb1eaddd8329330df073224f9575Dan Gohman return Ref; 21114ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner} 21253ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 21314ac877e0a898ab46eeba1b0b72b8e5a9918179fChris LattnerAliasAnalysis::ModRefResult 214b2143b6247901ae4eca2192ee134564c4f5f7853Dan GohmanAliasAnalysis::getModRefInfo(const StoreInst *S, const Location &Loc) { 215b9db52dcbcf4279270eab972f3d560b4e5654260Dan Gohman // Be conservative in the face of volatile. 216b9db52dcbcf4279270eab972f3d560b4e5654260Dan Gohman if (S->isVolatile()) 217b9db52dcbcf4279270eab972f3d560b4e5654260Dan Gohman return ModRef; 218b9db52dcbcf4279270eab972f3d560b4e5654260Dan Gohman 2199b8639c9bd98ae08d0fe3630e2d3421a9277564aDan Gohman // If the store address cannot alias the pointer in question, then the 2209b8639c9bd98ae08d0fe3630e2d3421a9277564aDan Gohman // specified memory cannot be modified by the store. 221b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if (!alias(Location(S->getOperand(1), 222b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman getTypeStoreSize(S->getOperand(0)->getType()), 223b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman S->getMetadata(LLVMContext::MD_tbaa)), 224b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman Loc)) 225f4d904d7e326c9cbed497ca681b6270170fd2020Chris Lattner return NoModRef; 226f4d904d7e326c9cbed497ca681b6270170fd2020Chris Lattner 227f4d904d7e326c9cbed497ca681b6270170fd2020Chris Lattner // If the pointer is a pointer to constant memory, then it could not have been 228f4d904d7e326c9cbed497ca681b6270170fd2020Chris Lattner // modified by this store. 229b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if (pointsToConstantMemory(Loc)) 23014a498a48677eb1eaddd8329330df073224f9575Dan Gohman return NoModRef; 23114a498a48677eb1eaddd8329330df073224f9575Dan Gohman 23214a498a48677eb1eaddd8329330df073224f9575Dan Gohman // Otherwise, a store just writes. 23314a498a48677eb1eaddd8329330df073224f9575Dan Gohman return Mod; 23453ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner} 23553ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 236e26a7b5e21a49543a727b1b2524a934e73c89772Dan GohmanAliasAnalysis::ModRefResult 237b2143b6247901ae4eca2192ee134564c4f5f7853Dan GohmanAliasAnalysis::getModRefInfo(const VAArgInst *V, const Location &Loc) { 238e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman // If the va_arg address cannot alias the pointer in question, then the 239e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman // specified memory cannot be accessed by the va_arg. 240b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if (!alias(Location(V->getOperand(0), 241b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman UnknownSize, 242b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman V->getMetadata(LLVMContext::MD_tbaa)), 243b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman Loc)) 244e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman return NoModRef; 245e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman 246e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman // If the pointer is a pointer to constant memory, then it could not have been 247e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman // modified by this va_arg. 248b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if (pointsToConstantMemory(Loc)) 249e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman return NoModRef; 250e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman 251e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman // Otherwise, a va_arg reads and writes. 252e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman return ModRef; 253e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman} 254e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman 255dff6710717b159f089c76a07eda074eb6347eb92Duncan SandsAliasAnalysis::ModRefBehavior 25679fca6fea87be7221843031870bbf2c9ae1fc555Dan GohmanAliasAnalysis::getIntrinsicModRefBehavior(unsigned iid) { 257d869b3847f1dee78e1e4e1ed3cb41bd3ab0a079cDuncan Sands#define GET_INTRINSIC_MODREF_BEHAVIOR 258d869b3847f1dee78e1e4e1ed3cb41bd3ab0a079cDuncan Sands#include "llvm/Intrinsics.gen" 259d869b3847f1dee78e1e4e1ed3cb41bd3ab0a079cDuncan Sands#undef GET_INTRINSIC_MODREF_BEHAVIOR 260dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands} 261dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands 26253ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// AliasAnalysis destructor: DO NOT move this to the header file for 26353ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// AliasAnalysis or else clients of the AliasAnalysis class may not depend on 26453ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// the AliasAnalysis.o file in the current .a file, causing alias analysis 26553ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// support to not be included in the tool correctly! 26653ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// 26753ad0edd361c724df623c082a8a37eaf762d1703Chris LattnerAliasAnalysis::~AliasAnalysis() {} 26853ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 2695a56bf631eef695b04bbd306b53d6094f7616b5eDan Gohman/// InitializeAliasAnalysis - Subclasses must call this method to initialize the 27014ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner/// AliasAnalysis interface before any other methods are called. 271f9355f636b6a7d59993081766dd0481bd08f545dChris Lattner/// 27214ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattnervoid AliasAnalysis::InitializeAliasAnalysis(Pass *P) { 273fc2a3ed0c9e32cf7edaf5030fa0972b916cc5f0bDan Gohman TD = P->getAnalysisIfAvailable<TargetData>(); 2745a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner AA = &P->getAnalysis<AliasAnalysis>(); 27514ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner} 27653ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 27714ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner// getAnalysisUsage - All alias analysis implementations should invoke this 278fc2a3ed0c9e32cf7edaf5030fa0972b916cc5f0bDan Gohman// directly (using AliasAnalysis::getAnalysisUsage(AU)). 27914ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattnervoid AliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 2805a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner AU.addRequired<AliasAnalysis>(); // All AA's chain 28114ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner} 28253ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 283fc2a3ed0c9e32cf7edaf5030fa0972b916cc5f0bDan Gohman/// getTypeStoreSize - Return the TargetData store size for the given type, 284fc2a3ed0c9e32cf7edaf5030fa0972b916cc5f0bDan Gohman/// if known, or a conservative value otherwise. 285fc2a3ed0c9e32cf7edaf5030fa0972b916cc5f0bDan Gohman/// 286fc2a3ed0c9e32cf7edaf5030fa0972b916cc5f0bDan Gohmanunsigned AliasAnalysis::getTypeStoreSize(const Type *Ty) { 287fc2a3ed0c9e32cf7edaf5030fa0972b916cc5f0bDan Gohman return TD ? TD->getTypeStoreSize(Ty) : ~0u; 288fc2a3ed0c9e32cf7edaf5030fa0972b916cc5f0bDan Gohman} 289fc2a3ed0c9e32cf7edaf5030fa0972b916cc5f0bDan Gohman 29014ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner/// canBasicBlockModify - Return true if it is possible for execution of the 29114ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner/// specified basic block to modify the value pointed to by Ptr. 29214ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner/// 29314ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattnerbool AliasAnalysis::canBasicBlockModify(const BasicBlock &BB, 294b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman const Location &Loc) { 295b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman return canInstructionRangeModify(BB.front(), BB.back(), Loc); 29653ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner} 29753ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 298f9355f636b6a7d59993081766dd0481bd08f545dChris Lattner/// canInstructionRangeModify - Return true if it is possible for the execution 299f9355f636b6a7d59993081766dd0481bd08f545dChris Lattner/// of the specified instructions to modify the value pointed to by Ptr. The 300f9355f636b6a7d59993081766dd0481bd08f545dChris Lattner/// instructions to consider are all of the instructions in the range of [I1,I2] 301f9355f636b6a7d59993081766dd0481bd08f545dChris Lattner/// INCLUSIVE. I1 and I2 must be in the same basic block. 302f9355f636b6a7d59993081766dd0481bd08f545dChris Lattner/// 30353ad0edd361c724df623c082a8a37eaf762d1703Chris Lattnerbool AliasAnalysis::canInstructionRangeModify(const Instruction &I1, 30453ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner const Instruction &I2, 305b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman const Location &Loc) { 30653ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner assert(I1.getParent() == I2.getParent() && 30753ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner "Instructions not in same basic block!"); 30879fca6fea87be7221843031870bbf2c9ae1fc555Dan Gohman BasicBlock::const_iterator I = &I1; 30979fca6fea87be7221843031870bbf2c9ae1fc555Dan Gohman BasicBlock::const_iterator E = &I2; 31053ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner ++E; // Convert from inclusive to exclusive range. 31153ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 31214ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner for (; I != E; ++I) // Check every instruction in range 313b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if (getModRefInfo(I, Loc) & Mod) 31453ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner return true; 31553ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner return false; 31653ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner} 31753ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 318a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman/// isNoAliasCall - Return true if this pointer is returned by a noalias 319a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman/// function. 320a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohmanbool llvm::isNoAliasCall(const Value *V) { 321a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman if (isa<CallInst>(V) || isa<InvokeInst>(V)) 32279fca6fea87be7221843031870bbf2c9ae1fc555Dan Gohman return ImmutableCallSite(cast<Instruction>(V)) 323a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman .paramHasAttr(0, Attribute::NoAlias); 324a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman return false; 325a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman} 326a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman 327a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman/// isIdentifiedObject - Return true if this pointer refers to a distinct and 328a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman/// identifiable object. This returns true for: 3295753a4a0033da4add45f2e9930a4e1159d92a869Dan Gohman/// Global Variables and Functions (but not Global Aliases) 330a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman/// Allocas and Mallocs 3319e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman/// ByVal and NoAlias Arguments 3329e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman/// NoAlias returns 333a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman/// 3349e86f4364b912ae743490ba01d6989acfd12c046Dan Gohmanbool llvm::isIdentifiedObject(const Value *V) { 3356be2bd516a3022721480f8fee6986617baf0944fDan Gohman if (isa<AllocaInst>(V)) 3365753a4a0033da4add45f2e9930a4e1159d92a869Dan Gohman return true; 3375753a4a0033da4add45f2e9930a4e1159d92a869Dan Gohman if (isa<GlobalValue>(V) && !isa<GlobalAlias>(V)) 338a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman return true; 3399e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman if (isNoAliasCall(V)) 3409e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman return true; 3419e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman if (const Argument *A = dyn_cast<Argument>(V)) 3429e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman return A->hasNoAliasAttr() || A->hasByValAttr(); 343a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman return false; 344a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman} 345a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman 346d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner// Because of the way .a files work, we must force the BasicAA implementation to 347d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner// be pulled in if the AliasAnalysis classes are pulled in. Otherwise we run 348d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner// the risk of AliasAnalysis being used, but the default implementation not 349d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner// being linked into the tool that uses it. 3504f1bd9e9963239c119db70070db1d68286b3de7eReid SpencerDEFINING_FILE_FOR(AliasAnalysis) 351