* tree-cfg.c (edge_to_cases): Renamed from edge_to_case_leader. (edge_to_cases_elt): Renamed from edge_to_case_leader. (edge_to_cases_hash): Renamed from edge_to_case_leader_hash. (edge_to_cases_eq): Renamed from edge_to_case_leader_eq. (edge_to_cases_cleanup, recording_case_labels_p): New functions. (get_cases_for_edge): New function. (start_recording_case_labels, end_recording_case_labels): Similarly. (record_switch_edge): Don't muck with the CASE_LABEL. Instead chain equivalent CASE_LABEL_EXPRs together. (get_case_leader_for_edge, get_case_leader_for_edge_hash): Kill. (make_switch_expr_edges): Do not record edge/cases here. (cleanup_tree_cfg): Record cases around the call to thread_jumps. (split_critical_edges): Record cases around the edge splitting code. (cleanup_dead_labels): Use CASE_LABEL again. (tree_redirect_edge_and_branch): If we have a mapping from edge to cases, use it to handle redirections. Else do it the slow way. * tree.h (CASE_LEADER_OR_LABEL): Kill. (CASE_LABEL): Revert to just looking at the tree's second operand. * tree.c (get_case_label): Kill. Index: tree-cfg.c =================================================================== RCS file: /cvs/gcc/gcc/gcc/tree-cfg.c,v retrieving revision 2.108 diff -c -p -r2.108 tree-cfg.c *** tree-cfg.c 14 Nov 2004 04:08:04 -0000 2.108 --- tree-cfg.c 17 Nov 2004 19:09:50 -0000 *************** static const int initial_cfg_capacity = *** 58,86 **** building of the CFG in code with lots of gotos. */ static GTY(()) varray_type label_to_block_map; ! /* This hash table allows us to efficiently lookup the one and only one ! CASE_LABEL_EXPR which contains the LABEL_DECL for the target block ! of one or more case statements. Efficient access to this node ! allows us to efficiently update the case vector in response to ! edge redirections and similar operations. ! ! Right now this is only used to set up case label leaders. In the ! future we hope to make this table more persistent and use it to ! more efficiently update case labels. */ ! struct edge_to_case_leader_elt { /* The edge itself. Necessary for hashing and equality tests. */ edge e; ! /* The "leader" for all the CASE_LABEL_EXPRs which transfer control ! to E->dest. When we change the destination of E, we will need to ! update the CASE_LEADER_OR_LABEL of this CASE_LABEL_EXPR (and no ! others). */ ! tree case_label; }; ! static htab_t edge_to_case_leader; /* CFG statistics. */ struct cfg_stats_d --- 58,89 ---- building of the CFG in code with lots of gotos. */ static GTY(()) varray_type label_to_block_map; ! /* This hash table allows us to efficiently lookup all CASE_LABEL_EXPRs ! which use a particular edge. The CASE_LABEL_EXPRs are chained together ! via their TREE_CHAIN field, which we clear after we're done with the ! hash table to prevent problems with duplication of SWITCH_EXPRs. ! ! Access to this list of CASE_LABEL_EXPRs allows us to efficiently ! update the case vector in response to edge redirections. ! ! Right now this table is set up and torn down at key points in the ! compilation process. It would be nice if we could make the table ! more persistent. The key is getting notification of changes to ! the CFG (particularly edge removal, creation and redirection). */ ! struct edge_to_cases_elt { /* The edge itself. Necessary for hashing and equality tests. */ edge e; ! /* The case labels associated with this edge. We link these up via ! their TREE_CHAIN field, then we wipe out the TREE_CHAIN fields ! when we destroy the hash table. This prevents problems when copying ! SWITCH_EXPRs. */ ! tree case_labels; }; ! static htab_t edge_to_cases; /* CFG statistics. */ struct cfg_stats_d *************** make_cond_expr_edges (basic_block bb) *** 601,644 **** make_edge (bb, else_bb, EDGE_FALSE_VALUE); } ! /* Hashing routine for EDGE_TO_CASE_LEADER. */ static hashval_t ! edge_to_case_leader_hash (const void *p) { ! edge e = ((struct edge_to_case_leader_elt *)p)->e; /* Hash on the edge itself (which is a pointer). */ return htab_hash_pointer (e); } ! /* Equality routine for EDGE_TO_CASE_LEADER, edges are unique, so testing for equality is just a pointer comparison. */ static int ! edge_to_case_leader_eq (const void *p1, const void *p2) { ! edge e1 = ((struct edge_to_case_leader_elt *)p1)->e; ! edge e2 = ((struct edge_to_case_leader_elt *)p2)->e; return e1 == e2; } /* Record that CASE_LABEL (a CASE_LABEL_EXPR) references edge E. */ static void record_switch_edge (edge e, tree case_label) { ! struct edge_to_case_leader_elt *elt; void **slot; /* Build a hash table element so we can see if E is already in the table. */ ! elt = xmalloc (sizeof (struct edge_to_case_leader_elt)); elt->e = e; ! elt->case_label = case_label; ! slot = htab_find_slot (edge_to_case_leader, elt, INSERT); if (*slot == NULL) { --- 604,698 ---- make_edge (bb, else_bb, EDGE_FALSE_VALUE); } ! /* Hashing routine for EDGE_TO_CASES. */ static hashval_t ! edge_to_cases_hash (const void *p) { ! edge e = ((struct edge_to_cases_elt *)p)->e; /* Hash on the edge itself (which is a pointer). */ return htab_hash_pointer (e); } ! /* Equality routine for EDGE_TO_CASES, edges are unique, so testing for equality is just a pointer comparison. */ static int ! edge_to_cases_eq (const void *p1, const void *p2) { ! edge e1 = ((struct edge_to_cases_elt *)p1)->e; ! edge e2 = ((struct edge_to_cases_elt *)p2)->e; return e1 == e2; } + /* Called for each element in the hash table (P) as we delete the + edge to cases hash table. + + Clear all the TREE_CHAINs to prevent problems with copying of + SWITCH_EXPRs and structure sharing rules, then free the hash table + element. */ + + static void + edge_to_cases_cleanup (void *p) + { + struct edge_to_cases_elt *elt = p; + tree t, next; + + for (t = elt->case_labels; t; t = next) + { + next = TREE_CHAIN (t); + TREE_CHAIN (t) = NULL; + } + free (p); + } + + /* Start recording information mapping edges to case labels. */ + + static void + start_recording_case_labels (void) + { + gcc_assert (edge_to_cases == NULL); + + edge_to_cases = htab_create (37, + edge_to_cases_hash, + edge_to_cases_eq, + edge_to_cases_cleanup); + } + + /* Return nonzero if we are recording information for case labels. */ + + static bool + recording_case_labels_p (void) + { + return (edge_to_cases != NULL); + } + + /* Stop recording information mapping edges to case labels and + remove any information we have recorded. */ + static void + end_recording_case_labels (void) + { + htab_delete (edge_to_cases); + edge_to_cases = NULL; + } + /* Record that CASE_LABEL (a CASE_LABEL_EXPR) references edge E. */ static void record_switch_edge (edge e, tree case_label) { ! struct edge_to_cases_elt *elt; void **slot; /* Build a hash table element so we can see if E is already in the table. */ ! elt = xmalloc (sizeof (struct edge_to_cases_elt)); elt->e = e; ! elt->case_labels = case_label; ! slot = htab_find_slot (edge_to_cases, elt, INSERT); if (*slot == NULL) { *************** record_switch_edge (edge e, tree case_la *** 652,721 **** free (elt); /* Get the entry stored in the hash table. */ ! elt = (struct edge_to_case_leader_elt *) *slot; ! /* Make ELT->case_label the leader for CASE_LABEL. */ ! CASE_LEADER_OR_LABEL (case_label) = elt->case_label; } } ! /* Subroutine of get_case_leader_for_edge; returns the case leader for the ! chain of CASE_LABEL_EXPRs associated with E using a hash table lookup. */ static tree ! get_case_leader_for_edge_hash (edge e) { ! struct edge_to_case_leader_elt elt, *elt_p; void **slot; elt.e = e; ! elt.case_label = NULL; ! slot = htab_find_slot (edge_to_case_leader, &elt, NO_INSERT); if (slot) { ! tree t; ! ! elt_p = (struct edge_to_case_leader_elt *)*slot; ! t = elt_p->case_label; ! ! while (TREE_CODE (CASE_LEADER_OR_LABEL (t)) == CASE_LABEL_EXPR) ! t = CASE_LEADER_OR_LABEL (t); ! return t; } ! return NULL; ! } ! ! /* Given an edge E, return the case leader for the chain of CASE_LABEL_EXPRs ! which use E. */ ! ! static tree ! get_case_leader_for_edge (edge e) ! { ! tree vec, stmt; ! size_t i, n; ! /* If we have a hash table, then use it as it's significantly faster. */ ! if (edge_to_case_leader) ! return get_case_leader_for_edge_hash (e); ! ! /* No hash table. We have to walk the case vector. */ ! stmt = bsi_stmt (bsi_last (e->src)); ! vec = SWITCH_LABELS (stmt); n = TREE_VEC_LENGTH (vec); - for (i = 0; i < n; i++) { ! tree elt = TREE_VEC_ELT (vec, i); ! tree t = CASE_LEADER_OR_LABEL (elt); ! ! if (TREE_CODE (t) == LABEL_DECL ! && label_to_block (t) == e->dest) ! return elt; } ! ! abort (); } /* Create the edges for a SWITCH_EXPR starting at block BB. --- 706,761 ---- free (elt); /* Get the entry stored in the hash table. */ ! elt = (struct edge_to_cases_elt *) *slot; ! /* Add it to the chain of CASE_LABEL_EXPRs referencing E. */ ! TREE_CHAIN (case_label) = elt->case_labels; ! elt->case_labels = case_label; } } ! /* If we are inside a {start,end}_recording_cases block, then return ! a chain of CASE_LABEL_EXPRs from T which reference E. ! ! Otherwise return NULL. */ static tree ! get_cases_for_edge (edge e, tree t) { ! struct edge_to_cases_elt elt, *elt_p; void **slot; + size_t i, n; + tree vec; + /* If we are not recording cases, then we do not have CASE_LABEL_EXPR + chains available. Return NULL so the caller can detect this case. */ + if (!recording_case_labels_p ()) + return NULL; + + restart: elt.e = e; ! elt.case_labels = NULL; ! slot = htab_find_slot (edge_to_cases, &elt, NO_INSERT); if (slot) { ! elt_p = (struct edge_to_cases_elt *)*slot; ! return elt_p->case_labels; } ! /* If we did not find E in the hash table, then this must be the first ! time we have been queried for information about E & T. Add all the ! elements from T to the hash table then perform the query again. */ ! vec = SWITCH_LABELS (t); n = TREE_VEC_LENGTH (vec); for (i = 0; i < n; i++) { ! tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i)); ! basic_block label_bb = label_to_block (lab); ! record_switch_edge (find_edge (e->src, label_bb), TREE_VEC_ELT (vec, i)); } ! goto restart; } /* Create the edges for a SWITCH_EXPR starting at block BB. *************** make_switch_expr_edges (basic_block bb) *** 732,753 **** vec = SWITCH_LABELS (entry); n = TREE_VEC_LENGTH (vec); - edge_to_case_leader - = htab_create (n, edge_to_case_leader_hash, edge_to_case_leader_eq, free); - for (i = 0; i < n; ++i) { tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i)); basic_block label_bb = label_to_block (lab); ! edge e = make_edge (bb, label_bb, 0); ! ! if (!e) ! e = find_edge (bb, label_bb); ! ! record_switch_edge (e, TREE_VEC_ELT (vec, i)); } - htab_delete (edge_to_case_leader); - edge_to_case_leader = NULL; } --- 772,783 ---- vec = SWITCH_LABELS (entry); n = TREE_VEC_LENGTH (vec); for (i = 0; i < n; ++i) { tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i)); basic_block label_bb = label_to_block (lab); ! make_edge (bb, label_bb, 0); } } *************** cleanup_tree_cfg (void) *** 869,875 **** --- 899,911 ---- retval = cleanup_control_flow (); retval |= delete_unreachable_blocks (); + + /* thread_jumps can redirect edges out of SWITCH_EXPRs, which can get + expensive. So we want to enable recording of edge to CASE_LABEL_EXPR + mappings around the call to thread_jumps. */ + start_recording_case_labels (); retval |= thread_jumps (); + end_recording_case_labels (); #ifdef ENABLE_CHECKING if (retval) *************** cleanup_dead_labels (void) *** 1019,1025 **** { tree elt = TREE_VEC_ELT (vec, i); tree label = main_block_label (CASE_LABEL (elt)); ! CASE_LEADER_OR_LABEL (elt) = label; } break; } --- 1055,1061 ---- { tree elt = TREE_VEC_ELT (vec, i); tree label = main_block_label (CASE_LABEL (elt)); ! CASE_LABEL (elt) = label; } break; } *************** tree_redirect_edge_and_branch (edge e, b *** 4290,4319 **** case SWITCH_EXPR: { ! edge e2; ! ! /* We need to update the LABEL_DECL in the switch vector to ! reflect the edge redirection. ! There is precisely one CASE_LABEL_EXPR in the switch vector ! which needs updating. Either its label needs to be updated ! or it needs to be directed to a new case leader. */ ! e2 = find_edge (e->src, dest); ! if (e2) { ! /* In this case we need to change the case leader for the ! current leader of E to be the case leader for E2. */ ! tree e_leader = get_case_leader_for_edge (e); ! tree e2_leader = get_case_leader_for_edge (e2); ! CASE_LEADER_OR_LABEL (e_leader) = e2_leader; } else { ! /* No edge exists from E->src to DEST, so we will simply ! change E->dest. The case leader does not change, but ! the LABEL_DECL for the leader does change. */ ! CASE_LEADER_OR_LABEL (get_case_leader_for_edge (e)) = label; } break; } --- 4326,4372 ---- case SWITCH_EXPR: { ! tree cases = get_cases_for_edge (e, stmt); ! edge e2 = find_edge (e->src, dest); ! /* If we have a list of cases associated with E, then use it ! as it's a lot faster than walking the entire case vector. */ ! if (cases) { ! tree last, first; ! ! first = cases; ! while (cases) ! { ! last = cases; ! CASE_LABEL (cases) = label; ! cases = TREE_CHAIN (cases); ! } ! ! /* If there was already an edge in the CFG, then we need ! to move all the cases associated with E to E2. */ ! if (e2) ! { ! tree cases2 = get_cases_for_edge (e2, stmt); ! ! TREE_CHAIN (last) = TREE_CHAIN (cases2); ! TREE_CHAIN (cases2) = first; ! } } else { ! tree vec = SWITCH_LABELS (stmt); ! size_t i, n = TREE_VEC_LENGTH (vec); ! ! for (i = 0; i < n; i++) ! { ! tree elt = TREE_VEC_ELT (vec, i); ! ! if (label_to_block (CASE_LABEL (elt)) == e->dest) ! CASE_LABEL (elt) = label; ! } } + break; } *************** split_critical_edges (void) *** 5329,5334 **** --- 5382,5391 ---- edge e; edge_iterator ei; + /* split_edge can redirect edges out of SWITCH_EXPRs, which can get + expensive. So we want to enable recording of edge to CASE_LABEL_EXPR + mappings around the calls to split_edge. */ + start_recording_case_labels (); FOR_ALL_BB (bb) { FOR_EACH_EDGE (e, ei, bb->succs) *************** split_critical_edges (void) *** 5337,5342 **** --- 5394,5400 ---- split_edge (e); } } + end_recording_case_labels (); } struct tree_opt_pass pass_split_crit_edges = Index: tree.c =================================================================== RCS file: /cvs/gcc/gcc/gcc/tree.c,v retrieving revision 1.448 diff -c -p -r1.448 tree.c *** tree.c 15 Nov 2004 00:18:33 -0000 1.448 --- tree.c 17 Nov 2004 19:09:53 -0000 *************** signed_type_for (tree type) *** 6061,6079 **** return lang_hooks.types.signed_type (type); } - /* Return the LABEL_DECL associated with T, which must be a - CASE_LABEL_EXPR. This will walk through any CASE_LABEL_EXPRs - appearing in operand 2 until it finds a CASE_LABEL_EXPR with - a LABEL_DECL in operand 2. */ - - tree - get_case_label (tree t) - { - while (TREE_CODE (CASE_LEADER_OR_LABEL (t)) == CASE_LABEL_EXPR) - t = CASE_LEADER_OR_LABEL (t); - return CASE_LEADER_OR_LABEL (t); - } - /* Returns the largest value obtainable by casting something in INNER type to OUTER type. */ --- 6061,6066 ---- Index: tree.h =================================================================== RCS file: /cvs/gcc/gcc/gcc/tree.h,v retrieving revision 1.655 diff -c -p -r1.655 tree.h *** tree.h 15 Nov 2004 00:18:33 -0000 1.655 --- tree.h 17 Nov 2004 19:09:54 -0000 *************** struct tree_vec GTY(()) *** 1231,1245 **** of a case label, respectively. */ #define CASE_LOW(NODE) TREE_OPERAND ((NODE), 0) #define CASE_HIGH(NODE) TREE_OPERAND ((NODE), 1) ! ! /* Operand 2 has two uses, it may either be a LABEL_DECL node or a ! another CASE_LABEL_EXPR node. This accessor gets direct access ! to that operand. Use it when you want to assign a value to ! operand 2 or when you want to conditionalize actions based on ! whether operand 2 is a LABEL_DECL or CASE_LABEL_EXPR. */ ! #define CASE_LEADER_OR_LABEL(NODE) TREE_OPERAND ((NODE), 2) ! ! #define CASE_LABEL(NODE) get_case_label (NODE) /* The operands of a BIND_EXPR. */ #define BIND_EXPR_VARS(NODE) (TREE_OPERAND (BIND_EXPR_CHECK (NODE), 0)) --- 1231,1237 ---- of a case label, respectively. */ #define CASE_LOW(NODE) TREE_OPERAND ((NODE), 0) #define CASE_HIGH(NODE) TREE_OPERAND ((NODE), 1) ! #define CASE_LABEL(NODE) TREE_OPERAND ((NODE), 2) /* The operands of a BIND_EXPR. */ #define BIND_EXPR_VARS(NODE) (TREE_OPERAND (BIND_EXPR_CHECK (NODE), 0))