On sparse evaluation representations (Q1605227)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On sparse evaluation representations |
scientific article |
Statements
On sparse evaluation representations (English)
0 references
15 July 2002
0 references
The sparse evaluation graph has emerged over the past several years as an intermediate representation that captures the dataflow information in a program compactly and helps perform dataflow analysis efficiently. The contributions of this paper are three-fold: We present a linear time algorithm for constructing a variant of the sparse evaluation graph for any dataflow analysis problem. Our algorithm has two advantages over previous algorithms for constructing sparse evaluation graphs. First, it is simpler to understand and implement. Second, our algorithm generates a more compact representation than the one generated by previous algorithms. (Our algorithm is also as efficient as the most efficient known algorithm for the problem.) We present a formal definition of an equivalent flow graph, which attempts to capture the goals of sparse evaluation. We present a quadratic algorithm for constructing an equivalent flow graph consisting of the minimum number of vertices possible. We show that the problem of constructing an equivalent flow graph consisting of the minimum number of vertices and edges is NP-hard. We generalize the notion of an equivalent flow graph to that of a partially equivalent flow graph, an even more compact representation, utilizing the fact that the dataflow solution is not required at every node of the control-flow graph. We also present an efficient linear time algorithm for constructing a partially equivalent flow graph.
0 references
sparse evaluation graphs
0 references
static single assignment forms
0 references
dataflow analysis
0 references
graph transformations
0 references
quick propagation graphs
0 references
equivalent flow graphs
0 references
partially equivalent flow graphs
0 references