Browse Prior Art Database

Monotonically Increasing Counter for Local Code Optimization Algorithm

IP.com Disclosure Number: IPCOM000106860D
Original Publication Date: 1993-Dec-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 6 page(s) / 223K

Publishing Venue

IBM

Related People

Besaw, K: AUTHOR [+2]

Abstract

A generalized algorithm for local code optimization based on a monotonically increasing counter is disclosed. The algorithm performs common subexpression elimination, redundant store elimination, and copy propagation simultaneously and in a consistent fashion.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 29% of the total text.

Monotonically Increasing Counter for Local Code Optimization Algorithm

      A generalized algorithm for local code optimization based on a
monotonically increasing counter is disclosed.  The algorithm
performs common subexpression elimination, redundant store
elimination, and copy propagation simultaneously and in a consistent
fashion.

      A monotonically increasing counter, called the alias counter,
is used to develop a generalized algorithm for local optimization.
The generalized algorithm, through application of the alias counter,
performs common subexpression elimination, redundant load
elimination, redundant store elimination, and copy propagation
simultaneously and in a consistent fashion.  As a result, it is
possible to do local optimizations in a single pass over the code of
a basic block.  This reduces the running time and implementation
complexity of the optimizer.

      Briefly, the optimizer manages the alias counter in the
following manner to develop the generalized algorithm:

1.  The alias counter is incremented whenever storage is modified, a
    debug boundary occurs, an exception handler boundary occurs, the
    floating-point rounding mode changes, or a multitasking
    synchronization point is encountered.  It can also be incremented
    for other reasons that are not discussed in this disclosure.

2.  The current value of the alias counter is associated with each
    expression in the basic block as the expression is read and
    processed.  This value associated with an expression is called
    its captured alias counter.

3.  Each time a variable is used, the current value of the alias
    counter is "captured"  and recorded in the dictionary (symbol
    table) entry of the variable and in the dictionary entry of each
    of its aliases.  This value is called the variable's last-use
    alias counter.

4.  Each time a variable is defined, the current value of the alias
    counter is incremented and then "captured"  and recorded in the
    dictionary entry of the variable and in the dictionary entry of
    each of its aliases.  This value is called the variable's
    last-definition alias counter.

      Because of the monotonically increasing behavior of the alias
counter, the value of the captured alias counter associated with a
given expression in the basic block will be greater than or equal to
the captured alias counter associated with another expression at an
earlier point in the basic block.  This enables the generalized local
optimization algorithm to determine the relative order in which
storage uses, storage definitions, and other events occur within a
basic block.

      The present invention may best be understood from the following
detailed description of the preferred embodiment of the invention.

      Fig. 1.  is a logic flow diagram illustrating a compiler
embodying the present invention.  A first module 100 labelled...