Method and apparatus for optimizing complex control structures using abstract web patterns
First Claim
1. A method of optimizing a selected program segment of a computer program, comprising the steps of:
- generating a first abstract representation of the selected program segment;
comparing the first abstract representation with at least one other abstract representation stored in a memory of a computer system to determine if a match exists between the generated abstract representation and at least one other stored abstract representation, wherein each other abstract representation is associated with an optimized instruction sequence; and
replacing the selected program segment with the optimized instruction sequence associated with a matched one of the at least one stored abstract representation.
4 Assignments
0 Petitions
Accused Products
Abstract
An optimizing compiler for optimizing a computer program. The compiler builds abstract web representations for the code segments of the computer program. The compiler also maintains a library of abstract web patterns. Each abstract pattern in the library represents an optimized sequence of computer instructions. The compiler compares each abstract web generated from the code segments with the abstract web patterns in its library. If any of the abstract webs match, the compiler replaces the original code segment in the computer program with the optimized sequence of instructions corresponding to the matching abstract web pattern. By using the above described technique, the compiler can replace loops with instructions that implicitly iterate. In addition, the compiler can micro-vectorize code segments and remove unnecessary instructions from loops.
32 Citations
19 Claims
-
1. A method of optimizing a selected program segment of a computer program, comprising the steps of:
-
generating a first abstract representation of the selected program segment; comparing the first abstract representation with at least one other abstract representation stored in a memory of a computer system to determine if a match exists between the generated abstract representation and at least one other stored abstract representation, wherein each other abstract representation is associated with an optimized instruction sequence; and replacing the selected program segment with the optimized instruction sequence associated with a matched one of the at least one stored abstract representation. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. An compiler adapted for execution on a computer system having a CPU and a memory, comprising:
-
means, executing on the CPU and stored in the memory, for converting a high-level computer program into low-level code comprised of at least one code segment; means for scanning the low-level code and generating a first abstract representation of the code segment; means for comparing the first abstract representation with at least one other abstract representation stored in the memory, wherein the compared at least one other abstract representation has an associated optimized code segment; and means for replacing the code segment with the optimized code segment corresponding to a matched one in the memory of the at least one other abstract representation. - View Dependent Claims (8, 9, 10, 11, 12, 13)
-
-
14. A computer program product having a computer readable medium having computer program logic recorded thereon for optimizing code segments on a computer system having a processor and a memory, the computer program product comprising:
-
means, executing on the processor, for building a first abstract representation of a code segment; means for comparing the first abstract representation with a second abstract representation stored in the memory, wherein the second abstract representation represents an optimized code segment; means for replacing the code segment with the optimized code segment if the first and second abstract representations match. - View Dependent Claims (15, 16, 17, 18, 19)
-
Specification