/* 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.
#include "config.h"
#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
#include "toplev.h"
#include "rtl.h"
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));
/* Point to release obstack data from for each pass. */
char *gcse_obstack_bottom;
- /* Insertion of instructions on edges can create new basic blocks; we
- need the original basic block count so that we can properly deallocate
- arrays sized on the number of basic blocks originally in the cfg. */
- int orig_bb_count;
/* We do not construct an accurate cfg in functions which call
setjmp, so just punt to be safe. */
if (current_function_calls_setjmp)
if (file)
dump_flow_info (file);
- orig_bb_count = n_basic_blocks;
/* Return if there's nothing to do. */
if (n_basic_blocks <= 1)
return 0;
/* 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);
= (rtx *) gmalloc (last_basic_block * sizeof (rtx));
memset ((char *) modify_mem_list, 0, last_basic_block * sizeof (rtx));
memset ((char *) canon_modify_mem_list, 0, last_basic_block * sizeof (rtx));
- orig_bb_count = n_basic_blocks;
}
free_reg_set_mem ();
alloc_reg_set_mem (max_reg_num ());
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)
/* Scan the function and record each set of each pseudo-register.
This is called once, at the start of the gcse pass. See the comments for
- `reg_set_table' for further documenation. */
+ `reg_set_table' for further documentation. */
static void
compute_sets (f)
case CONST_DOUBLE:
case CONST_VECTOR:
case CALL:
+ case CONSTANT_P_RTX:
return 0;
default:
const char *fmt;
/* Used to turn recursion into iteration. We can't rely on GCC's
- tail-recursion eliminatio since we need to keep accumulating values
+ tail-recursion elimination since we need to keep accumulating values
in HASH. */
if (x == 0)
&& REGNO (src) >= FIRST_PSEUDO_REGISTER
&& can_copy_p [GET_MODE (dest)]
&& REGNO (src) != regno)
- || CONSTANT_P (src))
+ || (CONSTANT_P (src)
+ && GET_CODE (src) != CONSTANT_P_RTX))
/* 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. */
/* REG_EQUAL may get simplified into register.
We don't allow that. Remove that note. This code ought
- not to hapen, because previous code ought to syntetize
+ not to happen, because previous code ought to synthesize
reg-reg move, but be on the safe side. */
if (note && REG_P (XEXP (note, 0)))
remove_note (insn, note);
/* Subroutine of cprop_insn that tries to propagate constants into
JUMP_INSNS. JUMP must be a conditional jump. If SETCC is non-NULL
- it is the instruction that immediately preceeds JUMP, and must be a
+ it is the instruction that immediately precedes JUMP, and must be a
single SET of a register. FROM is what we will try to replace,
SRC is the constant we will try to substitute for it. Returns nonzero
if a change was made. */
conditional branch instructions first. */
if (alter_jumps
&& (sset = single_set (insn)) != NULL
+ && NEXT_INSN (insn)
&& any_condjump_p (NEXT_INSN (insn)) && onlyjump_p (NEXT_INSN (insn)))
{
rtx dest = SET_DEST (sset);
/* LIBCALL_SP is a zero-terminated array of insns at the end of a libcall;
their REG_EQUAL notes need updating. */
+
static bool
do_local_cprop (x, insn, alter_jumps, libcall_sp)
rtx x;
{
rtx newreg = NULL, newcnst = NULL;
- /* Rule out USE instructions and ASM statements as we don't want to change the hard registers mentioned. */
+ /* 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)))
+ || (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;
rtx this_rtx = l->loc;
rtx note;
- if (CONSTANT_P (this_rtx))
+ if (l->in_libcall)
+ continue;
+
+ if (CONSTANT_P (this_rtx)
+ && GET_CODE (this_rtx) != CONSTANT_P_RTX)
newcnst = this_rtx;
if (REG_P (this_rtx) && REGNO (this_rtx) >= FIRST_PSEUDO_REGISTER
/* Don't copy propagate if it has attached REG_EQUIV note.
if (newcnst && constprop_register (insn, x, newcnst, alter_jumps))
{
/* If we find a case where we can't fix the retval REG_EQUAL notes
- match the new register, we either have to abandom this replacement
+ match the new register, we either have to abandon this replacement
or fix delete_trivially_dead_insns to preserve the setting insn,
or make it delete the REG_EUAQL note, and fix up all passes that
require the REG_EQUAL note there. */
rtx insn;
struct reg_use *reg_used;
rtx libcall_stack[MAX_NESTED_LIBCALLS + 1], *libcall_sp;
+ bool changed = false;
cselib_init ();
libcall_sp = &libcall_stack[MAX_NESTED_LIBCALLS];
reg_used++, reg_use_count--)
if (do_local_cprop (reg_used->reg_rtx, insn, alter_jumps,
libcall_sp))
- break;
+ {
+ changed = true;
+ break;
+ }
}
while (reg_use_count);
}
cselib_process_insn (insn);
}
cselib_finish ();
+ /* Global analysis may get into infinite loops for unreachable blocks. */
+ if (changed && alter_jumps)
+ {
+ delete_unreachable_blocks ();
+ free_reg_set_mem ();
+ alloc_reg_set_mem (max_reg_num ());
+ compute_sets (get_insns ());
+ }
}
/* Forward propagate copies. This includes copies and constants. Return
}
/* 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);
{
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 ();
}
fprintf (gcse_file, "%d const props, %d copy props\n\n",
const_prop_count, copy_prop_count);
}
+ /* Global analysis may get into infinite loops for unreachable blocks. */
+ if (changed && cprop_jumps)
+ delete_unreachable_blocks ();
return changed;
}
\f
/* Bypass conditional jumps. */
+/* The value of last_basic_block at the beginning of the jump_bypass
+ pass. The use of redirect_edge_and_branch_force may introduce new
+ basic blocks, but the data flow analysis is only valid for basic
+ block indices less than bypass_last_basic_block. */
+
+static int bypass_last_basic_block;
+
/* Find a set of REGNO to a constant that is available at the end of basic
block BB. Returns NULL if no such set is found. Based heavily upon
find_avail_set. */
for (e = bb->pred; e; e = enext)
{
enext = e->pred_next;
+ if (e->flags & EDGE_COMPLEX)
+ continue;
+
+ /* We can't redirect edges from new basic blocks. */
+ if (e->src->index >= bypass_last_basic_block)
+ continue;
+
for (i = 0; i < reg_use_count; i++)
{
struct reg_use *reg_used = ®_use_table[i];
else
dest = NULL;
- /* Once basic block indices are stable, we should be able
- to use redirect_edge_and_branch_force instead. */
old_dest = e->dest;
- if (dest != NULL && dest != old_dest
- && redirect_edge_and_branch (e, dest))
- {
+ if (dest != NULL
+ && dest != old_dest
+ && dest != EXIT_BLOCK_PTR)
+ {
+ redirect_edge_and_branch_force (e, dest);
+
/* Copy the register setter to the redirected edge.
Don't copy CC0 setters, as CC0 is dead after jump. */
if (setcc)
if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
return 0;
+ bypass_last_basic_block = last_basic_block;
+
changed = 0;
FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb->next_bb,
EXIT_BLOCK_PTR, next_bb)
}
/* If we bypassed any register setting insns, we inserted a
- copy on the redirected edge. These need to be commited. */
+ copy on the redirected edge. These need to be committed. */
if (changed)
commit_edge_insertions();
/* Keeping in mind SMALL_REGISTER_CLASSES and parameters in registers,
we search backward and place the instructions before the first
parameter is loaded. Do this for everyone for consistency and a
- presumtion that we'll get better code elsewhere as well.
+ presumption that we'll get better code elsewhere as well.
It should always be the case that we can put these instructions
anywhere in the basic block with performing PRE optimizations.
else
eqv = SET_SRC (set);
- set_unique_reg_note (new, REG_EQUAL, copy_insn_1 (src));
+ set_unique_reg_note (new, REG_EQUAL, copy_insn_1 (eqv));
return new;
}
}
/* Now compute global properties based on the local properties. This
- is a classic global availablity algorithm. */
+ is a classic global availability algorithm. */
compute_available (nonnull_local, nonnull_killed,
nonnull_avout, nonnull_avin);
reference of that form, then we know the register can not have the value
zero at the conditional branch.
- So we merely need to compute the local properies and propagate that data
+ So we merely need to compute the local properties and propagate that data
around the cfg, then optimize where possible.
We run this pass two times. Once before CSE, then again after CSE. This
Note that if registers are changed ANYWHERE in the block, we'll
decide we can't move it, regardless of whether it changed above
or below the store. This could be improved by checking the register
- operands while lookinng for aliasing in each insn. */
+ operands while looking for aliasing in each insn. */
if (!store_ops_ok (XEXP (x, 0), bb))
return 1;
Note that if registers are changed ANYWHERE in the block, we'll
decide we can't move it, regardless of whether it changed above
or below the store. This could be improved by checking the register
- operands while lookinng for aliasing in each insn. */
+ operands while looking for aliasing in each insn. */
if (!store_ops_ok (XEXP (x, 0), bb))
return 1;
if (!store_killed_after (ptr->pattern, insn, bb))
{
- /* If we've already seen an availale expression in this block,
+ /* If we've already seen an available expression in this block,
we can delete the one we saw already (It occurs earlier in
the block), and replace it with this one). We'll copy the
old SRC expression to an unused register in case there
Load in the middle here if we push the store down. It happens in
gcc.c-torture/execute/960311-1.c with -O3
If we always kill it in this case, we'll sometimes do
- uneccessary work, but it shouldn't actually hurt anything.
+ unnecessary work, but it shouldn't actually hurt anything.
if (!TEST_BIT (ae_gen[b], ptr->index)). */
SET_BIT (ae_kill[b->index], ptr->index);
}
}
}
-/* Insert an instruction at the begining of a basic block, and update
+/* Insert an instruction at the beginning of a basic block, and update
the BLOCK_HEAD if needed. */
static void
end_alias_analysis ();
}
+\f
+/* 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"
OSDN Git Service
