From patchwork Thu Jun 17 00:13:49 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1493131 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=WilNOXip; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4G52cv1ZT6z9sW4 for ; Thu, 17 Jun 2021 10:15:11 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id C141538515F9 for ; Thu, 17 Jun 2021 00:15:08 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org C141538515F9 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1623888908; bh=Gk+crj8zKWO0ICbrAiTClPzGmu34LmrorxG1EBLK4pM=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=WilNOXiprSbGk+EBPCyiikZqH6SJEGtEhUGp21XFa1N4PGOPvWV0S7z9CNjcg06nO o9WPt6xBG9I/DIeo0xd13naiwsLJtPvgU1wzvEQlksb1jPpKvnu+7SGl4nDtMAi98T JFfLJkjzY8JlFMtLTu5e0pIQJbnt9we4a/vRT4C8= 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 71E3E385042E for ; Thu, 17 Jun 2021 00:13:53 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 71E3E385042E Received: from mail-qk1-f200.google.com (mail-qk1-f200.google.com [209.85.222.200]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-5-3E2UqneqN9WaWsmssAHOLA-1; Wed, 16 Jun 2021 20:13:51 -0400 X-MC-Unique: 3E2UqneqN9WaWsmssAHOLA-1 Received: by mail-qk1-f200.google.com with SMTP id e13-20020a37e50d0000b02903ad5730c883so735364qkg.22 for ; Wed, 16 Jun 2021 17:13:51 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:to:cc:from:subject:message-id:date:user-agent :mime-version:content-language; bh=qfL22lEuAXaNhNHo/PcvH0T3M5W+xMZKhbRNHpRwQ9U=; b=eQi61Im/jRcvgo96LM/+ijQyHNiqJGgl09L9ApzKji3NPz/ytUr7piMNFwgH6rTh91 3RE53ro0pp4cam5jZ010fcGNokKJDGdX2dd5Gy8ZLi4oUK5+yVk1w9WgLIr0tYI+36Si wuDEjLWpQVXSk/Et2XM3REehGqGxZoyocBuebhMVRhE2AZLJcZLtHGPaIfHLJGFdGoPY I1eIXxHpFcg05tUTK+W2fcmmLwS9KbVdHqJgdNahetYD9XL6mKbN++M8g4HBP+eULzr8 s2YGFXcxUkfiwC4Fc3m8kAMi37A4c1UBQBKZeSWihiVo5tUeCDrQoT4+QvCe1LsyWYlj YkIA== X-Gm-Message-State: AOAM530QynyDxGHb11id455sLXbMluHYWNa9MOf+gQI7n8EiUTcCl7MI ddbSB3U58MYcjME2TGhYpKON5mEGYmoDva4BUEtStPfCEgBkEc3M3ZVn5ZBALFVIz3Aod7iYFg+ 68+qeornA06llitdDNA== X-Received: by 2002:ad4:4e62:: with SMTP id ec2mr2881852qvb.19.1623888830753; Wed, 16 Jun 2021 17:13:50 -0700 (PDT) X-Google-Smtp-Source: ABdhPJzqOjVPEFqdgj5OBNrbZshepaBQ3sFShNtnv/qzYS7rnPRU1T45X3tAXy3tkQQbUL3aAN3WIw== X-Received: by 2002:ad4:4e62:: with SMTP id ec2mr2881843qvb.19.1623888830620; Wed, 16 Jun 2021 17:13:50 -0700 (PDT) Received: from ?IPv6:2607:fea8:a241:4600::58f9? ([2607:fea8:a241:4600::58f9]) by smtp.gmail.com with ESMTPSA id y22sm610427qky.58.2021.06.16.17.13.49 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 16 Jun 2021 17:13:50 -0700 (PDT) To: gcc-patches Subject: [PATCH] Add recomputation to outgoing_edge_range. Message-ID: <7e0fac9c-089b-6ae3-3c76-86061c999ef9@redhat.com> Date: Wed, 16 Jun 2021 20:13:49 -0400 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.10.0 MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-CA X-Spam-Status: No, score=-11.8 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, HTML_MESSAGE, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H4, 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-Content-Filtered-By: Mailman/MimeDel 2.1.29 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: Andrew MacLeod via Gcc-patches From: Andrew MacLeod Reply-To: Andrew MacLeod Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" This change adds first degree recomputation to the gori engine. "Exports" are any ssa_name which is in the definition chain of one of the SSA_NAMES on the condition. a_2 = b_3 +6 if (a_2 > 10 && a_2 <20)    // a_2 has the range [11, 19] The condition tells us that the range of a_2 is [11, 19] on the true edge, and since b_3 is used in the definition chain of a_2, the gori_compute engine can solve the equation    [11, 19] = b_3 + 6    to deduce that b_3 has a range of [5, 13] on the true range. These export chains are built for each basic block with a condition, and in this block, a_2 and b_3 are in the export list.   IF an SSA_NAME is not in the export list,we cannot calculate a range for it.    If we tweak to the original case: x_5 = b_3 * 2 a_2 = b_3 +6 if (a_2 > 10 && a_2 <20)    // a_2 has the range [11, 19] Following just definition chains, there is no use/def relationship between x_5 and a_2.   Using the export list, we know that a_2 and b_3 are both exports from this block. The new GORI rework also contains dependency summaries as well.  Each statement has up to 2 "direct dependencies" cached.  These are ssa_names which occur in the statement and could change it value. This patch adds the ability to recompute values by checking if one of these direct dependants ise an export, and recomputing the original statement using the values as they appear on this edge. In this latter example, b_3 is a direct dependent for x_5's statement,  and x_5 is therefore determined to be recomputable. Using fold_using_range we ask for the range of x_5 to be calculated as if it were on that edge.  It can determine that b_3 is [5, 13] on the edge and will now calculate x_5 as [10, 26] on the edge The nature of SSA makes this a safe operation (assuming the statement has no side effects).  It also removes any need for x_5 = b_3 * 2 to occur in this block.. it can be anywhere in the IL and this still works. This is integrated directly in outgoing_edge_range_p and picks up quite a few new opportunities. Bootstraps on x86_64-pc-linux-gnu with no regressions.  Pushed. Andrew commit 786188e8b8cab47cb31177c6f4ab1a1578a607c3 Author: Andrew MacLeod Date: Wed Jun 16 18:08:03 2021 -0400 Add recomputation to outgoing_edge_range. The gori engine can calculate outgoing ranges for exported values. This change allows 1st degree recomputation. If a name is not exported from a block, but one of the ssa_names used directly in computing it is, then we can recompute the ssa_name on the edge using the edge values for its operands. * gimple-range-gori.cc (gori_compute::has_edge_range_p): Check with may_recompute_p. (gori_compute::may_recompute_p): New. (gori_compute::outgoing_edge_range_p): Perform recomputations. * gimple-range-gori.h (class gori_compute): Add prototype. diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc index 09dcd694319..647f4964769 100644 --- a/gcc/gimple-range-gori.cc +++ b/gcc/gimple-range-gori.cc @@ -972,16 +972,18 @@ gori_compute::compute_operand1_and_operand2_range (irange &r, r.intersect (op_range); return true; } -// Return TRUE if a range can be calcalated for NAME on edge E. +// Return TRUE if a range can be calculated or recomputed for NAME on edge E. bool gori_compute::has_edge_range_p (tree name, edge e) { - // If no edge is specified, check if NAME is an export on any edge. - if (!e) - return is_export_p (name); + // Check if NAME is an export or can be recomputed. + if (e) + return is_export_p (name, e->src) || may_recompute_p (name, e); - return is_export_p (name, e->src); + // If no edge is specified, check if NAME can have a range calculated + // on any edge. + return is_export_p (name) || may_recompute_p (name); } // Dump what is known to GORI computes to listing file F. @@ -992,6 +994,32 @@ gori_compute::dump (FILE *f) gori_map::dump (f); } +// Return TRUE if NAME can be recomputed on edge E. If any direct dependant +// is exported on edge E, it may change the computed value of NAME. + +bool +gori_compute::may_recompute_p (tree name, edge e) +{ + tree dep1 = depend1 (name); + tree dep2 = depend2 (name); + + // If the first dependency is not set, there is no recompuation. + if (!dep1) + return false; + + // Don't recalculate PHIs or statements with side_effects. + gimple *s = SSA_NAME_DEF_STMT (name); + if (is_a (s) || gimple_has_side_effects (s)) + return false; + + // If edge is specified, check if NAME can be recalculated on that edge. + if (e) + return ((is_export_p (dep1, e->src)) + || (dep2 && is_export_p (dep2, e->src))); + + return (is_export_p (dep1)) || (dep2 && is_export_p (dep2)); +} + // Calculate a range on edge E and return it in R. Try to evaluate a // range for NAME on this edge. Return FALSE if this is either not a // control edge or NAME is not defined by this edge. @@ -1026,6 +1054,27 @@ gori_compute::outgoing_edge_range_p (irange &r, edge e, tree name, return true; } } + // If NAME isn't exported, check if it can be recomputed. + else if (may_recompute_p (name, e)) + { + gimple *def_stmt = SSA_NAME_DEF_STMT (name); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "recomputation attempt on edge %d->%d for ", + e->src->index, e->dest->index); + print_generic_expr (dump_file, name, TDF_SLIM); + } + // Simply calculate DEF_STMT on edge E usng the range query Q. + fold_range (r, def_stmt, e, &q); + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " : Calculated :"); + r.dump (dump_file); + fputc ('\n', dump_file); + } + return true; + } return false; } diff --git a/gcc/gimple-range-gori.h b/gcc/gimple-range-gori.h index 06f3b791359..6f187db08cb 100644 --- a/gcc/gimple-range-gori.h +++ b/gcc/gimple-range-gori.h @@ -157,6 +157,7 @@ public: bool has_edge_range_p (tree name, edge e = NULL); void dump (FILE *f); private: + bool may_recompute_p (tree name, edge e = NULL); bool compute_operand_range (irange &r, gimple *stmt, const irange &lhs, tree name, class fur_source &src); bool compute_operand_range_switch (irange &r, gswitch *s, const irange &lhs,