Method for unrolling two-deep loops with convex bounds and imperfectly nested code, and for unrolling arbitrarily deep nests with constant bounds and imperfectly nested code

[0002] The present invention pertains to a method for optimizing source code by a compiler so that the resulting compiled code can be run much faster. More particularly, the present invention relates to a method for unrolling two-deep loops with convex bounds and imperfectly nested code, and for unrolling arbitrarily deep nests with constant bounds and imperfectly nested code.

[0003] Computers are being used today to perform a wide variety of tasks. Many different areas of business, industry, government, education, entertainment, and most recently, the home, are tapping into the enormous and rapidly growing list of applications developed for today's increasingly powerful computer devices. Computers have also become a key technology for communicating ideas, data, and trends between and among business professionals. These devices have become so useful and ubiquitous, it would be hard to imagine today's society functioning without them.

[0004] Computers operate by executing programs, or a series of instructions stored in its memory. These programs, and their series of instructions, are collectively referred to as software. Software is key to utility of computers. Software is what makes the computer devices function and perform useful tasks. Efficient software makes for effective machines, whereas inefficient software makes for difficult to use, less effective, slower machines. Thus, the utility of the computer device often hinges upon the quality of the software written for the device.

[0005] Initially, software is crafted by professionals referred to as programmers or software engineers. As programs have become larger and more complex, the task of writing software has become correspondingly more difficult. As a result, programmers typically code in “high level languages” to improve productivity. The use of high level language makes the task of writing extremely long and complex programs more manageable. The completed program, however, must eventually be translated into machine executable language in order to run on a computer. The process of translating the program written in high level language into a program written in machine language is referred to as compiling. The actual translation is performed by a software program referred to as a compiler. Programmers rely upon compilers to translate their programs which are written in high level language (e.g., Basic, Fortran, C++, Pascal, etc.) into a program comprised of machine executable code, known as “machine language.”

[0006] Basically, the compiler operates on the program written in high level language. The high level language program is referred to as source code. The compiler translates the source code into machine executable code. Ultimately, it is the machine executable code which will run on the computer. The speed and reliability of the executable code depends upon the sophistication of the compiler, i.e. how it “optimizes”. If the compiler is unsophisticated, the size of the executable code will be larger than necessary. Worse, execution speed and reliability, may also be affected. Hence, it is critical to the speed and efficiency of the program that the compiler thoroughly optimize the executable code during the translation process.

[0007] There are several different methods and techniques used to optimize source code for scientific applications, loop interchange, cache tiling or blocking, etc. The present invention pertains to an improved variation for performing an optimization technique commonly referred to as “unroll and jam.” With the prior art technique, perfectly nested loop nests with constant loop bounds in source code can be compiled more efficiently. A “loop” refers to a sequence of steps which is repeated over and over again until a condition is satisfied. Often, source code contains nested loops whereby an inner loop is executed as part of the sequence of steps within an outer loop. Nested loops, under certain circumstances, may be “unrolled and jammed” such that it produces an equivalent result, yet the total number of load or store operations is reduced. Load and store operations are costly because it takes a relatively long period of time to load and store data into the appropriate registers. Consequently, reducing the number of load and store operations increases the speed at which a compiled code can run.

[0008] An example is now offered to demonstrate the prior art unroll and jam operation. The following source code shows a two-deep perfectly nested loop:

[0009] Each time through the inner “DO” loop, the same a(i) variable is used, but a different b(j) must be loaded. Hence, a separate load operation must be performed each time the statement “a(i)=a(i)+b(j)” is executed. The outer loop can be unrolled as follows:

