From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 16806 invoked by alias); 13 Jul 2002 18:49:02 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 16799 invoked from network); 13 Jul 2002 18:49:01 -0000 Received: from unknown (HELO atrey.karlin.mff.cuni.cz) (195.113.31.123) by sources.redhat.com with SMTP; 13 Jul 2002 18:49:01 -0000 Received: by atrey.karlin.mff.cuni.cz (Postfix, from userid 4018) id D1D394F88D; Sat, 13 Jul 2002 20:49:02 +0200 (CEST) Date: Sat, 13 Jul 2002 12:00:00 -0000 From: Jan Hubicka To: gcc-patches@gcc.gnu.org, rth@cygnus.com Subject: cprop "fix" Message-ID: <20020713184902.GD1909@atrey.karlin.mff.cuni.cz> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.3.28i X-SW-Source: 2002-07/txt/msg00618.txt.bz2 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 * 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)