[CFLAA] Add support for field offset in CFLAnders::FunctionInfo

[grievejia]

Summary

CFLAnders::FunctionInfo used to record, for each value X, what other values Y may-alias it. Such an approach is inadequate if we were to move to a field-sensitive analysis. This patch changes the map type from Value->[Value] to Value->[(Value, Offset)]. In other words, instead of keeping track of "X alias Y", FunctionInfo now understands a more general alias pattern "X alias (Y + FieldOffset)". The strategy of alias query handling gets adjusted accordingly to cope with this change: now CFLAnders can potentially answer "PartialAlias" for certain queries.

Note that only the interfaces of FunctionInfo gets changed in this patch. The analysis body is still oblivious about field offset, therefore no functional change was introduced.

More patches on field-sensitivity will come in the near future.

[grievejia]

Slight precision improvement.

[george.burgess.iv]

Thanks for the patch!

lib/Analysis/AliasAnalysisSummary.h

140

Please rebase; it looks like my intuition on your prior patch was only half-correct. ;)

We apparently have a bot that uses clang on Windows, with earlier versions of MS's stdlib. So, LLVM_CONSTEXPR becomes constexpr, and max() still isn't constexpr on that particular bot. My bad.

lib/Analysis/CFLAndersAliasAnalysis.cpp

512

Given that we're using a different comparator than the one we sorted with here, can we add the following above this line, please?

#ifdef EXPENSIVE_CHECKS
assert(std::is_sorted(Itr->second.begin(), Itr->second.end(), /* your comparator here */));
#endif

534

Pick your favorite:

assert(LHSSize <= INT64_MAX)

or

if (LLVM_UNLIKELY(LHSSize > INT64_MAX || RHSSize > INT64_MAX)) return MayAlias;

:)

536

If we care about potential overflow, this may be a good place to put a FIXME, as well.

540

PartialAlias doesn't seem quite right here. PartialAlias is essentially MustAlias (at some offset, as you've noted), and, unless I'm missing something obvious, I think we'd need to do many more checks to prove MustAlias.

(If I *am* wrong, s/MayAlias/MustAlias/, please)

553–554

Given that these checks are relatively cheap, can we put them before our AliasMap checks (which seem potentially more expensive)?

[grievejia]

Rebase and style improvement

lib/Analysis/CFLAndersAliasAnalysis.cpp

540

My original thought was that PartialAlias = MayAlias at nonzero offset.

If PartialAlias = MustAlias at nonzero offset, then we probably don't have anything smarter than MayAlias, since the analysis only handles may info.

[george.burgess.iv]

LGTM -- thanks for the patch!

lib/Analysis/CFLAndersAliasAnalysis.cpp

540

If PartialAlias = MustAlias at nonzero offset, then we probably don't have anything smarter than MayAlias, since the analysis only handles may info

Agreed :)

lib/Analysis/AliasAnalysisSummary.h

 }
 inline bool operator<=(InterfaceValue LHS, InterfaceValue RHS) {
   return !(RHS < LHS);
 }
 inline bool operator>=(InterfaceValue LHS, InterfaceValue RHS) {
   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 = INT64_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;
 }
 inline bool operator<=(ExternalRelation LHS, ExternalRelation RHS) {
   return !(RHS < LHS);
 }
 inline bool operator>=(ExternalRelation LHS, ExternalRelation RHS) {

 inline bool operator>=(InstantiatedValue LHS, InstantiatedValue RHS) {
   return !(LHS < RHS);
 }
 
 /// This is the result of instantiating ExternalRelation at a particular
 /// callsite
 struct InstantiatedRelation {
   InstantiatedValue From, To;
+  int64_t Offset;
 };
 Optional<InstantiatedRelation> instantiateExternalRelation(ExternalRelation,
                                                            CallSite);
 
 /// This is the result of instantiating ExternalAttribute at a particular
 /// callsite
 struct InstantiatedAttr {
   InstantiatedValue IValue;

lib/Analysis/AliasAnalysisSummary.cpp

 Optional<InstantiatedRelation>
 instantiateExternalRelation(ExternalRelation ERelation, CallSite CS) {
   auto From = instantiateInterfaceValue(ERelation.From, CS);
   if (!From)
     return None;
   auto To = instantiateInterfaceValue(ERelation.To, CS);
   if (!To)
     return None;
-  return InstantiatedRelation{*From, *To};
+  return InstantiatedRelation{*From, *To, ERelation.Offset};
 }
 
 Optional<InstantiatedAttr> instantiateExternalAttribute(ExternalAttribute EAttr,
                                                         CallSite CS) {
   auto Value = instantiateInterfaceValue(EAttr.IValue, CS);
   if (!Value)
     return None;
   return InstantiatedAttr{*Value, EAttr.Attr};
 }
 }
 }

