Rewrite some jump.c routines to use flags

This patch rewrites some jump.c routines to operate on flags that
describe comparisons rather than handling each comparison code
separately.  This in turn makes it easier to add some new routines
in the next patch.

Maybe the change isn't worth it for swap_condition, unsigned_condition
and signed_condition, but it does make comparison_dominates_p simpler.

The patch also has the effect of making signed_condition accept all
FP comparisons, rather than just those that are used for integers.
I don't think that's particularly useful, but it doesn't seem harmful
either, since all FP comparisons are signed.

Tested on aarch64-linux-gnu, aarch64_be-elf and x86_64-linux-gnu.
OK to install?

Richard


2019-07-12  Richard Sandiford  <richard.sandiford@arm.com>

gcc/
	* jump.c (FLAGS_EQ, FLAGS_LT, FLAGS_GT, FLAGS_UNORDERED, FLAGS_ORDER)
	(FLAGS_SIGNED, FLAGS_UNSIGNED, FLAGS_SIGNEDNESS, FLAGS_CAN_TRAP): New
	defines.
	(condition_to_flags, flags_to_condition): New functions.
	(swap_condition, unsigned_condition, signed_condition)
	(comparison_dominates_p): Use them.

> +/* Invoke T (CODE, ORDER, SIGNEDNESS, CAN_TRAP) for each comparison, where:
> +
> +   - CODE is the rtl comparison code
> +   - ORDER is the OR of the conditions under which CODE returns true
> +   - SIGNEDNESS is the signedness of COND, or 0 if it is sign-agnostic
> +   - CAN_TRAP is true if CODE can trap on some forms of NaN.  */

Are you talking about any NaNs here or just quiet NaNs?  If the former, what's 
the point to encode anything for signaling NaNs?

> +#define FOR_MAPPING(T) \
> +  T (EQ,	FLAGS_EQ,			0,		true) \
> +  T (NE,	~FLAGS_EQ,			0,		true) \

This doesn't look correct: EQ and NE do not trap on quiet NaNs, unlike GT/LT.

Eric Botcazou <ebotcazou@adacore.com> writes:
>> +/* Invoke T (CODE, ORDER, SIGNEDNESS, CAN_TRAP) for each comparison, where:
>> +
>> +   - CODE is the rtl comparison code
>> +   - ORDER is the OR of the conditions under which CODE returns true
>> +   - SIGNEDNESS is the signedness of COND, or 0 if it is sign-agnostic
>> +   - CAN_TRAP is true if CODE can trap on some forms of NaN.  */
>
> Are you talking about any NaNs here or just quiet NaNs?  If the former, what's 
> the point to encode anything for signaling NaNs?

Yeah, the former, so...

>> +#define FOR_MAPPING(T) \
>> +  T (EQ,	FLAGS_EQ,			0,		true) \
>> +  T (NE,	~FLAGS_EQ,			0,		true) \
>
> This doesn't look correct: EQ and NE do not trap on quiet NaNs, unlike GT/LT.

...trapping on signalling NaNs is enough for the field to be true.

At least AIUI, __builtin_isunordered etc. don't raise an exception even
for signalling NaNs.

Thanks,
Richard

> ...trapping on signalling NaNs is enough for the field to be true.

So what's the point in encoding this?  The main distinction, and the only one 
relevant for the RTL middle-end, is whether the operator traps on quiet NaNs 
since this can change the comparison instruction emitted by the back-end.

Eric Botcazou <ebotcazou@adacore.com> writes:
>> ...trapping on signalling NaNs is enough for the field to be true.
>
> So what's the point in encoding this?  The main distinction, and the only one 
> relevant for the RTL middle-end, is whether the operator traps on quiet NaNs 
> since this can change the comparison instruction emitted by the back-end.

AIUI, neither ORDERED nor UNEQ trap on signalling NaNs.  Without this,
the follow-on patch would fold

   (and (ordered x y) (uneq x y)) -> (eq x y)

which is the same thing for quiet NaNs but not for signalling NaNs.

Thanks,
Richard

