Browse Prior Art Database

Iterative Unrolling During Compilation

IP.com Disclosure Number: IPCOM000112741D
Original Publication Date: 1994-Jun-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 2 page(s) / 106K

Publishing Venue

IBM

Related People

White, SW: AUTHOR

Abstract

Disclosed is a methodology for improving the effectiveness of automatic loop unrolling during the compilation of a computer program. As an alternative to using heuristics to control unrolling, a compiler could experiment with several choices of unrolling parameters on a loop-by-loop basis. For each resulting version of a loop, high-level scheduling and cycle estimation can be used by the compiler to select the candidate which is likely to result in the optimum execution-time performance.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Iterative Unrolling During Compilation

      Disclosed is a methodology for improving the effectiveness of
automatic loop unrolling during the compilation of a computer
program.  As an alternative to using heuristics to control unrolling,
a compiler could experiment with several choices of unrolling
parameters on a loop-by-loop basis.  For each resulting version of a
loop, high-level scheduling and cycle estimation can be used by the
compiler to select the candidate which is likely to result in the
optimum execution-time performance.

      Loop unrolling, replicating the loop body and decreasing the
loop count, is a well-known technique for improving the
execution-time performance of programs.  Several independent
operations are often necessary to fully exploit processors which
support multiple, pipelined, functional units.  Applications often
contain sufficient independence; however, programming styles often
conceal the opportunity.  Unrolling is a key technique for exposing
the latent instruction-level parallelism.  When loops are unrolled,
operations from multiple iterations are available for scheduling by
the compiler.  This increased flexibility often allows the compiler
to generate more efficient machine-executable code.  Since loop
unrolling is always a safe transformation, determining which loops to
unroll and to what degree is the difficult problem to solve.

      One solution is user-specified unrolling.  However, manual
intervention for each loop is tedious.  Subroutine-level
specification often is not optimal as unrolling may be beneficial for
one loop and detrimental for an adjacent loop.  Furthermore,
unrolling trade-offs are complex and often only appear at the
assembly language level (rather than the typical high-level language
with which the user is familiar); therefore, many users lack the
skills to determine which loops should be unrolled.

      Another current solution is automated unrolling of loops, often
in a pre-compilation stage.  However, prior to the final compilation
stage, the advantages/disadvantages for the possible unrolling
choices are often difficult to assess.  The optimal unrolling amount
for a loop depends on many factors including 1) the number of
registers required after each unrolling (affecting spill code), 2)
the operations and variables which are common across iterations
(affecting reuse of operands), 3) the operations from one iteration
which can be interleaved with operations from other iterations
(effectively hiding some latency), and 4) pipeline considerations
(interlocks within and across iterations).

      The proposed solution is to iteratively unroll loops during
compilation.  Many compilers have the ability to "estimate" the
number of cycles required to execute an instruction sequence.  When
the compiler generates code for a loop, it can estimate the
associated execution time.  The...