Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

A technique to apply loop peeling based on the forward path profile

IP.com Disclosure Number: IPCOM000012697D
Original Publication Date: 2003-May-21
Included in the Prior Art Database: 2003-May-21
Document File: 2 page(s) / 20K

Publishing Venue

IBM

Abstract

A loop optimization technique for compilers is disclosed that applies a loop peeling optimization selectively based on forward path profiles. In the disclosed technique, after collecting forward path profiles, three indices for each loop are calculated by using the forward path profiles: the number of loop iterations, the execution-time probability of termination of the loop at the first iteration, and the differences in the hot paths between the first iteration and the later iterations. These indices are then compared with their corresponding thresholds to decide whether or not loop peeling is applied to each loop.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 54% of the total text.

Page 1 of 2

A technique to apply loop peeling based on the forward path profile

  Loop peeling is an optimization to transform a loop by peeling several iterations off from the loop body [1]. The disclosed technique is to calculate three indices for each loop by using forward path profiles collected by the Ball-Larus path profiling technique [2], and to apply loop peeling to the loops if the performance can be improved by the loop peeling. The three indices are described as follows.

The first index, index1, is the number of loop iterations estimated from the forward path profiles, which is calculated using the following expression, where L is the target loop, Cp is the profile count of path p, Pbackedge-exit(L) is the set of paths that start from a backedge of L and contain an exit edge of L, and Pbackedge-backedge(L) is the set of paths that start from a backedge of L and end with a backedge of L.

C

  P q q

backedge

(

-=)LIndex

If the ratio is less than the threshold, the number of loop iterations is small and it will be effective to peel that number of iterations off from the loop body.

The second index, index2, is the execution-time probability of the termination of the loop at the first iteration, which is calculated using the following expression, where L is the target loop, Cp is the profile count of path p, Pentry-exit(L) is the set of paths that contain both an entry edge of L and an exit edge of L, and Pentry-*(L) is the set of paths that contain an entry edge of L.

1

backedge

backedge

exit

C

  P p p

=

-

(

)

L

C

C

  P q q

entry

exit

(

-=)LIndex

If the ratio is more than the threshold, most of loop executions are terminated at the first iteration and it will be effective to peel the first iteration off from the loop body.

The third index, index3, measures the differences in the ho...