From patchwork Thu Oct 13 15:30:29 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1689609 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=aDZHItOq; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4MpD4g6q1Dz23k1 for ; Fri, 14 Oct 2022 02:30:59 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 2E6C7385086B for ; Thu, 13 Oct 2022 15:30:57 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 2E6C7385086B DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1665675057; bh=IzRTYeCbjvLIiFXX+QMs6n4vmwDSRjI98PUqwNJagpM=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=aDZHItOq/7x5LukvDov765jUnPvFRB9Y47qXQdXvtTrJuW6HTHhzzEZv8pXDbwabF +zhh554Twk9eLFi997dL2uFad7Q6iCP5CnMTvh1IceoTRO4dl+YVIAYZ0Iuf0EiCyo 4/WvcH3Pegl5eR/JqJJE/LjAJyxNppRwn7jE+EW8= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by sourceware.org (Postfix) with ESMTPS id 70FD43857407 for ; Thu, 13 Oct 2022 15:30:35 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 70FD43857407 Received: from mail-qv1-f69.google.com (mail-qv1-f69.google.com [209.85.219.69]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-93-wogbHgPkMlOj3r9p6DahUw-1; Thu, 13 Oct 2022 11:30:33 -0400 X-MC-Unique: wogbHgPkMlOj3r9p6DahUw-1 Received: by mail-qv1-f69.google.com with SMTP id i7-20020a0cab47000000b004b4376895bfso1624291qvb.20 for ; Thu, 13 Oct 2022 08:30:33 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=subject:from:cc:to:content-language:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=4r1zjwJgdxy/ThvLqBMAg5yOKKfQJKh6g4qF4GtIASI=; b=WXqFBfamsura7qpQLXWuofJp7f7H1VFkAW4yJN1ySIhTWIIDknvzbqes8867cL4h20 tgbUN6TX8iIEuFpx4RXIVnZSZt3DWzdfqbaHTnbEw65Nz+TZkh/U7p+wARTUGFrfZjll iehaSnmhky8Ui7MDwIRO+1vgBgK5ddTeoEfdlsLTzgrXT5qtHPhIoqoP/Mh8u34atc1Q +wz9Sh9UvXy3x/E2YaKObPH/vFP4Grda8ApvXn2xkWpUmmmUuG650jOvb/H+oDg9+F3R uC8uZ3xO1lqS90N0oHWm7CY+JKd2wT/g/GPhWpN3WmFSX8zF7rDUmrtqvuwy+9E3jczs RGjw== X-Gm-Message-State: ACrzQf2lZvxL7V4ZWD/d1/9ugzdavI75os+IIUJQCg540xgCCsrQPmKY to3LpqrQzzxCVj2M2V/NYDfZbTjg1lo8JZgU0ETuK80dMGYtRqivUEGlybQJu232wzdRmrheXI3 xSOpiBET3i+wk3SSnYrueopcRT5SAsYHl6gO2XmHEi9P1hojBDbDIjGxpmu2TXPCDMO5Nxw== X-Received: by 2002:a05:622a:30c:b0:39c:d45b:4d85 with SMTP id q12-20020a05622a030c00b0039cd45b4d85mr274576qtw.467.1665675032193; Thu, 13 Oct 2022 08:30:32 -0700 (PDT) X-Google-Smtp-Source: AMsMyM7K6XPZAm909sed7ONzhJ/wpTKBGoLbyymAzG3cbs4y435DbnUAGA63JbgHYVbasLny40ttAQ== X-Received: by 2002:a05:622a:30c:b0:39c:d45b:4d85 with SMTP id q12-20020a05622a030c00b0039cd45b4d85mr274553qtw.467.1665675031903; Thu, 13 Oct 2022 08:30:31 -0700 (PDT) Received: from ?IPV6:2607:fea8:a263:f600::50d4? ([2607:fea8:a263:f600::50d4]) by smtp.gmail.com with ESMTPSA id i14-20020ac871ce000000b00398d83256ddsm149094qtp.31.2022.10.13.08.30.30 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 13 Oct 2022 08:30:30 -0700 (PDT) Message-ID: <8c6b6582-59c7-6e1d-4bd9-6673d455a7af@redhat.com> Date: Thu, 13 Oct 2022 11:30:29 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.2.1 To: gcc-patches Subject: [COMMITTED 1/4] Add partial equivalence support to the relation oracle. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-11.2 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Andrew MacLeod via Gcc-patches From: Andrew MacLeod Reply-To: Andrew MacLeod Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" This patch provide the new relation kinds as well as management of the partial equivalency slice table. Bootstrapped on x86_64-pc-linux-gnu with no regressions.  Pushed Andrew From b5563410ea613ff2b2d7c6fa1847cfcb1ff91efb Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Thu, 6 Oct 2022 15:00:52 -0400 Subject: [PATCH 1/4] Add partial equivalence support to the relation oracle. This provides enhancements to the equivalence oracle to also track partial equivalences. They are tracked similar to equivalences, except it tracks a 'slice' of another ssa name. 8, 16, 32 and 64 bit slices are tracked. This will allow casts and mask of the same value to compare equal. * value-relation.cc (equiv_chain::dump): Don't print empty equivalences. (equiv_oracle::equiv_oracle): Allocate a partial equiv table. (equiv_oracle::~equiv_oracle): Release the partial equiv table. (equiv_oracle::add_partial_equiv): New. (equiv_oracle::partial_equiv_set): New. (equiv_oracle::partial_equiv): New. (equiv_oracle::query_relation): Check for partial equivs too. (equiv_oracle::dump): Also dump partial equivs. (dom_oracle::register_relation): Handle partial equivs. (dom_oracle::query_relation): Check for partial equivs. * value-relation.h (enum relation_kind_t): Add partial equivs. (relation_partial_equiv_p): New. (relation_equiv_p): New. (class pe_slice): New. (class equiv_oracle): Add prototypes. (pe_to_bits): New. (bits_to_pe): New. (pe_min): New. --- gcc/value-relation.cc | 165 +++++++++++++++++++++++++++++++++++++++--- gcc/value-relation.h | 78 +++++++++++++++++++- 2 files changed, 229 insertions(+), 14 deletions(-) diff --git a/gcc/value-relation.cc b/gcc/value-relation.cc index 1ee6da199f2..ceeca53e0a1 100644 --- a/gcc/value-relation.cc +++ b/gcc/value-relation.cc @@ -32,10 +32,11 @@ along with GCC; see the file COPYING3. If not see #include "alloc-pool.h" #include "dominance.h" -#define VREL_LAST VREL_NE +#define VREL_LAST VREL_PE64 static const char *kind_string[VREL_LAST + 1] = -{ "varying", "undefined", "<", "<=", ">", ">=", "==", "!=" }; +{ "varying", "undefined", "<", "<=", ">", ">=", "==", "!=", "pe8", "pe16", + "pe32", "pe64" }; // Print a relation_kind REL to file F. @@ -302,7 +303,7 @@ equiv_chain::dump (FILE *f) const bitmap_iterator bi; unsigned i; - if (!m_names) + if (!m_names || bitmap_empty_p (m_names)) return; fprintf (f, "Equivalence set : ["); unsigned c = 0; @@ -329,18 +330,124 @@ equiv_oracle::equiv_oracle () obstack_init (&m_chain_obstack); m_self_equiv.create (0); m_self_equiv.safe_grow_cleared (num_ssa_names + 1); + m_partial.create (0); + m_partial.safe_grow_cleared (num_ssa_names + 1); } // Destruct an equivalency oracle. equiv_oracle::~equiv_oracle () { + m_partial.release (); m_self_equiv.release (); obstack_free (&m_chain_obstack, NULL); m_equiv.release (); bitmap_obstack_release (&m_bitmaps); } +// Add a partial equivalence R between OP1 and OP2. + +void +equiv_oracle::add_partial_equiv (relation_kind r, tree op1, tree op2) +{ + int v1 = SSA_NAME_VERSION (op1); + int v2 = SSA_NAME_VERSION (op2); + int prec2 = TYPE_PRECISION (TREE_TYPE (op2)); + int bits = pe_to_bits (r); + gcc_checking_assert (bits && prec2 >= bits); + + if (v1 >= (int)m_partial.length () || v2 >= (int)m_partial.length ()) + m_partial.safe_grow_cleared (num_ssa_names + 1); + gcc_checking_assert (v1 < (int)m_partial.length () + && v2 < (int)m_partial.length ()); + + pe_slice &pe1 = m_partial[v1]; + pe_slice &pe2 = m_partial[v2]; + + if (pe1.members) + { + // If the definition pe1 already has an entry, either the stmt is + // being re-evaluated, or the def was used before being registered. + // In either case, if PE2 has an entry, we simply do nothing. + if (pe2.members) + return; + // PE1 is the LHS and already has members, so everything in the set + // should be a slice of PE2 rather than PE1. + pe2.code = pe_min (r, pe1.code); + pe2.ssa_base = op2; + pe2.members = pe1.members; + bitmap_iterator bi; + unsigned x; + EXECUTE_IF_SET_IN_BITMAP (pe1.members, 0, x, bi) + { + m_partial[x].ssa_base = op2; + m_partial[x].code = pe2.code; + } + bitmap_set_bit (pe1.members, v2); + return; + } + if (pe2.members) + { + pe1.ssa_base = pe2.ssa_base; + // If pe2 is a 16 bit value, but only an 8 bit copy, we can't be any + // more than an 8 bit equivalence here, so choose MIN value. + pe1.code = pe_min (r, pe2.code); + pe1.members = pe2.members; + bitmap_set_bit (pe1.members, v1); + } + else + { + // Neither name has an entry, simply create op1 as slice of op2. + pe2.code = bits_to_pe (TYPE_PRECISION (TREE_TYPE (op2))); + if (pe2.code == VREL_VARYING) + return; + pe2.ssa_base = op2; + pe2.members = BITMAP_ALLOC (&m_bitmaps); + bitmap_set_bit (pe2.members, v2); + pe1.ssa_base = op2; + pe1.code = r; + pe1.members = pe2.members; + bitmap_set_bit (pe1.members, v1); + } +} + +// Return the set of partial equivalences associated with NAME. The bitmap +// will be NULL if there are none. + +const pe_slice * +equiv_oracle::partial_equiv_set (tree name) +{ + int v = SSA_NAME_VERSION (name); + if (v >= (int)m_partial.length ()) + return NULL; + return &m_partial[v]; +} + +// Query if there is a partial equivalence between SSA1 and SSA2. Return +// VREL_VARYING if there is not one. If BASE is non-null, return the base +// ssa-name this is a slice of. + +relation_kind +equiv_oracle::partial_equiv (tree ssa1, tree ssa2, tree *base) const +{ + int v1 = SSA_NAME_VERSION (ssa1); + int v2 = SSA_NAME_VERSION (ssa2); + + if (v1 >= (int)m_partial.length () || v2 >= (int)m_partial.length ()) + return VREL_VARYING; + + const pe_slice &pe1 = m_partial[v1]; + const pe_slice &pe2 = m_partial[v2]; + if (pe1.members && pe2.members == pe1.members) + { + if (base) + *base = pe1.ssa_base; + return pe_min (pe1.code, pe2.code); + } + return VREL_VARYING; +} + + // Find and return the equivalency set for SSA along the dominators of BB. // This is the external API. @@ -365,7 +472,7 @@ equiv_oracle::equiv_set (tree ssa, basic_block bb) return m_self_equiv[v]; } -// Query if thre is a relation (equivalence) between 2 SSA_NAMEs. +// Query if there is a relation (equivalence) between 2 SSA_NAMEs. relation_kind equiv_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2) @@ -373,7 +480,9 @@ equiv_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2) // If the 2 ssa names share the same equiv set, they are equal. if (equiv_set (ssa1, bb) == equiv_set (ssa2, bb)) return VREL_EQ; - return VREL_VARYING; + + // Check if there is a partial equivalence. + return partial_equiv (ssa1, ssa2); } // Query if thre is a relation (equivalence) between 2 SSA_NAMEs. @@ -515,6 +624,12 @@ void equiv_oracle::register_relation (basic_block bb, relation_kind k, tree ssa1, tree ssa2) { + // Process partial equivalencies. + if (relation_partial_equiv_p (k)) + { + add_partial_equiv (k, ssa1, ssa2); + return; + } // Only handle equality relations. if (k != VREL_EQ) return; @@ -611,12 +726,34 @@ 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); + // Process equivalences. + if (m_equiv[bb->index]) + { + equiv_chain *ptr = m_equiv[bb->index]->m_next; + for (; ptr; ptr = ptr->m_next) + ptr->dump (f); + } + // Look for partial equivalences defined in this block.. + for (unsigned i = 0; i < num_ssa_names; i++) + { + tree name = ssa_name (i); + if (!gimple_range_ssa_p (name) || !SSA_NAME_DEF_STMT (name)) + continue; + if (i >= m_partial.length ()) + break; + tree base = m_partial[i].ssa_base; + if (base && name != base && gimple_bb (SSA_NAME_DEF_STMT (name)) == bb) + { + relation_kind k = partial_equiv (name, base); + if (k != VREL_VARYING) + { + value_relation vr (k, name, base); + fprintf (f, "Partial equiv "); + vr.dump (f); + fputc ('\n',f); + } + } + } } // Dump all equivalence sets known to the oracle. @@ -906,7 +1043,7 @@ dom_oracle::register_relation (basic_block bb, relation_kind k, tree op1, return; // Equivalencies are handled by the equivalence oracle. - if (k == VREL_EQ) + if (relation_equiv_p (k)) equiv_oracle::register_relation (bb, k, op1, op2); else { @@ -1210,6 +1347,10 @@ dom_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2) if (bitmap_bit_p (equiv1, v2) && bitmap_bit_p (equiv2, v1)) return VREL_EQ; + kind = partial_equiv (ssa1, ssa2); + if (kind != VREL_VARYING) + return kind; + // Initially look for a direct relationship and just return that. kind = find_relation_dom (bb, v1, v2); if (kind != VREL_VARYING) diff --git a/gcc/value-relation.h b/gcc/value-relation.h index e1347ea8ad8..f5f2524ad56 100644 --- a/gcc/value-relation.h +++ b/gcc/value-relation.h @@ -70,7 +70,11 @@ typedef enum relation_kind_t VREL_GT, // r1 > r2 VREL_GE, // r1 >= r2 VREL_EQ, // r1 == r2 - VREL_NE // r1 != r2 + VREL_NE, // r1 != r2 + VREL_PE8, // 8 bit partial equivalency + VREL_PE16, // 16 bit partial equivalency + VREL_PE32, // 32 bit partial equivalency + VREL_PE64 // 64 bit partial equivalency } relation_kind; // General relation kind transformations. @@ -79,7 +83,12 @@ relation_kind relation_intersect (relation_kind r1, relation_kind r2); relation_kind relation_negate (relation_kind r); relation_kind relation_swap (relation_kind r); inline bool relation_lt_le_gt_ge_p (relation_kind r) - { return (r >= VREL_LT && r <= VREL_GE); } + { return (r >= VREL_LT && r <= VREL_GE); } +inline bool relation_partial_equiv_p (relation_kind r) + { return (r >= VREL_PE8 && r <= VREL_PE64); } +inline bool relation_equiv_p (relation_kind r) + { return r == VREL_EQ || relation_partial_equiv_p (r); } + void print_relation (FILE *f, relation_kind rel); class relation_oracle @@ -93,6 +102,7 @@ public: // Return equivalency set for an SSA name in a basic block. virtual const_bitmap equiv_set (tree, basic_block) = 0; + virtual const class pe_slice *partial_equiv_set (tree) { return NULL; } // register a relation between 2 ssa names in a basic block. virtual void register_relation (basic_block, relation_kind, tree, tree) = 0; // Query for a relation between two ssa names in a basic block. @@ -125,6 +135,14 @@ public: equiv_chain *find (unsigned ssa); }; +class pe_slice +{ +public: + tree ssa_base; // Slice of this name. + relation_kind code; // bits that are equivalent. + bitmap members; // Other members in the partial equivalency. +}; + // 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, @@ -137,9 +155,12 @@ public: ~equiv_oracle (); const_bitmap equiv_set (tree ssa, basic_block bb) final override; + const pe_slice *partial_equiv_set (tree name) final override; void register_relation (basic_block bb, relation_kind k, tree ssa1, tree ssa2) override; + void add_partial_equiv (relation_kind, tree, tree); + relation_kind partial_equiv (tree ssa1, tree ssa2, tree *base = NULL) const; relation_kind query_relation (basic_block, tree, tree) override; relation_kind query_relation (basic_block, const_bitmap, const_bitmap) override; @@ -153,6 +174,7 @@ private: bitmap m_equiv_set; // Index by ssa-name. true if an equivalence exists. vec m_equiv; // Index by BB. list of equivalences. vec m_self_equiv; // Index by ssa-name, self equivalency set. + vec m_partial; // Partial equivalencies. void limit_check (basic_block bb = NULL); equiv_chain *find_equiv_block (unsigned ssa, int bb) const; @@ -315,4 +337,56 @@ value_relation::value_relation (relation_kind kind, tree n1, tree n2) set_relation (kind, n1, n2); } +// Return the number of bits associated with partial equivalency T. +// Return 0 if this is not a supported partial equivalency relation. + +inline int +pe_to_bits (relation_kind t) +{ + switch (t) + { + case VREL_PE8: + return 8; + case VREL_PE16: + return 16; + case VREL_PE32: + return 32; + case VREL_PE64: + return 64; + default: + return 0; + } +} + +// Return the partial equivalency code associated with the number of BITS. +// return VREL_VARYING if there is no exact match. + +inline relation_kind +bits_to_pe (int bits) +{ + switch (bits) + { + case 8: + return VREL_PE8; + case 16: + return VREL_PE16; + case 32: + return VREL_PE32; + case 64: + return VREL_PE64; + default: + return VREL_VARYING; + } +} + +// Given partial equivalencies T1 and T2, return the snmallest kind. + +inline relation_kind +pe_min (relation_kind t1, relation_kind t2) +{ + gcc_checking_assert (relation_partial_equiv_p (t1)); + gcc_checking_assert (relation_partial_equiv_p (t2)); + // VREL_PE are declared small to large, so simple min will suffice. + return MIN (t1, t2); +} #endif /* GCC_VALUE_RELATION_H */ -- 2.37.3 From patchwork Thu Oct 13 15:30:55 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1689610 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=nDIJhZ1p; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4MpD5924RCz23k1 for ; Fri, 14 Oct 2022 02:31:25 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 11BE1385114A for ; Thu, 13 Oct 2022 15:31:23 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 11BE1385114A DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1665675083; bh=sW/gYUrlawUVl1s6yjjfYWzkla69td0Dc90dhqHKA4E=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=nDIJhZ1paybwv3r9JLfWd+qdeAr+LXN/ES6vcFfke1jwcf2VZi7Xo5gZr5ODpXSd5 HvxSqGgsD2/rZIq1ZKEzUNJbQicrL/9SxlFbpdXneMmucrjGPyJpgMwVM15vaj8rZu t9WzKsqJ7Vu01nM51pO3HWS8MvHhqdyDE/ZYCs0E= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id DE47B3856DC3 for ; Thu, 13 Oct 2022 15:31:01 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org DE47B3856DC3 Received: from mail-qt1-f198.google.com (mail-qt1-f198.google.com [209.85.160.198]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-10-1G2ax6iPONyJ3WvJgyEssA-1; Thu, 13 Oct 2022 11:30:59 -0400 X-MC-Unique: 1G2ax6iPONyJ3WvJgyEssA-1 Received: by mail-qt1-f198.google.com with SMTP id bv21-20020a05622a0a1500b00393a6724d4cso1552205qtb.23 for ; Thu, 13 Oct 2022 08:30:58 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=subject:from:cc:to:content-language:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=B0fmdpW/AHa+kEUt4IyswpaL3sus9BHHp58tNocHyCQ=; b=bTpC8Ua4Ts+EhjhFhkYFMqJeRO2d6+p+iX21vJLgRPYW03tU0aQ5qd6bb6HOdSJTVI ViIaHhOe1Su/cGd/SZ4Om2Mi+4sh7IeGLYc+AxWKiuMNCG9Dud9x4N2hLDrY7beZ+fr8 9x7JhUeSZxMyMDldEI/0NtqqGmUE3lRbcNa2s66Gz3DmAec481tD/TUdyvDx5thPFhVQ NqFcgoXIYarKqSLHp4oVcuGC2pC9loxb0fbIovPjha6fyEYhdNutNa33DXcLGst6W2GG /mKlV78IK6Car8BZJjpXHJDmC7V5i4CFExcNTmv6nUDvg4PVmfa95FG3t7D2KatqHCkL 5xyg== X-Gm-Message-State: ACrzQf2IEaQ4BHW2qD8dgYV9PkIcYepbGIETNfY8Q5xq5QS4loatsH36 mVDlUYSWiaJwvHU+0252fXDnHT4PNpdnJedk3ycZcO0hhqDRk27RLW6Fv8qVD9w1rReyZ/MtTTi HqqeNse6tqIiidtuqOoYRwf9qBI76D9F+Pnq5hq0ljJ+e41BrzX8ytK2kbiVBmLnDWRINDQ== X-Received: by 2002:a05:622a:492:b0:35d:518d:2b58 with SMTP id p18-20020a05622a049200b0035d518d2b58mr365399qtx.78.1665675057567; Thu, 13 Oct 2022 08:30:57 -0700 (PDT) X-Google-Smtp-Source: AMsMyM71zTjD9DyZMolruvupIa6KYXZ5Odtcdfuo7o5Q934Vj7Aa5EolRw51Muvs5ccioPki84/IeA== X-Received: by 2002:a05:622a:492:b0:35d:518d:2b58 with SMTP id p18-20020a05622a049200b0035d518d2b58mr365371qtx.78.1665675057251; Thu, 13 Oct 2022 08:30:57 -0700 (PDT) Received: from ?IPV6:2607:fea8:a263:f600::50d4? ([2607:fea8:a263:f600::50d4]) by smtp.gmail.com with ESMTPSA id t13-20020a05620a450d00b006ec62032d3dsm17596qkp.30.2022.10.13.08.30.55 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 13 Oct 2022 08:30:56 -0700 (PDT) Message-ID: <70c3023e-cbc0-312b-431b-7fd8eda37e74@redhat.com> Date: Thu, 13 Oct 2022 11:30:55 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.2.1 To: gcc-patches Subject: [COMMITTED 2/4] Add equivalence iterator to relation oracle. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-11.4 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_NONE, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Andrew MacLeod via Gcc-patches From: Andrew MacLeod Reply-To: Andrew MacLeod Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" Instead of looping over an exposed equivalence bitmap, provide iterators to loop over equivalences, partial equivalences, or both. Bootstrapped on x86_64-pc-linux-gnu with no regressions.  Pushed Andrew From aa05838b0536422256e0c477c57f1ea1d2915e92 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Fri, 7 Oct 2022 12:55:32 -0400 Subject: [PATCH 2/4] Add equivalence iterator to relation oracle. Instead of looping over an exposed equivalence bitmap, provide iterators to loop over equivalences, partial equivalences, or both. * gimple-range-cache.cc (ranger_cache::fill_block_cache): Use iterator. * value-relation.cc (equiv_relation_iterator::equiv_relation_iterator): New. (equiv_relation_iterator::next): New. (equiv_relation_iterator::get_name): New. * value-relation.h (class relation_oracle): Privatize some methods. (class equiv_relation_iterator): New. (FOR_EACH_EQUIVALENCE): New. (FOR_EACH_PARTIAL_EQUIV): New. (FOR_EACH_PARTIAL_AND_FULL_EQUIV): New. --- gcc/gimple-range-cache.cc | 10 +---- gcc/value-relation.cc | 78 +++++++++++++++++++++++++++++++++++++++ gcc/value-relation.h | 41 ++++++++++++++++++-- 3 files changed, 118 insertions(+), 11 deletions(-) diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index 4782d47265e..8c80ba6cd14 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -1220,15 +1220,9 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) // See if any equivalences can refine it. if (m_oracle) { - unsigned i; - bitmap_iterator bi; - // Query equivalences in read-only mode. - const_bitmap equiv = m_oracle->equiv_set (name, bb); - EXECUTE_IF_SET_IN_BITMAP (equiv, 0, i, bi) + tree equiv_name; + FOR_EACH_EQUIVALENCE (m_oracle, bb, name, equiv_name) { - if (i == SSA_NAME_VERSION (name)) - continue; - tree equiv_name = ssa_name (i); basic_block equiv_bb = gimple_bb (SSA_NAME_DEF_STMT (equiv_name)); // Check if the equiv has any ranges calculated. diff --git a/gcc/value-relation.cc b/gcc/value-relation.cc index ceeca53e0a1..50fc190a36b 100644 --- a/gcc/value-relation.cc +++ b/gcc/value-relation.cc @@ -1641,3 +1641,81 @@ path_oracle::dump (FILE *f) const fprintf (f, "\n"); } } + +// ------------------------------------------------------------------------ +// EQUIV iterator. Although we have bitmap iterators, don't expose that it +// is currently a bitmap. Use an export iterator to hide future changes. + +// Construct a basic iterator over an equivalence bitmap. + +equiv_relation_iterator::equiv_relation_iterator (relation_oracle *oracle, + basic_block bb, tree name, + bool full, bool partial) +{ + m_name = name; + m_oracle = oracle; + m_pe = partial ? oracle->partial_equiv_set (name) : NULL; + m_bm = NULL; + if (full) + m_bm = oracle->equiv_set (name, bb); + if (!m_bm && m_pe) + m_bm = m_pe->members; + if (m_bm) + bmp_iter_set_init (&m_bi, m_bm, 1, &m_y); +} + +// Move to the next export bitmap spot. + +void +equiv_relation_iterator::next () +{ + bmp_iter_next (&m_bi, &m_y); +} + +// Fetch the name of the next export in the export list. Return NULL if +// iteration is done. + +tree +equiv_relation_iterator::get_name (relation_kind *rel) +{ + if (!m_bm) + return NULL_TREE; + + while (bmp_iter_set (&m_bi, &m_y)) + { + // Do not return self. + tree t = ssa_name (m_y); + if (t && t != m_name) + { + relation_kind k = VREL_EQ; + if (m_pe && m_bm == m_pe->members) + { + const pe_slice *equiv_pe = m_oracle->partial_equiv_set (t); + if (equiv_pe && equiv_pe->members == m_pe->members) + k = pe_min (m_pe->code, equiv_pe->code); + else + k = VREL_VARYING; + } + if (relation_equiv_p (k)) + { + if (rel) + *rel = k; + return t; + } + } + next (); + } + + // Process partial equivs after full equivs if both were requested. + if (m_pe && m_bm != m_pe->members) + { + m_bm = m_pe->members; + if (m_bm) + { + // Recursively call back to process First PE. + bmp_iter_set_init (&m_bi, m_bm, 1, &m_y); + return get_name (rel); + } + } + return NULL_TREE; +} diff --git a/gcc/value-relation.h b/gcc/value-relation.h index f5f2524ad56..a3bbe1e8157 100644 --- a/gcc/value-relation.h +++ b/gcc/value-relation.h @@ -100,9 +100,6 @@ public: // register a relation between 2 ssa names on an edge. void register_edge (edge, relation_kind, tree, tree); - // Return equivalency set for an SSA name in a basic block. - virtual const_bitmap equiv_set (tree, basic_block) = 0; - virtual const class pe_slice *partial_equiv_set (tree) { return NULL; } // register a relation between 2 ssa names in a basic block. virtual void register_relation (basic_block, relation_kind, tree, tree) = 0; // Query for a relation between two ssa names in a basic block. @@ -115,6 +112,11 @@ public: virtual void dump (FILE *) const = 0; void debug () const; protected: + friend class equiv_relation_iterator; + // Return equivalency set for an SSA name in a basic block. + virtual const_bitmap equiv_set (tree, basic_block) = 0; + // Return partial equivalency record for an SSA name. + virtual const class pe_slice *partial_equiv_set (tree) { return NULL; } void valid_equivs (bitmap b, const_bitmap equivs, basic_block bb); // Query for a relation between two equivalency sets in a basic block. virtual relation_kind query_relation (basic_block, const_bitmap, @@ -281,6 +283,39 @@ private: struct obstack m_chain_obstack; }; +// Used to assist with iterating over the equivalence list. +class equiv_relation_iterator { +public: + equiv_relation_iterator (relation_oracle *oracle, basic_block bb, tree name, + bool full = true, bool partial = false); + void next (); + tree get_name (relation_kind *rel = NULL); +protected: + relation_oracle *m_oracle; + const_bitmap m_bm; + const pe_slice *m_pe; + bitmap_iterator m_bi; + unsigned m_y; + tree m_name; +}; + +#define FOR_EACH_EQUIVALENCE(oracle, bb, name, equiv_name) \ + for (equiv_relation_iterator iter (oracle, bb, name, true, false); \ + ((equiv_name) = iter.get_name ()); \ + iter.next ()) + +#define FOR_EACH_PARTIAL_EQUIV(oracle, bb, name, equiv_name, equiv_rel) \ + for (equiv_relation_iterator iter (oracle, bb, name, false, true); \ + ((equiv_name) = iter.get_name (&equiv_rel)); \ + iter.next ()) + +#define FOR_EACH_PARTIAL_AND_FULL_EQUIV(oracle, bb, name, equiv_name, \ + equiv_rel) \ + for (equiv_relation_iterator iter (oracle, bb, name, true, true); \ + ((equiv_name) = iter.get_name (&equiv_rel)); \ + iter.next ()) + + // 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. -- 2.37.3 From patchwork Thu Oct 13 15:31:23 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1689612 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=TcaOh+1M; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4MpD6J09Fsz23k1 for ; Fri, 14 Oct 2022 02:32:24 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 01925384F024 for ; Thu, 13 Oct 2022 15:32:22 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 01925384F024 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1665675142; bh=+iMPgB0u+nHBL9l5oWAzS9rKeUrowoqlGjJxfn+QSVY=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=TcaOh+1MJKycEUdlT72kzyEW9yfzQAeGSLmla1xxj4C37UxrVCJlJYLuFgrQyLdkK Qc56d4oq5aVVldYgOgufEmZHuEcznrT12a8Gwa8JZUB2RLQmzfZ5EoKvGWgAyRKm5S cuj/4Opw6bolZ8RUxXKMv5qmabAAm53Zp1Qz52E8= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by sourceware.org (Postfix) with ESMTPS id F38BB3857407 for ; Thu, 13 Oct 2022 15:31:28 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org F38BB3857407 Received: from mail-qt1-f200.google.com (mail-qt1-f200.google.com [209.85.160.200]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-417-Pds1i8sQMfOdkKiedfoKYw-1; Thu, 13 Oct 2022 11:31:27 -0400 X-MC-Unique: Pds1i8sQMfOdkKiedfoKYw-1 Received: by mail-qt1-f200.google.com with SMTP id cg13-20020a05622a408d00b0035bb2f77e7eso1563413qtb.10 for ; Thu, 13 Oct 2022 08:31:27 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=subject:from:cc:to:content-language:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=BQJNRgvI3LsacgWiir6gsfy8ziwx/PsyYAmgwTpopEM=; b=XHSFc3/hiQgtEURR0TcCk32+iZ+tHptpUHqCD/Rg7s7BCgVmv/BVPttK09RIUGO32W gc7MDe+s+wO0JRnSHkPiajNxMbpMFC7ebx1WdkpPD3WpQpT1CUVIjkTNx/Sgvk/u4rXq hZ5crG4wxku24+2gxcP1OZ4a/hnTmjVa0BU7VuXgtYo38CMifS8bg1OWJZda6h7k+ZVo EcYtjYCbjcTZJwvtvyDLxGxzFdmZXtS5YTn1Cdc6lXpckiiwv62krKODY0MZsXOMMI9J VwzWzCQm/XcGSGpZIBu9LjsAecouSgsaFdIrf0XGgS7EqkLfvFWdpd+OGzKUY4NocW5j D+tg== X-Gm-Message-State: ACrzQf0mUfmfrDtkrdTCDsMuxIhJ1oHrSWhEdOg8i65GqbfsxoSneUpo Ge8cQLZziDdpyozlpv6HOp3zkSfN63wi/nbDtO02k1gpZnu0FIRFja1rrGei8dcOkTyB9BKxZK/ sLW7Jor1mmsaXQEck63EBhn/3LCBPYeHzm3KlVz8jyiGyo0Z8Uk0Y8u/tum5De4xnc7xD5A== X-Received: by 2002:a37:8205:0:b0:6e4:3d36:10a4 with SMTP id e5-20020a378205000000b006e43d3610a4mr304922qkd.783.1665675086150; Thu, 13 Oct 2022 08:31:26 -0700 (PDT) X-Google-Smtp-Source: AMsMyM5Aq7WTgtw9q5cHxoX0js1ANddKJ7UDwTr9om0yeq/flrY+WR/Ic4/C0ihm+PVPK4wcixC+QA== X-Received: by 2002:a37:8205:0:b0:6e4:3d36:10a4 with SMTP id e5-20020a378205000000b006e43d3610a4mr304895qkd.783.1665675085803; Thu, 13 Oct 2022 08:31:25 -0700 (PDT) Received: from ?IPV6:2607:fea8:a263:f600::50d4? ([2607:fea8:a263:f600::50d4]) by smtp.gmail.com with ESMTPSA id t4-20020a05620a450400b006eeacec79a3sm3723203qkp.104.2022.10.13.08.31.24 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 13 Oct 2022 08:31:24 -0700 (PDT) Message-ID: Date: Thu, 13 Oct 2022 11:31:23 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.2.1 To: gcc-patches Subject: [COMMITTED 3/4] Add partial equivalence recognition to cast and bitwise and. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-11.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_NONE, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Andrew MacLeod via Gcc-patches From: Andrew MacLeod Reply-To: Andrew MacLeod Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" This provides the hooks that will register basic partial equivalencies for casts and bitwise AND operations with the appropriate bit pattern. Bootstrapped on x86_64-pc-linux-gnu with no regressions.  Pushed Andrew From d75be7e4343f049176546aa9517d570e5eb67954 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Thu, 6 Oct 2022 15:01:24 -0400 Subject: [PATCH 3/4] Add partial equivalence recognition to cast and bitwise and. This provides the hooks that will register partial equivalencies for casts and bitwise AND operations with the appropriate bit pattern. * range-op.cc (operator_cast::lhs_op1_relation): New. (operator_bitwise_and::lhs_op1_relation): New. --- gcc/range-op.cc | 65 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 65 insertions(+) diff --git a/gcc/range-op.cc b/gcc/range-op.cc index f8255dd10a1..cf7f0dcd670 100644 --- a/gcc/range-op.cc +++ b/gcc/range-op.cc @@ -2417,6 +2417,10 @@ public: const irange &lhs, const irange &op2, relation_kind rel = VREL_VARYING) const; + virtual relation_kind lhs_op1_relation (const irange &lhs, + const irange &op1, + const irange &op2, + relation_kind) 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, @@ -2425,6 +2429,35 @@ private: const irange &outer) const; } op_convert; +// Add a partial equivalence between the LHS and op1 for casts. + +relation_kind +operator_cast::lhs_op1_relation (const irange &lhs, + const irange &op1, + const irange &op2 ATTRIBUTE_UNUSED, + relation_kind) const +{ + if (lhs.undefined_p () || op1.undefined_p ()) + return VREL_VARYING; + unsigned lhs_prec = TYPE_PRECISION (lhs.type ()); + unsigned op1_prec = TYPE_PRECISION (op1.type ()); + // If the result gets sign extended into a larger type check first if this + // qualifies as a partial equivalence. + if (TYPE_SIGN (op1.type ()) == SIGNED && lhs_prec > op1_prec) + { + // If the result is sign extended, and the LHS is larger than op1, + // check if op1's range can be negative as the sign extention will + // cause the upper bits to be 1 instead of 0, invalidating the PE. + int_range<3> negs = range_negatives (op1.type ()); + negs.intersect (op1); + if (!negs.undefined_p ()) + return VREL_VARYING; + } + + unsigned prec = MIN (lhs_prec, op1_prec); + return bits_to_pe (prec); +} + // Return TRUE if casting from INNER to OUTER is a truncating cast. inline bool @@ -2739,6 +2772,10 @@ public: const wide_int &lh_ub, const wide_int &rh_lb, const wide_int &rh_ub) const; + virtual relation_kind lhs_op1_relation (const irange &lhs, + const irange &op1, + const irange &op2, + relation_kind) const; private: void simple_op1_range_solver (irange &r, tree type, const irange &lhs, @@ -2784,6 +2821,34 @@ wi_optimize_signed_bitwise_op (irange &r, tree type, return true; } +// An AND of 8,16, 32 or 64 bits can produce a partial equivalence between +// the LHS and op1. + +relation_kind +operator_bitwise_and::lhs_op1_relation (const irange &lhs, + const irange &op1, + const irange &op2, + relation_kind) const +{ + if (lhs.undefined_p () || op1.undefined_p () || op2.undefined_p ()) + return VREL_VARYING; + if (!op2.singleton_p ()) + return VREL_VARYING; + // if val == 0xff or 0xFFFF OR 0Xffffffff OR 0Xffffffffffffffff, return TRUE + int prec1 = TYPE_PRECISION (op1.type ()); + int prec2 = TYPE_PRECISION (op2.type ()); + int mask_prec = 0; + wide_int mask = op2.lower_bound (); + if (wi::eq_p (mask, wi::mask (8, false, prec2))) + mask_prec = 8; + else if (wi::eq_p (mask, wi::mask (16, false, prec2))) + mask_prec = 16; + else if (wi::eq_p (mask, wi::mask (32, false, prec2))) + mask_prec = 32; + else if (wi::eq_p (mask, wi::mask (64, false, prec2))) + mask_prec = 64; + return bits_to_pe (MIN (prec1, mask_prec)); +} // Optimize BIT_AND_EXPR and BIT_IOR_EXPR in terms of a mask if // possible. Basically, see if we can optimize: -- 2.37.3 From patchwork Thu Oct 13 15:31:40 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1689611 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=jdPpcvJ1; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4MpD605fxpz23k1 for ; Fri, 14 Oct 2022 02:32:08 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 2A533385020A for ; Thu, 13 Oct 2022 15:32:06 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 2A533385020A DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1665675126; bh=Fhj8+a0wAuUHYEQgIkRiODo86vszpqovS8+uYYy8jtY=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=jdPpcvJ1oWlz0Wq05IPkOgbt38ecXG6kQ4IhNQoVqAdOSvr12JET/GzCqokC90lvW v3+o8iVLck+ml3c22ucYwz1ZWZMhjXdpf3zelgUj/j31kuK9D4T2dLFtJGVaY4FomP Ybws0FIM7800WMp+ad8NW3J52v9fSttO6gkxhYME= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by sourceware.org (Postfix) with ESMTPS id C4D9C3860771 for ; Thu, 13 Oct 2022 15:31:45 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org C4D9C3860771 Received: from mail-qt1-f198.google.com (mail-qt1-f198.google.com [209.85.160.198]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-31-t9QiBiuQMXCsxjT4YHgxcA-1; Thu, 13 Oct 2022 11:31:44 -0400 X-MC-Unique: t9QiBiuQMXCsxjT4YHgxcA-1 Received: by mail-qt1-f198.google.com with SMTP id g21-20020ac87d15000000b0035bb6f08778so1556106qtb.2 for ; Thu, 13 Oct 2022 08:31:44 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=subject:from:cc:to:content-language:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=3n7wwLBavjl1yOg6F6cTdgV7zfuhtOWvjc9sV3e9p+k=; b=InC4t0npHoswBijYKSYaDPfBQgdOvafhel58/+U46x78YG+aZa//JdAcNfkTYcjXxy +sBALrstwvA8DDgEd1pMKrz3uYbJNBErNalU89aZhQSL2edf+D+8O/rS5nUNMQYc6BzR vcASm9z94WhBadOb23dQ50AUmYnreq50xZCR62MUFIwsnkvVsBq47YTpJbWbrrF7J7IX t2OkMEJixFu0+UOnct1RbFqgea4a2m0TwGI5AHs0gcqJAG0yWVdXPNa/JmKl83n6RpAj mm22h9hNrhT27C3mmCGDsW3s2+tkQHhfqqe9crfCPcVUY5unDlyOOCjc5nXgb0Thpvxk CCqw== X-Gm-Message-State: ACrzQf1J3XOw9CuRFG4cCPG1JgVJdTG9GqC6K26JUF2FazBaI7/aqWaN wc7RiI4RGcAHMqhymjknXYxhPEdwAkHHOUonPDHYNNEPmDTuTSo+CmLUsIN6Eouus/YpGwn+kCR Ux1MkMVBIV9PQJdZszBIXwGuvIiWx4xbrFqSY/2/jalbqGFvdChgznfChofScI6hEldheSw== X-Received: by 2002:a05:6214:29ef:b0:4b4:5d8c:637c with SMTP id jv15-20020a05621429ef00b004b45d8c637cmr164015qvb.77.1665675102836; Thu, 13 Oct 2022 08:31:42 -0700 (PDT) X-Google-Smtp-Source: AMsMyM4DiyVWWkB3/UV6JVt9z9qlSlrWIjm8q42DopHMqjSMmIM8X8EUwPcs/oyWJQ52lIlSx30oug== X-Received: by 2002:a05:6214:29ef:b0:4b4:5d8c:637c with SMTP id jv15-20020a05621429ef00b004b45d8c637cmr163989qvb.77.1665675102525; Thu, 13 Oct 2022 08:31:42 -0700 (PDT) Received: from ?IPV6:2607:fea8:a263:f600::50d4? ([2607:fea8:a263:f600::50d4]) by smtp.gmail.com with ESMTPSA id j4-20020a05620a410400b006eea4b5abcesm4172552qko.89.2022.10.13.08.31.41 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 13 Oct 2022 08:31:41 -0700 (PDT) Message-ID: <8fef9e41-6f71-c3d8-09b9-419201b6c9e7@redhat.com> Date: Thu, 13 Oct 2022 11:31:40 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.2.1 To: gcc-patches Subject: [COMMITTED 4/4] PR tree-optimization/102540 - propagate partial equivs in the cache. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-11.7 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_NONE, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Andrew MacLeod via Gcc-patches From: Andrew MacLeod Reply-To: Andrew MacLeod Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" Rangers on entry cache propagation already evaluates equivalences when calculating values. This patch also allows it to work with partial equivalences, and if the bit sizes are compatible, make use of those ranges as well. It attempts to be conservative, so should be safe. This resolves regressions in both PR 102540 and PR 102872. Bootstrapped on x86_64-pc-linux-gnu with no regressions.  Pushed Andrew From 6cc3394507a2303a18891d34222c53f679256c37 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Wed, 5 Oct 2022 10:42:07 -0400 Subject: [PATCH 4/4] propagate partial equivs in the cache. Adjust on-entry cache propagation to look for and propagate both full and partial equivalences. gcc/ PR tree-optimization/102540 PR tree-optimization/102872 * gimple-range-cache.cc (ranger_cache::fill_block_cache): Handle partial equivs. (ranger_cache::range_from_dom): Cleanup dump output. gcc/testsuite/ * gcc.dg/pr102540.c: New. * gcc.dg/pr102872.c: New. --- gcc/gimple-range-cache.cc | 37 +++++++++++++++++++++++++++------ gcc/testsuite/gcc.dg/pr102540.c | 19 +++++++++++++++++ gcc/testsuite/gcc.dg/pr102872.c | 16 ++++++++++++++ 3 files changed, 66 insertions(+), 6 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/pr102540.c create mode 100644 gcc/testsuite/gcc.dg/pr102872.c diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index 8c80ba6cd14..0b9aa3639c5 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -1189,8 +1189,9 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) { edge_iterator ei; edge e; - Value_Range block_result (TREE_TYPE (name)); - Value_Range undefined (TREE_TYPE (name)); + tree type = TREE_TYPE (name); + Value_Range block_result (type); + Value_Range undefined (type); // At this point we shouldn't be looking at the def, entry or exit block. gcc_checking_assert (bb != def_bb && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) && @@ -1221,10 +1222,16 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) if (m_oracle) { tree equiv_name; - FOR_EACH_EQUIVALENCE (m_oracle, bb, name, equiv_name) + relation_kind rel; + int prec = TYPE_PRECISION (type); + FOR_EACH_PARTIAL_AND_FULL_EQUIV (m_oracle, bb, name, equiv_name, rel) { basic_block equiv_bb = gimple_bb (SSA_NAME_DEF_STMT (equiv_name)); + // Ignore partial equivs that are smaller than this object. + if (rel != VREL_EQ && prec > pe_to_bits (rel)) + continue; + // Check if the equiv has any ranges calculated. if (!m_gori.has_edge_range_p (equiv_name)) continue; @@ -1234,16 +1241,32 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) (equiv_bb && !dominated_by_p (CDI_DOMINATORS, bb, equiv_bb))) continue; + if (DEBUG_RANGE_CACHE) + { + if (rel == VREL_EQ) + fprintf (dump_file, "Checking Equivalence ("); + else + fprintf (dump_file, "Checking Partial equiv ("); + print_relation (dump_file, rel); + fprintf (dump_file, ") "); + print_generic_expr (dump_file, equiv_name, TDF_SLIM); + fprintf (dump_file, "\n"); + } Value_Range equiv_range (TREE_TYPE (equiv_name)); if (range_from_dom (equiv_range, equiv_name, bb, RFD_READ_ONLY)) { + if (rel != VREL_EQ) + range_cast (equiv_range, type); if (block_result.intersect (equiv_range)) { if (DEBUG_RANGE_CACHE) { - fprintf (dump_file, "Equivalence update! : "); + if (rel == VREL_EQ) + fprintf (dump_file, "Equivalence update! : "); + else + fprintf (dump_file, "Partial equiv update! : "); print_generic_expr (dump_file, equiv_name, TDF_SLIM); - fprintf (dump_file, "had range : "); + fprintf (dump_file, " has range : "); equiv_range.dump (dump_file); fprintf (dump_file, " refining range to :"); block_result.dump (dump_file); @@ -1458,7 +1481,9 @@ ranger_cache::range_from_dom (vrange &r, tree name, basic_block start_bb, if (DEBUG_RANGE_CACHE) { - fprintf (dump_file, "CACHE: BB %d DOM query, found ", start_bb->index); + fprintf (dump_file, "CACHE: BB %d DOM query for ", start_bb->index); + print_generic_expr (dump_file, name, TDF_SLIM); + fprintf (dump_file, ", found "); r.dump (dump_file); if (bb) fprintf (dump_file, " at BB%d\n", bb->index); diff --git a/gcc/testsuite/gcc.dg/pr102540.c b/gcc/testsuite/gcc.dg/pr102540.c new file mode 100644 index 00000000000..c12f8fcebfb --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr102540.c @@ -0,0 +1,19 @@ +/* { dg-do compile } */ +/* { dg-options "-O3 -fdump-tree-evrp" } */ + + +void kill(); + +static long a; +static unsigned b; +int test1 () { + long c, e; + c = b = a; + e = c ? 2 / (c + 1) : 0; + if (e && !b) + kill (); + a = 0; +} + +/* { dg-final { scan-tree-dump-not "kill" "evrp" } } */ + diff --git a/gcc/testsuite/gcc.dg/pr102872.c b/gcc/testsuite/gcc.dg/pr102872.c new file mode 100644 index 00000000000..971bb03a5a7 --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr102872.c @@ -0,0 +1,16 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-evrp" } */ + +void foo(void); + +static int a, b; +int main() { + for (; a; ++a) { + unsigned short d = a; + if (!(b | d) && d) + foo(); + } +} + +/* { dg-final { scan-tree-dump-not "foo" "evrp" } } */ + -- 2.37.3