From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ed1-x529.google.com (mail-ed1-x529.google.com [IPv6:2a00:1450:4864:20::529]) by sourceware.org (Postfix) with ESMTPS id 923EA3858D39 for ; Tue, 9 Nov 2021 13:37:57 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 923EA3858D39 Received: by mail-ed1-x529.google.com with SMTP id m14so76223996edd.0 for ; Tue, 09 Nov 2021 05:37:57 -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=gtAPKNvI+G/shN6vstX78XVgPsLPlIM6yKA99hfbbQg=; b=bSgl7/VIGIb3etmSGE7SkkZd93pk30o8qp1T/udjZLvcQbm2IUQWUvAxQPs2W+DmEm UytFZ43K1Yw5kmnWW+r6kFXzDFxhCeLAVdAtcTc2dDKn5KVL44DUJESSUsnUuojgXlAU 6+0EWJSm7xbH0D3n6PrcYfFEzPoacOCOIJM4HfruUEk3zaEKvUEAZ5lvabGTIW9M+wtp mABnFsNEN6n6F3HDCcZRS4G37CGz5H8E7xDU3/BE+dK1OmPsfG88EI6JhLcAfNdVe1gf gr7c+rGGAFiJAnvYZTZZokdCJHSA2j7x3olJZqAVlI5cC2JmCc9zXaKRUqmVvQ++G73V I+uA== X-Gm-Message-State: AOAM532zI6opYuexwwmvbcVJ+MiS8XNUvkjdzjoq+lreWvP2eBC3EnNJ 1kebJZjnJZB2143e7nibFbOtUy1icIIQsp1P/2M= X-Google-Smtp-Source: ABdhPJw93ypDB2bkyH1p8XOThHlHWxdylKKxVnxBW2DhEXqkxBMJELUHA7UbEhtRInmmMy0MhJ3z/n6prlVUkv/Ezb0= X-Received: by 2002:a17:906:a0d7:: with SMTP id bh23mr9525720ejb.82.1636465076447; Tue, 09 Nov 2021 05:37:56 -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> In-Reply-To: <8da24825-19ec-56a6-a68c-5c37c7acc3e1@redhat.com> From: Richard Biener Date: Tue, 9 Nov 2021 14:37:45 +0100 Message-ID: Subject: Re: [PATCH] Loop unswitching: support gswitch statements. To: Andrew MacLeod Cc: =?UTF-8?Q?Martin_Li=C5=A1ka?= , GCC Patches Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-2.5 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: Tue, 09 Nov 2021 13:37:59 -0000 On Mon, Nov 8, 2021 at 8:45 PM Andrew MacLeod wrote: > > On 11/8/21 10:05 AM, Martin Li=C5=A1ka wrote: > > On 9/28/21 22:39, Andrew MacLeod wrote: > >> In Theory, modifying the IL should be fine, it happens already in > >> places, but its not extensively tested under those conditions yet. > > > > Hello Andrew. > > > > I've just tried using a global gimple_ranger and it crashes when loop > > unswitching duplicates > > some BBs. > > > > Please try the attached patch for: > > hey Martin, > > try using this in your tree. Since nothing else is using a growing BB > right now, I'll let you work with it and see if everything works as > expected before checking it in, just in case we need more tweaking. > With this, > > make RUNTESTFLAGS=3Ddg.exp=3Dloop-unswitch*.c check-gcc > > runs clean. > > > basically, I tried to grow it by either a factor of 10% for the current > BB size when the grow is requested, or some double the needed extra > size, or 128... whichever value is "maximum" That means it shoudnt be > asking for tooo much each time, but also not a minimum amount. > > Im certainly open to suggestion on how much to grow it each time. > Note the vector being grown is ONLY fo the SSA_NAme being asked for.. so > it really an on-demand thing just for specific names, in your case, > mostly just the switch index. > > Let me know how this works for you, and if you have any other issues. So I think in the end we shouldn't need the growing. Ideally we'd do all the analysis before the first transform, but for that we'd need ranger to be able to "simplify" conditions based on a known true/false predicate that's not yet in the IL. Consider for (;;) { if (invariant < 3) // A { ... } if (invariant < 5) // B { ... } } unswitch analysis will run into the condition 'A' and determine the loop can be unswitched with the condition 'invariant < 3'. To be able to perform cost assessment and to avoid redundant unswitching we want to determine that if we unswitch with 'invariant < 3' being true then the condition at 'B' is true as well before actually inserting the if (invariant < 3) outside of the loop. So I'm thinking of assigning a gimple_uid to each condition we want to unswitch on and have an array indexed by the uid with meta-data on the unswitch opportunity, the "related" conditions could be marked with the same uid (or some other), and the folding result recorded so that at transform time we can just do the appropriate replacement without invoking ranger again. Now, but how do we arrange for the ranger analysis here? We might also somehow want to remember that on the 'invariant < 3' =3D=3D false copy of the loop there's still the unswitching opportunity on 'invariant < 5', but not on the 'invariant < 5' =3D=3D true copy. Currently unswitching uses a custom simplify_using_entry_checks which tries to do simplification only after the fact (and so costing also is far from costing the true cost and ordering of the opportunities to do the best first is not implemented either). Richard. > Andrew >