Method and system for automated improvement of parallelism in program compilation

1. A computer implemented method of program compilation to improve parallelism during the linking of the program by a compiler, the method comprising:

converting statements of the program to canonical form;

constructing abstract syntax tree (AST) for each procedure in the program;

traversing the program to construct a functional dataflow graph, in which an assignment statement or function call is represented as a node, a control flow decision is represented by a first set of nodes, or an array or set is represented as a second set of nodes and in which edges of the functional dataflow graph represent typed data;

identifying at least one loop in the functional dataflow graph that can be executed in parallel;

transforming the at least one loop to a set operation by retyping connections between nodes of the functional dataflow graph;

parsing code of the program to identify control structures that govern alternative statements; and

converting each control structure into a sub-graph with conditioning function and with alternative statements represented as separate paths in the graph that later merge and loop.

2. The method of claim 1 , further comprising:

identifying a recursive procedure; and

expanding the recursive procedure to provide nodes for each recursion in the AST representation of the recursive procedure.

3. The method of claim 1 , further comprising:

identifying indirect procedure calls; and

converting the indirect procedure calls to switch structures in the AST.

4. The method of claim 1 , wherein traversing further comprises:

expanding procedures found in the AST of a primary procedure of the program to incorporate an AST representing each secondary procedure of the program.

5. The method of claim 1 , further comprising:

creating a table of initial values for global variables.

6. The method of claim 1 , further comprising:

creating nodes representing initial global variable values; and

adding the nodes representing the initial global variable values as input nodes for the AST.

7. The method of claim 1 , further comprising:

creating a global procedures table to reference each procedure and associated AST for the program.

8. The method of claim 1 , further comprising:

linking the sub-graph structure to the functional dataflow graph by linking input and output interfaces of the sub-graph structure to surrounding nodes of the functional dataflow graph.

9. The method of claim 1 , further comprising:

outputting the functional dataflow graph of the program to a compiler to guide parallelized compilation of the program.

10. A non-transitory machine-readable medium having instructions stored thereon, which when executed by a computer system, execute a method of program compilation to improve parallelism during the linking of the program by a compiler, the method comprising:

converting statements of the program to canonical form;

constructing abstract syntax tree (AST) for each procedure in the program;

traversing the program to construct a functional dataflow graph, in which an assignment statement or function call is represented as a node, a control flow decision is represented by a first set of nodes, or an array or set is represented as a second set of nodes and in which edges of the functional dataflow graph represent typed data;

identifying at least one loop in the functional dataflow graph that can be executed in parallel;

transforming the at least one loop to a set operation by retyping connections between nodes of the functional dataflow graph;

parsing code of the program to identify control structures that govern alternative statements; and

converting each control structure into a sub-graph with conditioning function and with alternative statements represented as separate paths in the graph that later merge and loop.

11. The non-transitory machine-readable medium of claim 10 , further comprising:

identifying a recursive procedure; and

expanding the recursive procedure to provide nodes for each recursion in the AST representation of the recursive procedure.

12. The non-transitory machine-readable medium of claim 10 , further comprising:

identifying indirect procedure calls; and

converting the indirect procedure calls to switch structures in the AST.

13. The non-transitory machine-readable medium of claim 10 , wherein traversing further comprises:

expanding procedures found in the AST of a primary procedure of the program to incorporate an AST representing each secondary procedure of the program.

14. The non-transitory machine-readable medium of claim 10 , further comprising:

creating a table of initial values for global variables.

15. The non-transitory machine-readable non-transitory of claim 10 , further including instructions, when executed perform the method further comprising:

creating nodes representing initial global variable values; and

adding the nodes representing the initial global variable values as input nodes for the AST.

16. The non-transitory machine-readable medium of claim 10 , further comprising:

creating a global procedures table to reference each procedure and associated AST for the program.

17. The non-transitory machine-readable medium of claim 10 , further comprising:

linking the sub-graph structure to the functional dataflow graph by linking input and output interfaces of the sub-graph structure to surrounding nodes of the functional dataflow graph.

18. The non-transitory machine-readable medium of claim 10 , further comprising:

outputting the functional dataflow graph of the program to a compiler to guide parallelized compilation of the program.