pruning unused debugging types (enums/PR23336)

pruning unused debugging types (enums/PR23336)

[Aldy Hernandez]

On a similar note than PR debug/21391...

In PR23336 we have the same thing happen with enums:

	enum something { JTI_PROMOTED_BYTE_TYPE_NODE, etc };

	use JTI_PROMOTED_BYTE_TYPE_NODE

JTI_PROMOTED_BYTE_TYPE_NODE and "something" get pruned even though we
use it.  I see two alternatives:

	1. Don't prune enumeration types.
	2. Similar solution to PR21391: mark all enum types we use as
	   un-prunable in the front-end.

Thoughts?

Aldy

p.s. PING: http://gcc.gnu.org/ml/gcc-patches/2005-11/msg01227.html

Re: pruning unused debugging types (enums/PR23336)

[Richard Henderson]

On Thu, Nov 17, 2005 at 06:08:35PM -0400, Aldy Hernandez wrote:
> On a similar note than PR debug/21391...
> 
> In PR23336 we have the same thing happen with enums:
> 
> 	enum something { JTI_PROMOTED_BYTE_TYPE_NODE, etc };
> 
> 	use JTI_PROMOTED_BYTE_TYPE_NODE
> 
> JTI_PROMOTED_BYTE_TYPE_NODE and "something" get pruned even though we
> use it.  I see two alternatives:
> 
> 	1. Don't prune enumeration types.
> 	2. Similar solution to PR21391: mark all enum types we use as
> 	   un-prunable in the front-end.
> 
> Thoughts?
> 
> Aldy
> 
> p.s. PING: http://gcc.gnu.org/ml/gcc-patches/2005-11/msg01227.html

I'm not altogether fond of either of these.  The problem, as I 
see it, is that we don't actually know if either the case type
or the enum type is used in any of the code that actually makes
it into the object file.

If we're going to devolve into marking everything that's ever
used once, we might as well rely on the TREE_USED bit on the type;
in the end it isn't going to make a difference, seeing as how we
will tend to pull in all of the types anyway.  Which would seem to
defeat the purpose of eliminating unused types in the first place.

If we're going to keep elimination of unused types, we're going to
have to come up with something new to associate used types with 
the code that uses them.  So that if the code is eliminated, the
used type will be as well.

If we set the granularity of this elimination to be the function,
we could add something to the function's debug data that could be
seen by the debug generator, and thus wouldn't be seen if the 
entire function is eliminated.

A solution that comes to mind is to have the front-end add dummy
TYPE_DECL nodes to the BLOCK_VARS list of the function's outer-most
BLOCK.  If the TYPE_DECL node were marked DECL_ARTIFICIAL and had
no DECL_NAME, it'd be easy for us to notice that we shouldn't 
actually emit debug info for the TYPE_DECL itself, but that we
should consider its TREE_TYPE to be used.

I'm open to better schemes.  Perhaps a used-type hash table in
the struct function.


r~

Re: pruning unused debugging types (enums/PR23336)

[Mark Mitchell]

Richard Henderson wrote:

> A solution that comes to mind is to have the front-end add dummy
> TYPE_DECL nodes to the BLOCK_VARS list of the function's outer-most
> BLOCK.  If the TYPE_DECL node were marked DECL_ARTIFICIAL and had
> no DECL_NAME, it'd be easy for us to notice that we shouldn't 
> actually emit debug info for the TYPE_DECL itself, but that we
> should consider its TREE_TYPE to be used.
> 
> I'm open to better schemes.  Perhaps a used-type hash table in
> the struct function.

I like the idea, but I think a hash table would be better.  In fact, I
think the best choice would be a hash table during compilation of the
function, transformed into a vector after the closing brace of the
function, so that we do not have the wasted memory associated with
either dummy TYPE_DECLs or hash table entries.  Also, we should do this
only for the kinds of types we tend to lose (maybe casts and enums?), to
keep the extra memory cost to a minimum.

-- 
Mark Mitchell
CodeSourcery, LLC
mark@codesourcery.com
(916) 791-8304

Re: pruning unused debugging types (enums/PR23336)

[Aldy Hernandez]

