[CFLAA] Add an initial implementation of field-sensitivity to CFLAndersAliasAnalyiss

[grievejia]

Summary

This patch teaches CFLAnders to perform field offset arithmetic when propagating reachability along assignment edges.The only tricky part here is to get the plus/minus signs of those offsets right. Other than that, the analysis logic doesn't need to change too much.

Vurrent implementation should suffice for intra-procedural field-sensitive analysis. Unfortunately if we move to inter-procedural case, the correctness of the analysis is lost. The reason is that our current interprocedural analysis framework can only record ExternalRelations of the form "X = Y + Offset", where X and Y are InterfaceValues. Field-sensitive inter-procedural function summary often encounters relations of the form "*X = *(Y + Offset)", and there is no way to describe such a relation in the function summary without introducing any temporaries. In fact, even if the function summary knows how to describe those relations, for CFLGraph we have the same problem.

This is not a fundamentally hard problem to solve, but it is annoying in the sense that it's hard to get around it with just simple hacks. I am still figuring out a way to solve the aforementioned problem with as little modification to the current codebase as possible. My intuition is that no matter what I do, the change is not going to be small. So I'll just check in the intraprocedural analysis works to ease the burden of code review.

[george.burgess.iv]

So I'll just check in the intraprocedural analysis works to ease the burden of code review.

Thank you :)

lib/Analysis/AliasAnalysisSummary.h

148

If we get many more of these, it may be nice to just have a cflaa::PointerOffset type (or whatever) with operators that know how to handle checking for unknown. If only because it would make it more difficult to cause subtle bugs.

lib/Analysis/CFLAndersAliasAnalysis.cpp

145

Please rebase; Having DenseMapInfo outside of namespace llvm { upset GCC and made it issue warnings. :)

458

Until we make it correct, would it make sense to put an assert(not_using_broken_params && "This won't produce correct output for ${case}.")? Or will that loudly break lots of things?

[grievejia]

lib/Analysis/AliasAnalysisSummary.h

148

Agreed. The addOffset() and subOffset() functions are just quick helpers I wrote to get things going. At some point we may want to switch to a dedicated newtype.

lib/Analysis/CFLAndersAliasAnalysis.cpp

458

Unfortunately I think compared to those cases where this work, there are far more cases where this doesn't work :(

I'm going to abandon this patch for now, since committing into the codebase will just break CFLAnders and I don't think it can be fixed quickly in the near future. I'll bring it back once I get a better understanding of how to properly construct a field-sensitive function summary.

lib/Analysis/AliasAnalysisSummary.h

 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;
 }
+inline int64_t subOffset(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;
+}
+inline int64_t negOffset(int64_t Offset) { return subOffset(0, Offset); }
 
 /// 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;
 };
 

lib/Analysis/CFLAndersAliasAnalysis.cpp

 struct OffsetInstantiatedValue {
   InstantiatedValue IVal;
   int64_t Offset;
 };
 
 bool operator==(OffsetInstantiatedValue LHS, OffsetInstantiatedValue RHS) {
   return LHS.IVal == RHS.IVal && LHS.Offset == RHS.Offset;
 }
