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 6EFF03858C83 for ; Wed, 11 Jan 2023 10:52:58 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 6EFF03858C83 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.de 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 1A0E7457D for ; Wed, 11 Jan 2023 10:52:57 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1673434377; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc: mime-version:mime-version:content-type:content-type; bh=ajMxy4bk+JA3mKjjBiREH4EoBzd5fVVXCfjFAxaXi3M=; b=dRTuEDhyZlr4Atcsd8WS2Xxh3hewDd26TJeu+tenYKmjlPN89l/ZQmXx6vQ8vLqLeZxPDs biAGxOjwYwZ8r6+LExFZo4to7HzhbI/kWxvZPmUBUemt7VsOcRcRB6fTBx0KVmyb0JUQP2 nE5961LmdTGhfXXuqB+7uNQyKGGJCKA= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1673434377; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc: mime-version:mime-version:content-type:content-type; bh=ajMxy4bk+JA3mKjjBiREH4EoBzd5fVVXCfjFAxaXi3M=; b=CUj37QxNdC3Dk/Hm1/Vjcwf3iQ78Jzzga2/QoZPHtRRKsXRnFOYNunzvVEmBaP7ETkXNCX YTA2oOzwGqPVSHDA== 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 05FEB13591 for ; Wed, 11 Jan 2023 10:52:57 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id pbQmAAmVvmP4EwAAMHmgww (envelope-from ) for ; Wed, 11 Jan 2023 10:52:56 +0000 Date: Wed, 11 Jan 2023 11:52:56 +0100 (CET) From: Richard Biener To: gcc-patches@gcc.gnu.org Subject: [PATCH] tree-optimization/108353 - copyprop iteration order MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Message-Id: <20230111105257.05FEB13591@imap2.suse-dmz.suse.de> X-Spam-Status: No, score=-11.8 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: After recent improvements to copyprop to catch more constants it shows that the current iteration order prefering forward progress over iterating doesn't make much sense for an SSA propagator. The following instead first iterates cycles which makes sure to not start with optimistically constant PHIs out of cycles that optimistically do not exit. Bootstrapped and tested on x86_64-unknown-linux-gnu, pushed. PR tree-optimization/108353 * tree-ssa-propagate.cc (cfg_blocks_back, ssa_edge_worklist_back): Remove. (add_ssa_edge): Simplify. (add_control_edge): Likewise. (ssa_prop_init): Likewise. (ssa_prop_fini): Likewise. (ssa_propagation_engine::ssa_propagate): Likewise. * gcc.dg/tree-ssa/ssa-copyprop-3.c: New testcase. --- .../gcc.dg/tree-ssa/ssa-copyprop-3.c | 38 +++++++++++++++++++ gcc/tree-ssa-propagate.cc | 35 ++--------------- 2 files changed, 42 insertions(+), 31 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-copyprop-3.c diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-copyprop-3.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-copyprop-3.c new file mode 100644 index 00000000000..d22b39294ab --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-copyprop-3.c @@ -0,0 +1,38 @@ +/* { dg-do link } */ +/* { dg-require-effective-target int32plus } */ +/* { dg-options "-O -fdump-tree-copyprop2" } */ + +#include +enum { a } b(); +int d; +int e; +int f; +void foo(); +[[gnu::noipa]] +void bar49_(void){} +[[gnu::noipa]] +void(c)(void){} +static short g(int h, int i) { + int j = -1420678603, k = 1; + if (h) + for (; j < INT_MAX-18; j = j + 9) { + f = 0; + for (; f <= 1; c()) + k = 90; + } + i = k; + for (; e; ++e) { + if (i) + continue; + foo(); + i = b(); + } + return 4; +} +int l() { + bar49_(); + return 1; +} +int main() { d = d || g(d, l()); } + +/* { dg-final { scan-tree-dump-not "foo" "copyprop2" } } */ diff --git a/gcc/tree-ssa-propagate.cc b/gcc/tree-ssa-propagate.cc index 472c4bcb540..76708ca185f 100644 --- a/gcc/tree-ssa-propagate.cc +++ b/gcc/tree-ssa-propagate.cc @@ -113,7 +113,6 @@ order by visiting in bit-order. We use two worklists to first make forward progress before iterating. */ static bitmap cfg_blocks; -static bitmap cfg_blocks_back; static int *bb_to_cfg_order; static int *cfg_order_to_bb; @@ -123,7 +122,6 @@ static int *cfg_order_to_bb; UID in a bitmap. UIDs order stmts in execution order. We use two worklists to first make forward progress before iterating. */ static bitmap ssa_edge_worklist; -static bitmap ssa_edge_worklist_back; static vec uid_to_stmt; /* Current RPO index in the iteration. */ @@ -159,12 +157,7 @@ add_ssa_edge (tree var) & EDGE_EXECUTABLE)) continue; - bitmap worklist; - if (bb_to_cfg_order[gimple_bb (use_stmt)->index] < curr_order) - worklist = ssa_edge_worklist_back; - else - worklist = ssa_edge_worklist; - if (bitmap_set_bit (worklist, gimple_uid (use_stmt))) + if (bitmap_set_bit (ssa_edge_worklist, gimple_uid (use_stmt))) { uid_to_stmt[gimple_uid (use_stmt)] = use_stmt; if (dump_file && (dump_flags & TDF_DETAILS)) @@ -193,10 +186,7 @@ add_control_edge (edge e) e->flags |= EDGE_EXECUTABLE; int bb_order = bb_to_cfg_order[bb->index]; - if (bb_order < curr_order) - bitmap_set_bit (cfg_blocks_back, bb_order); - else - bitmap_set_bit (cfg_blocks, bb_order); + bitmap_set_bit (cfg_blocks, bb_order); if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "Adding destination of edge (%d -> %d) to worklist\n", @@ -380,9 +370,7 @@ ssa_prop_init (void) /* Worklists of SSA edges. */ ssa_edge_worklist = BITMAP_ALLOC (NULL); - ssa_edge_worklist_back = BITMAP_ALLOC (NULL); bitmap_tree_view (ssa_edge_worklist); - bitmap_tree_view (ssa_edge_worklist_back); /* Worklist of basic-blocks. */ bb_to_cfg_order = XNEWVEC (int, last_basic_block_for_fn (cfun) + 1); @@ -392,7 +380,6 @@ ssa_prop_init (void) for (int i = 0; i < n; ++i) bb_to_cfg_order[cfg_order_to_bb[i]] = i; cfg_blocks = BITMAP_ALLOC (NULL); - cfg_blocks_back = BITMAP_ALLOC (NULL); /* Initially assume that every edge in the CFG is not executable. (including the edges coming out of the entry block). Mark blocks @@ -430,11 +417,9 @@ static void ssa_prop_fini (void) { BITMAP_FREE (cfg_blocks); - BITMAP_FREE (cfg_blocks_back); free (bb_to_cfg_order); free (cfg_order_to_bb); BITMAP_FREE (ssa_edge_worklist); - BITMAP_FREE (ssa_edge_worklist_back); uid_to_stmt.release (); } @@ -453,8 +438,7 @@ ssa_propagation_engine::ssa_propagate (void) curr_order = 0; /* Iterate until the worklists are empty. We iterate both blocks - and stmts in RPO order, using sets of two worklists to first - complete the current iteration before iterating over backedges. + and stmts in RPO order, prioritizing backedge processing. Seed the algorithm by adding the successors of the entry block to the edge worklist. */ edge e; @@ -471,18 +455,7 @@ ssa_propagation_engine::ssa_propagate (void) int next_stmt_uid = (bitmap_empty_p (ssa_edge_worklist) ? -1 : bitmap_first_set_bit (ssa_edge_worklist)); if (next_block_order == -1 && next_stmt_uid == -1) - { - if (bitmap_empty_p (cfg_blocks_back) - && bitmap_empty_p (ssa_edge_worklist_back)) - break; - - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "Regular worklists empty, now processing " - "backedge destinations\n"); - std::swap (cfg_blocks, cfg_blocks_back); - std::swap (ssa_edge_worklist, ssa_edge_worklist_back); - continue; - } + break; int next_stmt_bb_order = -1; gimple *next_stmt = NULL; -- 2.35.3