PATCH: Speed cfg_layout_duplicate_bb

[Brad Lucier <lucier at math dot purdue dot edu>]

This is Michael Matz's patch to remove the quadratic behavior in
make_edge when adding a new basic block.

It was bootstrapped and regtested on alphaev6-unknown-linux-gnu.  Although
there were some changes in the results, I don't think that they're
related to the patch---I've been having strange, seemingly arbitrary
regression changes.  Anyway, here is the diff between the two mail-report.log:

popov-1456% diff -u ../mail-report-with-warnings.log mail-report-with-warnings.log
--- ../mail-report-with-warnings.log    Sun Mar  9 12:38:20 2003
+++ mail-report-with-warnings.log       Sun Mar  9 15:56:58 2003
@@ -15,7 +15,7 @@
 FAIL: SyncTest execution - gij test
 WARNING: program timed out.
 FAIL: SyncTest -O execution - bytecode->native test
-FAIL: Thread_Interrupt output - gij test
+FAIL: Thread_Interrupt -O output - bytecode->native test
 FAIL: initexc execution - gij test
 FAIL: initexc execution - gij test

@@ -101,7 +101,6 @@
 FAIL: gcc.dg/typespec-1.c unsigned long long int signed (test for errors, line
935)
 FAIL: gcc.dg/typespec-1.c unsigned long long int unsigned (test for errors, line 936)
 FAIL: gcc.dg/typespec-1.c unsigned long long int _Bool (test for errors, line 937)
-FAIL: gcc.dg/typespec-1.c (test for excess errors)
 FAIL: gcc.dg/warn-1.c  (test for warnings, line 8)
 FAIL: gcc.dg/warn-1.c  (test for warnings, line 15)
 FAIL: gcc.dg/pch/inline-1.c (test for excess errors)
@@ -109,8 +108,8 @@

                === gcc Summary ===

-# of expected passes           21731
-# of unexpected failures       27
+# of expected passes           21732
+# of unexpected failures       26
 # of expected failures         79
 # of untested testcases                1
 # of unsupported tests         178

Without this patch, bootstrap with --disable-checking took 6549.367
user seconds, with it, it took 6496.817 user seconds.  On my testcases,
involving large routines with computed gotos, it almost doubles the
speed of compilation.

Brad

	* cfg.c (unchecked_make_edge): New.  Break out from ...
	(cached_make_edge): Here.  Call unchecked_make_edge.
	* cfglayout.c (cfg_layout_dupicate_bb): Call unchecked_make_edge
	instead of make_edge.
	* basic_block.h (unchecked_make_edge): Declare.

===================================================================
RCS file: RCS/cfg.c,v
retrieving revision 1.1
diff -u -p -r1.1 cfg.c
--- cfg.c	2003/03/09 17:39:23	1.1
+++ cfg.c	2003/03/10 03:06:58
@@ -280,6 +280,32 @@ expunge_block (b)
   pool_free (bb_pool, b);
 }
 
+/* Create an edge connecting SRC and DEST with flags FLAGS without
+   checking whether the edge already exists.  Use this only if you
+   are sure that this edge can't possibly already exist.  */
+
+edge
+unchecked_make_edge (src, dst, flags)
+     basic_block src, dst;
+     int flags;
+{
+  edge e;
+  e = pool_alloc (edge_pool);
+  memset (e, 0, sizeof (*e));
+  n_edges++;
+
+  e->succ_next = src->succ;
+  e->pred_next = dst->pred;
+  e->src = src;
+  e->dest = dst;
+  e->flags = flags;
+
+  src->succ = e;
+  dst->pred = e;
+
+  return e;
+}
+
 /* Create an edge connecting SRC and DST with FLAGS optionally using
    edge cache CACHE.  Return the new edge, NULL if already exist.  */
 
@@ -320,19 +346,7 @@ cached_make_edge (edge_cache, src, dst, 
       break;
     }
   
-  
-  e = pool_alloc (edge_pool);
-  memset (e, 0, sizeof (*e));
-  n_edges++;
-
-  e->succ_next = src->succ;
-  e->pred_next = dst->pred;
-  e->src = src;
-  e->dest = dst;
-  e->flags = flags;
-
-  src->succ = e;
-  dst->pred = e;
+  e = unchecked_make_edge (src, dst, flags);
 
   if (use_edge_cache)
     SET_BIT (edge_cache[src->index], dst->index);
===================================================================
RCS file: RCS/basic-block.h,v
retrieving revision 1.1
diff -u -p -r1.1 basic-block.h
--- basic-block.h	2003/03/09 17:39:23	1.1
+++ basic-block.h	2003/03/10 03:06:58
@@ -345,6 +345,8 @@ extern void remove_fake_edges		PARAMS ((
 extern void add_noreturn_fake_exit_edges	PARAMS ((void));
 extern void connect_infinite_loops_to_exit	PARAMS ((void));
 extern int flow_call_edges_add		PARAMS ((sbitmap));
+extern edge unchecked_make_edge		PARAMS ((basic_block,
+						 basic_block, int));
 extern edge cached_make_edge		PARAMS ((sbitmap *, basic_block,
 						 basic_block, int));
 extern edge make_edge			PARAMS ((basic_block,
===================================================================
RCS file: RCS/cfglayout.c,v
retrieving revision 1.1
diff -u -p -r1.1 cfglayout.c
--- cfglayout.c	2003/03/09 17:39:23	1.1
+++ cfglayout.c	2003/03/10 03:06:58
@@ -980,7 +980,7 @@ cfg_layout_duplicate_bb (bb, e)
   new_bb->flags = bb->flags;
   for (s = bb->succ; s; s = s->succ_next)
     {
-      n = make_edge (new_bb, s->dest, s->flags);
+      n = unchecked_make_edge (new_bb, s->dest, s->flags);
       n->probability = s->probability;
       if (new_count)
 	/* Take care for overflows!  */