+}
+
+// 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;
+  }
+};
+
+namespace {
 
 // 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<OffsetInstantiatedValue, StateSet> ValueStateMap;
   typedef DenseMap<InstantiatedValue, ValueStateMap> ValueReachMap;
   ValueReachMap ReachMap;
 
 public:
   typedef ValueStateMap::const_iterator const_valuestate_iterator;
   typedef ValueReachMap::const_iterator const_value_iterator;
 
   // Insert edge 'From->To' at state 'State'
-  bool insert(InstantiatedValue From, InstantiatedValue To, MatchState State) {
+  bool insert(InstantiatedValue From, InstantiatedValue To, int64_t Offset,
+              MatchState State) {
     assert(From != To);
-    auto &States = ReachMap[To][From];
+    auto &States = ReachMap[To][OffsetInstantiatedValue{From, Offset}];
     auto Idx = static_cast<size_t>(State);
     if (!States.test(Idx)) {
       States.set(Idx);
       return true;
     }
     return false;
   }
 
public:
   iterator_range<const_iterator> mappings() const {
     return make_range<const_iterator>(AttrMap.begin(), AttrMap.end());
   }
 };
 
 struct WorkListItem {
   InstantiatedValue From;
   InstantiatedValue To;
+  int64_t Offset;
   MatchState State;
 };
 
 struct ValueSummary {
   struct Record {
     InterfaceValue IValue;
     unsigned DerefLevel;
+    int64_t Offset;
   };
   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<OffsetValue>> AliasMap;
 
   /// Map a value to its corresponding AliasAttrs
populateAliasMap(DenseMap<const Value *, std::vector<OffsetValue>> &AliasMap,
   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) {
+      auto OVal = InnerMapping.first;
       // Again, AliasMap only cares about top-level values
-      if (InnerMapping.first.DerefLevel == 0)
-        AliasList.push_back(OffsetValue{InnerMapping.first.Val, UnknownOffset});
+      if (OVal.IVal.DerefLevel == 0)
+        AliasList.push_back(OffsetValue{OVal.IVal.Val, negOffset(OVal.Offset)});
     }
 
     // Sort AliasList for faster lookup
     std::sort(AliasList.begin(), AliasList.end());
   }
 }
 
 static void populateExternalRelations(
static void populateExternalRelations(
   // 'ValueMap' here records, for each value, which InterfaceValues read from or
   // write into it. If both the read list and the write list of a given value
   // are non-empty, we know that a particular value is an intermidate and we
   // need to add summary edges from the writes to the reads.
   DenseMap<Value *, ValueSummary> ValueMap;
   for (const auto &OuterMapping : ReachSet.value_mappings()) {
     if (auto Dst = getInterfaceValue(OuterMapping.first, RetVals)) {
       for (const auto &InnerMapping : OuterMapping.second) {
+        auto OVal = InnerMapping.first;
+        auto SrcIVal = OVal.IVal;
+        auto Offset = OVal.Offset;
         // If Src is a param/return value, we get a same-level assignment.
-        if (auto Src = getInterfaceValue(InnerMapping.first, RetVals)) {
+        if (auto Src = getInterfaceValue(SrcIVal, 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, UnknownOffset});
+            ExtRelations.push_back(ExternalRelation{*Dst, *Src, Offset});
           // 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});
+                ValueSummary::Record{*Dst, SrcIVal.DerefLevel, Offset});
           if (hasWriteOnlyState(InnerMapping.second))
             ValueMap[SrcIVal.Val].ToRecords.push_back(
-                ValueSummary::Record{*Dst, SrcIVal.DerefLevel});
+                ValueSummary::Record{*Dst, SrcIVal.DerefLevel, Offset});
         }
       }
     }
   }
 
   for (const auto &Mapping : ValueMap) {
     for (const auto &FromRecord : Mapping.second.FromRecords) {
       for (const auto &ToRecord : Mapping.second.ToRecords) {
         auto ToLevel = ToRecord.DerefLevel;
         auto FromLevel = FromRecord.DerefLevel;
         // Same-level assignments should have already been processed by now
         if (ToLevel == FromLevel)
           continue;
 
         auto SrcIndex = FromRecord.IValue.Index;
         auto SrcLevel = FromRecord.IValue.DerefLevel;
+        auto SrcOffset = FromRecord.Offset;
         auto DstIndex = ToRecord.IValue.Index;
         auto DstLevel = ToRecord.IValue.DerefLevel;
+        auto DstOffset = ToRecord.Offset;
+
         if (ToLevel > FromLevel)
           SrcLevel += ToLevel - FromLevel;
         else
           DstLevel += FromLevel - ToLevel;
 
-        ExtRelations.push_back(ExternalRelation{
-            InterfaceValue{SrcIndex, SrcLevel},
-            InterfaceValue{DstIndex, DstLevel}, UnknownOffset});
+        // FIXME: The following ExternalRelation is INCORRECT when SrcLevel > 0
+        // or DstLevel > 0.
+        ExtRelations.push_back(
+            ExternalRelation{InterfaceValue{SrcIndex, SrcLevel},
+                             InterfaceValue{DstIndex, DstLevel},
+                             subOffset(SrcOffset, DstOffset)});
       }
     }
   }
 
   // Remove duplicates in ExtRelations
   std::sort(ExtRelations.begin(), ExtRelations.end());
   ExtRelations.erase(std::unique(ExtRelations.begin(), ExtRelations.end()),
                      ExtRelations.end());
