[RFC] New SSA variable mapping infrastructure

[RFC] New SSA variable mapping infrastructure

[Richard Guenther]

[-- Attachment #1: Type: text/plain, Size: 3268 bytes --]

This is an introduction to the SSA varmap infrastructure.  The
infrastructure was added to address the shortcoming that we only
can remember one user variable (name) per SSA name.  This makes
producing accurate debug information difficult.

Variable mappings build on the requirement to associate user
variables (that is, VAR_DECLs or PARAM_DECLs represented by their UID)
with values that are computed in a program.  In SSA representation
conveniently values can be mapped to SSA names which yields both a
handle for an (unchanging) value and a location for its definition.

SSA names have one associated variable, their SSA_NAME_VAR.  The
ability is added to on demand adding further variables to an SSA name
via a bitmap that is stored in a hashtable mapping SSA name version
to a bitmap of variable UIDs that at some point in the program give
a name to the SSA names value.

Throughout optimization the variable mapping of a SSA name changes
in the following occasions:
 - The SSA name is deleted.  In this case the variable mapping is
   deleted as well.
 - The SSA name is copied to another SSA name.  This relates both
   SSA names and their variable mapping becomes the union of both
   variable mappings.

New SSA names get their variable mappings initialized by either
based off an existing user variable, being initialized by copying
from another SSA name or by being defined as a result of a PHI
operation.  In the latter case its variable mapping is the
intersection of all variable mappings of the PHI arguments.

Unless we start creating/writing debug information for DECLs early,
we need to get hold of the DECLs referenced in the variable mappings.
This is done by a separate hashtable indexed by the DECL uids to not
artificially keep the referenced var list big.

At the time of going out-of SSA we need to attach the variable mapping
to the SSA name defining statement.  This is not yet implemented and
TER may require to attach the information to expression nodes instead.

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)

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.

Note that the implementation detail that bitmaps are used is subject
to change dependent on statistical analysis how many variables are
in the mappings for typical programs.  For C I expect this number
to be pretty low making bitmaps a high overhead solution.  For C++
the story may be different.

Note that in the current implementation only the places where we
clearly lose information (DCE of a copy and substituting an inlined
PARAM_DECL for its argument) are "fixed".  The idea is to run a
(yet unimplemented) propagation pass just before out-of SSA instead
of keeping the sets propagated always.

I'll continue working on this, but any comments are welcome.  Please
also consider the different approach from Alexandre.

Thanks,
Richard.

[-- Attachment #2: debug-varmap --]
[-- Type: application/octet-stream, Size: 26237 bytes --]

2007-10-03  Richard Guenther  <rguenther@suse.de>

	* bitmap.h (struct int_bitmap_map): Declare.
	(int_bitmap_map_eq): Likewise.
	(int_bitmap_map_hash): Likewise.
	* bitmap.c (int_bitmap_map_eq): New function.
	(int_bitmap_map_hash): Likewise.
	* function.h (struct function): Add varmap_hash, varmap_vars
	and varmap_obstack members.
	* tree-ssanames.c (release_ssa_name): Call ssa_varmap_release.
	(release_defs): Process a copy for updating variable mappings.
	(ssa_varmap_lookup): New function.
	(ssa_varmap_set): Likewise.
	(ssa_varmap_replace): Likewise.
	(ssa_varmap_release): Likewise.
	(ssa_varmap_add_ref): Likewise.
	(ssa_varmap_get_ref): Likewise.
	(ssa_varmap_process_copy_1): Likewise.
	(ssa_varmap_process_copy): Likewise.
	(ssa_varmap_add_var): Likewise.
	(ssa_varmap_process_phi): Likewise.
	(ssa_varmap_process_all): Likewise.
	(print_ssa_varmap): Likewise.
	* function.c (allocate_struct_function): Initialize varmap members.
	* tree-dfa.c (referenced_var_lookup): Do not ICE on non-existing
	vars.
	* tree-dump.c (struct dump_option_value_in): Add vars modifier.
	* tree-inline.c (setup_one_parameter): Add the decl of the param
	to the argument SSA_NAME varmap.
	* tree-pass.h (TDF_VARS): Define.
	* tree-pretty-print.c (print_varmap): New helper function.
	(dump_generic_node): Call it on defs and return expressions.
	* tree.h (ssa_varmap_lookup): Declare.
	(ssa_varmap_add_ref): Likewise.
	(ssa_varmap_get_ref): Likewise.
	(ssa_varmap_process_copy_1): Likewise.
	(ssa_varmap_process_copy): Likewise.
	(ssa_varmap_add_var): Likewise.
	(ssa_varmap_process_phi): Likewise.
	(ssa_varmap_process_all): Likewise.
	(print_ssa_varmap): Likewise.
	* passes.c (execute_function_todo): Print variable mapping
	info if requested.

Index: trunk/gcc/bitmap.c
===================================================================
*** trunk.orig/gcc/bitmap.c	2007-10-03 13:15:56.000000000 +0200
--- trunk/gcc/bitmap.c	2007-10-03 13:47:01.000000000 +0200
*************** bitmap_hash (const_bitmap head)
*** 1969,1972 ****
--- 1969,1988 ----
    return (hashval_t)hash;
  }
  
+ /* Equality function for uid to bitmap map.  */
+ 
+ int int_bitmap_map_eq (const void *va, const void *vb)
+ {
+   const struct int_bitmap_map *a = (const struct int_bitmap_map *) va;
+   const struct int_bitmap_map *b = (const struct int_bitmap_map *) vb;
+   return (a->uid == b->uid);
+ }
+ 
+ /* Hash value for uid to bitmap map.  */
+ 
+ unsigned int int_bitmap_map_hash (const void *item)
+ {
+   return ((const struct int_bitmap_map *)item)->uid;
+ }
+ 
  #include "gt-bitmap.h"
Index: trunk/gcc/bitmap.h
===================================================================
*** trunk.orig/gcc/bitmap.h	2007-10-03 13:12:04.000000000 +0200
--- trunk/gcc/bitmap.h	2007-10-03 13:46:31.000000000 +0200
*************** bmp_iter_and_compl (bitmap_iterator *bi,
*** 580,583 ****
--- 580,591 ----
         bmp_iter_and_compl (&(ITER), &(BITNUM));				\
         bmp_iter_next (&(ITER), &(BITNUM)))
  
+ struct int_bitmap_map {
+   int uid;
+   bitmap map;
+ };
+ 
+ int int_bitmap_map_eq (const void *va, const void *vb);
+ unsigned int int_bitmap_map_hash (const void *item);
+ 
  #endif /* GCC_BITMAP_H */
Index: trunk/gcc/function.h
===================================================================
*** trunk.orig/gcc/function.h	2007-10-03 12:05:54.000000000 +0200
--- trunk/gcc/function.h	2007-10-03 19:05:02.000000000 +0200
*************** along with GCC; see the file COPYING3.  
*** 23,28 ****
--- 23,29 ----
  
  #include "tree.h"
  #include "hashtab.h"
+ #include "bitmap.h"
  
  /* Stack of pending (incomplete) sequences saved by `start_sequence'.
     Each element describes one pending sequence.
*************** struct function GTY(())
*** 322,327 ****
--- 323,336 ----
    /* The variables unexpanded so far.  */
    tree unexpanded_var_list;
  
+   /* The mapping of SSA_NAMEs to user variables.  The varmap hashtable is
+      indexed by the SSA_NAME version and contains bitmaps that contain
+      variable declaration UIDs allocated from the varmap obstack.
+      The vars hashtable keeps a reference to all used DECLs.  */
+   htab_t GTY((skip)) varmap_hash;
+   htab_t GTY((param_is (struct int_tree_map))) varmap_vars;
+   bitmap_obstack varmap_obstack;
+ 
    /* Assembly labels for the hot and cold text sections, to
       be used by debugger functions for determining the size of text
       sections.  */
Index: trunk/gcc/tree-ssanames.c
===================================================================
*** trunk.orig/gcc/tree-ssanames.c	2007-10-03 12:05:34.000000000 +0200
--- trunk/gcc/tree-ssanames.c	2007-10-03 19:20:45.000000000 +0200
*************** along with GCC; see the file COPYING3.  
*** 26,31 ****
--- 26,32 ----
  #include "ggc.h"
  #include "tree-flow.h"
  #include "tree-pass.h"
+ #include "diagnostic.h"
  
  /* Rewriting a function into SSA form can create a huge number of SSA_NAMEs,
     many of which may be thrown away shortly after their creation if jumps
*************** unsigned int ssa_name_nodes_reused;
*** 67,72 ****
--- 68,75 ----
  unsigned int ssa_name_nodes_created;
  #endif
  
+ static void ssa_varmap_release (tree var);
+ 
  /* Initialize management of SSA_NAMEs.  */
  
  void
*************** release_ssa_name (tree var)
*** 177,182 ****
--- 180,188 ----
    if (!var)
      return;
  
+   /* Remove variable mapping for this name.  */
+   ssa_varmap_release (var);
+ 
    /* Never release the default definition for a symbol.  It's a
       special SSA name that should always exist once it's created.  */
    if (SSA_NAME_IS_DEFAULT_DEF (var))