On Thu, Nov 17, 2005 at 10:24:21PM -0800, Mark Mitchell wrote:
> Richard Henderson wrote:
> 
> > A solution that comes to mind is to have the front-end add dummy
> > TYPE_DECL nodes to the BLOCK_VARS list of the function's outer-most
> > BLOCK.  If the TYPE_DECL node were marked DECL_ARTIFICIAL and had
> > no DECL_NAME, it'd be easy for us to notice that we shouldn't 
> > actually emit debug info for the TYPE_DECL itself, but that we
> > should consider its TREE_TYPE to be used.
> > 
> > I'm open to better schemes.  Perhaps a used-type hash table in
> > the struct function.
> 
> I like the idea, but I think a hash table would be better.  In fact, I
> think the best choice would be a hash table during compilation of the
> function, transformed into a vector after the closing brace of the

Either way is fine by me.  Just to make sure I understand things;
you want me to hack the front-end to fill the hash table every time
it parses a cast or enum type?

For example:

Index: c-parser.c
===================================================================
--- c-parser.c  (revision 107115)
+++ c-parser.c  (working copy)
@@ -4485,6 +4485,7 @@ c_parser_cast_expression (c_parser *pars
          ret.original_code = ERROR_MARK;
          return ret;
        }
+      add_to_some_hash (TREE_TYPE (groktypename (type_name)));
       if (c_parser_next_token_is (parser, CPP_OPEN_BRACE))
        return c_parser_postfix_expression_after_paren_type (parser,

Thanks.

Re: pruning unused debugging types (enums/PR23336)

[Mark Mitchell]

Aldy Hernandez wrote:

> Either way is fine by me.  Just to make sure I understand things;
> you want me to hack the front-end to fill the hash table every time
> it parses a cast or enum type?

Yes.

-- 
Mark Mitchell
CodeSourcery, LLC
mark@codesourcery.com
(916) 791-8304

Re: pruning unused debugging types (enums/PR23336)

[Aldy Hernandez]

Hi folks.

Sorry I've taken so long on this.  There was this marriage thing in
which I was a protagonist, and it's gotten me way off balance :).

I've been chasing my tail on implementation details.  I was hoping
someone could give me a few hints.

 >> A solution that comes to mind is to have the front-end add dummy
 >> TYPE_DECL nodes to the BLOCK_VARS list of the function's outer-most
 >> BLOCK.  If the TYPE_DECL node were marked DECL_ARTIFICIAL and had
 >> no DECL_NAME, it'd be easy for us to notice that we shouldn't 
 >> actually emit debug info for the TYPE_DECL itself, but that we
 >> should consider its TREE_TYPE to be used.
 >> 
 >> I'm open to better schemes.  Perhaps a used-type hash table in
 >> the struct function.

 > I like the idea, but I think a hash table would be better.  In fact, I
 > think the best choice would be a hash table during compilation of the
 > function, transformed into a vector after the closing brace of the
 > function, so that we do not have the wasted memory associated with
 > either dummy TYPE_DECLs or hash table entries.  Also, we should do this
 > only for the kinds of types we tend to lose (maybe casts and enums?), to
 > keep the extra memory cost to a minimum.

So far the way I've envisioned (correct me if I'm wrong please), is to
add 2 entries to struct function: one for a hash table which will be
freed when we're done parsing the function, and one containing the
vector of used types.

I'd like to avoid adding 2 entries, but just the vector.  However,
parsing nested functions require us to keep a used type hash table for
each function while we parse.  Mark is this ok (adding 2 entries)?

[I was thinking we could have a static stack of hashes of used types
in the parser, and only pollute struct function with the vector.  Mark
what did you have in mind?]

[Diego suggested doing all this in the gimplifier, since we gimplify
one function at a time plus we'd only have to implement this once
instead of in each parser, but by the time the gimplifier gets a hold
of things like "(struct foo *)0x1234)->I", we no longer have a cast;
it has been decomposed into an INDIRECT_REF.]

Problem number two... I'm apparently GTY clueless, and have been
unable to declare a vector of trees as a field of struct function.
So far I have:

        VEC(tree,gc) * GTY (()) used_types_vector;

