From patchwork Wed Nov 9 14:30:53 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dominik Vogt X-Patchwork-Id: 692802 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 3tDTBl33tZz9tlW for ; Thu, 10 Nov 2016 01:31:26 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="tAgZ73V9"; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:cc:subject:reply-to:references:mime-version :content-type:in-reply-to:message-id; q=dns; s=default; b=b31VxX KOslsIUE3+ThqqeD1x3X5eCEnLUrniWaPeYzcxJFCthxUlAIgLdIb1ReyyPShau2 ikfhhLtG4nRFvzoMNfPkTEr50WylUrNnUuXqIpj4xj+gwzz0HIVcKjKqnhDSbrUd h41549Xau52QSLeTjul1ppuKDCFP1K2Kb8XSU= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:cc:subject:reply-to:references:mime-version :content-type:in-reply-to:message-id; s=default; bh=TnovB4tKrgFE mGZSxFqJ86V3xMo=; b=tAgZ73V95K1EEnm2S5e5uNxktxDISbuDYTrbbjy+S92R 0xyrMIduunHsRHkZ9R5fhG6k+hqq6dY2D6xKMEg2fvzMDG+Kmamt32m3NYdM1r6r my+rERvjk0G069s7Bu6sftKReLf6ZU3GUKiK1a0Tb9FUIvsnWk/1Anxommc4UWc= Received: (qmail 46437 invoked by alias); 9 Nov 2016 14:31:15 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 46374 invoked by uid 89); 9 Nov 2016 14:31:15 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-0.3 required=5.0 tests=AWL, BAYES_05, KAM_LAZY_DOMAIN_SECURITY, RCVD_IN_DNSWL_LOW autolearn=no version=3.3.2 spammy=robin, Robin, blocker, ciao X-HELO: mx0a-001b2d01.pphosted.com Received: from mx0b-001b2d01.pphosted.com (HELO mx0a-001b2d01.pphosted.com) (148.163.158.5) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 09 Nov 2016 14:31:04 +0000 Received: from pps.filterd (m0098417.ppops.net [127.0.0.1]) by mx0a-001b2d01.pphosted.com (8.16.0.17/8.16.0.17) with SMTP id uA9ESntQ144723 for ; Wed, 9 Nov 2016 09:31:01 -0500 Received: from e06smtp13.uk.ibm.com (e06smtp13.uk.ibm.com [195.75.94.109]) by mx0a-001b2d01.pphosted.com with ESMTP id 26m2kkpt5c-1 (version=TLSv1.2 cipher=AES256-SHA bits=256 verify=NOT) for ; Wed, 09 Nov 2016 09:31:01 -0500 Received: from localhost by e06smtp13.uk.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Wed, 9 Nov 2016 14:30:56 -0000 Received: from d06dlp02.portsmouth.uk.ibm.com (9.149.20.14) by e06smtp13.uk.ibm.com (192.168.101.143) with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted; Wed, 9 Nov 2016 14:30:54 -0000 Received: from b06cxnps4076.portsmouth.uk.ibm.com (d06relay13.portsmouth.uk.ibm.com [9.149.109.198]) by d06dlp02.portsmouth.uk.ibm.com (Postfix) with ESMTP id 3973F219005E for ; Wed, 9 Nov 2016 14:30:08 +0000 (GMT) Received: from d06av05.portsmouth.uk.ibm.com (d06av05.portsmouth.uk.ibm.com [9.149.37.229]) by b06cxnps4076.portsmouth.uk.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id uA9EUsCP14418216 for ; Wed, 9 Nov 2016 14:30:54 GMT Received: from d06av05.portsmouth.uk.ibm.com (localhost [127.0.0.1]) by d06av05.portsmouth.uk.ibm.com (8.14.4/8.14.4/NCO v10.0 AVout) with ESMTP id uA9EUr2V024479 for ; Wed, 9 Nov 2016 07:30:53 -0700 Received: from oc5510024614.ibm.com (dyn-9-152-224-33.boeblingen.de.ibm.com [9.152.224.33]) by d06av05.portsmouth.uk.ibm.com (8.14.4/8.14.4/NCO v10.0 AVin) with ESMTP id uA9EUrqP024476; Wed, 9 Nov 2016 07:30:53 -0700 Received: by oc5510024614.ibm.com (Postfix, from userid 500) id 5CDC817E7B; Wed, 9 Nov 2016 15:30:53 +0100 (CET) Date: Wed, 9 Nov 2016 15:30:53 +0100 From: Dominik Vogt To: Richard Biener Cc: GCC Patches , Ulrich Weigand , Andreas Krebbel Subject: Re: [RFC] Check number of uses in simplify_cond_using_ranges(). Reply-To: vogt@linux.vnet.ibm.com Mail-Followup-To: vogt@linux.vnet.ibm.com, Richard Biener , GCC Patches , Ulrich Weigand , Andreas Krebbel References: <20161103150322.GA3523@linux.vnet.ibm.com> <20161104110822.GA23310@linux.vnet.ibm.com> <20161108143125.GA16341@linux.vnet.ibm.com> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.20 (2009-12-10) X-TM-AS-MML: disable X-Content-Scanned: Fidelis XPS MAILER x-cbid: 16110914-0012-0000-0000-00000487D925 X-IBM-AV-DETECTION: SAVI=unused REMOTE=unused XFE=unused x-cbparentid: 16110914-0013-0000-0000-00001625E2B6 Message-Id: <20161109143053.GA21900@linux.vnet.ibm.com> X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10432:, , definitions=2016-11-09_06:, , signatures=0 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 spamscore=0 suspectscore=0 malwarescore=0 phishscore=0 adultscore=0 bulkscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.0.1-1609300000 definitions=main-1611090271 On Wed, Nov 09, 2016 at 01:43:58PM +0100, Richard Biener wrote: > On Tue, Nov 8, 2016 at 5:18 PM, Marc Glisse 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 > >>> 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 > >>>>> 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 ^_^ ^_^ 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 (stmt)); + return simplify_cond_using_ranges (gsi, as_a (stmt)); else if (gimple_code (stmt) == GIMPLE_SWITCH) return simplify_switch_using_ranges (as_a (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);