Example program takes 2000 times as long to compile underC++ as C

Mark Mitchell mark@codesourcery.com
Tue Sep 5 00:38:00 GMT 2000


Zack --

  I couldn't do better than you.  The SAVE_EXPRs are coming from
constant folding: we are turning

  (a ? b : c) | x 

into:

  a ? (b | x) : (c | x)

This blows up the size of the expression (if the folding doesn't
actually fold anything).  I suspect that we should not be doing this
transformation in this case, but we do.  In any case, this
transformation requires the insertion of SAVE_EXPRs in some cases.
  
  This is part of why SAVE_EXPRs are evil.  We should create explicit
tmeporary variables, and save the values we need to save there.  That
would avoid the exponential behavior and make lots of other things
easier too.

  However, it is never-the-less a good thing to avoid walking the same
tree multiple times, where possible.  (It's definitely not safe to
always do this.)

  Here's the patch I came up with, which does cut the compile time
down to almost zero for your test case.

  Thanks,

--
Mark Mitchell                   mark@codesourcery.com
CodeSourcery, LLC               http://www.codesourcery.com

2000-09-05  Mark Mitchell  <mark@codesourcery.com>

	* Makefile.in (CXX_TREE_H): Add dependency on HTAB_H.
	(pt.o): Remove dependency on HTAB_H.
	* cp-tree.h: Include hashtab.h.
	(walk_tree): Change prototype.
	(walk_tree_without_duplicates): New function.
	* decl.c (check_default_argument): Use it.
	* optimize.c (remap_decl): Adjust calls to walk_tree.
	(copy_body): Likewise.
	(expand_calls_inline): Likewise.
	(calls_setjmp_p): Use walk_tree_without_duplicates.
	* pt.c: Don't include hashtab.h.
	(for_each_template_parm): Use walk_tree_without_duplicates.
	* semantics.c (finish-stmt_tree): Likewise.
	(expand_body): Likewise.
	* tree.c (walk_tree): Add additional parameter.
	(walk_tree_without_duplicates): New function.
	(count_trees): Use it.
	(verify_stmt_tree): Adjust call to walk_tree.
	(find_tree): Use walk_tree_without_duplicates.
	(no_linkage_check): Likewise.
	(break_out_target_exprs): Adjust call to walk_tree.
	(cp_unsave): Likewise.

Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/egcs/gcc/cp/Makefile.in,v
retrieving revision 1.96
diff -c -p -r1.96 Makefile.in
*** Makefile.in	2000/08/22 20:26:40	1.96
--- Makefile.in	2000/09/05 07:30:13
*************** TREE_H = $(srcdir)/../tree.h $(srcdir)/.
*** 208,214 ****
  CXX_TREE_H = $(TREE_H) cp-tree.h $(srcdir)/../c-common.h cp-tree.def \
  	$(srcdir)/../c-common.def $(srcdir)/../function.h $(srcdir)/../varray.h \
  	$(srcdir)/../../include/splay-tree.h \
! 	$(srcdir)/../system.h $(CONFIG_H)
  PARSE_H = $(srcdir)/parse.h
  PARSE_C = $(srcdir)/parse.c
  EXPR_H = $(srcdir)/../expr.h ../insn-codes.h
--- 208,214 ----
  CXX_TREE_H = $(TREE_H) cp-tree.h $(srcdir)/../c-common.h cp-tree.def \
  	$(srcdir)/../c-common.def $(srcdir)/../function.h $(srcdir)/../varray.h \
  	$(srcdir)/../../include/splay-tree.h \
! 	$(srcdir)/../system.h $(CONFIG_H) $(HTAB_H)
  PARSE_H = $(srcdir)/parse.h
  PARSE_C = $(srcdir)/parse.c
  EXPR_H = $(srcdir)/../expr.h ../insn-codes.h
*************** xref.o : xref.c $(CXX_TREE_H) $(srcdir)/
*** 299,305 ****
    $(srcdir)/../toplev.h
  pt.o : pt.c $(CXX_TREE_H) decl.h $(PARSE_H) lex.h \
    $(srcdir)/../toplev.h $(GGC_H) $(RTL_H) \
!   $(srcdir)/../except.h $(HTAB_H)
  error.o : error.c $(CXX_TREE_H) \
    $(srcdir)/../toplev.h $(srcdir)/../diagnostic.h
  errfn.o : errfn.c $(CXX_TREE_H) \
