Method and apparatus for moving area operator definition instruction statements within control flow structures

1. A method of comprising:

using one or more processors for:

identifying, within data representing control flow information that includes one or more blocks of statements and one or more data dependent control flow structures each including one or more data dependent branches each branch including one or more blocks of statements, an area operator definition instruction statement located outside the one or more data dependent control flow structures where the area operator definition instruction statement includes a resultant and at least one operand;

identifying, within one of the one or more data dependent branches, at least one area operator use instruction statement having the resultant of the area operator definition instruction statement as an operand; and

moving the area operator definition instruction statement within the data dependent branch.

2. The method of claim 1 wherein moving the area operator definition instruction statement within the data dependent branch comprises:

identifying, within the one or more data dependent branches, an area operator least common dominator (“LCD”) block representative of the least common dominator of all area operator use instruction statements; and

moving the area operator definition instruction statement within the area operator LCD block.

3. The method of claim 2 further comprising:

identifying, outside the one or more data dependent control flow structures, at least one source instruction statement having a resultant that is needed to compute the area operator definition instruction statement; and

creating a source instruction block within the one of the one or more data dependent branches such that the source instruction block precedes the area operator LCD block and contains data representing one or more of:

the at least one source instruction statement; and

at least one symbolic memory location statement allocated to store the resultant of the at least one source instruction statement.

4. The method of claim 3 further comprising:

identifying a first path, from an entry block to an exit block within the data representing the control flow information, that includes the area operator LCD block;

identifying at least one alternate path, from the entry block to the exit block, that does not include the area operator LCD block;

identifying a common computation instruction block for all alternate paths where the common computation instruction block is located where each alternate path first intersects the first path; and

for each alternate path, adding one mirror block such that each mirror block immediately precedes the corresponding common computation instruction block wherein each mirror block contains data representing one or more of:

at least one of a source instruction statement having a resultant that is needed to compute the area operator definition instruction statement; and

at least one of a symbolic memory location statement allocated to store the resultant of the source instruction statement.

5. The method of claim 4 further comprising determining, for each block in the data representing the control flow information, live memory location information representing symbolic memory locations that may be needed at any subsequent point within the data representing the control flow information.

6. The method of claim 5 , wherein determining live memory location information for each block comprises:

for each non-mirror block, providing data representing at least one symbolic memory location allocated to store at least one resultant that might be used as an operand in at least one statement on a path from the non-mirror block to an exit block of the data representing the control flow information; and

for each mirror block, providing data representing one or more of:

data provided as live memory location information for the source instruction block; and

data representing the at least one symbolic memory location statement allocated to store the resultant of the at least one source instruction statement if contained in the source instruction block.

7. The method of claim 5 further comprising at least one of:

applying a physical memory location allocation scheme to determine for each block within the data representing the control flow information, at least one physical memory location corresponding to the live memory location information; and

applying an optimization scheme to the data representing the control flow information.

8. The method of claim 5 further comprising translating the data representing the control flow information into data representing a shader program.

9. The method of claim 8 , wherein translating the data representing the control flow information into data representing the shader program comprises marking each instruction statement contained in the source instruction block to execute for each pixel in a grid whenever at least one pixel in the grid executes the area operator definition instruction statement.

10. The method of claim 1 further comprising, prior to identifying the area operator definition instruction statement, generating the data representing the control flow information based on received data representing application code.

11. A memory comprising stored instructions such that when executed, cause at least one of the one or more processors to:

identify, within data representing control flow information that includes one or more blocks of statements and one or more data dependent control flow structures each including one or more data dependent branches each branch including one or more blocks of statements, an area operator definition instruction statement located outside the one or more data dependent control flow structures where the area operator definition instruction statement includes a resultant and at least one operand;

identify, within one of the one or more data dependent branches, at least one area operator use instruction statement having the resultant of the area operator definition instruction statement as an operand; and

move the area operator definition instruction statement within the data dependent branch.

12. The memory of claim 11 , wherein the stored instructions that cause the at least one of the one or more processors to move the area operator definition instruction statement within the data dependent branch further cause at least one of the one or more processors to:

identify, within the one or more data dependent branches, an area operator least common dominator (“LCD”) block representative of the least common dominator of all area operator use instruction statements; and

move the area operator definition instruction statement within the area operator LCD block.

13. The memory of claim 12 , wherein the memory further comprises stored instructions such that when executed, cause at least one of the one or more processors to:

identify, outside the one or more data dependent control flow structures, at least one source instruction statement having a resultant that is needed to compute the area operator definition instruction statement; and

create a source instruction block within one of the one or more data dependent branches such that the source instruction block precedes the area operator LCD block and contains data representing one or more of:

the at least one source instruction statement; and

at least one symbolic memory location statement allocated to store the resultant of the at least one source instruction statement.

14. The memory of claim 13 , wherein the memory further comprises stored instructions such that when executed, cause at least one of the one or more processors to:

identify a first path, from an entry block to an exit block within the data representing the control flow information, that includes the area operator LCD block;

identify at least one alternate path, from the entry block to the exit block, that does not include the area operator LCD block;

