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.129.124]) by sourceware.org (Postfix) with ESMTPS id 1BFC13858D38 for ; Mon, 17 Jul 2023 17:24:12 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 1BFC13858D38 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1689614651; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=qJz+dufdhYit+sBjYVhC9iljlpjpWwRas6aJCEBEKGI=; b=CJQJ0nqLeW9vYtvQWSSSuaNJ7LoBG13cHiEr0A1PqJbxODBN5wNhIkY/u8Lpd4+VNwu4cM mgRBxXsQU3bORmkWxyfFYKbSXFdo8xroxbS7RsPwjc1wMn2mUKC0Q55lrOIp6fus0bkbSA VpfJ+0inteuDLzp8a2SwZwshBoh22KQ= Received: from mail-qt1-f198.google.com (mail-qt1-f198.google.com [209.85.160.198]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-675-Qc60ckDROUGghLxXRz_A_Q-1; Mon, 17 Jul 2023 13:24:09 -0400 X-MC-Unique: Qc60ckDROUGghLxXRz_A_Q-1 Received: by mail-qt1-f198.google.com with SMTP id d75a77b69052e-403caba5e26so31975331cf.1 for ; Mon, 17 Jul 2023 10:24:09 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689614649; x=1692206649; h=in-reply-to:from:references:cc:to:content-language:subject :user-agent:mime-version:date:message-id:x-gm-message-state:from:to :cc:subject:date:message-id:reply-to; bh=5E5eRyM/bwitAgTE40vvWX6icWaAKPsrmJAMxw2+Bk0=; b=DlG4nU0HgndaCKpn3/K5LwMokC49vFlxCGdIGb1LCNGL+3xwRuXBYYwzZ9Ts5TjkgV H1/F/R0N1sX/f+pIdlJp6PGCNy8xKmr91Cvn05qVR2pUF2aKYgxg6eOHcpFZBdA68dWg ChVN01Jt4jALHevQ6VZLpDZqDS7mmhQwqnq7RVM+Ao4baB0Rsne3iQUiPFHeWzedgPsM HP8tj7SWq6VRpZd+svNTL+sj0npzm2bS+XCEeDGhkYCyFGe5wm960kxIJoq3Pn6pTYjC /3cWYorLlGL6TPQwZqKnwTz2iU7duo3h5Bgtpqqch6/iNGQjHXyjRjRUz3m5lBbytsKR 6zkg== X-Gm-Message-State: ABy/qLZnydW5uxziuybSJApYdNxq+EEab3NZzMd+MOwAeVVhqN4KJ1Wg nJcPU5LSqEhmqVhBKzqvdqEeFifPj/lTqH5H7K2Zs+nv2rlQiiI6KJNnK/2OQt8RghSzZwaMCOE Sns+fQ8zxHROvrxSXwQ== X-Received: by 2002:a05:622a:241:b0:403:b9c4:b5de with SMTP id c1-20020a05622a024100b00403b9c4b5demr11056669qtx.21.1689614648975; Mon, 17 Jul 2023 10:24:08 -0700 (PDT) X-Google-Smtp-Source: APBJJlFGvOTGfUpLmvl9uAk+SiyBTShXKr/rxLZwDmMVK/fyi5n/xqToAatKKDHWmfdMPjZb+r+/lw== X-Received: by 2002:a05:622a:241:b0:403:b9c4:b5de with SMTP id c1-20020a05622a024100b00403b9c4b5demr11056651qtx.21.1689614648651; Mon, 17 Jul 2023 10:24:08 -0700 (PDT) Received: from ?IPV6:2605:8d80:5e1:adf2:ddd3:fd05:529f:4aa4? ([2605:8d80:5e1:adf2:ddd3:fd05:529f:4aa4]) by smtp.gmail.com with ESMTPSA id d17-20020ac847d1000000b00400aa8592d1sm11426qtr.36.2023.07.17.10.24.06 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 17 Jul 2023 10:24:07 -0700 (PDT) Message-ID: Date: Mon, 17 Jul 2023 13:24:06 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.11.0 Subject: Re: [PATCH V4] Optimize '(X - N * M) / N' to 'X / N - M' if valid To: Jiufu Guo , Richard Biener Cc: Aldy Hernandez , gcc-patches@gcc.gnu.org, jeffreyalaw@gmail.com, richard.sandiford@arm.com, segher@kernel.crashing.org, dje.gcc@gmail.com, linkw@gcc.gnu.org, bergner@linux.ibm.com References: <20230711090413.3587421-1-guojiufu@linux.ibm.com> <430f2117-3848-d9e5-edab-607a58a460de@redhat.com> <7nsf9mzm73.fsf@ltcden2-lp1.aus.stglabs.ibm.com> From: Andrew MacLeod In-Reply-To: <7nsf9mzm73.fsf@ltcden2-lp1.aus.stglabs.ibm.com> X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: multipart/mixed; boundary="------------jV2AHK5MDZuloCjR9S0EZZIV" Content-Language: en-US X-Spam-Status: No, score=-11.0 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_NONE,RCVD_IN_MSPIKE_H4,RCVD_IN_MSPIKE_WL,SPF_HELO_NONE,SPF_NONE,TXREP,T_SCC_BODY_TEXT_LINE autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: This is a multi-part message in MIME format. --------------jV2AHK5MDZuloCjR9S0EZZIV Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit On 7/17/23 09:45, Jiufu Guo wrote: > >>> Should we decide we would like it in general, it wouldnt be hard to add to >>> irange.  wi_fold() cuurently returns null, it could easily return a bool >>> indicating if an overflow happened, and wi_fold_in_parts and fold_range would >>> simply OR the results all together of the compoent wi_fold() calls.  It would >>> require updating/audfiting  a number of range-op entries and adding an >>> overflowed_p()  query to irange. >> Ah, yeah - the folding APIs would be a good fit I guess. I was >> also looking to have the "new" helpers to be somewhat consistent >> with the ranger API. >> >> So if we had a fold_range overload with either an output argument >> or a flag that makes it return false on possible overflow that >> would work I guess? Since we have a virtual class setup we >> might be able to provide a default failing method and implement >> workers for plus and mult (as needed for this patch) as the need >> arises? > Thanks for your comments! > Here is a concern. The patterns in match.pd may be supported by > 'vrp' passes. At that time, the range info would be computed (via > the value-range machinery) and cached for each SSA_NAME. In the > patterns, when range_of_expr is called for a capture, the range > info is retrieved from the cache, and no need to fold_range again. > This means the overflow info may also need to be cached together > with other range info. There may be additional memory and time > cost. > I've been thinking about this a little bit, and how to make the info available in a useful way. I wonder if maybe we just add another entry point  to range-ops that looks a bit like fold_range ..   Attached is an (untested) patch which ads overflow_free_p(op1, op2, relation)  to rangeops.   It defaults to returning false.  If you want to implement it for say plus,  you'd add to operator_plus in range-ops.cc  something like operator_plus::overflow_free_p (irange&op1, irange& op2, relation_kind) {    // stuff you do in plus_without_overflow } I added relation_kind as  param, but you can ignore it.  maybe it wont ever help, but it seems like if we know there is a relation between op1 and op2 we might be able to someday determine something else?     if not, remove it. Then all you need to do too access it is to go thru range-op_handler.. so for instance: range_op_handler (PLUS_EXPR).overflow_free_p (op1, op2) It'll work for all types an all tree codes. the dispatch machinery will return false unless both op1 and op2 are integral ranges, and then it will invoke the appropriate handler, defaulting to returning FALSE. I also am not a fan of the get_range  routine.  It would be better to generally just call range_of_expr, get the results, then handle undefined in the new overflow_free_p() routine and return false.  varying should not need anything special since it will trigger the overflow when you do the calculation. The auxillary routines could go in vr-values.h/cc.  They seem like things that simplify_using_ranges could utilize, and when we get to integrating simplify_using_ranges better,  what you are doing may end up there anyway Does that work? Andrew --------------jV2AHK5MDZuloCjR9S0EZZIV Content-Type: text/x-patch; charset=UTF-8; name="ofp.diff" Content-Disposition: attachment; filename="ofp.diff" Content-Transfer-Encoding: base64 ZGlmZiAtLWdpdCBhL2djYy9yYW5nZS1vcC5jYyBiL2djYy9yYW5nZS1vcC5jYwppbmRleCBkMWM3 MzVlZTZhYS4uZjJhODYzZGIyODYgMTAwNjQ0Ci0tLSBhL2djYy9yYW5nZS1vcC5jYworKysgYi9n Y2MvcmFuZ2Utb3AuY2MKQEAgLTM2Niw2ICszNjYsMjQgQEAgcmFuZ2Vfb3BfaGFuZGxlcjo6b3Ax X29wMl9yZWxhdGlvbiAoY29uc3QgdnJhbmdlICZsaHMpIGNvbnN0CiAgICAgfQogfQogCitib29s CityYW5nZV9vcF9oYW5kbGVyOjpvdmVyZmxvd19mcmVlX3AgKGNvbnN0IHZyYW5nZSAmbGgsCisJ CQkJICAgY29uc3QgdnJhbmdlICZyaCwKKwkJCQkgICByZWxhdGlvbl90cmlvIHJlbCkgY29uc3QK K3sKKyAgZ2NjX2NoZWNraW5nX2Fzc2VydCAobV9vcGVyYXRvcik7CisgIHN3aXRjaCAoZGlzcGF0 Y2hfa2luZCAobGgsIGxoLCByaCkpCisgICAgeworICAgICAgY2FzZSBST19JSUk6CisJcmV0dXJu IG1fb3BlcmF0b3ItPm92ZXJmbG93X2ZyZWVfcChhc19hIDxpcmFuZ2U+IChsaCksCisJCQkJCSAg IGFzX2EgPGlyYW5nZT4gKHJoKSwKKwkJCQkJICAgcmVsKTsKKyAgICAgIGRlZmF1bHQ6CisJcmV0 dXJuIGZhbHNlOworICAgIH0KK30KKworCiAKIC8vIENvbnZlcnQgaXJhbmdlIGJpdG1hc2tzIGlu dG8gYSBWQUxVRSBNQVNLIHBhaXIgc3VpdGFibGUgZm9yIGNhbGxpbmcgQ0NQLgogCkBAIC02ODgs NiArNzA2LDEzIEBAIHJhbmdlX29wZXJhdG9yOjpvcDFfb3AyX3JlbGF0aW9uX2VmZmVjdCAoaXJh bmdlICZsaHNfcmFuZ2UgQVRUUklCVVRFX1VOVVNFRCwKICAgcmV0dXJuIGZhbHNlOwogfQogCiti b29sCityYW5nZV9vcGVyYXRvcjo6b3ZlcmZsb3dfZnJlZV9wIChjb25zdCBpcmFuZ2UgJiwgY29u c3QgaXJhbmdlICYsCisJCQkJIHJlbGF0aW9uX3RyaW8pIGNvbnN0Cit7CisgIHJldHVybiBmYWxz ZTsKK30KKwogLy8gQXBwbHkgYW55IGtub3duIGJpdG1hc2sgdXBkYXRlcyBiYXNlZCBvbiB0aGlz IG9wZXJhdG9yLgogCiB2b2lkCmRpZmYgLS1naXQgYS9nY2MvcmFuZ2Utb3AuaCBiL2djYy9yYW5n ZS1vcC5oCmluZGV4IGFmOTRjMjc1NmE3Li5kYjNiMDNmMjhhNSAxMDA2NDQKLS0tIGEvZ2NjL3Jh bmdlLW9wLmgKKysrIGIvZ2NjL3JhbmdlLW9wLmgKQEAgLTE0Nyw2ICsxNDcsOSBAQCBwdWJsaWM6 CiAKICAgdmlydHVhbCByZWxhdGlvbl9raW5kIG9wMV9vcDJfcmVsYXRpb24gKGNvbnN0IGlyYW5n ZSAmbGhzKSBjb25zdDsKICAgdmlydHVhbCByZWxhdGlvbl9raW5kIG9wMV9vcDJfcmVsYXRpb24g KGNvbnN0IGZyYW5nZSAmbGhzKSBjb25zdDsKKworICB2aXJ0dWFsIGJvb2wgb3ZlcmZsb3dfZnJl ZV9wIChjb25zdCBpcmFuZ2UgJmxoLCBjb25zdCBpcmFuZ2UgJnJoLAorCQkJCXJlbGF0aW9uX3Ry aW8gPSBUUklPX1ZBUllJTkcpIGNvbnN0OwogcHJvdGVjdGVkOgogICAvLyBQZXJmb3JtIGFuIGlu dGVncmFsIG9wZXJhdGlvbiBiZXR3ZWVuIDIgc3ViLXJhbmdlcyBhbmQgcmV0dXJuIGl0LgogICB2 aXJ0dWFsIHZvaWQgd2lfZm9sZCAoaXJhbmdlICZyLCB0cmVlIHR5cGUsCkBAIC0yMTQsNiArMjE3 LDggQEAgcHVibGljOgogCQkJCSAgY29uc3QgdnJhbmdlICZvcDIsCiAJCQkJICByZWxhdGlvbl9r aW5kID0gVlJFTF9WQVJZSU5HKSBjb25zdDsKICAgcmVsYXRpb25fa2luZCBvcDFfb3AyX3JlbGF0 aW9uIChjb25zdCB2cmFuZ2UgJmxocykgY29uc3Q7CisgIGJvb2wgb3ZlcmZsb3dfZnJlZV9wIChj b25zdCB2cmFuZ2UgJmxoLCBjb25zdCB2cmFuZ2UgJnJoLAorCQkJcmVsYXRpb25fdHJpbyA9IFRS SU9fVkFSWUlORykgY29uc3Q7CiBwcm90ZWN0ZWQ6CiAgIHVuc2lnbmVkIGRpc3BhdGNoX2tpbmQg KGNvbnN0IHZyYW5nZSAmbGhzLCBjb25zdCB2cmFuZ2UgJm9wMSwKIAkJCSAgY29uc3QgdnJhbmdl JiBvcDIpIGNvbnN0Owo= --------------jV2AHK5MDZuloCjR9S0EZZIV--