[tree-ssa] Eliminating unnecessary variables during out-of-ssa

[tree-ssa] Eliminating unnecessary variables during out-of-ssa

[Andrew MacLeod]

Given the large number of variables which can exist, anything we can do
to reduce the number we need to look at during the out-of-ssa phase
would be a blessing.

As near as I can tell, all the PHI nodes which *define* dereferenced
variables are used purely for alaising placeholders and can be
eliminated.

Let me step back for a moment. I'll use ugly examples since they will
emphasize my point better :-)

The out of SSA pass only needs to rewrite real variables which occur in
code. Virtual operands do not occur in the actual statements being
rewritten. So given the stmt:

  #   (*tree_ssa_dump_flags.756)_59 = VDEF <(*tree_ssa_dump_flags.756)_50>;
  #   (*fndecl)_60 = VDEF <(*fndecl)_51>;
  #   (*globals)_61 = VDEF <(*globals)_52>;
  #   (*T.765)_62 = VDEF <(*T.765)_53>;
  #   (*entry_exit_blocks.766)_63 = VDEF <(*entry_exit_blocks.766)_54>;
  #   (*T.782)_64 = VDEF <(*T.782)_55>;
  #   (*def_blocks)_65 = VDEF <(*def_blocks)_56>;
  #   (*tree_ssa_dump_file)_66 = VDEF <(*tree_ssa_dump_file)_57>;
  #   .GLOBAL_VAR_67 = VDEF <.GLOBAL_VAR_49>;
  #   VUSE <(*tree_ssa_dump_flags.756)_50>;
  #   VUSE <(*fndecl)_51>;
  #   VUSE <(*globals)_52>;
  #   VUSE <(*T.765)_53>;
  #   VUSE <(*entry_exit_blocks.766)_54>;
  #   VUSE <(*T.782)_55>;
  #   VUSE <(*def_blocks)_56>;
  #   VUSE <(*tree_ssa_dump_file)_57>;
  #   VUSE <.GLOBAL_VAR_49>;
  tree_ssa_dump_flags.756_58 = &tree_ssa_dump_flags;


The only variable being rewritten here is 'tree_ssa_dump_flags.756_58'.
The rest is fluff as far as the out-of-ssa pass is concerned.

Currently, the out of SSA pass only looks at variables which occur in
either an operand USE or DEF, or in a PHI node. 

Clearly, an operand use or def will be rewritten, so they must all be
included. 

PHI nodes on the otherhand, are only important sometimes. Take for
example:

      #   .GLOBAL_VAR_1 = PHI <.GLOBAL_VAR_108(0), .GLOBAL_VAR_267(3)>;
      #   (*tree_ssa_dump_flags.756)_9 = PHI <(*tree_ssa_dump_flags.756)_87(0), (*tree_ssa_dump_flags.756)_260(3)>;
      #   i_22 = PHI <i_109(0), i_273(3)>;
      #   (*T.763)_24 = PHI <(*T.763)_103(0), (*T.763)_268(3)>;
      #   (*T.765)_28 = PHI <(*T.765)_104(0), (*T.765)_269(3)>;
      #   (*entry_exit_blocks.766)_32 = PHI <(*entry_exit_blocks.766)_105(0), (*entry_exit_blocks.766)_270(3)>;
      #   (*T.782)_36 = PHI <(*T.782)_106(0), (*T.782)_271(3)>;
      #   (*tree_ssa_dump_file)_43 = PHI <(*tree_ssa_dump_file)_107(0), (*tree_ssa_dump_file)_272(3)>;
      if (i_22 >= n_basic_blocks)

The only PHI element in this stmt that is needed is:
#   i_22 = PHI <i_109(0), i_273(3)>;

But notice that i_22 already occurs as a real def and as real uses in
one or more stmts, so its being considered already.

All of these other PHI nodes are adding variables which get put into the
variable list, but are all of them needed? If we can determine which
ones aren't needed, we can eliminate those PHIS from the program before
we build the out-of-ssa variable list, and then not do any unnecessary
work on them.

Currently, I dont think we need anything that has a derefernced variable
as a PHI_RESULT.

Here's my logic :-)

  #   (*p)_6 = VDEF <(*p)_5>;
  #   VUSE <p_4>;
  *p = 20;

This stmt only *uses* p_4. What we are really doing here is storing a
value into the memory location that p_4 points to. So the stmt is really
*p_4 = 20. There is no *def* of a variable in this stmt. The (*p)_6
represents the memory location which is being stored into, and we will
never actually rewrite that.. all we will ever rewrite is the store
using the pointer. When we go to read this value:
  
  #   VUSE <(*p)_6>;
  #   VUSE <p_4>;
  y_9 = *p;
we again have only a use of p_4, and the stmt is viewed as 
y_9 = *p_4

Since we never rewrite  something like (*p)_6, anything which is ussed
to compute it shouldn't matter either, so we can eliminate any PHI node
which defines a (*p)_x...

Its possible to have a derefernced value as an *argument* to a PHI which
has meaning, as long as the PHI_RESULT is used in a real stmt, or is
used in the calculation of a real value.

In particular, Ive seen copy propagation do the following:
     #   VUSE <T.6_12>;
      i_14 = (*T.6)_13
    };
  #   i_1 = PHI <i_6(0), (*T.6)_13(1)>;
  
