1029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner//===- LibCallAliasAnalysis.cpp - Implement AliasAnalysis for libcalls ----===// 2029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner// 3029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner// The LLVM Compiler Infrastructure 4029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner// 5029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner// This file is distributed under the University of Illinois Open Source 6029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner// License. See LICENSE.TXT for details. 7029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner// 8029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner//===----------------------------------------------------------------------===// 9029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner// 10029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner// This file implements the LibCallAliasAnalysis class. 11029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner// 12029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner//===----------------------------------------------------------------------===// 13029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner 145c490610a166a31b4a34c9fcaebbf744fd524049Chris Lattner#include "llvm/Analysis/LibCallAliasAnalysis.h" 15029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner#include "llvm/Analysis/LibCallSemantics.h" 16d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/Passes.h" 170b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 18029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner#include "llvm/Pass.h" 19029840c93521f5c54380e037a66216c8227ad1e1Chris Lattnerusing namespace llvm; 20029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner 21d208a803a614a0ce6d5a8c6df045fd130f5dfed7Dan Gohman// Register this pass... 22d208a803a614a0ce6d5a8c6df045fd130f5dfed7Dan Gohmanchar LibCallAliasAnalysis::ID = 0; 23d8cc7be0262092882d848a1c7d8a4cb6752cce6fOwen AndersonINITIALIZE_AG_PASS(LibCallAliasAnalysis, AliasAnalysis, "libcall-aa", 24ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "LibCall Alias Analysis", false, true, false) 25029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner 26029840c93521f5c54380e037a66216c8227ad1e1Chris LattnerFunctionPass *llvm::createLibCallAliasAnalysisPass(LibCallInfo *LCI) { 27029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner return new LibCallAliasAnalysis(LCI); 28029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner} 29029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner 305c490610a166a31b4a34c9fcaebbf744fd524049Chris LattnerLibCallAliasAnalysis::~LibCallAliasAnalysis() { 315c490610a166a31b4a34c9fcaebbf744fd524049Chris Lattner delete LCI; 325c490610a166a31b4a34c9fcaebbf744fd524049Chris Lattner} 335c490610a166a31b4a34c9fcaebbf744fd524049Chris Lattner 345c490610a166a31b4a34c9fcaebbf744fd524049Chris Lattnervoid LibCallAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 355c490610a166a31b4a34c9fcaebbf744fd524049Chris Lattner AliasAnalysis::getAnalysisUsage(AU); 365c490610a166a31b4a34c9fcaebbf744fd524049Chris Lattner AU.setPreservesAll(); // Does not transform code 375c490610a166a31b4a34c9fcaebbf744fd524049Chris Lattner} 385c490610a166a31b4a34c9fcaebbf744fd524049Chris Lattner 395c490610a166a31b4a34c9fcaebbf744fd524049Chris Lattner 40029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner 41029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner/// AnalyzeLibCallDetails - Given a call to a function with the specified 42029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner/// LibCallFunctionInfo, see if we can improve the mod/ref footprint of the call 43029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner/// vs the specified pointer/size. 44029840c93521f5c54380e037a66216c8227ad1e1Chris LattnerAliasAnalysis::ModRefResult 45029840c93521f5c54380e037a66216c8227ad1e1Chris LattnerLibCallAliasAnalysis::AnalyzeLibCallDetails(const LibCallFunctionInfo *FI, 46b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman ImmutableCallSite CS, 47b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman const Location &Loc) { 48029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner // If we have a function, check to see what kind of mod/ref effects it 49029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner // has. Start by including any info globally known about the function. 50029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner AliasAnalysis::ModRefResult MRInfo = FI->UniversalBehavior; 51029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner if (MRInfo == NoModRef) return MRInfo; 52029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner 53029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner // If that didn't tell us that the function is 'readnone', check to see 54029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner // if we have detailed info and if 'P' is any of the locations we know 55029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner // about. 56029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner const LibCallFunctionInfo::LocationMRInfo *Details = FI->LocationDetails; 57029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner if (Details == 0) 58029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner return MRInfo; 59029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner 60029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner // If the details array is of the 'DoesNot' kind, we only know something if 61029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner // the pointer is a match for one of the locations in 'Details'. If we find a 62029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner // match, we can prove some interactions cannot happen. 63029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner // 64029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner if (FI->DetailsType == LibCallFunctionInfo::DoesNot) { 65029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner // Find out if the pointer refers to a known location. 66029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner for (unsigned i = 0; Details[i].LocationID != ~0U; ++i) { 67b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman const LibCallLocationInfo &LocInfo = 68029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner LCI->getLocationInfo(Details[i].LocationID); 69b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman LibCallLocationInfo::LocResult Res = LocInfo.isLocation(CS, Loc); 70029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner if (Res != LibCallLocationInfo::Yes) continue; 71029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner 72029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner // If we find a match against a location that we 'do not' interact with, 73029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner // learn this info into MRInfo. 74029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner return ModRefResult(MRInfo & ~Details[i].MRInfo); 75029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner } 76029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner return MRInfo; 77029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner } 78029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner 79029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner // If the details are of the 'DoesOnly' sort, we know something if the pointer 80029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner // is a match for one of the locations in 'Details'. Also, if we can prove 81029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner // that the pointers is *not* one of the locations in 'Details', we know that 82029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner // the call is NoModRef. 83029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner assert(FI->DetailsType == LibCallFunctionInfo::DoesOnly); 84029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner 85029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner // Find out if the pointer refers to a known location. 86029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner bool NoneMatch = true; 87029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner for (unsigned i = 0; Details[i].LocationID != ~0U; ++i) { 88b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman const LibCallLocationInfo &LocInfo = 89029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner LCI->getLocationInfo(Details[i].LocationID); 90b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman LibCallLocationInfo::LocResult Res = LocInfo.isLocation(CS, Loc); 91029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner if (Res == LibCallLocationInfo::No) continue; 92029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner 93029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner // If we don't know if this pointer points to the location, then we have to 94029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner // assume it might alias in some case. 95029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner if (Res == LibCallLocationInfo::Unknown) { 96029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner NoneMatch = false; 97029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner continue; 98029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner } 99029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner 100029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner // If we know that this pointer definitely is pointing into the location, 101029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner // merge in this information. 102029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner return ModRefResult(MRInfo & Details[i].MRInfo); 103029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner } 104029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner 105029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner // If we found that the pointer is guaranteed to not match any of the 106029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner // locations in our 'DoesOnly' rule, then we know that the pointer must point 107029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner // to some other location. Since the libcall doesn't mod/ref any other 108029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner // locations, return NoModRef. 109029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner if (NoneMatch) 110029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner return NoModRef; 111029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner 112029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner // Otherwise, return any other info gained so far. 113029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner return MRInfo; 114029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner} 115029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner 116029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner// getModRefInfo - Check to see if the specified callsite can clobber the 117029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner// specified memory object. 118029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner// 119029840c93521f5c54380e037a66216c8227ad1e1Chris LattnerAliasAnalysis::ModRefResult 12079fca6fea87be7221843031870bbf2c9ae1fc555Dan GohmanLibCallAliasAnalysis::getModRefInfo(ImmutableCallSite CS, 121b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman const Location &Loc) { 122029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner ModRefResult MRInfo = ModRef; 123029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner 124029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner // If this is a direct call to a function that LCI knows about, get the 125029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner // information about the runtime function. 12615ccbf59a90e796dd6e756c4ae43cc7ac03d0b1bChris Lattner if (LCI) { 12779fca6fea87be7221843031870bbf2c9ae1fc555Dan Gohman if (const Function *F = CS.getCalledFunction()) { 128029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner if (const LibCallFunctionInfo *FI = LCI->getFunctionInfo(F)) { 129b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman MRInfo = ModRefResult(MRInfo & AnalyzeLibCallDetails(FI, CS, Loc)); 130029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner if (MRInfo == NoModRef) return NoModRef; 131029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner } 132029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner } 133029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner } 134029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner 135029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner // The AliasAnalysis base class has some smarts, lets use them. 136b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman return (ModRefResult)(MRInfo | AliasAnalysis::getModRefInfo(CS, Loc)); 137029840c93521f5c54380e037a66216c8227ad1e1Chris Lattner} 138