*************** 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);
*************** replace_ssa_name_symbol (tree ssa_name, 
*** 305,310 ****
--- 317,682 ----
    TREE_TYPE (ssa_name) = TREE_TYPE (sym);
  }
  
+ bitmap
+ ssa_varmap_lookup (tree name)
+ {
+   struct int_bitmap_map x;
+   struct int_bitmap_map **loc;
+ 
+   x.uid = SSA_NAME_VERSION (name);
+   loc = (struct int_bitmap_map **)
+ 	htab_find_slot_with_hash (cfun->varmap_hash, &x,
+  				  SSA_NAME_VERSION (name), NO_INSERT);
+   if (!loc)
+     return NULL;
+   return (*loc)->map;
+ }
+ 
+ static void
+ ssa_varmap_set (tree name, bitmap map)
+ {
+   struct int_bitmap_map x;
+   struct int_bitmap_map **loc;
+ 
+   x.uid = SSA_NAME_VERSION (name);
+   loc = (struct int_bitmap_map **)
+ 	htab_find_slot_with_hash (cfun->varmap_hash, &x,
+  				  SSA_NAME_VERSION (name), INSERT);
+   if (!*loc)
+     {
+       /* ???  We need to free this memory somewhere.  */
+       *loc = XNEW (struct int_bitmap_map);
+       (*loc)->uid = SSA_NAME_VERSION (name);
+     }
+   /* ???  If we had a reference counter on bitmaps we could eventually
+      free the old (*loc)->map.  */
+   (*loc)->map = map;
+ }
+ 
+ static void
+ ssa_varmap_replace (tree name, bitmap map)
+ {
+   struct int_bitmap_map x;
+   struct int_bitmap_map **loc;
+ 
+   x.uid = SSA_NAME_VERSION (name);
+   loc = (struct int_bitmap_map **)
+ 	htab_find_slot_with_hash (cfun->varmap_hash, &x,
+  				  SSA_NAME_VERSION (name), INSERT);
+   if (!*loc)
+     {
+       /* ???  We need to free this memory somewhere.  */
+       *loc = XNEW (struct int_bitmap_map);
+       (*loc)->uid = SSA_NAME_VERSION (name);
+       (*loc)->map = BITMAP_ALLOC (&cfun->varmap_obstack);
+     }
+   bitmap_copy ((*loc)->map, map);
+ }
+ 
+ /* Releases the variable mapping information for SSA_NAME var.  */
+ 
+ static void
+ ssa_varmap_release (tree var)
+ {
+   struct int_bitmap_map x;
+   struct int_bitmap_map **loc;
+ 
+   x.uid = SSA_NAME_VERSION (var);
+   loc = (struct int_bitmap_map **)
+ 	htab_find_slot_with_hash (cfun->varmap_hash, &x,
+  				  SSA_NAME_VERSION (var), NO_INSERT);
+   if (loc)
+     htab_remove_elt_with_hash (cfun->varmap_hash, &x, SSA_NAME_VERSION (var));
+ }
+ 
+ /* Reference the variable VAR used in variable mappings.
+    ???  Do this only if creating debug information.  */
+ 
+ void
+ ssa_varmap_add_ref (tree var)
+ {
+   struct int_tree_map in;
+   struct int_tree_map **loc;
+ 
+   in.uid = DECL_UID (var);
+   in.to = var;
+   loc = (struct int_tree_map **)
+ 	htab_find_slot_with_hash (cfun->varmap_vars, &in,
+ 				  DECL_UID (var), INSERT);
+   if (*loc)
+     return;
+ 
+   *loc = GGC_NEW (struct int_tree_map);
+   (*loc)->uid = DECL_UID (var);
+   (*loc)->to = var;
+ }
+ 
+ /* Get hands on the DECL stored by UID.  */
+ 
+ tree
+ ssa_varmap_get_ref (int uid)
+ {
+   struct int_tree_map in;
+   struct int_tree_map **loc;
+ 
+   in.uid = uid;
+   loc = (struct int_tree_map **)
+ 	htab_find_slot_with_hash (cfun->varmap_vars, &in,
+ 				  uid, NO_INSERT);
+   if (!loc)
+     return referenced_var (uid);
+ 
+   return (*loc)->to;
+ }
+ 
+ /* Update the two SSA_NAMEs variable map appearing in the copy
+    relation LHS = RHS.  */
+ 
+ void
+ ssa_varmap_process_copy_1 (tree lhs, tree rhs)
+ {
+   bitmap lhs_vars, rhs_vars;
+ 
+   if (dump_file && dump_flags & TDF_VARS)
+     {
+       fprintf (dump_file, "Processing copy relation ");
+       print_generic_expr (dump_file, lhs, 0);
+       fprintf (dump_file, " = ");
+       print_generic_expr (dump_file, rhs, 0);
+       fprintf (dump_file, "\n");
+     }
+ 
+   /* We cannot blindly exchange an artificial vars ssa_name variable
+      with another as this may create overlapping life-ranges.  So we
+      also cannot assume that artificial vars do not have a variable map.  */
+ 
+   /* Instead we merge variable maps if available or add the variable
+      uids of non-artificial variables to the maps.  */
+   lhs_vars = ssa_varmap_lookup (lhs);
+   rhs_vars = ssa_varmap_lookup (rhs);
+   if (lhs_vars && rhs_vars)
+     {
+       bitmap_ior_into (lhs_vars, rhs_vars);
+       ssa_varmap_set (rhs, lhs_vars);
+     }
+   else if (lhs_vars
+ 	   && !rhs_vars && !DECL_ARTIFICIAL (SSA_NAME_VAR (rhs)))
+     {
+       bitmap_set_bit (lhs_vars, DECL_UID (SSA_NAME_VAR (rhs)));
+       ssa_varmap_set (rhs, lhs_vars);
+     }
+   else if (!lhs_vars && !DECL_ARTIFICIAL (SSA_NAME_VAR (lhs))
+ 	   && rhs_vars)
+     {
+       bitmap_set_bit (rhs_vars, DECL_UID (SSA_NAME_VAR (lhs)));
+       ssa_varmap_set (lhs, rhs_vars);
+     }
+   else if (SSA_NAME_VAR (lhs) != SSA_NAME_VAR (rhs)
+ 	   && !DECL_ARTIFICIAL (SSA_NAME_VAR (rhs))
+ 	   && !DECL_ARTIFICIAL (SSA_NAME_VAR (lhs)))
+     {
+       bitmap tmp = BITMAP_ALLOC (&cfun->varmap_obstack);
+       bitmap_set_bit (tmp, DECL_UID (SSA_NAME_VAR (lhs)));
+       bitmap_set_bit (tmp, DECL_UID (SSA_NAME_VAR (rhs)));
+       ssa_varmap_set (lhs, tmp);
+       ssa_varmap_set (rhs, tmp);
+     }
+ }
+ 
+ /* Update the two SSA_NAMEs variable map appearing in the copy
+    relation STMT.  */
+ 
+ void
+ ssa_varmap_process_copy (tree stmt)
+ {
+   gcc_assert (gimple_in_ssa_p (cfun)
+ 	      && TREE_CODE (stmt) == GIMPLE_MODIFY_STMT);
+ 
+   ssa_varmap_process_copy_1 (GIMPLE_STMT_OPERAND (stmt, 0),
+ 			     GIMPLE_STMT_OPERAND (stmt, 1));
+ }
+ 
+ /* Add a single variable VAR to the mapping of SSA_NAME NAME.  */
+ 
+ void
+ ssa_varmap_add_var (tree name, tree var)
+ {
+   bitmap lhs_vars;
+ 
+   if (dump_file && dump_flags & TDF_VARS)
+     {
+       fprintf (dump_file, "Adding variable ");
+       print_generic_expr (dump_file, var, 0);
+       fprintf (dump_file, " to SSA_NAME ");
+       print_generic_expr (dump_file, name, 0);
+       fprintf (dump_file, " map\n");
+     }
+ 
+   if (DECL_ARTIFICIAL (var))
+     return;
+ 
+   lhs_vars = ssa_varmap_lookup (name);
+   if (lhs_vars)
+     bitmap_set_bit (lhs_vars, DECL_UID (var));
+   else if (SSA_NAME_VAR (name) != var)
+     {
+       bitmap tmp = BITMAP_ALLOC (&cfun->varmap_obstack);
+       if (!DECL_ARTIFICIAL (SSA_NAME_VAR (name)))
+         bitmap_set_bit (tmp, DECL_UID (SSA_NAME_VAR (name)));
+       bitmap_set_bit (tmp, DECL_UID (var));
+       ssa_varmap_set (name, tmp);
+     }
+ 
+   ssa_varmap_add_ref (var);
+ }
+ 
+ /* Update the PHI_RESULTs variable map of STMT based on the PHI arguments.  */
+ 
+ void
+ ssa_varmap_process_phi (tree stmt)
+ {
+   tree lhs;
+   bitmap arg_vars;
+   bitmap tmp;
+   ssa_op_iter i;
+   use_operand_p use;
+   bool first_p;
+ 
+   gcc_assert (gimple_in_ssa_p (cfun)
+ 	      && TREE_CODE (stmt) == PHI_NODE);
+ 
+   if (MTAG_P (SSA_NAME_VAR (PHI_RESULT (stmt))))
+     return;
+ 
+   /* A PHI nodes result represents the intersection of all decls of
+      the PHI arguments.  */
+   tmp = BITMAP_ALLOC (&cfun->varmap_obstack);
+   first_p = true;
+   FOR_EACH_PHI_ARG (use, stmt, i, SSA_OP_USE)
+     {
+       tree op = USE_FROM_PTR (use);
+ 
+       /* Look up vars for the argument.  If it is the first variable
+ 	 we visit, initialize the temporary map with its map.  */
+       arg_vars = ssa_varmap_lookup (op);
+       if (arg_vars)
+         {
+ 	  if (first_p)
+ 	    bitmap_copy (tmp, arg_vars);
+ 	  else
+ 	    bitmap_and_into (tmp, arg_vars);
+ 	}
+       else
+ 	{
+ 	  if (first_p
+ 	      && !DECL_ARTIFICIAL (SSA_NAME_VAR (op)))
+ 	    bitmap_set_bit (tmp, DECL_UID (SSA_NAME_VAR (op)));
+ 	  else if (!bitmap_bit_p (tmp, DECL_UID (SSA_NAME_VAR (op))))
+ 	    {
+ 	      bitmap_clear (tmp);
+ 	      break;
+ 	    }
+ 	}
+ 
+       if (bitmap_empty_p (tmp))
+         break;
+       first_p = false;
+     }
+ 
+   /* Clearing the PHI results bit first makes the following easier.  */
+   lhs = PHI_RESULT (stmt);
+   bitmap_clear_bit (tmp, DECL_UID (SSA_NAME_VAR (lhs)));
+ 
+   /* The result is now the argument intersection.  If that is empty
+      there is nothing to do.  */
+   if (bitmap_empty_p (tmp))
+     {
+       BITMAP_FREE (tmp);
+       return;
+     }
+ 
+   /* Otherwise re-add the UID from the PHI result var and replace the
+      map.  Note this by purpose affects all shared copies.  */
+   if (!DECL_ARTIFICIAL (SSA_NAME_VAR (lhs)))
+     bitmap_set_bit (tmp, DECL_UID (SSA_NAME_VAR (lhs)));
+   ssa_varmap_replace (lhs, tmp);
+   BITMAP_FREE (tmp);
+ }
+ 
+ /* Scan all stmts in a function, updating and propagating variable
+    maps.
+    ???  We want to do this in dominator order.  */
+ 
+ void
+ ssa_varmap_process_all (void)
+ {
+   basic_block bb;
+ 
+   FOR_EACH_BB (bb)
+     {
+       block_stmt_iterator bsi;
+       tree phi;
+ 
+       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+         ssa_varmap_process_phi (phi);
+ 
+       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+         {
+           tree stmt = bsi_stmt (bsi);
+           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);
+         }
+     }
+ }
+ 
+ /* Print variable maps to FILE.  */
+ 
+ void
+ print_ssa_varmap (FILE *file)
+ {
+   int live_ssa_names = 0, with_map = 0, max_vars = 0, total_vars = 0;
+   unsigned int i;
+ 
+   fprintf (file, "\nSSA variable maps:\n");
+   for (i = 0; i < num_ssa_names; ++i)
+     {
+       tree name = ssa_name (i);
+       int n = 0;
+       bitmap_iterator bi;
+       unsigned int i;
+       bitmap vars;
+       if (!name)
+         continue;
+       live_ssa_names++;
+       vars = ssa_varmap_lookup (name);
+       if (!vars)
+         continue;
+       with_map++;
+       fprintf (file, "  ");
+       print_generic_expr (file, name, 0);
+       fprintf (file, ": ");
+       EXECUTE_IF_SET_IN_BITMAP (vars, 0, i, bi)
+ 	{
+ 	  tree var = ssa_varmap_get_ref (i);
+ 	  n++;
+ 	  if (var)
+ 	    print_generic_expr (file, var, 0);
+ 	  else
+ 	    fprintf (file, "%u", i);
+ 	  fprintf (file, " ");
+ 	}
+       total_vars += n;
+       if (n > max_vars)
+ 	max_vars = n;
+       fprintf (file, "\n");
+     }
+   fprintf (file, "%d SSA_NAMEs, %d with variable map\n"
+ 	   "with average %.3f variables (%d max)\n\n", live_ssa_names,
+ 	   with_map, total_vars / (float)with_map, max_vars);
+ }
+ 
  /* Return SSA names that are unused to GGC memory.  This is used to keep
     footprint of compiler during interprocedural optimization.
     As a side effect the SSA_NAME_VERSION number reuse is reduced
Index: trunk/gcc/function.c
===================================================================
*** trunk.orig/gcc/function.c	2007-10-03 13:58:15.000000000 +0200
--- trunk/gcc/function.c	2007-10-03 19:21:27.000000000 +0200
*************** along with GCC; see the file COPYING3.  
*** 65,70 ****
--- 65,71 ----
  #include "df.h"
  #include "timevar.h"
  #include "vecprim.h"
+ #include "tree-flow.h"
  
  #ifndef LOCAL_ALIGNMENT
  #define LOCAL_ALIGNMENT(TYPE, ALIGNMENT) ALIGNMENT
*************** allocate_struct_function (tree fndecl)
*** 3911,3916 ****
--- 3912,3924 ----
        /* Assume all registers in stdarg functions need to be saved.  */
        cfun->va_list_gpr_size = VA_LIST_MAX_GPR_SIZE;
        cfun->va_list_fpr_size = VA_LIST_MAX_FPR_SIZE;
