From 64326bb428ac750ec3b0f56c06dfb98277cd41b5 Mon Sep 17 00:00:00 2001 From: Richard Biener Date: Thu, 12 Nov 2020 09:10:51 +0100 Subject: [PATCH] tree-optimization/97806 - fix PRE expression post order This fixes the postorder compute for the case of multiple expression leaders for a value. 2020-11-12 Richard Biener PR tree-optimization/97806 * tree-ssa-pre.c (pre_expr_DFS): New overload for visiting values, visiting all leaders for a value. Use a bitmap for visited values. (sorted_array_from_bitmap_set): Walk over values and adjust. * gcc.dg/pr97806.c: New testcase. --- gcc/testsuite/gcc.dg/pr97806.c | 16 ++++++++++ gcc/tree-ssa-pre.c | 70 ++++++++++++++++++++++++------------------ 2 files changed, 56 insertions(+), 30 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/pr97806.c diff --git a/gcc/testsuite/gcc.dg/pr97806.c b/gcc/testsuite/gcc.dg/pr97806.c new file mode 100644 index 0000000..9ec3299 --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr97806.c @@ -0,0 +1,16 @@ +/* { dg-do compile } */ +/* { dg-options "-O2" } */ + +int b; +long c; +int g(); +void h(long *); +void i(long *); +void d() { + int e, f = b - e; + if (g()) + h(&c + f); + else + i(&c + f); + __builtin_memset(0, 0, f * 8); +} diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c index 10d223b..eb18173 100644 --- a/gcc/tree-ssa-pre.c +++ b/gcc/tree-ssa-pre.c @@ -805,16 +805,36 @@ bitmap_set_free (bitmap_set_t set) bitmap_clear (&set->values); } +static void +pre_expr_DFS (pre_expr expr, bitmap_set_t set, bitmap expr_visited, + bitmap val_visited, vec &post); + +/* DFS walk leaders of VAL to their operands with leaders in SET, collecting + expressions in SET in postorder into POST. */ + +static void +pre_expr_DFS (unsigned val, bitmap_set_t set, bitmap expr_visited, + bitmap val_visited, vec &post) +{ + unsigned int i; + bitmap_iterator bi; + + /* Iterate over all leaders and DFS recurse. Borrowed from + bitmap_find_leader. */ + bitmap exprset = value_expressions[val]; + EXECUTE_IF_AND_IN_BITMAP (exprset, &set->expressions, 0, i, bi) + pre_expr_DFS (expression_for_id (i), + set, expr_visited, val_visited, post); +} /* DFS walk EXPR to its operands with leaders in SET, collecting expressions in SET in postorder into POST. */ static void -pre_expr_DFS (pre_expr expr, bitmap_set_t set, bitmap visited, - hash_set > &leader_set, - vec &post) +pre_expr_DFS (pre_expr expr, bitmap_set_t set, bitmap expr_visited, + bitmap val_visited, vec &post) { - if (!bitmap_set_bit (visited, get_expression_id (expr))) + if (!bitmap_set_bit (expr_visited, get_expression_id (expr))) return; switch (expr->kind) @@ -829,12 +849,9 @@ pre_expr_DFS (pre_expr expr, bitmap_set_t set, bitmap visited, unsigned int op_val_id = VN_INFO (nary->op[i])->value_id; /* If we already found a leader for the value we've recursed already. Avoid the costly bitmap_find_leader. */ - if (!leader_set.add (op_val_id)) - { - pre_expr leader = bitmap_find_leader (set, op_val_id); - if (leader) - pre_expr_DFS (leader, set, visited, leader_set, post); - } + if (bitmap_bit_p (&set->values, op_val_id) + && bitmap_set_bit (val_visited, op_val_id)) + pre_expr_DFS (op_val_id, set, expr_visited, val_visited, post); } break; } @@ -854,12 +871,10 @@ pre_expr_DFS (pre_expr expr, bitmap_set_t set, bitmap visited, if (!op[n] || TREE_CODE (op[n]) != SSA_NAME) continue; unsigned op_val_id = VN_INFO (op[n])->value_id; - if (!leader_set.add (op_val_id)) - { - pre_expr leader = bitmap_find_leader (set, op_val_id); - if (leader) - pre_expr_DFS (leader, set, visited, leader_set, post); - } + if (bitmap_bit_p (&set->values, op_val_id) + && bitmap_set_bit (val_visited, op_val_id)) + pre_expr_DFS (op_val_id, + set, expr_visited, val_visited, post); } } break; @@ -879,20 +894,15 @@ sorted_array_from_bitmap_set (bitmap_set_t set) vec result; /* Pre-allocate enough space for the array. */ - size_t len = bitmap_count_bits (&set->expressions); - result.create (len); - hash_set > leader_set (2*len); - - auto_bitmap visited (&grand_bitmap_obstack); - bitmap_tree_view (visited); - FOR_EACH_EXPR_ID_IN_SET (set, i, bi) - { - pre_expr expr = expression_for_id (i); - /* Hoist insertion calls us with a value-set we have to and with, - do so. */ - if (bitmap_set_contains_value (set, get_expr_value_id (expr))) - pre_expr_DFS (expr, set, visited, leader_set, result); - } + result.create (bitmap_count_bits (&set->expressions)); + + auto_bitmap expr_visited (&grand_bitmap_obstack); + auto_bitmap val_visited (&grand_bitmap_obstack); + bitmap_tree_view (expr_visited); + bitmap_tree_view (val_visited); + FOR_EACH_VALUE_ID_IN_SET (set, i, bi) + if (bitmap_set_bit (val_visited, i)) + pre_expr_DFS (i, set, expr_visited, val_visited, result); return result; } -- 2.7.4