[Bug tree-optimization/55157] Missed VRP with != 0 and multiply

["aldyh at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=55157

Aldy Hernandez <aldyh at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |aldyh at gcc dot gnu.org,
                   |                            |amacleod at redhat dot com

--- Comment #4 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
We have a variety of ways of fixing this:
  1. Improve the range-op entry for MULT_EXPR.
  2. Handle nonzero bits in the relational operators.
  3. Reflect the nonzero bits in the actual range for trivial masks.

At evrp time we have:

=========== BB 2 ============
Imports: t_3(D)  
Exports: t_3(D)  g_4  
         g_4 : t_3(D)(I)  
t_3(D)  [irange] unsigned int VARYING
    <bb 2> :
    g_4 = t_3(D) * 16;
    if (g_4 == 0)
      goto <bb 3>; [INV]
    else
      goto <bb 4>; [INV]

2->3  (T) g_4 :         [irange] unsigned int [0, 0] NONZERO 0x0
2->4  (F) g_4 :         [irange] unsigned int [1, +INF]

Since this is unsigned, improving the multiply range-op entry could give a
range for g_4 of [0,0][16,+INF].  This would be enough to fold the other
conditional: if (g_4 <= 4).

The code for mult and div is legacy code inherited from legacy VRP.  I'm
assuming we didn't handle the above originally because legacy ranges couldn't
represent [0,0][16,+INF].  We can now, so we could improve here.

However, even without a multiplication improvement, the nonzero mask could help
here.  Though this mask is missing by evrp time (because mult doesn't handle it
(yet)), CCP2 does provide it and we can see it by vrp1 time:

        g_4: [irange] unsigned int [1, +INF] NONZERO 0xfffffff0

This should be enough to fold the second conditional: if (g_4 <= 4).  But alas,
the LE_EXPR range-op entry does not take into account nonzero bits.

The above mask of 0xfffffff0 is fancy talk for [0, 0][16, +INF] which we could
intersect with [1, +INF].  We could teach the LE_EXPR range-op entry about
nonzero bits.

However, perhaps instead of teaching all the relation operators about nonzero
bits, we could augment the range in irange::set_nonzero_bits().  Basically,
intersecting [0,0][16,+INF] with the [1, +INF] when setting the nonzero mask.

The patch below does this, but it does have a 3% penalty for VRP (though no
penalty to overall compilation).  I'm inclined to pursue this route, since it
makes nonzero mask optimization more pervasive across the board.

What do you think Andrew?

diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index a855aaf626c..db6a3b7bcb6 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -2962,6 +2962,20 @@ irange::set_nonzero_bits (const wide_int_ref &bits)
   normalize_kind ();
   if (flag_checking)
     verify_range ();
+
+  // Reflect the mask as a simple range.  For example, a mask of
+  // 0xff00 could be represented as [0,0][0x100, 0xffff].
+  if (TYPE_UNSIGNED (type ()) && prec > 1)
+    {
+      gcc_checking_assert (nz != 0);
+      wide_int lb = wi::lshift (wi::one (prec), wi::ctz (nz));
+      wide_int ub = wi::lrshift (wi::minus_one (prec), wi::clz (nz));
+      int_range<2> r (type (), lb, ub);
+      int_range<2> zero;
+      zero.set_zero (type ());
+      r.union_ (zero);
+      intersect (r);
+    }
 }

 // Return the nonzero bitmask.  This will return the nonzero bits plus