[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