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 42DC83850854 for ; Wed, 12 Oct 2022 14:31:05 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 42DC83850854 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=1665585064; 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=2158h6TUBvJyGa3p4Oc2533uoaDReUKETXoKMtwv/Ws=; b=F6SKFV8/u9WtWXa5huxZzfnh7BRHcww3F76EzQJiJmBhsXjUtpnac551MxQNBgp8ulTDGn jDnI1cIJJJFWpTiak5A7Z0Is9qD1yNWnaHchia90SBtp8mSHUDFjkP/b0qv+C+7SgmsJDV qxLMhca3/AYtmBqOd+A+n0WPmJq5BxU= 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-584-KRTDMNI_PAKxuLkVuHid3Q-1; Wed, 12 Oct 2022 10:31:04 -0400 X-MC-Unique: KRTDMNI_PAKxuLkVuHid3Q-1 Received: by mail-qv1-f72.google.com with SMTP id ok8-20020a0562143c8800b004b07e9ca57eso9872530qvb.19 for ; Wed, 12 Oct 2022 07:31:03 -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=2158h6TUBvJyGa3p4Oc2533uoaDReUKETXoKMtwv/Ws=; b=eUbgD7PUGBaYj+PDYL/4HpegCDFNKrDoImZgHcNI45HQb31Ln6SZSVFEyaktZb+SQX V3qkN5iA09bnA6Li6aKPvQI5tNFIvVffetL57USS+b9CL0NuLx6qw7ZTTOMcvN9IYltZ Gy3UQx7ItyjuFk1mZpt/7IBNErjGNwQuuiyGhhGTaA1TZ/CYlci6Bd6MymIsMvagsewH B1qbJUNZdygMz6+fHpDxFBiHy2Qdfm+OMbCtEJaaRhN/uiarV6qxxqTFHmGC8W2gb7YY ZJDFE+WzUsgelYmvz18HBH5ZF0OgeXvtkPRCJUlMx25wtWH+h51tr/Iv+YFxpAEC9Ya2 4DRw== X-Gm-Message-State: ACrzQf1QIarcNxDz59ju/C/5KMsZPQdR8vlnqsMKeSMFHChocV+J4yOE cfQI0cSms+TnOikaFcchYr6TP/QvE1CwCT5A2g1QP+fg6bmVrsJqm9OKZQKJMQdQ6FilXmzW1WJ aDpfrayG/MD87s8CmJQ== X-Received: by 2002:ac8:7f49:0:b0:35c:d64a:eee5 with SMTP id g9-20020ac87f49000000b0035cd64aeee5mr23010655qtk.127.1665585063344; Wed, 12 Oct 2022 07:31:03 -0700 (PDT) X-Google-Smtp-Source: AMsMyM7P3+1BB1NOfa3lHidRHaQR3f6ESo4APUPaQSKFW7GlNYnXbx7F2wt+GRQg/zs1LE+v3+oEQA== X-Received: by 2002:ac8:7f49:0:b0:35c:d64a:eee5 with SMTP id g9-20020ac87f49000000b0035cd64aeee5mr23010618qtk.127.1665585063003; Wed, 12 Oct 2022 07:31:03 -0700 (PDT) Received: from ?IPV6:2607:fea8:a263:f600::50d4? ([2607:fea8:a263:f600::50d4]) by smtp.gmail.com with ESMTPSA id k19-20020a05620a0b9300b006ecb9dfdd15sm8253500qkh.92.2022.10.12.07.31.01 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 12 Oct 2022 07:31:02 -0700 (PDT) Message-ID: <144534bb-c25e-5303-47e5-cf56beb98261@redhat.com> Date: Wed, 12 Oct 2022 10:31:00 -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 Cc: Richard Biener , Jan Hubicka , Aldy Hernandez , gcc-patches@gcc.gnu.org References: <244e087a-8680-9c21-0774-c7b6621e2eda@redhat.com> 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=-3.7 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/12/22 06:15, Jakub Jelinek wrote: > >> 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? > The options would be to evaluate it each time ranger processes .ASSUME, > or to perform this backwards range propagation somewhere late during post > IPA optimizations of the cfun->assume_function and remember it somewhere > (e.g. in SSA_NAME_RANGE_INFO of the default defs of the params) and then > when visiting .ASSUME just look those up. I think the latter is better, > we'd do it only once - the assumption that the function returns true after > the assume function itself is optimized will always be the same. > It could be a separate pass (gated on fun->assume_function, so done only > for them) somewhere shortly before expansion to RTL (which is what isn't > done and nothing later for those), or could be done say in VRP2 or some > other existing late pass. > I agree, I think it would be better to process once, and store the results some where. I could provide a routine which attempts the evaluation of the current function, and returns a "safe" range for each of the parameters.   By safe, I mean it would assume VARYING for every unknown value in the function, reduced by whatever the backward walk determined.  We can refine that later by wiring this call in after a full ranger walk of VRP for instance to get more precise values, but that is not necessary at the moment. I can also make it so that we always try to look up values from the .ASSUME in fold_using_range, which means any VRP or other ranger client will pick up the results.  If there is nothing available, it would return VARYING as the default.   Any current range would be intersected with what the ASSUME query returns. I presume you are looking to get this working for this release, making the priority high? :-) >> 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. > If we cache the range info for the assume_function arguments the above way > on SSA_NAME_RANGE_INFO, then you'd just see .ASSUME call and for (n+1)th > argument find nth argument of the 1st argument FUNCTION_DECL's > DECL_ARGUMENTS, ssa_default_def (DECL_STRUCT_FUNCTION (assume_fndecl), parm) > and just union the current range of (n+1)th argument with > SSA_NAME_RANGE_INFO of the ssa_default_def (if non-NULL). Intersection I believe...?  I think the value from the assume's should add restrictions to the range.. >> 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. > Yeah. Note, it is fine to handle say single block assume functions (after > optimizations) first and improve incrementally later, the goal is that > people actually see useful optimizations with simpler (but not simplest) > assume conditions, so they don't say they aren't completely useless, and if > they come up with something more complex that we don't handle yet, they > can file enhancement requests. Of course, trying to walk all the bbs > backwards would be nicer, though even then it is important to be primarily > correct and so punting on anything we can't handle is fine (e.g. if there > are loops etc.). Single blocks for the first cut and POC.  easier.  then look at expansion >> 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? > The assume function can have many arguments (one is created for each > automatic var referenced or set by the condition), so it would be nice to > track all of them rather than just hardcoding the first. And, the argument > doesn't necessarily have to be a scalar, so perhaps later on we could derive > ranges even for structure members etc. if needed. Or just handle > assume_function in IPA-SRA somehow at least. > > The C++23 paper mentions > [[assume(size > 0)]]; > [[assume(size % 32 == 0)]]; > [[assume(std::isfinite(data[i]))]]; > [[assume(*pn >= 1)]]; > [[assume(i == 42)]]; > [[assume(++i == 43)]]; > [[assume((std::cin >> i, i == 42))]]; > [[assume(++almost_last == last)]]; > among other things, the first and fifth are already handled the > if (!cond) __builtin_unreachable (); way and so work even without this > patch, the (std::cin >> i, i == 42) case is not worth bothering for now > and the rest would be single block assumptions that can be handled easily > (except the last one which would have record type arguments and so we'd need > SRA). I figured as much, I was just wondering if there might be some way to "simplify" certain things by processing it and turning each parameter query into a smaller function returning the range we determined from the main one...   but perhaps that is more complicated. Andrew