[0010] By unrolling the “i” loop once, the same result is achieved. The difference is that the “i” loop is now stepping by two. Note that the unrolling process described above does not result in any changes to the statements. All statements are executed in the same order as before: (1,1), (1,2), . . . (1,N), (2,1), (2,2), . . . (2,N). The purpose for unrolling the source code is to prepare it for the jamming process. It should be noted that stepping by two poses a couple of problems. First, it must be ensured that the unrolled code does not overshoot and perform an extra step. Hence, one is subtracted from the upper bounds (N1−i). Second, there must be a mechanism for handling the case if N1 is odd. This is accomplished by implementing a wind-down loop. The wind-down loop executes the last step in case N1 is odd.

[0011] After unrolling, the source code is optimized by applying a “jamming” procedure. Jamming as applied to the above example produces the following code:

[0012] By jamming the two “j” loops into a single loop, the computation has been changed. Instead of performing (1,1), (1,2), . . . , (1,N), (2,1), (2,2), . . . (2,N); the new process runs (1,1), (2,1), (1,2), (2,2), (3,1), (3,2), etc. Now, b(1) which was used by both (1,1) and (2,1), no longer has to wait for the N iterations of “j” to happen. It can be loaded for (1,1) and used without having to be reloaded for (2,1). This is due to the fact that (1,1) and (2,1) occur one right after the other. Hence, jamming effectively reduces the total number of loads. In effect, the jamming procedure combines the unrolled loops. As a result, the unrolled and jammed version runs much faster than the original source code.

[0013] However, prior art unroll and jam procedures are limited to code having both constant loop bounds and whose loops also happen to be perfectly nested as well. Both of these are very strong restrictions. First non-constant loop boundaries (e.g. in the above example, if the loop bounds for the j loop had depended on i) are frequently found in source code. Second, it is very common for these to be statements nested in the outer loop, but not loops further in.

[0014] Thus, there is a need in the prior art for a compiler that can unroll and jam the more general case of source code having variable loop boundaries and non-perfectly nested statements. The present invention provides an elegant solution to these problems in important cases by implementing an “outer loop unrolling” process. With the present invention, source code which normally cannot be unrolled and jammed, can now be optimized by an outer loop unrolling process to reduce the total number of load and store operations. Specifically, in the case of doubly nested loops (i.e., 2D loop nests), both restrictions are relaxed. In other words, the code may be imperfectly nested with loop bounds of any linear convex configuration, and be outer unrolled. Since two-deep nests are by far the more common case and since it is extremely common that bounds are not constant but are linear convex, the present invention offers a very important extension to prior art optimization techniques. Furthermore, this present invention can be applied to loop nests of any depth with constant bounds, and, unlike with the prior art, the loop nest need not be perfectly nested. Since loop nests are typically not perfectly nested, this also is a very significant extension to the prior art.

[0015] The present invention pertains to a compiler for compiling source code whereby the compiled source code is optimized by performing unroll and jam on selected loop nests. The present invention allows any arbitrarily deep loop nests with constant bounds to be properly unrolled, even those loop nests having imperfectly nested code. This is accomplished by transforming the code into multiple loops. In the transformed code, the imperfect code is isolated in one of the loops while the other loops are placed in a condition such that a conventional unroll and jam operation may be applied. For three-deep or greater loop nests, the process is repeated recursively from the outer-most loop.

[0016] The present invention also allows outer loop unrolling for two-deep loop nests not only with imperfectly nested code, but also with convex bounds. This is accomplished by identifying strips of code which do not contain imperfectly nested code. An unroll and jam operation is executed for the identified strips. Code falling outside of the identified strips as well as wind-down code, are executed according to their original untransformed order.

[0017] The present invention is illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings and in which like reference numerals refer to similar elements and in which:

[0018] FIG. 1 is a flowchart describing the steps for outer loop unrolling any two-deep loop with constant bounds, even those having imperfect code.

[0019] FIG. 2 is a flowchart describing the steps for outer loop unrolling any depth nest with constant bounds, even those having imperfect code.

[0020] FIG. 3 shows a graph of the iteration space corresponding to a nested loop that has non-constant bounds.