+ 
+       /* Initialize the variable mapping.  */
+       bitmap_obstack_initialize (&cfun->varmap_obstack);
+       cfun->varmap_hash = htab_create (7, int_bitmap_map_hash,
+ 				       int_bitmap_map_eq, NULL);
+       cfun->varmap_vars = htab_create_ggc (7, int_tree_map_hash,
+ 					   int_tree_map_eq, NULL);
      }
  
    invoke_set_current_function_hook (fndecl);
Index: trunk/gcc/tree-dfa.c
===================================================================
*** trunk.orig/gcc/tree-dfa.c	2007-10-03 14:36:30.000000000 +0200
--- trunk/gcc/tree-dfa.c	2007-10-03 14:36:47.000000000 +0200
*************** referenced_var_lookup (unsigned int uid)
*** 639,645 ****
    in.uid = uid;
    h = (struct int_tree_map *)
  	htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid);
!   gcc_assert (h || uid == 0);
    if (h)
      return h->to;
    return NULL_TREE;
--- 639,645 ----
    in.uid = uid;
    h = (struct int_tree_map *)
  	htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid);
!   /* ???  gcc_assert (h || uid == 0); */
    if (h)
      return h->to;
    return NULL_TREE;
Index: trunk/gcc/tree-dump.c
===================================================================
*** trunk.orig/gcc/tree-dump.c	2007-10-03 13:59:43.000000000 +0200
--- trunk/gcc/tree-dump.c	2007-10-03 14:00:32.000000000 +0200
*************** static const struct dump_option_value_in
*** 825,830 ****
--- 825,831 ----
    {"uid", TDF_UID},
    {"stmtaddr", TDF_STMTADDR},
    {"memsyms", TDF_MEMSYMS},
+   {"vars", TDF_VARS},
    {"all", ~(TDF_RAW | TDF_SLIM | TDF_LINENO | TDF_TREE | TDF_RTL | TDF_IPA 
  	    | TDF_STMTADDR | TDF_GRAPH | TDF_DIAGNOSTIC)},
    {NULL, 0}
Index: trunk/gcc/tree-inline.c
===================================================================
*** trunk.orig/gcc/tree-inline.c	2007-10-03 15:47:28.000000000 +0200
--- trunk/gcc/tree-inline.c	2007-10-03 18:22:48.000000000 +0200
*************** setup_one_parameter (copy_body_data *id,
*** 1458,1463 ****
--- 1458,1473 ----
  	  || is_gimple_min_invariant (rhs))
        && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def))
      {
+ #if 0
+       /* This doesn't work as the SSA_NAMEs are from two different functions.
+ 	 ???  Add a cfun parameter to all ssa_varmap functions.  */
+       if (TREE_CODE (rhs) == SSA_NAME)
+ 	ssa_varmap_process_copy_1 (def, rhs);
+ #endif
+       /* This remembers the parameters name but loses its variable mapping
+ 	 from inside the inlined function.  */
+       if (TREE_CODE (rhs) == SSA_NAME)
+ 	ssa_varmap_add_var (rhs, SSA_NAME_VAR (def));
        insert_decl_map (id, def, rhs);
        return;
      }