--- 299,305 ----
    $(srcdir)/../toplev.h
  pt.o : pt.c $(CXX_TREE_H) decl.h $(PARSE_H) lex.h \
    $(srcdir)/../toplev.h $(GGC_H) $(RTL_H) \
!   $(srcdir)/../except.h
  error.o : error.c $(CXX_TREE_H) \
    $(srcdir)/../toplev.h $(srcdir)/../diagnostic.h
  errfn.o : errfn.c $(CXX_TREE_H) \
Index: cp-tree.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/cp/cp-tree.h,v
retrieving revision 1.520
diff -c -p -r1.520 cp-tree.h
*** cp-tree.h	2000/09/05 00:57:55	1.520
--- cp-tree.h	2000/09/05 07:30:17
*************** the Free Software Foundation, 59 Temple 
*** 21,26 ****
--- 21,27 ----
  Boston, MA 02111-1307, USA.  */
  
  #include "function.h"
+ #include "hashtab.h"
  #include "splay-tree.h"
  #include "varray.h"
  
*************** extern tree build_dummy_object			PARAMS 
*** 4535,4541 ****
  extern tree maybe_dummy_object			PARAMS ((tree, tree *));
  extern int is_dummy_object			PARAMS ((tree));
  typedef tree (*walk_tree_fn)                    PARAMS ((tree *, int *, void *));
! extern tree walk_tree                           PARAMS ((tree *, walk_tree_fn, void *));
  extern tree copy_tree_r                         PARAMS ((tree *, int *, void *));
  extern int cp_valid_lang_attribute		PARAMS ((tree, tree, tree, tree));
  extern tree make_ptrmem_cst                     PARAMS ((tree, tree));
--- 4536,4548 ----
  extern tree maybe_dummy_object			PARAMS ((tree, tree *));
  extern int is_dummy_object			PARAMS ((tree));
  typedef tree (*walk_tree_fn)                    PARAMS ((tree *, int *, void *));
! extern tree walk_tree                           PARAMS ((tree *,
! 							 walk_tree_fn,
! 							 void *, 
! 							 htab_t));
! extern tree walk_tree_without_duplicates        PARAMS ((tree *,
! 							 walk_tree_fn,
! 							 void *));
  extern tree copy_tree_r                         PARAMS ((tree *, int *, void *));
  extern int cp_valid_lang_attribute		PARAMS ((tree, tree, tree, tree));
  extern tree make_ptrmem_cst                     PARAMS ((tree, tree));
Index: decl.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/cp/decl.c,v
retrieving revision 1.680
diff -c -p -r1.680 decl.c
*** decl.c	2000/09/05 00:57:56	1.680
--- decl.c	2000/09/05 07:30:26
*************** check_default_argument (decl, arg)
*** 11946,11952 ****
  
       The keyword `this' shall not be used in a default argument of a
       member function.  */
!   var = walk_tree (&arg, local_variable_p_walkfn, NULL);
    if (var)
      {
        cp_error ("default argument `%E' uses local variable `%D'",
--- 11946,11953 ----
  
       The keyword `this' shall not be used in a default argument of a
       member function.  */
!   var = walk_tree_without_duplicates (&arg, local_variable_p_walkfn, 
! 				      NULL);
    if (var)
      {
        cp_error ("default argument `%E' uses local variable `%D'",
Index: optimize.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/cp/optimize.c,v
retrieving revision 1.42
diff -c -p -r1.42 optimize.c
*** optimize.c	2000/07/27 21:10:29	1.42
--- optimize.c	2000/09/05 07:30:27
*************** remap_decl (decl, id)
*** 109,116 ****
        /* The decl T could be a dynamic array or other variable size type,
  	 in which case some fields need to be remapped because they may
  	 contain SAVE_EXPRs.  */
