Crossjumping of tablejumps
Josef Zlomek
zlomj9am@artax.karlin.mff.cuni.cz
Mon Mar 3 18:14:00 GMT 2003
Hi,
this patch adds crossjumping of identical tablejumps. When there are
two identical jump tables, it replaces the references to one table by
references to another and then crossjumping deletes common instructions
as usual resulting in deleting of one jump table. The code size is thus smaller.
For example in the following code, there are 2 jump tables without this
patch, one of them is deleted by this patch. Although the following code seems
to be rare (no one could write such an ugly code) it appears in some sources
(probably generated by macros or so) because a similar code was a testcase
(several times) for a bug I have fixed some time ago.
int *f, *g;
int main (void)
{
switch (*f)
{
case 0:
{
switch (*g)
{
case 0: *g = 1; break;
case 1:
case 2: *g = 1; break;
case 3:
case 4: *g = 2; break;
}
break;
}
case 1:
{
switch (*g)
{
case 0: *g = 1; break;
case 1:
case 2: *g = 1; break;
case 3:
case 4: *g = 2; break;
}
}
}
return 0;
}
Bootstrapped/regtested i386 and x86-64.
OK for mainline?
Josef
2003-03-03 Josef Zlomek <zlomekj@suse.cz>
* cfgcleanup.c (outgoing_edges_match): Compare the jump tables and if they
are identical, replace references to one table by references to another,
and thus crossjump tablejumps.
* loop.c (load_mems): Moved setting the JUMP_LABEL to replace_label.
(replace_label): Moved to rtlanal.c.
(struct rtx_pair): Moved to rtl.h.
* rtl.h (replace_label): New extern function.
(struct rtx_pair): Moved from loop.c.
* rtlanal.c (replace_label): Moved from loop.c.
Index: cfgcleanup.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgcleanup.c,v
retrieving revision 1.74
diff -c -3 -p -r1.74 cfgcleanup.c
*** cfgcleanup.c 22 Feb 2003 10:02:29 -0000 1.74
--- cfgcleanup.c 3 Mar 2003 12:59:25 -0000
*************** outgoing_edges_match (mode, bb1, bb2)
*** 1243,1252 ****
/* Generic case - we are seeing a computed jump, table jump or trapping
instruction. */
/* First ensure that the instructions match. There may be many outgoing
! edges so this test is generally cheaper.
! ??? Currently the tablejumps will never match, as they do have
! different tables. */
if (!insns_match_p (mode, bb1->end, bb2->end))
return false;
--- 1243,1316 ----
/* Generic case - we are seeing a computed jump, table jump or trapping
instruction. */
+ /* Check whether there are tablejumps in the end of BB1 and BB2
+ and merge them if they are identical. */
+
+ if (onlyjump_p (bb1->end) && onlyjump_p (bb2->end))
+ {
+ rtx label1, label2;
+ rtx table1, table2;
+
+ if ((label1 = JUMP_LABEL (bb1->end)) != NULL_RTX
+ && (table1 = NEXT_INSN (label1)) != NULL_RTX
+ && GET_CODE (table1) == JUMP_INSN
+ && (GET_CODE (PATTERN (table1)) == ADDR_VEC
+ || GET_CODE (PATTERN (table1)) == ADDR_DIFF_VEC)
+ && (label2 = JUMP_LABEL (bb2->end)) != NULL_RTX
+ && (table2 = NEXT_INSN (label2)) != NULL_RTX
+ && GET_CODE (table2) == JUMP_INSN
+ && (GET_CODE (PATTERN (table1)) == GET_CODE (PATTERN (table2))))
+ {
+ /* Set REPLACE to true when the tables are identical. */
+ bool replace = false;
+ rtx p1, p2;
+
+ p1 = PATTERN (table1);
+ p2 = PATTERN (table2);
+ if (GET_CODE (p1) == ADDR_VEC && rtx_equal_p (p1, p2))
+ {
+ replace = true;
+ }
+ else if (GET_CODE (p1) == ADDR_DIFF_VEC
+ && (XVECLEN (p1, 1) == XVECLEN (p2, 1))
+ && rtx_equal_p (XEXP (p1, 2), XEXP (p2, 2))
+ && rtx_equal_p (XEXP (p1, 3), XEXP (p2, 3)))
+ {
+ int i;
+
+ replace = true;
+ for (i = XVECLEN (p1, 1) - 1; i >= 0 && replace; i--)
+ if (!rtx_equal_p (XVECEXP (p1, 1, i), XVECEXP (p2, 1, i)))
+ replace = false;
+ }
+
+ if (replace)
+ {
+ rtx insn;
+ rtx_pair rr;
+ bool match;
+
+ /* Replace all references to LABEL1 with LABEL2. */
+ rr.r1 = label1;
+ rr.r2 = label2;
+ for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
+ for_each_rtx (&insn, replace_label, &rr);
+ match = insns_match_p (mode, bb1->end, bb2->end);
+
+ /* Set the original label in BB1->END because when deleting
+ a block whose end is a tablejump, the tablejump referenced from
+ the instruction is deleted too. */
+ rr.r1 = label2;
+ rr.r2 = label1;
+ for_each_rtx (&bb1->end, replace_label, &rr);
+ return match;
+ }
+ return false;
+ }
+ }
+
/* First ensure that the instructions match. There may be many outgoing
! edges so this test is generally cheaper. */
if (!insns_match_p (mode, bb1->end, bb2->end))
return false;
Index: loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop.c,v
retrieving revision 1.445
diff -c -3 -p -r1.445 loop.c
*** loop.c 28 Feb 2003 18:45:38 -0000 1.445
--- loop.c 3 Mar 2003 12:59:26 -0000
*************** static void note_reg_stored PARAMS ((rtx
*** 338,344 ****
static void try_copy_prop PARAMS ((const struct loop *, rtx, unsigned int));
static void try_swap_copy_prop PARAMS ((const struct loop *, rtx,
unsigned int));
- static int replace_label PARAMS ((rtx *, void *));
static rtx check_insn_for_givs PARAMS((struct loop *, rtx, int, int));
static rtx check_insn_for_bivs PARAMS((struct loop *, rtx, int, int));
static rtx gen_add_mult PARAMS ((rtx, rtx, rtx, rtx));
--- 338,343 ----
*************** void debug_giv PARAMS ((const struct ind
*** 363,374 ****
void debug_loop PARAMS ((const struct loop *));
void debug_loops PARAMS ((const struct loops *));
- typedef struct rtx_pair
- {
- rtx r1;
- rtx r2;
- } rtx_pair;
-
typedef struct loop_replace_args
{
rtx match;
--- 362,367 ----
*************** load_mems (loop)
*** 10151,10165 ****
for (p = loop->start; p != loop->end; p = NEXT_INSN (p))
{
for_each_rtx (&p, replace_label, &rr);
-
- /* If this is a JUMP_INSN, then we also need to fix the JUMP_LABEL
- field. This is not handled by for_each_rtx because it doesn't
- handle unprinted ('0') fields. We need to update JUMP_LABEL
- because the immediately following unroll pass will use it.
- replace_label would not work anyways, because that only handles
- LABEL_REFs. */
- if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == end_label)
- JUMP_LABEL (p) = label;
}
}
--- 10144,10149 ----
*************** replace_loop_regs (insn, reg, replacemen
*** 10488,10522 ****
args.replacement = replacement;
for_each_rtx (&insn, replace_loop_reg, &args);
- }
-
- /* Replace occurrences of the old exit label for the loop with the new
- one. DATA is an rtx_pair containing the old and new labels,
- respectively. */
-
- static int
- replace_label (x, data)
- rtx *x;
- void *data;
- {
- rtx l = *x;
- rtx old_label = ((rtx_pair *) data)->r1;
- rtx new_label = ((rtx_pair *) data)->r2;
-
- if (l == NULL_RTX)
- return 0;
-
- if (GET_CODE (l) != LABEL_REF)
- return 0;
-
- if (XEXP (l, 0) != old_label)
- return 0;
-
- XEXP (l, 0) = new_label;
- ++LABEL_NUSES (new_label);
- --LABEL_NUSES (old_label);
-
- return 0;
}
/* Emit insn for PATTERN after WHERE_INSN in basic block WHERE_BB
--- 10472,10477 ----
Index: rtl.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/rtl.h,v
retrieving revision 1.386
diff -c -3 -p -r1.386 rtl.h
*** rtl.h 28 Feb 2003 07:06:33 -0000 1.386
--- rtl.h 3 Mar 2003 12:59:26 -0000
*************** extern rtx set_unique_reg_note PARAMS (
*** 1595,1600 ****
--- 1595,1607 ----
: NULL_RTX)
#define single_set_1(I) single_set_2 (I, PATTERN (I))
+ /* Structure used for passing data to REPLACE_LABEL. */
+ typedef struct rtx_pair
+ {
+ rtx r1;
+ rtx r2;
+ } rtx_pair;
+
extern int rtx_addr_can_trap_p PARAMS ((rtx));
extern bool nonzero_address_p PARAMS ((rtx));
extern int rtx_unstable_p PARAMS ((rtx));
*************** extern int inequality_comparisons_p PARA
*** 1654,1659 ****
--- 1661,1667 ----
extern rtx replace_rtx PARAMS ((rtx, rtx, rtx));
extern rtx replace_regs PARAMS ((rtx, rtx *, unsigned int,
int));
+ extern int replace_label PARAMS ((rtx *, void *));
extern int computed_jump_p PARAMS ((rtx));
typedef int (*rtx_function) PARAMS ((rtx *, void *));
extern int for_each_rtx PARAMS ((rtx *, rtx_function, void *));
Index: rtlanal.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/rtlanal.c,v
retrieving revision 1.147
diff -c -3 -p -r1.147 rtlanal.c
*** rtlanal.c 11 Feb 2003 21:26:48 -0000 1.147
--- rtlanal.c 3 Mar 2003 12:59:26 -0000
*************** computed_jump_p_1 (x)
*** 2845,2850 ****
--- 2845,2884 ----
return 0;
}
+ /* Replace occurrences of the old label in *X with the new one.
+ DATA is an rtx_pair containing the old and new labels, respectively. */
+
+ int
+ replace_label (x, data)
+ rtx *x;
+ void *data;
+ {
+ rtx l = *x;
+ rtx old_label = ((rtx_pair *) data)->r1;
+ rtx new_label = ((rtx_pair *) data)->r2;
+
+ if (l == NULL_RTX)
+ return 0;
+
+ /* If this is a JUMP_INSN, then we also need to fix the JUMP_LABEL
+ field. This is not handled by for_each_rtx because it doesn't
+ handle unprinted ('0') fields. */
+ if (GET_CODE (l) == JUMP_INSN && JUMP_LABEL (l) == old_label)
+ JUMP_LABEL (l) = new_label;
+
+ if (GET_CODE (l) != LABEL_REF)
+ return 0;
+
+ if (XEXP (l, 0) != old_label)
+ return 0;
+
+ XEXP (l, 0) = new_label;
+ ++LABEL_NUSES (new_label);
+ --LABEL_NUSES (old_label);
+
+ return 0;
+ }
+
/* Return nonzero if INSN is an indirect jump (aka computed jump).
Tablejumps and casesi insns are not considered indirect jumps;
More information about the Gcc-patches
mailing list