With the patch for PR85275 I throttled loop-header copying too much. The following reverts that patch and instead adds heuristics to should_duplicate_loop_header_p as to _not_ copy exit tests that are based on non-IV/invariant tests. Since CH runs before any LIM we have to keep track of what is invariant ourselves. Then it's also easy enough to see what tests are based on IVs without resorting to SCEV which would be limited in some cases as well.
Bootstrapped and tested on x86_64-unknown-linux-gnu, applied to trunk. Richard. 2018-12-19 Richard Biener <rguent...@suse.de> PR tree-optimization/88533 Revert 2018-04-30 Richard Biener <rguent...@suse.de> PR tree-optimization/28364 PR tree-optimization/85275 * tree-ssa-loop-ch.c (ch_base::copy_headers): Stop after copying first exit test. * gcc.dg/tree-ssa/ssa-dom-thread-7.c: Adjust. * tree-ssa-loop-ch.c: Include tree-phinodes.h and ssa-iterators.h. (should_duplicate_loop_header_p): Track whether stmt compute loop invariants or values based on IVs. Apart from the original loop header only duplicate blocks with exit tests that are based on IVs or invariants. * gcc.dg/tree-ssa/copy-headers-6.c: New testcase. * gcc.dg/tree-ssa/copy-headers-7.c: Likewise. * gcc.dg/tree-ssa/ivopt_mult_1.c: Un-XFAIL. * gcc.dg/tree-ssa/ivopt_mult_2.c: Likewise. Index: gcc/testsuite/gcc.dg/tree-ssa/copy-headers-6.c =================================================================== --- gcc/testsuite/gcc.dg/tree-ssa/copy-headers-6.c (nonexistent) +++ gcc/testsuite/gcc.dg/tree-ssa/copy-headers-6.c (working copy) @@ -0,0 +1,16 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-ch2-details" } */ + +int is_sorted(int *a, int n) +{ + for (int i = 0; i < n - 1; i++) + if (a[i] > 0) + return 0; + return 1; +} + +/* Verify we apply loop header copying but only copy the IV test and + not the alternate exit test. */ + +/* { dg-final { scan-tree-dump "is now do-while loop" "ch2" } } */ +/* { dg-final { scan-tree-dump-times " if " 3 "ch2" } } */ Index: gcc/testsuite/gcc.dg/tree-ssa/copy-headers-7.c =================================================================== --- gcc/testsuite/gcc.dg/tree-ssa/copy-headers-7.c (nonexistent) +++ gcc/testsuite/gcc.dg/tree-ssa/copy-headers-7.c (working copy) @@ -0,0 +1,16 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-ch2-details --param logical-op-non-short-circuit=0" } */ + +int is_sorted(int *a, int n, int m, int k) +{ + for (int i = 0; i < n - 1 && m && k > i; i++) + if (a[i] > a[i + 1]) + return 0; + return 1; +} + +/* Verify we apply loop header copying but only copy the IV tests and + the invariant test, not the alternate exit test. */ + +/* { dg-final { scan-tree-dump "is now do-while loop" "ch2" } } */ +/* { dg-final { scan-tree-dump-times "Will duplicate bb" 3 "ch2" } } */ Index: gcc/testsuite/gcc.dg/tree-ssa/ivopt_mult_1.c =================================================================== --- gcc/testsuite/gcc.dg/tree-ssa/ivopt_mult_1.c (revision 267232) +++ gcc/testsuite/gcc.dg/tree-ssa/ivopt_mult_1.c (working copy) @@ -20,4 +20,4 @@ long foo(long* p, long* p2, int N1, int return s; } -/* { dg-final { scan-tree-dump-times "Replacing" 1 "ivopts" { xfail *-*-* } } } */ +/* { dg-final { scan-tree-dump-times "Replacing" 1 "ivopts" } } */ Index: gcc/testsuite/gcc.dg/tree-ssa/ivopt_mult_2.c =================================================================== --- gcc/testsuite/gcc.dg/tree-ssa/ivopt_mult_2.c (revision 267232) +++ gcc/testsuite/gcc.dg/tree-ssa/ivopt_mult_2.c (working copy) @@ -21,4 +21,4 @@ long foo(long* p, long* p2, int N1, int return s; } -/* { dg-final { scan-tree-dump-times "Replacing" 2 "ivopts" { xfail *-*-* } } } */ +/* { dg-final { scan-tree-dump-times "Replacing" 2 "ivopts" } } */ Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c =================================================================== --- gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c (revision 267232) +++ gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c (working copy) @@ -2,7 +2,7 @@ /* { dg-options "-O2 -fdump-tree-thread1-stats -fdump-tree-thread2-stats -fdump-tree-dom2-stats -fdump-tree-thread3-stats -fdump-tree-dom3-stats -fdump-tree-vrp2-stats -fno-guess-branch-probability" } */ /* { dg-final { scan-tree-dump "Jumps threaded: 16" "thread1" } } */ /* { dg-final { scan-tree-dump "Jumps threaded: 9" "thread2" } } */ -/* { dg-final { scan-tree-dump "Jumps threaded: 1" "dom2" } } */ +/* { dg-final { scan-tree-dump-not "Jumps threaded" "dom2" } } */ /* aarch64 has the highest CASE_VALUES_THRESHOLD in GCC. It's high enough to change decisions in switch expansion which in turn can expose new jump threading opportunities. Skip the later tests on aarch64. */ Index: gcc/tree-ssa-loop-ch.c =================================================================== --- gcc/tree-ssa-loop-ch.c (revision 267232) +++ gcc/tree-ssa-loop-ch.c (working copy) @@ -34,6 +34,8 @@ along with GCC; see the file COPYING3. #include "tree-ssa-scopedtables.h" #include "tree-ssa-threadedge.h" #include "tree-ssa-sccvn.h" +#include "tree-phinodes.h" +#include "ssa-iterators.h" #include "params.h" /* Duplicates headers of loops if they are small enough, so that the statements @@ -50,7 +52,6 @@ should_duplicate_loop_header_p (basic_bl int *limit) { gimple_stmt_iterator bsi; - gimple *last; gcc_assert (!header->aux); @@ -99,8 +100,8 @@ should_duplicate_loop_header_p (basic_bl return false; } - last = last_stmt (header); - if (gimple_code (last) != GIMPLE_COND) + gcond *last = dyn_cast <gcond *> (last_stmt (header)); + if (!last) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, @@ -109,10 +110,24 @@ should_duplicate_loop_header_p (basic_bl return false; } - /* Count number of instructions and punt on calls. */ + for (gphi_iterator psi = gsi_start_phis (header); !gsi_end_p (psi); + gsi_next (&psi)) + { + gphi *phi = psi.phi (); + tree res = gimple_phi_result (phi); + if (INTEGRAL_TYPE_P (TREE_TYPE (res)) + || POINTER_TYPE_P (TREE_TYPE (res))) + gimple_set_uid (phi, 1 /* IV */); + else + gimple_set_uid (phi, 0); + } + + /* Count number of instructions and punt on calls. + Populate stmts INV/IV flag to later apply heuristics to the + kind of conditions we want to copy. */ for (bsi = gsi_start_bb (header); !gsi_end_p (bsi); gsi_next (&bsi)) { - last = gsi_stmt (bsi); + gimple *last = gsi_stmt (bsi); if (gimple_code (last) == GIMPLE_LABEL) continue; @@ -142,7 +157,52 @@ should_duplicate_loop_header_p (basic_bl header->index); return false; } + + /* Classify the stmt based on whether its computation is based + on a IV or whether it is invariant in the loop. */ + gimple_set_uid (last, 0); + if (!gimple_vuse (last)) + { + bool inv = true; + bool iv = false; + ssa_op_iter i; + tree op; + FOR_EACH_SSA_TREE_OPERAND (op, last, i, SSA_OP_USE) + if (!SSA_NAME_IS_DEFAULT_DEF (op) + && flow_bb_inside_loop_p (loop, + gimple_bb (SSA_NAME_DEF_STMT (op)))) + { + if (!(gimple_uid (SSA_NAME_DEF_STMT (op)) & 2 /* INV */)) + inv = false; + if (gimple_uid (SSA_NAME_DEF_STMT (op)) & 1 /* IV */) + iv = true; + } + gimple_set_uid (last, (iv ? 1 : 0) | (inv ? 2 : 0)); + } } + + /* If the condition tests a non-IV loop variant we do not want to rotate + the loop further. Unless this is the original loop header. */ + tree lhs = gimple_cond_lhs (last); + tree rhs = gimple_cond_rhs (last); + if (header != loop->header + && ((TREE_CODE (lhs) == SSA_NAME + && !SSA_NAME_IS_DEFAULT_DEF (lhs) + && flow_bb_inside_loop_p (loop, gimple_bb (SSA_NAME_DEF_STMT (lhs))) + && gimple_uid (SSA_NAME_DEF_STMT (lhs)) == 0) + || (TREE_CODE (rhs) == SSA_NAME + && !SSA_NAME_IS_DEFAULT_DEF (rhs) + && flow_bb_inside_loop_p (loop, + gimple_bb (SSA_NAME_DEF_STMT (rhs))) + && gimple_uid (SSA_NAME_DEF_STMT (rhs)) == 0))) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, + " Not duplicating bb %i: condition based on non-IV loop" + "variant.\n", header->index); + return false; + } + if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " Will duplicate bb %i\n", header->index); return true; @@ -343,11 +403,6 @@ ch_base::copy_headers (function *fun) bbs[n_bbs++] = header; gcc_assert (bbs_size > n_bbs); header = exit->dest; - /* Make sure to stop copying after we copied the first exit test. - Without further heuristics we do not want to rotate the loop - any further. */ - if (loop_exits_from_bb_p (loop, exit->src)) - break; } if (!exit)