!       walk_tree (&DECL_SIZE (t), copy_body_r, id);
!       walk_tree (&DECL_SIZE_UNIT (t), copy_body_r, id);
        if (TREE_TYPE (t) && TREE_CODE (TREE_TYPE (t)) == ARRAY_TYPE
  	  && TYPE_DOMAIN (TREE_TYPE (t)))
  	{
--- 109,116 ----
        /* The decl T could be a dynamic array or other variable size type,
  	 in which case some fields need to be remapped because they may
  	 contain SAVE_EXPRs.  */
!       walk_tree (&DECL_SIZE (t), copy_body_r, id, NULL);
!       walk_tree (&DECL_SIZE_UNIT (t), copy_body_r, id, NULL);
        if (TREE_TYPE (t) && TREE_CODE (TREE_TYPE (t)) == ARRAY_TYPE
  	  && TYPE_DOMAIN (TREE_TYPE (t)))
  	{
*************** remap_decl (decl, id)
*** 118,124 ****
  	  TYPE_DOMAIN (TREE_TYPE (t)) 
  	    = copy_node (TYPE_DOMAIN (TREE_TYPE (t)));
  	  walk_tree (&TYPE_MAX_VALUE (TYPE_DOMAIN (TREE_TYPE (t))),
! 		     copy_body_r, id);
  	}
  
        /* Remember it, so that if we encounter this local entity
--- 118,124 ----
  	  TYPE_DOMAIN (TREE_TYPE (t)) 
  	    = copy_node (TYPE_DOMAIN (TREE_TYPE (t)));
  	  walk_tree (&TYPE_MAX_VALUE (TYPE_DOMAIN (TREE_TYPE (t))),
! 		     copy_body_r, id, NULL);
  	}
  
        /* Remember it, so that if we encounter this local entity
*************** copy_body (id)
*** 356,362 ****
    tree body;
  
    body = DECL_SAVED_TREE (VARRAY_TOP_TREE (id->fns));
!   walk_tree (&body, copy_body_r, id);
  
    return body;
  }
--- 356,362 ----
    tree body;
  
    body = DECL_SAVED_TREE (VARRAY_TOP_TREE (id->fns));
!   walk_tree (&body, copy_body_r, id, NULL);
  
    return body;
  }
*************** expand_call_inline (tp, walk_subtrees, d
*** 636,642 ****
  	{
  	  if (i == 2)
  	    ++id->in_target_cleanup_p;
! 	  walk_tree (&TREE_OPERAND (*tp, i), expand_call_inline, data);
  	  if (i == 2)
  	    --id->in_target_cleanup_p;
  	}
--- 636,643 ----
  	{
  	  if (i == 2)
  	    ++id->in_target_cleanup_p;
! 	  walk_tree (&TREE_OPERAND (*tp, i), expand_call_inline, data,
! 		     NULL);
  	  if (i == 2)
  	    --id->in_target_cleanup_p;
  	}
*************** expand_calls_inline (tp, id)
*** 792,798 ****
  {
    /* Search through *TP, replacing all calls to inline functions by
       appropriate equivalents.  */
!   walk_tree (tp, expand_call_inline, id);
  }
  
  /* Optimize the body of FN.  */
--- 793,799 ----
  {
    /* Search through *TP, replacing all calls to inline functions by
       appropriate equivalents.  */
!   walk_tree (tp, expand_call_inline, id, NULL);
  }
  
  /* Optimize the body of FN.  */
*************** int
*** 879,886 ****
  calls_setjmp_p (fn)
       tree fn;
  {
!   return (walk_tree (&DECL_SAVED_TREE (fn), calls_setjmp_r, NULL) 
! 	  != NULL_TREE);
  }
  
  /* FN is a function that has a complete body.  Clone the body as
--- 880,888 ----
  calls_setjmp_p (fn)
       tree fn;
  {
!   return walk_tree_without_duplicates (&DECL_SAVED_TREE (fn), 
! 				       calls_setjmp_r, 
! 				       NULL) != NULL_TREE;
  }
  
  /* FN is a function that has a complete body.  Clone the body as
Index: pt.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/cp/pt.c,v
retrieving revision 1.463
diff -c -p -r1.463 pt.c
*** pt.c	2000/09/05 00:57:56	1.463
--- pt.c	2000/09/05 07:30:33
*************** Boston, MA 02111-1307, USA.  */
*** 43,49 ****
  #include "rtl.h"
  #include "defaults.h"
  #include "ggc.h"
- #include "hashtab.h"
  #include "timevar.h"
  
  /* The type of functions taking a tree, and some additional data, and
--- 43,48 ----
*************** for_each_template_parm (t, fn, data)
*** 4276,4282 ****
    pfd.data = data;
  
    /* Walk the tree.  */
!   return walk_tree (&t, for_each_template_parm_r, &pfd) != NULL_TREE;
  }
  
  int
--- 4275,4283 ----
    pfd.data = data;
  
    /* Walk the tree.  */
!   return walk_tree_without_duplicates (&t, 
! 				       for_each_template_parm_r, 
! 				       &pfd) != NULL_TREE;
  }
  
  int
