@@ -1,3 +1,14 @@
+2016-02-05 Jeff Law <law@redhat.com>
+
+ 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 <msebor@redhat.com>
PR c++/69662
@@ -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
@@ -1,3 +1,13 @@
+2016-02-05 Jeff Law <law@redhat.com>
+
+ 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 <msebor@redhat.com>
PR c++/69662
new file mode 100644
@@ -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" } } */
+
new file mode 100644
@@ -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" } } */
new file mode 100644
@@ -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" } } */
+
new file mode 100644
@@ -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" } } */
new file mode 100644
@@ -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" } } */
new file mode 100644
@@ -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" } } */
This patch addresses multiple issues with how we determine when to split paths. The primary motivation is addressing 68541 (P1). As I've gotten testcodes from Ajit, I've been able to look closely at the path splitting opportunities and consistently what I've seen is that contrary to the original belief, CSE/DCE opportunities are rarely exposed by path splitting. It seems the benefit is more due to removing the unconditional jump inherent in a CFG diamond -- even more so on the microblaze where these jumps have delay slots. While there are cases where splitting allows for CSE/DCE, they're the exception rather than the rule in the codes I've looked at. With that in mind, we want to encourage path splitting when the amount of code we're duplicating is small. We also want to balance that with not path splitting when the original code is something that may be if-convertable. The vast majority of if-convertable codes are cases where the two predecessors of the join block are single statement blocks with their results feeding the same PHI in the join block. We now reject that case for path splitting so as not to spoil if-conversion. The only wrinkle with that heuristic is that some codes (MIN, MAX, ABS, COND, calls, etc) are not good candidates for further if conversion. (ie, we have a MIN_EXPR in both predecessors that feed the PHI in the join). So we still allow those cases for splitting. This can be easily refined as we find more cases or as the if-converter is extended. So with that in place as the first filter, we just need to put a limiter on the number of statements we allow to be copied. I punted a bit and re-used the PARAM for jump threading. They've got enough in common that I felt it was reasonable. If I were to create a new PARAM, I'd probably start with a smaller default value after doing further instrumentation. While I was working through this I noticed we were path splitting in some cases where we shouldn't. Particularly if we had a CFG like: a / \ b c / \ / e d / \ / \ / \ latch exit Duplicating d for the edges b->d and c->d isn't as helpful because the duplicate can't be merged into b. We now detect this kind of case and reject it for path splitting. The new tests are a combination of reductions of codes from Ajit and my own poking around. Looking further out, I really wonder if the low level aspects of path splitting like we're trying to capture here really belong in the cross-jumping phase of the RTL optimizers. The higher level aspects (when we are able to expose CSE/DCE opportunities) should be driven by actually looking at the propagation/simplifications enabled by a potential split path. But those are gcc-7 things. Bootstrapped and regression tested on x86 linux. Installed on the trunk. I'll obviously keep an eye out for how the tests are handled on other platforms -- I don't think the tests are real sensitive to branch costs and such, but I've been surprised before. Onward to the jump threading code explosion wrap-up... jeff