This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: Fix ICE in predictive commoning
Hi,
> > On Sat, Feb 14, 2009 at 1:43 PM, Joseph S. Myers
> > <joseph@codesourcery.com> wrote:
> > > This patch fixes an ICE in predictive commoning seen on
> > > arm-none-linux-gnueabi. (I do not know why it is target-dependent.)
> > >
> > > The ICE arises from simple_iv being passed a NULL statement from
> > > first_stmt (loop->header) called in ref_at_iteration, because the
> > > block loop->header is empty. In the 087t.loopinit dump we have
> > >
> > > ;; Loop 1
> > > ;; header 4, latch 12
> > >
> > > with nonempty block 4, but the next dump (088t.copyprop4) has empty
> > > block 4, and this persists through the 089t.dceloop1 and 090t.lim
> > > dumps before leading to the ICE.
> > >
> > > As far as I can tell it's valid for basic blocks to be empty, so this
> > > patch (which should only affect cases that previously ICEd) makes this
> > > code pass from an empty block to its successor as many times as
> > > needed. Tested with no regressions with cross to
> > > arm-none-linux-gnueabi. OK to commit?
> >
> > I'll defer to Zdenek for this particular patch, but a patch just
> > returning NULL_TREE
> > for the empty block case is pre-approved for 4.4.
>
> I think the right solution would be to modify simple_iv to take a basic
> block (or loop), not a statement, as an argument (currently, we use
> only bb_for_stmt (stmt)->loop_father there, anyway). I will prepare
> a patch,
here it is, bootstrapped & regtested on i686. I am not sure whether the patch is
appropriate for the current stage, I will defer the decision to you,
Zdenek
* tree-scalar-evolution.c (analyze_scalar_evolution_in_loop):
Extend comments.
(simple_iv): Take loop as an argument instead of statement.
* tree-scalar-evolution.h (simple_iv): Declaration changed.
* tree-ssa-loop-niter.c (number_of_iterations_exit): Update calls
to simple_iv.
* tree-ssa-loop-ivopts.c (determine_biv_step, find_givs_in_stmt_scev):
Ditto.
* tree-parloops.c (loop_parallel_p, canonicalize_loop_ivs): Ditto.
* matrix-reorg.c (analyze_transpose): Ditto.
* tree-data-ref.c (dr_analyze_innermost): Ditto.
* tree-vect-analyze.c (vect_analyze_data_refs): Ditto.
* tree-predcom.c (ref_at_iteration): Ditto.
* tree-ssa-loop-prefetch.c (idx_analyze_ref): Ditto.
Index: tree-ssa-loop-niter.c
===================================================================
*** tree-ssa-loop-niter.c (revision 144375)
--- tree-ssa-loop-niter.c (working copy)
*************** number_of_iterations_exit (struct loop *
*** 1781,1789 ****
&& !POINTER_TYPE_P (type))
return false;
! if (!simple_iv (loop, stmt, op0, &iv0, false))
return false;
! if (!simple_iv (loop, stmt, op1, &iv1, false))
return false;
/* We don't want to see undefined signed overflow warnings while
--- 1781,1789 ----
&& !POINTER_TYPE_P (type))
return false;
! if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, false))
return false;
! if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, false))
return false;
/* We don't want to see undefined signed overflow warnings while
Index: tree-scalar-evolution.c
===================================================================
*** tree-scalar-evolution.c (revision 144375)
--- tree-scalar-evolution.c (working copy)
*************** analyze_scalar_evolution (struct loop *l
*** 1915,1926 ****
}
/* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
! WRTO_LOOP (which should be a superloop of both USE_LOOP and definition
! of VERSION).
FOLDED_CASTS is set to true if resolve_mixers used
chrec_convert_aggressive (TODO -- not really, we are way too conservative
! at the moment in order to keep things simple). */
static tree
analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
--- 1915,1968 ----
}
/* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
! WRTO_LOOP (which should be a superloop of USE_LOOP)
FOLDED_CASTS is set to true if resolve_mixers used
chrec_convert_aggressive (TODO -- not really, we are way too conservative
! at the moment in order to keep things simple).
!
! To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
! example:
!
! for (i = 0; i < 100; i++) -- loop 1
! {
! for (j = 0; j < 100; j++) -- loop 2
! {
! k1 = i;
! k2 = j;
!
! use2 (k1, k2);
!
! for (t = 0; t < 100; t++) -- loop 3
! use3 (k1, k2);
!
! }
! use1 (k1, k2);
! }
!
! Both k1 and k2 are invariants in loop3, thus
! analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
! analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
!
! As they are invariant, it does not matter whether we consider their
! usage in loop 3 or loop 2, hence
! analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
! analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
! analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
! analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
!
! Similarly for their evolutions with respect to loop 1. The values of K2
! in the use in loop 2 vary independently on loop 1, thus we cannot express
! the evolution with respect to loop 1:
! analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
! analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
! analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
! analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
!
! The value of k2 in the use in loop 1 is known, though:
! analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
! analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
! */
static tree
analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
*************** analyze_scalar_evolution_in_loop (struct
*** 1929,1934 ****
--- 1971,1995 ----
bool val = false;
tree ev = version, tmp;
+ /* We cannot just do
+
+ tmp = analyze_scalar_evolution (use_loop, version);
+ ev = resolve_mixers (wrto_loop, tmp);
+
+ as resolve_mixers would query the scalar evolution with respect to
+ wrto_loop. For example, in the situation described in the function
+ comment, suppose that wrto_loop = loop1, use_loop = loop3 and
+ version = k2. Then
+
+ analyze_scalar_evolution (use_loop, version) = k2
+
+ and resolve_mixers (loop1, k2) finds that the value of k2 in loop 1
+ is 100, which is a wrong result, since we are interested in the
+ value in loop 3.
+
+ Instead, we need to proceed from use_loop to wrto_loop loop by loop,
+ each time checking that there is no evolution in the inner loop. */
+
if (folded_casts)
*folded_casts = false;
while (1)
*************** scev_reset (void)
*** 2743,2759 ****
}
}
! /* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns
! its base and step in IV if possible. If ALLOW_NONCONSTANT_STEP is true, we
! want step to be invariant in LOOP. Otherwise we require it to be an
! integer constant. IV->no_overflow is set to true if we are sure the iv cannot
! overflow (e.g. because it is computed in signed arithmetics). */
bool
! simple_iv (struct loop *loop, gimple stmt, tree op, affine_iv *iv,
! bool allow_nonconstant_step)
{
- basic_block bb = gimple_bb (stmt);
tree type, ev;
bool folded_casts;
--- 2804,2834 ----
}
}
! /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
! respect to WRTO_LOOP and returns its base and step in IV if possible
! (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
! and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
! invariant in LOOP. Otherwise we require it to be an integer constant.
!
! IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
! because it is computed in signed arithmetics). Consequently, adding an
! induction variable
!
! for (i = IV->base; ; i += IV->step)
!
! is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
! false for the type of the induction variable, or you can prove that i does
! not wrap by some other argument. Otherwise, this might introduce undefined
! behavior, and
!
! for (i = iv->base; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
!
! must be used instead. */
bool
! simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op,
! affine_iv *iv, bool allow_nonconstant_step)
{
tree type, ev;
bool folded_casts;
*************** simple_iv (struct loop *loop, gimple stm
*** 2766,2778 ****
&& TREE_CODE (type) != POINTER_TYPE)
return false;
! ev = analyze_scalar_evolution_in_loop (loop, bb->loop_father, op,
&folded_casts);
! if (chrec_contains_undetermined (ev))
return false;
! if (tree_does_not_contain_chrecs (ev)
! && !chrec_contains_symbols_defined_in_loop (ev, loop->num))
{
iv->base = ev;
iv->step = build_int_cst (TREE_TYPE (ev), 0);
--- 2841,2853 ----
&& TREE_CODE (type) != POINTER_TYPE)
return false;
! ev = analyze_scalar_evolution_in_loop (wrto_loop, use_loop, op,
&folded_casts);
! if (chrec_contains_undetermined (ev)
! || chrec_contains_symbols_defined_in_loop (ev, wrto_loop->num))
return false;
! if (tree_does_not_contain_chrecs (ev))
{
iv->base = ev;
iv->step = build_int_cst (TREE_TYPE (ev), 0);
*************** simple_iv (struct loop *loop, gimple stm
*** 2781,2802 ****
}
if (TREE_CODE (ev) != POLYNOMIAL_CHREC
! || CHREC_VARIABLE (ev) != (unsigned) loop->num)
return false;
iv->step = CHREC_RIGHT (ev);
! if (allow_nonconstant_step)
! {
! if (tree_contains_chrecs (iv->step, NULL)
! || chrec_contains_symbols_defined_in_loop (iv->step, loop->num))
! return false;
! }
! else if (TREE_CODE (iv->step) != INTEGER_CST)
return false;
iv->base = CHREC_LEFT (ev);
! if (tree_contains_chrecs (iv->base, NULL)
! || chrec_contains_symbols_defined_in_loop (iv->base, loop->num))
return false;
iv->no_overflow = !folded_casts && TYPE_OVERFLOW_UNDEFINED (type);
--- 2856,2871 ----
}
if (TREE_CODE (ev) != POLYNOMIAL_CHREC
! || CHREC_VARIABLE (ev) != (unsigned) wrto_loop->num)
return false;
iv->step = CHREC_RIGHT (ev);
! if ((!allow_nonconstant_step && TREE_CODE (iv->step) != INTEGER_CST)
! || tree_contains_chrecs (iv->step, NULL))
return false;
iv->base = CHREC_LEFT (ev);
! if (tree_contains_chrecs (iv->base, NULL))
return false;
iv->no_overflow = !folded_casts && TYPE_OVERFLOW_UNDEFINED (type);
Index: tree-scalar-evolution.h
===================================================================
*** tree-scalar-evolution.h (revision 144375)
--- tree-scalar-evolution.h (working copy)
*************** extern void scev_analysis (void);
*** 36,42 ****
unsigned int scev_const_prop (void);
bool expression_expensive_p (tree);
! extern bool simple_iv (struct loop *, gimple, tree, affine_iv *, bool);
/* Returns the basic block preceding LOOP or ENTRY_BLOCK_PTR when the
loop is function's body. */
--- 36,42 ----
unsigned int scev_const_prop (void);
bool expression_expensive_p (tree);
! extern bool simple_iv (struct loop *, struct loop *, tree, affine_iv *, bool);
/* Returns the basic block preceding LOOP or ENTRY_BLOCK_PTR when the
loop is function's body. */
Index: tree-ssa-loop-ivopts.c
===================================================================
*** tree-ssa-loop-ivopts.c (revision 144375)
--- tree-ssa-loop-ivopts.c (working copy)
*************** determine_biv_step (gimple phi)
*** 884,890 ****
if (!is_gimple_reg (name))
return NULL_TREE;
! if (!simple_iv (loop, phi, name, &iv, true))
return NULL_TREE;
return integer_zerop (iv.step) ? NULL_TREE : iv.step;
--- 884,890 ----
if (!is_gimple_reg (name))
return NULL_TREE;
! if (!simple_iv (loop, loop, name, &iv, true))
return NULL_TREE;
return integer_zerop (iv.step) ? NULL_TREE : iv.step;
*************** find_givs_in_stmt_scev (struct ivopts_da
*** 990,996 ****
if (TREE_CODE (lhs) != SSA_NAME)
return false;
! if (!simple_iv (loop, stmt, lhs, iv, true))
return false;
iv->base = expand_simple_operations (iv->base);
--- 990,996 ----
if (TREE_CODE (lhs) != SSA_NAME)
return false;
! if (!simple_iv (loop, loop_containing_stmt (stmt), lhs, iv, true))
return false;
iv->base = expand_simple_operations (iv->base);
Index: tree-parloops.c
===================================================================
*** tree-parloops.c (revision 144375)
--- tree-parloops.c (working copy)
*************** loop_parallel_p (struct loop *loop, htab
*** 385,391 ****
tree def = PHI_RESULT (phi);
affine_iv iv;
! if (is_gimple_reg (def) && !simple_iv (loop, phi, def, &iv, true))
{
struct reduction_info *red;
--- 385,391 ----
tree def = PHI_RESULT (phi);
affine_iv iv;
! if (is_gimple_reg (def) && !simple_iv (loop, loop, def, &iv, true))
{
struct reduction_info *red;
*************** canonicalize_loop_ivs (struct loop *loop
*** 1367,1373 ****
continue;
}
! ok = simple_iv (loop, phi, res, &iv, true);
if (reduction_list)
red = reduction_phi (reduction_list, phi);
--- 1367,1373 ----
continue;
}
! ok = simple_iv (loop, loop, res, &iv, true);
if (reduction_list)
red = reduction_phi (reduction_list, phi);
Index: matrix-reorg.c
===================================================================
*** matrix-reorg.c (revision 144375)
--- matrix-reorg.c (working copy)
*************** analyze_transpose (void **slot, void *da
*** 930,936 ****
free (acc_info);
continue;
}
! if (simple_iv (loop, acc_info->stmt, acc_info->offset, &iv, true))
{
if (iv.step != NULL)
{
--- 930,936 ----
free (acc_info);
continue;
}
! if (simple_iv (loop, loop, acc_info->offset, &iv, true))
{
if (iv.step != NULL)
{
Index: tree-data-ref.c
===================================================================
*** tree-data-ref.c (revision 144375)
--- tree-data-ref.c (working copy)
*************** dr_analyze_innermost (struct data_refere
*** 698,704 ****
}
base = build_fold_addr_expr (base);
! if (!simple_iv (loop, stmt, base, &base_iv, false))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "failed: evolution of base is not affine.\n");
--- 698,704 ----
}
base = build_fold_addr_expr (base);
! if (!simple_iv (loop, loop_containing_stmt (stmt), base, &base_iv, false))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "failed: evolution of base is not affine.\n");
*************** dr_analyze_innermost (struct data_refere
*** 709,715 ****
offset_iv.base = ssize_int (0);
offset_iv.step = ssize_int (0);
}
! else if (!simple_iv (loop, stmt, poffset, &offset_iv, false))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "failed: evolution of offset is not affine.\n");
--- 709,716 ----
offset_iv.base = ssize_int (0);
offset_iv.step = ssize_int (0);
}
! else if (!simple_iv (loop, loop_containing_stmt (stmt),
! poffset, &offset_iv, false))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "failed: evolution of offset is not affine.\n");
Index: tree-vect-analyze.c
===================================================================
*** tree-vect-analyze.c (revision 144375)
--- tree-vect-analyze.c (working copy)
*************** vect_analyze_data_refs (loop_vec_info lo
*** 3622,3628 ****
}
outer_base = build_fold_addr_expr (outer_base);
! if (!simple_iv (loop, stmt, outer_base, &base_iv, false))
{
if (vect_print_dump_info (REPORT_DETAILS))
fprintf (vect_dump, "failed: evolution of base is not affine.\n");
--- 3622,3629 ----
}
outer_base = build_fold_addr_expr (outer_base);
! if (!simple_iv (loop, loop_containing_stmt (stmt), outer_base,
! &base_iv, false))
{
if (vect_print_dump_info (REPORT_DETAILS))
fprintf (vect_dump, "failed: evolution of base is not affine.\n");
*************** vect_analyze_data_refs (loop_vec_info lo
*** 3642,3648 ****
offset_iv.base = ssize_int (0);
offset_iv.step = ssize_int (0);
}
! else if (!simple_iv (loop, stmt, poffset, &offset_iv, false))
{
if (vect_print_dump_info (REPORT_DETAILS))
fprintf (vect_dump, "evolution of offset is not affine.\n");
--- 3643,3650 ----
offset_iv.base = ssize_int (0);
offset_iv.step = ssize_int (0);
}
! else if (!simple_iv (loop, loop_containing_stmt (stmt), poffset,
! &offset_iv, false))
{
if (vect_print_dump_info (REPORT_DETAILS))
fprintf (vect_dump, "evolution of offset is not affine.\n");
Index: tree-predcom.c
===================================================================
*** tree-predcom.c (revision 144375)
--- tree-predcom.c (working copy)
*************** ref_at_iteration (struct loop *loop, tre
*** 1374,1380 ****
else
return NULL_TREE;
! ok = simple_iv (loop, first_stmt (loop->header), idx, &iv, true);
if (!ok)
return NULL_TREE;
iv.base = expand_simple_operations (iv.base);
--- 1374,1380 ----
else
return NULL_TREE;
! ok = simple_iv (loop, loop, idx, &iv, true);
if (!ok)
return NULL_TREE;
iv.base = expand_simple_operations (iv.base);
Index: tree-ssa-loop-prefetch.c
===================================================================
*** tree-ssa-loop-prefetch.c (revision 144375)
--- tree-ssa-loop-prefetch.c (working copy)
*************** idx_analyze_ref (tree base, tree *index,
*** 364,370 ****
|| TREE_CODE (base) == ALIGN_INDIRECT_REF)
return false;
! if (!simple_iv (ar_data->loop, ar_data->stmt, *index, &iv, false))
return false;
ibase = iv.base;
step = iv.step;
--- 364,371 ----
|| TREE_CODE (base) == ALIGN_INDIRECT_REF)
return false;
! if (!simple_iv (ar_data->loop, loop_containing_stmt (ar_data->stmt),
! *index, &iv, false))
return false;
ibase = iv.base;
step = iv.step;