[0021] FIG. 4 shows an exemplary computer system upon which the present invention may be practiced.

[0022] A method for unrolling convex and non-perfectly looped nests for use in a compiler is described. In the following description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be obvious, however, to one skilled in the art that the present invention may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form in order to avoid obscuring the present invention.

[0023] The present invention pertains to a method for performing a generalization of unroll and jam that we call outer loop unrolling. Outer loop unrolling improves the performance of software by reducing the number of requisite load and store operations. The present invention is capable of unrolling outer loops, even when the nest is not perfectly nested and. for two deep nests, even when the bounds are non-constant as well too deep. The compiler of the present invention is especially effective on scientific code (e.g., code having loops with array references).

[0024] The first aspect of the present invention pertaining to the optimization of source code having constant bounds and imperfect code is now described. Imperfect code pertains to a statement which is does not reside within both of the loops. The following imperfect code is offered as an example:

[0025] It can be seen that the c(i)=c(i)+3 statement resides within the outer “i” loop, but falls outside the inner “j” loop. The imperfect code can be thought of as having executed in the first iteration of “j.” The above code was not written in this way, but if it had been, it would have given the same result:

[0026] If the tiling dependence conditions are met on this nest, then it is perfectly legal to rewrite the code as:

[0027] Rearranging this code produces:

[0028] It can be seen that the second loop nest has constant bounds and is also perfectly nested. The second loop nest is referred to as a “synchronized” loop. Using the prior art, it is in proper condition to be jammed. Thus, the present invention has successfully unrolled and jammed this nonperfectly nested loop by transforming it into a perfectly nested loop and then jamming.

[0029] The example given above can be applied to any general case as follows. Any code of the form:

[0030] may be replaced by:

[0031] so long as N3 is less than or equal to N4. This condition can be verified or tested during runtime to ensure proper compliance.

[0032] The above description describes the entire algorithm for unrolling an imperfectly nested 2D loop with constant bounds when the imperfect code is above the second nest. If the imperfect code is below the second nest, the transformation is analogous. However, if there exist imperfect code both above and below the nest:

[0033] it can be replaced with the following code:

[0034] The middle of these three loop nests, which typically contains the majority of the computation, may now be properly unrolled and jammed using the prior art. Thus, the present invention grants the compiler the capability to outer loop unroll any 2D loop with constant bounds, even if the code is imperfectly nested.

[0035] FIG. 1 is a flowchart describing the steps for outer loop unrolling any code identified to be a two-deep loop with constant bounds and imperfect code. If such a case is encountered during the compilation process, the compiler checks to determine whether there exist any imperfect code, step 101. Imperfect code include any statement which does not reside within both of the loops. If there are no imperfect code, the compiler simply performs a standard unroll and jam operation, step 108. However, if there exist imperfect code, the entire loop nest is transformed. If the imperfect code is above the second nest only, step 102, then it is transformed into a single loop followed by a 2D loop nest with perfect code according to step 103. If the imperfect code only exists below the second nest as determined by step 104, then the code is transformed into a 2-D loop nest with perfect code followed by a single loop nest, step 105. Step 106 represents the case whereupon the imperfect code is found both above and below the second nest. In this case, the code is transformed into a 2-D loop nest with perfect code which is straddled by single loop nests, step 107. In step 108, the 2-D loop nest with perfectly nested statements is unrolled and jammed.

[0036] The above description discloses how the present invention accomplishes unroll and jam for any two deep loop with constant bounds, even if imperfectly nested. Now, this technique is extended to cover any nest depth greater than two, even if imperfectly nested, so long as the bounds are constant. To do this, however, requires applying the above technique recursively. The following three-deep example is now offered for purposes of explanation:

[0037] First, the same technique as described above is applied to the outermost two loops. That is, everything inside the “j” loop is treated as a single unit. So, applying the example above to loops “i” and “j” below yields:

