advanced value range propagation for tree-ssa

advanced value range propagation for tree-ssa

[zhouyi zhou]

High, 
   Currently gcc can optimize following program by threading a block:
int
fn(int s, int w) {
  int i;

  i = 2;

  if (s)
   i = 1;

  if (s)
   printf("%d\n", i);

  return 0;
}

  While it cannot handle programs of following kind:
int
fn(int s, int w) {
  int i;

  i = 2;

  if (s)
   i = 1;

  if (w)
   goto out1;

  if (s)
   printf("%d\n", i);

out1:
  return 0;
}

The advanced value range propagation:
http://wiki.freebsd.org/ZhouyiZHOU?action=AttachFile&do=get&target=avrp.patch

nicely handles the above case

      2 (if s)
    /   \
   8     3
    \     |
     \__ 4----
        / 
      5(if s)  
    /  \
   6   10

The advanced value range propagation 
1) identify the candidate basic block pairs by 
recurively matching the dom son and dom parent (in our case block 5 and block 2 are
selected)
2) identiy the threadable edge pairs:
here edge pair 8-4 and 5-6, 3-4 and 5-10 are selected
3) thread the edges (duplicate the basic blocks between)
      2
    /  \
   8    3
   |     \
   4'-    4''-
   |      |
   5'     5''
  /       |
 6        10

The patch is being compiled and bootstraped on i686-linux m-32.
and passed most of regression test by make -k check (the not passed tests
 are caused the wrong configuration of my machine like libgmp and libmpfr)

The patch is rudimentary and very dirty written currently, I will clean it in the future

Your review and reply are greatly appreciated.
Zhouyi
and libmpfr

Re: advanced value range propagation for tree-ssa

[Jeff Law]

zhouyi zhou wrote:
> High, 
>    Currently gcc can optimize following program by threading a block:
> int
> fn(int s, int w) {
>   int i;
> 
>   i = 2;
> 
>   if (s)
>    i = 1;
> 
>   if (s)
>    printf("%d\n", i);
> 
>   return 0;
> }
> 
>   While it cannot handle programs of following kind:
> int
> fn(int s, int w) {
>   int i;
> 
>   i = 2;
> 
>   if (s)
>    i = 1;
> 
>   if (w)
>    goto out1;
> 
>   if (s)
>    printf("%d\n", i);
> 
> out1:
>   return 0;
> }
> 
> The advanced value range propagation:
> http://wiki.freebsd.org/ZhouyiZHOU?action=AttachFile&do=get&target=avrp.patch
> 
> nicely handles the above case
> 
>       2 (if s)
>     /   \
>    8     3
>     \     |
>      \__ 4----
>         / 
>       5(if s)  
>     /  \
>    6   10
> 
> The advanced value range propagation 
> 1) identify the candidate basic block pairs by 
> recurively matching the dom son and dom parent (in our case block 5 and block 2 are
> selected)
> 2) identiy the threadable edge pairs:
> here edge pair 8-4 and 5-6, 3-4 and 5-10 are selected
> 3) thread the edges (duplicate the basic blocks between)
>       2
>     /  \
>    8    3
>    |     \
>    4'-    4''-
>    |      |
>    5'     5''
>   /       |
>  6        10
> 
> The patch is being compiled and bootstraped on i686-linux m-32.
> and passed most of regression test by make -k check (the not passed tests
>  are caused the wrong configuration of my machine like libgmp and libmpfr)
> 
> The patch is rudimentary and very dirty written currently, I will clean it in the future
Kenny outlined an algorithm which should handle these cases rather 
easily at the GCC summit a few years back.   You might ask him for the 
slides from his opening presentation as they included the outline of the 
algorithm.

I did an implementation to compare it against the current edge threading 
code and while it didn't stack up too well, there were a few cases where 
Kenny's algorithm would find something optimizable, but the current 
threader would not.  Your example is one of those cases.

Implementation was fairly easy -- it might be easier to work from 
Kenny's algorithm than cleaning up your own.


Jeff
> 

Re: advanced value range propagation for tree-ssa

[Daniel Berlin]

On Sat, Mar 15, 2008 at 3:57 AM, zhouyi zhou <zhouzhouyi@gmail.com> wrote:
> High,
>    Currently gcc can optimize following program by threading a block:
>  int
>  fn(int s, int w) {
>   int i;
>
>   i = 2;
>
>   if (s)
>    i = 1;
>
>   if (s)
>    printf("%d\n", i);
>
>   return 0;
>  }
>
>   While it cannot handle programs of following kind:
>  int
>  fn(int s, int w) {
>   int i;
>
>   i = 2;
>
>   if (s)
>    i = 1;
>
>   if (w)
>    goto out1;
>
>   if (s)
>    printf("%d\n", i);
>
>  out1:
>   return 0;
>  }
>
>  The advanced value range propagation:
>  http://wiki.freebsd.org/ZhouyiZHOU?action=AttachFile&do=get&target=avrp.patch
>
>  nicely handles the above case
>
>       2 (if s)
>     /   \
>    8     3
>     \     |
>      \__ 4----
>         /
>       5(if s)
>     /  \
>    6   10
>
>  The advanced value range propagation
>  1) identify the candidate basic block pairs by
>  recurively matching the dom son and dom parent (in our case block 5 and block 2 are
>  selected)
>  2) identiy the threadable edge pairs:
>  here edge pair 8-4 and 5-6, 3-4 and 5-10 are selected
>  3) thread the edges (duplicate the basic blocks between)
>       2
>     /  \
>    8    3
>    |     \
>    4'-    4''-
>    |      |
>    5'     5''
>   /       |
>   6        10
>
>  The patch is being compiled and bootstraped on i686-linux m-32.
>  and passed most of regression test by make -k check (the not passed tests
>   are caused the wrong configuration of my machine like libgmp and libmpfr)
>
>  The patch is rudimentary and very dirty written currently, I will clean it in the future
>
>  Your review and reply are greatly appreciated.
>  Zhouyi
>  and libmpfr

You didn't svn add tree-avrp.c, so it doesn't appear in the patch :)
>

Re: advanced value range propagation for tree-ssa

[Zhouyi Zhou]

and thank you Daniel, I do forgot it,  the patch is updated as:
http://wiki.freebsd.org/ZhouyiZHOU?action=AttachFile&do=get&target=avrp20080316.patch
----- Original Message ----- 
From: "Daniel Berlin" <dberlin@dberlin.org>
To: "zhouyi zhou" <zhouzhouyi@gmail.com>
Cc: <gcc-patches@gcc.gnu.org>
Sent: Sunday, March 16, 2008 11:41 AM
Subject: Re: advanced value range propagation for tree-ssa
> You didn't svn add tree-avrp.c, so it doesn't appear in the patch :)

Re: advanced value range propagation for tree-ssa

[Zhouyi Zhou]

Nice! but who is kenny and I can't google him or the slides out :-)
(there are so many kenny hehe)


On 3/16/08, Jeff Law <law@redhat.com> wrote:
Kenny outlined an algorithm which should handle these cases rather 

Re: advanced value range propagation for tree-ssa

[zhouyi zhou]

There is some logic error in the patch, I will provide the corrected one later, sorry for the trouble :-)
On Sat, 15 Mar 2008 23:41:11 -0400
"Daniel Berlin" <dberlin@dberlin.org> wrote:


> >  http://wiki.freebsd.org/ZhouyiZHOU?action=AttachFile&do=get&target=avrp.patch

> 
> You didn't svn add tree-avrp.c, so it doesn't appear in the patch :)
> >
>