This removes the overhead of clearing a vector of n_basic_blocks elements per anti expression during insertion by making it a vector indexed by pred edge index and allocating it once for each basic block instead. This can make a significant difference for large functions.
Bootstrap and regtest pending on x86_64-unknown-linux-gnu. Richard. 2012-08-14 Richard Guenther <rguent...@suse.de> * tree-ssa-pre.c (do_regular_insertion): Use a VEC indexed by pred edge index for avail. (do_partial_partial_insertion): Likewise. (insert_into_preds_of_block): Adjust. Index: gcc/tree-ssa-pre.c =================================================================== *** gcc/tree-ssa-pre.c (revision 190376) --- gcc/tree-ssa-pre.c (working copy) *************** inhibit_phi_insertion (basic_block bb, p *** 3188,3194 **** static bool insert_into_preds_of_block (basic_block block, unsigned int exprnum, ! pre_expr *avail) { pre_expr expr = expression_for_id (exprnum); pre_expr newphi; --- 3188,3194 ---- static bool insert_into_preds_of_block (basic_block block, unsigned int exprnum, ! VEC(pre_expr, heap) *avail) { pre_expr expr = expression_for_id (exprnum); pre_expr newphi; *************** insert_into_preds_of_block (basic_block *** 3229,3235 **** gimple_seq stmts = NULL; tree builtexpr; bprime = pred->src; ! eprime = avail[bprime->index]; if (eprime->kind != NAME && eprime->kind != CONSTANT) { --- 3229,3235 ---- gimple_seq stmts = NULL; tree builtexpr; bprime = pred->src; ! eprime = VEC_index (pre_expr, avail, pred->dest_idx); if (eprime->kind != NAME && eprime->kind != CONSTANT) { *************** insert_into_preds_of_block (basic_block *** 3239,3252 **** type); gcc_assert (!(pred->flags & EDGE_ABNORMAL)); gsi_insert_seq_on_edge (pred, stmts); ! avail[bprime->index] = get_or_alloc_expr_for_name (builtexpr); insertions = true; } else if (eprime->kind == CONSTANT) { /* Constants may not have the right type, fold_convert ! should give us back a constant with the right type. ! */ tree constant = PRE_EXPR_CONSTANT (eprime); if (!useless_type_conversion_p (type, TREE_TYPE (constant))) { --- 3239,3252 ---- type); gcc_assert (!(pred->flags & EDGE_ABNORMAL)); gsi_insert_seq_on_edge (pred, stmts); ! VEC_replace (pre_expr, avail, pred->dest_idx, ! get_or_alloc_expr_for_name (builtexpr)); insertions = true; } else if (eprime->kind == CONSTANT) { /* Constants may not have the right type, fold_convert ! should give us back a constant with the right type. */ tree constant = PRE_EXPR_CONSTANT (eprime); if (!useless_type_conversion_p (type, TREE_TYPE (constant))) { *************** insert_into_preds_of_block (basic_block *** 3278,3288 **** } gsi_insert_seq_on_edge (pred, stmts); } ! avail[bprime->index] = get_or_alloc_expr_for_name (forcedexpr); } } else ! avail[bprime->index] = get_or_alloc_expr_for_constant (builtexpr); } } else if (eprime->kind == NAME) --- 3278,3290 ---- } gsi_insert_seq_on_edge (pred, stmts); } ! VEC_replace (pre_expr, avail, pred->dest_idx, ! get_or_alloc_expr_for_name (forcedexpr)); } } else ! VEC_replace (pre_expr, avail, pred->dest_idx, ! get_or_alloc_expr_for_constant (builtexpr)); } } else if (eprime->kind == NAME) *************** insert_into_preds_of_block (basic_block *** 3321,3327 **** } gsi_insert_seq_on_edge (pred, stmts); } ! avail[bprime->index] = get_or_alloc_expr_for_name (forcedexpr); } } } --- 3323,3330 ---- } gsi_insert_seq_on_edge (pred, stmts); } ! VEC_replace (pre_expr, avail, pred->dest_idx, ! get_or_alloc_expr_for_name (forcedexpr)); } } } *************** insert_into_preds_of_block (basic_block *** 3344,3357 **** bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (gimple_phi_result (phi))); FOR_EACH_EDGE (pred, ei, block->preds) { ! pre_expr ae = avail[pred->src->index]; gcc_assert (get_expr_type (ae) == type || useless_type_conversion_p (type, get_expr_type (ae))); if (ae->kind == CONSTANT) add_phi_arg (phi, PRE_EXPR_CONSTANT (ae), pred, UNKNOWN_LOCATION); else ! add_phi_arg (phi, PRE_EXPR_NAME (avail[pred->src->index]), pred, ! UNKNOWN_LOCATION); } newphi = get_or_alloc_expr_for_name (gimple_phi_result (phi)); --- 3347,3359 ---- bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (gimple_phi_result (phi))); FOR_EACH_EDGE (pred, ei, block->preds) { ! pre_expr ae = VEC_index (pre_expr, avail, pred->dest_idx); gcc_assert (get_expr_type (ae) == type || useless_type_conversion_p (type, get_expr_type (ae))); if (ae->kind == CONSTANT) add_phi_arg (phi, PRE_EXPR_CONSTANT (ae), pred, UNKNOWN_LOCATION); else ! add_phi_arg (phi, PRE_EXPR_NAME (ae), pred, UNKNOWN_LOCATION); } newphi = get_or_alloc_expr_for_name (gimple_phi_result (phi)); *************** static bool *** 3411,3425 **** do_regular_insertion (basic_block block, basic_block dom) { bool new_stuff = false; ! VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (ANTIC_IN (block)); pre_expr expr; int i; FOR_EACH_VEC_ELT (pre_expr, exprs, i, expr) { if (expr->kind != NAME) { - pre_expr *avail; unsigned int val; bool by_some = false; bool cant_insert = false; --- 3413,3430 ---- do_regular_insertion (basic_block block, basic_block dom) { bool new_stuff = false; ! VEC (pre_expr, heap) *exprs; pre_expr expr; + VEC (pre_expr, heap) *avail = NULL; int i; + exprs = sorted_array_from_bitmap_set (ANTIC_IN (block)); + VEC_safe_grow (pre_expr, heap, avail, EDGE_COUNT (block->preds)); + FOR_EACH_VEC_ELT (pre_expr, exprs, i, expr) { if (expr->kind != NAME) { unsigned int val; bool by_some = false; bool cant_insert = false; *************** do_regular_insertion (basic_block block, *** 3442,3451 **** continue; } - /* FIXME: This costs N_EXPR*N_BASIC_BLOCKS. Should use - a less costly data structure for avail (e.g. a VEC - indexed by edge index). */ - avail = XCNEWVEC (pre_expr, last_basic_block); FOR_EACH_EDGE (pred, ei, block->preds) { unsigned int vprime; --- 3447,3452 ---- *************** do_regular_insertion (basic_block block, *** 3468,3473 **** --- 3469,3475 ---- rest of the results are. */ if (eprime == NULL) { + VEC_replace (pre_expr, avail, pred->dest_idx, NULL); cant_insert = true; break; } *************** do_regular_insertion (basic_block block, *** 3478,3489 **** vprime, NULL); if (edoubleprime == NULL) { ! avail[bprime->index] = eprime; all_same = false; } else { ! avail[bprime->index] = edoubleprime; by_some = true; /* We want to perform insertions to remove a redundancy on a path in the CFG we want to optimize for speed. */ --- 3480,3491 ---- vprime, NULL); if (edoubleprime == NULL) { ! VEC_replace (pre_expr, avail, pred->dest_idx, eprime); all_same = false; } else { ! VEC_replace (pre_expr, avail, pred->dest_idx, edoubleprime); by_some = true; /* We want to perform insertions to remove a redundancy on a path in the CFG we want to optimize for speed. */ *************** do_regular_insertion (basic_block block, *** 3562,3572 **** } } } - free (avail); } } VEC_free (pre_expr, heap, exprs); return new_stuff; } --- 3564,3574 ---- } } } } } VEC_free (pre_expr, heap, exprs); + VEC_free (pre_expr, heap, avail); return new_stuff; } *************** static bool *** 3582,3596 **** do_partial_partial_insertion (basic_block block, basic_block dom) { bool new_stuff = false; ! VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (PA_IN (block)); pre_expr expr; int i; FOR_EACH_VEC_ELT (pre_expr, exprs, i, expr) { if (expr->kind != NAME) { - pre_expr *avail; unsigned int val; bool by_all = true; bool cant_insert = false; --- 3584,3601 ---- do_partial_partial_insertion (basic_block block, basic_block dom) { bool new_stuff = false; ! VEC (pre_expr, heap) *exprs; pre_expr expr; + VEC (pre_expr, heap) *avail = NULL; int i; + exprs = sorted_array_from_bitmap_set (PA_IN (block)); + VEC_safe_grow (pre_expr, heap, avail, EDGE_COUNT (block->preds)); + FOR_EACH_VEC_ELT (pre_expr, exprs, i, expr) { if (expr->kind != NAME) { unsigned int val; bool by_all = true; bool cant_insert = false; *************** do_partial_partial_insertion (basic_bloc *** 3605,3614 **** if (bitmap_set_contains_value (AVAIL_OUT (dom), val)) continue; - /* FIXME: This costs N_EXPR*N_BASIC_BLOCKS. Should use - a less costly data structure for avail (e.g. a VEC - indexed by edge index). */ - avail = XCNEWVEC (pre_expr, last_basic_block); FOR_EACH_EDGE (pred, ei, block->preds) { unsigned int vprime; --- 3610,3615 ---- *************** do_partial_partial_insertion (basic_bloc *** 3633,3638 **** --- 3634,3640 ---- rest of the results are. */ if (eprime == NULL) { + VEC_replace (pre_expr, avail, pred->dest_idx, NULL); cant_insert = true; break; } *************** do_partial_partial_insertion (basic_bloc *** 3641,3653 **** vprime = get_expr_value_id (eprime); edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime), vprime, NULL); if (edoubleprime == NULL) { by_all = false; break; } - else - avail[bprime->index] = edoubleprime; } /* If we can insert it, it's not the same value --- 3643,3654 ---- vprime = get_expr_value_id (eprime); edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime), vprime, NULL); + VEC_replace (pre_expr, avail, pred->dest_idx, edoubleprime); if (edoubleprime == NULL) { by_all = false; break; } } /* If we can insert it, it's not the same value *************** do_partial_partial_insertion (basic_bloc *** 3701,3711 **** new_stuff = true; } } - free (avail); } } VEC_free (pre_expr, heap, exprs); return new_stuff; } --- 3702,3712 ---- new_stuff = true; } } } } VEC_free (pre_expr, heap, exprs); + VEC_free (pre_expr, heap, avail); return new_stuff; }