From patchwork Tue Feb 15 15:46:21 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1593126 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: bilbo.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=os1i4lXc; dkim-atps=neutral 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=) Received: from sourceware.org (ip-8-43-85-97.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 bilbo.ozlabs.org (Postfix) with ESMTPS id 4Jylnr1bNLz9sFh for ; Wed, 16 Feb 2022 02:46:54 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 407243858419 for ; Tue, 15 Feb 2022 15:46:48 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 407243858419 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1644940008; bh=az+3EdR/LDmBH3EXHidkL83GWyFehhLpX5W6qt/ScP8=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:Cc:From; b=os1i4lXcpB5/hFMWo4/wvVFNXYDWOH88F2mCJ12IcQ8S8JKAXZofBVVvms7DUQNVf TfbjyInDhofZoL3SNAJHRQYw/xXkNP5nrScn2PkkfpLiLPJhjX4JgbgaDJJRmkNyLj nt3F4CvuSuw6Ex1N/VaApWjFo0Kd2w4qb1Tkvgj4= 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 ESMTPS id 184DB3858C83 for ; Tue, 15 Feb 2022 15:46:27 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 184DB3858C83 Received: from mail-qk1-f200.google.com (mail-qk1-f200.google.com [209.85.222.200]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-382-PaLlQYmIMRm3FPm50bc1fQ-1; Tue, 15 Feb 2022 10:46:25 -0500 X-MC-Unique: PaLlQYmIMRm3FPm50bc1fQ-1 Received: by mail-qk1-f200.google.com with SMTP id p23-20020a05620a15f700b00506d8ec3749so11540852qkm.4 for ; Tue, 15 Feb 2022 07:46:25 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:date:mime-version:user-agent :content-language:to:cc:from:subject; bh=gqrUufX+X0MOu/MFyLFyjL4Ej7IBDnDv5W9wU7fO8kY=; b=R9OHjfJZZ74XsncNI3/AkYo6jJWMkKShZEg9OblvXh+L8iikx05/Jbbe9IvJ02tjO9 7p7H6JYDfttoVG5DK1L01WbRbQICEiWVPZMIIL6rjrroLarQ5MvB4eLQ3tA9CzotW506 SSiW0u/sSb8QsaKKFOevuLnPLFS71yjBl4N7zGvY5LiNCer8cX+0bEIh8SQJFrnWCjOK HAvTT4Ho0xD++ERFZvioiKdHwsp28FN8yTLx3X/M9kCoLsTOOvMv+qVKHGxRXAq1Lp9J s26QA3jgo3nZZIrd+HHbP5RZs4b9CVmgWc6n6Sf1S88PBYSGsr6SHgvnD7uG73X7zj/b 9xnw== X-Gm-Message-State: AOAM533uE2rjdCF0upI8aGNSNryAPBd/dS8KNa9Ou9obkbw3+V1AFkUl 59+lUpxPWj01SxhPCpoL5KAjI8+e6YfNFTli6pTLuHwhyvDUxIf+YE/SdyDMz/wMfmQ8rXEHO2q wKUgkQroxTG0GIBCv5EZcvIEju+hwRY+fCEJvD3PkbvpxJLYLtxUBb6Q8nJ57eP6Kk02j/Q== X-Received: by 2002:a05:620a:854:: with SMTP id u20mr2308192qku.716.1644939984747; Tue, 15 Feb 2022 07:46:24 -0800 (PST) X-Google-Smtp-Source: ABdhPJwEC2tPHxPZ7SAegrUlxEWZB0QarNn4w3Jfhhp55TvwasCkVBxdCpweiPupebZiuEmZliNuYQ== X-Received: by 2002:a05:620a:854:: with SMTP id u20mr2308178qku.716.1644939984384; Tue, 15 Feb 2022 07:46:24 -0800 (PST) Received: from ?IPV6:2607:fea8:a262:5f00::9b6f? ([2607:fea8:a262:5f00::9b6f]) by smtp.gmail.com with ESMTPSA id u9sm12223220qko.130.2022.02.15.07.46.23 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 15 Feb 2022 07:46:23 -0800 (PST) Message-ID: <9c021b40-576b-9904-6ccc-05dd29389547@redhat.com> Date: Tue, 15 Feb 2022 10:46:21 -0500 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.5.1 To: gcc-patches Subject: [PATCH] PR tree-optimization/104526 - Use GORI to evaluate arguments of a COND_EXPR. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-CA X-Spam-Status: No, score=-12.2 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, T_SCC_BODY_TEXT_LINE 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: Andrew MacLeod via Gcc-patches From: Andrew MacLeod Reply-To: Andrew MacLeod Cc: Jakub Jelinek Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" As requested in the PR, this patch wires GORI into the evaluation of a COND_EXPR.  This late in the cycle, we'll keep it simple. given   COND ? X : Y if there is any dependency between COND and X or COND and Y, we use the GORI engine to determine the range of the SSA_NAME in COND when its TRUE and when its FALSE and then use those values  to solve for any dependent name in X and/or Y. IE, in the testcase: _11 = (unsigned int) _2; _12 = _11 + 1; _3 = _12 <= 2 ? _2 : 0; GORI detects the dependency between _12 and _2, and can calculate that _2 is [-1, 1] in the true clause based on the restriction that  [1,1] = _12 <= 2 Limitations:  I kept it simple. It requires - COND is a COMPARISON_CLASS_P  expression with a single SSA_NAME, (ie  _12 > 45,   but not h_5 < j_2) - one or both of the  2 operands must be a dependant of the name (_12) in the condition. - This doesn't include the full bidirectional recomputations like outgoing edge does, ie _11 = (unsigned int) _2; _12 = _11 + 1; _22 = _12 + 3 _3 = _12 <= 2 ? _22 : 0; This patch will not recompute _12 to be [2,4] as the dependency goes the other way (_22 is dependant on _12, not vice versa)  I can do that for next release unless its an issue for this one Half of the patch is outputting listing info.  There isn't really much new, just connecting a couple of existing wires. In the next stage1, I will will COND_EXPR into the complete outgoing edge mechanism more seamlessly so it can take better advantages of everything available (like relations too). Bootstraps on x86_64-pc-linux-gnu with no regressions.  But I'm running it through again to be sure.   OK for trunk, or want to wait for the next release? Andrew commit 496e3d19a8570d4d62a64bd540ce86bc1ddef219 Author: Andrew MacLeod Date: Mon Feb 14 19:43:40 2022 -0500 Use GORI to evaluate arguments of a COND_EXPR. Provide an API into gori to perform a basic evaluation of the arguments of a COND_EXPR if they are in the dependency chain of the condition. PR tree-optimization/104526 gcc/ * gimple-range-fold.cc (fold_using_range::range_of_cond_expr): Call new routine. * gimple-range-gori.cc (range_def_chain::get_def_chain): Force a build of dependency chain if there isn't one. (gori_compute::condexpr_adjust): New. * gimple-range-gori.h (class gori_compute): New prototype. gcc/testsuite/ * gcc.dg/pr104526.c: New. diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc index 2ac7562aceb..a62b954d013 100644 --- a/gcc/gimple-range-fold.cc +++ b/gcc/gimple-range-fold.cc @@ -1273,6 +1273,18 @@ fold_using_range::range_of_cond_expr (irange &r, gassign *s, fur_source &src) src.get_operand (range1, op1); src.get_operand (range2, op2); + // Try to see if there is a dependence between the COND and either operand + if (src.gori ()) + if (src.gori ()->condexpr_adjust (range1, range2, s, cond, op1, op2, src)) + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Possible COND_EXPR adjustment. Range op1 : "); + range1.dump(dump_file); + fprintf (dump_file, " and Range op2: "); + range2.dump(dump_file); + fprintf (dump_file, "\n"); + } + // If the condition is known, choose the appropriate expression. if (cond_range.singleton_p ()) { diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc index 3e5328389c0..99cc5c1f3c4 100644 --- a/gcc/gimple-range-gori.cc +++ b/gcc/gimple-range-gori.cc @@ -334,7 +334,7 @@ range_def_chain::get_def_chain (tree name) unsigned v = SSA_NAME_VERSION (name); // If it has already been processed, just return the cached value. - if (has_def_chain (name)) + if (has_def_chain (name) && m_def_chain[v].bm) return m_def_chain[v].bm; // No definition chain for default defs. @@ -1303,6 +1303,99 @@ gori_compute::outgoing_edge_range_p (irange &r, edge e, tree name, return false; } +// Given COND ? OP1 : OP2 with ranges R1 for OP1 and R2 for OP2, Use gori +// to further resolve R1 and R2 if there are any dependencies between +// OP1 and COND or OP2 and COND. All values can are to be calculated using SRC +// as the origination source location for operands.. +// Effectively, use COND an the edge condition and solve for OP1 on the true +// edge and OP2 on the false edge. + +bool +gori_compute::condexpr_adjust (irange &r1, irange &r2, gimple *, tree cond, + tree op1, tree op2, fur_source &src) +{ + int_range_max tmp, cond_true, cond_false; + tree ssa1 = gimple_range_ssa_p (op1); + tree ssa2 = gimple_range_ssa_p (op2); + if (!ssa1 && !ssa2) + return false; + if (!COMPARISON_CLASS_P (cond)) + return false; + range_operator *hand = range_op_handler (TREE_CODE (cond), TREE_TYPE (op1)); + if (!hand) + return false; + + tree c1 = gimple_range_ssa_p (TREE_OPERAND (cond, 0)); + tree c2 = gimple_range_ssa_p (TREE_OPERAND (cond, 1)); + + // Only solve if there is one SSA name in the condition. + if ((!c1 && !c2) || (c1 && c2)) + return false; + + // Pick up the current values of each part of the condition. + int_range_max cl, cr; + src.get_operand (cl, TREE_OPERAND (cond, 0)); + src.get_operand (cr, TREE_OPERAND (cond, 1)); + + tree cond_name = c1 ? c1 : c2; + gimple *def_stmt = SSA_NAME_DEF_STMT (cond_name); + + // Evaluate the value of COND_NAME on the true and false edges, using either + // the op1 or op2 routines based on its location. + if (c1) + { + tree t = TREE_TYPE (TREE_OPERAND (cond, 0)); + if (!hand->op1_range (cond_false, t, m_bool_zero, cr)) + return false; + if (!hand->op1_range (cond_true, t, m_bool_one, cr)) + return false; + cond_false.intersect (cl); + cond_true.intersect (cl); + } + else + { + tree t = TREE_TYPE (TREE_OPERAND (cond, 1)); + if (!hand->op2_range (cond_false, t, m_bool_zero, cl)) + return false; + if (!hand->op2_range (cond_true, t, m_bool_one, cl)) + return false; + cond_false.intersect (cr); + cond_true.intersect (cr); + } + + unsigned idx; + if ((idx = tracer.header ("cond_expr evaluation : "))) + { + fprintf (dump_file, " range1 = "); + r1.dump (dump_file); + fprintf (dump_file, ", range2 = "); + r1.dump (dump_file); + fprintf (dump_file, "\n"); + } + + // Now solve for SSA1 or SSA2 if they are in the dependency chain. + if (ssa1 && in_chain_p (ssa1, cond_name)) + { + if (compute_operand_range (tmp, def_stmt, cond_true, ssa1, src)) + r1.intersect (tmp); + } + if (ssa2 && in_chain_p (ssa2, cond_name)) + { + if (compute_operand_range (tmp, def_stmt, cond_false, ssa2, src)) + r2.intersect (tmp); + } + if (idx) + { + tracer.print (idx, "outgoing: range1 = "); + r1.dump (dump_file); + fprintf (dump_file, ", range2 = "); + r1.dump (dump_file); + fprintf (dump_file, "\n"); + tracer.trailer (idx, "cond_expr", true, cond_name, cond_true); + } + return true; +} + // Dump what is known to GORI computes to listing file F. void diff --git a/gcc/gimple-range-gori.h b/gcc/gimple-range-gori.h index b799a84c588..605884e2e53 100644 --- a/gcc/gimple-range-gori.h +++ b/gcc/gimple-range-gori.h @@ -158,6 +158,8 @@ class gori_compute : public gori_map public: gori_compute (int not_executable_flag = 0); bool outgoing_edge_range_p (irange &r, edge e, tree name, range_query &q); + bool condexpr_adjust (irange &r1, irange &r2, gimple *s, tree cond, tree op1, + tree op2, fur_source &src); bool has_edge_range_p (tree name, basic_block bb = NULL); bool has_edge_range_p (tree name, edge e); void dump (FILE *f); diff --git a/gcc/testsuite/gcc.dg/pr104526.c b/gcc/testsuite/gcc.dg/pr104526.c new file mode 100644 index 00000000000..a2953082901 --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr104526.c @@ -0,0 +1,15 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-evrp" } */ + +void foo(void); + +static int a, b = 1, *c = &b; +int main() { + for (; a; a--) { + int d = 2 >> (1 / *c); + if (!d) + foo(); + } +} + +/* { dg-final { scan-tree-dump-not "foo" "evrp" } } */