Abstract:
One embodiment of the present invention provides a system that facilitates multi-versioning loops to facilitate modulo scheduling. Upon receiving a computer program, the system analyzes the code to locate loops within the program. When a loop is located, the system examines the loop termination condition to determine if it is based on a “not-equal-to” condition that makes it hard to determine beforehand whether the loop will terminate. If the loop termination condition is based on a “not-equal-to” condition, the system creates multiple versions of the loop, at least one of which will terminate and can be modulo scheduled, and at least one of which might be an infinite loop and consequently cannot be modulo scheduled.

Description:
BACKGROUND 
   1. Field of the Invention 
   The present invention relates to compilers for computer systems. More specifically, the present invention relates to a method and an apparatus for creating multiple versions of loops to facilitate modulo scheduling. 
   2. Related Art 
   The latest generation of processors are able to execute multiple instructions simultaneously. However, compilers need to arrange executable code to take advantage of this parallel processing capability. Modulo scheduling is one such way in which compilers can arrange code to perform as many instructions as possible in each clock cycle. 
   Many computationally intensive applications spend the bulk of their time executing loops. Modulo scheduling extracts instruction-level parallelism in loops, and can thereby significantly increase the execution speed of a program. Hence, in order to maximize system performance, it is important that a compiler be able to modulo schedule as many loops as possible. 
   There are many different types of loops, and it may not be possible to modulo schedule all of them. In order to modulo schedule a loop, it is important that the loop be in a form such that the number of iterations of the loop be determined before the loop is executed. If the loop has a termination condition that is based on a “not-equal-to” test, then it may not be possible to determine the trip count of the loop because the loop might be an infinite loop. 
   In order to modulo schedule the loop, the loop has to be transformed into a form which allows the trip count of the loop to be determined before the loop is executed. Note that if the loop counter gets incremented or decremented by one, then the loop can be trivially transformed into a loop with a less than or greater than test. 
   What is needed is a method and apparatus for transforming loops that cannot be modulo scheduled, such as loops with a “not-equal-to” test, into a form that allows them to be modulo scheduled. 
   SUMMARY 
   One embodiment of the present invention provides a system that facilitates multi-versioning loops to facilitate modulo scheduling. Upon receiving a computer program, the system analyzes the code to locate loops within the program. When a loop is located, the system examines the loop termination condition to determine if it is based on a “not-equal-to” condition that makes it hard to determine beforehand whether the loop will terminate. If the loop termination condition is based on a “not-equal-to” condition, the system creates multiple versions of the loop, at least one of which will terminate and can be modulo scheduled, and at least one of which might be an infinite loop and consequently cannot be modulo scheduled. 
   In a variation on this embodiment, the system creates multiple versions of the loop by modifying the loop termination condition to be a “greater-than” condition, whereby the resulting loop can be modulo scheduled. 
   In a variation on this embodiment, the system creates multiple versions of the loop by modifying the loop termination condition to be a “less-than” condition, whereby the resulting loop can be modulo scheduled. 
   In a variation on this embodiment, the system generates code that causes a selected version of the loop to execute at run time based on the loop parameters, wherein the loop parameters include at least one of, the initial value, the final value, and the increment value. 
   In a variation on this embodiment, if the initial value, final value, and increment value are known, the system generates a single version of the loop which can be modulo scheduled. 
   In a variation on this embodiment, the system creates the multiple versions of the loop in the front end of a compiler. 
   In a variation on this embodiment, the system creates the multiple versions of the loop within an intermediate language optimizer within a compiler. 
   In a variation on this embodiment, the system creates the multiple versions of the loop in a code generator within a compiler. 

   
     BRIEF DESCRIPTION OF THE FIGURES 
       FIG. 1  illustrates a computer system in accordance with an embodiment of the present invention. 
       FIG. 2  illustrates the structure of a compiler in accordance with an embodiment of the present invention. 
       FIG. 3  illustrates the process of loop optimization in accordance with an embodiment of the present invention. 
       FIG. 4  illustrates the process of generating multiple versions of a loop in accordance with an embodiment of the present invention. 
       FIG. 5  illustrates the process of executing the appropriate version of the loop in accordance with an embodiment of the present invention. 
   

   DETAILED DESCRIPTION 
   The following description is presented to enable any person skilled in the art to make and use the invention, and is provided in the context of a particular application and its requirements. Various modifications to the disclosed embodiments will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the present invention. Thus, the present invention is not intended to be limited to the embodiments shown, but is to be accorded the widest scope consistent with the principles and features disclosed herein. 
   The data structures and code described in this detailed description are typically stored on a computer readable storage medium, which may be any device or medium that can store code and/or data for use by a computer system. This includes, but is not limited to, magnetic and optical storage devices such as disk drives, magnetic tape, CDs (compact discs) and DVDs (digital versatile discs or digital video discs), and computer instruction signals embodied in a transmission medium (with or without a carrier wave upon which the signals are modulated). For example, the transmission medium may include a communications network, such as the Internet. 
   Computer System 
     FIG. 1  illustrates a computer system  100  in accordance with an embodiment of the present invention. As illustrated in  FIG. 1 , computer system  100  includes processor  102 , which is coupled to a memory  112  and to peripheral bus  110  through bridge  106 . Bridge  106  can generally include any type of circuitry for coupling components of computer system  100  together. 
   Processor  102  can include any type of processor, including, but not limited to, a microprocessor, a mainframe computer, a digital signal processor, a personal organizer, a device controller and a computational engine within an appliance. Processor  102  includes a cache  104  that stores code and data for execution by processor  102 . 
   Processor  102  communicates with storage device  108  through bridge  106  and peripheral bus  110 . Storage device  108  can include any type of non-volatile storage device that can be coupled to a computer system. This includes, but is not limited to, magnetic, optical, and magneto-optical storage devices, as well as storage devices based on flash memory and/or battery-backed up memory. 
   Processor  102  communicates with memory  112  through bridge  106 . Memory  112  can include any type of memory that can store code and data for execution by processor  102 . 
   As illustrated in  FIG. 1 , memory  112  contains compiler  116 . Compiler  116  converts source code  114  into executable code  118 . In doing so, compiler  116  creates multiple versions of loops with a “not-equal-to” termination conditions to facilitate modulo scheduling, and inserts the multiple versions into executable code  118  as is described in more detail below with reference to  FIGS. 2–5 . 
   Note that although the present invention is described in the context of computer system  100  illustrated in  FIG. 1 , the present invention can generally operate on any type of computing device. Hence, the present invention is not limited to the specific computer system  100  illustrated in  FIG. 1 . 
   Compiler 
     FIG. 2  illustrates the structure of compiler  116  in accordance with an embodiment of the present invention. Compiler  116  takes as input source code  114  and outputs executable code  118 . Note that source code  114  may include any computer program written in a high-level programming language, such as the JAVA™ programming language. Executable code  118  includes executable instructions for a specific virtual machine or a specific processor architecture. 
   Compiler  116  includes a number of components, including as front end  202  and back end  206 . Front end  202  takes in source code  114  and parses source code  114  to produce intermediate representation  204 . 
   Intermediate representation  204  feeds into back end  206 , which operates on intermediate representation  204  to produce executable code  118 . During this process, intermediate representation  204  feeds through optimizer  208 , and the resulting optimized intermediate representation  209  is passed to code generator  210 . 
   The process of creating multiple versions of the loop to facilitate modulo scheduling can occur at a number of different places within the system. For example, the system can create multiple versions of the loop in front end  202 , optimizer  208 , or code generator  210 . 
   Process of Loop Optimization 
     FIG. 3  illustrates the process of loop optimization in accordance with an embodiment of the present invention. The system starts by examining the loop (step  300 ) and determining whether the loop contains a single basic block (step  302 ). If the loop contains more than a single basic block, the system schedules the loop to execute without modulo scheduling (step  304 ) because modulo scheduling is only practical for loops containing a single basic block. 
   If the loop contains a single basic block, the system determines if the loop termination condition is a “not-equal-to” condition (step  306 ). If the loop termination condition is not a “not-equal-to” condition, then the system modulo schedules the loop (step  308 ). However, if the loop termination condition is a “not-equal-to” condition, then the system checks if the loop is a simple loop (step  310 ). 
   Note that a simple loop is a loop where the initial value, the final value, and the increment value are known. If all three of these values are known, it can be determined if the loop will terminate, or if the loop is an infinite loop. If one or more of these values is not known, it is impossible to determine if the loop will terminate, or if the loop is an infinite loop. If the loop is a simple loop, then the system checks if the loop is an infinite loop (step  312 ). If so, the system schedules the loop to execute without modulo scheduling (step  314 ) since infinite loops cannot be modulo scheduled. If the loop is not an infinite loop, and hence can be modulo scheduled, then the system modifies the loop termination condition to be a “greater-than” or “less-than” condition (step  316 ) and modulo schedules the loop (step  318 ). 
   In the situation where the loop is not a simple loop, meaning that one or more of the initial value, the final value, and the increment value is not known, the system generates multiple versions of the loop (step  320 ) as illustrated below in  FIG. 4 . 
   Process of Generating Multiple Versions of a Loop 
     FIG. 4  illustrates the process of generating multiple versions of a loop in accordance with an embodiment of the present invention. If one or more of the initial value, the final value, and the increment value is not known, the loop can be optimized by creating multiple versions of the loop, at least one of which can be modulo scheduled, and at least one of which cannot be modulo scheduled. 
   First, the system schedules the original version of the loop without modulo scheduling (step  402 ). This first version of the loop is created for the case where the loop might be infinite, so that the loop cannot be modulo scheduled. Next, the system creates a second version of the loop where the loop termination condition is changed to a “greater-than” condition (step  404 ) and modulo schedules the “greater-than” version of the loop to execute (step  406 ). The system also creates a third version of the loop where the loop termination condition is changed to a “less-than” condition (step  408 ) and modulo schedules the “less-than” version of the loop to execute (step  410 ). 
   After the multiple versions of the loop have been created, the system generates the code to execute a selected version of the loop at runtime based on l, m, and n, or the initial value, the final value, and the increment value respectively (step  412 ). 
   Note that in some situations where some, but not all, of the values of l, m, and n are known, the system might generate only two versions of the loop where one is the original loop. For instance, if the initial value l and the final value m are known, but the increment value n is unknown, and l is less than m, then the system can produce two versions of the loop. For the case where n is negative, the loop will not terminate. Hence, the system schedules the original version of the loop without modulo scheduling. For the case where n is positive, the system creates a second version of the loop where the loop termination condition is a “less-than” condition, and modulo schedules the loop. Note that at runtime, if the value of n is found to be positive, the original version of the loop, which is an infinite loop, might still be executed if ((m−l) mod n )≈0 since the termination condition would never be met. 
   Process of Executing the Appropriate Version of the Loop 
     FIG. 5  illustrates the process of executing the selected version of the loop in accordance with an embodiment of the present invention. At runtime, the initial value l, the final value m, and the increment value n of the loop are known, and the system determines which version of the loop to execute. 
   The system determines if n is greater than zero (step  502 ), and if so, checks if l is less than m (step  504 ). If l is not less than m, the loop will not terminate, so the system executes the original version of the loop, which is an infinite loop (step  506 ). If l is less than m, the system checks if (m−l mod n)=0 (step  508 ). If so, the system executes the “less-than” version of the loop (step  510 ). However, if the modulus is not equal to zero, then the system executes the original version of the loop which is an infinite loop (step  506 ). 
   If n is not greater than zero (step  502 ), the system checks if l is greater than m (step  512 ). If l is not greater than m, the loop will not terminate, so the system executes the original version of the loop which is an infinite loop (step  506 ). If l is greater than m, the system checks if (l−m mod n)=0 (step  514 ) and if so, executes the “greater-than” version of the loop (step  516 ). However, if the modulus is not equal to zero, then the system executes the original version of the loop which is an infinite loop (step  506 ). 
   Note that the increment value n is assumed not to be zero. If n is zero, then the loop is an infinite loop and would be executed as such. 
   For example, where the original loop is: 
                                           for(i=1; i!=m; i+=n {             A [i]=0;           }                        
the loop counter is i; the loop counter initial value is l; the loop counter final value is m; the loop test is “not-equal-to”; the loop counter increment is n, and i, l, m, and n are of the integer type. The transformed code with multiple versions might look like:
 
                                           if ((n&gt;0 &amp;&amp; l&lt;m) &amp;&amp; (mod(m−l, n)= =0)) {              for (i=l; i&lt;m; i+=n) {                A[i]=0;              }           } else if ((n&lt;0 &amp;&amp; l&gt;m) &amp;&amp; (mod(l−m, n)= =0)) {              for (i=l; i&gt;m; i+=n) {                A[i]=0;              }           } else {              for(i=l; i!=m; i+=n {                A[i]=0;              }           }                        
In the transformed code, the first two loops, which are the likely case, can potentially be modulo scheduled. The third loop is the original loop itself and is an infinite loop in this instance. In most cases, the value of n is known at compile time and the transformed code would incur the penalty of only one modulus computation. Hence, with only a small overhead, the system is able to optimize loops containing a “not-equal-to” test efficiently.
 
   The foregoing descriptions of embodiments of the present invention have been presented for purposes of illustration and description only. They are not intended to be exhaustive or to limit the present invention to the forms disclosed. Accordingly, many modifications and variations will be apparent to practitioners skilled in the art. Additionally, the above disclosure is not intended to limit the present invention. The scope of the present invention is defined by the appended claims.