From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ed1-x52a.google.com (mail-ed1-x52a.google.com [IPv6:2a00:1450:4864:20::52a]) by sourceware.org (Postfix) with ESMTPS id 71BFD3858D3C for ; Fri, 19 Nov 2021 09:49:41 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 71BFD3858D3C Received: by mail-ed1-x52a.google.com with SMTP id z5so40372033edd.3 for ; Fri, 19 Nov 2021 01:49:41 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc:content-transfer-encoding; bh=EYpwG1SPePKNbVtTnfJ5bsYPW/9PvLiWWY4uB53SLjk=; b=LtZR7qto/QrS03fASXPPoDJuXgsjtkItGIES+jiHUqTg/RpFdh+TysaSRPd+SR7pMP fDogPoZgJYdQ9hBINmbK1zSxHLL3Tr1e7WLi8Woe/Na8Y7Cmp6Zo99ediYdFKkaokqIP ZBonvsun/Kr4i8c9PI60lM74myOdBeISGyD5YKtB1I2SouRMn/HAkiIvu1i22kYj/IjJ kOu2A5YSOSSlr/G4adiyUudPyM5eDHy5ONdBYSUi6mSQybMzUFuTM8tQ0nCK1WeTJgzM NlH4fpjfIEnIZNM4P+kypPOjhqQ89JsAK+46Un23/7RwVi3TNKX5/Po31n3n3KVSvlpQ Y61g== X-Gm-Message-State: AOAM533vhFBsDauNwTzLV710Nq91zZkIMkWQsLRu3jsqwqlVVXWOCVim KgQo7+eTIYIe36R7QHre3X5HKfdj2/ZsVX7hNbw= X-Google-Smtp-Source: ABdhPJy5hdKSizzSVdjPMO7QFUdQ5tGNxHcDgSwJmF6v3pYHg9RGbgwnLnYT3g+QgMBRlbEManqwuN/Vyd8GReWhHuA= X-Received: by 2002:a17:906:388c:: with SMTP id q12mr6028340ejd.281.1637315380453; Fri, 19 Nov 2021 01:49:40 -0800 (PST) MIME-Version: 1.0 References: <7791e850-f74d-8c1c-f67c-e02f3f6e007d@redhat.com> <5c6c91d4-ed8b-8d98-2cd9-bafc84e6f2a4@suse.cz> <8da24825-19ec-56a6-a68c-5c37c7acc3e1@redhat.com> <59763e1a-8432-5f23-c399-a9b4dd6c6dff@suse.cz> <0ce410d3-148d-b640-4da6-a443795d4b16@suse.cz> In-Reply-To: <0ce410d3-148d-b640-4da6-a443795d4b16@suse.cz> From: Richard Biener Date: Fri, 19 Nov 2021 10:49:29 +0100 Message-ID: Subject: Re: [PATCH] Loop unswitching: support gswitch statements. To: =?UTF-8?Q?Martin_Li=C5=A1ka?= Cc: Andrew MacLeod , GCC Patches Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-2.3 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) 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: Fri, 19 Nov 2021 09:49:43 -0000 On Tue, Nov 16, 2021 at 2:53 PM Martin Li=C5=A1ka wrote: > > On 11/11/21 08:15, Richard Biener wrote: > > If you look at simplify_using_entry_checks then this is really really s= imple, > > so I'd try to abstract this, recording sth like a unswitch_predicate wh= ere > > we store the condition we unswitch on plus maybe cache the constant > > range of a VAR cmp CST variable condition on the true/false edge. We > > can then try to simplify each gcond/gswitch based on such an unswitch_p= redicate > > (when we ever scan the loop once to discover all opportunities we'd hav= e a > > set of unswitch_predicates to try simplifying against). As said the in= teger > > range thing would be an improvement over the current state so even that > > can be done as followup but I guess for gswitch support that's going to= be > > the thing to use. > > I started working on the unswitch_predicate where I recond also true/fals= e-edge irange > of an expression we unswitch on. > > I noticed one significant problem, let's consider: > > for (int i =3D 0; i < size; i++) > { > double tmp; > > if (order =3D=3D 1) > tmp =3D -8 * a[i]; > else > { > if (order =3D=3D 2) > tmp =3D -4 * b[i]; > else > tmp =3D a[i]; > } > > r[i] =3D 3.4f * tmp + d[i]; > } > > We can end up with first unswitching candidate being 'if (order =3D=3D 2)= ' (I have a real benchmark where it happens). > So I collect ranges and they are [2,2] for true edge and [-INF, 0], [3, I= NF] (because we came to the condition through order !=3D 1 cond). You can only record a range from the unswitch condition itself, not from the path you came, so your false edge range looks wrong. > Then the loop is cloned and we have > if (order =3D=3D 2) > loop_version_1 > else > loop_version_2 > > but in loop_version_2 we wrongly fold 'if (order =3D=3D 1)' to false beca= use it's reflected in the range. Of course for loop_version_1 the range is [2, 2] and for loop_version_2 it is ~[2, 2] - you do have to invert the range when folding the "false" version. > So the question is, can one iterate get_loop_body stmts in some dominator= order? I don't think this would fix anything, but yes, in the end we'd like to unswitch on "outer" conditions first. That would mean iterating blocks in program order, the easiest way is to use get_loop_body_in_dom_order which should fix the above testcase but likely not arbitrary nested ifs. For those you could use rev_post_order_and_mark_dfs_back_seme, but as said using get_loop_body_in_dom_order should be a strict improvement even without any other change (you could propose a patch if you have a testcase that shows a difference with otherwise unchanged unswitching, for example choosing the outer condition instead of the inner with --param max-unswitch-level=3D=3D0). Richard. > > Thanks, > Martin > >