AliasAnalysis.cpp revision 0c7f116bb6950ef819323d855415b2f2b0aad987
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" 2881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky#include "llvm/Analysis/CFG.h" 2936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Analysis/CaptureTracking.h" 30ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "llvm/Analysis/TargetLibraryInfo.h" 313a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier#include "llvm/Analysis/ValueTracking.h" 320b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/BasicBlock.h" 330b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DataLayout.h" 3436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Dominators.h" 350b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 360b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 370b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/IntrinsicInst.h" 380b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/LLVMContext.h" 390b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Type.h" 40d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Pass.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 63c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen HinesAliasAnalysis::Location 64c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen HinesAliasAnalysis::getArgLocation(ImmutableCallSite CS, unsigned ArgIdx, 65c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines AliasAnalysis::ModRefResult &Mask) { 66c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 67c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines return AA->getArgLocation(CS, ArgIdx, Mask); 68c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines} 69c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 705a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattnervoid AliasAnalysis::deleteValue(Value *V) { 715a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 725a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner AA->deleteValue(V); 735a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner} 745a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner 755a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattnervoid AliasAnalysis::copyValue(Value *From, Value *To) { 765a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 775a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner AA->copyValue(From, To); 785a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner} 795a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner 80ab6acc6ecdc4585a55059e36d81481d1c26d3ff9Owen Andersonvoid AliasAnalysis::addEscapingUse(Use &U) { 81ab6acc6ecdc4585a55059e36d81481d1c26d3ff9Owen Anderson assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 82ab6acc6ecdc4585a55059e36d81481d1c26d3ff9Owen Anderson AA->addEscapingUse(U); 83ab6acc6ecdc4585a55059e36d81481d1c26d3ff9Owen Anderson} 84ab6acc6ecdc4585a55059e36d81481d1c26d3ff9Owen Anderson 850c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga NainarAliasAnalysis::ModRefResult 860c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga NainarAliasAnalysis::getModRefInfo(Instruction *I, ImmutableCallSite Call) { 870c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar // We may have two calls 880c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar if (auto CS = ImmutableCallSite(I)) { 890c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar // Check if the two calls modify the same memory 900c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar return getModRefInfo(Call, CS); 910c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar } else { 920c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar // Otherwise, check if the call modifies or references the 930c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar // location this memory access defines. The best we can say 940c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar // is that if the call references what this instruction 950c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar // defines, it must be clobbered by this location. 960c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar const AliasAnalysis::Location DefLoc = AA->getLocation(I); 970c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar if (getModRefInfo(Call, DefLoc) != AliasAnalysis::NoModRef) 980c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar return AliasAnalysis::ModRef; 990c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar } 1000c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar return AliasAnalysis::NoModRef; 1010c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar} 102ab6acc6ecdc4585a55059e36d81481d1c26d3ff9Owen Anderson 1035a24d70d99cc76be190ed6ebe37d09585046ddc3Chris LattnerAliasAnalysis::ModRefResult 1046ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanAliasAnalysis::getModRefInfo(ImmutableCallSite CS, 105b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman const Location &Loc) { 106852dda46251f50286b6d83425f39e20a5c7592e9Dan Gohman assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 1076ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1086ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman ModRefBehavior MRB = getModRefBehavior(CS); 1096ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (MRB == DoesNotAccessMemory) 1106ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return NoModRef; 1116ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1126ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman ModRefResult Mask = ModRef; 113c07661c1fa7fd646c1e904f2327ca7f0105fb322Dan Gohman if (onlyReadsMemory(MRB)) 1146ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman Mask = Ref; 115c07661c1fa7fd646c1e904f2327ca7f0105fb322Dan Gohman 11668a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman if (onlyAccessesArgPointees(MRB)) { 1176ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman bool doesAlias = false; 118c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines ModRefResult AllArgsMask = NoModRef; 119bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman if (doesAccessArgPointees(MRB)) { 12068a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman for (ImmutableCallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end(); 121bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman AI != AE; ++AI) { 122bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman const Value *Arg = *AI; 123bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman if (!Arg->getType()->isPointerTy()) 124bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman continue; 125c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines ModRefResult ArgMask; 126c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Location CSLoc = 127c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines getArgLocation(CS, (unsigned) std::distance(CS.arg_begin(), AI), 128c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines ArgMask); 129bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman if (!isNoAlias(CSLoc, Loc)) { 13068a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman doesAlias = true; 131c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines AllArgsMask = ModRefResult(AllArgsMask | ArgMask); 13268a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman } 133bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman } 134bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman } 1356ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (!doesAlias) 1366ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return NoModRef; 137c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Mask = ModRefResult(Mask & AllArgsMask); 1386ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman } 1396ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 140b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman // If Loc is a constant memory location, the call definitely could not 1416ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // modify the memory location. 142b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if ((Mask & Mod) && pointsToConstantMemory(Loc)) 1436ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman Mask = ModRefResult(Mask & ~Mod); 1446ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 145e46a3881fc74652b23c3b31ee487e0ca9a6a268aDan Gohman // If this is the end of the chain, don't forward. 1466ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (!AA) return Mask; 1476ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1486ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // Otherwise, fall back to the next AA in the chain. But we can merge 1496ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // in any mask we've managed to compute. 150b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman return ModRefResult(AA->getModRefInfo(CS, Loc) & Mask); 1516ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman} 1526ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1536ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanAliasAnalysis::ModRefResult 15479fca6fea87be7221843031870bbf2c9ae1fc555Dan GohmanAliasAnalysis::getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2) { 155852dda46251f50286b6d83425f39e20a5c7592e9Dan Gohman assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 1566ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1576ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // If CS1 or CS2 are readnone, they don't interact. 1586ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman ModRefBehavior CS1B = getModRefBehavior(CS1); 1596ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (CS1B == DoesNotAccessMemory) return NoModRef; 1606ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1616ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman ModRefBehavior CS2B = getModRefBehavior(CS2); 1626ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (CS2B == DoesNotAccessMemory) return NoModRef; 1636ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1646ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // If they both only read from memory, there is no dependence. 165c07661c1fa7fd646c1e904f2327ca7f0105fb322Dan Gohman if (onlyReadsMemory(CS1B) && onlyReadsMemory(CS2B)) 1666ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return NoModRef; 1676ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1686ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman AliasAnalysis::ModRefResult Mask = ModRef; 1696ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1706ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // If CS1 only reads memory, the only dependence on CS2 can be 1716ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // from CS1 reading memory written by CS2. 172c07661c1fa7fd646c1e904f2327ca7f0105fb322Dan Gohman if (onlyReadsMemory(CS1B)) 1736ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman Mask = ModRefResult(Mask & Ref); 1746ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 1756ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // If CS2 only access memory through arguments, accumulate the mod/ref 1766ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // information from CS1's references to the memory referenced by 1776ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // CS2's arguments. 17868a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman if (onlyAccessesArgPointees(CS2B)) { 1796ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman AliasAnalysis::ModRefResult R = NoModRef; 180bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman if (doesAccessArgPointees(CS2B)) { 18168a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman for (ImmutableCallSite::arg_iterator 18268a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman I = CS2.arg_begin(), E = CS2.arg_end(); I != E; ++I) { 183bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman const Value *Arg = *I; 184bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman if (!Arg->getType()->isPointerTy()) 185bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman continue; 186c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines ModRefResult ArgMask; 187c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Location CS2Loc = 188c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines getArgLocation(CS2, (unsigned) std::distance(CS2.arg_begin(), I), 189c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines ArgMask); 190c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // ArgMask indicates what CS2 might do to CS2Loc, and the dependence of 191c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // CS1 on that location is the inverse. 192c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (ArgMask == Mod) 193c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines ArgMask = ModRef; 194c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines else if (ArgMask == Ref) 195c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines ArgMask = Mod; 196c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 197c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines R = ModRefResult((R | (getModRefInfo(CS1, CS2Loc) & ArgMask)) & Mask); 19868a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman if (R == Mask) 19968a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman break; 20068a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman } 201bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman } 2026ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return R; 2036ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman } 2046ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 2056ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // If CS1 only accesses memory through arguments, check if CS2 references 2066ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // any of the memory referenced by CS1's arguments. If not, return NoModRef. 20768a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman if (onlyAccessesArgPointees(CS1B)) { 2086ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman AliasAnalysis::ModRefResult R = NoModRef; 209bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman if (doesAccessArgPointees(CS1B)) { 21068a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman for (ImmutableCallSite::arg_iterator 211bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman I = CS1.arg_begin(), E = CS1.arg_end(); I != E; ++I) { 212bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman const Value *Arg = *I; 213bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman if (!Arg->getType()->isPointerTy()) 214bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman continue; 215c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines ModRefResult ArgMask; 21637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Location CS1Loc = getArgLocation( 21737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines CS1, (unsigned)std::distance(CS1.arg_begin(), I), ArgMask); 21837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // ArgMask indicates what CS1 might do to CS1Loc; if CS1 might Mod 21937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // CS1Loc, then we care about either a Mod or a Ref by CS2. If CS1 22037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // might Ref, then we care only about a Mod by CS2. 22137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines ModRefResult ArgR = getModRefInfo(CS2, CS1Loc); 22237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (((ArgMask & Mod) != NoModRef && (ArgR & ModRef) != NoModRef) || 22337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines ((ArgMask & Ref) != NoModRef && (ArgR & Mod) != NoModRef)) 22437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines R = ModRefResult((R | ArgMask) & Mask); 22537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 22637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (R == Mask) 22768a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman break; 228bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman } 229bddc1ca18a8ca23f6f145d2f5d006fa07e72a870Dan Gohman } 23037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return R; 2316ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman } 2326ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 233e46a3881fc74652b23c3b31ee487e0ca9a6a268aDan Gohman // If this is the end of the chain, don't forward. 2346ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (!AA) return Mask; 2356ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 2366ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // Otherwise, fall back to the next AA in the chain. But we can merge 2376ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // in any mask we've managed to compute. 2386ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return ModRefResult(AA->getModRefInfo(CS1, CS2) & Mask); 2396ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman} 2406ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 2416ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanAliasAnalysis::ModRefBehavior 2426ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanAliasAnalysis::getModRefBehavior(ImmutableCallSite CS) { 243852dda46251f50286b6d83425f39e20a5c7592e9Dan Gohman assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 2446ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 2456ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman ModRefBehavior Min = UnknownModRefBehavior; 2466ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 2476ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // Call back into the alias analysis with the other form of getModRefBehavior 2486ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // to see if it can give a better response. 2496ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (const Function *F = CS.getCalledFunction()) 2506ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman Min = getModRefBehavior(F); 2516ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 252e46a3881fc74652b23c3b31ee487e0ca9a6a268aDan Gohman // If this is the end of the chain, don't forward. 2536ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (!AA) return Min; 2546ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 2556ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // Otherwise, fall back to the next AA in the chain. But we can merge 2566ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // in any result we've managed to compute. 25742c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman return ModRefBehavior(AA->getModRefBehavior(CS) & Min); 2586ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman} 2596ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 2606ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanAliasAnalysis::ModRefBehavior 2616ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanAliasAnalysis::getModRefBehavior(const Function *F) { 2625a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 2636ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return AA->getModRefBehavior(F); 2645a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner} 2655a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner 2665a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner//===----------------------------------------------------------------------===// 2675a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner// AliasAnalysis non-virtual helper method implementation 2685a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner//===----------------------------------------------------------------------===// 2695a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner 2706d8eb156e6be727570b300bac7712f745a318c7dDan GohmanAliasAnalysis::Location AliasAnalysis::getLocation(const LoadInst *LI) { 27137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines AAMDNodes AATags; 27237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines LI->getAAMetadata(AATags); 27337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 2746d8eb156e6be727570b300bac7712f745a318c7dDan Gohman return Location(LI->getPointerOperand(), 27537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines getTypeStoreSize(LI->getType()), AATags); 2766d8eb156e6be727570b300bac7712f745a318c7dDan Gohman} 2776d8eb156e6be727570b300bac7712f745a318c7dDan Gohman 2786d8eb156e6be727570b300bac7712f745a318c7dDan GohmanAliasAnalysis::Location AliasAnalysis::getLocation(const StoreInst *SI) { 27937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines AAMDNodes AATags; 28037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines SI->getAAMetadata(AATags); 28137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 2826d8eb156e6be727570b300bac7712f745a318c7dDan Gohman return Location(SI->getPointerOperand(), 28337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines getTypeStoreSize(SI->getValueOperand()->getType()), AATags); 2846d8eb156e6be727570b300bac7712f745a318c7dDan Gohman} 2856d8eb156e6be727570b300bac7712f745a318c7dDan Gohman 2866d8eb156e6be727570b300bac7712f745a318c7dDan GohmanAliasAnalysis::Location AliasAnalysis::getLocation(const VAArgInst *VI) { 28737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines AAMDNodes AATags; 28837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines VI->getAAMetadata(AATags); 28937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 29037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return Location(VI->getPointerOperand(), UnknownSize, AATags); 2916d8eb156e6be727570b300bac7712f745a318c7dDan Gohman} 2926d8eb156e6be727570b300bac7712f745a318c7dDan Gohman 29346cb5afdcd031c371c78201fb34291d9d48b2ee4Eli FriedmanAliasAnalysis::Location 29446cb5afdcd031c371c78201fb34291d9d48b2ee4Eli FriedmanAliasAnalysis::getLocation(const AtomicCmpXchgInst *CXI) { 29537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines AAMDNodes AATags; 29637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines CXI->getAAMetadata(AATags); 29737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 29846cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman return Location(CXI->getPointerOperand(), 29946cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman getTypeStoreSize(CXI->getCompareOperand()->getType()), 30037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines AATags); 30146cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman} 30246cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman 30346cb5afdcd031c371c78201fb34291d9d48b2ee4Eli FriedmanAliasAnalysis::Location 30446cb5afdcd031c371c78201fb34291d9d48b2ee4Eli FriedmanAliasAnalysis::getLocation(const AtomicRMWInst *RMWI) { 30537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines AAMDNodes AATags; 30637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RMWI->getAAMetadata(AATags); 30737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 30846cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman return Location(RMWI->getPointerOperand(), 30937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines getTypeStoreSize(RMWI->getValOperand()->getType()), AATags); 31046cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman} 311e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner 31237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen HinesAliasAnalysis::Location 313e90c5cb747631b315350e7ee7424048c7778bdf9Chris LattnerAliasAnalysis::getLocationForSource(const MemTransferInst *MTI) { 314e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner uint64_t Size = UnknownSize; 315e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner if (ConstantInt *C = dyn_cast<ConstantInt>(MTI->getLength())) 316e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner Size = C->getValue().getZExtValue(); 317e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner 31837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // memcpy/memmove can have AA tags. For memcpy, they apply 319387f28aff41bae6a81311279b203a1281eaa443aDan Gohman // to both the source and the destination. 32037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines AAMDNodes AATags; 32137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines MTI->getAAMetadata(AATags); 322387f28aff41bae6a81311279b203a1281eaa443aDan Gohman 32337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return Location(MTI->getRawSource(), Size, AATags); 324e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner} 325e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner 32637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen HinesAliasAnalysis::Location 3279dc9e81aa7412b329bbaf51a589a81475214802bChris LattnerAliasAnalysis::getLocationForDest(const MemIntrinsic *MTI) { 328e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner uint64_t Size = UnknownSize; 329e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner if (ConstantInt *C = dyn_cast<ConstantInt>(MTI->getLength())) 330e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner Size = C->getValue().getZExtValue(); 331387f28aff41bae6a81311279b203a1281eaa443aDan Gohman 33237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // memcpy/memmove can have AA tags. For memcpy, they apply 333387f28aff41bae6a81311279b203a1281eaa443aDan Gohman // to both the source and the destination. 33437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines AAMDNodes AATags; 33537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines MTI->getAAMetadata(AATags); 33637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 33737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return Location(MTI->getRawDest(), Size, AATags); 338e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner} 339e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner 340e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner 341e90c5cb747631b315350e7ee7424048c7778bdf9Chris Lattner 34214ac877e0a898ab46eeba1b0b72b8e5a9918179fChris LattnerAliasAnalysis::ModRefResult 343b2143b6247901ae4eca2192ee134564c4f5f7853Dan GohmanAliasAnalysis::getModRefInfo(const LoadInst *L, const Location &Loc) { 344667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman // Be conservative in the face of volatile/atomic. 345667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman if (!L->isUnordered()) 346b9db52dcbcf4279270eab972f3d560b4e5654260Dan Gohman return ModRef; 347b9db52dcbcf4279270eab972f3d560b4e5654260Dan Gohman 34814a498a48677eb1eaddd8329330df073224f9575Dan Gohman // If the load address doesn't alias the given address, it doesn't read 34914a498a48677eb1eaddd8329330df073224f9575Dan Gohman // or write the specified memory. 3500c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar if (Loc.Ptr && !alias(getLocation(L), Loc)) 35114a498a48677eb1eaddd8329330df073224f9575Dan Gohman return NoModRef; 35214a498a48677eb1eaddd8329330df073224f9575Dan Gohman 35314a498a48677eb1eaddd8329330df073224f9575Dan Gohman // Otherwise, a load just reads. 35414a498a48677eb1eaddd8329330df073224f9575Dan Gohman return Ref; 35514ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner} 35653ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 35714ac877e0a898ab46eeba1b0b72b8e5a9918179fChris LattnerAliasAnalysis::ModRefResult 358b2143b6247901ae4eca2192ee134564c4f5f7853Dan GohmanAliasAnalysis::getModRefInfo(const StoreInst *S, const Location &Loc) { 359667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman // Be conservative in the face of volatile/atomic. 360667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman if (!S->isUnordered()) 361b9db52dcbcf4279270eab972f3d560b4e5654260Dan Gohman return ModRef; 362b9db52dcbcf4279270eab972f3d560b4e5654260Dan Gohman 3630c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar if (Loc.Ptr) { 3640c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar // If the store address cannot alias the pointer in question, then the 3650c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar // specified memory cannot be modified by the store. 3660c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar if (!alias(getLocation(S), Loc)) 3670c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar return NoModRef; 368f4d904d7e326c9cbed497ca681b6270170fd2020Chris Lattner 3690c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar // If the pointer is a pointer to constant memory, then it could not have 3700c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar // been modified by this store. 3710c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar if (pointsToConstantMemory(Loc)) 3720c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar return NoModRef; 3730c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar 3740c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar } 37514a498a48677eb1eaddd8329330df073224f9575Dan Gohman 37614a498a48677eb1eaddd8329330df073224f9575Dan Gohman // Otherwise, a store just writes. 37714a498a48677eb1eaddd8329330df073224f9575Dan Gohman return Mod; 37853ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner} 37953ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 380e26a7b5e21a49543a727b1b2524a934e73c89772Dan GohmanAliasAnalysis::ModRefResult 381b2143b6247901ae4eca2192ee134564c4f5f7853Dan GohmanAliasAnalysis::getModRefInfo(const VAArgInst *V, const Location &Loc) { 382e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman // If the va_arg address cannot alias the pointer in question, then the 383e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman // specified memory cannot be accessed by the va_arg. 3846d8eb156e6be727570b300bac7712f745a318c7dDan Gohman if (!alias(getLocation(V), Loc)) 385e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman return NoModRef; 386e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman 387e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman // If the pointer is a pointer to constant memory, then it could not have been 388e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman // modified by this va_arg. 389b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if (pointsToConstantMemory(Loc)) 390e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman return NoModRef; 391e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman 392e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman // Otherwise, a va_arg reads and writes. 393e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman return ModRef; 394e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman} 395e26a7b5e21a49543a727b1b2524a934e73c89772Dan Gohman 39646cb5afdcd031c371c78201fb34291d9d48b2ee4Eli FriedmanAliasAnalysis::ModRefResult 39746cb5afdcd031c371c78201fb34291d9d48b2ee4Eli FriedmanAliasAnalysis::getModRefInfo(const AtomicCmpXchgInst *CX, const Location &Loc) { 39846cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman // Acquire/Release cmpxchg has properties that matter for arbitrary addresses. 39936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (CX->getSuccessOrdering() > Monotonic) 40046cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman return ModRef; 40146cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman 40246cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman // If the cmpxchg address does not alias the location, it does not access it. 40346cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman if (!alias(getLocation(CX), Loc)) 40446cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman return NoModRef; 40546cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman 40646cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman return ModRef; 40746cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman} 40846cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman 40946cb5afdcd031c371c78201fb34291d9d48b2ee4Eli FriedmanAliasAnalysis::ModRefResult 41046cb5afdcd031c371c78201fb34291d9d48b2ee4Eli FriedmanAliasAnalysis::getModRefInfo(const AtomicRMWInst *RMW, const Location &Loc) { 41146cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman // Acquire/Release atomicrmw has properties that matter for arbitrary addresses. 41246cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman if (RMW->getOrdering() > Monotonic) 41346cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman return ModRef; 41446cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman 41546cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman // If the atomicrmw address does not alias the location, it does not access it. 41646cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman if (!alias(getLocation(RMW), Loc)) 41746cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman return NoModRef; 41846cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman 41946cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman return ModRef; 42046cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman} 42146cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman 4223a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier// FIXME: this is really just shoring-up a deficiency in alias analysis. 4233a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier// BasicAA isn't willing to spend linear time determining whether an alloca 4243a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier// was captured before or after this particular call, while we are. However, 4253a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier// with a smarter AA in place, this test is just wasting compile time. 4263a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad RosierAliasAnalysis::ModRefResult 4273a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad RosierAliasAnalysis::callCapturesBefore(const Instruction *I, 4283a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier const AliasAnalysis::Location &MemLoc, 4293a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier DominatorTree *DT) { 4304c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (!DT) 4314c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return AliasAnalysis::ModRef; 4323a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier 4334c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar const Value *Object = GetUnderlyingObject(MemLoc.Ptr, *DL); 4343a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier if (!isIdentifiedObject(Object) || isa<GlobalValue>(Object) || 4353a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier isa<Constant>(Object)) 4363a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier return AliasAnalysis::ModRef; 4373a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier 4383a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier ImmutableCallSite CS(I); 4393a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier if (!CS.getInstruction() || CS.getInstruction() == Object) 4403a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier return AliasAnalysis::ModRef; 4413a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier 44237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (llvm::PointerMayBeCapturedBefore(Object, /* ReturnCaptures */ true, 44337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines /* StoreCaptures */ true, I, DT, 44437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines /* include Object */ true)) 4453a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier return AliasAnalysis::ModRef; 4463a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier 4473a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier unsigned ArgNo = 0; 44837ade2b8015d86e73c62ab48a2ce5f0ce10de708Nick Lewycky AliasAnalysis::ModRefResult R = AliasAnalysis::NoModRef; 4493a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier for (ImmutableCallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 4503a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier CI != CE; ++CI, ++ArgNo) { 4513a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier // Only look at the no-capture or byval pointer arguments. If this 4523a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier // pointer were passed to arguments that were neither of these, then it 4533a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier // couldn't be no-capture. 4543a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier if (!(*CI)->getType()->isPointerTy() || 4553a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier (!CS.doesNotCapture(ArgNo) && !CS.isByValArgument(ArgNo))) 4563a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier continue; 4573a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier 4583a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier // If this is a no-capture pointer argument, see if we can tell that it 4593a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier // is impossible to alias the pointer we're checking. If not, we have to 4603a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier // assume that the call could touch the pointer, even though it doesn't 4613a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier // escape. 46237ade2b8015d86e73c62ab48a2ce5f0ce10de708Nick Lewycky if (isNoAlias(AliasAnalysis::Location(*CI), 46337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines AliasAnalysis::Location(Object))) 46437ade2b8015d86e73c62ab48a2ce5f0ce10de708Nick Lewycky continue; 46537ade2b8015d86e73c62ab48a2ce5f0ce10de708Nick Lewycky if (CS.doesNotAccessMemory(ArgNo)) 46637ade2b8015d86e73c62ab48a2ce5f0ce10de708Nick Lewycky continue; 46737ade2b8015d86e73c62ab48a2ce5f0ce10de708Nick Lewycky if (CS.onlyReadsMemory(ArgNo)) { 46837ade2b8015d86e73c62ab48a2ce5f0ce10de708Nick Lewycky R = AliasAnalysis::Ref; 46937ade2b8015d86e73c62ab48a2ce5f0ce10de708Nick Lewycky continue; 4703a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier } 47137ade2b8015d86e73c62ab48a2ce5f0ce10de708Nick Lewycky return AliasAnalysis::ModRef; 4723a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier } 47337ade2b8015d86e73c62ab48a2ce5f0ce10de708Nick Lewycky return R; 4743a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier} 47546cb5afdcd031c371c78201fb34291d9d48b2ee4Eli Friedman 47653ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// AliasAnalysis destructor: DO NOT move this to the header file for 47753ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// AliasAnalysis or else clients of the AliasAnalysis class may not depend on 47853ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// the AliasAnalysis.o file in the current .a file, causing alias analysis 47953ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// support to not be included in the tool correctly! 48053ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// 48153ad0edd361c724df623c082a8a37eaf762d1703Chris LattnerAliasAnalysis::~AliasAnalysis() {} 48253ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 4835a56bf631eef695b04bbd306b53d6094f7616b5eDan Gohman/// InitializeAliasAnalysis - Subclasses must call this method to initialize the 48414ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner/// AliasAnalysis interface before any other methods are called. 485f9355f636b6a7d59993081766dd0481bd08f545dChris Lattner/// 4864c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarvoid AliasAnalysis::InitializeAliasAnalysis(Pass *P, const DataLayout *NewDL) { 4874c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DL = NewDL; 488ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines auto *TLIP = P->getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>(); 489ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines TLI = TLIP ? &TLIP->getTLI() : nullptr; 4905a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner AA = &P->getAnalysis<AliasAnalysis>(); 49114ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner} 49253ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 49314ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner// getAnalysisUsage - All alias analysis implementations should invoke this 494fc2a3ed0c9e32cf7edaf5030fa0972b916cc5f0bDan Gohman// directly (using AliasAnalysis::getAnalysisUsage(AU)). 49514ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattnervoid AliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 4965a24d70d99cc76be190ed6ebe37d09585046ddc3Chris Lattner AU.addRequired<AliasAnalysis>(); // All AA's chain 49714ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner} 49853ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 4993574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow/// getTypeStoreSize - Return the DataLayout store size for the given type, 500fc2a3ed0c9e32cf7edaf5030fa0972b916cc5f0bDan Gohman/// if known, or a conservative value otherwise. 501fc2a3ed0c9e32cf7edaf5030fa0972b916cc5f0bDan Gohman/// 502db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattneruint64_t AliasAnalysis::getTypeStoreSize(Type *Ty) { 50336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return DL ? DL->getTypeStoreSize(Ty) : UnknownSize; 504fc2a3ed0c9e32cf7edaf5030fa0972b916cc5f0bDan Gohman} 505fc2a3ed0c9e32cf7edaf5030fa0972b916cc5f0bDan Gohman 50614ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner/// canBasicBlockModify - Return true if it is possible for execution of the 507ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// specified basic block to modify the location Loc. 50814ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner/// 50914ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattnerbool AliasAnalysis::canBasicBlockModify(const BasicBlock &BB, 510b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman const Location &Loc) { 511ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return canInstructionRangeModRef(BB.front(), BB.back(), Loc, Mod); 51253ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner} 51353ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 514ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// canInstructionRangeModRef - Return true if it is possible for the 515ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// execution of the specified instructions to mod\ref (according to the 516ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// mode) the location Loc. The instructions to consider are all 517ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// of the instructions in the range of [I1,I2] INCLUSIVE. 518ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// I1 and I2 must be in the same basic block. 519ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesbool AliasAnalysis::canInstructionRangeModRef(const Instruction &I1, 52053ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner const Instruction &I2, 521ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const Location &Loc, 522ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const ModRefResult Mode) { 52353ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner assert(I1.getParent() == I2.getParent() && 52453ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner "Instructions not in same basic block!"); 52579fca6fea87be7221843031870bbf2c9ae1fc555Dan Gohman BasicBlock::const_iterator I = &I1; 52679fca6fea87be7221843031870bbf2c9ae1fc555Dan Gohman BasicBlock::const_iterator E = &I2; 52753ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner ++E; // Convert from inclusive to exclusive range. 52853ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 52914ac877e0a898ab46eeba1b0b72b8e5a9918179fChris Lattner for (; I != E; ++I) // Check every instruction in range 530ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (getModRefInfo(I, Loc) & Mode) 53153ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner return true; 53253ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner return false; 53353ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner} 53453ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 535a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman/// isNoAliasCall - Return true if this pointer is returned by a noalias 536a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman/// function. 537a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohmanbool llvm::isNoAliasCall(const Value *V) { 538a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman if (isa<CallInst>(V) || isa<InvokeInst>(V)) 53979fca6fea87be7221843031870bbf2c9ae1fc555Dan Gohman return ImmutableCallSite(cast<Instruction>(V)) 540034b94b17006f51722886b0f2283fb6fb19aca1fBill Wendling .paramHasAttr(0, Attribute::NoAlias); 541a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman return false; 542a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman} 543a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman 5449f5de6dadcdb9922ad8c8135a29e4abccec11671Michael Kuperstein/// isNoAliasArgument - Return true if this is an argument with the noalias 5459f5de6dadcdb9922ad8c8135a29e4abccec11671Michael Kuperstein/// attribute. 5469f5de6dadcdb9922ad8c8135a29e4abccec11671Michael Kupersteinbool llvm::isNoAliasArgument(const Value *V) 5479f5de6dadcdb9922ad8c8135a29e4abccec11671Michael Kuperstein{ 5489f5de6dadcdb9922ad8c8135a29e4abccec11671Michael Kuperstein if (const Argument *A = dyn_cast<Argument>(V)) 5499f5de6dadcdb9922ad8c8135a29e4abccec11671Michael Kuperstein return A->hasNoAliasAttr(); 5509f5de6dadcdb9922ad8c8135a29e4abccec11671Michael Kuperstein return false; 5519f5de6dadcdb9922ad8c8135a29e4abccec11671Michael Kuperstein} 5529f5de6dadcdb9922ad8c8135a29e4abccec11671Michael Kuperstein 553a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman/// isIdentifiedObject - Return true if this pointer refers to a distinct and 554a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman/// identifiable object. This returns true for: 5555753a4a0033da4add45f2e9930a4e1159d92a869Dan Gohman/// Global Variables and Functions (but not Global Aliases) 556a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman/// Allocas and Mallocs 5579e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman/// ByVal and NoAlias Arguments 5589e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman/// NoAlias returns 559a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman/// 5609e86f4364b912ae743490ba01d6989acfd12c046Dan Gohmanbool llvm::isIdentifiedObject(const Value *V) { 5616be2bd516a3022721480f8fee6986617baf0944fDan Gohman if (isa<AllocaInst>(V)) 5625753a4a0033da4add45f2e9930a4e1159d92a869Dan Gohman return true; 5635753a4a0033da4add45f2e9930a4e1159d92a869Dan Gohman if (isa<GlobalValue>(V) && !isa<GlobalAlias>(V)) 564a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman return true; 5659e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman if (isNoAliasCall(V)) 5669e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman return true; 5679e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman if (const Argument *A = dyn_cast<Argument>(V)) 5689e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman return A->hasNoAliasAttr() || A->hasByValAttr(); 569a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman return false; 570a5f81bba4ab18d6129774d4d67495f14b6f64375Dan Gohman} 57137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 57237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// isIdentifiedFunctionLocal - Return true if V is umabigously identified 57337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// at the function-level. Different IdentifiedFunctionLocals can't alias. 57437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// Further, an IdentifiedFunctionLocal can not alias with any function 57537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// arguments other than itself, which is not necessarily true for 57637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// IdentifiedObjects. 57737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesbool llvm::isIdentifiedFunctionLocal(const Value *V) 57837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines{ 57937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return isa<AllocaInst>(V) || isNoAliasCall(V) || isNoAliasArgument(V); 58037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 581