On sparse evaluation representations (Q1605227): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3619797 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Languages and compilers for parallel computing. Proceedings of the 6th international Workshop, Portland, OR, USA, August 12-14, 1993. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Fast and Usually Linear Algorithm for Global Flow Analysis / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4068060 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fast algorithms for the elimination of common subexpressions / rank | |||
Normal rank |
Latest revision as of 11:53, 4 June 2024
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