Re: [RFC] New SRA and early interprocedural SRA

[Martin Jambor <mjambor at suse dot cz>]

Hi,

On Fri, Feb 20, 2009 at 03:26:07PM -0800, Chris Lattner wrote:
>
> On Feb 20, 2009, at 11:39 AM, Martin Jambor wrote:
>
>>
>> I will be grateful for any comments and suggestions but please keep in
>> mind that this is still to large extent work in progress.  Also please
>> ignore  the ugly  hunks  in  passes.c, obviously  they  are there  for
>> development and  testing purposes only, specifically they  allow me to
>> test the early IPA-SRA on its own.
>
> This looks very interesting Martin.  Do you have some testcase that  
> demonstrate what this pass does?

Sorry for  the delay, I  do not know  how it happened but  two serious
flaws have  escaped my attention last  week and it took  me quite some
time to track down both of them.  Anyway, I am about to post out a new
version soon.

I assume you  are asking about the interprocedural  variant, since the
intraprocedural has  largely the same goals as  the current tree-sra.c
but is in fact simpler.

Well, yes, I have a few test cases, of course, and I guess I can share
the following two which are the less messy ones:

Consider the following file:
======================================================================
struct bovid
{
  float red;
  int green;
  void *blue;
};

static void
__attribute__((noinline))
print_stuff_1 (struct bovid cow, int z, struct bovid calf, long l)
{
  printf ("red: %f\nblue: %p\nblue again: %p\nl:%li\n", cow.red,
	  cow.blue, cow.blue, l);
}

static void
__attribute__((noinline))
print_stuff_2 (struct bovid *cow, int *z, struct bovid *calf, long *l)
{
  printf ("red: %f\nblue: %p\nblue again: %p\nl:%li\n", cow->red,
	  cow->blue, cow->blue, *l);
  cow->red++;
}


int main (int argc, char *argv[])
{
  struct bovid cow, calf;
  int i = 4;
  long l = 5;
  
  cow.red = 7.4;
  cow.green = 6;
  cow.blue = &cow;

  calf.red = 8.4;
  calf.green = 5;
  calf.blue = &cow;
  
  print_stuff_1 (cow, 4, calf, 2);
  print_stuff_2 (&cow, &i, &calf, &l);
  return 0;
}
======================================================================

I will attach the dump file produced  by the pass (if I do not forget)
but basically the following is happening:

Parameters z  and calf in  both print_stuff_[12] functions  are unused
and so they will be eliminated.

The red and blue are the only accessed components of the cow parameter
in both functions  too.  We should never be worse off  if we pass just
the two to  print_stuff_1 and so the cow parameter  is replaced by two
new  ones  representing  these   two  components.   All  uses  of  the
components are also replaced by the new corresponding parameters.  The
function prototype thus becomes:

  print_stuff_1 (float isra.14, void * isra.15, long int l);

and is called by a new sequence of statements:
  D.2316_1 = cow.red;
  D.2317_2 = cow.blue;
  print_stuff_1 (D.2316_1, D.2317_2, 2);

Cow  and  l  are passed  by  reference  to  print_stuff_2 and  so  the
situation  is more  complicated.  The  pass notices  that blue  is not
modified in  the function  and that it  cannot be  modified indirectly
before it is read (this is  currently determined only in a very simple
manner, we  hope to do  better on a-i  branch) and that cow  is always
dereferenced  (more on  this later).   Therefore it  can be  passed by
value rather than  by reference.  OTOH, the component  red is modified
and thus  it has to  be passed by  reference.  The cumulative  size of
these two proposed  new parameters is not bigger  than double the size
of the original pointer and there  is not more than two of them (these
limits are currently hard-coded but will become parameters) and so the
old parameter is  replaced by two such new  parameters.  The pass also
finds out  that l is also  always dereferenced and  never modified and
thus  it  replaces it  with  a  simple  int.  The  function  prototype
becomes:

  print_stuff_2 (float * isra.16, void * isra.17, long int isra.18)

(note  that even  though the  second parameter  is a  pointer  we have
actually eliminated  a level of indirection  here) and is  called by a
new sequence:

  D.2321_3 = cow.blue;
  print_stuff_2 (&cow.red, D.2321_3, l_6);

In order to see another issue which often prevents us from promoting a
by reference  parameter to  one passed directly  by value  (other than
directly modifying it) have a look at the following example:

======================================================================
static int
__attribute__((noinline))
ox (bool fail, struct bovid *cow)
{
  int r;
  if (fail)
    r = cow->red;
  else
    r = 0;
  return r;
}

int main (int argc, char *argv[])
{
  struct bovid cow;
  
  cow.red = 7.4;
  cow.green = 6;
  cow.blue = &cow;
  
  return ox ((argc > 3), NULL);
}
======================================================================

If we  moved dereferencing the NULL  parameter to the  caller we would
have introduced a segfault in an application which did not suffer from
it before.  Therefore we have to examine whether on each path from cal
to exit in the caller there  is a dereferencing statement.  We do this
by going up the dominator tree from the exit block and looking whether
there are any dereferences there.

If a by reference parameter has more ssa names, we only operate on the
default_def one, leaving the  other ones intact (well, not really, but
replacing them with a new variable rather than a parameter).

I hope these simple examples show what the pass does.  Please wait for
the new version if  you want to have a look at  the source, I will try
to send it out soon.

Martin

Attachment: remove.c.037t.eipa_sra
Description: Text document