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 9940B385840E for ; Wed, 24 Nov 2021 10:48:24 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 9940B385840E 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 6D7941FD37; Wed, 24 Nov 2021 10:48:23 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1637750903; 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=TzNV71E4+08I1LFI6YB9kejKrmIq70ITTIdhUUUjlhE=; b=JVGC6u+nGHxs+mXLRknjk0iE1t74VG4BDRblhxLOlcLKFY2W9Q2pcJbYSGO0WrXK8IYK5v gnB1mccJrM2ayISlMhpS9IIpuY0hXA0VlscFtM3mtDtMU7YblALuuGBfVBjnOfZ8fI1vC4 xpt3ydVzhxMaZKwuxscat0xL0AgQHpc= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1637750903; 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=TzNV71E4+08I1LFI6YB9kejKrmIq70ITTIdhUUUjlhE=; b=Otz1VQt7lx04VZAB4r01f2ikcu4bMtWcmMRy3/4oavnko/NUDIy+bVMer1wCrLWA00o12E argIKMjacoekPXCA== 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 56B7013F05; Wed, 24 Nov 2021 10:48:23 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id 62FNFHcYnmGEbwAAMHmgww (envelope-from ); Wed, 24 Nov 2021 10:48:23 +0000 Message-ID: <3a07ef98-d05f-dc07-2e36-a2b4ffd52936@suse.cz> Date: Wed, 24 Nov 2021 11:48:22 +0100 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.3.0 Subject: Re: [PATCH] Loop unswitching: support gswitch statements. Content-Language: en-US To: Richard Biener , Aldy Hernandez Cc: GCC Patches 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> 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=-7.6 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, 24 Nov 2021 10:48:26 -0000 On 11/24/21 09:00, Richard Biener wrote: > On Tue, Nov 23, 2021 at 5:36 PM Martin Liška wrote: >> >> On 11/23/21 16:20, Martin Liška wrote: >>> Sure, so for e.g. case 1 ... 5 we would need to create a new unswitch_predicate >>> with 1 <= index && index <= 5 tree predicate (and the corresponding irange range). >>> Later once we unswitch on it, we should use a special unreachable_flag that will >>> be used for marking of dead edges (similarly how we fold gconds to boolean_{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 select 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. > 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_flag (we can't fold it away as shown in the original patch attempt). > Looking somewhat at the sources it seems like we "simply" need to do what > 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 would still > stick to a basic interface that marks not taken outgoing edges of a stmt based > on the set of versioning predicates. Lemme try working on another version of the patch. Martin > > Richard. > >> >> Martin