identify a common computation instruction block for all alternate paths where the common computation instruction block is located where each alternate path first intersects the first path; and

for each alternate path, add one mirror block such that each mirror block immediately precedes the corresponding common computation instruction block wherein each mirror block contains data representing one or more of:

at least one of a source instruction statement having a resultant that is needed to compute the area operator definition instruction statement; and

at least one of a symbolic memory location statement allocated to store the resultant of the source instruction statement.

15. The method of claim 14 , wherein the memory further comprises stored instructions such that when executed, cause at least one of the one or more processors to:

determine, for each block in the data representing the control flow information, live memory location information representing symbolic memory locations that may be needed at any subsequent point within the data representing the control flow information;

wherein, for each non-mirror block, the live memory location information corresponds to data representing at least one symbolic memory location allocated to store at least one resultant that might be used as an operand in at least one statement on a path from the non-mirror block to an exit block of the data representing the control flow information; and

wherein, for each mirror block, the live memory location information corresponds to one or more of:

data provided as live memory location information for the source instruction block; and

data representing the at least one symbolic memory location statement allocated to store the resultant of the at least one source instruction statement if contained in the source instruction block.

16. The memory of claim 15 , wherein the memory further comprises stored instructions such that when executed, cause at least one of the one or more processors to:

translate the data representing the control flow information into data representing a shader program; and

wherein translating the data representing the control flow information into data representing the shader program includes marking each instruction statement contained in the source instruction block to execute for each pixel in a grid whenever at least one pixel in the grid executes the area operator definition instruction statement.

17. An apparatus comprising:

one or more processors coupled to memory that contains stored instructions such that when executed by at least one of the one or more processors, cause at least one of the one or more processors to:

identify, within data representing control flow information that includes one or more blocks of statements and one or more data dependent control flow structures each including one or more data dependent branches each branch including one or more blocks of statements, an area operator definition instruction statement located outside the one or more data dependent control flow structures where the area operator definition instruction statement includes a resultant and at least one operand;

identify, within one of the one or more data dependent branches, at least one area operator use instruction statement having the resultant of the area operator definition instruction statement as an operand; and

move the area operator definition instruction statement within the data dependent branch.

18. The apparatus of claim 17 , wherein the stored instructions that cause the at least one of the one or more processors to move the area operator definition instruction statement within the data dependent branch further cause at least one of the one or more processors to:

identify, within the one or more data dependent branches, an area operator least common dominator (“LCD”) block representative of the least common dominator of all area operator use instruction statements; and

move the area operator definition instruction statement within the area operator LCD block.

19. The apparatus of claim 18 , wherein the memory further comprises stored instructions such that when executed, cause at lest one of the one or more processors to:

identify, outside the one or more data dependent control flow structures, at least one source instruction statement having a resultant that is needed to compute the area operator definition instruction statement; and

create a source instruction block within the one of the one or more data dependent branches such that the source instruction block precedes the area operator LCD block and contains data representing one or more of:

the at least one source instruction statement; and

at least one symbolic memory location statement allocated to store the resultant of the at least one source instruction statement.

20. The apparatus of claim 19 , wherein the memory further comprises stored instructions such that when executed, cause at least one of the one or more processors to:

identify a first path, from an entry block to an exit block within the data representing the control flow information, that includes the area operator LCD block;

identify at least one alternate path, from the entry block to the exit block, that does not include the area operator LCD block;

identify a common computation instruction block for all alternate paths where the common computation instruction block is located where each alternate path first intersects the first path; and

for each alternate path, add one mirror block such that each mirror block immediately precedes the corresponding common computation instruction block wherein each mirror block contains data representing one or more of:

at least one of a source instruction statement having a resultant that is needed to compute the area operator definition instruction statement; and

at least one of a symbolic memory location statement allocated to store the resultant of the source instruction statement.

21. The apparatus of claim 20 , wherein the memory further comprises stored instructions such that when executed, cause at least one of the one or more processors to:

determine, for each block in the data representing the control flow information, live memory location information representing symbolic memory locations that may be needed at any subsequent point within the data representing the control flow information;

wherein, for each non-mirror block, the live memory location information corresponds to data representing at least one symbolic memory location allocated to store at least one resultant that might be used as an operand in at least one statement on a path from the non-mirror block to an exit block of the data representing the control flow information; and

wherein, for each mirror block, the live memory location information corresponds to one or more of:

data provided as live memory location information for the source instruction block; and

data representing the at least one symbolic memory location statement allocated to store the resultant of the at least one source instruction statement if contained in the source instruction block.

22. The apparatus of claim 17 , wherein the memory further comprises stored instructions such that when executed, cause at least one of the one or more processors to provide at least one shading operation on a plurality of pixels based on the control flow information.

23. The apparatus of claim 17 , wherein the memory further comprises stored instructions such that when executed, cause at least one of the one or more processors to:

translate the data representing the control flow information into data representing a shader program; and

wherein translating the data representing the control flow information into data representing the shader program includes marking each instruction statement contained in the source instruction block to execute for each pixel in a grid whenever at least one pixel in the grid executes the area operator definition instruction statement.