+/* Bounds on some value, BELOW <= X <= UP. */
+
+typedef struct
+{
+ mpz_t below, up;
+} bounds;
+
+/* Sets RESULT to VAL, taken unsigned if UNS is true and as signed
+ otherwise. */
+
+static void
+mpz_set_double_int (mpz_t result, double_int val, bool uns)
+{
+ bool negate = false;
+ unsigned HOST_WIDE_INT vp[2];
+
+ if (!uns && double_int_negative_p (val))
+ {
+ negate = true;
+ val = double_int_neg (val);
+ }
+
+ vp[0] = val.low;
+ vp[1] = (unsigned HOST_WIDE_INT) val.high;
+ mpz_import (result, 2, -1, sizeof (HOST_WIDE_INT), 0, 0, vp);
+
+ if (negate)
+ mpz_neg (result, result);
+}
+
+/* Stores bounds of TYPE to MIN and MAX. */
+
+static void
+get_type_bounds (tree type, mpz_t min, mpz_t max)
+{
+ if (TYPE_UNSIGNED (type))
+ {
+ mpz_set_ui (min, 0);
+ mpz_set_double_int (max, double_int_mask (TYPE_PRECISION (type)), true);
+ }
+ else
+ {
+ double_int mx, mn;
+
+ mx = double_int_mask (TYPE_PRECISION (type) - 1);
+ mn = double_int_sext (double_int_add (mx, double_int_one),
+ TYPE_PRECISION (type));
+ mpz_set_double_int (max, mx, true);
+ mpz_set_double_int (min, mn, false);
+ }
+}
+
+/* Returns VAL converted to TYPE. If VAL does not fit in TYPE,
+ the minimum or maximum value of the type is returned instead. */
+
+static double_int
+mpz_to_double_int (tree type, mpz_t val)
+{
+ mpz_t min, max;
+ unsigned HOST_WIDE_INT vp[2];
+ bool negate = false;
+ size_t count;
+ double_int res;
+
+ mpz_init (min);
+ mpz_init (max);
+ get_type_bounds (type, min, max);
+
+ if (mpz_cmp (val, min) < 0)
+ mpz_set (val, min);
+ else if (mpz_cmp (val, max) > 0)
+ mpz_set (val, max);
+
+ if (mpz_sgn (val) < 0)
+ negate = true;
+
+ vp[0] = 0;
+ vp[1] = 0;
+ mpz_export (vp, &count, -1, sizeof (HOST_WIDE_INT), 0, 0, val);
+ gcc_assert (count <= 2);
+
+ mpz_clear (min);
+ mpz_clear (max);
+
+ res.low = vp[0];
+ res.high = (HOST_WIDE_INT) vp[1];
+
+ res = double_int_ext (res, TYPE_PRECISION (type), TYPE_UNSIGNED (type));
+ if (negate)
+ res = double_int_neg (res);
+
+ return res;
+}
+
+/* Splits expression EXPR to a variable part VAR and constant OFFSET. */
+
+static void
+split_to_var_and_offset (tree expr, tree *var, mpz_t offset)
+{
+ tree type = TREE_TYPE (expr);
+ tree op0, op1;
+ double_int off;
+ bool negate = false;
+
+ *var = expr;
+ mpz_set_ui (offset, 0);
+
+ switch (TREE_CODE (expr))
+ {
+ case MINUS_EXPR:
+ negate = true;
+ /* Fallthru. */
+
+ case PLUS_EXPR:
+ op0 = TREE_OPERAND (expr, 0);
+ op1 = TREE_OPERAND (expr, 1);
+
+ if (TREE_CODE (op1) != INTEGER_CST)
+ break;
+
+ *var = op0;
+ /* Always sign extend the offset. */
+ off = double_int_sext (tree_to_double_int (op1),
+ TYPE_PRECISION (type));
+ mpz_set_double_int (offset, off, false);
+ break;
+
+ case INTEGER_CST:
+ *var = build_int_cst_type (type, 0);
+ off = tree_to_double_int (expr);
+ mpz_set_double_int (offset, off, TYPE_UNSIGNED (type));
+ break;
+
+ default:
+ break;
+ }
+}
+
+/* Stores estimate on the minimum/maximum value of the expression VAR + OFF
+ in TYPE to MIN and MAX. */
+
+static void
+determine_value_range (tree type, tree var, mpz_t off,
+ mpz_t min, mpz_t max)
+{
+ /* If the expression is a constant, we know its value exactly. */
+ if (integer_zerop (var))
+ {
+ mpz_set (min, off);
+ mpz_set (max, off);
+ return;
+ }
+
+ /* If the computation may wrap, we know nothing about the value, except for
+ the range of the type. */
+ get_type_bounds (type, min, max);
+ if (!nowrap_type_p (type))
+ return;
+
+ /* Since the addition of OFF does not wrap, if OFF is positive, then we may
+ add it to MIN, otherwise to MAX. */
+ if (mpz_sgn (off) < 0)
+ mpz_add (max, max, off);
+ else
+ mpz_add (min, min, off);
+}
+
+/* Stores the bounds on the difference of the values of the expressions
+ (var + X) and (var + Y), computed in TYPE, to BNDS. */
+
+static void
+bound_difference_of_offsetted_base (tree type, mpz_t x, mpz_t y,
+ bounds *bnds)
+{
+ int rel = mpz_cmp (x, y);
+ bool may_wrap = !nowrap_type_p (type);
+ mpz_t m;
+
+ /* If X == Y, then the expressions are always equal.
+ If X > Y, there are the following possibilities:
+ a) neither of var + X and var + Y overflow or underflow, or both of
+ them do. Then their difference is X - Y.
+ b) var + X overflows, and var + Y does not. Then the values of the
+ expressions are var + X - M and var + Y, where M is the range of
+ the type, and their difference is X - Y - M.
+ c) var + Y underflows and var + X does not. Their difference again
+ is M - X + Y.
+ Therefore, if the arithmetics in type does not overflow, then the
+ bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y)
+ Similarly, if X < Y, the bounds are either (X - Y, X - Y) or
+ (X - Y, X - Y + M). */
+
+ if (rel == 0)
+ {
+ mpz_set_ui (bnds->below, 0);
+ mpz_set_ui (bnds->up, 0);
+ return;
+ }
+
+ mpz_init (m);
+ mpz_set_double_int (m, double_int_mask (TYPE_PRECISION (type)), true);
+ mpz_add_ui (m, m, 1);
+ mpz_sub (bnds->up, x, y);
+ mpz_set (bnds->below, bnds->up);
+
+ if (may_wrap)
+ {
+ if (rel > 0)
+ mpz_sub (bnds->below, bnds->below, m);
+ else
+ mpz_add (bnds->up, bnds->up, m);
+ }
+
+ mpz_clear (m);
+}
+
+/* From condition C0 CMP C1 derives information regarding the
+ difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE,
+ and stores it to BNDS. */
+
+static void
+refine_bounds_using_guard (tree type, tree varx, mpz_t offx,
+ tree vary, mpz_t offy,
+ tree c0, enum tree_code cmp, tree c1,
+ bounds *bnds)
+{
+ tree varc0, varc1, tmp;
+ mpz_t offc0, offc1, loffx, loffy, bnd;
+ bool lbound = false;
+ bool no_wrap = nowrap_type_p (type);
+ bool x_ok, y_ok;
+
+ switch (cmp)
+ {
+ case LT_EXPR:
+ case LE_EXPR:
+ case GT_EXPR:
+ case GE_EXPR:
+ break;
+
+ case EQ_EXPR:
+ /* We could derive quite precise information from EQ_EXPR, however, such
+ a guard is unlikely to appear, so we do not bother with handling it.
+ TODO. */
+ return;
+
+ case NE_EXPR:
+ /* NE_EXPR comparisons do not contain much of useful information (except for
+ special cases like comparing with the bounds of the type, TODO). */
+ return;
+ default:
+ return;
+ }
+
+ mpz_init (offc0);
+ mpz_init (offc1);
+ split_to_var_and_offset (expand_simple_operations (c0), &varc0, offc0);
+ split_to_var_and_offset (expand_simple_operations (c1), &varc1, offc1);
+
+ /* We are only interested in comparisons of expressions based on VARX and
+ VARY. TODO -- we might also be able to derive some bounds from
+ expressions containing just one of the variables. */
+
+ if (operand_equal_p (varx, varc1, 0))
+ {
+ tmp = varc0; varc0 = varc1; varc1 = tmp;
+ mpz_swap (offc0, offc1);
+ cmp = swap_tree_comparison (cmp);
+ }
+
+ if (!operand_equal_p (varx, varc0, 0)
+ || !operand_equal_p (vary, varc1, 0))
+ goto end;
+
+ mpz_init_set (loffx, offx);
+ mpz_init_set (loffy, offy);
+
+ if (cmp == GT_EXPR || cmp == GE_EXPR)
+ {
+ tmp = varx; varx = vary; vary = tmp;
+ mpz_swap (offc0, offc1);
+ mpz_swap (loffx, loffy);
+ cmp = swap_tree_comparison (cmp);
+ lbound = true;
+ }
+
+ /* If there is no overflow, the condition implies that
+
+ (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0).
+
+ The overflows and underflows may complicate things a bit; each
+ overflow decreases the appropriate offset by M, and underflow
+ increases it by M. The above inequality would not necessarily be
+ true if
+
+ -- VARX + OFFX underflows and VARX + OFFC0 does not, or
+ VARX + OFFC0 overflows, but VARX + OFFX does not.
+ This may only happen if OFFX < OFFC0.
+ -- VARY + OFFY overflows and VARY + OFFC1 does not, or
+ VARY + OFFC1 underflows and VARY + OFFY does not.
+ This may only happen if OFFY > OFFC1. */
+
+ if (no_wrap)
+ {
+ x_ok = true;
+ y_ok = true;
+ }
+ else
+ {
+ x_ok = (integer_zerop (varx)
+ || mpz_cmp (loffx, offc0) >= 0);
+ y_ok = (integer_zerop (vary)
+ || mpz_cmp (loffy, offc1) <= 0);
+ }
+
+ if (x_ok && y_ok)
+ {
+ mpz_init (bnd);
+ mpz_sub (bnd, loffx, loffy);
+ mpz_add (bnd, bnd, offc1);
+ mpz_sub (bnd, bnd, offc0);
+
+ if (cmp == LT_EXPR)
+ mpz_sub_ui (bnd, bnd, 1);
+
+ if (lbound)
+ {
+ mpz_neg (bnd, bnd);
+ if (mpz_cmp (bnds->below, bnd) < 0)
+ mpz_set (bnds->below, bnd);
+ }
+ else
+ {
+ if (mpz_cmp (bnd, bnds->up) < 0)
+ mpz_set (bnds->up, bnd);
+ }
+ mpz_clear (bnd);
+ }
+
+ mpz_clear (loffx);
+ mpz_clear (loffy);
+end:
+ mpz_clear (offc0);
+ mpz_clear (offc1);
+}
+
+/* Stores the bounds on the value of the expression X - Y in LOOP to BNDS.
+ The subtraction is considered to be performed in arbitrary precision,
+ without overflows.
+
+ We do not attempt to be too clever regarding the value ranges of X and
+ Y; most of the time, they are just integers or ssa names offsetted by
+ integer. However, we try to use the information contained in the
+ comparisons before the loop (usually created by loop header copying). */
+
+static void
+bound_difference (struct loop *loop, tree x, tree y, bounds *bnds)
+{
+ tree type = TREE_TYPE (x);
+ tree varx, vary;
+ mpz_t offx, offy;
+ mpz_t minx, maxx, miny, maxy;
+ int cnt = 0;
+ edge e;
+ basic_block bb;
+ tree cond, c0, c1, ctype;
+ enum tree_code cmp;
+
+ mpz_init (bnds->below);
+ mpz_init (bnds->up);
+ mpz_init (offx);
+ mpz_init (offy);
+ split_to_var_and_offset (x, &varx, offx);
+ split_to_var_and_offset (y, &vary, offy);
+
+ if (!integer_zerop (varx)
+ && operand_equal_p (varx, vary, 0))
+ {
+ /* Special case VARX == VARY -- we just need to compare the
+ offsets. The matters are a bit more complicated in the
+ case addition of offsets may wrap. */
+ bound_difference_of_offsetted_base (type, offx, offy, bnds);
+ }
+ else
+ {
+ /* Otherwise, use the value ranges to determine the initial
+ estimates on below and up. */
+ mpz_init (minx);
+ mpz_init (maxx);
+ mpz_init (miny);
+ mpz_init (maxy);
+ determine_value_range (type, varx, offx, minx, maxx);
+ determine_value_range (type, vary, offy, miny, maxy);
+
+ mpz_sub (bnds->below, minx, maxy);
+ mpz_sub (bnds->up, maxx, miny);
+ mpz_clear (minx);
+ mpz_clear (maxx);
+ mpz_clear (miny);
+ mpz_clear (maxy);
+ }
+
+ /* If both X and Y are constants, we cannot get any more precise. */
+ if (integer_zerop (varx) && integer_zerop (vary))
+ goto end;
+
+ /* Now walk the dominators of the loop header and use the entry
+ guards to refine the estimates. */
+ for (bb = loop->header;
+ bb != ENTRY_BLOCK_PTR && cnt < MAX_DOMINATORS_TO_WALK;
+ bb = get_immediate_dominator (CDI_DOMINATORS, bb))
+ {
+ if (!single_pred_p (bb))
+ continue;
+ e = single_pred_edge (bb);
+
+ if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
+ continue;
+
+ cond = COND_EXPR_COND (last_stmt (e->src));
+ if (!COMPARISON_CLASS_P (cond))
+ continue;
+ c0 = TREE_OPERAND (cond, 0);
+ cmp = TREE_CODE (cond);
+ c1 = TREE_OPERAND (cond, 1);
+ ctype = TREE_TYPE (c0);
+
+ if (!tree_ssa_useless_type_conversion_1 (ctype, type))
+ continue;
+
+ if (e->flags & EDGE_FALSE_VALUE)
+ cmp = invert_tree_comparison (cmp, false);
+
+ refine_bounds_using_guard (type, varx, offx, vary, offy,
+ c0, cmp, c1, bnds);
+ ++cnt;
+ }
+
+end:
+ mpz_clear (offx);
+ mpz_clear (offy);
+}
+
+/* Update the bounds in BNDS that restrict the value of X to the bounds
+ that restrict the value of X + DELTA. X can be obtained as a
+ difference of two values in TYPE. */
+
+static void
+bounds_add (bounds *bnds, double_int delta, tree type)
+{
+ mpz_t mdelta, max;
+
+ mpz_init (mdelta);
+ mpz_set_double_int (mdelta, delta, false);
+
+ mpz_init (max);
+ mpz_set_double_int (max, double_int_mask (TYPE_PRECISION (type)), true);
+
+ mpz_add (bnds->up, bnds->up, mdelta);
+ mpz_add (bnds->below, bnds->below, mdelta);
+
+ if (mpz_cmp (bnds->up, max) > 0)
+ mpz_set (bnds->up, max);
+
+ mpz_neg (max, max);
+ if (mpz_cmp (bnds->below, max) < 0)
+ mpz_set (bnds->below, max);
+
+ mpz_clear (mdelta);
+ mpz_clear (max);
+}
+
+/* Update the bounds in BNDS that restrict the value of X to the bounds
+ that restrict the value of -X. */
+
+static void
+bounds_negate (bounds *bnds)
+{
+ mpz_t tmp;
+
+ mpz_init_set (tmp, bnds->up);
+ mpz_neg (bnds->up, bnds->below);
+ mpz_neg (bnds->below, tmp);
+ mpz_clear (tmp);
+}
+
OSDN Git Service
