From 0f69b26633846fc6227dacd6bec1ad50dba7c420 Mon Sep 17 00:00:00 2001 From: rakdver Date: Mon, 14 Mar 2005 15:19:56 +0000 Subject: [PATCH] * basic-block.h (BB_VISITED): Removed. * cfganal.c (dfs_enumerate_from): Do not use BB_VISITED flag. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@96434 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/ChangeLog | 5 +++++ gcc/basic-block.h | 44 +++++++++++++++++++++----------------------- gcc/cfganal.c | 50 ++++++++++++++++++++++++++++++++++++++++++++------ 3 files changed, 70 insertions(+), 29 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 6fb6f6d..abce9f2 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,8 @@ +2005-03-14 Zdenek Dvorak + + * basic-block.h (BB_VISITED): Removed. + * cfganal.c (dfs_enumerate_from): Do not use BB_VISITED flag. + 2005-03-14 Falk Hueffner PR bootstrap/20424 diff --git a/gcc/basic-block.h b/gcc/basic-block.h index 0821dc5..bc5f448 100644 --- a/gcc/basic-block.h +++ b/gcc/basic-block.h @@ -287,43 +287,41 @@ typedef struct reorder_block_def /* Masks for basic_block.flags. - BB_VISITED should not be used by passes, it is used internally by - dfs_enumerate_from. - BB_HOT_PARTITION and BB_COLD_PARTITION should be preserved throughout the compilation, so they are never cleared. All other flags may be cleared by clear_bb_flags(). It is generally a bad idea to rely on any flags being up-to-date. */ -/* Set if insns in BB have are modified. Used for updating liveness info. */ -#define BB_DIRTY 1 +enum +{ -/* Only set on blocks that have just been created by create_bb. */ -#define BB_NEW 2 + /* Set if insns in BB have are modified. Used for updating liveness info. */ + BB_DIRTY = 1, -/* Set by find_unreachable_blocks. Do not rely on this being set in any - pass. */ -#define BB_REACHABLE 4 + /* Only set on blocks that have just been created by create_bb. */ + BB_NEW = 2, -/* Used by dfs_enumerate_from to keep track of visited basic blocks. */ -#define BB_VISITED 8 + /* Set by find_unreachable_blocks. Do not rely on this being set in any + pass. */ + BB_REACHABLE = 4, -/* Set for blocks in an irreducible loop by loop analysis. */ -#define BB_IRREDUCIBLE_LOOP 16 + /* Set for blocks in an irreducible loop by loop analysis. */ + BB_IRREDUCIBLE_LOOP = 8, -/* Set on blocks that may actually not be single-entry single-exit block. */ -#define BB_SUPERBLOCK 32 + /* Set on blocks that may actually not be single-entry single-exit block. */ + BB_SUPERBLOCK = 16, -/* Set on basic blocks that the scheduler should not touch. This is used - by SMS to prevent other schedulers from messing with the loop schedule. */ -#define BB_DISABLE_SCHEDULE 64 + /* Set on basic blocks that the scheduler should not touch. This is used + by SMS to prevent other schedulers from messing with the loop schedule. */ + BB_DISABLE_SCHEDULE = 32, -/* Set on blocks that should be put in a hot section. */ -#define BB_HOT_PARTITION 128 + /* Set on blocks that should be put in a hot section. */ + BB_HOT_PARTITION = 64, -/* Set on blocks that should be put in a cold section. */ -#define BB_COLD_PARTITION 256 + /* Set on blocks that should be put in a cold section. */ + BB_COLD_PARTITION = 128 +}; /* Dummy flag for convenience in the hot/cold partitioning code. */ #define BB_UNPARTITIONED 0 diff --git a/gcc/cfganal.c b/gcc/cfganal.c index 7cecd98..5afbabc 100644 --- a/gcc/cfganal.c +++ b/gcc/cfganal.c @@ -900,10 +900,45 @@ dfs_enumerate_from (basic_block bb, int reverse, { basic_block *st, lbb; int sp = 0, tv = 0; + unsigned size; + + /* A bitmap to keep track of visited blocks. Allocating it each time + this function is called is not possible, since dfs_enumerate_from + is often used on small (almost) disjoint parts of cfg (bodies of + loops), and allocating a large sbitmap would lead to quadratic + behavior. */ + static sbitmap visited; + static unsigned v_size; + +#define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index + 2)) +#define UNMARK_VISITED(BB) (RESET_BIT (visited, (BB)->index + 2)) +#define VISITED_P(BB) (TEST_BIT (visited, (BB)->index + 2)) + + /* Resize the VISITED sbitmap if necessary. */ + size = last_basic_block + 2; + if (size < 10) + size = 10; + + if (!visited) + { + + visited = sbitmap_alloc (size); + sbitmap_zero (visited); + v_size = size; + } + else if (v_size < size) + { + /* Ensure that we increase the size of the sbitmap exponentially. */ + if (2 * v_size > size) + size = 2 * v_size; + + visited = sbitmap_resize (visited, size, 0); + v_size = size; + } st = xcalloc (rslt_max, sizeof (basic_block)); rslt[tv++] = st[sp++] = bb; - bb->flags |= BB_VISITED; + MARK_VISITED (bb); while (sp) { edge e; @@ -912,28 +947,31 @@ dfs_enumerate_from (basic_block bb, int reverse, if (reverse) { FOR_EACH_EDGE (e, ei, lbb->preds) - if (!(e->src->flags & BB_VISITED) && predicate (e->src, data)) + if (!VISITED_P (e->src) && predicate (e->src, data)) { gcc_assert (tv != rslt_max); rslt[tv++] = st[sp++] = e->src; - e->src->flags |= BB_VISITED; + MARK_VISITED (e->src); } } else { FOR_EACH_EDGE (e, ei, lbb->succs) - if (!(e->dest->flags & BB_VISITED) && predicate (e->dest, data)) + if (!VISITED_P (e->dest) && predicate (e->dest, data)) { gcc_assert (tv != rslt_max); rslt[tv++] = st[sp++] = e->dest; - e->dest->flags |= BB_VISITED; + MARK_VISITED (e->dest); } } } free (st); for (sp = 0; sp < tv; sp++) - rslt[sp]->flags &= ~BB_VISITED; + UNMARK_VISITED (rslt[sp]); return tv; +#undef MARK_VISITED +#undef UNMARK_VISITED +#undef VISITED_P } -- 2.7.4