Browse Prior Art Database

Uni-Directional Flow Solution of Morel-Renvoise Partial Redundancy Equations

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

Publishing Venue

IBM

Related People

Hicks, DR: AUTHOR [+2]

Abstract

Disclosed here is a method for improving the efficiency of obtaining a solution to the Morel-Renvoise equations for partial redundancy elimination by taking advantage of the presence of landing pad blocks to simplify the equations so that they can be solved as a uni-directional data flow problem. The Morel-Renvoise equations for partial redundancy elimination represent the basis for a fundamental optimization in modern programming language compilers. The equations are applicable to backward code motion. A dual form of the equations is applicable to forward code motion.

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

Uni-Directional Flow Solution of Morel-Renvoise Partial Redundancy
Equations

      Disclosed here is a method for improving the efficiency of
obtaining a solution to the Morel-Renvoise equations for partial
redundancy elimination by taking advantage of the presence of landing
pad blocks to simplify the equations so that they can be solved as a
uni-directional data flow problem.  The Morel-Renvoise equations for
partial redundancy elimination represent the basis for a fundamental
optimization in modern programming language compilers.  The equations
are applicable to backward code motion.  A dual form of the equations
is applicable to forward code motion.

      The Morel-Renvoise equations, like other data flow problems,
are solved iteratively until the equations converge (the values
computed by the equations cease to change).  A set of these equations
for each optimizable expression must be solved for each basic block
in the program.

      An unfortunate aspect of the Morel-Renvoise equations is that
they represent a bi-directional data flow problem.  In particular,
the equation for PPIN shown below (Placement Possible at INput to
block) exhibits this bi-directional characteristic.  PPIN and PPOUT
(Placement Possible at OUTput from block) are the fundamental
attributes which allow code motion.  The PPIN attribute can be seen
to depend on the PPOUT attribute of its predecessors, which in turn
depends on the PPIN attributes of its successors.  Known bounds on
the computational complexity of uni-directional data flow problems
are thus not applicable.

The equations from the Morel-Renvoise paper are repeated here for
reference:
     eqno (1 a)
      AVIN sub j = left lb
         < product from <p memberof Pred(j)> AVOUT sub p >
  lvabove < "false" %%%%% 'if j is entry block'>   right rb
  eqno (1 b)
      AVOUT sub j = COMP sub j + AVIN sub j * TRANSP sub j
  eqno (1 c)
      ANTOUT sub j = left lb
        <product from <s memberof Succ(j)> ANTIN sub s >
   lvabove < "false" %%%%% 'if j is exit block'>   right rb
   eqno (1 d)
     ANTIN sub j = ANTLOC sub j + ANTOUT sub j * TRANSP sub j
   eqno (1 e)
     PAVIN sub j = left lb
        <sum from <p memberof Pred(j)> PAVOUT sub p >
  lvabove < "false" %%%%% 'if j is entry block'>   right rb
  eqno (1 f)
     PAVOUT sub j = COMP sub j + PAVIN sub j * TRANSP sub j
  eqno (1 g)
     CONST sub j = ANTIN sub j *
                  (PAVIN sub j + lnot ANTLOC sub j * TRANSP sub j)
  eqno (1 h)
     PPIN sub j = % left lb
         <CONST sub j * product from <p memberof Pred(j)>
                        of <(PPOUT sub p + AVOUT sub p)> *
                      ...