How should I go about implementing a points-to analysis in Maude?
- by reprogrammer
I'm going to implement a points-to analysis algorithm. I'd like to implement this analysis mainly based on the algorithm by Whaley and Lam. Whaley and Lam use a BDD based implementation of Datalog to represent and compute the points-to analysis relations.
The following lists some of the relations that are used in a typical points-to analysis. Note that D(w, z) :- A(w, x),B(x, y), C(y, z) means D(w, z) is true if A(w, x), B(x, y), and C(y, z) are all true. BDD is the data structure used to represent these relations.
Relations
input vP0 (variable : V, heap : H)
input store (base : V, field : F, source : V)
input load (base : V, field : F, dest : V)
input assign (dest : V, source : V)
output vP (variable : V, heap : H)
output hP (base : H, field : F, target : H)
Rules
vP(v, h) :- vP0(v, h)
vP(v1, h) :- assign(v1, v2), vP(v2, h)
hP(h1, f,h2) :- store(v1, f, v2), vP(v1, h1), vP(v2, h2)
vP(v2, h2) :- load(v1, f, v2), vP(v1, h1), hP(h1, f, h2)
I need to understand if Maude is a good environment for implementing points-to analysis. I noticed that Maude uses a BDD library called BuDDy. But, it looks like that Maude uses BDDs for a different purpose, i.e. unification. So, I thought I might be able to use Maude instead of a Datalog engine to compute the relations of my points-to analysis. I assume Maude propagates independent information concurrently. And this concurrency could potentially make my points-to analysis faster than sequential processing of rules. But, I don't know the best way to represent my relations in Maude. Should I implement BDD in Maude myself, or Maude's internal unification based on BDD has the same effect?