Index: trunk/gcc/tree-into-ssa.c
===================================================================
*** trunk.orig/gcc/tree-into-ssa.c	2007-10-03 14:40:49.000000000 +0200
--- trunk/gcc/tree-into-ssa.c	2007-10-03 15:42:52.000000000 +0200
*************** rewrite_into_ssa (void)
*** 2293,2298 ****
--- 2293,2301 ----
  
    fini_ssa_renamer ();
  
+   /* Update variable maps.
+   ssa_varmap_process_all (); */
+ 
    timevar_pop (TV_TREE_SSA_OTHER);
    return 0;
  }
Index: trunk/gcc/tree-pass.h
===================================================================
*** trunk.orig/gcc/tree-pass.h	2007-10-03 13:58:37.000000000 +0200
--- trunk/gcc/tree-pass.h	2007-10-03 13:59:38.000000000 +0200
*************** enum tree_dump_index
*** 73,78 ****
--- 73,80 ----
  #define TDF_DIAGNOSTIC	(1 << 15)	/* A dump to be put in a diagnostic
  					   message.  */
  
+ #define TDF_VARS	(1 << 16)	/* Dump variable mappings.  */
+ 
  extern char *get_dump_file_name (enum tree_dump_index);
  extern int dump_enabled_p (enum tree_dump_index);
  extern int dump_initialized_p (enum tree_dump_index);
Index: trunk/gcc/tree-pretty-print.c
===================================================================
*** trunk.orig/gcc/tree-pretty-print.c	2007-10-03 14:00:44.000000000 +0200
--- trunk/gcc/tree-pretty-print.c	2007-10-03 15:42:15.000000000 +0200
*************** dump_symbols (pretty_printer *buffer, bi
*** 435,440 ****
--- 435,467 ----
  }
  
  
+ static void
+ print_varmap (pretty_printer *buffer, tree name, int spc, int flags)
+ {
+   bitmap vars;
+   bitmap_iterator bi;
+   unsigned int i;
+ 
+   if (DECL_ARTIFICIAL (SSA_NAME_VAR (name)))
+     return;
+ 
+   vars = ssa_varmap_lookup (name);
+   if (!vars)
+     return;
+ 
+   pp_string (buffer, "\t{ ");
+   EXECUTE_IF_SET_IN_BITMAP (vars, 0, i, bi)
+     {
+       tree var = referenced_var (i);
+       if (var)
+ 	dump_generic_node (buffer, var, spc, flags, false);
+       else
+ 	pp_string (buffer, "[optimized out]");
+       pp_space (buffer);
+     }
+   pp_character (buffer, '}');
+ }
+ 
  /* Dump the node NODE on the pretty_printer BUFFER, SPC spaces of indent.
     FLAGS specifies details to show in the dump (see TDF_* in tree-pass.h).
     If IS_STMT is true, the object printed is considered to be a statement
*************** dump_generic_node (pretty_printer *buffe
*** 1099,1104 ****
--- 1126,1135 ----
        pp_space (buffer);
        dump_generic_node (buffer, GENERIC_TREE_OPERAND (node, 1), spc, flags,
  	  		 false);
+       if (flags & TDF_VARS
+ 	  && TREE_CODE (node) == GIMPLE_MODIFY_STMT
+ 	  && TREE_CODE (GIMPLE_STMT_OPERAND (node, 0)) == SSA_NAME)
+ 	print_varmap (buffer, GIMPLE_STMT_OPERAND (node, 0), spc, flags);
        break;
  
      case TARGET_EXPR:
*************** dump_generic_node (pretty_printer *buffe
*** 1594,1603 ****
  	  pp_space (buffer);
  	  if (TREE_CODE (op0) == MODIFY_EXPR
  	      || TREE_CODE (op0) == GIMPLE_MODIFY_STMT)
! 	    dump_generic_node (buffer, GENERIC_TREE_OPERAND (op0, 1),
! 			       spc, flags, false);
! 	  else
! 	    dump_generic_node (buffer, op0, spc, flags, false);
  	}
        break;
  
--- 1625,1635 ----
  	  pp_space (buffer);
  	  if (TREE_CODE (op0) == MODIFY_EXPR
  	      || TREE_CODE (op0) == GIMPLE_MODIFY_STMT)
! 	    op0 = GENERIC_TREE_OPERAND (op0, 1);
! 	  dump_generic_node (buffer, op0, spc, flags, false);
! 	  if (flags & TDF_VARS
! 	      && TREE_CODE (op0) == SSA_NAME)
! 	    print_varmap (buffer, op0, spc, flags);
  	}
        break;
  
Index: trunk/gcc/tree-ssa-propagate.c
===================================================================
*** trunk.orig/gcc/tree-ssa-propagate.c	2007-10-03 14:18:50.000000000 +0200
--- trunk/gcc/tree-ssa-propagate.c	2007-10-03 15:47:18.000000000 +0200
*************** replace_phi_args_in (tree phi, prop_valu
*** 1117,1123 ****
  	    }
  	}
      }
!   
    if (replaced && dump_file && (dump_flags & TDF_DETAILS))
      {
        fprintf (dump_file, "Folded PHI node: ");
--- 1117,1128 ----
  	    }
  	}
      }
! 
! #if 0
!   if (replaced)
!     ssa_varmap_process_phi (phi);
! #endif
! 
    if (replaced && dump_file && (dump_flags & TDF_DETAILS))
      {
        fprintf (dump_file, "Folded PHI node: ");
*************** substitute_and_fold (prop_value_t *prop_
*** 1265,1270 ****
--- 1270,1282 ----
  	      fold_stmt (bsi_stmt_ptr (i));
  	      stmt = bsi_stmt (i);
  
+ #if 0
+ 	      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);
+ #endif
+ 
                /* If we cleaned up EH information from the statement,
                   remove EH edges.  */
  	      if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
Index: trunk/gcc/tree.h
===================================================================
*** trunk.orig/gcc/tree.h	2007-10-03 14:07:25.000000000 +0200
--- trunk/gcc/tree.h	2007-10-03 19:18:53.000000000 +0200
*************** extern void duplicate_ssa_name_ptr_info 
*** 3893,3898 ****
--- 3893,3909 ----
  extern void release_ssa_name (tree);
  extern void release_defs (tree);
  extern void replace_ssa_name_symbol (tree, tree);
+ extern bitmap ssa_varmap_lookup (tree);
+ extern void ssa_varmap_process_copy_1 (tree, tree);
+ extern void ssa_varmap_process_copy (tree);
+ extern void ssa_varmap_add_var (tree, tree);
+ extern void ssa_varmap_process_phi (tree);
+ extern void ssa_varmap_process_all (void);
+ tree ssa_varmap_get_ref (int);
+ void ssa_varmap_add_ref (tree);
+ #ifdef BUFSIZ
+ extern void print_ssa_varmap (FILE *);
+ #endif
  
  #ifdef GATHER_STATISTICS
  extern void ssanames_print_statistics (void);
Index: trunk/gcc/passes.c
===================================================================
*** trunk.orig/gcc/passes.c	2007-10-03 18:00:13.000000000 +0200
--- trunk/gcc/passes.c	2007-10-03 18:01:06.000000000 +0200
*************** execute_function_todo (void *data)
*** 900,905 ****
--- 900,908 ----
        unsigned update_flags = flags & TODO_update_ssa_any;
        update_ssa (update_flags);
        cfun->last_verified &= ~TODO_verify_ssa;
+ 
+       if (dump_flags & TDF_VARS)
+ 	print_ssa_varmap (dump_file);
      }
    
    if (flags & TODO_rebuild_alias)

Re: [RFC] New SSA variable mapping infrastructure

[Michael Matz]

Hi,

On Wed, 3 Oct 2007, Richard Guenther 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)

Well, similar propagation and merging of sets need to happen for 
transformations on RTL create copy instructions.

One plan would be to add a new slot to all SET rtxs, which can represent 
the set of user variables associated with the LHS of that very SET (e.g. 
in a PARALLEL with multiple SETs it would be possible to associate 
different sets with the different LHSs).  The semantic would be that after 
_that_ insn the LHS contains all these user variables.  var-tracking would 
then nearly automagically create the right location notes.

An additional benefit is that not many places in RTL land would have to 
be changed to deal with those SETs.  Their runtime semantic is unchanged 
after all.  Some transformations (one offensive one is probably combine) 
simply need to deal with the additional information to preserve it.

> 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.

From my p.o.v. this aspect of better debug information for some use-cases 
should not be part of general improvements to debug info improvement.  
Forcing some values to be live will inevitably inhibit some 
transformations and therefore optimizations, and hence should only be done 
when really requested by the user.  Otherwise our "-g should not change 
code" dogma (which I agree with) would force us to generally switch off 
some optimizations even without -g, and that I don't want.

So forcing values live should be done by a separate mean, e.g. an 
artificial volatile instruction which uses that value.


Ciao,
Michael.

Re: [RFC] New SSA variable mapping infrastructure

[Paolo Bonzini]

