2009-06-22 Jakub Jelinek * var-tracking.c (unshare_variable): Force initialized to be VAR_INIT_STATUS_INITIALIZED unless flag_var_tracking_uninit. (set_variable_part): Likewise. (struct variable_union_info): Remove pos_src field. (vui_vec, vui_buf, vui_allocated): New variables. (variable_union): Pass VAR_INIT_STATUS_UNKNOWN to unshare_variable unconditionally. Avoid XCVECNEW/free for every sorting, for dst_l == 1 use a simpler sorting algorithm. Compute pos field right away, don't fill in pos_src. For dst_l == 2 avoid qsort. Avoid quadratic comparison if !flag_var_tracking_uninit. (variable_canonicalize): Pass VAR_INIT_STATUS_UNKNOWN to unshare_variable unconditionally. (dataflow_set_different_2): Removed. (dataflow_set_different): Don't traverse second hash table. (compute_bb_dataflow): Pass VAR_INIT_STATUS_UNINITIALIZED unconditionally to var_reg_set or var_mem_set. (emit_notes_in_bb): Likewise. (delete_variable_part): Pass VAR_INIT_STATUS_UNKNOWN to unshare_variable. (emit_note_insn_var_location): Don't set initialized to VAR_INIT_STATUS_INITIALIZED early. (vt_finalize): Free vui_vec if needed, clear vui_vec and vui_allocated. * rtl.c (rtx_equal_p): Don't implement on top of rtx_equal_p_cb. --- gcc/var-tracking.c.jj 2009-06-22 12:45:35.000000000 +0200 +++ gcc/var-tracking.c 2009-06-23 12:03:20.000000000 +0200 @@ -347,7 +347,6 @@ static void dataflow_set_union (dataflow static bool variable_part_different_p (variable_part *, variable_part *); static bool variable_different_p (variable, variable, bool); static int dataflow_set_different_1 (void **, void *); -static int dataflow_set_different_2 (void **, void *); static bool dataflow_set_different (dataflow_set *, dataflow_set *); static void dataflow_set_destroy (dataflow_set *); @@ -878,6 +877,9 @@ unshare_variable (dataflow_set *set, var var->refcount--; new_var->n_var_parts = var->n_var_parts; + if (! flag_var_tracking_uninit) + initialized = VAR_INIT_STATUS_INITIALIZED; + for (i = 0; i < var->n_var_parts; i++) { location_chain node; @@ -1202,11 +1204,15 @@ struct variable_union_info /* The sum of positions in the input chains. */ int pos; - /* The position in the chains of SRC and DST dataflow sets. */ - int pos_src; + /* The position in the chain of DST dataflow set. */ int pos_dst; }; +/* Buffer for location list sorting and its allocated size. */ +static struct variable_union_info *vui_vec; +static int vui_allocated; +static struct variable_union_info vui_buf[16]; + /* Compare function for qsort, order the structures by POS element. */ static int @@ -1263,14 +1269,9 @@ variable_union (void **slot, void *data) } if (k < src->n_var_parts) { - enum var_init_status status = VAR_INIT_STATUS_UNKNOWN; - - if (! flag_var_tracking_uninit) - status = VAR_INIT_STATUS_INITIALIZED; - if (dstp) *dstp = (void *) src; - unshare_variable (set, src, status); + unshare_variable (set, src, VAR_INIT_STATUS_UNKNOWN); } else { @@ -1311,13 +1312,7 @@ variable_union (void **slot, void *data) if ((dst->refcount > 1 || shared_hash_shared (set->vars)) && dst->n_var_parts != k) - { - enum var_init_status status = VAR_INIT_STATUS_UNKNOWN; - - if (! flag_var_tracking_uninit) - status = VAR_INIT_STATUS_INITIALIZED; - dst = unshare_variable (set, dst, status); - } + dst = unshare_variable (set, dst, VAR_INIT_STATUS_UNKNOWN); i = src->n_var_parts - 1; j = dst->n_var_parts - 1; @@ -1366,70 +1361,157 @@ variable_union (void **slot, void *data) dst_l = 0; for (node = dst->var_part[j].loc_chain; node; node = node->next) dst_l++; - vui = XCNEWVEC (struct variable_union_info, src_l + dst_l); - /* Fill in the locations from DST. */ - for (node = dst->var_part[j].loc_chain, jj = 0; node; - node = node->next, jj++) + if (dst_l == 1) { - vui[jj].lc = node; - vui[jj].pos_dst = jj; + /* The most common case, much simpler, no qsort is needed. */ + location_chain dstnode = dst->var_part[j].loc_chain; + dst->var_part[k].loc_chain = dstnode; + dst->var_part[k].offset = dst->var_part[j].offset; + node2 = dstnode; + for (node = src->var_part[i].loc_chain; node; node = node->next) + if (!((REG_P (dstnode->loc) + && REG_P (node->loc) + && REGNO (dstnode->loc) == REGNO (node->loc)) + || rtx_equal_p (dstnode->loc, node->loc))) + { + location_chain new_node; - /* Value larger than a sum of 2 valid positions. */ - vui[jj].pos_src = src_l + dst_l; + /* Copy the location from SRC. */ + new_node = (location_chain) pool_alloc (loc_chain_pool); + new_node->loc = node->loc; + new_node->init = node->init; + if (!node->set_src || MEM_P (node->set_src)) + new_node->set_src = NULL; + else + new_node->set_src = node->set_src; + node2->next = new_node; + node2 = new_node; + } + node2->next = NULL; } - - /* Fill in the locations from SRC. */ - n = dst_l; - for (node = src->var_part[i].loc_chain, ii = 0; node; - node = node->next, ii++) + else { - /* Find location from NODE. */ - for (jj = 0; jj < dst_l; jj++) + if (src_l + dst_l <= (int) ARRAY_SIZE (vui_buf)) + vui = vui_buf; + else { - if ((REG_P (vui[jj].lc->loc) - && REG_P (node->loc) - && REGNO (vui[jj].lc->loc) == REGNO (node->loc)) - || rtx_equal_p (vui[jj].lc->loc, node->loc)) + if (src_l + dst_l > vui_allocated) { - vui[jj].pos_src = ii; - break; + vui_allocated = MAX (vui_allocated * 2, src_l + dst_l); + vui_vec = XRESIZEVEC (struct variable_union_info, vui_vec, + vui_allocated); } + vui = vui_vec; } - if (jj >= dst_l) /* The location has not been found. */ + + /* Fill in the locations from DST. */ + for (node = dst->var_part[j].loc_chain, jj = 0; node; + node = node->next, jj++) { - location_chain new_node; + vui[jj].lc = node; + vui[jj].pos_dst = jj; - /* Copy the location from SRC. */ - new_node = (location_chain) pool_alloc (loc_chain_pool); - new_node->loc = node->loc; - new_node->init = node->init; - if (!node->set_src || MEM_P (node->set_src)) - new_node->set_src = NULL; - else - new_node->set_src = node->set_src; - vui[n].lc = new_node; - vui[n].pos_src = ii; - vui[n].pos_dst = src_l + dst_l; - n++; + /* Pos plus value larger than a sum of 2 valid positions. */ + vui[jj].pos = jj + src_l + dst_l; } - } - for (ii = 0; ii < src_l + dst_l; ii++) - vui[ii].pos = vui[ii].pos_src + vui[ii].pos_dst; + /* Fill in the locations from SRC. */ + n = dst_l; + for (node = src->var_part[i].loc_chain, ii = 0; node; + node = node->next, ii++) + { + /* Find location from NODE. */ + for (jj = 0; jj < dst_l; jj++) + { + if ((REG_P (vui[jj].lc->loc) + && REG_P (node->loc) + && REGNO (vui[jj].lc->loc) == REGNO (node->loc)) + || rtx_equal_p (vui[jj].lc->loc, node->loc)) + { + vui[jj].pos = jj + ii; + break; + } + } + if (jj >= dst_l) /* The location has not been found. */ + { + location_chain new_node; - qsort (vui, n, sizeof (struct variable_union_info), - variable_union_info_cmp_pos); + /* Copy the location from SRC. */ + new_node = (location_chain) pool_alloc (loc_chain_pool); + new_node->loc = node->loc; + new_node->init = node->init; + if (!node->set_src || MEM_P (node->set_src)) + new_node->set_src = NULL; + else + new_node->set_src = node->set_src; + vui[n].lc = new_node; + vui[n].pos_dst = src_l + dst_l; + vui[n].pos = ii + src_l + dst_l; + n++; + } + } - /* Reconnect the nodes in sorted order. */ - for (ii = 1; ii < n; ii++) - vui[ii - 1].lc->next = vui[ii].lc; - vui[n - 1].lc->next = NULL; + if (dst_l == 2) + { + /* Special case still very common case. For dst_l == 2 + all entries dst_l ... n-1 are sorted, with for i >= dst_l + vui[i].pos == i + src_l + dst_l. */ + if (vui[0].pos > vui[1].pos) + { + /* Order should be 1, 0, 2... */ + dst->var_part[k].loc_chain = vui[1].lc; + vui[1].lc->next = vui[0].lc; + if (n >= 3) + { + vui[0].lc->next = vui[2].lc; + vui[n - 1].lc->next = NULL; + } + else + vui[0].lc->next = NULL; + ii = 3; + } + else + { + dst->var_part[k].loc_chain = vui[0].lc; + if (n >= 3 && vui[2].pos < vui[1].pos) + { + /* Order should be 0, 2, 1, 3... */ + vui[0].lc->next = vui[2].lc; + vui[2].lc->next = vui[1].lc; + if (n >= 4) + { + vui[1].lc->next = vui[3].lc; + vui[n - 1].lc->next = NULL; + } + else + vui[1].lc->next = NULL; + ii = 4; + } + else + { + /* Order should be 0, 1, 2... */ + ii = 1; + vui[n - 1].lc->next = NULL; + } + } + for (; ii < n; ii++) + vui[ii - 1].lc->next = vui[ii].lc; + } + else + { + qsort (vui, n, sizeof (struct variable_union_info), + variable_union_info_cmp_pos); - dst->var_part[k].loc_chain = vui[0].lc; - dst->var_part[k].offset = dst->var_part[j].offset; + /* Reconnect the nodes in sorted order. */ + for (ii = 1; ii < n; ii++) + vui[ii - 1].lc->next = vui[ii].lc; + vui[n - 1].lc->next = NULL; + dst->var_part[k].loc_chain = vui[0].lc; + } - free (vui); + dst->var_part[k].offset = dst->var_part[j].offset; + } i--; j--; } @@ -1477,17 +1559,18 @@ variable_union (void **slot, void *data) dst->var_part[k].cur_loc = NULL; } - for (i = 0; i < src->n_var_parts && i < dst->n_var_parts; i++) - { - location_chain node, node2; - for (node = src->var_part[i].loc_chain; node; node = node->next) - for (node2 = dst->var_part[i].loc_chain; node2; node2 = node2->next) - if (rtx_equal_p (node->loc, node2->loc)) - { - if (node->init > node2->init) - node2->init = node->init; - } - } + if (flag_var_tracking_uninit) + for (i = 0; i < src->n_var_parts && i < dst->n_var_parts; i++) + { + location_chain node, node2; + for (node = src->var_part[i].loc_chain; node; node = node->next) + for (node2 = dst->var_part[i].loc_chain; node2; node2 = node2->next) + if (rtx_equal_p (node->loc, node2->loc)) + { + if (node->init > node2->init) + node2->init = node->init; + } + } /* Continue traversing the hash table. */ return 1; @@ -1522,14 +1605,7 @@ variable_canonicalize (void **slot, void } } if (k < src->n_var_parts) - { - enum var_init_status status = VAR_INIT_STATUS_UNKNOWN; - - if (! flag_var_tracking_uninit) - status = VAR_INIT_STATUS_INITIALIZED; - - unshare_variable (set, src, status); - } + unshare_variable (set, src, VAR_INIT_STATUS_UNKNOWN); return 1; } @@ -1650,34 +1726,6 @@ dataflow_set_different_1 (void **slot, v return 1; } -/* Compare variable *SLOT with the same variable in hash table DATA - and set DATAFLOW_SET_DIFFERENT_VALUE if they are different. */ - -static int -dataflow_set_different_2 (void **slot, void *data) -{ - htab_t htab = (htab_t) data; - variable var1, var2; - - var1 = *(variable *) slot; - var2 = (variable) htab_find_with_hash (htab, var1->decl, - VARIABLE_HASH_VAL (var1->decl)); - if (!var2) - { - dataflow_set_different_value = true; - - /* Stop traversing the hash table. */ - return 0; - } - - /* If both variables are defined they have been already checked for - equivalence. */ - gcc_assert (!variable_different_p (var1, var2, false)); - - /* Continue traversing the hash table. */ - return 1; -} - /* Return true if dataflow sets OLD_SET and NEW_SET differ. */ static bool @@ -1694,14 +1742,9 @@ dataflow_set_different (dataflow_set *ol htab_traverse (shared_hash_htab (old_set->vars), dataflow_set_different_1, shared_hash_htab (new_set->vars)); - if (!dataflow_set_different_value) - { - /* We have compared the variables which are in both hash tables - so now only check whether there are some variables in NEW_SET->VARS - which are not in OLD_SET->VARS. */ - htab_traverse (shared_hash_htab (new_set->vars), dataflow_set_different_2, - shared_hash_htab (old_set->vars)); - } + /* No need to traverse the second hashtab, if both have the same number + of elements and the second one had all entries found in the first one, + then it can't have any extra entries. */ return dataflow_set_different_value; } @@ -2215,15 +2258,11 @@ compute_bb_dataflow (basic_block bb) case MO_USE: { rtx loc = VTI (bb)->mos[i].u.loc; - enum var_init_status status = VAR_INIT_STATUS_UNINITIALIZED; - - if (! flag_var_tracking_uninit) - status = VAR_INIT_STATUS_INITIALIZED; if (REG_P (loc)) - var_reg_set (out, loc, status, NULL); + var_reg_set (out, loc, VAR_INIT_STATUS_UNINITIALIZED, NULL); else if (MEM_P (loc)) - var_mem_set (out, loc, status, NULL); + var_mem_set (out, loc, VAR_INIT_STATUS_UNINITIALIZED, NULL); } break; @@ -2262,10 +2301,12 @@ compute_bb_dataflow (basic_block bb) if (! flag_var_tracking_uninit) src_status = VAR_INIT_STATUS_INITIALIZED; else - src_status = find_src_status (in, set_src); + { + src_status = find_src_status (in, set_src); - if (src_status == VAR_INIT_STATUS_UNKNOWN) - src_status = find_src_status (out, set_src); + if (src_status == VAR_INIT_STATUS_UNKNOWN) + src_status = find_src_status (out, set_src); + } set_src = find_src_set_src (in, set_src); @@ -2609,6 +2650,9 @@ set_variable_part (dataflow_set *set, rt variable var; void **slot = shared_hash_find_slot (set->vars, decl); + if (! flag_var_tracking_uninit) + initialized = VAR_INIT_STATUS_INITIALIZED; + if (!slot || !*slot) { if (!slot) @@ -2815,10 +2859,8 @@ delete_variable_part (dataflow_set *set, && REGNO (node->loc) == REGNO (loc)) || rtx_equal_p (node->loc, loc)) { - enum var_init_status status = VAR_INIT_STATUS_UNKNOWN; - if (! flag_var_tracking_uninit) - status = VAR_INIT_STATUS_INITIALIZED; - var = unshare_variable (set, var, status); + var = unshare_variable (set, var, + VAR_INIT_STATUS_UNKNOWN); break; } } @@ -2893,9 +2935,6 @@ emit_note_insn_var_location (void **varp gcc_assert (var->decl); - if (! flag_var_tracking_uninit) - initialized = VAR_INIT_STATUS_INITIALIZED; - complete = true; last_limit = 0; n_var_parts = 0; @@ -3147,14 +3186,11 @@ emit_notes_in_bb (basic_block bb) case MO_USE: { rtx loc = VTI (bb)->mos[i].u.loc; - - enum var_init_status status = VAR_INIT_STATUS_UNINITIALIZED; - if (! flag_var_tracking_uninit) - status = VAR_INIT_STATUS_INITIALIZED; + if (REG_P (loc)) - var_reg_set (&set, loc, status, NULL); + var_reg_set (&set, loc, VAR_INIT_STATUS_UNINITIALIZED, NULL); else - var_mem_set (&set, loc, status, NULL); + var_mem_set (&set, loc, VAR_INIT_STATUS_UNINITIALIZED, NULL); emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN); } @@ -3552,6 +3588,10 @@ vt_finalize (void) free_alloc_pool (var_pool); free_alloc_pool (loc_chain_pool); free_alloc_pool (shared_hash_pool); + if (vui_vec) + free (vui_vec); + vui_vec = NULL; + vui_allocated = 0; } /* The entry point to variable tracking pass. */ --- gcc/rtl.c.jj 2009-06-22 12:45:36.000000000 +0200 +++ gcc/rtl.c 2009-06-22 12:56:38.000000000 +0200 @@ -458,7 +458,109 @@ rtx_equal_p_cb (const_rtx x, const_rtx y int rtx_equal_p (const_rtx x, const_rtx y) { - return rtx_equal_p_cb (x, y, NULL); + int i; + int j; + enum rtx_code code; + const char *fmt; + + if (x == y) + return 1; + if (x == 0 || y == 0) + return 0; + + code = GET_CODE (x); + /* Rtx's of different codes cannot be equal. */ + if (code != GET_CODE (y)) + return 0; + + /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. + (REG:SI x) and (REG:HI x) are NOT equivalent. */ + + if (GET_MODE (x) != GET_MODE (y)) + return 0; + + /* Some RTL can be compared nonrecursively. */ + switch (code) + { + case REG: + return (REGNO (x) == REGNO (y)); + + case LABEL_REF: + return XEXP (x, 0) == XEXP (y, 0); + + case SYMBOL_REF: + return XSTR (x, 0) == XSTR (y, 0); + + case SCRATCH: + case CONST_DOUBLE: + case CONST_INT: + case CONST_FIXED: + return 0; + + default: + break; + } + + /* Compare the elements. If any pair of corresponding elements + fail to match, return 0 for the whole thing. */ + + fmt = GET_RTX_FORMAT (code); + for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) + { + switch (fmt[i]) + { + case 'w': + if (XWINT (x, i) != XWINT (y, i)) + return 0; + break; + + case 'n': + case 'i': + if (XINT (x, i) != XINT (y, i)) + return 0; + break; + + case 'V': + case 'E': + /* Two vectors must have the same length. */ + if (XVECLEN (x, i) != XVECLEN (y, i)) + return 0; + + /* And the corresponding elements must match. */ + for (j = 0; j < XVECLEN (x, i); j++) + if (rtx_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j)) == 0) + return 0; + break; + + case 'e': + if (rtx_equal_p (XEXP (x, i), XEXP (y, i)) == 0) + return 0; + break; + + case 'S': + case 's': + if ((XSTR (x, i) || XSTR (y, i)) + && (! XSTR (x, i) || ! XSTR (y, i) + || strcmp (XSTR (x, i), XSTR (y, i)))) + return 0; + break; + + case 'u': + /* These are just backpointers, so they don't matter. */ + break; + + case '0': + case 't': + break; + + /* It is believed that rtx's at this level will never + contain anything but integers and other rtx's, + except for within LABEL_REFs and SYMBOL_REFs. */ + default: + gcc_unreachable (); + } + } + return 1; } void