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);