> SSA names have one associated variable, their SSA_NAME_VAR.  The
> ability is added to on demand adding further variables to an SSA name
> via a bitmap that is stored in a hashtable mapping SSA name version
> to a bitmap of variable UIDs that at some point in the program give
> a name to the SSA names value.
> 
> Throughout optimization the variable mapping of a SSA name changes
> in the following occasions:
>  - The SSA name is deleted.  In this case the variable mapping is
>    deleted as well.
>  - The SSA name is copied to another SSA name.  This relates both
>    SSA names and their variable mapping becomes the union of both
>    variable mappings.

Looks like a perfect job for union-find (aka partition.c in libiberty), 
though it would waste memory (4 bytes) for every deleted SSA name.

Paolo

Re: [RFC] New SSA variable mapping infrastructure

[Alexandre Oliva]

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

-- 
Alexandre Oliva         http://www.lsd.ic.unicamp.br/~oliva/
FSF Latin America Board Member         http://www.fsfla.org/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}

Re: [RFC] New SSA variable mapping infrastructure

[Alexandre Oliva]

On Oct  4, 2007, Michael Matz <matz@suse.de> wrote:

> One plan would be to add a new slot to all SET rtxs,

Yuck, too much memory overhead even if no debug info is requested.
Notes with an index or pointer to indicate which set they refer to
would probably be better.

> The semantic would be that after 
> _that_ insn the LHS contains all these user variables.

This is imprecise, not only in terms of point of assignment, but also
in terms of which loc lists should be an lvalue and which should be
rvalues.  When the same LHS has the value for multiple variables, it
probably *is* only one of them, and it holds a copy of the others.
You don't want a debugger user that tries to tell the debugger to
modify variable a, that had been copied from b, and end up modifying
b.  We should be able to denote this somehow.  And no, I don't have a
complete answer for this yet, but I do have some thoughts.

> var-tracking would then nearly automagically create the right
> location notes.

> An additional benefit is that not many places in RTL land would have to 
> be changed to deal with those SETs.

You heavily underestimate the use of emit_move_insn().  Each of these
is a point that would require at least some investigation to tell
whether it needs adjusting:

% grep -nH -e emit_move_insn *.[ch] | wc -l
317

and then, there's reload, that might need to be taught to annotate the
copies it makes.

And, for this, I do have a solution, and it might actually help
alleviate the need for adjusting reload, but not necessarily other
uses of emit_move_insn().  It's the DF-globalized cselib analysis I
mentioned elsewhere
(http://gcc.gnu.org/ml/gcc-patches/2007-10/msg00160.html, bullet 4),
that uses the new debug annotations as basis to propagate location
information about user variables backward and forward, based on
locations that contain equivalent values.  It still doesn't fully
answer the question of how to determine where the lvalue location of a
variable is at any point, if any, though.

-- 
Alexandre Oliva         http://www.lsd.ic.unicamp.br/~oliva/
FSF Latin America Board Member         http://www.fsfla.org/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}

Re: [RFC] New SSA variable mapping infrastructure

[Richard Guenther]

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.

Re: [RFC] New SSA variable mapping infrastructure

[Alexandre Oliva]

On Nov  7, 2007, "Richard Guenther" <richard.guenther@gmail.com> wrote:

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

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

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

In this case, there's not much harm done in annotating the assignment
to D.1545 as an assignment to k.  It's close enough, even in the same
block.  But what if it wasn't?  What if k had a value before, that is
live into the separate basic block?  What if the assignment is
conditional?

And what happened to l?

Consider:

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

  if (i < j) {
    k = i * 10;
    breakpoint1();
  } else
    breakpoint2();
  }

  breakpoint3();

  return l + k;
}

Given your infrastructure, if I set breakpoints in the empty
uninlinable breakpoint* functions, go up a frame and print k, what
will you get, assuming the optimized code just before out-of-ssa ends
up looking like this:

int foo(int i, int j) {
  int D;
  int k;

 <bb 2>:
  D_2 = i_1(D) * 10; /* E { k } ? */
  if (i_1(D) < j_4(D))
    goto <bb 3>;
  else
    goto <bb 4>;

 <bb 3>:
   breakpoint1();
   goto <bb 5>;

 <bb 4>:
   breakpoint2();
   goto <bb 5>;

 <bb 5>:
   # k_3 = PHI<D(3), 0(4)>;
   breakpoint3();
   return j_4(D) + D_2 + k_3;
}

-- 
Alexandre Oliva         http://www.lsd.ic.unicamp.br/~oliva/
FSF Latin America Board Member         http://www.fsfla.org/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}

Re: [RFC] New SSA variable mapping infrastructure

[Richard Guenther]

On 11/7/07, Alexandre Oliva <aoliva@redhat.com> wrote:
> On Nov  7, 2007, "Richard Guenther" <richard.guenther@gmail.com> wrote:
>
> > int foo(int i, int j)
> > {
> >   int l = j + i * 10;
> >   int k = i * 10;
> >   return l + k;
> > }
>
> > foo (i, j)
> > {
> >   int D.1545;
>
> > <bb 2>:
> >   D.1545 = i * 10 E{ k };
> >   return (D.1545 + D.1545) + j;
> > }
>
> In this case, there's not much harm done in annotating the assignment
> to D.1545 as an assignment to k.  It's close enough, even in the same
> block.  But what if it wasn't?  What if k had a value before, that is
> live into the separate basic block?  What if the assignment is
> conditional?
>
> And what happened to l?

l is no longer a value that is computed (we do not compute D.1545 + j, but
only D.1545 + D.1545 and the final sum.  This is what I mean with "preserving
values" - values that are no longer computed do not have their values retained)

> Consider:
>
> int foo(int i, int j) {
>   int l = j + i * 10;
>   int k = 0;
>
>   if (i < j) {
>     k = i * 10;
>     breakpoint1();
>   } else
>     breakpoint2();
>   }
>
>   breakpoint3();
>
>   return l + k;
> }
>
> Given your infrastructure, if I set breakpoints in the empty
> uninlinable breakpoint* functions, go up a frame and print k, what
> will you get, assuming the optimized code just before out-of-ssa ends
> up looking like this:
>
> int foo(int i, int j) {
>   int D;
>   int k;
>
>  <bb 2>:
>   D_2 = i_1(D) * 10; /* E { k } ? */
>   if (i_1(D) < j_4(D))
>     goto <bb 3>;
>   else
>     goto <bb 4>;
>
>  <bb 3>:
>    breakpoint1();
>    goto <bb 5>;
>
>  <bb 4>:
>    breakpoint2();
>    goto <bb 5>;
>
>  <bb 5>:
>    # k_3 = PHI<D(3), 0(4)>;
>    breakpoint3();
>    return j_4(D) + D_2 + k_3;
> }

While in general if you have a single location and multiple names for it there
are things you cannot work around (but you can just declare them as designed
as such).  For example if in register 'ax' you have a value that has names 'a'
and 'd', what happens if in the debugger you set 'a'?  Of course the
value of 'd'
also changes - 'a' and 'd' have been CSEd and we certainly don't want to undo
this transformation.

Now onto the above case.  What we end up with after tree optimizations in
the moment is:

foo (i, j)
{
  int k.5;
  int k;

<bb 2>:
  k.5 = i * 10 E{ k };
  if (i < j)
    goto <bb 3>;
  else
    goto <bb 4>;

<bb 3>:
  k = k.5;
  goto <bb 5>;

<bb 4>:
  k = 0;

<bb 5>:
  return (j + k.5 E{ l }) + k;

}

That is, i * 10 has the name 'k' (yes, computed unconditionally - but it is also
life in the relevant block), we still compute 'l' in this case, as j +
k.5, and the
final value in 'k' after the merge will be either 0 or i * 10.

I believe you cannot do better here unless you limit optimization.

With VTA I see (final_cleanup again):

foo (i, j)
{
  int k.5;
  int k;

<bb 2>:
  k.5 = i * 10;
  # DEBUG l optimized away;
  # DEBUG k = 0;
  if (i < j)
    goto <bb 3>;
  else
    goto <bb 4>;

<bb 3>:
  k = k.5;
  goto <bb 5>;

<bb 4>:
  k = 0;

<bb 5>:
  # DEBUG k = k;
  return (j + k.5) + k;

}

