[COMMITTED,1/2] Remove simple ranges from trailing zero bitmasks.

Message ID 14b069dc-711f-4643-97a0-b64142017f24@redhat.com
State Unresolved
Headers
Series [COMMITTED,1/2] Remove simple ranges from trailing zero bitmasks. |

Checks

Context Check Description
snail/gcc-patch-check warning Git am fail log

Commit Message

Andrew MacLeod Nov. 3, 2023, 5:14 p.m. UTC
  WHen we set bitmasks indicating known zero or one bits, we see some 
"obvious" things once in a while that are easy to prevent. ie

unsigned int [2, +INF] MASK 0xfffffffe VALUE 0x1

the range [2, 2] is obviously impossible since the final bit must be a 
one.   This doesn't usually cause us too much trouble, but the 
subsequent patch triggers some more interesting situations in which it 
helps to remove the obvious ranges when we have  mask that is trailing 
zeros.

Its too much of a performance impact to constantly be checking the range 
every time we set the bitmask, but it turns out that if we simply try to 
take care of it during intersection operations (which happen at most key 
times, like changing an existing value), the impact is pretty minimal.. 
like 0.6% of VRP.

This patch looks for trailing zeros in the mask, and replaces the low 
end range covered by those bits with those bits from the value field.

Bootstraps on build-x86_64-pc-linux-gnu with no regressions. Pushed.

Andrew
  

Patch

From b20f1dce46fb8bb1b142e9087530e546a40edec8 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
Date: Tue, 31 Oct 2023 11:51:34 -0400
Subject: [PATCH 1/2] Remove simple ranges from trailing zero bitmasks.

During the intersection operation, it can be helpful to remove any
low-end ranges when the bitmask has trailing zeros.  This prevents
obviously incorrect ranges from appearing without requiring a bitmask
check.

	* value-range.cc (irange_bitmask::adjust_range): New.
	(irange::intersect_bitmask): Call adjust_range.
	* value-range.h (irange_bitmask::adjust_range): New prototype.
---
 gcc/value-range.cc | 30 ++++++++++++++++++++++++++++++
 gcc/value-range.h  |  2 ++
 2 files changed, 32 insertions(+)

diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index fcf53efa1dd..a1e72c78f8b 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -1857,6 +1857,35 @@  irange::get_bitmask_from_range () const
   return irange_bitmask (wi::zero (prec), min | xorv);
 }
 
+// Remove trailing ranges that this bitmask indicates can't exist.
+
+void
+irange_bitmask::adjust_range (irange &r) const
+{
+  if (unknown_p () || r.undefined_p ())
+    return;
+
+  int_range_max range;
+  tree type = r.type ();
+  int prec = TYPE_PRECISION (type);
+  // If there are trailing zeros, create a range representing those bits.
+  gcc_checking_assert (m_mask != 0);
+  int z = wi::ctz (m_mask);
+  if (z)
+    {
+      wide_int ub = (wi::one (prec) << z) - 1;
+      range = int_range<5> (type, wi::zero (prec), ub);
+      // Then remove the specific value these bits contain from the range.
+      wide_int value = m_value & ub;
+      range.intersect (int_range<2> (type, value, value, VR_ANTI_RANGE));
+      // Inverting produces a list of ranges which can be valid.
+      range.invert ();
+      // And finally select R from only those valid values.
+      r.intersect (range);
+      return;
+    }
+}
+
 // If the the mask can be trivially converted to a range, do so and
 // return TRUE.
 
@@ -2002,6 +2031,7 @@  irange::intersect_bitmask (const irange &r)
 
   if (!set_range_from_bitmask ())
     normalize_kind ();
+  m_bitmask.adjust_range (*this);
   if (flag_checking)
     verify_range ();
   return true;
diff --git a/gcc/value-range.h b/gcc/value-range.h
index e9d81d22cd0..84f65ffb591 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -139,6 +139,8 @@  public:
   void verify_mask () const;
   void dump (FILE *) const;
 
+  void adjust_range (irange &r) const;
+
   // Convenience functions for nonzero bitmask compatibility.
   wide_int get_nonzero_bits () const;
   void set_nonzero_bits (const wide_int &bits);
-- 
2.41.0