This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: Value Range Propagation Patch (Version 4)
- To: toon at moene dot indiv dot nluug dot nl
- Subject: Re: Value Range Propagation Patch (Version 4)
- From: John Wehle <john at feith dot com>
- Date: Fri, 28 Jul 2000 17:20:24 -0400 (EDT)
- CC: gcc-patches at gcc dot gnu dot org, law at cygnus dot com
> subroutine aap(a, n)
> dimension a(n)
> do i = 1, n
> a(i) = i
> enddo
> end
>
> VRP cannot determine that the range test by array bound checking is
> superfluous (because n is not a constant, and hence not subject to
> *value* range propagation).
>
> However, it should be possible to determine that `i' can never have a
> value less than the lower bound of the array `a' (which is 1 by default)
> because both are constants.
Two problems:
1) infer_value_range_from_loop was being overly conservative. This
issue is addressed by the attached patch and allows the call to
abort to be deleted when compiling:
func (int n)
{
int b;
int i;
b = 0;
for (i = 0; i < n; i++)
{
if (i < 0)
abort ();
b += i;
}
return b;
}
on i386 or sparc. Unfortunately the call isn't deleted (even with
the patch) on the alpha due to subreg / sign_extension interactions.
2) The fortran example still results in two BIVs ... one for the loop
counter and one for the array index. VRP can't tell that the array
index doesn't overflow. However, VRP can delete later comparisons
against zero.
-- John
-------------------8<-------------------------8<-------------------------
*** gcc/vrp.c.ORIGINAL Fri Jul 28 17:12:23 2000
--- gcc/vrp.c Fri Jul 28 00:31:09 2000
*************** compute_value_range (vr, mode, x, simpli
*** 2933,2939 ****
/* For each register mentioned in X, record the number
of bits needed to compute X starting with the knowledge
! that only NLSB bits of X is used. */
static void
record_value_range_nlsb (x, nlsb)
--- 2933,2940 ----
/* For each register mentioned in X, record the number
of bits needed to compute X starting with the knowledge
! that only NLSB bits of X is used (0 means all bits
! are significant). */
static void
record_value_range_nlsb (x, nlsb)
*************** infer_value_range_from_comparison (code,
*** 3414,3421 ****
/* Given value ranges OP0 and OP1 (described by condition
COND) where one value range is diverging towards the
! other which is constant, modify the diverging value
! range so that it includes the constant value range.
JUMP is the conditional jump at the end of a loop
which is evaluating condition COND. */
--- 3415,3422 ----
/* Given value ranges OP0 and OP1 (described by condition
COND) where one value range is diverging towards the
! other which is unchanging, modify the diverging value
! range so that it includes the unchanging value range.
JUMP is the conditional jump at the end of a loop
which is evaluating condition COND. */
*************** infer_value_range_from_loop (jump, cond,
*** 3480,3521 ****
TREE_UNSIGNED (TREE_TYPE (&op1->min))))
return;
- /* Ensure that exactly one of the operands is constant. */
- if ((tree_int_cst_equal (&op0->min, &previous_op[0].min)
- && tree_int_cst_equal (&op0->max, &previous_op[0].max))
- == (tree_int_cst_equal (&op1->min, &previous_op[1].min)
- && tree_int_cst_equal (&op1->max, &previous_op[1].max)))
- return;
-
if (TREE_UNSIGNED (TREE_TYPE (&op0->min)))
{
! if (INT_CST_LT_UNSIGNED (&op0->max, &op1->min)
! && (INT_CST_LT_UNSIGNED (&previous_op[0].max, &op0->max)
! || INT_CST_LT_UNSIGNED (&op1->min, &previous_op[1].min)))
! merge_value_ranges (op0, op1,
! INT_CST_LT_UNSIGNED (&previous_op[0].max,
! &op0->max) ? op0 : op1);
! else if (INT_CST_LT_UNSIGNED (&op1->max, &op0->min)
! && (INT_CST_LT_UNSIGNED (&previous_op[1].max, &op1->max)
! || INT_CST_LT_UNSIGNED (&op0->min, &previous_op[0].min)))
! merge_value_ranges (op0, op1,
! INT_CST_LT_UNSIGNED (&previous_op[1].max,
! &op1->max) ? op1 : op0);
}
else
{
! if (INT_CST_LT (&op0->max, &op1->min)
! && (INT_CST_LT (&previous_op[0].max, &op0->max)
! || INT_CST_LT (&op1->min, &previous_op[1].min)))
! merge_value_ranges (op0, op1,
! INT_CST_LT (&previous_op[0].max,
! &op0->max) ? op0 : op1);
! else if (INT_CST_LT (&op1->max, &op0->min)
! && (INT_CST_LT (&previous_op[1].max, &op1->max)
! || INT_CST_LT (&op0->min, &previous_op[0].min)))
! merge_value_ranges (op0, op1,
! INT_CST_LT (&previous_op[1].max,
! &op1->max) ? op1 : op0);
}
}
--- 3481,3543 ----
TREE_UNSIGNED (TREE_TYPE (&op1->min))))
return;
if (TREE_UNSIGNED (TREE_TYPE (&op0->min)))
{
! if (tree_int_cst_equal (&op0->min, &previous_op[0].min)
! && tree_int_cst_equal (&op0->max, &previous_op[0].max))
! {
! if (INT_CST_LT_UNSIGNED (&op1->min, &previous_op[1].min)
! == INT_CST_LT_UNSIGNED (&previous_op[1].max, &op1->max))
! return;
! if (INT_CST_LT_UNSIGNED (&op1->min, &previous_op[1].min)
! && INT_CST_LT_UNSIGNED (&op0->min, &op1->min))
! op1->min = op0->min;
! else if (INT_CST_LT_UNSIGNED (&previous_op[1].max, &op1->max)
! && INT_CST_LT_UNSIGNED (&op1->max, &op0->max))
! op1->max = op0->max;
! }
! else if (tree_int_cst_equal (&op1->min, &previous_op[1].min)
! && tree_int_cst_equal (&op1->max, &previous_op[1].max))
! {
! if (INT_CST_LT_UNSIGNED (&op0->min, &previous_op[0].min)
! == INT_CST_LT_UNSIGNED (&previous_op[0].max, &op0->max))
! return;
! if (INT_CST_LT_UNSIGNED (&op0->min, &previous_op[0].min)
! && INT_CST_LT_UNSIGNED (&op1->min, &op0->min))
! op0->min = op1->min;
! else if (INT_CST_LT_UNSIGNED (&previous_op[0].max, &op0->max)
! && INT_CST_LT_UNSIGNED (&op0->max, &op1->max))
! op0->max = op1->max;
! }
}
else
{
! if (tree_int_cst_equal (&op0->min, &previous_op[0].min)
! && tree_int_cst_equal (&op0->max, &previous_op[0].max))
! {
! if (INT_CST_LT (&op1->min, &previous_op[1].min)
! == INT_CST_LT (&previous_op[1].max, &op1->max))
! return;
! if (INT_CST_LT (&op1->min, &previous_op[1].min)
! && INT_CST_LT (&op0->min, &op1->min))
! op1->min = op0->min;
! else if (INT_CST_LT (&previous_op[1].max, &op1->max)
! && INT_CST_LT (&op1->max, &op0->max))
! op1->max = op0->max;
! }
! else if (tree_int_cst_equal (&op1->min, &previous_op[1].min)
! && tree_int_cst_equal (&op1->max, &previous_op[1].max))
! {
! if (INT_CST_LT (&op0->min, &previous_op[0].min)
! == INT_CST_LT (&previous_op[0].max, &op0->max))
! return;
! if (INT_CST_LT (&op0->min, &previous_op[0].min)
! && INT_CST_LT (&op1->min, &op0->min))
! op0->min = op1->min;
! else if (INT_CST_LT (&previous_op[0].max, &op0->max)
! && INT_CST_LT (&op0->max, &op1->max))
! op0->max = op1->max;
! }
}
}
*************** propagate_value_range_compare_backwards
*** 3777,3782 ****
--- 3799,3816 ----
}
}
+ for (i = 0; i < 2; i++)
+ {
+ x = XEXP (cond, i);
+
+ if (GET_CODE (x) == SUBREG)
+ x = SUBREG_REG (x);
+
+ if (GET_CODE (x) == REG
+ && TEST_BIT (bb_reg_vr_unknown[BLOCK_NUM (insn)], REGNO (x)))
+ return;
+ }
+
record_compare_value_range (code, cond, *op0, *op1);
for (i = 0; i < 2; i++)
*************** propagate_value_range_compare_backwards
*** 3971,3981 ****
--- 4005,4021 ----
break;
previous_vr = reg_vr_table [REGNO (x)];
+
+ /* Give up if the current value range is narrower */
if (TREE_CONSTANT (&previous_vr.min)
&& (! convert_value_ranges (&vr, &previous_vr)
|| value_range_diverges (&vr, &previous_vr)))
break;
+ /* or if it is unknown. */
+ if (TEST_BIT (bb_reg_vr_unknown[BLOCK_NUM (insn)], REGNO (x)))
+ break;
+
if (original)
{
*original = (struct reg_value_range *)
*************** value_range_prop (f, alter_jumps, file)
*** 4440,4447 ****
max_bb_reg_vr_allocated = 0;
- sbitmap_ones (bb_reg_vr_unknown[0]);
-
bb_info[0].reached = 1;
bb_queue.write = 0;
--- 4480,4485 ----
*************** value_range_prop (f, alter_jumps, file)
*** 4627,4633 ****
|| ! tree_int_cst_equal (&rvrp->vr.max, &prvrp->vr.max))
{
changed = 1;
! if (pass >= (bb_info[bb].preds_converged + 6)
&& value_range_diverges (&rvrp->vr, &prvrp->vr))
SET_BIT (bb_reg_vr_unknown[bb], i);
}
--- 4665,4672 ----
|| ! tree_int_cst_equal (&rvrp->vr.max, &prvrp->vr.max))
{
changed = 1;
! if (bb_info[bb].preds_converged
! && pass >= (bb_info[bb].preds_converged + 6)
&& value_range_diverges (&rvrp->vr, &prvrp->vr))
SET_BIT (bb_reg_vr_unknown[bb], i);
}
-------------------------------------------------------------------------
| Feith Systems | Voice: 1-215-646-8000 | Email: john@feith.com |
| John Wehle | Fax: 1-215-540-5495 | |
-------------------------------------------------------------------------