Method for vectorizing and executing on an SIMD machine outer loops in the presence of recurrent inner loops

Claim 1

A method for execution on an SISD machine for ascertaining any source code procedural language statements which are amenable to being compiled into object code for execution on an SIMD machine, comprising the steps of: (a) mapping in said SISD machine said source code statements onto n counterpart nodes of a dependence graph, said graph (FIGS. 2A, 2B) having directed edges, the edges connecting nodes according to dependences and selectively forming closed traverses or loops, the edges further being selectively nested and labeled with a level number (FIGS. 2A, 3A, edges labeled 4) indicating the level of any node (1, 2, . . . , n) causing the dependence, each edge (FIG. 2B) being further labeled with indicia as to whether it is either innermost-sensitive or innermost-preventing; (b) identifying in said SISD machine the statements at the nodes bounding each level of any innermost-sensitive and loop-independent edges of the graph, if at that level, the edges having the labeled dependences can be reordered to operate as an innermost loop and if there are no cycles in the graph after recording; and (c) generating in said SISD machine object code obtained from any statements identified in step (b).

Claim 2

A method for execution on an SISD machine for ascertaining any source code procedural language statements which are amenable to being compiled into object code for execution on an SIMD machine, comprising the steps of: (a) mapping in said SISD machine said source code statements onto n counterpart nodes of a dependence graph, said graph (FIGS. 2A, 2B) having directed edges, the edges connecting nodes according to dependences and selectively forming closed traverses or loops, the edges further being selectively nested and labeled with a level number (FIGS. 2A, 3A, edges labeled 4) indicating the level of any node (1, 2, . . . , n) causing the dependence, each edge (FIG. 2B) being further labeled with indicia as to whether it is either innermost-sensitive or innermost-preventing; (b) identifying in said SISD machine the statements at the nodes bounding each level of any innermost-sensitive and loop-independent edges of the graph, if at that level, the edges having the labeled dependences can be reordered to operate as an innermost loop and if there are no cycles in the graph after recording; and (c) generating in said SISD machine object code obtained from any statements identified in step (b).

Claim 5

A method for vectorizing and compiling object code for execution on an SIMD machine, said object code being derived from procedural language source code statements, said source code including nested loops in which at least one loop is innermost and at least one loop is outermost, said nested loops occurring where at least one innermost loop and at least one outermost loop recur, said method being executable on an SISD machine, comprising the steps of: (a) converting in said SISD machine source code into an intermediate language string and optimizing said string; (b) forming in said SISD machine a dependence graph from the string, said dependence graph including at least one node, the nodes of the dependence graph representing statements in the string; (c) partitioning the dependence graph into regions, said partitioning occurring within the SISD machine, the regions being denominated "strongly-connected regions" (SCRs), each node in an SCR being connected to every other node by at least one path, said partitioning being conducted on a level-by-level basis from outside to inside; (d) ascertaining in said SISD machine which SCRs of said dependence graph partitioned according to step (c) are executable on an SIMD machine by: (1) ascertaining at each level within a region and for each dependence at that level whether the dependence at that level is interchangeable with each successive inner loop until any preselected one of the loops at that level is the innermost loop, and (2) forming in said SISD machine a subgraph from all dependences at that level which are ascertained to be interchangeable to the innermost loop and all loop-independent dependences, the statements constituting the subgraph being vectorized at that level if said subgraph is acyclic; and (e) generating in said SISD machine object code for the statements constituting the subgraph.

Claim 6

A method for vectorizing and compiling object code for execution on an SIMD machine, said object code being derived from procedural language source code statements, said source code including nested loops in which at least one loop is innermost and at least one loop is outermost, said nested loops occurring where at least one innermost loop and at least one outermost loop recur, said method being executable on an SISD machine, comprising the steps of: (a) converting in said SISD machine source code into an intermediate language string and optimizing said string; (b) forming in said SISD machine a dependence graph from the string, said dependence graph including at least one node, the nodes of the dependence graph representing statements in the string; (c) partitioning the dependence graph into regions, said partitioning occurring within the SISD machine, the regions being denominated "strongly-connected regions" (SCRs), each node in an SCR being connected to every other node by at least one path, said partitioning being conducted on a level-by-level basis from outside to inside; (d) ascertaining in said SISD machine which SCRs of said dependence graph partitioned according to step (c) are executable on an SIMD machine by: (1) ascertaining at each level within a region and for each dependence at that level whether the dependence at that level is interchangeable with each successive inner loop until any preselected one of the loops at that level is the innermost loop, and (2) forming in said SISD machine a subgraph from all dependences at that level which are ascertained to be interchangeable to the innermost loop and all loop-independent dependences, the statements constituting the subgraph being vectorized at that level if said subgraph is acyclic; and (e) generating in said SISD machine object code for the statements constituting the subgraph.