From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id 8428138582B4 for ; Wed, 15 Jun 2022 13:29:20 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 8428138582B4 Received: from mail-qk1-f200.google.com (mail-qk1-f200.google.com [209.85.222.200]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-208-ShP-bfA_O06GY_Ex69996A-1; Wed, 15 Jun 2022 09:29:19 -0400 X-MC-Unique: ShP-bfA_O06GY_Ex69996A-1 Received: by mail-qk1-f200.google.com with SMTP id bj2-20020a05620a190200b005084968bb24so9996335qkb.23 for ; Wed, 15 Jun 2022 06:29:19 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:date:mime-version:user-agent:subject :content-language:to:cc:references:from:in-reply-to :content-transfer-encoding; bh=/nO8Re5R2cflz+CfHf555duAZptrEYw/t9Kg6uwLL1k=; b=a1OFPDxKDOvNQajRYmNBGwxAukqyHl63SGvhYlRsumWljTnS5J+PPiV6Ja67ojoYnR 8KVnb87r62yTddvG3rhP21Ii0+L2X/TIxER6iBNDSw+0HLRotT6hEPYc7nfXk61rd+0O 0MzZpNlp4El0oXXTnhDLqwWGpX2y6ajyNYvPerFrWJv9eKQWkci+v5LuqNpzlrGZgaBE tcvO4R8bxa2jzFhySqi+3Sc2Ntc1zKUjD5uKyaGhJ8bhQVWCHv8rWqDTZQoWzzuifLJ0 gCwvi/9JhIbHwGux/QVFGCCrUarB42y9q7v+UciANibi8fXwwjKujAjZqo987AOeTf6D OqLA== X-Gm-Message-State: AOAM532hve+1u5Gvv4bgzZp77X7dyMwxTnYko33U5PKp8z0CWDwOHkEV TPMyGHjXopDknxLUZN8ndPE/9OSGLOFATRfdjAfpdkM97ifoGchrMfZRrIu4L4FkAN2mgcHz6kM TogFE6ESLx6FW2QphRg== X-Received: by 2002:a05:622a:4c9:b0:306:6959:e1d3 with SMTP id q9-20020a05622a04c900b003066959e1d3mr6059462qtx.680.1655299758539; Wed, 15 Jun 2022 06:29:18 -0700 (PDT) X-Google-Smtp-Source: ABdhPJxI9hTlfMWHTexfXtC5tRC0aHmGeqNDWsCPTDIcQBFd2IsFpyKSSrzQuMprTAOCvbRMa+YF8w== X-Received: by 2002:a05:622a:4c9:b0:306:6959:e1d3 with SMTP id q9-20020a05622a04c900b003066959e1d3mr6059448qtx.680.1655299758304; Wed, 15 Jun 2022 06:29:18 -0700 (PDT) Received: from ?IPV6:2607:fea8:a261:5e00::b58? ([2607:fea8:a261:5e00::b58]) by smtp.gmail.com with ESMTPSA id w12-20020ac86b0c000000b00304fe96c7aasm9382590qts.24.2022.06.15.06.29.15 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 15 Jun 2022 06:29:16 -0700 (PDT) Message-ID: <76123da2-8fdb-d188-8dfc-a0972a218709@redhat.com> Date: Wed, 15 Jun 2022 09:29:14 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.10.0 Subject: Re: [PATCH] Simplify (B * v + C) * D -> BD* v + CD when B, C, D are all INTEGER_CST. To: Richard Biener , liuhongt Cc: GCC Patches References: <20220607075431.24764-1-hongtao.liu@intel.com> From: Andrew MacLeod In-Reply-To: X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-CA Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-12.8 required=5.0 tests=BAYES_00, BODY_8BITS, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, NICE_REPLY_A, RCVD_IN_DNSWL_LOW, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 15 Jun 2022 13:29:22 -0000 On 6/15/22 04:24, Richard Biener wrote: > >> diff --git a/gcc/match.pd b/gcc/match.pd >> index 44a385b912d..54f53a1f988 100644 >> --- a/gcc/match.pd >> +++ b/gcc/match.pd >> @@ -489,6 +489,88 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) >> (if (!overflow || TYPE_OVERFLOW_WRAPS (type)) >> (mult @0 { wide_int_to_tree (type, mul); })))) >> >> +/* Similar to above, but there could be an extra add/sub between >> + successive multuiplications. */ >> +(simplify >> + (mult (plus:s (mult:s@4 @0 INTEGER_CST@1) INTEGER_CST@2) INTEGER_CST@3) >> + (with { >> + bool overflowed = true; >> + wi::overflow_type ovf1, ovf2; >> + wide_int mul = wi::mul (wi::to_wide (@1), wi::to_wide (@3), >> + TYPE_SIGN (type), &ovf1); >> + wide_int add = wi::mul (wi::to_wide (@2), wi::to_wide (@3), >> + TYPE_SIGN (type), &ovf2); >> + if (TYPE_OVERFLOW_UNDEFINED (type)) >> + { >> +#if GIMPLE >> + value_range vr0; >> + if (ovf1 == wi::OVF_NONE && ovf2 == wi::OVF_NONE >> + && get_global_range_query ()->range_of_expr (vr0, @4) >> + && vr0.kind () == VR_RANGE) >> + { >> + wide_int wmin0 = vr0.lower_bound (); >> + wide_int wmax0 = vr0.upper_bound (); >> + wmin0 = wi::mul (wmin0, wi::to_wide (@3), TYPE_SIGN (type), &ovf1); >> + wmax0 = wi::mul (wmax0, wi::to_wide (@3), TYPE_SIGN (type), &ovf2); >> + if (ovf1 == wi::OVF_NONE && ovf2 == wi::OVF_NONE) >> + { >> + wi::add (wmin0, add, TYPE_SIGN (type), &ovf1); >> + wi::add (wmax0, add, TYPE_SIGN (type), &ovf2); >> + if (ovf1 == wi::OVF_NONE && ovf2 == wi::OVF_NONE) >> + overflowed = false; > I wonder if we have an API available for these kind of queries already? > Possibly value_range expr_range (MULT_EXPR, vr0, vr1, &ovf), > computing the result range of the operation on ranges vr0 and vr1 > indicating overflow behavior in 'ovf' (similar as to the wide_int APIs)? > > Andrew? > > I see match.pd already has similar code in a few places. The overflow characteristic is currently "hidden" in the API. ie, you can do   range_op_handler (MULT_EXPR, type).fold_range (r, type, vr0, vr1); and get the result in 'r', which typcically if it overflows for MULT is varying I think.  (we give up easily :-)  BUt the fact than an overflow may have happened is not explicitly provided. If this was something generally useful, we could consider adding an optional flag to the API which indicates is an overflow may happen.  Then you'd have something like:   range_op_handler (MULT_EXPR, type).fold_range (r, type, vr0, vr1, &ovf); The original range-ops implementation way back when did carry an overflow around, but it was removed early on.  Someone would have to go in and tweak all the fold_range routines to set the flag correctly, if it was passed in. If its going to work for one it would have to work for all. I do believe the information is all contained in every relevant range-op routine, we just don't propagate it back to the caller. Most of the "generic" routines have a wi_op_overflows () method which determines whether any pair of wide-ints overflow the operation, we'd just have to return the  flag in those cases.  The rest of the cases would have to be audited. And in todays multi-type environment, we'd have to handle it for the other types as well.. so an integer specific value like wi::OVF_*  may not be appropriate.   Perhaps just a boolean flag indicating if the result is an accurate calculation, or integrates possibly out of range values. Andrew PS.  We could also simplify the API slightly for general consumption via the gimple-range-fold.h routines. they currently support just gimple statements:      bool fold_range (vrange &r, gimple *s, vrange &r1, vrange &r2); but we could probably also manage something like:     bool fold_range (vrange &r, MULT_EXPR, vrange &r1, vrange &r2); where we key off the types of r1 and r2 when possible... and return false otherwise.   Then if we have extended the range-ops API to include an overflow, we could attach it here too. Andrew