so i_1 has a value of either i_6, or *T.6_12.  Note that again we are't
using the actual dereferenced variable version here, just the
dereferenced T.6_12 variable. So again this is in fact a use of T.6_12
rather than (*T.6)_13. If we need to insert a copy on this edge (which
we will), we'll be inserting  
   i_1 = *T.6_12


We can also throw away any PHI node which defines GLOBAL_VAR. That is
also purely used for aliasing. ie:
      #   .GLOBAL_VAR_2 = PHI <.GLOBAL_VAR_122(4), .GLOBAL_VAR_3(13)>;

can also be eliminated


I've done some preliminary tests and implementations, and it looks quite
promising. 

Can anyone thing of when we might actually need any of these variables
in the rewriting stage?

Andrew

Re: [tree-ssa] Eliminating unnecessary variables during out-of-ssa

[Andrew MacLeod]

On Mon, 2003-05-12 at 14:43, Daniel Berlin wrote:
> > Currently, I dont think we need anything that has a derefernced 
> > variable
> > as a PHI_RESULT.
> 
> For SSAPRE store movement and load movement, I need it.
> 
> In particular, i need the vdefs for load movement, and the uses/phi 
> results for store movement.
> 
> Otherwise, i can't tell when a load is possibly killed without 
> calculating the exact same info (in the case of vdefs), or the possible 
> insertion points for the store (that's what the PHI's give us).
> 
> There are other optimizations i'm working on (loop related) that need 
> this info, too.
> 
> Just because our basic opts don't need it, doesn't mean you should 
> remove it.
> Can't you just ignore it in out-of-ssa, rather than remove it 
> altogether?
> 

Of course you need them for those optimizations, otherwise we wouldn't
generate them in the first place.

After we go out of SSA form, we no longer have an SSA form, so no one
needs these things. All PHI nodes are deleted as part of the process. 

I was asking if anyone could think of a reason why we might need to keep
them during the out of SSA translation phase. I'm trying to identify a
way of reducing the number of PHI nodes that I have to look at, thus
reducing the number of variables which have to be examined during the
entire phase. 

Andrew

Re: [tree-ssa] Eliminating unnecessary variables during out-of-ssa

[Daniel Berlin]

> Currently, I dont think we need anything that has a derefernced 
> variable
> as a PHI_RESULT.

For SSAPRE store movement and load movement, I need it.

In particular, i need the vdefs for load movement, and the uses/phi 
results for store movement.

Otherwise, i can't tell when a load is possibly killed without 
calculating the exact same info (in the case of vdefs), or the possible 
insertion points for the store (that's what the PHI's give us).

There are other optimizations i'm working on (loop related) that need 
this info, too.

Just because our basic opts don't need it, doesn't mean you should 
remove it.
Can't you just ignore it in out-of-ssa, rather than remove it 
altogether?

--Dan

Re: [tree-ssa] Eliminating unnecessary variables during out-of-ssa

[Daniel Berlin]

On Monday, May 12, 2003, at 02:54  PM, Andrew MacLeod wrote:

> On Mon, 2003-05-12 at 14:43, Daniel Berlin wrote:
>>> Currently, I dont think we need anything that has a derefernced
>>> variable
>>> as a PHI_RESULT.
>>
>> For SSAPRE store movement and load movement, I need it.
>>
>> In particular, i need the vdefs for load movement, and the uses/phi
>> results for store movement.
>>
>> Otherwise, i can't tell when a load is possibly killed without
>> calculating the exact same info (in the case of vdefs), or the 
>> possible
>> insertion points for the store (that's what the PHI's give us).
>>
>> There are other optimizations i'm working on (loop related) that need
>> this info, too.
>>
>> Just because our basic opts don't need it, doesn't mean you should
>> remove it.
>> Can't you just ignore it in out-of-ssa, rather than remove it
>> altogether?
>>
>
> Of course you need them for those optimizations, otherwise we wouldn't
> generate them in the first place.
>
:P
> After we go out of SSA form, we no longer have an SSA form, so no one
> needs these things. All PHI nodes are deleted as part of the process.
>
You said "Can anyone thing of when we might actually need any of these 
variables
in the rewriting stage?"
I was confused, because i usually think of the rewriting stage as 
into-ssa, not out-of-ssa.
>

Re: [tree-ssa] Eliminating unnecessary variables during out-of-ssa

[Andrew MacLeod]

On Mon, 2003-05-12 at 15:42, Daniel Berlin wrote:
> 
> On Monday, May 12, 2003, at 02:54  PM, Andrew MacLeod wrote:
> 
> >
> > Of course you need them for those optimizations, otherwise we wouldn't
> > generate them in the first place.
> >
> :P
> > After we go out of SSA form, we no longer have an SSA form, so no one
> > needs these things. All PHI nodes are deleted as part of the process.
> >
> You said "Can anyone thing of when we might actually need any of these 
> variables
> in the rewriting stage?"
> I was confused, because i usually think of the rewriting stage as 
> into-ssa, not out-of-ssa.
> >
> 

:-). Sorry, I was originally going to attach the note to my out-of-ssa
status note, but decided it was long enough and made it a seperate note.
I just carried forward the same thoughts forward, so I can see how it
might be missing some information :-).

Sorry for the confusion. 

Andrew