Re: [tree-ssa] must-alias analysis

[law at redhat dot com]

In message <1058187784.4973.106.camel@frodo.toronto.redhat.com>, Diego Novillo 
writes:
 >
 >Given this code:
 >
 >foo (int i)
 >{
 >  int *p = &i;
 >
 >  if (*p == 10)
 >    return i--;
 >
 >  *p = *p + 2;
 >  return *p;
 >}
 >
 >This patch allows the compiler to convert it to:
 >
 >foo (int i)
 >{
 >   if (i == 10)
 >     return 9;
 >
 >   i = i + 2;
 >   return i;
 >}
 >
 >Must-alias analysis works in four phases:
 >
 >     1. While the program is renamed into SSA form, the renamer
 >        propagates instances of &VAR values into pointer dereferences,
 >        yielding *&VAR operands which are folded into VAR.
 >     2. The previous step exposes new variables which may not be in SSA
 >        form.  If this happens, the SSA pass is run once more on the new
 >        exposed variables.
 >     3. Right after the SSA pass, we run dead code elimination to remove
 >        statements of the form 'PTR = &VAR;'.
 >     4. The must-alias pass will then scan the program looking for
 >        variables whose address is not needed anymore.  Those that match
 >        are removed from alias lists and are renamed into SSA as regular
 >        non-addressable variables.  This exposes the variables to all
 >        the usual optimizations.
Cool.  Do we make sure and clear TREE_ADDRESSABLE on these variables?

I _think_ that's the only missing step to get you to a point where you
never have to worry about put_var_into_stack and fixup_var_refs!   ie,
for a given automatic variable, we know before expanding into RTL whether
or not the variable is going to need a stack slot or not.

The reason this is important is fixup_var_refs can have a significant
negative impact on compile time performance.


 >In POOMA I found a larger difference.  Notably in LocalPatch.ii.  Not
 >only the new patch compiles faster, it produces significantly smaller
 >code.
In fact, I was going to suggest you look at POOMA.  

You might look and see if you're calling put_var_into_stack and 
fixup_var_refs*.  If you are, then we should fix that! :-)


 >We now do a full DCE pass right after SSA construction just to get the
 >'PTR = &VAR' statements removed.  We could probably get by with a very
 >simplistic pass that just looked for these assignments.  It would be
 >less powerful, but it would catch most of the cases we are interested
 >in.
I've always wanted to have a quick and dirty DCE pass that could be
run whenever we need it.  tree-ssa-dce.c is too heavyweight for that
kind of use.


 >We currently do not propagate ADDR_EXPR values that have been type
 >casted.  So, things like 'PTR = (type *)&VAR' are not propagated.  The
 >problem with this is that we would need to fold instances of *PTR into
 >(type)VAR, which would produce non-GIMPLE code and confuse the
 >optimizers.  I'm not quite sure how to handle this one.  I think it's
 >important because right now we are not handling code like this (from Joe
 >Buck's sample code a while back):
We've *REALLY* got to fix our handling of NOP_EXPRs.  REALLY REALLY REALLY.

They're getting in the way far too often.  I really want to see someone
tackle that problem.  I'm consistently running into cases where we either
miss a redundancy, generate a useless copy, etc because of the way we
handle NOP_EXPRs.


jeff