From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out2.suse.de (smtp-out2.suse.de [195.135.220.29]) by sourceware.org (Postfix) with ESMTPS id 8F8233858401 for ; Wed, 1 Dec 2021 14:10:35 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 8F8233858401 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=suse.cz Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.cz Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by smtp-out2.suse.de (Postfix) with ESMTPS id 6140A1FD5A; Wed, 1 Dec 2021 14:10:34 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1638367834; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=EfcUUcLH/vdPHiZfcZUwkcGIZJIZ4Pd5wLIaVngveV0=; b=eAxHt60fvt709gtzszL37RJ89veC1qPzt9Py0bSfe5sTk6SclHodH4ZO1UZh4q3V1DNYwU yBgLysU1qBEhrqbq+M4sjUaWcC9tDl4r/gRZEdGGrYfF5ptZQSHfDc/56jDZP2c4/5q+QE g2D46nBgZUHH/cSp/rvkWuy3rpAUEY4= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1638367834; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=EfcUUcLH/vdPHiZfcZUwkcGIZJIZ4Pd5wLIaVngveV0=; b=yKX5QtC0XEsVQOGhShwkwJXZa6QUKThRt0CVT34kAaEzIm3vrjSaX2K40MaZXLs3r3r+en xFPb41eZDH8onFDw== Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by imap2.suse-dmz.suse.de (Postfix) with ESMTPS id 4CFD113D0B; Wed, 1 Dec 2021 14:10:34 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id RGS2EVqCp2FMWAAAMHmgww (envelope-from ); Wed, 01 Dec 2021 14:10:34 +0000 Message-ID: Date: Wed, 1 Dec 2021 15:10:33 +0100 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.3.2 Subject: Re: [PATCH] Loop unswitching: support gswitch statements. Content-Language: en-US To: Richard Biener Cc: GCC Patches 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> From: =?UTF-8?Q?Martin_Li=c5=a1ka?= In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-6.7 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, NICE_REPLY_A, 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:10:37 -0000 On 11/30/21 12:17, Richard Biener wrote: > On Mon, Nov 29, 2021 at 1:45 PM Martin Liška wrote: >> >> On 11/26/21 09:12, Richard Biener wrote: >>> On Wed, Nov 24, 2021 at 3:32 PM Martin Liška wrote: >>>> >>>> On 11/24/21 15:14, Martin Liška 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 |= 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 >= 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 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? I'm going to work on that in the upcoming days. When are you leaving for the Christmas holidays :P ? > >> 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_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 should > decay to vec<> when passed around. Ok. > > + unswitch_predicate *predicate = 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 = 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 range > on the else branch? No, as shown in the previous emails, Ranger is CFG sensitive and we should rely on our irange merging. > > } > > -/* Simplifies COND using checks in front of the entry of the LOOP. Just very > - 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_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 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? Yes, we can do better. I have a patch that appends to the path, and merges with the previous irange that has equal LHS. Doing that, we can only first the last predicate for a LHS and this one would have precise range (merged with all previous). > > + if (EDGE_COUNT (bb->succs) == 2) > + { > + gcond *cond = dyn_cast (last_stmt (bb)); > + if (cond != 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