+static tree
+strip_wrap_conserving_type_conversions (tree exp)
+{
+ while (tree_ssa_useless_type_conversion (exp)
+ && (nowrap_type_p (TREE_TYPE (exp))
+ == nowrap_type_p (TREE_TYPE (TREE_OPERAND (exp, 0)))))
+ exp = TREE_OPERAND (exp, 0);
+ return exp;
+}
+
+/* Walk the SSA form and check whether E == WHAT. Fairly simplistic, we
+ check for an exact match. */
+
+static bool
+expr_equal_p (tree e, tree what)
+{
+ gimple stmt;
+ enum tree_code code;
+
+ e = strip_wrap_conserving_type_conversions (e);
+ what = strip_wrap_conserving_type_conversions (what);
+
+ code = TREE_CODE (what);
+ if (TREE_TYPE (e) != TREE_TYPE (what))
+ return false;
+
+ if (operand_equal_p (e, what, 0))
+ return true;
+
+ if (TREE_CODE (e) != SSA_NAME)
+ return false;
+
+ stmt = SSA_NAME_DEF_STMT (e);
+ if (gimple_code (stmt) != GIMPLE_ASSIGN
+ || gimple_assign_rhs_code (stmt) != code)
+ return false;
+
+ switch (get_gimple_rhs_class (code))
+ {
+ case GIMPLE_BINARY_RHS:
+ if (!expr_equal_p (gimple_assign_rhs2 (stmt), TREE_OPERAND (what, 1)))
+ return false;
+ /* Fallthru. */
+
+ case GIMPLE_UNARY_RHS:
+ case GIMPLE_SINGLE_RHS:
+ return expr_equal_p (gimple_assign_rhs1 (stmt), TREE_OPERAND (what, 0));
+ default:
+ return false;
+ }
+}
+
+/* Returns true if we can prove that BASE - OFFSET does not overflow. For now,
+ we only detect the situation that BASE = SOMETHING + OFFSET, where the
+ calculation is performed in non-wrapping type.
+
+ TODO: More generally, we could test for the situation that
+ BASE = SOMETHING + OFFSET' and OFFSET is between OFFSET' and zero.
+ This would require knowing the sign of OFFSET.
+
+ Also, we only look for the first addition in the computation of BASE.
+ More complex analysis would be better, but introducing it just for
+ this optimization seems like an overkill. */
+
+static bool
+difference_cannot_overflow_p (tree base, tree offset)
+{
+ enum tree_code code;
+ tree e1, e2;
+
+ if (!nowrap_type_p (TREE_TYPE (base)))
+ return false;
+
+ base = expand_simple_operations (base);
+
+ if (TREE_CODE (base) == SSA_NAME)
+ {
+ gimple stmt = SSA_NAME_DEF_STMT (base);
+
+ if (gimple_code (stmt) != GIMPLE_ASSIGN)
+ return false;
+
+ code = gimple_assign_rhs_code (stmt);
+ if (get_gimple_rhs_class (code) != GIMPLE_BINARY_RHS)
+ return false;
+
+ e1 = gimple_assign_rhs1 (stmt);
+ e2 = gimple_assign_rhs2 (stmt);
+ }
+ else
+ {
+ code = TREE_CODE (base);
+ if (get_gimple_rhs_class (code) != GIMPLE_BINARY_RHS)
+ return false;
+ e1 = TREE_OPERAND (base, 0);
+ e2 = TREE_OPERAND (base, 1);
+ }
+
+ /* TODO: deeper inspection may be necessary to prove the equality. */
+ switch (code)
+ {
+ case PLUS_EXPR:
+ return expr_equal_p (e1, offset) || expr_equal_p (e2, offset);
+ case POINTER_PLUS_EXPR:
+ return expr_equal_p (e2, offset);
+
+ default:
+ return false;
+ }
+}
+
+/* Tries to replace loop exit by one formulated in terms of a LT_EXPR
+ comparison with CAND. NITER describes the number of iterations of
+ the loops. If successful, the comparison in COMP_P is altered accordingly.
+
+ We aim to handle the following situation:
+
+ sometype *base, *p;
+ int a, b, i;
+
+ i = a;
+ p = p_0 = base + a;
+
+ do
+ {
+ bla (*p);
+ p++;
+ i++;
+ }
+ while (i < b);
+
+ Here, the number of iterations of the loop is (a + 1 > b) ? 0 : b - a - 1.
+ We aim to optimize this to
+
+ p = p_0 = base + a;
+ do
+ {
+ bla (*p);
+ p++;
+ }
+ while (p < p_0 - a + b);
+
+ This preserves the correctness, since the pointer arithmetics does not
+ overflow. More precisely:
+
+ 1) if a + 1 <= b, then p_0 - a + b is the final value of p, hence there is no
+ overflow in computing it or the values of p.
+ 2) if a + 1 > b, then we need to verify that the expression p_0 - a does not
+ overflow. To prove this, we use the fact that p_0 = base + a. */
+
+static bool
+iv_elimination_compare_lt (struct ivopts_data *data,
+ struct iv_cand *cand, enum tree_code *comp_p,
+ struct tree_niter_desc *niter)
+{
+ tree cand_type, a, b, mbz, nit_type = TREE_TYPE (niter->niter), offset;
+ struct affine_tree_combination nit, tmpa, tmpb;
+ enum tree_code comp;
+ HOST_WIDE_INT step;
+
+ /* We need to know that the candidate induction variable does not overflow.
+ While more complex analysis may be used to prove this, for now just
+ check that the variable appears in the original program and that it
+ is computed in a type that guarantees no overflows. */
+ cand_type = TREE_TYPE (cand->iv->base);
+ if (cand->pos != IP_ORIGINAL || !nowrap_type_p (cand_type))
+ return false;
+
+ /* Make sure that the loop iterates till the loop bound is hit, as otherwise
+ the calculation of the BOUND could overflow, making the comparison
+ invalid. */
+ if (!data->loop_single_exit_p)
+ return false;
+
+ /* We need to be able to decide whether candidate is increasing or decreasing
+ in order to choose the right comparison operator. */
+ if (!cst_and_fits_in_hwi (cand->iv->step))
+ return false;
+ step = int_cst_value (cand->iv->step);
+
+ /* Check that the number of iterations matches the expected pattern:
+ a + 1 > b ? 0 : b - a - 1. */
+ mbz = niter->may_be_zero;
+ if (TREE_CODE (mbz) == GT_EXPR)
+ {
+ /* Handle a + 1 > b. */
+ tree op0 = TREE_OPERAND (mbz, 0);
+ if (TREE_CODE (op0) == PLUS_EXPR && integer_onep (TREE_OPERAND (op0, 1)))
+ {
+ a = TREE_OPERAND (op0, 0);
+ b = TREE_OPERAND (mbz, 1);
+ }
+ else
+ return false;
+ }
+ else if (TREE_CODE (mbz) == LT_EXPR)
+ {
+ tree op1 = TREE_OPERAND (mbz, 1);
+
+ /* Handle b < a + 1. */
+ if (TREE_CODE (op1) == PLUS_EXPR && integer_onep (TREE_OPERAND (op1, 1)))
+ {
+ a = TREE_OPERAND (op1, 0);
+ b = TREE_OPERAND (mbz, 0);
+ }
+ else
+ return false;
+ }
+ else
+ return false;
+
+ /* Expected number of iterations is B - A - 1. Check that it matches
+ the actual number, i.e., that B - A - NITER = 1. */
+ tree_to_aff_combination (niter->niter, nit_type, &nit);
+ tree_to_aff_combination (fold_convert (nit_type, a), nit_type, &tmpa);
+ tree_to_aff_combination (fold_convert (nit_type, b), nit_type, &tmpb);
+ aff_combination_scale (&nit, double_int_minus_one);
+ aff_combination_scale (&tmpa, double_int_minus_one);
+ aff_combination_add (&tmpb, &tmpa);
+ aff_combination_add (&tmpb, &nit);
+ if (tmpb.n != 0 || !double_int_equal_p (tmpb.offset, double_int_one))
+ return false;
+
+ /* Finally, check that CAND->IV->BASE - CAND->IV->STEP * A does not
+ overflow. */
+ offset = fold_build2 (MULT_EXPR, TREE_TYPE (cand->iv->step),
+ cand->iv->step,
+ fold_convert (TREE_TYPE (cand->iv->step), a));
+ if (!difference_cannot_overflow_p (cand->iv->base, offset))
+ return false;
+
+ /* Determine the new comparison operator. */
+ comp = step < 0 ? GT_EXPR : LT_EXPR;
+ if (*comp_p == NE_EXPR)
+ *comp_p = comp;
+ else if (*comp_p == EQ_EXPR)
+ *comp_p = invert_tree_comparison (comp, false);
+ else
+ gcc_unreachable ();
+
+ return true;
+}
+
OSDN Git Service
