This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: Minimize downward code motion during reassociation
On Fri, Oct 19, 2012 at 5:13 PM, Xinliang David Li <davidxl@google.com> wrote:
> On Thu, Oct 18, 2012 at 3:36 PM, Easwaran Raman <eraman@google.com> wrote:
>> Hi,
>>
>> During expression reassociation, statements are conservatively moved
>> downwards to ensure that dependences are correctly satisfied after
>> reassocation. This could lead to lengthening of live ranges. This
>> patch moves statements only to the extent necessary. Bootstraps and no
>> test regression on x86_64/linux. OK for trunk?
>>
>> Thanks,
>> Easwaran
>>
>> 2012-10-18 Easwaran Raman <eraman@google.com>
>> * tree-ssa-reassoc.c(assign_uids): New function.
>> (assign_uids_in_relevant_bbs): Likewise.
>> (ensure_ops_are_available): Likewise.
>> (rewrite_expr_tree): Do not move statements beyond what is
>> necessary. Remove call to swap_ops_for_binary_stmt...
>> (reassociate_bb): ... and move it here.
>>
>>
>>
>> Index: gcc/tree-ssa-reassoc.c
>> ===================================================================
>> --- gcc/tree-ssa-reassoc.c (revision 192487)
>> +++ gcc/tree-ssa-reassoc.c (working copy)
>> @@ -2250,6 +2250,128 @@ swap_ops_for_binary_stmt (VEC(operand_entry_t, hea
>> }
>> }
>>
>> +/* Assign UIDs to statements in basic block BB. */
>> +
>> +static void
>> +assign_uids (basic_block bb)
>> +{
>> + unsigned uid = 0;
>> + gimple_stmt_iterator gsi;
>> + /* First assign uids to phis. */
>> + for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
>> + {
>> + gimple stmt = gsi_stmt (gsi);
>> + gimple_set_uid (stmt, uid++);
>> + }
>> +
>> + /* Then assign uids to stmts. */
>> + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
>> + {
>> + gimple stmt = gsi_stmt (gsi);
>> + gimple_set_uid (stmt, uid++);
>> + }
>> +}
>> +
>> +/* For each operand in OPS, find the basic block that contains the statement
>> + which defines the operand. For all such basic blocks, assign UIDs. */
>> +
>> +static void
>> +assign_uids_in_relevant_bbs (VEC(operand_entry_t, heap) * ops)
>> +{
>> + operand_entry_t oe;
>> + int i;
>> + struct pointer_set_t *seen_bbs = pointer_set_create ();
>> +
>> + for (i = 0; VEC_iterate (operand_entry_t, ops, i, oe); i++)
>> + {
>> + gimple def_stmt;
>> + basic_block bb;
>> + if (TREE_CODE (oe->op) != SSA_NAME)
>> + continue;
>> + def_stmt = SSA_NAME_DEF_STMT (oe->op);
>> + bb = gimple_bb (def_stmt);
>> + if (!pointer_set_contains (seen_bbs, bb))
>> + {
>> + assign_uids (bb);
>> + pointer_set_insert (seen_bbs, bb);
>> + }
>> + }
>> + pointer_set_destroy (seen_bbs);
>> +}
>> +
>> +/* Ensure that operands in the OPS vector starting from OPINDEXth
>> entry are live
>> + at STMT. This is accomplished by moving STMT if needed. */
>> +
>> +static void
>> +ensure_ops_are_available (gimple stmt, VEC(operand_entry_t, heap) *
>> ops, int opindex)
>
> format issue?
>
>> +{
>> + int i;
>> + int len = VEC_length (operand_entry_t, ops);
>> + gimple insert_stmt = stmt;
>> + basic_block insert_bb = gimple_bb (stmt);
>> + gimple_stmt_iterator gsi_insert, gsistmt;
>> + for (i = opindex; i < len; i++)
>> + {
>> + operand_entry_t oe = VEC_index (operand_entry_t, ops, i);
>> + gimple def_stmt;
>> + basic_block def_bb;
>> + /* Ignore constants and operands with default definitons. */
>> + if (TREE_CODE (oe->op) != SSA_NAME
>> + || SSA_NAME_IS_DEFAULT_DEF (oe->op))
>> + continue;
>> + def_stmt = SSA_NAME_DEF_STMT (oe->op);
>> + def_bb = gimple_bb (def_stmt);
>> + if (def_bb != insert_bb
>> + && !dominated_by_p (CDI_DOMINATORS, insert_bb, def_bb))
>> + {
>> + insert_bb = def_bb;
>> + insert_stmt = def_stmt;
>> + }
>> + else if (def_bb == insert_bb
>> + && gimple_uid (insert_stmt) < gimple_uid (def_stmt))
>> + insert_stmt = def_stmt;
>> + }
>> + if (insert_stmt == stmt)
>> + return;
>> + gsistmt = gsi_for_stmt (stmt);
>> + /* If GSI_STMT is a phi node, then do not insert just after that statement.
>
> GSI_STMT --> INSERT_STMT?
Ok.
>> + Instead, find the first non-label gimple statement in BB and insert before
>> + that. */
>> + if (gimple_code (insert_stmt) == GIMPLE_PHI)
>> + {
>> + gsi_insert = gsi_after_labels (insert_bb);
>> + gsi_move_before (&gsistmt, &gsi_insert);
>> + }
>> + /* Statements marked for throw can not be in the middle of a basic block. So
>> + we can not insert a statement (not marked for throw) immediately
>> after. */
>> + else if (lookup_stmt_eh_lp (insert_stmt) > 0
>> + && stmt_can_throw_internal (insert_stmt))
>
>
>
>
>> + {
>> + edge e, succ_edge = NULL;
>> + edge_iterator ei;
>> +
>> + /* There should be exactly one normal edge out of the basic block. */
>> + FOR_EACH_EDGE (e, ei, insert_bb->succs)
>> + {
>> + if (!(e->flags & EDGE_COMPLEX))
>> + {
>> + gcc_assert (succ_edge == NULL);
>> + succ_edge = e;
>> + }
>> + }
>> + /* Insert STMT at the beginning of the successor basic block. */
>> + insert_bb = succ_edge->dest;
>> + gsi_insert = gsi_after_labels (insert_bb);
>> + gsi_move_before (&gsistmt, &gsi_insert);
>> + }
>> + else
>> + {
>> + gsi_insert = gsi_for_stmt (insert_stmt);
>> + gsi_move_after (&gsistmt, &gsi_insert);
>> + }
>> +
>> +}
>> +
>> /* Recursively rewrite our linearized statements so that the operators
>> match those in OPS[OPINDEX], putting the computation in rank
>> order. */
>> @@ -2262,11 +2384,6 @@ rewrite_expr_tree (gimple stmt, unsigned int opind
>> tree rhs2 = gimple_assign_rhs2 (stmt);
>> operand_entry_t oe;
>>
>> - /* If we have three operands left, then we want to make sure the ones
>> - that get the double binary op are chosen wisely. */
>> - if (opindex + 3 == VEC_length (operand_entry_t, ops))
>> - swap_ops_for_binary_stmt (ops, opindex, stmt);
>> -
>
> Why moving the swap down ?
Otherwise, when I call ensure_ops_are_available on the leaf statement
(last statement in the chain), I might end up using the wrong
operands. ensure_ops_are_available makes sure that the last stmt comes
after ops[len-2] and ops[len-1]. If I call swap_ops_for_binary_stmt
after this, we might have the wrong deps.
>
>> /* The final recursion case for this function is that you have
>> exactly two operations left.
>> If we had one exactly one op in the entire list to start with, we
>> @@ -2312,19 +2429,17 @@ rewrite_expr_tree (gimple stmt, unsigned int opind
>> {
>> if (!moved)
>> {
>> - gimple_stmt_iterator gsinow, gsirhs1;
>> - gimple stmt1 = stmt, stmt2;
>> - unsigned int count;
>> + gimple stmt1 = stmt;
>> + unsigned int count, i = 1;
>>
>> - gsinow = gsi_for_stmt (stmt);
>> count = VEC_length (operand_entry_t, ops) - opindex - 2;
>> - while (count-- != 0)
>> + while (i <= count)
>> {
>> - stmt2 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt1));
>> - gsirhs1 = gsi_for_stmt (stmt2);
>> - gsi_move_before (&gsirhs1, &gsinow);
>> - gsi_prev (&gsinow);
>> - stmt1 = stmt2;
>> + stmt1 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt1));
>> + /* Ensure that STMT1 is moved to a place where all operands in
>> + OPS[opindex + i...] are available. */
>> + ensure_ops_are_available (stmt1, ops, opindex + i);
>> + i++;
>> }
>> moved = true;
>> }
>> @@ -3542,8 +3657,18 @@ reassociate_bb (basic_block bb)
>> && VEC_length (operand_entry_t, ops) > 3)
>> rewrite_expr_tree_parallel (stmt, width, ops);
>> else
>> - rewrite_expr_tree (stmt, 0, ops, false);
>> + {
>> + /* When there are three operands left, we want
>> + to make sure the ones that get the double
>> + binary op are chosen wisely. */
>> + int len = VEC_length (operand_entry_t, ops);
>> + if (len >= 3)
>> + swap_ops_for_binary_stmt (ops, len - 3, stmt);
>>
>> + assign_uids_in_relevant_bbs (ops);
>> + rewrite_expr_tree (stmt, 0, ops, false);
>> + }
>
> Fix indentation.
>
Ok.
- Easwaran
> David
>> +
>> /* If we combined some repeated factors into a
>> __builtin_powi call, multiply that result by the
>> reassociated operands. */