1db4708cf86cece22539ff022cc0601612dd02eadDan Gohman//===- BasicAliasAnalysis.cpp - Stateless Alias Analysis Impl -------------===// 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//===----------------------------------------------------------------------===// 9d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner// 10db4708cf86cece22539ff022cc0601612dd02eadDan Gohman// This file defines the primary stateless implementation of the 11db4708cf86cece22539ff022cc0601612dd02eadDan Gohman// Alias Analysis interface that implements identities (two different 12db4708cf86cece22539ff022cc0601612dd02eadDan Gohman// globals cannot alias, etc), but does no stateful analysis. 13d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner// 14d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner//===----------------------------------------------------------------------===// 15d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 16d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner#include "llvm/Analysis/AliasAnalysis.h" 17534927d82de6d1be0f6e939263eeb309ad135661Jeff Cohen#include "llvm/Analysis/Passes.h" 186eb88d44c93f782a988039a047a9b80354a81887Chris Lattner#include "llvm/Constants.h" 19d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner#include "llvm/DerivedTypes.h" 204244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner#include "llvm/Function.h" 2130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner#include "llvm/GlobalAlias.h" 224244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner#include "llvm/GlobalVariable.h" 23eb62bc77b68e8d2350453d15aca300f481a612d5Alkis Evlogimenos#include "llvm/Instructions.h" 249b636cb3385376faa7f33a943cac7d40bff1531aOwen Anderson#include "llvm/IntrinsicInst.h" 25b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman#include "llvm/LLVMContext.h" 263a7a68c10880c2a28387617b42d14d774e218727Dan Gohman#include "llvm/Operator.h" 274244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner#include "llvm/Pass.h" 285d5261c819fa2a203dc8d09c7bb71e041a12cd69Chris Lattner#include "llvm/Analysis/CaptureTracking.h" 295d5261c819fa2a203dc8d09c7bb71e041a12cd69Chris Lattner#include "llvm/Analysis/MemoryBuiltins.h" 30c01895c7db4c4d8883dd4c31427c42cdae356567Dan Gohman#include "llvm/Analysis/InstructionSimplify.h" 315d5261c819fa2a203dc8d09c7bb71e041a12cd69Chris Lattner#include "llvm/Analysis/ValueTracking.h" 32d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner#include "llvm/Target/TargetData.h" 3369acc93b3de6854732a6d91b581c3c29b59bb315Owen Anderson#include "llvm/Target/TargetLibraryInfo.h" 34e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner#include "llvm/ADT/SmallPtrSet.h" 35a77600e8612c51e75f55710ce9af7eb8aba8b083Chris Lattner#include "llvm/ADT/SmallVector.h" 36c25e7581b9b8088910da31702d4ca21c4734c6d7Torok Edwin#include "llvm/Support/ErrorHandling.h" 3730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner#include "llvm/Support/GetElementPtrTypeIterator.h" 3820aa474f8fbebde588edc101b90e834df28ce4ceAlkis Evlogimenos#include <algorithm> 39ec4e8085e83fa1f14a82849548f7c1ad82009adeChris Lattnerusing namespace llvm; 40d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 41defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner//===----------------------------------------------------------------------===// 42defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner// Useful predicates 43defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner//===----------------------------------------------------------------------===// 44defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner 45defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner/// isNonEscapingLocalObject - Return true if the pointer is to a function-local 46defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner/// object that never escapes from the function. 4721de4c0daf2b35963d16541a3007c543237eb7bfDan Gohmanstatic bool isNonEscapingLocalObject(const Value *V) { 48defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner // If this is a local allocation, check to see if it escapes. 4921de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman if (isa<AllocaInst>(V) || isNoAliasCall(V)) 50f94b5edc452c32d9ae258e7de30c33391fda6cc9Dan Gohman // Set StoreCaptures to True so that we can assume in our callers that the 51f94b5edc452c32d9ae258e7de30c33391fda6cc9Dan Gohman // pointer is not the result of a load instruction. Currently 52f94b5edc452c32d9ae258e7de30c33391fda6cc9Dan Gohman // PointerMayBeCaptured doesn't have any special analysis for the 53f94b5edc452c32d9ae258e7de30c33391fda6cc9Dan Gohman // StoreCaptures=false case; if it did, our callers could be refined to be 54f94b5edc452c32d9ae258e7de30c33391fda6cc9Dan Gohman // more precise. 55f94b5edc452c32d9ae258e7de30c33391fda6cc9Dan Gohman return !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true); 5691c9c31033ff8166289bfee050b02bb6b586d510Duncan Sands 57defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner // If this is an argument that corresponds to a byval or noalias argument, 5891c9c31033ff8166289bfee050b02bb6b586d510Duncan Sands // then it has not escaped before entering the function. Check if it escapes 5991c9c31033ff8166289bfee050b02bb6b586d510Duncan Sands // inside the function. 6021de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman if (const Argument *A = dyn_cast<Argument>(V)) 6121de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman if (A->hasByValAttr() || A->hasNoAliasAttr()) { 6221de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman // Don't bother analyzing arguments already known not to escape. 6321de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman if (A->hasNoCaptureAttr()) 6421de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman return true; 6521de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman return !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true); 6621de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman } 67defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner return false; 68defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner} 69defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner 706be2bd516a3022721480f8fee6986617baf0944fDan Gohman/// isEscapeSource - Return true if the pointer is one which would have 716be2bd516a3022721480f8fee6986617baf0944fDan Gohman/// been considered an escape by isNonEscapingLocalObject. 7221de4c0daf2b35963d16541a3007c543237eb7bfDan Gohmanstatic bool isEscapeSource(const Value *V) { 7321de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman if (isa<CallInst>(V) || isa<InvokeInst>(V) || isa<Argument>(V)) 7421de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman return true; 756be2bd516a3022721480f8fee6986617baf0944fDan Gohman 766be2bd516a3022721480f8fee6986617baf0944fDan Gohman // The load case works because isNonEscapingLocalObject considers all 776be2bd516a3022721480f8fee6986617baf0944fDan Gohman // stores to be escapes (it passes true for the StoreCaptures argument 786be2bd516a3022721480f8fee6986617baf0944fDan Gohman // to PointerMayBeCaptured). 796be2bd516a3022721480f8fee6986617baf0944fDan Gohman if (isa<LoadInst>(V)) 806be2bd516a3022721480f8fee6986617baf0944fDan Gohman return true; 816be2bd516a3022721480f8fee6986617baf0944fDan Gohman 826be2bd516a3022721480f8fee6986617baf0944fDan Gohman return false; 836be2bd516a3022721480f8fee6986617baf0944fDan Gohman} 84defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner 85615da1a9bcca05de06fab5f48ee9110267312974Dan Gohman/// getObjectSize - Return the size of the object specified by V, or 86615da1a9bcca05de06fab5f48ee9110267312974Dan Gohman/// UnknownSize if unknown. 871680a24e534f3066f99fa6b8a618e71373e2920cEli Friedmanstatic uint64_t getObjectSize(const Value *V, const TargetData &TD, 888e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const TargetLibraryInfo &TLI, 891680a24e534f3066f99fa6b8a618e71373e2920cEli Friedman bool RoundToAlign = false) { 909e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes uint64_t Size; 918e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer if (getObjectSize(V, Size, &TD, &TLI, RoundToAlign)) 929e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return Size; 939e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return AliasAnalysis::UnknownSize; 94615da1a9bcca05de06fab5f48ee9110267312974Dan Gohman} 95615da1a9bcca05de06fab5f48ee9110267312974Dan Gohman 96615da1a9bcca05de06fab5f48ee9110267312974Dan Gohman/// isObjectSmallerThan - Return true if we can prove that the object specified 97615da1a9bcca05de06fab5f48ee9110267312974Dan Gohman/// by V is smaller than Size. 98615da1a9bcca05de06fab5f48ee9110267312974Dan Gohmanstatic bool isObjectSmallerThan(const Value *V, uint64_t Size, 998e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const TargetData &TD, 1008e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const TargetLibraryInfo &TLI) { 1011680a24e534f3066f99fa6b8a618e71373e2920cEli Friedman // This function needs to use the aligned object size because we allow 1021680a24e534f3066f99fa6b8a618e71373e2920cEli Friedman // reads a bit past the end given sufficient alignment. 1038e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer uint64_t ObjectSize = getObjectSize(V, TD, TLI, /*RoundToAlign*/true); 1041680a24e534f3066f99fa6b8a618e71373e2920cEli Friedman 105615da1a9bcca05de06fab5f48ee9110267312974Dan Gohman return ObjectSize != AliasAnalysis::UnknownSize && ObjectSize < Size; 106615da1a9bcca05de06fab5f48ee9110267312974Dan Gohman} 107615da1a9bcca05de06fab5f48ee9110267312974Dan Gohman 108615da1a9bcca05de06fab5f48ee9110267312974Dan Gohman/// isObjectSize - Return true if we can prove that the object specified 109615da1a9bcca05de06fab5f48ee9110267312974Dan Gohman/// by V has size Size. 110615da1a9bcca05de06fab5f48ee9110267312974Dan Gohmanstatic bool isObjectSize(const Value *V, uint64_t Size, 1118e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const TargetData &TD, const TargetLibraryInfo &TLI) { 1128e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer uint64_t ObjectSize = getObjectSize(V, TD, TLI); 113615da1a9bcca05de06fab5f48ee9110267312974Dan Gohman return ObjectSize != AliasAnalysis::UnknownSize && ObjectSize == Size; 114defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner} 115defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner 116defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner//===----------------------------------------------------------------------===// 11730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner// GetElementPtr Instruction Decomposition and Analysis 11830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner//===----------------------------------------------------------------------===// 11930963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 1208807e9fbdf81221b277506064c46829732f019cfChris Lattnernamespace { 1218807e9fbdf81221b277506064c46829732f019cfChris Lattner enum ExtensionKind { 1228807e9fbdf81221b277506064c46829732f019cfChris Lattner EK_NotExtended, 1238807e9fbdf81221b277506064c46829732f019cfChris Lattner EK_SignExt, 1248807e9fbdf81221b277506064c46829732f019cfChris Lattner EK_ZeroExt 1258807e9fbdf81221b277506064c46829732f019cfChris Lattner }; 1268807e9fbdf81221b277506064c46829732f019cfChris Lattner 1278807e9fbdf81221b277506064c46829732f019cfChris Lattner struct VariableGEPIndex { 1288807e9fbdf81221b277506064c46829732f019cfChris Lattner const Value *V; 1298807e9fbdf81221b277506064c46829732f019cfChris Lattner ExtensionKind Extension; 1308807e9fbdf81221b277506064c46829732f019cfChris Lattner int64_t Scale; 131029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer 132029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer bool operator==(const VariableGEPIndex &Other) const { 133029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer return V == Other.V && Extension == Other.Extension && 134029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer Scale == Other.Scale; 135029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer } 136029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer 137029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer bool operator!=(const VariableGEPIndex &Other) const { 138029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer return !operator==(Other); 139029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer } 1408807e9fbdf81221b277506064c46829732f019cfChris Lattner }; 1418807e9fbdf81221b277506064c46829732f019cfChris Lattner} 1428807e9fbdf81221b277506064c46829732f019cfChris Lattner 14330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 14430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// GetLinearExpression - Analyze the specified value as a linear expression: 14530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// "A*V + B", where A and B are constant integers. Return the scale and offset 1462215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner/// values as APInts and return V as a Value*, and return whether we looked 1472215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner/// through any sign or zero extends. The incoming Value is known to have 1482215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner/// IntegerType and it may already be sign or zero extended. 1492215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner/// 1502215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner/// Note that this looks through extends, so the high bits may not be 1512215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner/// represented in the result. 15230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattnerstatic Value *GetLinearExpression(Value *V, APInt &Scale, APInt &Offset, 1532215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner ExtensionKind &Extension, 154ff2efb9f9caf6669beb587aa4d65f24d3a026090Chris Lattner const TargetData &TD, unsigned Depth) { 15530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner assert(V->getType()->isIntegerTy() && "Not an integer value"); 15630963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 15730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // Limit our recursion depth. 15830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner if (Depth == 6) { 15930963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner Scale = 1; 16030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner Offset = 0; 16130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner return V; 16230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 16330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 16430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(V)) { 16530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner if (ConstantInt *RHSC = dyn_cast<ConstantInt>(BOp->getOperand(1))) { 16630963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner switch (BOp->getOpcode()) { 16730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner default: break; 16830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner case Instruction::Or: 16930963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // X|C == X+C if all the bits in C are unset in X. Otherwise we can't 17030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // analyze it. 171ff2efb9f9caf6669beb587aa4d65f24d3a026090Chris Lattner if (!MaskedValueIsZero(BOp->getOperand(0), RHSC->getValue(), &TD)) 17230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner break; 17330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // FALL THROUGH. 17430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner case Instruction::Add: 1752215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension, 1762215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner TD, Depth+1); 17730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner Offset += RHSC->getValue(); 17830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner return V; 17930963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner case Instruction::Mul: 1802215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension, 1812215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner TD, Depth+1); 18230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner Offset *= RHSC->getValue(); 18330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner Scale *= RHSC->getValue(); 18430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner return V; 18530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner case Instruction::Shl: 1862215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension, 1872215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner TD, Depth+1); 18830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner Offset <<= RHSC->getValue().getLimitedValue(); 18930963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner Scale <<= RHSC->getValue().getLimitedValue(); 19030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner return V; 19130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 19230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 19330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 19430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 19530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // Since GEP indices are sign extended anyway, we don't care about the high 1962215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner // bits of a sign or zero extended value - just scales and offsets. The 1972215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner // extensions have to be consistent though. 1982215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner if ((isa<SExtInst>(V) && Extension != EK_ZeroExt) || 1992215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner (isa<ZExtInst>(V) && Extension != EK_SignExt)) { 20030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner Value *CastOp = cast<CastInst>(V)->getOperand(0); 20130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner unsigned OldWidth = Scale.getBitWidth(); 20230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner unsigned SmallWidth = CastOp->getType()->getPrimitiveSizeInBits(); 20340f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad Scale = Scale.trunc(SmallWidth); 20440f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad Offset = Offset.trunc(SmallWidth); 2052215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner Extension = isa<SExtInst>(V) ? EK_SignExt : EK_ZeroExt; 2062215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner 2072215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner Value *Result = GetLinearExpression(CastOp, Scale, Offset, Extension, 2082215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner TD, Depth+1); 20940f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad Scale = Scale.zext(OldWidth); 21040f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad Offset = Offset.zext(OldWidth); 2112215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner 21230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner return Result; 21330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 21430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 21530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner Scale = 1; 21630963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner Offset = 0; 21730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner return V; 21830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner} 21930963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 22030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// DecomposeGEPExpression - If V is a symbolic pointer expression, decompose it 22130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// into a base pointer with a constant offset and a number of scaled symbolic 22230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// offsets. 22330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// 22430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// The scaled symbolic offsets (represented by pairs of a Value* and a scale in 22530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// the VarIndices vector) are Value*'s that are known to be scaled by the 22630963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// specified amount, but which may have other unrepresented high bits. As such, 22730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// the gep cannot necessarily be reconstructed from its decomposed form. 22830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// 22930963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// When TargetData is around, this function is capable of analyzing everything 2305034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman/// that GetUnderlyingObject can look through. When not, it just looks 23130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// through pointer casts. 23230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// 23330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattnerstatic const Value * 23430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris LattnerDecomposeGEPExpression(const Value *V, int64_t &BaseOffs, 2358807e9fbdf81221b277506064c46829732f019cfChris Lattner SmallVectorImpl<VariableGEPIndex> &VarIndices, 23630963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner const TargetData *TD) { 23730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // Limit recursion depth to limit compile time in crazy cases. 23830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner unsigned MaxLookup = 6; 23930963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 24030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner BaseOffs = 0; 24130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner do { 24230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // See if this is a bitcast or GEP. 24330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner const Operator *Op = dyn_cast<Operator>(V); 24430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner if (Op == 0) { 24530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // The only non-operator case we can handle are GlobalAliases. 24630963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { 24730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner if (!GA->mayBeOverridden()) { 24830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner V = GA->getAliasee(); 24930963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner continue; 25030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 25130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 25230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner return V; 25330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 25430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 25530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner if (Op->getOpcode() == Instruction::BitCast) { 25630963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner V = Op->getOperand(0); 25730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner continue; 25830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 259c01895c7db4c4d8883dd4c31427c42cdae356567Dan Gohman 26030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner const GEPOperator *GEPOp = dyn_cast<GEPOperator>(Op); 2619adf151b3d46740ac103c4e21fbdec66d6ef1cdfDan Gohman if (GEPOp == 0) { 2629adf151b3d46740ac103c4e21fbdec66d6ef1cdfDan Gohman // If it's not a GEP, hand it off to SimplifyInstruction to see if it 2639adf151b3d46740ac103c4e21fbdec66d6ef1cdfDan Gohman // can come up with something. This matches what GetUnderlyingObject does. 2649adf151b3d46740ac103c4e21fbdec66d6ef1cdfDan Gohman if (const Instruction *I = dyn_cast<Instruction>(V)) 2659adf151b3d46740ac103c4e21fbdec66d6ef1cdfDan Gohman // TODO: Get a DominatorTree and use it here. 2669adf151b3d46740ac103c4e21fbdec66d6ef1cdfDan Gohman if (const Value *Simplified = 2679adf151b3d46740ac103c4e21fbdec66d6ef1cdfDan Gohman SimplifyInstruction(const_cast<Instruction *>(I), TD)) { 2689adf151b3d46740ac103c4e21fbdec66d6ef1cdfDan Gohman V = Simplified; 2699adf151b3d46740ac103c4e21fbdec66d6ef1cdfDan Gohman continue; 2709adf151b3d46740ac103c4e21fbdec66d6ef1cdfDan Gohman } 2719adf151b3d46740ac103c4e21fbdec66d6ef1cdfDan Gohman 27230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner return V; 2739adf151b3d46740ac103c4e21fbdec66d6ef1cdfDan Gohman } 27430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 27530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // Don't attempt to analyze GEPs over unsized objects. 27630963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner if (!cast<PointerType>(GEPOp->getOperand(0)->getType()) 27730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner ->getElementType()->isSized()) 27830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner return V; 27930963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 28030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // If we are lacking TargetData information, we can't compute the offets of 28130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // elements computed by GEPs. However, we can handle bitcast equivalent 28230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // GEPs. 283ff2efb9f9caf6669beb587aa4d65f24d3a026090Chris Lattner if (TD == 0) { 28430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner if (!GEPOp->hasAllZeroIndices()) 28530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner return V; 28630963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner V = GEPOp->getOperand(0); 28730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner continue; 28830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 28930963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 29030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // Walk the indices of the GEP, accumulating them into BaseOff/VarIndices. 29130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner gep_type_iterator GTI = gep_type_begin(GEPOp); 29230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner for (User::const_op_iterator I = GEPOp->op_begin()+1, 29330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner E = GEPOp->op_end(); I != E; ++I) { 29430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner Value *Index = *I; 29530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // Compute the (potentially symbolic) offset in bytes for this index. 296db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner if (StructType *STy = dyn_cast<StructType>(*GTI++)) { 29730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // For a struct, add the member offset. 29830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue(); 29930963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner if (FieldNo == 0) continue; 30030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 30130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner BaseOffs += TD->getStructLayout(STy)->getElementOffset(FieldNo); 30230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner continue; 30330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 30430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 30530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // For an array/pointer, add the element offset, explicitly scaled. 30630963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner if (ConstantInt *CIdx = dyn_cast<ConstantInt>(Index)) { 30730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner if (CIdx->isZero()) continue; 30830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner BaseOffs += TD->getTypeAllocSize(*GTI)*CIdx->getSExtValue(); 30930963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner continue; 31030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 31130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 31230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner uint64_t Scale = TD->getTypeAllocSize(*GTI); 3138807e9fbdf81221b277506064c46829732f019cfChris Lattner ExtensionKind Extension = EK_NotExtended; 31430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 3152215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner // If the integer type is smaller than the pointer size, it is implicitly 3162215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner // sign extended to pointer size. 31730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner unsigned Width = cast<IntegerType>(Index->getType())->getBitWidth(); 3182215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner if (TD->getPointerSizeInBits() > Width) 3192215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner Extension = EK_SignExt; 3202215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner 3212215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner // Use GetLinearExpression to decompose the index into a C1*V+C2 form. 32230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner APInt IndexScale(Width, 0), IndexOffset(Width, 0); 3232215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner Index = GetLinearExpression(Index, IndexScale, IndexOffset, Extension, 3242215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner *TD, 0); 32530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 32630963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // The GEP index scale ("Scale") scales C1*V+C2, yielding (C1*V+C2)*Scale. 32730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // This gives us an aggregate computation of (C1*Scale)*V + C2*Scale. 32839e30124e50534972c2e58f4dab7d67c0c437743Eli Friedman BaseOffs += IndexOffset.getSExtValue()*Scale; 32939e30124e50534972c2e58f4dab7d67c0c437743Eli Friedman Scale *= IndexScale.getSExtValue(); 33030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 33130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 3327a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner // If we already had an occurrence of this index variable, merge this 33330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // scale into it. For example, we want to handle: 33430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // A[x][x] -> x*16 + x*4 -> x*20 33530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // This also ensures that 'x' only appears in the index list once. 33630963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner for (unsigned i = 0, e = VarIndices.size(); i != e; ++i) { 3378807e9fbdf81221b277506064c46829732f019cfChris Lattner if (VarIndices[i].V == Index && 3388807e9fbdf81221b277506064c46829732f019cfChris Lattner VarIndices[i].Extension == Extension) { 3398807e9fbdf81221b277506064c46829732f019cfChris Lattner Scale += VarIndices[i].Scale; 34030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner VarIndices.erase(VarIndices.begin()+i); 34130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner break; 34230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 34330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 34430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 34530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // Make sure that we have a scale that makes sense for this target's 34630963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // pointer size. 34730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner if (unsigned ShiftBits = 64-TD->getPointerSizeInBits()) { 34830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner Scale <<= ShiftBits; 34939e30124e50534972c2e58f4dab7d67c0c437743Eli Friedman Scale = (int64_t)Scale >> ShiftBits; 35030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 35130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 3528807e9fbdf81221b277506064c46829732f019cfChris Lattner if (Scale) { 353a44defeb2208376ca3113ffdddc391570ba865b8Jeffrey Yasskin VariableGEPIndex Entry = {Index, Extension, 354a44defeb2208376ca3113ffdddc391570ba865b8Jeffrey Yasskin static_cast<int64_t>(Scale)}; 3558807e9fbdf81221b277506064c46829732f019cfChris Lattner VarIndices.push_back(Entry); 3568807e9fbdf81221b277506064c46829732f019cfChris Lattner } 35730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 35830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 35930963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // Analyze the base pointer next. 36030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner V = GEPOp->getOperand(0); 36130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } while (--MaxLookup); 36230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 36330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // If the chain of expressions is too deep, just return early. 36430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner return V; 36530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner} 36630963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 36730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// GetIndexDifference - Dest and Src are the variable indices from two 36830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// decomposed GetElementPtr instructions GEP1 and GEP2 which have common base 36930963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// pointers. Subtract the GEP2 indices from GEP1 to find the symbolic 37030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// difference between the two pointers. 3718807e9fbdf81221b277506064c46829732f019cfChris Lattnerstatic void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest, 3728807e9fbdf81221b277506064c46829732f019cfChris Lattner const SmallVectorImpl<VariableGEPIndex> &Src) { 37330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner if (Src.empty()) return; 37430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 37530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner for (unsigned i = 0, e = Src.size(); i != e; ++i) { 3768807e9fbdf81221b277506064c46829732f019cfChris Lattner const Value *V = Src[i].V; 3778807e9fbdf81221b277506064c46829732f019cfChris Lattner ExtensionKind Extension = Src[i].Extension; 3788807e9fbdf81221b277506064c46829732f019cfChris Lattner int64_t Scale = Src[i].Scale; 37930963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 38030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // Find V in Dest. This is N^2, but pointer indices almost never have more 38130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // than a few variable indexes. 38230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner for (unsigned j = 0, e = Dest.size(); j != e; ++j) { 3838807e9fbdf81221b277506064c46829732f019cfChris Lattner if (Dest[j].V != V || Dest[j].Extension != Extension) continue; 38430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 38530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // If we found it, subtract off Scale V's from the entry in Dest. If it 38630963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // goes to zero, remove the entry. 3878807e9fbdf81221b277506064c46829732f019cfChris Lattner if (Dest[j].Scale != Scale) 3888807e9fbdf81221b277506064c46829732f019cfChris Lattner Dest[j].Scale -= Scale; 38930963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner else 39030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner Dest.erase(Dest.begin()+j); 39130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner Scale = 0; 39230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner break; 39330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 39430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 39530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // If we didn't consume this entry, add it to the end of the Dest list. 3968807e9fbdf81221b277506064c46829732f019cfChris Lattner if (Scale) { 3978807e9fbdf81221b277506064c46829732f019cfChris Lattner VariableGEPIndex Entry = { V, Extension, -Scale }; 3988807e9fbdf81221b277506064c46829732f019cfChris Lattner Dest.push_back(Entry); 3998807e9fbdf81221b277506064c46829732f019cfChris Lattner } 40030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 40130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner} 40230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 40330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner//===----------------------------------------------------------------------===// 4046be2bd516a3022721480f8fee6986617baf0944fDan Gohman// BasicAliasAnalysis Pass 405defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner//===----------------------------------------------------------------------===// 406defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner 4079e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman#ifndef NDEBUG 4086be2bd516a3022721480f8fee6986617baf0944fDan Gohmanstatic const Function *getParent(const Value *V) { 4096f205cbceb487b327708faf7ad25007b754dcf36Dan Gohman if (const Instruction *inst = dyn_cast<Instruction>(V)) 4106be2bd516a3022721480f8fee6986617baf0944fDan Gohman return inst->getParent()->getParent(); 4116be2bd516a3022721480f8fee6986617baf0944fDan Gohman 4126f205cbceb487b327708faf7ad25007b754dcf36Dan Gohman if (const Argument *arg = dyn_cast<Argument>(V)) 4136be2bd516a3022721480f8fee6986617baf0944fDan Gohman return arg->getParent(); 4146be2bd516a3022721480f8fee6986617baf0944fDan Gohman 4156be2bd516a3022721480f8fee6986617baf0944fDan Gohman return NULL; 4166be2bd516a3022721480f8fee6986617baf0944fDan Gohman} 4176be2bd516a3022721480f8fee6986617baf0944fDan Gohman 41821de4c0daf2b35963d16541a3007c543237eb7bfDan Gohmanstatic bool notDifferentParent(const Value *O1, const Value *O2) { 41921de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman 42021de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman const Function *F1 = getParent(O1); 42121de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman const Function *F2 = getParent(O2); 42221de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman 4236be2bd516a3022721480f8fee6986617baf0944fDan Gohman return !F1 || !F2 || F1 == F2; 4246be2bd516a3022721480f8fee6986617baf0944fDan Gohman} 4253432d70d5b48164f0adaec0771c89c54408e2be9Benjamin Kramer#endif 4266be2bd516a3022721480f8fee6986617baf0944fDan Gohman 427b52f44086006434039b0c5df55aaac1079d26b96Chris Lattnernamespace { 428db4708cf86cece22539ff022cc0601612dd02eadDan Gohman /// BasicAliasAnalysis - This is the primary alias analysis implementation. 429db4708cf86cece22539ff022cc0601612dd02eadDan Gohman struct BasicAliasAnalysis : public ImmutablePass, public AliasAnalysis { 4301997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel static char ID; // Class identification, replacement for typeinfo 431998d3cca2937393d91b04d4d6105d9e67dd3b1b6Benjamin Kramer BasicAliasAnalysis() : ImmutablePass(ID) { 432081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeBasicAliasAnalysisPass(*PassRegistry::getPassRegistry()); 433081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 4346be2bd516a3022721480f8fee6986617baf0944fDan Gohman 435c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman virtual void initializePass() { 436c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman InitializeAliasAnalysis(this); 437c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman } 438c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman 439c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman virtual void getAnalysisUsage(AnalysisUsage &AU) const { 440c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman AU.addRequired<AliasAnalysis>(); 44169acc93b3de6854732a6d91b581c3c29b59bb315Owen Anderson AU.addRequired<TargetLibraryInfo>(); 442c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman } 443c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman 444b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman virtual AliasResult alias(const Location &LocA, 445b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman const Location &LocB) { 4461fc18d71deb0e23a9101c87bb7b1455098ce1c09Dan Gohman assert(AliasCache.empty() && "AliasCache must be cleared after use!"); 447b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman assert(notDifferentParent(LocA.Ptr, LocB.Ptr) && 4489e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman "BasicAliasAnalysis doesn't support interprocedural queries."); 4496cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman AliasResult Alias = aliasCheck(LocA.Ptr, LocA.Size, LocA.TBAATag, 4506cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman LocB.Ptr, LocB.Size, LocB.TBAATag); 451998d3cca2937393d91b04d4d6105d9e67dd3b1b6Benjamin Kramer // AliasCache rarely has more than 1 or 2 elements, always use 452998d3cca2937393d91b04d4d6105d9e67dd3b1b6Benjamin Kramer // shrink_and_clear so it quickly returns to the inline capacity of the 453998d3cca2937393d91b04d4d6105d9e67dd3b1b6Benjamin Kramer // SmallDenseMap if it ever grows larger. 454998d3cca2937393d91b04d4d6105d9e67dd3b1b6Benjamin Kramer // FIXME: This should really be shrink_to_inline_capacity_and_clear(). 455998d3cca2937393d91b04d4d6105d9e67dd3b1b6Benjamin Kramer AliasCache.shrink_and_clear(); 456f0429fd1ca7f6d359a33c20617785d7572a0292dEvan Cheng return Alias; 45750a5914e129c348e8878d4654b4306e0349281c2Evan Cheng } 458bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner 4596ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman virtual ModRefResult getModRefInfo(ImmutableCallSite CS, 460b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman const Location &Loc); 4616ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 4626ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman virtual ModRefResult getModRefInfo(ImmutableCallSite CS1, 4636ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman ImmutableCallSite CS2) { 4646ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // The AliasAnalysis base class has some smarts, lets use them. 4656ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return AliasAnalysis::getModRefInfo(CS1, CS2); 4666ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman } 467e79422096ea5319a365d160693d0957a2a4df75eOwen Anderson 468bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner /// pointsToConstantMemory - Chase pointers until we find a (constant 469bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner /// global) or not. 470a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman virtual bool pointsToConstantMemory(const Location &Loc, bool OrLocal); 4716ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 4726ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman /// getModRefBehavior - Return the behavior when calling the given 4736ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman /// call site. 4746ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman virtual ModRefBehavior getModRefBehavior(ImmutableCallSite CS); 4756ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 4766ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman /// getModRefBehavior - Return the behavior when calling the given function. 4776ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman /// For use when the call site is not known. 4786ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman virtual ModRefBehavior getModRefBehavior(const Function *F); 479bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner 4802033097b1f5b1889a5d801febbc7848c7b8ca439Chris Lattner /// getAdjustedAnalysisPointer - This method is used when a pass implements 4815eeb19d189fd448293e607227e5564d2efab0f7fDan Gohman /// an analysis interface through multiple inheritance. If needed, it 4825eeb19d189fd448293e607227e5564d2efab0f7fDan Gohman /// should override this to adjust the this pointer as needed for the 4835eeb19d189fd448293e607227e5564d2efab0f7fDan Gohman /// specified pass info. 48490c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson virtual void *getAdjustedAnalysisPointer(const void *ID) { 48590c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson if (ID == &AliasAnalysis::ID) 4862033097b1f5b1889a5d801febbc7848c7b8ca439Chris Lattner return (AliasAnalysis*)this; 4872033097b1f5b1889a5d801febbc7848c7b8ca439Chris Lattner return this; 4882033097b1f5b1889a5d801febbc7848c7b8ca439Chris Lattner } 4892033097b1f5b1889a5d801febbc7848c7b8ca439Chris Lattner 490d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner private: 4911fc18d71deb0e23a9101c87bb7b1455098ce1c09Dan Gohman // AliasCache - Track alias queries to guard against recursion. 4921fc18d71deb0e23a9101c87bb7b1455098ce1c09Dan Gohman typedef std::pair<Location, Location> LocPair; 493998d3cca2937393d91b04d4d6105d9e67dd3b1b6Benjamin Kramer typedef SmallDenseMap<LocPair, AliasResult, 8> AliasCacheTy; 4941fc18d71deb0e23a9101c87bb7b1455098ce1c09Dan Gohman AliasCacheTy AliasCache; 4951fc18d71deb0e23a9101c87bb7b1455098ce1c09Dan Gohman 4961fc18d71deb0e23a9101c87bb7b1455098ce1c09Dan Gohman // Visited - Track instructions visited by pointsToConstantMemory. 49750f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman SmallPtrSet<const Value*, 16> Visited; 4983dbe43b1b50472f4f24df17fff5ac2443be63d5fEvan Cheng 4995d56b2d47d324ecf2d1cc1551a28cce49d16ab01Chris Lattner // aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP 5005d56b2d47d324ecf2d1cc1551a28cce49d16ab01Chris Lattner // instruction against another. 5013da848bbda62b25c12335998aaa44ab361f0bf15Dan Gohman AliasResult aliasGEP(const GEPOperator *V1, uint64_t V1Size, 502029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer const MDNode *V1TBAAInfo, 5033da848bbda62b25c12335998aaa44ab361f0bf15Dan Gohman const Value *V2, uint64_t V2Size, 5046cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman const MDNode *V2TBAAInfo, 50523e2a5b2fff8b5b483a464ce1bea9a686e6731deChris Lattner const Value *UnderlyingV1, const Value *UnderlyingV2); 50650a5914e129c348e8878d4654b4306e0349281c2Evan Cheng 5075d56b2d47d324ecf2d1cc1551a28cce49d16ab01Chris Lattner // aliasPHI - Provide a bunch of ad-hoc rules to disambiguate a PHI 5085d56b2d47d324ecf2d1cc1551a28cce49d16ab01Chris Lattner // instruction against another. 5093da848bbda62b25c12335998aaa44ab361f0bf15Dan Gohman AliasResult aliasPHI(const PHINode *PN, uint64_t PNSize, 5106cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman const MDNode *PNTBAAInfo, 5113da848bbda62b25c12335998aaa44ab361f0bf15Dan Gohman const Value *V2, uint64_t V2Size, 5126cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman const MDNode *V2TBAAInfo); 51350a5914e129c348e8878d4654b4306e0349281c2Evan Cheng 5146665b0ea688941c1c044a5c034ee45d45862168fDan Gohman /// aliasSelect - Disambiguate a Select instruction against another value. 5153da848bbda62b25c12335998aaa44ab361f0bf15Dan Gohman AliasResult aliasSelect(const SelectInst *SI, uint64_t SISize, 5166cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman const MDNode *SITBAAInfo, 5173da848bbda62b25c12335998aaa44ab361f0bf15Dan Gohman const Value *V2, uint64_t V2Size, 5186cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman const MDNode *V2TBAAInfo); 5196665b0ea688941c1c044a5c034ee45d45862168fDan Gohman 5203da848bbda62b25c12335998aaa44ab361f0bf15Dan Gohman AliasResult aliasCheck(const Value *V1, uint64_t V1Size, 5216cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman const MDNode *V1TBAATag, 5223da848bbda62b25c12335998aaa44ab361f0bf15Dan Gohman const Value *V2, uint64_t V2Size, 5236cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman const MDNode *V2TBAATag); 524d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner }; 525844731a7f1909f55935e3514c9e713a62d67662eDan Gohman} // End of anonymous namespace 5262b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 527844731a7f1909f55935e3514c9e713a62d67662eDan Gohman// Register this pass... 528844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar BasicAliasAnalysis::ID = 0; 52969acc93b3de6854732a6d91b581c3c29b59bb315Owen AndersonINITIALIZE_AG_PASS_BEGIN(BasicAliasAnalysis, AliasAnalysis, "basicaa", 53069acc93b3de6854732a6d91b581c3c29b59bb315Owen Anderson "Basic Alias Analysis (stateless AA impl)", 53169acc93b3de6854732a6d91b581c3c29b59bb315Owen Anderson false, true, false) 53269acc93b3de6854732a6d91b581c3c29b59bb315Owen AndersonINITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) 53369acc93b3de6854732a6d91b581c3c29b59bb315Owen AndersonINITIALIZE_AG_PASS_END(BasicAliasAnalysis, AliasAnalysis, "basicaa", 534db4708cf86cece22539ff022cc0601612dd02eadDan Gohman "Basic Alias Analysis (stateless AA impl)", 535c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman false, true, false) 536d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 53769acc93b3de6854732a6d91b581c3c29b59bb315Owen Anderson 538534927d82de6d1be0f6e939263eeb309ad135661Jeff CohenImmutablePass *llvm::createBasicAliasAnalysisPass() { 539534927d82de6d1be0f6e939263eeb309ad135661Jeff Cohen return new BasicAliasAnalysis(); 540534927d82de6d1be0f6e939263eeb309ad135661Jeff Cohen} 541534927d82de6d1be0f6e939263eeb309ad135661Jeff Cohen 542a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman/// pointsToConstantMemory - Returns whether the given pointer value 543a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman/// points to memory that is local to the function, with global constants being 544a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman/// considered local to all functions. 545a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohmanbool 546a25e5dbcc2371352386a01e3c1b8e76dd890272bDan GohmanBasicAliasAnalysis::pointsToConstantMemory(const Location &Loc, bool OrLocal) { 547a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman assert(Visited.empty() && "Visited must be cleared after use!"); 5484a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner 5493fcfc9fafac268d282d1373ea4517b6901fc510dDan Gohman unsigned MaxLookup = 8; 550a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman SmallVector<const Value *, 16> Worklist; 551a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman Worklist.push_back(Loc.Ptr); 552a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman do { 553bd1801b5553c8be3960255a92738464e0010b6f6Dan Gohman const Value *V = GetUnderlyingObject(Worklist.pop_back_val(), TD); 554a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman if (!Visited.insert(V)) { 555a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman Visited.clear(); 556a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 557a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman } 558a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman 559a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman // An alloca instruction defines local memory. 560a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman if (OrLocal && isa<AllocaInst>(V)) 561a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman continue; 562a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman 563a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman // A global constant counts as local memory for our purposes. 564a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) { 565a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman // Note: this doesn't require GV to be "ODR" because it isn't legal for a 566a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman // global to be marked constant in some modules and non-constant in 567a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman // others. GV may even be a declaration, not a definition. 568a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman if (!GV->isConstant()) { 569a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman Visited.clear(); 570a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 571a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman } 572a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman continue; 573a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman } 574a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman 575a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman // If both select values point to local memory, then so does the select. 576a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman if (const SelectInst *SI = dyn_cast<SelectInst>(V)) { 577a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman Worklist.push_back(SI->getTrueValue()); 578a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman Worklist.push_back(SI->getFalseValue()); 579a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman continue; 580a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman } 581a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman 582a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman // If all values incoming to a phi node point to local memory, then so does 583a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman // the phi. 584a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman if (const PHINode *PN = dyn_cast<PHINode>(V)) { 5853fcfc9fafac268d282d1373ea4517b6901fc510dDan Gohman // Don't bother inspecting phi nodes with many operands. 5863fcfc9fafac268d282d1373ea4517b6901fc510dDan Gohman if (PN->getNumIncomingValues() > MaxLookup) { 5873fcfc9fafac268d282d1373ea4517b6901fc510dDan Gohman Visited.clear(); 5883fcfc9fafac268d282d1373ea4517b6901fc510dDan Gohman return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 5893fcfc9fafac268d282d1373ea4517b6901fc510dDan Gohman } 590a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 591a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman Worklist.push_back(PN->getIncomingValue(i)); 592a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman continue; 593a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman } 594a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman 595a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman // Otherwise be conservative. 596a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman Visited.clear(); 597a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 598a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman 5993fcfc9fafac268d282d1373ea4517b6901fc510dDan Gohman } while (!Worklist.empty() && --MaxLookup); 6006ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 601a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman Visited.clear(); 6023fcfc9fafac268d282d1373ea4517b6901fc510dDan Gohman return Worklist.empty(); 603bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner} 6044a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner 6056ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman/// getModRefBehavior - Return the behavior when calling the given call site. 6066ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanAliasAnalysis::ModRefBehavior 6076ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanBasicAliasAnalysis::getModRefBehavior(ImmutableCallSite CS) { 6086ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (CS.doesNotAccessMemory()) 6096ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // Can't do better than this. 6106ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return DoesNotAccessMemory; 6116ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 6126ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman ModRefBehavior Min = UnknownModRefBehavior; 6136ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 6146ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // If the callsite knows it only reads memory, don't return worse 6156ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // than that. 6166ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (CS.onlyReadsMemory()) 6176ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman Min = OnlyReadsMemory; 6186ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 6196ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // The AliasAnalysis base class has some smarts, lets use them. 62042c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman return ModRefBehavior(AliasAnalysis::getModRefBehavior(CS) & Min); 6216ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman} 6226ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 6236ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman/// getModRefBehavior - Return the behavior when calling the given function. 6246ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman/// For use when the call site is not known. 6256ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanAliasAnalysis::ModRefBehavior 6266ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanBasicAliasAnalysis::getModRefBehavior(const Function *F) { 627431c794ade88f5da17ba06436f781b009c745ddeDan Gohman // If the function declares it doesn't access memory, we can't do better. 6286ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (F->doesNotAccessMemory()) 6296ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return DoesNotAccessMemory; 630431c794ade88f5da17ba06436f781b009c745ddeDan Gohman 631431c794ade88f5da17ba06436f781b009c745ddeDan Gohman // For intrinsics, we can check the table. 632431c794ade88f5da17ba06436f781b009c745ddeDan Gohman if (unsigned iid = F->getIntrinsicID()) { 633431c794ade88f5da17ba06436f781b009c745ddeDan Gohman#define GET_INTRINSIC_MODREF_BEHAVIOR 634431c794ade88f5da17ba06436f781b009c745ddeDan Gohman#include "llvm/Intrinsics.gen" 635431c794ade88f5da17ba06436f781b009c745ddeDan Gohman#undef GET_INTRINSIC_MODREF_BEHAVIOR 636431c794ade88f5da17ba06436f781b009c745ddeDan Gohman } 637431c794ade88f5da17ba06436f781b009c745ddeDan Gohman 63842c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman ModRefBehavior Min = UnknownModRefBehavior; 63942c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman 640431c794ade88f5da17ba06436f781b009c745ddeDan Gohman // If the function declares it only reads memory, go with that. 6416ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (F->onlyReadsMemory()) 64242c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman Min = OnlyReadsMemory; 6436ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 644431c794ade88f5da17ba06436f781b009c745ddeDan Gohman // Otherwise be conservative. 64542c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman return ModRefBehavior(AliasAnalysis::getModRefBehavior(F) & Min); 6466ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman} 647e79422096ea5319a365d160693d0957a2a4df75eOwen Anderson 6485d56b2d47d324ecf2d1cc1551a28cce49d16ab01Chris Lattner/// getModRefInfo - Check to see if the specified callsite can clobber the 6495d56b2d47d324ecf2d1cc1551a28cce49d16ab01Chris Lattner/// specified memory object. Since we only look at local properties of this 6505d56b2d47d324ecf2d1cc1551a28cce49d16ab01Chris Lattner/// function, we really can't say much about this query. We do, however, use 6515d56b2d47d324ecf2d1cc1551a28cce49d16ab01Chris Lattner/// simple "address taken" analysis on local objects. 65204b75935462642641469fb264aab9f1110ce2666Chris LattnerAliasAnalysis::ModRefResult 65379fca6fea87be7221843031870bbf2c9ae1fc555Dan GohmanBasicAliasAnalysis::getModRefInfo(ImmutableCallSite CS, 654b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman const Location &Loc) { 655b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman assert(notDifferentParent(CS.getInstruction(), Loc.Ptr) && 6569e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman "AliasAnalysis query involving multiple functions!"); 6579e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman 658bd1801b5553c8be3960255a92738464e0010b6f6Dan Gohman const Value *Object = GetUnderlyingObject(Loc.Ptr, TD); 65992e803c2a412cda777535e4ae01fe78007997f8aChris Lattner 660b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman // If this is a tail call and Loc.Ptr points to a stack location, we know that 66192e803c2a412cda777535e4ae01fe78007997f8aChris Lattner // the tail call cannot access or modify the local stack. 66292e803c2a412cda777535e4ae01fe78007997f8aChris Lattner // We cannot exclude byval arguments here; these belong to the caller of 66392e803c2a412cda777535e4ae01fe78007997f8aChris Lattner // the current function not to the current function, and a tail callee 66492e803c2a412cda777535e4ae01fe78007997f8aChris Lattner // may reference them. 66592e803c2a412cda777535e4ae01fe78007997f8aChris Lattner if (isa<AllocaInst>(Object)) 66679fca6fea87be7221843031870bbf2c9ae1fc555Dan Gohman if (const CallInst *CI = dyn_cast<CallInst>(CS.getInstruction())) 66792e803c2a412cda777535e4ae01fe78007997f8aChris Lattner if (CI->isTailCall()) 66892e803c2a412cda777535e4ae01fe78007997f8aChris Lattner return NoModRef; 66992e803c2a412cda777535e4ae01fe78007997f8aChris Lattner 67092e803c2a412cda777535e4ae01fe78007997f8aChris Lattner // If the pointer is to a locally allocated object that does not escape, 671b34b82e9d1ec6ddbdc23dfd9bb65cd9d22527cd2Chris Lattner // then the call can not mod/ref the pointer unless the call takes the pointer 672b34b82e9d1ec6ddbdc23dfd9bb65cd9d22527cd2Chris Lattner // as an argument, and itself doesn't capture it. 673403ac2ece33046c58b66fffa105184f44fa4527eChris Lattner if (!isa<Constant>(Object) && CS.getInstruction() != Object && 67421de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman isNonEscapingLocalObject(Object)) { 675b34b82e9d1ec6ddbdc23dfd9bb65cd9d22527cd2Chris Lattner bool PassedAsArg = false; 676b34b82e9d1ec6ddbdc23dfd9bb65cd9d22527cd2Chris Lattner unsigned ArgNo = 0; 67779fca6fea87be7221843031870bbf2c9ae1fc555Dan Gohman for (ImmutableCallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 678b34b82e9d1ec6ddbdc23dfd9bb65cd9d22527cd2Chris Lattner CI != CE; ++CI, ++ArgNo) { 679c10ecd8f23ebb4541acbe18563b7f19c4f79e721Chris Lattner // Only look at the no-capture or byval pointer arguments. If this 680c10ecd8f23ebb4541acbe18563b7f19c4f79e721Chris Lattner // pointer were passed to arguments that were neither of these, then it 681c10ecd8f23ebb4541acbe18563b7f19c4f79e721Chris Lattner // couldn't be no-capture. 6821df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands if (!(*CI)->getType()->isPointerTy() || 683173862e5468fbcf4b022b9088d2c81b25c2d60c5Nick Lewycky (!CS.doesNotCapture(ArgNo) && !CS.isByValArgument(ArgNo))) 684b34b82e9d1ec6ddbdc23dfd9bb65cd9d22527cd2Chris Lattner continue; 685b34b82e9d1ec6ddbdc23dfd9bb65cd9d22527cd2Chris Lattner 686b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman // If this is a no-capture pointer argument, see if we can tell that it 687b34b82e9d1ec6ddbdc23dfd9bb65cd9d22527cd2Chris Lattner // is impossible to alias the pointer we're checking. If not, we have to 688b34b82e9d1ec6ddbdc23dfd9bb65cd9d22527cd2Chris Lattner // assume that the call could touch the pointer, even though it doesn't 689b34b82e9d1ec6ddbdc23dfd9bb65cd9d22527cd2Chris Lattner // escape. 690e6fadced87cef8faa69f00e3e13fc3a7369210b1Eli Friedman if (!isNoAlias(Location(*CI), Location(Object))) { 691b34b82e9d1ec6ddbdc23dfd9bb65cd9d22527cd2Chris Lattner PassedAsArg = true; 692b34b82e9d1ec6ddbdc23dfd9bb65cd9d22527cd2Chris Lattner break; 693b34b82e9d1ec6ddbdc23dfd9bb65cd9d22527cd2Chris Lattner } 694b34b82e9d1ec6ddbdc23dfd9bb65cd9d22527cd2Chris Lattner } 695a413960a4847b996e48ebad5c41f094df441641dChris Lattner 696b34b82e9d1ec6ddbdc23dfd9bb65cd9d22527cd2Chris Lattner if (!PassedAsArg) 69792e803c2a412cda777535e4ae01fe78007997f8aChris Lattner return NoModRef; 69892e803c2a412cda777535e4ae01fe78007997f8aChris Lattner } 69992e803c2a412cda777535e4ae01fe78007997f8aChris Lattner 70069acc93b3de6854732a6d91b581c3c29b59bb315Owen Anderson const TargetLibraryInfo &TLI = getAnalysis<TargetLibraryInfo>(); 70142c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman ModRefResult Min = ModRef; 70242c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman 70392e803c2a412cda777535e4ae01fe78007997f8aChris Lattner // Finally, handle specific knowledge of intrinsics. 70479fca6fea87be7221843031870bbf2c9ae1fc555Dan Gohman const IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction()); 7056ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (II != 0) 7066ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman switch (II->getIntrinsicID()) { 7076ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman default: break; 7086ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman case Intrinsic::memcpy: 7096ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman case Intrinsic::memmove: { 7103da848bbda62b25c12335998aaa44ab361f0bf15Dan Gohman uint64_t Len = UnknownSize; 7116ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getArgOperand(2))) 7126ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman Len = LenCI->getZExtValue(); 71371339c965ca6268b9bff91213364783c3d06f666Gabor Greif Value *Dest = II->getArgOperand(0); 7146ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman Value *Src = II->getArgOperand(1); 71513815d9d3eec3d0ef2fc2f8a09e8ca8a9fa2654aChris Lattner // If it can't overlap the source dest, then it doesn't modref the loc. 716b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if (isNoAlias(Location(Dest, Len), Loc)) { 717b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if (isNoAlias(Location(Src, Len), Loc)) 7186ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return NoModRef; 71913815d9d3eec3d0ef2fc2f8a09e8ca8a9fa2654aChris Lattner // If it can't overlap the dest, then worst case it reads the loc. 72042c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman Min = Ref; 72113815d9d3eec3d0ef2fc2f8a09e8ca8a9fa2654aChris Lattner } else if (isNoAlias(Location(Src, Len), Loc)) { 72213815d9d3eec3d0ef2fc2f8a09e8ca8a9fa2654aChris Lattner // If it can't overlap the source, then worst case it mutates the loc. 72313815d9d3eec3d0ef2fc2f8a09e8ca8a9fa2654aChris Lattner Min = Mod; 7246ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman } 7256ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman break; 7266ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman } 7276ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman case Intrinsic::memset: 7286ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // Since memset is 'accesses arguments' only, the AliasAnalysis base class 7296ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // will handle it for the variable length case. 7306ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getArgOperand(2))) { 7313da848bbda62b25c12335998aaa44ab361f0bf15Dan Gohman uint64_t Len = LenCI->getZExtValue(); 7326ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman Value *Dest = II->getArgOperand(0); 733b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if (isNoAlias(Location(Dest, Len), Loc)) 7346ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return NoModRef; 7356ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman } 736201d1e56bb7535802c70d5eb46601afcc325045dChris Lattner // We know that memset doesn't load anything. 737201d1e56bb7535802c70d5eb46601afcc325045dChris Lattner Min = Mod; 7386ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman break; 7396ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman case Intrinsic::lifetime_start: 7406ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman case Intrinsic::lifetime_end: 7416ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman case Intrinsic::invariant_start: { 7423da848bbda62b25c12335998aaa44ab361f0bf15Dan Gohman uint64_t PtrSize = 7436ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman cast<ConstantInt>(II->getArgOperand(0))->getZExtValue(); 744b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if (isNoAlias(Location(II->getArgOperand(1), 745b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman PtrSize, 746b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman II->getMetadata(LLVMContext::MD_tbaa)), 747b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman Loc)) 74892e803c2a412cda777535e4ae01fe78007997f8aChris Lattner return NoModRef; 7496ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman break; 7505c9be67cffd689fa0e2111a3c60d7556c07b8608Nick Lewycky } 7516ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman case Intrinsic::invariant_end: { 7523da848bbda62b25c12335998aaa44ab361f0bf15Dan Gohman uint64_t PtrSize = 7536ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman cast<ConstantInt>(II->getArgOperand(1))->getZExtValue(); 754b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if (isNoAlias(Location(II->getArgOperand(2), 755b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman PtrSize, 756b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman II->getMetadata(LLVMContext::MD_tbaa)), 757b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman Loc)) 75892e803c2a412cda777535e4ae01fe78007997f8aChris Lattner return NoModRef; 7596ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman break; 7606ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman } 7611d7e818a386610da70d56809ea67eb81e0f9c84bDan Gohman case Intrinsic::arm_neon_vld1: { 7621d7e818a386610da70d56809ea67eb81e0f9c84bDan Gohman // LLVM's vld1 and vst1 intrinsics currently only support a single 7631d7e818a386610da70d56809ea67eb81e0f9c84bDan Gohman // vector register. 7641d7e818a386610da70d56809ea67eb81e0f9c84bDan Gohman uint64_t Size = 7651d7e818a386610da70d56809ea67eb81e0f9c84bDan Gohman TD ? TD->getTypeStoreSize(II->getType()) : UnknownSize; 7661d7e818a386610da70d56809ea67eb81e0f9c84bDan Gohman if (isNoAlias(Location(II->getArgOperand(0), Size, 7671d7e818a386610da70d56809ea67eb81e0f9c84bDan Gohman II->getMetadata(LLVMContext::MD_tbaa)), 7681d7e818a386610da70d56809ea67eb81e0f9c84bDan Gohman Loc)) 7691d7e818a386610da70d56809ea67eb81e0f9c84bDan Gohman return NoModRef; 7701d7e818a386610da70d56809ea67eb81e0f9c84bDan Gohman break; 7711d7e818a386610da70d56809ea67eb81e0f9c84bDan Gohman } 7721d7e818a386610da70d56809ea67eb81e0f9c84bDan Gohman case Intrinsic::arm_neon_vst1: { 7731d7e818a386610da70d56809ea67eb81e0f9c84bDan Gohman uint64_t Size = 7741d7e818a386610da70d56809ea67eb81e0f9c84bDan Gohman TD ? TD->getTypeStoreSize(II->getArgOperand(1)->getType()) : UnknownSize; 7751d7e818a386610da70d56809ea67eb81e0f9c84bDan Gohman if (isNoAlias(Location(II->getArgOperand(0), Size, 7761d7e818a386610da70d56809ea67eb81e0f9c84bDan Gohman II->getMetadata(LLVMContext::MD_tbaa)), 7771d7e818a386610da70d56809ea67eb81e0f9c84bDan Gohman Loc)) 7781d7e818a386610da70d56809ea67eb81e0f9c84bDan Gohman return NoModRef; 7791d7e818a386610da70d56809ea67eb81e0f9c84bDan Gohman break; 7801d7e818a386610da70d56809ea67eb81e0f9c84bDan Gohman } 78192e803c2a412cda777535e4ae01fe78007997f8aChris Lattner } 78204b75935462642641469fb264aab9f1110ce2666Chris Lattner 78369acc93b3de6854732a6d91b581c3c29b59bb315Owen Anderson // We can bound the aliasing properties of memset_pattern16 just as we can 78469acc93b3de6854732a6d91b581c3c29b59bb315Owen Anderson // for memcpy/memset. This is particularly important because the 78569acc93b3de6854732a6d91b581c3c29b59bb315Owen Anderson // LoopIdiomRecognizer likes to turn loops into calls to memset_pattern16 78669acc93b3de6854732a6d91b581c3c29b59bb315Owen Anderson // whenever possible. 78769acc93b3de6854732a6d91b581c3c29b59bb315Owen Anderson else if (TLI.has(LibFunc::memset_pattern16) && 78869acc93b3de6854732a6d91b581c3c29b59bb315Owen Anderson CS.getCalledFunction() && 78969acc93b3de6854732a6d91b581c3c29b59bb315Owen Anderson CS.getCalledFunction()->getName() == "memset_pattern16") { 79069acc93b3de6854732a6d91b581c3c29b59bb315Owen Anderson const Function *MS = CS.getCalledFunction(); 79169acc93b3de6854732a6d91b581c3c29b59bb315Owen Anderson FunctionType *MemsetType = MS->getFunctionType(); 79269acc93b3de6854732a6d91b581c3c29b59bb315Owen Anderson if (!MemsetType->isVarArg() && MemsetType->getNumParams() == 3 && 79369acc93b3de6854732a6d91b581c3c29b59bb315Owen Anderson isa<PointerType>(MemsetType->getParamType(0)) && 79469acc93b3de6854732a6d91b581c3c29b59bb315Owen Anderson isa<PointerType>(MemsetType->getParamType(1)) && 79569acc93b3de6854732a6d91b581c3c29b59bb315Owen Anderson isa<IntegerType>(MemsetType->getParamType(2))) { 79669acc93b3de6854732a6d91b581c3c29b59bb315Owen Anderson uint64_t Len = UnknownSize; 79769acc93b3de6854732a6d91b581c3c29b59bb315Owen Anderson if (const ConstantInt *LenCI = dyn_cast<ConstantInt>(CS.getArgument(2))) 79869acc93b3de6854732a6d91b581c3c29b59bb315Owen Anderson Len = LenCI->getZExtValue(); 79969acc93b3de6854732a6d91b581c3c29b59bb315Owen Anderson const Value *Dest = CS.getArgument(0); 80069acc93b3de6854732a6d91b581c3c29b59bb315Owen Anderson const Value *Src = CS.getArgument(1); 80169acc93b3de6854732a6d91b581c3c29b59bb315Owen Anderson // If it can't overlap the source dest, then it doesn't modref the loc. 80269acc93b3de6854732a6d91b581c3c29b59bb315Owen Anderson if (isNoAlias(Location(Dest, Len), Loc)) { 803e421ad64ff76b7d89a4ddf41bdb056376bc5f6a6Owen Anderson // Always reads 16 bytes of the source. 804e421ad64ff76b7d89a4ddf41bdb056376bc5f6a6Owen Anderson if (isNoAlias(Location(Src, 16), Loc)) 80569acc93b3de6854732a6d91b581c3c29b59bb315Owen Anderson return NoModRef; 80669acc93b3de6854732a6d91b581c3c29b59bb315Owen Anderson // If it can't overlap the dest, then worst case it reads the loc. 80769acc93b3de6854732a6d91b581c3c29b59bb315Owen Anderson Min = Ref; 808e421ad64ff76b7d89a4ddf41bdb056376bc5f6a6Owen Anderson // Always reads 16 bytes of the source. 809e421ad64ff76b7d89a4ddf41bdb056376bc5f6a6Owen Anderson } else if (isNoAlias(Location(Src, 16), Loc)) { 81069acc93b3de6854732a6d91b581c3c29b59bb315Owen Anderson // If it can't overlap the source, then worst case it mutates the loc. 81169acc93b3de6854732a6d91b581c3c29b59bb315Owen Anderson Min = Mod; 81269acc93b3de6854732a6d91b581c3c29b59bb315Owen Anderson } 81369acc93b3de6854732a6d91b581c3c29b59bb315Owen Anderson } 81469acc93b3de6854732a6d91b581c3c29b59bb315Owen Anderson } 81569acc93b3de6854732a6d91b581c3c29b59bb315Owen Anderson 816bbcc147220d885b129743c009c3e46a7a3d8ab2eChris Lattner // The AliasAnalysis base class has some smarts, lets use them. 81742c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman return ModRefResult(AliasAnalysis::getModRefInfo(CS, Loc) & Min); 81865924111bf648db8f20599f485be918c7aa1e7efDan Gohman} 819a413960a4847b996e48ebad5c41f094df441641dChris Lattner 820029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighoferstatic bool areVarIndicesEqual(SmallVector<VariableGEPIndex, 4> &Indices1, 821029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer SmallVector<VariableGEPIndex, 4> &Indices2) { 822029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer unsigned Size1 = Indices1.size(); 823029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer unsigned Size2 = Indices2.size(); 824029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer 825029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer if (Size1 != Size2) 826029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer return false; 827029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer 828029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer for (unsigned I = 0; I != Size1; ++I) 829029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer if (Indices1[I] != Indices2[I]) 830029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer return false; 831029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer 832029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer return true; 833029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer} 834029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer 835539c9b99c27c0fe4f22a0498bc65334e4aa72ef0Chris Lattner/// aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP instruction 836539c9b99c27c0fe4f22a0498bc65334e4aa72ef0Chris Lattner/// against another pointer. We know that V1 is a GEP, but we don't know 837bd1801b5553c8be3960255a92738464e0010b6f6Dan Gohman/// anything about V2. UnderlyingV1 is GetUnderlyingObject(GEP1, TD), 83823e2a5b2fff8b5b483a464ce1bea9a686e6731deChris Lattner/// UnderlyingV2 is the same for V2. 839539c9b99c27c0fe4f22a0498bc65334e4aa72ef0Chris Lattner/// 840d501c13b7d6ce418b0144886dde16525d13f835aChris LattnerAliasAnalysis::AliasResult 8413da848bbda62b25c12335998aaa44ab361f0bf15Dan GohmanBasicAliasAnalysis::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size, 842029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer const MDNode *V1TBAAInfo, 8433da848bbda62b25c12335998aaa44ab361f0bf15Dan Gohman const Value *V2, uint64_t V2Size, 8446cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman const MDNode *V2TBAAInfo, 84523e2a5b2fff8b5b483a464ce1bea9a686e6731deChris Lattner const Value *UnderlyingV1, 84623e2a5b2fff8b5b483a464ce1bea9a686e6731deChris Lattner const Value *UnderlyingV2) { 847d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner int64_t GEP1BaseOffset; 8488807e9fbdf81221b277506064c46829732f019cfChris Lattner SmallVector<VariableGEPIndex, 4> GEP1VariableIndices; 849d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner 850029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer // If we have two gep instructions with must-alias or not-alias'ing base 851029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer // pointers, figure out if the indexes to the GEP tell us anything about the 852029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer // derived pointer. 853539c9b99c27c0fe4f22a0498bc65334e4aa72ef0Chris Lattner if (const GEPOperator *GEP2 = dyn_cast<GEPOperator>(V2)) { 854029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer // Check for geps of non-aliasing underlying pointers where the offsets are 855029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer // identical. 856029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer if (V1Size == V2Size) { 857029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer // Do the base pointers alias assuming type and size. 858029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer AliasResult PreciseBaseAlias = aliasCheck(UnderlyingV1, V1Size, 859029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer V1TBAAInfo, UnderlyingV2, 860029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer V2Size, V2TBAAInfo); 861029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer if (PreciseBaseAlias == NoAlias) { 862029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer // See if the computed offset from the common pointer tells us about the 863029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer // relation of the resulting pointer. 864029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer int64_t GEP2BaseOffset; 865029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer SmallVector<VariableGEPIndex, 4> GEP2VariableIndices; 866029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer const Value *GEP2BasePtr = 867029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices, TD); 868029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer const Value *GEP1BasePtr = 869029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD); 870029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer // DecomposeGEPExpression and GetUnderlyingObject should return the 871029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer // same result except when DecomposeGEPExpression has no TargetData. 872029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) { 873029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer assert(TD == 0 && 874029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer "DecomposeGEPExpression and GetUnderlyingObject disagree!"); 875029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer return MayAlias; 876029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer } 877029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer // Same offsets. 878029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer if (GEP1BaseOffset == GEP2BaseOffset && 879029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer areVarIndicesEqual(GEP1VariableIndices, GEP2VariableIndices)) 880029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer return NoAlias; 881029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer GEP1VariableIndices.clear(); 882029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer } 883029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer } 884029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer 885b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Do the base pointers alias? 8866cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman AliasResult BaseAlias = aliasCheck(UnderlyingV1, UnknownSize, 0, 8876cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman UnderlyingV2, UnknownSize, 0); 888d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner 889d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // If we get a No or May, then return it immediately, no amount of analysis 890d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // will improve this situation. 891d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner if (BaseAlias != MustAlias) return BaseAlias; 892d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner 893d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // Otherwise, we have a MustAlias. Since the base pointers alias each other 894d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // exactly, see if the computed offset from the common pointer tells us 895d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // about the relation of the resulting pointer. 896d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner const Value *GEP1BasePtr = 897d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD); 898d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner 899d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner int64_t GEP2BaseOffset; 9008807e9fbdf81221b277506064c46829732f019cfChris Lattner SmallVector<VariableGEPIndex, 4> GEP2VariableIndices; 901d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner const Value *GEP2BasePtr = 902d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices, TD); 903d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner 904029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer // DecomposeGEPExpression and GetUnderlyingObject should return the 905029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer // same result except when DecomposeGEPExpression has no TargetData. 906d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) { 907d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner assert(TD == 0 && 9085034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman "DecomposeGEPExpression and GetUnderlyingObject disagree!"); 909d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner return MayAlias; 910b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 911d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner 912d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // Subtract the GEP2 pointer from the GEP1 pointer to find out their 913d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // symbolic difference. 914d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner GEP1BaseOffset -= GEP2BaseOffset; 9156fc24467e91a2c515fa5347e90071573c454bccaDan Gohman GetIndexDifference(GEP1VariableIndices, GEP2VariableIndices); 916d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner 917d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner } else { 918d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // Check to see if these two pointers are related by the getelementptr 919d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // instruction. If one pointer is a GEP with a non-zero index of the other 920d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // pointer, we know they cannot alias. 9215369250b73e172efe886b20bfcdab74e5b251a71Chris Lattner 9225369250b73e172efe886b20bfcdab74e5b251a71Chris Lattner // If both accesses are unknown size, we can't do anything useful here. 923ef1cfac9e50def9097cd3e3ab3c5cad7f4c758ccDan Gohman if (V1Size == UnknownSize && V2Size == UnknownSize) 924d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner return MayAlias; 925681a33e26dd3222477f13520b94e7417bff59e32Evan Cheng 9266cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman AliasResult R = aliasCheck(UnderlyingV1, UnknownSize, 0, 9276cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman V2, V2Size, V2TBAAInfo); 928d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner if (R != MustAlias) 929d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // If V2 may alias GEP base pointer, conservatively returns MayAlias. 930d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // If V2 is known not to alias GEP base pointer, then the two values 931d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // cannot alias per GEP semantics: "A pointer value formed from a 932d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // getelementptr instruction is associated with the addresses associated 933d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // with the first operand of the getelementptr". 934d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner return R; 935d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner 936d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner const Value *GEP1BasePtr = 937d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD); 938d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner 939029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer // DecomposeGEPExpression and GetUnderlyingObject should return the 940029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer // same result except when DecomposeGEPExpression has no TargetData. 941d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner if (GEP1BasePtr != UnderlyingV1) { 942d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner assert(TD == 0 && 9435034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman "DecomposeGEPExpression and GetUnderlyingObject disagree!"); 944d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner return MayAlias; 945d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner } 94623e2a5b2fff8b5b483a464ce1bea9a686e6731deChris Lattner } 94723e2a5b2fff8b5b483a464ce1bea9a686e6731deChris Lattner 948d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // In the two GEP Case, if there is no difference in the offsets of the 949d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // computed pointers, the resultant pointers are a must alias. This 950d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // hapens when we have two lexically identical GEP's (for example). 951d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // 952d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // In the other case, if we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 953d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // must aliases the GEP, the end result is a must alias also. 954d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner if (GEP1BaseOffset == 0 && GEP1VariableIndices.empty()) 955681a33e26dd3222477f13520b94e7417bff59e32Evan Cheng return MustAlias; 956681a33e26dd3222477f13520b94e7417bff59e32Evan Cheng 95781ac8ddc674d1589dbba97f752ec77750901f510Eli Friedman // If there is a constant difference between the pointers, but the difference 95881ac8ddc674d1589dbba97f752ec77750901f510Eli Friedman // is less than the size of the associated memory object, then we know 95981ac8ddc674d1589dbba97f752ec77750901f510Eli Friedman // that the objects are partially overlapping. If the difference is 96081ac8ddc674d1589dbba97f752ec77750901f510Eli Friedman // greater, we know they do not overlap. 9610f7f194416b9f139d4233b499a1f56b20bd84022Dan Gohman if (GEP1BaseOffset != 0 && GEP1VariableIndices.empty()) { 96281ac8ddc674d1589dbba97f752ec77750901f510Eli Friedman if (GEP1BaseOffset >= 0) { 96381ac8ddc674d1589dbba97f752ec77750901f510Eli Friedman if (V2Size != UnknownSize) { 96481ac8ddc674d1589dbba97f752ec77750901f510Eli Friedman if ((uint64_t)GEP1BaseOffset < V2Size) 96581ac8ddc674d1589dbba97f752ec77750901f510Eli Friedman return PartialAlias; 96681ac8ddc674d1589dbba97f752ec77750901f510Eli Friedman return NoAlias; 96781ac8ddc674d1589dbba97f752ec77750901f510Eli Friedman } 96881ac8ddc674d1589dbba97f752ec77750901f510Eli Friedman } else { 96981ac8ddc674d1589dbba97f752ec77750901f510Eli Friedman if (V1Size != UnknownSize) { 97081ac8ddc674d1589dbba97f752ec77750901f510Eli Friedman if (-(uint64_t)GEP1BaseOffset < V1Size) 97181ac8ddc674d1589dbba97f752ec77750901f510Eli Friedman return PartialAlias; 97281ac8ddc674d1589dbba97f752ec77750901f510Eli Friedman return NoAlias; 97381ac8ddc674d1589dbba97f752ec77750901f510Eli Friedman } 97481ac8ddc674d1589dbba97f752ec77750901f510Eli Friedman } 9750f7f194416b9f139d4233b499a1f56b20bd84022Dan Gohman } 9760f7f194416b9f139d4233b499a1f56b20bd84022Dan Gohman 97781ac8ddc674d1589dbba97f752ec77750901f510Eli Friedman // Try to distinguish something like &A[i][1] against &A[42][0]. 97881ac8ddc674d1589dbba97f752ec77750901f510Eli Friedman // Grab the least significant bit set in any of the scales. 979184166da619ac7f14d8460b4b0f8f85bfc601ebcEli Friedman if (!GEP1VariableIndices.empty()) { 980184166da619ac7f14d8460b4b0f8f85bfc601ebcEli Friedman uint64_t Modulo = 0; 981184166da619ac7f14d8460b4b0f8f85bfc601ebcEli Friedman for (unsigned i = 0, e = GEP1VariableIndices.size(); i != e; ++i) 982184166da619ac7f14d8460b4b0f8f85bfc601ebcEli Friedman Modulo |= (uint64_t)GEP1VariableIndices[i].Scale; 983184166da619ac7f14d8460b4b0f8f85bfc601ebcEli Friedman Modulo = Modulo ^ (Modulo & (Modulo - 1)); 984184166da619ac7f14d8460b4b0f8f85bfc601ebcEli Friedman 985184166da619ac7f14d8460b4b0f8f85bfc601ebcEli Friedman // We can compute the difference between the two addresses 986184166da619ac7f14d8460b4b0f8f85bfc601ebcEli Friedman // mod Modulo. Check whether that difference guarantees that the 987184166da619ac7f14d8460b4b0f8f85bfc601ebcEli Friedman // two locations do not alias. 988184166da619ac7f14d8460b4b0f8f85bfc601ebcEli Friedman uint64_t ModOffset = (uint64_t)GEP1BaseOffset & (Modulo - 1); 989184166da619ac7f14d8460b4b0f8f85bfc601ebcEli Friedman if (V1Size != UnknownSize && V2Size != UnknownSize && 990184166da619ac7f14d8460b4b0f8f85bfc601ebcEli Friedman ModOffset >= V2Size && V1Size <= Modulo - ModOffset) 991184166da619ac7f14d8460b4b0f8f85bfc601ebcEli Friedman return NoAlias; 992184166da619ac7f14d8460b4b0f8f85bfc601ebcEli Friedman } 99381ac8ddc674d1589dbba97f752ec77750901f510Eli Friedman 9945f1312c36e811562c3ea3136332771aed98016edDan Gohman // Statically, we can see that the base objects are the same, but the 9955f1312c36e811562c3ea3136332771aed98016edDan Gohman // pointers have dynamic offsets which we can't resolve. And none of our 9965f1312c36e811562c3ea3136332771aed98016edDan Gohman // little tricks above worked. 9975f1312c36e811562c3ea3136332771aed98016edDan Gohman // 9985f1312c36e811562c3ea3136332771aed98016edDan Gohman // TODO: Returning PartialAlias instead of MayAlias is a mild hack; the 9995f1312c36e811562c3ea3136332771aed98016edDan Gohman // practical effect of this is protecting TBAA in the case of dynamic 1000ebad58dc58d73097b3546e7fcb6fd7c17336d413Dan Gohman // indices into arrays of unions or malloc'd memory. 10015f1312c36e811562c3ea3136332771aed98016edDan Gohman return PartialAlias; 1002094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng} 1003094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng 1004965fefa1add8151619cc340c373a812c94342e58Dan Gohmanstatic AliasAnalysis::AliasResult 1005965fefa1add8151619cc340c373a812c94342e58Dan GohmanMergeAliasResults(AliasAnalysis::AliasResult A, AliasAnalysis::AliasResult B) { 1006965fefa1add8151619cc340c373a812c94342e58Dan Gohman // If the results agree, take it. 1007965fefa1add8151619cc340c373a812c94342e58Dan Gohman if (A == B) 1008965fefa1add8151619cc340c373a812c94342e58Dan Gohman return A; 1009965fefa1add8151619cc340c373a812c94342e58Dan Gohman // A mix of PartialAlias and MustAlias is PartialAlias. 1010965fefa1add8151619cc340c373a812c94342e58Dan Gohman if ((A == AliasAnalysis::PartialAlias && B == AliasAnalysis::MustAlias) || 1011965fefa1add8151619cc340c373a812c94342e58Dan Gohman (B == AliasAnalysis::PartialAlias && A == AliasAnalysis::MustAlias)) 1012965fefa1add8151619cc340c373a812c94342e58Dan Gohman return AliasAnalysis::PartialAlias; 1013965fefa1add8151619cc340c373a812c94342e58Dan Gohman // Otherwise, we don't know anything. 1014965fefa1add8151619cc340c373a812c94342e58Dan Gohman return AliasAnalysis::MayAlias; 1015965fefa1add8151619cc340c373a812c94342e58Dan Gohman} 1016965fefa1add8151619cc340c373a812c94342e58Dan Gohman 10175d56b2d47d324ecf2d1cc1551a28cce49d16ab01Chris Lattner/// aliasSelect - Provide a bunch of ad-hoc rules to disambiguate a Select 10185d56b2d47d324ecf2d1cc1551a28cce49d16ab01Chris Lattner/// instruction against another. 10196665b0ea688941c1c044a5c034ee45d45862168fDan GohmanAliasAnalysis::AliasResult 10203da848bbda62b25c12335998aaa44ab361f0bf15Dan GohmanBasicAliasAnalysis::aliasSelect(const SelectInst *SI, uint64_t SISize, 10216cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman const MDNode *SITBAAInfo, 10223da848bbda62b25c12335998aaa44ab361f0bf15Dan Gohman const Value *V2, uint64_t V2Size, 10236cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman const MDNode *V2TBAAInfo) { 10246665b0ea688941c1c044a5c034ee45d45862168fDan Gohman // If the values are Selects with the same condition, we can do a more precise 10256665b0ea688941c1c044a5c034ee45d45862168fDan Gohman // check: just check for aliases between the values on corresponding arms. 10266665b0ea688941c1c044a5c034ee45d45862168fDan Gohman if (const SelectInst *SI2 = dyn_cast<SelectInst>(V2)) 10276665b0ea688941c1c044a5c034ee45d45862168fDan Gohman if (SI->getCondition() == SI2->getCondition()) { 10286665b0ea688941c1c044a5c034ee45d45862168fDan Gohman AliasResult Alias = 10296cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman aliasCheck(SI->getTrueValue(), SISize, SITBAAInfo, 10306cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman SI2->getTrueValue(), V2Size, V2TBAAInfo); 10316665b0ea688941c1c044a5c034ee45d45862168fDan Gohman if (Alias == MayAlias) 10326665b0ea688941c1c044a5c034ee45d45862168fDan Gohman return MayAlias; 10336665b0ea688941c1c044a5c034ee45d45862168fDan Gohman AliasResult ThisAlias = 10346cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman aliasCheck(SI->getFalseValue(), SISize, SITBAAInfo, 10356cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman SI2->getFalseValue(), V2Size, V2TBAAInfo); 1036965fefa1add8151619cc340c373a812c94342e58Dan Gohman return MergeAliasResults(ThisAlias, Alias); 10376665b0ea688941c1c044a5c034ee45d45862168fDan Gohman } 10386665b0ea688941c1c044a5c034ee45d45862168fDan Gohman 10396665b0ea688941c1c044a5c034ee45d45862168fDan Gohman // If both arms of the Select node NoAlias or MustAlias V2, then returns 10406665b0ea688941c1c044a5c034ee45d45862168fDan Gohman // NoAlias / MustAlias. Otherwise, returns MayAlias. 10416665b0ea688941c1c044a5c034ee45d45862168fDan Gohman AliasResult Alias = 10426cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman aliasCheck(V2, V2Size, V2TBAAInfo, SI->getTrueValue(), SISize, SITBAAInfo); 10436665b0ea688941c1c044a5c034ee45d45862168fDan Gohman if (Alias == MayAlias) 10446665b0ea688941c1c044a5c034ee45d45862168fDan Gohman return MayAlias; 104550f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman 10466665b0ea688941c1c044a5c034ee45d45862168fDan Gohman AliasResult ThisAlias = 10476cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman aliasCheck(V2, V2Size, V2TBAAInfo, SI->getFalseValue(), SISize, SITBAAInfo); 1048965fefa1add8151619cc340c373a812c94342e58Dan Gohman return MergeAliasResults(ThisAlias, Alias); 10496665b0ea688941c1c044a5c034ee45d45862168fDan Gohman} 10506665b0ea688941c1c044a5c034ee45d45862168fDan Gohman 1051d83c2ca3368f90d60234848e751842d29b248039Evan Cheng// aliasPHI - Provide a bunch of ad-hoc rules to disambiguate a PHI instruction 10523dbe43b1b50472f4f24df17fff5ac2443be63d5fEvan Cheng// against another. 105350a5914e129c348e8878d4654b4306e0349281c2Evan ChengAliasAnalysis::AliasResult 10543da848bbda62b25c12335998aaa44ab361f0bf15Dan GohmanBasicAliasAnalysis::aliasPHI(const PHINode *PN, uint64_t PNSize, 10556cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman const MDNode *PNTBAAInfo, 10563da848bbda62b25c12335998aaa44ab361f0bf15Dan Gohman const Value *V2, uint64_t V2Size, 10576cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman const MDNode *V2TBAAInfo) { 10586665b0ea688941c1c044a5c034ee45d45862168fDan Gohman // If the values are PHIs in the same block, we can do a more precise 10596665b0ea688941c1c044a5c034ee45d45862168fDan Gohman // as well as efficient check: just check for aliases between the values 10606665b0ea688941c1c044a5c034ee45d45862168fDan Gohman // on corresponding edges. 10616665b0ea688941c1c044a5c034ee45d45862168fDan Gohman if (const PHINode *PN2 = dyn_cast<PHINode>(V2)) 10626665b0ea688941c1c044a5c034ee45d45862168fDan Gohman if (PN2->getParent() == PN->getParent()) { 10633d5f96ee1bf5189e324089976026ed09b6be9e58Arnold Schwaighofer LocPair Locs(Location(PN, PNSize, PNTBAAInfo), 10643d5f96ee1bf5189e324089976026ed09b6be9e58Arnold Schwaighofer Location(V2, V2Size, V2TBAAInfo)); 10653d5f96ee1bf5189e324089976026ed09b6be9e58Arnold Schwaighofer if (PN > V2) 10663d5f96ee1bf5189e324089976026ed09b6be9e58Arnold Schwaighofer std::swap(Locs.first, Locs.second); 10673d5f96ee1bf5189e324089976026ed09b6be9e58Arnold Schwaighofer 10686665b0ea688941c1c044a5c034ee45d45862168fDan Gohman AliasResult Alias = 10696cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman aliasCheck(PN->getIncomingValue(0), PNSize, PNTBAAInfo, 10706665b0ea688941c1c044a5c034ee45d45862168fDan Gohman PN2->getIncomingValueForBlock(PN->getIncomingBlock(0)), 10716cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman V2Size, V2TBAAInfo); 10726665b0ea688941c1c044a5c034ee45d45862168fDan Gohman if (Alias == MayAlias) 10736665b0ea688941c1c044a5c034ee45d45862168fDan Gohman return MayAlias; 10743d5f96ee1bf5189e324089976026ed09b6be9e58Arnold Schwaighofer 10753d5f96ee1bf5189e324089976026ed09b6be9e58Arnold Schwaighofer // If the first source of the PHI nodes NoAlias and the other inputs are 10763d5f96ee1bf5189e324089976026ed09b6be9e58Arnold Schwaighofer // the PHI node itself through some amount of recursion this does not add 10773d5f96ee1bf5189e324089976026ed09b6be9e58Arnold Schwaighofer // any new information so just return NoAlias. 10783d5f96ee1bf5189e324089976026ed09b6be9e58Arnold Schwaighofer // bb: 10793d5f96ee1bf5189e324089976026ed09b6be9e58Arnold Schwaighofer // ptr = ptr2 + 1 10803d5f96ee1bf5189e324089976026ed09b6be9e58Arnold Schwaighofer // loop: 10813d5f96ee1bf5189e324089976026ed09b6be9e58Arnold Schwaighofer // ptr_phi = phi [bb, ptr], [loop, ptr_plus_one] 10823d5f96ee1bf5189e324089976026ed09b6be9e58Arnold Schwaighofer // ptr2_phi = phi [bb, ptr2], [loop, ptr2_plus_one] 10833d5f96ee1bf5189e324089976026ed09b6be9e58Arnold Schwaighofer // ... 10843d5f96ee1bf5189e324089976026ed09b6be9e58Arnold Schwaighofer // ptr_plus_one = gep ptr_phi, 1 10853d5f96ee1bf5189e324089976026ed09b6be9e58Arnold Schwaighofer // ptr2_plus_one = gep ptr2_phi, 1 10863d5f96ee1bf5189e324089976026ed09b6be9e58Arnold Schwaighofer // We assume for the recursion that the the phis (ptr_phi, ptr2_phi) do 10873d5f96ee1bf5189e324089976026ed09b6be9e58Arnold Schwaighofer // not alias each other. 10883d5f96ee1bf5189e324089976026ed09b6be9e58Arnold Schwaighofer bool ArePhisAssumedNoAlias = false; 10893d5f96ee1bf5189e324089976026ed09b6be9e58Arnold Schwaighofer AliasResult OrigAliasResult; 10903d5f96ee1bf5189e324089976026ed09b6be9e58Arnold Schwaighofer if (Alias == NoAlias) { 10913d5f96ee1bf5189e324089976026ed09b6be9e58Arnold Schwaighofer // Pretend the phis do not alias. 10923d5f96ee1bf5189e324089976026ed09b6be9e58Arnold Schwaighofer assert(AliasCache.count(Locs) && 10933d5f96ee1bf5189e324089976026ed09b6be9e58Arnold Schwaighofer "There must exist an entry for the phi node"); 10943d5f96ee1bf5189e324089976026ed09b6be9e58Arnold Schwaighofer OrigAliasResult = AliasCache[Locs]; 10953d5f96ee1bf5189e324089976026ed09b6be9e58Arnold Schwaighofer AliasCache[Locs] = NoAlias; 10963d5f96ee1bf5189e324089976026ed09b6be9e58Arnold Schwaighofer ArePhisAssumedNoAlias = true; 10973d5f96ee1bf5189e324089976026ed09b6be9e58Arnold Schwaighofer } 10983d5f96ee1bf5189e324089976026ed09b6be9e58Arnold Schwaighofer 10996665b0ea688941c1c044a5c034ee45d45862168fDan Gohman for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) { 11006665b0ea688941c1c044a5c034ee45d45862168fDan Gohman AliasResult ThisAlias = 11016cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman aliasCheck(PN->getIncomingValue(i), PNSize, PNTBAAInfo, 11026665b0ea688941c1c044a5c034ee45d45862168fDan Gohman PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)), 11036cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman V2Size, V2TBAAInfo); 1104965fefa1add8151619cc340c373a812c94342e58Dan Gohman Alias = MergeAliasResults(ThisAlias, Alias); 1105965fefa1add8151619cc340c373a812c94342e58Dan Gohman if (Alias == MayAlias) 1106965fefa1add8151619cc340c373a812c94342e58Dan Gohman break; 11076665b0ea688941c1c044a5c034ee45d45862168fDan Gohman } 11083d5f96ee1bf5189e324089976026ed09b6be9e58Arnold Schwaighofer 11093d5f96ee1bf5189e324089976026ed09b6be9e58Arnold Schwaighofer // Reset if speculation failed. 11103d5f96ee1bf5189e324089976026ed09b6be9e58Arnold Schwaighofer if (ArePhisAssumedNoAlias && Alias != NoAlias) 11113d5f96ee1bf5189e324089976026ed09b6be9e58Arnold Schwaighofer AliasCache[Locs] = OrigAliasResult; 11123d5f96ee1bf5189e324089976026ed09b6be9e58Arnold Schwaighofer 11136665b0ea688941c1c044a5c034ee45d45862168fDan Gohman return Alias; 11146665b0ea688941c1c044a5c034ee45d45862168fDan Gohman } 11156665b0ea688941c1c044a5c034ee45d45862168fDan Gohman 1116a846a8a1dcb8ab28e75e364c0cf0272634d023f2Evan Cheng SmallPtrSet<Value*, 4> UniqueSrc; 111750a5914e129c348e8878d4654b4306e0349281c2Evan Cheng SmallVector<Value*, 4> V1Srcs; 111850a5914e129c348e8878d4654b4306e0349281c2Evan Cheng for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 111950a5914e129c348e8878d4654b4306e0349281c2Evan Cheng Value *PV1 = PN->getIncomingValue(i); 112050a5914e129c348e8878d4654b4306e0349281c2Evan Cheng if (isa<PHINode>(PV1)) 112150a5914e129c348e8878d4654b4306e0349281c2Evan Cheng // If any of the source itself is a PHI, return MayAlias conservatively 1122681a33e26dd3222477f13520b94e7417bff59e32Evan Cheng // to avoid compile time explosion. The worst possible case is if both 1123681a33e26dd3222477f13520b94e7417bff59e32Evan Cheng // sides are PHI nodes. In which case, this is O(m x n) time where 'm' 1124681a33e26dd3222477f13520b94e7417bff59e32Evan Cheng // and 'n' are the number of PHI sources. 112550a5914e129c348e8878d4654b4306e0349281c2Evan Cheng return MayAlias; 112650a5914e129c348e8878d4654b4306e0349281c2Evan Cheng if (UniqueSrc.insert(PV1)) 112750a5914e129c348e8878d4654b4306e0349281c2Evan Cheng V1Srcs.push_back(PV1); 112850a5914e129c348e8878d4654b4306e0349281c2Evan Cheng } 112950a5914e129c348e8878d4654b4306e0349281c2Evan Cheng 11306cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman AliasResult Alias = aliasCheck(V2, V2Size, V2TBAAInfo, 11316cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman V1Srcs[0], PNSize, PNTBAAInfo); 1132d83c2ca3368f90d60234848e751842d29b248039Evan Cheng // Early exit if the check of the first PHI source against V2 is MayAlias. 1133d83c2ca3368f90d60234848e751842d29b248039Evan Cheng // Other results are not possible. 1134d83c2ca3368f90d60234848e751842d29b248039Evan Cheng if (Alias == MayAlias) 1135d83c2ca3368f90d60234848e751842d29b248039Evan Cheng return MayAlias; 1136d83c2ca3368f90d60234848e751842d29b248039Evan Cheng 113750a5914e129c348e8878d4654b4306e0349281c2Evan Cheng // If all sources of the PHI node NoAlias or MustAlias V2, then returns 113850a5914e129c348e8878d4654b4306e0349281c2Evan Cheng // NoAlias / MustAlias. Otherwise, returns MayAlias. 113950a5914e129c348e8878d4654b4306e0349281c2Evan Cheng for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) { 114050a5914e129c348e8878d4654b4306e0349281c2Evan Cheng Value *V = V1Srcs[i]; 11416665b0ea688941c1c044a5c034ee45d45862168fDan Gohman 11426cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman AliasResult ThisAlias = aliasCheck(V2, V2Size, V2TBAAInfo, 11436cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman V, PNSize, PNTBAAInfo); 1144965fefa1add8151619cc340c373a812c94342e58Dan Gohman Alias = MergeAliasResults(ThisAlias, Alias); 1145965fefa1add8151619cc340c373a812c94342e58Dan Gohman if (Alias == MayAlias) 1146965fefa1add8151619cc340c373a812c94342e58Dan Gohman break; 114750a5914e129c348e8878d4654b4306e0349281c2Evan Cheng } 114850a5914e129c348e8878d4654b4306e0349281c2Evan Cheng 114950a5914e129c348e8878d4654b4306e0349281c2Evan Cheng return Alias; 115050a5914e129c348e8878d4654b4306e0349281c2Evan Cheng} 115150a5914e129c348e8878d4654b4306e0349281c2Evan Cheng 115250a5914e129c348e8878d4654b4306e0349281c2Evan Cheng// aliasCheck - Provide a bunch of ad-hoc rules to disambiguate in common cases, 115350a5914e129c348e8878d4654b4306e0349281c2Evan Cheng// such as array references. 1154094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng// 1155094f04b429c11547ed98d7a53dd3399db51083bdEvan ChengAliasAnalysis::AliasResult 11563da848bbda62b25c12335998aaa44ab361f0bf15Dan GohmanBasicAliasAnalysis::aliasCheck(const Value *V1, uint64_t V1Size, 11576cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman const MDNode *V1TBAAInfo, 11583da848bbda62b25c12335998aaa44ab361f0bf15Dan Gohman const Value *V2, uint64_t V2Size, 11596cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman const MDNode *V2TBAAInfo) { 1160b57b6f1575ec87b22dc793fe03539cae9df0e586Dan Gohman // If either of the memory references is empty, it doesn't matter what the 1161b57b6f1575ec87b22dc793fe03539cae9df0e586Dan Gohman // pointer values are. 1162b57b6f1575ec87b22dc793fe03539cae9df0e586Dan Gohman if (V1Size == 0 || V2Size == 0) 1163b57b6f1575ec87b22dc793fe03539cae9df0e586Dan Gohman return NoAlias; 1164b57b6f1575ec87b22dc793fe03539cae9df0e586Dan Gohman 1165094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng // Strip off any casts if they exist. 1166094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng V1 = V1->stripPointerCasts(); 1167094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng V2 = V2->stripPointerCasts(); 1168094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng 1169094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng // Are we checking for alias of the same value? 1170094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng if (V1 == V2) return MustAlias; 1171094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng 11721df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands if (!V1->getType()->isPointerTy() || !V2->getType()->isPointerTy()) 1173094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng return NoAlias; // Scalars cannot alias each other 1174094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng 1175094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng // Figure out what objects these things are pointing to if we can. 1176bd1801b5553c8be3960255a92738464e0010b6f6Dan Gohman const Value *O1 = GetUnderlyingObject(V1, TD); 1177bd1801b5553c8be3960255a92738464e0010b6f6Dan Gohman const Value *O2 = GetUnderlyingObject(V2, TD); 1178094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng 1179f75ef668a7d35d361e797b7b160008b37d62f15cDan Gohman // Null values in the default address space don't point to any object, so they 1180f75ef668a7d35d361e797b7b160008b37d62f15cDan Gohman // don't alias any other pointer. 1181f75ef668a7d35d361e797b7b160008b37d62f15cDan Gohman if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O1)) 1182f75ef668a7d35d361e797b7b160008b37d62f15cDan Gohman if (CPN->getType()->getAddressSpace() == 0) 1183f75ef668a7d35d361e797b7b160008b37d62f15cDan Gohman return NoAlias; 1184f75ef668a7d35d361e797b7b160008b37d62f15cDan Gohman if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O2)) 1185f75ef668a7d35d361e797b7b160008b37d62f15cDan Gohman if (CPN->getType()->getAddressSpace() == 0) 1186f75ef668a7d35d361e797b7b160008b37d62f15cDan Gohman return NoAlias; 1187f75ef668a7d35d361e797b7b160008b37d62f15cDan Gohman 1188094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng if (O1 != O2) { 1189094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng // If V1/V2 point to two different objects we know that we have no alias. 11909e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman if (isIdentifiedObject(O1) && isIdentifiedObject(O2)) 1191094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng return NoAlias; 119220162ac5662a45388911ef1d35ba7559aae368f5Nick Lewycky 119320162ac5662a45388911ef1d35ba7559aae368f5Nick Lewycky // Constant pointers can't alias with non-const isIdentifiedObject objects. 11949e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman if ((isa<Constant>(O1) && isIdentifiedObject(O2) && !isa<Constant>(O2)) || 11959e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman (isa<Constant>(O2) && isIdentifiedObject(O1) && !isa<Constant>(O1))) 119620162ac5662a45388911ef1d35ba7559aae368f5Nick Lewycky return NoAlias; 119720162ac5662a45388911ef1d35ba7559aae368f5Nick Lewycky 119821de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman // Arguments can't alias with local allocations or noalias calls 119921de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman // in the same function. 12009e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman if (((isa<Argument>(O1) && (isa<AllocaInst>(O2) || isNoAliasCall(O2))) || 120121de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman (isa<Argument>(O2) && (isa<AllocaInst>(O1) || isNoAliasCall(O1))))) 120221de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman return NoAlias; 1203094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng 1204094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng // Most objects can't alias null. 12059e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman if ((isa<ConstantPointerNull>(O2) && isKnownNonNull(O1)) || 12069e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman (isa<ConstantPointerNull>(O1) && isKnownNonNull(O2))) 1207094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng return NoAlias; 1208094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng 1209b8c86a010c2d958d6f655b0f66101d8964d7a0fcDan Gohman // If one pointer is the result of a call/invoke or load and the other is a 1210b8c86a010c2d958d6f655b0f66101d8964d7a0fcDan Gohman // non-escaping local object within the same function, then we know the 1211b8c86a010c2d958d6f655b0f66101d8964d7a0fcDan Gohman // object couldn't escape to a point where the call could return it. 1212b8c86a010c2d958d6f655b0f66101d8964d7a0fcDan Gohman // 1213b8c86a010c2d958d6f655b0f66101d8964d7a0fcDan Gohman // Note that if the pointers are in different functions, there are a 1214b8c86a010c2d958d6f655b0f66101d8964d7a0fcDan Gohman // variety of complications. A call with a nocapture argument may still 1215b8c86a010c2d958d6f655b0f66101d8964d7a0fcDan Gohman // temporary store the nocapture argument's value in a temporary memory 1216b8c86a010c2d958d6f655b0f66101d8964d7a0fcDan Gohman // location if that memory location doesn't escape. Or it may pass a 1217b8c86a010c2d958d6f655b0f66101d8964d7a0fcDan Gohman // nocapture value to other functions as long as they don't capture it. 1218b8c86a010c2d958d6f655b0f66101d8964d7a0fcDan Gohman if (isEscapeSource(O1) && isNonEscapingLocalObject(O2)) 1219b8c86a010c2d958d6f655b0f66101d8964d7a0fcDan Gohman return NoAlias; 1220b8c86a010c2d958d6f655b0f66101d8964d7a0fcDan Gohman if (isEscapeSource(O2) && isNonEscapingLocalObject(O1)) 1221b8c86a010c2d958d6f655b0f66101d8964d7a0fcDan Gohman return NoAlias; 1222b8c86a010c2d958d6f655b0f66101d8964d7a0fcDan Gohman } 1223b8c86a010c2d958d6f655b0f66101d8964d7a0fcDan Gohman 1224094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng // If the size of one access is larger than the entire object on the other 1225094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng // side, then we know such behavior is undefined and can assume no alias. 1226094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng if (TD) 12278e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer if ((V1Size != UnknownSize && isObjectSmallerThan(O2, V1Size, *TD, *TLI)) || 12288e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer (V2Size != UnknownSize && isObjectSmallerThan(O1, V2Size, *TD, *TLI))) 1229094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng return NoAlias; 1230094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng 12311fc18d71deb0e23a9101c87bb7b1455098ce1c09Dan Gohman // Check the cache before climbing up use-def chains. This also terminates 12321fc18d71deb0e23a9101c87bb7b1455098ce1c09Dan Gohman // otherwise infinitely recursive queries. 12331fc18d71deb0e23a9101c87bb7b1455098ce1c09Dan Gohman LocPair Locs(Location(V1, V1Size, V1TBAAInfo), 12341fc18d71deb0e23a9101c87bb7b1455098ce1c09Dan Gohman Location(V2, V2Size, V2TBAAInfo)); 12351fc18d71deb0e23a9101c87bb7b1455098ce1c09Dan Gohman if (V1 > V2) 12361fc18d71deb0e23a9101c87bb7b1455098ce1c09Dan Gohman std::swap(Locs.first, Locs.second); 12371fc18d71deb0e23a9101c87bb7b1455098ce1c09Dan Gohman std::pair<AliasCacheTy::iterator, bool> Pair = 12381fc18d71deb0e23a9101c87bb7b1455098ce1c09Dan Gohman AliasCache.insert(std::make_pair(Locs, MayAlias)); 12391fc18d71deb0e23a9101c87bb7b1455098ce1c09Dan Gohman if (!Pair.second) 12401fc18d71deb0e23a9101c87bb7b1455098ce1c09Dan Gohman return Pair.first->second; 12411fc18d71deb0e23a9101c87bb7b1455098ce1c09Dan Gohman 12424e91ee7a2a80142c3774a9984f92a3fae1c126e7Chris Lattner // FIXME: This isn't aggressively handling alias(GEP, PHI) for example: if the 12434e91ee7a2a80142c3774a9984f92a3fae1c126e7Chris Lattner // GEP can't simplify, we don't even look at the PHI cases. 1244391d23b6c29e17b5c969e732169a789ac9d0d422Chris Lattner if (!isa<GEPOperator>(V1) && isa<GEPOperator>(V2)) { 1245094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng std::swap(V1, V2); 1246094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng std::swap(V1Size, V2Size); 124723e2a5b2fff8b5b483a464ce1bea9a686e6731deChris Lattner std::swap(O1, O2); 1248094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng } 1249c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman if (const GEPOperator *GV1 = dyn_cast<GEPOperator>(V1)) { 1250029032693fdb065b6edfff6d68df188f98bee8acArnold Schwaighofer AliasResult Result = aliasGEP(GV1, V1Size, V1TBAAInfo, V2, V2Size, V2TBAAInfo, O1, O2); 12511fc18d71deb0e23a9101c87bb7b1455098ce1c09Dan Gohman if (Result != MayAlias) return AliasCache[Locs] = Result; 1252c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman } 125350a5914e129c348e8878d4654b4306e0349281c2Evan Cheng 125450a5914e129c348e8878d4654b4306e0349281c2Evan Cheng if (isa<PHINode>(V2) && !isa<PHINode>(V1)) { 125550a5914e129c348e8878d4654b4306e0349281c2Evan Cheng std::swap(V1, V2); 125650a5914e129c348e8878d4654b4306e0349281c2Evan Cheng std::swap(V1Size, V2Size); 125750a5914e129c348e8878d4654b4306e0349281c2Evan Cheng } 1258c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman if (const PHINode *PN = dyn_cast<PHINode>(V1)) { 12596cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman AliasResult Result = aliasPHI(PN, V1Size, V1TBAAInfo, 12606cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman V2, V2Size, V2TBAAInfo); 12611fc18d71deb0e23a9101c87bb7b1455098ce1c09Dan Gohman if (Result != MayAlias) return AliasCache[Locs] = Result; 1262c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman } 12632b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 12646665b0ea688941c1c044a5c034ee45d45862168fDan Gohman if (isa<SelectInst>(V2) && !isa<SelectInst>(V1)) { 12656665b0ea688941c1c044a5c034ee45d45862168fDan Gohman std::swap(V1, V2); 12666665b0ea688941c1c044a5c034ee45d45862168fDan Gohman std::swap(V1Size, V2Size); 12676665b0ea688941c1c044a5c034ee45d45862168fDan Gohman } 1268c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman if (const SelectInst *S1 = dyn_cast<SelectInst>(V1)) { 12696cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman AliasResult Result = aliasSelect(S1, V1Size, V1TBAAInfo, 12706cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman V2, V2Size, V2TBAAInfo); 12711fc18d71deb0e23a9101c87bb7b1455098ce1c09Dan Gohman if (Result != MayAlias) return AliasCache[Locs] = Result; 1272c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman } 12736665b0ea688941c1c044a5c034ee45d45862168fDan Gohman 1274615da1a9bcca05de06fab5f48ee9110267312974Dan Gohman // If both pointers are pointing into the same object and one of them 1275615da1a9bcca05de06fab5f48ee9110267312974Dan Gohman // accesses is accessing the entire object, then the accesses must 1276615da1a9bcca05de06fab5f48ee9110267312974Dan Gohman // overlap in some way. 1277615da1a9bcca05de06fab5f48ee9110267312974Dan Gohman if (TD && O1 == O2) 12788e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer if ((V1Size != UnknownSize && isObjectSize(O1, V1Size, *TD, *TLI)) || 12798e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer (V2Size != UnknownSize && isObjectSize(O2, V2Size, *TD, *TLI))) 12801fc18d71deb0e23a9101c87bb7b1455098ce1c09Dan Gohman return AliasCache[Locs] = PartialAlias; 1281615da1a9bcca05de06fab5f48ee9110267312974Dan Gohman 12821fc18d71deb0e23a9101c87bb7b1455098ce1c09Dan Gohman AliasResult Result = 12831fc18d71deb0e23a9101c87bb7b1455098ce1c09Dan Gohman AliasAnalysis::alias(Location(V1, V1Size, V1TBAAInfo), 12841fc18d71deb0e23a9101c87bb7b1455098ce1c09Dan Gohman Location(V2, V2Size, V2TBAAInfo)); 12851fc18d71deb0e23a9101c87bb7b1455098ce1c09Dan Gohman return AliasCache[Locs] = Result; 1286d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner} 1287