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 4C67B3858D28 for ; Tue, 11 Oct 2022 18:08:11 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 4C67B3858D28 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=1665511690; 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: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=EybUbfA/0GyZ4SOrhPv2V9I7gWk/CvZathLUEk3ugsE=; b=e+t8lTe34D/kEsJskA2W6glH8qxz6f3h1Ng8EU/Dme/Bhm0WxRIaNNlCbDpl0WZgnwhSig wHnikS7ACjm9mJctWrvS1g9xrVbpoFanwY8DuN0ccf4NXN8jjrx4+wV6R9bgdlzvOEAh9N LCvKjIkhd8rrew2MS+Qe/5cl1hXUVsY= Received: from mail-qv1-f72.google.com (mail-qv1-f72.google.com [209.85.219.72]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-258-knxYEFqzP-iKfW7Dl3xiMA-1; Tue, 11 Oct 2022 14:08:09 -0400 X-MC-Unique: knxYEFqzP-iKfW7Dl3xiMA-1 Received: by mail-qv1-f72.google.com with SMTP id q17-20020a056214019100b004b1d3c9f3acso8377977qvr.0 for ; Tue, 11 Oct 2022 11:08:09 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding: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=EybUbfA/0GyZ4SOrhPv2V9I7gWk/CvZathLUEk3ugsE=; b=tEJJiWtemIXz80CpxGch9igUYciMorwHR5mYoOME28NCwyubAPs8Qg2f8n/vv6McWN zmhC9cBzXRGBkFWz3m7OinBt4/XCBoHnwVqG/+EqhzTRS4g+soOKxijXldrNePHAlKSv oXWog0nH3g3/rLmquPIUtoXegddOY5+LKR1UFM/CwR5o1cG3Jy/1MSNvfmCKC9RaCrh0 uGXfiz0jdLKC1c/gZtE6ifeVvWpit6HwoVebSB4yVK5r0J6EGMpNSrRhRqj2Lkk5C9AH ccNJlch9EDDIVCGHXVgokqf0197ECDmKPFDrrkw7asQ3FGXzYbb0mx/DWozJ0O6Wu/L/ qObw== X-Gm-Message-State: ACrzQf1CK4NRYg6Hnea6LZvL8/pEJwyQEOvkUnSe0RTLB8bBqnSqOST0 nB14CU3oeycr+8xBpuOk6DN15jVfK3FOez83/8Uq20CnZiOck3xBUk5tsOurq/92GWvq5/9kKPN oSYb399SHuPvgKatUyw== X-Received: by 2002:ac8:5c02:0:b0:39a:bf28:81d7 with SMTP id i2-20020ac85c02000000b0039abf2881d7mr7902848qti.437.1665511689117; Tue, 11 Oct 2022 11:08:09 -0700 (PDT) X-Google-Smtp-Source: AMsMyM7qQ2bOv1gzz31i5PYY/BTxDJwuTD2+w2s1qqzyg2ZgaLoCrvO7sXNsk5M3dHdIYqoSxjKZew== X-Received: by 2002:ac8:5c02:0:b0:39a:bf28:81d7 with SMTP id i2-20020ac85c02000000b0039abf2881d7mr7902822qti.437.1665511688828; Tue, 11 Oct 2022 11:08:08 -0700 (PDT) Received: from [192.168.72.179] ([24.114.84.152]) by smtp.gmail.com with ESMTPSA id u16-20020a05620a0c5000b006ce441816e0sm13451192qki.15.2022.10.11.11.08.06 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 11 Oct 2022 11:08:08 -0700 (PDT) Message-ID: <244e087a-8680-9c21-0774-c7b6621e2eda@redhat.com> Date: Tue, 11 Oct 2022 14:05:52 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.2.1 Subject: Re: [PATCH] middle-end IFN_ASSUME support [PR106654] To: Jakub Jelinek , Richard Biener , Jan Hubicka , Aldy Hernandez Cc: gcc-patches@gcc.gnu.org References: From: Andrew MacLeod In-Reply-To: X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-5.2 required=5.0 tests=BAYES_00,BODY_8BITS,DKIMWL_WL_HIGH,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,NICE_REPLY_A,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_NONE,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: On 10/10/22 04:54, Jakub Jelinek via Gcc-patches wrote: > Hi! > > My earlier patches gimplify the simplest non-side-effects assumptions > into if (cond) ; else __builtin_unreachable (); and throw the rest > on the floor. > The following patch attempts to do something with the rest too. > For -O0, it actually throws even the simplest assumptions on the floor, > we don't expect optimizations and the assumptions are there to allow > optimizations. Otherwise, it keeps the handling of the simplest > assumptions as is, and otherwise arranges for the assumptions to be > visible in the IL as > .ASSUME (_Z2f4i._assume.0, i_1(D)); > call where there is an artificial function like: > bool _Z2f4i._assume.0 (int i) > { > bool _2; > > [local count: 1073741824]: > _2 = i_1(D) == 43; > return _2; > > } > with the semantics that there is UB unless the assumption function > would return true. > > Aldy, could ranger handle this? If it sees .ASSUME call, > walk the body of such function from the edge(s) to exit with the > assumption that the function returns true, so above set _2 [true, true] > and from there derive that i_1(D) [43, 43] and then map the argument > in the assumption function to argument passed to IFN_ASSUME (note, > args there are shifted by 1)? Ranger GORI component could assume the return value is [1,1] and work backwards from there. Single basic blocks would be trivial. The problem becomes when there are multiple blocks.   The gori engine has no real restriction other than it works from within a basic block only I see no reason we couldn't wire something up that continues propagating values out the top of the block evaluating things for more complicated cases.  you would end up with a set of ranges for names which are the "maximal" possible range based on the restriction that the return value is [1,1]. > During gimplification it actually gimplifies it into > D.2591 = .ASSUME (); > if (D.2591 != 0) goto ; else goto ; > : > { > i = i + 1; > D.2591 = i == 44; > } > : > .ASSUME (D.2591); > with the condition wrapped into a GIMPLE_BIND (I admit the above isn't > extra clean but it is just something to hold it from gimplifier until > gimple low pass; it reassembles if (condition_never_true) { cond; }; What we really care about is what the SSA form looks like.. thats what ranger will deal with. Is this function inlined?  If it isn't then you'd need LTO/IPA to propagate the ranges we calculated above for the function. Or some special pass that reads assumes, does the processing you mention above and applies it?  Is that what you are thinking? Looking at assume7.C, I see: int bar (int x) {   [local count: 1073741824]:   .ASSUME (_Z3bari._assume.0, x_1(D));   return x_1(D); And: bool _Z3bari._assume.0 (int x) {   bool _2;   [local count: 1073741824]:   _2 = x_1(D) == 42;   return _2; Using the above approach, GORI could tell you that if _2 is [1,1] that x_1 must be [42,42]. If you are parsing that ASSUME, you could presumably match things pu and we could make x_1 have a range of [42,42] in bar() at that call. this would require a bit of processing in fold_using_range for handling function calls, checking for this case and so on, but quite doable. looking at the more complicated case for bool _Z3bazi._assume.0 (int x) it seems that the answer is determines without processing most of the function. ie:, work from the bottom up:   [local count: 670631318]:   _8 = x_3 == 43;                       x_3 = [43,43]   [local count: 1073741824]:   # _1 = PHI <0(2), _8(5)>              _8 = [1,1]  2->6 cant happen   return _1;                            _1 = [1,1] you only care about x, so as soon as you find a result that that, you'd actually be done.   However, I can imagine cases where you do need to go all the way back to the top of the assume function.. and combine values. Ie bool assume (int x, int y) {   if (y > 10)     return x == 2;   return x > 20; }   [local count: 1073741824]:   if (y_2(D) > 10)     goto ; [34.00%]   else     goto ; [66.00%]   [local count: 365072224]:   _5 = x_3(D) == 2;                    x_3 = [2,2]   goto ; [100.00%]   [local count: 708669601]:   _4 = x_3(D) > 20;                    x_3 = [21, +INF]   [local count: 1073741824]:   # _1 = PHI <_5(3), _4(4)>          _5 = [1,1], _4 = [1,1]   return _1; And we'd have a range of [2,2][21, +INF] if you wanted to be able to plug values of Y in, things would get more complicated, but the framework would all be there. OK, enough pontificating,   it wouldn't be ranger, but yes, you could wire GORI into a pass which evaluates what we think the range of a set of inputs would be if we return 1.  I don't think It would be very difficult, just a bit of work to work the IL in reverse.  And then you should be able to wire in a range update for those parameters in fold_using_range (or wherever else I suppose) with a little more work. It seems to me that if you were to "optimize" the function via this new pass,  assuming 1 was returned,  you could probably eliminate a lot of the extraneous code..   for what thats worth. Can the assume function produce more than one assumption you care about? Andrew