@@ -7,6 +7,15 @@
2015-10-12 Jeff Law <law@redhat.com>
+ * tree-ssa-threadbackward.c (get_gimple_control_stmt): New function.
+ (fsm_find_control_stmt_paths): Change name of first argument to
+ more accurately relfect what it really is. Handle simplification
+ of GIMPLE_COND after finding a thread path for NAME.
+ * tree-ssa-threadedge.c (simplify_control_stmt_condition): Allow
+ nontrivial conditions to be handled by FSM threader.
+ (thread_through_normal_block): Extract the name to looup via
+ FSM threader from COND_EXPR.
+
* tree-ssa-threadbackward.c (fsm_find_thread_path): Remove
restriction that traced SSA_NAME is a user variable.
@@ -1,5 +1,10 @@
2015-10-12 Jeff Law <law@redhat.com>
+ * gcc.dg/tree-ssa/ssa-thread-12.c: New test.
+ * gcc.dg/tree-ssa/ssa-dom-thread-7.c: Update expected output.
+ * gcc.dg/tree-ssa/ssa-thread-11.c: Renamed from
+ ssa-dom-thread-11.c.
+
* gcc.dg/tree-ssa/ssa-dom-thread-11.c: New test.
2015-10-12 Ville Voutilainen <ville.voutilainen@gmail.com>
deleted file mode 100644
@@ -1,49 +0,0 @@
-/* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-vrp2-details" } */
-/* { dg-final { scan-tree-dump "FSM" "vrp2" } } */
-
-void abort (void);
-typedef struct bitmap_head_def *bitmap;
-typedef const struct bitmap_head_def *const_bitmap;
-typedef struct bitmap_obstack
-{
- struct bitmap_obstack *next;
- unsigned int indx;
-}
-bitmap_element;
-typedef struct bitmap_head_def
-{
- bitmap_element *first;
-}
-bitmap_head;
-static __inline__ unsigned char
-bitmap_elt_ior (bitmap dst, bitmap_element * dst_elt,
- bitmap_element * dst_prev, const bitmap_element * a_elt,
- const bitmap_element * b_elt)
-{
- ((void) (!(a_elt || b_elt) ? abort (), 0 : 0));
-}
-
-unsigned char
-bitmap_ior_and_compl (bitmap dst, const_bitmap a, const_bitmap b,
- const_bitmap kill)
-{
- bitmap_element *dst_elt = dst->first;
- const bitmap_element *a_elt = a->first;
- const bitmap_element *b_elt = b->first;
- const bitmap_element *kill_elt = kill->first;
- bitmap_element *dst_prev = ((void *) 0);
- while (a_elt || b_elt)
- {
- if (b_elt && kill_elt && kill_elt->indx == b_elt->indx
- && (!a_elt || a_elt->indx >= b_elt->indx));
- else
- {
- bitmap_elt_ior (dst, dst_elt, dst_prev, a_elt, b_elt);
- if (a_elt && b_elt && a_elt->indx == b_elt->indx)
- ;
- else if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx))
- a_elt = a_elt->next;
- }
- }
-}
@@ -1,6 +1,6 @@
/* { dg-do compile } */
/* { dg-options "-O2 -fdump-tree-dom1-details" } */
-/* { dg-final { scan-tree-dump-times "FSM" 19 "dom1" } } */
+/* { dg-final { scan-tree-dump-times "FSM" 38 "dom1" } } */
enum STATE {
S0=0,
new file mode 100644
@@ -0,0 +1,49 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-vrp2-details" } */
+/* { dg-final { scan-tree-dump "FSM" "vrp2" } } */
+
+void abort (void);
+typedef struct bitmap_head_def *bitmap;
+typedef const struct bitmap_head_def *const_bitmap;
+typedef struct bitmap_obstack
+{
+ struct bitmap_obstack *next;
+ unsigned int indx;
+}
+bitmap_element;
+typedef struct bitmap_head_def
+{
+ bitmap_element *first;
+}
+bitmap_head;
+static __inline__ unsigned char
+bitmap_elt_ior (bitmap dst, bitmap_element * dst_elt,
+ bitmap_element * dst_prev, const bitmap_element * a_elt,
+ const bitmap_element * b_elt)
+{
+ ((void) (!(a_elt || b_elt) ? abort (), 0 : 0));
+}
+
+unsigned char
+bitmap_ior_and_compl (bitmap dst, const_bitmap a, const_bitmap b,
+ const_bitmap kill)
+{
+ bitmap_element *dst_elt = dst->first;
+ const bitmap_element *a_elt = a->first;
+ const bitmap_element *b_elt = b->first;
+ const bitmap_element *kill_elt = kill->first;
+ bitmap_element *dst_prev = ((void *) 0);
+ while (a_elt || b_elt)
+ {
+ if (b_elt && kill_elt && kill_elt->indx == b_elt->indx
+ && (!a_elt || a_elt->indx >= b_elt->indx));
+ else
+ {
+ bitmap_elt_ior (dst, dst_elt, dst_prev, a_elt, b_elt);
+ if (a_elt && b_elt && a_elt->indx == b_elt->indx)
+ ;
+ else if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx))
+ a_elt = a_elt->next;
+ }
+ }
+}
new file mode 100644
@@ -0,0 +1,72 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-dom1-details" } */
+/* { dg-final { scan-tree-dump "FSM" "dom1" } } */
+
+typedef struct bitmap_head_def *bitmap;
+typedef const struct bitmap_head_def *const_bitmap;
+typedef struct VEC_int_base
+{
+}
+VEC_int_base;
+typedef struct VEC_int_heap
+{
+ VEC_int_base base;
+}
+VEC_int_heap;
+typedef unsigned long BITMAP_WORD;
+typedef struct bitmap_element_def
+{
+ struct bitmap_element_def *next;
+ unsigned int indx;
+}
+bitmap_element;
+typedef struct bitmap_head_def
+{
+}
+bitmap_head;
+typedef struct
+{
+ bitmap_element *elt1;
+ bitmap_element *elt2;
+ BITMAP_WORD bits;
+}
+bitmap_iterator;
+static __inline__ void
+bmp_iter_and_compl_init (bitmap_iterator * bi, const_bitmap map1,
+ const_bitmap map2, unsigned start_bit,
+ unsigned *bit_no)
+{
+}
+
+static __inline__ void
+bmp_iter_next (bitmap_iterator * bi, unsigned *bit_no)
+{
+}
+
+static __inline__ unsigned char
+bmp_iter_and_compl (bitmap_iterator * bi, unsigned *bit_no)
+{
+ if (bi->bits)
+ {
+ while (bi->elt2 && bi->elt2->indx < bi->elt1->indx)
+ bi->elt2 = bi->elt2->next;
+ }
+}
+
+extern int VEC_int_base_length (VEC_int_base *);
+bitmap
+compute_idf (bitmap def_blocks, 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)))
+ {
+ }
+ }
+}
@@ -36,6 +36,22 @@ along with GCC; see the file COPYING3. If not see
static int max_threaded_paths;
+/* Simple helper to get the last statement from BB, which is assumed
+ to be a control statement. */
+static gimple *
+get_gimple_control_stmt (basic_block bb)
+{
+ gimple_stmt_iterator gsi = gsi_last_bb (bb);
+
+ if (gsi_end_p (gsi))
+ return NULL;
+
+ gimple *stmt = gsi_stmt (gsi);
+ enum gimple_code code = gimple_code (stmt);
+ gcc_assert (code == GIMPLE_COND || code == GIMPLE_SWITCH || code == GIMPLE_GOTO);
+ return stmt;
+}
+
/* Return true if the CFG contains at least one path from START_BB to END_BB.
When a path is found, record in PATH the blocks from END_BB to START_BB.
VISITED_BBS is used to make sure we don't fall into an infinite loop. Bound
@@ -70,17 +86,17 @@ fsm_find_thread_path (basic_block start_bb, basic_block end_bb,
return false;
}
-/* We trace the value of the SSA_NAME EXPR back through any phi nodes looking
+/* We trace the value of the SSA_NAME NAME back through any phi nodes looking
for places where it gets a constant value and save the path. Stop after
having recorded MAX_PATHS jump threading paths. */
static void
-fsm_find_control_statement_thread_paths (tree expr,
+fsm_find_control_statement_thread_paths (tree name,
hash_set<basic_block> *visited_bbs,
vec<basic_block, va_gc> *&path,
bool seen_loop_phi)
{
- gimple *def_stmt = SSA_NAME_DEF_STMT (expr);
+ gimple *def_stmt = SSA_NAME_DEF_STMT (name);
basic_block var_bb = gimple_bb (def_stmt);
if (var_bb == NULL)
@@ -284,6 +300,20 @@ fsm_find_control_statement_thread_paths (tree expr,
jump_thread_path->safe_push (x);
}
+ gimple *stmt = get_gimple_control_stmt ((*path)[0]);
+ gcc_assert (stmt);
+ /* We have found a constant value for ARG. For GIMPLE_SWITCH
+ and GIMPLE_GOTO, we use it as-is. However, for a GIMPLE_COND
+ we need to substitute, fold and simplify. */
+ if (gimple_code (stmt) == GIMPLE_COND)
+ {
+ enum tree_code cond_code = gimple_cond_code (stmt);
+
+ /* We know the underyling format of the condition. */
+ arg = fold_binary (cond_code, boolean_type_node,
+ arg, gimple_cond_rhs (stmt));
+ }
+
/* Add the edge taken when the control variable has value ARG. */
edge taken_edge = find_taken_edge ((*path)[0], arg);
jump_thread_edge *x
@@ -551,11 +551,13 @@ simplify_control_stmt_condition (edge e,
|| !is_gimple_min_invariant (cached_lhs))
cached_lhs = (*simplify) (dummy_cond, stmt, avail_exprs_stack);
- /* If we were just testing that an integral type was != 0, and that
- failed, just return the first operand. This gives the FSM code a
- chance to optimize the path. */
- if (cached_lhs == NULL
- && cond_code == NE_EXPR)
+ /* If we were testing an integer/pointer against a constant, then
+ we can use the FSM code to trace the value of the SSA_NAME. If
+ a value is found, then the condition will collapse to a constant.
+
+ Return the SSA_NAME we want to trace back rather than the full
+ expression and give the FSM threader a chance to find its value. */
+ if (cached_lhs == NULL)
{
/* Recover the original operands. They may have been simplified
using context sensitive equivalences. Those context sensitive
@@ -563,9 +565,10 @@ simplify_control_stmt_condition (edge e,
tree op0 = gimple_cond_lhs (stmt);
tree op1 = gimple_cond_rhs (stmt);
- if (INTEGRAL_TYPE_P (TREE_TYPE (op0))
+ if ((INTEGRAL_TYPE_P (TREE_TYPE (op0))
+ || POINTER_TYPE_P (TREE_TYPE (op0)))
&& TREE_CODE (op0) == SSA_NAME
- && integer_zerop (op1))
+ && TREE_CODE (op1) == INTEGER_CST)
return op0;
}
@@ -1046,11 +1049,19 @@ thread_through_normal_block (edge e,
if (!flag_expensive_optimizations
|| optimize_function_for_size_p (cfun)
- || TREE_CODE (cond) != SSA_NAME
+ || !(TREE_CODE (cond) == SSA_NAME
+ || (TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison
+ && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME
+ && TREE_CODE (TREE_OPERAND (cond, 1)) == INTEGER_CST))
|| e->dest->loop_father != e->src->loop_father
|| loop_depth (e->dest->loop_father) == 0)
return 0;
+ /* Extract the SSA_NAME we want to trace backwards if COND is not
+ already a bare SSA_NAME. */
+ if (TREE_CODE (cond) != SSA_NAME)
+ cond = TREE_OPERAND (cond, 0);
+
/* When COND cannot be simplified, try to find paths from a control
statement back through the PHI nodes which would affect that control
statement. */
Right now the FSM threader only handles trivial conditions. Specifically looking up a naked SSA_NAME (used for GIMPLE_SWITCH) and SSA_NAME != 0. The FSM threader need not be so restrictive. We can easily use it to lookup things like SSA_NAME <OP> constant for integral and pointer names. Essentially the FSM threader walks backwards to find a value for a name. If we find a constant, we can then substitute the value into the expression and simplify. This patch implements the substitution part, then exploits it from tree-ssa-threadedge.c. I'm also renaming the test I added in my previous commit. It was poorly associated with DOM when in fact it was testing the FSM threader when called via VRP. Given the desire to run the FSM threader independently, I'm just going to call these ssa-thread-<whatever>.c tests. Bootstrapped and regression tested on x86_64-linux-gnu. Installed on the trunk. Jeff commit 4b7f0fb7fbb338ae677c83d3be33570edd464885 Author: Jeff Law <law@redhat.com> Date: Mon Oct 12 15:37:42 2015 -0600 [PATCH] Allow FSM threader to thread more complex conditions * tree-ssa-threadbackward.c (get_gimple_control_stmt): New function. (fsm_find_control_stmt_paths): Change name of first argument to more accurately relfect what it really is. Handle simplification of GIMPLE_COND after finding a thread path for NAME. * tree-ssa-threadedge.c (simplify_control_stmt_condition): Allow nontrivial conditions to be handled by FSM threader. (thread_through_normal_block): Extract the name to looup via FSM threader from COND_EXPR. * gcc.dg/tree-ssa/ssa-thread-12.c: New test. * gcc.dg/tree-ssa/ssa-dom-thread-7.c: Update expected output. * gcc.dg/tree-ssa/ssa-thread-11.c: Renamed from ssa-dom-thread-11.c.