diff options
| -rw-r--r-- | gcc/ChangeLog | 14 | ||||
| -rw-r--r-- | gcc/doc/passes.texi | 17 | ||||
| -rw-r--r-- | gcc/gcse.c | 129 | ||||
| -rw-r--r-- | gcc/rtl.h | 3 | ||||
| -rw-r--r-- | gcc/timevar.def | 3 | ||||
| -rw-r--r-- | gcc/toplev.c | 28 |
6 files changed, 179 insertions, 15 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 0d7d19c..a98b2b3 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,17 @@ +2003-01-15 Roger Sayle <roger@eyesopen.com> + + * gcse.c (one_cprop_pass): Change function arguments to take both + cprop_jumps and bypass_jumps flags instead of just alter_jumps. + (gcse_main): Update calls to one_cprop_pass, disabling bypassing. + (bypass_jumps): New function to perform separate jump bypassing pass. + * rtl.h (bypass_jumps): Add function prototype. + * timevar.def (TV_BYPASS): New timing variable. + * toplev.c (enum dump_file_index): Add new entry DFI_bypass. + (dump_file): New entry for the bypass RTL dump file. + (rest_of_compilation): Insert new jump bypassing optimization + pass after loop. + * doc/passes.texi: Document new pass. + 2003-01-15 John David Anglin <dave@hiauly1.hia.nrc.ca> * som.h (SUPPORTS_WEAK, SUPPORTS_ONE_ONLY, MAKE_DECL_ONE_ONLY, diff --git a/gcc/doc/passes.texi b/gcc/doc/passes.texi index 8a96a69..fe0fc2e 100644 --- a/gcc/doc/passes.texi +++ b/gcc/doc/passes.texi @@ -1,5 +1,5 @@ -@c Copyright (C) 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 2002, -@c 1999, 2000, 2001 Free Software Foundation, Inc. +@c Copyright (C) 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, +@c 2000, 2001, 2002, 2003 Free Software Foundation, Inc. @c This is part of the GCC manual. @c For copying conditions, see the file gcc.texi. @@ -338,6 +338,19 @@ The option @option{-dL} causes a debugging dump of the RTL code after this pass. This dump file's name is made by appending @samp{.loop} to the input file name. +@cindex jump bypassing +@item +Jump bypassing. This pass is an aggressive form of GCSE that transforms +the control flow graph of a function by propagating constants into +conditional branch instructions. + +The source file for this pass is @file{gcse.c}. + +@opindex dG +The option @option{-dG} causes a debugging dump of the RTL code after +this pass. This dump file's name is made by appending @samp{.bypass} +to the input file name. + @item @opindex frerun-cse-after-loop If @option{-frerun-cse-after-loop} was enabled, a second common @@ -1,6 +1,6 @@ /* Global common subexpression elimination/Partial redundancy elimination and global constant/copy propagation for GNU compiler. - Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002 + Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003 Free Software Foundation, Inc. This file is part of GCC. @@ -614,7 +614,7 @@ 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 int one_cprop_pass PARAMS ((int, 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)); @@ -819,7 +819,7 @@ gcse_main (f, file) /* Don't allow constant propagation to modify jumps during this pass. */ - changed = one_cprop_pass (pass + 1, 0); + changed = one_cprop_pass (pass + 1, 0, 0); if (optimize_size) changed |= one_classic_gcse_pass (pass + 1); @@ -886,7 +886,7 @@ gcse_main (f, file) max_gcse_regno = max_reg_num (); alloc_gcse_mem (f); /* This time, go ahead and allow cprop to alter jumps. */ - one_cprop_pass (pass + 1, 1); + one_cprop_pass (pass + 1, 1, 0); free_gcse_mem (); if (file) @@ -4463,20 +4463,22 @@ cprop (alter_jumps) } /* Perform one copy/constant propagation pass. - F is the first insn in the function. - PASS is the pass count. */ + PASS is the pass count. If CPROP_JUMPS is true, perform constant + propagation into conditional jumps. If BYPASS_JUMPS is true, + perform conditional jump bypassing optimizations. */ static int -one_cprop_pass (pass, alter_jumps) +one_cprop_pass (pass, cprop_jumps, bypass_jumps) int pass; - int alter_jumps; + int cprop_jumps; + int bypass_jumps; { int changed = 0; const_prop_count = 0; copy_prop_count = 0; - local_cprop_pass (alter_jumps); + local_cprop_pass (cprop_jumps); alloc_hash_table (max_cuid, &set_hash_table, 1); compute_hash_table (&set_hash_table); @@ -4486,8 +4488,8 @@ one_cprop_pass (pass, alter_jumps) { alloc_cprop_mem (last_basic_block, set_hash_table.n_elems); compute_cprop_data (); - changed = cprop (alter_jumps); - if (alter_jumps) + changed = cprop (cprop_jumps); + if (bypass_jumps) changed |= bypass_conditional_jumps (); free_cprop_mem (); } @@ -7348,4 +7350,109 @@ store_motion () end_alias_analysis (); } + +/* Entry point for jump bypassing optimization pass. */ + +int +bypass_jumps (file) + FILE *file; +{ + int changed; + + /* We do not construct an accurate cfg in functions which call + 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_file = file; + + /* Identify the basic block information for this function, including + successors and predecessors. */ + max_gcse_regno = max_reg_num (); + + if (file) + dump_flow_info (file); + + /* Return if there's nothing to do. */ + if (n_basic_blocks <= 1) + return 0; + + /* Trying to perform global optimizations on flow graphs which have + a high connectivity will take a long time and is unlikely to be + particularly useful. + + In normal circumstances a cfg should have about twice as many edges + as blocks. But we do not want to punish small functions which have + a couple switch statements. So we require a relatively large number + of basic blocks and the ratio of edges to blocks to be high. */ + if (n_basic_blocks > 1000 && n_edges / n_basic_blocks >= 20) + { + if (warn_disabled_optimization) + warning ("BYPASS disabled: %d > 1000 basic blocks and %d >= 20 edges/basic block", + n_basic_blocks, n_edges / n_basic_blocks); + return 0; + } + + /* If allocating memory for the cprop bitmap would take up too much + storage it's better just to disable the optimization. */ + if ((n_basic_blocks + * SBITMAP_SET_SIZE (max_gcse_regno) + * sizeof (SBITMAP_ELT_TYPE)) > MAX_GCSE_MEMORY) + { + if (warn_disabled_optimization) + warning ("GCSE disabled: %d basic blocks and %d registers", + n_basic_blocks, max_gcse_regno); + + return 0; + } + + /* See what modes support reg/reg copy operations. */ + if (! can_copy_init_p) + { + compute_can_copy (); + can_copy_init_p = 1; + } + + gcc_obstack_init (&gcse_obstack); + bytes_used = 0; + + /* We need alias. */ + init_alias_analysis (); + + /* Record where pseudo-registers are set. This data is kept accurate + during each pass. ??? We could also record hard-reg information here + [since it's unchanging], however it is currently done during hash table + computation. + + It may be tempting to compute MEM set information here too, but MEM sets + will be subject to code motion one day and thus we need to compute + information about memory sets when we build the hash tables. */ + + alloc_reg_set_mem (max_gcse_regno); + compute_sets (get_insns ()); + + max_gcse_regno = max_reg_num (); + alloc_gcse_mem (get_insns ()); + changed = one_cprop_pass (1, 1, 1); + free_gcse_mem (); + + if (file) + { + fprintf (file, "BYPASS of %s: %d basic blocks, ", + current_function_name, n_basic_blocks); + fprintf (file, "%d bytes\n\n", bytes_used); + } + + obstack_free (&gcse_obstack, NULL); + free_reg_set_mem (); + + /* We are finished with alias. */ + end_alias_analysis (); + allocate_reg_info (max_reg_num (), FALSE, FALSE); + + return changed; +} + #include "gt-gcse.h" @@ -1,6 +1,6 @@ /* Register Transfer Language (RTL) definitions for GNU C-Compiler Copyright (C) 1987, 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1998, - 1999, 2000, 2001, 2002 Free Software Foundation, Inc. + 1999, 2000, 2001, 2002, 2003 Free Software Foundation, Inc. This file is part of GCC. @@ -2086,6 +2086,7 @@ extern rtx expand_mult_highpart PARAMS ((enum machine_mode, rtx, /* In gcse.c */ #ifdef BUFSIZ extern int gcse_main PARAMS ((rtx, FILE *)); +extern int bypass_jumps PARAMS ((FILE *)); #endif /* In global.c */ diff --git a/gcc/timevar.def b/gcc/timevar.def index 4d1eba8..766207e 100644 --- a/gcc/timevar.def +++ b/gcc/timevar.def @@ -1,6 +1,6 @@ /* This file contains the definitions for timing variables used to measure run-time performance of the compiler. - Copyright (C) 2000 Free Software Foundation, Inc. + Copyright (C) 2000, 2001, 2002, 2003 Free Software Foundation, Inc. Contributed by Alex Samuel <samuel@codesourcery.com> This file is part of GCC. @@ -59,6 +59,7 @@ DEFTIMEVAR (TV_JUMP , "jump") DEFTIMEVAR (TV_CSE , "CSE") DEFTIMEVAR (TV_GCSE , "global CSE") DEFTIMEVAR (TV_LOOP , "loop analysis") +DEFTIMEVAR (TV_BYPASS , "bypass jumps") DEFTIMEVAR (TV_TRACER , "tracer") DEFTIMEVAR (TV_CSE2 , "CSE 2") DEFTIMEVAR (TV_BRANCH_PROB , "branch prediction") diff --git a/gcc/toplev.c b/gcc/toplev.c index 554f471..b860500 100644 --- a/gcc/toplev.c +++ b/gcc/toplev.c @@ -232,6 +232,7 @@ enum dump_file_index DFI_addressof, DFI_gcse, DFI_loop, + DFI_bypass, DFI_cfg, DFI_bp, DFI_ce1, @@ -281,6 +282,7 @@ static struct dump_file_info dump_file[DFI_MAX] = { "addressof", 'F', 0, 0, 0 }, { "gcse", 'G', 1, 0, 0 }, { "loop", 'L', 1, 0, 0 }, + { "bypass", 'G', 1, 0, 0 }, /* Yes, duplicate enable switch. */ { "cfg", 'f', 1, 0, 0 }, { "bp", 'b', 1, 0, 0 }, { "ce1", 'C', 1, 0, 0 }, @@ -2964,6 +2966,32 @@ rest_of_compilation (decl) ggc_collect (); } + /* Perform jump bypassing and control flow optimizations. */ + if (optimize > 0 && flag_gcse) + { + timevar_push (TV_BYPASS); + open_dump_file (DFI_bypass, decl); + + cleanup_cfg (CLEANUP_EXPENSIVE); + tem = bypass_jumps (rtl_dump_file); + + if (tem) + { + rebuild_jump_labels (insns); + cleanup_cfg (CLEANUP_EXPENSIVE); + delete_trivially_dead_insns (insns, max_reg_num ()); + } + + close_dump_file (DFI_bypass, print_rtl_with_bb, insns); + timevar_pop (TV_BYPASS); + + ggc_collect (); + +#ifdef ENABLE_CHECKING + verify_flow_info (); +#endif + } + /* Do control and data flow analysis; wrote some of the results to the dump file. */ |