This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] cfgbuild.c: Speed up make_edges.
- From: Kazu Hirata <kazu at cs dot umass dot edu>
- To: gcc-patches at gcc dot gnu dot org
- Date: Mon, 07 Mar 2005 20:46:54 -0500 (EST)
- Subject: [patch] cfgbuild.c: Speed up make_edges.
Hi,
Attached is a patch to speed up make_edges.
find_many_sub_basic_blocks and make_edges are used to fix up CFG after
non-CFG-aware changes are made, such as expansion from tree to RTL and
insn splitting.
The problem is that the current code also tries to fix up basic blocks
that have not changed.
The patch speeds up make_edges by skipping basic blocks that have not
changed. Specifically, with the patch, make_edges skips those basic
blocks with BLOCK_ORIGINAL.
Here is a timing in seconds for five runs of ./cc1 -quiet -O2
-fomit-frame-pointer -o /dev/null.
original patched diff%
----------------------------------------------
c-common.i 13.857 13.767 -0.649%
combine.i 16.741 16.728 -0.077%
fold-const.i 18.295 18.210 -0.464%
reload1.i 11.958 11.956 -0.016%
reload.i 11.859 11.840 -0.160%
insn-attrtab.i 207.372 206.232 -0.549%
#unchecked_make_edge 948010 948010 0.000%
#cached_make_edge 1483573 759126 -48.831%
#make_edge 1642690 1181173 -28.095%
#foo is the number of times foo is called while compiling cc1-i files.
Note that the number of times unchecked_make_edge is called stays
unchanged with this patch.
Tested on i686-pc-linux-gnu. OK to apply?
Kazu Hirata
2005-03-08 Kazu Hirata <kazu@cs.umass.edu>
* cfgbuild.c (state, STATE, SET_STATE,
BLOCK_USED_BY_TABLEJUMP, FULL_STATE): Move just before
make_edges.
(make_edges): Speed up by skipping blocks with BLOCK_ORIGINAL.
(find_basic_blocks): Set the state of each basic block to
BLOCK_NEW.
Index: cfgbuild.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgbuild.c,v
retrieving revision 1.62
diff -u -d -p -r1.62 cfgbuild.c
--- cfgbuild.c 7 Mar 2005 13:55:57 -0000 1.62
+++ cfgbuild.c 7 Mar 2005 16:54:49 -0000
@@ -211,6 +211,16 @@ rtl_make_eh_edge (sbitmap *edge_cache, b
free_INSN_LIST_list (&handlers);
}
+/* State of basic block as seen by find_many_sub_basic_blocks. */
+enum state {BLOCK_NEW = 0, BLOCK_ORIGINAL, BLOCK_TO_SPLIT};
+
+#define STATE(BB) (enum state) ((size_t) (BB)->aux)
+#define SET_STATE(BB, STATE) ((BB)->aux = (void *) (size_t) (STATE))
+
+/* Used internally by purge_dead_tablejump_edges, ORed into state. */
+#define BLOCK_USED_BY_TABLEJUMP 32
+#define FULL_STATE(BB) ((size_t) (BB)->aux)
+
/* Identify the edges between basic blocks MIN to MAX.
NONLOCAL_LABEL_LIST is a list of non-local labels in the function. Blocks
@@ -234,15 +244,18 @@ make_edges (basic_block min, basic_block
sbitmap_vector_zero (edge_cache, last_basic_block);
if (update_p)
- FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb)
- {
- edge e;
- edge_iterator ei;
-
- FOR_EACH_EDGE (e, ei, bb->succs)
- if (e->dest != EXIT_BLOCK_PTR)
- SET_BIT (edge_cache[bb->index], e->dest->index);
- }
+ {
+ FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb)
+ if (STATE (bb) != BLOCK_ORIGINAL)
+ {
+ edge e;
+ edge_iterator ei;
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (e->dest != EXIT_BLOCK_PTR)
+ SET_BIT (edge_cache[bb->index], e->dest->index);
+ }
+ }
}
/* By nature of the way these get numbered, ENTRY_BLOCK_PTR->next_bb block
@@ -257,6 +270,9 @@ make_edges (basic_block min, basic_block
enum rtx_code code;
edge e;
+ if (STATE (bb) == BLOCK_ORIGINAL)
+ continue;
+
if (LABEL_P (BB_HEAD (bb))
&& LABEL_ALT_ENTRY_P (BB_HEAD (bb)))
cached_make_edge (NULL, ENTRY_BLOCK_PTR, bb, 0);
@@ -522,6 +538,9 @@ find_basic_blocks (rtx f)
profile_status = PROFILE_ABSENT;
+ FOR_EACH_BB (bb)
+ SET_STATE (bb, BLOCK_NEW);
+
/* Discover the edges of our cfg. */
make_edges (ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR->prev_bb, 0);
@@ -535,16 +554,6 @@ find_basic_blocks (rtx f)
timevar_pop (TV_CFG);
}
-/* State of basic block as seen by find_many_sub_basic_blocks. */
-enum state {BLOCK_NEW = 0, BLOCK_ORIGINAL, BLOCK_TO_SPLIT};
-
-#define STATE(BB) (enum state) ((size_t) (BB)->aux)
-#define SET_STATE(BB, STATE) ((BB)->aux = (void *) (size_t) (STATE))
-
-/* Used internally by purge_dead_tablejump_edges, ORed into state. */
-#define BLOCK_USED_BY_TABLEJUMP 32
-#define FULL_STATE(BB) ((size_t) (BB)->aux)
-
static void
mark_tablejump_edge (rtx label)
{