> AIUI, neither ORDERED nor UNEQ trap on signalling NaNs.  Without this,
> the follow-on patch would fold
> 
>    (and (ordered x y) (uneq x y)) -> (eq x y)
> 
> which is the same thing for quiet NaNs but not for signalling NaNs.

I see, thanks for explaining.

> AIUI, neither ORDERED nor UNEQ trap on signalling NaNs.  Without this,
> the follow-on patch would fold
> 
>    (and (ordered x y) (uneq x y)) -> (eq x y)
> 
> which is the same thing for quiet NaNs but not for signalling NaNs.

Note that GCC defaults to -fno-signaling-nans and the transformation would be 
valid in this mode.

Eric Botcazou <ebotcazou@adacore.com> writes:
>> AIUI, neither ORDERED nor UNEQ trap on signalling NaNs.  Without this,
>> the follow-on patch would fold
>> 
>>    (and (ordered x y) (uneq x y)) -> (eq x y)
>> 
>> which is the same thing for quiet NaNs but not for signalling NaNs.
>
> Note that GCC defaults to -fno-signaling-nans and the transformation would be 
> valid in this mode.

OK, how about this version?  Tested on aarch64-linux-gnu so far.

Thanks,
Richard


2019-07-15  Richard Sandiford  <richard.sandiford@arm.com>

gcc/
	* jump.c (FLAGS_EQ, FLAGS_LT, FLAGS_GT, FLAGS_UNORDERED, FLAGS_ORDER)
	(FLAGS_SIGNED, FLAGS_UNSIGNED, FLAGS_SIGN_AGNOSTIC, FLAGS_SIGNEDNESS)
	(FLAGS_TRAP_QNANS, FLAGS_TRAP_SNANS, FLAGS_TRAP_NANS, FLAGS_TRAP_NONE)
	(FLAGS_TRAPS): New constants.
	(condition_to_flags, flags_to_condition): New functions.
	(swap_condition, unsigned_condition, signed_condition)
	(comparison_dominates_p): Use them.

