[CFLAA] Teach CFLAndersAliasAnalysis to discern reads from writes

[grievejia]

Summary

This patch introduces no functional changes.

The original 4-state state machine we used previously does not provide us with enough information to tell value reads from value writes. When given a reachable value alias pair (X, Y), we want to be able to tell if the function (transitively) assigns X to Y, or if the function (transitively) assigns Y to X, or if the function (transitively) assigns a third value Z to both, or if X and Y alias each other only because someone above X and someone above Y alias each other. The "directions" of assignments are very important to us since we need them to generate precise function summaries and yield better mod/ref results.

To keep track of assignment directions, I tried to add more states to the state machine. The semantics of the new machine should be exactly the same as before, except that given a particular state there's no ambiguities any more regarding what is read and what is written. Please refer to the codes for more details on the meaning of those newly added states.

I also tried to simplify the state machine matching codes with some macro abuses. We might want to get rid of those macros someday, but for now I think they do make things cleaner.

[george.burgess.iv]

Thanks for the patch!

lib/Analysis/CFLAndersAliasAnalysis.cpp

86

Why are we now starting from 1?

92

Out of curiosity, do we gain anything from having FlowToWriteOnly on something that already has FlowToReadWrite on it?

Specifically, given:

ReachabilitySet R = whatever;
R.insert(FromVal, ToVal, FlowToReadWrite);
R.insert(FromVal, ToVal, FlowToWriteOnly);

Is the second insert at all meaningful to us? If not, can we add a FIXME or TODO somewhere noting that we may be able to do less propagations if we check for this later?

(Same question for FlowFromMemAliasNoReadWrite vs FlowFromMemAliasReadOnly, and FlowToMemAliasWriteOnly vs FlowToMemAliasReadWrite)

367

Can this be a lambda instead?

396

Can this (and the 2 below) be lambdas instead?

[grievejia]

lib/Analysis/CFLAndersAliasAnalysis.cpp

86

There was a state "FlowFromNoReadWrite" which was labelled 0. It was supposed to be the starting state. Later I found that we don't really need it since we do not store identity mapping (X, X) in ReachabilitySet, so I removed that state.

I thought the starting index doesn't really matter that much. I'm OK with any choice here.

92

The state FlowToWriteOnly does carry important information: if x is reachable from y at FlowToWriteOnly state, we know that y is (transitively) assigned to x. If x is reachable from y at FlowToReadWrite state, then there's a third value z which gets assigned to both x and y. The distinction here is basically what motivates this patch.

396

... I think you are right. Let me change them to lambdas.

[george.burgess.iv]

lib/Analysis/CFLAndersAliasAnalysis.cpp

86

The only reason I asked is because we're using these as indices into a bitset. 7 bits vs 8 bits is a wash; I was just making sure we weren't sneakily using the bits[0] bit in some way. :)

92

Ahh, now that makes sense. Thanks for clarifying!

[grievejia]

lib/Analysis/CFLAndersAliasAnalysis.cpp

92

Now that you mentioned it, maybe XXXReadWrite is not a good name for those states. At a first glance it looks like if X is reachable from Y at XXXReadWrite states it means that X is both read from and written to Y, yet this is not true: what it really means is that the path from X to Y contains both assignment edges and reverse assignment edges, which implies a third value written to both.

Let me add some comments that try to clarify this.

[grievejia]

Replace macros with lambdas.

[george.burgess.iv]

LGTM; thanks for adding the clarification!

lib/Analysis/CFLAndersAliasAnalysis.cpp

 // algorithm to perform CFL matching along the way: instead of recording
 // "whether X is reachable from Y", we keep track of "whether X is reachable
 // from Y at state Z", where the "state" field indicates where we are in the CFL
 // matching process. To understand the matching better, it is advisable to have
 // the state machine shown in Figure 3 of the paper available when reading the
 // codes: all we do here is to selectively expand the transitive closure by
 // discarding edges that are not recognized by the state machine.
 //
-// There is one difference between our current implementation and the one
-// described in the paper: out algorithm eagerly computes all alias pairs after
-// the CFLGraph is built, while in the paper the authors did the computation in
-// a demand-driven fashion. We did not implement the demand-driven algorithm due
-// to the additional coding complexity and higher memory profile, but if we
-// found it necessary we may switch to it eventually.
+// There are two differences between our current implementation and the one
+// described in the paper:
+// - Our algorithm eagerly computes all alias pairs after the CFLGraph is built,
+// while in the paper the authors did the computation in a demand-driven
+// fashion. We did not implement the demand-driven algorithm due to the
+// additional coding complexity and higher memory profile, but if we found it
+// necessary we may switch to it eventually.
+// - In the paper the authors use a state machine that does not distinguish
+// value reads from value writes. For example, if Y is reachable from X at state
+// S3, it may be the case that X is written into Y, or it may be the case that
+// there's a third value Z that writes into both X and Y. To make that
+// distinction (which is crucial in building function summary as well as
+// retrieving mod-ref info), we choose to duplicate some of the states in the
+// paper's proposed state machine. The duplication does not change the set the
+// machine accepts. Given a pair of reachable values, it only provides more
+// detailed information on which value is being written into and which is being
+// read from.
 //
 //===----------------------------------------------------------------------===//
 
 // N.B. AliasAnalysis as a whole is phrased as a FunctionPass at the moment, and
 // CFLAndersAA is interprocedural. This is *technically* A Bad Thing, because
 // FunctionPasses are only allowed to inspect the Function that they're being
 // run on. Realistically, this likely isn't a problem until we allow
 // FunctionPasses to run concurrently.
