## § Dataflow analysis using Grobner basis

This was a quick experiment in using Grobner basis to model situations. We can represent our dataflow analysis constraints in terms of polynomial rewrites over $F_2$. Given the program:
p = { 0: ["=", "x", 'y'],
1: ['br', 2, 100],
2: ['=', 'z', 'x'],
3: ['br', 2],
100: ['ret', 'z'] }

whose semantics I hope are fairly straightforward --- the dictionary represents instruction locations. Instructions proceed sequentially. branch moves control flow around. Note that br can branch to multiple locations, since we are not control-flow sensitive. The idea is that since in a dataflow analysis, we need information at each variable at each program point, we can create a ring of polynomials over $F_2$ for each variable at each program point. So in this case, we wold need:
R = F_2[x0, y0, z0, x1, y1, z1, x2, y2, z2, x3, y3, z3, x100, y100, z100]

We then add elements into the ideal that represents our constraints. For example, to perform dataflow analysis, we need to add constraints about how if a variable z is alive, all variables that are used to compute z at 100 are alive. This sets up equations that may have cycles (in the case of loops). These are usually resolved using the Kildall algorithm. However, we can also ask SAGE to kindly solve the Grobner basis. I hypothesize that the "easy" dataflow problems out to be toric ideals which admit much faster solutions.