cprop into conditional jumps
Jeffrey A Law
law@hurl.cygnus.com
Wed Mar 10 19:44:00 GMT 1999
This patch allows global constant/copy propagation to propgate values into
conditional jumps on non-cc0 machines.
Consider this example:
int length, width, radius;
enum figure {RECTANGLE, CIRCLE};
main()
{
int area = 0, volume = 0, height;
enum figure kind = RECTANGLE;
for (height = 0; height < 10; height++) {
if (kind == RECTANGLE) {
area += length * width;
volume += length * width * height;
} else if (kind == CIRCLE) {
area += 3.14 * radius * radius;
volume += 3.14 * radius * radius * height;
}
}
process(area, volume);
}
KIND will always have the value RECTANGLE, so it is possible to determine
at compile time whether or not the conditionals involving KIND are true.
Without this patch the loop compiles into the following ocde on my PA:
L$0006
comib,<>,n 0,%r22,L$0007
addl %r26,%r20,%r26
bl L$0005,0
addl %r25,%r21,%r25
L$0007
comib,<>,n 1,%r22,L$0005
stw %r19,-16(0,%r30)
fcnvxf,sgl,dbl %fr27L,%fr26
fldws -16(0,%r30),%fr22L
stw %r26,-16(0,%r30)
fcnvxf,sgl,dbl %fr22L,%fr25
fldws -16(0,%r30),%fr23L
fmpy,dbl %fr26,%fr28,%fr22
stw %r25,-16(0,%r30)
fcnvxf,sgl,dbl %fr23L,%fr24
fmpy,dbl %fr22,%fr26,%fr22
fldws -16(0,%r30),%fr26L
fmpyadd,dbl %fr22,%fr25,%fr25,%fr22,%fr24
fcnvxf,sgl,dbl %fr26L,%fr23
fcnvfxt,dbl,sgl %fr24,%fr24L
fstws %fr24L,-16(0,%r30)
fadd,dbl %fr23,%fr25,%fr23
ldw -16(0,%r30),%r26
fcnvfxt,dbl,sgl %fr23,%fr23L
fstws %fr23L,-16(0,%r30)
ldw -16(0,%r30),%r25
L$0005
ldo 1(%r19),%r19
comib,>= 9,%r19,L$0006
addl %r21,%r20,%r21
Note the two conditional branches (first two comib instructions).
After applying the patch the code collapses into:
L$0006
addl %r25,%r21,%r25
addib,>= -1,%r20,L$0006
addl %r21,%r19,%r21
Which is a hell of a lot more efficient ;-)
Note this code does nothing for cc0 machines like the x86, and m68k. If
someone wants to try to extend this code to work on those machines, feel
free to contact me.
* gcse.c (run_jump_opt_after_gcse): New variable.
(gcse_main): Returns an integer.
(hash_scan_set): Record initializations from CONST_DOUBLEs too.
(try_replace_reg): Update some comments.
(cprop_insn): Allow propagation into some JUMP_INSNs too.
* rtl.h (gcse_main): Update prototype.
* toplev.c (rest_of_compilation): If gcse_main returns nonzero,
then run a jump optimization pass.
* jump.c (delete_barrier_successors): Delete nop jumps too.
Index: gcse.c
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/gcse.c,v
retrieving revision 1.28
diff -c -3 -p -r1.28 gcse.c
*** gcse.c 1999/03/06 05:34:18 1.28
--- gcse.c 1999/03/11 03:34:33
*************** yyy
*** 188,194 ****
4) Perform global cse.
! 5) Perform another pass of copy/constant propagation [only if PRE].
Two passes of copy/constant propagation are done because the first one
enables more GCSE and the second one helps to clean up the copies that
--- 188,194 ----
4) Perform global cse.
! 5) Perform another pass of copy/constant propagation.
Two passes of copy/constant propagation are done because the first one
enables more GCSE and the second one helps to clean up the copies that
*************** static int_list_ptr *s_succs;
*** 333,338 ****
--- 333,347 ----
static int *num_preds;
static int *num_succs;
+ /* Note whether or not we should run jump optimization after gcse. We
+ want to do this for two cases.
+
+ * If we changed any jumps via cprop.
+
+ * If we added any labels via edge splitting. */
+
+ static int run_jump_opt_after_gcse;
+
/* Hash table of expressions. */
struct expr
*************** static void add_label_notes PROTO
*** 648,654 ****
/* Entry point for global common subexpression elimination.
F is the first instruction in the function. */
! void
gcse_main (f, file)
rtx f;
FILE *file;
--- 657,663 ----
/* Entry point for global common subexpression elimination.
F is the first instruction in the function. */
! int
gcse_main (f, file)
rtx f;
FILE *file;
*************** gcse_main (f, file)
*** 661,670 ****
/* Point to release obstack data from for each pass. */
char *gcse_obstack_bottom;
/* It's impossible to construct a correct control flow graph in the
presense of setjmp, so just punt to be safe. */
if (current_function_calls_setjmp)
! return;
/* For calling dump_foo fns from gdb. */
debug_stderr = stderr;
--- 670,681 ----
/* Point to release obstack data from for each pass. */
char *gcse_obstack_bottom;
+ run_jump_opt_after_gcse = 0;
+
/* It's impossible to construct a correct control flow graph in the
presense of setjmp, so just punt to be safe. */
if (current_function_calls_setjmp)
! return 0;
/* For calling dump_foo fns from gdb. */
debug_stderr = stderr;
*************** gcse_main (f, file)
*** 677,683 ****
{
/* Free storage allocated by find_basic_blocks. */
free_basic_block_vars (0);
! return;
}
/* See what modes support reg/reg copy operations. */
--- 688,694 ----
{
/* Free storage allocated by find_basic_blocks. */
free_basic_block_vars (0);
! return 0;
}
/* See what modes support reg/reg copy operations. */
*************** gcse_main (f, file)
*** 778,783 ****
--- 789,795 ----
free_bb_mem ();
/* Free storage allocated by find_basic_blocks. */
free_basic_block_vars (0);
+ return run_jump_opt_after_gcse;
}
/* Misc. utilities. */
*************** hash_scan_set (pat, insn, set_p)
*** 1800,1806 ****
&& REGNO (src) >= FIRST_PSEUDO_REGISTER
&& can_copy_p [GET_MODE (dest)])
/* ??? CONST_INT:wip */
! || GET_CODE (src) == CONST_INT)
/* A copy is not available if its src or dest is subsequently
modified. Here we want to search from INSN+1 on, but
oprs_available_p searches from INSN on. */
--- 1812,1819 ----
&& REGNO (src) >= FIRST_PSEUDO_REGISTER
&& can_copy_p [GET_MODE (dest)])
/* ??? CONST_INT:wip */
! || GET_CODE (src) == CONST_INT
! || GET_CODE (src) == CONST_DOUBLE)
/* A copy is not available if its src or dest is subsequently
modified. Here we want to search from INSN+1 on, but
oprs_available_p searches from INSN on. */
*************** static int
*** 3690,3695 ****
--- 3703,3713 ----
try_replace_reg (from, to, insn)
rtx from, to, insn;
{
+ /* If this fails we could try to simplify the result of the
+ replacement and attempt to recognize the simplified insn.
+
+ But we need a general simplify_rtx that doesn't have pass
+ specific state variables. I'm not aware of one at the moment. */
return validate_replace_src (from, to, insn);
}
*************** cprop_insn (insn)
*** 3723,3730 ****
struct reg_use *reg_used;
int changed = 0;
! /* ??? For now only propagate into SETs. */
! if (GET_CODE (insn) != INSN
|| GET_CODE (PATTERN (insn)) != SET)
return 0;
--- 3741,3750 ----
struct reg_use *reg_used;
int changed = 0;
! /* Only propagate into SETs. Note that a conditional jump is a
! SET with pc_rtx as the destination. */
! if ((GET_CODE (insn) != INSN
! && GET_CODE (insn) != JUMP_INSN)
|| GET_CODE (PATTERN (insn)) != SET)
return 0;
*************** cprop_insn (insn)
*** 3760,3768 ****
abort ();
src = SET_SRC (pat);
! if (GET_CODE (src) == CONST_INT)
{
! if (try_replace_reg (reg_used->reg_rtx, src, insn))
{
changed = 1;
const_prop_count++;
--- 3780,3791 ----
abort ();
src = SET_SRC (pat);
! /* Constant propagation. */
! if (GET_CODE (src) == CONST_INT || GET_CODE (src) == CONST_DOUBLE)
{
! /* Handle normal insns first. */
! if (GET_CODE (insn) == INSN
! && try_replace_reg (reg_used->reg_rtx, src, insn))
{
changed = 1;
const_prop_count++;
*************** cprop_insn (insn)
*** 3770,3781 ****
{
fprintf (gcse_file, "CONST-PROP: Replacing reg %d in insn %d with constant ",
regno, INSN_UID (insn));
! fprintf (gcse_file, HOST_WIDE_INT_PRINT_DEC, INTVAL (src));
fprintf (gcse_file, "\n");
}
/* The original insn setting reg_used may or may not now be
deletable. We leave the deletion to flow. */
}
}
else if (GET_CODE (src) == REG
--- 3793,3881 ----
{
fprintf (gcse_file, "CONST-PROP: Replacing reg %d in insn %d with constant ",
regno, INSN_UID (insn));
! print_rtl (gcse_file, src);
fprintf (gcse_file, "\n");
}
/* The original insn setting reg_used may or may not now be
deletable. We leave the deletion to flow. */
+ }
+
+ /* Try to propagate a CONST_INT into a conditional jump.
+ We're pretty specific about what we will handle in this
+ code, we can extend this as necessary over time.
+
+ Right now the insn in question must look like
+
+ (set (pc) (if_then_else ...))
+
+ Note this does not currently handle machines which use cc0. */
+ else if (GET_CODE (insn) == JUMP_INSN && condjump_p (insn))
+ {
+ /* We want a copy of the JUMP_INSN so we can modify it
+ in-place as needed without effecting the original. */
+ rtx copy = copy_rtx (insn);
+ rtx set = PATTERN (copy);
+ rtx temp;
+
+ /* Replace the register with the appropriate constant. */
+ replace_rtx (SET_SRC (set), reg_used->reg_rtx, src);
+
+ temp = simplify_ternary_operation (GET_CODE (SET_SRC (set)),
+ GET_MODE (SET_SRC (set)),
+ GET_MODE (XEXP (SET_SRC (set), 0)),
+ XEXP (SET_SRC (set), 0),
+ XEXP (SET_SRC (set), 1),
+ XEXP (SET_SRC (set), 2));
+
+ /* If no simplification can be made, then try the next
+ register. */
+ if (temp)
+ SET_SRC (set) = temp;
+ else
+ continue;
+
+ /* That may have changed the structure of TEMP, so
+ force it to be rerecognized if it has not turned
+ into a nop or unconditional jump. */
+
+ INSN_CODE (copy) = -1;
+ if ((SET_DEST (set) == pc_rtx
+ && (SET_SRC (set) == pc_rtx
+ || GET_CODE (SET_SRC (set)) == LABEL_REF))
+ || recog (PATTERN (copy), copy, NULL) >= 0)
+ {
+ /* This has either become an unconditional jump
+ or a nop-jump. We'd like to delete nop jumps
+ here, but doing so confuses gcse. So we just
+ make the replacement and let later passes
+ sort things out. */
+ PATTERN (insn) = set;
+ INSN_CODE (insn) = -1;
+
+ /* One less use of the label this insn used to jump to
+ if we turned this into a NOP jump. */
+ if (SET_SRC (set) == pc_rtx && JUMP_LABEL (insn) != 0)
+ --LABEL_NUSES (JUMP_LABEL (insn));
+
+ /* If this has turned into an unconditional jump,
+ then put a barrier after it so that the unreachable
+ code will be deleted. */
+ if (GET_CODE (SET_SRC (set)) == LABEL_REF)
+ emit_barrier_after (insn);
+
+ run_jump_opt_after_gcse = 1;
+
+ changed = 1;
+ const_prop_count++;
+ if (gcse_file != NULL)
+ {
+ fprintf (gcse_file, "CONST-PROP: Replacing reg %d in insn %d with constant ",
+ regno, INSN_UID (insn));
+ print_rtl (gcse_file, src);
+ fprintf (gcse_file, "\n");
+ }
+ }
}
}
else if (GET_CODE (src) == REG
Index: rtl.h
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/rtl.h,v
retrieving revision 1.89
diff -c -3 -p -r1.89 rtl.h
*** rtl.h 1999/02/25 23:45:35 1.89
--- rtl.h 1999/03/11 03:34:37
*************** extern rtx expand_mult_highpart PROTO (
*** 1452,1458 ****
/* In gcse.c */
#ifdef BUFSIZ
! extern void gcse_main PROTO ((rtx, FILE *));
#endif
/* In global.c */
--- 1452,1458 ----
/* In gcse.c */
#ifdef BUFSIZ
! extern int gcse_main PROTO ((rtx, FILE *));
#endif
/* In global.c */
Index: toplev.c
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/toplev.c,v
retrieving revision 1.158
diff -c -3 -p -r1.158 toplev.c
*** toplev.c 1999/03/09 06:40:49 1.158
--- toplev.c 1999/03/11 03:34:50
*************** rest_of_compilation (decl)
*** 3789,3795 ****
if (gcse_dump)
open_dump_file (".gcse", IDENTIFIER_POINTER (DECL_NAME (decl)));
! TIMEVAR (gcse_time, gcse_main (insns, rtl_dump_file));
if (gcse_dump)
{
--- 3789,3804 ----
if (gcse_dump)
open_dump_file (".gcse", IDENTIFIER_POINTER (DECL_NAME (decl)));
! TIMEVAR (gcse_time, tem = gcse_main (insns, rtl_dump_file));
!
! /* If gcse altered any jumps, rerun jump optimizations to clean
! things up. */
! if (tem)
! {
! TIMEVAR (jump_time, jump_optimize (insns, !JUMP_CROSS_JUMP,
! !JUMP_NOOP_MOVES,
! !JUMP_AFTER_REGSCAN));
! }
if (gcse_dump)
{
Index: jump.c
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/jump.c,v
retrieving revision 1.54
diff -c -3 -p -r1.54 jump.c
*** jump.c 1999/02/25 23:45:23 1.54
--- jump.c 1999/03/11 03:35:04
*************** init_label_info (f)
*** 2076,2082 ****
return largest_uid;
}
! /* Delete insns following barriers, up to next label. */
static void
delete_barrier_successors (f)
rtx f;
--- 2076,2084 ----
return largest_uid;
}
! /* Delete insns following barriers, up to next label.
!
! Also delete no-op jumps created by gcse. */
static void
delete_barrier_successors (f)
rtx f;
*************** delete_barrier_successors (f)
*** 2098,2103 ****
--- 2100,2113 ----
}
/* INSN is now the code_label. */
}
+ /* Also remove (set (pc) (pc)) insns which can be created by
+ gcse. We eliminate such insns now to avoid having them
+ cause problems later. */
+ else if (GET_CODE (insn) == JUMP_INSN
+ && SET_SRC (PATTERN (insn)) == pc_rtx
+ && SET_DEST (PATTERN (insn)) == pc_rtx)
+ insn = delete_insn (insn);
+
else
insn = NEXT_INSN (insn);
}
More information about the Gcc-patches
mailing list