From 8981d7127bf3caffdb760897def90c8f0e052931 Mon Sep 17 00:00:00 2001 From: Jeff Law Date: Fri, 5 Feb 2016 16:49:08 -0700 Subject: [PATCH] re PR tree-optimization/68541 (Path splitting causes if-conversion miss) PR tree-optimization/68541 * gimple-ssa-split-paths.c: Include tree-cfg.h and params.h. (count_stmts_in_block): New function. (poor_ifcvt_candidate_code): Likewise. (is_feasible_trace): Add some heuristics to determine when path splitting is profitable. (find_block_to_duplicate_for_splitting_paths): Make sure the graph is a diamond with a single exit. PR tree-optimization/68541 * gcc.dg/tree-ssa/split-path-2.c: New test. * gcc.dg/tree-ssa/split-path-3.c: New test. * gcc.dg/tree-ssa/split-path-4.c: New test. * gcc.dg/tree-ssa/split-path-5.c: New test. * gcc.dg/tree-ssa/split-path-6.c: New test. * gcc.dg/tree-ssa/split-path-7.c: New test. From-SVN: r233191 --- gcc/ChangeLog | 11 +++ gcc/gimple-ssa-split-paths.c | 113 ++++++++++++++++++++++++--- gcc/testsuite/ChangeLog | 10 +++ gcc/testsuite/gcc.dg/tree-ssa/split-path-2.c | 21 +++++ gcc/testsuite/gcc.dg/tree-ssa/split-path-3.c | 90 +++++++++++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/split-path-4.c | 24 ++++++ gcc/testsuite/gcc.dg/tree-ssa/split-path-5.c | 60 ++++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/split-path-6.c | 72 +++++++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/split-path-7.c | 94 ++++++++++++++++++++++ 9 files changed, 483 insertions(+), 12 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/split-path-2.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/split-path-3.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/split-path-4.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/split-path-5.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/split-path-6.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/split-path-7.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 9a51133..a465156 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,14 @@ +2016-02-05 Jeff Law + + PR tree-optimization/68541 + * gimple-ssa-split-paths.c: Include tree-cfg.h and params.h. + (count_stmts_in_block): New function. + (poor_ifcvt_candidate_code): Likewise. + (is_feasible_trace): Add some heuristics to determine when path + splitting is profitable. + (find_block_to_duplicate_for_splitting_paths): Make sure the graph + is a diamond with a single exit. + 2016-02-05 Martin Sebor PR c++/69662 diff --git a/gcc/gimple-ssa-split-paths.c b/gcc/gimple-ssa-split-paths.c index 40c099a..ac6de81 100644 --- a/gcc/gimple-ssa-split-paths.c +++ b/gcc/gimple-ssa-split-paths.c @@ -25,11 +25,13 @@ along with GCC; see the file COPYING3. If not see #include "tree.h" #include "gimple.h" #include "tree-pass.h" +#include "tree-cfg.h" #include "cfganal.h" #include "cfgloop.h" #include "gimple-iterator.h" #include "tracer.h" #include "predict.h" +#include "params.h" /* Given LATCH, the latch block in a loop, see if the shape of the path reaching LATCH is suitable for being split by duplication. @@ -79,6 +81,11 @@ find_block_to_duplicate_for_splitting_paths (basic_block latch) || !find_edge (bb_idom, EDGE_PRED (bb, 1)->src)) return NULL; + /* And that the predecessors of BB each have a single successor. */ + if (!single_succ_p (EDGE_PRED (bb, 0)->src) + || !single_succ_p (EDGE_PRED (bb, 1)->src)) + return NULL; + /* So at this point we have a simple diamond for an IF-THEN-ELSE construct starting at BB_IDOM, with a join point at BB. BB pass control outside the loop or to the loop latch. @@ -91,29 +98,111 @@ find_block_to_duplicate_for_splitting_paths (basic_block latch) return NULL; } +/* Return the number of non-debug statements in a block. */ +static unsigned int +count_stmts_in_block (basic_block bb) +{ + gimple_stmt_iterator gsi; + unsigned int num_stmts = 0; + + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gimple *stmt = gsi_stmt (gsi); + if (!is_gimple_debug (stmt)) + num_stmts++; + } + return num_stmts; +} + +/* Return TRUE if CODE represents a tree code that is not likely to + be easily if-convertable because it likely expands into multiple + insns, FALSE otherwise. */ +static bool +poor_ifcvt_candidate_code (enum tree_code code) +{ + return (code == MIN_EXPR + || code == MAX_EXPR + || code == ABS_EXPR + || code == COND_EXPR + || code == CALL_EXPR); +} + /* Return TRUE if BB is a reasonable block to duplicate by examining its size, false otherwise. BB will always be a loop latch block. - Should this use the same tests as we do for jump threading? */ + Things to consider: + + We do not want to spoil if-conversion if at all possible. + + Most of the benefit seems to be from eliminating the unconditional + jump rather than CSE/DCE opportunities. So favor duplicating + small latches. A latch with just a conditional branch is ideal. + + CSE/DCE opportunties crop up when statements from the predecessors + feed statements in the latch and allow statements in the latch to + simplify. */ static bool is_feasible_trace (basic_block bb) { - int num_stmt = 0; - gimple_stmt_iterator gsi; - - for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + basic_block pred1 = EDGE_PRED (bb, 0)->src; + basic_block pred2 = EDGE_PRED (bb, 1)->src; + int num_stmts_in_join = count_stmts_in_block (bb); + int num_stmts_in_pred1 = count_stmts_in_block (pred1); + int num_stmts_in_pred2 = count_stmts_in_block (pred2); + + /* This is meant to catch cases that are likely opportunities for + if-conversion. Essentially we look for the case where + BB's predecessors are both single statement blocks where + the output of that statement feed the same PHI in BB. */ + if (num_stmts_in_pred1 == 1 && num_stmts_in_pred2 == 1) { - gimple *stmt = gsi_stmt (gsi); - if (!is_gimple_debug (stmt)) - num_stmt++; + gimple *stmt1 = last_and_only_stmt (pred1); + gimple *stmt2 = last_and_only_stmt (pred2); + + if (stmt1 && stmt2 + && gimple_code (stmt1) == GIMPLE_ASSIGN + && gimple_code (stmt2) == GIMPLE_ASSIGN) + { + enum tree_code code1 = gimple_assign_rhs_code (stmt1); + enum tree_code code2 = gimple_assign_rhs_code (stmt2); + + if (!poor_ifcvt_candidate_code (code1) + && !poor_ifcvt_candidate_code (code2)) + { + tree lhs1 = gimple_assign_lhs (stmt1); + tree lhs2 = gimple_assign_lhs (stmt2); + gimple_stmt_iterator gsi; + for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gimple *phi = gsi_stmt (gsi); + if ((gimple_phi_arg_def (phi, 0) == lhs1 + && gimple_phi_arg_def (phi, 1) == lhs2) + || (gimple_phi_arg_def (phi, 1) == lhs1 + && gimple_phi_arg_def (phi, 0) == lhs2)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, + "Block %d appears to be a join point for " + "if-convertable diamond.\n", + bb->index); + return false; + } + } + } + } } - /* We may want to limit how many statements we copy. */ - if (num_stmt > 1) - return true; + /* We may want something here which looks at dataflow and tries + to guess if duplication of BB is likely to result in simplification + of instructions in BB in either the original or the duplicate. */ + + /* Upper Hard limit on the number statements to copy. */ + if (num_stmts_in_join + >= PARAM_VALUE (PARAM_MAX_JUMP_THREAD_DUPLICATION_STMTS)) + return false; - return false; + return true; } /* If the immediate dominator of the latch of the loop is diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index cce24b4..388b2b9 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,13 @@ +2016-02-05 Jeff Law + + PR tree-optimization/68541 + * gcc.dg/tree-ssa/split-path-2.c: New test. + * gcc.dg/tree-ssa/split-path-3.c: New test. + * gcc.dg/tree-ssa/split-path-4.c: New test. + * gcc.dg/tree-ssa/split-path-5.c: New test. + * gcc.dg/tree-ssa/split-path-6.c: New test. + * gcc.dg/tree-ssa/split-path-7.c: New test. + 2016-02-05 Martin Sebor PR c++/69662 diff --git a/gcc/testsuite/gcc.dg/tree-ssa/split-path-2.c b/gcc/testsuite/gcc.dg/tree-ssa/split-path-2.c new file mode 100644 index 0000000..aeb926e --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/split-path-2.c @@ -0,0 +1,21 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fsplit-paths -fdump-tree-split-paths-details " } */ + +int +foo(char *p, int n) +{ + int s = 0; + int i; + + for (i = 0; i < n; i++) { + if (p[i] >= 0) + s++; + else + s--; + } + + return s; +} + +/* { dg-final { scan-tree-dump "appears to be a join point for if-convertable diamond" "split-paths" } } */ + diff --git a/gcc/testsuite/gcc.dg/tree-ssa/split-path-3.c b/gcc/testsuite/gcc.dg/tree-ssa/split-path-3.c new file mode 100644 index 0000000..814504a --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/split-path-3.c @@ -0,0 +1,90 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fsplit-paths -fdump-tree-split-paths-details -w" } */ + +typedef struct bitmap_head_def *bitmap; +extern void vec_assert_fail (const char *, const char *, const char *file_, + unsigned line_, const char *function_) + __attribute__ ((__noreturn__)); +typedef struct VEC_int_base +{ + unsigned num; + unsigned alloc; + int vec[1]; +} +VEC_int_base; +static __inline__ int +VEC_int_base_space (VEC_int_base * vec_, int alloc_, const char *file_, + unsigned line_, const char *function_) +{ + return vec_ ? vec_->alloc - vec_->num >= (unsigned) alloc_ : !alloc_; +} + +static __inline__ int * +VEC_int_base_quick_push (VEC_int_base * vec_, int obj_, const char *file_, + unsigned line_, const char *function_) +{ + (void) ((vec_->num < + vec_->alloc) ? 0 : (vec_assert_fail ("push", "VEC(int,base)", + file_, line_, function_), 0)); +} + +typedef struct VEC_int_heap +{ + VEC_int_base base; +} +VEC_int_heap; +static __inline__ int +VEC_int_heap_reserve (VEC_int_heap ** vec_, int alloc_, const char *file_, + unsigned line_, const char *function_) +{ + int extend = + !VEC_int_base_space (((*vec_) ? &(*vec_)->base : 0), alloc_, file_, line_, + function_); + if (extend) + *vec_ = + (VEC_int_heap *) vec_heap_o_reserve (*vec_, alloc_, + __builtin_offsetof (VEC_int_heap, + base.vec), + sizeof (int)); +} + +static __inline__ int * +VEC_int_heap_safe_push (VEC_int_heap ** vec_, const int obj_, + const char *file_, unsigned line_, + const char *function_) +{ + VEC_int_heap_reserve (vec_, 1, file_, line_, function_); + return VEC_int_base_quick_push (((*vec_) ? &(*vec_)->base : 0), obj_, file_, + line_, function_); +}; + +typedef struct bitmap_head_def +{ +} +bitmap_head; +typedef struct +{ +} +bitmap_iterator; +bitmap +compute_idf (bitmap_head * dfs) +{ + bitmap_iterator bi; + unsigned bb_index, i; + VEC_int_heap *work_stack; + bitmap phi_insertion_points; + while ((VEC_int_base_length (((work_stack) ? &(work_stack)->base : 0))) > 0) + { + for (bmp_iter_and_compl_init + (&(bi), (&dfs[bb_index]), (phi_insertion_points), (0), &(i)); + bmp_iter_and_compl (&(bi), &(i)); bmp_iter_next (&(bi), &(i))) + { + (VEC_int_heap_safe_push + (&(work_stack), i, "/home/gcc/virgin-gcc/gcc/cfganal.c", 1349, + __FUNCTION__)); + } + } + (VEC_int_heap_free (&work_stack)); +} + +/* { dg-final { scan-tree-dump-not "Duplicating join block" "split-paths" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/split-path-4.c b/gcc/testsuite/gcc.dg/tree-ssa/split-path-4.c new file mode 100644 index 0000000..dac931c --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/split-path-4.c @@ -0,0 +1,24 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fsplit-paths -fdump-tree-split-paths-details -w" } */ + +powi_cost (long n) +{ + unsigned char cache[256]; + unsigned long digit; + unsigned long val; + int result; + while (val >= 256) + { + if (val & 1) + { + result += powi_lookup_cost (digit, cache) + 3 + 1; + } + else + { + val >>= 1; + } + } +} + +/* { dg-final { scan-tree-dump-times "Duplicating join block" 1 "split-paths" } } */ + diff --git a/gcc/testsuite/gcc.dg/tree-ssa/split-path-5.c b/gcc/testsuite/gcc.dg/tree-ssa/split-path-5.c new file mode 100644 index 0000000..5044c73 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/split-path-5.c @@ -0,0 +1,60 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fsplit-paths -fdump-tree-split-paths-details -w" } */ + +const extern char *__ctype_ptr__; +typedef unsigned char uchar; +static int patlen; +static int skip[(0x7f * 2 + 1) + 1]; +static uchar *pat = ((void *) 0); +void +bmhi_init (const char *pattern) +{ + int i, lastpatchar; + patlen = strlen (pattern); + for (i = 0; i < patlen; i++) + pat[i] = ( + { + __typeof__ (pattern[i]) __x = (pattern[i]); + ((((__ctype_ptr__ + + sizeof (""[__x]))[(int) (__x)]) & (01 | 02)) + == 02) ? (int) __x - 'a' + 'A' : (int) __x; + }); + for (i = 0; i < patlen - 1; ++i) + { + skip[( + { + __typeof__ (pat[i]) __x = (pat[i]); + ((((__ctype_ptr__ + + sizeof (""[__x]))[(int) (__x)]) & (01 | 02)) == + 01) ? (int) __x - 'A' + 'a' : (int) __x; + })] = patlen - i - 1; + } + skip[( + { + __typeof__ (lastpatchar) __x = (lastpatchar); + ((((__ctype_ptr__ + + sizeof (""[__x]))[(int) (__x)]) & (01 | 02)) == + 01) ? (int) __x - 'A' + 'a' : (int) __x; + })] = 32767; + for (i = 0; i < patlen - 1; ++i) + { + } +} + +char * +bmhi_search (const char *string, const int stringlen) +{ + int i, j; + char *s; + for (;;) + { + while (--j >= 0 && ( + { + __typeof__ (s[j]) __x = (s[j]); + ((((__ctype_ptr__ + + sizeof (""[__x]))[(int) (__x)]) & + (01 | 02)) == + 02) ? (int) __x - 'a' + + 'A' : (int) __x;}) == pat[j]); +}} +/* { dg-final { scan-tree-dump-times "Duplicating join block" 2 "split-paths" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/split-path-6.c b/gcc/testsuite/gcc.dg/tree-ssa/split-path-6.c new file mode 100644 index 0000000..682166f --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/split-path-6.c @@ -0,0 +1,72 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fsplit-paths -fdump-tree-split-paths-details -w" } */ + +struct __sFILE +{ + unsigned char *_p; + int _r; +}; +typedef struct __sFILE __FILE; +struct _reent +{ + __FILE *_stdin, *_stdout, *_stderr; +}; +extern struct _reent *_impure_ptr; +extern char contextbufs[10][1024]; +extern int contextoffset; +extern int sflag; +void +givehelp (interactive) + int interactive; +{ + if (interactive) + { + while ((--((_impure_ptr->_stdin))->_r < + 0 ? __srget_r (_impure_ptr, + (_impure_ptr-> + _stdin)) : (int) (*((_impure_ptr->_stdin))-> + _p++)) != ' '); + } +} + +oof () +{ + int bufsize; + int hadnl; + while (1) + { + if (bufsize == (sizeof contextbufs[0]) / 2 - 1) + { + if (contextbufs[0][0] == '*' || contextbufs[0][0] == '@') + treeinsert (ichartosstr (strtosichar (contextbufs[0] + 1, 0), 1), + (100 + 4 * 20 + 4), contextbufs[0][0] == '*'); + } + if (hadnl) + contextoffset = 0; + else + contextoffset += bufsize; + if (sflag) + { + stop (); + } + } +} + +void +lookharder (string) + char *string; +{ + register char *g; + register char *s; + for (s = string; *s != '\0'; s++) + { + if (*s == '*') + { + *g++ = '.'; + } + else + *g++ = *s; + } +} + +/* { dg-final { scan-tree-dump-times "Duplicating join block" 3 "split-paths" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/split-path-7.c b/gcc/testsuite/gcc.dg/tree-ssa/split-path-7.c new file mode 100644 index 0000000..f14ab79 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/split-path-7.c @@ -0,0 +1,94 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fsplit-paths -fdump-tree-split-paths-details -w" } */ + + +struct _reent +{ +}; +typedef unsigned char ichar_t; +struct dent +{ + char *word; +}; +struct flagent +{ + ichar_t *strip; + ichar_t *affix; + short stripl; + short affl; +}; +union ptr_union +{ + struct flagptr *fp; + struct flagent *ent; +}; +struct flagptr +{ + union ptr_union pu; + int numents; +}; +struct hashheader +{ +}; +extern struct dent *hashtbl; +extern char *hashstrings; +extern int hashsize; +extern int nodictflag; +extern int numsflags; +extern int numpflags; +extern struct flagent *pflaglist; +extern struct flagent *sflaglist; +int +linit () +{ + register int i; + register struct dent *dp; + struct flagent *entry; + struct flagptr *ind; + int viazero; + register ichar_t *cp; + if (!nodictflag) + { + for (i = hashsize, dp = hashtbl; --i >= 0; dp++) + { + if (dp->word == (char *) -1) + dp->word = ((void *) 0); + else + dp->word = &hashstrings[(int) (dp->word)]; + } + } + for (i = numsflags + numpflags, entry = sflaglist; --i >= 0; entry++) + { + if (entry->stripl) + entry->strip = (ichar_t *) & hashstrings[(int) entry->strip]; + else + entry->affix = ((void *) 0); + } + for (i = numsflags, entry = sflaglist; i > 0; i--, entry++) + { + if (entry->affl == 0) + { + if (ind->pu.fp == ((void *) 0)) + { + } + } + } + for (i = numpflags, entry = pflaglist; i > 0; i--, entry++) + { + if (entry->affl == 0) + { + while (ind->numents == 0 && ind->pu.fp != ((void *) 0)) + { + if (*cp == 0) + { + } + } + } + if (!viazero && ind->numents >= 4 + && strcmp ((char *) (entry->affix), + (char *) (ind->pu.ent->affix)) != 0) + { + } + } +} +/* { dg-final { scan-tree-dump-times "Duplicating join block" 2 "split-paths" } } */ -- 2.7.4