On Wed, Nov 09, 2016 at 01:43:58PM +0100, Richard Biener wrote:
> On Tue, Nov 8, 2016 at 5:18 PM, Marc Glisse <marc.gli...@inria.fr> wrote:
> > On Tue, 8 Nov 2016, Dominik Vogt wrote:
> >
> >> On Fri, Nov 04, 2016 at 01:54:20PM +0100, Richard Biener wrote:
> >>>
> >>> On Fri, Nov 4, 2016 at 12:08 PM, Dominik Vogt <v...@linux.vnet.ibm.com>
> >>> wrote:
> >>>>
> >>>> On Fri, Nov 04, 2016 at 09:47:26AM +0100, Richard Biener wrote:
> >>>>>
> >>>>> On Thu, Nov 3, 2016 at 4:03 PM, Dominik Vogt <v...@linux.vnet.ibm.com>
> >>>>> wrote:
> >>>>>>
> >>>>>> Is VRP the right pass to do this optimisation or should a later
> >>>>>> pass rather attempt to eliminate the new use of b_5 instead? Uli
> >>>>>> has brought up the idea a mini "sign extend elimination" pass that
> >>>>>> checks if the result of a sign extend could be replaced by the
> >>>>>> original quantity in all places, and if so, eliminate the ssa
> >>>>>> name. (I guess that won't help with the above code because l is
> >>>>>> used also as a function argument.) How could a sensible approach
> >>>>>> to deal with the situation look like?
> >>>>>
> >>>>>
> >>>>> We run into this kind of situation regularly and for general foldings
> >>>>> in match.pd we settled with single_use () even though it is not
> >>>>> perfect.
> >>>>> Note the usual complaint is not extra extension instructions but
> >>>>> the increase of register pressure.
> >>>>>
> >>>>> This is because it is hard to do better when you are doing local
> >>>>> optimization.
> >>>>>
> >>>>> As for the question on whether VRP is the right pass to do this the
> >>>>> answer is two-fold -- VRP has the most precise range information.
> >>>>> But the folding itself should be moved to generic code and use
> >>>>> get_range_info ().
> >>>>
> >>>>
> >>>> All right, is this a sensible approach then?
> >>>
> >>>
> >>> Yes.
> >>>
> >>>> 1. Using has_single_use as in the experimental patch is good
> >>>> enough (provided further testing does not show serious
> >>>> regressions).
> >>>
> >>>
> >>> I'd approve that, yes.
> >>>
> >>>> 2. Rip the whole top level if-block from simplify_cond_using_ranges().
> >>>> 3. Translate that code to match.pd syntax.
> >>>
> >>>
> >>> Might be some work but yes, that's also desired (you'd lose the ability
> >>> to emit the warnings though).
> >>
> >>
> >> Could you give me a match-pd-hint please? We now have something
> >> like this:
> >>
> >> (simplify
> >> (cond (gt SSA_NAME@0 INTEGER_CST@1) @2 @3)
> >> (if (... many conditions ...)
> >> (cond (gt ... ...) @2 @3))
> >>
> >> The generated code ends up in gimple_simplify_COND_EXPR, but when
> >> gimple_simplify is actually called, it goes through the
> >> GIMPLE_COND case and calls gimple_resimplify2(..., GT, ...) and
> >> there it tries gimple_simplify_GT_EXPR(), peeling of the (cond
> >> ...), i.e. it never tries the generated code.
> >
> >
> > Not sure what you mean here.
> >
> >> There is another pattern in match.pd that uses a (cond ...) as the
> >> first operand, and I do not understand how this works. Should we
> >> just use "(gt SSA_NAME@0 INTEGER_CST@1)" as the first operand
> >> instead, and wouldn't this pattern be too general that way?
> >
> >
> > IIUC, you are trying to move the second half of simplify_cond_using_ranges
> > to match.pd. I don't see any reason to restrict it to the case where the
> > comparison result is used directly in a COND_EXPR, so that would look like:
> >
> > (for cmp (...)
> > (simplify
> > (cmp (convert SSA_NAME@0) INTEGER_CST@1)
> > (if (...)
> > (cmp @0 (convert @1)))))
> >
> > maybe? I think I may have missed your point.
>
> Yeah, if you'd use (cond (gt ... then it only matches in assignments
> with COND_EXPRs on the RHS, _not_ in GIMPLE_CONDs.
>
> So you ran into the (cond vs. GIMPLE_COND "mismatch".
>
> You'd essentially implement sth similar to shorten_compare in match.pd.
Something like the attached patch? Robin and me have spent quite
some time to figure out the new pattern. Two questions:
1) In the match expression you cannot just use SSA_NAME@0 because
then the "case SSA_NAME:" is added to a switch for another
pattern that already has that label. Thus we made that "proxy"
predicate "ssa_name_p" that forces the code for the new pattern
out of the old switch and into a separate code block. We
couldn't figure out whether this joining of case labels is a
feature in the matching language. So, is this the right way to
deal with the conflicting labels?
2) There's an awful lot of if-clauses in the replacement
expression. Is it the right place to do all this checking?
> Btw, moving to match.pd shouldn't be a blocker for adding proper
> single_use tests
> just in case you get lost ...
Ciao
Dominik ^_^ ^_^
--
Dominik Vogt
IBM Germany
>From 26f75d777254c7e29d721c6813eca33539ac6574 Mon Sep 17 00:00:00 2001
From: Dominik Vogt <v...@linux.vnet.ibm.com>
Date: Wed, 2 Nov 2016 14:01:46 +0100
Subject: [PATCH] Convert folding in simplify_cond_using_ranges() to
match.pd.
In cases like this
ac_4 = *p_3(D);
bc_5 = ac_4 & 63;
l_6 = (long int) bc_5;
if (l_6 > 9)
bar(l_6);
the function would fold bc_5 into the condition, replacing l_6, but l_6 cannot
be eliminated. We'd end up with bc_5 being used in two places and l_6 in one
place without the chance to eliminate either.
The patched code suppresses folding if
bc_5 has only a single use (i.e. being cast to l_6),
AND
l_6 has more than one use.
However, the patch does not catch the case where all uses of l_6 could be
eliminated by the function, e.g.
...
if (l_6 > 9)
bar();
else if (l_6 > 5)
foo();
---
gcc/match.pd | 40 ++++++++++++++++++++++++++++
gcc/tree-vrp.c | 82 ++++++----------------------------------------------------
gcc/tree-vrp.h | 7 ++++-
3 files changed, 54 insertions(+), 75 deletions(-)
diff --git a/gcc/match.pd b/gcc/match.pd
index 48f7351..e2a663b 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -3501,3 +3501,43 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
{ CONSTRUCTOR_ELT (ctor, idx / k)->value; })
(BIT_FIELD_REF { CONSTRUCTOR_ELT (ctor, idx / k)->value; }
@1 { bitsize_int ((idx % k) * width); })))))))))
+
+/* If we have a comparison of an SSA_NAME (OP0) against a constant,
+ see if OP0 was set by a type conversion where the source of
+ the conversion is another SSA_NAME with a range that fits
+ into the range of OP0's type.
+
+ If so, the conversion is redundant as the earlier SSA_NAME can be
+ used for the comparison directly if we just massage the constant in the
+ comparison. */
+
+(match ssa_name_p SSA_NAME)
+(for cmp (eq ne gt ge lt le)
+ (simplify
+ (cmp ssa_name_p@0 INTEGER_CST@1)
+ (with { gimple *def_stmt = SSA_NAME_DEF_STMT (@0); }
+ (if (is_gimple_assign (def_stmt)
+ && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
+ (with { tree innerop = gimple_assign_rhs1 (def_stmt); }
+ (if (TREE_CODE (innerop) == SSA_NAME
+ && !POINTER_TYPE_P (TREE_TYPE (innerop))
+ && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop)
+ && desired_pro_or_demotion_p (TREE_TYPE (innerop), TREE_TYPE (@0)))
+ (with { value_range *vr = get_value_range (innerop); }
+ (if (vr
+ && range_int_cst_p (vr)
+ && range_fits_type_p (vr,
+ TYPE_PRECISION (TREE_TYPE (@0)),
+ TYPE_SIGN (TREE_TYPE (@0)))
+ && int_fits_type_p (@1, TREE_TYPE (innerop))
+ /* The range must not have overflowed, or if it did overflow we
+ must not be wrapping/trapping overflow and optimizing with
+ strict overflow semantics. */
+ && ((!is_negative_overflow_infinity (vr->min)
+ && !is_positive_overflow_infinity (vr->max))
+ || TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (innerop)))
+ /* If the only use of INNEROP is the cast to @0, and @0 is also
+ used in other places, folding would introduce new uses of the
+ otherwise dead INNEROP without eliminating @0, so do not. */
+ && (!has_single_use (innerop) || has_single_use (@0)))
+ (cmp { innerop; } (convert @1))))))))))
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 68fe2ac..1b128e2 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -259,7 +259,7 @@ positive_overflow_infinity (tree type)
/* Return whether VAL is a negative overflow infinity. */
-static inline bool
+bool
is_negative_overflow_infinity (const_tree val)
{
return (TREE_OVERFLOW_P (val)
@@ -269,7 +269,7 @@ is_negative_overflow_infinity (const_tree val)
/* Return whether VAL is a positive overflow infinity. */
-static inline bool
+bool
is_positive_overflow_infinity (const_tree val)
{
return (TREE_OVERFLOW_P (val)
@@ -640,7 +640,7 @@ abs_extent_range (value_range *vr, tree min, tree max)
If we have no values ranges recorded (ie, VRP is not running), then
return NULL. Otherwise create an empty range if none existed for VAR. */
-static value_range *
+value_range *
get_value_range (const_tree var)
{
static const value_range vr_const_varying
@@ -877,7 +877,7 @@ range_is_null (value_range *vr)
/* Return true if max and min of VR are INTEGER_CST. It's not necessary
a singleton. */
-static inline bool
+bool
range_int_cst_p (value_range *vr)
{
return (vr->type == VR_RANGE
@@ -9432,7 +9432,7 @@ test_for_singularity (enum tree_code cond_code, tree op0,
/* Return whether the value range *VR fits in an integer type specified
by PRECISION and UNSIGNED_P. */
-static bool
+bool
range_fits_type_p (value_range *vr, unsigned dest_precision, signop dest_sgn)
{
tree src_type;
@@ -9486,7 +9486,7 @@ range_fits_type_p (value_range *vr, unsigned
dest_precision, signop dest_sgn)
the original conditional. */
static bool
-simplify_cond_using_ranges (gcond *stmt)
+simplify_cond_using_ranges (gimple_stmt_iterator *gsi, gcond *stmt)
{
tree op0 = gimple_cond_lhs (stmt);
tree op1 = gimple_cond_rhs (stmt);
@@ -9590,73 +9590,7 @@ simplify_cond_using_ranges (gcond *stmt)
}
}
- /* If we have a comparison of an SSA_NAME (OP0) against a constant,
- see if OP0 was set by a type conversion where the source of
- the conversion is another SSA_NAME with a range that fits
- into the range of OP0's type.
-
- If so, the conversion is redundant as the earlier SSA_NAME can be
- used for the comparison directly if we just massage the constant in the
- comparison. */
- if (TREE_CODE (op0) == SSA_NAME
- && TREE_CODE (op1) == INTEGER_CST)
- {
- gimple *def_stmt = SSA_NAME_DEF_STMT (op0);
- tree innerop;
-
- if (!is_gimple_assign (def_stmt)
- || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
- return false;
-
- innerop = gimple_assign_rhs1 (def_stmt);
-
- if (TREE_CODE (innerop) == SSA_NAME
- && !POINTER_TYPE_P (TREE_TYPE (innerop))
- && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop)
- && desired_pro_or_demotion_p (TREE_TYPE (innerop), TREE_TYPE (op0)))
- {
- value_range *vr = get_value_range (innerop);
-
- if (range_int_cst_p (vr)
- && range_fits_type_p (vr,
- TYPE_PRECISION (TREE_TYPE (op0)),
- TYPE_SIGN (TREE_TYPE (op0)))
- && int_fits_type_p (op1, TREE_TYPE (innerop))
- /* The range must not have overflowed, or if it did overflow
- we must not be wrapping/trapping overflow and optimizing
- with strict overflow semantics. */
- && ((!is_negative_overflow_infinity (vr->min)
- && !is_positive_overflow_infinity (vr->max))
- || TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (innerop))))
- {
- /* If the range overflowed and the user has asked for warnings
- when strict overflow semantics were used to optimize code,
- issue an appropriate warning. */
- if (cond_code != EQ_EXPR && cond_code != NE_EXPR
- && (is_negative_overflow_infinity (vr->min)
- || is_positive_overflow_infinity (vr->max))
- && issue_strict_overflow_warning
(WARN_STRICT_OVERFLOW_CONDITIONAL))
- {
- location_t location;
-
- if (!gimple_has_location (stmt))
- location = input_location;
- else
- location = gimple_location (stmt);
- warning_at (location, OPT_Wstrict_overflow,
- "assuming signed overflow does not occur when "
- "simplifying conditional");
- }
-
- tree newconst = fold_convert (TREE_TYPE (innerop), op1);
- gimple_cond_set_lhs (stmt, innerop);
- gimple_cond_set_rhs (stmt, newconst);
- return true;
- }
- }
- }
-
- return false;
+ return fold_stmt (gsi, follow_single_use_edges);
}
/* Simplify a switch statement using the value range of the switch
@@ -10250,7 +10184,7 @@ simplify_stmt_using_ranges (gimple_stmt_iterator *gsi)
}
}
else if (gimple_code (stmt) == GIMPLE_COND)
- return simplify_cond_using_ranges (as_a <gcond *> (stmt));
+ return simplify_cond_using_ranges (gsi, as_a <gcond *> (stmt));
else if (gimple_code (stmt) == GIMPLE_SWITCH)
return simplify_switch_using_ranges (as_a <gswitch *> (stmt));
else if (is_gimple_call (stmt)
diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h
index 5cea709..38cd1be 100644
--- a/gcc/tree-vrp.h
+++ b/gcc/tree-vrp.h
@@ -56,4 +56,9 @@ extern void extract_range_from_unary_expr (value_range *vr,
tree type,
value_range *vr0_,
tree op0_type);
-
+extern value_range *get_value_range (const_tree var);
+extern bool range_fits_type_p (value_range *vr, unsigned dest_precision,
+ signop dest_sgn);
+extern bool is_negative_overflow_infinity (const_tree val);
+extern bool is_positive_overflow_infinity (const_tree val);
+extern bool range_int_cst_p (value_range *vr);
--
2.3.0
