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 126C7384F022 for ; Wed, 12 Oct 2022 10:15:31 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 126C7384F022 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=1665569730; h=from:from:reply-to: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=QRFnIllmp6YbVfMI+0K/K73rtb86VkEE1lvQqjEjNzA=; b=Org0xKoOoK/v4KB+KOfey80nyqP7VNkntZ1tCfstkLd8dkLw9QZQ1u7gWqr2vQo3cA482W NnF1auKhVB0liRrD/NrDxgS1YCLxMXCB1A+GlWyMG6Vdd8B/0fA2Bqr7XJ9MU3RxuBn5ju Zl9jVe/MOWmJThcuxo6ZX3cVNDI2bjY= Received: from mimecast-mx02.redhat.com (mimecast-mx02.redhat.com [66.187.233.88]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-402-qUMlStngPhC2ZU6KZ0_fog-1; Wed, 12 Oct 2022 06:15:29 -0400 X-MC-Unique: qUMlStngPhC2ZU6KZ0_fog-1 Received: from smtp.corp.redhat.com (int-mx04.intmail.prod.int.rdu2.redhat.com [10.11.54.4]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id 3323F858F13; Wed, 12 Oct 2022 10:15:29 +0000 (UTC) Received: from tucnak.zalov.cz (unknown [10.39.192.55]) by smtp.corp.redhat.com (Postfix) with ESMTPS id C438C2084844; Wed, 12 Oct 2022 10:15:28 +0000 (UTC) Received: from tucnak.zalov.cz (localhost [127.0.0.1]) by tucnak.zalov.cz (8.17.1/8.17.1) with ESMTPS id 29CAFPq5848505 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Wed, 12 Oct 2022 12:15:25 +0200 Received: (from jakub@localhost) by tucnak.zalov.cz (8.17.1/8.17.1/Submit) id 29CAFOtl848504; Wed, 12 Oct 2022 12:15:24 +0200 Date: Wed, 12 Oct 2022 12:15:24 +0200 From: Jakub Jelinek To: Andrew MacLeod Cc: Richard Biener , Jan Hubicka , Aldy Hernandez , gcc-patches@gcc.gnu.org Subject: Re: [PATCH] middle-end IFN_ASSUME support [PR106654] Message-ID: Reply-To: Jakub Jelinek References: <244e087a-8680-9c21-0774-c7b6621e2eda@redhat.com> MIME-Version: 1.0 In-Reply-To: <244e087a-8680-9c21-0774-c7b6621e2eda@redhat.com> X-Scanned-By: MIMEDefang 3.1 on 10.11.54.4 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=WINDOWS-1252 Content-Disposition: inline Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,BODY_8BITS,DKIMWL_WL_HIGH,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,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 Tue, Oct 11, 2022 at 02:05:52PM -0400, Andrew MacLeod wrote: > > 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. Sure. > Is this function inlined?  If it isn't then you'd need LTO/IPA to propagate Never (the code is not supposed to be actually executed at runtime ever, it is purely as if, if this function would be executed, then it would return true, otherwise it would be UB). But the goal is of course to inline stuff into it and optimize the function even post IPA. > 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. > 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). > > 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.). > 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). Jakub