US 5,327,561 A · System and method for solving monotone information propagation problems

Abstract

A method and system is provided for constructing sparse evaluation graphs for forward or backward monotone data flow problems. The sparse graph combines information as early as possible, yet directly connects nodes that generate and use information. This allows problems from the large, general class of monotone data flow problems to enjoy the advantages of solutions based on Static Single Assignment (SSA) form. The present invention includes a compiler configured to transform a source program into optimized executable code. The compiler contains an optimizer which is configured to optimize the source program, in which the source program and optimization program are represented by a data flow framework. The optimizer includes a sparse evaluation graph generator which generates a sparse evaluation graph and an evaluator connected to evaluate the sparse evaluation graph in relation to the data flow framework.

Claims28

Dependent claims

A computer-based system for solving monotone information propagation problems during the optimization of computer code, comprising:

optimizer means for optimizing a source program represented by a data flow framework that includes a flow graph, wherein said optimizer means comprises:
(a) first constructing means for constructing a sparse evaluation graph and a sparse map, wherein said sparse map maps edges from the flow graph to nodes in said sparse evaluation graph;
(b) evaluator means connected to said first constructing means for evaluating said sparse evaluation graph in relation to said data flow framework in order to determine a partial solution to a monotone information propagation problem;
and
(c) combiner means for applying said sparse map to said partial solution to obtain an extended solution to said monotone information propagation problem.

2 more elements

A computer-based method for solving monotone information propagation problems during the optimization of source code, comprising the steps of:

(1) entering source code into an optimizer, said source code represented by a data flow framework, said data flow framework includes a flow graph;
(2) defining a dominator tree from said flow graph, and defining a dominance frontier from said dominator tree and said flow graph;
(3) constructing a sparse evaluation graph and a sparse map from said data flow framework, said dominator tree, and said dominance frontier, wherein said sparse map maps edges from said flow graph to nodes in said sparse evaluation graph;
(4) evaluating said sparse evaluation graph with respect to said data flow framework, in order to determine a partial solution to a monotone information propagation problem;
and
(5) applying said sparse map to said partial solution to obtain an extended solution to said monotone information propagation problem.

3 more elements

A computer-based method of constructing a sparse evaluation graph and a sparse map from a source program represented by a data flow framework, the data flow framework includes a flow graph representing the source program and a formal basis for describing the behavior of nodes within the flow graph, wherein the sparse evaluation graph and sparse map are used for solving a monotone information propagation problem, the computer-based method comprising the steps of:

(1) generating a dominator tree from the flow graph, and generating a dominance frontier from said dominator tree and the flow graph;
(2) generating a set of sparse evaluation graph nodes, comprising the steps of:
(i) defining a set of Active Nodes by forming a set that includes all nodes that do not have an identity transfer function and a starting root node;
(ii) defining a set of Meet Nodes by taking the iterated dominance frontier of said active nodes;
and
(iii) combining said set of Active Nodes with said set of Meet Nodes;
(3) initializing each input of said sparse evaluation graph nodes to the best possible solution;
(4) determining a set of sparse evaluation graph edges;
and
(5) mapping edges from the flow graph to nodes in the sparse evaluation graph to form the sparse map;
and
(6) evaluating said sparse evaluation graph with respect to said data flow framework, in order to determine a partial solution to a monotone information propagation problem;
and
(7) applying said sparse map to said partial solution to obtain an extended solution to said monotone information propagation problem.

11 more elements

Dependencies are inferred from the claim text.

System and method for solving monotone information propagation problems

Life of this patent

System and method for solving monotone information propagation problems

Life of this patent

Abstract

Claims28