From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ed1-x52d.google.com (mail-ed1-x52d.google.com [IPv6:2a00:1450:4864:20::52d]) by sourceware.org (Postfix) with ESMTPS id A8B8A3858C2C for ; Tue, 30 Nov 2021 11:17:28 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org A8B8A3858C2C Received: by mail-ed1-x52d.google.com with SMTP id g14so85203682edb.8 for ; Tue, 30 Nov 2021 03:17:28 -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=ZiVmNelYM5B7g/hXRI32U33M8v8lPdlKyuldnzZ6q8k=; b=QMJcm+VYL0zxcj+l7QnDIL/qq5gEX2pZenmHGLWqy5qSTgLlIkKK//7L1bJzZJ99ma MZtMpBoAy1zTNE7kh3GQyjNYy56jt8V4snqOYhlAYNP6A3yc5tSIJ/zIAzroniX9G4M4 YVLroOsBFX9lfH46ypbxevg5YZfznjdxRiZZKpLVqXvzrC1PTbEwdeAk2qFVJv9unhaW QbRH1RGTBBA8SwN9iv83USF7iYr7ns67h/7KsY3GABr2b8MFcbjCwKzbKt0Et/lGh9HO mGu6+3DqKhzC8qD+5wO+7aXO1rFb5ORM1MESJYyNbHi7Rxfz4v0lyo5qrUbPgKJQusE7 ojzg== X-Gm-Message-State: AOAM533woCPLYgttyYy3Lbena/DJLBWvZ7YwuYQHfKuWiVIeN23iRbwa 2g1TFJz+Wnn8br8MU9KzJP0itY6PhYwhTlEwr+U= X-Google-Smtp-Source: ABdhPJyRAmMvFKfBEfk264u9mn2qgMc7srIIBqQPgwO+IyeCRwLZvo8VL42EY654Bg9li6XCCgNHdUKGD8ntqm8UZgk= X-Received: by 2002:a05:6402:5194:: with SMTP id q20mr82799034edd.250.1638271047471; Tue, 30 Nov 2021 03:17:27 -0800 (PST) MIME-Version: 1.0 References: <59763e1a-8432-5f23-c399-a9b4dd6c6dff@suse.cz> <0db1d9e8-f097-e766-a9fa-1a98c47b8115@suse.cz> <3a07ef98-d05f-dc07-2e36-a2b4ffd52936@suse.cz> <7bcc368c-3f26-4503-aec1-a3d6378e33ec@suse.cz> <561a3ffd-8973-d771-418f-76c484085cc5@suse.cz> <20265d97-6350-c234-695d-bc18e2e617b4@suse.cz> In-Reply-To: <20265d97-6350-c234-695d-bc18e2e617b4@suse.cz> From: Richard Biener Date: Tue, 30 Nov 2021 12:17:16 +0100 Message-ID: Subject: Re: [PATCH] Loop unswitching: support gswitch statements. To: =?UTF-8?Q?Martin_Li=C5=A1ka?= Cc: 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, 30 Nov 2021 11:17:31 -0000 On Mon, Nov 29, 2021 at 1:45 PM Martin Li=C5=A1ka wrote: > > On 11/26/21 09:12, Richard Biener wrote: > > On Wed, Nov 24, 2021 at 3:32 PM Martin Li=C5=A1ka wrot= e: > >> > >> On 11/24/21 15:14, Martin Li=C5=A1ka wrote: > >>> It likely miscompiles gcc.dg/loop-unswitch-5.c, working on that.. > >> > >> Fixed that in the updated version. > > > > Function level comments need updating it seems. > > I've done that. > > > > > +static unsigned > > +evaluate_insns (class loop *loop, basic_block *bbs, > > + predicate_vector &predicate_path, > > + auto_bb_flag &reachable_flag) > > +{ > > + auto_vec worklist (loop->num_nodes); > > + worklist.quick_push (bbs[0]); > > ... > > > > so when adding gswitch support the easiest way to make > > > > + FOR_EACH_EDGE (e, ei, bb->succs) > > + { > > ... > > + { > > + worklist.safe_push (dest); > > + dest->flags |=3D reachable_flag; > > > > work is when the gcond/gswitch simplification would mark > > outgoing edges as (non-)executable. For gswitch this > > could be achieved by iterating over the case labels and > > intersecting that with the range while for gcond it's a > > matter of setting an edge flag instead of returning true/false. > > Exactly, it can be quite naturally added to the current patch. > > > I'd call the common function evaluate_control_stmt_using_entry_checks > > or so and invoke it on the last stmt of a block with >=3D 2 outgoing > > edges. > > Yes, I'll do it for the gswitch support patch. > > > > > We still seem to do the simplification work twice, once for costing > > and once for transform, but that's OK for now I guess. > > > > I think you want to clear_aux_for_blocks at the end of the pass. > > Called that. > > > > > Otherwise I like it - it seems you have some TODO around cost > > modeling. Did you try to do gswitch support ontop as I suggested > > to see if the general structure keeps working? > > I vanished and tested the patch. No, I don't have the gswitch support pat= ch > as the current patch was reworked a few times. > > Can we please progress and have installed the suggested patch? I'd like to see the gswitch support - that's what was posted before stage3 close, this patch on its own doesn't seem worth pushing for. That said, I have some comments below (and the already raised ones about how things might need to change with gswitch support). Is it so difficult to develop gswitch support as a separate change ontop of this? > Patch can bootstrap on x86_64-linux-gnu and survives regression tests. +#include that's included unconditionally by system.h +/* The type represents a predicate path leading to a basic block. */ +typedef auto_vec> predicate_vector; +static bool tree_unswitch_single_loop (class loop *, int, + predicate_vector &predicate_path, I think we don't want to pass auto_vec by reference, instead auto_vec shoul= d decay to vec<> when passed around. + unswitch_predicate *predicate =3D new unswitch_predicate (cond, lhs); + if (irange::supports_type_p (TREE_TYPE (lhs)) && CONSTANT_CLASS_P (rhs)) + { + ranger->range_on_edge (predicate->true_range, edge_true, lhs); + predicate->false_range =3D predicate->true_range; - return cond; + if (!predicate->false_range.varying_p () + && !predicate->false_range.undefined_p ()) + predicate->false_range.invert (); + } is that correct? I would guess range_on_edge, for if (a > 10) if (a < 15) /* true */ else /* false */ figures [11, 14] on the true edge of if (a < 15) (considered the unswitch predicate), inverting that yields [0, 10] u [15, +INF] but that's at least sub-optimal for the else range. I think we want to call range_on_edge again to determine the r= ange on the else branch? } -/* Simplifies COND using checks in front of the entry of the LOOP. Just v= ery - simplish (sufficient to prevent us from duplicating loop in unswitching - unnecessarily). */ +static void +combine_range (predicate_vector &predicate_path, tree index, irange &path_range) +{ unless I misread the patch combine_range misses a comment. +evaluate_control_stmt_using_entry_checks (gimple *stmt, + predicate_vector &predicate_path) { so this function for ranger does combine all predicates on the predicate_pa= th but for the symbolic evaluation it looks at the last predicate only? I gue= ss that's because other predicate simplification opportunities are applied alr= eady, correct? But doesn't that mean that the combine_range could be done once when we build the predicate vector instead of for each stmt? I'm just looking at the difference in treating both cases - if we first analyze the = whole unswitching path (including all recursions) then we'd have to simplify all opportunities at once, so iterating over all predicates would make sense. Still merging ranges when pushing the to the predicate vector rather than for each stmt would make sense? We'd then have at most one predicate supported by irange for a specific lhs on the vector? + if (EDGE_COUNT (bb->succs) =3D=3D 2) + { + gcond *cond =3D dyn_cast (last_stmt (bb)); + if (cond !=3D NULL) + { since gcond always has two edges the edge count test is redundant and removing it allows to indent less ;) Richard. > Ready to be installed? > Thanks, > Martin > > > > > Thanks, > > Richard. > > > >> > >> Martin