Method of, system for, and computer program product for performing weighted loop fusion by an optimizing compiler

An article of manufacture for use in a computer system for performing weighted loop fusion on a plurality of loop nests by the computer system, said article of manufacture comprising a computer-readable storage medium having a computer program embodied in said medium which may cause the computer system to:

• create a loop dependence graph (LDG) representing the plurality of loop nests, wherein each of the plurality of loop nests is associated with a node of the LDG, and wherein an edge of the LDG represents a loop-independent data dependence from a source loop nest to a destination loop nest;
• associate a weight w.sub.ij =w.sub.ji with each pair of nodes i and j, wherein the weight represents a cost savings obtained if loop nests i and j are fused;
• determine a set, AN.times.N, of directed summary arcs on N, wherein N is a set of nodes of the loop dependence graph, N={1, 2, . . . , n};
• determine a set, C, of contractable arcs wherein C is a subset of the set of directed summary arcs, CA;
• determine a set, NC, of noncontractable arcs wherein NC is a subset of the set of directed summary arcs, NC=A-C
• determine a set, B, of unordered pairs of nodes (i,j) that have a w.sub.ij >0 and that are not connected by a summary arc, both (i,j).epsilon slash.A and (j,i).epsilon slash.A;
• associate a (0,1)-variable x.sub.ij with each unordered pair of nodes (i,j), and setting the x.sub.ij =0 if and only if i and j are placed in a same cluster and setting x.sub.ij =1 otherwise;
• determine a set of multipliers .pi..sub.i (i.di-elect cons.N) wherein each of the multipliers .pi..sub.i are an integer between 0 and n=.vertline.N.vertline., wherein .pi..sub.j -.pi..sub.i .gtoreq.1 for all (i,j).di-elect cons.A, wherein .pi..sub.i =.pi..sub.j if x.sub.ij =0, wherein .pi..sub.j -.pi..sub.i .gtoreq.1 if x.sub.ij =1 and (i,j).di-elect cons.A;
• and
• minimize a summation of a product of w.sub.ij and x.sub.ij over a set of nodes (i,j) comprising a union of the set B and the set of contractable arcs C, (i,j).di-elect cons.B.orgate.C, subject to a set of constraints comprising:
• ##EQU13## perform loop fusion on the plurality of loop nests using loop partitions based on the minimized summation.

A computer system for performing weighted loop fusion on a plurality of loop nests by the computer system, said computer system comprising:

• means for creating a loop dependence graph (LDG) representing the plurality of loop nests, wherein each of the plurality of loop nests is associated with a node of the LDG, and wherein an edge of the LDG represents a loop-independent data dependence from a source loop nest to a destination loop nest;
• means for associating a weight w.sub.ij =w.sub.ji with each pair of nodes i and j, wherein the weight represents a cost savings obtained if loop nests i and j are fused;
• means for determining a set, AN.times.N, of directed summary arcs on N, wherein N is a set of nodes of the loop dependence graph, N={1, 2, . . . , n};
• means for determining a set, C, of contractable arcs wherein C is a subset of the set of directed summary arcs, CA;
• means for determining a set, NC, of noncontractable arcs wherein NC is a subset of the set of directed summary arcs, NC=A-C
• means for determining a set, B, of unordered pairs of nodes (i,j) that have a w.sub.ij >0 and that are not connected by a summary arc, both (i,j).epsilon slash.A and (j,i).epsilon slash.A;
• means for associating a (0,1)-variable x.sub.ij with each unordered pair of nodes (i,j), where the x.sub.ij =0 if and only if i and j are placed in a same cluster and x.sub.ij =1 otherwise;
• means for determining a set of multipliers .pi..sub.i (i.di-elect cons.N) wherein each of the multipliers .pi..sub.i are an integer between 0 and n=.vertline.N.vertline., wherein .pi..sub.j -.pi..sub.i .gtoreq.1 for all (i,j).di-elect cons.A, wherein .pi..sub.i =.pi..sub.j if x.sub.ij =0, wherein .pi..sub.j -.pi..sub.i .gtoreq.1 if x.sub.ij =1 and (i,j).di-elect cons.A;
• and
• means for minimizing a summation of a product of w.sub.ij and x.sub.ij over a set of nodes (i,j) comprising a union of the set B and the set of contractable arcs ##EQU16## means for performing loop fusion on the plurality of loop nests using loop partitions based on the minimized summation.