From 3d466672b1290916bfc75f191787bc7459479ca3 Mon Sep 17 00:00:00 2001 From: Jeff Law Date: Mon, 12 Oct 2015 15:39:35 -0600 Subject: [PATCH] [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. From-SVN: r228739 --- gcc/ChangeLog | 9 +++ gcc/testsuite/ChangeLog | 5 ++ .../gcc.dg/tree-ssa/ssa-dom-thread-7.c | 2 +- .../{ssa-dom-thread-11.c => ssa-thread-11.c} | 0 gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-12.c | 72 +++++++++++++++++++ gcc/tree-ssa-threadbackward.c | 36 +++++++++- gcc/tree-ssa-threadedge.c | 27 ++++--- 7 files changed, 139 insertions(+), 12 deletions(-) rename gcc/testsuite/gcc.dg/tree-ssa/{ssa-dom-thread-11.c => ssa-thread-11.c} (100%) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-12.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 61e46ff8c56..a8650439eef 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -7,6 +7,15 @@ 2015-10-12 Jeff Law + * 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. diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 89f33632865..4a08f0fe637 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,5 +1,10 @@ 2015-10-12 Jeff Law + * 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 diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c index d8be023cd57..445f2509dc3 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c @@ -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, diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-11.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-11.c similarity index 100% rename from gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-11.c rename to gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-11.c diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-12.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-12.c new file mode 100644 index 00000000000..0697fb0caf5 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-12.c @@ -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))) + { + } + } +} diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c index ff6481c9547..5be6ee443e3 100644 --- a/gcc/tree-ssa-threadbackward.c +++ b/gcc/tree-ssa-threadbackward.c @@ -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 *visited_bbs, vec *&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 diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c index 5ca945864e7..da2fb1fde46 100644 --- a/gcc/tree-ssa-threadedge.c +++ b/gcc/tree-ssa-threadedge.c @@ -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. */ -- 2.30.2