Outer loop vectorization

• US 5,802,375 A
• Filed: 11/23/1994
• Issued: 09/01/1998
• Est. Priority Date: 11/23/1994
• Status: Expired due to Fees

• Current Assignee: RPX Corporation
• Original Assignee: CRAY Incorporated (Hewlett-Packard Enterprise Company)
• Inventors: Ngo, Viet N., Tsai, Wei-Tek
• Primary Examiner(s): Oberley, Alvin E.
• Assistant Examiner(s): COURTENAY III, ST JOHN
• Application Number:
  US08/344,236
• Time in Patent Office: 1,378 Days
• Field of Search: 395/700, 395/701-709
• US Class Current: 717/160
• CPC Class Codes: G06F 8/452 Loops

Abstract

A system and method for vectorizing a non-innermost loop of a nested loop. Iterative loops of a nested loop are analyzed to determine if they can be vectorized (vector legality). If more than one iterative loop can be vectorized, a selection criteria is applied to select the iterative loop which would provide the most return from vectorization (vector selection).

Claims

1. A computer-implemented method of vectorizing a nested loop having a plurality of iterative loops, the method comprising the steps of:

analyzing each iterative loop to determine if it is vectorizable, wherein the step of analyzing each iterative loop includes the steps of;

preparing a program dependence graph for the nested loop, wherein the program dependence graph explicitly represents both control and data dependencies; and

extracting, from the program dependence graph, a level dependence graph for each of the plurality of iterative loops, wherein each level dependence graph includes all control and data dependencies relevant to vectorization of the nested loop at that level;

determining for each iterative loop whether dependence edges in its respective level dependence graph include a vectorization preventing dependence edge;

determining for each iterative loop whether there are dependence cycles within its respective level dependence graph; and

if an iterative loop from the plurality of iterative loops has no vectorization preventing dependence edges and no dependence cycles within its respective level dependence graph, indicating that the iterative loop is vectorizable; and

if more than one iterative loop is vectorizable, applying a selection criteria to select an optimal iterative loop from the plurality of iterative loops.

2. The method according to claim 1 wherein the step of applying a selection criteria comprises the steps of:

calculating a metric for each iterative loop in the plurality of iterative loops; and

choosing the iterative loop with the best metric.

3. A computer-implemented method of vectorizing a nested loop having a plurality of iterative loops, including a kth-level iterative loop, wherein k is an integer greater than one, the method comprising the steps of:

preparing a program dependence graph for the nested loop, wherein the program dependence graph explicitly represents both control and data dependencies;

extracting, from the program dependence graph, a level dependence graph for the kth-level iterative loop, wherein the level dependence graph includes all control and data dependencies relevant to vectorization of the nested loop at level k;

determining whether any dependence edges within the level dependence graph are k-vectorization preventing;

determining if there are any dependence cycles within the level dependence graph; and

if none of the dependence edges are k-vectorization preventing and if there are no dependence cycles within the level dependence graph, vectorizing the kth-level loop.

4. A computer-implemented method of vectorizing a nested loop having a plurality of iterative loops, the method comprising the steps of:

preparing a program dependence graph for the nested loop, wherein the program dependence graph explicitly represents both control and data dependencies;

extracting, from the program dependence graph, a level dependence graph for each of the plurality of iterative loops, wherein the level dependence graph includes all control and data dependencies relevant to vectorization of the nested loop at that level;

determining for each iterative loop whether dependence edges in its respective level dependence graph include a vectorization preventing dependence edge;

determining for each iterative loop whether there are dependence cycles within its respective level dependence graph;

building a list of those iterative loops having no vectorization preventing dependence edges and no dependence cycles within their respective level dependence graphs;

selecting an iterative loop from the list of iterative loops; and

vectorizing the selected iterative loop.

5. The computer-implemented method of claim 4 wherein the step of vectorizing the selected iterative loop comprises the steps of:

determining if statements within the selected iterative loop should be reordered; and

if the statements should be reordered, reordering the statements.

6. The computer-implemented method of claim 4 wherein the step of selecting an iterative loop from the list of iterative loops comprises the steps of:

calculating a metric for each iterative loop in the list of iterative loops; and

choosing the iterative loop with the best metric.

7. The computer-implemented method of claim 6 wherein the step of vectorizing the selected iterative loop comprises the steps of:

determining if statements within the selected iterative loop should be reordered; and

if the statements should be reordered, reordering the statements.

8. For computer program code having a nested loop, wherein the nested loop includes a plurality of vectorizable iterative loops, a computer-implemented method of selecting an optimal vectorizable iterative loop from the plurality of vectorizable iterative loops, the method comprising the steps of:

calculating a metric for each of the plurality of vectorizable iterative loops, wherein the step of calculating a metric includes the step of calculating overhead for an iterative loop as;

space="preserve" listing-type="equation">O.sub.l =(VLO+(T.sub.l /VL)*(ML+MS)/T.sub.l

where (T_l /VL) is the number of vector trips; and

selecting the iterative loop having the best metric.