Index: semantics.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/cp/semantics.c,v
retrieving revision 1.165
diff -c -p -r1.165 semantics.c
*** semantics.c	2000/08/29 22:13:20	1.165
--- semantics.c	2000/09/05 07:30:34
*************** finish_stmt_tree (t)
*** 2324,2330 ****
    /* Remove unused decls from the stmt tree.  walk_tree messes with
       the line number, so save/restore it.  */
    old_lineno = lineno;
!   walk_tree (t, prune_unused_decls, 0);
    lineno = old_lineno;
  
    if (cfun)
--- 2324,2330 ----
    /* Remove unused decls from the stmt tree.  walk_tree messes with
       the line number, so save/restore it.  */
    old_lineno = lineno;
!   walk_tree_without_duplicates (t, prune_unused_decls, NULL);
    lineno = old_lineno;
  
    if (cfun)
*************** expand_body (fn)
*** 2639,2645 ****
      }
  
    /* Replace AGGR_INIT_EXPRs with appropriate CALL_EXPRs.  */
!   walk_tree (&DECL_SAVED_TREE (fn), simplify_aggr_init_exprs_r, NULL);
  
    /* If this is a constructor or destructor body, we have to clone it
       under the new ABI.  */
--- 2639,2647 ----
      }
  
    /* Replace AGGR_INIT_EXPRs with appropriate CALL_EXPRs.  */
!   walk_tree_without_duplicates (&DECL_SAVED_TREE (fn),
! 				simplify_aggr_init_exprs_r,
! 				NULL);
  
    /* If this is a constructor or destructor body, we have to clone it
       under the new ABI.  */
Index: tree.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/cp/tree.c,v
retrieving revision 1.212
diff -c -p -r1.212 tree.c
*** tree.c	2000/09/05 00:57:57	1.212
--- tree.c	2000/09/05 07:30:35
*************** Boston, MA 02111-1307, USA.  */
*** 26,32 ****
  #include "tree.h"
  #include "cp-tree.h"
  #include "flags.h"
- #include "hashtab.h"
  #include "rtl.h"
  #include "toplev.h"
  #include "ggc.h"
--- 26,31 ----
*************** copy_template_template_parm (t, newargs)
*** 1224,1254 ****
  /* Apply FUNC to all the sub-trees of TP in a pre-order traversal.
     FUNC is called with the DATA and the address of each sub-tree.  If
     FUNC returns a non-NULL value, the traversal is aborted, and the
!    value returned by FUNC is returned.  */
  
  tree 