[0038] One can now apply a slightly unusual version of unroll-and-jam to the “i” loop, which is legal so long as tiling is legal. Let us illustrate with outer unrolling the i loop only once:

[0039] Now the inner two loops of the (i, j, k) nest (i.e., the “j” and “k” loops) are imperfect with constant bounds. This can be outer loop unrolled with the technique already described above. And it already contains two iterations of the “i” loop. Thus, one can apply the same technique to that loop, completing the unrolling and achieving the goal of outer loop unrolling both the “i” and “j” loops. To finish the example, given below is the complete code:

[0040] The entire algorithm works as follows. Given a loop nest, imperfectly nested but with constant bounds, first, from the outside in, optimize as follows. Without loss of generality, every loop nest is of the form:

[0041] where the S(i, j) actually may contain loops further in. In each of these cases, according to the previous discussion, the exact code to outer unroll is known. Second, there may be wind-up and/or wind-down loops. Do not optimize those. Instead, consider only the single remaining non-wind-up non-wind-down loop. Thirdly, if that nest has two or more perfectly nested or non-perfectly nested loops inside it, optimize using the same technique. This algorithm has been illustrated already on the three-deep example given above.

[0042] FIG. 2 is a flowchart describing the steps for optimizing any depth nest with constant bounds, even those having imperfect code. When identified, the outermost loop is outer loop unrolled in a manner as described in FIG. 1, step 201. This process is exited if there is no two deep or greater loop nest residing within the current outer loop nest, step 202. Otherwise, the process is repeated with loops further in, step 203.

[0043] Another aspect of the present invention pertaining to practicing outer loop unrolling for linear convex bounds and two deep nests is now described. Linear convex implies that for a loop in the form:

[0044] L(i) can be any linear function of “i” or the MAX of any of those; and U(i) may be any linear function of “i” or the MIN of those. The following nested loop illustrates the general case of non-constant bounds:

[0045] Suppose that the above nested loop has non-constant bounds according to the iteration space graph shown in FIG. 3. The convex polyhedron 401 indicates which nodes are executed. More specifically, the white nodes are not executed. The crosses represent the execution of S1 and/or S2 in addition to S. The black nodes just execute S. Although tiling formulas may be used to construct the loop bounds, this approach does not tell us when the blocksize is maximal (i.e., when unrolling can be performed) and thus is useless for outer loop unrolling. Instead, the present invention traverses the iteration space according to appropriate patterns such that the unrolling scheme is always known. Unrolling is legal as long as S(i,j) is executed before S(i+1,j) and S(i,j) is executed before S(i,j+1); and provided that the imperfectly nest portions are executed with the corresponding first iteration. In addition, it must be ensured that Lj(i)<=Uj(i) for all “i” in [Li,Ui]. The goal then is to demonstrate an ordering that obeys the constraint that S(i,j) executes before both S(i,j+1) and S(i+1,j); that is such that imperfect code is executed with the corresponding first iteration of the next inner loop; and is such that it is easy to know when exactly B iterations of the outer loop (where B is the amount to unroll) are available, so that amount can be unrolled.

[0046] In this case, the inner loop is the “j” loop, with multiple “i” iteration at a time in that particular loop.

[0047] Note that in the top line of this code, the “i” loop is stepped through by B, which is the amount that unrolling is being attempted. Note that B is not a variable; it is a number chosen by the compiler (e.g., 2 or 3). At this point, it is not known whether outer unroll can even be accomplished or not. But the algorithm attempts to execute i=Li through i=Li+B−1 in an unrolled fashion. Then, the next iteration of the loop is tried: i=Li+B to i=Li+2B−1, etc.

[0048] Next, based on the code, L* is made to be the smallest iteration of “i” that has no imperfect code. This is due to the observation that imperfect code can only occur on a boundary. The code has made L* bigger than the entire left-hand edge. Likewise, for U*, it is smaller than the entire right-hand edge. Hence, if L*<=U*, then there is some range of “i” that has no imperfect code. The IF condition in the code testes whether there exists any range of “i” where there is no imperfect code. If so, then “j” is constant in that region, and unroll and jam is performed for that particular portion of the code. This is referred to as the “large strip execution.”

