[PATCH][varmap] Preserve variable names over out-of-ssa, TER and expansion

[Richard Guenther <rguenther at suse dot de>]

This is the (somewhat ugly) glue part that transitions the information
attached to SSA_NAMEs to the RTL representation which is the information
attached to SETs.

Unfortunately as we go out-of-ssa and do things like TER we need an
intermediate representation that is able to retain all information.  This
is done by creating a temporary map of expressions to the bitmap of
variable uids.  This is also one point of improvement over what we had
previously, where we just lost names for expressions that are TERed.

RTL expansion is also tricky in its current form, but a wrapper around
expand_expr_real seems to catch all interesting cases.

In the end we hope to get rid of the temporary representation at least
once we go to expansion out of SSA form.  But that's for the future.

Applied to var-mappings-branch.

Richard.

2007-11-07  Richard Guenther  <rguenther@suse.de>

	* function.h (struct function): Add varmap_exprmap member.
	* tree-ssanames.c (ssa_varmap_exprmap_lookup): New function.
	(ssa_varmap_exprmap_insert): Likewise.
	(ssa_varmap_build_exprmap): Likewise.
	* tree.h (ssa_varmap_exprmap_lookup): Likewise.
	(ssa_varmap_exprmap_insert): Likewise.
	(ssa_varmap_build_exprmap): Likewise.
	* tree-outof-ssa.c (replace_use_variable): Remember names
	for TERed expressions.
	(rewrite_trees): If available, associate
	the expressions with the bitmap of names.
	(remove_ssa_form): Associate expressions with bitmaps of names.
	(rewrite_out_of_ssa): Propagate names information.  Allocate
	map of expressions to names bitmaps.  Free SSA_NAME to decls
	bitmap.
	* expr.c (expand_expr_real): Rename to ...
	(expand_expr_real_x): ... this.
	(expand_expr_real): New wrapper initializing the expanded
	expressions target SET insns bitmap of names if possible.
	* cfgexpand.c (tree_expand_cfg): Delete expression to names
	bitmap after expansion.

