From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1666) id 798153857C51; Wed, 11 Jan 2023 10:53:28 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 798153857C51 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1673434408; bh=Pe9MbIS//MX+s8VQqeDhj0liz/mTNBacXTG+tslHNLg=; h=From:To:Subject:Date:From; b=nXONGOePXSd/SOtaLNY6DU/noKUzV4O5UESflGLOGjbuw33X9O4y+FBQzNMG8KbFk psqRaIOefqurofOz1L35LJ0M7tmnL5q0An81y0QM37eYzql2WwczWjR09AxBjC4GRW ov/N9Cs5Pro5E5VEdPFW/BoVux4iMOyOhi0OADlE= MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Richard Biener To: gcc-cvs@gcc.gnu.org Subject: [gcc r13-5102] tree-optimization/108353 - copyprop iteration order X-Act-Checkin: gcc X-Git-Author: Richard Biener X-Git-Refname: refs/heads/master X-Git-Oldrev: 2ce074a7f858a1cd30ff68ec636dad9be218e04b X-Git-Newrev: 445a48a226ffd530b37bcdc13b6bdca94ba2e122 Message-Id: <20230111105328.798153857C51@sourceware.org> Date: Wed, 11 Jan 2023 10:53:28 +0000 (GMT) List-Id: https://gcc.gnu.org/g:445a48a226ffd530b37bcdc13b6bdca94ba2e122 commit r13-5102-g445a48a226ffd530b37bcdc13b6bdca94ba2e122 Author: Richard Biener Date: Wed Jan 11 09:32:36 2023 +0100 tree-optimization/108353 - copyprop iteration order 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. 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. Diff: --- gcc/testsuite/gcc.dg/tree-ssa/ssa-copyprop-3.c | 38 ++++++++++++++++++++++++++ gcc/tree-ssa-propagate.cc | 35 +++--------------------- 2 files changed, 42 insertions(+), 31 deletions(-) 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;