Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1997-09-24
2001-06-12
Courtenay, III, St. John (Department: 2151)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
Reexamination Certificate
active
06247173
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to systems and methods for compiler optimizers for computers. More particularly, the present invention relates to lowering the overhead of determining data dependence analysis information after applying the compiler optimization loop unrolling.
BACKGROUND OF THE INVENTION
Many computers have been designed to execute instructions which are independent of other instructions in a parallel rather than a serial fashion. The decision regarding whether an instruction is independent and a candidate for parallel execution can be made by a computer compiler when source code is compiled, and is a type of compiler optimization.
Another type of compiler optimization comprises data dependence analysis and the determination of computer memory location candidates for redundant load instruction elimination. Re-loading information from memory into a computer register which has previously been loaded by a compiled program is considered a redundant load instruction which wastes computer resources. When the target of a load instruction is the same as a previous store or load instruction, a compiler will attempt to eliminate this redundant load instruction to yield more efficient code. However, determining whether two load instructions access the same memory location is a complicated process.
Dependence analysis is a compiler technology used to determine whether two memory references in a loop access the same memory location, even across loop iterations. That is, dependence analysis is used to determine whether a subsequent register load action will access the same location that was stored on a previous loop iteration. The data dependence phase of compiler optimization also allows independent memory operations to be scheduled concurrently by methods such as pipeline scheduling to exploit instruction level parallelism, while exactly dependent or possibly dependent memory references must continue to be executed in instruction order. The data dependence analysis phase is sometimes termed memory disambiguation. The process of data dependence testing often requires extensive analysis of pairs of memory references in a loop, and is a very large and computer resource intensive solution to apply to the problem of memory disambiguation.
Loop unrolling may be produced by a method of replicating a loop during the process of compilation. Data dependence distance is related to the number of loop iterations and is always an integer value. More particularly, data dependence distance for a dependent memory reference pair is the number of loop iterations required for a second memory reference to reach the same memory reference location as the first memory reference previously accessed. Loop carried dependence occurs when the data dependence distance is greater than zero and therefore, at least one loop iteration is required to reach the distance between two exactly dependent memory references. One of the results of loop unrolling is the reduction of loop carried data dependence across loop iterations. While compiler optimizers may be optionally enhanced by the use of data dependence analysis with loop unrolling, data dependence analysis on an unrolled loop adds significant computer resource overhead to the compiler optimization process.
It should be evident that the current solution to compiler optimization analysis of repetitive loop instructions to determine if the memory reference is independent requires a great deal of computer resources. The large amount of memory references which result from loop unrolling only exacerbates the general problem related to the optimizer overhead involved in data dependence analysis. Current loop unrolling compiler optimizers can create efficient code but at the same time use significant computer resources to process optimization techniques on an unrolled loop which has become larger than the original loop. The opportunities for optimizing computer code for pipeline scheduling to take full advantage of powerful computer hardware and for reduction of register loads have not been fully realized due to the expense associated with data dependence analysis and loop unrolling.
SUMMARY OF THE INVENTION
The present invention may be implemented as part of an optimizing compiler in a novel way by combining data dependence analysis with loop unrolling to determine whether pipeline scheduling of independent memory references is possible or whether re-use of dependent memory references to reduce redundant load instructions is possible. The present invention does not require the typical extensive amount of compiler analysis and computer resources to perform data dependence analysis on an unrolled loop. Data dependence analysis for the pre-loop unrolled memory references is determined using techniques well known to those skilled in the art and includes tests such as the Fourier-Motzkin Test, the Bannerjee Test, the Equals Slope Test, and the GCD Test.
The present invention determines more quickly than in the past whether a pair of memory references in an unrolled loop are exactly dependent and if they are dependent, the precise data dependence distance between the two memory references. As previously discussed, determining the precise distance between data dependent memory references not only facilitates re-use of the memory reference but also refines the information available for further data dependence analysis. After loop unrolling, the present invention may assign one of two states, either independent or exactly dependent, to any memory reference pair which was exactly dependent before loop unrolling. Further, after the loop is unrolled the present invention assigns an independent state for any two memory references which were independent before the loop unrolled, thus eliminating further data dependence analysis for the previously independent memory reference pair.
When the pre-loop unrolled memory reference pair is exactly dependent, the preferred embodiment of the invention quickly determines the distance between the post-loop unrolled memory reference pair by an elegant method of using easily accessible values based on previously determined calculations from the pre-loop unrolled memory reference pair. Due to loop unrolling, a pair of memory references that was originally data dependent with a precise dependence distance is translated into many pairs of memory references. The present invention may be implemented by tagging as related the many post-loop unrolled memory reference pairs which are related to the same pre-loop unrolled memory reference pair. Further, the present invention may take advantage of the data dependence distance of any pre-loop unrolled exactly dependent memory reference pair to quickly translate the data dependence distance for any related post-loop unrolled memory reference pair having an exactly dependent state.
The present invention establishes for related, post-loop unrolled memory reference pairs, that only one memory reference pair exists which is exactly dependent and has an integral data dependence distance which is greater than zero. When the one distance which is an integer greater than zero is determined, no further data dependence analysis is required for any of the post-loop unrolled memory reference pairs which were tagged as related to the same pre-loop unrolled memory reference pair, since all other memory reference pairs related to the same pre-loop unrolled memory reference pair will be independent. This reduces the computer resources required for analysis after loop unrolling.
The quick recognition of whether two memory references are exactly dependent or independent after loop unrolling, the method of quick determination of exact dependence distances after loop unrolling, and the elimination of further analysis of a group of related memory reference pairs when an exactly dependent memory reference pair is located, all simplify the previous methods of data dependence analysis after loop unrolling.
Upon the determination of the one distance which is an integer greater than zero for an exactly
Courtenay III St. John
Hewlett--Packard Company
Opie George
Smith Christine H.
LandOfFree
Computer compiler optimizer for reducing computer resource... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Computer compiler optimizer for reducing computer resource..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computer compiler optimizer for reducing computer resource... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2443373