International Business Machines Corporation

Dz Ching Ju

Kalyan Muthukumar

Shankar Ramaswamy

John Shek-Luen Ng

Barbara Bluestein Simons

Vivek Sarkar

Code restructuring or reordering based on profiling information and memory hierarchy is provided by constructing a Program Execution Graph (PEG) corresponding to a level of the memory hierarchy, partitioning this PEG to reduce estimated memory overhead costs below an upper bound, and constructing a PEG for a next level of the memory hierarchy from the partitioned PEG. The PEG is constructed from control flow and frequency information from a profile of the program to be restructured. The PEG is a weighted undirected graph comprising nodes representing basic blocks and edges representing transfer of control between pairs of basic blocks. The weight of a node is the size of the basic block it represents and the weight of an edge is the frequency of transition between the pair of basic blocs it connects.

Method of, system for, and computer program product for providing efficient utilization of memory hierarchy through code restructuring

Code restructuring or reordering based on profiling information and memory hierarchy is provided by constructing a Program Execution Graph (PEG) corresponding to a level of the memory hierarchy, partitioning this PEG to reduce estimated memory overhead costs below an upper bound, and constructing a PEG for a next level of the memory hierarchy from the partitioned PEG. The PEG is constructed from control flow and frequency information from a profile of the program to be restructured. The PEG is a weighted undirected graph comprising nodes representing basic blocks and edges representing transfer of control between pairs of basic blocks. The weight of a node is the size of the basic block it represents and the weight of an edge is the frequency of transition between the pair of basic blocks it connects. The nodes of the PEG are partitioned or clustered into clusters such that the sum of the weights of the nodes in any cluster is no greater than an upper bound. A next PEG is then constructed from the clusters of the partitioned PEG such that a node in the next PEG corresponds to a cluster in the partitioned PEG, and such that there is an edge between two nodes in the next PEG if there is an edge between the clusters represented by the two nodes. Weights are assigned to the nodes and edges of the next PEG to produce a PEG, and then the PEG partitioning, basic block reordering, and PEG construction steps may be repeated for each level of the memory hierarchy. After the clustering is completed, the basic blocks are reordered in memory by grouping all of the nodes of a cluster in an adjacent order beginning at a boundary for all the levels of the memory hierarchy. Because clusters must not cross boundaries of memory hierarchies, NOPs are added to fill out the portion of a memory hierarchy level that is not filled by the clusters.

FORTRAN WHERE construct compilation and optimization is provided by excluding an assignment statement containing a transformational intrinsic function from loop fusion of the WHERE construct. To perform this loop fusion, intrastatement dependence analysis is performed within each assignment statement of the WHERE construct, and then interstatement dependence analysis is performed between each assignment statement and assignment statements subsequent to the assignment statement. Responsive to this dependence analysis, pairs of assignment statements which may not be fused into a single loop are identified, and non-fusion boundaries between adjacent assignment statements where assignment statements preceding a non-fusion boundary and assignment statements subsequent to the non-fusion boundary may not be fused into a single loop are identified. This fusion analysis yields a loop fusion configuration. After the loop fusion configuration is identified and the rank of any temporary expression is determined, code generation is performed by scalarizing each assignment statement. This provides better optimization than the conventional straight forward approach to compiling a WHERE construct, and further provides an optimized compilation of a WHERE construct by the use of less compilation time than that required by conventional high-level optimization.

Method of, system for, and computer program product for providing quick

Method of, system for, and computer program product for generating efficient code for a set of nested Fortran 90 array constructors without introducing temporary vectors by the use of normalized counters and by maintaining array constructor extent structure trees. Non-perfectly nested array constructors and array constructors with dynamic extents may be inlined. The results provided include a reduction in run-time memory storage usage and an improvement in execution time performance.

Growing community of inventors

Sunnyvale, CA, United States of America

Dz Ching Ju