diff options
author | Alexander Monakov <amonakov@ispras.ru> | 2016-11-09 16:58:17 +0300 |
---|---|---|
committer | Alexander Monakov <amonakov@ispras.ru> | 2016-11-09 16:58:17 +0300 |
commit | 333610c1ceadf0febb112e8f9a3f405d25a0345a (patch) | |
tree | 29ee0b1fc30f8a28e916e1c06f982933a73f4f2b /gcc/gimple-ssa-strength-reduction.c | |
parent | 16ca0e4e4bc093bfb2c08b167ce1f2116e37758b (diff) | |
parent | 421721dfaaddd54b376a5ac48e15ce6c7704bde3 (diff) | |
download | gcc-333610c1ceadf0febb112e8f9a3f405d25a0345a.tar.gz |
Merge remote-tracking branch 'origin/trunk' into gomp-nvptx-branch-merge-trunkamonakov/gomp-nvptx
Diffstat (limited to 'gcc/gimple-ssa-strength-reduction.c')
-rw-r--r-- | gcc/gimple-ssa-strength-reduction.c | 233 |
1 files changed, 170 insertions, 63 deletions
diff --git a/gcc/gimple-ssa-strength-reduction.c b/gcc/gimple-ssa-strength-reduction.c index 5dad1193c27..bdfdb9a82b1 100644 --- a/gcc/gimple-ssa-strength-reduction.c +++ b/gcc/gimple-ssa-strength-reduction.c @@ -246,6 +246,13 @@ struct slsr_cand_d replacement MEM_REF.) */ tree cand_type; + /* The type to be used to interpret the stride field when the stride + is not a constant. Normally the same as the type of the recorded + stride, but when the stride has been cast we need to maintain that + knowledge in order to make legal substitutions without losing + precision. When the stride is a constant, this will be sizetype. */ + tree stride_type; + /* The kind of candidate (CAND_MULT, etc.). */ enum cand_kind kind; @@ -502,6 +509,7 @@ find_basis_for_base_expr (slsr_cand_t c, tree base_expr) || one_basis->cand_stmt == c->cand_stmt || !operand_equal_p (one_basis->stride, c->stride, 0) || !types_compatible_p (one_basis->cand_type, c->cand_type) + || !types_compatible_p (one_basis->stride_type, c->stride_type) || !dominated_by_p (CDI_DOMINATORS, gimple_bb (c->cand_stmt), gimple_bb (one_basis->cand_stmt))) @@ -615,7 +623,7 @@ record_potential_basis (slsr_cand_t c, tree base) static slsr_cand_t alloc_cand_and_find_basis (enum cand_kind kind, gimple *gs, tree base, const widest_int &index, tree stride, tree ctype, - unsigned savings) + tree stype, unsigned savings) { slsr_cand_t c = (slsr_cand_t) obstack_alloc (&cand_obstack, sizeof (slsr_cand)); @@ -624,6 +632,7 @@ alloc_cand_and_find_basis (enum cand_kind kind, gimple *gs, tree base, c->stride = stride; c->index = index; c->cand_type = ctype; + c->stride_type = stype; c->kind = kind; c->cand_num = cand_vec.length () + 1; c->next_interp = 0; @@ -809,7 +818,8 @@ slsr_process_phi (gphi *phi, bool speed) base_type = TREE_TYPE (arg0_base); c = alloc_cand_and_find_basis (CAND_PHI, phi, arg0_base, - 0, integer_one_node, base_type, savings); + 0, integer_one_node, base_type, + sizetype, savings); /* Add the candidate to the statement-candidate mapping. */ add_cand_for_stmt (phi, c); @@ -838,7 +848,8 @@ backtrace_base_for_ref (tree *pbase) e.g. 'B' is widened from an 'int' in order to calculate a 64-bit address. */ if (CONVERT_EXPR_P (base_in) - && legal_cast_p_1 (base_in, TREE_OPERAND (base_in, 0))) + && legal_cast_p_1 (TREE_TYPE (base_in), + TREE_TYPE (TREE_OPERAND (base_in, 0)))) base_in = get_unwidened (base_in, NULL_TREE); if (TREE_CODE (base_in) != SSA_NAME) @@ -995,7 +1006,7 @@ slsr_process_ref (gimple *gs) return; c = alloc_cand_and_find_basis (CAND_REF, gs, base, index, offset, - type, 0); + type, sizetype, 0); /* Add the candidate to the statement-candidate mapping. */ add_cand_for_stmt (gs, c); @@ -1010,6 +1021,7 @@ static slsr_cand_t create_mul_ssa_cand (gimple *gs, tree base_in, tree stride_in, bool speed) { tree base = NULL_TREE, stride = NULL_TREE, ctype = NULL_TREE; + tree stype = NULL_TREE; widest_int index; unsigned savings = 0; slsr_cand_t c; @@ -1030,6 +1042,7 @@ create_mul_ssa_cand (gimple *gs, tree base_in, tree stride_in, bool speed) index = base_cand->index; stride = stride_in; ctype = base_cand->cand_type; + stype = TREE_TYPE (stride_in); if (has_single_use (base_in)) savings = (base_cand->dead_savings + stmt_cost (base_cand->cand_stmt, speed)); @@ -1045,6 +1058,7 @@ create_mul_ssa_cand (gimple *gs, tree base_in, tree stride_in, bool speed) index = base_cand->index * wi::to_widest (base_cand->stride); stride = stride_in; ctype = base_cand->cand_type; + stype = TREE_TYPE (stride_in); if (has_single_use (base_in)) savings = (base_cand->dead_savings + stmt_cost (base_cand->cand_stmt, speed)); @@ -1064,10 +1078,11 @@ create_mul_ssa_cand (gimple *gs, tree base_in, tree stride_in, bool speed) index = 0; stride = stride_in; ctype = TREE_TYPE (base_in); + stype = TREE_TYPE (stride_in); } c = alloc_cand_and_find_basis (CAND_MULT, gs, base, index, stride, - ctype, savings); + ctype, stype, savings); return c; } @@ -1156,7 +1171,7 @@ create_mul_imm_cand (gimple *gs, tree base_in, tree stride_in, bool speed) } c = alloc_cand_and_find_basis (CAND_MULT, gs, base, index, stride, - ctype, savings); + ctype, sizetype, savings); return c; } @@ -1212,7 +1227,8 @@ static slsr_cand_t create_add_ssa_cand (gimple *gs, tree base_in, tree addend_in, bool subtract_p, bool speed) { - tree base = NULL_TREE, stride = NULL_TREE, ctype = NULL; + tree base = NULL_TREE, stride = NULL_TREE, ctype = NULL_TREE; + tree stype = NULL_TREE; widest_int index; unsigned savings = 0; slsr_cand_t c; @@ -1237,6 +1253,7 @@ create_add_ssa_cand (gimple *gs, tree base_in, tree addend_in, index = -index; stride = addend_cand->base_expr; ctype = TREE_TYPE (base_in); + stype = addend_cand->cand_type; if (has_single_use (addend_in)) savings = (addend_cand->dead_savings + stmt_cost (addend_cand->cand_stmt, speed)); @@ -1263,6 +1280,8 @@ create_add_ssa_cand (gimple *gs, tree base_in, tree addend_in, index = subtract_p ? -1 : 1; stride = addend_in; ctype = base_cand->cand_type; + stype = (TREE_CODE (addend_in) == INTEGER_CST ? sizetype + : TREE_TYPE (addend_in)); if (has_single_use (base_in)) savings = (base_cand->dead_savings + stmt_cost (base_cand->cand_stmt, speed)); @@ -1286,6 +1305,7 @@ create_add_ssa_cand (gimple *gs, tree base_in, tree addend_in, index = -index; stride = subtrahend_cand->base_expr; ctype = TREE_TYPE (base_in); + stype = subtrahend_cand->cand_type; if (has_single_use (addend_in)) savings = (subtrahend_cand->dead_savings + stmt_cost (subtrahend_cand->cand_stmt, speed)); @@ -1312,10 +1332,12 @@ create_add_ssa_cand (gimple *gs, tree base_in, tree addend_in, index = subtract_p ? -1 : 1; stride = addend_in; ctype = TREE_TYPE (base_in); + stype = (TREE_CODE (addend_in) == INTEGER_CST ? sizetype + : TREE_TYPE (addend_in)); } c = alloc_cand_and_find_basis (CAND_ADD, gs, base, index, stride, - ctype, savings); + ctype, stype, savings); return c; } @@ -1329,6 +1351,7 @@ create_add_imm_cand (gimple *gs, tree base_in, const widest_int &index_in, { enum cand_kind kind = CAND_ADD; tree base = NULL_TREE, stride = NULL_TREE, ctype = NULL_TREE; + tree stype = NULL_TREE; widest_int index, multiple; unsigned savings = 0; slsr_cand_t c; @@ -1356,6 +1379,7 @@ create_add_imm_cand (gimple *gs, tree base_in, const widest_int &index_in, index = base_cand->index + multiple; stride = base_cand->stride; ctype = base_cand->cand_type; + stype = base_cand->stride_type; if (has_single_use (base_in)) savings = (base_cand->dead_savings + stmt_cost (base_cand->cand_stmt, speed)); @@ -1376,10 +1400,11 @@ create_add_imm_cand (gimple *gs, tree base_in, const widest_int &index_in, index = index_in; stride = integer_one_node; ctype = TREE_TYPE (base_in); + stype = sizetype; } c = alloc_cand_and_find_basis (kind, gs, base, index, stride, - ctype, savings); + ctype, stype, savings); return c; } @@ -1456,14 +1481,11 @@ slsr_process_neg (gimple *gs, tree rhs1, bool speed) for more details. */ static bool -legal_cast_p_1 (tree lhs, tree rhs) +legal_cast_p_1 (tree lhs_type, tree rhs_type) { - tree lhs_type, rhs_type; unsigned lhs_size, rhs_size; bool lhs_wraps, rhs_wraps; - lhs_type = TREE_TYPE (lhs); - rhs_type = TREE_TYPE (rhs); lhs_size = TYPE_PRECISION (lhs_type); rhs_size = TYPE_PRECISION (rhs_type); lhs_wraps = ANY_INTEGRAL_TYPE_P (lhs_type) && TYPE_OVERFLOW_WRAPS (lhs_type); @@ -1521,7 +1543,7 @@ legal_cast_p (gimple *gs, tree rhs) || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (gs))) return false; - return legal_cast_p_1 (gimple_assign_lhs (gs), rhs); + return legal_cast_p_1 (TREE_TYPE (gimple_assign_lhs (gs)), TREE_TYPE (rhs)); } /* Given GS which is a cast to a scalar integer type, determine whether @@ -1556,7 +1578,8 @@ slsr_process_cast (gimple *gs, tree rhs1, bool speed) c = alloc_cand_and_find_basis (base_cand->kind, gs, base_cand->base_expr, base_cand->index, base_cand->stride, - ctype, savings); + ctype, base_cand->stride_type, + savings); if (base_cand->next_interp) base_cand = lookup_cand (base_cand->next_interp); else @@ -1574,10 +1597,10 @@ slsr_process_cast (gimple *gs, tree rhs1, bool speed) The first of these is somewhat arbitrary, but the choice of 1 for the stride simplifies the logic for propagating casts into their uses. */ - c = alloc_cand_and_find_basis (CAND_ADD, gs, rhs1, - 0, integer_one_node, ctype, 0); - c2 = alloc_cand_and_find_basis (CAND_MULT, gs, rhs1, - 0, integer_one_node, ctype, 0); + c = alloc_cand_and_find_basis (CAND_ADD, gs, rhs1, 0, + integer_one_node, ctype, sizetype, 0); + c2 = alloc_cand_and_find_basis (CAND_MULT, gs, rhs1, 0, + integer_one_node, ctype, sizetype, 0); c->next_interp = c2->cand_num; } @@ -1613,7 +1636,8 @@ slsr_process_copy (gimple *gs, tree rhs1, bool speed) c = alloc_cand_and_find_basis (base_cand->kind, gs, base_cand->base_expr, base_cand->index, base_cand->stride, - base_cand->cand_type, savings); + base_cand->cand_type, + base_cand->stride_type, savings); if (base_cand->next_interp) base_cand = lookup_cand (base_cand->next_interp); else @@ -1631,10 +1655,12 @@ slsr_process_copy (gimple *gs, tree rhs1, bool speed) The first of these is somewhat arbitrary, but the choice of 1 for the stride simplifies the logic for propagating casts into their uses. */ - c = alloc_cand_and_find_basis (CAND_ADD, gs, rhs1, - 0, integer_one_node, TREE_TYPE (rhs1), 0); - c2 = alloc_cand_and_find_basis (CAND_MULT, gs, rhs1, - 0, integer_one_node, TREE_TYPE (rhs1), 0); + c = alloc_cand_and_find_basis (CAND_ADD, gs, rhs1, 0, + integer_one_node, TREE_TYPE (rhs1), + sizetype, 0); + c2 = alloc_cand_and_find_basis (CAND_MULT, gs, rhs1, 0, + integer_one_node, TREE_TYPE (rhs1), + sizetype, 0); c->next_interp = c2->cand_num; } @@ -1755,6 +1781,13 @@ dump_candidate (slsr_cand_t c) fputs (" + ", dump_file); print_decs (c->index, dump_file); fputs (") * ", dump_file); + if (TREE_CODE (c->stride) != INTEGER_CST + && c->stride_type != TREE_TYPE (c->stride)) + { + fputs ("(", dump_file); + print_generic_expr (dump_file, c->stride_type, 0); + fputs (")", dump_file); + } print_generic_expr (dump_file, c->stride, 0); fputs (" : ", dump_file); break; @@ -1764,6 +1797,13 @@ dump_candidate (slsr_cand_t c) fputs (" + (", dump_file); print_decs (c->index, dump_file); fputs (" * ", dump_file); + if (TREE_CODE (c->stride) != INTEGER_CST + && c->stride_type != TREE_TYPE (c->stride)) + { + fputs ("(", dump_file); + print_generic_expr (dump_file, c->stride_type, 0); + fputs (")", dump_file); + } print_generic_expr (dump_file, c->stride, 0); fputs (") : ", dump_file); break; @@ -2143,7 +2183,7 @@ create_add_on_incoming_edge (slsr_cand_t c, tree basis_name, basic_block insert_bb; gimple_stmt_iterator gsi; tree lhs, basis_type; - gassign *new_stmt; + gassign *new_stmt, *cast_stmt = NULL; /* If the add candidate along this incoming edge has the same index as C's hidden basis, the hidden basis represents this @@ -2187,27 +2227,61 @@ create_add_on_incoming_edge (slsr_cand_t c, tree basis_name, new_stmt = gimple_build_assign (lhs, code, basis_name, incr_vec[i].initializer); } - else if (increment == 1) - new_stmt = gimple_build_assign (lhs, plus_code, basis_name, c->stride); - else if (increment == -1) - new_stmt = gimple_build_assign (lhs, MINUS_EXPR, basis_name, - c->stride); - else - gcc_unreachable (); + else { + tree stride; + + if (!types_compatible_p (TREE_TYPE (c->stride), c->stride_type)) + { + tree cast_stride = make_temp_ssa_name (c->stride_type, NULL, + "slsr"); + cast_stmt = gimple_build_assign (cast_stride, NOP_EXPR, + c->stride); + stride = cast_stride; + } + else + stride = c->stride; + + if (increment == 1) + new_stmt = gimple_build_assign (lhs, plus_code, basis_name, stride); + else if (increment == -1) + new_stmt = gimple_build_assign (lhs, MINUS_EXPR, basis_name, stride); + else + gcc_unreachable (); + } } insert_bb = single_succ_p (e->src) ? e->src : split_edge (e); gsi = gsi_last_bb (insert_bb); if (!gsi_end_p (gsi) && is_ctrl_stmt (gsi_stmt (gsi))) - gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT); + { + gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT); + if (cast_stmt) + { + gsi_insert_before (&gsi, cast_stmt, GSI_SAME_STMT); + gimple_set_location (cast_stmt, loc); + } + } else - gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT); + { + if (cast_stmt) + { + gsi_insert_after (&gsi, cast_stmt, GSI_NEW_STMT); + gimple_set_location (cast_stmt, loc); + } + gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT); + } gimple_set_location (new_stmt, loc); if (dump_file && (dump_flags & TDF_DETAILS)) { + if (cast_stmt) + { + fprintf (dump_file, "Inserting cast in block %d: ", + insert_bb->index); + print_gimple_stmt (dump_file, cast_stmt, 0, 0); + } fprintf (dump_file, "Inserting in block %d: ", insert_bb->index); print_gimple_stmt (dump_file, new_stmt, 0, 0); } @@ -2825,40 +2899,35 @@ analyze_increments (slsr_cand_t first_dep, machine_mode mode, bool speed) && !POINTER_TYPE_P (first_dep->cand_type))) incr_vec[i].cost = COST_NEUTRAL; - /* FORNOW: If we need to add an initializer, give up if a cast from - the candidate's type to its stride's type can lose precision. - This could eventually be handled better by expressly retaining the - result of a cast to a wider type in the stride. Example: + /* If we need to add an initializer, give up if a cast from the + candidate's type to its stride's type can lose precision. + Note that this already takes into account that the stride may + have been cast to a wider type, in which case this test won't + fire. Example: short int _1; _2 = (int) _1; _3 = _2 * 10; - _4 = x + _3; ADD: x + (10 * _1) : int + _4 = x + _3; ADD: x + (10 * (int)_1) : int _5 = _2 * 15; - _6 = x + _3; ADD: x + (15 * _1) : int - - Right now replacing _6 would cause insertion of an initializer - of the form "short int T = _1 * 5;" followed by a cast to - int, which could overflow incorrectly. Had we recorded _2 or - (int)_1 as the stride, this wouldn't happen. However, doing - this breaks other opportunities, so this will require some - care. */ + _6 = x + _5; ADD: x + (15 * (int)_1) : int + + Although the stride was a short int initially, the stride + used in the analysis has been widened to an int, and such + widening will be done in the initializer as well. */ else if (!incr_vec[i].initializer && TREE_CODE (first_dep->stride) != INTEGER_CST - && !legal_cast_p_1 (first_dep->stride, - gimple_assign_lhs (first_dep->cand_stmt))) - + && !legal_cast_p_1 (first_dep->stride_type, + TREE_TYPE (gimple_assign_lhs + (first_dep->cand_stmt)))) incr_vec[i].cost = COST_INFINITE; /* If we need to add an initializer, make sure we don't introduce a multiply by a pointer type, which can happen in certain cast - scenarios. FIXME: When cleaning up these cast issues, we can - afford to introduce the multiply provided we cast out to an - unsigned int of appropriate size. */ + scenarios. */ else if (!incr_vec[i].initializer && TREE_CODE (first_dep->stride) != INTEGER_CST - && POINTER_TYPE_P (TREE_TYPE (first_dep->stride))) - + && POINTER_TYPE_P (first_dep->stride_type)) incr_vec[i].cost = COST_INFINITE; /* For any other increment, if this is a multiply candidate, we @@ -3105,7 +3174,8 @@ insert_initializers (slsr_cand_t c) basic_block bb; slsr_cand_t where = NULL; gassign *init_stmt; - tree stride_type, new_name, incr_tree; + gassign *cast_stmt = NULL; + tree new_name, incr_tree, init_stride; widest_int incr = incr_vec[i].incr; if (!profitable_increment_p (i) @@ -3134,37 +3204,74 @@ insert_initializers (slsr_cand_t c) that block, the earliest one will be returned in WHERE. */ bb = nearest_common_dominator_for_cands (c, incr, &where); + /* If the nominal stride has a different type than the recorded + stride type, build a cast from the nominal stride to that type. */ + if (!types_compatible_p (TREE_TYPE (c->stride), c->stride_type)) + { + init_stride = make_temp_ssa_name (c->stride_type, NULL, "slsr"); + cast_stmt = gimple_build_assign (init_stride, NOP_EXPR, c->stride); + } + else + init_stride = c->stride; + /* Create a new SSA name to hold the initializer's value. */ - stride_type = TREE_TYPE (c->stride); - new_name = make_temp_ssa_name (stride_type, NULL, "slsr"); + new_name = make_temp_ssa_name (c->stride_type, NULL, "slsr"); incr_vec[i].initializer = new_name; /* Create the initializer and insert it in the latest possible dominating position. */ - incr_tree = wide_int_to_tree (stride_type, incr); + incr_tree = wide_int_to_tree (c->stride_type, incr); init_stmt = gimple_build_assign (new_name, MULT_EXPR, - c->stride, incr_tree); + init_stride, incr_tree); if (where) { gimple_stmt_iterator gsi = gsi_for_stmt (where->cand_stmt); + location_t loc = gimple_location (where->cand_stmt); + + if (cast_stmt) + { + gsi_insert_before (&gsi, cast_stmt, GSI_SAME_STMT); + gimple_set_location (cast_stmt, loc); + } + gsi_insert_before (&gsi, init_stmt, GSI_SAME_STMT); - gimple_set_location (init_stmt, gimple_location (where->cand_stmt)); + gimple_set_location (init_stmt, loc); } else { gimple_stmt_iterator gsi = gsi_last_bb (bb); gimple *basis_stmt = lookup_cand (c->basis)->cand_stmt; + location_t loc = gimple_location (basis_stmt); if (!gsi_end_p (gsi) && is_ctrl_stmt (gsi_stmt (gsi))) - gsi_insert_before (&gsi, init_stmt, GSI_SAME_STMT); + { + if (cast_stmt) + { + gsi_insert_before (&gsi, cast_stmt, GSI_SAME_STMT); + gimple_set_location (cast_stmt, loc); + } + gsi_insert_before (&gsi, init_stmt, GSI_SAME_STMT); + } else - gsi_insert_after (&gsi, init_stmt, GSI_SAME_STMT); + { + if (cast_stmt) + { + gsi_insert_after (&gsi, cast_stmt, GSI_NEW_STMT); + gimple_set_location (cast_stmt, loc); + } + gsi_insert_after (&gsi, init_stmt, GSI_SAME_STMT); + } gimple_set_location (init_stmt, gimple_location (basis_stmt)); } if (dump_file && (dump_flags & TDF_DETAILS)) { + if (cast_stmt) + { + fputs ("Inserting stride cast: ", dump_file); + print_gimple_stmt (dump_file, cast_stmt, 0, 0); + } fputs ("Inserting initializer: ", dump_file); print_gimple_stmt (dump_file, init_stmt, 0, 0); } |