From patchwork Thu Sep 29 22:36:53 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1684646 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: legolas.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=lk0Q6lzH; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4MdpCQ2ymnz1yqc for ; Fri, 30 Sep 2022 08:37:38 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 36CF8389942B for ; Thu, 29 Sep 2022 22:37:36 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 36CF8389942B DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1664491056; bh=GTOqdAdEbiNojwpwjwdTAbgt1zclJtY7PD++JOXqt/0=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=lk0Q6lzHdYM/46gKTSvl8g0Pt09Nk+5BMVQxahRD5Gn/KzT2JbQfChwnMb7z16rWv 44hphWOps9oueNRb/zK+mrPd7oVoLGwBVshfHtC+37vEm1HFN8wEkESXF4at6JeLw6 iiJGq6qbK5yJRssKV1MAPpwUmK0S58VtoAWxdCxs= 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 ESMTPS id 31F5F3839DE5 for ; Thu, 29 Sep 2022 22:36:59 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 31F5F3839DE5 Received: from mail-qv1-f70.google.com (mail-qv1-f70.google.com [209.85.219.70]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-21-vrA2qutBOh-tIO6kYB1_Fg-1; Thu, 29 Sep 2022 18:36:57 -0400 X-MC-Unique: vrA2qutBOh-tIO6kYB1_Fg-1 Received: by mail-qv1-f70.google.com with SMTP id mo5-20020a056214330500b004ad711537a6so1884669qvb.10 for ; Thu, 29 Sep 2022 15:36:57 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=subject:from:cc:to:content-language:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date; bh=lTg6+/Fb6lcyIF8LXml9qdla0bYPjatdO63CBDiRnOo=; b=J+OOHetSQTvNyTyEL0zU5EDVlJj0JFnjuYM/gXcsQfyajhwP+X2eLBgy2IF6Lqirtg ImiCXX1r5y9uTmp4+4CTZYOGbeKbLwxDDCAh4/Ckl58gBXilehUZrtg/FIsRhGOGyHjl 5yVvirglfFyv4II64H4KjFUi5QE+kLC8UEDy3h/YSvAhOgPWZr4Oj29YZCvY7rvMuLAx tA9oXI83e4QfA4rIAKzwhJFmx20oefgxQrrulWYjy7/TbV+Vgc9yQBZqY2sxy2nZrXOc sYHYnmmQNcP6PrqbY6me0jcRxo9ye0kkx/VemczjbbNVWXIsQdyLU2tGIxrP9rGCgpzO 5AVg== X-Gm-Message-State: ACrzQf2QAGIZh/Xka/GTS4ha1O3vb+ArCGoBz7NWlXssYWmET6mo4MGg L0yv2ZW6fZ0ACt7DUxalOlN5xdYK6Bp2u2by/97Y618m/gHa7tKp0IzstCrJG5JM51OU03WfCKY xHfU1PpDsLhP9NUsWiC2zLKsfCuBIWTaQIj2b1VViHXNdNPfTlT+Fn7Cf7iDdwCiI0mJ4fA== X-Received: by 2002:a37:68d6:0:b0:6cb:cf29:dfb with SMTP id d205-20020a3768d6000000b006cbcf290dfbmr3972968qkc.406.1664491016413; Thu, 29 Sep 2022 15:36:56 -0700 (PDT) X-Google-Smtp-Source: AMsMyM5ohaZFzzcZrR3GMilluIs3ZQvET/r55OR2KyRB3Iz1C7D4enOdFMX9Sz7bHmYR5eRO/7CQsw== X-Received: by 2002:a37:68d6:0:b0:6cb:cf29:dfb with SMTP id d205-20020a3768d6000000b006cbcf290dfbmr3972945qkc.406.1664491016088; Thu, 29 Sep 2022 15:36:56 -0700 (PDT) Received: from ?IPV6:2607:fea8:a263:f600::3dbe? ([2607:fea8:a263:f600::3dbe]) by smtp.gmail.com with ESMTPSA id a21-20020ac86115000000b0035d1f846b91sm391790qtm.64.2022.09.29.15.36.54 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 29 Sep 2022 15:36:55 -0700 (PDT) Message-ID: Date: Thu, 29 Sep 2022 18:36:53 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.2.1 To: gcc-patches Subject: [PATCH] Refine ranges using relations in GORI. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-12.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.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) 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: 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 allows GORI to recognize when a relation passed in applies to the 2 operands of the current statement.  Check to see if further range refinement is possible before proceeding. There are 2 primary ways this can happen. 1)  The relation record indicates there is a relation between the LHS and the operand being calculated.  If this is the case, then the relation is passed thru to the range-ops op1_range or op2_range routine for use in evaluating the operand. 2) if there is a relation between op1 and op2, then we take a special step (the new routine refine_using_relation) and look to see if there is also any dependence between op1 and op2.  If there is, we attempt to "refine" their ranges based on this dependence before proceeding further.   For example: d_4 =a_1 * 2 a_1 = b_2 + 1 if (a_1 < b_2) Looking at the true edge, we start with [1,1] = a_1 < b_2 There is a relation between a_1 and b_2, it checks if the value of a_1 is dependent on b_2, and tries to calculate new values for a_1 and b_2 based on this dependence. if op1_range is properly implemented for operator_plus (next patch), then resolving the value of b_2 in a_1 = b_2 + 1  with the relation op1 >= LHS would return the range of [+INF, +INF].  and using that value, a_1 would then have a range of [0, 0]. We calculate and substitute these values early, so that if we are looking for other exported values (such as d_4), the range of a_1 = [0,0] will trickle up to that calculation on the edge, and we'll get d_4 = [0,0] on that edge too. Bootstrapped on x86_64-pc-linux-gnu with no regressions.  Pushed. Andrew From 242ea7e93aaa0a1a3f24d555ded71bf9da7e5c0d Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Thu, 22 Sep 2022 18:17:20 -0400 Subject: [PATCH 5/6] Refine ranges using relations in GORI. This allows GORI to recognize when a relation passed in applies to the 2 operands of the current statement. Check to see if further range refinement is possible before proceeding. * gimple-range-gori.cc (gori_compute::refine_using_relation): New. (gori_compute::compute_operand1_range): Invoke refine_using_relation when applicable. (gori_compute::compute_operand2_range): Ditto. * gimple-range-gori.h (class gori_compute): Adjust prototypes. --- gcc/gimple-range-gori.cc | 146 ++++++++++++++++++++++++++++++++++++++- gcc/gimple-range-gori.h | 3 + 2 files changed, 146 insertions(+), 3 deletions(-) diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc index 57a7e820749..b37d03cddda 100644 --- a/gcc/gimple-range-gori.cc +++ b/gcc/gimple-range-gori.cc @@ -934,6 +934,115 @@ gori_compute::compute_logical_operands (vrange &true_range, vrange &false_range, src.get_operand (false_range, name); } + +// This routine will try to refine the ranges of OP1 and OP2 given a relation +// K between them. In order to perform this refinement, one of the operands +// must be in the definition chain of the other. The use is refined using +// op1/op2_range on the statement, and the defintion is then recalculated +// using the relation. + +bool +gori_compute::refine_using_relation (tree op1, vrange &op1_range, + tree op2, vrange &op2_range, + fur_source &src, relation_kind k) +{ + gcc_checking_assert (TREE_CODE (op1) == SSA_NAME); + gcc_checking_assert (TREE_CODE (op2) == SSA_NAME); + gcc_checking_assert (k != VREL_VARYING && k != VREL_UNDEFINED); + + bool change = false; + bool op1_def_p = in_chain_p (op2, op1); + if (!op1_def_p) + if (!in_chain_p (op1, op2)) + return false; + + tree def_op = op1_def_p ? op1 : op2; + tree use_op = op1_def_p ? op2 : op1; + + if (!op1_def_p) + k = relation_swap (k); + + // op1_def is true if we want to look up op1, otherwise we want op2. + // if neither is the case, we returned in the above check. + + gimple *def_stmt = SSA_NAME_DEF_STMT (def_op); + gimple_range_op_handler op_handler (def_stmt); + if (!op_handler) + return false; + tree def_op1 = op_handler.operand1 (); + tree def_op2 = op_handler.operand2 (); + // if the def isn't binary, the relation will not be useful. + if (!def_op2) + return false; + + // Determine if op2 is directly referenced as an operand. + if (def_op1 == use_op) + { + // def_stmt has op1 in the 1st operand position. + Value_Range other_op (TREE_TYPE (def_op2)); + src.get_operand (other_op, def_op2); + + // Using op1_range as the LHS, and relation REL, evaluate op2. + tree type = TREE_TYPE (def_op1); + Value_Range new_result (type); + if (!op_handler.op1_range (new_result, type, + op1_def_p ? op1_range : op2_range, + other_op, k)) + return false; + if (op1_def_p) + { + change |= op2_range.intersect (new_result); + // Recalculate op2. + if (op_handler.fold_range (new_result, type, op2_range, other_op)) + { + change |= op1_range.intersect (new_result); + } + } + else + { + change |= op1_range.intersect (new_result); + // Recalculate op1. + if (op_handler.fold_range (new_result, type, op1_range, other_op)) + { + change |= op2_range.intersect (new_result); + } + } + } + else if (def_op2 == use_op) + { + // def_stmt has op1 in the 1st operand position. + Value_Range other_op (TREE_TYPE (def_op1)); + src.get_operand (other_op, def_op1); + + // Using op1_range as the LHS, and relation REL, evaluate op2. + tree type = TREE_TYPE (def_op2); + Value_Range new_result (type); + if (!op_handler.op2_range (new_result, type, + op1_def_p ? op1_range : op2_range, + other_op, k)) + return false; + if (op1_def_p) + { + change |= op2_range.intersect (new_result); + // Recalculate op1. + if (op_handler.fold_range (new_result, type, other_op, op2_range)) + { + change |= op1_range.intersect (new_result); + } + } + else + { + change |= op1_range.intersect (new_result); + // Recalculate op2. + if (op_handler.fold_range (new_result, type, other_op, op1_range)) + { + change |= op2_range.intersect (new_result); + } + } + } + return change; +} + // Calculate a range for NAME from the operand 1 position of STMT // assuming the result of the statement is LHS. Return the range in // R, or false if no range could be calculated. @@ -947,6 +1056,7 @@ gori_compute::compute_operand1_range (vrange &r, gimple *stmt = handler.stmt (); tree op1 = handler.operand1 (); tree op2 = handler.operand2 (); + tree lhs_name = gimple_get_lhs (stmt); Value_Range op1_range (TREE_TYPE (op1)); Value_Range tmp (TREE_TYPE (op1)); @@ -959,7 +1069,21 @@ gori_compute::compute_operand1_range (vrange &r, if (op2) { src.get_operand (op2_range, op2); - if (!handler.calc_op1 (tmp, lhs, op2_range)) + relation_kind k = VREL_VARYING; + if (rel) + { + if (lhs_name == rel->op1 () && op1 == rel->op2 ()) + k = rel->kind (); + else if (lhs_name == rel->op2 () && op1 == rel->op1 ()) + k = relation_swap (rel->kind ()); + else if (op1 == rel->op1 () && op2 == rel->op2 ()) + refine_using_relation (op1, op1_range, op2, op2_range, src, + rel->kind ()); + else if (op1 == rel->op2 () && op2 == rel->op1 ()) + refine_using_relation (op1, op1_range, op2, op2_range, src, + relation_swap (rel->kind ())); + } + if (!handler.calc_op1 (tmp, lhs, op2_range, k)) return false; } else @@ -967,7 +1091,7 @@ gori_compute::compute_operand1_range (vrange &r, // We pass op1_range to the unary operation. Nomally it's a // hidden range_for_type parameter, but sometimes having the // actual range can result in better information. - if (!handler.calc_op1 (tmp, lhs, op1_range)) + if (!handler.calc_op1 (tmp, lhs, op1_range, VREL_VARYING)) return false; } @@ -1030,6 +1154,7 @@ gori_compute::compute_operand2_range (vrange &r, gimple *stmt = handler.stmt (); tree op1 = handler.operand1 (); tree op2 = handler.operand2 (); + tree lhs_name = gimple_get_lhs (stmt); Value_Range op1_range (TREE_TYPE (op1)); Value_Range op2_range (TREE_TYPE (op2)); @@ -1037,9 +1162,24 @@ gori_compute::compute_operand2_range (vrange &r, src.get_operand (op1_range, op1); src.get_operand (op2_range, op2); + relation_kind k = VREL_VARYING; + if (rel) + { + if (lhs_name == rel->op1 () && op2 == rel->op2 ()) + k = rel->kind (); + else if (lhs_name == rel->op2 () && op2 == rel->op1 ()) + k = relation_swap (rel->kind ()); + else if (op1 == rel->op1 () && op2 == rel->op2 ()) + refine_using_relation (op1, op1_range, op2, op2_range, src, + rel->kind ()); + else if (op1 == rel->op2 () && op2 == rel->op1 ()) + refine_using_relation (op1, op1_range, op2, op2_range, src, + relation_swap (rel->kind ())); + } + // Intersect with range for op2 based on lhs and op1. - if (!handler.calc_op2 (tmp, lhs, op1_range)) + if (!handler.calc_op2 (tmp, lhs, op1_range, k)) return false; unsigned idx; diff --git a/gcc/gimple-range-gori.h b/gcc/gimple-range-gori.h index 1fff3e6255a..c7a32162a1b 100644 --- a/gcc/gimple-range-gori.h +++ b/gcc/gimple-range-gori.h @@ -166,6 +166,9 @@ public: bool has_edge_range_p (tree name, edge e); void dump (FILE *f); private: + bool refine_using_relation (tree op1, vrange &op1_range, + tree op2, vrange &op2_range, + fur_source &src, relation_kind k); bool may_recompute_p (tree name, edge e); bool may_recompute_p (tree name, basic_block bb = NULL); bool compute_operand_range (vrange &r, gimple *stmt, const vrange &lhs, -- 2.37.3