This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] Speed up PRE insertion
- From: Richard Guenther <rguenther at suse dot de>
- To: gcc-patches at gcc dot gnu dot org
- Date: Tue, 14 Aug 2012 12:01:19 +0200 (CEST)
- Subject: [PATCH] Speed up PRE insertion
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 <rguenther@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;
}