Patent US6070011A successfully refreshed from Google Patents.
US6070011A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Compiler for performing a loop fusion, dependent upon loop peeling and/or loop reversal
Assignee: Hewlett Packard Development Co LP
•
Filing: 1997-10-21
•
Granted: 2000-05-30
•
Expires: 2017-10-21
Abstract
Abstract A compile method employs loop fusion to improve execution of a first loop and a second loop in a code sequence. A compile method initially peels one or more loop iterations from one of the loops to cause each of the loops to exhibit an equal number of loop iterations. Thereafter, an attempt is made to fuse the first and second loops, upon a condition that the resulting fused loop produces a same computational result as would be produced if the first loop and second loop were not fused. If the condition is not met, a loop reversal is performed on one of the loops and a fusing action is again attempted; if the attempted fusing action of the loops does not fulfill the condition, a loop reversal is performed on the other loop and a fusing action is again attempted. The combined loop peeling/loop reversal actions provide a higher probability of an ability to fuse the loops than otherwise.
Inventors
- 👤 Jiyang Liu
- 👤 Robert Gottlieb
- 👤 Andrew E. Ayers
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 16:46
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/43; G06F8/433; G06F8/44; G06F8/443
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
164 words
A compile method which employs loop fusion to improve execution of a first loop and a second loop in a code sequence, said first loop and second loop including different numbers of loop iterations, said compile method comprising the steps of: a) peeling one or more loop iterations from one said loop to cause each said loop to exhibit an equal number of loop iterations; b) fusing said first loop and second loop upon a condition that a resulting fused loop produces a same computational result as would be produced if said first loop and second loop were not fused; c) performing a loop reversal on one said loop and repeating step b), if the condition of step b) is not met as a result of a prior fusing action; and d) performing a loop reversal on another said loop and repeating step b), if the condition of step b) is not met as a result of a fusing action subsequent to step c).
Claim 2
Dependent Claim
164 words
A compile method which employs loop fusion to improve execution of a first loop and a second loop in a code sequence, said first loop and second loop including different numbers of loop iterations, said compile method comprising the steps of: a) peeling one or more loop iterations from one said loop to cause each said loop to exhibit an equal number of loop iterations; b) fusing said first loop and second loop upon a condition that a resulting fused loop produces a same computational result as would be produced if said first loop and second loop were not fused; c) performing a loop reversal on one said loop and repeating step b), if the condition of step b) is not met as a result of a prior fusing action; and d) performing a loop reversal on another said loop and repeating step b), if the condition of step b) is not met as a result of a fusing action subsequent to step c).
Claim 3
Dependent Claim
61 words
The compiler method as recited in claim 1, wherein step a), subsequent to said peeling, further comprises the substep of: a1) analyzing said first loop and said second loop to assure that data dependencies in both said first loop and said second loop will not be violated in an event of a fusion of said first loop and said second loop.
Claim 4
Dependent Claim
92 words
The compiler method as recited in claim 2, wherein step a) subsequent to substep al), further comprises the substep of: a2) upon a finding in substep al) that data dependencies in at least one said loop will be violated in an event of a fusion of said first loop and said second loop, analyzing said first loop and said second loop to assure that a reversal of at least one said loop will not violate data dependencies in said loop to be reversed and, if so, proceeding to execution of step b).
Claim 5
Dependent Claim
63 words
The compiler method as recited in claim 1, wherein step a), subsequent to said peeling, further comprises the substep of: a1) analyzing said first loop and said second loop to assure that performance of a fused loop from said first loop and said second loop will exhibit an improvement in performance over performance of said first loop and said second loop, before fusion.
Claim 6
Dependent Claim
208 words
A memory media for controlling a computer to perform a compile action on a code sequence, said compile action including loop fusion to improve execution of a first loop and a second loop in said code sequence, said first loop and second loop including different numbers of loop iterations, said memory media comprising: a) means for controlling said computer to peel one or more loop iterations from one said loop to cause each said loop to exhibit an equal number of loop iterations; b) means for controlling said computer to fuse said first loop and second loop upon a condition that a resulting fused loop produces a same computational result as would be produced if said first loop and second loop were not fused; c) means for controlling said computer to perform a loop reversal on one said loop and to cause a repetition of operation of means b), if said condition is not met as a result of a prior fusing action; and d) means for controlling said computer to perform a loop reversal on another said loop and to cause a repetition of operation of means b), if said condition is not met as a result of a fusing action subsequent to operation of means c).
Claim 7
Dependent Claim
208 words
A memory media for controlling a computer to perform a compile action on a code sequence, said compile action including loop fusion to improve execution of a first loop and a second loop in said code sequence, said first loop and second loop including different numbers of loop iterations, said memory media comprising: a) means for controlling said computer to peel one or more loop iterations from one said loop to cause each said loop to exhibit an equal number of loop iterations; b) means for controlling said computer to fuse said first loop and second loop upon a condition that a resulting fused loop produces a same computational result as would be produced if said first loop and second loop were not fused; c) means for controlling said computer to perform a loop reversal on one said loop and to cause a repetition of operation of means b), if said condition is not met as a result of a prior fusing action; and d) means for controlling said computer to perform a loop reversal on another said loop and to cause a repetition of operation of means b), if said condition is not met as a result of a fusing action subsequent to operation of means c).
Claim 8
Dependent Claim
59 words
The memory media as recited in claim 5, wherein means a) subsequent to said peeling, controls said computer to analyze said first loop and said second loop to assure that data dependencies in both said first loop and said second loop will not be violated in an event of a fusion of said first loop and said second loop.
Claim 9
Dependent Claim
82 words
The memory media as recited in claim 6, wherein means a) further controls said computer, upon finding that data dependencies in at least one said loop will be violated in an event of a fusion of said first loop and said second loop, to analyze said first loop and said second loop to assure that a reversal of at least one said loop will not violate data dependencies in said loop to be reversed and, if so, causes operation of means b).
Claim 10
Dependent Claim
62 words
The memory media as recited in claim 5, wherein means a), subsequent to said peeling, further controls said computer to analyze said first loop and said second loop to assure that performance of a fused loop from said first loop and said second loop will exhibit an improvement in performance over performance of said first loop and said second loop, before fusion.
References Cited (Backward Citations)
US5303357A
Cited
US5548761A
Cited
US5491823A
Cited
US5457799A
Cited
US5752037A
Cited
US5822593A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-05-30 | 2003-11-29 | 2004-05-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-05-30 | 2007-11-29 | 2008-05-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-05-30 | 2011-11-29 | 2012-05-30 | $7700.00 | Window Closed / Lapsed |