Unrolling loops with partial hot traces
AssigneeInternational Business Machines Corporation
InventorsRobert Ralph Roediger, William Jon Schmidt, Peter Jerome Steinmetz
Life of this patent
Estimating the term…
Abstract
Methods and apparatus are disclosed for improved loop unrolling by a compiler. A large class of loops exists for which effective loop unrolling has not previously been performed because they are too large to be completely unrolled, but which do not have a single hot trace that covers an entire loop iteration. The present invention recognizes such loops that have partial hot traces identified using profile data. A set of instructions which constitute a proper superset of the hot trace and a proper subset of the entire loop, and which forms a complete loop iteration is identified. This set of instructions can then be unrolled without unrolling the entire loop.
Claims18
A method for optimizing a loop in an instruction stream of a computer program, the method comprising the steps of:
- identifying a partial hot trace using profile data;
- identifying an augmented hot trace set of instructions comprising a proper superset of the partial hot trace, but comprising a proper subset of the entire loop, and which forms a complete loop iteration;
- optimizing the loop in the instruction stream of the computer program by unrolling the augmented hot trace set of instructions without unrolling the entire loop;
- identifying an augmentation path set using the profile data;
- combining the augmentation path set with the partial hot trace to form the augmented hot trace set of instructions;
- and
- the step of identifying an augmentation path set using the profile data further comprising the step of:
- identifying a candidate augmentation path set of instructions having more than one trace through the candidate augmentation path set of instructions, and more than one of the traces having similar probabilities of being executed during an iteration of the loop, the sum of the probabilities of the one or more traces through the set being similar to the probability of execution of the partial hot trace.
A program product, stored on a computer readable medium, which, when executed by a suitable computer, performs a method of optimizing a loop in an instruction stream of a computer program, the method comprising the steps of:
- identifying a partial hot trace using profile data,
- identifying an augmented hot trace set of instructions comprising a proper superset of the partial hot trace, but comprising a proper subset of the entire loop, and which forms a complete loop iteration;
- unrolling the augmented hot trace set of instructions without unrolling the entire loop;
- identifying an augmentation path set using the profile data;
- combining the augmentation path set with the partial hot trace to form the augmented hot trace set of instructions;
- and
- the step of identifying an augmentation path set using the profile data further comprising the step of identifying a candidate augmentation path set of instructions having more than one trace through the candidate augmentation path set of instructions, and more than one of the traces having similar probabilities of being executed during an iteration of the loop, the sum of the probabilities of the one or more traces through the set being similar to the probability of execution of the partial hot trace.
Dependencies are inferred from the claim text.