Browse Prior Art Database

Method of Preserving High-level Dependence Analysis for Low-level Compiler Optimizations

IP.com Disclosure Number: IPCOM000021065D
Original Publication Date: 2003-Dec-19
Included in the Prior Art Database: 2003-Dec-19
Document File: 3 page(s) / 41K

Publishing Venue

IBM

Abstract

This invention introduces a compact way to preserve the high-level dependence analysis information for low-level optimizations.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 35% of the total text.

Page 1 of 3

Method of Preserving High-level Dependence Analysis for Low-level Compiler Optimizations

Modern compilers typically consist of multiple optimization phases and use multiple intermediate languages (ILs) which are appropriate for the kinds and degree of high-level and low-level transformations to be performed. The intermediate languages for high-level transformation could be a form suited for machine-independent optimizations, and may include whole program analysis and source code level information. The low-level intermediate languages are often for machine-dependent optimizations, particularly for machine code generation for a specific instruction set and hardware platform. One of the important issues is how to preserve the information from high-level to low-level languages in a precise and compact way, so that low-level optimizations can utilize the high-level analysis.

IBM XLC/XLF compilers perform high-level transformations using a compact high-level intermediate language WCODE on an abstract stack machine. Low-level optimizations and code generation use an intermediate language named XIL (Extended Intermediate Language), which is similar to generic assembly code with some machine-specific constructs. During the high-level optimization phase, a detailed dependence analysis is performed which identifies if particular uses of program variables could access the same memory during execution of the program. For example, a variable 'a' may access the same memory as a pointer 'b', if the pointer is set to address of 'a'. High-level dependence analysis can often determine for a specific point in the program if 2 memory accesses through variables could access the same memory. If it is not possible that 2 particular memory accesses overlap, then it can be said that these accesses are independent of each other.

One application of high-level dependence analysis is to determine when iterations of a loop have no data dependences between them. Data dependencies between loop iterations are called 'loop carried dependences'. If all of the memory accesses of iteration i of a loop are independent of all of the memory accesses of iteration i + 1 of the loop, then the 2 iterations can be said to be independent of each other. Furthermore, if iteration i of the loop is independent of all successive iterations of the loop, then the loop has the unique property that there is no limitation to how many loop iterations can be executed simultaneously. For our purposes, we will describe loops with this property as being loop-independent.

There exists a method for conveying the information that a loop has the loop-independent property from high-level dependence analysis to low-level optimizations. This method is to insert a directive instruction into the code of the loop, marking it as loop-independent. The instruction will only exist in the intermediate language and will not turn into any generated instructions in the final object code, so its only purpose i...