public inbox for gcc-cvs@sourceware.org
help / color / mirror / Atom feed
From: Aldy Hernandez <aldyh@gcc.gnu.org>
To: gcc-cvs@gcc.gnu.org
Subject: [gcc r13-3806] Use bit-CCP in range-ops.
Date: Tue,  8 Nov 2022 14:18:19 +0000 (GMT)	[thread overview]
Message-ID: <20221108141819.973A23858C36@sourceware.org> (raw)

https://gcc.gnu.org/g:b74dd1bbd2a02a0755bc882c6e64964b2a47ba5d

commit r13-3806-gb74dd1bbd2a02a0755bc882c6e64964b2a47ba5d
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Sun Nov 6 13:05:39 2022 +0100

    Use bit-CCP in range-ops.
    
    After Jakub and Richi's suggestion of using the same representation
    for tracking known bits as we do in CCP, I took a peek at the code and
    realized there's a plethora of bit-tracking code there that we could
    be sharing with range-ops.  For example, the multiplication
    optimizations are way better than what I had cobbled together.  For
    that matter, our maybe nonzero tracking as a whole has a lot of room
    for improvement.  Being the lazy ass that I am, I think we should just
    use one code base (CCP's).
    
    This patch provides a thin wrapper for converting the irange maybe
    nonzero bits to what CCP requires, and uses that to call into
    bit_value_binop().  I have so far converted the MULT_EXPR range-op
    entry to use it, as the DIV_EXPR entry we have gets a case CCP doesn't
    get so I'd like to contribute the enhancement to CCP before converting
    over.
    
    I'd like to use this approach with the dozen or so tree_code's that
    are handled in CCP, thus saving us from having to implement any of
    them :).
    
    Early next season I'd like to change irange's internal representation
    to a pair of value / mask, and start tracking all known bits.  This
    ties in nicely with our plan for tracking known set bits.
    
    Perhaps if the stars align, we could merge the bit twiddling in CCP
    into range-ops and have a central repository for it.  That is, once we
    make the switch to wide-ints, and assuming there are no performance
    issues.  Note that range-ops is our lowest level abstraction.
    i.e. it's just the math, there's no GORI or ranger, or even the
    concept of a symbolic or SSA.
    
    gcc/ChangeLog:
    
            * range-op.cc (irange_to_masked_value): New.
            (update_known_bitmask): New.
            (operator_mult::fold_range): Call update_known_bitmask.

Diff:
---
 gcc/range-op.cc | 64 +++++++++++++++++++++++++++++++++++++++++++--------------
 1 file changed, 49 insertions(+), 15 deletions(-)

diff --git a/gcc/range-op.cc b/gcc/range-op.cc
index a13e88840a6..846931ddcae 100644
--- a/gcc/range-op.cc
+++ b/gcc/range-op.cc
@@ -46,6 +46,54 @@ along with GCC; see the file COPYING3.  If not see
 #include "wide-int.h"
 #include "value-relation.h"
 #include "range-op.h"
+#include "tree-ssa-ccp.h"
+
+// Convert irange bitmasks into a VALUE MASK pair suitable for calling CCP.
+
+static void
+irange_to_masked_value (const irange &r, widest_int &value, widest_int &mask)
+{
+  if (r.singleton_p ())
+    {
+      mask = 0;
+      value = widest_int::from (r.lower_bound (), TYPE_SIGN (r.type ()));
+    }
+  else
+    {
+      mask = widest_int::from (r.get_nonzero_bits (), TYPE_SIGN (r.type ()));
+      value = 0;
+    }
+}
+
+// Update the known bitmasks in R when applying the operation CODE to
+// LH and RH.
+
+static void
+update_known_bitmask (irange &r, tree_code code,
+		      const irange &lh, const irange &rh)
+{
+  if (r.undefined_p () || lh.undefined_p () || rh.undefined_p ())
+    return;
+
+  widest_int value, mask, lh_mask, rh_mask, lh_value, rh_value;
+  tree type = r.type ();
+  signop sign = TYPE_SIGN (type);
+  int prec = TYPE_PRECISION (type);
+  signop lh_sign = TYPE_SIGN (lh.type ());
+  signop rh_sign = TYPE_SIGN (rh.type ());
+  int lh_prec = TYPE_PRECISION (lh.type ());
+  int rh_prec = TYPE_PRECISION (rh.type ());
+
+  irange_to_masked_value (lh, lh_value, lh_mask);
+  irange_to_masked_value (rh, rh_value, rh_mask);
+  bit_value_binop (code, sign, prec, &value, &mask,
+		   lh_sign, lh_prec, lh_value, lh_mask,
+		   rh_sign, rh_prec, rh_value, rh_mask);
+
+  int_range<2> tmp (type);
+  tmp.set_nonzero_bits (value | mask);
+  r.intersect (tmp);
+}
 
 // Return the upper limit for a type.
 
@@ -1775,21 +1823,7 @@ operator_mult::fold_range (irange &r, tree type,
   if (!cross_product_operator::fold_range (r, type, lh, rh, trio))
     return false;
 
-  if (lh.undefined_p ())
-    return true;
-
-  tree t;
-  if (rh.singleton_p (&t))
-    {
-      wide_int w = wi::to_wide (t);
-      int shift = wi::exact_log2 (w);
-      if (shift != -1)
-	{
-	  wide_int nz = lh.get_nonzero_bits ();
-	  nz = wi::lshift (nz, shift);
-	  r.set_nonzero_bits (nz);
-	}
-    }
+  update_known_bitmask (r, MULT_EXPR, lh, rh);
   return true;
 }

                 reply	other threads:[~2022-11-08 14:18 UTC|newest]

Thread overview: [no followups] expand[flat|nested]  mbox.gz  Atom feed

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20221108141819.973A23858C36@sourceware.org \
    --to=aldyh@gcc.gnu.org \
    --cc=gcc-cvs@gcc.gnu.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).