From patchwork Wed May 24 21:19:07 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1785867 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=heApfGz4; 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 4QRPG15zC2z20Q0 for ; Thu, 25 May 2023 07:19:36 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id D1FD7385735A for ; Wed, 24 May 2023 21:19:34 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org D1FD7385735A DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1684963174; bh=VXZ2+Hza/5Cvula+mMPCpMRmpJKae8Td0zd0psgVBUc=; h=Date:To:Cc:Subject:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=heApfGz4uuqKM5ZdrOi2nLn7dTtdXKqx2nqcfrwI3bBwU8a8gH51ggGR+wzp3ROgU s6JcfjvzkGLLlxxa6G+SFvnt37grzl7Rte7kBLABHwL7UQWc4o2pz3cMv6FbM04sdd rJ7JnDr6q/muM7ObRUFYeCa4URL0Y6uYGbFJjoUA= 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 69A383857710 for ; Wed, 24 May 2023 21:19:13 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 69A383857710 Received: from mail-qv1-f72.google.com (mail-qv1-f72.google.com [209.85.219.72]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-101-F5tlERoaNeOMQUk6cPLZ3Q-1; Wed, 24 May 2023 17:19:10 -0400 X-MC-Unique: F5tlERoaNeOMQUk6cPLZ3Q-1 Received: by mail-qv1-f72.google.com with SMTP id 6a1803df08f44-6238a4e544bso2759966d6.0 for ; Wed, 24 May 2023 14:19:10 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684963150; x=1687555150; 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=Iq4ame4ESPjJh95Ow3MB6rTmT8xifHJMgV2IUAIVC3c=; b=idvofVWrP8CrOUc1M/QG4LqdO39YfgD/S70t2CN2yKd20FueVZqcpSkyCC4Td7sGqC orlnHQEQUsgZmBo25KuaIehT975IrFuLcnxiV6XIcgU8ajkOtmONnwt3GEtri8N1+Al0 z7Ng0TzFr9yBkMNynTDGaKD+IZBeLC2SxL3bswSUtDaMlvlyvK51ujR4zGOCtupnHHgp r3RyRLzZiLQiHGZz5zpslZDeRHqK3gTogYo0YbM4DkkMVa+1GgQ3FdIEb2QX5DP9gVg2 pYy9w7B9yGINLd7ONheqCGGhw00xnqfB3Kpb+N1qRg5+il/NFoI2v30Apk2TFclotLXU 5Ceg== X-Gm-Message-State: AC+VfDzdVpXpzyvfVyhgtWwaO7d/yA2QdSmTjYGOuYmP4V0HklCIJk8u MVXnJxEbz+O99FGF6rsdifID3kbDbdhxempZ54GMnB0tp+yekAYVbMhdWtLNe3sAt4BpXXudcot c2lj2AMErLd85Rjztv1TqTryIqNqKsDqKXxYlgDVW8mFGfTXrwJafFRWcn7HklFDknaRJwNJvr3 mNgA== X-Received: by 2002:a05:6214:21a7:b0:5cd:1adc:30e2 with SMTP id t7-20020a05621421a700b005cd1adc30e2mr28891514qvc.11.1684963149852; Wed, 24 May 2023 14:19:09 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ7qKDvTFC1mmRKbKO9OEwKGf88wHtmUDWX5izy7N8F37u1OyhOHGmlWNnbDlMfy3iK5YACtlQ== X-Received: by 2002:a05:6214:21a7:b0:5cd:1adc:30e2 with SMTP id t7-20020a05621421a700b005cd1adc30e2mr28891492qvc.11.1684963149523; Wed, 24 May 2023 14:19:09 -0700 (PDT) Received: from ?IPV6:2607:fea8:51df:4200::933? ([2607:fea8:51df:4200::933]) by smtp.gmail.com with ESMTPSA id p7-20020a0cf687000000b006238cf6d2a8sm3890646qvn.2.2023.05.24.14.19.08 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 24 May 2023 14:19:09 -0700 (PDT) Message-ID: Date: Wed, 24 May 2023 17:19:07 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.11.0 To: gcc-patches Cc: "hernandez, aldy" Subject: [COMMITTED 1/4] - Make ssa_cache and ssa_lazy_cache virtual. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-11.9 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_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Andrew MacLeod via Gcc-patches From: Andrew MacLeod Reply-To: Andrew MacLeod Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" I originally implemented the lazy ssa cache by inheriting from an ssa_cache in protected mode and providing the required routines. This makes it a little awkward to do various things, and they also become not quite as interchangeable as I'd like.   Making the routines virtual and using proper inheritance will avoid an inevitable issue down the road, and allows me to remove the printing hack which provided a protected output routine. Overall performance impact is pretty negligible, so lets just clean it up. Bootstraps on x86_64-pc-linux-gnu  with no regressions.  Pushed. Andrew From 3079056d0b779b907f8adc01d48a8aa495b8a661 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Wed, 24 May 2023 08:49:30 -0400 Subject: [PATCH 1/4] Make ssa_cache and ssa_lazy_cache virtual. Making them virtual allows us to interchangebly use the caches. * gimple-range-cache.cc (ssa_cache::dump): Use get_range. (ssa_cache::dump_range_query): Delete. (ssa_lazy_cache::dump_range_query): Delete. (ssa_lazy_cache::get_range): Move from header file. (ssa_lazy_cache::clear_range): ditto. (ssa_lazy_cache::clear): Ditto. * gimple-range-cache.h (class ssa_cache): Virtualize. (class ssa_lazy_cache): Inherit and virtualize. --- gcc/gimple-range-cache.cc | 43 +++++++++++++++++++++++++++------------ gcc/gimple-range-cache.h | 37 ++++++++++----------------------- 2 files changed, 41 insertions(+), 39 deletions(-) diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index e069241bc9d..f25abaffd34 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -626,7 +626,7 @@ ssa_cache::dump (FILE *f) // Invoke dump_range_query which is a private virtual version of // get_range. This avoids performance impacts on general queries, // but allows sharing of the dump routine. - if (dump_range_query (r, ssa_name (x)) && !r.varying_p ()) + if (get_range (r, ssa_name (x)) && !r.varying_p ()) { if (print_header) { @@ -648,23 +648,14 @@ ssa_cache::dump (FILE *f) fputc ('\n', f); } -// Virtual private get_range query for dumping. +// Return true if NAME has an active range in the cache. bool -ssa_cache::dump_range_query (vrange &r, tree name) const +ssa_lazy_cache::has_range (tree name) const { - return get_range (r, name); + return bitmap_bit_p (active_p, SSA_NAME_VERSION (name)); } -// Virtual private get_range query for dumping. - -bool -ssa_lazy_cache::dump_range_query (vrange &r, tree name) const -{ - return get_range (r, name); -} - - // Set range of NAME to R in a lazy cache. Return FALSE if it did not already // have a range. @@ -684,6 +675,32 @@ ssa_lazy_cache::set_range (tree name, const vrange &r) return false; } +// Return TRUE if NAME has a range, and return it in R. + +bool +ssa_lazy_cache::get_range (vrange &r, tree name) const +{ + if (!bitmap_bit_p (active_p, SSA_NAME_VERSION (name))) + return false; + return ssa_cache::get_range (r, name); +} + +// Remove NAME from the active range list. + +void +ssa_lazy_cache::clear_range (tree name) +{ + bitmap_clear_bit (active_p, SSA_NAME_VERSION (name)); +} + +// Remove all ranges from the active range list. + +void +ssa_lazy_cache::clear () +{ + bitmap_clear (active_p); +} + // -------------------------------------------------------------------------- diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h index 871255a8116..4fc98230430 100644 --- a/gcc/gimple-range-cache.h +++ b/gcc/gimple-range-cache.h @@ -57,14 +57,13 @@ class ssa_cache public: ssa_cache (); ~ssa_cache (); - bool has_range (tree name) const; - bool get_range (vrange &r, tree name) const; - bool set_range (tree name, const vrange &r); - void clear_range (tree name); - void clear (); + virtual bool has_range (tree name) const; + virtual bool get_range (vrange &r, tree name) const; + virtual bool set_range (tree name, const vrange &r); + virtual void clear_range (tree name); + virtual void clear (); void dump (FILE *f = stderr); protected: - virtual bool dump_range_query (vrange &r, tree name) const; vec m_tab; vrange_allocator *m_range_allocator; }; @@ -72,35 +71,21 @@ protected: // This is the same as global cache, except it maintains an active bitmap // rather than depending on a zero'd out vector of pointers. This is better // for sparsely/lightly used caches. -// It could be made a fully derived class, but at this point there doesnt seem -// to be a need to take the performance hit for it. -class ssa_lazy_cache : protected ssa_cache +class ssa_lazy_cache : public ssa_cache { public: inline ssa_lazy_cache () { active_p = BITMAP_ALLOC (NULL); } inline ~ssa_lazy_cache () { BITMAP_FREE (active_p); } - bool set_range (tree name, const vrange &r); - inline bool get_range (vrange &r, tree name) const; - inline void clear_range (tree name) - { bitmap_clear_bit (active_p, SSA_NAME_VERSION (name)); } ; - inline void clear () { bitmap_clear (active_p); } - inline void dump (FILE *f = stderr) { ssa_cache::dump (f); } + virtual bool has_range (tree name) const; + virtual bool set_range (tree name, const vrange &r); + virtual bool get_range (vrange &r, tree name) const; + virtual void clear_range (tree name); + virtual void clear (); protected: - virtual bool dump_range_query (vrange &r, tree name) const; bitmap active_p; }; -// Return TRUE if NAME has a range, and return it in R. - -bool -ssa_lazy_cache::get_range (vrange &r, tree name) const -{ - if (!bitmap_bit_p (active_p, SSA_NAME_VERSION (name))) - return false; - return ssa_cache::get_range (r, name); -} - // This class provides all the caches a global ranger may need, and makes // them available for gori-computes to query so outgoing edges can be // properly calculated. -- 2.40.1 From patchwork Wed May 24 21:19:21 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1785870 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=8.43.85.97; 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=PL8SUS5O; dkim-atps=neutral Received: from sourceware.org (ip-8-43-85-97.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4QRPHC0SZSz20Pb for ; Thu, 25 May 2023 07:20:39 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id E69EA384D193 for ; Wed, 24 May 2023 21:20:34 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org E69EA384D193 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1684963234; bh=23WmnUHFrwoYvA2oTx4PYQVO0WFaSEXi5M4OVa2UmTA=; h=Date:To:Cc:Subject:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=PL8SUS5OrA1lbOU8Al1ZsOne4YLSsTxs8GSri7VbsrEp1Kfkaw1QQEemdtoopmVUn aE57VL484iqMX4seHx8ecHSMf2Jp/PxuXUOOT/Qun3ivg9D/9LJGTFt7hqfCjbRQC0 +xIF2P2ODJqCgfO8A5pftBrgbaG0bxMGd0U1FSIs= 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 596933857343 for ; Wed, 24 May 2023 21:19:28 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 596933857343 Received: from mail-qv1-f70.google.com (mail-qv1-f70.google.com [209.85.219.70]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-166-hBeINsmePLOjXU08TB3Xeg-1; Wed, 24 May 2023 17:19:24 -0400 X-MC-Unique: hBeINsmePLOjXU08TB3Xeg-1 Received: by mail-qv1-f70.google.com with SMTP id 6a1803df08f44-6240a60181dso2589446d6.0 for ; Wed, 24 May 2023 14:19:24 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684963163; x=1687555163; 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=LO1Vafa56bb9ZL5nD2r3XeEA1usRx8y5+Ip5BXYQk6k=; b=WL8VCQXbK271tg+RyXA313zrhXVaGQmUKVD7ia+pv5EnupCTdwrTyLWXVIPVHz3IUz ldRxB6HeP0uWk605Bq0p4FQAXdtxTWnMTHwbZ7qi9XrSU0YfyDvsdNnyXRNleJMSRAPi yMBrNPQ16yKdbmEu1PSTbUO/tTa0LMbBxR5/y7gU4A29jLPm0NvDCCQkEZzZt8sxlAqV qhECjYkrDlLkjnaWgANnJ8b3rguQk5T2kSZHU9PMOJToxfd1Uf2edM8c+VGyWOQwO5cC ZWYG77G0yeeBcjMgmo5LcLPw2RUhjHl1SpWyzk4MLd/6yPgnnZTcTy2ZZ7lcKvFLc3c3 DHug== X-Gm-Message-State: AC+VfDxi23KFxHDNmbYF4ojCxDJIj44cCYvJEoUAwGVoCu+6AnHBLyYX +yizBvMbPqI5XEtQp2F0v8rXR5kUm9K+RxmLhqpDpJzeo/m1U+ALU/htANWjdQn5lT7F8zlS/Qb yLDPTiazw0ZPmYaGn68Iwj7GeQP/s2yQ4e1F9lKzKAKOLKyWKK7mqwS+SP9LfeREii+a+d8CzMf /mHw== X-Received: by 2002:a05:6214:29e9:b0:623:42c5:612f with SMTP id jv9-20020a05621429e900b0062342c5612fmr24039131qvb.49.1684963163197; Wed, 24 May 2023 14:19:23 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ5gDK0za9m4IcVaBU8eTpyi61XbV5Up0dJ32lSLCCnmhBO7Cjx5OZpproi6NxgG1Qs7vlTJwg== X-Received: by 2002:a05:6214:29e9:b0:623:42c5:612f with SMTP id jv9-20020a05621429e900b0062342c5612fmr24039104qvb.49.1684963162752; Wed, 24 May 2023 14:19:22 -0700 (PDT) Received: from ?IPV6:2607:fea8:51df:4200::933? ([2607:fea8:51df:4200::933]) by smtp.gmail.com with ESMTPSA id qd14-20020ad4480e000000b00625b4eb9126sm374204qvb.10.2023.05.24.14.19.21 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 24 May 2023 14:19:22 -0700 (PDT) Message-ID: <5490c9c6-d4ea-a4f4-1718-238ef3caf9f5@redhat.com> Date: Wed, 24 May 2023 17:19:21 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.11.0 To: gcc-patches Cc: "hernandez, aldy" Subject: [COMMITTED 2/4] - Make ssa_cache a range_query. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-12.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, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Andrew MacLeod via Gcc-patches From: Andrew MacLeod Reply-To: Andrew MacLeod Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" By having an ssa_cache inherit from a range_query, and then providing a range_of_expr routine which returns the current global value, we open up the possibility of folding statements and doing other interesting things with an ssa-cache. In particular, you can now call fold_range()  with an ssa-range cache and fold a stmt by retrieving the values which are stored in the cache. This patch also provides a ranger object with a  const_query() method which will allow access to the current global ranges ranger knows for folding.   There are times where we use get_global_range_query(), but we'd actually get more accuarte results if we have a ranger and use const_query ().    const_query should be  a superset of what get_global_range_query knows. There is 0 performance impact. Bootstraps on x86_64-pc-linux-gnu  with no regressions.  Pushed. Andrew From be6e6b93cc5d42a09a1f2be26dfdf7e3f897d296 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Wed, 24 May 2023 09:06:26 -0400 Subject: [PATCH 2/4] Make ssa_cache a range_query. By providing range_of_expr as a range_query, we can fold and do other interesting things using values from the global table. Make ranger's knonw globals available via const_query. * gimple-range-cache.cc (ssa_cache::range_of_expr): New. * gimple-range-cache.h (class ssa_cache): Inherit from range_query. (ranger_cache::const_query): New. * gimple-range.cc (gimple_ranger::const_query): New. * gimple-range.h (gimple_ranger::const_query): New prototype. --- gcc/gimple-range-cache.cc | 14 ++++++++++++++ gcc/gimple-range-cache.h | 5 ++++- gcc/gimple-range.cc | 8 ++++++++ gcc/gimple-range.h | 1 + 4 files changed, 27 insertions(+), 1 deletion(-) diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index f25abaffd34..52165d2405b 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -545,6 +545,20 @@ ssa_cache::~ssa_cache () delete m_range_allocator; } +// Enable a query to evaluate staements/ramnges based on picking up ranges +// from just an ssa-cache. + +bool +ssa_cache::range_of_expr (vrange &r, tree expr, gimple *stmt) +{ + if (!gimple_range_ssa_p (expr)) + return get_tree_range (r, expr, stmt); + + if (!get_range (r, expr)) + gimple_range_global (r, expr, cfun); + return true; +} + // Return TRUE if the global range of NAME has a cache entry. bool diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h index 4fc98230430..afcf8d7de7b 100644 --- a/gcc/gimple-range-cache.h +++ b/gcc/gimple-range-cache.h @@ -52,7 +52,7 @@ private: // has been visited during this incarnation. Once the ranger evaluates // a name, it is typically not re-evaluated again. -class ssa_cache +class ssa_cache : public range_query { public: ssa_cache (); @@ -63,6 +63,8 @@ public: virtual void clear_range (tree name); virtual void clear (); void dump (FILE *f = stderr); + virtual bool range_of_expr (vrange &r, tree expr, gimple *stmt); + protected: vec m_tab; vrange_allocator *m_range_allocator; @@ -103,6 +105,7 @@ public: bool get_global_range (vrange &r, tree name) const; bool get_global_range (vrange &r, tree name, bool ¤t_p); void set_global_range (tree name, const vrange &r, bool changed = true); + range_query &const_query () { return m_globals; } void propagate_updated_value (tree name, basic_block bb); diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc index 4fae3f95e6a..01e62d3ff39 100644 --- a/gcc/gimple-range.cc +++ b/gcc/gimple-range.cc @@ -70,6 +70,14 @@ gimple_ranger::~gimple_ranger () m_stmt_list.release (); } +// Return a range_query which accesses just the known global values. + +range_query & +gimple_ranger::const_query () +{ + return m_cache.const_query (); +} + bool gimple_ranger::range_of_expr (vrange &r, tree expr, gimple *stmt) { diff --git a/gcc/gimple-range.h b/gcc/gimple-range.h index e3aa9475f5e..6587e4923ff 100644 --- a/gcc/gimple-range.h +++ b/gcc/gimple-range.h @@ -64,6 +64,7 @@ public: bool fold_stmt (gimple_stmt_iterator *gsi, tree (*) (tree)); void register_inferred_ranges (gimple *s); void register_transitive_inferred_ranges (basic_block bb); + range_query &const_query (); protected: bool fold_range_internal (vrange &r, gimple *s, tree name); void prefill_name (vrange &r, tree name); -- 2.40.1 From patchwork Wed May 24 21:19:39 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1785868 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=BHt3XVwL; 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 4QRPGc4sNBz20Q1 for ; Thu, 25 May 2023 07:20:08 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id AB207386D634 for ; Wed, 24 May 2023 21:20:06 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org AB207386D634 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1684963206; bh=J5Ly9c6LEUXvvkQckx+S1qVDcqIidexUrzs0unllPUo=; h=Date:To:Cc:Subject:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=BHt3XVwLRVxOSwliRP8vUctKTG/1IigliCwcT41YGzH3vDibZRZWiQttikjVNx6J+ 1tKS/NlZelYAkbtsZqTkOjlguLn65oRMR018WILTg0CVKWIM+zA1UuJ2icT4RnNubz EYkY3fmEPE44XhnVLNR8SiTodHmKv3j4x68P3wL8= 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 177A8385E003 for ; Wed, 24 May 2023 21:19:44 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 177A8385E003 Received: from mail-qk1-f199.google.com (mail-qk1-f199.google.com [209.85.222.199]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-369-XLbtrSwdOK-PJqq81DSAng-1; Wed, 24 May 2023 17:19:42 -0400 X-MC-Unique: XLbtrSwdOK-PJqq81DSAng-1 Received: by mail-qk1-f199.google.com with SMTP id af79cd13be357-75b03d12d38so31807785a.2 for ; Wed, 24 May 2023 14:19:42 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684963181; x=1687555181; 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=Jfo5+J5EGeH1JfUalKqkVQVtHiDWvMUJ9Fn3sUWDc9c=; b=g7RxTf6ucsAgik7M8Lmh5A9Pc7P16wNj8ER4zJ4OzqImXumu3ETXP1hKDpCkjEaU/L EuQ4ZFAq4v55WeuX6rMdam/t/h4dB/hX3l02Yqa/HI+TAYmJPGMzjgRnDhASKc+m+kuT vErFAxIny+UOIvYnoycc0g3DzXcVWCR1Hqs41FHol7BOR5pDZzf2I11rZkZ4sZN4JeEB MWzVehKDf71+v5zX/Af7xN3pHh/V2oPutagGIGYMKTq1rhWaB0n03oiRbwMrscmlBANG ZBz9fJJJR/o0Yujcf6coIqq70/Mh8f5r5Fiy0vwrc6tQRF9rme15cacfAO1mlZ8nBSGn muEQ== X-Gm-Message-State: AC+VfDzWKqO952ujMZrpHyXAPgUusQ6Cf5nsXoAorkO/Eu9ePuADXnsi MDaRxoYbQ6/5ub7m8SdE6RMVd7WYbSByLNjZoMUWDkUu/tel+Tof7OMH2BGQ0OBoJ6OPNK/64eA DGEV1zqBUhvFREuAENnqdNhL84G4qdCz/aerj1MP3gnbCsx5EPO9BnYJpeM/z8DTzEHmBsYppyp 9cdw== X-Received: by 2002:a05:620a:6285:b0:75b:23a1:3676 with SMTP id ov5-20020a05620a628500b0075b23a13676mr8685504qkn.55.1684963181283; Wed, 24 May 2023 14:19:41 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ4FVMiB9Ow+2nva3hDg2jganiyPq3iWJXeugWbOXXWQTnDT6oG7ypAoaWRaxCdC3DdCbZycwA== X-Received: by 2002:a05:620a:6285:b0:75b:23a1:3676 with SMTP id ov5-20020a05620a628500b0075b23a13676mr8685491qkn.55.1684963180963; Wed, 24 May 2023 14:19:40 -0700 (PDT) Received: from ?IPV6:2607:fea8:51df:4200::933? ([2607:fea8:51df:4200::933]) by smtp.gmail.com with ESMTPSA id c2-20020a05620a11a200b007578622c861sm785402qkk.108.2023.05.24.14.19.40 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 24 May 2023 14:19:40 -0700 (PDT) Message-ID: <92f97ed8-6149-21c7-731e-0b618667f33c@redhat.com> Date: Wed, 24 May 2023 17:19:39 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.11.0 To: gcc-patches Cc: "hernandez, aldy" Subject: [COMMITTED 3/4] Provide relation queries for a stmt. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-12.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, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Andrew MacLeod via Gcc-patches From: Andrew MacLeod Reply-To: Andrew MacLeod Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" This tweaks someof the fold_stmt routines and helpers.. in particular the ones which you provide a vector of ranges to to satisfy any ssa-names. Previously, once the vector was depleted, any remaining values were picked up from the default get_global_range_query() query. It is useful to be able to speiocyf your own range_query to these routines, as most fo the other fold_stmt routines allow. This patch changes it so the default doesnt change, but you can optionally specify your own range_query to the routines. It also provides a new routine:     relation_trio fold_relations (gimple *s, range_query *q) Which instead of folding a stmt, will return a relation trio based on folding the stmt with the range_query.  The relation trio will let you know if the statement causes a relation between LHS-OP1,  LHS_OP2, or OP1_OP2...  so for something like    a_3 = b_4 + 6 based on known ranges and types, we might get back (LHS  > OP1) It just provides  a generic interface into what relations a statement may provide based on what a range_query returns for values and the stmt itself. There is no performance impact. Bootstraps on x86_64-pc-linux-gnu  with no regressions.  Pushed. Andrew From 933e14dc613269641ffe3613bf4792ac50590275 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Wed, 24 May 2023 09:17:32 -0400 Subject: [PATCH 3/4] Provide relation queries for a stmt. Allow fur_list and fold_stmt to be provided a range_query rather than always defaultsing to NULL (which becomes a global query). Also provide a fold_relations () routine which can provide a range_trio for an arbitrary statement using any range_query * gimple-range-fold.cc (fur_list::fur_list): Add range_query param to contructors. (fold_range): Add range_query parameter. (fur_relation::fur_relation): New. (fur_relation::trio): New. (fur_relation::register_relation): New. (fold_relations): New. * gimple-range-fold.h (fold_range): Adjust prototypes. (fold_relations): New. --- gcc/gimple-range-fold.cc | 128 +++++++++++++++++++++++++++++++++++---- gcc/gimple-range-fold.h | 11 +++- 2 files changed, 124 insertions(+), 15 deletions(-) diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc index 96cbd799488..4df065c8a6e 100644 --- a/gcc/gimple-range-fold.cc +++ b/gcc/gimple-range-fold.cc @@ -214,9 +214,9 @@ fur_depend::register_relation (edge e, relation_kind k, tree op1, tree op2) class fur_list : public fur_source { public: - fur_list (vrange &r1); - fur_list (vrange &r1, vrange &r2); - fur_list (unsigned num, vrange **list); + fur_list (vrange &r1, range_query *q = NULL); + fur_list (vrange &r1, vrange &r2, range_query *q = NULL); + fur_list (unsigned num, vrange **list, range_query *q = NULL); virtual bool get_operand (vrange &r, tree expr) override; virtual bool get_phi_operand (vrange &r, tree expr, edge e) override; private: @@ -228,7 +228,7 @@ private: // One range supplied for unary operations. -fur_list::fur_list (vrange &r1) : fur_source (NULL) +fur_list::fur_list (vrange &r1, range_query *q) : fur_source (q) { m_list = m_local; m_index = 0; @@ -238,7 +238,7 @@ fur_list::fur_list (vrange &r1) : fur_source (NULL) // Two ranges supplied for binary operations. -fur_list::fur_list (vrange &r1, vrange &r2) : fur_source (NULL) +fur_list::fur_list (vrange &r1, vrange &r2, range_query *q) : fur_source (q) { m_list = m_local; m_index = 0; @@ -249,7 +249,8 @@ fur_list::fur_list (vrange &r1, vrange &r2) : fur_source (NULL) // Arbitrary number of ranges in a vector. -fur_list::fur_list (unsigned num, vrange **list) : fur_source (NULL) +fur_list::fur_list (unsigned num, vrange **list, range_query *q) + : fur_source (q) { m_list = list; m_index = 0; @@ -278,20 +279,20 @@ fur_list::get_phi_operand (vrange &r, tree expr, edge e ATTRIBUTE_UNUSED) // Fold stmt S into range R using R1 as the first operand. bool -fold_range (vrange &r, gimple *s, vrange &r1) +fold_range (vrange &r, gimple *s, vrange &r1, range_query *q) { fold_using_range f; - fur_list src (r1); + fur_list src (r1, q); return f.fold_stmt (r, s, src); } // Fold stmt S into range R using R1 and R2 as the first two operands. bool -fold_range (vrange &r, gimple *s, vrange &r1, vrange &r2) +fold_range (vrange &r, gimple *s, vrange &r1, vrange &r2, range_query *q) { fold_using_range f; - fur_list src (r1, r2); + fur_list src (r1, r2, q); return f.fold_stmt (r, s, src); } @@ -299,10 +300,11 @@ fold_range (vrange &r, gimple *s, vrange &r1, vrange &r2) // operands encountered. bool -fold_range (vrange &r, gimple *s, unsigned num_elements, vrange **vector) +fold_range (vrange &r, gimple *s, unsigned num_elements, vrange **vector, + range_query *q) { fold_using_range f; - fur_list src (num_elements, vector); + fur_list src (num_elements, vector, q); return f.fold_stmt (r, s, src); } @@ -326,6 +328,108 @@ fold_range (vrange &r, gimple *s, edge on_edge, range_query *q) return f.fold_stmt (r, s, src); } +// Provide a fur_source which can be used to determine any relations on +// a statement. It manages the callback from fold_using_ranges to determine +// a relation_trio for a statement. + +class fur_relation : public fur_stmt +{ +public: + fur_relation (gimple *s, range_query *q = NULL); + 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); + relation_trio trio() const; +private: + relation_kind def_op1, def_op2, op1_op2; +}; + +fur_relation::fur_relation (gimple *s, range_query *q) : fur_stmt (s, q) +{ + def_op1 = def_op2 = op1_op2 = VREL_VARYING; +} + +// Construct a trio from what is known. + +relation_trio +fur_relation::trio () const +{ + return relation_trio (def_op1, def_op2, op1_op2); +} + +// Don't support edges, but avoid a compiler warning by providing the routine. + +void +fur_relation::register_relation (edge, relation_kind, tree, tree) +{ +} + +// Register relation K between OP1 and OP2 on STMT. + +void +fur_relation::register_relation (gimple *stmt, relation_kind k, tree op1, + tree op2) +{ + tree lhs = gimple_get_lhs (stmt); + tree a1 = NULL_TREE; + tree a2 = NULL_TREE; + switch (gimple_code (stmt)) + { + case GIMPLE_COND: + a1 = gimple_cond_lhs (stmt); + a2 = gimple_cond_rhs (stmt); + break; + case GIMPLE_ASSIGN: + a1 = gimple_assign_rhs1 (stmt); + if (gimple_num_ops (stmt) >= 3) + a2 = gimple_assign_rhs2 (stmt); + break; + default: + break; + } + // STMT is of the form LHS = A1 op A2, now map the relation to these + // operands, if possible. + if (op1 == lhs) + { + if (op2 == a1) + def_op1 = k; + else if (op2 == a2) + def_op2 = k; + } + else if (op2 == lhs) + { + if (op1 == a1) + def_op1 = relation_swap (k); + else if (op1 == a2) + def_op2 = relation_swap (k); + } + else + { + if (op1 == a1 && op2 == a2) + op1_op2 = k; + else if (op2 == a1 && op1 == a2) + op1_op2 = relation_swap (k); + } +} + +// Return the relation trio for stmt S using query Q. + +relation_trio +fold_relations (gimple *s, range_query *q) +{ + fold_using_range f; + fur_relation src (s, q); + tree lhs = gimple_range_ssa_p (gimple_get_lhs (s)); + if (lhs) + { + Value_Range vr(TREE_TYPE (lhs)); + if (f.fold_stmt (vr, s, src)) + return src.trio (); + } + return TRIO_VARYING; +} + // ------------------------------------------------------------------------- // Adjust the range for a pointer difference where the operands came diff --git a/gcc/gimple-range-fold.h b/gcc/gimple-range-fold.h index 68c6d7743e9..939b7a76f0e 100644 --- a/gcc/gimple-range-fold.h +++ b/gcc/gimple-range-fold.h @@ -37,9 +37,14 @@ bool fold_range (vrange &v, gimple *s, edge on_edge, range_query *q = NULL); // These routines the operands to be specified when manually folding. // Any excess queries will be drawn from the current range_query. -bool fold_range (vrange &r, gimple *s, vrange &r1); -bool fold_range (vrange &r, gimple *s, vrange &r1, vrange &r2); -bool fold_range (vrange &r, gimple *s, unsigned num_elements, vrange **vector); +bool fold_range (vrange &r, gimple *s, vrange &r1, range_query *q = NULL); +bool fold_range (vrange &r, gimple *s, vrange &r1, vrange &r2, + range_query *q = NULL); +bool fold_range (vrange &r, gimple *s, unsigned num_elements, vrange **vector, + range_query *q = NULL); + +// This routine will return a relation trio for stmt S. +relation_trio fold_relations (gimple *s, range_query *q = NULL); // Return the type of range which statement S calculates. If the type is // unsupported or no type can be determined, return NULL_TREE. -- 2.40.1 From patchwork Wed May 24 21:19:52 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1785869 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=yuSYPPIc; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4QRPGv5j4Lz20Pb for ; Thu, 25 May 2023 07:20:23 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 25FF1383FBB2 for ; Wed, 24 May 2023 21:20:21 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 25FF1383FBB2 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1684963221; bh=a1J2z+RL4l/lgRkEHT8+qwWtPK52fFvUUTASkTyBgdc=; h=Date:Subject:To:Cc:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=yuSYPPIcy8L3bzbb/TqUb9adfMoUeui7psv1eTsFCsdIZsETkJuUnotkbT9+E5vSs 9ZMnmzsfHqFoKG13nQ/LcE7ECaT0SAHI6t9PIzfFfWL0x59Lq7To6qWWMODkOYKNgg EmPuD97FsAwJejR6OnwaKpHZvbrmwaQ18ZlHq8/I= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id 43CDF3857734 for ; Wed, 24 May 2023 21:19:59 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 43CDF3857734 Received: from mail-qv1-f72.google.com (mail-qv1-f72.google.com [209.85.219.72]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-330-gMktcfPGOD-FF_6yVVtCWA-1; Wed, 24 May 2023 17:19:55 -0400 X-MC-Unique: gMktcfPGOD-FF_6yVVtCWA-1 Received: by mail-qv1-f72.google.com with SMTP id 6a1803df08f44-62382e86f83so2639556d6.0 for ; Wed, 24 May 2023 14:19:55 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684963194; x=1687555194; h=content-language:cc:to:subject:from:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=E0P9tX2Cz7GFR0qXOcS8a2BjfJo2/t1JrPXhHSsAb4U=; b=Nen/D37miiu4NdHA5obAgVQv3bzrUqZh4wMRO0lMfKFl7GtyWkBNo1aqPAGH/x2pT8 VSqtwcBuNIKQDHzCeqLKGmgCKV4soPgwvCIj8JKUVEo7sdirgj/lZ0xshjRpf5/dXFTq ZkaavabQRoUbsjtQ4wxEyKblJj4rO6V01eel0eAaaJY+tP5Ed9CGzGVKJfZ8N+zhByZn lAkhqRijGsZABe5jVnyGWhYf0Vu8WPtB4bnpFWSkOEHS519mEJ4ig6K/RWFae8xDi83t oQuiIECQnd1BY0q1pjnuwPw2IkH56JSBjgELdXqOWvxFJiWTKb+kospKkOjp2y8+8STm F1uQ== X-Gm-Message-State: AC+VfDzVVMC+tVnE7iD6msjS0pu48H20XQcLUCJ7NhWSFYcfH8mXfoqQ UA0zMypdhzEksZyM6AsbKPS7zeLy8pxusPl1lS5UJ+8P4FF0bJm/2UbiNqSj5uIwBj205SJ+Uu/ 8zTsQ3KM7rElVosW1fL5eEtYWS2JJGRVucCG9qMFB31PO075EJ+B2Bfv6zmxHx67dZnUjA77qzX dfiA== X-Received: by 2002:a05:622a:28c:b0:3f4:f58d:d00d with SMTP id z12-20020a05622a028c00b003f4f58dd00dmr30511297qtw.40.1684963194392; Wed, 24 May 2023 14:19:54 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ6V+2mST+DX+G0K5HEhG8XNLiI6v4gsY+tpX+KzLfZDefa4DKY3NmkdG1njxZDqqlydopgWlw== X-Received: by 2002:a05:622a:28c:b0:3f4:f58d:d00d with SMTP id z12-20020a05622a028c00b003f4f58dd00dmr30511274qtw.40.1684963194001; Wed, 24 May 2023 14:19:54 -0700 (PDT) Received: from ?IPV6:2607:fea8:51df:4200::933? ([2607:fea8:51df:4200::933]) by smtp.gmail.com with ESMTPSA id lf19-20020a0562142cd300b0061b608dc4c1sm3871196qvb.94.2023.05.24.14.19.53 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 24 May 2023 14:19:53 -0700 (PDT) Message-ID: <6a24c0bf-aa0d-5e13-6852-705605db15ec@redhat.com> Date: Wed, 24 May 2023 17:19:52 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.11.0 Subject: [COMMITTED 4/4] - Gimple range PHI analyzer and testcases To: gcc-patches Cc: "hernandez, aldy" X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-10.4 required=5.0 tests=BAYES_00, BODY_8BITS, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_ASCII_DIVIDERS, KAM_SHORT, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Andrew MacLeod via Gcc-patches From: Andrew MacLeod Reply-To: Andrew MacLeod Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" This patch provide the framework for a gimple-range phi analyzer. Currently, the  primary purpose is to give better initial values for members of a "phi group" a PHI group is defined as a a group of PHI nodes whose arguments are all either members of the same PHI group, or one of 2 other values:  - An initializer, (typically a constant), but not necessarily,  - A modifier, which is always of the form:   member_ssa = member_ssa OP op2 When the analyzer finds a group which matches this pattern, it tries to evaluate the modifier using the initial value and project a range for the entire group. This initial version is fairly simplistic.  It looks for 2 things: 1) if there is a relation between LHS and the other ssa_name in the modifier, then we can project a range. ie,         a_3 = a_2 + 1 if there is a relation generated by the stmt which say a_3 > a_2, and the initial value is 0, we can project a range of [0, +INF] as the moifier will cause the value to always increase, and not wrap. Likewise, for a_3 = a_2 - 1,  we can project a range of [-INF, 0] based on the "<" relationship between a_3 and a_2. 2) If there is no relationship, then we use the initial range and "simulate" the modifier statement a set number of times looking to see if the value converges. Currently I have arbitrarily hard coded 10 attempts, but intend to change this down the road with a --param, as well as to perhaps influence it with any known values from SCEV regarding known iterations of the loop and possibly change it based on optimization levels. I also suspect something like one more than the number of bits in the type might help with any bitmasking tricks. Theres a lot of additinal things we can do to enhance this, but this framework provides a start.  These 2 initial evaluations fix 107822, and part of 107986.  There is about a 1.5% slowdown to VRP to invoke and utilize the analyzer in all 3 passes of VRP.  overall compile time is 0.06% slower. Bootstraps on x86_64-pc-linux-gnu  with no regressions.  Pushed. Andrew From 64e844c1182198e49d33f9fa138b9a782371225d Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Wed, 24 May 2023 09:52:26 -0400 Subject: [PATCH 4/4] Gimple range PHI analyzer and testcases Provide a PHI analyzer framework to provive better initial values for PHI nodes which formk groups with initial values and single statements which modify the PHI values in some predicatable way. PR tree-optimization/107822 PR tree-optimization/107986 gcc/ * Makefile.in (OBJS): Add gimple-range-phi.o. * gimple-range-cache.h (ranger_cache::m_estimate): New phi_analyzer pointer member. * gimple-range-fold.cc (fold_using_range::range_of_phi): Use phi_analyzer if no loop info is available. * gimple-range-phi.cc: New file. * gimple-range-phi.h: New file. * tree-vrp.cc (execute_ranger_vrp): Utililze a phi_analyzer. gcc/testsuite/ * gcc.dg/pr107822.c: New. * gcc.dg/pr107986-1.c: New. --- gcc/Makefile.in | 1 + gcc/gimple-range-cache.h | 2 + gcc/gimple-range-fold.cc | 27 ++ gcc/gimple-range-phi.cc | 518 ++++++++++++++++++++++++++++++ gcc/gimple-range-phi.h | 109 +++++++ gcc/testsuite/gcc.dg/pr107822.c | 20 ++ gcc/testsuite/gcc.dg/pr107986-1.c | 16 + gcc/tree-vrp.cc | 7 +- 8 files changed, 699 insertions(+), 1 deletion(-) create mode 100644 gcc/gimple-range-phi.cc create mode 100644 gcc/gimple-range-phi.h create mode 100644 gcc/testsuite/gcc.dg/pr107822.c create mode 100644 gcc/testsuite/gcc.dg/pr107986-1.c diff --git a/gcc/Makefile.in b/gcc/Makefile.in index bb63b5c501d..1d39e6dd3f8 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1454,6 +1454,7 @@ OBJS = \ gimple-range-gori.o \ gimple-range-infer.o \ gimple-range-op.o \ + gimple-range-phi.o \ gimple-range-trace.o \ gimple-ssa-backprop.o \ gimple-ssa-isolate-paths.o \ diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h index afcf8d7de7b..93d16294d2e 100644 --- a/gcc/gimple-range-cache.h +++ b/gcc/gimple-range-cache.h @@ -23,6 +23,7 @@ along with GCC; see the file COPYING3. If not see #include "gimple-range-gori.h" #include "gimple-range-infer.h" +#include "gimple-range-phi.h" // This class manages a vector of pointers to ssa_block ranges. It // provides the basis for the "range on entry" cache for all @@ -136,6 +137,7 @@ private: void exit_range (vrange &r, tree expr, basic_block bb, enum rfd_mode); bool edge_range (vrange &r, edge e, tree name, enum rfd_mode); + phi_analyzer *m_estimate; vec m_workback; class update_list *m_update; }; diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc index 4df065c8a6e..173d9f386c5 100644 --- a/gcc/gimple-range-fold.cc +++ b/gcc/gimple-range-fold.cc @@ -934,6 +934,7 @@ fold_using_range::range_of_phi (vrange &r, gphi *phi, fur_source &src) } } + bool loop_info_p = false; // If SCEV is available, query if this PHI has any known values. if (scev_initialized_p () && !POINTER_TYPE_P (TREE_TYPE (phi_def))) @@ -956,6 +957,32 @@ fold_using_range::range_of_phi (vrange &r, gphi *phi, fur_source &src) fprintf (dump_file, "\n"); } r.intersect (loop_range); + loop_info_p = true; + } + } + } + + if (!loop_info_p && phi_analysis_available_p () + && irange::supports_p (TREE_TYPE (phi_def))) + { + phi_group *g = (phi_analysis())[phi_def]; + if (g && !(g->range ().varying_p ())) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " PHI group range found for "); + print_generic_expr (dump_file, phi_def, TDF_SLIM); + fprintf (dump_file, ": "); + g->range ().dump (dump_file); + fprintf (dump_file, " and adjusted original range from :"); + r.dump (dump_file); + } + r.intersect (g->range ()); + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " to :"); + r.dump (dump_file); + fprintf (dump_file, "\n"); } } } diff --git a/gcc/gimple-range-phi.cc b/gcc/gimple-range-phi.cc new file mode 100644 index 00000000000..ffb4691d06b --- /dev/null +++ b/gcc/gimple-range-phi.cc @@ -0,0 +1,518 @@ +/* Gimple range phi analysis. + Copyright (C) 2023 Free Software Foundation, Inc. + Contributed by Andrew MacLeod . + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 3, or (at your option) +any later version. + +GCC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "insn-codes.h" +#include "tree.h" +#include "gimple.h" +#include "ssa.h" +#include "gimple-pretty-print.h" +#include "gimple-range.h" +#include "gimple-range-cache.h" +#include "value-range-storage.h" +#include "tree-cfg.h" +#include "target.h" +#include "attribs.h" +#include "gimple-iterator.h" +#include "gimple-walk.h" +#include "cfganal.h" + +// There can be only one running at a time. +static phi_analyzer *phi_analysis_object = NULL; + +// Initialize a PHI analyzer with range query Q. + +void +phi_analysis_initialize (range_query &q) +{ + gcc_checking_assert (!phi_analysis_object); + phi_analysis_object = new phi_analyzer (q); +} + +// Terminate the current PHI analyzer. if F is non-null, dump the tables + +void +phi_analysis_finalize () +{ + gcc_checking_assert (phi_analysis_object); + delete phi_analysis_object; + phi_analysis_object = NULL; +} + +// Return TRUE is there is a PHI analyzer operating. +bool +phi_analysis_available_p () +{ + return phi_analysis_object != NULL; +} + +// Return the phi analyzer object. + +phi_analyzer &phi_analysis () +{ + gcc_checking_assert (phi_analysis_object); + return *phi_analysis_object; +} + +// Initialize a phi_group from another group G. + +phi_group::phi_group (const phi_group &g) +{ + m_group = g.m_group; + m_initial_value = g.m_initial_value; + m_initial_edge = g.m_initial_edge; + m_modifier = g.m_modifier; + m_modifier_op = g.m_modifier_op; + m_vr = g.m_vr; +} + +// Create a new phi_group with members BM, initialvalue INIT_VAL, modifier +// statement MOD, and resolve values using query Q. +// Calculate the range for the gropup if possible, otherwise set it to +// VARYING. + +phi_group::phi_group (bitmap bm, tree init_val, edge e, gimple *mod, + range_query *q) +{ + // we dont expect a modifer and no inital value, so trap to have a look. + // perhaps they are dead cycles and we can just used UNDEFINED. + gcc_checking_assert (init_val); + + m_modifier_op = is_modifier_p (mod, bm); + m_group = bm; + m_initial_value = init_val; + m_initial_edge = e; + m_modifier = mod; + if (q->range_on_edge (m_vr, m_initial_edge, m_initial_value)) + { + // No modifier means the initial range is the full range. + // Otherwise try to calculate a range. + if (!m_modifier_op || calculate_using_modifier (q)) + return; + } + // Couldn't calculate a range, set to varying. + m_vr.set_varying (TREE_TYPE (init_val)); +} + +// Return 0 if S is not a modifier statment for group members BM. +// If it could be a modifier, return which operand position (1 or 2) +// the phi member occurs in. +unsigned +phi_group::is_modifier_p (gimple *s, const bitmap bm) +{ + if (!s) + return 0; + gimple_range_op_handler handler (s); + if (handler) + { + tree op1 = gimple_range_ssa_p (handler.operand1 ()); + tree op2 = gimple_range_ssa_p (handler.operand2 ()); + // Also disallow modifiers that have 2 ssa-names. + if (op1 && !op2 && bitmap_bit_p (bm, SSA_NAME_VERSION (op1))) + return 1; + else if (op2 && !op1 && bitmap_bit_p (bm, SSA_NAME_VERSION (op2))) + return 2; + } + return 0; +} + +// Calulcate the range of the phi group using range_query Q. + +bool +phi_group::calculate_using_modifier (range_query *q) +{ + // Look at the modifier for any relation + relation_trio trio = fold_relations (m_modifier, q); + relation_kind k = VREL_VARYING; + if (m_modifier_op == 1) + k = trio.lhs_op1 (); + else if (m_modifier_op == 2) + k = trio.lhs_op2 (); + else + return false; + + // If we can resolve the range using relations, use that range. + if (refine_using_relation (k, q)) + return true; + + // If the initial value is undefined, do not calculate a range. + if (m_vr.undefined_p ()) + return false; + + // Examine modifier and run X iterations to see if it convergences. + // The constructor initilaized m_vr to the initial value already. + int_range_max nv; + for (unsigned x = 0; x< 10; x++) + { + if (!fold_range (nv, m_modifier, m_vr, q)) + return false; + // If they are equal, then we have convergence. + if (nv == m_vr) + return true; + // Update range and try again. + m_vr.union_ (nv); + } + // Never converged, so bail for now. we could examine the pattern + // from m_initial to m_vr as an extension Especially if we had a way + // to project the actual number of iterations (SCEV?) + // + // We can also try to identify "parallel" phis to get loop counts and + // determine the number of iterations of these parallel PHIs. + // + return false; +} + + +// IF the modifier statement has a relation K between the modifier and the +// PHI member in it, we can project a range based on that. +// Use range_query Q to resolve values. +// ie, a_2 = PHI <0, a_3> and a_3 = a_2 + 1 +// if the relation a_3 > a_2 is present, the know the range is [0, +INF] + +bool +phi_group::refine_using_relation (relation_kind k, range_query *q) +{ + if (k == VREL_VARYING) + return false; + tree type = TREE_TYPE (m_initial_value); + // If the type wraps, then relations dont tell us much. + if (TYPE_OVERFLOW_WRAPS (type)) + return false; + + switch (k) + { + case VREL_LT: + case VREL_LE: + { + // Value always decreases. + int_range<2> lb; + int_range<2> ub; + if (!q->range_on_edge (ub, m_initial_edge, m_initial_value)) + break; + if (ub.undefined_p ()) + return false; + lb.set_varying (type); + m_vr.set (type, lb.lower_bound (), ub.upper_bound ()); + return true; + } + + case VREL_GT: + case VREL_GE: + { + // Value always increases. + int_range<2> lb; + int_range<2> ub; + if (!q->range_on_edge (lb, m_initial_edge, m_initial_value)) + break; + if (lb.undefined_p ()) + return false; + ub.set_varying (type); + m_vr.set (type, lb.lower_bound (), ub.upper_bound ()); + return true; + } + + // If its always equal, then its simply the initial value. + // which is what m_vr has already been set to. + case VREL_EQ: + return true; + + default: + break; + } + + return false; +} + +// Dump the information for a phi group to file F. + +void +phi_group::dump (FILE *f) +{ + unsigned i; + bitmap_iterator bi; + fprintf (f, "PHI GROUP <"); + + EXECUTE_IF_SET_IN_BITMAP (m_group, 0, i, bi) + { + print_generic_expr (f, ssa_name (i), TDF_SLIM); + fputc (' ',f); + } + + fprintf (f, ">\n - Initial value : "); + if (m_initial_value) + { + if (TREE_CODE (m_initial_value) == SSA_NAME) + print_gimple_stmt (f, SSA_NAME_DEF_STMT (m_initial_value), 0, TDF_SLIM); + else + print_generic_expr (f, m_initial_value, TDF_SLIM); + fprintf (f, " on edge %d->%d", m_initial_edge->src->index, + m_initial_edge->dest->index); + } + else + fprintf (f, "NONE"); + fprintf (f, "\n - Modifier : "); + if (m_modifier) + print_gimple_stmt (f, m_modifier, 0, TDF_SLIM); + else + fprintf (f, "NONE\n"); + fprintf (f, " - Range : "); + m_vr.dump (f); + fputc ('\n', f); +} + +// ------------------------------------------------------------------------- + +// Construct a phi analyzer which uses range_query G to pick up values. + +phi_analyzer::phi_analyzer (range_query &g) : m_global (g) +{ + m_work.create (0); + m_work.safe_grow (20); + + m_tab.create (0); +// m_tab.safe_grow_cleared (num_ssa_names + 100); + bitmap_obstack_initialize (&m_bitmaps); + m_simple = BITMAP_ALLOC (&m_bitmaps); + m_current = BITMAP_ALLOC (&m_bitmaps); +} + +// Destruct a PHI analyzer. + +phi_analyzer::~phi_analyzer () +{ + bitmap_obstack_release (&m_bitmaps); + m_tab.release (); + m_work.release (); +} + +// Return the group, if any, that NAME is part of. Do no analysis. + +phi_group * +phi_analyzer::group (tree name) const +{ + gcc_checking_assert (TREE_CODE (name) == SSA_NAME); + if (!is_a (SSA_NAME_DEF_STMT (name))) + return NULL; + unsigned v = SSA_NAME_VERSION (name); + if (v >= m_tab.length ()) + return NULL; + return m_tab[v]; +} + +// Return the group NAME is associated with, if any. If name has not been +// procvessed yet, do the analysis to determine if it is part of a group +// and return that. + +phi_group * +phi_analyzer::operator[] (tree name) +{ + gcc_checking_assert (TREE_CODE (name) == SSA_NAME); + + // Initial support for irange only. + if (!irange::supports_p (TREE_TYPE (name))) + return NULL; + if (!is_a (SSA_NAME_DEF_STMT (name))) + return NULL; + + unsigned v = SSA_NAME_VERSION (name); + // Already been processed and not part of a group. + if (bitmap_bit_p (m_simple, v)) + return NULL; + + if (v >= m_tab.length () || !m_tab[v]) + { + process_phi (as_a (SSA_NAME_DEF_STMT (name))); + if (bitmap_bit_p (m_simple, v)) + return NULL; + // If m_simple bit isn't set, then process_phi allocated the table + // and should have a group. + gcc_checking_assert (v < m_tab.length ()); + } + return m_tab[v]; +} + +// Process phi node PHI to see if it it part of a group. + +void +phi_analyzer::process_phi (gphi *phi) +{ + gcc_checking_assert (!group (gimple_phi_result (phi))); + bool cycle_p = true; + + // Start with the LHS of the PHI in the worklist. + unsigned x; + m_work.truncate (0); + m_work.safe_push (gimple_phi_result (phi)); + bitmap_clear (m_current); + + // We can only have 2 externals: an initial value and a modifier. + // Any more than that and this fails to be a group. + unsigned m_num_extern = 0; + tree m_external[2]; + edge m_ext_edge[2]; + + while (m_work.length () > 0) + { + tree phi_def = m_work.pop (); + gphi *phi_stmt = as_a (SSA_NAME_DEF_STMT (phi_def)); + // if the phi is already in a cycle, its a complex situation, so revert + // to simple. + if (group (phi_def)) + { + cycle_p = false; + continue; + } + bitmap_set_bit (m_current, SSA_NAME_VERSION (phi_def)); + // Process the args. + for (x = 0; x < gimple_phi_num_args (phi_stmt); x++) + { + tree arg = gimple_phi_arg_def (phi_stmt, x); + if (arg == phi_def) + continue; + enum tree_code code = TREE_CODE (arg); + if (code == SSA_NAME) + { + unsigned v = SSA_NAME_VERSION (arg); + // Already a member of this potential group. + if (bitmap_bit_p (m_current, v)) + continue; + // Part of a different group ends cycle possibility. + if (group (arg) || bitmap_bit_p (m_simple, v)) + { + cycle_p = false; + break; + } + // Check if its a PHI to examine. + // *FIX* Will miss initial values that originate from a PHI. + gimple *arg_stmt = SSA_NAME_DEF_STMT (arg); + if (arg_stmt && is_a (arg_stmt)) + { + m_work.safe_push (arg); + continue; + } + } + // Other non-ssa names that arent constants are not understood + // and terminate analysis. + else if (code != INTEGER_CST && code != REAL_CST) + { + cycle_p = false; + continue; + } + // More than 2 outside names/CONST is too complicated. + if (m_num_extern >= 2) + { + cycle_p = false; + break; + } + + m_external[m_num_extern] = arg; + m_ext_edge[m_num_extern++] = gimple_phi_arg_edge (phi_stmt, x); + } + } + + // If there are no names in the group, we're done. + if (bitmap_empty_p (m_current)) + return; + + phi_group *g = NULL; + if (cycle_p) + { + bool valid = true; + gimple *mod = NULL; + signed init_idx = -1; + // At this point all the PHIs have been added to the bitmap. + // the external list needs to be checked for initial values and modifiers. + for (x = 0; x < m_num_extern; x++) + { + tree name = m_external[x]; + if (TREE_CODE (name) == SSA_NAME + && phi_group::is_modifier_p (SSA_NAME_DEF_STMT (name), m_current)) + { + // Can't have multiple modifiers. + if (mod) + valid = false; + mod = SSA_NAME_DEF_STMT (name); + continue; + } + // Can't have 2 initializers either. + if (init_idx != -1) + valid = false; + init_idx = x; + } + if (valid) + { + // Try to create a group based on m_current. If a result comes back + // with a range that isn't varying, create the group. + phi_group cyc (m_current, m_external[init_idx], + m_ext_edge[init_idx], mod, &m_global); + if (!cyc.range ().varying_p ()) + g = new phi_group (cyc); + } + } + // If this dpoesn;t form a group, all members are instead simple phis. + if (!g) + { + bitmap_ior_into (m_simple, m_current); + return; + } + + if (num_ssa_names >= m_tab.length ()) + m_tab.safe_grow_cleared (num_ssa_names + 100); + + // Now set all entries in the group to this record. + unsigned i; + bitmap_iterator bi; + EXECUTE_IF_SET_IN_BITMAP (m_current, 0, i, bi) + { + // Can't be in more than one group. + gcc_checking_assert (m_tab[i] == NULL); + m_tab[i] = g; + } + // Allocate a new bitmap for the next time as the original one is now part + // of the new phi group. + m_current = BITMAP_ALLOC (&m_bitmaps); +} + +void +phi_analyzer::dump (FILE *f) +{ + bool header = false; + bitmap_clear (m_current); + for (unsigned x = 0; x < m_tab.length (); x++) + { + if (bitmap_bit_p (m_simple, x)) + continue; + if (bitmap_bit_p (m_current, x)) + continue; + if (m_tab[x] == NULL) + continue; + phi_group *g = m_tab[x]; + bitmap_ior_into (m_current, g->group ()); + if (!header) + { + header = true; + fprintf (dump_file, "\nPHI GROUPS:\n"); + } + g->dump (f); + } +} diff --git a/gcc/gimple-range-phi.h b/gcc/gimple-range-phi.h new file mode 100644 index 00000000000..b5120e97bf3 --- /dev/null +++ b/gcc/gimple-range-phi.h @@ -0,0 +1,109 @@ +/* Header file for gimple range phi analysis. + Copyright (C) 2023 Free Software Foundation, Inc. + Contributed by Andrew MacLeod . + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#ifndef GCC_SSA_RANGE_PHI_H +#define GCC_SSA_RANGE_PHI_H + +// ------------------------------------------------------------------------- + +// A PHI_GROUP consists of a set of SSA_NAMES which are all PHI_DEFS, and +// their arguemnts contain nothing but other PHI defintions, with at most +// 2 exceptions: +// 1 - An initial value. This is either a constant, or another non-phi name +// with a single incoming edge to the cycle group +// 2 - A modifier statement which adjusts the value. ie, name2 = phi_name + 1 +// The initial range is used to create one bound and the modifier is examined +// to determine the other bound. +// All members of the PHI cycle will be given the same range. +// +// For example, given the follwoing sequences: +// qa_20 = qa_10 + 1; +// qa_9 = PHI +// qa_10 = PHI <0(2), qa_9(5)> +// +// We can determine the following group: +// +// PHI cycle members qa_9, qa_10 +// Initial value : 0 +// modifier stmt: qa_20 = qa_10 + 1; +// +// Based on just this analysis, We can project that qa_9 and qa_10 will have +// a range of [0, +INF]. + +class phi_group +{ +public: + phi_group (bitmap bm, tree init_val, edge e, gimple *mod, range_query *q); + phi_group (const phi_group &g); + const_bitmap group () const { return m_group; } + const vrange &range () const { return m_vr; } + tree initial_value () const { return m_initial_value; } + gimple *modifier_stmt () const { return m_modifier; } + void dump (FILE *); +protected: + bool calculate_using_modifier (range_query *q); + bool refine_using_relation (relation_kind k, range_query *q); + static unsigned is_modifier_p (gimple *s, const bitmap bm); + bitmap m_group; + tree m_initial_value; // Name or constant. + edge m_initial_edge; // Edge of initial value. + gimple *m_modifier; // Single stmt which modifies phi group. + unsigned m_modifier_op; // Operand of group member in modifier stmt. + int_range<3> m_vr; + friend class phi_analyzer; +}; + +// The phi anlyzer will return the group that name belongs to. +// If inforamtion is not known about a name yet, analysis is conducted by +// looking at the arguments to PHIS and following them to their defs to +// determine whether the conditions are met to form a new group. + +class phi_analyzer +{ +public: + phi_analyzer (range_query &); + ~phi_analyzer (); + phi_group *operator[] (tree name); + void dump (FILE *f); +protected: + phi_group *group (tree name) const; + void process_phi (gphi *phi); + range_query &m_global; + vec m_work; + + bitmap m_simple; // Processed, not part of a group. + bitmap m_current; // Potential group currently being analyzed. + vec m_tab; + bitmap_obstack m_bitmaps; +}; + +// These are the APIs to start and stop a phi analyzerin a SCEV like manner. +// There can only be one operating at any given time. +// When initialized, a range-query if provided to do lookups of values for +// PHIs and to evaluate modifier and initial value statements. +// To avoid problems, this should be some form of constant query, like +// global_range_query or better yet a const_query from a functioning ranger. + +bool phi_analysis_available_p (); +phi_analyzer &phi_analysis (); +void phi_analysis_initialize (range_query &); +void phi_analysis_finalize (); + +#endif // GCC_SSA_RANGE_PHI_H diff --git a/gcc/testsuite/gcc.dg/pr107822.c b/gcc/testsuite/gcc.dg/pr107822.c new file mode 100644 index 00000000000..c68ecbe8f66 --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr107822.c @@ -0,0 +1,20 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-evrp" } */ + +int b; +void foo(); +void(a)(); +int main() { + int c; + int *d = &c; + *d = a && 8; + b = 0; + for (; b < 9; ++b) + *d ^= 3; + if (*d) + ; + else + foo(); +} + +/* { dg-final { scan-tree-dump-not "foo" "evrp" } } */ diff --git a/gcc/testsuite/gcc.dg/pr107986-1.c b/gcc/testsuite/gcc.dg/pr107986-1.c new file mode 100644 index 00000000000..1125ab0ea18 --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr107986-1.c @@ -0,0 +1,16 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-evrp" } */ + +void bar (); +void foo (int *a) +{ + int qa = 0; + for (int i = 0; i < 3; i++) + if (a[i]) + a[qa++] = 0; +/* Show that we know qa is not negative. */ + if (qa < 0) + bar (); +} + +/* { dg-final { scan-tree-dump-not "bar" "evrp" } } */ diff --git a/gcc/tree-vrp.cc b/gcc/tree-vrp.cc index 7f03f54cdd7..c52e9971faa 100644 --- a/gcc/tree-vrp.cc +++ b/gcc/tree-vrp.cc @@ -994,11 +994,15 @@ execute_ranger_vrp (struct function *fun, bool warn_array_bounds_p, set_all_edges_as_executable (fun); gimple_ranger *ranger = enable_ranger (fun, false); rvrp_folder folder (ranger); + phi_analysis_initialize (ranger->const_query ()); folder.substitute_and_fold (); // Remove tagged builtin-unreachable and maybe update globals. folder.m_unreachable.remove_and_update_globals (final_p); if (dump_file && (dump_flags & TDF_DETAILS)) - ranger->dump (dump_file); + { + phi_analysis ().dump (dump_file); + ranger->dump (dump_file); + } if ((warn_array_bounds || warn_strict_flex_arrays) && warn_array_bounds_p) { @@ -1020,6 +1024,7 @@ execute_ranger_vrp (struct function *fun, bool warn_array_bounds_p, array_checker.check (); } + phi_analysis_finalize (); disable_ranger (fun); scev_finalize (); loop_optimizer_finalize (); -- 2.40.1