Fw: IPA Constant Propagation Optimization

[Razya Ladelsky <RAZYA at il dot ibm dot com>]

Hello,

Following our message ( http://gcc.gnu.org/ml/gcc/2003-11/msg01243.html )
regarding IPA constant propagation, we enclose the first draft 
of the optimization.
The algorithm would interact very closely with the intermodule 
infrastructure 
(the call graph and the parse trees)
We would appreciate any comment or suggestion.

Razya and Mircea


GCC IPA CONSTANT PROPAGATION OVERVIEW

Introduction

-IPA aim

  The IPA constant propagation will find which function's argument has the 

  same constant value in each invocation.

- IPA framework:

   Repository of all parse trees of the application kept in memory.
   IPA analysis is done on this all parse trees.
   Then the rest of the compilation is performed, one parse tree at a 
time.

   We use the call graph where each node represents a method.
   There is an edge from a node to another if one method may call the 
other.



Overview

Algorithm based on paper by Callahan and others.[3]

First phase - intraprocedural analysis
 Determines which actual arguments at each call site are constants or 
 a simple function of formal arguments of the caller - intraprocedural 
analysis.

Computation of Jump functions  -
Jump functions represents the value that is passes to each  actual 
argument 
by this callsite.

Example 1:
f (int a,  int b)
{
 cs1:  g (b,a);
 cs2:  g (a,1);
}
g (int c, int d)
{
}

J (cs1,c) = b
J (cs1,d) = a
J (cs2,c) = a
J (cs2,d) = 1

Example 2: (modify included)
f (int a,  int b)
{
 cs1:  g (b,a);
 a = .... ;      // a modified
 cs2:  g (a,1);
}
g (int c, int d)
{
}

J (cs1,c) = b
J (cs1,d) = NonConstant
J (cs2,c) = NonConstant
J (cs2,d) = 1

Computation of Mod information
Determines whether the formal being sent as actual argument has been 
modified.

Second phase - interprocedural analysis
Solving the interprocedural constant propagation problem

IPA algorithm

Each formal has cval which represents its value computed so far
(value : TOP, BOTTOM, constant_value)
The algoritm computes for all formal parameters in the program their cval 
value.
cval (formal f) will have a constant value if all callsites to this 
function have the same constant value passed to f and will have BOTTOM 
value 
otherwise.

while (worklist not empty)
    remove a method mt from worklist
    for all callsites cs of  mt
        for every actual argument i from [0. .callsiteGetArgCount]
              (type, info_type) = value of jump function for argument i in 
cs
              //type = const, means a constant was passed to i in cs. 
              //value is placed in info_type
              //type = formal,  means a formal was passed to i in cs.
                  //       index of the formal is placed in info_type
              //type = NonConstant

             //calculating the value passed to i in this callsite
             if(type == NonConstant)
                  new_cval = bottom;
             if (type == formal)
                  new_cval = get_cval(mt, info_type);
             if (type == const)
                  new_cval =   info_type;
             old_cval = get_cval  (callee, i);   //old value of i
             cval =   Meet (new_cval, old_cval);
                 //Meet(BOTTOM, x) = BOTTOM
                 //Meet(TOP,x) = x
                 //Meet(const_a,const_b) = BOTTOM , if const_a != const_b
              if (cval != old_cval)   // if there's a change
                 set _cval (callee, i, cval);
                  add callee to worklist;


Third phase
Propagates the constant-valued formals into the function

ipaCvalPropagate() - propagates the constant cvals to the parse trees.

Decisions

Flow insensitive analysis
Call site independent form of IPA constant  propagation
Pass through parameters jump function. (extension: expression of formals)
Intraprocedural modify (for C  it's enough, passing by value)


Bibliography

[1]Steven S. Muchnick, Advanced Compilation Design implementation
[2]Michael Wolfe, High Performance Compilers for Parallel Computing
[3]Challahan David, Keith D Cooper, Ken Kennedy, Linda Torczon, 
Interprocedural
 Constant Propagation, Comp86
[4]Grove, Dan and Linda Torczon. Inetrprocedural Constant Propagation : A 
Study
 of Jump Function Implementation, PLDI93