[0049] However, there may be instances in the code where there is some imperfect code for “i” between “i” and i+B−1. When this situation is encountered, the code is not unrolled at all. Instead, the code is simply executed in some legal way, known as “small strip execution.” The small strips are executed without tiling as follows. The small strips are executed in the same order that corresponds to their original, untransformed program. This is analogous to the wind-down code. The code is executed as it was originally written.

[0050] For, the large strips, unrolling is performed between L* and U*. Before L* and after U*, the loop is run without unrolling. In other words, the following loop is generated only if L**<L*. The point is that the code between L* and U* may be unrolled, but L* is not necessarily the smallest value of “j.” All the smaller “j's” are executed in the original program order.

[0051] In summary, chunks of “i” code are executed B size at a time. If there is a region of “j's” that do not have boundaries, they are isolated in a rectangular region and executed unrolled. All other code is executed in the normal order. Hence, with the present invention, all two-deep integer non-degenerate convex loops can be unrolled, subject to dependence constraints. By utilizing the transformation technique according to the present invention, compilers may now unroll a far larger class of loop nests. In fact, an extremely broad range of loops, by far all the important common cases (e.g., any two-deep loop with any convex bounds, and any deeper nest with non-varying bound, even if imperfectly nested) may now be outer loop unrolled.

[0052] To summarize, the most general two-deep loop is:

[0053] Simplifications arise if there is no S1(i) or S3(i). Likewise, simplifications arise if L(i), U(i), or both are constant. However, without these simplifications, the code given below results in outer unrolled loops.

[0054] Referring to FIG. 4, an exemplary computer system 412 upon which the present invention may be practiced is shown. It is appreciated that the computer system 412 of FIG. 4 is exemplary only and that the present invention can operate within a number of different computer systems including general purpose computers, embedded computes, portable computers, and computer systems specially adapted for graphics display. Computer system 412 of FIG. 4 includes an address/data bus 400 for communicating information between the various components. A central processor unit 401 is coupled to the bus 400. It is used for processing information and instructions. Also coupled to bus 400 is a random access memory 402 (e.g., DRAM) for storing information and instructions for the central processor 401. A small cache memory 409 resides within microprocessor 401. Processor 401 reads data from and writes data to cache 409. Occasionally, data from main memory 402 is loaded into cache 409 and the main memory 402 is updated with the most recent data from cache 409. A read only memory (ROM) 403 is used for storing semi-permanent information and instructions for the processor 401. The compiler may be stored within ROM 403. For storing vast amounts of data, a data storage device 404 (e.g., a magnetic or optical disk and disk drive) is coupled to bus 400. Finally, an I/O unit 408 is used to interface the computer system 412 with external devices (e.g., keyboard, modem, network interface, display, mouse, etc.). Externally, a display device 405 is coupled to bus 400 for displaying information (e.g., graphics, text, spreadsheets, etc.) to a computer user. An alphanumeric input device 406 (e.g., a keyboards is used for communicating information and command selections to the central processor 401. Optionally, a cursor control device 407 (e.g., a mouse, trackball, etc.) is used for communicating user input information and command selections to the central processor 401.

[0055] The foregoing descriptions of specific embodiments of the present invention have been presented for purposes of illustration and description. They are not intended to be exhaustive or to limit the invention to the precise forms disclosed, and obviously many modifications and variations are possible in light of the above teaching. The embodiments were chosen and described in order to best explain the principles of the invention and its practical application, to thereby enable others skilled in the art to best utilize the invention and various embodiments with various modifications as are suited to the particular use contemplated. It is intended that the scope of the invention be defined by the Claims appended hereto and their equivalents.