Browse Prior Art Database

Synonyms for Common Subexpression Elimination

IP.com Disclosure Number: IPCOM000114489D
Original Publication Date: 1994-Dec-01
Included in the Prior Art Database: 2005-Mar-28
Document File: 4 page(s) / 92K

Publishing Venue

IBM

Related People

Besaw, K: AUTHOR [+4]

Abstract

Disclosed is a method for enhancing the ability of an optimizing compiler to recognize common subexpressions as it generates code for any target machine architecture.

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

Synonyms for Common Subexpression Elimination

      Disclosed is a method for enhancing the ability of an
optimizing compiler to recognize common subexpressions as it
generates code for any target machine architecture.

      It is desirable that compilers for computer languages produce
machine language sequences which are the most efficient ones
possible, given the constraints of the language and environment.  One
of the techniques optimizing compilers use to accomplish this is the
optimization generally referred to as Common Subexpression
Elimination (CSE).

      When applying optimizations, the order that optimization
transformations are applied may expose some common subexpressions,
but may also cause some other common subexpressions to to be obscured
and hidden.  For example, consider the code fragment shown below.
Two basic blocks are shown, with the code fragments transformed as
shown by use of local copy propagation.  With this transformation,
global CSE would now be able to recognize that i*c and j*c produce
the same result.

      However, in other cases replacing the variable reference with
its value expression may cause us to fail to recognize common
expressions.  In the code fragment shown below, if the assignment to
x is transformed as shown, we will not recognize that (a+k)*b and i*b
are global common subexpressions.

      When applying transformations like local copy propagation, the
method disclosed here utilizes both the original and transformed
expressions, and then sees which one wins subsequently in terms of
being eliminated as common.  The two expressions are referred to as
synonyms or twins of each other for a given basic block.  The
expression prior to local copy propagation is referred to as the
unresolved twin, and the expression after local copy propagation is
referred to as the resolved twin.

      Locally, the resolved twin is used for subsequent local CSE
processing within a basic block.  Globally, both the resolved and
unresolved twins are added to the global expression table.  Each of
these expressions are then processed with the global CSE algorithm
(for example, solving data flow equations based on the Morel-Renvoise
partial redundancy algorithm) to see whether either "synonym" for the
expression has merit of surfacing redundancies that can be eli...