Browse Prior Art Database

Value Numbering in the Context of Merging Control Flow

IP.com Disclosure Number: IPCOM000045913D
Original Publication Date: 1983-May-01
Included in the Prior Art Database: 2005-Feb-07
Document File: 3 page(s) / 69K

Publishing Venue

IBM

Related People

Saade, HY: AUTHOR [+2]

Abstract

In this article we describe a method and apparatus for operating a computer during compilation of a source program to optimize the translated code output by removing unnecessary redundant instructions. First, the computation environment for each of a plurality of paths from a first basic block to a subsequent common path is determined. Then, the computation environment is pruned to create a single environment for the subsequent common path.

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

Page 1 of 3

Value Numbering in the Context of Merging Control Flow

In this article we describe a method and apparatus for operating a computer during compilation of a source program to optimize the translated code output by removing unnecessary redundant instructions. First, the computation environment for each of a plurality of paths from a first basic block to a subsequent common path is determined. Then, the computation environment is pruned to create a single environment for the subsequent common path.

This technique extends the simple, but powerful, value numbering optimization technique, previously confined to the context of (extended) basic blocks, to a merging control flow context, thus enhancing its usefulness, giving some of the benefits of global optimization, without the associated expense.

Program optimization is a process whereby the translated form of a computer program is improved in some respect. Optimization is usually an integral part of a translation program or compiler. Typically, the improvements have the effect of making the program execute faster. Strategies include (1) removing altogether instructions that can be determined to be unnecessary and (2) replacing a slow sequence of instructions with an equivalent, but faster, sequence.

Basic blocks of a program are maximal sequences of instructions such that if the first instruction is executed, then it follows that every instruction in the sequence must also be executed. Thus, there is only one entry to the sequence of instructions at the first instruction, and only one exit after the last instruction in the sequence.

Value numbering is a technique that can be used for eliminating unnecessary instructions from within basic blocks. Each value that participates in a computation is denoted by a unique value number, as is the result of a particular computation. As each computation within the basic block is encountered, it is reduced to a canonic form, based on the value numbers of its inputs and its result, and is then entered in a table of available computations. If a computation involving the same, unaltered inputs was previously encountered within the basic block, then the canonic form of the computation will already be in this table. In this event, the subsequent, redundant computation can be eliminated from the program. References to its result are replaced by references to the saved result of the earlier, irredundant computation. In addition, a computation whose inputs are all constant can be evaluated during program translation and then removed from the translated program. References to its result are replaced by references to the evaluated constant.

Value numbering is defined in terms of basic blocks, but is commonly extended to a tree-like control flow context, known as an extended basic block. This kind of control flow context is typical of conditional statements, such as is illustrated in the extended basic block of Fig. 1, where the boxes labelled Test, True Path...