Zdenek Dvorak - Re: [patch] (-fstrict-overflow) optimize counted loops on signed iv (original) (raw)

This is the mail archive of the gcc-patches@gcc.gnu.orgmailing list for the GCC project.

• From: Zdenek Dvorak
• To: Christian BRUEL
• Cc: Ian Lance Taylor , Richard Guenther , gcc-patches at gcc dot gnu dot org
• Date: Thu, 15 Feb 2007 10:33:43 +0100
• Subject: Re: [patch] (-fstrict-overflow) optimize counted loops on signed iv
• References: <45D42560.2010506@st.com>

Hello,

This allows to optimize loops like : for (i = start; i <= start+1; i++) ...

•  niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node,

•            iv1->base, iv0->base);

I sort of do not understand why you need this change. fold is (or should be) able to derive that start < start + 1, if the computation is performed in TYPE_OVERFLOW_UNDEFINED type.

Index: gcc/tree-ssa-loop-niter.c

--- gcc/tree-ssa-loop-niter.c (.../vendor/tags/4.3.20070209) (revision 77) +++ gcc/tree-ssa-loop-niter.c (.../branches/4.3_devs_loop_overflow) (revision 77) @@ -169,6 +169,80 @@ return true; }

+/* Checks whether the number of iterations is a constant value if iv1 is relative

• to iv0. If we are allowed to optimize overflows, it may be a constant when the
• control variable wraps.
• iv0 is the chrec for the initial value of the control variable.
• iv1 is the chrec for the stop value.
• Optimizes loops like (i = v; i <= v+cst; i++). */
• +static bool +relative_count_iv (affine_iv *iv0, affine_iv *iv1) +{
• enum tree_code code_base0;
• enum tree_code code_base1;
• tree op0 = iv0->base;
• tree op1 = iv1->base;
• if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (op0))

•  || !TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (op1)))

• return false;
• STRIP_SIGN_NOPS (op0);
• STRIP_SIGN_NOPS (op1);
• code_base0 = TREE_CODE (op0);
• code_base1 = TREE_CODE (op1);
• /* iv0 -> {a+cst, +/-, cst}, iv1 -> {a+cst, +/-, cst}. */
• if ((code_base0 == PLUS_EXPR && code_base1 == PLUS_EXPR)

•  || (code_base0 == MINUS_EXPR && code_base1 == MINUS_EXPR))

• {

•  tree opb0 = TREE_OPERAND (op0, 0);

•  tree opb1 = TREE_OPERAND (op1, 0);

•  STRIP_SIGN_NOPS (opb0);

•  STRIP_SIGN_NOPS (opb1);

•  if (TREE_CODE (opb0) == SSA_NAME && TREE_CODE (opb1) == SSA_NAME

•  && SSA_NAME_DEF_STMT(opb0) == SSA_NAME_DEF_STMT(opb1)

you want to check opb0 == opb1, here. Or more likely, not to check that opb0 and opb1 are ssa names, and just use operand_equal_p

•  && TREE_CONSTANT (TREE_OPERAND (op0, 1))

•  && TREE_CONSTANT (TREE_OPERAND (op1, 1)))

• return true;

/* Checks whether we can determine the final value of the control variable of the loop with ending condition IV0 < IV1 (computed in TYPE). DELTA is the difference IV1->base - IV0->base, STEP is the absolute value @@ -236,7 +310,8 @@ niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, niter->assumptions, assumption);

• if (!integer_zerop (noloop))

• if (!integer_zerop (noloop) && !relative_count_iv (iv0, iv1)) niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, niter->may_be_zero, noloop);

@@ -367,7 +442,8 @@ if (!integer_nonzerop (assumption)) niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, niter->assumptions, assumption);

• if (!integer_zerop (mbz))

• if (!integer_zerop (mbz) && !relative_count_iv (iv0, iv1)) niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, niter->may_be_zero, mbz);

} @@ -413,8 +489,9 @@

  In both cases # of iterations is iv1->base - iv0->base, assuming that
  iv1->base >= iv0->base.  */

•  niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node,

•            iv1->base, iv0->base);

•  if (!relative_count_iv (iv0, iv1))

• niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node,

•              iv1->base, iv0->base);
    niter->niter = delta;
    return true;
  }

Nevertheless, this looks just wrong. relative_count_iv does not compare the relative values of the bases of the induction variables, hence this would also make you eliminate the the may_be_zero assumptions in cases like

for (i = a + 17; i < a + 5; i++)

which is obviously wrong.

Zdenek

• Follow-Ups:
  • Re: [patch] (-fstrict-overflow) optimize counted loops on signed iv
    * From: Christian BRUEL
• References:
  • Re: [patch] (-fstrict-overflow) optimize counted loops on signed iv
    * From: Christian BRUEL