From patchwork Tue Jun 22 13:18:14 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1495679 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=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: 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=fpKTregS; 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 RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4G8RqM32pNz9sS8 for ; Tue, 22 Jun 2021 23:21:03 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 2013938930D1 for ; Tue, 22 Jun 2021 13:21:00 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 2013938930D1 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1624368060; bh=v8zvNWYZoN1c9oEfl7fsMEc69srPFqYRoxGQIMg4498=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=fpKTregSQ75/RiOdfT6dnmHzJrWrRIg9FpkCRrqGE/YJoP5iEbTBW0xXsY5EtGI8f 7TzMt4ACC3rexSFh519ANqozArNYfX8WnvFvKBvtMQUpAMFk9NL3myZmQSsgE188+P tecb0KNSkUrIooNMJxCtN7Vv6irExSiO8lqOSAGo= 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 ESMTP id 204D33891C22 for ; Tue, 22 Jun 2021 13:18:19 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 204D33891C22 Received: from mail-qv1-f71.google.com (mail-qv1-f71.google.com [209.85.219.71]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-266-cN2ycmvKMcudh5I_oFpkbg-1; Tue, 22 Jun 2021 09:18:17 -0400 X-MC-Unique: cN2ycmvKMcudh5I_oFpkbg-1 Received: by mail-qv1-f71.google.com with SMTP id k12-20020a0cfd6c0000b029020df9543019so18037293qvs.14 for ; Tue, 22 Jun 2021 06:18:16 -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=v8zvNWYZoN1c9oEfl7fsMEc69srPFqYRoxGQIMg4498=; b=qai4is0ZpVXB2oJ7+eXkR5cbExemac8F8Bn+bqlJagh00D3iP1qSNOIyu7UM05OysA wA0R7558FiS0NS3F5TrBiXPFdcLsWLP94mcjd2WrW+ezLNKX17SXO/SOIbyxXd5k3j8m SrezLZ0j5KhqR94MRgR7IzrypNgJ2T6kiJw71482grtj7iP3J/w4wcBZoR89/I0T2XH1 ZpMAuRB2ssKfxetmqhsGtIPLpwC6hXoyqej8mzLBGt6WtoQZQNakp6TGmMIXGqrhXzMN 85TNCKMzKGOmkIV/WXROkp8gMPWmyXhx6bOSCqr0O5h8oCjZgRsqeUFLoV7EZap86FMC 9bkQ== X-Gm-Message-State: AOAM5303kICPzZlZ5hLgNoR0rwtXRxG5snNKhnDqvSCOz8FhrYvEJ+oA GKm1O/LEvHXr4fS8xHLJkM5xlw6u438SoMIE12+HBlz8CibxzFT1q/YpswFui5YVVFdF6jvacER xUWYWFp1dHfOsar7cWg== X-Received: by 2002:a05:620a:4510:: with SMTP id t16mr2017553qkp.76.1624367896576; Tue, 22 Jun 2021 06:18:16 -0700 (PDT) X-Google-Smtp-Source: ABdhPJyZwxCOZ6oT+Jdgdh61EutFCH9fm/iwHMmZ5Oe4yKAbn+4YVMjA2uvMWAtQbmp90M99wJQ8GQ== X-Received: by 2002:a05:620a:4510:: with SMTP id t16mr2017542qkp.76.1624367896427; Tue, 22 Jun 2021 06:18:16 -0700 (PDT) Received: from ?IPv6:2607:fea8:a241:4600:84d5:145a:ba5d:a5af? ([2607:fea8:a241:4600:84d5:145a:ba5d:a5af]) by smtp.gmail.com with ESMTPSA id d3sm1613907qtr.19.2021.06.22.06.18.14 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 22 Jun 2021 06:18:15 -0700 (PDT) To: gcc-patches Subject: [COMMITTED 3/7] Add relational support to fold_using_range Message-ID: Date: Tue, 22 Jun 2021 09:18:14 -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=-12.1 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_ASCII_DIVIDERS, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H4, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP, T_FILL_THIS_FORM_SHORT 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-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 patch get the ball rolling by adding relation support to fold_using_ranges. This enables relations to be set and queried by ranger, and the results applied to any ranges being calculated. At this point, any further additions to range-ops will be reflected in relational processing.  Currently only range-ops enabled opcodes are being handled, but the design of fold_using_range and gori_computes is such that we can now add relation processing to builtins or any other kind of statement easily.   That will be follow on work. With this patch we can finally fold useless relations away. I've tried to be efficient, and the current overhead is less than 1% of compile time in EVRP. Bootstraps on x86_64-pc-linux-gnu with no regressions.  Pushed. Andrew From a2c9173331914eff3d728c07afaeee71892689ba Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Thu, 17 Jun 2021 14:09:48 -0400 Subject: [PATCH 3/7] Add relational support to fold_using_range Enable a relation oracle in ranger, and add full range-op relation support to fold_using_range. * gimple-range-cache.cc (ranger_cache::ranger_cache): Create a relation_oracle if dominators exist. (ranger_cache::~ranger_cache): Dispose of oracle. (ranger_cache::dump_bb): Dump oracle. * gimple-range.cc (fur_source::fur_source): New. (fur_source::get_operand): Use mmeber query. (fur_source::get_phi_operand): Use member_query. (fur_source::query_relation): New. (fur_source::register_dependency): Delete. (fur_source::register_relation): New. (fur_edge::fur_edge): Adjust. (fur_edge::get_phi_operand): Fix comment. (fur_edge::query): Delete. (fur_stmt::fur_stmt): Adjust. (fur_stmt::query): Delete. (fur_depend::fur_depend): Adjust. (fur_depend::register_relation): New. (fur_depend::register_relation): New. (fur_list::fur_list): Adjust. (fur_list::get_operand): Use member query. (fold_using_range::range_of_range_op): Process and query relations. (fold_using_range::range_of_address): Adjust dependency call. (fold_using_range::range_of_phi): Ditto. (gimple_ranger::gimple_ranger): New. Use ranger_ache oracle. (fold_using_range::relation_fold_and_or): New. (fold_using_range::postfold_gcond_edges): New. * gimple-range.h (class gimple_ranger): Adjust. (class fur_source): Adjust members. (class fur_stmt): Ditto. (class fold_using_range): Ditto. --- gcc/gimple-range-cache.cc | 10 ++ gcc/gimple-range.cc | 355 +++++++++++++++++++++++++++++++------- gcc/gimple-range.h | 22 ++- 3 files changed, 324 insertions(+), 63 deletions(-) diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index def604dc149..4347485cf98 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -714,6 +714,12 @@ ranger_cache::ranger_cache () m_update_list.safe_grow_cleared (last_basic_block_for_fn (cfun)); m_update_list.truncate (0); m_temporal = new temporal_cache; + // If DOM info is available, spawn an oracle as well. + if (dom_info_available_p (CDI_DOMINATORS)) + m_oracle = new relation_oracle (); + else + m_oracle = NULL; + unsigned x, lim = last_basic_block_for_fn (cfun); // Calculate outgoing range info upfront. This will fully populate the // m_maybe_variant bitmap which will help eliminate processing of names @@ -728,6 +734,8 @@ ranger_cache::ranger_cache () ranger_cache::~ranger_cache () { + if (m_oracle) + delete m_oracle; delete m_temporal; m_workback.release (); m_update_list.release (); @@ -750,6 +758,8 @@ ranger_cache::dump_bb (FILE *f, basic_block bb) { m_gori.gori_map::dump (f, bb, false); m_on_entry.dump (f, bb); + if (m_oracle) + m_oracle->dump (f, bb); } // Get the global range for NAME, and return in R. Return false if the diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc index 0a2c72b29aa..385cecf330b 100644 --- a/gcc/gimple-range.cc +++ b/gcc/gimple-range.cc @@ -47,14 +47,25 @@ along with GCC; see the file COPYING3. If not see #include "vr-values.h" #include "gimple-range.h" -// Evaluate expression EXPR using the source information the class was -// instantiated with. Place the result in R, and return TRUE. If a range -// cannot be calculated, return FALSE. +// Construct a fur_source, and set the m_query field. + +fur_source::fur_source (range_query *q) +{ + if (q) + m_query = q; + else if (cfun) + m_query = get_range_query (cfun); + else + m_query = get_global_range_query (); + m_gori = NULL; +} + +// Invoke range_of_expr on EXPR. bool fur_source::get_operand (irange &r, tree expr) { - return get_range_query (cfun)->range_of_expr (r, expr); + return m_query->range_of_expr (r, expr); } // Evaluate EXPR for this stmt as a PHI argument on edge E. Use the current @@ -63,23 +74,36 @@ fur_source::get_operand (irange &r, tree expr) bool fur_source::get_phi_operand (irange &r, tree expr, edge e) { - return get_range_query (cfun)->range_on_edge (r, e, expr); + return m_query->range_on_edge (r, e, expr); +} + +// Default is no relation. + +relation_kind +fur_source::query_relation (tree op1 ATTRIBUTE_UNUSED, + tree op2 ATTRIBUTE_UNUSED) +{ + return VREL_NONE; } -// Default is to not register any dependencies from fold_using_range. +// Default registers nothing. void -fur_source::register_dependency (tree lhs ATTRIBUTE_UNUSED, - tree rhs ATTRIBUTE_UNUSED) +fur_source::register_relation (gimple *s ATTRIBUTE_UNUSED, + relation_kind k ATTRIBUTE_UNUSED, + tree op1 ATTRIBUTE_UNUSED, + tree op2 ATTRIBUTE_UNUSED) { } -// Default object is the current range query. +// Default registers nothing. -range_query * -fur_source::query () +void +fur_source::register_relation (edge e ATTRIBUTE_UNUSED, + relation_kind k ATTRIBUTE_UNUSED, + tree op1 ATTRIBUTE_UNUSED, + tree op2 ATTRIBUTE_UNUSED) { - return get_range_query (cfun); } // This version of fur_source will pick a range up off an edge. @@ -90,22 +114,16 @@ public: fur_edge (edge e, range_query *q = NULL); virtual bool get_operand (irange &r, tree expr) OVERRIDE; virtual bool get_phi_operand (irange &r, tree expr, edge e) OVERRIDE; - virtual range_query *query () OVERRIDE; private: - range_query *m_query; edge m_edge; }; // Instantiate an edge based fur_source. inline -fur_edge::fur_edge (edge e, range_query *q) +fur_edge::fur_edge (edge e, range_query *q) : fur_source (q) { m_edge = e; - if (q) - m_query = q; - else - m_query = get_range_query (cfun); } // Get the value of EXPR on edge m_edge. @@ -122,31 +140,19 @@ fur_edge::get_operand (irange &r, tree expr) bool fur_edge::get_phi_operand (irange &r, tree expr, edge e) { - // edge to edge recalculations not supoprted yet, until we sort it out. + // Edge to edge recalculations not supoprted yet, until we sort it out. gcc_checking_assert (e == m_edge); return m_query->range_on_edge (r, e, expr); } -// Return the current range_query object. - -range_query * -fur_edge::query () -{ - return m_query; -} - // Instantiate a stmt based fur_source. -fur_stmt::fur_stmt (gimple *s, range_query *q) +fur_stmt::fur_stmt (gimple *s, range_query *q) : fur_source (q) { m_stmt = s; - if (q) - m_query = q; - else - m_query = get_global_range_query (); } -// Retrieve range of EXPR as it occurs as a use on stmt M_STMT. +// Retreive range of EXPR as it occurs as a use on stmt M_STMT. bool fur_stmt::get_operand (irange &r, tree expr) @@ -165,12 +171,12 @@ fur_stmt::get_phi_operand (irange &r, tree expr, edge e) return e_src.get_operand (r, expr); } -// Return the current range_query object. +// Return relation based from m_stmt. -range_query * -fur_stmt::query () +relation_kind +fur_stmt::query_relation (tree op1, tree op2) { - return m_query; + return m_query->query_relation (m_stmt, op1, op2); } // This version of fur_source will pick a range from a stmt, and also register @@ -180,12 +186,15 @@ class fur_depend : public fur_stmt { public: fur_depend (gimple *s, gori_compute *gori, range_query *q = NULL); - virtual void register_dependency (tree lhs, tree rhs) OVERRIDE; + virtual void register_relation (gimple *stmt, relation_kind k, tree op1, + tree op2) OVERRIDE; + virtual void register_relation (edge e, relation_kind k, tree op1, + tree op2) OVERRIDE; private: - gori_compute *m_gori; + relation_oracle *m_oracle; }; -// Instantiate a stmt based fur_source with a GORI object +// Instantiate a stmt based fur_source with a GORI object. inline fur_depend::fur_depend (gimple *s, gori_compute *gori, range_query *q) @@ -193,14 +202,28 @@ fur_depend::fur_depend (gimple *s, gori_compute *gori, range_query *q) { gcc_checking_assert (gori); m_gori = gori; + // Set relations if there is an oracle in the range_query. + // This will enable registering of relationships as they are discovered. + m_oracle = q->oracle (); + +} + +// Register a relation on a stmt if there is an oracle. + +void +fur_depend::register_relation (gimple *s, relation_kind k, tree op1, tree op2) +{ + if (m_oracle) + m_oracle->register_relation (s, k, op1, op2); } -// find and add any dependnecy between LHS and RHS +// Register a relation on an edge if there is an oracle. void -fur_depend::register_dependency (tree lhs, tree rhs) +fur_depend::register_relation (edge e, relation_kind k, tree op1, tree op2) { - m_gori->register_dependency (lhs, rhs); + if (m_oracle) + m_oracle->register_relation (e, k, op1, op2); } // This version of fur_source will pick a range up from a list of ranges @@ -223,7 +246,7 @@ private: // One range supplied for unary operations. -fur_list::fur_list (irange &r1) +fur_list::fur_list (irange &r1) : fur_source (NULL) { m_list = m_local; m_index = 0; @@ -233,7 +256,7 @@ fur_list::fur_list (irange &r1) // Two ranges supplied for binary operations. -fur_list::fur_list (irange &r1, irange &r2) +fur_list::fur_list (irange &r1, irange &r2) : fur_source (NULL) { m_list = m_local; m_index = 0; @@ -244,7 +267,7 @@ fur_list::fur_list (irange &r1, irange &r2) // Arbitrary number of ranges in a vector. -fur_list::fur_list (unsigned num, irange *list) +fur_list::fur_list (unsigned num, irange *list) : fur_source (NULL) { m_list = list; m_index = 0; @@ -257,7 +280,7 @@ bool fur_list::get_operand (irange &r, tree expr) { if (m_index >= m_limit) - return get_range_query (cfun)->range_of_expr (r, expr); + return m_query->range_of_expr (r, expr); r = m_list[m_index++]; gcc_checking_assert (range_compatible_p (TREE_TYPE (expr), r.type ())); return true; @@ -290,7 +313,6 @@ fold_range (irange &r, gimple *s, irange &r1, irange &r2) return f.fold_stmt (r, s, src); } - // Fold stmt S into range R using NUM_ELEMENTS from VECTOR as the initial // operands encountered. @@ -636,18 +658,50 @@ fold_using_range::range_of_range_op (irange &r, gimple *s, fur_source &src) // Fold range, and register any dependency if available. int_range<2> r2 (type); handler->fold_range (r, type, range1, r2); - if (lhs) - src.register_dependency (lhs, op1); + if (lhs && gimple_range_ssa_p (op1)) + { + if (src.gori ()) + src.gori ()->register_dependency (lhs, op1); + relation_kind rel; + rel = handler->lhs_op1_relation (r, range1, range1); + if (rel != VREL_NONE) + src.register_relation (s, rel, lhs, op1); + } } else if (src.get_operand (range2, op2)) { + relation_kind rel = src.query_relation (op1, op2); + if (dump_file && (dump_flags & TDF_DETAILS) && rel != VREL_NONE) + { + fprintf (dump_file, " folding with relation "); + print_relation (dump_file, rel); + fputc ('\n', dump_file); + } // Fold range, and register any dependency if available. - handler->fold_range (r, type, range1, range2); + handler->fold_range (r, type, range1, range2, rel); + relation_fold_and_or (r, s, src); if (lhs) { - src.register_dependency (lhs, op1); - src.register_dependency (lhs, op2); + if (src.gori ()) + { + src.gori ()->register_dependency (lhs, op1); + src.gori ()->register_dependency (lhs, op2); + } + if (gimple_range_ssa_p (op1)) + { + rel = handler->lhs_op1_relation (r, range1, range2); + if (rel != VREL_NONE) + src.register_relation (s, rel, lhs, op1); + } + if (gimple_range_ssa_p (op2)) + { + rel= handler->lhs_op2_relation (r, range1, range2); + if (rel != VREL_NONE) + src.register_relation (s, rel, lhs, op2); + } } + else if (is_a (s)) + postfold_gcond_edges (as_a (s), src); } else r.set_varying (type); @@ -686,8 +740,8 @@ fold_using_range::range_of_address (irange &r, gimple *stmt, fur_source &src) { tree ssa = TREE_OPERAND (base, 0); tree lhs = gimple_get_lhs (stmt); - if (lhs && gimple_range_ssa_p (ssa)) - src.register_dependency (lhs, ssa); + if (lhs && gimple_range_ssa_p (ssa) && src.gori ()) + src.gori ()->register_dependency (lhs, ssa); gcc_checking_assert (irange::supports_type_p (TREE_TYPE (ssa))); src.get_operand (r, ssa); range_cast (r, TREE_TYPE (gimple_assign_rhs1 (stmt))); @@ -764,8 +818,8 @@ fold_using_range::range_of_phi (irange &r, gphi *phi, fur_source &src) edge e = gimple_phi_arg_edge (phi, x); // Register potential dependencies for stale value tracking. - if (gimple_range_ssa_p (arg)) - src.register_dependency (phi_def, arg); + if (gimple_range_ssa_p (arg) && src.gori ()) + src.gori ()->register_dependency (phi_def, arg); // Get the range of the argument on its edge. src.get_phi_operand (arg_range, arg, e); @@ -1149,6 +1203,12 @@ fold_using_range::range_of_cond_expr (irange &r, gassign *s, fur_source &src) return true; } +gimple_ranger::gimple_ranger () +{ + // If the cache has a relation oracle, use it. + m_oracle = m_cache.oracle (); +} + bool gimple_ranger::range_of_expr (irange &r, tree expr, gimple *stmt) { @@ -1464,6 +1524,185 @@ fold_using_range::range_of_ssa_name_with_loop_info (irange &r, tree name, r.set_varying (type); } +// ----------------------------------------------------------------------- + +// Check if an && or || expression can be folded based on relations. ie +// c_2 = a_6 > b_7 +// c_3 = a_6 < b_7 +// c_4 = c_2 && c_3 +// c_2 and c_3 can never be true at the same time, +// Therefore c_4 can always resolve to false based purely on the relations. + +void +fold_using_range::relation_fold_and_or (irange& lhs_range, gimple *s, + fur_source &src) +{ + // No queries or already folded. + if (!src.gori () || !src.query ()->oracle () || lhs_range.singleton_p ()) + return; + + // Only care about AND and OR expressions. + enum tree_code code = gimple_expr_code (s); + bool is_and = false; + if (code == BIT_AND_EXPR || code == TRUTH_AND_EXPR) + is_and = true; + else if (code != BIT_IOR_EXPR && code != TRUTH_OR_EXPR) + return; + + tree lhs = gimple_get_lhs (s); + tree ssa1 = gimple_range_ssa_p (gimple_range_operand1 (s)); + tree ssa2 = gimple_range_ssa_p (gimple_range_operand2 (s)); + + // Deal with || and && only when there is a full set of symbolics. + if (!lhs || !ssa1 || !ssa2 + || (TREE_CODE (TREE_TYPE (lhs)) != BOOLEAN_TYPE) + || (TREE_CODE (TREE_TYPE (ssa1)) != BOOLEAN_TYPE) + || (TREE_CODE (TREE_TYPE (ssa2)) != BOOLEAN_TYPE)) + return; + + // Now we know its a boolean AND or OR expression with boolean operands. + // Ideally we search dependencies for common names, and see what pops out. + // until then, simply try to resolve direct dependencies. + + // Both names will need to have 2 direct dependencies. + tree ssa1_dep2 = src.gori ()->depend2 (ssa1); + tree ssa2_dep2 = src.gori ()->depend2 (ssa2); + if (!ssa1_dep2 || !ssa2_dep2) + return; + + tree ssa1_dep1 = src.gori ()->depend1 (ssa1); + tree ssa2_dep1 = src.gori ()->depend1 (ssa2); + // Make sure they are the same dependencies, and detect the order of the + // relationship. + bool reverse_op2 = true; + if (ssa1_dep1 == ssa2_dep1 && ssa1_dep2 == ssa2_dep2) + reverse_op2 = false; + else if (ssa1_dep1 != ssa2_dep2 || ssa1_dep2 != ssa2_dep1) + return; + + range_operator *handler1 = gimple_range_handler (SSA_NAME_DEF_STMT (ssa1)); + range_operator *handler2 = gimple_range_handler (SSA_NAME_DEF_STMT (ssa2)); + + int_range<2> bool_one (boolean_true_node, boolean_true_node); + + relation_kind relation1 = handler1->op1_op2_relation (bool_one); + relation_kind relation2 = handler2->op1_op2_relation (bool_one); + if (relation1 == VREL_NONE || relation2 == VREL_NONE) + return; + + if (reverse_op2) + relation2 = relation_negate (relation2); + + // x && y is false if the relation intersection of the true cases is NULL. + if (is_and && relation_intersect (relation1, relation2) == VREL_EMPTY) + lhs_range = int_range<2> (boolean_false_node, boolean_false_node); + // x || y is true if the union of the true cases is NO-RELATION.. + // ie, one or the other being true covers the full range of possibilties. + else if (!is_and && relation_union (relation1, relation2) == VREL_NONE) + lhs_range = bool_one; + else + return; + + range_cast (lhs_range, TREE_TYPE (lhs)); + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " Relation adjustment: "); + print_generic_expr (dump_file, ssa1, TDF_SLIM); + fprintf (dump_file, " and "); + print_generic_expr (dump_file, ssa2, TDF_SLIM); + fprintf (dump_file, " combine to produce "); + lhs_range.dump (dump_file); + fputc ('\n', dump_file); + } + + return; +} + +// Register any outgoing edge relations from a conditional branch. + +void +fold_using_range::postfold_gcond_edges (gcond *s, fur_source &src) +{ + int_range_max r; + tree name; + range_operator *handler; + basic_block bb = gimple_bb (s); + + edge e0 = EDGE_SUCC (bb, 0); + if (!single_pred_p (e0->dest)) + e0 = NULL; + + edge e1 = EDGE_SUCC (bb, 1); + if (!single_pred_p (e1->dest)) + e1 = NULL; + + // At least one edge needs to be single pred. + if (!e0 && !e1) + return; + + // First, register the gcond itself. This will catch statements like + // if (a_2 < b_5) + tree ssa1 = gimple_range_ssa_p (gimple_range_operand1 (s)); + tree ssa2 = gimple_range_ssa_p (gimple_range_operand2 (s)); + if (ssa1 && ssa2) + { + handler = gimple_range_handler (s); + gcc_checking_assert (handler); + if (e0) + { + gcond_edge_range (r, e0); + relation_kind relation = handler->op1_op2_relation (r); + if (relation != VREL_NONE) + src.register_relation (e0, relation, ssa1, ssa2); + } + if (e1) + { + gcond_edge_range (r, e1); + relation_kind relation = handler->op1_op2_relation (r); + if (relation != VREL_NONE) + src.register_relation (e1, relation, ssa1, ssa2); + } + } + + // Outgoing relations of GORI exports require a gori engine. + if (!src.gori ()) + return; + + range_query *q = src.query (); + // Now look for other relations in the exports. This will find stmts + // leading to the condition such as: + // c_2 = a_4 < b_7 + // if (c_2) + + FOR_EACH_GORI_EXPORT_NAME (*(src.gori ()), bb, name) + { + if (TREE_CODE (TREE_TYPE (name)) != BOOLEAN_TYPE) + continue; + gimple *stmt = SSA_NAME_DEF_STMT (name); + handler = gimple_range_handler (stmt); + if (!handler) + continue; + tree ssa1 = gimple_range_ssa_p (gimple_range_operand1 (stmt)); + tree ssa2 = gimple_range_ssa_p (gimple_range_operand2 (stmt)); + if (ssa1 && ssa2) + { + if (e0 && src.gori ()->outgoing_edge_range_p (r, e0, name, *q) + && r.singleton_p ()) + { + relation_kind relation = handler->op1_op2_relation (r); + if (relation != VREL_NONE) + src.register_relation (e0, relation, ssa1, ssa2); + } + if (e1 && src.gori ()->outgoing_edge_range_p (r, e1, name, *q) + && r.singleton_p ()) + { + relation_kind relation = handler->op1_op2_relation (r); + if (relation != VREL_NONE) + src.register_relation (e1, relation, ssa1, ssa2); + } + } + } +} // -------------------------------------------------------------------------- // trace_ranger implementation. diff --git a/gcc/gimple-range.h b/gcc/gimple-range.h index b9cffdb8ee0..87911b95d86 100644 --- a/gcc/gimple-range.h +++ b/gcc/gimple-range.h @@ -58,6 +58,7 @@ along with GCC; see the file COPYING3. If not see class gimple_ranger : public range_query { public: + gimple_ranger (); virtual bool range_of_stmt (irange &r, gimple *, tree name = NULL) OVERRIDE; virtual bool range_of_expr (irange &r, tree name, gimple * = NULL) OVERRIDE; virtual bool range_on_edge (irange &r, edge e, tree name) OVERRIDE; @@ -74,15 +75,25 @@ protected: // Source of all operands for fold_using_range and gori_compute. // It abstracts out the source of an operand so it can come from a stmt or -// and edge or anywhere a derived classof fur_source wants. +// and edge or anywhere a derived class of fur_source wants. +// THe default simply picks up ranges from the current range_query. class fur_source { public: + fur_source (range_query *q = NULL); + inline range_query *query () { return m_query; } + inline class gori_compute *gori () { return m_gori; }; virtual bool get_operand (irange &r, tree expr); virtual bool get_phi_operand (irange &r, tree expr, edge e); - virtual void register_dependency (tree lhs, tree rhs); - virtual range_query *query (); + virtual relation_kind query_relation (tree op1, tree op2); + virtual void register_relation (gimple *stmt, relation_kind k, tree op1, + tree op2); + virtual void register_relation (edge e, relation_kind k, tree op1, + tree op2); +protected: + range_query *m_query; + gori_compute *m_gori; }; // fur_stmt is the specification for drawing an operand from range_query Q @@ -94,9 +105,8 @@ public: fur_stmt (gimple *s, range_query *q = NULL); virtual bool get_operand (irange &r, tree expr) OVERRIDE; virtual bool get_phi_operand (irange &r, tree expr, edge e) OVERRIDE; - virtual range_query *query () OVERRIDE; + virtual relation_kind query_relation (tree op1, tree op2) OVERRIDE; private: - range_query *m_query; gimple *m_stmt; }; @@ -132,6 +142,8 @@ protected: bool range_of_phi (irange &r, gphi *phi, fur_source &src); void range_of_ssa_name_with_loop_info (irange &, tree, class loop *, gphi *, fur_source &src); + void relation_fold_and_or (irange& lhs_range, gimple *s, fur_source &src); + void postfold_gcond_edges (gcond *s, fur_source &src); }; -- 2.17.2