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 AAEB03858401 for ; Wed, 1 Dec 2021 14:20:03 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org AAEB03858401 Received: by mail-ed1-x52d.google.com with SMTP id e3so102421312edu.4 for ; Wed, 01 Dec 2021 06:20: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=V2QWM7teEQgIrlSkZgzZ/+QrH8QpWkQFtcil9XSyU+E=; b=hHkqgNqQFF9IajHrwo9V9BXiW/VV1Pwj1eU7QlqGAkm79fY42ddJ5D7lzeCaJKkbGL Jby8zdW61VUQWHAQS+Ktcs4ZKqiX4m6b35GzcIBxRGThcMhkPxX6Q2IoRc7QIWJQU8XA F1ekGExZN3BPMh9AlVC7cca8xOVlnphrLlffSpHJcFW9rXcTyC9COT8ZGPCBi4iilZdt uYVXHs7xEg4NX2k9JObcPLAixaqRBNejuQ8j/JEASTWzfERY86tmW+kBDBvorIFvdi2N Gss2Q4lDThmFqiFIkZX8luGaYGcFx9nia2bnicBvuRvzTgb0yTGlxXVDbRZqNSgSApsD WEng== X-Gm-Message-State: AOAM531BH1fGj9RWJZSzUQk8wN8exfvXe8KCYRBMZduQRKhFXaH/sBsi +f8hk2y2IhUxIsjFzU5QJnzCjGninog/6nEZdL8= X-Google-Smtp-Source: ABdhPJxxMnOO3EKjrb8+1gS6cMQhSGcZBGF1ExHjeFPQbVnoGpB+Nu+Bpn9SiWeos0Ck4HafoW0rrjrPiq0/kZ4+3kE= X-Received: by 2002:a17:907:6d28:: with SMTP id sa40mr7434570ejc.201.1638368402582; Wed, 01 Dec 2021 06:20:02 -0800 (PST) MIME-Version: 1.0 References: <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: From: Richard Biener Date: Wed, 1 Dec 2021 15:19:51 +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: Wed, 01 Dec 2021 14:20:05 -0000 On Wed, Dec 1, 2021 at 3:10 PM Martin Li=C5=A1ka wrote: > > On 11/30/21 12:17, Richard Biener wrote: > > On Mon, Nov 29, 2021 at 1:45 PM Martin Li=C5=A1ka wrot= e: > >> > >> On 11/26/21 09:12, Richard Biener wrote: > >>> On Wed, Nov 24, 2021 at 3:32 PM Martin Li=C5=A1ka wr= ote: > >>>> > >>>> 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 = patch > >> 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 sta= ge3 > > 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? > > I'm going to work on that in the upcoming days. When are you leaving for = the Christmas > holidays :P ? Wednesday next week is my first day off, but I might peek into mails now and then. > > > >> Patch can bootstrap on x86_64-linux-gnu and survives regression tests. > > > > +#include > > > > that's included unconditionally by system.h > > Good. > > > > > +/* The type represents a predicate path leading to a basic block. */ > > +typedef auto_vec> predicate_vect= or; > > > > +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 s= hould > > decay to vec<> when passed around. > > Ok. > > > > > + unswitch_predicate *predicate =3D new unswitch_predicate (cond, lhs)= ; > > + if (irange::supports_type_p (TREE_TYPE (lhs)) && CONSTANT_CLASS_P (r= hs)) > > + { > > + 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 t= he range > > on the else branch? > > No, as shown in the previous emails, Ranger is CFG sensitive and we shoul= d rely > on our irange merging. I don't understand. You do > > + unswitch_predicate *predicate =3D new unswitch_predicate (cond, lhs)= ; > > + if (irange::supports_type_p (TREE_TYPE (lhs)) && CONSTANT_CLASS_P (r= hs)) > > + { > > + 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 (); > > + } which is compute the range of 'lhs' on edge_true into predicate->true_range= , assign that same range to ->false_range and then invert it to get the range on the false_edge. What I am saying is that for better precision you should do ranger->range_on_edge (predicate->false_range, edge_false, lhs); rather than prematurely optimize this to the inversion of the true range since yes, ranger is CFG sensitive and only the _last_ predicate on a long CFG path is actually inverted. What am I missing? > > > > > } > > > > -/* Simplifies COND using checks in front of the entry of the LOOP. Ju= st very > > - simplish (sufficient to prevent us from duplicating loop in unswitc= hing > > - 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_p= ath) > > { > > > > so this function for ranger does combine all predicates on the predicat= e_path > > but for the symbolic evaluation it looks at the last predicate only? > > Yes. > > > I guess > > that's because other predicate simplification opportunities are applied= already, > > correct? > > Exactly. > > > 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 sens= e. > > Still merging ranges when pushing the to the predicate vector rather th= an > > for each stmt would make sense? We'd then have at most one predicate > > supported by irange for a specific lhs on the vector? > > Yes, we can do better. I have a patch that appends to the path, and merge= s > with the previous irange that has equal LHS. Doing that, we can only firs= t the > last predicate for a LHS and this one would have precise range (merged wi= th all previous). > > > > > + 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 ;) > > Lemme work on the gswitch support now. > > Martin > > > > > Richard. > > > > > >> Ready to be installed? > >> Thanks, > >> Martin > >> > >>> > >>> Thanks, > >>> Richard. > >>> > >>>> > >>>> Martin >