static const Function *parentFunctionOfValue(const Value *Val) {
   if (auto *Arg = dyn_cast<Argument>(Val))
     return Arg->getParent();
   return nullptr;
 }
 
 namespace {
 
 enum class MatchState : uint8_t {
-  FlowFrom = 0,     // S1 in the paper
-  FlowFromMemAlias, // S2 in the paper
-  FlowTo,           // S3 in the paper
-  FlowToMemAlias    // S4 in the paper
+  // The following state represents S1 in the paper.
+  FlowFromReadOnly = 0,
+  // The following two states together represent S2 in the paper.
+  // The 'NoReadWrite' suffix indicates that there exists an alias path that
+  // does not contain assignment and reverse assignment edges.
+  // The 'ReadOnly' suffix indicates that there exists an alias path that
+  // contains reverse assignment edges only.
+  FlowFromMemAliasNoReadWrite,
+  FlowFromMemAliasReadOnly,
+  // The following two states together represent S3 in the paper.
+  // The 'WriteOnly' suffix indicates that there exists an alias path that
+  // contains assignment edges only.
+  // The 'ReadWrite' suffix indicates that there exists an alias path that
+  // contains both assignment and reverse assignment edges. Note that if X and Y
+  // are reachable at 'ReadWrite' state, it does NOT mean X is both read from
+  // and written to Y. Instead, it means that a third value Z is written to both
+  // X and Y.
+  FlowToWriteOnly,
+  FlowToReadWrite,
+  // The following two states together represent S4 in the paper.
+  FlowToMemAliasWriteOnly,
+  FlowToMemAliasReadWrite,
 };
 
 // We use ReachabilitySet to keep track of value aliases (The nonterminal "V" in
 // the paper) during the analysis.
 class ReachabilitySet {
-  typedef std::bitset<4> StateSet;
+  typedef std::bitset<7> StateSet;
   typedef DenseMap<InstantiatedValue, StateSet> ValueStateMap;
   typedef DenseMap<InstantiatedValue, ValueStateMap> ValueReachMap;
   ValueReachMap ReachMap;
 
 public:
   typedef ValueStateMap::const_iterator const_valuestate_iterator;
   typedef ValueReachMap::const_iterator const_value_iterator;
 
for (const auto &Mapping : Graph.value_mappings()) {
     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
       for (auto &Edge : ValueInfo.getNodeInfoAtLevel(I).Edges) {
-        propagate(Edge.Other, Src, MatchState::FlowFrom, ReachSet, WorkList);
-        propagate(Src, Edge.Other, MatchState::FlowTo, ReachSet, WorkList);
+        propagate(Edge.Other, Src, MatchState::FlowFromReadOnly, ReachSet,
+                  WorkList);
+        propagate(Src, Edge.Other, MatchState::FlowToWriteOnly, ReachSet,
+                  WorkList);
       }
     }
   }
 }
 
 static Optional<InstantiatedValue> getNodeBelow(const CFLGraph &Graph,
                                                 InstantiatedValue V) {
   auto NodeBelow = InstantiatedValue{V.Val, V.DerefLevel + 1};
static void processWorkListItem(const WorkListItem &Item, const CFLGraph &Graph,
   // sorting FromNode and ToNode before insertion happens.
 
   // The newly added value alias pair may pontentially generate more memory
   // alias pairs. Check for them here.
   auto FromNodeBelow = getNodeBelow(Graph, FromNode);
   auto ToNodeBelow = getNodeBelow(Graph, ToNode);
   if (FromNodeBelow && ToNodeBelow &&
       MemSet.insert(*FromNodeBelow, *ToNodeBelow)) {
-    propagate(*FromNodeBelow, *ToNodeBelow, MatchState::FlowFromMemAlias,
-              ReachSet, WorkList);
+    propagate(*FromNodeBelow, *ToNodeBelow,
+              MatchState::FlowFromMemAliasNoReadWrite, ReachSet, WorkList);
     for (const auto &Mapping : ReachSet.reachableValueAliases(*FromNodeBelow)) {
       auto Src = Mapping.first;
-      if (Mapping.second.test(static_cast<size_t>(MatchState::FlowFrom)))
-        propagate(Src, *ToNodeBelow, MatchState::FlowFromMemAlias, ReachSet,
-                  WorkList);
-      if (Mapping.second.test(static_cast<size_t>(MatchState::FlowTo)))
-        propagate(Src, *ToNodeBelow, MatchState::FlowToMemAlias, ReachSet,
-                  WorkList);
+      auto MemAliasPropagate = [&](MatchState FromState, MatchState ToState) {
+        if (Mapping.second.test(static_cast<size_t>(FromState)))
+          propagate(Src, *ToNodeBelow, 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.
-  switch (Item.State) {
-  case MatchState::FlowFrom: {
-    for (const auto &RevAssignEdge : NodeInfo->ReverseEdges)
-      propagate(FromNode, RevAssignEdge.Other, MatchState::FlowFrom, ReachSet,
-                WorkList);
+  auto NextAssignState = [&](MatchState State) {
     for (const auto &AssignEdge : NodeInfo->Edges)
-      propagate(FromNode, AssignEdge.Other, MatchState::FlowTo, ReachSet,
-                WorkList);
+      propagate(FromNode, AssignEdge.Other, State, ReachSet, WorkList);
+  };
+  auto NextRevAssignState = [&](MatchState State) {
+    for (const auto &RevAssignEdge : NodeInfo->ReverseEdges)
+      propagate(FromNode, RevAssignEdge.Other, State, ReachSet, WorkList);
+  };
+  auto NextMemState = [&](MatchState State) {
     if (auto AliasSet = MemSet.getMemoryAliases(ToNode)) {
       for (const auto &MemAlias : *AliasSet)
-        propagate(FromNode, MemAlias, MatchState::FlowFromMemAlias, ReachSet,
-                  WorkList);
+        propagate(FromNode, MemAlias, State, ReachSet, WorkList);
     }
+  };
+
+  switch (Item.State) {
+  case MatchState::FlowFromReadOnly: {
+    NextRevAssignState(MatchState::FlowFromReadOnly);
+    NextAssignState(MatchState::FlowToReadWrite);
+    NextMemState(MatchState::FlowFromMemAliasReadOnly);
     break;
   }
-  case MatchState::FlowFromMemAlias: {
-    for (const auto &RevAssignEdge : NodeInfo->ReverseEdges)
-      propagate(FromNode, RevAssignEdge.Other, MatchState::FlowFrom, ReachSet,
-                WorkList);
-    for (const auto &AssignEdge : NodeInfo->Edges)
-      propagate(FromNode, AssignEdge.Other, MatchState::FlowTo, ReachSet,
-                WorkList);
+  case MatchState::FlowFromMemAliasNoReadWrite: {
+    NextRevAssignState(MatchState::FlowFromReadOnly);
+    NextAssignState(MatchState::FlowToWriteOnly);
     break;
   }
-  case MatchState::FlowTo: {
-    for (const auto &AssignEdge : NodeInfo->Edges)
-      propagate(FromNode, AssignEdge.Other, MatchState::FlowTo, ReachSet,
-                WorkList);
-    if (auto AliasSet = MemSet.getMemoryAliases(ToNode)) {
-      for (const auto &MemAlias : *AliasSet)
-        propagate(FromNode, MemAlias, MatchState::FlowToMemAlias, ReachSet,
-                  WorkList);
-    }
+  case MatchState::FlowFromMemAliasReadOnly: {
+    NextRevAssignState(MatchState::FlowFromReadOnly);
+    NextAssignState(MatchState::FlowToReadWrite);
+    break;
+  case MatchState::FlowToWriteOnly: {
+    NextAssignState(MatchState::FlowToWriteOnly);
+    NextMemState(MatchState::FlowToMemAliasWriteOnly);
     break;
   }
-  case MatchState::FlowToMemAlias: {
-    for (const auto &AssignEdge : NodeInfo->Edges)
-      propagate(FromNode, AssignEdge.Other, MatchState::FlowTo, ReachSet,
-                WorkList);
+  case MatchState::FlowToReadWrite: {
+    NextAssignState(MatchState::FlowToReadWrite);
+    NextMemState(MatchState::FlowToMemAliasReadWrite);
+    break;
+  }
+  case MatchState::FlowToMemAliasWriteOnly: {
+    NextAssignState(MatchState::FlowToWriteOnly);
+    break;
+  }
+  case MatchState::FlowToMemAliasReadWrite: {
+    NextAssignState(MatchState::FlowToReadWrite);
     break;
   }
   }
 }
 
 static AliasAttrMap buildAttrMap(const CFLGraph &Graph,
                                  const ReachabilitySet &ReachSet) {
   AliasAttrMap AttrMap;