From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mx2.suse.de (mx2.suse.de [195.135.220.15]) by sourceware.org (Postfix) with ESMTPS id 103A239F6E78 for ; Thu, 12 Nov 2020 10:00:40 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 103A239F6E78 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=rguenther@suse.de X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id DBB6FADE2 for ; Thu, 12 Nov 2020 10:00:38 +0000 (UTC) Date: Thu, 12 Nov 2020 11:00:38 +0100 (CET) From: Richard Biener Sender: rguenther@ryzen.fritz.box To: gcc-patches@gcc.gnu.org Subject: [PATCH] tree-optimization/97806 - fix PRE expression post order Message-ID: User-Agent: Alpine 2.21 (LSU 202 2017-01-01) MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII X-Spam-Status: No, score=-11.2 required=5.0 tests=BAYES_00, GIT_PATCH_0, KAM_DMARC_STATUS, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 12 Nov 2020 10:00:41 -0000 This fixes the postorder compute for the case of multiple expression leaders for a value. Bootstrapped and tested on x86_64-unknown-linux-gnu, pushed. 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 00000000000..9ec3299c0b1 --- /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 10d223bd365..eb181735e7f 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.26.2