so you lost 'l' (I didn't ;)) and from what I see you might in this
case avoid making
the value i * 10 globally associated to 'k' because you track constants in debug
expressions?  (I didn't investigate what this means to debug information).  So
let's avoid having k constant in one path:

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

I get

foo (i, j)
{
  int k.5;
  int k;

<bb 2>:
  k.5 = i * 10 E{ k };
  if (i < j)
    goto <bb 3>;
  else
    goto <bb 4>;

<bb 3>:
  k = k.5;
  goto <bb 5>;

<bb 4>:
  k = j + i;

<bb 5>:
  return (j + k.5 E{ l }) + k;

}

which is basically the same situation as before.  With VTA we get

foo (i, j)
{
  int k.5;
  int k;

<bb 2>:
  k.5 = i * 10;
  # DEBUG l optimized away;
  # DEBUG k optimized away;
  if (i < j)
    goto <bb 3>;
  else
    goto <bb 4>;

<bb 3>:
  k = k.5;
  goto <bb 5>;

<bb 4>:
  k = j + i;

<bb 5>:
  # DEBUG k = k;
  return (j + k.5) + k;

}

which looks confusing somehow (it looks to me that some of the 'k' in DEBUG
exprs should be 'k.5'?)  But maybe you can explain what happens to what names
here?

Thanks,
Richard.

Re: [RFC] New SSA variable mapping infrastructure

[Alexandre Oliva]

On Nov  8, 2007, "Richard Guenther" <richard.guenther@gmail.com> wrote:

>> And what happened to l?

> l is no longer a value that is computed (we do not compute D.1545 +
> j, but only D.1545 + D.1545 and the final sum.  This is what I mean
> with "preserving values" - values that are no longer computed do not
> have their values retained)

So, you intentionally let it go, even though debug information could
encode it.  And, worse, you leave no note behind that the value of l
is no longer known at that point, so if l is retained elsewhere, debug
information will be emitted for it, but it will point at a location
that does not hold the value of l at all in the region where it was
optimized away.  That's bad.

> Now onto the above case.  What we end up with after tree optimizations in
> the moment is

Looks like you threw away the function calls.  That's cheating! :-)

Seriously, the whole point of my introducing those calls were to
expose additional obvious weaknesses in your design.

> foo (i, j)
> {
>   int k.5;
>   int k;

> <bb 2>:
>   k.5 = i * 10 E{ k };
>   if (i < j)
>     goto <bb 3>;
>   else
>     goto <bb 4>;

> <bb 3>:
>   k = k.5;
>   goto <bb 5>;

> <bb 4>:
>   k = 0;

> <bb 5>:
>   return (j + k.5 E{ l }) + k;

> }

> That is, i * 10 has the name 'k' (yes, computed unconditionally -
> but it is also life in the relevant block)

I don't care that it's live or that it's computed.  The question is
whether it makes any sense whatsoever to indicate, in debug
information, that the value of k in bb4 is in k.5, rather than zero.
That's an obvious bug to me.

> we still compute 'l' in this case,

I understood you were adding annotations only to SSA assignments.  The
presence of E{l} seems to contradict this.  So, what's missing from
your design description?

> I believe you cannot do better here unless you limit optimization.

> With VTA I see (final_cleanup again):

The VTA branch is work in progress.  We're discussing design, not
incomplete implementations.  It's just silly to point at raw food and
say "hey, your cooking recipe sucks!" ;-)

In my design, what I envision for the optimized foo() is:

foo (i, j)
{
  int T.1;
  int k;

<bb 2>:
  T.1 = i * 10;
  # DEBUG l = T.1;
  # DEBUG k = 0;
  if (i < j)
    goto <bb 3>;
  else
    goto <bb 4>;

<bb 3>:
  # DEBUG k = T.1;
  breakpoint1 ();
  k = T.1;
  goto <bb 5>;

<bb 4>:
  breakpoint2 ();

<bb 5>:
  # DEBUG k = k;
  breakpoint3 ();
  return (j + T.1) + k;
}

> so you lost 'l' (I didn't ;))

See?, it's there.  It's at least present in the debug stmts design,
and you haven't explained how you get it into the
bitmap-aside-to-SSA-assignments one.

> and from what I see you might in this case avoid making the value i
> * 10 globally associated to 'k' because you track constants in debug
> expressions?

The fact that it's constant is just a distraction.  See in the debug
annotation that 'k = 0' could be anything else, any other expression
live at that point.  And the value of k would be tracked starting from
that location, and any other locations holding that value, as long as
it remained available or k was assigned another value.

> which is basically the same situation as before.  With VTA we get

When the implementation in the VTA branch is complete such that it
matches the design, I expect to get something like this (starting from
your call-less foo(int,int)):

foo (i, j)
{
  int T.1;
  int k;

<bb 2>:
  T.1 = i * 10;
  # DEBUG l = j + T.1;
  # DEBUG k = j + i;
  if (i < j)
    goto <bb 3>;
  else
    goto <bb 4>;

<bb 3>:
  # DEBUG k = T.1;
  k = T.1;
  goto <bb 5>;

<bb 4>:
  k = j + i;

<bb 5>:
  # DEBUG k = k;
  return (j + T.1) + k;
}

>   # DEBUG k optimized away;

should have been 'k = j + i';

>   # DEBUG k = k;

> which looks confusing somehow (it looks to me that some of the 'k' in DEBUG
> exprs should be 'k.5'?)

Why?  k.5 doesn't model anything in the source level.  DEBUG_STMTS are
supposed to indicate that the value of a source-level concept (the
left-hand k) can be determined by computing a certain expression,
e.g., by adding the implementation arguments j and i in one case, or
by taking the value of the implementation variable k in the other.

> But maybe you can explain what happens to what names here?

See above.  Also, see the debug stmt in bb3 above, that refers to T.1
(which the compiler happens to name k.5).  Does it make sense to you
now?

If not, maybe you can explain why/where you think k.5 should be
mentioned.  Is that what you were expecting?  If not, perhaps there's
some misunderstanding as to what the debug stmts stand for.

-- 
Alexandre Oliva         http://www.lsd.ic.unicamp.br/~oliva/
FSF Latin America Board Member         http://www.fsfla.org/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}

Re: [RFC] New SSA variable mapping infrastructure

[Richard Guenther]

On Nov 8, 2007 6:25 PM, Alexandre Oliva <aoliva@redhat.com> wrote:
> On Nov  8, 2007, "Richard Guenther" <richard.guenther@gmail.com> wrote:
>
> >> And what happened to l?
>
> > l is no longer a value that is computed (we do not compute D.1545 +
> > j, but only D.1545 + D.1545 and the final sum.  This is what I mean
> > with "preserving values" - values that are no longer computed do not
> > have their values retained)
>
> So, you intentionally let it go, even though debug information could
> encode it.

No, the optimizers chose to.

>  And, worse, you leave no note behind that the value of l
> is no longer known at that point, so if l is retained elsewhere, debug
> information will be emitted for it, but it will point at a location
> that does not hold the value of l at all in the region where it was
> optimized away.  That's bad.

I have to think about this - as we don't yet generate debug
information out of this
I cannot verify if this is really true.

> > Now onto the above case.  What we end up with after tree optimizations in
> > the moment is
>
> Looks like you threw away the function calls.  That's cheating! :-)

Oh - I thought it was breakpoints, that is, what you'd debug, not
function calls.

> Seriously, the whole point of my introducing those calls were to
> expose additional obvious weaknesses in your design.
>
> > foo (i, j)
> > {
> >   int k.5;
> >   int k;
>
> > <bb 2>:
> >   k.5 = i * 10 E{ k };
> >   if (i < j)
> >     goto <bb 3>;
> >   else
> >     goto <bb 4>;
>
> > <bb 3>:
> >   k = k.5;
> >   goto <bb 5>;
>
> > <bb 4>:
> >   k = 0;
>
> > <bb 5>:
> >   return (j + k.5 E{ l }) + k;
>
> > }
>
> > That is, i * 10 has the name 'k' (yes, computed unconditionally -
> > but it is also life in the relevant block)
>
> I don't care that it's live or that it's computed.  The question is
> whether it makes any sense whatsoever to indicate, in debug
> information, that the value of k in bb4 is in k.5, rather than zero.
> That's an obvious bug to me.

I don't see what you do different here (but I also don't see what is
your complaint - I'll have to think about it).

> > we still compute 'l' in this case,
>
> I understood you were adding annotations only to SSA assignments.  The
> presence of E{l} seems to contradict this.  So, what's missing from
> your design description?

Well, the missing piece is that we obviously go out-of-ssa before we
expand to RTL
and we even to TER inbetween.  So inbetween those we transfer the information
attached to the SSA_NAME definition sites to the expressions computed (in the
end tuples promise to do expansion out of SSA form, so we can remove this
intermediate step).  So for less confusion I should have posted the
state just before
going out of SSA form.

> > I believe you cannot do better here unless you limit optimization.
>
> > With VTA I see (final_cleanup again):
>
> The VTA branch is work in progress.  We're discussing design, not
> incomplete implementations.  It's just silly to point at raw food and
> say "hey, your cooking recipe sucks!" ;-)

Nor is our approach a complete implementation ;)  But of course the easies
judgement of a concept is to look at what the (current state of) code does.

