This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[Committed] PR25724: Optimize multi-word modes in do_compare_rtx_and_jump
- From: Roger Sayle <roger at eyesopen dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Sun, 12 Feb 2006 18:57:08 -0700 (MST)
- Subject: [Committed] PR25724: Optimize multi-word modes in do_compare_rtx_and_jump
The following patch overhauls the way that conditional jumps are
expanded to RTL by the middle-end. The most significant change
is that do_compare_rtx_and_jump is improved to optimize lowering
of multi-word comparisons. This whole area was a mess, with
duplicated functionality and different functions doing almost
the same thing or working around the defficiencies in other APIs.
To summarise, dojump.c:do_compare_rtx_and_jump previously didn't
bother optimizing multi-word comparisons. Instead multi-word
comparisons were only optimized when expanding RTL from trees,
via do_jump, not when generating comparisons at the RTL-level.
To work around this failing expmed.c used its own do_cmp_and_jump
which called into dojump.c's low-level do_jump_parts_*_rtx code.
This patch:
[1] Renames do_jump_parts_equality_rtx to do_jump_parts_zero_rtx
as it only handles comparisons against zero.
[2] It makes the new do_jump_parts_zero_rtx static as its now
only called from within dojump.c.
[3] Adds a MODE argument to do_jump_parts_zero_rtx to prevent
having to figure out the comparison mode from its argument.
[4] Splits out a new static do_jump_parts_equality_rtx from the
tree expander do_jump_parts_equality for generic equality
and inequality comparisons.
[5] Optimizes do_jump_parts_equality_rtx for comparisons against
zero by calling do_jump_parts_zero_rtx.
[6] Add multi-word comparison optimization to do_compare_rtx_and_jump
using the above functions (based heavily on expmed.c's
do_cmp_and_jump).
Once multi-word comparisons are optimized in do_compare_rtx_and_jump
its possible to clean-up several other functions in GCC's middle-end.
[1] dojump.c:do_jump can now call do_compare_rtx_and_jump directly.
[2] expmed.c:do_cmp_and_jump can now call do_compare_rtx_and_jump
directly (avoiding do_jump_by_parts_equality_rtx needing to
be exported via expr.h).
[3] stmt.c:do_jump_if_equal can now call do_compare_rtx_and_jump to
implement all of its previous functionality, and now optimize
multi-word comparisons.
There are still more clean-ups that can be made following this change
that I'll commit as a follow-up patch.
Finally, whilst I was changing it anyway I updated stmt.c:do_jump_if_equal
to also take a comparison mode, again to avoid trying to calculate the
mode of the comparison from its operands.
All of this not only clean-ups and organizes the conditional jump
expansion code, but also resolves PR middle-end/25724 where on some
targets "switch (x) { case C: foo(); }" would produce inferior code
to the equivalent "if (x == C) foo();".
The following patch has been tested on both i686-pc-linux-gnu, all
default languages including Ada, and powerpc-unknown-linux-gnu, all
default languages, and regression checked with a top-level "make -k
check" with no new failures on either platform.
Committed to mainline as revision 110906.
2006-02-12 Roger Sayle <roger@eyesopen.com>
PR middle-end/25724
* dojump.c (do_jump): Call do_compare_rtx_and_jump.
(do_jump_parts_zero_rtx): New function renamed from
do_jump_parts_equality_rtx. Made static. Add a mode argument.
(do_jump_parts_equality_rtx): New function split out from
do_jump_parts_equality. Old implementation renamed as above.
Call do_jump_parts_zero_rtx if either operand is zero.
(do_jump_parts_equality): Call do_jump_parts_equality_rtx to
do all of the heavy lifting.
(do_compare_rtx_and_jump): Handle multi-word comparisons by
calling either do_jump_by_parts_greater_rtx or
do_jump_by_parts_equality_rtx.
* expr.h (do_jump_by_parts_equality_rtx): Remove prototype.
* expmed.c (do_cmp_and_jump): Now multi-word optimization has
moved to do_compare_rtx_and_jump, call it directly.
* stmt.c (do_jump_if_equal): Remove static prototype. Add a
mode argument. Call do_compare_rtx_and_jump.
(emit_case_nodes): Update calls to do_jump_if_equal.
Index: dojump.c
===================================================================
*** dojump.c (revision 110873)
--- dojump.c (working copy)
***************
*** 1,6 ****
/* Convert tree expression to rtl instructions, for GNU compiler.
Copyright (C) 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999,
! 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
This file is part of GCC.
--- 1,6 ----
/* Convert tree expression to rtl instructions, for GNU compiler.
Copyright (C) 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999,
! 2000, 2001, 2002, 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
This file is part of GCC.
*************** do_jump (tree exp, rtx if_false_label, r
*** 586,623 ****
normal:
temp = expand_normal (exp);
do_pending_stack_adjust ();
!
! if (GET_CODE (temp) == CONST_INT
! || (GET_CODE (temp) == CONST_DOUBLE && GET_MODE (temp) == VOIDmode)
! || GET_CODE (temp) == LABEL_REF)
! {
! rtx target = temp == const0_rtx ? if_false_label : if_true_label;
! if (target)
! emit_jump (target);
! }
! else if (GET_MODE_CLASS (GET_MODE (temp)) == MODE_INT
! && ! can_compare_p (NE, GET_MODE (temp), ccp_jump))
! /* Note swapping the labels gives us not-equal. */
! do_jump_by_parts_equality_rtx (temp, if_true_label, if_false_label);
! else
{
! gcc_assert (GET_MODE (temp) != VOIDmode);
!
! /* The RTL optimizers prefer comparisons against pseudos. */
! if (GET_CODE (temp) == SUBREG)
! {
! /* Compare promoted variables in their promoted mode. */
! if (SUBREG_PROMOTED_VAR_P (temp)
! && REG_P (XEXP (temp, 0)))
! temp = XEXP (temp, 0);
! else
! temp = copy_to_reg (temp);
! }
! do_compare_rtx_and_jump (temp, CONST0_RTX (GET_MODE (temp)),
! NE, TYPE_UNSIGNED (TREE_TYPE (exp)),
! GET_MODE (temp), NULL_RTX,
! if_false_label, if_true_label);
}
}
if (drop_through_label)
--- 586,605 ----
normal:
temp = expand_normal (exp);
do_pending_stack_adjust ();
! /* The RTL optimizers prefer comparisons against pseudos. */
! if (GET_CODE (temp) == SUBREG)
{
! /* Compare promoted variables in their promoted mode. */
! if (SUBREG_PROMOTED_VAR_P (temp)
! && REG_P (XEXP (temp, 0)))
! temp = XEXP (temp, 0);
! else
! temp = copy_to_reg (temp);
}
+ do_compare_rtx_and_jump (temp, CONST0_RTX (GET_MODE (temp)),
+ NE, TYPE_UNSIGNED (TREE_TYPE (exp)),
+ GET_MODE (temp), NULL_RTX,
+ if_false_label, if_true_label);
}
if (drop_through_label)
*************** do_jump_by_parts_greater_rtx (enum machi
*** 695,737 ****
if (drop_through_label)
emit_label (drop_through_label);
}
-
- /* Given an EQ_EXPR expression EXP for values too wide to be compared
- with one insn, test the comparison and jump to the appropriate label. */
-
- static void
- do_jump_by_parts_equality (tree exp, rtx if_false_label, rtx if_true_label)
- {
- rtx op0 = expand_normal (TREE_OPERAND (exp, 0));
- rtx op1 = expand_normal (TREE_OPERAND (exp, 1));
- enum machine_mode mode = TYPE_MODE (TREE_TYPE (TREE_OPERAND (exp, 0)));
- int nwords = (GET_MODE_SIZE (mode) / UNITS_PER_WORD);
- int i;
- rtx drop_through_label = 0;
-
- if (! if_false_label)
- drop_through_label = if_false_label = gen_label_rtx ();
-
- for (i = 0; i < nwords; i++)
- do_compare_rtx_and_jump (operand_subword_force (op0, i, mode),
- operand_subword_force (op1, i, mode),
- EQ, TYPE_UNSIGNED (TREE_TYPE (exp)),
- word_mode, NULL_RTX, if_false_label, NULL_RTX);
-
- if (if_true_label)
- emit_jump (if_true_label);
- if (drop_through_label)
- emit_label (drop_through_label);
- }
! /* Jump according to whether OP0 is 0.
! We assume that OP0 has an integer mode that is too wide
! for the available compare insns. */
! void
! do_jump_by_parts_equality_rtx (rtx op0, rtx if_false_label, rtx if_true_label)
{
! int nwords = GET_MODE_SIZE (GET_MODE (op0)) / UNITS_PER_WORD;
rtx part;
int i;
rtx drop_through_label = 0;
--- 677,693 ----
if (drop_through_label)
emit_label (drop_through_label);
}
! /* Jump according to whether OP0 is 0. We assume that OP0 has an integer
! mode, MODE, that is too wide for the available compare insns. Either
! Either (but not both) of IF_TRUE_LABEL and IF_FALSE_LABEL may be NULL_RTX
! to indicate drop through. */
! static void
! do_jump_by_parts_zero_rtx (enum machine_mode mode, rtx op0,
! rtx if_false_label, rtx if_true_label)
{
! int nwords = GET_MODE_SIZE (mode) / UNITS_PER_WORD;
rtx part;
int i;
rtx drop_through_label = 0;
*************** do_jump_by_parts_equality_rtx (rtx op0,
*** 771,776 ****
--- 727,784 ----
if (drop_through_label)
emit_label (drop_through_label);
}
+
+ /* Test for the equality of two RTX expressions OP0 and OP1 in mode MODE,
+ where MODE is an integer mode too wide to be compared with one insn.
+ Either (but not both) of IF_TRUE_LABEL and IF_FALSE_LABEL may be NULL_RTX
+ to indicate drop through. */
+
+ static void
+ do_jump_by_parts_equality_rtx (enum machine_mode mode, rtx op0, rtx op1,
+ rtx if_false_label, rtx if_true_label)
+ {
+ int nwords = (GET_MODE_SIZE (mode) / UNITS_PER_WORD);
+ rtx drop_through_label = 0;
+ int i;
+
+ if (op1 == const0_rtx)
+ {
+ do_jump_by_parts_zero_rtx (mode, op0, if_false_label, if_true_label);
+ return;
+ }
+ else if (op0 == const0_rtx)
+ {
+ do_jump_by_parts_zero_rtx (mode, op1, if_false_label, if_true_label);
+ return;
+ }
+
+ if (! if_false_label)
+ drop_through_label = if_false_label = gen_label_rtx ();
+
+ for (i = 0; i < nwords; i++)
+ do_compare_rtx_and_jump (operand_subword_force (op0, i, mode),
+ operand_subword_force (op1, i, mode),
+ EQ, 0, word_mode, NULL_RTX,
+ if_false_label, NULL_RTX);
+
+ if (if_true_label)
+ emit_jump (if_true_label);
+ if (drop_through_label)
+ emit_label (drop_through_label);
+ }
+
+ /* Given an EQ_EXPR expression EXP for values too wide to be compared
+ with one insn, test the comparison and jump to the appropriate label. */
+
+ static void
+ do_jump_by_parts_equality (tree exp, rtx if_false_label, rtx if_true_label)
+ {
+ rtx op0 = expand_normal (TREE_OPERAND (exp, 0));
+ rtx op1 = expand_normal (TREE_OPERAND (exp, 1));
+ enum machine_mode mode = TYPE_MODE (TREE_TYPE (TREE_OPERAND (exp, 0)));
+ do_jump_by_parts_equality_rtx (mode, op0, op1, if_false_label,
+ if_true_label);
+ }
/* Generate code for a comparison of OP0 and OP1 with rtx code CODE.
MODE is the machine mode of the comparison, not of the result.
*************** do_compare_rtx_and_jump (rtx op0, rtx op
*** 886,899 ****
unsignedp = (code == GTU || code == LTU || code == GEU || code == LEU);
}
if (! if_true_label)
{
dummy_true_label = 1;
if_true_label = gen_label_rtx ();
}
! emit_cmp_and_jump_insns (op0, op1, code, size, mode, unsignedp,
! if_true_label);
if (if_false_label)
emit_jump (if_false_label);
--- 894,953 ----
unsignedp = (code == GTU || code == LTU || code == GEU || code == LEU);
}
+
if (! if_true_label)
{
dummy_true_label = 1;
if_true_label = gen_label_rtx ();
}
! if (GET_MODE_CLASS (mode) == MODE_INT
! && ! can_compare_p (code, mode, ccp_jump))
! {
! switch (code)
! {
! case LTU:
! do_jump_by_parts_greater_rtx (mode, 1, op1, op0,
! if_false_label, if_true_label);
! break;
!
! case LEU:
! do_jump_by_parts_greater_rtx (mode, 1, op0, op1,
! if_true_label, if_false_label);
! break;
!
! case LT:
! do_jump_by_parts_greater_rtx (mode, 0, op1, op0,
! if_false_label, if_true_label);
! break;
!
! case GT:
! do_jump_by_parts_greater_rtx (mode, 0, op0, op1,
! if_false_label, if_true_label);
! break;
!
! case GE:
! do_jump_by_parts_greater_rtx (mode, 0, op1, op0,
! if_true_label, if_false_label);
! break;
!
! case EQ:
! do_jump_by_parts_equality_rtx (mode, op0, op1, if_false_label,
! if_true_label);
! break;
!
! case NE:
! do_jump_by_parts_equality_rtx (mode, op0, op1, if_true_label,
! if_false_label);
! break;
!
! default:
! gcc_unreachable ();
! }
! }
! else
! emit_cmp_and_jump_insns (op0, op1, code, size, mode, unsignedp,
! if_true_label);
if (if_false_label)
emit_jump (if_false_label);
Index: expr.h
===================================================================
*** expr.h (revision 110873)
--- expr.h (working copy)
***************
*** 1,6 ****
/* Definitions for code generation pass of GNU compiler.
Copyright (C) 1987, 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
! 1999, 2000, 2001, 2002, 2003, 2004, 2005
Free Software Foundation, Inc.
This file is part of GCC.
--- 1,6 ----
/* Definitions for code generation pass of GNU compiler.
Copyright (C) 1987, 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
! 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006
Free Software Foundation, Inc.
This file is part of GCC.
*************** extern void init_all_optabs (void);
*** 743,749 ****
/* Call this to initialize an optab function entry. */
extern rtx init_one_libfunc (const char *);
- extern void do_jump_by_parts_equality_rtx (rtx, rtx, rtx);
extern void do_jump_by_parts_greater_rtx (enum machine_mode, int, rtx, rtx,
rtx, rtx);
--- 743,748 ----
Index: expmed.c
===================================================================
*** expmed.c (revision 110873)
--- expmed.c (working copy)
***************
*** 1,7 ****
/* Medium-level subroutines: convert bit-field store and extract
and shifts, multiplies and divides to rtl instructions.
Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
! 1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
This file is part of GCC.
--- 1,8 ----
/* Medium-level subroutines: convert bit-field store and extract
and shifts, multiplies and divides to rtl instructions.
Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
! 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006
! Free Software Foundation, Inc.
This file is part of GCC.
*************** emit_store_flag_force (rtx target, enum
*** 5564,5629 ****
}
/* Perform possibly multi-word comparison and conditional jump to LABEL
! if ARG1 OP ARG2 true where ARG1 and ARG2 are of mode MODE
!
! The algorithm is based on the code in expr.c:do_jump.
!
! Note that this does not perform a general comparison. Only
! variants generated within expmed.c are correctly handled, others
! could be handled if needed. */
static void
do_cmp_and_jump (rtx arg1, rtx arg2, enum rtx_code op, enum machine_mode mode,
rtx label)
{
! /* If this mode is an integer too wide to compare properly,
! compare word by word. Rely on cse to optimize constant cases. */
!
! if (GET_MODE_CLASS (mode) == MODE_INT
! && ! can_compare_p (op, mode, ccp_jump))
! {
! rtx label2 = gen_label_rtx ();
!
! switch (op)
! {
! case LTU:
! do_jump_by_parts_greater_rtx (mode, 1, arg2, arg1, label2, label);
! break;
!
! case LEU:
! do_jump_by_parts_greater_rtx (mode, 1, arg1, arg2, label, label2);
! break;
!
! case LT:
! do_jump_by_parts_greater_rtx (mode, 0, arg2, arg1, label2, label);
! break;
!
! case GT:
! do_jump_by_parts_greater_rtx (mode, 0, arg1, arg2, label2, label);
! break;
!
! case GE:
! do_jump_by_parts_greater_rtx (mode, 0, arg2, arg1, label, label2);
! break;
!
! /* do_jump_by_parts_equality_rtx compares with zero. Luckily
! that's the only equality operations we do */
! case EQ:
! gcc_assert (arg2 == const0_rtx && mode == GET_MODE(arg1));
! do_jump_by_parts_equality_rtx (arg1, label2, label);
! break;
!
! case NE:
! gcc_assert (arg2 == const0_rtx && mode == GET_MODE(arg1));
! do_jump_by_parts_equality_rtx (arg1, label, label2);
! break;
!
! default:
! gcc_unreachable ();
! }
!
! emit_label (label2);
! }
! else
! emit_cmp_and_jump_insns (arg1, arg2, op, NULL_RTX, mode, 0, label);
}
--- 5565,5578 ----
}
/* Perform possibly multi-word comparison and conditional jump to LABEL
! if ARG1 OP ARG2 true where ARG1 and ARG2 are of mode MODE. This is
! now a thin wrapper around do_compare_rtx_and_jump. */
static void
do_cmp_and_jump (rtx arg1, rtx arg2, enum rtx_code op, enum machine_mode mode,
rtx label)
{
! int unsignedp = (op == LTU || op == LEU || op == GTU || op == GEU);
! do_compare_rtx_and_jump (arg1, arg2, op, unsignedp, mode,
! NULL_RTX, NULL_RTX, label);
}
Index: stmt.c
===================================================================
*** stmt.c (revision 110873)
--- stmt.c (working copy)
***************
*** 1,6 ****
/* Expands front end tree to back end RTL for GCC
Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997,
! 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005
Free Software Foundation, Inc.
This file is part of GCC.
--- 1,6 ----
/* Expands front end tree to back end RTL for GCC
Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997,
! 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006
Free Software Foundation, Inc.
This file is part of GCC.
*************** static bool check_unique_operand_names (
*** 112,118 ****
static char *resolve_operand_name_1 (char *, tree, tree);
static void expand_null_return_1 (void);
static void expand_value_return (rtx);
- static void do_jump_if_equal (rtx, rtx, rtx, int);
static int estimate_case_costs (case_node_ptr);
static bool lshift_cheap_p (void);
static int case_bit_test_cmp (const void *, const void *);
--- 112,117 ----
*************** expand_case (tree exp)
*** 2588,2608 ****
free_temp_slots ();
}
! /* Generate code to jump to LABEL if OP1 and OP2 are equal. */
static void
! do_jump_if_equal (rtx op1, rtx op2, rtx label, int unsignedp)
{
! if (GET_CODE (op1) == CONST_INT && GET_CODE (op2) == CONST_INT)
! {
! if (op1 == op2)
! emit_jump (label);
! }
! else
! emit_cmp_and_jump_insns (op1, op2, EQ, NULL_RTX,
! (GET_MODE (op1) == VOIDmode
! ? GET_MODE (op2) : GET_MODE (op1)),
! unsignedp, label);
}
/* Not all case values are encountered equally. This function
--- 2587,2600 ----
free_temp_slots ();
}
! /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. */
static void
! do_jump_if_equal (enum machine_mode mode, rtx op0, rtx op1, rtx label,
! int unsignedp)
{
! do_compare_rtx_and_jump (op0, op1, EQ, unsignedp, mode,
! NULL_RTX, NULL_RTX, label);
}
/* Not all case values are encountered equally. This function
*************** emit_case_nodes (rtx index, case_node_pt
*** 2954,2960 ****
/* Node is single valued. First see if the index expression matches
this node and then check our children, if any. */
! do_jump_if_equal (index,
convert_modes (mode, imode,
expand_normal (node->low),
unsignedp),
--- 2946,2952 ----
/* Node is single valued. First see if the index expression matches
this node and then check our children, if any. */
! do_jump_if_equal (mode, index,
convert_modes (mode, imode,
expand_normal (node->low),
unsignedp),
*************** emit_case_nodes (rtx index, case_node_pt
*** 3007,3013 ****
/* See if the value matches what the right hand side
wants. */
! do_jump_if_equal (index,
convert_modes (mode, imode,
expand_normal (node->right->low),
unsignedp),
--- 2999,3005 ----
/* See if the value matches what the right hand side
wants. */
! do_jump_if_equal (mode, index,
convert_modes (mode, imode,
expand_normal (node->right->low),
unsignedp),
*************** emit_case_nodes (rtx index, case_node_pt
*** 3016,3022 ****
/* See if the value matches what the left hand side
wants. */
! do_jump_if_equal (index,
convert_modes (mode, imode,
expand_normal (node->left->low),
unsignedp),
--- 3008,3014 ----
/* See if the value matches what the left hand side
wants. */
! do_jump_if_equal (mode, index,
convert_modes (mode, imode,
expand_normal (node->left->low),
unsignedp),
*************** emit_case_nodes (rtx index, case_node_pt
*** 3082,3088 ****
/* We cannot process node->right normally
since we haven't ruled out the numbers less than
this node's value. So handle node->right explicitly. */
! do_jump_if_equal (index,
convert_modes
(mode, imode,
expand_normal (node->right->low),
--- 3074,3080 ----
/* We cannot process node->right normally
since we haven't ruled out the numbers less than
this node's value. So handle node->right explicitly. */
! do_jump_if_equal (mode, index,
convert_modes
(mode, imode,
expand_normal (node->right->low),
*************** emit_case_nodes (rtx index, case_node_pt
*** 3113,3119 ****
/* We cannot process node->left normally
since we haven't ruled out the numbers less than
this node's value. So handle node->left explicitly. */
! do_jump_if_equal (index,
convert_modes
(mode, imode,
expand_normal (node->left->low),
--- 3105,3111 ----
/* We cannot process node->left normally
since we haven't ruled out the numbers less than
this node's value. So handle node->left explicitly. */
! do_jump_if_equal (mode, index,
convert_modes
(mode, imode,
expand_normal (node->left->low),
Roger
--