! walk_tree (tp, func, data)
       tree *tp;
       walk_tree_fn func;
       void *data;
  {
    enum tree_code code;
    int walk_subtrees;
    tree result;
    
! #define WALK_SUBTREE(NODE)			\
!   do						\
!     {						\
!       result = walk_tree (&(NODE), func, data);	\
!       if (result)				\
! 	return result;				\
!     }						\
    while (0)
  
    /* Skip empty subtrees.  */
    if (!*tp)
      return NULL_TREE;
  
    /* Call the function.  */
    walk_subtrees = 1;
    result = (*func) (tp, &walk_subtrees, data);
--- 1223,1267 ----
  /* Apply FUNC to all the sub-trees of TP in a pre-order traversal.
     FUNC is called with the DATA and the address of each sub-tree.  If
     FUNC returns a non-NULL value, the traversal is aborted, and the
!    value returned by FUNC is returned.  The FLAGS govern the way in
!    which nodes are walked.  If HTAB is non-NULL it is used to record
!    the nodes visited, and to avoid visiting a node more than once.  */
  
  tree 
! walk_tree (tp, func, data, htab)
       tree *tp;
       walk_tree_fn func;
       void *data;
+      htab_t htab;
  {
    enum tree_code code;
    int walk_subtrees;
    tree result;
    
! #define WALK_SUBTREE(NODE)				\
!   do							\
!     {							\
!       result = walk_tree (&(NODE), func, data, htab);	\
!       if (result)					\
! 	return result;					\
!     }							\
    while (0)
  
    /* Skip empty subtrees.  */
    if (!*tp)
      return NULL_TREE;
  
+   if (htab) {
+     void **slot;
+     /* Don't walk the same tree twice, if the user has requested that we
+        avoid doing so. */
+     if (htab_find (htab, *tp))
+       return NULL_TREE;
+     /* If we haven't already seen this node, add it to the table. */
+     slot = htab_find_slot (htab, *tp, INSERT);
+     *slot = *tp;
+   }
+ 
    /* Call the function.  */
    walk_subtrees = 1;
    result = (*func) (tp, &walk_subtrees, data);
*************** walk_tree (tp, func, data)
*** 1423,1428 ****
--- 1436,1459 ----
  #undef WALK_SUBTREE
  }
  
+ /* Like walk_tree, but does not walk duplicate nodes more than 
+    once.  */
+ 
+ tree 
+ walk_tree_without_duplicates (tp, func, data)
+      tree *tp;
+      walk_tree_fn func;
+      void *data;
+ {
+   tree result;
+   htab_t htab;
+ 
+   htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
+   result = walk_tree (tp, func, data, htab);
+   htab_delete (htab);
+   return result;
+ }
+ 
  /* Called from count_trees via walk_tree.  */
  
  static tree
*************** count_trees (t)
*** 1443,1449 ****
       tree t;
  {
    int n_trees = 0;
!   walk_tree (&t, count_trees_r, &n_trees);
    return n_trees;
  }  
  
--- 1474,1480 ----
       tree t;
  {
    int n_trees = 0;
!   walk_tree_without_duplicates (&t, count_trees_r, &n_trees);
    return n_trees;
  }  
  
*************** verify_stmt_tree (t)
*** 1483,1489 ****
  {
    htab_t statements;
    statements = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
!   walk_tree (&t, verify_stmt_tree_r, &statements);
    htab_delete (statements);
  }
  
--- 1514,1520 ----
  {
    htab_t statements;
    statements = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
!   walk_tree (&t, verify_stmt_tree_r, &statements, NULL);
    htab_delete (statements);
  }
  
*************** find_tree (t, x)
*** 1508,1514 ****
       tree t;
       tree x;
  {
!   return walk_tree (&t, find_tree_r, x);
  }
  
  /* Passed to walk_tree.  Checks for the use of types with no linkage.  */
--- 1539,1545 ----
       tree t;
       tree x;
  {
!   return walk_tree_without_duplicates (&t, find_tree_r, x);
  }
  
  /* Passed to walk_tree.  Checks for the use of types with no linkage.  */
*************** no_linkage_check (t)
*** 1541,1547 ****
    if (processing_template_decl)
      return NULL_TREE;
  
!   t = walk_tree (&t, no_linkage_helper, NULL);
    if (t != error_mark_node)
      return t;
    return NULL_TREE;
--- 1572,1578 ----
    if (processing_template_decl)
      return NULL_TREE;
  
!   t = walk_tree_without_duplicates (&t, no_linkage_helper, NULL);
    if (t != error_mark_node)
      return t;
    return NULL_TREE;
*************** break_out_target_exprs (t)
*** 1736,1743 ****
      target_remap = splay_tree_new (splay_tree_compare_pointers, 
  				   /*splay_tree_delete_key_fn=*/NULL, 
  				   /*splay_tree_delete_value_fn=*/NULL);
!   walk_tree (&t, bot_manip, target_remap);
!   walk_tree (&t, bot_replace, target_remap);
  
    if (!--target_remap_count)
      {
--- 1767,1774 ----
      target_remap = splay_tree_new (splay_tree_compare_pointers, 
  				   /*splay_tree_delete_key_fn=*/NULL, 
  				   /*splay_tree_delete_value_fn=*/NULL);
!   walk_tree (&t, bot_manip, target_remap, NULL);
!   walk_tree (&t, bot_replace, target_remap, NULL);
  
    if (!--target_remap_count)
      {
*************** cp_unsave (tp)
*** 2520,2529 ****
    st = splay_tree_new (splay_tree_compare_pointers, NULL, NULL);
  
    /* Walk the tree once figuring out what needs to be remapped.  */
!   walk_tree (tp, mark_local_for_remap_r, st);
  
    /* Walk the tree again, copying, remapping, and unsaving.  */
!   walk_tree (tp, cp_unsave_r, st);
  
    /* Clean up.  */
    splay_tree_delete (st);
--- 2551,2560 ----
    st = splay_tree_new (splay_tree_compare_pointers, NULL, NULL);
  
    /* Walk the tree once figuring out what needs to be remapped.  */
!   walk_tree (tp, mark_local_for_remap_r, st, NULL);
  
    /* Walk the tree again, copying, remapping, and unsaving.  */
!   walk_tree (tp, cp_unsave_r, st, NULL);
  
    /* Clean up.  */
    splay_tree_delete (st);


More information about the Gcc-bugs mailing list