From patchwork Tue Sep 21 16:53:44 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Aldy Hernandez X-Patchwork-Id: 45248 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 3D4B6385841C for ; Tue, 21 Sep 2021 16:59:34 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 3D4B6385841C DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1632243574; bh=SsSilHF61099LbxFmDmo36ijk+sUsO5tsiEGN5VS86c=; h=To:Subject:Date:In-Reply-To:References:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To:Cc: From; b=h6fmqCDuucie0axwsfVBCbblFXvdnniSqfiRiEr/Yd0O+U9+OLQgwu+/shWioMF3b Zh7OxesCMnGgehkG/pduyhjDMTHOTjd/SBBJVKn6GuUjpwtyZP7VBSdlcFV7myU7k1 YpB74HJgAKjxBAcORIcOvnI4RAF/yyAxAaUrAN+U= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTP id A8E0A385842E for ; Tue, 21 Sep 2021 16:54:12 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org A8E0A385842E Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-564-N6x_K18WOZWBCUs8uFPp8Q-1; Tue, 21 Sep 2021 12:54:10 -0400 X-MC-Unique: N6x_K18WOZWBCUs8uFPp8Q-1 Received: from smtp.corp.redhat.com (int-mx02.intmail.prod.int.phx2.redhat.com [10.5.11.12]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id E9CFF84A5E1; Tue, 21 Sep 2021 16:54:09 +0000 (UTC) Received: from abulafia.quesejoda.com (unknown [10.39.192.248]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 695B360C5F; Tue, 21 Sep 2021 16:54:03 +0000 (UTC) Received: from abulafia.quesejoda.com (localhost [127.0.0.1]) by abulafia.quesejoda.com (8.16.1/8.15.2) with ESMTPS id 18LGs1SG414663 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Tue, 21 Sep 2021 18:54:01 +0200 Received: (from aldyh@localhost) by abulafia.quesejoda.com (8.16.1/8.16.1/Submit) id 18LGs1jH414662; Tue, 21 Sep 2021 18:54:01 +0200 To: Andrew MacLeod Subject: [PATCH 1/7] Allocate non_null_ref tables at creation. Date: Tue, 21 Sep 2021 18:53:44 +0200 Message-Id: <20210921165350.414593-2-aldyh@redhat.com> In-Reply-To: <20210921165350.414593-1-aldyh@redhat.com> References: <20210921165350.414593-1-aldyh@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.79 on 10.5.11.12 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-13.8 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) 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-Patchwork-Original-From: Aldy Hernandez via Gcc-patches From: Aldy Hernandez Reply-To: Aldy Hernandez Cc: GCC patches Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" Preallocating the space is slightly cheaper than calling safe_grow_cleared. Committed. gcc/ChangeLog: * gimple-range-cache.cc (non_null_ref::non_null_ref): Use create and quick_grow_cleared instead of safe_grow_cleared. --- gcc/gimple-range-cache.cc | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index fbf0f95eef9..b856b212169 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -37,8 +37,8 @@ along with GCC; see the file COPYING3. If not see non_null_ref::non_null_ref () { - m_nn.create (0); - m_nn.safe_grow_cleared (num_ssa_names); + m_nn.create (num_ssa_names); + m_nn.quick_grow_cleared (num_ssa_names); bitmap_obstack_initialize (&m_bitmaps); } From patchwork Tue Sep 21 16:53:45 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Aldy Hernandez X-Patchwork-Id: 45249 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 5E5203858439 for ; Tue, 21 Sep 2021 17:00:30 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 5E5203858439 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1632243630; bh=32R3fQZZUdvg1eVtYP8Y7BIGezuU4+WLMqmYc4KtKnA=; h=To:Subject:Date:In-Reply-To:References:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To:Cc: From; b=POUZ3B8qpIt4JmDeO8soT++Ahj8q0uVDZkje7ejyRJxGp/5syU/h4kdj3M6vGZiAX PqAyg9s+463qL6BZ7QuG3Fmn5FvWvTLL5MazapeUflpI0PDty0e9X0uaTRUDjVWAqW 4a39Iw0EOkb7GZfMQ3CgFFruFg3A+c/Qy3r/j69I= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTP id D678B3858005 for ; Tue, 21 Sep 2021 16:54:12 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org D678B3858005 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-92-cNCLg7_KMRemNv1ixhX5nA-1; Tue, 21 Sep 2021 12:54:09 -0400 X-MC-Unique: cNCLg7_KMRemNv1ixhX5nA-1 Received: from smtp.corp.redhat.com (int-mx07.intmail.prod.int.phx2.redhat.com [10.5.11.22]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 365FF1018F62; Tue, 21 Sep 2021 16:54:08 +0000 (UTC) Received: from abulafia.quesejoda.com (unknown [10.39.192.248]) by smtp.corp.redhat.com (Postfix) with ESMTPS id C0B3E1024873; Tue, 21 Sep 2021 16:54:07 +0000 (UTC) Received: from abulafia.quesejoda.com (localhost [127.0.0.1]) by abulafia.quesejoda.com (8.16.1/8.15.2) with ESMTPS id 18LGs5m0414667 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Tue, 21 Sep 2021 18:54:05 +0200 Received: (from aldyh@localhost) by abulafia.quesejoda.com (8.16.1/8.16.1/Submit) id 18LGs5iY414666; Tue, 21 Sep 2021 18:54:05 +0200 To: Andrew MacLeod Subject: [PATCH 2/7] Do not query SCEV in range_of_phi unless dominators are available. Date: Tue, 21 Sep 2021 18:53:45 +0200 Message-Id: <20210921165350.414593-3-aldyh@redhat.com> In-Reply-To: <20210921165350.414593-1-aldyh@redhat.com> References: <20210921165350.414593-1-aldyh@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.84 on 10.5.11.22 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-13.8 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) 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-Patchwork-Original-From: Aldy Hernandez via Gcc-patches From: Aldy Hernandez Reply-To: Aldy Hernandez Cc: GCC patches Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" SCEV won't work without dominators and we can get called without dominators from debug_ranger. Another option would be to rename scev_initialized_p to something like scev_available_p and move the check there. For now, this will do. Committed. gcc/ChangeLog: * gimple-range-fold.cc (fold_using_range::range_of_phi): Check dom_info_available_p. --- gcc/gimple-range-fold.cc | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc index 997d02dd4b9..4dbf4188ec2 100644 --- a/gcc/gimple-range-fold.cc +++ b/gcc/gimple-range-fold.cc @@ -781,7 +781,9 @@ fold_using_range::range_of_phi (irange &r, gphi *phi, fur_source &src) } // If SCEV is available, query if this PHI has any knonwn values. - if (scev_initialized_p () && !POINTER_TYPE_P (TREE_TYPE (phi_def))) + if (dom_info_available_p (CDI_DOMINATORS) + && scev_initialized_p () + && !POINTER_TYPE_P (TREE_TYPE (phi_def))) { value_range loop_range; class loop *l = loop_containing_stmt (phi); From patchwork Tue Sep 21 16:53:46 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Aldy Hernandez X-Patchwork-Id: 45246 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 0EB59385841F for ; Tue, 21 Sep 2021 16:57:24 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 0EB59385841F DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1632243444; bh=3oTcb5l0QRns1ikVubp+1NdZ/4hQUXezmHVhEPFPCQk=; h=To:Subject:Date:In-Reply-To:References:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To:Cc: From; b=lIgjXIkaiq4Ma3yXbRKopAaClREThQRmuya9Bm/aT64QY0T1Z8+WK2XzoQxV47a7K hKvlolYH4z8hwa26lsauZRxEYAfLsbTt8F+cCSiOI7iHjchraU1ZzhexR8tGveB4VV L7f7cIhUYnniImZOjv1nFQEcECqCukTfe9ovTlTQ= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [216.205.24.124]) by sourceware.org (Postfix) with ESMTP id 84A48385843A for ; Tue, 21 Sep 2021 16:54:11 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 84A48385843A Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-417-AJPceUQsNliQq0zlVDK5Cg-1; Tue, 21 Sep 2021 12:54:09 -0400 X-MC-Unique: AJPceUQsNliQq0zlVDK5Cg-1 Received: from smtp.corp.redhat.com (int-mx07.intmail.prod.int.phx2.redhat.com [10.5.11.22]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 6796684A5E0; Tue, 21 Sep 2021 16:54:08 +0000 (UTC) Received: from abulafia.quesejoda.com (unknown [10.39.192.248]) by smtp.corp.redhat.com (Postfix) with ESMTPS id F28851010424; Tue, 21 Sep 2021 16:54:07 +0000 (UTC) Received: from abulafia.quesejoda.com (localhost [127.0.0.1]) by abulafia.quesejoda.com (8.16.1/8.15.2) with ESMTPS id 18LGs5Kk414671 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Tue, 21 Sep 2021 18:54:05 +0200 Received: (from aldyh@localhost) by abulafia.quesejoda.com (8.16.1/8.16.1/Submit) id 18LGs5Pj414670; Tue, 21 Sep 2021 18:54:05 +0200 To: Andrew MacLeod Subject: [PATCH 3/7] Move postfold_gcond_edges into fur_source. Date: Tue, 21 Sep 2021 18:53:46 +0200 Message-Id: <20210921165350.414593-4-aldyh@redhat.com> In-Reply-To: <20210921165350.414593-1-aldyh@redhat.com> References: <20210921165350.414593-1-aldyh@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.84 on 10.5.11.22 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-13.8 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) 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-Patchwork-Original-From: Aldy Hernandez via Gcc-patches From: Aldy Hernandez Reply-To: Aldy Hernandez Cc: GCC patches Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" The code registering outgoing edges from a cond is living in fold_using_range, which makes it difficult to be called from other places. Also, it refuses to register relations on the outgoing destinations that have more than one predecessor. This latter issue is a problem because we would like to register outgoing edges along a path in the path solver (regardless of single_pred_p). Committed. gcc/ChangeLog: * gimple-range-fold.cc (fold_using_range::range_of_range_op): Rename postfold_gcond_edges to register_outgoing_edges and adapt. (fold_using_range::postfold_gcond_edges): Rename... (fur_source::register_outgoing_edges): ...to this. * gimple-range-fold.h (postfold_gcond_edges): Rename to register_outgoing_edges and move to fur_source. --- gcc/gimple-range-fold.cc | 44 ++++++++++++++++++++-------------------- gcc/gimple-range-fold.h | 2 +- 2 files changed, 23 insertions(+), 23 deletions(-) diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc index 4dbf4188ec2..921e8e3388f 100644 --- a/gcc/gimple-range-fold.cc +++ b/gcc/gimple-range-fold.cc @@ -651,7 +651,17 @@ fold_using_range::range_of_range_op (irange &r, gimple *s, fur_source &src) } } else if (is_a (s)) - postfold_gcond_edges (as_a (s), r, src); + { + basic_block bb = gimple_bb (s); + edge e0 = EDGE_SUCC (bb, 0); + edge e1 = EDGE_SUCC (bb, 1); + + if (!single_pred_p (e0->dest)) + e0 = NULL; + if (!single_pred_p (e1->dest)) + e1 = NULL; + src.register_outgoing_edges (as_a (s), r, e0, e1); + } } else r.set_varying (type); @@ -1353,8 +1363,7 @@ fold_using_range::relation_fold_and_or (irange& lhs_range, gimple *s, // Register any outgoing edge relations from a conditional branch. void -fold_using_range::postfold_gcond_edges (gcond *s, irange& lhs_range, - fur_source &src) +fur_source::register_outgoing_edges (gcond *s, irange &lhs_range, edge e0, edge e1) { int_range_max r; int_range<2> e0_range, e1_range; @@ -1366,10 +1375,7 @@ fold_using_range::postfold_gcond_edges (gcond *s, irange& lhs_range, if (!bb) return; - edge e0 = EDGE_SUCC (bb, 0); - if (!single_pred_p (e0->dest)) - e0 = NULL; - else + if (e0) { // If this edge is never taken, ignore it. gcond_edge_range (e0_range, e0); @@ -1379,10 +1385,7 @@ fold_using_range::postfold_gcond_edges (gcond *s, irange& lhs_range, } - edge e1 = EDGE_SUCC (bb, 1); - if (!single_pred_p (e1->dest)) - e1 = NULL; - else + if (e1) { // If this edge is never taken, ignore it. gcond_edge_range (e1_range, e1); @@ -1391,7 +1394,6 @@ fold_using_range::postfold_gcond_edges (gcond *s, irange& lhs_range, e1 = NULL; } - // At least one edge needs to be single pred. if (!e0 && !e1) return; @@ -1407,27 +1409,25 @@ fold_using_range::postfold_gcond_edges (gcond *s, irange& lhs_range, { relation_kind relation = handler->op1_op2_relation (e0_range); if (relation != VREL_NONE) - src.register_relation (e0, relation, ssa1, ssa2); + register_relation (e0, relation, ssa1, ssa2); } if (e1) { relation_kind relation = handler->op1_op2_relation (e1_range); if (relation != VREL_NONE) - src.register_relation (e1, relation, ssa1, ssa2); + register_relation (e1, relation, ssa1, ssa2); } } // Outgoing relations of GORI exports require a gori engine. - if (!src.gori ()) + if (!gori ()) return; - range_query *q = src.query (); // Now look for other relations in the exports. This will find stmts // leading to the condition such as: // c_2 = a_4 < b_7 // if (c_2) - - FOR_EACH_GORI_EXPORT_NAME (*(src.gori ()), bb, name) + FOR_EACH_GORI_EXPORT_NAME (*(gori ()), bb, name) { if (TREE_CODE (TREE_TYPE (name)) != BOOLEAN_TYPE) continue; @@ -1439,19 +1439,19 @@ fold_using_range::postfold_gcond_edges (gcond *s, irange& lhs_range, tree ssa2 = gimple_range_ssa_p (gimple_range_operand2 (stmt)); if (ssa1 && ssa2) { - if (e0 && src.gori ()->outgoing_edge_range_p (r, e0, name, *q) + if (e0 && gori ()->outgoing_edge_range_p (r, e0, name, *m_query) && r.singleton_p ()) { relation_kind relation = handler->op1_op2_relation (r); if (relation != VREL_NONE) - src.register_relation (e0, relation, ssa1, ssa2); + register_relation (e0, relation, ssa1, ssa2); } - if (e1 && src.gori ()->outgoing_edge_range_p (r, e1, name, *q) + if (e1 && gori ()->outgoing_edge_range_p (r, e1, name, *m_query) && r.singleton_p ()) { relation_kind relation = handler->op1_op2_relation (r); if (relation != VREL_NONE) - src.register_relation (e1, relation, ssa1, ssa2); + register_relation (e1, relation, ssa1, ssa2); } } } diff --git a/gcc/gimple-range-fold.h b/gcc/gimple-range-fold.h index ceed7ba48e1..d62d29b7133 100644 --- a/gcc/gimple-range-fold.h +++ b/gcc/gimple-range-fold.h @@ -129,6 +129,7 @@ public: tree op2); virtual void register_relation (edge e, relation_kind k, tree op1, tree op2); + void register_outgoing_edges (gcond *, irange &lhs_range, edge e0, edge e1); protected: range_query *m_query; gori_compute *m_gori; @@ -188,6 +189,5 @@ protected: void range_of_ssa_name_with_loop_info (irange &, tree, class loop *, gphi *, fur_source &src); void relation_fold_and_or (irange& lhs_range, gimple *s, fur_source &src); - void postfold_gcond_edges (gcond *s, irange &lhs_range, fur_source &src); }; #endif // GCC_GIMPLE_RANGE_FOLD_H From patchwork Tue Sep 21 16:53:47 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Aldy Hernandez X-Patchwork-Id: 45247 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 5FBAA3858002 for ; Tue, 21 Sep 2021 16:58:20 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 5FBAA3858002 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1632243500; bh=m5YZ81ZOzau8oE8LNeNmOSKYED4L9T7v+BlL+simVvE=; h=To:Subject:Date:In-Reply-To:References:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To:Cc: From; b=nO4g1SjqtvUleV1Qp+e8wJexKjjVYGg3NA41HxRk49CVsxAfnItab/EgQbbZJL6bP GkGUGBYU1FssQ3w0LWLNQwwBJVe/CrzYk5085B6jjnciQuiqtlfozXo+CJyrDH1Xwb 52BR3Wfi0lur6eJdZAfhKzQEnKcUXPe2NrLV65Q8= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [216.205.24.124]) by sourceware.org (Postfix) with ESMTP id 30CF63858422 for ; Tue, 21 Sep 2021 16:54:11 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 30CF63858422 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-371-YCuPujU_Obmrazj1v-LojQ-1; Tue, 21 Sep 2021 12:54:09 -0400 X-MC-Unique: YCuPujU_Obmrazj1v-LojQ-1 Received: from smtp.corp.redhat.com (int-mx04.intmail.prod.int.phx2.redhat.com [10.5.11.14]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 36B0E100724C; Tue, 21 Sep 2021 16:54:08 +0000 (UTC) Received: from abulafia.quesejoda.com (unknown [10.39.192.248]) by smtp.corp.redhat.com (Postfix) with ESMTPS id C07905DA2D; Tue, 21 Sep 2021 16:54:07 +0000 (UTC) Received: from abulafia.quesejoda.com (localhost [127.0.0.1]) by abulafia.quesejoda.com (8.16.1/8.15.2) with ESMTPS id 18LGs5tW414675 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Tue, 21 Sep 2021 18:54:05 +0200 Received: (from aldyh@localhost) by abulafia.quesejoda.com (8.16.1/8.16.1/Submit) id 18LGs5B1414674; Tue, 21 Sep 2021 18:54:05 +0200 To: Andrew MacLeod Subject: [PATCH 4/7] path solver: Add relation support. Date: Tue, 21 Sep 2021 18:53:47 +0200 Message-Id: <20210921165350.414593-5-aldyh@redhat.com> In-Reply-To: <20210921165350.414593-1-aldyh@redhat.com> References: <20210921165350.414593-1-aldyh@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.79 on 10.5.11.14 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-13.8 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) 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-Patchwork-Original-From: Aldy Hernandez via Gcc-patches From: Aldy Hernandez Reply-To: Aldy Hernandez Cc: GCC patches Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" This patch adds relational support to the path solver. It uses a path_oracle that keeps track of relations within a path which are augmented by relations on entry to the path. With it, range_of_stmt, range_of_expr, and friends can give relation aware answers. Committed. gcc/ChangeLog: * gimple-range-fold.h (class fur_source): Make oracle protected. * gimple-range-path.cc (path_range_query::path_range_query): Add resolve argument. Initialize oracle. (path_range_query::~path_range_query): Delete oracle. (path_range_query::range_of_stmt): Adapt to use relations. (path_range_query::precompute_ranges): Pre-compute relations. (class jt_fur_source): New (jt_fur_source::jt_fur_source): New. (jt_fur_source::register_relation): New. (jt_fur_source::query_relation): New. (path_range_query::precompute_relations): New. (path_range_query::precompute_phi_relations): New. * gimple-range-path.h (path_range_query): Add resolve argument. Add oracle, precompute_relations, precompute_phi_relations. * tree-ssa-threadbackward.c (back_threader::back_threader): Pass resolve argument to solver. --- gcc/gimple-range-fold.h | 2 +- gcc/gimple-range-path.cc | 204 +++++++++++++++++++++++++++++++--- gcc/gimple-range-path.h | 15 ++- gcc/tree-ssa-threadbackward.c | 2 +- 4 files changed, 200 insertions(+), 23 deletions(-) diff --git a/gcc/gimple-range-fold.h b/gcc/gimple-range-fold.h index d62d29b7133..bc0874b5f31 100644 --- a/gcc/gimple-range-fold.h +++ b/gcc/gimple-range-fold.h @@ -160,7 +160,7 @@ public: tree op2) OVERRIDE; virtual void register_relation (edge e, relation_kind k, tree op1, tree op2) OVERRIDE; -private: +protected: relation_oracle *m_oracle; }; diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc index 10b018b5211..b3040c9bc00 100644 --- a/gcc/gimple-range-path.cc +++ b/gcc/gimple-range-path.cc @@ -30,11 +30,13 @@ along with GCC; see the file COPYING3. If not see #include "tree-pretty-print.h" #include "gimple-range-path.h" #include "ssa.h" +#include "tree-cfg.h" +#include "gimple-iterator.h" // Internal construct to help facilitate debugging of solver. #define DEBUG_SOLVER (0 && dump_file) -path_range_query::path_range_query (gimple_ranger &ranger) +path_range_query::path_range_query (gimple_ranger &ranger, bool resolve) : m_ranger (ranger) { if (DEBUG_SOLVER) @@ -43,12 +45,15 @@ path_range_query::path_range_query (gimple_ranger &ranger) m_cache = new ssa_global_cache; m_has_cache_entry = BITMAP_ALLOC (NULL); m_path = NULL; + m_resolve = resolve; + m_oracle = new path_oracle (ranger.oracle ()); } path_range_query::~path_range_query () { BITMAP_FREE (m_has_cache_entry); delete m_cache; + delete m_oracle; } // Mark cache entry for NAME as unused. @@ -161,22 +166,6 @@ path_range_query::unreachable_path_p () return m_undefined_path; } -// Return the range of STMT at the end of the path being analyzed. - -bool -path_range_query::range_of_stmt (irange &r, gimple *stmt, tree) -{ - tree type = gimple_range_type (stmt); - - if (!irange::supports_type_p (type)) - return false; - - if (!fold_range (r, stmt, this)) - r.set_varying (type); - - return true; -} - // Initialize the current path to PATH. The current block is set to // the entry block to the path. // @@ -371,6 +360,12 @@ path_range_query::precompute_ranges (const vec &path, m_imports = imports; m_undefined_path = false; + if (m_resolve) + { + m_oracle->reset_path (); + precompute_relations (path); + } + if (DEBUG_SOLVER) { fprintf (dump_file, "\npath_range_query: precompute_ranges for path: "); @@ -400,3 +395,178 @@ path_range_query::precompute_ranges (const vec &path, if (DEBUG_SOLVER) dump (dump_file); } + +// A folding aid used to register and query relations along a path. +// When queried, it returns relations as they would appear on exit to +// the path. +// +// Relations are registered on entry so the path_oracle knows which +// block to query the root oracle at when a relation lies outside the +// path. However, when queried we return the relation on exit to the +// path, since the root_oracle ignores the registered. + +class jt_fur_source : public fur_depend +{ +public: + jt_fur_source (gimple *s, path_range_query *, gori_compute *, + const vec &); + relation_kind query_relation (tree op1, tree op2) override; + void register_relation (gimple *, relation_kind, tree op1, tree op2) override; + void register_relation (edge, relation_kind, tree op1, tree op2) override; +private: + basic_block m_entry; +}; + +jt_fur_source::jt_fur_source (gimple *s, + path_range_query *query, + gori_compute *gori, + const vec &path) + : fur_depend (s, gori, query) +{ + gcc_checking_assert (!path.is_empty ()); + + m_entry = path[path.length () - 1]; + + if (dom_info_available_p (CDI_DOMINATORS)) + m_oracle = query->oracle (); + else + m_oracle = NULL; +} + +// Ignore statement and register relation on entry to path. + +void +jt_fur_source::register_relation (gimple *, relation_kind k, tree op1, tree op2) +{ + if (m_oracle) + m_oracle->register_relation (m_entry, k, op1, op2); +} + +// Ignore edge and register relation on entry to path. + +void +jt_fur_source::register_relation (edge, relation_kind k, tree op1, tree op2) +{ + if (m_oracle) + m_oracle->register_relation (m_entry, k, op1, op2); +} + +relation_kind +jt_fur_source::query_relation (tree op1, tree op2) +{ + if (!m_oracle) + return VREL_NONE; + + if (TREE_CODE (op1) != SSA_NAME || TREE_CODE (op2) != SSA_NAME) + return VREL_NONE; + + return m_oracle->query_relation (m_entry, op1, op2); +} + +// Return the range of STMT at the end of the path being analyzed. + +bool +path_range_query::range_of_stmt (irange &r, gimple *stmt, tree) +{ + tree type = gimple_range_type (stmt); + + if (!irange::supports_type_p (type)) + return false; + + // If resolving unknowns, fold the statement as it would have + // appeared at the end of the path. + if (m_resolve) + { + fold_using_range f; + jt_fur_source src (stmt, this, &m_ranger.gori (), *m_path); + if (!f.fold_stmt (r, stmt, src)) + r.set_varying (type); + } + // Otherwise, use the global ranger to fold it as it would appear in + // the original IL. This is more conservative, but faster. + else if (!fold_range (r, stmt, this)) + r.set_varying (type); + + return true; +} + +// Precompute relations on a path. This involves two parts: relations +// along the conditionals joining a path, and relations determined by +// examining PHIs. + +void +path_range_query::precompute_relations (const vec &path) +{ + if (!dom_info_available_p (CDI_DOMINATORS)) + return; + + jt_fur_source src (NULL, this, &m_ranger.gori (), path); + basic_block prev = NULL; + for (unsigned i = path.length (); i > 0; --i) + { + basic_block bb = path[i - 1]; + gimple *stmt = last_stmt (bb); + + precompute_phi_relations (bb, prev); + + // Compute relations in outgoing edges along the path. Skip the + // final conditional which we don't know yet. + if (i > 1 + && stmt + && gimple_code (stmt) == GIMPLE_COND + && irange::supports_type_p (TREE_TYPE (gimple_cond_lhs (stmt)))) + { + basic_block next = path[i - 2]; + int_range<2> r; + gcond *cond = as_a (stmt); + + if (EDGE_SUCC (bb, 0)->dest == next) + gcond_edge_range (r, EDGE_SUCC (bb, 0)); + else if (EDGE_SUCC (bb, 1)->dest == next) + gcond_edge_range (r, EDGE_SUCC (bb, 1)); + else + gcc_unreachable (); + + edge e0 = EDGE_SUCC (bb, 0); + edge e1 = EDGE_SUCC (bb, 1); + src.register_outgoing_edges (cond, r, e0, e1); + } + prev = bb; + } +} + +// Precompute relations for each PHI in BB. For example: +// +// x_5 = PHI +// +// If the path flows through BB5, we can register that x_5 == y_9. + +void +path_range_query::precompute_phi_relations (basic_block bb, basic_block prev) +{ + if (prev == NULL) + return; + + basic_block entry = entry_bb (); + edge e_in = find_edge (prev, bb); + gcc_checking_assert (e_in); + + for (gphi_iterator iter = gsi_start_phis (bb); !gsi_end_p (iter); + gsi_next (&iter)) + { + gphi *phi = iter.phi (); + tree result = gimple_phi_result (phi); + unsigned nargs = gimple_phi_num_args (phi); + + for (size_t i = 0; i < nargs; ++i) + if (e_in == gimple_phi_arg_edge (phi, i)) + { + tree arg = gimple_phi_arg_def (phi, i); + + if (gimple_range_ssa_p (arg)) + m_oracle->register_relation (entry, EQ_EXPR, arg, result); + + break; + } + } +} diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h index c75721f6dc0..d12fd7743ca 100644 --- a/gcc/gimple-range-path.h +++ b/gcc/gimple-range-path.h @@ -35,13 +35,14 @@ along with GCC; see the file COPYING3. If not see class path_range_query : public range_query { public: - path_range_query (class gimple_ranger &ranger); + path_range_query (class gimple_ranger &ranger, bool resolve); virtual ~path_range_query (); void precompute_ranges (const vec &path, const bitmap_head *imports); bool range_of_expr (irange &r, tree name, gimple * = NULL) override; bool range_of_stmt (irange &r, gimple *, tree name = NULL) override; bool unreachable_path_p (); + path_oracle *oracle () { return m_oracle; } void dump (FILE *) override; void debug (); @@ -58,6 +59,8 @@ private: void precompute_ranges_in_block (basic_block bb); void adjust_for_non_null_uses (basic_block bb); void ssa_range_in_phi (irange &r, gphi *phi); + void precompute_relations (const vec &); + void precompute_phi_relations (basic_block bb, basic_block prev); // Path navigation. void set_path (const vec &); @@ -79,12 +82,16 @@ private: // Path being analyzed. const vec *m_path; - // Current path position. - unsigned m_pos; - const bitmap_head *m_imports; gimple_ranger &m_ranger; non_null_ref m_non_null; + path_oracle *m_oracle; + + // Current path position. + unsigned m_pos; + + // Use ranger to resolve anything not known on entry. + bool m_resolve; // Set if there were any undefined expressions while pre-calculating path. bool m_undefined_path; diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c index c6530d3a6bb..95542079faf 100644 --- a/gcc/tree-ssa-threadbackward.c +++ b/gcc/tree-ssa-threadbackward.c @@ -122,7 +122,7 @@ const edge back_threader::UNREACHABLE_EDGE = (edge) -1; back_threader::back_threader (bool speed_p) : m_registry (param_max_fsm_thread_paths), m_profit (speed_p), - m_solver (m_ranger) + m_solver (m_ranger, /*resolve=*/false) { m_last_stmt = NULL; m_imports = BITMAP_ALLOC (NULL); From patchwork Tue Sep 21 16:53:48 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Aldy Hernandez X-Patchwork-Id: 45250 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id A255F385842E for ; Tue, 21 Sep 2021 17:01:26 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org A255F385842E DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1632243686; bh=ZP95xm2G6MELGcV/mNk+ICgbDr0NDtfBUYoAouOLD8M=; h=To:Subject:Date:In-Reply-To:References:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To:Cc: From; b=IXVJjw26xEHC4FaLAs92xwKLkgz5Q5lYUV4fACeGz/NKUqToNEdE2la3TqmVgfF5H d0m6WAnsJKAdfzexxmNHaw9NttPqbabvJrp4Ei5o90zTMoIOn6j7S+f34XsPS5Zdn1 h/I3snOQknDFCFbIpiR6MOfD8NcgCQgehZb0wpYE= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [216.205.24.124]) by sourceware.org (Postfix) with ESMTP id AA1BD3858422 for ; Tue, 21 Sep 2021 16:54:15 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org AA1BD3858422 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-375-hO3h_dyWPpKFTx2W7d-JBQ-1; Tue, 21 Sep 2021 12:54:14 -0400 X-MC-Unique: hO3h_dyWPpKFTx2W7d-JBQ-1 Received: from smtp.corp.redhat.com (int-mx01.intmail.prod.int.phx2.redhat.com [10.5.11.11]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 3942E1018F61; Tue, 21 Sep 2021 16:54:13 +0000 (UTC) Received: from abulafia.quesejoda.com (unknown [10.39.192.248]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 0684B6D985; Tue, 21 Sep 2021 16:54:07 +0000 (UTC) Received: from abulafia.quesejoda.com (localhost [127.0.0.1]) by abulafia.quesejoda.com (8.16.1/8.15.2) with ESMTPS id 18LGs5ql414679 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Tue, 21 Sep 2021 18:54:05 +0200 Received: (from aldyh@localhost) by abulafia.quesejoda.com (8.16.1/8.16.1/Submit) id 18LGs51v414678; Tue, 21 Sep 2021 18:54:05 +0200 To: Andrew MacLeod Subject: [PATCH 5/7] path solver: Remove useless code. Date: Tue, 21 Sep 2021 18:53:48 +0200 Message-Id: <20210921165350.414593-6-aldyh@redhat.com> In-Reply-To: <20210921165350.414593-1-aldyh@redhat.com> References: <20210921165350.414593-1-aldyh@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.79 on 10.5.11.11 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-13.8 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) 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-Patchwork-Original-From: Aldy Hernandez via Gcc-patches From: Aldy Hernandez Reply-To: Aldy Hernandez Cc: GCC patches Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" Committed. gcc/ChangeLog: * gimple-range-path.cc (path_range_query::range_defined_in_block): Remove useless code. --- gcc/gimple-range-path.cc | 4 ---- 1 file changed, 4 deletions(-) diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc index b3040c9bc00..b86a76fa74b 100644 --- a/gcc/gimple-range-path.cc +++ b/gcc/gimple-range-path.cc @@ -246,10 +246,6 @@ path_range_query::range_defined_in_block (irange &r, tree name, basic_block bb) fprintf (dump_file, "\n"); } - // We may have an artificial statement not in the IL. - if (!bb && r.varying_p ()) - return false; - return true; } From patchwork Tue Sep 21 16:53:49 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Aldy Hernandez X-Patchwork-Id: 45245 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 471AE3858437 for ; Tue, 21 Sep 2021 16:56:27 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 471AE3858437 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1632243387; bh=DrTA6A1HiS6fZ2jg1CN8XeMzCSbMKPqQAo6bBcfcDF4=; h=To:Subject:Date:In-Reply-To:References:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To:Cc: From; b=pT/0/i5ydGOhVo2DlWFUcicyuoMKR9Ci99pKmY2/qW4+nu9yabWxjHgXeVdtAhZUN 2zDRYGBGd2/e+BJKciIBnpNMq7rD7Y1a/3DzGwJTu4KgOgWBMQwPJczQ/eTvyTppno RtLQNJvtY62GFzUNHrOykIZbomc8fFCVAwhgWHxc= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTP id 674A73858020 for ; Tue, 21 Sep 2021 16:54:11 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 674A73858020 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-192-SM5Y96_LNdqNafLmUzITZg-1; Tue, 21 Sep 2021 12:54:09 -0400 X-MC-Unique: SM5Y96_LNdqNafLmUzITZg-1 Received: from smtp.corp.redhat.com (int-mx07.intmail.prod.int.phx2.redhat.com [10.5.11.22]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 362FF1007249; Tue, 21 Sep 2021 16:54:08 +0000 (UTC) Received: from abulafia.quesejoda.com (unknown [10.39.192.248]) by smtp.corp.redhat.com (Postfix) with ESMTPS id C0C201024888; Tue, 21 Sep 2021 16:54:07 +0000 (UTC) Received: from abulafia.quesejoda.com (localhost [127.0.0.1]) by abulafia.quesejoda.com (8.16.1/8.15.2) with ESMTPS id 18LGs5aG414683 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Tue, 21 Sep 2021 18:54:05 +0200 Received: (from aldyh@localhost) by abulafia.quesejoda.com (8.16.1/8.16.1/Submit) id 18LGs5Jr414682; Tue, 21 Sep 2021 18:54:05 +0200 To: Andrew MacLeod Subject: [PATCH 6/7] path solver: Add related SSAs to solvable set. Date: Tue, 21 Sep 2021 18:53:49 +0200 Message-Id: <20210921165350.414593-7-aldyh@redhat.com> In-Reply-To: <20210921165350.414593-1-aldyh@redhat.com> References: <20210921165350.414593-1-aldyh@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.84 on 10.5.11.22 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-13.8 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) 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-Patchwork-Original-From: Aldy Hernandez via Gcc-patches From: Aldy Hernandez Reply-To: Aldy Hernandez Cc: GCC patches Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" The path solver takes an initial set of SSA names which are deemed interesting. These are then solved along the path. Adding any copies of said SSA names to the list of interesting names yields significantly better results. This patch adds said copies to the already provided list. Currently this code is guarded by "m_resolve", which is the more expensive mode, but it would be reasonable to make it available always, especially since adding more imports usually has minimal impact on the processing time. I will investigate and make it universally available if this is indeed the case. Committed. gcc/ChangeLog: * gimple-range-path.cc (path_range_query::add_to_imports): New. (path_range_query::add_copies_to_imports): New. (path_range_query::precompute_ranges): Call add_copies_to_imports. * gimple-range-path.h (class path_range_query): Add prototypes for add_copies_to_imports and add_to_imports. --- gcc/gimple-range-path.cc | 80 +++++++++++++++++++++++++++++++++++++++- gcc/gimple-range-path.h | 4 +- 2 files changed, 82 insertions(+), 2 deletions(-) diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc index b86a76fa74b..a8ead3da4dc 100644 --- a/gcc/gimple-range-path.cc +++ b/gcc/gimple-range-path.cc @@ -343,6 +343,71 @@ path_range_query::adjust_for_non_null_uses (basic_block bb) } } +// If NAME is a supported SSA_NAME, add it the bitmap in IMPORTS. + +bool +path_range_query::add_to_imports (tree name, bitmap imports) +{ + if (TREE_CODE (name) == SSA_NAME + && irange::supports_type_p (TREE_TYPE (name))) + return bitmap_set_bit (imports, SSA_NAME_VERSION (name)); + return false; +} + +// Add the copies of any SSA names in IMPORTS to IMPORTS. +// +// These are hints for the solver. Adding more elements (within +// reason) doesn't slow us down, because we don't solve anything that +// doesn't appear in the path. On the other hand, not having enough +// imports will limit what we can solve. + +void +path_range_query::add_copies_to_imports () +{ + auto_vec worklist (bitmap_count_bits (m_imports)); + bitmap_iterator bi; + unsigned i; + + EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi) + { + tree name = ssa_name (i); + worklist.quick_push (name); + } + + while (!worklist.is_empty ()) + { + tree name = worklist.pop (); + gimple *def_stmt = SSA_NAME_DEF_STMT (name); + + if (is_gimple_assign (def_stmt)) + { + // ?? Adding assignment copies doesn't get us much. At the + // time of writing, we got 63 more threaded paths across the + // .ii files from a bootstrap. + add_to_imports (gimple_assign_rhs1 (def_stmt), m_imports); + tree rhs = gimple_assign_rhs2 (def_stmt); + if (rhs && add_to_imports (rhs, m_imports)) + worklist.safe_push (rhs); + rhs = gimple_assign_rhs3 (def_stmt); + if (rhs && add_to_imports (rhs, m_imports)) + worklist.safe_push (rhs); + } + else if (gphi *phi = dyn_cast (def_stmt)) + { + for (size_t i = 0; i < gimple_phi_num_args (phi); ++i) + { + edge e = gimple_phi_arg_edge (phi, i); + tree arg = gimple_phi_arg (phi, i)->def; + + if (TREE_CODE (arg) == SSA_NAME + && m_path->contains (e->src) + && bitmap_set_bit (m_imports, SSA_NAME_VERSION (arg))) + worklist.safe_push (arg); + } + } + } +} + // Precompute the ranges for IMPORTS along PATH. // // IMPORTS are the set of SSA names, any of which could potentially @@ -353,11 +418,12 @@ path_range_query::precompute_ranges (const vec &path, const bitmap_head *imports) { set_path (path); - m_imports = imports; + bitmap_copy (m_imports, imports); m_undefined_path = false; if (m_resolve) { + add_copies_to_imports (); m_oracle->reset_path (); precompute_relations (path); } @@ -379,6 +445,18 @@ path_range_query::precompute_ranges (const vec &path, { basic_block bb = curr_bb (); + if (m_resolve) + { + gori_compute &gori = m_ranger.gori (); + tree name; + + // Exported booleans along the path, may help conditionals. + // Add them as interesting imports. + FOR_EACH_GORI_EXPORT_NAME (gori, bb, name) + if (TREE_CODE (TREE_TYPE (name)) == BOOLEAN_TYPE) + bitmap_set_bit (m_imports, SSA_NAME_VERSION (name)); + } + precompute_ranges_in_block (bb); adjust_for_non_null_uses (bb); diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h index d12fd7743ca..f23cce18391 100644 --- a/gcc/gimple-range-path.h +++ b/gcc/gimple-range-path.h @@ -61,6 +61,8 @@ private: void ssa_range_in_phi (irange &r, gphi *phi); void precompute_relations (const vec &); void precompute_phi_relations (basic_block bb, basic_block prev); + void add_copies_to_imports (); + bool add_to_imports (tree name, bitmap imports); // Path navigation. void set_path (const vec &); @@ -82,7 +84,7 @@ private: // Path being analyzed. const vec *m_path; - const bitmap_head *m_imports; + auto_bitmap m_imports; gimple_ranger &m_ranger; non_null_ref m_non_null; path_oracle *m_oracle; From patchwork Tue Sep 21 16:53:50 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Aldy Hernandez X-Patchwork-Id: 45244 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 16698385842E for ; Tue, 21 Sep 2021 16:55:31 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 16698385842E DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1632243331; bh=l4tLhgE6bL0IvaJHm0ftRIeQ+hnk+PZaQYb07MwE/fk=; h=To:Subject:Date:In-Reply-To:References:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To:Cc: From; b=RhJTEPC5D4GAG3E4YPYkLAz9LJqtcNcCdma5OWV4Y7/1gqIDJXLnxu1C/bOR4bXoE 3oe2y7n7+cycb8hNFoaNuTq1Zzsj2gkuJkBxvl/IsrEr75IfpQV1P56UtjRe4h5GUi IzlIMU20WbwLXmAE+FIROSUafXfB+wX0A4FPIv0c= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by sourceware.org (Postfix) with ESMTP id 280453858437 for ; Tue, 21 Sep 2021 16:54:11 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 280453858437 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-29-Y7yFhIgCPpmLxqkF00x_PQ-1; Tue, 21 Sep 2021 12:54:09 -0400 X-MC-Unique: Y7yFhIgCPpmLxqkF00x_PQ-1 Received: from smtp.corp.redhat.com (int-mx07.intmail.prod.int.phx2.redhat.com [10.5.11.22]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 36BFD801E72; Tue, 21 Sep 2021 16:54:08 +0000 (UTC) Received: from abulafia.quesejoda.com (unknown [10.39.192.248]) by smtp.corp.redhat.com (Postfix) with ESMTPS id C0AEF102482F; Tue, 21 Sep 2021 16:54:07 +0000 (UTC) Received: from abulafia.quesejoda.com (localhost [127.0.0.1]) by abulafia.quesejoda.com (8.16.1/8.15.2) with ESMTPS id 18LGs5Zj414687 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Tue, 21 Sep 2021 18:54:05 +0200 Received: (from aldyh@localhost) by abulafia.quesejoda.com (8.16.1/8.16.1/Submit) id 18LGs5qS414686; Tue, 21 Sep 2021 18:54:05 +0200 To: Andrew MacLeod Subject: [PATCH 7/7] path solver: Use ranger to solve unknowns. Date: Tue, 21 Sep 2021 18:53:50 +0200 Message-Id: <20210921165350.414593-8-aldyh@redhat.com> In-Reply-To: <20210921165350.414593-1-aldyh@redhat.com> References: <20210921165350.414593-1-aldyh@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.84 on 10.5.11.22 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-13.8 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_LOW, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) 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-Patchwork-Original-From: Aldy Hernandez via Gcc-patches From: Aldy Hernandez Reply-To: Aldy Hernandez Cc: GCC patches Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" The default behavior for the path solver is to resort to VARYING when the range for an unknown SSA is outside the given path. This is both cheap and fast, but fails to get a significant amount of ranges that traditionally the DOM and VRP threaders could get. This patch uses the ranger to resolve any unknown names upon entry to the path. It also uses equivalences to improve ranges. Committed. gcc/ChangeLog: * gimple-range-path.cc (path_range_query::defined_outside_path): New. (path_range_query::range_on_path_entry): New. (path_range_query::internal_range_of_expr): Resolve unknowns with ranger. (path_range_query::improve_range_with_equivs): New. (path_range_query::ssa_range_in_phi): Resolve unknowns with ranger. * gimple-range-path.h (class path_range_query): Add defined_outside_path, range_on_path_entry, and improve_range_with_equivs. --- gcc/gimple-range-path.cc | 89 ++++++++++++++++++++++++++++++++++++++-- gcc/gimple-range-path.h | 3 ++ 2 files changed, 88 insertions(+), 4 deletions(-) diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc index a8ead3da4dc..e65c7996bb7 100644 --- a/gcc/gimple-range-path.cc +++ b/gcc/gimple-range-path.cc @@ -121,6 +121,34 @@ path_range_query::debug () dump (stderr); } +// Return TRUE if NAME is defined outside the current path. + +bool +path_range_query::defined_outside_path (tree name) +{ + gimple *def = SSA_NAME_DEF_STMT (name); + basic_block bb = gimple_bb (def); + + return !bb || !m_path->contains (bb); +} + +// Return the range of NAME on entry to the path. + +void +path_range_query::range_on_path_entry (irange &r, tree name) +{ + int_range_max tmp; + basic_block entry = entry_bb (); + r.set_undefined (); + for (unsigned i = 0; i < EDGE_COUNT (entry->preds); ++i) + { + edge e = EDGE_PRED (entry, i); + if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun) + && m_ranger.range_on_edge (tmp, e, name)) + r.union_ (tmp); + } +} + // Return the range of NAME at the end of the path being analyzed. bool @@ -132,6 +160,16 @@ path_range_query::internal_range_of_expr (irange &r, tree name, gimple *stmt) if (get_cache (r, name)) return true; + if (m_resolve && defined_outside_path (name)) + { + range_on_path_entry (r, name); + + if (r.varying_p ()) + improve_range_with_equivs (r, name); + + set_cache (r, name); + return true; + } basic_block bb = stmt ? gimple_bb (stmt) : exit_bb (); if (stmt && range_defined_in_block (r, name, bb)) @@ -139,6 +177,9 @@ path_range_query::internal_range_of_expr (irange &r, tree name, gimple *stmt) if (TREE_CODE (name) == SSA_NAME) r.intersect (gimple_range_global (name)); + if (m_resolve && r.varying_p ()) + improve_range_with_equivs (r, name); + set_cache (r, name); return true; } @@ -160,6 +201,33 @@ path_range_query::range_of_expr (irange &r, tree name, gimple *stmt) return false; } +// Improve the range of NAME with the range of any of its equivalences. + +void +path_range_query::improve_range_with_equivs (irange &r, tree name) +{ + if (TREE_CODE (name) != SSA_NAME) + return; + + basic_block entry = entry_bb (); + relation_oracle *oracle = m_ranger.oracle (); + + if (const bitmap_head *equivs = oracle->equiv_set (name, entry)) + { + int_range_max t; + bitmap_iterator bi; + unsigned i; + + EXECUTE_IF_SET_IN_BITMAP (equivs, 0, i, bi) + if (i != SSA_NAME_VERSION (name) && r.varying_p ()) + { + tree equiv = ssa_name (i); + range_on_path_entry (t, equiv); + r.intersect (t); + } + } +} + bool path_range_query::unreachable_path_p () { @@ -189,10 +257,11 @@ path_range_query::ssa_range_in_phi (irange &r, gphi *phi) tree name = gimple_phi_result (phi); basic_block bb = gimple_bb (phi); - // We experimented with querying ranger's range_on_entry here, but - // the performance penalty was too high, for hardly any improvements. if (at_entry ()) { + if (m_resolve && m_ranger.range_of_expr (r, name, phi)) + return; + // Try fold just in case we can resolve simple things like PHI <5(99), 6(88)>. if (!fold_range (r, phi, this)) r.set_varying (TREE_TYPE (name)); @@ -210,8 +279,20 @@ path_range_query::ssa_range_in_phi (irange &r, gphi *phi) tree arg = gimple_phi_arg_def (phi, i); if (!get_cache (r, arg)) - r.set_varying (TREE_TYPE (name)); - + { + if (m_resolve) + { + int_range_max tmp; + // Using both the range on entry to the path, and the + // range on this edge yields significantly better + // results. + range_on_path_entry (r, arg); + m_ranger.range_on_edge (tmp, e_in, arg); + r.intersect (tmp); + return; + } + r.set_varying (TREE_TYPE (name)); + } return; } gcc_unreachable (); diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h index f23cce18391..6f81f21d42f 100644 --- a/gcc/gimple-range-path.h +++ b/gcc/gimple-range-path.h @@ -48,6 +48,8 @@ public: private: bool internal_range_of_expr (irange &r, tree name, gimple *); + bool defined_outside_path (tree name); + void range_on_path_entry (irange &r, tree name); // Cache manipulation. void set_cache (const irange &r, tree name); @@ -61,6 +63,7 @@ private: void ssa_range_in_phi (irange &r, gphi *phi); void precompute_relations (const vec &); void precompute_phi_relations (basic_block bb, basic_block prev); + void improve_range_with_equivs (irange &r, tree name); void add_copies_to_imports (); bool add_to_imports (tree name, bitmap imports);