if (RangePair.first != RangePair.second) {
       }
     }
   }
 
   return false;
 }
 
 static void propagate(InstantiatedValue From, InstantiatedValue To,
-                      MatchState State, ReachabilitySet &ReachSet,
+                      int64_t Offset, MatchState State,
+                      ReachabilitySet &ReachSet,
                       std::vector<WorkListItem> &WorkList) {
   if (From == To)
     return;
-  if (ReachSet.insert(From, To, State))
-    WorkList.push_back(WorkListItem{From, To, State});
+  if (ReachSet.insert(From, To, Offset, State))
+    WorkList.push_back(WorkListItem{From, To, Offset, State});
 }
 
 static void initializeWorkList(std::vector<WorkListItem> &WorkList,
                                ReachabilitySet &ReachSet,
                                const CFLGraph &Graph) {
   for (const auto &Mapping : Graph.value_mappings()) {
     auto Val = Mapping.first;
     auto &ValueInfo = Mapping.second;
     assert(ValueInfo.getNumLevels() > 0);
 
     // Insert all immediate assignment neighbors to the worklist
     for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; ++I) {
       auto Src = InstantiatedValue{Val, I};
-      // If there's an assignment edge from X to Y, it means Y is reachable from
-      // X at S2 and X is reachable from Y at S1
+      // If there's an assignment edge from X + Offset to Y, it means (Y -
+      // Offset) is reachable from X at state FlowToWriteOnly and (X + Offset)
+      // is reachable from Y at state FlowFromReadOnly
       for (auto &Edge : ValueInfo.getNodeInfoAtLevel(I).Edges) {
-        propagate(Edge.Other, Src, MatchState::FlowFromReadOnly, ReachSet,
-                  WorkList);
-        propagate(Src, Edge.Other, MatchState::FlowToWriteOnly, ReachSet,
-                  WorkList);
+        propagate(Edge.Other, Src, Edge.Offset, MatchState::FlowFromReadOnly,
+                  ReachSet, WorkList);
+        propagate(Src, Edge.Other, negOffset(Edge.Offset),
+                  MatchState::FlowToWriteOnly, ReachSet, WorkList);
       }
     }
   }
 }
 
 static Optional<InstantiatedValue> getNodeBelow(const CFLGraph &Graph,
                                                 InstantiatedValue V) {
   auto NodeBelow = InstantiatedValue{V.Val, V.DerefLevel + 1};
   if (Graph.getNode(NodeBelow))
     return NodeBelow;
   return None;
 }
 
 static void processWorkListItem(const WorkListItem &Item, const CFLGraph &Graph,
                                 ReachabilitySet &ReachSet, AliasMemSet &MemSet,
                                 std::vector<WorkListItem> &WorkList) {
   auto FromNode = Item.From;
   auto ToNode = Item.To;
+  auto Offset = Item.Offset;
 
   auto NodeInfo = Graph.getNode(ToNode);
   assert(NodeInfo != nullptr);
 
   // TODO: propagate field offsets
 
   // FIXME: Here is a neat trick we can do: since both ReachSet and MemSet holds
   // relations that are symmetric, we could actually cut the storage by half by
   // sorting FromNode and ToNode before insertion happens.
 
   // The newly added value alias pair may pontentially generate more memory
   // alias pairs. Check for them here.
+  // Note that MemAlias reachability can only be triggered when Offset is 0 or
+  // Unknown
+  if (Offset == 0 || Offset == UnknownOffset) {
     auto FromNodeBelow = getNodeBelow(Graph, FromNode);
     auto ToNodeBelow = getNodeBelow(Graph, ToNode);
     if (FromNodeBelow && ToNodeBelow &&
         MemSet.insert(*FromNodeBelow, *ToNodeBelow)) {
-    propagate(*FromNodeBelow, *ToNodeBelow,
+      propagate(*FromNodeBelow, *ToNodeBelow, Offset,
                 MatchState::FlowFromMemAliasNoReadWrite, ReachSet, WorkList);
-    for (const auto &Mapping : ReachSet.reachableValueAliases(*FromNodeBelow)) {
-      auto Src = Mapping.first;
+      for (const auto &Mapping :
+           ReachSet.reachableValueAliases(*FromNodeBelow)) {
+        auto SrcOVal = Mapping.first;
         auto MemAliasPropagate = [&](MatchState FromState, MatchState ToState) {
           if (Mapping.second.test(static_cast<size_t>(FromState)))
-          propagate(Src, *ToNodeBelow, ToState, ReachSet, WorkList);
+            propagate(SrcOVal.IVal, *ToNodeBelow, SrcOVal.Offset, ToState,
+                      ReachSet, WorkList);
         };
 
         MemAliasPropagate(MatchState::FlowFromReadOnly,
                           MatchState::FlowFromMemAliasReadOnly);
         MemAliasPropagate(MatchState::FlowToWriteOnly,
                           MatchState::FlowToMemAliasWriteOnly);
         MemAliasPropagate(MatchState::FlowToReadWrite,
                           MatchState::FlowToMemAliasReadWrite);
       }
     }
+  }
 
   // This is the core of the state machine walking algorithm. We expand ReachSet
   // based on which state we are at (which in turn dictates what edges we
   // should examine)
   // From a high-level point of view, the state machine here guarantees two
   // properties:
   // - If *X and *Y are memory aliases, then X and Y are value aliases
   // - If Y is an alias of X, then reverse assignment edges (if there is any)
   // should precede any assignment edges on the path from X to Y.
   auto NextAssignState = [&](MatchState State) {
     for (const auto &AssignEdge : NodeInfo->Edges)
-      propagate(FromNode, AssignEdge.Other, State, ReachSet, WorkList);
+      propagate(FromNode, AssignEdge.Other,
+                subOffset(Offset, AssignEdge.Offset), State, ReachSet,
+                WorkList);
   };
   auto NextRevAssignState = [&](MatchState State) {
     for (const auto &RevAssignEdge : NodeInfo->ReverseEdges)
-      propagate(FromNode, RevAssignEdge.Other, State, ReachSet, WorkList);
+      propagate(FromNode, RevAssignEdge.Other,
+                addOffset(Offset, RevAssignEdge.Offset), State, ReachSet,
+                WorkList);
   };
   auto NextMemState = [&](MatchState State) {
     if (auto AliasSet = MemSet.getMemoryAliases(ToNode)) {
       for (const auto &MemAlias : *AliasSet)
-        propagate(FromNode, MemAlias, State, ReachSet, WorkList);
+        propagate(FromNode, MemAlias, Offset, State, ReachSet, WorkList);
     }
   };
 
   switch (Item.State) {
   case MatchState::FlowFromReadOnly: {
     NextRevAssignState(MatchState::FlowFromReadOnly);
     NextAssignState(MatchState::FlowToReadWrite);
     NextMemState(MatchState::FlowFromMemAliasReadOnly);
static AliasAttrMap buildAttrMap(const CFLGraph &Graph,
   while (!WorkList.empty()) {
     for (const auto &Dst : WorkList) {
       auto DstAttr = AttrMap.getAttrs(Dst);
       if (DstAttr.none())
         continue;
 
       // Propagate attr on the same level
       for (const auto &Mapping : ReachSet.reachableValueAliases(Dst)) {
-        auto Src = Mapping.first;
+        auto Src = Mapping.first.IVal;
         if (AttrMap.add(Src, DstAttr))
           NextList.push_back(Src);
       }
 
       // Propagate attr to the levels below
       auto DstBelow = getNodeBelow(Graph, Dst);
       while (DstBelow) {
         if (AttrMap.add(*DstBelow, DstAttr)) {

lib/Analysis/CFLGraph.h

bool tryInterproceduralAnalysis(CallSite CS,
         assert(Summary != nullptr);
 
         auto &RetParamRelations = Summary->RetParamRelations;
         for (auto &Relation : RetParamRelations) {
           auto IRelation = instantiateExternalRelation(Relation, CS);
           if (IRelation.hasValue()) {
             Graph.addNode(IRelation->From);
             Graph.addNode(IRelation->To);
-            Graph.addEdge(IRelation->From, IRelation->To);
+            Graph.addEdge(IRelation->From, IRelation->To, IRelation->Offset);
           }
         }
 
         auto &RetParamAttributes = Summary->RetParamAttributes;
         for (auto &Attribute : RetParamAttributes) {
           auto IAttr = instantiateExternalAttribute(Attribute, CS);
           if (IAttr.hasValue())
             Graph.addNode(IAttr->IValue, IAttr->Attr);

test/Analysis/CFLAliasAnalysis/Andersen/gep_basic.ll

+; This testcase ensures that CFLAA correctly handles basic field offset
+; calculation.
+
+; RUN: opt < %s -disable-basicaa -cfl-anders-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+; CHECK: Function: test_basic_gep
+; CHECK: MayAlias: [3 x i32]* %a, i32* %a4
+; CHECK: MayAlias: [3 x i32]* %a, i32* %a8
+; CHECK: NoAlias: i32* %a4, i32* %a8
+; CHECK: MayAlias: [3 x i32]* %a, i32* %b
+; CHECK: NoAlias: i32* %a4, i32* %b
+; CHECK: NoAlias: i32* %a8, i32* %b
+; CHECK: MayAlias: [3 x i32]* %a, i32* %b4
+; CHECK: MayAlias: i32* %a4, i32* %b4
+; CHECK: NoAlias: i32* %a8, i32* %b4
+; CHECK: NoAlias: i32* %b, i32* %b4
+define void @test_basic_gep() {
+  %a = alloca [3 x i32], align 4
+  %a4 = getelementptr inbounds [3 x i32], [3 x i32]* %a, i32 0, i32 1
+  %a8 = getelementptr inbounds [3 x i32], [3 x i32]* %a, i32 0, i32 2
+  %b = bitcast [3 x i32]* %a to i32*
+  %b4 = getelementptr inbounds i32, i32* %b, i32 1
+  ret void
+}

test/Analysis/CFLAliasAnalysis/Andersen/gep_memalias.ll

+; This testcase ensures that CFLAA correctly handles aliasing patterns that
+; involves both field arithmetic and reference/dereference
+
+; RUN: opt < %s -disable-basicaa -cfl-anders-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+; CHECK: Function: test_mem_gep
+; CHECK: NoAlias: i64* %b, i64** %acast
+; CHECK: NoAlias: i64** %acast, i64** %aoff
+; CHECK: NoAlias: i64* %b, i64** %acastoff
+; CHECK: NoAlias: i64** %acast, i64** %acastoff
+; CHECK: NoAlias: [2 x i64*]* %a, i64* %acastload
+; CHECK: MayAlias: i64* %acastload, i64* %b
+; CHECK: NoAlias: i64* %acastload, i64** %aoff
+; CHECK: NoAlias: i64* %acastload, i64** %acast
+; CHECK: NoAlias: i64* %acastload, i64** %acastoff
+define void @test_mem_gep() {
+  %a = alloca [2 x i64*], align 8
+  %b = alloca i64, align 4
+  %aoff = getelementptr inbounds [2 x i64*], [2 x i64*]* %a, i64 0, i64 1
+  store i64* %b, i64** %aoff
+  
+  %acast = bitcast [2 x i64*]* %a to i64**
+  %acastoff = getelementptr inbounds i64*, i64** %acast, i64 1
+  %acastload = load i64*, i64** %acastoff
+  ret void
+}

test/Analysis/CFLAliasAnalysis/Andersen/gep_unknown.ll

+; This testcase ensures that CFLAA correctly handles field offset
+; calculations that involve UnknownOffset.
+
+; RUN: opt < %s -disable-basicaa -cfl-anders-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+; CHECK: Function: test_unknown_gep
+; CHECK: MayAlias: [3 x i32]* %a, i32* %an
+; CHECK: MayAlias: i32* %a4, i32* %an
+; CHECK: MayAlias: i32* %a8, i32* %an
+; CHECK: MayAlias: i32* %an, i32* %b
+; CHECK: MayAlias: [3 x i32]* %a, i32* %bn
+; CHECK: MayAlias: i32* %a4, i32* %bn
+; CHECK: MayAlias: i32* %a8, i32* %bn
+; CHECK: MayAlias: i32* %an, i32* %bn
+; CHECK: MayAlias: i32* %b, i32* %bn
+define void @test_unknown_gep(i32 %n) {
+  %a = alloca [3 x i32], align 4
+  %a4 = getelementptr inbounds [3 x i32], [3 x i32]* %a, i32 0, i32 1
+  %a8 = getelementptr inbounds [3 x i32], [3 x i32]* %a, i32 0, i32 2
+  %an = getelementptr inbounds [3 x i32], [3 x i32]* %a, i32 0, i32 %n
+  %b = bitcast [3 x i32]* %a to i32*
+  %bn = getelementptr inbounds i32, i32* %b, i32 %n
+  ret void
+}

test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-arg-gep.ll

+; This testcase ensures that CFL AA answers queries soundly when callee tries 
+; to return one of its parameters with certain field offset
+
+; RUN: opt < %s -disable-basicaa -cfl-anders-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+%S = type { i32, i32, i32 }
+
+define i32* @return_arg_gep(%S* %arg1, %S* %arg2) {
+  %acast = bitcast %S* %arg1 to i32*
+  %aoffset = getelementptr i32, i32* %acast, i32 1
+  ret i32* %aoffset
+}
+; CHECK-LABEL: Function: test_return_arg_gep
+; CHECK: NoAlias: %S* %a, %S* %b
+; CHECK: MayAlias: %S* %a, i32* %c
+; CHECK: NoAlias: %S* %b, i32* %c
+; CHECK: NoAlias: i32* %acast, i32* %c
+; CHECK: NoAlias: i32* %acast, i32* %d
+define void @test_return_arg_gep() {
+  %a = alloca %S, align 8
+  %b = alloca %S, align 8
+
+  %c = call i32* @return_arg_gep(%S* %a, %S* %b)
+  %d = getelementptr %S, %S* %a, i32 0, i32 1
+  ; We need %acast here for precise offset checking (it has smaller Size)
+  %acast = bitcast %S* %a to i32*
+
+  ret void
+}
 No newline at end of file

test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-deref-arg-gep.ll

+; This testcase ensures that CFL AA answers queries soundly when callee tries 
+; to return the dereference of one of its parameters with field offsets
+
+; RUN: opt < %s -disable-basicaa -cfl-anders-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+%S = type { i32, i32, i32 }
+
+define i32* @return_deref_arg_gep(%S** %arg1) {
+  %deref = load %S*, %S** %arg1
+  %deref_off = getelementptr %S, %S* %deref, i32 0, i32 1
+  ret i32* %deref_off
+}
+; CHECK-LABEL: Function: test_return_deref_arg_gep
+; CHECK: NoAlias: %S** %p, i32* %c
+; CHECK: NoAlias: %S* %lp, %S** %p
+; CHECK: MayAlias: %S* %lp, i32* %c
+; CHECK: NoAlias: %S** %p, i32* %lp_off
+; CHECK: MayAlias: i32* %c, i32* %lp_off
+; CHECK: MayAlias: %S* %lp, i32* %lp_off
+; CHECK: NoAlias: %S** %p, i32* %acast
+; CHECK: NoAlias: i32* %acast, i32* %c
+; CHECK: MayAlias: %S* %lp, i32* %acast
+; CHECK: NoAlias: i32* %acast, i32* %lp_off
+define void @test_return_deref_arg_gep() {
+  %a = alloca %S, align 8
+  %p = alloca %S*, align 8
+
+  store %S* %a, %S** %p
+  %c = call i32* @return_deref_arg_gep(%S** %p)
+
+  %lp = load %S*, %S** %p
+  %lp_off = getelementptr %S, %S* %lp, i32 0, i32 1
+  ; We need %acast here for precise offset checking (it has smaller Size)
+  %acast = bitcast %S* %a to i32*
+
+  ret void
+}
 No newline at end of file