0
$\begingroup$

In order to optimize a program, I am trying to figure out how the idea of a lattice applies to data-flow graphs, as introduced by this presentation (first diagram below). The lattice seems to take a program, order its inputs and outputs, and allow for easily determining flow of variables and state, so you can perform verification and optimization. But I am not sure how to construct the lattice from the program statements.

In this question I would like to know how to construct the lattice from the program.

Specifically, given a program such as this:

var x = 10
var y = 20
var z = 0
var i = z
while (i < x) {
  y = y + x * i
  i = i + 1
  z = y + i
}

We can construct a Control-Flow Graph (CFG) where each node is a program statement such as var x = 10. From that we can construct a Data-Flow Graph (DFG) where we are keeping track of how a variable is used. This creates an def-use ordering, along the lines of:

x, y, i at the same time
z comes after i
...

That's where I start getting lost. But once we have a partial ordering, somehow a lattice is created. Finally from the lattice, we can do things such as doing pointer analysis (Figure 2) and computing fix-points (Figure 3). That will help in optimization and verification of the program.

I'm wondering only the first part, how to construct the lattice from the example program above. Wondering what is needed to construct the lattice at a high-level. I understand the upper and lower bounds of a lattice, which seems to correspond to CFG inputs and outputs being joined, but I don't quite see how to actually do the join (meet), what the nodes/vertices are in the lattice (not sure if it's a single program statement, a variable, or what), and what the edges are in the lattice. Once that is defined, then doing the rest of the stuff should be straightforward. Thank you for your help.


enter image description here

^- Figure (1).


enter image description here

^- Figure (2).


enter image description here

^- Figure (3).

$\endgroup$
  • $\begingroup$ I think this is too broad. You are asking us to explain something that might be an entire chapter of a textbook. This is not the kind of thing that can be explained in a few paragraphs, so isn't a good fit for our site format -- and when you are having trouble following an explanation in a textbook, that suggests you'll need an especially detailed (and hence) lengthy answer. I suggest you find a textbook and read about it, and if your first choice is confusing, try to find a different one. Online references aren't a substitute for a good textbook. $\endgroup$ – D.W. Apr 30 '18 at 5:33
  • $\begingroup$ Good points. Though I would specifically like to know the anatomy of the lattice image in that last picture, how the elements in the program I wrote would show up in a lattice. That's all I want to know. $\endgroup$ – Lance Pollard Apr 30 '18 at 5:41
  • $\begingroup$ The first link is broken. $\endgroup$ – chi May 31 '18 at 10:53
  • $\begingroup$ @chi Updated, it's a search for "piazza data-flow analysis and lattices", for some reason the links to it though expire after a few hours/days. $\endgroup$ – Lance Pollard May 31 '18 at 23:27
1
$\begingroup$

There is no such thing as a "DataFlow Graph lattice". Those are two separate things. A data flow graph is a graph that represents how data flows in a program, which can be helpful in data flow analysis. A lattice is a mathematical object that can be helpful for data flow analysis.

Data flow analysis is a broad subject. There are many techniques for data flow analysis (many use lattices, but it's not a hard requirement). They don't all use lattices in the same way. So, there's no one way to do the conversion you are referring to.

To learn more about the subject, I suggest reading a good textbook on program analysis.

$\endgroup$
  • $\begingroup$ I am not interested in learning about data flow analysis as a broad subject. I am specifically interested in how to construct a lattice from program statements. Updated the question to reflect that. $\endgroup$ – Lance Pollard May 1 '18 at 0:32
  • $\begingroup$ @LancePollard, I'm saying that that topic is very broad. There is not just one way to do that; there are many algorithms for data flow analysis, each of which might construct a different lattice, in a different way. I still suggest you find a good textbook. $\endgroup$ – D.W. May 1 '18 at 0:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.