On sparse evaluation representations
type: Item
instance of: scholarly article
title: On sparse evaluation representations
zbMATH Open document ID: 0996.68131
DOI: 10.1016/S0304-3975(00)00315-7
author: G. Ramalingam
published in: Theoretical Computer Science
publication date: 2002-07-15T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1768116
zbMATH Keywords: sparse evaluation graphs
zbMATH Keywords: static single assignment forms
zbMATH Keywords: dataflow analysis
zbMATH Keywords: graph transformations
zbMATH Keywords: quick propagation graphs
zbMATH Keywords: equivalent flow graphs
zbMATH Keywords: partially equivalent flow graphs
MaRDI profile type: Publication
cites work: Q3619797
cites work: Languages and compilers for parallel computing. Proceedings of the 6th international Workshop, Portland, OR, USA, August 12-14, 1993.
cites work: A Fast and Usually Linear Algorithm for Global Flow Analysis
cites work: Q4068060
cites work: Fast algorithms for the elimination of common subexpressions
description: scientific article; zbMATH DE number 1768116