Index: gcc/jump.c
===================================================================
--- gcc/jump.c	2019-07-15 16:22:55.000000000 +0100
+++ gcc/jump.c	2019-07-15 16:22:55.342699887 +0100
@@ -65,6 +65,99 @@ static void mark_jump_label_asm (rtx, rt
 static void redirect_exp_1 (rtx *, rtx, rtx, rtx_insn *);
 static int invert_exp_1 (rtx, rtx_insn *);
 
+/* Flags that describe when a condition is true.  */
+const int FLAGS_EQ = 0x1;
+const int FLAGS_LT = 0x2;
+const int FLAGS_GT = 0x4;
+const int FLAGS_UNORDERED = 0x8;
+const int FLAGS_ORDER = 0xf;
+
+/* When describing an existing condition, these flags say whether the
+   inputs are interpreted as signed and whether they are interpreted as
+   unsigned.  When asking for a new condition, the flags say whether
+   the comparison must handle signed values and whether it must handle
+   unsigned values.  Floats are treated as signed in both cases.  */
+const int FLAGS_SIGNED = 0x10;
+const int FLAGS_UNSIGNED = 0x20;
+const int FLAGS_SIGN_AGNOSTIC = 0;
+const int FLAGS_SIGNEDNESS = FLAGS_SIGNED | FLAGS_UNSIGNED;
+
+/* When describing an existing condition, these flag say whether the
+   comparison traps for quiet NaNs and signaling NaNs.  When asking for
+   a new condition, the flag says whether the comparison is allowed to
+   trap for such NaNs.  */
+const int FLAGS_TRAP_QNANS = 0x40;
+const int FLAGS_TRAP_SNANS = 0x80;
+const int FLAGS_TRAP_NANS = FLAGS_TRAP_SNANS | FLAGS_TRAP_QNANS;
+const int FLAGS_TRAP_NONE = 0;
+const int FLAGS_TRAPS = FLAGS_TRAP_SNANS | FLAGS_TRAP_QNANS;
+
+/* Invoke T (CODE, ORDER, SIGNEDNESS, TRAPS) for each comparison, where:
+
+   - CODE is the rtl comparison code
+   - ORDER is the OR of the conditions under which CODE returns true
+   - SIGNEDNESS is the FLAGS_* suffix describing the sigedness of COND
+   - TRAPS is the FLAGS_* suffix describing when COND can trap.  */
+#define FOR_MAPPING(T) \
+  T (EQ,	FLAGS_EQ,			SIGN_AGNOSTIC,	TRAP_SNANS) \
+  T (NE,	~FLAGS_EQ,			SIGN_AGNOSTIC,	TRAP_SNANS) \
+  T (LTGT,	FLAGS_LT | FLAGS_GT,		SIGNED,		TRAP_NANS) \
+  T (LT,	FLAGS_LT,			SIGNED,		TRAP_NANS) \
+  T (LE,	FLAGS_LT | FLAGS_EQ,		SIGNED,		TRAP_NANS) \
+  T (GT,	FLAGS_GT,			SIGNED,		TRAP_NANS) \
+  T (GE,	FLAGS_GT | FLAGS_EQ,		SIGNED,		TRAP_NANS) \
+  T (LTU,	FLAGS_LT,			UNSIGNED,	TRAP_NONE) \
+  T (LEU,	FLAGS_LT | FLAGS_EQ,		UNSIGNED,	TRAP_NONE) \
+  T (GTU,	FLAGS_GT,			UNSIGNED,	TRAP_NONE) \
+  T (GEU,	FLAGS_GT | FLAGS_EQ,		UNSIGNED,	TRAP_NONE) \
+  T (ORDERED,	~FLAGS_UNORDERED,		SIGNED,		TRAP_NONE) \
+  T (UNORDERED,	FLAGS_UNORDERED,		SIGNED,		TRAP_NONE) \
+  T (UNEQ,	FLAGS_UNORDERED | FLAGS_EQ,	SIGNED,		TRAP_NONE) \
+  T (UNLT,	FLAGS_UNORDERED | FLAGS_LT,	SIGNED,		TRAP_NONE) \
+  T (UNLE,	~FLAGS_GT,			SIGNED,		TRAP_NONE) \
+  T (UNGT,	FLAGS_UNORDERED | FLAGS_GT,	SIGNED,		TRAP_NONE) \
+  T (UNGE,	~FLAGS_LT,			SIGNED,		TRAP_NONE)
+
+/* Describe comparison CODE as a bitmask of FLAGS_*.  */
+
+static unsigned int
+condition_to_flags (rtx_code code)
+{
+#define CASE(CODE, ORDER, SIGNEDNESS, TRAPS)		\
+  case CODE:						\
+    return ((ORDER) & FLAGS_ORDER) | FLAGS_##SIGNEDNESS | FLAGS_##TRAPS;
+
+  switch (code)
+    {
+    FOR_MAPPING (CASE);
+    default:
+      gcc_unreachable ();
+    }
+
+#undef CASE
+}
+
+/* Return the comparison code that implements FLAGS_* bitmask FLAGS.
+   Assert on failure if FORCE, otherwise return UNKNOWN.  */
+
+static rtx_code
+flags_to_condition (unsigned int flags, bool force)
+{
+#define TEST(CODE, ORDER, SIGNEDNESS, TRAPS)				\
+  if (((flags ^ (ORDER)) & FLAGS_ORDER) == 0				\
+      && (FLAGS_##SIGNEDNESS == 0					\
+	  || ((FLAGS_##SIGNEDNESS ^ flags) & FLAGS_SIGNEDNESS) == 0)	\
+      && (FLAGS_##TRAPS & ~flags & FLAGS_TRAPS) == 0)			\
+    return CODE;
+
+  FOR_MAPPING (TEST);
+
+  gcc_assert (!force);
+  return UNKNOWN;
+#undef TEST
+}
+#undef FOR_MAPPING
+
 /* Worker for rebuild_jump_labels and rebuild_jump_labels_chain.  */
 static void
 rebuild_jump_labels_1 (rtx_insn *f, bool count_forced)
@@ -583,44 +676,11 @@ reverse_condition_maybe_unordered (enum
 enum rtx_code
 swap_condition (enum rtx_code code)
 {
-  switch (code)
-    {
-    case EQ:
-    case NE:
-    case UNORDERED:
-    case ORDERED:
-    case UNEQ:
-    case LTGT:
-      return code;
-
-    case GT:
-      return LT;
-    case GE:
-      return LE;
-    case LT:
-      return GT;
-    case LE:
-      return GE;
-    case GTU:
-      return LTU;
-    case GEU:
-      return LEU;
-    case LTU:
-      return GTU;
-    case LEU:
-      return GEU;
-    case UNLT:
-      return UNGT;
-    case UNLE:
-      return UNGE;
-    case UNGT:
-      return UNLT;
-    case UNGE:
-      return UNLE;
-
-    default:
-      gcc_unreachable ();
-    }
+  unsigned int flags = condition_to_flags (code);
+  flags = ((flags & ~(FLAGS_GT | FLAGS_LT))
+	   | (flags & FLAGS_GT ? FLAGS_LT : 0)
+	   | (flags & FLAGS_LT ? FLAGS_GT : 0));
+  return flags_to_condition (flags, true);
 }
 
 /* Given a comparison CODE, return the corresponding unsigned comparison.
@@ -630,28 +690,8 @@ swap_condition (enum rtx_code code)
 enum rtx_code
 unsigned_condition (enum rtx_code code)
 {
-  switch (code)
-    {
-    case EQ:
-    case NE:
-    case GTU:
-    case GEU:
-    case LTU:
-    case LEU:
-      return code;
-
-    case GT:
-      return GTU;
-    case GE:
-      return GEU;
-    case LT:
-      return LTU;
-    case LE:
-      return LEU;
-
-    default:
-      gcc_unreachable ();
-    }
+  unsigned int flags = condition_to_flags (code);
+  return flags_to_condition ((flags & ~FLAGS_SIGNED) | FLAGS_UNSIGNED, true);
 }
 
 /* Similarly, return the signed version of a comparison.  */
@@ -659,28 +699,8 @@ unsigned_condition (enum rtx_code code)
 enum rtx_code
 signed_condition (enum rtx_code code)
 {
-  switch (code)
-    {
-    case EQ:
-    case NE:
-    case GT:
-    case GE:
-    case LT:
-    case LE:
-      return code;
-
-    case GTU:
-      return GT;
-    case GEU:
-      return GE;
-    case LTU:
-      return LT;
-    case LEU:
-      return LE;
-
-    default:
-      gcc_unreachable ();
-    }
+  unsigned int flags = condition_to_flags (code);
+  return flags_to_condition ((flags & ~FLAGS_UNSIGNED) | FLAGS_SIGNED, true);
 }
 
 /* Return nonzero if CODE1 is more strict than CODE2, i.e., if the
@@ -695,74 +715,12 @@ comparison_dominates_p (enum rtx_code co
   if (code1 == UNKNOWN || code2 == UNKNOWN)
     return 0;
 
-  if (code1 == code2)
-    return 1;
-
-  switch (code1)
-    {
-    case UNEQ:
-      if (code2 == UNLE || code2 == UNGE)
-	return 1;
-      break;
-
-    case EQ:
-      if (code2 == LE || code2 == LEU || code2 == GE || code2 == GEU
-	  || code2 == ORDERED)
-	return 1;
-      break;
-
-    case UNLT:
-      if (code2 == UNLE || code2 == NE)
-	return 1;
-      break;
-
-    case LT:
-      if (code2 == LE || code2 == NE || code2 == ORDERED || code2 == LTGT)
-	return 1;
-      break;
-
-    case UNGT:
-      if (code2 == UNGE || code2 == NE)
-	return 1;
-      break;
-
-    case GT:
-      if (code2 == GE || code2 == NE || code2 == ORDERED || code2 == LTGT)
-	return 1;
-      break;
-
-    case GE:
-    case LE:
-      if (code2 == ORDERED)
-	return 1;
-      break;
-
-    case LTGT:
-      if (code2 == NE || code2 == ORDERED)
-	return 1;
-      break;
-
-    case LTU:
-      if (code2 == LEU || code2 == NE)
-	return 1;
-      break;
-
-    case GTU:
-      if (code2 == GEU || code2 == NE)
-	return 1;
-      break;
-
-    case UNORDERED:
-      if (code2 == NE || code2 == UNEQ || code2 == UNLE || code2 == UNLT
-	  || code2 == UNGE || code2 == UNGT)
-	return 1;
-      break;
-
-    default:
-      break;
-    }
-
-  return 0;
+  unsigned int flags1 = condition_to_flags (code1);
+  unsigned int flags2 = condition_to_flags (code2);
+  /* Make sure that the conditions do not use different sign interpretations
+     and that FLAGS2 contains every condition that FLAGS1 contains.  */
+  return (((flags1 | flags2) & FLAGS_SIGNEDNESS) != FLAGS_SIGNEDNESS
+	  && (flags1 & ~flags2 & FLAGS_ORDER) == 0);
 }
 
 /* Return 1 if INSN is an unconditional jump and nothing else.  */

> gcc/
> 	* jump.c (FLAGS_EQ, FLAGS_LT, FLAGS_GT, FLAGS_UNORDERED, FLAGS_ORDER)
> 	(FLAGS_SIGNED, FLAGS_UNSIGNED, FLAGS_SIGN_AGNOSTIC, FLAGS_SIGNEDNESS)
> 	(FLAGS_TRAP_QNANS, FLAGS_TRAP_SNANS, FLAGS_TRAP_NANS, FLAGS_TRAP_NONE)
> 	(FLAGS_TRAPS): New constants.
> 	(condition_to_flags, flags_to_condition): New functions.
> 	(swap_condition, unsigned_condition, signed_condition)
> 	(comparison_dominates_p): Use them.

What's the run time cost of this?  In particular, do the first 3 rewritten 
functions still have a trivial path for EQ/NE/...?

Eric Botcazou <ebotcazou@adacore.com> writes:
>> gcc/
>> 	* jump.c (FLAGS_EQ, FLAGS_LT, FLAGS_GT, FLAGS_UNORDERED, FLAGS_ORDER)
>> 	(FLAGS_SIGNED, FLAGS_UNSIGNED, FLAGS_SIGN_AGNOSTIC, FLAGS_SIGNEDNESS)
>> 	(FLAGS_TRAP_QNANS, FLAGS_TRAP_SNANS, FLAGS_TRAP_NANS, FLAGS_TRAP_NONE)
>> 	(FLAGS_TRAPS): New constants.
>> 	(condition_to_flags, flags_to_condition): New functions.
>> 	(swap_condition, unsigned_condition, signed_condition)
>> 	(comparison_dominates_p): Use them.
>
> What's the run time cost of this?  In particular, do the first 3 rewritten 
> functions still have a trivial path for EQ/NE/...?  

No, no trivial paths unfortunately.  I'd hoped that inlining and
jump threading would give us very similar code, but no such luck.
condition_to_flags is a table lookup, but then flags_to_condition
is a branch tree.

If that's a concern, I can drop the changes to the existing
functions and just use the new flags for the follow-on patch.

Thanks,
Richard

> No, no trivial paths unfortunately.  I'd hoped that inlining and
> jump threading would give us very similar code, but no such luck.
> condition_to_flags is a table lookup, but then flags_to_condition
> is a branch tree.

Too bad.  Perhaps this would be an interesting optimization exercise.

> If that's a concern, I can drop the changes to the existing
> functions and just use the new flags for the follow-on patch.

IMO the net pessimization is a little hard to swallow, although it probably 
doesn't matter much in practice.  I'd suggest adding the new logic in every 
case, but keeping the fast path when it's a nop:

 enum rtx_code
 swap_condition (enum rtx_code code)
 {
  /* Deal with the trivial cases first.  */
  switch (code)
    {
    case EQ:
    case NE:
    case UNORDERED:
    case ORDERED:
    case UNEQ:
    case LTGT:
      return code;
    default:
      break;
    }

  unsigned int flags = condition_to_flags (code);
  flags = ((flags & ~(FLAGS_GT | FLAGS_LT))
          | (flags & FLAGS_GT ? FLAGS_LT : 0)
          | (flags & FLAGS_LT ? FLAGS_GT : 0));
  return flags_to_condition (flags, true);
 }

OK with this additional change.

Eric Botcazou <ebotcazou@adacore.com> writes:
>> No, no trivial paths unfortunately.  I'd hoped that inlining and
>> jump threading would give us very similar code, but no such luck.
>> condition_to_flags is a table lookup, but then flags_to_condition
>> is a branch tree.
>
> Too bad.  Perhaps this would be an interesting optimization exercise.

Yeah.  Unfortunately I have a lot of those to get through for GCC 10
already :-)

>> If that's a concern, I can drop the changes to the existing
>> functions and just use the new flags for the follow-on patch.
>
> IMO the net pessimization is a little hard to swallow, although it probably 
> doesn't matter much in practice.  I'd suggest adding the new logic in every 
> case, but keeping the fast path when it's a nop:
>
>  enum rtx_code
>  swap_condition (enum rtx_code code)
>  {
>   /* Deal with the trivial cases first.  */
>   switch (code)
>     {
>     case EQ:
>     case NE:
>     case UNORDERED:
>     case ORDERED:
>     case UNEQ:
>     case LTGT:
>       return code;
>     default:
>       break;
>     }
>
>   unsigned int flags = condition_to_flags (code);
>   flags = ((flags & ~(FLAGS_GT | FLAGS_LT))
>           | (flags & FLAGS_GT ? FLAGS_LT : 0)
>           | (flags & FLAGS_LT ? FLAGS_GT : 0));
>   return flags_to_condition (flags, true);
>  }
>
> OK with this additional change.

I'm not sure using flags_to_condition really buys anything then,
since you have to think about each individual case to see whether
it belongs in the switch or not.  I also don't have any proof
that the no-op cases are the common ones (since adding this
fast path of course slows down the others).

I think I'll just use the new routines for the new optimisation
and leave the existing ones as-is.

Thanks,
Richard

> I'm not sure using flags_to_condition really buys anything then,
> since you have to think about each individual case to see whether
> it belongs in the switch or not.  I also don't have any proof
> that the no-op cases are the common ones (since adding this
> fast path of course slows down the others).

Really?  Branch prediction is rather efficient these days.

> I think I'll just use the new routines for the new optimisation
> and leave the existing ones as-is.

OK, your call.

Eric Botcazou <ebotcazou@adacore.com> writes:
>> I'm not sure using flags_to_condition really buys anything then,
>> since you have to think about each individual case to see whether
>> it belongs in the switch or not.  I also don't have any proof
>> that the no-op cases are the common ones (since adding this
>> fast path of course slows down the others).
>
> Really?  Branch prediction is rather efficient these days.

Sure.  But we're still adding another branch here to avoid the branches in
flags_to_condition in some cases.  There's no guarantee that this branch
is going to be more predictable than the ones in flags_to_condition,
or that the total number of mispredicts is going to be lower this way.
(Not saying it won't be, just that we're making assumptions if we think
it will.)

I just think we should only add extra code like this if we have proof
that it makes things better, or at least that the cases it handles
are worth handling specially.

But by the same token, the status quo wins if there's doubt about
whether the original patch itself is worthwhile.

Richard

On Fri, 12 Jul 2019, Richard Sandiford wrote:

> At least AIUI, __builtin_isunordered etc. don't raise an exception even
> for signalling NaNs.

__builtin_isunordered should raise "invalid" for signaling NaNs.  
(isunordered is the IEEE 754 operation compareQuietUnordered, and IEEE 754 
specifies for comparisons that "Invalid operation is the only exception 
that a comparison predicate can signal. All predicates signal the invalid 
operation exception on signaling NaN operands. The predicates named Quiet 
shall not signal any exception, unless an operand is a signaling NaN. The 
predicates named Signaling shall signal the invalid operation exception on 
quiet NaN operands.".)

Note that __builtin_isunordered (x, x) is thus not the same as 
__builtin_isnan (x), because isnan binds to isNaN and isNaN is a 
non-computational operation for which IEEE 754 specifies "Implementations 
shall provide the following non-computational operations for all supported 
arithmetic formats and should provide them for all supported interchange 
formats. They are never exceptional, even for signaling NaNs.".