From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [216.205.24.124]) by sourceware.org (Postfix) with ESMTPS id 34AD93858416 for ; Mon, 15 Nov 2021 12:16:09 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 34AD93858416 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-441-0hBkG-w-P6-AL9UlqyLdVw-1; Mon, 15 Nov 2021 07:16:07 -0500 X-MC-Unique: 0hBkG-w-P6-AL9UlqyLdVw-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 1F6DC871803 for ; Mon, 15 Nov 2021 12:16:06 +0000 (UTC) Received: from abulafia.quesejoda.com (unknown [10.39.193.97]) by smtp.corp.redhat.com (Postfix) with ESMTPS id A0991101E7F4; Mon, 15 Nov 2021 12:16:05 +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 1AFCG3Sp1207892 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Mon, 15 Nov 2021 13:16:03 +0100 Received: (from aldyh@localhost) by abulafia.quesejoda.com (8.16.1/8.16.1/Submit) id 1AFCG3in1207891; Mon, 15 Nov 2021 13:16:03 +0100 From: Aldy Hernandez To: GCC patches Subject: [COMMITTED] Fix PHI ordering problems in the path solver. Date: Mon, 15 Nov 2021 13:15:55 +0100 Message-Id: <20211115121555.1207800-2-aldyh@redhat.com> In-Reply-To: <20211115121555.1207800-1-aldyh@redhat.com> References: <20211115121555.1207800-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 Content-Transfer-Encoding: 8bit Content-Type: text/plain; charset="US-ASCII" X-Spam-Status: No, score=-13.3 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-List-Received-Date: Mon, 15 Nov 2021 12:16:11 -0000 After auditing the PHI range calculations, I'm not convinced we've caught all the corner cases. They haven't shown up in the wild (yet), but better safe than sorry. We shouldn't write anything to the cache or trigger additional lookups while calculating a PHI, as this may cause ordering problems. We should resolve the PHI with either the cache as it stands, or by asking for ranges on entry to the path. I've documented this. There was one dubious case where we called fold_range in ssa_range_in_phi, which mostly by luck wasn't triggering lookups, because fold_range solves a PHI by calling range_on_edge, which is set to pick up global ranges by default in path_range_query. This is fragile, so I've rewritten the call to explicitly use cached or global ranges. Also, the cache should be avoided in ssa_range_in_phi when the arg is defined in the PHI's block, as not doing so could create an ordering problem. We have a similar check when calculating relations in PHIs. Tested on x86-64 & ppc64le Linux. gcc/ChangeLog: * gimple-range-path.cc (path_range_query::internal_range_of_expr): Remove useless code. (path_range_query::ssa_defined_in_bb): New. (path_range_query::ssa_range_in_phi): Avoid fold_range call that could trigger additional lookups. Do not use the cache for ARGs defined in this block. (path_range_query::compute_ranges_in_block): Use ssa_defined_in_bb. (path_range_query::maybe_register_phi_relation): Same. (path_range_query::range_of_stmt): Adjust comment. * gimple-range-path.h (ssa_defined_in_bb): New. --- gcc/gimple-range-path.cc | 61 +++++++++++++++++++++++++++------------- gcc/gimple-range-path.h | 1 + 2 files changed, 42 insertions(+), 20 deletions(-) diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc index f6e31999293..4aa666d2c8b 100644 --- a/gcc/gimple-range-path.cc +++ b/gcc/gimple-range-path.cc @@ -202,8 +202,8 @@ path_range_query::internal_range_of_expr (irange &r, tree name, gimple *stmt) return true; } - basic_block bb = stmt ? gimple_bb (stmt) : exit_bb (); - if (stmt && range_defined_in_block (r, name, bb)) + if (stmt + && range_defined_in_block (r, name, gimple_bb (stmt))) { if (TREE_CODE (name) == SSA_NAME) r.intersect (gimple_range_global (name)); @@ -250,36 +250,62 @@ path_range_query::set_path (const vec &path) bitmap_clear (m_has_cache_entry); } +bool +path_range_query::ssa_defined_in_bb (tree name, basic_block bb) +{ + return (TREE_CODE (name) == SSA_NAME + && SSA_NAME_DEF_STMT (name) + && gimple_bb (SSA_NAME_DEF_STMT (name)) == bb); +} + // Return the range of the result of PHI in R. +// +// Since PHIs are calculated in parallel at the beginning of the +// block, we must be careful to never save anything to the cache here. +// It is the caller's responsibility to adjust the cache. Also, +// calculating the PHI's range must not trigger additional lookups. void path_range_query::ssa_range_in_phi (irange &r, gphi *phi) { tree name = gimple_phi_result (phi); basic_block bb = gimple_bb (phi); + unsigned nargs = gimple_phi_num_args (phi); 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)); - + // Try to fold the phi exclusively with global or cached values. + // This will get things like PHI <5(99), 6(88)>. We do this by + // calling range_of_expr with no context. + int_range_max arg_range; + r.set_undefined (); + for (size_t i = 0; i < nargs; ++i) + { + tree arg = gimple_phi_arg_def (phi, i); + if (range_of_expr (arg_range, arg, /*stmt=*/NULL)) + r.union_ (arg_range); + else + { + r.set_varying (TREE_TYPE (name)); + return; + } + } return; } basic_block prev = prev_bb (); edge e_in = find_edge (prev, bb); - 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 (!get_cache (r, arg)) + // Avoid using the cache for ARGs defined in this block, as + // that could create an ordering problem. + if (ssa_defined_in_bb (arg, bb) || !get_cache (r, arg)) { if (m_resolve) { @@ -393,10 +419,7 @@ path_range_query::compute_ranges_in_block (basic_block bb) EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi) { tree name = ssa_name (i); - gimple *def_stmt = SSA_NAME_DEF_STMT (name); - basic_block def_bb = gimple_bb (def_stmt); - - if (def_bb == bb) + if (ssa_defined_in_bb (name, bb)) clear_cache (name); } @@ -705,8 +728,8 @@ path_range_query::range_of_stmt (irange &r, gimple *stmt, tree) 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 resolving unknowns, fold the statement making use of any + // relations along the path. if (m_resolve) { fold_using_range f; @@ -714,8 +737,7 @@ path_range_query::range_of_stmt (irange &r, gimple *stmt, tree) 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. + // Otherwise, fold without relations. else if (!fold_range (r, stmt, this)) r.set_varying (type); @@ -727,11 +749,10 @@ path_range_query::maybe_register_phi_relation (gphi *phi, tree arg) { basic_block bb = gimple_bb (phi); tree result = gimple_phi_result (phi); - gimple *def = SSA_NAME_DEF_STMT (arg); // Avoid recording the equivalence if the arg is defined in this - // block, as that would create an ordering problem. - if (def && gimple_bb (def) == bb) + // block, as that could create an ordering problem. + if (ssa_defined_in_bb (arg, bb)) return; if (dump_file && (dump_flags & TDF_DETAILS)) diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h index c80734f65a1..57a9ae9bdcd 100644 --- a/gcc/gimple-range-path.h +++ b/gcc/gimple-range-path.h @@ -66,6 +66,7 @@ private: void maybe_register_phi_relation (gphi *, tree arg); bool add_to_imports (tree name, bitmap imports); bool import_p (tree name); + bool ssa_defined_in_bb (tree name, basic_block bb); // Path navigation. void set_path (const vec &); -- 2.31.1