diff options
Diffstat (limited to 'gcc')
| -rw-r--r-- | gcc/ChangeLog | 25 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-cse-1.c | 6 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-10.c | 14 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-11.c | 21 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-12.c | 27 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-13.c | 26 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-9.c | 13 | ||||
| -rw-r--r-- | gcc/tree-ssa-pre.c | 281 | ||||
| -rw-r--r-- | gcc/tree-vn.c | 26 |
9 files changed, 419 insertions, 20 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index ef16d8ba29e..24444470364 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,28 @@ +2005-05-15 Daniel Berlin <dberlin@dberlin.org> + + Fix PR tree-optimization/21576 + + * tree-ssa-pre.c (expression_node_pool): New pool. + (comparison_node_pool): Ditto. + (list_node_pool): Ditto. + (pool_copy_list): New function. + (phi_translate): Handle CALL_EXPR. + (valid_in_set): Ditto. + (create_expression_by_pieces): Ditto. + (insert_into_preds_of_block): Ditto. + (insert_aux): Ditto. + (compute_avail): Ditto. + (create_value_expr_from): Handle TREE_LIST and CALL_EXPR. + (can_value_number_call): New function. + (find_leader): Update comment. + (init_pre): Create new pools. + (fini_pre): Free new pools. + (pass_pre): Add TODO_update_ssa for the future when we are going + to need vops. + * tree-vn.c (expressions_equal_p): Handle TREE_LIST. + (set_value_handle): Ditto. + (get_value_handle): Ditto. + 2005-05-15 Richard Earnshaw <richard.earnshaw@arm.com> * arm.c (thumb_unexpanded_epilogue): Delete unused variable 'mode'. diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-cse-1.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-cse-1.c index 82687d71913..5bbfd3d17fb 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-cse-1.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-cse-1.c @@ -1,5 +1,5 @@ /* { dg-do compile } */ -/* { dg-options "-O2 -fdump-tree-dom1-details" } */ +/* { dg-options "-O2 -fdump-tree-fre-details" } */ int t(int a) __attribute__ ((const)); void q (void); void @@ -12,5 +12,5 @@ threading(int a,int b) } } /* We should thread the jump twice and eliminate it. */ -/* { dg-final { scan-tree-dump-times "Replaced.* t " 1 "dom1"} } */ -/* { dg-final { cleanup-tree-dump "dom1" } } */ +/* { dg-final { scan-tree-dump-times "Replaced.* t " 1 "fre"} } */ +/* { dg-final { cleanup-tree-dump "fre" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-10.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-10.c new file mode 100644 index 00000000000..127caa6cd6b --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-10.c @@ -0,0 +1,14 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fno-tree-dominator-opts -fdump-tree-fre-stats" } */ +double cos (double); +void link_error(); +void f(double a) +{ + double b = cos (a); + double c = cos (a); + if (b != c) + link_error(); +} + +/* { dg-final { scan-tree-dump-times "Eliminated: 1" 1 "fre"} } */ +/* { dg-final { cleanup-tree-dump "fre" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-11.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-11.c new file mode 100644 index 00000000000..26c47b1830b --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-11.c @@ -0,0 +1,21 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-pre-stats" } */ +double cos (double); +double f(double a) +{ + double b; + double c,d; + if (a < 2.0) + { + c = cos (a); + } + else + { + c = 1.0; + } + d = cos (a); + return d + c; +} + +/* { dg-final { scan-tree-dump-times "Eliminated: 1" 1 "pre"} } */ +/* { dg-final { cleanup-tree-dump "pre" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-12.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-12.c new file mode 100644 index 00000000000..fd80e3d8d50 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-12.c @@ -0,0 +1,27 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-pre-stats" } */ +double cos (double) __attribute__ ((const)); +double sin (double) __attribute__ ((const)); +double f(double a) +{ + double b; + double c,d; + double (*fp) (double) __attribute__ ((const)); + /* Fully redundant call, but we need a phi node to merge the results. */ + if (a < 2.0) + { + fp = sin; + c = fp (a); + } + else + { + c = 1.0; + fp = cos; + c = fp (a); + } + d = fp (a); + return d + c; +} + +/* { dg-final { scan-tree-dump-times "Eliminated: 1" 1 "pre"} } */ +/* { dg-final { cleanup-tree-dump "pre" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-13.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-13.c new file mode 100644 index 00000000000..dfce46b9907 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-13.c @@ -0,0 +1,26 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-pre-stats" } */ +double cos (double) __attribute__ ((const)); +double sin (double) __attribute__ ((const)); +double f(double a) +{ + double b; + double c,d; + double (*fp) (double) __attribute__ ((const)); + /* Partially redundant call */ + if (a < 2.0) + { + fp = sin; + c = fp (a); + } + else + { + c = 1.0; + fp = cos; + } + d = fp (a); + return d + c; +} + +/* { dg-final { scan-tree-dump-times "Eliminated: 1" 1 "pre"} } */ +/* { dg-final { cleanup-tree-dump "pre" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-9.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-9.c new file mode 100644 index 00000000000..32e37b99703 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-9.c @@ -0,0 +1,13 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fno-tree-dominator-opts -fdump-tree-fre-stats" } */ +int +foo (unsigned long a) +{ + int b = __builtin_clzl (a); + int c = __builtin_clzl (a); + if (b == c) + return 1; + return 0; +} +/* { dg-final { scan-tree-dump-times "Eliminated: 1" 1 "fre"} } */ +/* { dg-final { cleanup-tree-dump "fre" } } */ diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c index 0494774b608..859bf096210 100644 --- a/gcc/tree-ssa-pre.c +++ b/gcc/tree-ssa-pre.c @@ -305,6 +305,9 @@ static alloc_pool value_set_node_pool; static alloc_pool binary_node_pool; static alloc_pool unary_node_pool; static alloc_pool reference_node_pool; +static alloc_pool comparison_node_pool; +static alloc_pool expression_node_pool; +static alloc_pool list_node_pool; static bitmap_obstack grand_bitmap_obstack; /* Set of blocks with statements that have had its EH information @@ -855,6 +858,35 @@ fully_constant_expression (tree t) return t; } +/* Return a copy of a chain of nodes, chained through the TREE_CHAIN field. + For example, this can copy a list made of TREE_LIST nodes. + Allocates the nodes in list_node_pool*/ + +static tree +pool_copy_list (tree list) +{ + tree head; + tree prev, next; + + if (list == 0) + return 0; + head = pool_alloc (list_node_pool); + + memcpy (head, list, tree_size (list)); + prev = head; + + next = TREE_CHAIN (list); + while (next) + { + TREE_CHAIN (prev) = pool_alloc (list_node_pool); + memcpy (TREE_CHAIN (prev), next, tree_size (next)); + prev = TREE_CHAIN (prev); + next = TREE_CHAIN (next); + } + return head; +} + + /* Translate EXPR using phis in PHIBLOCK, so that it has the values of the phis in PRED. Return NULL if we can't find a leader for each part of the translated expression. */ @@ -879,6 +911,89 @@ phi_translate (tree expr, value_set_t set, basic_block pred, switch (TREE_CODE_CLASS (TREE_CODE (expr))) { + case tcc_expression: + { + if (TREE_CODE (expr) != CALL_EXPR) + return NULL; + else + { + tree oldop0 = TREE_OPERAND (expr, 0); + tree oldarglist = TREE_OPERAND (expr, 1); + tree oldop2 = TREE_OPERAND (expr, 2); + tree newop0; + tree newarglist; + tree newop2 = NULL; + tree oldwalker; + tree newwalker; + tree newexpr; + bool listchanged = false; + + /* Call expressions are kind of weird because they have an + argument list. We don't want to value number the list + as one value number, because that doesn't make much + sense, and just breaks the support functions we call, + which expect TREE_OPERAND (call_expr, 2) to be a + TREE_LIST. */ + + newop0 = phi_translate (find_leader (set, oldop0), + set, pred, phiblock); + if (newop0 == NULL) + return NULL; + if (oldop2) + { + newop2 = phi_translate (find_leader (set, oldop2), + set, pred, phiblock); + if (newop2 == NULL) + return NULL; + } + + /* phi translate the argument list piece by piece. + + We could actually build the list piece by piece here, + but it's likely to not be worth the memory we will save, + unless you have millions of call arguments. */ + + newarglist = pool_copy_list (oldarglist); + for (oldwalker = oldarglist, newwalker = newarglist; + oldwalker && newwalker; + oldwalker = TREE_CHAIN (oldwalker), + newwalker = TREE_CHAIN (newwalker)) + { + + tree oldval = TREE_VALUE (oldwalker); + tree newval; + if (oldval) + { + newval = phi_translate (find_leader (set, oldval), + set, pred, phiblock); + if (newval == NULL) + return NULL; + if (newval != oldval) + { + listchanged = true; + TREE_VALUE (newwalker) = get_value_handle (newval); + } + } + } + if (listchanged) + vn_lookup_or_add (newarglist, NULL); + + if (listchanged || (newop0 != oldop0) || (oldop2 != newop2)) + { + newexpr = pool_alloc (expression_node_pool); + memcpy (newexpr, expr, tree_size (expr)); + TREE_OPERAND (newexpr, 0) = newop0 == oldop0 ? oldop0 : get_value_handle (newop0); + TREE_OPERAND (newexpr, 1) = listchanged ? newarglist : oldarglist; + TREE_OPERAND (newexpr, 2) = newop2 == oldop2 ? oldop2 : get_value_handle (newop2); + create_tree_ann (newexpr); + vn_lookup_or_add (newexpr, NULL); + expr = newexpr; + phi_trans_add (oldexpr, newexpr, pred); + } + } + } + return expr; + case tcc_reference: /* XXX: Until we have PRE of loads working, none will be ANTIC. */ return NULL; @@ -1084,10 +1199,10 @@ find_leader (value_set_t set, tree val) we have a leader for each part of the expression (if it consists of values), or the expression is an SSA_NAME. - NB: We never should run into a case where we have SSA_NAME + + NB: We never should run into a case where we have SSA_NAME + SSA_NAME or SSA_NAME + value. The sets valid_in_set is called on, - the ANTIC sets, will only ever have SSA_NAME's or binary value - expression (IE VALUE1 + VALUE2) */ + the ANTIC sets, will only ever have SSA_NAME's or value expressions + (IE VALUE1 + VALUE2, *VALUE1, VALUE1 < VALUE2) */ static bool valid_in_set (value_set_t set, tree expr) @@ -1107,7 +1222,31 @@ valid_in_set (value_set_t set, tree expr) tree op1 = TREE_OPERAND (expr, 0); return set_contains_value (set, op1); } + + case tcc_expression: + { + if (TREE_CODE (expr) == CALL_EXPR) + { + tree op0 = TREE_OPERAND (expr, 0); + tree arglist = TREE_OPERAND (expr, 1); + tree op2 = TREE_OPERAND (expr, 2); + /* Check the non-list operands first. */ + if (!set_contains_value (set, op0) + || (op2 && !set_contains_value (set, op2))) + return false; + + /* Now check the operands. */ + for (; arglist; arglist = TREE_CHAIN (arglist)) + { + if (!set_contains_value (set, TREE_VALUE (arglist))) + return false; + } + return true; + } + return false; + } + case tcc_reference: /* XXX: Until PRE of loads works, no reference nodes are ANTIC. */ return false; @@ -1189,7 +1328,7 @@ compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge) translate through. */ else if (single_succ_p (block)) { - phi_translate_set (ANTIC_OUT, ANTIC_IN(single_succ (block)), + phi_translate_set (ANTIC_OUT, ANTIC_IN (single_succ (block)), block, single_succ (block)); } /* If we have multiple successors, we take the intersection of all of @@ -1359,6 +1498,42 @@ create_expression_by_pieces (basic_block block, tree expr, tree stmts) switch (TREE_CODE_CLASS (TREE_CODE (expr))) { + case tcc_expression: + { + tree op0, op2; + tree arglist; + tree genop0, genop2; + tree genarglist; + tree walker, genwalker; + + gcc_assert (TREE_CODE (expr) == CALL_EXPR); + genop2 = NULL; + + op0 = TREE_OPERAND (expr, 0); + arglist = TREE_OPERAND (expr, 1); + op2 = TREE_OPERAND (expr, 2); + + genop0 = find_or_generate_expression (block, op0, stmts); + genarglist = copy_list (arglist); + for (walker = arglist, genwalker = genarglist; + genwalker && walker; + genwalker = TREE_CHAIN (genwalker), walker = TREE_CHAIN (walker)) + { + TREE_VALUE (genwalker) = find_or_generate_expression (block, + TREE_VALUE (walker), + stmts); + } + + if (op2) + genop2 = find_or_generate_expression (block, op2, stmts); + folded = fold (build (TREE_CODE (expr), TREE_TYPE (expr), + genop0, genarglist, genop2)); + break; + + + } + break; + case tcc_binary: case tcc_comparison: { @@ -1499,7 +1674,8 @@ insert_into_preds_of_block (basic_block block, value_set_node_t node, eprime = avail[bprime->index]; if (BINARY_CLASS_P (eprime) || COMPARISON_CLASS_P (eprime) - || UNARY_CLASS_P (eprime)) + || UNARY_CLASS_P (eprime) + || TREE_CODE (eprime) == CALL_EXPR) { builtexpr = create_expression_by_pieces (bprime, eprime, @@ -1613,7 +1789,8 @@ insert_aux (basic_block block) { if (BINARY_CLASS_P (node->expr) || COMPARISON_CLASS_P (node->expr) - || UNARY_CLASS_P (node->expr)) + || UNARY_CLASS_P (node->expr) + || TREE_CODE (node->expr) == CALL_EXPR) { tree *avail; tree val; @@ -1817,17 +1994,55 @@ create_value_expr_from (tree expr, basic_block block, tree stmt) gcc_assert (TREE_CODE_CLASS (code) == tcc_unary || TREE_CODE_CLASS (code) == tcc_binary || TREE_CODE_CLASS (code) == tcc_comparison - || TREE_CODE_CLASS (code) == tcc_reference); + || TREE_CODE_CLASS (code) == tcc_reference + || TREE_CODE_CLASS (code) == tcc_expression + || TREE_CODE_CLASS (code) == tcc_exceptional); if (TREE_CODE_CLASS (code) == tcc_unary) pool = unary_node_pool; else if (TREE_CODE_CLASS (code) == tcc_reference) pool = reference_node_pool; - else + else if (TREE_CODE_CLASS (code) == tcc_binary) pool = binary_node_pool; + else if (TREE_CODE_CLASS (code) == tcc_comparison) + pool = comparison_node_pool; + else if (TREE_CODE_CLASS (code) == tcc_exceptional) + { + gcc_assert (code == TREE_LIST); + pool = list_node_pool; + } + else + { + gcc_assert (code == CALL_EXPR); + pool = expression_node_pool; + } vexpr = pool_alloc (pool); memcpy (vexpr, expr, tree_size (expr)); + + /* This case is only for TREE_LIST's that appear as part of + CALL_EXPR's. Anything else is a bug, but we can't easily verify + this, hence tihs comment. TREE_LIST is not handled by the + general case below is because they don't have a fixed length, or + operands, so you can't access purpose/value/chain through + TREE_OPERAND macros. */ + + if (code == TREE_LIST) + { + tree temp = NULL_TREE; + if (TREE_CHAIN (vexpr)) + temp = create_value_expr_from (TREE_CHAIN (vexpr), block, stmt); + TREE_CHAIN (vexpr) = temp ? temp : TREE_CHAIN (vexpr); + + /* This is the equivalent of inserting op into EXP_GEN like we + do below */ + if (!is_undefined_value (TREE_VALUE (vexpr))) + value_insert_into_set (EXP_GEN (block), TREE_VALUE (vexpr)); + + TREE_VALUE (vexpr) = vn_lookup_or_add (TREE_VALUE (vexpr), NULL); + + return vexpr; + } for (i = 0; i < TREE_CODE_LENGTH (code); i++) { @@ -1846,18 +2061,32 @@ create_value_expr_from (tree expr, basic_block block, tree stmt) return NULL; } - /* Recursively value-numberize reference ops */ + /* Recursively value-numberize reference ops and tree lists. */ if (REFERENCE_CLASS_P (op)) { tree tempop = create_value_expr_from (op, block, stmt); op = tempop ? tempop : op; val = vn_lookup_or_add (op, stmt); } + else if (TREE_CODE (op) == TREE_LIST) + { + tree tempop; + + gcc_assert (TREE_CODE (expr) == CALL_EXPR); + tempop = create_value_expr_from (op, block, stmt); + + op = tempop ? tempop : op; + vn_lookup_or_add (op, NULL); + /* Unlike everywhere else, we do *not* want to replace the + TREE_LIST itself with a value number, because support + functions we call will blow up. */ + val = op; + } else /* Create a value handle for OP and add it to VEXPR. */ val = vn_lookup_or_add (op, NULL); - if (!is_undefined_value (op)) + if (!is_undefined_value (op) && TREE_CODE (op) != TREE_LIST) value_insert_into_set (EXP_GEN (block), op); if (TREE_CODE (val) == VALUE_HANDLE) @@ -1870,6 +2099,22 @@ create_value_expr_from (tree expr, basic_block block, tree stmt) } +/* Return true if we can value number a call. This is true if we have + a pure or constant call. */ +static bool +can_value_number_call (tree stmt) +{ + tree call = get_call_expr_in (stmt); + + /* This is a temporary restriction until we translate vuses through + phi nodes. */ + if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)) + return false; + if (call_expr_flags (call) & (ECF_PURE | ECF_CONST)) + return true; + return false; +} + /* Compute the AVAIL set for all basic blocks. This function performs value numbering of the statements in each basic @@ -1964,7 +2209,9 @@ compute_avail (void) if (UNARY_CLASS_P (rhs) || BINARY_CLASS_P (rhs) || COMPARISON_CLASS_P (rhs) - || REFERENCE_CLASS_P (rhs)) + || REFERENCE_CLASS_P (rhs) + || (TREE_CODE (rhs) == CALL_EXPR + && can_value_number_call (stmt))) { /* For binary, unary, and reference expressions, create a duplicate expression with the operands @@ -2245,6 +2492,12 @@ init_pre (bool do_fre) tree_code_size (NEGATE_EXPR), 30); reference_node_pool = create_alloc_pool ("Reference tree nodes", tree_code_size (ARRAY_REF), 30); + expression_node_pool = create_alloc_pool ("Expression tree nodes", + tree_code_size (CALL_EXPR), 30); + list_node_pool = create_alloc_pool ("List tree nodes", + tree_code_size (TREE_LIST), 30); + comparison_node_pool = create_alloc_pool ("Comparison tree nodes", + tree_code_size (EQ_EXPR), 30); FOR_ALL_BB (bb) { EXP_GEN (bb) = set_new (true); @@ -2273,6 +2526,9 @@ fini_pre (bool do_fre) free_alloc_pool (binary_node_pool); free_alloc_pool (reference_node_pool); free_alloc_pool (unary_node_pool); + free_alloc_pool (list_node_pool); + free_alloc_pool (expression_node_pool); + free_alloc_pool (comparison_node_pool); htab_delete (phi_translate_table); remove_fake_exit_edges (); @@ -2398,7 +2654,8 @@ struct tree_opt_pass pass_pre = 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ - TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */ + TODO_update_ssa | TODO_dump_func | TODO_ggc_collect + | TODO_verify_ssa, /* todo_flags_finish */ 0 /* letter */ }; diff --git a/gcc/tree-vn.c b/gcc/tree-vn.c index 5f003720e4d..e46fafaf308 100644 --- a/gcc/tree-vn.c +++ b/gcc/tree-vn.c @@ -119,9 +119,25 @@ expressions_equal_p (tree e1, tree e2) te1 = TREE_TYPE (e1); te2 = TREE_TYPE (e2); - if (TREE_CODE (e1) == TREE_CODE (e2) - && (te1 == te2 || lang_hooks.types_compatible_p (te1, te2)) - && operand_equal_p (e1, e2, OEP_PURE_SAME)) + if (TREE_CODE (e1) == TREE_LIST && TREE_CODE (e2) == TREE_LIST) + { + tree lop1 = e1; + tree lop2 = e2; + for (lop1 = e1, lop2 = e2; + lop1 || lop2; + lop1 = TREE_CHAIN (lop1), lop2 = TREE_CHAIN (lop2)) + { + if (!lop1 || !lop2) + return false; + if (!expressions_equal_p (TREE_VALUE (lop1), TREE_VALUE (lop2))) + return false; + } + return true; + + } + else if (TREE_CODE (e1) == TREE_CODE (e2) + && (te1 == te2 || lang_hooks.types_compatible_p (te1, te2)) + && operand_equal_p (e1, e2, OEP_PURE_SAME)) return true; return false; @@ -166,7 +182,7 @@ set_value_handle (tree e, tree v) { if (TREE_CODE (e) == SSA_NAME) SSA_NAME_VALUE (e) = v; - else if (EXPR_P (e) || DECL_P (e)) + else if (EXPR_P (e) || DECL_P (e) || TREE_CODE (e) == TREE_LIST) get_tree_ann (e)->common.value_handle = v; else /* Do nothing. Constants are their own value handles. */ @@ -271,7 +287,7 @@ get_value_handle (tree expr) if (TREE_CODE (expr) == SSA_NAME) return SSA_NAME_VALUE (expr); - else if (EXPR_P (expr) || DECL_P (expr)) + else if (EXPR_P (expr) || DECL_P (expr) || TREE_CODE (expr) == TREE_LIST) { tree_ann_t ann = tree_ann (expr); return ((ann) ? ann->common.value_handle : NULL_TREE); |
