Index: lib/Analysis/AliasAnalysisSummary.h =================================================================== --- lib/Analysis/AliasAnalysisSummary.h +++ lib/Analysis/AliasAnalysisSummary.h @@ -134,20 +134,42 @@ return !(LHS < RHS); } +// We use UnknownOffset to represent pointer offsets that cannot be determined +// at compile time. Note that MemoryLocation::UnknownSize cannot be used here +// because we require a signed value. +static LLVM_CONSTEXPR int64_t UnknownOffset = + std::numeric_limits::max(); + +inline int64_t addOffset(int64_t LHS, int64_t RHS) { + if (LHS == UnknownOffset || RHS == UnknownOffset) + return UnknownOffset; + // FIXME: Do we need to guard against integer overflow here? + return LHS + RHS; +} + /// We use ExternalRelation to describe an externally visible aliasing relations /// between parameters/return value of a function. struct ExternalRelation { InterfaceValue From, To; + int64_t Offset; }; inline bool operator==(ExternalRelation LHS, ExternalRelation RHS) { - return LHS.From == RHS.From && LHS.To == RHS.To; + return LHS.From == RHS.From && LHS.To == RHS.To && LHS.Offset == RHS.Offset; } inline bool operator!=(ExternalRelation LHS, ExternalRelation RHS) { return !(LHS == RHS); } inline bool operator<(ExternalRelation LHS, ExternalRelation RHS) { - return LHS.From < RHS.From || (LHS.From == RHS.From && LHS.To < RHS.To); + if (LHS.From < RHS.From) + return true; + if (LHS.From > RHS.From) + return false; + if (LHS.To < RHS.To) + return true; + if (LHS.To > RHS.To) + return false; + return LHS.Offset < RHS.Offset; } inline bool operator>(ExternalRelation LHS, ExternalRelation RHS) { return RHS < LHS; @@ -206,6 +228,7 @@ /// callsite struct InstantiatedRelation { InstantiatedValue From, To; + int64_t Offset; }; Optional instantiateExternalRelation(ExternalRelation, CallSite); Index: lib/Analysis/AliasAnalysisSummary.cpp =================================================================== --- lib/Analysis/AliasAnalysisSummary.cpp +++ lib/Analysis/AliasAnalysisSummary.cpp @@ -91,7 +91,7 @@ auto To = instantiateInterfaceValue(ERelation.To, CS); if (!To) return None; - return InstantiatedRelation{*From, *To}; + return InstantiatedRelation{*From, *To, ERelation.Offset}; } Optional instantiateExternalAttribute(ExternalAttribute EAttr, Index: lib/Analysis/CFLAndersAliasAnalysis.cpp =================================================================== --- lib/Analysis/CFLAndersAliasAnalysis.cpp +++ lib/Analysis/CFLAndersAliasAnalysis.cpp @@ -116,6 +116,30 @@ (1U << static_cast(MatchState::FlowToWriteOnly)) | (1U << static_cast(MatchState::FlowToMemAliasWriteOnly)); +// A pair that consists of a value and an offset +struct OffsetValue { + const Value *Val; + int64_t Offset; +}; + +bool operator==(OffsetValue LHS, OffsetValue RHS) { + return LHS.Val == RHS.Val && LHS.Offset == RHS.Offset; +} +bool operator<(OffsetValue LHS, OffsetValue RHS) { + return std::less()(LHS.Val, RHS.Val) || + (LHS.Val == RHS.Val && LHS.Offset < RHS.Offset); +} + +// A pair that consists of an InstantiatedValue and an offset +struct OffsetInstantiatedValue { + InstantiatedValue IVal; + int64_t Offset; +}; + +bool operator==(OffsetInstantiatedValue LHS, OffsetInstantiatedValue RHS) { + return LHS.IVal == RHS.IVal && LHS.Offset == RHS.Offset; +} + // We use ReachabilitySet to keep track of value aliases (The nonterminal "V" in // the paper) during the analysis. class ReachabilitySet { @@ -227,12 +251,53 @@ }; } +// Specialize DenseMapInfo for OffsetValue. +template <> struct DenseMapInfo { + static OffsetValue getEmptyKey() { + return OffsetValue{DenseMapInfo::getEmptyKey(), + DenseMapInfo::getEmptyKey()}; + } + static OffsetValue getTombstoneKey() { + return OffsetValue{DenseMapInfo::getTombstoneKey(), + DenseMapInfo::getEmptyKey()}; + } + static unsigned getHashValue(const OffsetValue &OVal) { + return DenseMapInfo>::getHashValue( + std::make_pair(OVal.Val, OVal.Offset)); + } + static bool isEqual(const OffsetValue &LHS, const OffsetValue &RHS) { + return LHS == RHS; + } +}; + +// Specialize DenseMapInfo for OffsetInstantiatedValue. +template <> struct DenseMapInfo { + static OffsetInstantiatedValue getEmptyKey() { + return OffsetInstantiatedValue{ + DenseMapInfo::getEmptyKey(), + DenseMapInfo::getEmptyKey()}; + } + static OffsetInstantiatedValue getTombstoneKey() { + return OffsetInstantiatedValue{ + DenseMapInfo::getTombstoneKey(), + DenseMapInfo::getEmptyKey()}; + } + static unsigned getHashValue(const OffsetInstantiatedValue &OVal) { + return DenseMapInfo>::getHashValue( + std::make_pair(OVal.IVal, OVal.Offset)); + } + static bool isEqual(const OffsetInstantiatedValue &LHS, + const OffsetInstantiatedValue &RHS) { + return LHS == RHS; + } +}; + class CFLAndersAAResult::FunctionInfo { /// Map a value to other values that may alias it /// Since the alias relation is symmetric, to save some space we assume values /// are properly ordered: if a and b alias each other, and a < b, then b is in /// AliasMap[a] but not vice versa. - DenseMap> AliasMap; + DenseMap> AliasMap; /// Map a value to its corresponding AliasAttrs DenseMap AttrMap; @@ -246,7 +311,7 @@ FunctionInfo(const Function &, const SmallVectorImpl &, const ReachabilitySet &, AliasAttrMap); - bool mayAlias(const Value *LHS, const Value *RHS) const; + AliasResult alias(const Value *, uint64_t, const Value *, uint64_t) const; const AliasSummary &getAliasSummary() const { return Summary; } }; @@ -281,12 +346,12 @@ // AttrMap only cares about top-level values if (IVal.DerefLevel == 0) - AttrMap[IVal.Val] = Mapping.second; + AttrMap[IVal.Val] |= Mapping.second; } } static void -populateAliasMap(DenseMap> &AliasMap, +populateAliasMap(DenseMap> &AliasMap, const ReachabilitySet &ReachSet) { for (const auto &OuterMapping : ReachSet.value_mappings()) { // AliasMap only cares about top-level values @@ -298,11 +363,11 @@ for (const auto &InnerMapping : OuterMapping.second) { // Again, AliasMap only cares about top-level values if (InnerMapping.first.DerefLevel == 0) - AliasList.push_back(InnerMapping.first.Val); + AliasList.push_back(OffsetValue{InnerMapping.first.Val, UnknownOffset}); } // Sort AliasList for faster lookup - std::sort(AliasList.begin(), AliasList.end(), std::less()); + std::sort(AliasList.begin(), AliasList.end()); } } @@ -316,7 +381,7 @@ if (is_contained(RetVals, &Arg)) { auto ArgVal = InterfaceValue{Arg.getArgNo() + 1, 0}; auto RetVal = InterfaceValue{0, 0}; - ExtRelations.push_back(ExternalRelation{ArgVal, RetVal}); + ExtRelations.push_back(ExternalRelation{ArgVal, RetVal, UnknownOffset}); } } @@ -344,7 +409,7 @@ continue; if (hasReadOnlyState(InnerMapping.second)) - ExtRelations.push_back(ExternalRelation{*Dst, *Src}); + ExtRelations.push_back(ExternalRelation{*Dst, *Src, UnknownOffset}); // No need to check for WriteOnly state, since ReachSet is symmetric } else { // If Src is not a param/return, add it to ValueMap @@ -378,9 +443,9 @@ else DstLevel += FromLevel - ToLevel; - ExtRelations.push_back( - ExternalRelation{InterfaceValue{SrcIndex, SrcLevel}, - InterfaceValue{DstIndex, DstLevel}}); + ExtRelations.push_back(ExternalRelation{ + InterfaceValue{SrcIndex, SrcLevel}, + InterfaceValue{DstIndex, DstLevel}, UnknownOffset}); } } } @@ -422,29 +487,60 @@ return Attr; } -bool CFLAndersAAResult::FunctionInfo::mayAlias(const Value *LHS, - const Value *RHS) const { +AliasResult CFLAndersAAResult::FunctionInfo::alias(const Value *LHS, + uint64_t LHSSize, + const Value *RHS, + uint64_t RHSSize) const { assert(LHS && RHS); auto Itr = AliasMap.find(LHS); if (Itr != AliasMap.end()) { - if (std::binary_search(Itr->second.begin(), Itr->second.end(), RHS, - std::less())) - return true; + // Find out all (X, Offset) where X == RHS + auto RangePair = std::equal_range( + Itr->second.begin(), Itr->second.end(), OffsetValue{RHS, 0}, + [](OffsetValue LHS, OffsetValue RHS) { + return std::less()(LHS.Val, RHS.Val); + }); + + if (RangePair.first != RangePair.second) { + // Be conservative about UnknownSize + if (LHSSize == MemoryLocation::UnknownSize || + RHSSize == MemoryLocation::UnknownSize) + return MayAlias; + + for (const auto &OVal : make_range(RangePair)) { + // Be conservative about UnknownOffset + if (OVal.Offset == UnknownOffset) + return MayAlias; + + // We know that LHS aliases (RHS + OVal.Offset) if the control flow + // reaches here. The may-alias query essentially becomes integer + // range-overlap queries over two ranges [OVal.Offset, OVal.Offset + + // LHSSize) and [0, RHSSize). + + // FIXME: What happens when LHSSize or RHSSize is larger than INT64_MAX? + auto LHSStart = OVal.Offset; + auto LHSEnd = OVal.Offset + static_cast(LHSSize); + auto RHSStart = 0; + auto RHSEnd = static_cast(RHSSize); + if (LHSEnd > RHSStart && LHSStart < RHSEnd) + return (LHSStart == 0) ? MayAlias : PartialAlias; + } + } } - // Even if LHS and RHS are not reachable, they may still alias due to their + // Even if LHS and RHS are not related, they may still alias due to their // AliasAttrs auto AttrsA = getAttrs(LHS); auto AttrsB = getAttrs(RHS); if (AttrsA.none() || AttrsB.none()) - return false; + return NoAlias; if (hasUnknownOrCallerAttr(AttrsA) || hasUnknownOrCallerAttr(AttrsB)) - return true; + return MayAlias; if (isGlobalOrArgAttr(AttrsA) && isGlobalOrArgAttr(AttrsB)) - return true; - return false; + return MayAlias; + return NoAlias; } static void propagate(InstantiatedValue From, InstantiatedValue To, @@ -725,9 +821,7 @@ auto &FunInfo = ensureCached(*Fn); // AliasMap lookup - if (FunInfo->mayAlias(ValA, ValB)) - return MayAlias; - return NoAlias; + return FunInfo->alias(ValA, LocA.Size, ValB, LocB.Size); } AliasResult CFLAndersAAResult::alias(const MemoryLocation &LocA, Index: lib/Analysis/CFLGraph.h =================================================================== --- lib/Analysis/CFLGraph.h +++ lib/Analysis/CFLGraph.h @@ -24,19 +24,6 @@ namespace llvm { namespace cflaa { -// We use UnknownOffset to represent pointer offsets that cannot be determined -// at compile time. Note that MemoryLocation::UnknownSize cannot be used here -// because we require a signed value. -static LLVM_CONSTEXPR int64_t UnknownOffset = - std::numeric_limits::max(); - -inline int64_t addOffset(int64_t LHS, int64_t RHS) { - if (LHS == UnknownOffset || RHS == UnknownOffset) - return UnknownOffset; - // FIXME: Do we need to guard against integer overflow here? - return LHS + RHS; -} - /// \brief The Program Expression Graph (PEG) of CFL analysis /// CFLGraph is auxiliary data structure used by CFL-based alias analysis to /// describe flow-insensitive pointer-related behaviors. Given an LLVM function, Index: lib/Analysis/CFLSteensAliasAnalysis.cpp =================================================================== --- lib/Analysis/CFLSteensAliasAnalysis.cpp +++ lib/Analysis/CFLSteensAliasAnalysis.cpp @@ -153,7 +153,7 @@ if (Itr != InterfaceMap.end()) { if (CurrValue != Itr->second) Summary.RetParamRelations.push_back( - ExternalRelation{CurrValue, Itr->second}); + ExternalRelation{CurrValue, Itr->second, UnknownOffset}); break; }