Index: lib/Analysis/CFLAndersAliasAnalysis.cpp =================================================================== --- lib/Analysis/CFLAndersAliasAnalysis.cpp +++ lib/Analysis/CFLAndersAliasAnalysis.cpp @@ -27,12 +27,23 @@ // 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. // //===----------------------------------------------------------------------===// @@ -71,16 +82,23 @@ 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 = 1, + // The following two states together represent S2 in the paper + FlowFromMemAliasNoReadWrite, + FlowFromMemAliasReadOnly, + // The following two states together represent S3 in the paper + 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<8> StateSet; typedef DenseMap ValueStateMap; typedef DenseMap ValueReachMap; ValueReachMap ReachMap; @@ -292,8 +310,10 @@ // 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); } } } @@ -328,69 +348,88 @@ 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(MatchState::FlowFrom))) - propagate(Src, *ToNodeBelow, MatchState::FlowFromMemAlias, ReachSet, - WorkList); - if (Mapping.second.test(static_cast(MatchState::FlowTo))) - propagate(Src, *ToNodeBelow, MatchState::FlowToMemAlias, ReachSet, - WorkList); + +#define MEMALIAS_PROPAGATE(SRC, DST) \ + if (Mapping.second.test(static_cast(MatchState::SRC))) \ + propagate(Src, *ToNodeBelow, MatchState::DST, ReachSet, WorkList); + + MEMALIAS_PROPAGATE(FlowFromReadOnly, FlowFromMemAliasReadOnly); + MEMALIAS_PROPAGATE(FlowToWriteOnly, FlowToMemAliasWriteOnly); + MEMALIAS_PROPAGATE(FlowToReadWrite, FlowToMemAliasReadWrite); + +#undef MEMALIAS_PROPAGATE } } - // 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. +// 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. + +#define NEXT_ASSIGN_STATE(STATE) \ + for (const auto &AssignEdge : NodeInfo->Edges) \ + propagate(FromNode, AssignEdge.Other, MatchState::STATE, ReachSet, \ + WorkList); + +#define NEXT_REV_ASSIGN_STATE(STATE) \ + for (const auto &RevAssignEdge : NodeInfo->ReverseEdges) \ + propagate(FromNode, RevAssignEdge.Other, MatchState::STATE, ReachSet, \ + WorkList); + +#define NEXT_MEM_STATE(STATE) \ + if (auto AliasSet = MemSet.getMemoryAliases(ToNode)) { \ + for (const auto &MemAlias : *AliasSet) \ + propagate(FromNode, MemAlias, MatchState::STATE, ReachSet, WorkList); \ + } + switch (Item.State) { - case MatchState::FlowFrom: { - 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); - if (auto AliasSet = MemSet.getMemoryAliases(ToNode)) { - for (const auto &MemAlias : *AliasSet) - propagate(FromNode, MemAlias, MatchState::FlowFromMemAlias, ReachSet, - WorkList); - } + case MatchState::FlowFromReadOnly: { + NEXT_REV_ASSIGN_STATE(FlowFromReadOnly); + NEXT_ASSIGN_STATE(FlowToReadWrite); + NEXT_MEM_STATE(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: { + NEXT_REV_ASSIGN_STATE(FlowFromReadOnly); + NEXT_ASSIGN_STATE(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: { + NEXT_REV_ASSIGN_STATE(FlowFromReadOnly); + NEXT_ASSIGN_STATE(FlowToReadWrite); + break; + } + case MatchState::FlowToWriteOnly: { + NEXT_ASSIGN_STATE(FlowToWriteOnly); + NEXT_MEM_STATE(FlowToMemAliasWriteOnly); break; } - case MatchState::FlowToMemAlias: { - for (const auto &AssignEdge : NodeInfo->Edges) - propagate(FromNode, AssignEdge.Other, MatchState::FlowTo, ReachSet, - WorkList); + case MatchState::FlowToReadWrite: { + NEXT_ASSIGN_STATE(FlowToReadWrite); + NEXT_MEM_STATE(FlowToMemAliasReadWrite); break; } + case MatchState::FlowToMemAliasWriteOnly: { + NEXT_ASSIGN_STATE(FlowToWriteOnly); + break; + } + case MatchState::FlowToMemAliasReadWrite: { + NEXT_ASSIGN_STATE(FlowToReadWrite); + break; } + } + +#undef NEXT_ASSIGN_STATE +#undef NEXT_REV_ASSIGN_STATE +#undef NEXT_MEM_STATE } static AliasAttrMap buildAttrMap(const CFLGraph &Graph,