From 896db49a442a15a1fa1f641cd0385da1ba1794e3 Mon Sep 17 00:00:00 2001 From: Richard Biener Date: Thu, 12 Nov 2020 15:05:03 +0100 Subject: [PATCH] More PRE compile-time optimizations This fixes a bug in bitmap_list_view which could end up with a NULL head->current which makes followup searches fail. Oops. It also further optimizes the PRE DFS walk by removing useless stuff and special-casing bitmaps with just one element for EXECUTE_IF_AND_IN_BITMAP which makes a quite big difference. 2020-11-12 Richard Biener * bitmap.c (bitmap_list_view): Restore head->current. * tree-ssa-pre.c (pre_expr_DFS): Elide expr_visited bitmap. Special-case value expression bitmaps with one element. (bitmap_find_leader): Likewise. (sorted_array_from_bitmap_set): Elide expr_visited bitmap. --- gcc/bitmap.c | 5 +++++ gcc/tree-ssa-pre.c | 40 +++++++++++++++++++++++----------------- 2 files changed, 28 insertions(+), 17 deletions(-) diff --git a/gcc/bitmap.c b/gcc/bitmap.c index 810b80be1ba..c849b0d22f5 100644 --- a/gcc/bitmap.c +++ b/gcc/bitmap.c @@ -678,6 +678,11 @@ bitmap_list_view (bitmap head) } head->tree_form = false; + if (!head->current) + { + head->current = head->first; + head->indx = head->current ? head->current->indx : 0; + } } /* Convert bitmap HEAD from linked-list view to splay-tree view. diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c index 9db1b0258f7..e25cec7ffa1 100644 --- a/gcc/tree-ssa-pre.c +++ b/gcc/tree-ssa-pre.c @@ -806,15 +806,15 @@ bitmap_set_free (bitmap_set_t set) } static void -pre_expr_DFS (pre_expr expr, bitmap_set_t set, bitmap expr_visited, - bitmap val_visited, vec &post); +pre_expr_DFS (pre_expr expr, bitmap_set_t set, 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) +pre_expr_DFS (unsigned val, bitmap_set_t set, bitmap val_visited, + vec &post) { unsigned int i; bitmap_iterator bi; @@ -822,21 +822,25 @@ pre_expr_DFS (unsigned val, bitmap_set_t set, bitmap expr_visited, /* Iterate over all leaders and DFS recurse. Borrowed from bitmap_find_leader. */ bitmap exprset = value_expressions[val]; + if (!exprset->first->next) + { + EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi) + if (bitmap_bit_p (&set->expressions, i)) + pre_expr_DFS (expression_for_id (i), set, val_visited, post); + return; + } + EXECUTE_IF_AND_IN_BITMAP (exprset, &set->expressions, 0, i, bi) - pre_expr_DFS (expression_for_id (i), - set, expr_visited, val_visited, post); + pre_expr_DFS (expression_for_id (i), set, 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 expr_visited, - bitmap val_visited, vec &post) +pre_expr_DFS (pre_expr expr, bitmap_set_t set, bitmap val_visited, + vec &post) { - if (!bitmap_set_bit (expr_visited, get_expression_id (expr))) - return; - switch (expr->kind) { case NARY: @@ -851,7 +855,7 @@ pre_expr_DFS (pre_expr expr, bitmap_set_t set, bitmap expr_visited, recursed already. Avoid the costly bitmap_find_leader. */ 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); + pre_expr_DFS (op_val_id, set, val_visited, post); } break; } @@ -873,8 +877,7 @@ pre_expr_DFS (pre_expr expr, bitmap_set_t set, bitmap expr_visited, unsigned op_val_id = VN_INFO (op[n])->value_id; 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); + pre_expr_DFS (op_val_id, set, val_visited, post); } } break; @@ -896,13 +899,11 @@ sorted_array_from_bitmap_set (bitmap_set_t set) /* Pre-allocate enough space for the array. */ 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); + pre_expr_DFS (i, set, val_visited, result); return result; } @@ -1883,6 +1884,11 @@ bitmap_find_leader (bitmap_set_t set, unsigned int val) bitmap_iterator bi; bitmap exprset = value_expressions[val]; + if (!exprset->first->next) + EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi) + if (bitmap_bit_p (&set->expressions, i)) + return expression_for_id (i); + EXECUTE_IF_AND_IN_BITMAP (exprset, &set->expressions, 0, i, bi) return expression_for_id (i); } -- 2.30.2