Re: [RFC] New SSA variable mapping infrastructure

["Richard Guenther" <richard dot guenther at gmail dot com>]

On 11/7/07, Alexandre Oliva <aoliva@redhat.com> wrote:
> On Oct  3, 2007, "Richard Guenther" <richard.guenther@gmail.com> wrote:
>
> > During RTL optimization a reference or placeholder DECL from the
> > sets of associated variables will make var-tracking work as before.
> > Only at the time we write out debug information we will need to go
> > back to the variable sets and create copies of the variable location
> > lists for each of the variable in the associated set.  (fingers crossing,
> > this is all pure speculation)
>
> 'fraid this won't work.  Different SSA versions of the same variable
> can get coalesced or otherwise combined into different codegen
> variables, so you'd have to expand the individual tracking before or
> during var-tracking, such that it can do the propagation correctly.
>
> > Note that as opposed to the DEBUG_STMT/INSN approach this is _not_
> > a way we can conveniently cause values to be preserved that would
> > otherwise be deleted.
>
> The DEBUG_STMT/INSN doesn't do this, actually.  It doesn't (and can't)
> preserve values that would be deleted.  It must only keep track of
> what is still around, if it is.  The main difference with your
> approach is that you lose track of the point of assignment, so you
> might be extending inappropriately the life of a variable, or causing
> it to hold values at points that would be very surprising to users,
> even if they are defensible.  For an example, see
> http://gcc.gnu.org/ml/gcc/2007-11/msg00176.html

I see.  I have an example as well (complete, so you can actually compile it):

int foo(int i, int j)
{
  int l = j + i * 10;
  int k = i * 10;
  return l + k;
}

here we have a redundant computation of i * 10, and at the moment GCC choses
to preserve D.1234 (a temporary) rather than k, which we could generate debug
information for.

Up until 057t.phiprop the IL looks like the following (and no bitmaps with extra
names or whatsoever have been generated as no information is lost yet):

SSA variable maps:
7 SSA_NAMEs, 0 with variable map
with average 0.000 variables (0 max)

foo (i, j)
{
  int k;
  int l;
  int D.1546;
  int D.1545;

<bb 2>:
  D.1545_2 = i_1(D) * 10;
  l_4 = D.1545_2 + j_3(D);
  k_5 = i_1(D) * 10;
  D.1546_6 = l_4 + k_5;
  return D.1546_6;

}

now FRE obviously detects the redundancy and removes it.  The IL looks like
the following (still no extra annotaitons):

foo (i, j)
{
  int k;
  int l;
  int D.1546;
  int D.1545;

<bb 2>:
  D.1545_2 = i_1(D) * 10;
  l_4 = D.1545_2 + j_3(D);
  k_5 = D.1545_2;
  D.1546_6 = l_4 + k_5;
  return D.1546_6;

}

now more passes come along, but until 0.64t.dce3 nothing interesting happens.
At this point though, we are going to lose the stmt assigning to k_5:

;; Function foo (foo)

Processing copy relation k_5 = D.1545_2

SSA variable maps:
  D.1545_2: k
6 SSA_NAMEs, 1 with variable map
with average 1.000 variables (1 max)

foo (i, j)
{
  int l;
  int D.1546;
  int D.1545;

<bb 2>:
  D.1545_2 = i_1(D) * 10;
  l_4 = D.1545_2 + j_3(D);
  D.1546_6 = D.1545_2 + l_4;
  return D.1546_6;

}

and viola - we just processed the equivalency relation between the names
k_5 and D.1545_2 at the point it is lost from the IL (which conveniently can
be done in release_defs).  So right before expansion we end up with

foo (i, j)
{
  int D.1545;

<bb 2>:
  D.1545 = i * 10 E{ k };
  return (D.1545 + D.1545) + j;

}

(the extra annotation E{ k } says the stmt defines the name k).

So, actually all the code dealing with "updating" the on-the-side representation
is the following at the moment (testcases that won't work appreciated!):

Index: pointer_plus/gcc/tree-ssanames.c
===================================================================
*** pointer_plus.orig/gcc/tree-ssanames.c       2007-11-06
10:17:54.000000000 +0100
--- pointer_plus/gcc/tree-ssanames.c    2007-11-07 11:03:39.000000000 +0100
*************** release_defs (tree stmt)
*** 290,295 ****
--- 296,307 ----
       to garbage.  */
    gcc_assert (gimple_in_ssa_p (cfun));

+   /* If this was a copy stmt, save what the lhs knows about variables.  */
+   if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
+       && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == SSA_NAME
+       && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == SSA_NAME)
+     ssa_varmap_process_copy (stmt);
+
    FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
      if (TREE_CODE (def) == SSA_NAME)
        release_ssa_name (def);
Index: pointer_plus/gcc/tree-inline.c
===================================================================
*** pointer_plus.orig/gcc/tree-inline.c 2007-11-06 10:17:54.000000000 +0100
--- pointer_plus/gcc/tree-inline.c      2007-11-06 10:17:58.000000000 +0100
*************** setup_one_parameter (copy_body_data *id,
*** 1502,1507 ****
--- 1502,1513 ----
          || is_gimple_min_invariant (rhs))
        && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def))
      {
+       /* This remembers the parameters name.  It should not lose any
+        interesting information as the variable mapping from the param
+        from inside the inlined function should be empty (as DEFs definition
+        should be a default def).  */
+       if (TREE_CODE (rhs) == SSA_NAME)
+       ssa_varmap_add_var (rhs, SSA_NAME_VAR (def));
        insert_decl_map (id, def, rhs);
        return;
      }

(that's tree-level only of course and minus the infrastructure parts obviously).

I'll reply to the large mail later - that'll take me some time ;)  I'm
also preparing
posting of the current state of patches (or create a branch, I'm yet undecided -
the patches are quite small).

Richard.