diff options
Diffstat (limited to 'gcc/tree-ssa-phiopt.cc')
| -rw-r--r-- | gcc/tree-ssa-phiopt.cc | 671 |
1 files changed, 29 insertions, 642 deletions
diff --git a/gcc/tree-ssa-phiopt.cc b/gcc/tree-ssa-phiopt.cc index 031184d..88153d3 100644 --- a/gcc/tree-ssa-phiopt.cc +++ b/gcc/tree-ssa-phiopt.cc @@ -1007,7 +1007,34 @@ match_simplify_replacement (basic_block cond_bb, basic_block middle_bb, } if (!result) - return false; + { + /* If we don't get back a MIN/MAX_EXPR still make sure the expression + stays in a form to be recognized by ISA that map to IEEE x > y ? x : y + semantics (that's not IEEE max semantics). */ + if (!HONOR_NANS (type) && !HONOR_SIGNED_ZEROS (type)) + return false; + if (stmt_to_move || stmt_to_move_alt) + return false; + tree_code cmp = gimple_cond_code (stmt); + if (cmp != LT_EXPR && cmp != LE_EXPR + && cmp != GT_EXPR && cmp != GE_EXPR) + return false; + tree lhs = gimple_cond_lhs (stmt); + tree rhs = gimple_cond_rhs (stmt); + /* `lhs CMP rhs ? lhs : rhs` or `lhs CMP rhs ? rhs : lhs` + are only acceptable case here. */ + if ((!operand_equal_for_phi_arg_p (lhs, arg_false) + || !operand_equal_for_phi_arg_p (rhs, arg_true)) + && (!operand_equal_for_phi_arg_p (rhs, arg_false) + || !operand_equal_for_phi_arg_p (lhs, arg_true))) + return false; + seq = nullptr; + result = gimple_build (&seq, cmp, boolean_type_node, lhs, rhs); + result = gimple_build (&seq, COND_EXPR, type, result, + arg_true, arg_false); + statistics_counter_event (cfun, "Non-IEEE FP MIN/MAX PHI replacement", + 1); + } if (dump_file && (dump_flags & TDF_FOLDING)) fprintf (dump_file, "accepted the phiopt match-simplify.\n"); @@ -1767,622 +1794,6 @@ value_replacement (basic_block cond_bb, basic_block middle_bb, return 0; } -/* If VAR is an SSA_NAME that points to a BIT_NOT_EXPR then return the TREE for - the value being inverted. */ - -static tree -strip_bit_not (tree var) -{ - if (TREE_CODE (var) != SSA_NAME) - return NULL_TREE; - - gimple *assign = SSA_NAME_DEF_STMT (var); - if (gimple_code (assign) != GIMPLE_ASSIGN) - return NULL_TREE; - - if (gimple_assign_rhs_code (assign) != BIT_NOT_EXPR) - return NULL_TREE; - - return gimple_assign_rhs1 (assign); -} - -/* Invert a MIN to a MAX or a MAX to a MIN expression CODE. */ - -enum tree_code -invert_minmax_code (enum tree_code code) -{ - switch (code) { - case MIN_EXPR: - return MAX_EXPR; - case MAX_EXPR: - return MIN_EXPR; - default: - gcc_unreachable (); - } -} - -/* The function minmax_replacement does the main work of doing the minmax - replacement. Return true if the replacement is done. Otherwise return - false. - BB is the basic block where the replacement is going to be done on. ARG0 - is argument 0 from the PHI. Likewise for ARG1. - - If THREEWAY_P then expect the BB to be laid out in diamond shape with each - BB containing only a MIN or MAX expression. */ - -static bool -minmax_replacement (basic_block cond_bb, basic_block middle_bb, basic_block alt_middle_bb, - edge e0, edge e1, gphi *phi, tree arg0, tree arg1, bool threeway_p) -{ - tree result; - edge true_edge, false_edge; - enum tree_code minmax, ass_code; - tree smaller, larger, arg_true, arg_false; - gimple_stmt_iterator gsi, gsi_from; - - tree type = TREE_TYPE (gimple_phi_result (phi)); - - gcond *cond = as_a <gcond *> (*gsi_last_bb (cond_bb)); - enum tree_code cmp = gimple_cond_code (cond); - tree rhs = gimple_cond_rhs (cond); - - /* Turn EQ/NE of extreme values to order comparisons. */ - if ((cmp == NE_EXPR || cmp == EQ_EXPR) - && TREE_CODE (rhs) == INTEGER_CST - && INTEGRAL_TYPE_P (TREE_TYPE (rhs))) - { - if (wi::eq_p (wi::to_wide (rhs), wi::min_value (TREE_TYPE (rhs)))) - { - cmp = (cmp == EQ_EXPR) ? LT_EXPR : GE_EXPR; - rhs = wide_int_to_tree (TREE_TYPE (rhs), - wi::min_value (TREE_TYPE (rhs)) + 1); - } - else if (wi::eq_p (wi::to_wide (rhs), wi::max_value (TREE_TYPE (rhs)))) - { - cmp = (cmp == EQ_EXPR) ? GT_EXPR : LE_EXPR; - rhs = wide_int_to_tree (TREE_TYPE (rhs), - wi::max_value (TREE_TYPE (rhs)) - 1); - } - } - - /* This transformation is only valid for order comparisons. Record which - operand is smaller/larger if the result of the comparison is true. */ - tree alt_smaller = NULL_TREE; - tree alt_larger = NULL_TREE; - if (cmp == LT_EXPR || cmp == LE_EXPR) - { - smaller = gimple_cond_lhs (cond); - larger = rhs; - /* If we have smaller < CST it is equivalent to smaller <= CST-1. - Likewise smaller <= CST is equivalent to smaller < CST+1. */ - if (TREE_CODE (larger) == INTEGER_CST - && INTEGRAL_TYPE_P (TREE_TYPE (larger))) - { - if (cmp == LT_EXPR) - { - wi::overflow_type overflow; - wide_int alt = wi::sub (wi::to_wide (larger), 1, - TYPE_SIGN (TREE_TYPE (larger)), - &overflow); - if (! overflow) - alt_larger = wide_int_to_tree (TREE_TYPE (larger), alt); - } - else - { - wi::overflow_type overflow; - wide_int alt = wi::add (wi::to_wide (larger), 1, - TYPE_SIGN (TREE_TYPE (larger)), - &overflow); - if (! overflow) - alt_larger = wide_int_to_tree (TREE_TYPE (larger), alt); - } - } - } - else if (cmp == GT_EXPR || cmp == GE_EXPR) - { - smaller = rhs; - larger = gimple_cond_lhs (cond); - /* If we have larger > CST it is equivalent to larger >= CST+1. - Likewise larger >= CST is equivalent to larger > CST-1. */ - if (TREE_CODE (smaller) == INTEGER_CST - && INTEGRAL_TYPE_P (TREE_TYPE (smaller))) - { - wi::overflow_type overflow; - if (cmp == GT_EXPR) - { - wide_int alt = wi::add (wi::to_wide (smaller), 1, - TYPE_SIGN (TREE_TYPE (smaller)), - &overflow); - if (! overflow) - alt_smaller = wide_int_to_tree (TREE_TYPE (smaller), alt); - } - else - { - wide_int alt = wi::sub (wi::to_wide (smaller), 1, - TYPE_SIGN (TREE_TYPE (smaller)), - &overflow); - if (! overflow) - alt_smaller = wide_int_to_tree (TREE_TYPE (smaller), alt); - } - } - } - else - return false; - - /* Handle the special case of (signed_type)x < 0 being equivalent - to x > MAX_VAL(signed_type) and (signed_type)x >= 0 equivalent - to x <= MAX_VAL(signed_type). */ - if ((cmp == GE_EXPR || cmp == LT_EXPR) - && INTEGRAL_TYPE_P (type) - && TYPE_UNSIGNED (type) - && integer_zerop (rhs)) - { - tree op = gimple_cond_lhs (cond); - if (TREE_CODE (op) == SSA_NAME - && INTEGRAL_TYPE_P (TREE_TYPE (op)) - && !TYPE_UNSIGNED (TREE_TYPE (op))) - { - gimple *def_stmt = SSA_NAME_DEF_STMT (op); - if (gimple_assign_cast_p (def_stmt)) - { - tree op1 = gimple_assign_rhs1 (def_stmt); - if (INTEGRAL_TYPE_P (TREE_TYPE (op1)) - && TYPE_UNSIGNED (TREE_TYPE (op1)) - && (TYPE_PRECISION (TREE_TYPE (op)) - == TYPE_PRECISION (TREE_TYPE (op1))) - && useless_type_conversion_p (type, TREE_TYPE (op1))) - { - wide_int w1 = wi::max_value (TREE_TYPE (op)); - wide_int w2 = wi::add (w1, 1); - if (cmp == LT_EXPR) - { - larger = op1; - smaller = wide_int_to_tree (TREE_TYPE (op1), w1); - alt_smaller = wide_int_to_tree (TREE_TYPE (op1), w2); - alt_larger = NULL_TREE; - } - else - { - smaller = op1; - larger = wide_int_to_tree (TREE_TYPE (op1), w1); - alt_larger = wide_int_to_tree (TREE_TYPE (op1), w2); - alt_smaller = NULL_TREE; - } - } - } - } - } - - /* We need to know which is the true edge and which is the false - edge so that we know if have abs or negative abs. */ - extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge); - - /* Forward the edges over the middle basic block. */ - if (true_edge->dest == middle_bb) - true_edge = EDGE_SUCC (true_edge->dest, 0); - if (false_edge->dest == middle_bb) - false_edge = EDGE_SUCC (false_edge->dest, 0); - - /* When THREEWAY_P then e1 will point to the edge of the final transition - from middle-bb to end. */ - if (true_edge == e0) - { - if (!threeway_p) - gcc_assert (false_edge == e1); - arg_true = arg0; - arg_false = arg1; - } - else - { - gcc_assert (false_edge == e0); - if (!threeway_p) - gcc_assert (true_edge == e1); - arg_true = arg1; - arg_false = arg0; - } - - if (empty_block_p (middle_bb) - && (!threeway_p - || empty_block_p (alt_middle_bb))) - { - if ((operand_equal_for_phi_arg_p (arg_true, smaller) - || (alt_smaller - && operand_equal_for_phi_arg_p (arg_true, alt_smaller))) - && (operand_equal_for_phi_arg_p (arg_false, larger) - || (alt_larger - && operand_equal_for_phi_arg_p (arg_true, alt_larger)))) - { - /* Case - - if (smaller < larger) - rslt = smaller; - else - rslt = larger; */ - minmax = MIN_EXPR; - } - else if ((operand_equal_for_phi_arg_p (arg_false, smaller) - || (alt_smaller - && operand_equal_for_phi_arg_p (arg_false, alt_smaller))) - && (operand_equal_for_phi_arg_p (arg_true, larger) - || (alt_larger - && operand_equal_for_phi_arg_p (arg_true, alt_larger)))) - minmax = MAX_EXPR; - else - return false; - } - else if (HONOR_NANS (type) || HONOR_SIGNED_ZEROS (type)) - /* The optimization may be unsafe due to NaNs. */ - return false; - else if (middle_bb != alt_middle_bb && threeway_p) - { - /* Recognize the following case: - - if (smaller < larger) - a = MIN (smaller, c); - else - b = MIN (larger, c); - x = PHI <a, b> - - This is equivalent to - - a = MIN (smaller, c); - x = MIN (larger, a); */ - - gimple *assign = last_and_only_stmt (middle_bb); - tree lhs, op0, op1, bound; - tree alt_lhs, alt_op0, alt_op1; - bool invert = false; - - /* When THREEWAY_P then e1 will point to the edge of the final transition - from middle-bb to end. */ - if (true_edge == e0) - gcc_assert (false_edge == EDGE_PRED (e1->src, 0)); - else - gcc_assert (true_edge == EDGE_PRED (e1->src, 0)); - - bool valid_minmax_p = false; - gimple_stmt_iterator it1 - = gsi_start_nondebug_after_labels_bb (middle_bb); - gimple_stmt_iterator it2 - = gsi_start_nondebug_after_labels_bb (alt_middle_bb); - if (gsi_one_nondebug_before_end_p (it1) - && gsi_one_nondebug_before_end_p (it2)) - { - gimple *stmt1 = gsi_stmt (it1); - gimple *stmt2 = gsi_stmt (it2); - if (is_gimple_assign (stmt1) && is_gimple_assign (stmt2)) - { - enum tree_code code1 = gimple_assign_rhs_code (stmt1); - enum tree_code code2 = gimple_assign_rhs_code (stmt2); - valid_minmax_p = (code1 == MIN_EXPR || code1 == MAX_EXPR) - && (code2 == MIN_EXPR || code2 == MAX_EXPR); - } - } - - if (!valid_minmax_p) - return false; - - if (!assign - || gimple_code (assign) != GIMPLE_ASSIGN) - return false; - - /* There cannot be any phi nodes in the middle bb. */ - if (!gimple_seq_empty_p (phi_nodes (middle_bb))) - return false; - - lhs = gimple_assign_lhs (assign); - ass_code = gimple_assign_rhs_code (assign); - if (ass_code != MAX_EXPR && ass_code != MIN_EXPR) - return false; - - op0 = gimple_assign_rhs1 (assign); - op1 = gimple_assign_rhs2 (assign); - - assign = last_and_only_stmt (alt_middle_bb); - if (!assign - || gimple_code (assign) != GIMPLE_ASSIGN) - return false; - - /* There cannot be any phi nodes in the alt middle bb. */ - if (!gimple_seq_empty_p (phi_nodes (alt_middle_bb))) - return false; - - alt_lhs = gimple_assign_lhs (assign); - if (ass_code != gimple_assign_rhs_code (assign)) - return false; - - if (!operand_equal_for_phi_arg_p (lhs, arg_true) - || !operand_equal_for_phi_arg_p (alt_lhs, arg_false)) - return false; - - alt_op0 = gimple_assign_rhs1 (assign); - alt_op1 = gimple_assign_rhs2 (assign); - - if ((operand_equal_for_phi_arg_p (op0, smaller) - || (alt_smaller - && operand_equal_for_phi_arg_p (op0, alt_smaller))) - && (operand_equal_for_phi_arg_p (alt_op0, larger) - || (alt_larger - && operand_equal_for_phi_arg_p (alt_op0, alt_larger)))) - { - /* We got here if the condition is true, i.e., SMALLER < LARGER. */ - if (!operand_equal_for_phi_arg_p (op1, alt_op1)) - return false; - - if ((arg0 = strip_bit_not (op0)) != NULL - && (arg1 = strip_bit_not (alt_op0)) != NULL - && (bound = strip_bit_not (op1)) != NULL) - { - minmax = MAX_EXPR; - ass_code = invert_minmax_code (ass_code); - invert = true; - } - else - { - bound = op1; - minmax = MIN_EXPR; - arg0 = op0; - arg1 = alt_op0; - } - } - else if ((operand_equal_for_phi_arg_p (op0, larger) - || (alt_larger - && operand_equal_for_phi_arg_p (op0, alt_larger))) - && (operand_equal_for_phi_arg_p (alt_op0, smaller) - || (alt_smaller - && operand_equal_for_phi_arg_p (alt_op0, alt_smaller)))) - { - /* We got here if the condition is true, i.e., SMALLER > LARGER. */ - if (!operand_equal_for_phi_arg_p (op1, alt_op1)) - return false; - - if ((arg0 = strip_bit_not (op0)) != NULL - && (arg1 = strip_bit_not (alt_op0)) != NULL - && (bound = strip_bit_not (op1)) != NULL) - { - minmax = MIN_EXPR; - ass_code = invert_minmax_code (ass_code); - invert = true; - } - else - { - bound = op1; - minmax = MAX_EXPR; - arg0 = op0; - arg1 = alt_op0; - } - } - else - return false; - - /* Emit the statement to compute min/max. */ - location_t locus = gimple_location (last_nondebug_stmt (cond_bb)); - gimple_seq stmts = NULL; - tree phi_result = gimple_phi_result (phi); - result = gimple_build (&stmts, locus, minmax, TREE_TYPE (phi_result), - arg0, arg1); - result = gimple_build (&stmts, locus, ass_code, TREE_TYPE (phi_result), - result, bound); - if (invert) - result = gimple_build (&stmts, locus, BIT_NOT_EXPR, TREE_TYPE (phi_result), - result); - - gsi = gsi_last_bb (cond_bb); - gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT); - - replace_phi_edge_with_variable (cond_bb, e1, phi, result); - - return true; - } - else if (!threeway_p - || empty_block_p (alt_middle_bb)) - { - /* Recognize the following case, assuming d <= u: - - if (a <= u) - b = MAX (a, d); - x = PHI <b, u> - - This is equivalent to - - b = MAX (a, d); - x = MIN (b, u); */ - - gimple *assign = last_and_only_stmt (middle_bb); - tree lhs, op0, op1, bound; - - if (!single_pred_p (middle_bb)) - return false; - - if (!assign - || gimple_code (assign) != GIMPLE_ASSIGN) - return false; - - /* There cannot be any phi nodes in the middle bb. */ - if (!gimple_seq_empty_p (phi_nodes (middle_bb))) - return false; - - lhs = gimple_assign_lhs (assign); - ass_code = gimple_assign_rhs_code (assign); - if (ass_code != MAX_EXPR && ass_code != MIN_EXPR) - return false; - op0 = gimple_assign_rhs1 (assign); - op1 = gimple_assign_rhs2 (assign); - - if (true_edge->src == middle_bb) - { - /* We got here if the condition is true, i.e., SMALLER < LARGER. */ - if (!operand_equal_for_phi_arg_p (lhs, arg_true)) - return false; - - if (operand_equal_for_phi_arg_p (arg_false, larger) - || (alt_larger - && operand_equal_for_phi_arg_p (arg_false, alt_larger))) - { - /* Case - - if (smaller < larger) - { - r' = MAX_EXPR (smaller, bound) - } - r = PHI <r', larger> --> to be turned to MIN_EXPR. */ - if (ass_code != MAX_EXPR) - return false; - - minmax = MIN_EXPR; - if (operand_equal_for_phi_arg_p (op0, smaller) - || (alt_smaller - && operand_equal_for_phi_arg_p (op0, alt_smaller))) - bound = op1; - else if (operand_equal_for_phi_arg_p (op1, smaller) - || (alt_smaller - && operand_equal_for_phi_arg_p (op1, alt_smaller))) - bound = op0; - else - return false; - - /* We need BOUND <= LARGER. */ - if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node, - bound, arg_false))) - return false; - } - else if (operand_equal_for_phi_arg_p (arg_false, smaller) - || (alt_smaller - && operand_equal_for_phi_arg_p (arg_false, alt_smaller))) - { - /* Case - - if (smaller < larger) - { - r' = MIN_EXPR (larger, bound) - } - r = PHI <r', smaller> --> to be turned to MAX_EXPR. */ - if (ass_code != MIN_EXPR) - return false; - - minmax = MAX_EXPR; - if (operand_equal_for_phi_arg_p (op0, larger) - || (alt_larger - && operand_equal_for_phi_arg_p (op0, alt_larger))) - bound = op1; - else if (operand_equal_for_phi_arg_p (op1, larger) - || (alt_larger - && operand_equal_for_phi_arg_p (op1, alt_larger))) - bound = op0; - else - return false; - - /* We need BOUND >= SMALLER. */ - if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node, - bound, arg_false))) - return false; - } - else - return false; - } - else - { - /* We got here if the condition is false, i.e., SMALLER > LARGER. */ - if (!operand_equal_for_phi_arg_p (lhs, arg_false)) - return false; - - if (operand_equal_for_phi_arg_p (arg_true, larger) - || (alt_larger - && operand_equal_for_phi_arg_p (arg_true, alt_larger))) - { - /* Case - - if (smaller > larger) - { - r' = MIN_EXPR (smaller, bound) - } - r = PHI <r', larger> --> to be turned to MAX_EXPR. */ - if (ass_code != MIN_EXPR) - return false; - - minmax = MAX_EXPR; - if (operand_equal_for_phi_arg_p (op0, smaller) - || (alt_smaller - && operand_equal_for_phi_arg_p (op0, alt_smaller))) - bound = op1; - else if (operand_equal_for_phi_arg_p (op1, smaller) - || (alt_smaller - && operand_equal_for_phi_arg_p (op1, alt_smaller))) - bound = op0; - else - return false; - - /* We need BOUND >= LARGER. */ - if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node, - bound, arg_true))) - return false; - } - else if (operand_equal_for_phi_arg_p (arg_true, smaller) - || (alt_smaller - && operand_equal_for_phi_arg_p (arg_true, alt_smaller))) - { - /* Case - - if (smaller > larger) - { - r' = MAX_EXPR (larger, bound) - } - r = PHI <r', smaller> --> to be turned to MIN_EXPR. */ - if (ass_code != MAX_EXPR) - return false; - - minmax = MIN_EXPR; - if (operand_equal_for_phi_arg_p (op0, larger)) - bound = op1; - else if (operand_equal_for_phi_arg_p (op1, larger)) - bound = op0; - else - return false; - - /* We need BOUND <= SMALLER. */ - if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node, - bound, arg_true))) - return false; - } - else - return false; - } - - /* Move the statement from the middle block. */ - gsi = gsi_last_bb (cond_bb); - gsi_from = gsi_last_nondebug_bb (middle_bb); - reset_flow_sensitive_info (SINGLE_SSA_TREE_OPERAND (gsi_stmt (gsi_from), - SSA_OP_DEF)); - gsi_move_before (&gsi_from, &gsi); - } - else - return false; - - /* Emit the statement to compute min/max. */ - gimple_seq stmts = NULL; - tree phi_result = gimple_phi_result (phi); - - /* When we can't use a MIN/MAX_EXPR still make sure the expression - stays in a form to be recognized by ISA that map to IEEE x > y ? x : y - semantics (that's not IEEE max semantics). */ - if (HONOR_NANS (type) || HONOR_SIGNED_ZEROS (type)) - { - result = gimple_build (&stmts, cmp, boolean_type_node, - gimple_cond_lhs (cond), rhs); - result = gimple_build (&stmts, COND_EXPR, TREE_TYPE (phi_result), - result, arg_true, arg_false); - } - else - result = gimple_build (&stmts, minmax, TREE_TYPE (phi_result), arg0, arg1); - - gsi = gsi_last_bb (cond_bb); - gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT); - - replace_phi_edge_with_variable (cond_bb, e1, phi, result); - - return true; -} - /* Attempt to optimize (x <=> y) cmp 0 and similar comparisons. For strong ordering <=> try to match something like: <bb 2> : // cond3_bb (== cond2_bb) @@ -4365,9 +3776,8 @@ execute_over_cond_phis (func_type func) But in this case bb1/bb2 can only be forwarding basic blocks. This fully replaces the old "Conditional Replacement", - "ABS Replacement" transformations as they are now + "ABS Replacement" and "MIN/MAX Replacement" transformations as they are now implmeneted in match.pd. - Some parts of the "MIN/MAX Replacement" are re-implemented in match.pd. Value Replacement ----------------- @@ -4409,26 +3819,6 @@ execute_over_cond_phis (func_type func) t3 = t1 & t2; x = a; - MIN/MAX Replacement - ------------------- - - This transformation, minmax_replacement replaces - - bb0: - if (a <= b) goto bb2; else goto bb1; - bb1: - bb2: - x = PHI <b (bb1), a (bb0), ...>; - - with - - bb0: - x' = MIN_EXPR (a, b) - bb2: - x = PHI <x' (bb0), ...>; - - A similar transformation is done for MAX_EXPR. - This pass also performs a fifth transformation of a slightly different flavor. @@ -4642,9 +4032,6 @@ pass_phiopt::execute (function *) && cond_removal_in_builtin_zero_pattern (bb, bb1, e1, e2, phi, arg0, arg1)) cfgchanged = true; - else if (minmax_replacement (bb, bb1, bb2, e1, e2, phi, arg0, arg1, - diamond_p)) - cfgchanged = true; else if (single_pred_p (bb1) && !diamond_p && spaceship_replacement (bb, bb1, e1, e2, phi, arg0, arg1)) |