lib/Analysis/CFLAndersAliasAnalysis.cpp

 // apparently lack constexpr bitset ctors.
 LLVM_CONSTEXPR unsigned ReadOnlyStateMask =
     (1U << static_cast<uint8_t>(MatchState::FlowFromReadOnly)) |
     (1U << static_cast<uint8_t>(MatchState::FlowFromMemAliasReadOnly));
 LLVM_CONSTEXPR unsigned WriteOnlyStateMask =
     (1U << static_cast<uint8_t>(MatchState::FlowToWriteOnly)) |
     (1U << static_cast<uint8_t>(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<const Value *>()(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 {
   typedef DenseMap<InstantiatedValue, StateSet> ValueStateMap;
   typedef DenseMap<InstantiatedValue, ValueStateMap> ValueReachMap;
   ValueReachMap ReachMap;
 
 public:
struct ValueSummary {
   struct Record {
     InterfaceValue IValue;
     unsigned DerefLevel;
   };
   SmallVector<Record, 4> FromRecords, ToRecords;
 };
 }
 
+// Specialize DenseMapInfo for OffsetValue.
+template <> struct DenseMapInfo<OffsetValue> {
+  static OffsetValue getEmptyKey() {
+    return OffsetValue{DenseMapInfo<const Value *>::getEmptyKey(),
+                       DenseMapInfo<int64_t>::getEmptyKey()};
+  }
+  static OffsetValue getTombstoneKey() {
+    return OffsetValue{DenseMapInfo<const Value *>::getTombstoneKey(),
+                       DenseMapInfo<int64_t>::getEmptyKey()};
+  }
+  static unsigned getHashValue(const OffsetValue &OVal) {
+    return DenseMapInfo<std::pair<const Value *, int64_t>>::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<OffsetInstantiatedValue> {
+  static OffsetInstantiatedValue getEmptyKey() {
+    return OffsetInstantiatedValue{
+        DenseMapInfo<InstantiatedValue>::getEmptyKey(),
+        DenseMapInfo<int64_t>::getEmptyKey()};
+  }
+  static OffsetInstantiatedValue getTombstoneKey() {
+    return OffsetInstantiatedValue{
+        DenseMapInfo<InstantiatedValue>::getTombstoneKey(),
+        DenseMapInfo<int64_t>::getEmptyKey()};
+  }
+  static unsigned getHashValue(const OffsetInstantiatedValue &OVal) {
+    return DenseMapInfo<std::pair<InstantiatedValue, int64_t>>::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<const Value *, std::vector<const Value *>> AliasMap;
+  DenseMap<const Value *, std::vector<OffsetValue>> AliasMap;
 
   /// Map a value to its corresponding AliasAttrs
   DenseMap<const Value *, AliasAttrs> AttrMap;
 
   /// Summary of externally visible effects.
   AliasSummary Summary;
 
   AliasAttrs getAttrs(const Value *) const;
 
 public:
   FunctionInfo(const Function &, const SmallVectorImpl<Value *> &,
                const ReachabilitySet &, AliasAttrMap);
 
-  bool mayAlias(const Value *LHS, const Value *RHS) const;
+  bool mayAlias(const Value *, uint64_t, const Value *, uint64_t) const;
   const AliasSummary &getAliasSummary() const { return Summary; }
 };
 
 static bool hasReadOnlyState(StateSet Set) {
   return (Set & StateSet(ReadOnlyStateMask)).any();
 }
 
 static bool hasWriteOnlyState(StateSet Set) {

 
 static void populateAttrMap(DenseMap<const Value *, AliasAttrs> &AttrMap,
                             const AliasAttrMap &AMap) {
   for (const auto &Mapping : AMap.mappings()) {
     auto IVal = Mapping.first;
 
     // 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<const Value *, std::vector<const Value *>> &AliasMap,
+populateAliasMap(DenseMap<const Value *, std::vector<OffsetValue>> &AliasMap,
                  const ReachabilitySet &ReachSet) {
   for (const auto &OuterMapping : ReachSet.value_mappings()) {
     // AliasMap only cares about top-level values
     if (OuterMapping.first.DerefLevel > 0)
       continue;
 
     auto Val = OuterMapping.first.Val;
     auto &AliasList = AliasMap[Val];
     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<const Value *>());
+    std::sort(AliasList.begin(), AliasList.end());
   }
 }
 
 static void populateExternalRelations(
     SmallVectorImpl<ExternalRelation> &ExtRelations, const Function &Fn,
     const SmallVectorImpl<Value *> &RetVals, const ReachabilitySet &ReachSet) {
   // If a function only returns one of its argument X, then X will be both an
   // argument and a return value at the same time. This is an edge case that
   // needs special handling here.
   for (const auto &Arg : Fn.args()) {
     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, 0});
     }
   }
 
   // Below is the core summary construction logic.
   // A naive solution of adding only the value aliases that are parameters or
   // return values in ReachSet to the summary won't work: It is possible that a
   // parameter P is written into an intermediate value I, and the function
   // subsequently returns *I. In that case, *I is does not value alias anything
if (auto Dst = getInterfaceValue(OuterMapping.first, RetVals)) {
       for (const auto &InnerMapping : OuterMapping.second) {
         // If Src is a param/return value, we get a same-level assignment.
         if (auto Src = getInterfaceValue(InnerMapping.first, RetVals)) {
           // This may happen if both Dst and Src are return values
           if (*Dst == *Src)
             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
           auto SrcIVal = InnerMapping.first;
           if (hasReadOnlyState(InnerMapping.second))
             ValueMap[SrcIVal.Val].FromRecords.push_back(
                 ValueSummary::Record{*Dst, SrcIVal.DerefLevel});
           if (hasWriteOnlyState(InnerMapping.second))
for (const auto &FromRecord : Mapping.second.FromRecords) {
         auto SrcLevel = FromRecord.IValue.DerefLevel;
         auto DstIndex = ToRecord.IValue.Index;
         auto DstLevel = ToRecord.IValue.DerefLevel;
         if (ToLevel > FromLevel)
           SrcLevel += ToLevel - FromLevel;
         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});
       }
     }
   }
 
   // Remove duplicates in ExtRelations
   std::sort(ExtRelations.begin(), ExtRelations.end());
   ExtRelations.erase(std::unique(ExtRelations.begin(), ExtRelations.end()),
                      ExtRelations.end());
AliasAttrs CFLAndersAAResult::FunctionInfo::getAttrs(const Value *V) const {
   AliasAttrs Attr;
   auto Itr = AttrMap.find(V);
   if (Itr != AttrMap.end())
     Attr = Itr->second;
   return Attr;
 }
 
 bool CFLAndersAAResult::FunctionInfo::mayAlias(const Value *LHS,
-                                               const Value *RHS) const {
+                                               uint64_t LHSSize,
+                                               const Value *RHS,
+                                               uint64_t RHSSize) const {
   assert(LHS && RHS);
 
+  // Check AliasAttrs first since it's cheaper
+  auto AttrsA = getAttrs(LHS);
+  auto AttrsB = getAttrs(RHS);
+  if (hasUnknownOrCallerAttr(AttrsA))
+    return AttrsB.any();
+  if (hasUnknownOrCallerAttr(AttrsB))
+    return AttrsA.any();
+  if (isGlobalOrArgAttr(AttrsA))
+    return isGlobalOrArgAttr(AttrsB);
+  if (isGlobalOrArgAttr(AttrsB))
+    return isGlobalOrArgAttr(AttrsA);
+
+  // At this point both LHS and RHS should point to locally allocated objects
+
   auto Itr = AliasMap.find(LHS);
   if (Itr != AliasMap.end()) {
-    if (std::binary_search(Itr->second.begin(), Itr->second.end(), RHS,
-                           std::less<const Value *>()))
+
+    // Find out all (X, Offset) where X == RHS
+    auto Comparator = [](OffsetValue LHS, OffsetValue RHS) {
+      return std::less<const Value *>()(LHS.Val, RHS.Val);
+    };
+#ifdef EXPENSIVE_CHECKS
+    assert(std::is_sorted(Itr->second.begin(), Itr->second.end(), Comparator));
+#endif
+    auto RangePair = std::equal_range(Itr->second.begin(), Itr->second.end(),
+                                      OffsetValue{RHS, 0}, Comparator);
+
+    if (RangePair.first != RangePair.second) {
+      // Be conservative about UnknownSize
+      if (LHSSize == MemoryLocation::UnknownSize ||
+          RHSSize == MemoryLocation::UnknownSize)
         return true;
-  }
 
-  // Even if LHS and RHS are not reachable, they may still alias due to their
-  // AliasAttrs
-  auto AttrsA = getAttrs(LHS);
-  auto AttrsB = getAttrs(RHS);
+      for (const auto &OVal : make_range(RangePair)) {
+        // Be conservative about UnknownOffset
+        if (OVal.Offset == UnknownOffset)
+          return true;
 
-  if (AttrsA.none() || AttrsB.none())
-    return false;
-  if (hasUnknownOrCallerAttr(AttrsA) || hasUnknownOrCallerAttr(AttrsB))
+        // 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).
+
+        // Try to be conservative on super large offsets
+        if (LLVM_UNLIKELY(LHSSize > INT64_MAX || RHSSize > INT64_MAX))
           return true;
-  if (isGlobalOrArgAttr(AttrsA) && isGlobalOrArgAttr(AttrsB))
+
+        auto LHSStart = OVal.Offset;
+        // FIXME: Do we need to guard against integer overflow?
+        auto LHSEnd = OVal.Offset + static_cast<int64_t>(LHSSize);
+        auto RHSStart = 0;
+        auto RHSEnd = static_cast<int64_t>(RHSSize);
+        if (LHSEnd > RHSStart && LHSStart < RHSEnd)
           return true;
+      }
+    }
+  }
+
   return false;
 }
 
 static void propagate(InstantiatedValue From, InstantiatedValue To,
                       MatchState State, ReachabilitySet &ReachSet,
                       std::vector<WorkListItem> &WorkList) {
   if (From == To)
     return;
   if (ReachSet.insert(From, To, State))
AliasResult CFLAndersAAResult::query(const MemoryLocation &LocA,
   } else {
     assert(!parentFunctionOfValue(ValB) || parentFunctionOfValue(ValB) == Fn);
   }
 
   assert(Fn != nullptr);
   auto &FunInfo = ensureCached(*Fn);
 
   // AliasMap lookup
-  if (FunInfo->mayAlias(ValA, ValB))
+  if (FunInfo->mayAlias(ValA, LocA.Size, ValB, LocB.Size))
     return MayAlias;
   return NoAlias;
 }
 
 AliasResult CFLAndersAAResult::alias(const MemoryLocation &LocA,
                                      const MemoryLocation &LocB) {
   if (LocA.Ptr == LocB.Ptr)
     return LocA.Size == LocB.Size ? MustAlias : PartialAlias;

lib/Analysis/CFLGraph.h

 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/IR/InstVisitor.h"
 #include "llvm/IR/Instructions.h"
 
 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.
-enum : int64_t { UnknownOffset = INT64_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,
 /// the main purpose of this graph is to abstract away unrelated facts and
 /// translate the rest into a form that can be easily digested by CFL analyses.
 /// Each Node in the graph is an InstantiatedValue, and each edge represent a
 /// pointer assignment between InstantiatedValue. Pointer
 /// references/dereferences are not explicitly stored in the graph: we

lib/Analysis/CFLSteensAliasAnalysis.cpp

auto AddToRetParamRelations = [&](unsigned InterfaceIndex,
     unsigned Level = 0;
     while (true) {
       InterfaceValue CurrValue{InterfaceIndex, Level};
 
       auto Itr = InterfaceMap.find(SetIndex);
       if (Itr != InterfaceMap.end()) {
         if (CurrValue != Itr->second)
           Summary.RetParamRelations.push_back(
-              ExternalRelation{CurrValue, Itr->second});
+              ExternalRelation{CurrValue, Itr->second, UnknownOffset});
         break;
       }
 
       auto &Link = Sets.getLink(SetIndex);
       InterfaceMap.insert(std::make_pair(SetIndex, CurrValue));
       auto ExternalAttrs = getExternallyVisibleAttrs(Link.Attrs);
       if (ExternalAttrs.any())
         Summary.RetParamAttributes.push_back(