From dbf08f94a7e5f45d6fbfa1ba461fee95cd3b3b87 Mon Sep 17 00:00:00 2001 From: Richard Henderson Date: Tue, 5 Oct 1999 12:01:01 -0700 Subject: [PATCH] flow.c (make_edge): Accept an optional 2D bitmap in which to cache edge existence. * flow.c (make_edge): Accept an optional 2D bitmap in which to cache edge existence. Update all callers. (make_label_edge, make_eh_edge): Pass through the edge cache. (make_edges): Provide the cache. From-SVN: r29828 --- gcc/ChangeLog | 7 +++++ gcc/flow.c | 92 ++++++++++++++++++++++++++++++++++++++++------------------- 2 files changed, 69 insertions(+), 30 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index f91f855..0da5b3a 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,10 @@ +Tue Oct 5 12:00:32 1999 Richard Henderson + + * flow.c (make_edge): Accept an optional 2D bitmap in which + to cache edge existence. Update all callers. + (make_label_edge, make_eh_edge): Pass through the edge cache. + (make_edges): Provide the cache. + Tue Oct 5 12:16:49 1999 Kaveh R. Ghazi * mbchar.c (literal_codeset, local_mbtowc, local_mblen): Constify diff --git a/gcc/flow.c b/gcc/flow.c index f883d80..5e2ec61 100644 --- a/gcc/flow.c +++ b/gcc/flow.c @@ -280,10 +280,12 @@ static rtx find_basic_blocks_1 PROTO((rtx)); static void create_basic_block PROTO((int, rtx, rtx, rtx)); static void clear_edges PROTO((void)); static void make_edges PROTO((rtx)); -static void make_edge PROTO((basic_block, basic_block, int)); -static void make_label_edge PROTO((basic_block, rtx, int)); -static void make_eh_edge PROTO((eh_nesting_info *, basic_block, +static void make_edge PROTO((sbitmap *, basic_block, + basic_block, int)); +static void make_label_edge PROTO((sbitmap *, basic_block, rtx, int)); +static void make_eh_edge PROTO((sbitmap *, eh_nesting_info *, + basic_block, rtx, int)); static void mark_critical_edges PROTO((void)); static void move_stray_eh_region_notes PROTO((void)); static void record_active_eh_regions PROTO((rtx)); @@ -879,12 +881,22 @@ make_edges (label_value_list) { int i; eh_nesting_info *eh_nest_info = init_eh_nesting_info (); + sbitmap *edge_cache = NULL; /* Assume no computed jump; revise as we create edges. */ current_function_has_computed_jump = 0; + /* Heavy use of computed goto in machine-generated code can lead to + nearly fully-connected CFGs. In that case we spend a significant + amount of time searching the edge lists for duplicates. */ + if (forced_labels || label_value_list) + { + edge_cache = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks); + sbitmap_vector_zero (edge_cache, n_basic_blocks); + } + /* By nature of the way these get numbered, block 0 is always the entry. */ - make_edge (ENTRY_BLOCK_PTR, BASIC_BLOCK (0), EDGE_FALLTHRU); + make_edge (edge_cache, ENTRY_BLOCK_PTR, BASIC_BLOCK (0), EDGE_FALLTHRU); for (i = 0; i < n_basic_blocks; ++i) { @@ -920,7 +932,8 @@ make_edges (label_value_list) vec = XVEC (PATTERN (tmp), 1); for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j) - make_label_edge (bb, XEXP (RTVEC_ELT (vec, j), 0), 0); + make_label_edge (edge_cache, bb, + XEXP (RTVEC_ELT (vec, j), 0), 0); /* Some targets (eg, ARM) emit a conditional jump that also contains the out-of-range target. Scan for these and @@ -929,7 +942,8 @@ make_edges (label_value_list) && SET_DEST (tmp) == pc_rtx && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF) - make_label_edge (bb, XEXP (XEXP (SET_SRC (tmp), 2), 0), 0); + make_label_edge (edge_cache, bb, + XEXP (XEXP (SET_SRC (tmp), 2), 0), 0); #ifdef CASE_DROPS_THROUGH /* Silly VAXen. The ADDR_VEC is going to be in the way of @@ -945,22 +959,22 @@ make_edges (label_value_list) current_function_has_computed_jump = 1; for (x = label_value_list; x; x = XEXP (x, 1)) - make_label_edge (bb, XEXP (x, 0), EDGE_ABNORMAL); + make_label_edge (edge_cache, bb, XEXP (x, 0), EDGE_ABNORMAL); for (x = forced_labels; x; x = XEXP (x, 1)) - make_label_edge (bb, XEXP (x, 0), EDGE_ABNORMAL); + make_label_edge (edge_cache, bb, XEXP (x, 0), EDGE_ABNORMAL); } /* Returns create an exit out. */ else if (returnjump_p (insn)) - make_edge (bb, EXIT_BLOCK_PTR, 0); + make_edge (edge_cache, bb, EXIT_BLOCK_PTR, 0); /* Otherwise, we have a plain conditional or unconditional jump. */ else { if (! JUMP_LABEL (insn)) abort (); - make_label_edge (bb, JUMP_LABEL (insn), 0); + make_label_edge (edge_cache, bb, JUMP_LABEL (insn), 0); } } @@ -975,7 +989,7 @@ make_edges (label_value_list) /* If there's an EH region active at the end of a block, add the appropriate edges. */ if (bb->eh_end >= 0) - make_eh_edge (eh_nest_info, bb, insn, bb->eh_end); + make_eh_edge (edge_cache, eh_nest_info, bb, insn, bb->eh_end); /* If we have asynchronous exceptions, do the same for *all* exception regions active in the block. */ @@ -983,7 +997,8 @@ make_edges (label_value_list) && bb->eh_beg != bb->eh_end) { if (bb->eh_beg >= 0) - make_eh_edge (eh_nest_info, bb, NULL_RTX, bb->eh_beg); + make_eh_edge (edge_cache, eh_nest_info, bb, + NULL_RTX, bb->eh_beg); for (x = bb->head; x != bb->end; x = NEXT_INSN (x)) if (GET_CODE (x) == NOTE @@ -991,7 +1006,8 @@ make_edges (label_value_list) || NOTE_LINE_NUMBER (x) == NOTE_INSN_EH_REGION_END)) { int region = NOTE_EH_HANDLER (x); - make_eh_edge (eh_nest_info, bb, NULL_RTX, region); + make_eh_edge (edge_cache, eh_nest_info, bb, + NULL_RTX, region); } } @@ -1009,7 +1025,7 @@ make_edges (label_value_list) rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX); if (!note || XINT (XEXP (note, 0), 0) >= 0) for (x = nonlocal_goto_handler_labels; x ; x = XEXP (x, 1)) - make_label_edge (bb, XEXP (x, 0), + make_label_edge (edge_cache, bb, XEXP (x, 0), EDGE_ABNORMAL | EDGE_ABNORMAL_CALL); } } @@ -1020,42 +1036,53 @@ make_edges (label_value_list) returns to one of the eh_stub labels within it. So we have to make additional edges in the flow graph. */ if (i + 1 == n_basic_blocks && eh_return_stub_label != 0) - make_label_edge (bb, eh_return_stub_label, EDGE_EH); + make_label_edge (edge_cache, bb, eh_return_stub_label, EDGE_EH); /* Find out if we can drop through to the next block. */ insn = next_nonnote_insn (insn); if (!insn || (i + 1 == n_basic_blocks && force_fallthru)) - make_edge (bb, EXIT_BLOCK_PTR, EDGE_FALLTHRU); + make_edge (edge_cache, bb, EXIT_BLOCK_PTR, EDGE_FALLTHRU); else if (i + 1 < n_basic_blocks) { rtx tmp = BLOCK_HEAD (i + 1); if (GET_CODE (tmp) == NOTE) tmp = next_nonnote_insn (tmp); if (force_fallthru || insn == tmp) - make_edge (bb, BASIC_BLOCK (i + 1), EDGE_FALLTHRU); + make_edge (edge_cache, bb, BASIC_BLOCK (i + 1), EDGE_FALLTHRU); } } + free_eh_nesting_info (eh_nest_info); + if (edge_cache) + sbitmap_vector_free (edge_cache); } /* Create an edge between two basic blocks. FLAGS are auxiliary information about the edge that is accumulated between calls. */ static void -make_edge (src, dst, flags) +make_edge (edge_cache, src, dst, flags) + sbitmap *edge_cache; basic_block src, dst; int flags; { + int use_edge_cache; edge e; - /* Make sure we don't add duplicate edges. */ + /* Don't bother with edge cache for ENTRY or EXIT; there aren't that + many edges to them, and we didn't allocate memory for it. */ + use_edge_cache = (edge_cache + && src != ENTRY_BLOCK_PTR + && dst != EXIT_BLOCK_PTR); - for (e = src->succ; e ; e = e->succ_next) - if (e->dest == dst) - { - e->flags |= flags; - return; - } + /* Make sure we don't add duplicate edges. */ + if (! use_edge_cache || TEST_BIT (edge_cache[src->index], dst->index)) + for (e = src->succ; e ; e = e->succ_next) + if (e->dest == dst) + { + e->flags |= flags; + return; + } e = (edge) xcalloc (1, sizeof (*e)); @@ -1067,12 +1094,16 @@ make_edge (src, dst, flags) src->succ = e; dst->pred = e; + + if (use_edge_cache) + SET_BIT (edge_cache[src->index], dst->index); } /* Create an edge from a basic block to a label. */ static void -make_label_edge (src, label, flags) +make_label_edge (edge_cache, src, label, flags) + sbitmap *edge_cache; basic_block src; rtx label; int flags; @@ -1088,13 +1119,14 @@ make_label_edge (src, label, flags) if (INSN_UID (label) == 0) return; - make_edge (src, BLOCK_FOR_INSN (label), flags); + make_edge (edge_cache, src, BLOCK_FOR_INSN (label), flags); } /* Create the edges generated by INSN in REGION. */ static void -make_eh_edge (eh_nest_info, src, insn, region) +make_eh_edge (edge_cache, eh_nest_info, src, insn, region) + sbitmap *edge_cache; eh_nesting_info *eh_nest_info; basic_block src; rtx insn; @@ -1107,7 +1139,7 @@ make_eh_edge (eh_nest_info, src, insn, region) num = reachable_handlers (region, eh_nest_info, insn, &handler_list); while (--num >= 0) { - make_label_edge (src, handler_list[num]->handler_label, + make_label_edge (edge_cache, src, handler_list[num]->handler_label, EDGE_ABNORMAL | EDGE_EH | is_call); } } @@ -6989,5 +7021,5 @@ add_noreturn_fake_exit_edges () for (x = 0; x < n_basic_blocks; x++) if (BASIC_BLOCK (x)->succ == NULL) - make_edge (BASIC_BLOCK (x), EXIT_BLOCK_PTR, EDGE_FAKE); + make_edge (NULL, BASIC_BLOCK (x), EXIT_BLOCK_PTR, EDGE_FAKE); } -- 2.7.4