This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[Patch] Fix compilation time explosion in contains_label_p


Hi,

the attached testcase (with -gnato) triggers a compilation time explosion in 
contains_label_p because the tree passed to it contains many shared nodes, 
which are then walked multiple time.

Tested on i586-suse-linux, OK for mainline?


2009-06-28  Eric Botcazou  <ebotcazou@adacore.com>

	* fold-const.c: Include pointer-set.h.
	(contains_label_p): Do not walk trees multiple time.
	* Makefile.in (fold-const.o): Add dependency on pointer-set.h.


2009-06-28  Eric Botcazou  <ebotcazou@adacore.com>

	* gnat.dg/overflow_sum2.adb: New test
	* gnat.dg/namet.ads: New helper.


-- 
Eric Botcazou
Index: fold-const.c
===================================================================
--- fold-const.c	(revision 149005)
+++ fold-const.c	(working copy)
@@ -65,6 +65,7 @@ along with GCC; see the file COPYING3.  
 #include "hashtab.h"
 #include "langhooks.h"
 #include "md5.h"
+#include "pointer-set.h"
 #include "gimple.h"
 
 /* Nonzero if we are folding constants inside an initializer; zero
@@ -13253,7 +13254,11 @@ contains_label_1 (tree *tp,
 static bool
 contains_label_p (tree st)
 {
-  return (walk_tree (&st, contains_label_1 , NULL, NULL) != NULL_TREE);
+  bool ret;
+  struct pointer_set_t *visited = pointer_set_create ();
+  ret = (walk_tree (&st, contains_label_1, NULL, visited) != NULL_TREE);
+  pointer_set_destroy (visited);
+  return ret;
 }
 
 /* Fold a ternary expression of code CODE and type TYPE with operands
Index: Makefile.in
===================================================================
--- Makefile.in	(revision 149005)
+++ Makefile.in	(working copy)
@@ -2497,7 +2497,7 @@ tree-pretty-print.o : tree-pretty-print.
 fold-const.o : fold-const.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
    $(TREE_H) $(FLAGS_H) $(REAL_H) $(TOPLEV_H) $(HASHTAB_H) $(EXPR_H) $(RTL_H) \
    $(GGC_H) $(TM_P_H) langhooks.h $(MD5_H) intl.h fixed-value.h $(TARGET_H) \
-   $(GIMPLE_H)
+   pointer-set.h $(GIMPLE_H)
 diagnostic.o : diagnostic.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
    $(TREE_H) version.h $(TM_P_H) $(FLAGS_H) $(INPUT_H) $(TOPLEV_H) intl.h \
    $(DIAGNOSTIC_H) langhooks.h $(LANGHOOKS_DEF_H) diagnostic.def opts.h \
package Namet is

  Hash_Num : constant Integer := 2**12;

  subtype Hash_Index_Type is Integer range 0 .. Hash_Num - 1;

  Name_Buffer : String (1 .. 16*1024);

  Name_Len : Natural;

end Namet;
-- { dg-do compile }
-- { dg-options "-gnato" }

with Namet; use Namet;

function Overflow_Sum2 return Hash_Index_Type is

  Even_Name_Len : Integer;

begin

  if Name_Len > 12 then
    Even_Name_Len := (Name_Len) / 2 * 2;

  return ((((((((((((
    Character'Pos (Name_Buffer (01))) * 2 +
    Character'Pos (Name_Buffer (Even_Name_Len - 10))) * 2 +
    Character'Pos (Name_Buffer (03))) * 2 +
    Character'Pos (Name_Buffer (Even_Name_Len - 08))) * 2 +
    Character'Pos (Name_Buffer (05))) * 2 +
    Character'Pos (Name_Buffer (Even_Name_Len - 06))) * 2 +
    Character'Pos (Name_Buffer (07))) * 2 +
    Character'Pos (Name_Buffer (Even_Name_Len - 04))) * 2 +
    Character'Pos (Name_Buffer (09))) * 2 +
    Character'Pos (Name_Buffer (Even_Name_Len - 02))) * 2 +
    Character'Pos (Name_Buffer (11))) * 2 +
    Character'Pos (Name_Buffer (Even_Name_Len))) mod Hash_Num;
  end if;

  return 0;

end;

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]