[RFA] Minor optimization of variable bit testing

Richard Biener richard.guenther@gmail.com
Wed Nov 3 08:15:40 GMT 2021


On Tue, Nov 2, 2021 at 4:53 PM Jeff Law <jlaw@tachyum.com> wrote:
>
>
> I was wandering spec chasing down instances where we should be
> generating bit-test, bit-set and bit-clear types of instructions for our
> target when I ran across a generic missed optimization in this space.
>
>
> (((1 << N) & C) != 0)  -> (N == C')
> (((1 << N) & C) == 0)  -> (N != C')
>
> Where C is a constant power of 2 and C' is log2 (C).
>
>
>
> That obviously avoids the shift by a variable amount and the bit masking
> which is the primary effect.  I did see cases where we were able to
> constant propagate into uses of N, but those were only in PHI nodes and
> never triggered any real secondary effects in the cases I looked at.
>
>
> Anyway, it's a fairly minor optimization, but with the analysis done and
> patch in hand, it's silly not to take the easy win.
>
>
> Bootstrapped and regression tested on x86_64 and verified that the
> affected spec benchmark (gcc itself) still passes on our target.
>
> OK for the trunk?  Note I added the patterns at the end of match.pd.
> Certainly open to moving them elsewhere.

There are related patterns like

/* (CST1 << A) == CST2 -> A == ctz (CST2) - ctz (CST1)
   (CST1 << A) != CST2 -> A != ctz (CST2) - ctz (CST1)

please move the new patterns next to those.

+/* ((1 << n) & M) != 0  -> n == log2 (M) */
+(simplify
+ (ne
+  (bit_and
+   (nop_convert? (lshift integer_onep@0 @1)) integer_pow2p@2) integer_zerop@3)
+ (eq @1 { build_int_cst (integer_type_node,
+                         wi::exact_log2 (wi::to_wide (@2))); }))
+
+/* ((1 << n) & M) == 0  -> n != log2 (M) */
+(simplify
+ (eq
+  (bit_and
+   (nop_convert? (lshift integer_onep@0 @1)) integer_pow2p@2) integer_zerop@3)
+ (ne @1 { build_int_cst (integer_type_node,
+                         wi::exact_log2 (wi::to_wide (@2))); }))

you don't need @3 or @0 so no need to specify them.  You can merge the
patterns with

(for cmp (ne eq)
       icmp (eq ne)
  (simplify
    (cmp
+  (bit_and
      (nop_convert? (lshift integer_onep @1)) integer_pow2p@2) integer_zerop)
    (icmp @1 { wide_int_to_tree (TREE_TYPE (@1),
+                         wi::exact_log2 (wi::to_wide (@2))); }))

I belive the integer constant you build should be of the type of @1 (I
fixed that above,
also using wide_int_to_tree.  The pattern is written in a way that _could_ match
vector operations and a vector by vector shift in which case the
wi::to_wide would
ICE - integer_pow2p currently does not match vector constants.  But maybe be
defensive and add

  (if (INTEGRAL_TYPE_P (TREE_TYPE (@1)))

I think the patch is OK with those changes.

Thanks,
Richard.


>
> Jeff


More information about the Gcc-patches mailing list