Graphic software functions without branch instructions

Abstract

A method for improving the execution speed of compare operations in graphic software functions running on a RISC processor. A branch instruction in a software function comparing the value of two variables is replaced with an inline compare instruction that encodes the result of the compare into a third variable using an arithmetic shift-left instruction. An inline choice instruction selects the value of one of the two variables using the value of the third variable as a mask. The inline compare and an inline choice instructions reduce processor stalls during execution.

What is claimed is: 
     
       1. A method for reducing processor stalls when executing a software function, the function including a plurality of instructions, the method comprising the steps of: encoding a comparison between a first value and a second value in a first instruction, the first instruction providing a result of the comparison, wherein the encoding step includes the step of performing an arithmetic shift instruction; and   using the result of the comparison to indicate if the first and second value are in a predetermined relationship, wherein the comparison in the software function executes sequentially, and wherein the encoding and using steps reduce processor stalls.   
     
     
       2. A method as in claim 1 wherein the encoding step is an inline compare instruction. 
     
     
       3. A method as in claim 2 wherein the encoding step further includes the step of encoding the result of the comparison in a boolean expression. 
     
     
       4. A method as in claim 3 wherein the encoding step includes the step of subtracting the second value from the first value. 
     
     
       5. A method as in claim 1 wherein the first and second values are N bits in length and wherein the step of performing an arithmetic shift instruction comprises a shift-left of N-1 bits. 
     
     
       6. A method as in claim 5 wherein the software function is a binary search. 
     
     
       7. A method as in claim 1 wherein the using step is an inline choice instruction. 
     
     
       8. A method as in claim 7 wherein the predetermined relationship includes the first value being numerically equal, numerically smaller, and numerically larger than the second value. 
     
     
       9. A method as in claim 8 wherein the using step further includes the step of selecting the first value or the second value based on the result of the comparison. 
     
     
       10. A method for improving execution speed of a computer implemented software function, the method comprising: encoding a compare operation between a first variable and a second variable in a first software instruction, the first software instruction providing a result of the comparison;   setting a mask value equal to the result; and   selecting one of the first variable and the second variable based on the value of the mask in a second instruction, the selection being performed via an inline choice, and wherein the steps of encoding, setting, and selecting improve execution speed of a computer.   
     
     
       11. A method as in claim 10 wherein the computer implemented function is a minimum value function. 
     
     
       12. A method as in claim 11 wherein the setting step further includes the step of setting the mask value to select a numerically smaller value of the first variable and the second variable. 
     
     
       13. A method as in claim 10 wherein the computer implemented function is a maximum value function. 
     
     
       14. A method as in claim 13 wherein the setting step further includes the step of setting the mask value to select a numerically larger value of the first variable and the second variable. 
     
     
       15. A method as in claim 10 wherein the encoding step further includes the step of encoding the result of the comparison in a boolean expression. 
     
     
       16. A method as in claim 15 wherein the encoding step further includes the step of performing a boolean AND between the mask and the first variable. 
     
     
       17. A method as in claim 16 wherein the encoding step further includes the step of performing a boolean AND between the mask and the second variable. 
     
     
       18. A computer software method for determining if a first object having a first boundary and a second object having a second boundary are in a predetermined relationship without executing a branch instruction, the method comprising the steps of: encoding a comparison between the first boundary of the first object and the second boundary of the second object using an inline compare, wherein the inline compare provides a result of the comparison;   using the result of the comparison to indicate if the first and second object are in the predetermined relationship; and   filling a buffer in a manner according to the predetermined relationship.   
     
     
       19. A method as in claim 18 wherein the predetermined relationship between the first and second object comprises the first object intersecting the second object. 
     
     
       20. A method as in claim 19 wherein the predetermined relationship between the first and second object comprises the first object containing the second object. 
     
     
       21. A method as in claim 20 wherein the predetermined relationship between the first and second object comprises the first object and the second object overlapping. 
     
     
       22. A computer readable medium containing program instructions for: encoding a comparison between a first value and a second value in a first instruction, the first instruction providing a result of the comparison, wherein the encoding step includes the step of performing an arithmetic shift instruction; and   using the result of the comparison to indicate if the first and second value are in a predetermined relationship, wherein the comparison in the program executes sequentially.   
     
     
       23. A computer readable medium as in claim 22 wherein the encoding instruction is an inline compare instruction. 
     
     
       24. A computer readable medium as in claim 23 wherein the encoding instruction further includes the instruction of encoding the result of the comparison in a boolean expression. 
     
     
       25. A computer readable medium as in claim 24 wherein the encoding instruction includes the instruction of subtracting the second value from the first value. 
     
     
       26. A computer readable medium as in claim 25 wherein the encoding instruction further includes the instruction of performing an arithmetic shift instruction. 
     
     
       27. A computer readable medium as in claim 26 wherein the first and second values are N bits in length and wherein the instruction of performing an arithmetic shift instruction comprises a shift-left of N-1 bits. 
     
     
       28. A computer readable medium as in claim 22 wherein instruction is an inline choice instruction. 
     
     
       29. A computer readable medium as in claim 28 wherein the predetermined relationship includes the first value being numerically equal, numerically smaller, and numerically larger than the second value. 
     
     
       30. A computer readable medium as in claim 29 wherein instruction further includes the instruction of selecting the first value or the second value based on the result of the comparison.