US5797013A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Intelligent loop unrolling
Assignee: Hewlett Packard Enterprise Development LP
•
Filing: 1995-11-29
•
Granted: 1998-08-18
•
Expires: 2015-11-29
Abstract
Abstract A compiler facilitates efficient unrolling of loops and enables the elimination of extra branches from the loops, including the elimination of conditional branches from unrolled loops with early exits. Unrolling also enhances other optimizations, such as prefetch, scalar replacement, and instruction scheduling. The unroll factor is calculated to determine the amount of loop expansion and the optimum location to place compensation code to complete the original loop count, i.e. before or after the unrolled loop. The compiler is applicable, for example, to modern RISC architectures, where the latency of memory references and branches is higher than that of integer and floating point arithmetic instructions.
Inventors
- 👤 Uma Mahadevan
- 👤 Lacky Shah
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 03:35
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/44; G06F8/443
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
91 words
In a programmable machine, a compiler comprising: an analysis module for analyzing and unrolling loops within source applications; an optimizer module for determining an optimum unroll factor in response to said analysis module; an unroll module for generating an unrolled loop having said optimum unroll factor; and a compensation module for generating and placing any compensation code as required as a result of loop unroll optimization, wherein said compensation module performs a placement calculation to determine whether to put said compensation code before the unrolled loop or after the unrolled loop.
Claim 2
Dependent Claim
91 words
In a programmable machine, a compiler comprising: an analysis module for analyzing and unrolling loops within source applications; an optimizer module for determining an optimum unroll factor in response to said analysis module; an unroll module for generating an unrolled loop having said optimum unroll factor; and a compensation module for generating and placing any compensation code as required as a result of loop unroll optimization, wherein said compensation module performs a placement calculation to determine whether to put said compensation code before the unrolled loop or after the unrolled loop.
Claim 3
Dependent Claim
25 words
The compiler of claim 1, wherein said compensation module ensures that said compensation code is executed at least once when said unrolled loop is executed.
Claim 4
Dependent Claim
19 words
The compiler of claim 1, wherein said unroll factor is responsive to a number of instructions in the loop.
Claim 5
Dependent Claim
17 words
The compiler of claim 1, wherein said unroll factor is responsive to resource usage within the loop.
Claim 6
Dependent Claim
20 words
The compiler of claim 1, wherein said unroll factor is responsive to prefetch distance of memory references within the loop.
Claim 7
Dependent Claim
21 words
The compiler of claim 1, wherein said unroll factor is responsive to profile information collected from previous executions of compiled code.
Claim 8
Dependent Claim
19 words
The compiler of claim 1, wherein said unroll factor is responsive to recurrence of memory references within the loop.
Claim 9
Dependent Claim
19 words
The compiler of claim 1, wherein said unroll factor is responsive to the number of instructions in the loop.
Claim 10
Dependent Claim
41 words
The compiler of claim 1, wherein a trip count for the loop is known at compile time, and wherein said optimizer module determines an unroll factor that executes the compensation code zero times and suppresses the generation of said compensation code.
Claim 11
Dependent Claim
19 words
The compiler of claim 1, wherein said placement calculation is responsive to the unroll factor computed for the loop.
Claim 12
Dependent Claim
15 words
The compiler of claim 1, wherein said loop is a loop having an early exit.
Claim 13
Dependent Claim
15 words
The compiler of claim 1, wherein loop unrolling is integrated with other low-level optimization phases.
Claim 14
Dependent Claim
22 words
The compiler of claim 12, wherein said other low-level optimization phases include any of prefetch instruction insertion, register reassociation, and instruction scheduling.
Claim 15
Independent Claim
72 words
A method for unrolling loops, comprising the steps of: determining a unroll factor; generating an unrolled loop which always exits leaving a remaining trip count of at least one; generating compensation code; determining whether the compensation code should be placed before the unrolled loop or after the unrolled loop; and determining if the trip count is a power of two; and if it is placing the compensation code before the unrolled loop.
Claim 16
Independent Claim
72 words
A method for unrolling loops, comprising the steps of: determining a unroll factor; generating an unrolled loop which always exits leaving a remaining trip count of at least one; generating compensation code; determining whether the compensation code should be placed before the unrolled loop or after the unrolled loop; and determining if the trip count is a power of two; and if it is placing the compensation code before the unrolled loop.
Claim 17
Dependent Claim
18 words
The method of claim 14, wherein the loop to be unrolled is a loop having an early exit.
Claim 18
Dependent Claim
34 words
The method of claim 15, wherein the loop having an early exit after unrolling is transformed into a loop having an exit at its end, and from which all intermediate exits have been removed.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-08-17 | 2002-02-16 | 2002-08-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-08-17 | 2006-02-16 | 2006-08-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-08-17 | 2010-02-16 | 2010-08-18 | $7700.00 | Window Closed / Lapsed |