> In my design, what I envision for the optimized foo() is:
>
> foo (i, j)
> {
>   int T.1;
>   int k;
>
> <bb 2>:
>   T.1 = i * 10;
>   # DEBUG l = T.1;
>   # DEBUG k = 0;
>   if (i < j)
>     goto <bb 3>;
>   else
>     goto <bb 4>;
>
> <bb 3>:
>   # DEBUG k = T.1;
>   breakpoint1 ();
>   k = T.1;
>   goto <bb 5>;
>
> <bb 4>:
>   breakpoint2 ();
>
> <bb 5>:
>   # DEBUG k = k;
>   breakpoint3 ();
>   return (j + T.1) + k;
> }
>
> > so you lost 'l' (I didn't ;))
>
> See?, it's there.  It's at least present in the debug stmts design,
> and you haven't explained how you get it into the
> bitmap-aside-to-SSA-assignments one.

I see.  As we only track names at the point of the definition (that
is, the point the
get "live"), but not the point they die (I don't see you do this - but
you obviously
have redundant "becoming live" points, like DEBUG k = k (?)), we hope
(or believe...)
that var-tracking will do the lifetime analysis that avoids what you
call "wrong debug
information".

It would be nice to have a gdb testcase testing for not having this wrong debug
information - at least that would make it easier to understand your point.

> > and from what I see you might in this case avoid making the value i
> > * 10 globally associated to 'k' because you track constants in debug
> > expressions?
>
> The fact that it's constant is just a distraction.  See in the debug
> annotation that 'k = 0' could be anything else, any other expression
> live at that point.  And the value of k would be tracked starting from
> that location, and any other locations holding that value, as long as
> it remained available or k was assigned another value.

So, the thing you have as RHS of # DEBUG name = is an arbitrary expression?
(just trying to understand)

> > which is basically the same situation as before.  With VTA we get
>
> When the implementation in the VTA branch is complete such that it
> matches the design, I expect to get something like this (starting from
> your call-less foo(int,int)):
>
> foo (i, j)
> {
>   int T.1;
>   int k;
>
> <bb 2>:
>   T.1 = i * 10;
>   # DEBUG l = j + T.1;
>   # DEBUG k = j + i;

Ok, so I see GIMPLE expressions.  Are they required to be gimple?

>   if (i < j)
>     goto <bb 3>;
>   else
>     goto <bb 4>;
>
> <bb 3>:
>   # DEBUG k = T.1;
>   k = T.1;
>   goto <bb 5>;
>
> <bb 4>:
>   k = j + i;
>
> <bb 5>:
>   # DEBUG k = k;

What's this?  Why does it say k = k?

>   return (j + T.1) + k;
> }
>
> >   # DEBUG k optimized away;
>
> should have been 'k = j + i';
>
> >   # DEBUG k = k;
>
> > which looks confusing somehow (it looks to me that some of the 'k' in DEBUG
> > exprs should be 'k.5'?)
>
> Why?  k.5 doesn't model anything in the source level.  DEBUG_STMTS are
> supposed to indicate that the value of a source-level concept (the
> left-hand k) can be determined by computing a certain expression,
> e.g., by adding the implementation arguments j and i in one case, or
> by taking the value of the implementation variable k in the other.
>
> > But maybe you can explain what happens to what names here?
>
> See above.  Also, see the debug stmt in bb3 above, that refers to T.1
> (which the compiler happens to name k.5).  Does it make sense to you
> now?
>
> If not, maybe you can explain why/where you think k.5 should be
> mentioned.  Is that what you were expecting?  If not, perhaps there's
> some misunderstanding as to what the debug stmts stand for.

It's just that "k = k" looks like redundant information.  Of course k is the
same as k(?)  Or is it merely the location of this DEBUG expression that
makes the difference?

Thanks,
Richard.

Re: [RFC] New SSA variable mapping infrastructure

[Alexandre Oliva]

On Nov  8, 2007, "Richard Guenther" <richard.guenther@gmail.com> wrote:

> On Nov 8, 2007 6:25 PM, Alexandre Oliva <aoliva@redhat.com> wrote:
>> On Nov  8, 2007, "Richard Guenther" <richard.guenther@gmail.com> wrote:
>> 
>> >> And what happened to l?
>> 
>> > l is no longer a value that is computed (we do not compute D.1545 +
>> > j, but only D.1545 + D.1545 and the final sum.  This is what I mean
>> > with "preserving values" - values that are no longer computed do not
>> > have their values retained)
>> 
>> So, you intentionally let it go, even though debug information could
>> encode it.

> No, the optimizers chose to.

And it also chose (on its own, without any influence whatsoever from
the GCC developers ;-) to not keep the information around that would
be needed to add this piece of info to the compiler output, in the
debug info sections.

>> And, worse, you leave no note behind that the value of l
>> is no longer known at that point, so if l is retained elsewhere, debug
>> information will be emitted for it, but it will point at a location
>> that does not hold the value of l at all in the region where it was
>> optimized away.  That's bad.

> I have to think about this - as we don't yet generate debug
> information out of this
> I cannot verify if this is really true.

You don't mark the point at which l goes away.  The debug info
generator can't count on magic to find that out where it should emit
the label for the end of the range where 'l' is available.  The
information must be there somewhere.

>> > Now onto the above case.  What we end up with after tree optimizations in
>> > the moment is
>> 
>> Looks like you threw away the function calls.  That's cheating! :-)

> Oh - I thought it was breakpoints, that is, what you'd debug, not
> function calls.

I wrote it was functions on which you'd set breakpoints in a debugger,
go up one frame and print the value of the variable.

>> I don't care that it's live or that it's computed.  The question is
>> whether it makes any sense whatsoever to indicate, in debug
>> information, that the value of k in bb4 is in k.5, rather than zero.
>> That's an obvious bug to me.

> I don't see what you do different here (but I also don't see what is
> your complaint - I'll have to think about it).

What I do different is that bb4 succeeds bb2, and in bb2 there's a
note stating that user variable k holds the value 0, and this will
make to debug information.

>> > I believe you cannot do better here unless you limit optimization.
>> 
>> > With VTA I see (final_cleanup again):
>> 
>> The VTA branch is work in progress.  We're discussing design, not
>> incomplete implementations.  It's just silly to point at raw food and
>> say "hey, your cooking recipe sucks!" ;-)

> Nor is our approach a complete implementation ;)  But of course the easies
> judgement of a concept is to look at what the (current state of) code does.

Except when the code is not there for you to look at.

The fact that there is a branch with some code doesn't mean the design
is implemented in there.  Only a small portion of the design is
implemented there.  The most important piece is still missing, and
that's the bit that uses the notes, carried and updated throughout
compilation, to determine where each user variable is located at each
point in the program.  I'm talking about the dataflow-globalized cse
analysis in var-tracking that I mentioned in my initial writeup of
what the patch was about: bullet 3 in
http://gcc.gnu.org/ml/gcc-patches/2007-10/msg00160.html

None of this is implemented in the branch, but it's a necessary part
to get correct debug information.

> I see.  As we only track names at the point of the definition (that
> is, the point the get "live")

even if they get live for a completely different set of variables, and
the value might not even be assigned to the variable of interest but
your debug information will make it seem like it does...

> but not the point they die (I don't see you do this

That's what the cse is going to accomplish.  It's going to use the
debug notes as fixed points, and propagate information up and down
from them about alternate locations for a variable.  Such that, for
example, if you have, before var-tracking:


(set (reg 1) (mem (reg 2)))

(set (reg 5) (reg 1))

(set (reg 3) (reg 1))

(var_location "x" (reg 3))

(set (reg 1) (mem (reg 4)))

(set (mem (reg 4)) (reg 3))

(set (mem (reg 2)) (reg 1))

(set (reg 3) (mem/v (reg 6)))

(var_location "x" (reg 3))

(use (reg 3))

(clobber (reg 3))


we know that at the point of the var_location debug_insn, reg 3 holds
the value of x, and that x is assigned to that value at that point.

But since we've done cse, we know at that point that the value of x,
from the point of assignment on, is also available in (reg 1), in (mem
(reg 2)) and in (reg 5).

But when (reg 1) is modified, it no longer holds the value of x.

Then, since (reg 3) is copied to (mem (reg 4)), we know x is available
there as well.

And when (mem (reg 2)) is modified, we know it no longer contains the
value of x.  Now only (reg 3) holds the value of x.

But then, when (reg 3) is modified, we know it no longer holds the
value of x either, so the old value of x is only available in (reg 5)
and (mem (reg 4)).

But then, the var_location debug_insn right after that says that (reg
3) does indeed contain the value of "x", so we forget all other
locations of x, and now (reg 3) is it (the volatile mem isn't a usable
location, for it's volatile).

The use there is what keeps (reg 3) alive such that it can be
referenced in the var_location expression.  If it wasn't there, x
would have been regarded as optimized away at that point, and a dummy
expression in the var_location would reflect this.

The clobber says that (reg 3) is modified in unpredictable ways
removes (reg 3) from the set of available locations for x.  None
remain, so after the clobber we'd mark x as optimized away.


> - but you obviously have redundant "becoming live" points, like
> DEBUG k = k (?)),

There's nothing redundant in here.  It's a link between two separate
namespaces: k in the user level source representation, and an
arbitrary variable that the compiler chose to also name k.  In my
design, there's no implied correspondence between gimple register
variables and user variables.  Such implementation variable names are
completely arbitrary, and they're useful only for compiler dumps.  All
debug information for variables that qualify as gimple registers is
generated based on debug insns.  Addressable variables get different
treatment, for they do have a fixed location, so we don't have to work
so hard to generate correct debug information for them.

> we hope (or believe...)  that var-tracking will do the lifetime
> analysis that avoids what you call "wrong debug information".

It can't unless you somehow tell it that a certain location, after
modification, no longer reflects the value of a variable.  But your
model doesn't seem to make room for this.

> It would be nice to have a gdb testcase testing for not having this
> wrong debug information - at least that would make it easier to
> understand your point.

Consider this:

int foo(int i, int j) {
  int l;
  int k = 0;

  l = function_that_returns_5 ();
  breakpoint0 ();
  asm ("" : : "X" (l)); /* ensure it's live */

  l = j + i * 10;

  if (i < j) {
    k = i * 10;
    breakpoint1();
  } else
    breakpoint2();
  }

  breakpoint3();

  return l + k;
}

