cprop "fix"
Jan Hubicka
jh@suse.cz
Sat Jul 13 12:00:00 GMT 2002
Hi,
when the copy propagation is formulated in literature, it always contain local
and global passes. Our cprop does only the global stuff, probably assuming
that local CSE will do rest of job. It does not - the main problem is that CSE
does contain register pressure reduction heuristics that makes it sometimes to
decide to use new register instead of original after copy instruction defacto
reverting effect of copy propagation. Since CSE looses track of things on
complex CFG, it does so partly making both copies to be alive increasing
register pressure.
In the past I experimented with patch disabling the heuristics but it
does waste code quallity and additionally PRE pass is seriously crippled
by this fact especially in the second iteration, when redundant reg-reg
copies are more common and thus expressions appears to be different when
they are not.
The attached patch "fixes" our cprop implementation by adding the local
counterpart that is really easy given the infrastructure we developed.
It is effective on about any more complex function. For instance on
combine.c there is done 492 constant propagation instead of 130 and
1141 copy propagation instead of 486. Additionally 862 redundant
expressions are elliminated instead of 712 and in combine_simplify_rtx
after GCSE 216 trivially dead instructions are killed, next 5 after
local CSE pass, while oriiginaly 15 instructions are killed after GCSE
and 80 after local CSE. (I believe the local CSE pass run just after
GCSE can be elliminated now saving compilation time).
The results on code size are bit smaller - about 800 instructions for
combine.s, still I believe it is good thing to do and additionally if we
break up GCSE I think we should run cprop before first local CSE and
cleanup the CFG to elliminate dead and unreachable code before the slow
CSE beast.
I've also implemented the simple local CSE for a experiment but it is not that
effective doing just about 60 substitutions in combine. All of them seems to be
of the form:
(set (mem) (reg X))
(set (reg Y) (same mem))
I am surprised our local CSE don't know how to handle it, but I will check it
separately.
Honza
Sat Jul 13 20:31:17 CEST 2002 Jan Hubicka <jh@suse.cz>
* gcse.c: Include cselib.h
(constptop_register): Break out from ...
(cprop_insn): ... here; kill basic_block argument.
(do_local_cprop, local_cprop_pass): New functions.
(one_cprop_pass): Call local_cprop_pass.
Index: gcse.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/gcse.c,v
retrieving revision 1.208
diff -c -3 -p -r1.208 gcse.c
*** gcse.c 28 Jun 2002 23:41:19 -0000 1.208
--- gcse.c 13 Jul 2002 18:30:07 -0000
*************** Software Foundation, 59 Temple Place - S
*** 162,167 ****
--- 162,168 ----
#include "except.h"
#include "ggc.h"
#include "params.h"
+ #include "cselib.h"
#include "obstack.h"
#define obstack_chunk_alloc gmalloc
*************** static int cprop_jump PARAMS ((basic_bl
*** 613,621 ****
static void mems_conflict_for_gcse_p PARAMS ((rtx, rtx, void *));
static int load_killed_in_block_p PARAMS ((basic_block, int, rtx, int));
static void canon_list_insert PARAMS ((rtx, rtx, void *));
! static int cprop_insn PARAMS ((basic_block, rtx, int));
static int cprop PARAMS ((int));
static int one_cprop_pass PARAMS ((int, int));
static struct expr *find_bypass_set PARAMS ((int, int));
static int bypass_block PARAMS ((basic_block, rtx, rtx));
static int bypass_conditional_jumps PARAMS ((void));
--- 614,623 ----
static void mems_conflict_for_gcse_p PARAMS ((rtx, rtx, void *));
static int load_killed_in_block_p PARAMS ((basic_block, int, rtx, int));
static void canon_list_insert PARAMS ((rtx, rtx, void *));
! static int cprop_insn PARAMS ((rtx, int));
static int cprop PARAMS ((int));
static int one_cprop_pass PARAMS ((int, int));
+ static bool constprop_register PARAMS ((rtx, rtx, rtx, int));
static struct expr *find_bypass_set PARAMS ((int, int));
static int bypass_block PARAMS ((basic_block, rtx, rtx));
static int bypass_conditional_jumps PARAMS ((void));
*************** static void free_insn_expr_list_list PAR
*** 701,706 ****
--- 703,710 ----
static void clear_modify_mem_tables PARAMS ((void));
static void free_modify_mem_tables PARAMS ((void));
static rtx gcse_emit_move_after PARAMS ((rtx, rtx, rtx));
+ static bool do_local_cprop PARAMS ((rtx, rtx, int));
+ static void local_cprop_pass PARAMS ((int));
/* Entry point for global common subexpression elimination.
F is the first instruction in the function. */
*************** cprop_jump (bb, setcc, jump, from, src)
*** 4149,4160 ****
return 1;
}
/* Perform constant and copy propagation on INSN.
The result is non-zero if a change was made. */
static int
! cprop_insn (bb, insn, alter_jumps)
! basic_block bb;
rtx insn;
int alter_jumps;
{
--- 4153,4200 ----
return 1;
}
+ static bool
+ constprop_register (insn, from, to, alter_jumps)
+ rtx insn;
+ rtx from;
+ rtx to;
+ int alter_jumps;
+ {
+ rtx sset;
+
+ /* Check for reg or cc0 setting instructions followed by
+ conditional branch instructions first. */
+ if (alter_jumps
+ && (sset = single_set (insn)) != NULL
+ && any_condjump_p (NEXT_INSN (insn)) && onlyjump_p (NEXT_INSN (insn)))
+ {
+ rtx dest = SET_DEST (sset);
+ if ((REG_P (dest) || CC0_P (dest))
+ && cprop_jump (BLOCK_FOR_INSN (insn), insn, NEXT_INSN (insn), from, to))
+ return 1;
+ }
+
+ /* Handle normal insns next. */
+ if (GET_CODE (insn) == INSN
+ && try_replace_reg (from, to, insn))
+ return 1;
+
+ /* 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 ...)) */
+ else if (alter_jumps && any_condjump_p (insn) && onlyjump_p (insn))
+ return cprop_jump (BLOCK_FOR_INSN (insn), NULL, insn, from, to);
+ return 0;
+ }
+
/* Perform constant and copy propagation on INSN.
The result is non-zero if a change was made. */
static int
! cprop_insn (insn, alter_jumps)
rtx insn;
int alter_jumps;
{
*************** cprop_insn (bb, insn, alter_jumps)
*** 4207,4262 ****
/* Constant propagation. */
if (CONSTANT_P (src))
{
! rtx sset;
!
! /* Check for reg or cc0 setting instructions followed by
! conditional branch instructions first. */
! if (alter_jumps
! && (sset = single_set (insn)) != NULL
! && any_condjump_p (NEXT_INSN (insn))
! && onlyjump_p (NEXT_INSN (insn)))
! {
! rtx dest = SET_DEST (sset);
! if ((REG_P (dest) || CC0_P (dest))
! && cprop_jump (bb, insn, NEXT_INSN (insn),
! reg_used->reg_rtx, src))
! {
! changed = 1;
! break;
! }
! }
!
! /* Handle normal insns next. */
! if (GET_CODE (insn) == INSN
! && try_replace_reg (reg_used->reg_rtx, src, insn))
{
changed = 1;
const_prop_count++;
if (gcse_file != NULL)
{
! fprintf (gcse_file, "CONST-PROP: Replacing reg %d in ",
! regno);
! fprintf (gcse_file, "insn %d with constant ",
! 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 ...)) */
- else if (alter_jumps
- && any_condjump_p (insn)
- && onlyjump_p (insn))
- changed |= cprop_jump (bb, NULL, insn, reg_used->reg_rtx, src);
-
}
else if (GET_CODE (src) == REG
&& REGNO (src) >= FIRST_PSEUDO_REGISTER
--- 4247,4264 ----
/* Constant propagation. */
if (CONSTANT_P (src))
{
! if (constprop_register (insn, reg_used->reg_rtx, src, alter_jumps))
{
changed = 1;
const_prop_count++;
if (gcse_file != NULL)
{
! fprintf (gcse_file, "GLOBAL CONST-PROP: Replacing reg %d in ", regno);
! fprintf (gcse_file, "insn %d with constant ", INSN_UID (insn));
print_rtl (gcse_file, src);
fprintf (gcse_file, "\n");
}
}
}
else if (GET_CODE (src) == REG
&& REGNO (src) >= FIRST_PSEUDO_REGISTER
*************** cprop_insn (bb, insn, alter_jumps)
*** 4268,4274 ****
copy_prop_count++;
if (gcse_file != NULL)
{
! fprintf (gcse_file, "COPY-PROP: Replacing reg %d in insn %d",
regno, INSN_UID (insn));
fprintf (gcse_file, " with reg %d\n", REGNO (src));
}
--- 4270,4276 ----
copy_prop_count++;
if (gcse_file != NULL)
{
! fprintf (gcse_file, "GLOBAL COPY-PROP: Replacing reg %d in insn %d",
regno, INSN_UID (insn));
fprintf (gcse_file, " with reg %d\n", REGNO (src));
}
*************** cprop_insn (bb, insn, alter_jumps)
*** 4285,4290 ****
--- 4287,4382 ----
return changed;
}
+ static bool
+ do_local_cprop (x, insn, alter_jumps)
+ rtx x;
+ rtx insn;
+ int alter_jumps;
+ {
+ rtx newreg = NULL, newcnst = NULL;
+
+ /* Rule out USE instructions and ASM statements as we don't want to change the hard
+ registers mentioned. */
+ if (GET_CODE (x) == REG
+ && (REGNO (x) >= FIRST_PSEUDO_REGISTER
+ || (GET_CODE (PATTERN (insn)) != USE && asm_noperands (PATTERN (insn)) < 0)))
+ {
+ cselib_val *val = cselib_lookup (x, GET_MODE (x), 0);
+ struct elt_loc_list *l;
+
+ if (!val)
+ return false;
+ for (l = val->locs; l; l = l->next)
+ {
+ rtx this_rtx = l->loc;
+ if (CONSTANT_P (this_rtx))
+ newcnst = this_rtx;
+ if (REG_P (this_rtx) && REGNO (this_rtx) >= FIRST_PSEUDO_REGISTER)
+ newreg = this_rtx;
+ }
+ if (newcnst && constprop_register (insn, x, newcnst, alter_jumps))
+ {
+ if (gcse_file != NULL)
+ {
+ fprintf (gcse_file, "LOCAL CONST-PROP: Replacing reg %d in ",
+ REGNO (x));
+ fprintf (gcse_file, "insn %d with constant ",
+ INSN_UID (insn));
+ print_rtl (gcse_file, newcnst);
+ fprintf (gcse_file, "\n");
+ }
+ const_prop_count++;
+ return true;
+ }
+ else if (newreg && newreg != x && try_replace_reg (x, newreg, insn))
+ {
+ if (gcse_file != NULL)
+ {
+ fprintf (gcse_file,
+ "LOCAL COPY-PROP: Replacing reg %d in insn %d",
+ REGNO (x), INSN_UID (insn));
+ fprintf (gcse_file, " with reg %d\n", REGNO (newreg));
+ }
+ copy_prop_count++;
+ return true;
+ }
+ }
+ return false;
+ }
+
+ static void
+ local_cprop_pass (alter_jumps)
+ int alter_jumps;
+ {
+ rtx insn;
+ struct reg_use *reg_used;
+
+ cselib_init ();
+ for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
+ {
+ if (INSN_P (insn))
+ {
+ rtx note = find_reg_equal_equiv_note (insn);
+
+ do
+ {
+ reg_use_count = 0;
+ note_uses (&PATTERN (insn), find_used_regs, NULL);
+ if (note)
+ find_used_regs (&XEXP (note, 0), NULL);
+
+ for (reg_used = ®_use_table[0]; reg_use_count > 0;
+ reg_used++, reg_use_count--)
+ if (do_local_cprop (reg_used->reg_rtx, insn, alter_jumps))
+ break;
+ }
+ while (reg_use_count);
+ }
+ cselib_process_insn (insn);
+ }
+ cselib_finish ();
+ }
+
/* Forward propagate copies. This includes copies and constants. Return
non-zero if a change was made. */
*************** cprop (alter_jumps)
*** 4316,4322 ****
insn = NEXT_INSN (insn))
if (INSN_P (insn))
{
! changed |= cprop_insn (bb, insn, alter_jumps);
/* Keep track of everything modified by this insn. */
/* ??? Need to be careful w.r.t. mods done to INSN. Don't
--- 4408,4414 ----
insn = NEXT_INSN (insn))
if (INSN_P (insn))
{
! changed |= cprop_insn (insn, alter_jumps);
/* Keep track of everything modified by this insn. */
/* ??? Need to be careful w.r.t. mods done to INSN. Don't
*************** one_cprop_pass (pass, alter_jumps)
*** 4346,4351 ****
--- 4438,4445 ----
const_prop_count = 0;
copy_prop_count = 0;
+ local_cprop_pass (alter_jumps);
+
alloc_set_hash_table (max_cuid);
compute_set_hash_table ();
if (gcse_file)
More information about the Gcc-patches
mailing list