From patchwork Tue Jun 22 13:17:41 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1495677 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=PE2H5XB8; 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 4G8RmF61s4z9sVp for ; Tue, 22 Jun 2021 23:18:20 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 7F4163877035 for ; Tue, 22 Jun 2021 13:18:18 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 7F4163877035 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1624367898; bh=fwNbOHhzsH9fE650XUUG7XQydNZn9sSStbiI8SCO19w=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=PE2H5XB8/QwnK0aOc6SlYzkAX95/pOQJpBdNXCsbp30+AWejC2QeBXEhFCq2cwDES uHoEgEQCaE43Xboi9PUiHn2kbz/CcZjHUL4qOlxa/6Z1E+GCzaHYTCuGxPbOp1j52h Be6C7S29m/+iKcuJKyWZKbUVBlSUgxOb+vZ60iAg= 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 52F843890439 for ; Tue, 22 Jun 2021 13:17:48 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 52F843890439 Received: from mail-qk1-f199.google.com (mail-qk1-f199.google.com [209.85.222.199]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-5-sROl--z9MpS5jbOMBTQ9wA-1; Tue, 22 Jun 2021 09:17:46 -0400 X-MC-Unique: sROl--z9MpS5jbOMBTQ9wA-1 Received: by mail-qk1-f199.google.com with SMTP id 2-20020a3709020000b02903aa9873df32so17990247qkj.15 for ; Tue, 22 Jun 2021 06:17:46 -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=fwNbOHhzsH9fE650XUUG7XQydNZn9sSStbiI8SCO19w=; b=pjWlmu0/RPsFw9i2pmzBxRGXnZ/tnxEpc9QxtN2Xzl3npiG1WQA1R643pbl40UQysf REuIOTCWYs3HSJ7EQnm7b5vL1PhpVGexASBFywYltL1ebYibZAWnV0tW+Swe+fSrhe3M MLVHwAgkaH6N4n1XIkUrw7niGKRT0Ac1aTqyn+J8Do8sZNXKh8DWr1vsIYv6zHnO4mXx 6ASv0Hhb1iCraZyZ3ih8mcuICiXuzrXZUkF9Mb7mveIok6BjPLe7KFCAt3jQCODc3bvm 4s8HZIZ7zHBmMY6hVkHoo4UIAO4IaZ5/M4SJawgbQA39jLpXbfuV1LPMxG2G2XDaNeTT Nwjg== X-Gm-Message-State: AOAM530r5ODP+YMCIFe63SfYhVFpoDOeC7spjjcXQvDXpAyfnm6NJoIi aZgZiTGCZj+fXGWwuS8DUJ8ldL/AD7B9FSV1AQby8X0w3iJ/w1S2HVbPayYZyMFFQlG9n+I/uX0 Vx3acHLEziVm/XKdsPA== X-Received: by 2002:a05:622a:100b:: with SMTP id d11mr3399529qte.371.1624367865724; Tue, 22 Jun 2021 06:17:45 -0700 (PDT) X-Google-Smtp-Source: ABdhPJx6HZySC+kQ2e2VdRgUCQS4ArPEEsMe7qGk/1HR7Wk5tve4/lURf334sqUVL3u4sCsu52+F+A== X-Received: by 2002:a05:622a:100b:: with SMTP id d11mr3399501qte.371.1624367865509; Tue, 22 Jun 2021 06:17:45 -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 w28sm1719748qtt.88.2021.06.22.06.17.43 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 22 Jun 2021 06:17:44 -0700 (PDT) To: gcc-patches Subject: [COMMITTED 1/7] Initial value-relation code. Message-ID: Date: Tue, 22 Jun 2021 09:17:41 -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=-10.6 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_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-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 file introduces a relation oracle to GCC. Rather than introducing a new enum for relations, I chose to reuse a range of enum tree_code, leaving us with mostly familiar names: EQ_EXPR, NE_EXPR, GT_EXPR, GE_EXPR, LT_EXPR and LE_EXPR.  In addition to these relations, are 2 other codes: #define VREL_NONE              TRUTH_NOT_EXPR #define VREL_EMPTY             LTGT_EXPR VREL_NONE represents a lack of a relation (ie  a = b + c   there is no relation between b and c, so thats VREL_NONE) VREL_EMPTY represents an EMPTY , or impossible relation.  This is usually the result of combining relations that apply (ie, a > b && a < b  provides a VREL_EMPTY representing the relation between a and b on the true side.  Its impossible.) The additional relations have tree codes chosen carefully to form a contiguous series from VREL_NONE to  NE_EXPR enabling some internal calculation tables to be used indexing from 0..last_relation .   This is easily changed, but seems convenient. The oracle is pretty basic to start, but will be enhanced as we move along. It requires a dominance tree and stores/looks up things based on dominance. It hasn't been extensively analyzed in an iterative/on-demand environment yet, so there may be some warts that show up.  It should never give a wrong result, but its possible  it may miss something in some instances.  We'll work those out as we find them.     It exists in 2 parts: - an equivalence oracle which manages all the EQ_EXPR relations, and groups equivalences as sets, and - a relation oracle which derives from that which handles all the other relations. The API is straightforward.  Relations are registered via one of 2 routines: void register_relation (gimple *stmt, relation_kind k, tree op1, tree op2); void register_relation (edge e, relation_kind k, tree op1, tree op2); and there is a single query routine: relation_kind query_relation (basic_block bb, tree ssa1, tree ssa2); Our friend the range_query object now contains a relation pointer, and this is set and used by ranger.  range_query has also had 2 query routines added so if a pass is using a ranger, it can also invoke the range queries that same way range_of_expr is invokes.  ie:  get_range_query (cfun)->query_relation (stmt, ssa1, ssa2)   THis mechanism has the advantage that you dont need to check if an oracle is present, it'll simple return VREL_NONE (no relation) between 2 ssa-names if there is no oracle. More advanced users can access the oracle directly via the get_range_query (cfun)->oracle () call. It would be possible to create an oracle for a pass without a ranger, and manage the relations in the pass. That is not being done yet, but would be easy enough to add the enable/disable() oracle routines much like the enable/disable_ranger routines. When using ranger, this information is set and propagated automatically, and the results are transparently applied to the ranges that are generated.  For instance, if (a_2 < b_3)       // register relation a_2 < b_3 on the true edge    c_3 = a_2 > b_3    // applies a_2 < b_3, and the range of c_3 is set to [0, 0]  or false. Currently only direct 1st order relations are tracked. I will get to transitive relations soon, but that is not in this first round. Relations on edges are also currently limited to single predecessor blocks ..  They are simply dropped/ignored if the destination of the edge has multiple preds. I will be writing up a relation guide in the not too distant future, alone with a few of the other components. This patch provides the oracle, as well as the range_query interface, but does not actually do anything. Bootstraps on x86_64-pc-linux-gnu with no regressions.  Pushed. Andrew From 3aaa69e5f30e1904d7ca2bb711b1cb0c62b6895f Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Thu, 17 Jun 2021 10:19:31 -0400 Subject: [PATCH 1/7] Initial value-relation code. This code provides a both an equivalence and relation oracle which can be accessed via a range_query object. This initial code drop includes the oracles and access them, but does not utilize them yet. * Makefile.in (OBJS): Add value-relation.o. * gimple-range.h: Adjust include files. * tree-data-ref.c: Adjust include file order. * value-query.cc (range_query::get_value_range): Default to no oracle. (range_query::query_relation): New. (range_query::query_relation): New. * value-query.h (class range_query): Adjust. * value-relation.cc: New. * value-relation.h: New. --- gcc/Makefile.in | 1 + gcc/gimple-range.h | 2 +- gcc/tree-data-ref.c | 2 +- gcc/value-query.cc | 50 +++ gcc/value-query.h | 11 + gcc/value-relation.cc | 932 ++++++++++++++++++++++++++++++++++++++++++ gcc/value-relation.h | 159 +++++++ 7 files changed, 1155 insertions(+), 2 deletions(-) create mode 100644 gcc/value-relation.cc create mode 100644 gcc/value-relation.h diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 4cb2966157e..ebf26442992 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1688,6 +1688,7 @@ OBJS = \ value-query.o \ value-range.o \ value-range-equiv.o \ + value-relation.o \ value-prof.o \ var-tracking.o \ varasm.o \ diff --git a/gcc/gimple-range.h b/gcc/gimple-range.h index fc28123f9ec..b9cffdb8ee0 100644 --- a/gcc/gimple-range.h +++ b/gcc/gimple-range.h @@ -24,8 +24,8 @@ along with GCC; see the file COPYING3. If not see #include "range.h" -#include "range-op.h" #include "value-query.h" +#include "range-op.h" #include "gimple-range-edge.h" #include "gimple-range-gori.h" #include "gimple-range-cache.h" diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c index 6f3352ffb1f..b6abd8b8de7 100644 --- a/gcc/tree-data-ref.c +++ b/gcc/tree-data-ref.c @@ -97,8 +97,8 @@ along with GCC; see the file COPYING3. If not see #include "tree-eh.h" #include "ssa.h" #include "internal-fn.h" -#include "range-op.h" #include "vr-values.h" +#include "range-op.h" static struct datadep_stats { diff --git a/gcc/value-query.cc b/gcc/value-query.cc index 93609f3c7c4..17dfdb1ccbe 100644 --- a/gcc/value-query.cc +++ b/gcc/value-query.cc @@ -174,6 +174,7 @@ range_query::get_value_range (const_tree expr, gimple *stmt) range_query::range_query () { equiv_alloc = new equiv_allocator; + m_oracle = NULL; } range_query::~range_query () @@ -452,3 +453,52 @@ global_range_query::range_of_expr (irange &r, tree expr, gimple *stmt) return true; } + +// Return any known relation between SSA1 and SSA2 before stmt S is executed. +// If GET_RANGE is true, query the range of both operands first to ensure +// the defintions have been processed and any relations have be created. + +relation_kind +range_query::query_relation (gimple *s, tree ssa1, tree ssa2, bool get_range) +{ + int_range_max tmp; + if (!m_oracle || TREE_CODE (ssa1) != SSA_NAME || TREE_CODE (ssa2) != SSA_NAME) + return VREL_NONE; + + // Ensure ssa1 and ssa2 have both been evaluated. + if (get_range) + { + range_of_expr (tmp, ssa1, s); + range_of_expr (tmp, ssa2, s); + } + return m_oracle->query_relation (gimple_bb (s), ssa1, ssa2); +} + +// Return any known relation between SSA1 and SSA2 on edge E. +// If GET_RANGE is true, query the range of both operands first to ensure +// the defintions have been processed and any relations have be created. + +relation_kind +range_query::query_relation (edge e, tree ssa1, tree ssa2, bool get_range) +{ + basic_block bb; + int_range_max tmp; + if (!m_oracle || TREE_CODE (ssa1) != SSA_NAME || TREE_CODE (ssa2) != SSA_NAME) + return VREL_NONE; + + // Use destination block if it has a single predecessor, and this picks + // up any relation on the edge. + // Otherwise choose the src edge and the result is the same as on-exit. + if (!single_pred_p (e->dest)) + bb = e->src; + else + bb = e->dest; + + // Ensure ssa1 and ssa2 have both been evaluated. + if (get_range) + { + range_on_edge (tmp, e, ssa1); + range_on_edge (tmp, e, ssa2); + } + return m_oracle->query_relation (bb, ssa1, ssa2); +} diff --git a/gcc/value-query.h b/gcc/value-query.h index 54af031ea42..5161d23714b 100644 --- a/gcc/value-query.h +++ b/gcc/value-query.h @@ -22,6 +22,8 @@ along with GCC; see the file COPYING3. If not see #ifndef GCC_QUERY_H #define GCC_QUERY_H +#include "value-relation.h" + // The value_query class is used by optimization passes that require // valueizing SSA names in terms of a tree value, but have no neeed // for ranges. @@ -91,6 +93,14 @@ public: virtual bool range_on_edge (irange &r, edge, tree expr); virtual bool range_of_stmt (irange &r, gimple *, tree name = NULL); + // Query if there is any relation between SSA1 and SSA2. + relation_kind query_relation (gimple *s, tree ssa1, tree ssa2, + bool get_range = true); + relation_kind query_relation (edge e, tree ssa1, tree ssa2, + bool get_range = true); + // If present, Access relation oracle for more advanced uses. + inline relation_oracle *oracle () const { return m_oracle; } + // DEPRECATED: This method is used from vr-values. The plan is to // rewrite all uses of it to the above API. virtual const class value_range_equiv *get_value_range (const_tree, @@ -102,6 +112,7 @@ protected: void free_value_range_equiv (class value_range_equiv *); bool get_tree_range (irange &r, tree expr, gimple *stmt); bool get_arith_expr_range (irange &r, tree expr, gimple *stmt); + relation_oracle *m_oracle; private: class equiv_allocator *equiv_alloc; diff --git a/gcc/value-relation.cc b/gcc/value-relation.cc new file mode 100644 index 00000000000..3c8698f2a54 --- /dev/null +++ b/gcc/value-relation.cc @@ -0,0 +1,932 @@ +/* Header file for the value range relational processing. + Copyright (C) 2020-2021 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 "tree.h" +#include "gimple.h" +#include "ssa.h" + +#include "gimple-range.h" +#include "tree-pretty-print.h" +#include "gimple-pretty-print.h" +#include "alloc-pool.h" +#include "dominance.h" + +// These VREL codes are arranged such that VREL_NONE is the first +// code, and all the rest are contiguous up to and including VREL_LAST. + +#define VREL_FIRST VREL_NONE +#define VREL_LAST NE_EXPR +#define VREL_COUNT (VREL_LAST - VREL_FIRST + 1) + +// vrel_range_assert will either assert that the tree code passed is valid, +// or mark invalid codes as unreachable to help with table optimation. +#if CHECKING_P + #define vrel_range_assert(c) \ + gcc_checking_assert ((c) >= VREL_FIRST && (c) <= VREL_LAST) +#else + #define vrel_range_assert(c) \ + if ((c) < VREL_FIRST || (c) > VREL_LAST) \ + gcc_unreachable (); +#endif + +static const char *kind_string[VREL_COUNT] = +{ "none", "<", "<=", ">", ">=", "empty", "==", "!=" }; + +// Print a relation_kind REL to file F. + +void +print_relation (FILE *f, relation_kind rel) +{ + vrel_range_assert (rel); + fprintf (f, " %s ", kind_string[rel - VREL_FIRST]); +} + +// This table is used to negate the operands. op1 REL op2 -> !(op1 REL op2). +relation_kind rr_negate_table[VREL_COUNT] = { +// NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, EMPTY, EQ_EXPR, NE_EXPR + VREL_NONE, GE_EXPR, GT_EXPR, LE_EXPR, LT_EXPR, VREL_EMPTY, NE_EXPR, EQ_EXPR }; + +// Negate the relation, as in logical negation. + +relation_kind +relation_negate (relation_kind r) +{ + vrel_range_assert (r); + return rr_negate_table [r - VREL_FIRST]; +} + +// This table is used to swap the operands. op1 REL op2 -> op2 REL op1. +relation_kind rr_swap_table[VREL_COUNT] = { +// NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, EMPTY, EQ_EXPR, NE_EXPR + VREL_NONE, GT_EXPR, GE_EXPR, LT_EXPR, LE_EXPR, VREL_EMPTY, EQ_EXPR, NE_EXPR }; + +// Return the relation as if the operands were swapped. + +relation_kind +relation_swap (relation_kind r) +{ + vrel_range_assert (r); + return rr_swap_table [r - VREL_FIRST]; +} + +// This table is used to perform an intersection between 2 relations. + +relation_kind rr_intersect_table[VREL_COUNT][VREL_COUNT] = { +// NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, EMPTY, EQ_EXPR, NE_EXPR +// VREL_NONE + { VREL_NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, VREL_EMPTY, EQ_EXPR, NE_EXPR }, +// LT_EXPR + { LT_EXPR, LT_EXPR, LT_EXPR, VREL_EMPTY, VREL_EMPTY, VREL_EMPTY, VREL_EMPTY, LT_EXPR }, +// LE_EXPR + { LE_EXPR, LT_EXPR, LE_EXPR, VREL_EMPTY, EQ_EXPR, VREL_EMPTY, EQ_EXPR, LT_EXPR }, +// GT_EXPR + { GT_EXPR, VREL_EMPTY, VREL_EMPTY, GT_EXPR, GT_EXPR, VREL_EMPTY, VREL_EMPTY, GT_EXPR }, +// GE_EXPR + { GE_EXPR, VREL_EMPTY, EQ_EXPR, GT_EXPR, GE_EXPR, VREL_EMPTY, EQ_EXPR, GT_EXPR }, +// VREL_EMPTY + { VREL_EMPTY, VREL_EMPTY, VREL_EMPTY, VREL_EMPTY, VREL_EMPTY, VREL_EMPTY, VREL_EMPTY, VREL_EMPTY }, +// EQ_EXPR + { EQ_EXPR, VREL_EMPTY, EQ_EXPR, VREL_EMPTY, EQ_EXPR, VREL_EMPTY, EQ_EXPR, VREL_EMPTY }, +// NE_EXPR + { NE_EXPR, LT_EXPR, LT_EXPR, GT_EXPR, GT_EXPR, VREL_EMPTY, VREL_EMPTY, NE_EXPR } }; + + +// Intersect relation R! with relation R2 and return the resulting relation. + +relation_kind +relation_intersect (relation_kind r1, relation_kind r2) +{ + vrel_range_assert (r1); + vrel_range_assert (r2); + return rr_intersect_table[r1 - VREL_FIRST][r2 - VREL_FIRST]; +} + + +// This table is used to perform a union between 2 relations. + +relation_kind rr_union_table[VREL_COUNT][VREL_COUNT] = { +// NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, EMPTY, EQ_EXPR, NE_EXPR +// VREL_NONE + { VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE }, +// LT_EXPR + { VREL_NONE, LT_EXPR, LE_EXPR, NE_EXPR, VREL_NONE, LT_EXPR, LE_EXPR, NE_EXPR }, +// LE_EXPR + { VREL_NONE, LE_EXPR, LE_EXPR, VREL_NONE, VREL_NONE, LE_EXPR, LE_EXPR, VREL_NONE }, +// GT_EXPR + { VREL_NONE, NE_EXPR, VREL_NONE, GT_EXPR, GE_EXPR, GT_EXPR, GE_EXPR, NE_EXPR }, +// GE_EXPR + { VREL_NONE, VREL_NONE, VREL_NONE, GE_EXPR, GE_EXPR, GE_EXPR, GE_EXPR, VREL_NONE }, +// VREL_EMPTY + { VREL_NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, VREL_EMPTY, EQ_EXPR, NE_EXPR }, +// EQ_EXPR + { VREL_NONE, LE_EXPR, LE_EXPR, GE_EXPR, GE_EXPR, EQ_EXPR, EQ_EXPR, VREL_NONE }, +// NE_EXPR + { VREL_NONE, NE_EXPR, VREL_NONE, NE_EXPR, VREL_NONE, NE_EXPR, VREL_NONE, NE_EXPR } }; + +// Union relation R1 with relation R2 and return the result. + +relation_kind +relation_union (relation_kind r1, relation_kind r2) +{ + vrel_range_assert (r1); + vrel_range_assert (r2); + return rr_union_table[r1 - VREL_FIRST][r2 - VREL_FIRST]; +} + + +// ------------------------------------------------------------------------- + +// This class represents an equivalency set, and contains a link to the next +// one in the list to be searched. + +// The very first element in the m_equiv chain is actually just a summary +// element in which the m_names bitmap is used to indicate that an ssa_name +// has an equivalence set in this block. +// This allows for much faster traversal of the DOM chain, as a search for +// SSA_NAME simply requires walking the DOM chain until a block is found +// which has the bit for SSA_NAME set. Then scan for the equivalency set in +// that block. No previous blcoks need be searched. + +class equiv_chain +{ +public: + bitmap m_names; // ssa-names in equiv set. + basic_block m_bb; // Block this belongs to + equiv_chain *m_next; // Next in block list. + void dump (FILE *f) const; // Show names in this list. +}; + + +// Dump the names in this equivalence set. + +void +equiv_chain::dump (FILE *f) const +{ + bitmap_iterator bi; + unsigned i; + + if (!m_names) + return; + fprintf (f, "Equivalence set : ["); + unsigned c = 0; + EXECUTE_IF_SET_IN_BITMAP (m_names, 0, i, bi) + { + if (ssa_name (i)) + { + if (c++) + fprintf (f, ", "); + print_generic_expr (f, ssa_name (i), TDF_SLIM); + } + } + fprintf (f, "]\n"); +} + +// Instantiate an equivalency oracle. + +equiv_oracle::equiv_oracle () +{ + bitmap_obstack_initialize (&m_bitmaps); + m_equiv.create (0); + m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1); + m_equiv_set = BITMAP_ALLOC (&m_bitmaps); + obstack_init (&m_chain_obstack); +} + +// Destruct an equivalency oracle. + +equiv_oracle::~equiv_oracle () +{ + obstack_free (&m_chain_obstack, NULL); + m_equiv.release (); + bitmap_obstack_release (&m_bitmaps); +} + +// Find and return the equivalency set for SSA along the dominators of BB. +// This is the external API. + +const_bitmap +equiv_oracle::equiv_set (tree ssa, basic_block bb) const +{ + // Search the dominator tree for an equivalency. + equiv_chain *equiv = find_equiv_dom (ssa, bb); + if (equiv) + return equiv->m_names; + + return NULL; +} + + +// If SSA has an equivalence in block BB, find and return it. +// Otherwise return NULL. + +equiv_chain * +equiv_oracle::find_equiv_block (unsigned ssa, int bb) const +{ + equiv_chain *ptr = NULL; + if (bb >= (int)m_equiv.length ()) + return NULL; + + // If there are equiv sets and SSA is in one in this block, find it. + // Otherwise return NULL. + if (m_equiv[bb] && bitmap_bit_p (m_equiv[bb]->m_names, ssa)) + { + for (ptr = m_equiv[bb]->m_next; ptr; ptr = ptr->m_next) + if (bitmap_bit_p (ptr->m_names, ssa)) + break; + } + return ptr; +} + +// Starting at block BB, walk the dominator chain looking for the nearest +// equivalence set containing NAME. + +equiv_chain * +equiv_oracle::find_equiv_dom (tree name, basic_block bb) const +{ + unsigned v = SSA_NAME_VERSION (name); + // Short circuit looking for names which have no equivalences. + // Saves time looking for something which does not exist. + if (!bitmap_bit_p (m_equiv_set, v)) + return NULL; + + // NAME has at least once equivalence set, check to see if it has one along + // the dominator tree. + for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb)) + { + equiv_chain *ptr = find_equiv_block (v, bb->index); + if (ptr) + return ptr; + } + return NULL; +} + +// Register equivalance between ssa_name V and set EQUIV in block BB, + +bitmap +equiv_oracle::register_equiv (basic_block bb, unsigned v, equiv_chain *equiv) +{ + // V will have an equivalency now. + bitmap_set_bit (m_equiv_set, v); + + // If that equiv chain is in this block, simply use it. + if (equiv->m_bb == bb) + { + bitmap_set_bit (equiv->m_names, v); + bitmap_set_bit (m_equiv[bb->index]->m_names, v); + return NULL; + } + + // Otherwise create an equivalence for this block which is a copy + // of equiv, the add V to the set. + bitmap b = BITMAP_ALLOC (&m_bitmaps); + bitmap_copy (b, equiv->m_names); + bitmap_set_bit (b, v); + return b; +} + +// Register equivalence between set equiv_1 and equiv_2 in block BB. +// Return NULL if either name can be merged with the other. Otherwise +// return a pointer to the combined bitmap of names. This allows the +// caller to do any setup required for a new element. + +bitmap +equiv_oracle::register_equiv (basic_block bb, equiv_chain *equiv_1, + equiv_chain *equiv_2) +{ + // If equiv_1 is alreayd in BB, use it as the combined set. + if (equiv_1->m_bb == bb) + { + bitmap_ior_into (equiv_1->m_names, equiv_2->m_names); + // Its hard to delete from a single linked list, so + // just clear the second one. + if (equiv_2->m_bb == bb) + bitmap_clear (equiv_2->m_names); + else + // Ensure equiv_2s names are in the summary for BB. + bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_2->m_names); + return NULL; + } + // If equiv_2 is in BB, use it for the combined set. + if (equiv_2->m_bb == bb) + { + bitmap_ior_into (equiv_2->m_names, equiv_1->m_names); + // Add equiv_1 names into the summary. + bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_1->m_names); + return NULL; + } + + // At this point, neither equivalence is from this block. + bitmap b = BITMAP_ALLOC (&m_bitmaps); + bitmap_copy (b, equiv_1->m_names); + bitmap_ior_into (b, equiv_2->m_names); + return b; +} + + +// Register an equivalence between SSA1 and SSA2 in block BB. +// The equivalence oracle maintains a vector of equivalencies indexed by basic +// block. When an equivalence bteween SSA1 and SSA2 is registered in block BB, +// a query is made as to what equivalences both names have already, and +// any preexisting equivalences are merged to create a single equivalence +// containing all the ssa_names in this basic block. + +void +equiv_oracle::register_equiv (basic_block bb, tree ssa1, tree ssa2) +{ + unsigned v1 = SSA_NAME_VERSION (ssa1); + unsigned v2 = SSA_NAME_VERSION (ssa2); + equiv_chain *equiv_1 = find_equiv_dom (ssa1, bb); + equiv_chain *equiv_2 = find_equiv_dom (ssa2, bb); + + // Check if they are the same set + if (equiv_1 && equiv_1 == equiv_2) + return; + + bitmap equiv_set; + + // Case where we have 2 SSA_NAMEs that are not in any set. + if (!equiv_1 && !equiv_2) + { + bitmap_set_bit (m_equiv_set, v1); + bitmap_set_bit (m_equiv_set, v2); + + equiv_set = BITMAP_ALLOC (&m_bitmaps); + bitmap_set_bit (equiv_set, v1); + bitmap_set_bit (equiv_set, v2); + } + else if (!equiv_1 && equiv_2) + equiv_set = register_equiv (bb, v1, equiv_2); + else if (equiv_1 && !equiv_2) + equiv_set = register_equiv (bb, v2, equiv_1); + else + equiv_set = register_equiv (bb, equiv_1, equiv_2); + + // A non-null return is a bitmap that is to be added to the current + // block as a new equivalence. + if (!equiv_set) + return; + + equiv_chain *ptr; + + // Check if this is the first time a block has an equivalence added. + // and create a header block. And set the summary for this block. + if (!m_equiv[bb->index]) + { + ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, + sizeof (equiv_chain)); + ptr->m_names = BITMAP_ALLOC (&m_bitmaps); + bitmap_copy (ptr->m_names, equiv_set); + ptr->m_bb = bb; + ptr->m_next = NULL; + m_equiv[bb->index] = ptr; + } + + // Now create the element for this equiv set and initialize it. + ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, sizeof (equiv_chain)); + ptr->m_names = equiv_set; + ptr->m_bb = bb; + gcc_checking_assert (bb->index < (int)m_equiv.length ()); + ptr->m_next = m_equiv[bb->index]->m_next; + m_equiv[bb->index]->m_next = ptr; + bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_set); +} + +// Make sure the BB vector is big enough and grow it if needed. + +void +equiv_oracle::limit_check (basic_block bb) +{ + int i = (bb) ? bb->index : last_basic_block_for_fn (cfun); + if (i >= (int)m_equiv.length ()) + m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1); +} + +// Dump the equivalence sets in BB to file F. + +void +equiv_oracle::dump (FILE *f, basic_block bb) const +{ + if (bb->index >= (int)m_equiv.length ()) + return; + if (!m_equiv[bb->index]) + return; + + equiv_chain *ptr = m_equiv[bb->index]->m_next; + for (; ptr; ptr = ptr->m_next) + ptr->dump (f); +} + +// Dump all equivalence sets known to the oracle. + +void +equiv_oracle::dump (FILE *f) const +{ + fprintf (f, "Equivalency dump\n"); + for (unsigned i = 0; i < m_equiv.length (); i++) + if (m_equiv[i]) + { + fprintf (f, "BB%d\n", i); + dump (f, BASIC_BLOCK_FOR_FN (cfun, i)); + } +} + + +// -------------------------------------------------------------------------- + +// The value-relation class is used to encapsulate the represention of an +// individual relation between 2 ssa-names, and to facilitate operating on +// the relation. + +class value_relation +{ +public: + value_relation (); + value_relation (relation_kind kind, tree n1, tree n2); + void set_relation (relation_kind kind, tree n1, tree n2); + + inline relation_kind kind () const { return related; } + inline tree op1 () const { return name1; } + inline tree op2 () const { return name2; } + + bool union_ (value_relation &p); + bool intersect (value_relation &p); + void negate (); + void swap (); + + void dump (FILE *f) const; +private: + relation_kind related; + tree name1, name2; +}; + +// Set relation R between ssa_name N1 and N2. + +inline void +value_relation::set_relation (relation_kind r, tree n1, tree n2) +{ + gcc_checking_assert (SSA_NAME_VERSION (n1) != SSA_NAME_VERSION (n2)); + related = r; + name1 = n1; + name2 = n2; +} + +// Default constructor. + +inline +value_relation::value_relation () +{ + related = VREL_NONE; + name1 = NULL_TREE; + name2 = NULL_TREE; +} + +// Constructor for relation R between SSA version N1 nd N2. + +inline +value_relation::value_relation (relation_kind kind, tree n1, tree n2) +{ + set_relation (kind, n1, n2); +} + +// Negate the current relation. + +void +value_relation::negate () +{ + related = relation_negate (related); +} + +// Modify the relation as if the operands were being swapped. + +void +value_relation::swap () +{ + related = relation_swap (related); +} + +// Perform an intersection between 2 relations. *this &&= p. + +bool +value_relation::intersect (value_relation &p) +{ + // Save previous value + relation_kind old = related; + + if (p.op1 () == op1 () && p.op2 () == op2 ()) + related = relation_intersect (kind (), p.kind ()); + else if (p.op2 () == op1 () && p.op1 () == op2 ()) + related = relation_intersect (kind (), relation_swap (p.kind ())); + else + return false; + + return old != related; +} + +// Perform a union between 2 relations. *this ||= p. + +bool +value_relation::union_ (value_relation &p) +{ + // Save previous value + relation_kind old = related; + + if (p.op1 () == op1 () && p.op2 () == op2 ()) + related = relation_union (kind(), p.kind()); + else if (p.op2 () == op1 () && p.op1 () == op2 ()) + related = relation_union (kind(), relation_swap (p.kind ())); + else + return false; + + return old != related; +} + + +// Dump the relation to file F. + +void +value_relation::dump (FILE *f) const +{ + if (!name1 || !name2) + { + fprintf (f, "uninitialized"); + return; + } + fputc ('(', f); + print_generic_expr (f, op1 (), TDF_SLIM); + print_relation (f, kind ()); + print_generic_expr (f, op2 (), TDF_SLIM); + fputc(')', f); +} + +// This container is used to link relations in a chain. + +class relation_chain : public value_relation +{ +public: + relation_chain *m_next; +}; + +// ------------------------------------------------------------------------ + +// Instantiate a relation oracle. + +relation_oracle::relation_oracle () +{ + m_relations.create (0); + m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1); + m_relation_set = BITMAP_ALLOC (&m_bitmaps); + m_tmp = BITMAP_ALLOC (&m_bitmaps); +} + +// Destruct a relation oracle. + +relation_oracle::~relation_oracle () +{ + m_relations.release (); +} + +// Register relation K between ssa_name OP1 and OP2 on STMT. + +void +relation_oracle::register_relation (gimple *stmt, relation_kind k, tree op1, + tree op2) +{ + gcc_checking_assert (TREE_CODE (op1) == SSA_NAME); + gcc_checking_assert (TREE_CODE (op2) == SSA_NAME); + gcc_checking_assert (stmt && gimple_bb (stmt)); + + // Don't register lack of a relation. + if (k == VREL_NONE) + return; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + value_relation vr (k, op1, op2); + fprintf (dump_file, " Registering value_relation "); + vr.dump (dump_file); + fprintf (dump_file, " (bb%d) at ", gimple_bb (stmt)->index); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); + } + + // This relation applies to the entire block, use STMT's block. + // Equivalencies are handled by the equivalence oracle. + if (k == EQ_EXPR) + register_equiv (gimple_bb (stmt), op1, op2); + else + register_relation (gimple_bb (stmt), k, op1, op2); +} + +// Register relation K between ssa_name OP1 and OP2 on edge E. + +void +relation_oracle::register_relation (edge e, relation_kind k, tree op1, + tree op2) +{ + gcc_checking_assert (TREE_CODE (op1) == SSA_NAME); + gcc_checking_assert (TREE_CODE (op2) == SSA_NAME); + + // Do not register lack of relation, or blocks which have more than + // edge E for a predecessor. + if (k == VREL_NONE || !single_pred_p (e->dest)) + return; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + value_relation vr (k, op1, op2); + fprintf (dump_file, " Registering value_relation "); + vr.dump (dump_file); + fprintf (dump_file, " on (%d->%d)\n", e->src->index, e->dest->index); + } + + // Equivalencies are handled by the equivalence oracle. + if (k == EQ_EXPR) + register_equiv (e->dest, op1, op2); + else + register_relation (e->dest, k, op1, op2); +} + +// Register relation K between OP! and OP2 in block BB. +// This creates the record and searches for existing records in the dominator +// tree to merge with. + +void +relation_oracle::register_relation (basic_block bb, relation_kind k, tree op1, + tree op2) +{ + gcc_checking_assert (k != VREL_NONE); + + value_relation vr(k, op1, op2); + int bbi = bb->index; + + if (bbi >= (int)m_relations.length()) + m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1); + + // Summary bitmap indicating what ssa_names have relations in this BB. + bitmap bm = m_relations[bbi].m_names; + if (!bm) + bm = m_relations[bbi].m_names = BITMAP_ALLOC (&m_bitmaps); + unsigned v1 = SSA_NAME_VERSION (op1); + unsigned v2 = SSA_NAME_VERSION (op2); + + relation_kind curr; + relation_chain *ptr; + curr = find_relation_block (bbi, v1, v2, &ptr); + // There is an existing relation in this block, just intersect with it. + if (curr != VREL_NONE) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " Intersecting with existing "); + ptr->dump (dump_file); + } + // Check into whether we can simply replace the relation rather than + // intersecting it. THis may help with some optimistic iterative + // updating algorithms. + ptr->intersect (vr); + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " to produce "); + ptr->dump (dump_file); + fprintf (dump_file, "\n"); + } + return; + } + + // Check for an existing relation further up the DOM chain. + // By including dominating relations, The first one found in any search + // will be the aggregate of all the previous ones. + curr = find_relation_dom (bb, v1, v2); + if (curr != VREL_NONE) + k = relation_intersect (curr, k); + + bitmap_set_bit (bm, v1); + bitmap_set_bit (bm, v2); + bitmap_set_bit (m_relation_set, v1); + bitmap_set_bit (m_relation_set, v2); + + ptr = (relation_chain *) obstack_alloc (&m_chain_obstack, + sizeof (relation_chain)); + ptr->set_relation (k, op1, op2); + ptr->m_next = m_relations[bbi].m_head; + m_relations[bbi].m_head = ptr;; +} + +// Find the relation between any ssa_name in B1 and any name in B2 in block BB. +// This will allow equivalencies to be applied to any SSA_NAME in a relation. + +relation_kind +relation_oracle::find_relation_block (unsigned bb, const_bitmap b1, + const_bitmap b2) +{ + const_bitmap bm; + if (bb >= m_relations.length()) + return VREL_NONE; + + bm = m_relations[bb].m_names; + if (!bm) + return VREL_NONE; + + // If both b1 and b2 aren't referenced in thie block, cant be a relation + if (!bitmap_intersect_p (bm, b1) || !bitmap_intersect_p (bm, b2)) + return VREL_NONE; + + // Search for the fiorst relation that contains BOTH an element from B1 + // and B2, and return that relation. + for (relation_chain *ptr = m_relations[bb].m_head; ptr ; ptr = ptr->m_next) + { + unsigned op1 = SSA_NAME_VERSION (ptr->op1 ()); + unsigned op2 = SSA_NAME_VERSION (ptr->op2 ()); + if (bitmap_bit_p (b1, op1) && bitmap_bit_p (b1, op2)) + return ptr->kind (); + if (bitmap_bit_p (b1, op2) && bitmap_bit_p (b1, op1)) + return relation_swap (ptr->kind ()); + } + + return VREL_NONE; +} + +// Search the DOM tree for a relation between an element of B1 and B2, starting +// with block BB. + +relation_kind +relation_oracle::find_relation_dom (basic_block bb, const_bitmap b1, + const_bitmap b2) +{ + relation_kind r; + // If either name does not occur in a relation anywhere, there isnt one. + if (!bitmap_intersect_p (m_relation_set, b1) + || !bitmap_intersect_p (m_relation_set, b2)) + return VREL_NONE; + + // Search each block in the DOM tree checking. + for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb)) + { + r = find_relation_block (bb->index, b1, b2); + if (r != VREL_NONE) + return r; + } + return VREL_NONE; + +} + +// Find a relation in block BB between ssa version V1 and V2. If a relation +// is found, return a pointer to the chain object in OBJ. + +relation_kind +relation_oracle::find_relation_block (int bb, unsigned v1, unsigned v2, + relation_chain **obj) +{ + if (bb >= (int)m_relations.length()) + return VREL_NONE; + + const_bitmap bm = m_relations[bb].m_names; + if (!bm) + return VREL_NONE; + + // If both b1 and b2 aren't referenced in thie block, cant be a relation + if (!bitmap_bit_p (bm, v1) || !bitmap_bit_p (bm, v2)) + return VREL_NONE; + + relation_chain *ptr; + for (ptr = m_relations[bb].m_head; ptr ; ptr = ptr->m_next) + { + unsigned op1 = SSA_NAME_VERSION (ptr->op1 ()); + unsigned op2 = SSA_NAME_VERSION (ptr->op2 ()); + if (v1 == op1 && v2 == op2) + { + if (obj) + *obj = ptr; + return ptr->kind (); + } + if (v1 == op2 && v2 == op1) + { + if (obj) + *obj = ptr; + return relation_swap (ptr->kind ()); + } + } + + return VREL_NONE; +} + +// Find a relation between SSA version V1 and V2 in the dominator tree +// starting with block BB + +relation_kind +relation_oracle::find_relation_dom (basic_block bb, unsigned v1, unsigned v2) +{ + relation_kind r; + // IF either name does not occur in a relation anywhere, there isnt one. + if (!bitmap_bit_p (m_relation_set, v1) || !bitmap_bit_p (m_relation_set, v2)) + return VREL_NONE; + + for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb)) + { + r = find_relation_block (bb->index, v1, v2); + if (r != VREL_NONE) + return r; + } + return VREL_NONE; + +} + +// Query if there is a relation between SSA1 and SS2 in block BB or a +// dominator of BB + +relation_kind +relation_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2) +{ + relation_kind kind; + unsigned v1 = SSA_NAME_VERSION (ssa1); + unsigned v2 = SSA_NAME_VERSION (ssa2); + if (v1 == v2) + return EQ_EXPR; + + // Check for equivalence first. + const_bitmap equiv1 = equiv_set (ssa1, bb); + if (equiv1 && bitmap_bit_p (equiv1, v2)) + return EQ_EXPR; + + // Initially look for a direct relationship and just return that. + kind = find_relation_dom (bb, v1, v2); + if (kind != VREL_NONE) + return kind; + + // If one is not found, see if there is a relationship between equivalences. + // If v2 isn't in v1s equiv set, then v1 shouldn't be in v2's set either. + const_bitmap equiv2 = equiv_set (ssa2, bb); + gcc_checking_assert (!equiv2 || !bitmap_bit_p (equiv2, v1)); + + if (!equiv1 && !equiv2) + kind = VREL_NONE; + else if (!equiv1) + { + bitmap_clear (m_tmp); + bitmap_set_bit (m_tmp, v1); + kind = find_relation_dom (bb, m_tmp, equiv2); + } + else if (!equiv2) + { + bitmap_clear (m_tmp); + bitmap_set_bit (m_tmp, v2); + kind = find_relation_dom (bb, equiv1, m_tmp); + } + else + kind = find_relation_dom (bb, equiv1, equiv2); + return kind; +} + +// Dump all the relations in block BB to file F. + +void +relation_oracle::dump (FILE *f, basic_block bb) const +{ + equiv_oracle::dump (f,bb); + + if (bb->index >= (int)m_relations.length ()) + return; + if (!m_relations[bb->index].m_names) + return; + + relation_chain *ptr = m_relations[bb->index].m_head; + for (; ptr; ptr = ptr->m_next) + { + fprintf (f, "Relational : "); + ptr->dump (f); + fprintf (f, "\n"); + } +} + +// Dump all the relations known to file F. + +void +relation_oracle::dump (FILE *f) const +{ + fprintf (f, "Relation dump\n"); + for (unsigned i = 0; i < m_relations.length (); i++) + { + fprintf (f, "BB%d\n", i); + dump (f, BASIC_BLOCK_FOR_FN (cfun, i)); + } +} diff --git a/gcc/value-relation.h b/gcc/value-relation.h new file mode 100644 index 00000000000..11488541277 --- /dev/null +++ b/gcc/value-relation.h @@ -0,0 +1,159 @@ +/* Header file for the value range relational processing. + Copyright (C) 2020-2021 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_VALUE_RELATION_H +#define GCC_VALUE_RELATION_H + + +// This file provides access to a relation oracle which can be used to +// maintain and query relations and equivalences between SSA_NAMES. +// +// The general range_query object provided in value-query.h provides +// access to an oracle, if one is available, via the oracle() method. +// Thre are also a couple of access routines provided, which even if there is +// no oracle, will return the default VREL_NONE no relation. +// +// Typically, when a ranger object is active, there will be an oracle, and +// any information available can be directly queried. Ranger also sets and +// utilizes the relation information to enhance it's range calculations, this +// is totally transparent to the client, and they are free to make queries. +// +// +// relation_kind is a typedef of enum tree_code, but has restricted range +// and a couple of extra values. +// +// A query is made requesting the relation between SSA1 and SSA@ in a basic +// block, or on an edge, the possible return values are: +// +// EQ_EXPR, NE_EXPR, LT_EXPR, LE_EXPR, GT_EXPR, and GE_EXPR mean the same. +// VREL_NONE : No relation between the 2 names. +// VREL_EMPTY : Impossible relation (ie, A < B && A > B produces VREL_EMPTY. +// +// The oracle maintains EQ_EXPR relations with equivalency sets, so if a +// relation comes back EQ_EXPR, it is also possible to query the set of +// equivlaencies. These are basically bitmaps over ssa_names. +// +// relations are maintained via the dominace trees, are are optimized assuming +// they are registered in dominance order. When a new relation is added, it +// is intersected with whatever existing relation exists in the dominance tree +// and registered at the specified block. + + +// Rather than introduce a new enumerated type for relations, we can use the +// existing tree_codes for relations, plus add a couple of #defines for +// the other cases. These codes are arranged such that VREL_NONE is the first +// code, and all the rest are contiguous. + +typedef enum tree_code relation_kind; + +#define VREL_NONE TRUTH_NOT_EXPR +#define VREL_EMPTY LTGT_EXPR + +// General relation kind transformations. +relation_kind relation_union (relation_kind r1, relation_kind r2); +relation_kind relation_intersect (relation_kind r1, relation_kind r2); +relation_kind relation_negate (relation_kind r); +relation_kind relation_swap (relation_kind r); +void print_relation (FILE *f, relation_kind rel); + +// Declared internally in value-relation.cc +class equiv_chain; + +// The equivalency oracle maintains equivalencies using the dominator tree. +// Equivalencies apply to an entire basic block. Equivalencies on edges +// can be represented only on edges whose destination is a single-pred block, +// and the equivalence is simply applied to that succesor block. + +class equiv_oracle +{ +public: + equiv_oracle (); + ~equiv_oracle (); + + const_bitmap equiv_set (tree ssa, basic_block bb) const; + void register_equiv (basic_block bb, tree ssa1, tree ssa2); + + void dump (FILE *f, basic_block bb) const; + void dump (FILE *f) const; + +protected: + bitmap_obstack m_bitmaps; + struct obstack m_chain_obstack; +private: + bitmap m_equiv_set; // Index by ssa-name. true if an equivalence exists. + vec m_equiv; // Index by BB. list of equivalences. + + void limit_check (basic_block bb = NULL); + equiv_chain *find_equiv_block (unsigned ssa, int bb) const; + equiv_chain *find_equiv_dom (tree name, basic_block bb) const; + + bitmap register_equiv (basic_block bb, unsigned v, equiv_chain *equiv_1); + bitmap register_equiv (basic_block bb, equiv_chain *equiv_1, + equiv_chain *equiv_2); + +}; + +// Summary block header for relations. + +class relation_chain_head +{ +public: + bitmap m_names; // ssa_names with relations in this block. + class relation_chain *m_head; // List of relations in block. +}; + +// A relation oracle maintains a set of relations between ssa_names using the +// dominator tree structures. Equivalencies are considered a subset of +// a general relation and maintained by an equivalence oracle by transparently +// passing any EQ_EXPR relations to it. +// Relations are handled at the basic block level. All relations apply to +// an entire block, and are thus kept in a summary index by block. +// Similar to the equivalence oracle, edges are handled by applying the +// relation to the destination block of the edge, but ONLY if that block +// has a single successor. For now. + +class relation_oracle : public equiv_oracle +{ +public: + relation_oracle (); + ~relation_oracle (); + + void register_relation (gimple *stmt, relation_kind k, tree op1, tree op2); + void register_relation (edge e, relation_kind k, tree op1, tree op2); + + relation_kind query_relation (basic_block bb, tree ssa1, tree ssa2); + + void dump (FILE *f, basic_block bb) const; + void dump (FILE *f) const; +private: + bitmap m_tmp; + bitmap m_relation_set; // Index by ssa-name. True if a relation exists + vec m_relations; // Index by BB, list of relations. + relation_kind find_relation_block (unsigned bb, const_bitmap b1, + const_bitmap b2); + relation_kind find_relation_dom (basic_block bb, const_bitmap b1, + const_bitmap b2); + relation_kind find_relation_block (int bb, unsigned v1, unsigned v2, + relation_chain **obj = NULL); + relation_kind find_relation_dom (basic_block bb, unsigned v1, unsigned v2); + void register_relation (basic_block bb, relation_kind k, tree op1, tree op2); +}; + +#endif /* GCC_VALUE_RELATION_H */ -- 2.17.2 From patchwork Tue Jun 22 13:17:57 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1495678 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=ZiH7A0hy; 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 4G8Rnw0bwWz9sS8 for ; Tue, 22 Jun 2021 23:19:48 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id D75E73891C1B for ; Tue, 22 Jun 2021 13:19:44 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org D75E73891C1B DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1624367984; bh=e9hqhgeEewldJbGXTNR6PzRk8RHw+jYrD/r22atqUcA=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=ZiH7A0hyt+l7SMiPgI12aCJBkCBvO4WF9PTJDXmmEgnS5q2lNYhNsuI980WGo9hZo iME8OuMhNRYueCc7gQ+i/Hx01ketMbAkAWVIVhAllSYS7RjWrIRk3KsZvre9xlGY2G QZRveZ9OMR6nNAH6omgpN3UJM0xXFkhYNf5OCbLE= 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 368333892473 for ; Tue, 22 Jun 2021 13:18:03 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 368333892473 Received: from mail-qk1-f198.google.com (mail-qk1-f198.google.com [209.85.222.198]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-504-VQIVfh1vN_aWpM3pDEoRhg-1; Tue, 22 Jun 2021 09:18:01 -0400 X-MC-Unique: VQIVfh1vN_aWpM3pDEoRhg-1 Received: by mail-qk1-f198.google.com with SMTP id c3-20020a37b3030000b02903ad0001a2e8so17939533qkf.3 for ; Tue, 22 Jun 2021 06:18:00 -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=e9hqhgeEewldJbGXTNR6PzRk8RHw+jYrD/r22atqUcA=; b=S69keJSsLZwyjLb60/Yc/nKsR0Z9V1F0UxPKKVmBhqPd1T4JpS+kCjSG6qjTH28ICg 16KwMsLeJ1Lmzsh5SE2+ZR1Qazv1KB0vgnHmiTJdfmqHDR92JMqFUV6pIIadRJjqn93n u63xBUBPhybIbQZ6TyGSLFmSYuWVKRMuLTsp7gTVRJJTR8g0ERCRiE7cbsOoaMU9YAcD QStnPFijAdseKwqh1c4SV91tUS96rAtTX+kAXYPBPuh6dzl8HjSf4pXMYwvYfd9a9x0+ cpkghJxQPXDCGm2rIn3Mdc40ZubGJt0mE1aXCRaAl+6RdbKtSZS8h8oeJhCQq/DFrLE/ LqYw== X-Gm-Message-State: AOAM53230mcCc4FGzI32SJufqHwhB2HMExaDrzfmzWXaAkyraVVrHA4V Tsdqa0Iekc87SrmFNwBL5of2eA9BC4GEv1x4JCAaTDRMvC5gxqqJCvunq+Kb2jtGCZB5ofajyES c2aYMcbRJbKXrlyPqmA== X-Received: by 2002:a37:cc1:: with SMTP id 184mr4302008qkm.218.1624367880627; Tue, 22 Jun 2021 06:18:00 -0700 (PDT) X-Google-Smtp-Source: ABdhPJwosZGZAv6tGvueymBRFs7cnn8OuNlb2L2M4v2NkPS/JmzYncsjr3mELdCcH1uD9OZwh1evZA== X-Received: by 2002:a37:cc1:: with SMTP id 184mr4301989qkm.218.1624367880459; Tue, 22 Jun 2021 06:18:00 -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 m3sm10244733qkk.27.2021.06.22.06.17.58 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 22 Jun 2021 06:17:59 -0700 (PDT) To: gcc-patches Subject: [COMMITTED 2/7] Add relational support to range-op. Message-ID: <9cdb3a62-6be5-4d71-651f-bcd19a3ab454@redhat.com> Date: Tue, 22 Jun 2021 09:17:57 -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.5 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, 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-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 adds relation support to range-ops. a relation_kind is added to all fold and op1/2_range operations, which will allow any known relation to be applied during calculations. 4 more routines are provided which enable range-ops to indicate when a relation is caused by an expression/result and what effects it may have.    All relations are driven from these routines. virtual enum tree_code lhs_op1_relation (const irange &lhs, const irange &op1, const irange &op2) const; virtual enum tree_code lhs_op2_relation (const irange &lhs, const irange &op1, const irange &op2) const; virtual enum tree_code op1_op2_relation (const irange &lhs) const; virtual bool op1_op2_relation_effect (irange &lhs_range, tree type, const irange &op1_range, const irange &op2_range, relation_kind rel) const; This initial patch provides the basic of the relation opcodes. Ie,  operator_equal has added enum tree_code operator_equal::op1_op2_relation (const irange &lhs) const {   if (lhs.undefined_p ())     return VREL_EMPTY;   // FALSE = op1 == op2 indicates NE_EXPR.   if (lhs.zero_p ())     return NE_EXPR;   // TRUE = op1 == op2 indicates EQ_EXPR.   if (!lhs.contains_p (build_zero_cst (lhs.type ())))     return EQ_EXPR;   return VREL_NONE; } This teaches range-ops that there is a relation between op1 and op2 is the LHS has a range of FALSE, or TRUE.  Otherwise, we don't know what the relation is. All 6 basic relations are implemented, as well as folding of these opcodes when a relation is to be applied.  Ie, how to fold it ( if a_2 == b_2 is being folded., and the known relation coming into this expression is a_2 > b_2, it will fold to [0,0] or false. Again, this patch on its own will not cause anything to actually happen, that will be enabled in the next patch. Virtually all relation generation and application is handled via these range-ops routines.  Bootstraps on x86_64-pc-linux-gnu with no regressions.  Pushed. Andrew From 80dd13f5c3bdc7899ee6e863e05b254815ec0cef Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Thu, 17 Jun 2021 11:49:21 -0400 Subject: [PATCH 2/7] Add relational support to range-op. This patch integrates relations with range-op functionality so that any known relations can be used to help reduce or resolve ranges. Initially handle EQ_EXPR, NE_EXPR, LE_EXPR, LT_EXPR, GT_EXPR and GE_EXPR. * range-op.cc (range_operator::wi_fold): Apply relation effect. (range_operator::fold_range): Adjust and apply relation effect. (*::fold_range): Add relation parameters. (*::op1_range): Ditto. (*::op2_range): Ditto. (range_operator::lhs_op1_relation): New. (range_operator::lhs_op2_relation): New. (range_operator::op1_op2_relation): New. (range_operator::op1_op2_relation_effect): New. (relop_early_resolve): New. (operator_equal::op1_op2_relation): New. (operator_equal::fold_range): Call relop_early_resolve. (operator_not_equal::op1_op2_relation): New. (operator_not_equal::fold_range): Call relop_early_resolve. (operator_lt::op1_op2_relation): New. (operator_lt::fold_range): Call relop_early_resolve. (operator_le::op1_op2_relation): New. (operator_le::fold_range): Call relop_early_resolve. (operator_gt::op1_op2_relation): New. (operator_gt::fold_range): Call relop_early_resolve. (operator_ge::op1_op2_relation): New. (operator_ge::fold_range): Call relop_early_resolve. * range-op.h (class range_operator): Adjust parameters and methods. --- gcc/range-op.cc | 584 +++++++++++++++++++++++++++++++++++++----------- gcc/range-op.h | 24 +- 2 files changed, 469 insertions(+), 139 deletions(-) diff --git a/gcc/range-op.cc b/gcc/range-op.cc index e805f26a333..d807693900a 100644 --- a/gcc/range-op.cc +++ b/gcc/range-op.cc @@ -44,6 +44,7 @@ along with GCC; see the file COPYING3. If not see #include "gimple-walk.h" #include "tree-cfg.h" #include "wide-int.h" +#include "value-relation.h" #include "range-op.h" // Return the upper limit for a type. @@ -138,7 +139,8 @@ range_operator::wi_fold (irange &r, tree type, bool range_operator::fold_range (irange &r, tree type, const irange &lh, - const irange &rh) const + const irange &rh, + relation_kind rel) const { gcc_checking_assert (irange::supports_type_p (type)); if (empty_range_varying (r, type, lh, rh)) @@ -152,6 +154,7 @@ range_operator::fold_range (irange &r, tree type, { wi_fold (r, type, lh.lower_bound (0), lh.upper_bound (0), rh.lower_bound (0), rh.upper_bound (0)); + op1_op2_relation_effect (r, type, lh, rh, rel); return true; } @@ -167,8 +170,12 @@ range_operator::fold_range (irange &r, tree type, wi_fold (tmp, type, lh_lb, lh_ub, rh_lb, rh_ub); r.union_ (tmp); if (r.varying_p ()) - return true; + { + op1_op2_relation_effect (r, type, lh, rh, rel); + return true; + } } + op1_op2_relation_effect (r, type, lh, rh, rel); return true; } @@ -178,7 +185,8 @@ bool range_operator::op1_range (irange &r ATTRIBUTE_UNUSED, tree type ATTRIBUTE_UNUSED, const irange &lhs ATTRIBUTE_UNUSED, - const irange &op2 ATTRIBUTE_UNUSED) const + const irange &op2 ATTRIBUTE_UNUSED, + relation_kind rel ATTRIBUTE_UNUSED) const { return false; } @@ -189,11 +197,47 @@ bool range_operator::op2_range (irange &r ATTRIBUTE_UNUSED, tree type ATTRIBUTE_UNUSED, const irange &lhs ATTRIBUTE_UNUSED, - const irange &op1 ATTRIBUTE_UNUSED) const + const irange &op1 ATTRIBUTE_UNUSED, + relation_kind rel ATTRIBUTE_UNUSED) const { return false; } +// The default relation routines return VREL_NONE. + +enum tree_code +range_operator::lhs_op1_relation (const irange &lhs ATTRIBUTE_UNUSED, + const irange &op1 ATTRIBUTE_UNUSED, + const irange &op2 ATTRIBUTE_UNUSED) const +{ + return VREL_NONE; +} + +enum tree_code +range_operator::lhs_op2_relation (const irange &lhs ATTRIBUTE_UNUSED, + const irange &op1 ATTRIBUTE_UNUSED, + const irange &op2 ATTRIBUTE_UNUSED) const +{ + return VREL_NONE; +} + +enum tree_code +range_operator::op1_op2_relation (const irange &lhs ATTRIBUTE_UNUSED) const +{ + return VREL_NONE; +} + +// Default is no relation affects the LHS. + +bool +range_operator::op1_op2_relation_effect (irange &lhs_range ATTRIBUTE_UNUSED, + tree type ATTRIBUTE_UNUSED, + const irange &op1_range ATTRIBUTE_UNUSED, + const irange &op2_range ATTRIBUTE_UNUSED, + relation_kind rel ATTRIBUTE_UNUSED) const +{ + return false; +} // Create and return a range from a pair of wide-ints that are known // to have overflowed (or underflowed). @@ -385,27 +429,82 @@ get_bool_state (irange &r, const irange &lhs, tree val_type) return BRS_TRUE; } +// For relation opcodes, first try to see if the supplied relation +// forces a true or false result, and return that. +// Then check for undefined operands. If none of this applies, +// return false. + +static inline bool +relop_early_resolve (irange &r, tree type, const irange &op1, + const irange &op2, relation_kind rel, + relation_kind my_rel) +{ + // If known relation is a complete subset of this relation, always true. + if (relation_union (rel, my_rel) == my_rel) + { + r = range_true (type); + return true; + } + + // If known relation has no subset of this relation, always false. + if (relation_intersect (rel, my_rel) == VREL_EMPTY) + { + r = range_false (type); + return true; + } + + // If either operand is undefined, return VARYING. + if (empty_range_varying (r, type, op1, op2)) + return true; + + return false; +} + class operator_equal : public range_operator { public: virtual bool fold_range (irange &r, tree type, const irange &op1, - const irange &op2) const; + const irange &op2, + relation_kind rel = VREL_NONE) const; virtual bool op1_range (irange &r, tree type, const irange &lhs, - const irange &val) const; + const irange &val, + relation_kind rel = VREL_NONE) const; virtual bool op2_range (irange &r, tree type, const irange &lhs, - const irange &val) const; + const irange &val, + relation_kind rel = VREL_NONE) const; + virtual enum tree_code op1_op2_relation (const irange &lhs) const; } op_equal; +// Check if the LHS range indicates a relation between OP1 and OP2. + +enum tree_code +operator_equal::op1_op2_relation (const irange &lhs) const +{ + if (lhs.undefined_p ()) + return VREL_EMPTY; + + // FALSE = op1 == op2 indicates NE_EXPR. + if (lhs.zero_p ()) + return NE_EXPR; + + // TRUE = op1 == op2 indicates EQ_EXPR. + if (!lhs.contains_p (build_zero_cst (lhs.type ()))) + return EQ_EXPR; + return VREL_NONE; +} + + bool operator_equal::fold_range (irange &r, tree type, const irange &op1, - const irange &op2) const + const irange &op2, + relation_kind rel) const { - if (empty_range_varying (r, type, op1, op2)) + if (relop_early_resolve (r, type, op1, op2, rel, EQ_EXPR)) return true; // We can be sure the values are always equal or not if both ranges @@ -435,7 +534,8 @@ operator_equal::fold_range (irange &r, tree type, bool operator_equal::op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const + const irange &op2, + relation_kind rel ATTRIBUTE_UNUSED) const { switch (get_bool_state (r, lhs, type)) { @@ -465,32 +565,55 @@ operator_equal::op1_range (irange &r, tree type, bool operator_equal::op2_range (irange &r, tree type, const irange &lhs, - const irange &op1) const + const irange &op1, + relation_kind rel) const { - return operator_equal::op1_range (r, type, lhs, op1); + return operator_equal::op1_range (r, type, lhs, op1, rel); } - class operator_not_equal : public range_operator { public: virtual bool fold_range (irange &r, tree type, const irange &op1, - const irange &op2) const; + const irange &op2, + relation_kind rel = VREL_NONE) const; virtual bool op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const; + const irange &op2, + relation_kind rel = VREL_NONE) const; virtual bool op2_range (irange &r, tree type, const irange &lhs, - const irange &op1) const; + const irange &op1, + relation_kind rel = VREL_NONE) const; + virtual enum tree_code op1_op2_relation (const irange &lhs) const; } op_not_equal; +// Check if the LHS range indicates a relation between OP1 and OP2. + +enum tree_code +operator_not_equal::op1_op2_relation (const irange &lhs) const +{ + if (lhs.undefined_p ()) + return VREL_EMPTY; + + // FALSE = op1 != op2 indicates EQ_EXPR. + if (lhs.zero_p ()) + return EQ_EXPR; + + // TRUE = op1 != op2 indicates NE_EXPR. + if (!lhs.contains_p (build_zero_cst (lhs.type ()))) + return NE_EXPR; + return VREL_NONE; +} + bool operator_not_equal::fold_range (irange &r, tree type, const irange &op1, - const irange &op2) const + const irange &op2, + relation_kind rel) const { - if (empty_range_varying (r, type, op1, op2)) + if (relop_early_resolve (r, type, op1, op2, rel, NE_EXPR)) return true; // We can be sure the values are always equal or not if both ranges @@ -520,7 +643,8 @@ operator_not_equal::fold_range (irange &r, tree type, bool operator_not_equal::op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const + const irange &op2, + relation_kind rel ATTRIBUTE_UNUSED) const { switch (get_bool_state (r, lhs, type)) { @@ -551,9 +675,10 @@ operator_not_equal::op1_range (irange &r, tree type, bool operator_not_equal::op2_range (irange &r, tree type, const irange &lhs, - const irange &op1) const + const irange &op1, + relation_kind rel) const { - return operator_not_equal::op1_range (r, type, lhs, op1); + return operator_not_equal::op1_range (r, type, lhs, op1, rel); } // (X < VAL) produces the range of [MIN, VAL - 1]. @@ -607,21 +732,44 @@ class operator_lt : public range_operator public: virtual bool fold_range (irange &r, tree type, const irange &op1, - const irange &op2) const; + const irange &op2, + relation_kind rel = VREL_NONE) const; virtual bool op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const; + const irange &op2, + relation_kind rel = VREL_NONE) const; virtual bool op2_range (irange &r, tree type, const irange &lhs, - const irange &op1) const; + const irange &op1, + relation_kind rel = VREL_NONE) const; + virtual enum tree_code op1_op2_relation (const irange &lhs) const; } op_lt; +// Check if the LHS range indicates a relation between OP1 and OP2. + +enum tree_code +operator_lt::op1_op2_relation (const irange &lhs) const +{ + if (lhs.undefined_p ()) + return VREL_EMPTY; + + // FALSE = op1 < op2 indicates GE_EXPR. + if (lhs.zero_p ()) + return GE_EXPR; + + // TRUE = op1 < op2 indicates LT_EXPR. + if (!lhs.contains_p (build_zero_cst (lhs.type ()))) + return LT_EXPR; + return VREL_NONE; +} + bool operator_lt::fold_range (irange &r, tree type, const irange &op1, - const irange &op2) const + const irange &op2, + relation_kind rel) const { - if (empty_range_varying (r, type, op1, op2)) + if (relop_early_resolve (r, type, op1, op2, rel, LT_EXPR)) return true; signop sign = TYPE_SIGN (op1.type ()); @@ -639,7 +787,8 @@ operator_lt::fold_range (irange &r, tree type, bool operator_lt::op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const + const irange &op2, + relation_kind rel ATTRIBUTE_UNUSED) const { switch (get_bool_state (r, lhs, type)) { @@ -660,7 +809,8 @@ operator_lt::op1_range (irange &r, tree type, bool operator_lt::op2_range (irange &r, tree type, const irange &lhs, - const irange &op1) const + const irange &op1, + relation_kind rel ATTRIBUTE_UNUSED) const { switch (get_bool_state (r, lhs, type)) { @@ -684,21 +834,44 @@ class operator_le : public range_operator public: virtual bool fold_range (irange &r, tree type, const irange &op1, - const irange &op2) const; + const irange &op2, + relation_kind rel = VREL_NONE) const; virtual bool op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const; + const irange &op2, + relation_kind rel = VREL_NONE) const; virtual bool op2_range (irange &r, tree type, const irange &lhs, - const irange &op1) const; + const irange &op1, + relation_kind rel = VREL_NONE) const; + virtual enum tree_code op1_op2_relation (const irange &lhs) const; } op_le; +// Check if the LHS range indicates a relation between OP1 and OP2. + +enum tree_code +operator_le::op1_op2_relation (const irange &lhs) const +{ + if (lhs.undefined_p ()) + return VREL_EMPTY; + + // FALSE = op1 <= op2 indicates GT_EXPR. + if (lhs.zero_p ()) + return GT_EXPR; + + // TRUE = op1 <= op2 indicates LE_EXPR. + if (!lhs.contains_p (build_zero_cst (lhs.type ()))) + return LE_EXPR; + return VREL_NONE; +} + bool operator_le::fold_range (irange &r, tree type, const irange &op1, - const irange &op2) const + const irange &op2, + relation_kind rel) const { - if (empty_range_varying (r, type, op1, op2)) + if (relop_early_resolve (r, type, op1, op2, rel, LE_EXPR)) return true; signop sign = TYPE_SIGN (op1.type ()); @@ -716,7 +889,8 @@ operator_le::fold_range (irange &r, tree type, bool operator_le::op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const + const irange &op2, + relation_kind rel ATTRIBUTE_UNUSED) const { switch (get_bool_state (r, lhs, type)) { @@ -737,7 +911,8 @@ operator_le::op1_range (irange &r, tree type, bool operator_le::op2_range (irange &r, tree type, const irange &lhs, - const irange &op1) const + const irange &op1, + relation_kind rel ATTRIBUTE_UNUSED) const { switch (get_bool_state (r, lhs, type)) { @@ -761,20 +936,44 @@ class operator_gt : public range_operator public: virtual bool fold_range (irange &r, tree type, const irange &op1, - const irange &op2) const; + const irange &op2, + relation_kind rel = VREL_NONE) const; virtual bool op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const; + const irange &op2, + relation_kind rel = VREL_NONE) const; virtual bool op2_range (irange &r, tree type, const irange &lhs, - const irange &op1) const; + const irange &op1, + relation_kind rel = VREL_NONE) const; + virtual enum tree_code op1_op2_relation (const irange &lhs) const; } op_gt; +// Check if the LHS range indicates a relation between OP1 and OP2. + +enum tree_code +operator_gt::op1_op2_relation (const irange &lhs) const +{ + if (lhs.undefined_p ()) + return VREL_EMPTY; + + // FALSE = op1 > op2 indicates LE_EXPR. + if (lhs.zero_p ()) + return LE_EXPR; + + // TRUE = op1 > op2 indicates GT_EXPR. + if (!lhs.contains_p (build_zero_cst (lhs.type ()))) + return GT_EXPR; + return VREL_NONE; +} + + bool operator_gt::fold_range (irange &r, tree type, - const irange &op1, const irange &op2) const + const irange &op1, const irange &op2, + relation_kind rel) const { - if (empty_range_varying (r, type, op1, op2)) + if (relop_early_resolve (r, type, op1, op2, rel, GT_EXPR)) return true; signop sign = TYPE_SIGN (op1.type ()); @@ -791,7 +990,8 @@ operator_gt::fold_range (irange &r, tree type, bool operator_gt::op1_range (irange &r, tree type, - const irange &lhs, const irange &op2) const + const irange &lhs, const irange &op2, + relation_kind rel ATTRIBUTE_UNUSED) const { switch (get_bool_state (r, lhs, type)) { @@ -812,7 +1012,8 @@ operator_gt::op1_range (irange &r, tree type, bool operator_gt::op2_range (irange &r, tree type, const irange &lhs, - const irange &op1) const + const irange &op1, + relation_kind rel ATTRIBUTE_UNUSED) const { switch (get_bool_state (r, lhs, type)) { @@ -836,21 +1037,44 @@ class operator_ge : public range_operator public: virtual bool fold_range (irange &r, tree type, const irange &op1, - const irange &op2) const; + const irange &op2, + relation_kind rel = VREL_NONE) const; virtual bool op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const; + const irange &op2, + relation_kind rel = VREL_NONE) const; virtual bool op2_range (irange &r, tree type, const irange &lhs, - const irange &op1) const; + const irange &op1, + relation_kind rel = VREL_NONE) const; + virtual enum tree_code op1_op2_relation (const irange &lhs) const; } op_ge; +// Check if the LHS range indicates a relation between OP1 and OP2. + +enum tree_code +operator_ge::op1_op2_relation (const irange &lhs) const +{ + if (lhs.undefined_p ()) + return VREL_EMPTY; + + // FALSE = op1 >= op2 indicates LT_EXPR. + if (lhs.zero_p ()) + return LT_EXPR; + + // TRUE = op1 >= op2 indicates GE_EXPR. + if (!lhs.contains_p (build_zero_cst (lhs.type ()))) + return GE_EXPR; + return VREL_NONE; +} + bool operator_ge::fold_range (irange &r, tree type, const irange &op1, - const irange &op2) const + const irange &op2, + relation_kind rel) const { - if (empty_range_varying (r, type, op1, op2)) + if (relop_early_resolve (r, type, op1, op2, rel, GE_EXPR)) return true; signop sign = TYPE_SIGN (op1.type ()); @@ -868,7 +1092,8 @@ operator_ge::fold_range (irange &r, tree type, bool operator_ge::op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const + const irange &op2, + relation_kind rel ATTRIBUTE_UNUSED) const { switch (get_bool_state (r, lhs, type)) { @@ -889,7 +1114,8 @@ operator_ge::op1_range (irange &r, tree type, bool operator_ge::op2_range (irange &r, tree type, const irange &lhs, - const irange &op1) const + const irange &op1, + relation_kind rel ATTRIBUTE_UNUSED) const { switch (get_bool_state (r, lhs, type)) { @@ -913,10 +1139,12 @@ class operator_plus : public range_operator public: virtual bool op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const; + const irange &op2, + relation_kind rel ATTRIBUTE_UNUSED) const; virtual bool op2_range (irange &r, tree type, const irange &lhs, - const irange &op1) const; + const irange &op1, + relation_kind rel ATTRIBUTE_UNUSED) const; virtual void wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, @@ -939,7 +1167,8 @@ operator_plus::wi_fold (irange &r, tree type, bool operator_plus::op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const + const irange &op2, + relation_kind rel ATTRIBUTE_UNUSED) const { return range_op_handler (MINUS_EXPR, type)->fold_range (r, type, lhs, op2); } @@ -947,7 +1176,8 @@ operator_plus::op1_range (irange &r, tree type, bool operator_plus::op2_range (irange &r, tree type, const irange &lhs, - const irange &op1) const + const irange &op1, + relation_kind rel ATTRIBUTE_UNUSED) const { return range_op_handler (MINUS_EXPR, type)->fold_range (r, type, lhs, op1); } @@ -958,10 +1188,12 @@ class operator_minus : public range_operator public: virtual bool op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const; + const irange &op2, + relation_kind rel ATTRIBUTE_UNUSED) const; virtual bool op2_range (irange &r, tree type, const irange &lhs, - const irange &op1) const; + const irange &op1, + relation_kind rel ATTRIBUTE_UNUSED) const; virtual void wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, @@ -984,7 +1216,8 @@ operator_minus::wi_fold (irange &r, tree type, bool operator_minus::op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const + const irange &op2, + relation_kind rel ATTRIBUTE_UNUSED) const { return range_op_handler (PLUS_EXPR, type)->fold_range (r, type, lhs, op2); } @@ -992,7 +1225,8 @@ operator_minus::op1_range (irange &r, tree type, bool operator_minus::op2_range (irange &r, tree type, const irange &lhs, - const irange &op1) const + const irange &op1, + relation_kind rel ATTRIBUTE_UNUSED) const { return fold_range (r, type, op1, lhs); } @@ -1127,15 +1361,18 @@ public: const wide_int &w0, const wide_int &w1) const; virtual bool op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const; + const irange &op2, + relation_kind rel ATTRIBUTE_UNUSED) const; virtual bool op2_range (irange &r, tree type, const irange &lhs, - const irange &op1) const; + const irange &op1, + relation_kind rel ATTRIBUTE_UNUSED) const; } op_mult; bool operator_mult::op1_range (irange &r, tree type, - const irange &lhs, const irange &op2) const + const irange &lhs, const irange &op2, + relation_kind rel ATTRIBUTE_UNUSED) const { tree offset; @@ -1153,9 +1390,10 @@ operator_mult::op1_range (irange &r, tree type, bool operator_mult::op2_range (irange &r, tree type, - const irange &lhs, const irange &op1) const + const irange &lhs, const irange &op1, + relation_kind rel) const { - return operator_mult::op1_range (r, type, lhs, op1); + return operator_mult::op1_range (r, type, lhs, op1, rel); } bool @@ -1391,14 +1629,16 @@ public: operator_exact_divide () : operator_div (TRUNC_DIV_EXPR) { } virtual bool op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const; + const irange &op2, + relation_kind rel ATTRIBUTE_UNUSED) const; } op_exact_div; bool operator_exact_divide::op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const + const irange &op2, + relation_kind rel ATTRIBUTE_UNUSED) const { tree offset; // [2, 4] = op1 / [3,3] since its exact divide, no need to worry about @@ -1419,10 +1659,12 @@ class operator_lshift : public cross_product_operator public: virtual bool op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const; + const irange &op2, + relation_kind rel = VREL_NONE) const; virtual bool fold_range (irange &r, tree type, const irange &op1, - const irange &op2) const; + const irange &op2, + relation_kind rel = VREL_NONE) const; virtual void wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, @@ -1438,7 +1680,8 @@ class operator_rshift : public cross_product_operator public: virtual bool fold_range (irange &r, tree type, const irange &op1, - const irange &op2) const; + const irange &op2, + relation_kind rel = VREL_NONE) const; virtual void wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, @@ -1450,14 +1693,16 @@ public: const wide_int &w1) const; virtual bool op1_range (irange &, tree type, const irange &lhs, - const irange &op2) const; + const irange &op2, + relation_kind rel = VREL_NONE) const; } op_rshift; bool operator_lshift::fold_range (irange &r, tree type, const irange &op1, - const irange &op2) const + const irange &op2, + relation_kind rel ATTRIBUTE_UNUSED) const { int_range_max shift_range; if (!get_shift_range (shift_range, type, op2)) @@ -1572,7 +1817,8 @@ bool operator_lshift::op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const + const irange &op2, + relation_kind rel ATTRIBUTE_UNUSED) const { tree shift_amount; if (op2.singleton_p (&shift_amount)) @@ -1632,7 +1878,8 @@ bool operator_rshift::op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const + const irange &op2, + relation_kind rel ATTRIBUTE_UNUSED) const { tree shift; if (op2.singleton_p (&shift)) @@ -1708,7 +1955,8 @@ operator_rshift::wi_op_overflows (wide_int &res, bool operator_rshift::fold_range (irange &r, tree type, const irange &op1, - const irange &op2) const + const irange &op2, + relation_kind rel ATTRIBUTE_UNUSED) const { int_range_max shift; if (!get_shift_range (shift, type, op2)) @@ -1737,10 +1985,12 @@ class operator_cast: public range_operator public: virtual bool fold_range (irange &r, tree type, const irange &op1, - const irange &op2) const; + const irange &op2, + relation_kind rel = VREL_NONE) const; virtual bool op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const; + const irange &op2, + relation_kind rel = VREL_NONE) const; private: bool truncating_cast_p (const irange &inner, const irange &outer) const; bool inside_domain_p (const wide_int &min, const wide_int &max, @@ -1818,7 +2068,8 @@ operator_cast::fold_pair (irange &r, unsigned index, bool operator_cast::fold_range (irange &r, tree type ATTRIBUTE_UNUSED, const irange &inner, - const irange &outer) const + const irange &outer, + relation_kind rel ATTRIBUTE_UNUSED) const { if (empty_range_varying (r, type, inner, outer)) return true; @@ -1844,7 +2095,8 @@ operator_cast::fold_range (irange &r, tree type ATTRIBUTE_UNUSED, bool operator_cast::op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const + const irange &op2, + relation_kind rel ATTRIBUTE_UNUSED) const { tree lhs_type = lhs.type (); gcc_checking_assert (types_compatible_p (op2.type(), type)); @@ -1954,20 +2206,24 @@ class operator_logical_and : public range_operator public: virtual bool fold_range (irange &r, tree type, const irange &lh, - const irange &rh) const; + const irange &rh, + relation_kind rel = VREL_NONE) const; virtual bool op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const; + const irange &op2, + relation_kind rel = VREL_NONE) const; virtual bool op2_range (irange &r, tree type, const irange &lhs, - const irange &op1) const; + const irange &op1, + relation_kind rel = VREL_NONE) const; } op_logical_and; bool operator_logical_and::fold_range (irange &r, tree type, const irange &lh, - const irange &rh) const + const irange &rh, + relation_kind rel ATTRIBUTE_UNUSED) const { if (empty_range_varying (r, type, lh, rh)) return true; @@ -1989,7 +2245,8 @@ operator_logical_and::fold_range (irange &r, tree type, bool operator_logical_and::op1_range (irange &r, tree type, const irange &lhs, - const irange &op2 ATTRIBUTE_UNUSED) const + const irange &op2 ATTRIBUTE_UNUSED, + relation_kind rel ATTRIBUTE_UNUSED) const { switch (get_bool_state (r, lhs, type)) { @@ -2010,7 +2267,8 @@ operator_logical_and::op1_range (irange &r, tree type, bool operator_logical_and::op2_range (irange &r, tree type, const irange &lhs, - const irange &op1) const + const irange &op1, + relation_kind rel ATTRIBUTE_UNUSED) const { return operator_logical_and::op1_range (r, type, lhs, op1); } @@ -2021,13 +2279,16 @@ class operator_bitwise_and : public range_operator public: virtual bool fold_range (irange &r, tree type, const irange &lh, - const irange &rh) const; + const irange &rh, + relation_kind rel = VREL_NONE) const; virtual bool op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const; + const irange &op2, + relation_kind rel = VREL_NONE) const; virtual bool op2_range (irange &r, tree type, const irange &lhs, - const irange &op1) const; + const irange &op1, + relation_kind rel = VREL_NONE) const; virtual void wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, @@ -2106,7 +2367,8 @@ operator_bitwise_and::remove_impossible_ranges (irange &r, bool operator_bitwise_and::fold_range (irange &r, tree type, const irange &lh, - const irange &rh) const + const irange &rh, + relation_kind rel ATTRIBUTE_UNUSED) const { if (range_operator::fold_range (r, type, lh, rh)) { @@ -2397,7 +2659,8 @@ operator_bitwise_and::simple_op1_range_solver (irange &r, tree type, bool operator_bitwise_and::op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const + const irange &op2, + relation_kind rel ATTRIBUTE_UNUSED) const { if (types_compatible_p (type, boolean_type_node)) return op_logical_and.op1_range (r, type, lhs, op2); @@ -2420,7 +2683,8 @@ operator_bitwise_and::op1_range (irange &r, tree type, bool operator_bitwise_and::op2_range (irange &r, tree type, const irange &lhs, - const irange &op1) const + const irange &op1, + relation_kind rel ATTRIBUTE_UNUSED) const { return operator_bitwise_and::op1_range (r, type, lhs, op1); } @@ -2431,19 +2695,23 @@ class operator_logical_or : public range_operator public: virtual bool fold_range (irange &r, tree type, const irange &lh, - const irange &rh) const; + const irange &rh, + relation_kind rel = VREL_NONE) const; virtual bool op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const; + const irange &op2, + relation_kind rel = VREL_NONE) const; virtual bool op2_range (irange &r, tree type, const irange &lhs, - const irange &op1) const; + const irange &op1, + relation_kind rel = VREL_NONE) const; } op_logical_or; bool operator_logical_or::fold_range (irange &r, tree type ATTRIBUTE_UNUSED, const irange &lh, - const irange &rh) const + const irange &rh, + relation_kind rel ATTRIBUTE_UNUSED) const { if (empty_range_varying (r, type, lh, rh)) return true; @@ -2456,7 +2724,8 @@ operator_logical_or::fold_range (irange &r, tree type ATTRIBUTE_UNUSED, bool operator_logical_or::op1_range (irange &r, tree type, const irange &lhs, - const irange &op2 ATTRIBUTE_UNUSED) const + const irange &op2 ATTRIBUTE_UNUSED, + relation_kind rel ATTRIBUTE_UNUSED) const { switch (get_bool_state (r, lhs, type)) { @@ -2477,7 +2746,8 @@ operator_logical_or::op1_range (irange &r, tree type, bool operator_logical_or::op2_range (irange &r, tree type, const irange &lhs, - const irange &op1) const + const irange &op1, + relation_kind rel ATTRIBUTE_UNUSED) const { return operator_logical_or::op1_range (r, type, lhs, op1); } @@ -2488,10 +2758,12 @@ class operator_bitwise_or : public range_operator public: virtual bool op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const; + const irange &op2, + relation_kind rel = VREL_NONE) const; virtual bool op2_range (irange &r, tree type, const irange &lhs, - const irange &op1) const; + const irange &op1, + relation_kind rel= VREL_NONE) const; virtual void wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, @@ -2553,7 +2825,8 @@ operator_bitwise_or::wi_fold (irange &r, tree type, bool operator_bitwise_or::op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const + const irange &op2, + relation_kind rel ATTRIBUTE_UNUSED) const { // If this is really a logical wi_fold, call that. if (types_compatible_p (type, boolean_type_node)) @@ -2572,7 +2845,8 @@ operator_bitwise_or::op1_range (irange &r, tree type, bool operator_bitwise_or::op2_range (irange &r, tree type, const irange &lhs, - const irange &op1) const + const irange &op1, + relation_kind rel ATTRIBUTE_UNUSED) const { return operator_bitwise_or::op1_range (r, type, lhs, op1); } @@ -2588,10 +2862,12 @@ public: const wide_int &rh_ub) const; virtual bool op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const; + const irange &op2, + relation_kind rel = VREL_NONE) const; virtual bool op2_range (irange &r, tree type, const irange &lhs, - const irange &op1) const; + const irange &op1, + relation_kind rel = VREL_NONE) const; } op_bitwise_xor; void @@ -2628,7 +2904,8 @@ operator_bitwise_xor::wi_fold (irange &r, tree type, bool operator_bitwise_xor::op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const + const irange &op2, + relation_kind rel ATTRIBUTE_UNUSED) const { if (lhs.undefined_p () || lhs.varying_p ()) { @@ -2662,7 +2939,8 @@ operator_bitwise_xor::op1_range (irange &r, tree type, bool operator_bitwise_xor::op2_range (irange &r, tree type, const irange &lhs, - const irange &op1) const + const irange &op1, + relation_kind rel ATTRIBUTE_UNUSED) const { return operator_bitwise_xor::op1_range (r, type, lhs, op1); } @@ -2677,10 +2955,12 @@ public: const wide_int &rh_ub) const; virtual bool op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const; + const irange &op2, + relation_kind rel ATTRIBUTE_UNUSED) const; virtual bool op2_range (irange &r, tree type, const irange &lhs, - const irange &op1) const; + const irange &op1, + relation_kind rel ATTRIBUTE_UNUSED) const; } op_trunc_mod; void @@ -2730,7 +3010,8 @@ operator_trunc_mod::wi_fold (irange &r, tree type, bool operator_trunc_mod::op1_range (irange &r, tree type, const irange &lhs, - const irange &) const + const irange &, + relation_kind rel ATTRIBUTE_UNUSED) const { // PR 91029. signop sign = TYPE_SIGN (type); @@ -2753,7 +3034,8 @@ operator_trunc_mod::op1_range (irange &r, tree type, bool operator_trunc_mod::op2_range (irange &r, tree type, const irange &lhs, - const irange &) const + const irange &, + relation_kind rel ATTRIBUTE_UNUSED) const { // PR 91029. signop sign = TYPE_SIGN (type); @@ -2792,10 +3074,12 @@ class operator_logical_not : public range_operator public: virtual bool fold_range (irange &r, tree type, const irange &lh, - const irange &rh) const; + const irange &rh, + relation_kind rel = VREL_NONE) const; virtual bool op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const; + const irange &op2, + relation_kind rel = VREL_NONE) const; } op_logical_not; // Folding a logical NOT, oddly enough, involves doing nothing on the @@ -2815,7 +3099,8 @@ public: bool operator_logical_not::fold_range (irange &r, tree type, const irange &lh, - const irange &rh ATTRIBUTE_UNUSED) const + const irange &rh ATTRIBUTE_UNUSED, + relation_kind rel ATTRIBUTE_UNUSED) const { if (empty_range_varying (r, type, lh, rh)) return true; @@ -2831,7 +3116,8 @@ bool operator_logical_not::op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const + const irange &op2, + relation_kind rel ATTRIBUTE_UNUSED) const { // Logical NOT is involutary...do it again. return fold_range (r, type, lhs, op2); @@ -2843,16 +3129,19 @@ class operator_bitwise_not : public range_operator public: virtual bool fold_range (irange &r, tree type, const irange &lh, - const irange &rh) const; + const irange &rh, + relation_kind rel = VREL_NONE) const; virtual bool op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const; + const irange &op2, + relation_kind rel = VREL_NONE) const; } op_bitwise_not; bool operator_bitwise_not::fold_range (irange &r, tree type, const irange &lh, - const irange &rh) const + const irange &rh, + relation_kind rel ATTRIBUTE_UNUSED) const { if (empty_range_varying (r, type, lh, rh)) return true; @@ -2870,7 +3159,8 @@ operator_bitwise_not::fold_range (irange &r, tree type, bool operator_bitwise_not::op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const + const irange &op2, + relation_kind rel ATTRIBUTE_UNUSED) const { if (types_compatible_p (type, boolean_type_node)) return op_logical_not.op1_range (r, type, lhs, op2); @@ -2885,13 +3175,15 @@ class operator_cst : public range_operator public: virtual bool fold_range (irange &r, tree type, const irange &op1, - const irange &op2) const; + const irange &op2, + relation_kind rel = VREL_NONE) const; } op_integer_cst; bool operator_cst::fold_range (irange &r, tree type ATTRIBUTE_UNUSED, const irange &lh, - const irange &rh ATTRIBUTE_UNUSED) const + const irange &rh ATTRIBUTE_UNUSED, + relation_kind rel ATTRIBUTE_UNUSED) const { r = lh; return true; @@ -2903,16 +3195,19 @@ class operator_identity : public range_operator public: virtual bool fold_range (irange &r, tree type, const irange &op1, - const irange &op2) const; + const irange &op2, + relation_kind rel = VREL_NONE) const; virtual bool op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const; + const irange &op2, + relation_kind rel = VREL_NONE) const; } op_identity; bool operator_identity::fold_range (irange &r, tree type ATTRIBUTE_UNUSED, const irange &lh, - const irange &rh ATTRIBUTE_UNUSED) const + const irange &rh ATTRIBUTE_UNUSED, + relation_kind rel ATTRIBUTE_UNUSED) const { r = lh; return true; @@ -2921,7 +3216,8 @@ operator_identity::fold_range (irange &r, tree type ATTRIBUTE_UNUSED, bool operator_identity::op1_range (irange &r, tree type ATTRIBUTE_UNUSED, const irange &lhs, - const irange &op2 ATTRIBUTE_UNUSED) const + const irange &op2 ATTRIBUTE_UNUSED, + relation_kind rel ATTRIBUTE_UNUSED) const { r = lhs; return true; @@ -2933,13 +3229,15 @@ class operator_unknown : public range_operator public: virtual bool fold_range (irange &r, tree type, const irange &op1, - const irange &op2) const; + const irange &op2, + relation_kind rel = VREL_NONE) const; } op_unknown; bool operator_unknown::fold_range (irange &r, tree type, const irange &lh ATTRIBUTE_UNUSED, - const irange &rh ATTRIBUTE_UNUSED) const + const irange &rh ATTRIBUTE_UNUSED, + relation_kind rel ATTRIBUTE_UNUSED) const { r.set_varying (type); return true; @@ -2956,7 +3254,8 @@ class operator_abs : public range_operator const wide_int &rh_ub) const; virtual bool op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const; + const irange &op2, + relation_kind rel ATTRIBUTE_UNUSED) const; } op_abs; void @@ -3036,7 +3335,8 @@ operator_abs::wi_fold (irange &r, tree type, bool operator_abs::op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const + const irange &op2, + relation_kind rel ATTRIBUTE_UNUSED) const { if (empty_range_varying (r, type, lhs, op2)) return true; @@ -3108,16 +3408,19 @@ class operator_negate : public range_operator public: virtual bool fold_range (irange &r, tree type, const irange &op1, - const irange &op2) const; + const irange &op2, + relation_kind rel = VREL_NONE) const; virtual bool op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const; + const irange &op2, + relation_kind rel = VREL_NONE) const; } op_negate; bool operator_negate::fold_range (irange &r, tree type, const irange &lh, - const irange &rh) const + const irange &rh, + relation_kind rel ATTRIBUTE_UNUSED) const { if (empty_range_varying (r, type, lh, rh)) return true; @@ -3130,7 +3433,8 @@ operator_negate::fold_range (irange &r, tree type, bool operator_negate::op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const + const irange &op2, + relation_kind rel ATTRIBUTE_UNUSED) const { // NEGATE is involutory. return fold_range (r, type, lhs, op2); @@ -3142,16 +3446,19 @@ class operator_addr_expr : public range_operator public: virtual bool fold_range (irange &r, tree type, const irange &op1, - const irange &op2) const; + const irange &op2, + relation_kind rel = VREL_NONE) const; virtual bool op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const; + const irange &op2, + relation_kind rel = VREL_NONE) const; } op_addr; bool operator_addr_expr::fold_range (irange &r, tree type, const irange &lh, - const irange &rh) const + const irange &rh, + relation_kind rel ATTRIBUTE_UNUSED) const { if (empty_range_varying (r, type, lh, rh)) return true; @@ -3169,7 +3476,8 @@ operator_addr_expr::fold_range (irange &r, tree type, bool operator_addr_expr::op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const + const irange &op2, + relation_kind rel ATTRIBUTE_UNUSED) const { return operator_addr_expr::fold_range (r, type, lhs, op2); } @@ -3288,10 +3596,12 @@ class pointer_or_operator : public range_operator public: virtual bool op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const; + const irange &op2, + relation_kind rel = VREL_NONE) const; virtual bool op2_range (irange &r, tree type, const irange &lhs, - const irange &op1) const; + const irange &op1, + relation_kind rel = VREL_NONE) const; virtual void wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, const wide_int &rh_ub) const; @@ -3300,7 +3610,8 @@ public: bool pointer_or_operator::op1_range (irange &r, tree type, const irange &lhs, - const irange &op2 ATTRIBUTE_UNUSED) const + const irange &op2 ATTRIBUTE_UNUSED, + relation_kind rel ATTRIBUTE_UNUSED) const { if (lhs.zero_p ()) { @@ -3315,7 +3626,8 @@ pointer_or_operator::op1_range (irange &r, tree type, bool pointer_or_operator::op2_range (irange &r, tree type, const irange &lhs, - const irange &op1) const + const irange &op1, + relation_kind rel ATTRIBUTE_UNUSED) const { return pointer_or_operator::op1_range (r, type, lhs, op1); } diff --git a/gcc/range-op.h b/gcc/range-op.h index d3d44083093..2b5db64bb98 100644 --- a/gcc/range-op.h +++ b/gcc/range-op.h @@ -52,7 +52,8 @@ public: // Perform an operation between 2 ranges and return it. virtual bool fold_range (irange &r, tree type, const irange &lh, - const irange &rh) const; + const irange &rh, + relation_kind rel = VREL_NONE) const; // Return the range for op[12] in the general case. LHS is the range for // the LHS of the expression, OP[12]is the range for the other @@ -67,11 +68,23 @@ public: // is re-formed as R = [LHS] - OP2. virtual bool op1_range (irange &r, tree type, const irange &lhs, - const irange &op2) const; + const irange &op2, + relation_kind rel = VREL_NONE) const; virtual bool op2_range (irange &r, tree type, const irange &lhs, - const irange &op1) const; + const irange &op1, + relation_kind rel = VREL_NONE) const; + // The following routines are used to represent relations between the + // various operations. If the caller knows where the symbolics are, + // it can query for relationships between them given known ranges. + virtual enum tree_code lhs_op1_relation (const irange &lhs, + const irange &op1, + const irange &op2) const; + virtual enum tree_code lhs_op2_relation (const irange &lhs, + const irange &op1, + const irange &op2) const; + virtual enum tree_code op1_op2_relation (const irange &lhs) const; protected: // Perform an integral operation between 2 sub-ranges and return it. virtual void wi_fold (irange &r, tree type, @@ -79,6 +92,11 @@ protected: const wide_int &lh_ub, const wide_int &rh_lb, const wide_int &rh_ub) const; + // Side effect of relation for generic fold_range clients. + virtual bool op1_op2_relation_effect (irange &lhs_range, tree type, + const irange &op1_range, + const irange &op2_range, + relation_kind rel) const; }; extern range_operator *range_op_handler (enum tree_code code, tree type); -- 2.17.2 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 From patchwork Tue Jun 22 13:18:27 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1495681 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=mwGfp5A9; 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 4G8RrW5Kvzz9sS8 for ; Tue, 22 Jun 2021 23:22:03 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 0861C389364E for ; Tue, 22 Jun 2021 13:22:01 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 0861C389364E DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1624368121; bh=CiE0EWbPkbH+aQU1nWbqQEys7Wwo5YyYywZRPxvnZuk=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=mwGfp5A98elNovaW88rufq/PbJi4zi2QFn6dYBHVs4NATh/icuwQvB4rdGEEZIWwP 3zUDzDDW5NeywUt6RwSmJ6utwABkKmtP7NNrT3GFH+E9nEbEXizvaXR5CESiYePlQs AnAfq+pKMivZrNIiPrXPn0E6fIH3poHUFku4na8Q= 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 DE28F383D023 for ; Tue, 22 Jun 2021 13:18:39 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org DE28F383D023 Received: from mail-qv1-f70.google.com (mail-qv1-f70.google.com [209.85.219.70]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-500-t3YZdIf3PjqBAb1SkNMGWQ-1; Tue, 22 Jun 2021 09:18:37 -0400 X-MC-Unique: t3YZdIf3PjqBAb1SkNMGWQ-1 Received: by mail-qv1-f70.google.com with SMTP id x13-20020a0cfe0d0000b0290264540cb5d3so1343359qvr.17 for ; Tue, 22 Jun 2021 06:18:36 -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:from:subject:message-id:date:user-agent :mime-version:content-language; bh=CiE0EWbPkbH+aQU1nWbqQEys7Wwo5YyYywZRPxvnZuk=; b=aU9kpvJRLdAjgybMEbaoSQyREIt42d0ysrpwSnVvcyv0sQ/+gZWoLG2Mqdt9qorwZC bxb0OjepmKcbMWYri/FvhDu2L3exfC1rxBQS0TXrn/zRrP6Sk0Qg37ikcr+g2Q/Ok99l nK0U/iSj8aapj8R1OCDnqiTdCZ1RvVsQuEYgE/rFmhLAavl9fX5dflEXaOpdtrqVNO7z 6PV8hEo9WxGHo6Q8mdzy488Pn+m8C+qUkfqRfbSI3XgDwEtNpPfXRjAIFLjQUqtYqXvq eeIezwqgQ/KSLWqzjxzRBs2VKyDn5ynfOspojRradNpCH+HICIXbg7ge6HNOMEtrWDi0 SCrw== X-Gm-Message-State: AOAM533DNM2tn66jRpvgJL+x7507FmSIB6RtSM/7bCA2DmutIt7PVOwB vbEjx0nqxVSqBimYvkzoJllg9QKN8S79PBgJWW63e/lE/IrowiJ9iDtf9WjIVIaxE353gU6SZJx gjZoIzA9k+/TLXam61GCY7OUl4Vp9SefCg+dD+ORQqikMnT1qYS/sDANFtozszlS9ZYpYrg== X-Received: by 2002:a37:b42:: with SMTP id 63mr4284224qkl.325.1624367913530; Tue, 22 Jun 2021 06:18:33 -0700 (PDT) X-Google-Smtp-Source: ABdhPJwSK342EAn7NmGfWbQHm0mNMFzSqpMD2oyg6zEZhp5d3Bt7QwY5+YupSCmC36hZ4oUVcbfWAA== X-Received: by 2002:a37:b42:: with SMTP id 63mr4284188qkl.325.1624367913132; Tue, 22 Jun 2021 06:18:33 -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 i67sm12996986qkd.90.2021.06.22.06.18.28 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 22 Jun 2021 06:18:28 -0700 (PDT) To: gcc-patches Subject: [COMMITTED 4/7] Add relations between LHS and op1/op2 for PLUS_EXPR. Message-ID: <9103ab49-d653-fc55-0ef6-6465bde4913c@redhat.com> Date: Tue, 22 Jun 2021 09:18:27 -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.5 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, 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-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 demonstrates how to add relation generation between the LHS of an expression and one of the operands in range-ops, using PLUS_EXPR. a_2 = b_3 + c_1 if c_1 == [0, 0], we know a_2 == b_3 if c_1 > 0, and there is no overflow/wrapping, we know a_2 > b_3 likewise, if c1 < 0 we know a_2 < b_3 if c_1 does not contain zero, we also know a_2 != b_3. plus is symmetrical, so we can draw similar conclusions about the relation between a_2 and c_1 based on what we know about b_3's range. Bootstraps on x86_64-pc-linux-gnu with no regressions.  Pushed. Andrew From c526de3f432a037bdbdd44eb6fa43af4f3b22694 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Thu, 17 Jun 2021 13:35:10 -0400 Subject: [PATCH 4/7] Add relations between LHS and op1/op2 for PLUS_EXPR. * range-op.cc (operator_plus::lhs_op1_relation): New. (operator_plus::lhs_op2_relation): New. --- gcc/range-op.cc | 80 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 80 insertions(+) diff --git a/gcc/range-op.cc b/gcc/range-op.cc index d807693900a..a7698f21b0d 100644 --- a/gcc/range-op.cc +++ b/gcc/range-op.cc @@ -1150,8 +1150,88 @@ public: const wide_int &lh_ub, const wide_int &rh_lb, const wide_int &rh_ub) const; + virtual enum tree_code lhs_op1_relation (const irange &lhs, const irange &op1, + const irange &op2) const; + virtual enum tree_code lhs_op2_relation (const irange &lhs, const irange &op1, + const irange &op2) const; } op_plus; +// Check to see if the range of OP2 indicates anything about the relation +// between LHS and OP1. + +enum tree_code +operator_plus::lhs_op1_relation (const irange &lhs, + const irange &op1, + const irange &op2) const +{ + if (lhs.undefined_p () || op1.undefined_p () || op2.undefined_p ()) + return VREL_NONE; + + tree type = lhs.type (); + unsigned prec = TYPE_PRECISION (type); + wi::overflow_type ovf1, ovf2; + signop sign = TYPE_SIGN (type); + + // LHS = OP1 + 0 indicates LHS == OP1. + if (op2.zero_p ()) + return EQ_EXPR; + + if (TYPE_OVERFLOW_WRAPS (type)) + { + wi::add (op1.lower_bound (), op2.lower_bound (), sign, &ovf1); + wi::add (op1.upper_bound (), op2.upper_bound (), sign, &ovf2); + } + else + ovf1 = ovf2 = wi::OVF_NONE; + + // Never wrapping additions. + if (!ovf1 && !ovf2) + { + // Positive op2 means lhs > op1. + if (wi::gt_p (op2.lower_bound (), wi::zero (prec), sign)) + return GT_EXPR; + if (wi::ge_p (op2.lower_bound (), wi::zero (prec), sign)) + return GE_EXPR; + + // Negative op2 means lhs < op1. + if (wi::lt_p (op2.upper_bound (), wi::zero (prec), sign)) + return LT_EXPR; + if (wi::le_p (op2.upper_bound (), wi::zero (prec), sign)) + return LE_EXPR; + } + // Always wrapping additions. + else if (ovf1 && ovf1 == ovf2) + { + // Positive op2 means lhs < op1. + if (wi::gt_p (op2.lower_bound (), wi::zero (prec), sign)) + return LT_EXPR; + if (wi::ge_p (op2.lower_bound (), wi::zero (prec), sign)) + return LE_EXPR; + + // Negative op2 means lhs > op1. + if (wi::lt_p (op2.upper_bound (), wi::zero (prec), sign)) + return GT_EXPR; + if (wi::le_p (op2.upper_bound (), wi::zero (prec), sign)) + return GE_EXPR; + } + + // If op2 does not contain 0, then LHS and OP1 can never be equal. + if (!range_includes_zero_p (&op2)) + return NE_EXPR; + + return VREL_NONE; +} + +// PLUS is symmetrical, so we can simply call lhs_op1_relation with reversed +// operands. + +enum tree_code +operator_plus::lhs_op2_relation (const irange &lhs, const irange &op1, + const irange &op2) const +{ + return lhs_op1_relation (lhs, op2, op1); +} + void operator_plus::wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, -- 2.17.2 From patchwork Tue Jun 22 13:18:48 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1495682 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=UAUlPrOf; 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 4G8Rst0MGvz9sS8 for ; Tue, 22 Jun 2021 23:23:14 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 0DEC53896C26 for ; Tue, 22 Jun 2021 13:23:11 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 0DEC53896C26 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1624368191; bh=6FvWg9NWzFbAilEdKqfrK54BTuA88oeeufN6C31COZc=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=UAUlPrOfEn1f6HNiaIcy5Db1SpomjWg8kQ+gk8h7kclu2orHJxw8bpMmcfEog/i3b Ixu1e/v8mZ/Mbvt03vrgKQNB9+J4PCAq9A6/OylpxzEw2n3iSKMXtAXzeF+KE5WqAc YYxzk0cjj17FpQERLlOjbrYcxEqhSMiAA9On0nz0= 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 582CC383D023 for ; Tue, 22 Jun 2021 13:18:53 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 582CC383D023 Received: from mail-qv1-f69.google.com (mail-qv1-f69.google.com [209.85.219.69]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-350-4ZkEYnMINmemb1xybwF46A-1; Tue, 22 Jun 2021 09:18:51 -0400 X-MC-Unique: 4ZkEYnMINmemb1xybwF46A-1 Received: by mail-qv1-f69.google.com with SMTP id s9-20020ad452490000b02902786b63dbfeso2064922qvq.5 for ; Tue, 22 Jun 2021 06:18: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=6FvWg9NWzFbAilEdKqfrK54BTuA88oeeufN6C31COZc=; b=QTRx24yfPGDP6DmVyhg5imtqvhtbpSfKF1Bf+cgfvbhNRr9F+c3hZgtM7mLyok6tsu u49cAkuuXqhZl/moG7CIxnQ1XOMgbWEFJue6p6CksZJ2Bg8hYQJCNm/a6zMUGHDlQhzq tj3cZWupooBU47IL+WefMSbB6TMJAvzXiXsTkedGFsFFWzkkdUBesh0qY0KtbUMeoYjd PI4zjW3TaOsvlPnNEZb3B/Eh3VKGXXfbsaTwdN3qUvMdmEqV76X8Y8+S12cVkhPLg3i2 WuefTXmZxktI8kKH1nPhEtQRM+AgpAF92CfrJgpNoAmutL9gGMIRTJmbde5BWcejP7C4 so/w== X-Gm-Message-State: AOAM5331pAf6+p7BkWMcHAhS9rKCcGilPBjcBaHfQmh+dS+zNolxmojD GO1zeKTNtg9oifG1bv3bifQtyW2pXxSI8nEZ7JxGEwUU04ES2vnk67cBYhuvyfptyXKY/GOmM8R zRd987DJPjUulpDkA9Q== X-Received: by 2002:a05:6214:4b:: with SMTP id c11mr18161343qvr.18.1624367931240; Tue, 22 Jun 2021 06:18:51 -0700 (PDT) X-Google-Smtp-Source: ABdhPJyjc2W5ib15VRZ1ch2ypQbC+IiIQLndslHzWEM+XcAO0vKvF7vLIKnF07hYzhkccyT2TqezWw== X-Received: by 2002:a05:6214:4b:: with SMTP id c11mr18161317qvr.18.1624367931023; Tue, 22 Jun 2021 06:18:51 -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 z16sm1669455qta.39.2021.06.22.06.18.48 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 22 Jun 2021 06:18:49 -0700 (PDT) To: gcc-patches Subject: [COMMITTED 5/7] Add relation effects between operands to MINUS_EXPR. Message-ID: <59a8dcbe-1755-abda-54cf-92e5fe8bdcea@redhat.com> Date: Tue, 22 Jun 2021 09:18:48 -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.6 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, 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-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 enhances processing of OP_MINUS to show how we can utilize relations between op1 and op2 to produce a better result. Given: a_3 = b_4 - d_1 if we know b_4 > d_1, on top of whatever other range calculations we can do with the actual ranges, we can apply the knowledge that the result must also  be  in the range [1, +INF] as well. likewise, if we know b_4 == d_1, we know the result is [0,0] This provide a sample of how applying a relation between 2 operands is implemented. Bootstraps on x86_64-pc-linux-gnu with no regressions.  Pushed. Andrew From ae6b830f31a47aca7ca24c4fea245c29214eef3a Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Thu, 17 Jun 2021 13:38:03 -0400 Subject: [PATCH 5/7] Add relation effects between operands to MINUS_EXPR. * range-op.cc (operator_minus::op1_op2_relation_effect): New. --- gcc/range-op.cc | 44 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 44 insertions(+) diff --git a/gcc/range-op.cc b/gcc/range-op.cc index a7698f21b0d..ec4816d69fa 100644 --- a/gcc/range-op.cc +++ b/gcc/range-op.cc @@ -1279,6 +1279,11 @@ public: const wide_int &lh_ub, const wide_int &rh_lb, const wide_int &rh_ub) const; + virtual bool op1_op2_relation_effect (irange &lhs_range, + tree type, + const irange &op1_range, + const irange &op2_range, + relation_kind rel) const; } op_minus; void @@ -1293,6 +1298,45 @@ operator_minus::wi_fold (irange &r, tree type, value_range_with_overflow (r, type, new_lb, new_ub, ov_lb, ov_ub); } +// Check to see if the relation REL between OP1 and OP2 has any effect on the +// LHS of the epxression. If so, apply it to LHS_RANGE. + +bool +operator_minus::op1_op2_relation_effect (irange &lhs_range, tree type, + const irange &op1_range ATTRIBUTE_UNUSED, + const irange &op2_range ATTRIBUTE_UNUSED, + relation_kind rel) const +{ + if (rel == VREL_NONE) + return false; + + int_range<2> rel_range; + unsigned prec = TYPE_PRECISION (type); + signop sgn = TYPE_SIGN (type); + + switch (rel) + { + // op1 > op2, op1 - op2 can be restricted to [1, max] + case GT_EXPR: + rel_range = int_range<2> (type, wi::one (prec), + wi::max_value (prec, sgn)); + break; + // op1 >= op2, op1 - op2 can be restricted to [0, max] + case GE_EXPR: + rel_range = int_range<2> (type, wi::zero (prec), + wi::max_value (prec, sgn)); + break; + // op1 == op2, op1 - op2 can be restricted to [0, 0] + case EQ_EXPR: + rel_range = int_range<2> (type, wi::zero (prec), wi::zero (prec)); + break; + default: + return false; + } + lhs_range.intersect (rel_range); + return true; +} + bool operator_minus::op1_range (irange &r, tree type, const irange &lhs, -- 2.17.2 From patchwork Tue Jun 22 13:19:12 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1495683 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=c9QFa+QN; 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 4G8Rv25YtHz9sS8 for ; Tue, 22 Jun 2021 23:24:14 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 1DB643890439 for ; Tue, 22 Jun 2021 13:24:11 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 1DB643890439 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1624368251; bh=NhfSq3hKXATJH4a8F7J/AL1y7CeJDgKFsZJsd9KhsN8=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=c9QFa+QNZReY8ohu8MDHFAXQVLHwJsHEcaTCtaDu/+FhYBO+0/6cVaN1aiG8bmIAE 7IdutdnCc8/NBwIAnfi1BywNZS/QDlLYWn7KfqDGMZnrwQfQbv9sokGSQrxC4WiSYE mJ2Exsw46J7apCmPoh1av6c2YuwgwBVXnomfdl0w= 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 DB3AF3890036 for ; Tue, 22 Jun 2021 13:19:18 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org DB3AF3890036 Received: from mail-qt1-f198.google.com (mail-qt1-f198.google.com [209.85.160.198]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-106-O_F1unPWMXiTlRmmZqQgMQ-1; Tue, 22 Jun 2021 09:19:16 -0400 X-MC-Unique: O_F1unPWMXiTlRmmZqQgMQ-1 Received: by mail-qt1-f198.google.com with SMTP id a5-20020ac84d850000b029024998e61d00so10086996qtw.14 for ; Tue, 22 Jun 2021 06:19: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=NhfSq3hKXATJH4a8F7J/AL1y7CeJDgKFsZJsd9KhsN8=; b=KCQLEzHECd6eAtLc8aSL6/iS6aroKSBtR1CG32R6nf34hEJEZsja4xxPmicKwK59xq uAfxbfa548RCFIplWFLYYemsDNMz8TBlwKFWaLT1Lmh6kQnS1plmtTxgFgkt7OEkAhD2 KGY02dY4S1QYK8h+c2Eynpng5oqwU+ht6mJxEPZj0Q/GX1Rnp5v4INa7zYDsFmVhuAEr GS77/YqoipsbJPvFLL4FY5pWul0M4eg3qRBO329OcyQ8dSM8HJfA2ZIjBP3HvzWmQy5p QqXLvrl+o2n4XSS4oUx9+gqQGYFp9iLUZU7MO2PlALIepbSyyPcqhcQC0DGcALH5mj7P FiYA== X-Gm-Message-State: AOAM531j5hxt8HF5+7p42J7qKJgFxpQ7p7cbmurrs44Var9jC1txME98 910mSLzOuxxVggxQrR68CMl6OwxtasTQzKlEsCnh+dyVFIbC31rIDWkYe2S6ZIE3s1BIB3i9sup naAQ1nPpBQ4oVx10mxQ== X-Received: by 2002:a37:7485:: with SMTP id p127mr4214693qkc.323.1624367956270; Tue, 22 Jun 2021 06:19:16 -0700 (PDT) X-Google-Smtp-Source: ABdhPJyNr9CBlpV3jjGiGqfRQk6NKA+1l7qrWMqXiL/5V9cjKxxgBKeZCs/NlW8pJDMqVbMv791yCA== X-Received: by 2002:a37:7485:: with SMTP id p127mr4214679qkc.323.1624367956118; Tue, 22 Jun 2021 06:19: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 y14sm4146091qkj.8.2021.06.22.06.19.13 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 22 Jun 2021 06:19:14 -0700 (PDT) To: gcc-patches Subject: [COMMITTED 6/7] Add relation between LHS and op1 for casts and copies. Message-ID: <7a5d73c8-0638-5687-96cb-266cd4a1837b@redhat.com> Date: Tue, 22 Jun 2021 09:19:12 -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.6 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, 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-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 provides basic relations between the LHS and OP1 for casts and copies. Copies are very straightforward,  LHS == OP1 always. Casts are a little trickier. If the RHS of the copy is of the same or lower precision as the LHS,  then we can consider them EQ_EXPR.  Otherwise, they are considered to have NO relation. There is a comment regarding exactly why this is the case in the implementation of operator_cast::lhs_op1_relation. Bootstraps on x86_64-pc-linux-gnu with no regressions.  Pushed. Andrew From 0f7ccc063a42407f91fa52a54cc480950a45e75c Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Thu, 17 Jun 2021 13:39:02 -0400 Subject: [PATCH 6/7] Add relation between LHS and op1 for casts and copies. * range-op.cc (operator_cast::lhs_op1_relation): New. (operator_identity::lhs_op1_relation): Mew. --- gcc/range-op.cc | 41 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 41 insertions(+) diff --git a/gcc/range-op.cc b/gcc/range-op.cc index ec4816d69fa..92b314df9dd 100644 --- a/gcc/range-op.cc +++ b/gcc/range-op.cc @@ -2115,6 +2115,10 @@ public: const irange &lhs, const irange &op2, relation_kind rel = VREL_NONE) const; + virtual enum tree_code lhs_op1_relation (const irange &lhs, + const irange &op1, + const irange &op2) const; + private: bool truncating_cast_p (const irange &inner, const irange &outer) const; bool inside_domain_p (const wide_int &min, const wide_int &max, @@ -2123,6 +2127,27 @@ private: const irange &outer) const; } op_convert; +// Determine if there is a relationship between LHS and OP1. + +enum tree_code +operator_cast::lhs_op1_relation (const irange &lhs, + const irange &op1, + const irange &op2 ATTRIBUTE_UNUSED) const +{ + if (op1.undefined_p ()) + return VREL_NONE; + // We can't make larger types equivalent to smaller types because we can + // miss sign extensions in a chain of casts. + // u32 = 0xfffff + // s32 = (s32) u32 + // s64 = (s64) s32 + // we cant simply "convert" s64 = (s64)u32 or we get positive 0xffff + // value instead of sign extended negative value. + if (TYPE_PRECISION (lhs.type ()) == TYPE_PRECISION (op1.type ())) + return EQ_EXPR; + return VREL_NONE; +} + // Return TRUE if casting from INNER to OUTER is a truncating cast. inline bool @@ -3325,8 +3350,24 @@ public: const irange &lhs, const irange &op2, relation_kind rel = VREL_NONE) const; + virtual enum tree_code lhs_op1_relation (const irange &lhs, + const irange &op1, + const irange &op2) const; } op_identity; +// Determine if there is a relationship between LHS and OP1. + +enum tree_code +operator_identity::lhs_op1_relation (const irange &lhs, + const irange &op1 ATTRIBUTE_UNUSED, + const irange &op2 ATTRIBUTE_UNUSED) const +{ + if (lhs.undefined_p ()) + return VREL_NONE; + // Simply a copy, so they are equivalent. + return EQ_EXPR; +} + bool operator_identity::fold_range (irange &r, tree type ATTRIBUTE_UNUSED, const irange &lh, -- 2.17.2 From patchwork Tue Jun 22 13:19:27 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1495684 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=Ke1/eCi0; 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 4G8RwB4Fm1z9sS8 for ; Tue, 22 Jun 2021 23:25:14 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id C7BCC383B815 for ; Tue, 22 Jun 2021 13:25:11 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org C7BCC383B815 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1624368311; bh=42GFqg5tsnps5BEl9WAC/xnqgd+Vd0AFbbN2LvfE7dc=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=Ke1/eCi0hc+RY55L2VMw0VMt5t/6FYoQNabXq14axoAmhXztHfPWKWbAYPpKzbYmy 8dSpiJbqwuhsO2ejaC7oep6jPHRt8vRoTZKObP7hrRCR70PXEjO+Cx+H19FCoCh2bj Zo93xvKIxEIHJmGqyfqbkngkNInTg2RRFbcjTHHs= 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 3209A38930CA for ; Tue, 22 Jun 2021 13:19:34 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 3209A38930CA Received: from mail-qk1-f199.google.com (mail-qk1-f199.google.com [209.85.222.199]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-64-E35FIb8VO-yP-Rgc3NYMRg-1; Tue, 22 Jun 2021 09:19:32 -0400 X-MC-Unique: E35FIb8VO-yP-Rgc3NYMRg-1 Received: by mail-qk1-f199.google.com with SMTP id 81-20020a370e540000b02903aacdbd70b7so17917784qko.23 for ; Tue, 22 Jun 2021 06:19:32 -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:from:subject:message-id:date:user-agent :mime-version:content-language; bh=42GFqg5tsnps5BEl9WAC/xnqgd+Vd0AFbbN2LvfE7dc=; b=dxNbt3HxBDMmaGsS0guKseN5l9UKs64SHR6/RGZmgb7ZGy+8nq7DA2PDu3nk9chIfy mTEZusp9DoduYR8hr1e6cCQ3Mbpt155IFND503xVVC7NNo9C9FOqNsTCgRmCIKkA/hqm vzK7nLX1cpcAAWEivh1zbUXIyhXSSVNqIxpoj3zZ3nde0N1PVKfVUFiKcrjKg+17oy0u WRYeeqhXYWQI908HTa7DZAl/wf/sVoFQy0Jkmjj0Bs/FaQmMfQHr/2MiulzwsKu8BdFG EMLQ/dORgk/HvtFbc/sA7DNyo0GulQdDDq8J9L1gJ/pt9OyCphpvJXvwA9Yte/UJFgXO YiYA== X-Gm-Message-State: AOAM530bAKC+9TLSc6mRchdRkCJcPMPFhdD+wOtiDNOlDojEXlaCUqoy KwpRuBoznoPS+mfJxmKRrafYbJcgGYRWBgSMQGNAP2h827GOrC1MYzc6J/5Qpza1tSt1WPMR4jo l/Hy0aqdY92qOzrzw9bd5e1iLGnJBYNzr1Fx74vFbnlf+2klfls6IJxUpT8ECtlT/evEybA== X-Received: by 2002:aed:30c2:: with SMTP id 60mr3510620qtf.30.1624367971233; Tue, 22 Jun 2021 06:19:31 -0700 (PDT) X-Google-Smtp-Source: ABdhPJx1qtzLYL/h0/KSBj4pybtOOXae15rkgk8O3ezqN2FeOhBRYU3G7GJL54kxPNFDGfUuT2oYlw== X-Received: by 2002:aed:30c2:: with SMTP id 60mr3510604qtf.30.1624367971032; Tue, 22 Jun 2021 06:19:31 -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 r19sm1610806qtw.59.2021.06.22.06.19.29 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 22 Jun 2021 06:19:29 -0700 (PDT) To: gcc-patches Subject: [COMMITTED 7/7] Add relational self-tests. Message-ID: <25672866-17b3-d1a2-7152-c2a4db8f74c4@redhat.com> Date: Tue, 22 Jun 2021 09:19:27 -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.6 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, 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-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 just adds some basic self tests for some of the new relation operations. Bootstraps on x86_64-pc-linux-gnu with no regressions.  Pushed. Andrew From ca1f9f22854049d6f9cab5b4bfbc46edbcb5c990 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Thu, 17 Jun 2021 13:40:05 -0400 Subject: [PATCH 7/7] Add relational self-tests. * range-op.cc (range_relational_tests): New. (range_op_tests): Call range_relational_tests. --- gcc/range-op.cc | 25 +++++++++++++++++++++++++ 1 file changed, 25 insertions(+) diff --git a/gcc/range-op.cc b/gcc/range-op.cc index 92b314df9dd..1692a096e20 100644 --- a/gcc/range-op.cc +++ b/gcc/range-op.cc @@ -4244,6 +4244,30 @@ range_op_bitwise_and_tests () ASSERT_FALSE (res.contains_p (INT (0))); } +static void +range_relational_tests () +{ + int_range<2> lhs (unsigned_char_type_node); + int_range<2> op1 (UCHAR (8), UCHAR (10)); + int_range<2> op2 (UCHAR (20), UCHAR (20)); + + // Never wrapping additions mean LHS > OP1. + tree_code code = op_plus.lhs_op1_relation (lhs, op1, op2); + ASSERT_TRUE (code == GT_EXPR); + + // Most wrapping additions mean nothing... + op1 = int_range<2> (UCHAR (8), UCHAR (10)); + op2 = int_range<2> (UCHAR (0), UCHAR (255)); + code = op_plus.lhs_op1_relation (lhs, op1, op2); + ASSERT_TRUE (code == VREL_NONE); + + // However, always wrapping additions mean LHS < OP1. + op1 = int_range<2> (UCHAR (1), UCHAR (255)); + op2 = int_range<2> (UCHAR (255), UCHAR (255)); + code = op_plus.lhs_op1_relation (lhs, op1, op2); + ASSERT_TRUE (code == LT_EXPR); +} + void range_op_tests () { @@ -4251,6 +4275,7 @@ range_op_tests () range_op_lshift_tests (); range_op_bitwise_and_tests (); range_op_cast_tests (); + range_relational_tests (); } } // namespace selftest -- 2.17.2