From patchwork Wed May 24 21:19:52 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1785869 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=yuSYPPIc; 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 4QRPGv5j4Lz20Pb for ; Thu, 25 May 2023 07:20:23 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 25FF1383FBB2 for ; Wed, 24 May 2023 21:20:21 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 25FF1383FBB2 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1684963221; bh=a1J2z+RL4l/lgRkEHT8+qwWtPK52fFvUUTASkTyBgdc=; h=Date:Subject:To:Cc:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=yuSYPPIcy8L3bzbb/TqUb9adfMoUeui7psv1eTsFCsdIZsETkJuUnotkbT9+E5vSs 9ZMnmzsfHqFoKG13nQ/LcE7ECaT0SAHI6t9PIzfFfWL0x59Lq7To6qWWMODkOYKNgg EmPuD97FsAwJejR6OnwaKpHZvbrmwaQ18ZlHq8/I= 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 43CDF3857734 for ; Wed, 24 May 2023 21:19:59 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 43CDF3857734 Received: from mail-qv1-f72.google.com (mail-qv1-f72.google.com [209.85.219.72]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-330-gMktcfPGOD-FF_6yVVtCWA-1; Wed, 24 May 2023 17:19:55 -0400 X-MC-Unique: gMktcfPGOD-FF_6yVVtCWA-1 Received: by mail-qv1-f72.google.com with SMTP id 6a1803df08f44-62382e86f83so2639556d6.0 for ; Wed, 24 May 2023 14:19:55 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684963194; x=1687555194; h=content-language:cc:to:subject:from:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=E0P9tX2Cz7GFR0qXOcS8a2BjfJo2/t1JrPXhHSsAb4U=; b=Nen/D37miiu4NdHA5obAgVQv3bzrUqZh4wMRO0lMfKFl7GtyWkBNo1aqPAGH/x2pT8 VSqtwcBuNIKQDHzCeqLKGmgCKV4soPgwvCIj8JKUVEo7sdirgj/lZ0xshjRpf5/dXFTq ZkaavabQRoUbsjtQ4wxEyKblJj4rO6V01eel0eAaaJY+tP5Ed9CGzGVKJfZ8N+zhByZn lAkhqRijGsZABe5jVnyGWhYf0Vu8WPtB4bnpFWSkOEHS519mEJ4ig6K/RWFae8xDi83t oQuiIECQnd1BY0q1pjnuwPw2IkH56JSBjgELdXqOWvxFJiWTKb+kospKkOjp2y8+8STm F1uQ== X-Gm-Message-State: AC+VfDzVVMC+tVnE7iD6msjS0pu48H20XQcLUCJ7NhWSFYcfH8mXfoqQ UA0zMypdhzEksZyM6AsbKPS7zeLy8pxusPl1lS5UJ+8P4FF0bJm/2UbiNqSj5uIwBj205SJ+Uu/ 8zTsQ3KM7rElVosW1fL5eEtYWS2JJGRVucCG9qMFB31PO075EJ+B2Bfv6zmxHx67dZnUjA77qzX dfiA== X-Received: by 2002:a05:622a:28c:b0:3f4:f58d:d00d with SMTP id z12-20020a05622a028c00b003f4f58dd00dmr30511297qtw.40.1684963194392; Wed, 24 May 2023 14:19:54 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ6V+2mST+DX+G0K5HEhG8XNLiI6v4gsY+tpX+KzLfZDefa4DKY3NmkdG1njxZDqqlydopgWlw== X-Received: by 2002:a05:622a:28c:b0:3f4:f58d:d00d with SMTP id z12-20020a05622a028c00b003f4f58dd00dmr30511274qtw.40.1684963194001; Wed, 24 May 2023 14:19:54 -0700 (PDT) Received: from ?IPV6:2607:fea8:51df:4200::933? ([2607:fea8:51df:4200::933]) by smtp.gmail.com with ESMTPSA id lf19-20020a0562142cd300b0061b608dc4c1sm3871196qvb.94.2023.05.24.14.19.53 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 24 May 2023 14:19:53 -0700 (PDT) Message-ID: <6a24c0bf-aa0d-5e13-6852-705605db15ec@redhat.com> Date: Wed, 24 May 2023 17:19:52 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.11.0 Subject: [COMMITTED 4/4] - Gimple range PHI analyzer and testcases To: gcc-patches Cc: "hernandez, aldy" X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-10.4 required=5.0 tests=BAYES_00, BODY_8BITS, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_ASCII_DIVIDERS, KAM_SHORT, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE 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 patch provide the framework for a gimple-range phi analyzer. Currently, the  primary purpose is to give better initial values for members of a "phi group" a PHI group is defined as a a group of PHI nodes whose arguments are all either members of the same PHI group, or one of 2 other values:  - An initializer, (typically a constant), but not necessarily,  - A modifier, which is always of the form:   member_ssa = member_ssa OP op2 When the analyzer finds a group which matches this pattern, it tries to evaluate the modifier using the initial value and project a range for the entire group. This initial version is fairly simplistic.  It looks for 2 things: 1) if there is a relation between LHS and the other ssa_name in the modifier, then we can project a range. ie,         a_3 = a_2 + 1 if there is a relation generated by the stmt which say a_3 > a_2, and the initial value is 0, we can project a range of [0, +INF] as the moifier will cause the value to always increase, and not wrap. Likewise, for a_3 = a_2 - 1,  we can project a range of [-INF, 0] based on the "<" relationship between a_3 and a_2. 2) If there is no relationship, then we use the initial range and "simulate" the modifier statement a set number of times looking to see if the value converges. Currently I have arbitrarily hard coded 10 attempts, but intend to change this down the road with a --param, as well as to perhaps influence it with any known values from SCEV regarding known iterations of the loop and possibly change it based on optimization levels. I also suspect something like one more than the number of bits in the type might help with any bitmasking tricks. Theres a lot of additinal things we can do to enhance this, but this framework provides a start.  These 2 initial evaluations fix 107822, and part of 107986.  There is about a 1.5% slowdown to VRP to invoke and utilize the analyzer in all 3 passes of VRP.  overall compile time is 0.06% slower. Bootstraps on x86_64-pc-linux-gnu  with no regressions.  Pushed. Andrew From 64e844c1182198e49d33f9fa138b9a782371225d Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Wed, 24 May 2023 09:52:26 -0400 Subject: [PATCH 4/4] Gimple range PHI analyzer and testcases Provide a PHI analyzer framework to provive better initial values for PHI nodes which formk groups with initial values and single statements which modify the PHI values in some predicatable way. PR tree-optimization/107822 PR tree-optimization/107986 gcc/ * Makefile.in (OBJS): Add gimple-range-phi.o. * gimple-range-cache.h (ranger_cache::m_estimate): New phi_analyzer pointer member. * gimple-range-fold.cc (fold_using_range::range_of_phi): Use phi_analyzer if no loop info is available. * gimple-range-phi.cc: New file. * gimple-range-phi.h: New file. * tree-vrp.cc (execute_ranger_vrp): Utililze a phi_analyzer. gcc/testsuite/ * gcc.dg/pr107822.c: New. * gcc.dg/pr107986-1.c: New. --- gcc/Makefile.in | 1 + gcc/gimple-range-cache.h | 2 + gcc/gimple-range-fold.cc | 27 ++ gcc/gimple-range-phi.cc | 518 ++++++++++++++++++++++++++++++ gcc/gimple-range-phi.h | 109 +++++++ gcc/testsuite/gcc.dg/pr107822.c | 20 ++ gcc/testsuite/gcc.dg/pr107986-1.c | 16 + gcc/tree-vrp.cc | 7 +- 8 files changed, 699 insertions(+), 1 deletion(-) create mode 100644 gcc/gimple-range-phi.cc create mode 100644 gcc/gimple-range-phi.h create mode 100644 gcc/testsuite/gcc.dg/pr107822.c create mode 100644 gcc/testsuite/gcc.dg/pr107986-1.c diff --git a/gcc/Makefile.in b/gcc/Makefile.in index bb63b5c501d..1d39e6dd3f8 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1454,6 +1454,7 @@ OBJS = \ gimple-range-gori.o \ gimple-range-infer.o \ gimple-range-op.o \ + gimple-range-phi.o \ gimple-range-trace.o \ gimple-ssa-backprop.o \ gimple-ssa-isolate-paths.o \ diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h index afcf8d7de7b..93d16294d2e 100644 --- a/gcc/gimple-range-cache.h +++ b/gcc/gimple-range-cache.h @@ -23,6 +23,7 @@ along with GCC; see the file COPYING3. If not see #include "gimple-range-gori.h" #include "gimple-range-infer.h" +#include "gimple-range-phi.h" // This class manages a vector of pointers to ssa_block ranges. It // provides the basis for the "range on entry" cache for all @@ -136,6 +137,7 @@ private: void exit_range (vrange &r, tree expr, basic_block bb, enum rfd_mode); bool edge_range (vrange &r, edge e, tree name, enum rfd_mode); + phi_analyzer *m_estimate; vec m_workback; class update_list *m_update; }; diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc index 4df065c8a6e..173d9f386c5 100644 --- a/gcc/gimple-range-fold.cc +++ b/gcc/gimple-range-fold.cc @@ -934,6 +934,7 @@ fold_using_range::range_of_phi (vrange &r, gphi *phi, fur_source &src) } } + bool loop_info_p = false; // If SCEV is available, query if this PHI has any known values. if (scev_initialized_p () && !POINTER_TYPE_P (TREE_TYPE (phi_def))) @@ -956,6 +957,32 @@ fold_using_range::range_of_phi (vrange &r, gphi *phi, fur_source &src) fprintf (dump_file, "\n"); } r.intersect (loop_range); + loop_info_p = true; + } + } + } + + if (!loop_info_p && phi_analysis_available_p () + && irange::supports_p (TREE_TYPE (phi_def))) + { + phi_group *g = (phi_analysis())[phi_def]; + if (g && !(g->range ().varying_p ())) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " PHI group range found for "); + print_generic_expr (dump_file, phi_def, TDF_SLIM); + fprintf (dump_file, ": "); + g->range ().dump (dump_file); + fprintf (dump_file, " and adjusted original range from :"); + r.dump (dump_file); + } + r.intersect (g->range ()); + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " to :"); + r.dump (dump_file); + fprintf (dump_file, "\n"); } } } diff --git a/gcc/gimple-range-phi.cc b/gcc/gimple-range-phi.cc new file mode 100644 index 00000000000..ffb4691d06b --- /dev/null +++ b/gcc/gimple-range-phi.cc @@ -0,0 +1,518 @@ +/* Gimple range phi analysis. + Copyright (C) 2023 Free Software Foundation, Inc. + Contributed by Andrew MacLeod . + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 3, or (at your option) +any later version. + +GCC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "insn-codes.h" +#include "tree.h" +#include "gimple.h" +#include "ssa.h" +#include "gimple-pretty-print.h" +#include "gimple-range.h" +#include "gimple-range-cache.h" +#include "value-range-storage.h" +#include "tree-cfg.h" +#include "target.h" +#include "attribs.h" +#include "gimple-iterator.h" +#include "gimple-walk.h" +#include "cfganal.h" + +// There can be only one running at a time. +static phi_analyzer *phi_analysis_object = NULL; + +// Initialize a PHI analyzer with range query Q. + +void +phi_analysis_initialize (range_query &q) +{ + gcc_checking_assert (!phi_analysis_object); + phi_analysis_object = new phi_analyzer (q); +} + +// Terminate the current PHI analyzer. if F is non-null, dump the tables + +void +phi_analysis_finalize () +{ + gcc_checking_assert (phi_analysis_object); + delete phi_analysis_object; + phi_analysis_object = NULL; +} + +// Return TRUE is there is a PHI analyzer operating. +bool +phi_analysis_available_p () +{ + return phi_analysis_object != NULL; +} + +// Return the phi analyzer object. + +phi_analyzer &phi_analysis () +{ + gcc_checking_assert (phi_analysis_object); + return *phi_analysis_object; +} + +// Initialize a phi_group from another group G. + +phi_group::phi_group (const phi_group &g) +{ + m_group = g.m_group; + m_initial_value = g.m_initial_value; + m_initial_edge = g.m_initial_edge; + m_modifier = g.m_modifier; + m_modifier_op = g.m_modifier_op; + m_vr = g.m_vr; +} + +// Create a new phi_group with members BM, initialvalue INIT_VAL, modifier +// statement MOD, and resolve values using query Q. +// Calculate the range for the gropup if possible, otherwise set it to +// VARYING. + +phi_group::phi_group (bitmap bm, tree init_val, edge e, gimple *mod, + range_query *q) +{ + // we dont expect a modifer and no inital value, so trap to have a look. + // perhaps they are dead cycles and we can just used UNDEFINED. + gcc_checking_assert (init_val); + + m_modifier_op = is_modifier_p (mod, bm); + m_group = bm; + m_initial_value = init_val; + m_initial_edge = e; + m_modifier = mod; + if (q->range_on_edge (m_vr, m_initial_edge, m_initial_value)) + { + // No modifier means the initial range is the full range. + // Otherwise try to calculate a range. + if (!m_modifier_op || calculate_using_modifier (q)) + return; + } + // Couldn't calculate a range, set to varying. + m_vr.set_varying (TREE_TYPE (init_val)); +} + +// Return 0 if S is not a modifier statment for group members BM. +// If it could be a modifier, return which operand position (1 or 2) +// the phi member occurs in. +unsigned +phi_group::is_modifier_p (gimple *s, const bitmap bm) +{ + if (!s) + return 0; + gimple_range_op_handler handler (s); + if (handler) + { + tree op1 = gimple_range_ssa_p (handler.operand1 ()); + tree op2 = gimple_range_ssa_p (handler.operand2 ()); + // Also disallow modifiers that have 2 ssa-names. + if (op1 && !op2 && bitmap_bit_p (bm, SSA_NAME_VERSION (op1))) + return 1; + else if (op2 && !op1 && bitmap_bit_p (bm, SSA_NAME_VERSION (op2))) + return 2; + } + return 0; +} + +// Calulcate the range of the phi group using range_query Q. + +bool +phi_group::calculate_using_modifier (range_query *q) +{ + // Look at the modifier for any relation + relation_trio trio = fold_relations (m_modifier, q); + relation_kind k = VREL_VARYING; + if (m_modifier_op == 1) + k = trio.lhs_op1 (); + else if (m_modifier_op == 2) + k = trio.lhs_op2 (); + else + return false; + + // If we can resolve the range using relations, use that range. + if (refine_using_relation (k, q)) + return true; + + // If the initial value is undefined, do not calculate a range. + if (m_vr.undefined_p ()) + return false; + + // Examine modifier and run X iterations to see if it convergences. + // The constructor initilaized m_vr to the initial value already. + int_range_max nv; + for (unsigned x = 0; x< 10; x++) + { + if (!fold_range (nv, m_modifier, m_vr, q)) + return false; + // If they are equal, then we have convergence. + if (nv == m_vr) + return true; + // Update range and try again. + m_vr.union_ (nv); + } + // Never converged, so bail for now. we could examine the pattern + // from m_initial to m_vr as an extension Especially if we had a way + // to project the actual number of iterations (SCEV?) + // + // We can also try to identify "parallel" phis to get loop counts and + // determine the number of iterations of these parallel PHIs. + // + return false; +} + + +// IF the modifier statement has a relation K between the modifier and the +// PHI member in it, we can project a range based on that. +// Use range_query Q to resolve values. +// ie, a_2 = PHI <0, a_3> and a_3 = a_2 + 1 +// if the relation a_3 > a_2 is present, the know the range is [0, +INF] + +bool +phi_group::refine_using_relation (relation_kind k, range_query *q) +{ + if (k == VREL_VARYING) + return false; + tree type = TREE_TYPE (m_initial_value); + // If the type wraps, then relations dont tell us much. + if (TYPE_OVERFLOW_WRAPS (type)) + return false; + + switch (k) + { + case VREL_LT: + case VREL_LE: + { + // Value always decreases. + int_range<2> lb; + int_range<2> ub; + if (!q->range_on_edge (ub, m_initial_edge, m_initial_value)) + break; + if (ub.undefined_p ()) + return false; + lb.set_varying (type); + m_vr.set (type, lb.lower_bound (), ub.upper_bound ()); + return true; + } + + case VREL_GT: + case VREL_GE: + { + // Value always increases. + int_range<2> lb; + int_range<2> ub; + if (!q->range_on_edge (lb, m_initial_edge, m_initial_value)) + break; + if (lb.undefined_p ()) + return false; + ub.set_varying (type); + m_vr.set (type, lb.lower_bound (), ub.upper_bound ()); + return true; + } + + // If its always equal, then its simply the initial value. + // which is what m_vr has already been set to. + case VREL_EQ: + return true; + + default: + break; + } + + return false; +} + +// Dump the information for a phi group to file F. + +void +phi_group::dump (FILE *f) +{ + unsigned i; + bitmap_iterator bi; + fprintf (f, "PHI GROUP <"); + + EXECUTE_IF_SET_IN_BITMAP (m_group, 0, i, bi) + { + print_generic_expr (f, ssa_name (i), TDF_SLIM); + fputc (' ',f); + } + + fprintf (f, ">\n - Initial value : "); + if (m_initial_value) + { + if (TREE_CODE (m_initial_value) == SSA_NAME) + print_gimple_stmt (f, SSA_NAME_DEF_STMT (m_initial_value), 0, TDF_SLIM); + else + print_generic_expr (f, m_initial_value, TDF_SLIM); + fprintf (f, " on edge %d->%d", m_initial_edge->src->index, + m_initial_edge->dest->index); + } + else + fprintf (f, "NONE"); + fprintf (f, "\n - Modifier : "); + if (m_modifier) + print_gimple_stmt (f, m_modifier, 0, TDF_SLIM); + else + fprintf (f, "NONE\n"); + fprintf (f, " - Range : "); + m_vr.dump (f); + fputc ('\n', f); +} + +// ------------------------------------------------------------------------- + +// Construct a phi analyzer which uses range_query G to pick up values. + +phi_analyzer::phi_analyzer (range_query &g) : m_global (g) +{ + m_work.create (0); + m_work.safe_grow (20); + + m_tab.create (0); +// m_tab.safe_grow_cleared (num_ssa_names + 100); + bitmap_obstack_initialize (&m_bitmaps); + m_simple = BITMAP_ALLOC (&m_bitmaps); + m_current = BITMAP_ALLOC (&m_bitmaps); +} + +// Destruct a PHI analyzer. + +phi_analyzer::~phi_analyzer () +{ + bitmap_obstack_release (&m_bitmaps); + m_tab.release (); + m_work.release (); +} + +// Return the group, if any, that NAME is part of. Do no analysis. + +phi_group * +phi_analyzer::group (tree name) const +{ + gcc_checking_assert (TREE_CODE (name) == SSA_NAME); + if (!is_a (SSA_NAME_DEF_STMT (name))) + return NULL; + unsigned v = SSA_NAME_VERSION (name); + if (v >= m_tab.length ()) + return NULL; + return m_tab[v]; +} + +// Return the group NAME is associated with, if any. If name has not been +// procvessed yet, do the analysis to determine if it is part of a group +// and return that. + +phi_group * +phi_analyzer::operator[] (tree name) +{ + gcc_checking_assert (TREE_CODE (name) == SSA_NAME); + + // Initial support for irange only. + if (!irange::supports_p (TREE_TYPE (name))) + return NULL; + if (!is_a (SSA_NAME_DEF_STMT (name))) + return NULL; + + unsigned v = SSA_NAME_VERSION (name); + // Already been processed and not part of a group. + if (bitmap_bit_p (m_simple, v)) + return NULL; + + if (v >= m_tab.length () || !m_tab[v]) + { + process_phi (as_a (SSA_NAME_DEF_STMT (name))); + if (bitmap_bit_p (m_simple, v)) + return NULL; + // If m_simple bit isn't set, then process_phi allocated the table + // and should have a group. + gcc_checking_assert (v < m_tab.length ()); + } + return m_tab[v]; +} + +// Process phi node PHI to see if it it part of a group. + +void +phi_analyzer::process_phi (gphi *phi) +{ + gcc_checking_assert (!group (gimple_phi_result (phi))); + bool cycle_p = true; + + // Start with the LHS of the PHI in the worklist. + unsigned x; + m_work.truncate (0); + m_work.safe_push (gimple_phi_result (phi)); + bitmap_clear (m_current); + + // We can only have 2 externals: an initial value and a modifier. + // Any more than that and this fails to be a group. + unsigned m_num_extern = 0; + tree m_external[2]; + edge m_ext_edge[2]; + + while (m_work.length () > 0) + { + tree phi_def = m_work.pop (); + gphi *phi_stmt = as_a (SSA_NAME_DEF_STMT (phi_def)); + // if the phi is already in a cycle, its a complex situation, so revert + // to simple. + if (group (phi_def)) + { + cycle_p = false; + continue; + } + bitmap_set_bit (m_current, SSA_NAME_VERSION (phi_def)); + // Process the args. + for (x = 0; x < gimple_phi_num_args (phi_stmt); x++) + { + tree arg = gimple_phi_arg_def (phi_stmt, x); + if (arg == phi_def) + continue; + enum tree_code code = TREE_CODE (arg); + if (code == SSA_NAME) + { + unsigned v = SSA_NAME_VERSION (arg); + // Already a member of this potential group. + if (bitmap_bit_p (m_current, v)) + continue; + // Part of a different group ends cycle possibility. + if (group (arg) || bitmap_bit_p (m_simple, v)) + { + cycle_p = false; + break; + } + // Check if its a PHI to examine. + // *FIX* Will miss initial values that originate from a PHI. + gimple *arg_stmt = SSA_NAME_DEF_STMT (arg); + if (arg_stmt && is_a (arg_stmt)) + { + m_work.safe_push (arg); + continue; + } + } + // Other non-ssa names that arent constants are not understood + // and terminate analysis. + else if (code != INTEGER_CST && code != REAL_CST) + { + cycle_p = false; + continue; + } + // More than 2 outside names/CONST is too complicated. + if (m_num_extern >= 2) + { + cycle_p = false; + break; + } + + m_external[m_num_extern] = arg; + m_ext_edge[m_num_extern++] = gimple_phi_arg_edge (phi_stmt, x); + } + } + + // If there are no names in the group, we're done. + if (bitmap_empty_p (m_current)) + return; + + phi_group *g = NULL; + if (cycle_p) + { + bool valid = true; + gimple *mod = NULL; + signed init_idx = -1; + // At this point all the PHIs have been added to the bitmap. + // the external list needs to be checked for initial values and modifiers. + for (x = 0; x < m_num_extern; x++) + { + tree name = m_external[x]; + if (TREE_CODE (name) == SSA_NAME + && phi_group::is_modifier_p (SSA_NAME_DEF_STMT (name), m_current)) + { + // Can't have multiple modifiers. + if (mod) + valid = false; + mod = SSA_NAME_DEF_STMT (name); + continue; + } + // Can't have 2 initializers either. + if (init_idx != -1) + valid = false; + init_idx = x; + } + if (valid) + { + // Try to create a group based on m_current. If a result comes back + // with a range that isn't varying, create the group. + phi_group cyc (m_current, m_external[init_idx], + m_ext_edge[init_idx], mod, &m_global); + if (!cyc.range ().varying_p ()) + g = new phi_group (cyc); + } + } + // If this dpoesn;t form a group, all members are instead simple phis. + if (!g) + { + bitmap_ior_into (m_simple, m_current); + return; + } + + if (num_ssa_names >= m_tab.length ()) + m_tab.safe_grow_cleared (num_ssa_names + 100); + + // Now set all entries in the group to this record. + unsigned i; + bitmap_iterator bi; + EXECUTE_IF_SET_IN_BITMAP (m_current, 0, i, bi) + { + // Can't be in more than one group. + gcc_checking_assert (m_tab[i] == NULL); + m_tab[i] = g; + } + // Allocate a new bitmap for the next time as the original one is now part + // of the new phi group. + m_current = BITMAP_ALLOC (&m_bitmaps); +} + +void +phi_analyzer::dump (FILE *f) +{ + bool header = false; + bitmap_clear (m_current); + for (unsigned x = 0; x < m_tab.length (); x++) + { + if (bitmap_bit_p (m_simple, x)) + continue; + if (bitmap_bit_p (m_current, x)) + continue; + if (m_tab[x] == NULL) + continue; + phi_group *g = m_tab[x]; + bitmap_ior_into (m_current, g->group ()); + if (!header) + { + header = true; + fprintf (dump_file, "\nPHI GROUPS:\n"); + } + g->dump (f); + } +} diff --git a/gcc/gimple-range-phi.h b/gcc/gimple-range-phi.h new file mode 100644 index 00000000000..b5120e97bf3 --- /dev/null +++ b/gcc/gimple-range-phi.h @@ -0,0 +1,109 @@ +/* Header file for gimple range phi analysis. + Copyright (C) 2023 Free Software Foundation, Inc. + Contributed by Andrew MacLeod . + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#ifndef GCC_SSA_RANGE_PHI_H +#define GCC_SSA_RANGE_PHI_H + +// ------------------------------------------------------------------------- + +// A PHI_GROUP consists of a set of SSA_NAMES which are all PHI_DEFS, and +// their arguemnts contain nothing but other PHI defintions, with at most +// 2 exceptions: +// 1 - An initial value. This is either a constant, or another non-phi name +// with a single incoming edge to the cycle group +// 2 - A modifier statement which adjusts the value. ie, name2 = phi_name + 1 +// The initial range is used to create one bound and the modifier is examined +// to determine the other bound. +// All members of the PHI cycle will be given the same range. +// +// For example, given the follwoing sequences: +// qa_20 = qa_10 + 1; +// qa_9 = PHI +// qa_10 = PHI <0(2), qa_9(5)> +// +// We can determine the following group: +// +// PHI cycle members qa_9, qa_10 +// Initial value : 0 +// modifier stmt: qa_20 = qa_10 + 1; +// +// Based on just this analysis, We can project that qa_9 and qa_10 will have +// a range of [0, +INF]. + +class phi_group +{ +public: + phi_group (bitmap bm, tree init_val, edge e, gimple *mod, range_query *q); + phi_group (const phi_group &g); + const_bitmap group () const { return m_group; } + const vrange &range () const { return m_vr; } + tree initial_value () const { return m_initial_value; } + gimple *modifier_stmt () const { return m_modifier; } + void dump (FILE *); +protected: + bool calculate_using_modifier (range_query *q); + bool refine_using_relation (relation_kind k, range_query *q); + static unsigned is_modifier_p (gimple *s, const bitmap bm); + bitmap m_group; + tree m_initial_value; // Name or constant. + edge m_initial_edge; // Edge of initial value. + gimple *m_modifier; // Single stmt which modifies phi group. + unsigned m_modifier_op; // Operand of group member in modifier stmt. + int_range<3> m_vr; + friend class phi_analyzer; +}; + +// The phi anlyzer will return the group that name belongs to. +// If inforamtion is not known about a name yet, analysis is conducted by +// looking at the arguments to PHIS and following them to their defs to +// determine whether the conditions are met to form a new group. + +class phi_analyzer +{ +public: + phi_analyzer (range_query &); + ~phi_analyzer (); + phi_group *operator[] (tree name); + void dump (FILE *f); +protected: + phi_group *group (tree name) const; + void process_phi (gphi *phi); + range_query &m_global; + vec m_work; + + bitmap m_simple; // Processed, not part of a group. + bitmap m_current; // Potential group currently being analyzed. + vec m_tab; + bitmap_obstack m_bitmaps; +}; + +// These are the APIs to start and stop a phi analyzerin a SCEV like manner. +// There can only be one operating at any given time. +// When initialized, a range-query if provided to do lookups of values for +// PHIs and to evaluate modifier and initial value statements. +// To avoid problems, this should be some form of constant query, like +// global_range_query or better yet a const_query from a functioning ranger. + +bool phi_analysis_available_p (); +phi_analyzer &phi_analysis (); +void phi_analysis_initialize (range_query &); +void phi_analysis_finalize (); + +#endif // GCC_SSA_RANGE_PHI_H diff --git a/gcc/testsuite/gcc.dg/pr107822.c b/gcc/testsuite/gcc.dg/pr107822.c new file mode 100644 index 00000000000..c68ecbe8f66 --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr107822.c @@ -0,0 +1,20 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-evrp" } */ + +int b; +void foo(); +void(a)(); +int main() { + int c; + int *d = &c; + *d = a && 8; + b = 0; + for (; b < 9; ++b) + *d ^= 3; + if (*d) + ; + else + foo(); +} + +/* { dg-final { scan-tree-dump-not "foo" "evrp" } } */ diff --git a/gcc/testsuite/gcc.dg/pr107986-1.c b/gcc/testsuite/gcc.dg/pr107986-1.c new file mode 100644 index 00000000000..1125ab0ea18 --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr107986-1.c @@ -0,0 +1,16 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-evrp" } */ + +void bar (); +void foo (int *a) +{ + int qa = 0; + for (int i = 0; i < 3; i++) + if (a[i]) + a[qa++] = 0; +/* Show that we know qa is not negative. */ + if (qa < 0) + bar (); +} + +/* { dg-final { scan-tree-dump-not "bar" "evrp" } } */ diff --git a/gcc/tree-vrp.cc b/gcc/tree-vrp.cc index 7f03f54cdd7..c52e9971faa 100644 --- a/gcc/tree-vrp.cc +++ b/gcc/tree-vrp.cc @@ -994,11 +994,15 @@ execute_ranger_vrp (struct function *fun, bool warn_array_bounds_p, set_all_edges_as_executable (fun); gimple_ranger *ranger = enable_ranger (fun, false); rvrp_folder folder (ranger); + phi_analysis_initialize (ranger->const_query ()); folder.substitute_and_fold (); // Remove tagged builtin-unreachable and maybe update globals. folder.m_unreachable.remove_and_update_globals (final_p); if (dump_file && (dump_flags & TDF_DETAILS)) - ranger->dump (dump_file); + { + phi_analysis ().dump (dump_file); + ranger->dump (dump_file); + } if ((warn_array_bounds || warn_strict_flex_arrays) && warn_array_bounds_p) { @@ -1020,6 +1024,7 @@ execute_ranger_vrp (struct function *fun, bool warn_array_bounds_p, array_checker.check (); } + phi_analysis_finalize (); disable_ranger (fun); scev_finalize (); loop_optimizer_finalize (); -- 2.40.1