Loop execution with predicate computing for dataflow machines

1. A method for compiling a computer program for execution on a data flow machine for generating loop control signals, comprising:

receiving source instructions of the computer program;

parsing and analyzing the computer program including identifying nested loops of the computer program; and

generating and outputting executable code for the computer program to execute on a data flow machine based at least in part on results of the analyzing, wherein the executable code includes executable code that recursively computes predicates of identified nested loops to allow execution of each loop to start when the loop's predicate is available, independent of whether any other loop is in execution or not,

wherein the computed predicate of an identified loop is a function of the loop's initial predicate (Pinitial), its backedge predicate (Pbackedge), and branch conditions at its initial and final blocks.

2. The method of claim 1 , wherein the identified nested loops include inner loops and outer loops, and wherein the predicate for an inner loop is computed first.

3. The method of claim 1 , wherein the predicate of the identified loop is computed as: Pbackedge∥Pinitial, where ∥ is a short-circuit logical operator, wherein Pbackedge is first evaluated, and if Pbackedge is true, Pinitial is not evaluated.

4. The method of claim 1 , wherein the computation of the predicate for the identified loop is recursive.

5. The method of claim 1 , wherein the identified nested loops include inner loops and outer loops, and wherein the predicate for an inner loop is computed first.

6. A compiler for compiling a computer program, comprising:

one or more analyzers residing in a memory, to, when executed by at least one processor coupled to the memory, parse and analyze source instructions of a computer program including identification of nested loops of the computer program; and

a code generator, residing in the memory and coupled to the one or more analyzers, to, when executed by the at least one processor, generate and output executable code for the computer program that executes on a data flow machine, including a data flow graph, based at least in part on results of the analysis, wherein the executable code includes executable code that recursively computes predicates of identified nested loops for use to generate a control signal for the data flow graph to allow execution of each loop to start when the loop's predicate is available, independent of whether any other loop is in execution or not,

wherein the data flow graph includes information that indicates execution of the identified loop can commence if a backedge predicate of the identified loop (Pbackedge) is true.

7. The compiler of claim 6 , wherein the computed predicate of an identified loop is a function of the loop's initial predicate (Pinitial) and its Pbackedge.

8. The compiler of claim 7 , wherein the predicate of the identified loop is computed as: Pbackedge∥Pinitial, where ∥ is a logical OR operation.

9. The compiler of claim 8 , wherein the predicate of the identified loop is computed as: Pbackedge∥Pinitial, where ∥ operator is a short-circuit operator, wherein Pbackedge is first evaluated, and if Pbackedge is true, Pinitial is not evaluated.

10. The compiler of claim 7 , where Pinitial is only evaluated once for all iterations of the loop.

11. The compiler of claim 7 , wherein the computed predicate of an identified loop is also a function of branch conditions within the loop.

12. The compiler of claim 7 , wherein the computation of the predicate for the identified loop is recursive, Pbackedge being a function of: Pinitial, predicates of code blocks comprising the loop, and branch conditions of those code blocks.

13. The compiler of claim 12 , wherein the identified nested loops include inner loops and outer loops, and wherein the predicate for an inner loop is computed first.

14. The compiler of claim 13 , wherein, for an identified inner loop with two code blocks, an initial code block Bm and a final code block Bn, and wherein the initial code block Bm has a predecessor code block Bl, and if:

Pm is a predicate for code block Bm, Pn is a predicate for code block Bn,

Pmn is a predicate for a control edge BmBn denoting process flow moving from code block Bm to code block Bn,

Pnm is a predicate for a backedge Pnm denoting process flow moving from code block Bn to code block Bm,

Plm is a predicate for a control edge denoting process flow moving from code block Bl to code block Bm, and

Cm is a branch condition for code block Bm, and Cn is a branch condition for code block Bn,

then the predicate Pm for the identified inner loop is computed as:

Pm=Pnm∥Plm, where ∥ is a logical OR operation,

Pmn=Pm && Cm, where && is a logical AND operation,

Pn=Pmn, and

Pnm=Pn && Cn.

15. The compiler of claim 14 , further comprising computing a loop iteration predicate Piter for the inner loop, which is the backedge predicate Pnm of the loop when Pnm is true.

16. The compiler of claim 14 , wherein a predicate computation for the inner loop begins once Plm is true.

17. The compiler of claim 6 , wherein the source instructions of the computer program are written in a high level language selected from one of C, C++ or Fortran.

18. The compiler of claim 6 , wherein the executable code that recursively computes comprises executable code that recursively computes from inner loops to outer loops.

19. An apparatus for computing, comprising:

one or more processors; and

a compiler stored in a memory to be operated by the one or more processors to compile a computer program, wherein the compiler includes:

one or more analyzers to parse and analyze source instructions of a computer program including identification of nested loops of the computer program; and

a code generator coupled to the one or more analyzers to generate and output executable code for the computer program that executes on a data flow machine based at least in part on results of the analysis, wherein the executable code includes executable code that computes predicates of identified nested loops to allow execution of each loop to start when the loop's predicate is available, independent of whether any other loop is in execution or not,

wherein the executable code further includes an instruction to run the identified loop if a backedge predicate of the identified loop (Pbackedge) is true.

20. The apparatus of claim 19 , wherein the computed predicate of an identified loop is a function of the loop's initial predicate (Pinitial) and its backedge predicate (Pbackedge).

21. The apparatus of claim 20 , wherein the predicate of the identified loop is computed as: Pbackedge∥Pinitial, where ∥ is a short-circuit logical operator, wherein Pbackedge is first evaluated, and if Pbackedge is true, Pinitial is not evaluated.

22. The apparatus of claim 19 , wherein the computed predicate of an identified loop is also a function of branch conditions within the loop.

23. The apparatus of claim 19 , wherein the computation of the predicate for the identified loop is recursive, Pbackedge being a function of: Pinitial, predicates of blocks comprising the loop, and branch conditions of those blocks.

24. The apparatus of claim 19 , wherein the identified nested loops include inner loops and outer loops, and wherein the predicate for an inner loop is computed first.