From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ed1-x52b.google.com (mail-ed1-x52b.google.com [IPv6:2a00:1450:4864:20::52b]) by sourceware.org (Postfix) with ESMTPS id 366E03858C27 for ; Wed, 24 Nov 2021 12:49:03 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 366E03858C27 Received: by mail-ed1-x52b.google.com with SMTP id r25so9886553edq.7 for ; Wed, 24 Nov 2021 04:49:03 -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=wqHw/kDzDG0zYkyWNdjNUX9j9B8CjT/+hIfjw0PrRQE=; b=KdYk2O0cZe4uXC1RHwH2B93Oxef7+1YYTn5Cd2aEWq8DitO+wqQIhDTVCk46X+XzYB dZTns5/Sq1FKoBfH3Ayddx82pWQZNLapg7oSKxy51DangHVvATzd6irjSNkKKuBaFRzJ Fktd5geZ+Vcl4540aNKZd9p2SzT3rpW3bYW97UEy8cbiRBuzwErqjye0Lkb1q/oFyIob kx1womYqIn4UtAo/Rrdu4f8ilKhlRxwVZd8IQbtd72w7x9j0vHcIBIPvjHmHZdkZmyaf vJWcnejIVc3tfIYWFIButVZ9Lw/55eFtDik8p8BOSTFRlctlisSywJFKRR78VMMD77/1 cdFQ== X-Gm-Message-State: AOAM5304T8SHQbsN8TrCyjdLaXuYUUWXDYhSjfG8XA5H8UJPfFk5yeOL IoPcMoHZpaGi718CDf+ITdRNwBtW8CCyfgviiSA= X-Google-Smtp-Source: ABdhPJzzC8UDKa+C1LqA++rubMaI8cOPnSy8iYm+JEcPuALDX1Pd/ipZy6EXnu9mFPfy896K9fkO7B/rB+XcMwRfNrI= X-Received: by 2002:aa7:cd8a:: with SMTP id x10mr25153434edv.3.1637758142068; Wed, 24 Nov 2021 04:49:02 -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> <0db1d9e8-f097-e766-a9fa-1a98c47b8115@suse.cz> <3a07ef98-d05f-dc07-2e36-a2b4ffd52936@suse.cz> In-Reply-To: <3a07ef98-d05f-dc07-2e36-a2b4ffd52936@suse.cz> From: Richard Biener Date: Wed, 24 Nov 2021 13:48:51 +0100 Message-ID: Subject: Re: [PATCH] Loop unswitching: support gswitch statements. To: =?UTF-8?Q?Martin_Li=C5=A1ka?= Cc: Aldy Hernandez , 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: Wed, 24 Nov 2021 12:49:04 -0000 On Wed, Nov 24, 2021 at 11:48 AM Martin Li=C5=A1ka wrote: > > On 11/24/21 09:00, Richard Biener wrote: > > On Tue, Nov 23, 2021 at 5:36 PM Martin Li=C5=A1ka wrot= e: > >> > >> On 11/23/21 16:20, Martin Li=C5=A1ka wrote: > >>> Sure, so for e.g. case 1 ... 5 we would need to create a new unswitch= _predicate > >>> with 1 <=3D index && index <=3D 5 tree predicate (and the correspondi= ng irange range). > >>> Later once we unswitch on it, we should use a special unreachable_fla= g that will > >>> be used for marking of dead edges (similarly how we fold gconds to bo= olean_{false/true}_node. > >>> Does it make sense? > >> > >> I have thought about it more and it's not enough. What we really want = is having a irange > >> for *each edge* (2 for gconds and multiple for gswitchs). Once we sele= ct a unswitch_predicate, > >> then we need to fold_range in true/false loop all these iranges. Doing= that we can handle situations like: > >> > >> if (index < 1) > >> do_something1 > >> > >> if (index > 2) > >> do_something2 > >> > >> switch (index) > >> case 1 ... 2: > >> do_something; > >> ... > >> > >> as seen the once we unswitch on 'index < 1' and 'index > 2', then the = first case will be taken in the false_edge > >> of 'index > 2' loop unswitching. > > > > Hmm. I'm not sure it needs to be this complicated. We're basically > > evaluating ranges/predicates based > > on a fixed set of versioning predicates. Your implementation created > > "predicates" for the to be simplified > > conditions but in the end we like to evaluate the actual stmt to > > figure the taken/not taken edges. > > Yes. > > > IIRC > > elsewhere Andrew showed a snipped on how to evaluate a stmt with a > > given range - not sure if that > > I'm using that. First I isolate a irange from a versioning-predicate with > ranger->range_on_edge and I later combine it with: > fold_range (r, stmt, parent_range). > > > > was useful enough. So what I think would be nice if we could somehow > > use rangers path query > > without an actual CFG. So we virtuall have > > > > if (versioning-predicate1) > > if (versioning-predicate2) > > ; > > else > > for (;;) // out current loop > > { > > ... > > if (condition) > > ; > > ... > > switch (var) > > { > > ... > > } > > } > > > > and versioning-predicate1 and versioning-predicate2 are not in the IL. > > What we'd like > > to do is seed the path query with a "virtual" path through the two > > predicates to the > > entry of the loop and compute_ranges based on those. > > What I can do that via building of a vector of tuple > that would be passed to recursive calls of tree_unswitch_single_loop. > That basically describes which true/false edges are taken for the so far = created > versioning-predicates. Right? That should be usable. Yeah. Not sure how much incremental re-use we can have here. I'd keep things simple at this point and shoot for something that works on a single recursion level only. > > Then we like to > > use range_of_stmt on 'if (condition)' and 'switch (var)' to determine > > not taken edges. > > Works for me and we would mark unreachable case BBs with a unreachable_fl= ag > (we can't fold it away as shown in the original patch attempt). As said we probably want to mark edges, unreachable edges from upthread recursions should get their flags copied even. > > Looking somewhat at the sources it seems like we "simply" need to do wh= at > > compute_outgoing_relations does - unfortunately the code lacks comments > > so I have no idea what jt_fur_source src (...).register_outgoing_edges = does ... > > > > Anyway, for now manually simplifying things is fine but I probably woul= d still > > stick to a basic interface that marks not taken outgoing edges of a stm= t based > > on the set of versioning predicates. > > Lemme try working on another version of the patch. Yup. You did have a branch, right? Maybe I'll poke at it a bit as well. Richard. > Martin > > > > > Richard. > > > >> > >> Martin >