From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out1.suse.de (smtp-out1.suse.de [195.135.223.130]) by sourceware.org (Postfix) with ESMTPS id 1AA96384604F for ; Fri, 5 Apr 2024 13:13:16 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 1AA96384604F Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.de ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 1AA96384604F Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=195.135.223.130 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1712322798; cv=none; b=dmc3YvqFgDglhfmV1+dUPkmSrkqVqlsZwCtXHhygK/otIJ6RJnblOgn13DJVzI+4G/0p78qwTbS/EPYnAc7dJKBMpD9iC8gbCm6W5xMZvXyq84UtnZQf7TQTRBoJapQhnQ8HIv7Z1rficb4q4W52dZFyn/teDvV9/AsB3KMwDiA= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1712322798; c=relaxed/simple; bh=hOFeVA7xkIgncWzDgT7V/lp/AIedRHwQN9jl8dsB9k4=; h=DKIM-Signature:DKIM-Signature:DKIM-Signature:DKIM-Signature:Date: From:To:Subject:MIME-Version:Message-Id; b=DKxpr1cQJ7Xnyt5bYIYh5FTYBQ0guUoTrmDXfBgeA8P0unUm4SBFjqSSE8mXKRn065ewIoFmrq4dkfdRbFxDcxhiQXG9Sjtdiq1+/1hZ2R2vo9QcauMHLiGcvW8HAYkDr6tsG9SDp8kyZpDKjuY0wp/6I/md/XQFet3PofyUdIc= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from imap2.dmz-prg2.suse.org (imap2.dmz-prg2.suse.org [IPv6:2a07:de40:b281:104:10:150:64:98]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by smtp-out1.suse.de (Postfix) with ESMTPS id 099C021A3E; Fri, 5 Apr 2024 13:13:15 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1712322795; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=iO/mmzOJQH1qeVhFw/e3VcZ4yQjFDSL73JtAxaMaa2A=; b=u/g15qGMcaD3zx4kWnR+aYBWlzszhbAAOTqLulszAdH4dCRNGO8rJti9h/qWv6rODwmz08 8EIYWldW3M8qrxONNdzCG4SWpPC54HHmWaxpfLDsEmk5YbBxbdBqKyauWpk2j7vNtEHT9g 7EU3teeGjpOH7QkCOKH/pjpg5zl2HkE= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1712322795; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=iO/mmzOJQH1qeVhFw/e3VcZ4yQjFDSL73JtAxaMaa2A=; b=5G9g94EMXwTnqKJe8hLws/jFVsgWRygrF5Khm7DTvz4HVoJkdbvBWsnw+uTpV9YQNjGR43 XoVAY1L15H9Rd9Bw== Authentication-Results: smtp-out1.suse.de; dkim=pass header.d=suse.de header.s=susede2_rsa header.b="u/g15qGM"; dkim=pass header.d=suse.de header.s=susede2_ed25519 header.b=5G9g94EM DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1712322795; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=iO/mmzOJQH1qeVhFw/e3VcZ4yQjFDSL73JtAxaMaa2A=; b=u/g15qGMcaD3zx4kWnR+aYBWlzszhbAAOTqLulszAdH4dCRNGO8rJti9h/qWv6rODwmz08 8EIYWldW3M8qrxONNdzCG4SWpPC54HHmWaxpfLDsEmk5YbBxbdBqKyauWpk2j7vNtEHT9g 7EU3teeGjpOH7QkCOKH/pjpg5zl2HkE= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1712322795; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=iO/mmzOJQH1qeVhFw/e3VcZ4yQjFDSL73JtAxaMaa2A=; b=5G9g94EMXwTnqKJe8hLws/jFVsgWRygrF5Khm7DTvz4HVoJkdbvBWsnw+uTpV9YQNjGR43 XoVAY1L15H9Rd9Bw== Received: from imap2.dmz-prg2.suse.org (localhost [127.0.0.1]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by imap2.dmz-prg2.suse.org (Postfix) with ESMTPS id DEC1A139F1; Fri, 5 Apr 2024 13:13:14 +0000 (UTC) Received: from dovecot-director2.suse.de ([2a07:de40:b281:106:10:150:64:167]) by imap2.dmz-prg2.suse.org with ESMTPSA id ICbCNOr4D2ZzKAAAn2gu4w (envelope-from ); Fri, 05 Apr 2024 13:13:14 +0000 Date: Fri, 5 Apr 2024 15:13:10 +0200 (CEST) From: Richard Biener To: gcc-patches@gcc.gnu.org cc: Jan Hubicka Subject: [PATCH 2/3] Add get_loop_body_in_rpo MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Message-Id: <20240405131314.DEC1A139F1@imap2.dmz-prg2.suse.org> X-Spam-Score: -4.51 X-Rspamd-Action: no action X-Rspamd-Queue-Id: 099C021A3E X-Spam-Level: X-Rspamd-Server: rspamd2.dmz-prg2.suse.org X-Spamd-Result: default: False [-4.51 / 50.00]; BAYES_HAM(-3.00)[100.00%]; NEURAL_HAM_LONG(-1.00)[-1.000]; R_DKIM_ALLOW(-0.20)[suse.de:s=susede2_rsa,suse.de:s=susede2_ed25519]; NEURAL_HAM_SHORT(-0.20)[-1.000]; MIME_GOOD(-0.10)[text/plain]; MX_GOOD(-0.01)[]; RECEIVED_SPAMHAUS_BLOCKED_OPENRESOLVER(0.00)[2a07:de40:b281:106:10:150:64:167:received]; RBL_SPAMHAUS_BLOCKED_OPENRESOLVER(0.00)[2a07:de40:b281:104:10:150:64:98:from]; RCVD_VIA_SMTP_AUTH(0.00)[]; ARC_NA(0.00)[]; FUZZY_BLOCKED(0.00)[rspamd.com]; MIME_TRACE(0.00)[0:+]; MISSING_XM_UA(0.00)[]; RCVD_TLS_ALL(0.00)[]; RCPT_COUNT_TWO(0.00)[2]; TO_DN_SOME(0.00)[]; FROM_EQ_ENVFROM(0.00)[]; FROM_HAS_DN(0.00)[]; DWL_DNSWL_BLOCKED(0.00)[suse.de:dkim]; RCVD_COUNT_TWO(0.00)[2]; TO_MATCH_ENVRCPT_ALL(0.00)[]; DBL_BLOCKED_OPENRESOLVER(0.00)[imap2.dmz-prg2.suse.org:helo,imap2.dmz-prg2.suse.org:rdns,suse.de:dkim]; DKIM_SIGNED(0.00)[suse.de:s=susede2_rsa,suse.de:s=susede2_ed25519]; DKIM_TRACE(0.00)[suse.de:+] X-Spam-Status: No, score=-11.5 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,SPF_HELO_NONE,SPF_PASS,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: The following adds another get_loop_body variant, one to get blocks in RPO. Bootstrapped on x86_64-unknown-linux-gnu, testing in progress. * cfgloop.h (get_loop_body_in_rpo): Declare. * cfgloop.cc (get_loop_body_in_rpo): Compute loop body in RPO. --- gcc/cfgloop.cc | 68 ++++++++++++++++++++++++++++++++++++++++++++++++++ gcc/cfgloop.h | 1 + 2 files changed, 69 insertions(+) diff --git a/gcc/cfgloop.cc b/gcc/cfgloop.cc index 5202c3865d1..d79a006554f 100644 --- a/gcc/cfgloop.cc +++ b/gcc/cfgloop.cc @@ -1021,6 +1021,74 @@ get_loop_body_in_bfs_order (const class loop *loop) return blocks; } +/* Get the body of LOOP in FN in reverse post order. */ + +basic_block * +get_loop_body_in_rpo (function *fn, const class loop *loop) +{ + auto_vec stack (loop->num_nodes + 1); + auto_bb_flag visited (fn); + + basic_block *blocks = XNEWVEC (basic_block, loop->num_nodes); + int rev_post_order_num = loop->num_nodes - 1; + + /* Find a block leading to the loop header. */ + edge_iterator ei; + edge e; + FOR_EACH_EDGE (e, ei, loop->header->preds) + if (!flow_bb_inside_loop_p (loop, e->src)) + break; + basic_block preheader = e->src; + + stack.quick_push (ei_start (preheader->succs)); + + while (!stack.is_empty ()) + { + basic_block src; + basic_block dest; + + /* Look at the edge on the top of the stack. */ + edge_iterator ei = stack.last (); + src = ei_edge (ei)->src; + dest = ei_edge (ei)->dest; + + /* Check if the edge destination has been visited yet. */ + if (flow_bb_inside_loop_p (loop, dest) + && ! (dest->flags & visited)) + { + /* Mark that we have visited the destination. */ + dest->flags |= visited; + + if (EDGE_COUNT (dest->succs) > 0) + /* Since the DEST node has been visited for the first + time, check its successors. */ + stack.quick_push (ei_start (dest->succs)); + else + /* There are no successors for the DEST node so record + the block. */ + blocks[rev_post_order_num--] = dest; + } + else + { + if (ei_one_before_end_p (ei) + && src != preheader) + /* There are no more successors for the SRC node + so record the block. */ + blocks[rev_post_order_num--] = src; + + if (!ei_one_before_end_p (ei)) + ei_next (&stack.last ()); + else + stack.pop (); + } + } + + for (int i = rev_post_order_num + 1; i < (int) loop->num_nodes; ++i) + blocks[i]->flags &= ~visited; + + return blocks; +} + /* Hash function for struct loop_exit. */ hashval_t diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h index 30b5e40d0d9..42f3079102d 100644 --- a/gcc/cfgloop.h +++ b/gcc/cfgloop.h @@ -385,6 +385,7 @@ extern basic_block *get_loop_body_in_custom_order (const class loop *, int (*) (const void *, const void *)); extern basic_block *get_loop_body_in_custom_order (const class loop *, void *, int (*) (const void *, const void *, void *)); +extern basic_block *get_loop_body_in_rpo (function *, const class loop *); extern auto_vec get_loop_exit_edges (const class loop *, basic_block * = NULL); extern edge single_exit (const class loop *); -- 2.35.3