From 7d7e7aca3bcded9bccc3ebb4c020287ff21ef102 Mon Sep 17 00:00:00 2001 From: Jeff Law Date: Wed, 18 Nov 2015 17:33:27 -0700 Subject: [PATCH] [PATCH][PR tree-optimization/68198] Avoid CFG explosion due to threading PR tree-optimization/68198 * tree-ssa-threadupdate.c (valid_jump_thread_path): Distinguish between threading a multi-way branch and a thread path that contains a multi-way branch. Disallow the case where a path contains a multi-way branch and does not thread a multi-way branch. (thread_through_all_blocks): Update comment. PR tree-optimization/68198 * gcc.dg/tree-ssa/pr66752-3.c: Update expected output for VRP1. * gcc.dg/tree-ssa/pr68198.c: New test. From-SVN: r230586 --- gcc/ChangeLog | 9 +++++ gcc/testsuite/ChangeLog | 6 +++ gcc/testsuite/gcc.dg/tree-ssa/pr66752-3.c | 6 ++- gcc/testsuite/gcc.dg/tree-ssa/pr68198.c | 43 ++++++++++++++++++++ gcc/tree-ssa-threadupdate.c | 49 ++++++++++++++++++----- 5 files changed, 101 insertions(+), 12 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr68198.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 4b788d331e2..26ddcccfbd4 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,12 @@ +2015-11-18 Jeff Law + + PR tree-optimization/68198 + * tree-ssa-threadupdate.c (valid_jump_thread_path): Distinguish + between threading a multi-way branch and a thread path that contains + a multi-way branch. Disallow the case where a path contains a + multi-way branch and does not thread a multi-way branch. + (thread_through_all_blocks): Update comment. + 2015-11-18 Joseph Myers PR c/65083 diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 8109c33cb4b..48f536fc610 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,9 @@ +2015-11-18 Jeff Law + + PR tree-optimization/68198 + * gcc.dg/tree-ssa/pr66752-3.c: Update expected output for VRP1. + * gcc.dg/tree-ssa/pr68198.c: New test. + 2015-11-18 Steven G. Kargl PR fortran/59910 diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr66752-3.c b/gcc/testsuite/gcc.dg/tree-ssa/pr66752-3.c index 577a489dd8c..1f27b1a4c48 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/pr66752-3.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr66752-3.c @@ -32,8 +32,10 @@ foo (int N, int c, int b, int *a) pt--; } -/* There are 3 FSM jump threading opportunities. */ -/* { dg-final { scan-tree-dump-times "FSM" 3 "vrp1"} } */ +/* There are 3 FSM jump threading opportunities, one of which will + get cancelled. */ +/* { dg-final { scan-tree-dump-times "Registering FSM" 3 "vrp1"} } */ +/* { dg-final { scan-tree-dump-times "Cancelling FSM" 1 "vrp1"} } */ /* There should be no assignments or references to FLAG. */ /* { dg-final { scan-tree-dump-not "flag" "optimized"} } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr68198.c b/gcc/testsuite/gcc.dg/tree-ssa/pr68198.c new file mode 100644 index 00000000000..ddd3c76103e --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr68198.c @@ -0,0 +1,43 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-vrp1-details" } */ + +extern void abort (void); + +typedef union tree_node *tree; +union tree_node +{ + int code; + tree chain; + int omp_code; +} +bitmap_head; + +extern int c_omp_predetermined_sharing (tree); + +tree +c_finish_omp_clauses (tree clauses) +{ + tree c, t, *pc = &clauses; + for (pc = &clauses, c = clauses; c; c = *pc) + { + unsigned char remove = 0; + switch (((c->omp_code))) + { + case 1: + if (t->code != 42) + remove = 1; + switch (c_omp_predetermined_sharing (t)) + { + case 2: + abort (); + } + } + if (remove) + *pc = c->chain; + } +} + +/* There are 3 FSM jump threading opportunities, two of which will + get cancelled. */ +/* { dg-final { scan-tree-dump-times "Registering FSM" 3 "vrp1"} } */ +/* { dg-final { scan-tree-dump-times "Cancelling FSM" 2 "vrp1"} } */ diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c index c527206409a..3dd0e4f5fe6 100644 --- a/gcc/tree-ssa-threadupdate.c +++ b/gcc/tree-ssa-threadupdate.c @@ -2370,11 +2370,13 @@ static bool valid_jump_thread_path (vec *path) { unsigned len = path->length (); - bool multiway_branch = false; + bool threaded_multiway_branch = false; + bool multiway_branch_in_path = false; bool threaded_through_latch = false; /* Check that the path is connected and see if there's a multi-way - branch on the path. */ + branch on the path and whether or not a multi-way branch + is threaded. */ for (unsigned int j = 0; j < len - 1; j++) { edge e = (*path)[j]->e; @@ -2394,7 +2396,12 @@ valid_jump_thread_path (vec *path) threaded_through_latch = true; gimple *last = last_stmt (e->dest); - multiway_branch |= (last && gimple_code (last) == GIMPLE_SWITCH); + if (j == len - 2) + threaded_multiway_branch + |= (last && gimple_code (last) == GIMPLE_SWITCH); + else + multiway_branch_in_path + |= (last && gimple_code (last) == GIMPLE_SWITCH); } /* If we are trying to thread through the loop latch to a block in the @@ -2402,8 +2409,33 @@ valid_jump_thread_path (vec *path) irreducible loop. We avoid that unless the jump thread has a multi-way branch, in which case we have deemed it worth losing other loop optimizations later if we can eliminate the multi-way branch. */ - if (!multiway_branch && threaded_through_latch) - return false; + if (!threaded_multiway_branch && threaded_through_latch) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, + "Thread through latch without threading a multiway " + "branch.\n"); + dump_jump_thread_path (dump_file, *path, false); + } + return false; + } + + /* When there is a multi-way branch on the path, then threading can + explode the CFG due to duplicating the edges for that multi-way + branch. So like above, only allow a multi-way branch on the path + if we actually thread a multi-way branch. */ + if (!threaded_multiway_branch && multiway_branch_in_path) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, + "Thread through multiway branch without threading " + "a multiway branch.\n"); + dump_jump_thread_path (dump_file, *path, false); + } + return false; + } return true; } @@ -2494,11 +2526,8 @@ thread_through_all_blocks (bool may_peel_loop_headers) /* Do not jump-thread twice from the same block. */ if (bitmap_bit_p (threaded_blocks, entry->src->index) - /* Verify that the jump thread path is still valid: a - previous jump-thread may have changed the CFG, and - invalidated the current path or the requested jump - thread might create irreducible loops which should - generally be avoided. */ + /* We may not want to realize this jump thread path + for various reasons. So check it first. */ || !valid_jump_thread_path (path)) { /* Remove invalid FSM jump-thread paths. */ -- 2.30.2