Index: var-mappings-branch/gcc/tree-outof-ssa.c
===================================================================
*** var-mappings-branch.orig/gcc/tree-outof-ssa.c	2007-11-12 18:31:56.000000000 +0100
--- var-mappings-branch/gcc/tree-outof-ssa.c	2007-11-12 18:33:24.000000000 +0100
*************** replace_use_variable (var_map map, use_o
*** 559,567 ****
--- 559,579 ----
        int version = SSA_NAME_VERSION (var);
        if (expr[version])
          {
+ 	  bitmap vars;
  	  tree new_expr = GIMPLE_STMT_OPERAND (expr[version], 1);
  	  SET_USE (p, new_expr);
  
+ 	  /* For this replaced expression, record its names, if available.  */
+ 	  vars = ssa_varmap_lookup (var);
+ 	  if (!vars
+ 	      && !DECL_ARTIFICIAL (SSA_NAME_VAR (var)))
+ 	    {
+ 	      vars = BITMAP_GGC_ALLOC ();
+ 	      bitmap_set_bit (vars, DECL_UID (SSA_NAME_VAR (var)));
+ 	    }
+ 	  if (vars)
+ 	    ssa_varmap_exprmap_insert (new_expr, vars);
+ 
  	  /* Clear the stmt's RHS, or GC might bite us.  */
  	  GIMPLE_STMT_OPERAND (expr[version], 1) = NULL_TREE;
  	  return true;
*************** rewrite_trees (var_map map, tree *values
*** 737,742 ****
--- 749,757 ----
  		remove = true;
  	      else
  		{
+ 		  /* Remember the ssa names variable map.  */
+ 		  bitmap vars = ssa_varmap_lookup (DEF_FROM_PTR (def_p));
+ 
  		  if (replace_def_variable (map, def_p, NULL))
  		    changed = true;
  		  /* If both SSA_NAMEs coalesce to the same variable,
*************** rewrite_trees (var_map map, tree *values
*** 747,752 ****
--- 762,771 ----
  		      if (DEF_FROM_PTR (def_p) == USE_FROM_PTR (copy_use_p))
  			remove = true;
  		    }
+ 
+ 		  /* Attach the variable map to the defining stmt.  */
+ 		  if (!remove && vars)
+ 		    ssa_varmap_exprmap_insert (stmt, vars);
  		}
  	    }
  	  else
*************** remove_ssa_form (bool perform_ter)
*** 1158,1163 ****
--- 1177,1186 ----
        values = find_replaceable_exprs (map);
        if (values && dump_file && (dump_flags & TDF_DETAILS))
  	dump_replaceable_exprs (dump_file, values);
+ 
+       /* Create expression to varmap map based on the TER table.  */
+       if (values)
+         ssa_varmap_build_exprmap (values);
      }
  
    /* Assign real variables to the partitions now.  */
*************** insert_backedge_copies (void)
*** 1283,1288 ****
--- 1306,1315 ----
  static unsigned int
  rewrite_out_of_ssa (void)
  {
+   /* And allocate the temporary expression to debug variables mapping.  */
+   cfun->varmap_exprmap = htab_create_ggc (7, tree_bitmap_map_hash,
+ 					  tree_bitmap_map_eq, NULL);
+ 
    /* If elimination of a PHI requires inserting a copy on a backedge,
       then we will have to split the backedge which has numerous
       undesirable performance effects.
*************** rewrite_out_of_ssa (void)
*** 1302,1307 ****
--- 1329,1338 ----
      dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
  
    cfun->gimple_df->in_ssa_p = false;
+ 
+   /* Finally remove the SSA_NAME to debug variables mapping.  */
+   cfun->varmap_hash = NULL;
+ 
    return 0;
  }
  
Index: var-mappings-branch/gcc/expr.c
===================================================================
*** var-mappings-branch.orig/gcc/expr.c	2007-11-12 18:31:56.000000000 +0100
--- var-mappings-branch/gcc/expr.c	2007-11-12 18:33:12.000000000 +0100
*************** expand_constructor (tree exp, rtx target
*** 7042,7049 ****
  static rtx expand_expr_real_1 (tree, rtx, enum machine_mode,
  			       enum expand_modifier, rtx *);
  
! rtx
! expand_expr_real (tree exp, rtx target, enum machine_mode tmode,
  		  enum expand_modifier modifier, rtx *alt_rtl)
  {
    int rn = -1;
--- 7042,7049 ----
  static rtx expand_expr_real_1 (tree, rtx, enum machine_mode,
  			       enum expand_modifier, rtx *);
  
! static rtx
! expand_expr_real_x (tree exp, rtx target, enum machine_mode tmode,
  		  enum expand_modifier modifier, rtx *alt_rtl)
  {
    int rn = -1;
*************** expand_expr_real (tree exp, rtx target, 
*** 7116,7121 ****
--- 7116,7178 ----
    return ret;
  }
  
+ /* Generate code for computing expression EXP.
+    An rtx for the computed value is returned.  The value is never null.
+    In the case of a void EXP, const0_rtx is returned.  */
+ rtx
+ expand_expr_real (tree exp, rtx target, enum machine_mode tmode,
+ 		  enum expand_modifier modifier, rtx *alt_rtl)
+ {
+   rtx result, dest, insn, set;
+   bitmap vars;
+ 
+   result = expand_expr_real_x (exp, target, tmode, modifier, alt_rtl);
+ 
+   /* If there is no variable map attached to the expression, we
+      have done everything required.  */
+   vars = ssa_varmap_exprmap_lookup (exp);
+   if (!vars)
+     return result;
+ 
+   /* If we expanded an assignment, lookup the target RTX from the
+      lhs tree.  */
+   if (TREE_CODE (exp) == GIMPLE_MODIFY_STMT
+       && DECL_P (GIMPLE_STMT_OPERAND (exp, 0)))
+     dest = DECL_RTL (GIMPLE_STMT_OPERAND (exp, 0));
+   else
+     dest = result;
+ 
+   /* Now look for the last insn if this sets the result RTX.  */
+   insn = get_last_insn ();
+   if (insn
+       && (set = single_set (insn))
+       && XEXP (set, 0) == dest)
+     {
+       /* Found the set.  What we now can do is, if dest is a pseudo,
+ 	 attach a user variable to it.  This makes it more interesting
+ 	 to var-tracking.
+ 	 ???  What about mems and MEM_EXPR?  */
+       if (REG_P (dest)
+ 	  && REG_EXPR (dest)
+ 	  && DECL_ARTIFICIAL (REG_EXPR (dest)))
+ 	{
+ 	  int uid = bitmap_first_set_bit (vars);
+ 	  tree var = ssa_varmap_get_ref (uid);
+ 	  if (var)
+ 	    {
+ 	      REG_ATTRS (dest)->decl = var;
+ 	      /* If this was the only set bit we can get
+ 		 away without attaching the bitmap to the SET.  */
+ 	      if (bitmap_single_bit_set_p (vars))
+ 		return result;
+ 	    }
+ 	}
+       XBITMAP (set, 2) = vars;
+     }
+ 
+   return result;
+ }
+ 
  static rtx
  expand_expr_real_1 (tree exp, rtx target, enum machine_mode tmode,
  		    enum expand_modifier modifier, rtx *alt_rtl)
Index: var-mappings-branch/gcc/cfgexpand.c
===================================================================
*** var-mappings-branch.orig/gcc/cfgexpand.c	2007-11-12 18:31:56.000000000 +0100
--- var-mappings-branch/gcc/cfgexpand.c	2007-11-12 18:33:12.000000000 +0100
*************** tree_expand_cfg (void)
*** 1925,1930 ****
--- 1925,1933 ----
    /* We're done expanding trees to RTL.  */
    currently_expanding_to_rtl = 0;
  
+   /* Get rid of the temporary expression to debug variable mapping.  */
+   cfun->varmap_exprmap = NULL;
+ 
    /* Convert tree EH labels to RTL EH labels, and clean out any unreachable
       EH regions.  */
    convert_from_eh_region_ranges ();
Index: var-mappings-branch/gcc/function.h
===================================================================
*** var-mappings-branch.orig/gcc/function.h	2007-11-12 18:31:56.000000000 +0100
--- var-mappings-branch/gcc/function.h	2007-11-12 18:33:12.000000000 +0100
*************** struct function GTY(())
*** 326,331 ****
--- 326,336 ----
       and an obstack to allocate the bitmaps from.  */
    htab_t GTY((param_is (struct uid_bitmap_map))) varmap_hash;
  
+   /* A mapping from expression tree address to bitmap of DECL_UIDs that
+      represent this value.  This is initialized during out-of-ssa from
+      the varmap_hash data.  */
+   htab_t GTY((param_is (struct tree_bitmap_map))) varmap_exprmap;
+ 
    /* Assembly labels for the hot and cold text sections, to
       be used by debugger functions for determining the size of text
       sections.  */
Index: var-mappings-branch/gcc/tree-ssanames.c
===================================================================
*** var-mappings-branch.orig/gcc/tree-ssanames.c	2007-11-12 18:32:41.000000000 +0100
--- var-mappings-branch/gcc/tree-ssanames.c	2007-11-12 18:33:12.000000000 +0100
*************** ssa_varmap_process_phi (tree stmt)
*** 561,566 ****
--- 561,634 ----
    ssa_varmap_replace (lhs, tmp);
  }
  
+ /* Find the variable bitmap associated with EXPR.  Returns NULL if there
+    is no such association.  */
+ 
+ bitmap
+ ssa_varmap_exprmap_lookup (tree expr)
+ {
+   struct tree_bitmap_map id;
+   struct tree_bitmap_map *h;
+ 
+   if (!cfun
+       /* We might never have gone into and out of SSA.  */
+       || !cfun->varmap_exprmap)
+     return NULL;
+ 
+   id.base.from = expr;
+   h = (struct tree_bitmap_map *)
+       htab_find_with_hash (cfun->varmap_exprmap, &id, htab_hash_pointer (expr));
+   if (h)
+     return h->map;
+   return NULL;
+ }
+ 
+ /* Insert a mapping from EXPR to VARS.  */
+ 
+ void
+ ssa_varmap_exprmap_insert (tree expr, bitmap vars)
+ {
+   struct tree_bitmap_map id;
+   struct tree_bitmap_map **loc;
+ 
+   id.base.from = expr;
+   loc = (struct tree_bitmap_map **)
+ 	htab_find_slot_with_hash (cfun->varmap_exprmap, &id,
+ 				  htab_hash_pointer (expr), INSERT);
+   if (*loc)
+     return;
+   *loc = GGC_NEW (struct tree_bitmap_map);
+   (*loc)->base.from = expr;
+   (*loc)->map = vars;
+ }
+ 
+ /* Build a map from expressions that define ssa names *VALUES to
+    the variable bitmap.  */
+ 
+ void
+ ssa_varmap_build_exprmap (tree *values)
+ {
+   int i;
+ 
+   for (i = 0; i < (int)num_ssa_names; ++i)
+     if (values[i])
+       {
+ 	tree ssa_name = GIMPLE_STMT_OPERAND (values[i], 0);
+ 	tree expr = GIMPLE_STMT_OPERAND (values[i], 1);
+ 	bitmap map = ssa_varmap_lookup (ssa_name);
+ 	if (!map)
+ 	  continue;
+ 
+ 	ssa_varmap_exprmap_insert (expr, map);
+ 
+ 	/* Hold on the variable name.
+ 	   ???  Maybe as a fallback we could also reference the
+ 	   first bit set in the map.  */
+ 	if (!DECL_ARTIFICIAL (SSA_NAME_VAR (ssa_name)))
+ 	  ssa_varmap_add_ref (SSA_NAME_VAR (ssa_name));
+       }
+ }
+ 
  /* 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: var-mappings-branch/gcc/tree.h
===================================================================
*** var-mappings-branch.orig/gcc/tree.h	2007-11-12 18:32:49.000000000 +0100
--- var-mappings-branch/gcc/tree.h	2007-11-12 18:33:12.000000000 +0100
*************** extern void ssa_varmap_add_var (tree, tr
*** 3911,3916 ****
--- 3911,3919 ----
  extern void ssa_varmap_process_phi (tree);
  #define ssa_varmap_get_ref(uid) lookup_decl_from_uid (uid)
  void ssa_varmap_add_ref (tree);
+ extern bitmap ssa_varmap_exprmap_lookup (tree);
+ extern void ssa_varmap_exprmap_insert (tree, bitmap);
+ extern void ssa_varmap_build_exprmap (tree *);
  
  #ifdef GATHER_STATISTICS
  extern void ssanames_print_statistics (void);