Set a breakpoint in all 3 breakpoint functions and, when you reach
them, go up one frame and print k and l.

With your design, the optimizations that completely drop the second
assignment to l, leaving nothing behind to mark the death of the
previous value, debug information will likely indicate that variable l
still holds value 5 through to the end of the function, unless the
location holding it is reused for some other purpose, the only case in
which current var-tracking would realize l is no longer available
there.

> So, the thing you have as RHS of # DEBUG name = is an arbitrary expression?

Yup.  Pretty much anything.  Whether it's representable in dwarf or
not is something for the debug info back end to figure out.  If it's
not, it's perfectly legitimate for it to say "I can't represent the
location of this variable".

>> # DEBUG l = j + T.1;
>> # DEBUG k = j + i;

> Ok, so I see GIMPLE expressions.  Are they required to be gimple?

Nope.  Anything, really.  Requiring them to be gimple would limit the
ability to express complex value computations, necessary after various
optimizations, without any actual benefit.

>> # DEBUG k = k;

> What's this?  Why does it say k = k?

See above.  It means the implementation gimple register k now holds
the value of the user variable k.

> It's just that "k = k" looks like redundant information.

That's just because them appear to be the same k.  Maybe using '=' was
misleading.  Would it help if I changed it to '=>' or 'is at' or some
such?

> Of course k is the same as k(?)

Once you start optimizing the program, any expectations that gimple
registers match user variables with any precision are just feeble
hopes :-)

That's the whole point of the debug stmts: to provide strong
statements about the value a user variable is expected to hold at that
point in the program, such that we can mess however much we want with
implementation variables, without any fear of hampering debuggability.
Unless we mess with the debug notes themselves, that is.

-- 
Alexandre Oliva         http://www.lsd.ic.unicamp.br/~oliva/
FSF Latin America Board Member         http://www.fsfla.org/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}

Re: [RFC] New SSA variable mapping infrastructure

[Richard Guenther]

On 11/9/07, Alexandre Oliva <aoliva@redhat.com> wrote:
> On Nov  8, 2007, "Richard Guenther" <richard.guenther@gmail.com> wrote:
>
> > It would be nice to have a gdb testcase testing for not having this
> > wrong debug information - at least that would make it easier to
> > understand your point.
>
> Consider this:
>
> int foo(int i, int j) {
>   int l;
>   int k = 0;
>
>   l = function_that_returns_5 ();
>   breakpoint0 ();
>   asm ("" : : "X" (l)); /* ensure it's live */
>
>   l = j + i * 10;
>
>   if (i < j) {
>     k = i * 10;
>     breakpoint1();
>   } else
>     breakpoint2();
>   }
>
>   breakpoint3();
>
>   return l + k;
> }
>
> Set a breakpoint in all 3 breakpoint functions and, when you reach
> them, go up one frame and print k and l.
>
> With your design, the optimizations that completely drop the second
> assignment to l, leaving nothing behind to mark the death of the
> previous value, debug information will likely indicate that variable l
> still holds value 5 through to the end of the function, unless the
> location holding it is reused for some other purpose, the only case in
> which current var-tracking would realize l is no longer available
> there.

Right.  As optimization drops the second assignment to 'l' we only are
able to note that at the point we return from the function 'l' is computed
again:

foo (i, j)
{
  int k.6;
  int k;
  int l;

<bb 2>:
  l = function_that_returns_5 ();
  breakpoint0 ();
  __asm__ __volatile__(""::"X" l);
  k.6 = i * 10 E{ k };
  if (i < j)
    goto <bb 3>;
  else
    goto <bb 4>;

<bb 3>:
  breakpoint1 ();
  k = k.6;
  goto <bb 5>;

<bb 4>:
  breakpoint2 ();
  k = 0;

<bb 5>:
  breakpoint3 ();
  return (j + k.6 E{ l }) + k;

}

And you are right, with our design-proposal there is no way to say that at the
point of the second assignment to 'l' (even if that is removed), the
name 'l' shall
be no longer associated with the constant '5'.

So indeed, it is very likely that in the debugger you would be able to print
'l' and get 5 at all breakpoint locations.  'k' will also print as i *
10 at at least
breakpoint1() and breakpoint2() (it will be "correct" at
breakpoint3()).  Basically
the constraints we can force on debug information is only that at the point of
a use of a name the location information will be correct.  I also don't see how
you can solve this problem without retaining placeholders for each DCEd
instruction (which is what you do).  So yes, your approach is vastly superior
in the sense of creating correct debug information for optimized code.

What our approach basically does is to identify all names that a computed value
has at any point during program execution.  All flow-sensitive information that
is not tracked we hope to recover (I see it's not possible to recover
all of it).

So we're obviously going to finish our approach to a point where you can try
it (that is, run gdb sessions on the improved output) and then put it
on a branch.

Richard.

Re: [RFC] New SSA variable mapping infrastructure

[Alexandre Oliva]

On Nov  9, 2007, "Richard Guenther" <richard.guenther@gmail.com> wrote:

> What our approach basically does is to identify all names that a
> computed value has at any point during program execution.

I.e., you disregard pretty much all information as to where the value
gains each name, and as to where it ceases to have that name.  Do you
have any evidence that this can possibly get you better (not only more
complete, but also more correct) debug information than what we have
now?  The problem of non-concurrent uses being noted in debug info as
concurrent seems particularly serious to me (the mapping of c to both
x and y we debated before).

-- 
Alexandre Oliva         http://www.lsd.ic.unicamp.br/~oliva/
FSF Latin America Board Member         http://www.fsfla.org/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}

Re: [RFC] New SSA variable mapping infrastructure

[Richard Guenther]

On Nov 12, 2007 6:52 PM, Alexandre Oliva <aoliva@redhat.com> wrote:
> On Nov  9, 2007, "Richard Guenther" <richard.guenther@gmail.com> wrote:
>
> > What our approach basically does is to identify all names that a
> > computed value has at any point during program execution.
>
> I.e., you disregard pretty much all information as to where the value
> gains each name, and as to where it ceases to have that name.  Do you
> have any evidence that this can possibly get you better (not only more
> complete, but also more correct) debug information than what we have
> now?  The problem of non-concurrent uses being noted in debug info as
> concurrent seems particularly serious to me (the mapping of c to both
> x and y we debated before).

Yes.  What the approach basically addresses is that with it we can track
multiple variables for a single SSA_NAME.  This for example helps the
classical case with inlining where we now either remember the name of
the passed parameter or the name of the param decl of the function.

The second improvement we are implementing is that while we previously
lost track of names for values that are substituted during TER, we now
keep track of those.

It's an incremental improvement within the current scheme of generating
debug information, thereby addressing the most complained issues,
inlining and TER. And it also tries to avoid loosing names during
scalar optimizations.

It does not address any fundamental problems with the way we generate
debug info - all the fundamental weaknesses of the current approach are
retained (apart from the single variable per value limitation).

Richard.

Re: [RFC] New SSA variable mapping infrastructure

[Alexandre Oliva]

On Nov 13, 2007, "Richard Guenther" <richard.guenther@gmail.com> wrote:

> It's an incremental improvement within the current scheme of generating
> debug information,

For the record (in this thread), I dispute that it is an improvement
at all.

It might enable us to generate more information than we currently do,
but what good is that when the information is so often going to be
wrong?

No information is better than wrong information, so your scheme will
actually be a step backward in very many situations.

-- 
Alexandre Oliva         http://www.lsd.ic.unicamp.br/~oliva/
FSF Latin America Board Member         http://www.fsfla.org/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}

Re: [RFC] New SSA variable mapping infrastructure

[Richard Guenther]

On Nov 24, 2007 10:16 PM, Alexandre Oliva <aoliva@redhat.com> wrote:
> On Nov 13, 2007, "Richard Guenther" <richard.guenther@gmail.com> wrote:
>
> > It's an incremental improvement within the current scheme of generating
> > debug information,
>
> For the record (in this thread), I dispute that it is an improvement
> at all.

Fair enough.

> It might enable us to generate more information than we currently do,
> but what good is that when the information is so often going to be
> wrong?

I dispute that the information is so often going to be wrong in return.

> No information is better than wrong information, so your scheme will
> actually be a step backward in very many situations.

I don't think this is generally true, and it of course depends on how many
are the very many situations.

We're going to have the chance to evaluate two different approaches and
implementations, which is IMHO how open source (should) work.  After
the evaluation which should include maintainance issues of course there
are three options.  Take either approach or dismiss both.

At least I don't see an obvious winner yet.

Richard.