This gives me:

        build/gengtype /blah/function.h:324: unidentified type
        `VEC_tree_gc'

I've also tried:

        GTY (()) VEC(tree,gc) *used_types_vector;

        build/gengtype /blah/function.h:324: syntax error, unexpected GTY_TOKEN, expecting '}'

I've been looking for examples of tree VECTORs in GTY'able structures
to no avail, and my GTYfoo is as good as my surfing (I know I'm
supposed to go on the surfboard, but that's about it).

Below is my non working patch to function.h.

Any ideas?  Thanks.
Aldy

Index: function.h
===================================================================
--- function.h  (revision 110692)
+++ function.h  (working copy)
@@ -23,6 +23,11 @@ Software Foundation, 51 Franklin Street,
 #define GCC_FUNCTION_H

 #include "tree.h"
+#include "hashtab.h"
+#include "ggc.h"
+#include "alloc-pool.h"
+#include "varray.h"
+#include "vec.h"

 struct var_refs_queue GTY(())
 {
@@ -312,6 +317,12 @@ struct function GTY(())
   /* Language-specific code can use this to store whatever it likes.  */
   struct language_function * language;

+  /* Used types hash table.  */
+  htab_t GTY ((param_is (union tree_node))) used_types_hash;
+
+  /* Used types vector.  */
+  GTY (()) VEC(tree,gc) *used_types_vector;
+
   /* For reorg.  */

Re: pruning unused debugging types (enums/PR23336)

[Mark Mitchell]

Aldy Hernandez wrote:

> So far the way I've envisioned (correct me if I'm wrong please), is to
> add 2 entries to struct function: one for a hash table which will be
> freed when we're done parsing the function, and one containing the
> vector of used types.

I was hoping you could use a union of the two, to avoid adding two entries.

> Problem number two... I'm apparently GTY clueless, and have been
> unable to declare a vector of trees as a field of struct function.

I always have a hard time with this too; I'm sorry, but I don't know the
right incantation either.

A simpler way to do this would be to just maintain a single global hash
table of types-used-in-casts.  I'm concerned that might result in
writing out a lot of types you wouldn't otherwise need, because you'd be
writing out types used in casts in functions that were themselves never
written out.  That might be particularly bad in C++; #include <kde.h>
probably gives you a lot of such casts.

You could combine the two ideas: a global hash table of types used in
casts, where each entry had a list of functions using those types.  That
should take up no more storage than the per-function vectors.  Then,
you'd have to walk the entire hash table, writing out each type for
which at least one of the associated functions was written out,
including being inlined into another function.

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: pruning unused debugging types (enums/PR23336)

[Aldy Hernandez]

> You could combine the two ideas: a global hash table of types used in
> casts, where each entry had a list of functions using those types.  That
> should take up no more storage than the per-function vectors.  Then,
> you'd have to walk the entire hash table, writing out each type for
> which at least one of the associated functions was written out,
> including being inlined into another function.

Do we keep a hash of functions that have been written out somewhere?
I'd hate to walk the entire hash table each time we write out a function
searching for the types that function uses.

Aldy

Re: pruning unused debugging types (enums/PR23336)

[Mark Mitchell]

Aldy Hernandez wrote:

> Do we keep a hash of functions that have been written out somewhere?

Not to my knowledge.

> I'd hate to walk the entire hash table each time we write out a function
> searching for the types that function uses.

Agreed.

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: pruning unused debugging types (enums/PR23336)

[Aldy Hernandez]

On Tue, Feb 14, 2006 at 06:08:42PM -0800, Mark Mitchell wrote:
> Aldy Hernandez wrote:
> 
> > Do we keep a hash of functions that have been written out somewhere?
> 
> Not to my knowledge.
> 
> > I'd hate to walk the entire hash table each time we write out a function
> > searching for the types that function uses.
> 
> Agreed.

Hi Mark.  Hi folks.

I went through a couple prototypes, some more cumbersome to implement than
others.  I've opted for a hash table of types in struct function.  The
implementation is a lot cleaner.  Perhaps we can optimize it later if
you really hate it :(.

This patch fixes the cast problem.  A similar solution would be in order
for the enums; the infrastructure here would work for that.

Could you take a peek at this, so we can use this as a starting point, and
perhaps then I can start on the C++ front-end?  I've sat on this long enough
:(.

Thanks.
Aldy

	* function.h (struct function): Add used_types_hash field.
	Include hashtab.h.
	* function.c (used_types_insert): New.
	* c-parser.c (c_parser_cast_expression): Call used_types_insert.
	* dwarf2out.c (struct die_struct): Add die_perennial_p field.
	(premark_used_types_helper): New.
	(premark_used_types): New.
	(gen_subprogram_die): Call premark_used_types.
	(prune_unused_types_walk): Do not mark perennial types.
	* c-decl.c (store_parm_decls): Initialize used_types_hash.
	(used_types_insert): Protoize.
	* Makefile.in (FUNCTION_H): Depend on HASHTAB_H.

Index: function.h
===================================================================
--- function.h	(revision 110692)
+++ function.h	(working copy)
@@ -23,6 +23,7 @@ Software Foundation, 51 Franklin Street,
 #define GCC_FUNCTION_H
 
 #include "tree.h"
+#include "hashtab.h"
 
 struct var_refs_queue GTY(())
 {
@@ -312,6 +313,9 @@ struct function GTY(())
   /* Language-specific code can use this to store whatever it likes.  */
   struct language_function * language;
 
+  /* Used types hash table.  */
+  htab_t GTY ((param_is (union tree_node))) used_types_hash;
+
   /* For reorg.  */
 
   /* If some insns can be deferred to the delay slots of the epilogue, the
@@ -562,4 +566,6 @@ extern bool pass_by_reference (CUMULATIV
 extern bool reference_callee_copied (CUMULATIVE_ARGS *, enum machine_mode,
 				     tree, bool);
 
+extern void used_types_insert (tree, struct function *);
+
 #endif  /* GCC_FUNCTION_H */
Index: function.c
===================================================================
--- function.c	(revision 110692)
+++ function.c	(working copy)
@@ -5569,6 +5569,18 @@ rest_of_handle_check_leaf_regs (void)
 #endif
 }
 
+/* Insert a type into the used types hash table.  */
+void
+used_types_insert (tree t, struct function *cfun)
+{
+  if (t != NULL)
+    {
+      void **slot = htab_find_slot (cfun->used_types_hash, t, INSERT);
+      if (*slot == NULL)
+	*slot = t;
+    }
+}
+
 struct tree_opt_pass pass_leaf_regs =
 {
   NULL,                                 /* name */
Index: c-parser.c
===================================================================
--- c-parser.c	(revision 110692)
+++ c-parser.c	(working copy)
@@ -4660,6 +4660,10 @@ c_parser_cast_expression (c_parser *pars
 	  ret.original_code = ERROR_MARK;
 	  return ret;
 	}
+
+      /* Save casted types in the function's used types hash table.  */
+      used_types_insert (TREE_TYPE (groktypename (type_name)), cfun);
+
       if (c_parser_next_token_is (parser, CPP_OPEN_BRACE))
 	return c_parser_postfix_expression_after_paren_type (parser,
 							     type_name);
Index: dwarf2out.c
===================================================================
--- dwarf2out.c	(revision 110692)
+++ dwarf2out.c	(working copy)
@@ -3677,6 +3677,8 @@ typedef struct die_struct GTY(())
   dw_offset die_offset;
   unsigned long die_abbrev;
   int die_mark;
+  /* Die is used and must not be pruned as unused.  */
+  int die_perennial_p;
   unsigned int decl_id;
 }
 die_node;
@@ -11477,6 +11479,30 @@ dwarf2out_abstract_function (tree decl)
   current_function_decl = save_fn;
 }
 
+/* Helper function of premark_used_types() which gets called through
+   htab_traverse_resize().
+
+   Marks the DIE of a given type in *SLOT as perennial, so it never gets
+   marked as unused by prune_unused_types.  */
+static int
+premark_used_types_helper (void **slot, void *data ATTRIBUTE_UNUSED)
+{
+  tree type;
+  dw_die_ref die;
+
+  type = *slot;
+  die = lookup_type_die (type);
+  die->die_perennial_p = 1;
+  return 1;
+}
+
+/* Mark all members of used_types_hash as perennial.  */
+static
+void premark_used_types ()
+{
+  htab_traverse_noresize (cfun->used_types_hash, premark_used_types_helper, NULL);
+}
+
 /* Generate a DIE to represent a declared function (either file-scope or
    block-local).  */
 
@@ -11492,6 +11518,8 @@ gen_subprogram_die (tree decl, dw_die_re
   int declaration = (current_function_decl != decl
 		     || class_or_namespace_scope_p (context_die));
 
+  premark_used_types();
+
   /* It is possible to have both DECL_ABSTRACT and DECLARATION be true if we
      started to generate the abstract instance of an inline, decided to output
      its containing class, and proceeded to emit the declaration of the inline
@@ -13968,6 +13996,9 @@ prune_unused_types_walk (dw_die_ref die)
   case DW_TAG_subrange_type:
   case DW_TAG_ptr_to_member_type:
   case DW_TAG_file_type:
+    if (die->die_perennial_p)
+      break;
+
     /* It's a type node --- don't mark it.  */
     return;
 
Index: c-decl.c
===================================================================
--- c-decl.c	(revision 110692)
+++ c-decl.c	(working copy)
@@ -6477,6 +6477,9 @@ store_parm_decls (void)
   /* Initialize the RTL code for the function.  */
   allocate_struct_function (fndecl);
 
+  cfun->used_types_hash = htab_create (37, htab_hash_pointer,
+				       htab_eq_pointer, NULL);
+
   /* Begin the statement tree for this function.  */
   DECL_SAVED_TREE (fndecl) = push_stmt_list ();
 
Index: Makefile.in
===================================================================
--- Makefile.in	(revision 110692)
+++ Makefile.in	(working copy)
@@ -750,7 +750,7 @@ RECOG_H = recog.h
 ALIAS_H = alias.h
 EMIT_RTL_H = emit-rtl.h
 FLAGS_H = flags.h options.h
-FUNCTION_H = function.h $(TREE_H)
+FUNCTION_H = function.h $(TREE_H) $(HASHTAB_H)
 EXPR_H = expr.h insn-config.h $(FUNCTION_H) $(RTL_H) $(FLAGS_H) $(TREE_H) $(MACHMODE_H) $(EMIT_RTL_H)
 OPTABS_H = optabs.h insn-codes.h
 REGS_H = regs.h varray.h $(MACHMODE_H) $(OBSTACK_H) $(BASIC_BLOCK_H) $(FUNCTION_H)

Re: pruning unused debugging types (enums/PR23336)

[Richard Henderson]

On Thu, Feb 16, 2006 at 03:40:57PM -0400, Aldy Hernandez wrote:
> +  htab_t GTY ((param_is (union tree_node))) used_types_hash;

Should be "tree" not the union.  You're storing a pointer, 
not the union itself.

> +used_types_insert (tree t, struct function *cfun)

Call it something other than cfun.  Don't shadow globals this way.

> +  htab_traverse_noresize (cfun->used_types_hash, premark_used_types_helper, NULL);

Shouldn't need to specify noresize.

> @@ -6477,6 +6477,9 @@ store_parm_decls (void)
>    /* Initialize the RTL code for the function.  */
>    allocate_struct_function (fndecl);
>  
> +  cfun->used_types_hash = htab_create (37, htab_hash_pointer,
> +				       htab_eq_pointer, NULL);

This should be either done in function.c, or dwarf2out.c should
be prepared for the hash to be null.


r~

Re: pruning unused debugging types (enums/PR23336)

[Diego Novillo]

Aldy Hernandez wrote:
>> You could combine the two ideas: a global hash table of types used in
>> casts, where each entry had a list of functions using those types.  That
>> should take up no more storage than the per-function vectors.  Then,
>> you'd have to walk the entire hash table, writing out each type for
>> which at least one of the associated functions was written out,
>> including being inlined into another function.
> 
> Do we keep a hash of functions that have been written out somewhere?
>
You need a list of functions that have been written or scheduled to be
emitted?  Each node in the call graph has a field 'output' set to true
when the function is marked for generation.