Browse Prior Art Database

Flow Precedence Analysis for Optimizing Compilers

IP.com Disclosure Number: IPCOM000082549D
Original Publication Date: 1974-Dec-01
Included in the Prior Art Database: 2005-Feb-28
Document File: 4 page(s) / 32K

Publishing Venue

IBM

Related People

Kim, J: AUTHOR [+3]

Abstract

Two problems concerning optimizing compilers are addressed herein. They are, 1) reducing load/store instruction insertions, and 2) reducing residual control loading in microprogram compilers.

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 34% of the total text.

Page 1 of 4

Flow Precedence Analysis for Optimizing Compilers

Two problems concerning optimizing compilers are addressed herein. They are, 1) reducing load/store instruction insertions, and 2) reducing residual control loading in microprogram compilers.

The first one of these is concerned with the register allocation phase of an optimizing compiler - the problem of binding a limited number of registers to a large number of variables. Since the number of registers is limited (16 for System/370), very often, the content of a register has to be stored into main storage such that a reassignment of this register can be made to a different variable. The stored variable may, however, have to be reloaded back into a register if it is used again.

Described is a way of reducing the number of registers required for a given block (straight line code) by moving instructions within a block, such that the number of load/store instructions inserted is significantly reduced.

The second problem concerns the reduction of residual control loadings for certain microprogram controlled machines (e.g., System/370 Model 145). This also involves moving instructions within a block, since residual control information is associated with an instruction. By properly moving instructions within a block, it is possible to reduce the loading of residual control information when they differ for neighboring instructions.

Attempts to move instructions within a block to reduce the usage of registers have appeared in the literature. But their considerations have been centered around reducing registers for temporary variables. And they are applicable either to a specific machine dependent language or to a special class of expressions. The algorithm presented in this description is general in the sense that it can be applied to any language and any expression, and treats all the variables equally. Techniques for Code Motion

First, the technique of moving load/store instructions appearing in the original block is shown. Then the flow precedence analysis which allows movement of any instruction within the block is discussed. Finally, based on the flow precedence analysis, rules for moving instructions are presented. Moving Load/Store Instructions

Suppose that S(i) is an instruction which loads a variable V from main store into register R. If the instruction immediately after S(i) does not use the variable V, the variable V may be binding the register R unnecessarily. Moving S(i) immediately before the first use of V frees R for some other purpose.

Likewise, if a variable V in register R is stored into main store in instruction S(j) while its last use was in instruction S(i) where S(i) precedes S(j), then S(i) can be moved and free the register R for some other purpose. Furthermore, if the definition point of V (the instruction where the value of V is defined) is known, then S(j) can be moved to the point immediately after the last definition point of the variable V, since storing a var...