This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: Split postreload gcse from gcse.c
- From: Steven Bosscher <stevenb at suse dot de>
- To: gcc-patches at gcc dot gnu dot org
- Date: Wed, 18 Aug 2004 19:53:01 +0200
- Subject: Re: Split postreload gcse from gcse.c
- Organization: SUSE Labs
- References: <200408181808.53600.stevenb@suse.de>
And of course, I attached the wrong patch. The larger the patch,
the more likely it is you attach the wrong one.
So again,
On Wednesday 18 August 2004 18:08, Steven Bosscher wrote:
> Hi,
>
> This patch splits postreload gcse from gcse.c to a new file
> called (surprise) postreload-gcse.c.
>
> To avoid having yet another pair of hash/equivalence functions,
> I've merged expr_hash and expr_equiv from gcse.c with canon_hash
> and exp_equiv from cse.c
>
> I've bootstrapped it on a number of targets, as have others, and
> we've also looked at performance. This patch makes postreload
> gcse a lot faster, but the generated code is not better overall,
> unfortunately.
>
> For example, on x86 most test cases improve slightly, but eon
> takes a 7% hit. On PowerPC, for which this pass was originally
> contributed, there's also little or no overall improvement due to
> postreload gcse, neither for compile time nor for the generated
> code.
>
> So what's left with this patch is:
> - splitting it off from gcse.c, which is a nice cleanup, and
> - merging a bunch of almost-duplicate functions.
>
> I've just finished bootstrapping the patch (needed re-doing after
> rth's RTX_UNCHANGING_P patch) and testing is in progress.
> OK if it passes?
>
> Gr.
> Steven
>
>
>
>
> * Makefile.in (OBJS-common): Add postreload-gcse.c.
> Add new postreload-gcse.o.
> * cse.c (SAFE_HASH): Define as wrapper around safe_hash.
> (lookup_as_function, insert, rehash_using_reg, use_related_value,
> equiv_constant): Use SAFE_HASH instead of safe_hash.
> (exp_equiv_p): Export. Add for_gcse argument when comparing
> for GCSE.
> (lookup, lookup_for_remove, merge_equiv_classes, find_best_addr,
> find_comparison_args, fold_rtx, cse_insn): Update callers.
> (hash_rtx): New function derived from old canon_hash and bits
> from gcse.c hash_expr_1.
> (canon_hash_string): Rename to hash_rtx_string.
> (canon_hash, safe_hash): Make static inline. Call hash_rtx.
> * cselib.c (hash_rtx): Rename to cselib_hash_rtx.
> (cselib_lookup): Update this caller.
> * gcse.c (modify_mem_list_set, canon_modify_mem_list_set):
> Make static.
> (hash_expr): Call hash_rtx.
> (ldst_entry): Likewise.
> (expr_equiv_p): Call exp_equiv_p.
> (struct unoccr, hash_expr_1, hash_string_1, lookup_expr,
> reg_used_on_edge, reg_set_between_after_reload_p,
> reg_used_between_after_reload_p, get_avail_load_store_reg,
> is_jump_table_basic_block, bb_has_well_behaved_predecessors,
> get_bb_avail_insn, hash_scan_set_after_reload,
> compute_hash_table_after_reload,
> eliminate_partially_redundant_loads, gcse_after_reload,
> get_bb_avail_insn, gcse_after_reload_main): Remove.
> * postreload-gcse.c: New file, reincarnating most of the above.
> * rtl.h (exp_equiv_p, hash_rtx): New prototypes.
> (gcse_after_reload_main): Update prototype.
> * timevar.def (TV_GCSE_AFTER_RELOAD): New timevar.
> * passes.c (rest_of_handle_gcse2): Use it.
Gr.
Steven
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1349
diff -c -3 -p -r1.1349 Makefile.in
*** Makefile.in 17 Aug 2004 16:17:04 -0000 1.1349
--- Makefile.in 18 Aug 2004 17:51:29 -0000
*************** OBJS-common = \
*** 899,913 ****
genrtl.o ggc-common.o global.o graph.o gtype-desc.o \
haifa-sched.o hooks.o ifcvt.o insn-attrtab.o insn-emit.o insn-modes.o \
insn-extract.o insn-opinit.o insn-output.o insn-peep.o insn-recog.o \
! insn-preds.o integrate.o intl.o jump.o langhooks.o lcm.o lists.o \
! local-alloc.o loop.o modulo-sched.o \
! optabs.o options.o opts.o params.o postreload.o predict.o \
print-rtl.o print-tree.o value-prof.o var-tracking.o \
profile.o ra.o ra-build.o ra-colorize.o ra-debug.o ra-rewrite.o \
real.o recog.o reg-stack.o regclass.o regmove.o regrename.o \
reload.o reload1.o reorg.o resource.o rtl.o rtlanal.o rtl-error.o \
sbitmap.o sched-deps.o sched-ebb.o sched-rgn.o sched-vis.o sdbout.o \
! simplify-rtx.o sreal.o stmt.o stor-layout.o stringpool.o \
targhooks.o timevar.o toplev.o tracer.o tree.o tree-dump.o unroll.o \
varasm.o varray.o vec.o version.o vmsdbgout.o xcoffout.o alloc-pool.o \
et-forest.o cfghooks.o bt-load.o pretty-print.o $(GGC) web.o passes.o \
--- 899,916 ----
genrtl.o ggc-common.o global.o graph.o gtype-desc.o \
haifa-sched.o hooks.o ifcvt.o insn-attrtab.o insn-emit.o insn-modes.o \
insn-extract.o insn-opinit.o insn-output.o insn-peep.o insn-recog.o \
! integrate.o intl.o jump.o langhooks.o lcm.o lists.o local-alloc.o \
! loop.o modulo-sched.o optabs.o options.o opts.o \
! params.o postreload.o postreload-gcse.o predict.o \
! insn-preds.o integrate.o intl.o jump.o langhooks.o lcm.o lists.o \
! local-alloc.o loop.o modulo-sched.o optabs.o options.o opts.o \
! params.o postreload.o postreload-gcse.o predict.o \
print-rtl.o print-tree.o value-prof.o var-tracking.o \
profile.o ra.o ra-build.o ra-colorize.o ra-debug.o ra-rewrite.o \
real.o recog.o reg-stack.o regclass.o regmove.o regrename.o \
reload.o reload1.o reorg.o resource.o rtl.o rtlanal.o rtl-error.o \
sbitmap.o sched-deps.o sched-ebb.o sched-rgn.o sched-vis.o sdbout.o \
! simplify-rtx.o sreal.o stmt.o stor-layout.o stringpool.o \
targhooks.o timevar.o toplev.o tracer.o tree.o tree-dump.o unroll.o \
varasm.o varray.o vec.o version.o vmsdbgout.o xcoffout.o alloc-pool.o \
et-forest.o cfghooks.o bt-load.o pretty-print.o $(GGC) web.o passes.o \
*************** postreload.o : postreload.c $(CONFIG_H)
*** 2047,2052 ****
--- 2050,2059 ----
$(EXPR_H) $(OPTABS_H) reload.h $(REGS_H) hard-reg-set.h insn-config.h \
$(BASIC_BLOCK_H) $(RECOG_H) output.h function.h toplev.h cselib.h $(TM_P_H) \
except.h $(TREE_H)
+ postreload-gcse.o : postreload-gcse.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
+ $(RTL_H) $(REGS_H) hard-reg-set.h $(FLAGS_H) real.h insn-config.h $(GGC_H) \
+ $(RECOG_H) $(EXPR_H) $(BASIC_BLOCK_H) function.h output.h toplev.h $(TM_P_H) \
+ except.h $(TREE_H)
caller-save.o : caller-save.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
$(FLAGS_H) $(REGS_H) hard-reg-set.h insn-config.h $(BASIC_BLOCK_H) function.h \
$(RECOG_H) reload.h $(EXPR_H) toplev.h $(TM_P_H)
Index: cse.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cse.c,v
retrieving revision 1.308
diff -c -3 -p -r1.308 cse.c
*** cse.c 18 Aug 2004 08:23:37 -0000 1.308
--- cse.c 18 Aug 2004 17:51:30 -0000
*************** struct table_elt
*** 489,494 ****
--- 489,500 ----
? (((unsigned) REG << 7) + (unsigned) REG_QTY (REGNO (X))) \
: canon_hash (X, M)) & HASH_MASK)
+ /* Like HASH, but without side-effects. */
+ #define SAFE_HASH(X, M) \
+ ((REG_P (X) && REGNO (X) >= FIRST_PSEUDO_REGISTER \
+ ? (((unsigned) REG << 7) + (unsigned) REG_QTY (REGNO (X))) \
+ : safe_hash (X, M)) & HASH_MASK)
+
/* Determine whether register number N is considered a fixed register for the
purpose of approximating register costs.
It is desirable to replace other regs with fixed regs, to reduce need for
*************** static void rehash_using_reg (rtx);
*** 625,634 ****
static void invalidate_memory (void);
static void invalidate_for_call (void);
static rtx use_related_value (rtx, struct table_elt *);
! static unsigned canon_hash (rtx, enum machine_mode);
! static unsigned canon_hash_string (const char *);
! static unsigned safe_hash (rtx, enum machine_mode);
! static int exp_equiv_p (rtx, rtx, int, int);
static rtx canon_reg (rtx, rtx);
static void find_best_addr (rtx, rtx *, enum machine_mode);
static enum rtx_code find_comparison_args (enum rtx_code, rtx *, rtx *,
--- 631,641 ----
static void invalidate_memory (void);
static void invalidate_for_call (void);
static rtx use_related_value (rtx, struct table_elt *);
!
! static inline unsigned canon_hash (rtx, enum machine_mode);
! static inline unsigned safe_hash (rtx, enum machine_mode);
! static unsigned hash_rtx_string (const char *);
!
static rtx canon_reg (rtx, rtx);
static void find_best_addr (rtx, rtx *, enum machine_mode);
static enum rtx_code find_comparison_args (enum rtx_code, rtx *, rtx *,
*************** lookup (rtx x, unsigned int hash, enum m
*** 1324,1330 ****
for (p = table[hash]; p; p = p->next_same_hash)
if (mode == p->mode && ((x == p->exp && REG_P (x))
! || exp_equiv_p (x, p->exp, !REG_P (x), 0)))
return p;
return 0;
--- 1331,1337 ----
for (p = table[hash]; p; p = p->next_same_hash)
if (mode == p->mode && ((x == p->exp && REG_P (x))
! || exp_equiv_p (x, p->exp, !REG_P (x), false)))
return p;
return 0;
*************** lookup_for_remove (rtx x, unsigned int h
*** 1352,1358 ****
else
{
for (p = table[hash]; p; p = p->next_same_hash)
! if (mode == p->mode && (x == p->exp || exp_equiv_p (x, p->exp, 0, 0)))
return p;
}
--- 1359,1366 ----
else
{
for (p = table[hash]; p; p = p->next_same_hash)
! if (mode == p->mode
! && (x == p->exp || exp_equiv_p (x, p->exp, 0, false)))
return p;
}
*************** static rtx
*** 1366,1372 ****
lookup_as_function (rtx x, enum rtx_code code)
{
struct table_elt *p
! = lookup (x, safe_hash (x, VOIDmode) & HASH_MASK, GET_MODE (x));
/* If we are looking for a CONST_INT, the mode doesn't really matter, as
long as we are narrowing. So if we looked in vain for a mode narrower
--- 1374,1380 ----
lookup_as_function (rtx x, enum rtx_code code)
{
struct table_elt *p
! = lookup (x, SAFE_HASH (x, VOIDmode), GET_MODE (x));
/* If we are looking for a CONST_INT, the mode doesn't really matter, as
long as we are narrowing. So if we looked in vain for a mode narrower
*************** lookup_as_function (rtx x, enum rtx_code
*** 1376,1382 ****
{
x = copy_rtx (x);
PUT_MODE (x, word_mode);
! p = lookup (x, safe_hash (x, VOIDmode) & HASH_MASK, word_mode);
}
if (p == 0)
--- 1384,1390 ----
{
x = copy_rtx (x);
PUT_MODE (x, word_mode);
! p = lookup (x, SAFE_HASH (x, VOIDmode), word_mode);
}
if (p == 0)
*************** lookup_as_function (rtx x, enum rtx_code
*** 1385,1391 ****
for (p = p->first_same_value; p; p = p->next_same_value)
if (GET_CODE (p->exp) == code
/* Make sure this is a valid entry in the table. */
! && exp_equiv_p (p->exp, p->exp, 1, 0))
return p->exp;
return 0;
--- 1393,1399 ----
for (p = p->first_same_value; p; p = p->next_same_value)
if (GET_CODE (p->exp) == code
/* Make sure this is a valid entry in the table. */
! && exp_equiv_p (p->exp, p->exp, 1, false))
return p->exp;
return 0;
*************** insert (rtx x, struct table_elt *classp,
*** 1568,1574 ****
if (subexp != 0)
{
/* Get the integer-free subexpression in the hash table. */
! subhash = safe_hash (subexp, mode) & HASH_MASK;
subelt = lookup (subexp, subhash, mode);
if (subelt == 0)
subelt = insert (subexp, NULL, subhash, mode);
--- 1576,1582 ----
if (subexp != 0)
{
/* Get the integer-free subexpression in the hash table. */
! subhash = SAFE_HASH (subexp, mode);
subelt = lookup (subexp, subhash, mode);
if (subelt == 0)
subelt = insert (subexp, NULL, subhash, mode);
*************** merge_equiv_classes (struct table_elt *c
*** 1622,1628 ****
/* Remove old entry, make a new one in CLASS1's class.
Don't do this for invalid entries as we cannot find their
hash code (it also isn't necessary). */
! if (REG_P (exp) || exp_equiv_p (exp, exp, 1, 0))
{
bool need_rehash = false;
--- 1630,1636 ----
/* Remove old entry, make a new one in CLASS1's class.
Don't do this for invalid entries as we cannot find their
hash code (it also isn't necessary). */
! if (REG_P (exp) || exp_equiv_p (exp, exp, 1, false))
{
bool need_rehash = false;
*************** rehash_using_reg (rtx x)
*** 1917,1924 ****
{
next = p->next_same_hash;
if (reg_mentioned_p (x, p->exp)
! && exp_equiv_p (p->exp, p->exp, 1, 0)
! && i != (hash = safe_hash (p->exp, p->mode) & HASH_MASK))
{
if (p->next_same_hash)
p->next_same_hash->prev_same_hash = p->prev_same_hash;
--- 1925,1932 ----
{
next = p->next_same_hash;
if (reg_mentioned_p (x, p->exp)
! && exp_equiv_p (p->exp, p->exp, 1, false)
! && i != (hash = SAFE_HASH (p->exp, p->mode)))
{
if (p->next_same_hash)
p->next_same_hash->prev_same_hash = p->prev_same_hash;
*************** use_related_value (rtx x, struct table_e
*** 2017,2023 ****
rtx subexp = get_related_value (x);
if (subexp != 0)
relt = lookup (subexp,
! safe_hash (subexp, GET_MODE (subexp)) & HASH_MASK,
GET_MODE (subexp));
}
--- 2025,2031 ----
rtx subexp = get_related_value (x);
if (subexp != 0)
relt = lookup (subexp,
! SAFE_HASH (subexp, GET_MODE (subexp)),
GET_MODE (subexp));
}
*************** use_related_value (rtx x, struct table_e
*** 2068,2074 ****
/* Hash a string. Just add its bytes up. */
static inline unsigned
! canon_hash_string (const char *ps)
{
unsigned hash = 0;
const unsigned char *p = (const unsigned char *) ps;
--- 2076,2082 ----
/* Hash a string. Just add its bytes up. */
static inline unsigned
! hash_rtx_string (const char *ps)
{
unsigned hash = 0;
const unsigned char *p = (const unsigned char *) ps;
*************** canon_hash_string (const char *ps)
*** 2085,2107 ****
MODE is used in hashing for CONST_INTs only;
otherwise the mode of X is used.
! Store 1 in do_not_record if any subexpression is volatile.
! Store 1 in hash_arg_in_memory if X contains a MEM rtx
! which does not have the MEM_READONLY_P bit set.
Note that cse_insn knows that the hash code of a MEM expression
is just (int) MEM plus the hash code of the address. */
! static unsigned
! canon_hash (rtx x, enum machine_mode mode)
{
int i, j;
unsigned hash = 0;
enum rtx_code code;
const char *fmt;
! /* repeat is used to turn tail-recursion into iteration. */
repeat:
if (x == 0)
return hash;
--- 2093,2118 ----
MODE is used in hashing for CONST_INTs only;
otherwise the mode of X is used.
! Store 1 in DO_NOT_RECORD_P if any subexpression is volatile.
! If HASH_ARG_IN_MEMORY_P is not NULL, store 1 in it if X contains
! a MEM rtx which does not have the RTX_UNCHANGING_P bit set.
Note that cse_insn knows that the hash code of a MEM expression
is just (int) MEM plus the hash code of the address. */
! unsigned
! hash_rtx (rtx x, enum machine_mode mode, int *do_not_record_p,
! int *hash_arg_in_memory_p, bool have_reg_qty)
{
int i, j;
unsigned hash = 0;
enum rtx_code code;
const char *fmt;
! /* Used to turn recursion into iteration. We can't rely on GCC's
! tail-recursion elimination since we need to keep accumulating values
! in HASH. */
repeat:
if (x == 0)
return hash;
*************** canon_hash (rtx x, enum machine_mode mod
*** 2112,2159 ****
case REG:
{
unsigned int regno = REGNO (x);
- bool record;
-
- /* On some machines, we can't record any non-fixed hard register,
- because extending its life will cause reload problems. We
- consider ap, fp, sp, gp to be fixed for this purpose.
-
- We also consider CCmode registers to be fixed for this purpose;
- failure to do so leads to failure to simplify 0<100 type of
- conditionals.
-
- On all machines, we can't record any global registers.
- Nor should we record any register that is in a small
- class, as defined by CLASS_LIKELY_SPILLED_P. */
! if (regno >= FIRST_PSEUDO_REGISTER)
! record = true;
! else if (x == frame_pointer_rtx
! || x == hard_frame_pointer_rtx
! || x == arg_pointer_rtx
! || x == stack_pointer_rtx
! || x == pic_offset_table_rtx)
! record = true;
! else if (global_regs[regno])
! record = false;
! else if (fixed_regs[regno])
! record = true;
! else if (GET_MODE_CLASS (GET_MODE (x)) == MODE_CC)
! record = true;
! else if (SMALL_REGISTER_CLASSES)
! record = false;
! else if (CLASS_LIKELY_SPILLED_P (REGNO_REG_CLASS (regno)))
! record = false;
! else
! record = true;
!
! if (!record)
{
! do_not_record = 1;
! return 0;
}
! hash += ((unsigned) REG << 7) + (unsigned) REG_QTY (regno);
return hash;
}
--- 2123,2174 ----
case REG:
{
unsigned int regno = REGNO (x);
! if (!reload_completed)
{
! /* On some machines, we can't record any non-fixed hard register,
! because extending its life will cause reload problems. We
! consider ap, fp, sp, gp to be fixed for this purpose.
!
! We also consider CCmode registers to be fixed for this purpose;
! failure to do so leads to failure to simplify 0<100 type of
! conditionals.
!
! On all machines, we can't record any global registers.
! Nor should we record any register that is in a small
! class, as defined by CLASS_LIKELY_SPILLED_P. */
! bool record;
!
! if (regno >= FIRST_PSEUDO_REGISTER)
! record = true;
! else if (x == frame_pointer_rtx
! || x == hard_frame_pointer_rtx
! || x == arg_pointer_rtx
! || x == stack_pointer_rtx
! || x == pic_offset_table_rtx)
! record = true;
! else if (global_regs[regno])
! record = false;
! else if (fixed_regs[regno])
! record = true;
! else if (GET_MODE_CLASS (GET_MODE (x)) == MODE_CC)
! record = true;
! else if (SMALL_REGISTER_CLASSES)
! record = false;
! else if (CLASS_LIKELY_SPILLED_P (REGNO_REG_CLASS (regno)))
! record = false;
! else
! record = true;
!
! if (!record)
! {
! *do_not_record_p = 1;
! return 0;
! }
}
! hash += ((unsigned int) REG << 7);
! hash += (have_reg_qty ? (unsigned) REG_QTY (regno) : regno);
return hash;
}
*************** canon_hash (rtx x, enum machine_mode mod
*** 2164,2170 ****
{
if (REG_P (SUBREG_REG (x)))
{
! hash += (((unsigned) SUBREG << 7)
+ REGNO (SUBREG_REG (x))
+ (SUBREG_BYTE (x) / UNITS_PER_WORD));
return hash;
--- 2179,2185 ----
{
if (REG_P (SUBREG_REG (x)))
{
! hash += (((unsigned int) SUBREG << 7)
+ REGNO (SUBREG_REG (x))
+ (SUBREG_BYTE (x) / UNITS_PER_WORD));
return hash;
*************** canon_hash (rtx x, enum machine_mode mod
*** 2173,2193 ****
}
case CONST_INT:
! {
! unsigned HOST_WIDE_INT tem = INTVAL (x);
! hash += ((unsigned) CONST_INT << 7) + (unsigned) mode + tem;
! return hash;
! }
case CONST_DOUBLE:
/* This is like the general case, except that it only counts
the integers representing the constant. */
! hash += (unsigned) code + (unsigned) GET_MODE (x);
if (GET_MODE (x) != VOIDmode)
hash += real_hash (CONST_DOUBLE_REAL_VALUE (x));
else
! hash += ((unsigned) CONST_DOUBLE_LOW (x)
! + (unsigned) CONST_DOUBLE_HIGH (x));
return hash;
case CONST_VECTOR:
--- 2188,2206 ----
}
case CONST_INT:
! hash += (((unsigned int) CONST_INT << 7) + (unsigned int) mode
! + (unsigned int) INTVAL (x));
! return hash;
case CONST_DOUBLE:
/* This is like the general case, except that it only counts
the integers representing the constant. */
! hash += (unsigned int) code + (unsigned int) GET_MODE (x);
if (GET_MODE (x) != VOIDmode)
hash += real_hash (CONST_DOUBLE_REAL_VALUE (x));
else
! hash += ((unsigned int) CONST_DOUBLE_LOW (x)
! + (unsigned int) CONST_DOUBLE_HIGH (x));
return hash;
case CONST_VECTOR:
*************** canon_hash (rtx x, enum machine_mode mod
*** 2200,2206 ****
for (i = 0; i < units; ++i)
{
elt = CONST_VECTOR_ELT (x, i);
! hash += canon_hash (elt, GET_MODE (elt));
}
return hash;
--- 2213,2220 ----
for (i = 0; i < units; ++i)
{
elt = CONST_VECTOR_ELT (x, i);
! hash += hash_rtx (elt, GET_MODE (elt), do_not_record_p,
! hash_arg_in_memory_p, have_reg_qty);
}
return hash;
*************** canon_hash (rtx x, enum machine_mode mod
*** 2208,2230 ****
/* Assume there is only one rtx object for any given label. */
case LABEL_REF:
! hash += ((unsigned) LABEL_REF << 7) + (unsigned long) XEXP (x, 0);
return hash;
case SYMBOL_REF:
! hash += ((unsigned) SYMBOL_REF << 7) + (unsigned long) XSTR (x, 0);
! return hash;
case MEM:
/* We don't record if marked volatile or if BLKmode since we don't
know the size of the move. */
if (MEM_VOLATILE_P (x) || GET_MODE (x) == BLKmode)
{
! do_not_record = 1;
return 0;
}
! if (!MEM_READONLY_P (x))
! hash_arg_in_memory = 1;
/* Now that we have already found this special case,
might as well speed it up as much as possible. */
--- 2222,2260 ----
/* Assume there is only one rtx object for any given label. */
case LABEL_REF:
! /* We don't hash on the address of the CODE_LABEL to avoid bootstrap
! differences and differences between each stage's debugging dumps. */
! hash += (((unsigned int) LABEL_REF << 7)
! + CODE_LABEL_NUMBER (XEXP (x, 0)));
return hash;
case SYMBOL_REF:
! {
! /* Don't hash on the symbol's address to avoid bootstrap differences.
! Different hash values may cause expressions to be recorded in
! different orders and thus different registers to be used in the
! final assembler. This also avoids differences in the dump files
! between various stages. */
! unsigned int h = 0;
! const unsigned char *p = (const unsigned char *) XSTR (x, 0);
!
! while (*p)
! h += (h << 7) + *p++; /* ??? revisit */
!
! hash += ((unsigned int) SYMBOL_REF << 7) + h;
! return hash;
! }
case MEM:
/* We don't record if marked volatile or if BLKmode since we don't
know the size of the move. */
if (MEM_VOLATILE_P (x) || GET_MODE (x) == BLKmode)
{
! *do_not_record_p = 1;
return 0;
}
! if (hash_arg_in_memory_p && !MEM_READONLY_P (x))
! *hash_arg_in_memory_p = 1;
/* Now that we have already found this special case,
might as well speed it up as much as possible. */
*************** canon_hash (rtx x, enum machine_mode mod
*** 2236,2250 ****
/* A USE that mentions non-volatile memory needs special
handling since the MEM may be BLKmode which normally
prevents an entry from being made. Pure calls are
! marked by a USE which mentions BLKmode memory. */
if (MEM_P (XEXP (x, 0))
&& ! MEM_VOLATILE_P (XEXP (x, 0)))
{
hash += (unsigned) USE;
x = XEXP (x, 0);
! if (!MEM_READONLY_P (x))
! hash_arg_in_memory = 1;
/* Now that we have already found this special case,
might as well speed it up as much as possible. */
--- 2266,2281 ----
/* A USE that mentions non-volatile memory needs special
handling since the MEM may be BLKmode which normally
prevents an entry from being made. Pure calls are
! marked by a USE which mentions BLKmode memory.
! See calls.c:emit_call_1. */
if (MEM_P (XEXP (x, 0))
&& ! MEM_VOLATILE_P (XEXP (x, 0)))
{
hash += (unsigned) USE;
x = XEXP (x, 0);
! if (hash_arg_in_memory_p && !MEM_READONLY_P (x))
! *hash_arg_in_memory_p = 1;
/* Now that we have already found this special case,
might as well speed it up as much as possible. */
*************** canon_hash (rtx x, enum machine_mode mod
*** 2264,2297 ****
case CC0:
case CALL:
case UNSPEC_VOLATILE:
! do_not_record = 1;
return 0;
case ASM_OPERANDS:
if (MEM_VOLATILE_P (x))
{
! do_not_record = 1;
return 0;
}
else
{
/* We don't want to take the filename and line into account. */
hash += (unsigned) code + (unsigned) GET_MODE (x)
! + canon_hash_string (ASM_OPERANDS_TEMPLATE (x))
! + canon_hash_string (ASM_OPERANDS_OUTPUT_CONSTRAINT (x))
+ (unsigned) ASM_OPERANDS_OUTPUT_IDX (x);
if (ASM_OPERANDS_INPUT_LENGTH (x))
{
for (i = 1; i < ASM_OPERANDS_INPUT_LENGTH (x); i++)
{
! hash += (canon_hash (ASM_OPERANDS_INPUT (x, i),
! GET_MODE (ASM_OPERANDS_INPUT (x, i)))
! + canon_hash_string (ASM_OPERANDS_INPUT_CONSTRAINT
! (x, i)));
}
! hash += canon_hash_string (ASM_OPERANDS_INPUT_CONSTRAINT (x, 0));
x = ASM_OPERANDS_INPUT (x, 0);
mode = GET_MODE (x);
goto repeat;
--- 2295,2330 ----
case CC0:
case CALL:
case UNSPEC_VOLATILE:
! *do_not_record_p = 1;
return 0;
case ASM_OPERANDS:
if (MEM_VOLATILE_P (x))
{
! *do_not_record_p = 1;
return 0;
}
else
{
/* We don't want to take the filename and line into account. */
hash += (unsigned) code + (unsigned) GET_MODE (x)
! + hash_rtx_string (ASM_OPERANDS_TEMPLATE (x))
! + hash_rtx_string (ASM_OPERANDS_OUTPUT_CONSTRAINT (x))
+ (unsigned) ASM_OPERANDS_OUTPUT_IDX (x);
if (ASM_OPERANDS_INPUT_LENGTH (x))
{
for (i = 1; i < ASM_OPERANDS_INPUT_LENGTH (x); i++)
{
! hash += (hash_rtx (ASM_OPERANDS_INPUT (x, i),
! GET_MODE (ASM_OPERANDS_INPUT (x, i)),
! do_not_record_p, hash_arg_in_memory_p,
! have_reg_qty)
! + hash_rtx_string
! (ASM_OPERANDS_INPUT_CONSTRAINT (x, i)));
}
! hash += hash_rtx_string (ASM_OPERANDS_INPUT_CONSTRAINT (x, 0));
x = ASM_OPERANDS_INPUT (x, 0);
mode = GET_MODE (x);
goto repeat;
*************** canon_hash (rtx x, enum machine_mode mod
*** 2312,2359 ****
{
if (fmt[i] == 'e')
{
- rtx tem = XEXP (x, i);
-
/* If we are about to do the last recursive call
needed at this level, change it into iteration.
This function is called enough to be worth it. */
if (i == 0)
{
! x = tem;
goto repeat;
}
! hash += canon_hash (tem, 0);
}
else if (fmt[i] == 'E')
for (j = 0; j < XVECLEN (x, i); j++)
! hash += canon_hash (XVECEXP (x, i, j), 0);
else if (fmt[i] == 's')
! hash += canon_hash_string (XSTR (x, i));
else if (fmt[i] == 'i')
! {
! unsigned tem = XINT (x, i);
! hash += tem;
! }
else if (fmt[i] == '0' || fmt[i] == 't')
/* Unused. */
;
else
abort ();
}
return hash;
}
! /* Like canon_hash but with no side effects. */
! static unsigned
safe_hash (rtx x, enum machine_mode mode)
{
! int save_do_not_record = do_not_record;
! int save_hash_arg_in_memory = hash_arg_in_memory;
! unsigned hash = canon_hash (x, mode);
! hash_arg_in_memory = save_hash_arg_in_memory;
! do_not_record = save_do_not_record;
! return hash;
}
/* Return 1 iff X and Y would canonicalize into the same thing,
--- 2345,2403 ----
{
if (fmt[i] == 'e')
{
/* If we are about to do the last recursive call
needed at this level, change it into iteration.
This function is called enough to be worth it. */
if (i == 0)
{
! x = XEXP (x, i);
goto repeat;
}
!
! hash += hash_rtx (XEXP (x, i), 0, do_not_record_p,
! hash_arg_in_memory_p, have_reg_qty);
}
+
else if (fmt[i] == 'E')
for (j = 0; j < XVECLEN (x, i); j++)
! {
! hash += hash_rtx (XVECEXP (x, i, j), 0, do_not_record_p,
! hash_arg_in_memory_p, have_reg_qty);
! }
!
else if (fmt[i] == 's')
! hash += hash_rtx_string (XSTR (x, i));
else if (fmt[i] == 'i')
! hash += (unsigned int) XINT (x, i);
else if (fmt[i] == '0' || fmt[i] == 't')
/* Unused. */
;
else
abort ();
}
+
return hash;
}
! /* Hash an rtx X for cse via hash_rtx.
! Stores 1 in do_not_record if any subexpression is volatile.
! Stores 1 in hash_arg_in_memory if X contains a mem rtx which
! does not have the RTX_UNCHANGING_P bit set. */
!
! static inline unsigned
! canon_hash (rtx x, enum machine_mode mode)
! {
! return hash_rtx (x, mode, &do_not_record, &hash_arg_in_memory, true);
! }
!
! /* Like canon_hash but with no side effects, i.e. do_not_record
! and hash_arg_in_memory are not changed. */
! static inline unsigned
safe_hash (rtx x, enum machine_mode mode)
{
! int dummy_do_not_record;
! return hash_rtx (x, mode, &dummy_do_not_record, NULL, true);
}
/* Return 1 iff X and Y would canonicalize into the same thing,
*************** safe_hash (rtx x, enum machine_mode mode
*** 2363,2378 ****
and Y was found in the hash table. We check register refs
in Y for being marked as valid.
! If EQUAL_VALUES is nonzero, we allow a register to match a constant value
! that is known to be in the register. Ordinarily, we don't allow them
! to match, because letting them match would cause unpredictable results
! in all the places that search a hash table chain for an equivalent
! for a given value. A possible equivalent that has different structure
! has its hash code computed from different data. Whether the hash code
! is the same as that of the given value is pure luck. */
! static int
! exp_equiv_p (rtx x, rtx y, int validate, int equal_values)
{
int i, j;
enum rtx_code code;
--- 2407,2416 ----
and Y was found in the hash table. We check register refs
in Y for being marked as valid.
! If FOR_GCSE is true, we compare X and Y for equivalence for GCSE. */
! int
! exp_equiv_p (rtx x, rtx y, int validate, bool for_gcse)
{
int i, j;
enum rtx_code code;
*************** exp_equiv_p (rtx x, rtx y, int validate,
*** 2382,2423 ****
if VALIDATE is nonzero. */
if (x == y && !validate)
return 1;
if (x == 0 || y == 0)
return x == y;
code = GET_CODE (x);
if (code != GET_CODE (y))
! {
! if (!equal_values)
! return 0;
!
! /* If X is a constant and Y is a register or vice versa, they may be
! equivalent. We only have to validate if Y is a register. */
! if (CONSTANT_P (x) && REG_P (y)
! && REGNO_QTY_VALID_P (REGNO (y)))
! {
! int y_q = REG_QTY (REGNO (y));
! struct qty_table_elem *y_ent = &qty_table[y_q];
!
! if (GET_MODE (y) == y_ent->mode
! && rtx_equal_p (x, y_ent->const_rtx)
! && (! validate || REG_IN_TABLE (REGNO (y)) == REG_TICK (REGNO (y))))
! return 1;
! }
!
! if (CONSTANT_P (y) && code == REG
! && REGNO_QTY_VALID_P (REGNO (x)))
! {
! int x_q = REG_QTY (REGNO (x));
! struct qty_table_elem *x_ent = &qty_table[x_q];
!
! if (GET_MODE (x) == x_ent->mode
! && rtx_equal_p (y, x_ent->const_rtx))
! return 1;
! }
!
! return 0;
! }
/* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. */
if (GET_MODE (x) != GET_MODE (y))
--- 2420,2432 ----
if VALIDATE is nonzero. */
if (x == y && !validate)
return 1;
+
if (x == 0 || y == 0)
return x == y;
code = GET_CODE (x);
if (code != GET_CODE (y))
! return 0;
/* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. */
if (GET_MODE (x) != GET_MODE (y))
*************** exp_equiv_p (rtx x, rtx y, int validate,
*** 2437,2465 ****
return XSTR (x, 0) == XSTR (y, 0);
case REG:
! {
! unsigned int regno = REGNO (y);
! unsigned int endregno
! = regno + (regno >= FIRST_PSEUDO_REGISTER ? 1
! : hard_regno_nregs[regno][GET_MODE (y)]);
! unsigned int i;
!
! /* If the quantities are not the same, the expressions are not
! equivalent. If there are and we are not to validate, they
! are equivalent. Otherwise, ensure all regs are up-to-date. */
! if (REG_QTY (REGNO (x)) != REG_QTY (regno))
! return 0;
- if (! validate)
return 1;
! for (i = regno; i < endregno; i++)
! if (REG_IN_TABLE (i) != REG_TICK (i))
return 0;
! return 1;
! }
/* For commutative operations, check both orders. */
case PLUS:
--- 2446,2493 ----
return XSTR (x, 0) == XSTR (y, 0);
case REG:
! if (for_gcse)
! return REGNO (x) == REGNO (y);
! else
! {
! unsigned int regno = REGNO (y);
! unsigned int i;
! unsigned int endregno
! = regno + (regno >= FIRST_PSEUDO_REGISTER ? 1
! : hard_regno_nregs[regno][GET_MODE (y)]);
!
! /* If the quantities are not the same, the expressions are not
! equivalent. If there are and we are not to validate, they
! are equivalent. Otherwise, ensure all regs are up-to-date. */
! if (REG_QTY (REGNO (x)) != REG_QTY (regno))
! return 0;
!
! if (! validate)
! return 1;
!
! for (i = regno; i < endregno; i++)
! if (REG_IN_TABLE (i) != REG_TICK (i))
! return 0;
return 1;
+ }
! case MEM:
! if (for_gcse)
! {
! /* Can't merge two expressions in different alias sets, since we
! can decide that the expression is transparent in a block when
! it isn't, due to it being set with the different alias set. */
! if (MEM_ALIAS_SET (x) != MEM_ALIAS_SET (y))
return 0;
! /* A volatile mem should not be considered equivalent to any
! other. */
! if (MEM_VOLATILE_P (x) || MEM_VOLATILE_P (y))
! return 0;
! }
! break;
/* For commutative operations, check both orders. */
case PLUS:
*************** exp_equiv_p (rtx x, rtx y, int validate,
*** 2469,2481 ****
case XOR:
case NE:
case EQ:
! return ((exp_equiv_p (XEXP (x, 0), XEXP (y, 0), validate, equal_values)
&& exp_equiv_p (XEXP (x, 1), XEXP (y, 1),
! validate, equal_values))
|| (exp_equiv_p (XEXP (x, 0), XEXP (y, 1),
! validate, equal_values)
&& exp_equiv_p (XEXP (x, 1), XEXP (y, 0),
! validate, equal_values)));
case ASM_OPERANDS:
/* We don't use the generic code below because we want to
--- 2497,2510 ----
case XOR:
case NE:
case EQ:
! return ((exp_equiv_p (XEXP (x, 0), XEXP (y, 0),
! validate, for_gcse)
&& exp_equiv_p (XEXP (x, 1), XEXP (y, 1),
! validate, for_gcse))
|| (exp_equiv_p (XEXP (x, 0), XEXP (y, 1),
! validate, for_gcse)
&& exp_equiv_p (XEXP (x, 1), XEXP (y, 0),
! validate, for_gcse)));
case ASM_OPERANDS:
/* We don't use the generic code below because we want to
*************** exp_equiv_p (rtx x, rtx y, int validate,
*** 2498,2504 ****
for (i = ASM_OPERANDS_INPUT_LENGTH (x) - 1; i >= 0; i--)
if (! exp_equiv_p (ASM_OPERANDS_INPUT (x, i),
ASM_OPERANDS_INPUT (y, i),
! validate, equal_values)
|| strcmp (ASM_OPERANDS_INPUT_CONSTRAINT (x, i),
ASM_OPERANDS_INPUT_CONSTRAINT (y, i)))
return 0;
--- 2527,2533 ----
for (i = ASM_OPERANDS_INPUT_LENGTH (x) - 1; i >= 0; i--)
if (! exp_equiv_p (ASM_OPERANDS_INPUT (x, i),
ASM_OPERANDS_INPUT (y, i),
! validate, for_gcse)
|| strcmp (ASM_OPERANDS_INPUT_CONSTRAINT (x, i),
ASM_OPERANDS_INPUT_CONSTRAINT (y, i)))
return 0;
*************** exp_equiv_p (rtx x, rtx y, int validate,
*** 2511,2517 ****
}
/* Compare the elements. If any pair of corresponding elements
! fail to match, return 0 for the whole things. */
fmt = GET_RTX_FORMAT (code);
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
--- 2540,2546 ----
}
/* Compare the elements. If any pair of corresponding elements
! fail to match, return 0 for the whole thing. */
fmt = GET_RTX_FORMAT (code);
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
*************** exp_equiv_p (rtx x, rtx y, int validate,
*** 2519,2525 ****
switch (fmt[i])
{
case 'e':
! if (! exp_equiv_p (XEXP (x, i), XEXP (y, i), validate, equal_values))
return 0;
break;
--- 2548,2555 ----
switch (fmt[i])
{
case 'e':
! if (! exp_equiv_p (XEXP (x, i), XEXP (y, i),
! validate, for_gcse))
return 0;
break;
*************** exp_equiv_p (rtx x, rtx y, int validate,
*** 2528,2534 ****
return 0;
for (j = 0; j < XVECLEN (x, i); j++)
if (! exp_equiv_p (XVECEXP (x, i, j), XVECEXP (y, i, j),
! validate, equal_values))
return 0;
break;
--- 2558,2564 ----
return 0;
for (j = 0; j < XVECLEN (x, i); j++)
if (! exp_equiv_p (XVECEXP (x, i, j), XVECEXP (y, i, j),
! validate, for_gcse))
return 0;
break;
*************** find_best_addr (rtx insn, rtx *loc, enum
*** 2827,2833 ****
if (! p->flag)
{
if ((REG_P (p->exp)
! || exp_equiv_p (p->exp, p->exp, 1, 0))
&& ((exp_cost = address_cost (p->exp, mode)) < best_addr_cost
|| (exp_cost == best_addr_cost
&& ((p->cost + 1) >> 1) > best_rtx_cost)))
--- 2857,2863 ----
if (! p->flag)
{
if ((REG_P (p->exp)
! || exp_equiv_p (p->exp, p->exp, 1, false))
&& ((exp_cost = address_cost (p->exp, mode)) < best_addr_cost
|| (exp_cost == best_addr_cost
&& ((p->cost + 1) >> 1) > best_rtx_cost)))
*************** find_best_addr (rtx insn, rtx *loc, enum
*** 2903,2909 ****
p = p->next_same_value, count++)
if (! p->flag
&& (REG_P (p->exp)
! || exp_equiv_p (p->exp, p->exp, 1, 0)))
{
rtx new = simplify_gen_binary (GET_CODE (*loc), Pmode,
p->exp, op1);
--- 2933,2939 ----
p = p->next_same_value, count++)
if (! p->flag
&& (REG_P (p->exp)
! || exp_equiv_p (p->exp, p->exp, 1, false)))
{
rtx new = simplify_gen_binary (GET_CODE (*loc), Pmode,
p->exp, op1);
*************** find_comparison_args (enum rtx_code code
*** 3012,3019 ****
if (x == 0)
/* Look up ARG1 in the hash table and see if it has an equivalence
that lets us see what is being compared. */
! p = lookup (arg1, safe_hash (arg1, GET_MODE (arg1)) & HASH_MASK,
! GET_MODE (arg1));
if (p)
{
p = p->first_same_value;
--- 3042,3048 ----
if (x == 0)
/* Look up ARG1 in the hash table and see if it has an equivalence
that lets us see what is being compared. */
! p = lookup (arg1, SAFE_HASH (arg1, GET_MODE (arg1)), GET_MODE (arg1));
if (p)
{
p = p->first_same_value;
*************** find_comparison_args (enum rtx_code code
*** 3038,3044 ****
#endif
/* If the entry isn't valid, skip it. */
! if (! exp_equiv_p (p->exp, p->exp, 1, 0))
continue;
if (GET_CODE (p->exp) == COMPARE
--- 3067,3073 ----
#endif
/* If the entry isn't valid, skip it. */
! if (! exp_equiv_p (p->exp, p->exp, 1, false))
continue;
if (GET_CODE (p->exp) == COMPARE
*************** fold_rtx (rtx x, rtx insn)
*** 3235,3241 ****
if (GET_CODE (elt->exp) == SUBREG
&& GET_MODE (SUBREG_REG (elt->exp)) == mode
! && exp_equiv_p (elt->exp, elt->exp, 1, 0))
return copy_rtx (SUBREG_REG (elt->exp));
}
--- 3264,3270 ----
if (GET_CODE (elt->exp) == SUBREG
&& GET_MODE (SUBREG_REG (elt->exp)) == mode
! && exp_equiv_p (elt->exp, elt->exp, 1, false))
return copy_rtx (SUBREG_REG (elt->exp));
}
*************** fold_rtx (rtx x, rtx insn)
*** 3264,3271 ****
{
struct table_elt *elt;
- /* We can use HASH here since we know that canon_hash won't be
- called. */
elt = lookup (folded_arg0,
HASH (folded_arg0, GET_MODE (folded_arg0)),
GET_MODE (folded_arg0));
--- 3293,3298 ----
*************** fold_rtx (rtx x, rtx insn)
*** 3370,3376 ****
&& GET_MODE (SUBREG_REG (elt->exp)) == mode
&& (GET_MODE_SIZE (GET_MODE (folded_arg0))
<= UNITS_PER_WORD)
! && exp_equiv_p (elt->exp, elt->exp, 1, 0))
new = copy_rtx (SUBREG_REG (elt->exp));
if (new)
--- 3397,3403 ----
&& GET_MODE (SUBREG_REG (elt->exp)) == mode
&& (GET_MODE_SIZE (GET_MODE (folded_arg0))
<= UNITS_PER_WORD)
! && exp_equiv_p (elt->exp, elt->exp, 1, false))
new = copy_rtx (SUBREG_REG (elt->exp));
if (new)
*************** fold_rtx (rtx x, rtx insn)
*** 3829,3839 ****
&& (REG_QTY (REGNO (folded_arg0))
== REG_QTY (REGNO (folded_arg1))))
|| ((p0 = lookup (folded_arg0,
! (safe_hash (folded_arg0, mode_arg0)
! & HASH_MASK), mode_arg0))
&& (p1 = lookup (folded_arg1,
! (safe_hash (folded_arg1, mode_arg0)
! & HASH_MASK), mode_arg0))
&& p0->first_same_value == p1->first_same_value))
{
/* Sadly two equal NaNs are not equivalent. */
--- 3856,3866 ----
&& (REG_QTY (REGNO (folded_arg0))
== REG_QTY (REGNO (folded_arg1))))
|| ((p0 = lookup (folded_arg0,
! SAFE_HASH (folded_arg0, mode_arg0),
! mode_arg0))
&& (p1 = lookup (folded_arg1,
! SAFE_HASH (folded_arg1, mode_arg0),
! mode_arg0))
&& p0->first_same_value == p1->first_same_value))
{
/* Sadly two equal NaNs are not equivalent. */
*************** fold_rtx (rtx x, rtx insn)
*** 4007,4014 ****
{
rtx new_const = GEN_INT (-INTVAL (const_arg1));
struct table_elt *p
! = lookup (new_const, safe_hash (new_const, mode) & HASH_MASK,
! mode);
if (p)
for (p = p->first_same_value; p; p = p->next_same_value)
--- 4034,4040 ----
{
rtx new_const = GEN_INT (-INTVAL (const_arg1));
struct table_elt *p
! = lookup (new_const, SAFE_HASH (new_const, mode), mode);
if (p)
for (p = p->first_same_value; p; p = p->next_same_value)
*************** equiv_constant (rtx x)
*** 4195,4201 ****
if (CONSTANT_P (x))
return x;
! elt = lookup (x, safe_hash (x, GET_MODE (x)) & HASH_MASK, GET_MODE (x));
if (elt == 0)
return 0;
--- 4221,4227 ----
if (CONSTANT_P (x))
return x;
! elt = lookup (x, SAFE_HASH (x, GET_MODE (x)), GET_MODE (x));
if (elt == 0)
return 0;
*************** cse_insn (rtx insn, rtx libcall_insn)
*** 5182,5188 ****
/* If the expression is not valid, ignore it. Then we do not
have to check for validity below. In most cases, we can use
`rtx_equal_p', since canonicalization has already been done. */
! if (code != REG && ! exp_equiv_p (p->exp, p->exp, 1, 0))
continue;
/* Also skip paradoxical subregs, unless that's what we're
--- 5208,5214 ----
/* If the expression is not valid, ignore it. Then we do not
have to check for validity below. In most cases, we can use
`rtx_equal_p', since canonicalization has already been done. */
! if (code != REG && ! exp_equiv_p (p->exp, p->exp, 1, false))
continue;
/* Also skip paradoxical subregs, unless that's what we're
*************** cse_insn (rtx insn, rtx libcall_insn)
*** 5279,5285 ****
/* Skip invalid entries. */
while (elt && !REG_P (elt->exp)
! && ! exp_equiv_p (elt->exp, elt->exp, 1, 0))
elt = elt->next_same_value;
/* A paradoxical subreg would be bad here: it'll be the right
--- 5305,5311 ----
/* Skip invalid entries. */
while (elt && !REG_P (elt->exp)
! && ! exp_equiv_p (elt->exp, elt->exp, 1, false))
elt = elt->next_same_value;
/* A paradoxical subreg would be bad here: it'll be the right
*************** cse_insn (rtx insn, rtx libcall_insn)
*** 6006,6012 ****
/* Ignore invalid entries. */
if (!REG_P (elt->exp)
! && ! exp_equiv_p (elt->exp, elt->exp, 1, 0))
continue;
/* We may have already been playing subreg games. If the
--- 6032,6038 ----
/* Ignore invalid entries. */
if (!REG_P (elt->exp)
! && ! exp_equiv_p (elt->exp, elt->exp, 1, false))
continue;
/* We may have already been playing subreg games. If the
*************** cse_insn (rtx insn, rtx libcall_insn)
*** 6059,6065 ****
/* Ignore invalid entries. */
while (classp
&& !REG_P (classp->exp)
! && ! exp_equiv_p (classp->exp, classp->exp, 1, 0))
classp = classp->next_same_value;
}
}
--- 6085,6091 ----
/* Ignore invalid entries. */
while (classp
&& !REG_P (classp->exp)
! && ! exp_equiv_p (classp->exp, classp->exp, 1, false))
classp = classp->next_same_value;
}
}
Index: cselib.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cselib.c,v
retrieving revision 1.49
diff -c -3 -p -r1.49 cselib.c
*** cselib.c 9 Jul 2004 03:29:26 -0000 1.49
--- cselib.c 18 Aug 2004 17:51:30 -0000
*************** static int discard_useless_locs (void **
*** 55,61 ****
static int discard_useless_values (void **, void *);
static void remove_useless_values (void);
static rtx wrap_constant (enum machine_mode, rtx);
! static unsigned int hash_rtx (rtx, enum machine_mode, int);
static cselib_val *new_cselib_val (unsigned int, enum machine_mode);
static void add_mem_for_addr (cselib_val *, cselib_val *, rtx);
static cselib_val *cselib_lookup_mem (rtx, int);
--- 55,61 ----
static int discard_useless_values (void **, void *);
static void remove_useless_values (void);
static rtx wrap_constant (enum machine_mode, rtx);
! static unsigned int cselib_hash_rtx (rtx, enum machine_mode, int);
static cselib_val *new_cselib_val (unsigned int, enum machine_mode);
static void add_mem_for_addr (cselib_val *, cselib_val *, rtx);
static cselib_val *cselib_lookup_mem (rtx, int);
*************** entry_and_rtx_equal_p (const void *entry
*** 257,264 ****
}
/* The hash function for our hash table. The value is always computed with
! hash_rtx when adding an element; this function just extracts the hash
! value from a cselib_val structure. */
static hashval_t
get_value_hash (const void *entry)
--- 257,264 ----
}
/* The hash function for our hash table. The value is always computed with
! cselib_hash_rtx when adding an element; this function just extracts the
! hash value from a cselib_val structure. */
static hashval_t
get_value_hash (const void *entry)
*************** wrap_constant (enum machine_mode mode, r
*** 554,560 ****
otherwise the mode of X is used. */
static unsigned int
! hash_rtx (rtx x, enum machine_mode mode, int create)
{
cselib_val *e;
int i, j;
--- 554,560 ----
otherwise the mode of X is used. */
static unsigned int
! cselib_hash_rtx (rtx x, enum machine_mode mode, int create)
{
cselib_val *e;
int i, j;
*************** hash_rtx (rtx x, enum machine_mode mode,
*** 600,606 ****
for (i = 0; i < units; ++i)
{
elt = CONST_VECTOR_ELT (x, i);
! hash += hash_rtx (elt, GET_MODE (elt), 0);
}
return hash;
--- 600,606 ----
for (i = 0; i < units; ++i)
{
elt = CONST_VECTOR_ELT (x, i);
! hash += cselib_hash_rtx (elt, GET_MODE (elt), 0);
}
return hash;
*************** hash_rtx (rtx x, enum machine_mode mode,
*** 646,652 ****
if (fmt[i] == 'e')
{
rtx tem = XEXP (x, i);
! unsigned int tem_hash = hash_rtx (tem, 0, create);
if (tem_hash == 0)
return 0;
--- 646,652 ----
if (fmt[i] == 'e')
{
rtx tem = XEXP (x, i);
! unsigned int tem_hash = cselib_hash_rtx (tem, 0, create);
if (tem_hash == 0)
return 0;
*************** hash_rtx (rtx x, enum machine_mode mode,
*** 656,662 ****
else if (fmt[i] == 'E')
for (j = 0; j < XVECLEN (x, i); j++)
{
! unsigned int tem_hash = hash_rtx (XVECEXP (x, i, j), 0, create);
if (tem_hash == 0)
return 0;
--- 656,662 ----
else if (fmt[i] == 'E')
for (j = 0; j < XVECLEN (x, i); j++)
{
! unsigned int tem_hash = cselib_hash_rtx (XVECEXP (x, i, j), 0, create);
if (tem_hash == 0)
return 0;
*************** cselib_lookup (rtx x, enum machine_mode
*** 926,932 ****
if (MEM_P (x))
return cselib_lookup_mem (x, create);
! hashval = hash_rtx (x, mode, create);
/* Can't even create if hashing is not possible. */
if (! hashval)
return 0;
--- 926,932 ----
if (MEM_P (x))
return cselib_lookup_mem (x, create);
! hashval = cselib_hash_rtx (x, mode, create);
/* Can't even create if hashing is not possible. */
if (! hashval)
return 0;
Index: gcse.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/gcse.c,v
retrieving revision 1.309
diff -c -3 -p -r1.309 gcse.c
*** gcse.c 9 Aug 2004 16:58:42 -0000 1.309
--- gcse.c 18 Aug 2004 17:51:30 -0000
*************** static sbitmap *reg_set_in_block;
*** 495,505 ****
/* Array, indexed by basic block number for a list of insns which modify
memory within that block. */
static rtx * modify_mem_list;
! bitmap modify_mem_list_set;
/* This array parallels modify_mem_list, but is kept canonicalized. */
static rtx * canon_modify_mem_list;
! bitmap canon_modify_mem_list_set;
/* Various variables for statistics gathering. */
/* Memory used in a pass.
--- 495,506 ----
/* Array, indexed by basic block number for a list of insns which modify
memory within that block. */
static rtx * modify_mem_list;
! static bitmap modify_mem_list_set;
/* This array parallels modify_mem_list, but is kept canonicalized. */
static rtx * canon_modify_mem_list;
! static bitmap canon_modify_mem_list_set;
!
/* Various variables for statistics gathering. */
/* Memory used in a pass.
*************** static void insert_expr_in_table (rtx, e
*** 564,571 ****
struct hash_table *);
static void insert_set_in_table (rtx, rtx, struct hash_table *);
static unsigned int hash_expr (rtx, enum machine_mode, int *, int);
- static unsigned int hash_expr_1 (rtx, enum machine_mode, int *);
- static unsigned int hash_string_1 (const char *);
static unsigned int hash_set (int, int);
static int expr_equiv_p (rtx, rtx);
static void record_last_reg_set_info (rtx, int);
--- 565,570 ----
*************** static void alloc_hash_table (int, struc
*** 576,582 ****
static void free_hash_table (struct hash_table *);
static void compute_hash_table_work (struct hash_table *);
static void dump_hash_table (FILE *, const char *, struct hash_table *);
- static struct expr *lookup_expr (rtx, struct hash_table *);
static struct expr *lookup_set (unsigned int, struct hash_table *);
static struct expr *next_set (unsigned int, struct expr *);
static void reset_opr_set_tables (void);
--- 575,580 ----
*************** oprs_available_p (rtx x, rtx insn)
*** 1462,1470 ****
MODE is only used if X is a CONST_INT. DO_NOT_RECORD_P is a boolean
indicating if a volatile operand is found or if the expression contains
something we don't want to insert in the table. HASH_TABLE_SIZE is
! the current size of the hash table to be probed.
!
! ??? One might want to merge this with canon_hash. Later. */
static unsigned int
hash_expr (rtx x, enum machine_mode mode, int *do_not_record_p,
--- 1460,1466 ----
MODE is only used if X is a CONST_INT. DO_NOT_RECORD_P is a boolean
indicating if a volatile operand is found or if the expression contains
something we don't want to insert in the table. HASH_TABLE_SIZE is
! the current size of the hash table to be probed. */
static unsigned int
hash_expr (rtx x, enum machine_mode mode, int *do_not_record_p,
*************** hash_expr (rtx x, enum machine_mode mode
*** 1474,1681 ****
*do_not_record_p = 0;
! hash = hash_expr_1 (x, mode, do_not_record_p);
return hash % hash_table_size;
}
- /* Hash a string. Just add its bytes up. */
-
- static inline unsigned
- hash_string_1 (const char *ps)
- {
- unsigned hash = 0;
- const unsigned char *p = (const unsigned char *) ps;
-
- if (p)
- while (*p)
- hash += *p++;
-
- return hash;
- }
-
- /* Subroutine of hash_expr to do the actual work. */
-
- static unsigned int
- hash_expr_1 (rtx x, enum machine_mode mode, int *do_not_record_p)
- {
- int i, j;
- unsigned hash = 0;
- enum rtx_code code;
- const char *fmt;
-
- if (x == 0)
- return hash;
-
- /* Used to turn recursion into iteration. We can't rely on GCC's
- tail-recursion elimination since we need to keep accumulating values
- in HASH. */
- repeat:
-
- code = GET_CODE (x);
- switch (code)
- {
- case REG:
- hash += ((unsigned int) REG << 7) + REGNO (x);
- return hash;
-
- case CONST_INT:
- hash += (((unsigned int) CONST_INT << 7) + (unsigned int) mode
- + (unsigned int) INTVAL (x));
- return hash;
-
- case CONST_DOUBLE:
- /* This is like the general case, except that it only counts
- the integers representing the constant. */
- hash += (unsigned int) code + (unsigned int) GET_MODE (x);
- if (GET_MODE (x) != VOIDmode)
- for (i = 2; i < GET_RTX_LENGTH (CONST_DOUBLE); i++)
- hash += (unsigned int) XWINT (x, i);
- else
- hash += ((unsigned int) CONST_DOUBLE_LOW (x)
- + (unsigned int) CONST_DOUBLE_HIGH (x));
- return hash;
-
- case CONST_VECTOR:
- {
- int units;
- rtx elt;
-
- units = CONST_VECTOR_NUNITS (x);
-
- for (i = 0; i < units; ++i)
- {
- elt = CONST_VECTOR_ELT (x, i);
- hash += hash_expr_1 (elt, GET_MODE (elt), do_not_record_p);
- }
-
- return hash;
- }
-
- /* Assume there is only one rtx object for any given label. */
- case LABEL_REF:
- /* We don't hash on the address of the CODE_LABEL to avoid bootstrap
- differences and differences between each stage's debugging dumps. */
- hash += (((unsigned int) LABEL_REF << 7)
- + CODE_LABEL_NUMBER (XEXP (x, 0)));
- return hash;
-
- case SYMBOL_REF:
- {
- /* Don't hash on the symbol's address to avoid bootstrap differences.
- Different hash values may cause expressions to be recorded in
- different orders and thus different registers to be used in the
- final assembler. This also avoids differences in the dump files
- between various stages. */
- unsigned int h = 0;
- const unsigned char *p = (const unsigned char *) XSTR (x, 0);
-
- while (*p)
- h += (h << 7) + *p++; /* ??? revisit */
-
- hash += ((unsigned int) SYMBOL_REF << 7) + h;
- return hash;
- }
-
- case MEM:
- if (MEM_VOLATILE_P (x))
- {
- *do_not_record_p = 1;
- return 0;
- }
-
- hash += (unsigned int) MEM;
- /* We used alias set for hashing, but this is not good, since the alias
- set may differ in -fprofile-arcs and -fbranch-probabilities compilation
- causing the profiles to fail to match. */
- x = XEXP (x, 0);
- goto repeat;
-
- case PRE_DEC:
- case PRE_INC:
- case POST_DEC:
- case POST_INC:
- case PC:
- case CC0:
- case CALL:
- case UNSPEC_VOLATILE:
- *do_not_record_p = 1;
- return 0;
-
- case ASM_OPERANDS:
- if (MEM_VOLATILE_P (x))
- {
- *do_not_record_p = 1;
- return 0;
- }
- else
- {
- /* We don't want to take the filename and line into account. */
- hash += (unsigned) code + (unsigned) GET_MODE (x)
- + hash_string_1 (ASM_OPERANDS_TEMPLATE (x))
- + hash_string_1 (ASM_OPERANDS_OUTPUT_CONSTRAINT (x))
- + (unsigned) ASM_OPERANDS_OUTPUT_IDX (x);
-
- if (ASM_OPERANDS_INPUT_LENGTH (x))
- {
- for (i = 1; i < ASM_OPERANDS_INPUT_LENGTH (x); i++)
- {
- hash += (hash_expr_1 (ASM_OPERANDS_INPUT (x, i),
- GET_MODE (ASM_OPERANDS_INPUT (x, i)),
- do_not_record_p)
- + hash_string_1 (ASM_OPERANDS_INPUT_CONSTRAINT
- (x, i)));
- }
-
- hash += hash_string_1 (ASM_OPERANDS_INPUT_CONSTRAINT (x, 0));
- x = ASM_OPERANDS_INPUT (x, 0);
- mode = GET_MODE (x);
- goto repeat;
- }
- return hash;
- }
-
- default:
- break;
- }
-
- hash += (unsigned) code + (unsigned) GET_MODE (x);
- for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
- {
- if (fmt[i] == 'e')
- {
- /* If we are about to do the last recursive call
- needed at this level, change it into iteration.
- This function is called enough to be worth it. */
- if (i == 0)
- {
- x = XEXP (x, i);
- goto repeat;
- }
-
- hash += hash_expr_1 (XEXP (x, i), 0, do_not_record_p);
- if (*do_not_record_p)
- return 0;
- }
-
- else if (fmt[i] == 'E')
- for (j = 0; j < XVECLEN (x, i); j++)
- {
- hash += hash_expr_1 (XVECEXP (x, i, j), 0, do_not_record_p);
- if (*do_not_record_p)
- return 0;
- }
-
- else if (fmt[i] == 's')
- hash += hash_string_1 (XSTR (x, i));
- else if (fmt[i] == 'i')
- hash += (unsigned int) XINT (x, i);
- else
- abort ();
- }
-
- return hash;
- }
-
/* Hash a set of register REGNO.
Sets are hashed on the register that is set. This simplifies the PRE copy
--- 1470,1480 ----
*do_not_record_p = 0;
! hash = hash_rtx (x, mode, do_not_record_p,
! NULL, /*have_reg_qty=*/false);
return hash % hash_table_size;
}
/* Hash a set of register REGNO.
Sets are hashed on the register that is set. This simplifies the PRE copy
*************** hash_set (int regno, int hash_table_size
*** 1692,1839 ****
return hash % hash_table_size;
}
! /* Return nonzero if exp1 is equivalent to exp2.
! ??? Borrowed from cse.c. Might want to remerge with cse.c. Later. */
static int
expr_equiv_p (rtx x, rtx y)
{
! int i, j;
! enum rtx_code code;
! const char *fmt;
!
! if (x == y)
! return 1;
!
! if (x == 0 || y == 0)
! return 0;
!
! code = GET_CODE (x);
! if (code != GET_CODE (y))
! return 0;
!
! /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. */
! if (GET_MODE (x) != GET_MODE (y))
! return 0;
!
! switch (code)
! {
! case PC:
! case CC0:
! case CONST_INT:
! return 0;
!
! case LABEL_REF:
! return XEXP (x, 0) == XEXP (y, 0);
!
! case SYMBOL_REF:
! return XSTR (x, 0) == XSTR (y, 0);
!
! case REG:
! return REGNO (x) == REGNO (y);
!
! case MEM:
! /* Can't merge two expressions in different alias sets, since we can
! decide that the expression is transparent in a block when it isn't,
! due to it being set with the different alias set. */
! if (MEM_ALIAS_SET (x) != MEM_ALIAS_SET (y))
! return 0;
!
! /* A volatile mem should not be considered equivalent to any other. */
! if (MEM_VOLATILE_P (x) || MEM_VOLATILE_P (y))
! return 0;
! break;
!
! /* For commutative operations, check both orders. */
! case PLUS:
! case MULT:
! case AND:
! case IOR:
! case XOR:
! case NE:
! case EQ:
! return ((expr_equiv_p (XEXP (x, 0), XEXP (y, 0))
! && expr_equiv_p (XEXP (x, 1), XEXP (y, 1)))
! || (expr_equiv_p (XEXP (x, 0), XEXP (y, 1))
! && expr_equiv_p (XEXP (x, 1), XEXP (y, 0))));
!
! case ASM_OPERANDS:
! /* We don't use the generic code below because we want to
! disregard filename and line numbers. */
!
! /* A volatile asm isn't equivalent to any other. */
! if (MEM_VOLATILE_P (x) || MEM_VOLATILE_P (y))
! return 0;
!
! if (GET_MODE (x) != GET_MODE (y)
! || strcmp (ASM_OPERANDS_TEMPLATE (x), ASM_OPERANDS_TEMPLATE (y))
! || strcmp (ASM_OPERANDS_OUTPUT_CONSTRAINT (x),
! ASM_OPERANDS_OUTPUT_CONSTRAINT (y))
! || ASM_OPERANDS_OUTPUT_IDX (x) != ASM_OPERANDS_OUTPUT_IDX (y)
! || ASM_OPERANDS_INPUT_LENGTH (x) != ASM_OPERANDS_INPUT_LENGTH (y))
! return 0;
!
! if (ASM_OPERANDS_INPUT_LENGTH (x))
! {
! for (i = ASM_OPERANDS_INPUT_LENGTH (x) - 1; i >= 0; i--)
! if (! expr_equiv_p (ASM_OPERANDS_INPUT (x, i),
! ASM_OPERANDS_INPUT (y, i))
! || strcmp (ASM_OPERANDS_INPUT_CONSTRAINT (x, i),
! ASM_OPERANDS_INPUT_CONSTRAINT (y, i)))
! return 0;
! }
!
! return 1;
!
! default:
! break;
! }
!
! /* Compare the elements. If any pair of corresponding elements
! fail to match, return 0 for the whole thing. */
!
! fmt = GET_RTX_FORMAT (code);
! for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
! {
! switch (fmt[i])
! {
! case 'e':
! if (! expr_equiv_p (XEXP (x, i), XEXP (y, i)))
! return 0;
! break;
!
! case 'E':
! if (XVECLEN (x, i) != XVECLEN (y, i))
! return 0;
! for (j = 0; j < XVECLEN (x, i); j++)
! if (! expr_equiv_p (XVECEXP (x, i, j), XVECEXP (y, i, j)))
! return 0;
! break;
!
! case 's':
! if (strcmp (XSTR (x, i), XSTR (y, i)))
! return 0;
! break;
!
! case 'i':
! if (XINT (x, i) != XINT (y, i))
! return 0;
! break;
!
! case 'w':
! if (XWINT (x, i) != XWINT (y, i))
! return 0;
! break;
!
! case '0':
! break;
!
! default:
! abort ();
! }
! }
!
! return 1;
}
/* Insert expression X in INSN in the hash TABLE.
--- 1491,1502 ----
return hash % hash_table_size;
}
! /* Return nonzero if exp1 is equivalent to exp2. */
static int
expr_equiv_p (rtx x, rtx y)
{
! return exp_equiv_p (x, y, 0, true);
}
/* Insert expression X in INSN in the hash TABLE.
*************** compute_hash_table (struct hash_table *t
*** 2556,2583 ****
/* Expression tracking support. */
- /* Lookup pattern PAT in the expression TABLE.
- The result is a pointer to the table entry, or NULL if not found. */
-
- static struct expr *
- lookup_expr (rtx pat, struct hash_table *table)
- {
- int do_not_record_p;
- unsigned int hash = hash_expr (pat, GET_MODE (pat), &do_not_record_p,
- table->size);
- struct expr *expr;
-
- if (do_not_record_p)
- return NULL;
-
- expr = table->table[hash];
-
- while (expr && ! expr_equiv_p (expr->expr, pat))
- expr = expr->next_same_hash;
-
- return expr;
- }
-
/* Lookup REGNO in the set TABLE. The result is a pointer to the
table entry, or NULL if not found. */
--- 2219,2224 ----
*************** ldst_entry (rtx x)
*** 5426,5432 ****
struct ls_expr * ptr;
unsigned int hash;
! hash = hash_expr_1 (x, GET_MODE (x), & do_not_record_p);
for (ptr = pre_ldst_mems; ptr != NULL; ptr = ptr->next)
if (ptr->hash_index == hash && expr_equiv_p (ptr->pattern, x))
--- 5067,5074 ----
struct ls_expr * ptr;
unsigned int hash;
! hash = hash_rtx (x, GET_MODE (x), &do_not_record_p,
! NULL, /*have_reg_qty=*/false);
for (ptr = pre_ldst_mems; ptr != NULL; ptr = ptr->next)
if (ptr->hash_index == hash && expr_equiv_p (ptr->pattern, x))
*************** is_too_expensive (const char *pass)
*** 6945,7598 ****
return false;
}
- /* The following code implements gcse after reload, the purpose of this
- pass is to cleanup redundant loads generated by reload and other
- optimizations that come after gcse. It searches for simple inter-block
- redundancies and tries to eliminate them by adding moves and loads
- in cold places. */
-
- /* The following structure holds the information about the occurrences of
- the redundant instructions. */
- struct unoccr
- {
- struct unoccr *next;
- edge pred;
- rtx insn;
- };
-
- static bool reg_used_on_edge (rtx, edge);
- static rtx reg_set_between_after_reload_p (rtx, rtx, rtx);
- static rtx reg_used_between_after_reload_p (rtx, rtx, rtx);
- static rtx get_avail_load_store_reg (rtx);
- static bool is_jump_table_basic_block (basic_block);
- static bool bb_has_well_behaved_predecessors (basic_block);
- static struct occr* get_bb_avail_insn (basic_block, struct occr *);
- static void hash_scan_set_after_reload (rtx, rtx, struct hash_table *);
- static void compute_hash_table_after_reload (struct hash_table *);
- static void eliminate_partially_redundant_loads (basic_block,
- rtx,
- struct expr *);
- static void gcse_after_reload (void);
- static struct occr* get_bb_avail_insn (basic_block, struct occr *);
- void gcse_after_reload_main (rtx, FILE *);
-
-
- /* Check if register REG is used in any insn waiting to be inserted on E.
- Assumes no such insn can be a CALL_INSN; if so call reg_used_between_p
- with PREV(insn),NEXT(insn) instead of calling
- reg_overlap_mentioned_p. */
-
- static bool
- reg_used_on_edge (rtx reg, edge e)
- {
- rtx insn;
-
- for (insn = e->insns.r; insn; insn = NEXT_INSN (insn))
- if (INSN_P (insn) && reg_overlap_mentioned_p (reg, PATTERN (insn)))
- return true;
-
- return false;
- }
-
- /* Return the insn that sets register REG or clobbers it in between
- FROM_INSN and TO_INSN (exclusive of those two).
- Just like reg_set_between but for hard registers and not pseudos. */
-
- static rtx
- reg_set_between_after_reload_p (rtx reg, rtx from_insn, rtx to_insn)
- {
- rtx insn;
- int regno;
-
- if (! REG_P (reg))
- abort ();
- regno = REGNO (reg);
-
- /* We are called after register allocation. */
- if (regno >= FIRST_PSEUDO_REGISTER)
- abort ();
-
- if (from_insn == to_insn)
- return NULL_RTX;
-
- for (insn = NEXT_INSN (from_insn);
- insn != to_insn;
- insn = NEXT_INSN (insn))
- {
- if (INSN_P (insn))
- {
- if (FIND_REG_INC_NOTE (insn, reg)
- || (CALL_P (insn)
- && call_used_regs[regno])
- || find_reg_fusage (insn, CLOBBER, reg))
- return insn;
- }
- if (set_of (reg, insn) != NULL_RTX)
- return insn;
- }
- return NULL_RTX;
- }
-
- /* Return the insn that uses register REG in between FROM_INSN and TO_INSN
- (exclusive of those two). Similar to reg_used_between but for hard
- registers and not pseudos. */
-
- static rtx
- reg_used_between_after_reload_p (rtx reg, rtx from_insn, rtx to_insn)
- {
- rtx insn;
- int regno;
-
- if (! REG_P (reg))
- return to_insn;
- regno = REGNO (reg);
-
- /* We are called after register allocation. */
- if (regno >= FIRST_PSEUDO_REGISTER)
- abort ();
- if (from_insn == to_insn)
- return NULL_RTX;
-
- for (insn = NEXT_INSN (from_insn);
- insn != to_insn;
- insn = NEXT_INSN (insn))
- if (INSN_P (insn)
- && (reg_overlap_mentioned_p (reg, PATTERN (insn))
- || (CALL_P (insn)
- && call_used_regs[regno])
- || find_reg_fusage (insn, USE, reg)
- || find_reg_fusage (insn, CLOBBER, reg)))
- return insn;
- return NULL_RTX;
- }
-
- /* Return the loaded/stored register of a load/store instruction. */
-
- static rtx
- get_avail_load_store_reg (rtx insn)
- {
- if (REG_P (SET_DEST (PATTERN (insn)))) /* A load. */
- return SET_DEST(PATTERN(insn));
- if (REG_P (SET_SRC (PATTERN (insn)))) /* A store. */
- return SET_SRC (PATTERN (insn));
- abort ();
- }
-
- /* Don't handle ABNORMAL edges or jump tables. */
-
- static bool
- is_jump_table_basic_block (basic_block bb)
- {
- rtx insn = BB_END (bb);
-
- if (JUMP_TABLE_DATA_P (insn))
- return true;
- return false;
- }
-
- /* Return nonzero if the predecessors of BB are "well behaved". */
-
- static bool
- bb_has_well_behaved_predecessors (basic_block bb)
- {
- edge pred;
-
- if (! bb->pred)
- return false;
- for (pred = bb->pred; pred != NULL; pred = pred->pred_next)
- if (((pred->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (pred))
- || is_jump_table_basic_block (pred->src))
- return false;
- return true;
- }
-
-
- /* Search for the occurrences of expression in BB. */
-
- static struct occr*
- get_bb_avail_insn (basic_block bb, struct occr *occr)
- {
- for (; occr != NULL; occr = occr->next)
- if (BLOCK_FOR_INSN (occr->insn)->index == bb->index)
- return occr;
- return NULL;
- }
-
- /* Perform partial GCSE pass after reload, try to eliminate redundant loads
- created by the reload pass. We try to look for a full or partial
- redundant loads fed by one or more loads/stores in predecessor BBs,
- and try adding loads to make them fully redundant. We also check if
- it's worth adding loads to be able to delete the redundant load.
-
- Algorithm:
- 1. Build available expressions hash table:
- For each load/store instruction, if the loaded/stored memory didn't
- change until the end of the basic block add this memory expression to
- the hash table.
- 2. Perform Redundancy elimination:
- For each load instruction do the following:
- perform partial redundancy elimination, check if it's worth adding
- loads to make the load fully redundant. If so add loads and
- register copies and delete the load.
-
- Future enhancement:
- if loaded register is used/defined between load and some store,
- look for some other free register between load and all its stores,
- and replace load with a copy from this register to the loaded
- register. */
-
-
- /* This handles the case where several stores feed a partially redundant
- load. It checks if the redundancy elimination is possible and if it's
- worth it. */
-
- static void
- eliminate_partially_redundant_loads (basic_block bb, rtx insn,
- struct expr *expr)
- {
- edge pred;
- rtx avail_insn = NULL_RTX;
- rtx avail_reg;
- rtx dest, pat;
- struct occr *a_occr;
- struct unoccr *occr, *avail_occrs = NULL;
- struct unoccr *unoccr, *unavail_occrs = NULL;
- int npred_ok = 0;
- gcov_type ok_count = 0; /* Redundant load execution count. */
- gcov_type critical_count = 0; /* Execution count of critical edges. */
-
- /* The execution count of the loads to be added to make the
- load fully redundant. */
- gcov_type not_ok_count = 0;
- basic_block pred_bb;
-
- pat = PATTERN (insn);
- dest = SET_DEST (pat);
- /* Check that the loaded register is not used, set, or killed from the
- beginning of the block. */
- if (reg_used_between_after_reload_p (dest,
- PREV_INSN (BB_HEAD (bb)), insn)
- || reg_set_between_after_reload_p (dest,
- PREV_INSN (BB_HEAD (bb)), insn))
- return;
-
- /* Check potential for replacing load with copy for predecessors. */
- for (pred = bb->pred; pred; pred = pred->pred_next)
- {
- rtx next_pred_bb_end;
-
- avail_insn = NULL_RTX;
- pred_bb = pred->src;
- next_pred_bb_end = NEXT_INSN (BB_END (pred_bb));
- for (a_occr = get_bb_avail_insn (pred_bb, expr->avail_occr); a_occr;
- a_occr = get_bb_avail_insn (pred_bb, a_occr->next))
- {
- /* Check if the loaded register is not used. */
- avail_insn = a_occr->insn;
- if (! (avail_reg = get_avail_load_store_reg (avail_insn)))
- abort ();
- /* Make sure we can generate a move from register avail_reg to
- dest. */
- extract_insn (gen_move_insn (copy_rtx (dest),
- copy_rtx (avail_reg)));
- if (! constrain_operands (1)
- || reg_killed_on_edge (avail_reg, pred)
- || reg_used_on_edge (dest, pred))
- {
- avail_insn = NULL;
- continue;
- }
- if (! reg_set_between_after_reload_p (avail_reg, avail_insn,
- next_pred_bb_end))
- /* AVAIL_INSN remains non-null. */
- break;
- else
- avail_insn = NULL;
- }
- if (avail_insn != NULL_RTX)
- {
- npred_ok++;
- ok_count += pred->count;
- if (EDGE_CRITICAL_P (pred))
- critical_count += pred->count;
- occr = gmalloc (sizeof (struct unoccr));
- occr->insn = avail_insn;
- occr->pred = pred;
- occr->next = avail_occrs;
- avail_occrs = occr;
- }
- else
- {
- not_ok_count += pred->count;
- if (EDGE_CRITICAL_P (pred))
- critical_count += pred->count;
- unoccr = gmalloc (sizeof (struct unoccr));
- unoccr->insn = NULL_RTX;
- unoccr->pred = pred;
- unoccr->next = unavail_occrs;
- unavail_occrs = unoccr;
- }
- }
-
- if (npred_ok == 0 /* No load can be replaced by copy. */
- || (optimize_size && npred_ok > 1)) /* Prevent exploding the code. */
- goto cleanup;
-
- /* Check if it's worth applying the partial redundancy elimination. */
- if (ok_count < GCSE_AFTER_RELOAD_PARTIAL_FRACTION * not_ok_count)
- goto cleanup;
-
- if (ok_count < GCSE_AFTER_RELOAD_CRITICAL_FRACTION * critical_count)
- goto cleanup;
-
- /* Generate moves to the loaded register from where
- the memory is available. */
- for (occr = avail_occrs; occr; occr = occr->next)
- {
- avail_insn = occr->insn;
- pred = occr->pred;
- /* Set avail_reg to be the register having the value of the
- memory. */
- avail_reg = get_avail_load_store_reg (avail_insn);
- if (! avail_reg)
- abort ();
-
- insert_insn_on_edge (gen_move_insn (copy_rtx (dest),
- copy_rtx (avail_reg)),
- pred);
-
- if (gcse_file)
- fprintf (gcse_file,
- "GCSE AFTER reload generating move from %d to %d on \
- edge from %d to %d\n",
- REGNO (avail_reg),
- REGNO (dest),
- pred->src->index,
- pred->dest->index);
- }
-
- /* Regenerate loads where the memory is unavailable. */
- for (unoccr = unavail_occrs; unoccr; unoccr = unoccr->next)
- {
- pred = unoccr->pred;
- insert_insn_on_edge (copy_insn (PATTERN (insn)), pred);
-
- if (gcse_file)
- fprintf (gcse_file,
- "GCSE AFTER reload: generating on edge from %d to %d\
- a copy of load:\n",
- pred->src->index,
- pred->dest->index);
- }
-
- /* Delete the insn if it is not available in this block and mark it
- for deletion if it is available. If insn is available it may help
- discover additional redundancies, so mark it for later deletion.*/
- for (a_occr = get_bb_avail_insn (bb, expr->avail_occr);
- a_occr && (a_occr->insn != insn);
- a_occr = get_bb_avail_insn (bb, a_occr->next));
-
- if (!a_occr)
- delete_insn (insn);
- else
- a_occr->deleted_p = 1;
-
- cleanup:
-
- while (unavail_occrs)
- {
- struct unoccr *temp = unavail_occrs->next;
- free (unavail_occrs);
- unavail_occrs = temp;
- }
-
- while (avail_occrs)
- {
- struct unoccr *temp = avail_occrs->next;
- free (avail_occrs);
- avail_occrs = temp;
- }
- }
-
- /* Performing the redundancy elimination as described before. */
-
- static void
- gcse_after_reload (void)
- {
- unsigned int i;
- rtx insn;
- basic_block bb;
- struct expr *expr;
- struct occr *occr;
-
- /* Note we start at block 1. */
-
- if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
- return;
-
- FOR_BB_BETWEEN (bb,
- ENTRY_BLOCK_PTR->next_bb->next_bb,
- EXIT_BLOCK_PTR,
- next_bb)
- {
- if (! bb_has_well_behaved_predecessors (bb))
- continue;
-
- /* Do not try this optimization on cold basic blocks. */
- if (probably_cold_bb_p (bb))
- continue;
-
- reset_opr_set_tables ();
-
- for (insn = BB_HEAD (bb);
- insn != NULL
- && insn != NEXT_INSN (BB_END (bb));
- insn = NEXT_INSN (insn))
- {
- /* Is it a load - of the form (set (reg) (mem))? */
- if (NONJUMP_INSN_P (insn)
- && GET_CODE (PATTERN (insn)) == SET
- && REG_P (SET_DEST (PATTERN (insn)))
- && MEM_P (SET_SRC (PATTERN (insn))))
- {
- rtx pat = PATTERN (insn);
- rtx src = SET_SRC (pat);
- struct expr *expr;
-
- if (general_operand (src, GET_MODE (src))
- /* Is the expression recorded? */
- && (expr = lookup_expr (src, &expr_hash_table)) != NULL
- /* Are the operands unchanged since the start of the
- block? */
- && oprs_not_set_p (src, insn)
- && ! MEM_VOLATILE_P (src)
- && GET_MODE (src) != BLKmode
- && !(flag_non_call_exceptions && may_trap_p (src))
- && !side_effects_p (src))
- {
- /* We now have a load (insn) and an available memory at
- its BB start (expr). Try to remove the loads if it is
- redundant. */
- eliminate_partially_redundant_loads (bb, insn, expr);
- }
- }
-
- /* Keep track of everything modified by this insn. */
- if (INSN_P (insn))
- mark_oprs_set (insn);
- }
- }
-
- commit_edge_insertions ();
-
- /* Go over the expression hash table and delete insns that were
- marked for later deletion. */
- for (i = 0; i < expr_hash_table.size; i++)
- {
- for (expr = expr_hash_table.table[i];
- expr != NULL;
- expr = expr->next_same_hash)
- for (occr = expr->avail_occr; occr; occr = occr->next)
- if (occr->deleted_p)
- delete_insn (occr->insn);
- }
- }
-
- /* Scan pattern PAT of INSN and add an entry to the hash TABLE.
- After reload we are interested in loads/stores only. */
-
- static void
- hash_scan_set_after_reload (rtx pat, rtx insn, struct hash_table *table)
- {
- rtx src = SET_SRC (pat);
- rtx dest = SET_DEST (pat);
-
- if (! MEM_P (src) && ! MEM_P (dest))
- return;
-
- if (REG_P (dest))
- {
- if (/* Don't GCSE something if we can't do a reg/reg copy. */
- can_copy_p (GET_MODE (dest))
- /* GCSE commonly inserts instruction after the insn. We can't
- do that easily for EH_REGION notes so disable GCSE on these
- for now. */
- && ! find_reg_note (insn, REG_EH_REGION, NULL_RTX)
- /* Is SET_SRC something we want to gcse? */
- && general_operand (src, GET_MODE (src))
- /* Don't CSE a nop. */
- && ! set_noop_p (pat)
- && ! JUMP_P (insn))
- {
- /* An expression is not available if its operands are
- subsequently modified, including this insn. */
- if (oprs_available_p (src, insn))
- insert_expr_in_table (src, GET_MODE (dest), insn, 0, 1, table);
- }
- }
- else if (REG_P (src))
- {
- /* Only record sets of pseudo-regs in the hash table. */
- if (/* Don't GCSE something if we can't do a reg/reg copy. */
- can_copy_p (GET_MODE (src))
- /* GCSE commonly inserts instruction after the insn. We can't
- do that easily for EH_REGION notes so disable GCSE on these
- for now. */
- && ! find_reg_note (insn, REG_EH_REGION, NULL_RTX)
- /* Is SET_DEST something we want to gcse? */
- && general_operand (dest, GET_MODE (dest))
- /* Don't CSE a nop. */
- && ! set_noop_p (pat)
- &&! JUMP_P (insn)
- && ! (flag_float_store && FLOAT_MODE_P (GET_MODE (dest)))
- /* Check if the memory expression is killed after insn. */
- && ! load_killed_in_block_p (BLOCK_FOR_INSN (insn),
- INSN_CUID (insn) + 1,
- dest,
- 1)
- && oprs_unchanged_p (XEXP (dest, 0), insn, 1))
- {
- insert_expr_in_table (dest, GET_MODE (dest), insn, 0, 1, table);
- }
- }
- }
-
-
- /* Create hash table of memory expressions available at end of basic
- blocks. */
-
- static void
- compute_hash_table_after_reload (struct hash_table *table)
- {
- unsigned int i;
-
- table->set_p = 0;
-
- /* Initialize count of number of entries in hash table. */
- table->n_elems = 0;
- memset ((char *) table->table, 0,
- table->size * sizeof (struct expr *));
-
- /* While we compute the hash table we also compute a bit array of which
- registers are set in which blocks. */
- sbitmap_vector_zero (reg_set_in_block, last_basic_block);
-
- /* Re-cache any INSN_LIST nodes we have allocated. */
- clear_modify_mem_tables ();
-
- /* Some working arrays used to track first and last set in each block. */
- reg_avail_info = gmalloc (max_gcse_regno * sizeof (struct reg_avail_info));
-
- for (i = 0; i < max_gcse_regno; ++i)
- reg_avail_info[i].last_bb = NULL;
-
- FOR_EACH_BB (current_bb)
- {
- rtx insn;
- unsigned int regno;
-
- /* First pass over the instructions records information used to
- determine when registers and memory are first and last set. */
- for (insn = BB_HEAD (current_bb);
- insn && insn != NEXT_INSN (BB_END (current_bb));
- insn = NEXT_INSN (insn))
- {
- if (! INSN_P (insn))
- continue;
-
- if (CALL_P (insn))
- {
- bool clobbers_all = false;
-
- #ifdef NON_SAVING_SETJMP
- if (NON_SAVING_SETJMP
- && find_reg_note (insn, REG_SETJMP, NULL_RTX))
- clobbers_all = true;
- #endif
-
- for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
- if (clobbers_all
- || TEST_HARD_REG_BIT (regs_invalidated_by_call,
- regno))
- record_last_reg_set_info (insn, regno);
-
- mark_call (insn);
- }
-
- note_stores (PATTERN (insn), record_last_set_info, insn);
-
- if (GET_CODE (PATTERN (insn)) == SET)
- {
- rtx src, dest;
-
- src = SET_SRC (PATTERN (insn));
- dest = SET_DEST (PATTERN (insn));
- if (MEM_P (src) && auto_inc_p (XEXP (src, 0)))
- {
- regno = REGNO (XEXP (XEXP (src, 0), 0));
- record_last_reg_set_info (insn, regno);
- }
- if (MEM_P (dest) && auto_inc_p (XEXP (dest, 0)))
- {
- regno = REGNO (XEXP (XEXP (dest, 0), 0));
- record_last_reg_set_info (insn, regno);
- }
- }
- }
-
- /* The next pass builds the hash table. */
- for (insn = BB_HEAD (current_bb);
- insn && insn != NEXT_INSN (BB_END (current_bb));
- insn = NEXT_INSN (insn))
- if (INSN_P (insn) && GET_CODE (PATTERN (insn)) == SET)
- if (! find_reg_note (insn, REG_LIBCALL, NULL_RTX))
- hash_scan_set_after_reload (PATTERN (insn), insn, table);
- }
-
- free (reg_avail_info);
- reg_avail_info = NULL;
- }
-
-
- /* Main entry point of the GCSE after reload - clean some redundant loads
- due to spilling. */
-
- void
- gcse_after_reload_main (rtx f, FILE* file)
- {
- gcse_subst_count = 0;
- gcse_create_count = 0;
-
- gcse_file = file;
-
- gcc_obstack_init (&gcse_obstack);
- bytes_used = 0;
-
- /* We need alias. */
- init_alias_analysis ();
-
- max_gcse_regno = max_reg_num ();
-
- alloc_reg_set_mem (max_gcse_regno);
- alloc_gcse_mem (f);
- alloc_hash_table (max_cuid, &expr_hash_table, 0);
- compute_hash_table_after_reload (&expr_hash_table);
-
- if (gcse_file)
- dump_hash_table (gcse_file, "Expression", &expr_hash_table);
-
- if (expr_hash_table.n_elems > 0)
- gcse_after_reload ();
-
- free_hash_table (&expr_hash_table);
-
- free_gcse_mem ();
- free_reg_set_mem ();
-
- /* We are finished with alias. */
- end_alias_analysis ();
-
- obstack_free (&gcse_obstack, NULL);
- }
-
#include "gt-gcse.h"
--- 6587,6590 ----
Index: passes.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/passes.c,v
retrieving revision 2.36
diff -c -3 -p -r2.36 passes.c
*** passes.c 5 Aug 2004 05:51:50 -0000 2.36
--- passes.c 18 Aug 2004 17:51:30 -0000
*************** rest_of_handle_sched2 (void)
*** 839,848 ****
static void
rest_of_handle_gcse2 (void)
{
! timevar_push (TV_RELOAD_CSE_REGS);
open_dump_file (DFI_gcse2, current_function_decl);
! gcse_after_reload_main (get_insns (), dump_file);
rebuild_jump_labels (get_insns ());
delete_trivially_dead_insns (get_insns (), max_reg_num ());
close_dump_file (DFI_gcse2, print_rtl_with_bb, get_insns ());
--- 839,848 ----
static void
rest_of_handle_gcse2 (void)
{
! timevar_push (TV_GCSE_AFTER_RELOAD);
open_dump_file (DFI_gcse2, current_function_decl);
! gcse_after_reload_main (get_insns ());
rebuild_jump_labels (get_insns ());
delete_trivially_dead_insns (get_insns (), max_reg_num ());
close_dump_file (DFI_gcse2, print_rtl_with_bb, get_insns ());
*************** rest_of_handle_gcse2 (void)
*** 853,859 ****
verify_flow_info ();
#endif
! timevar_pop (TV_RELOAD_CSE_REGS);
}
/* Register allocation pre-pass, to reduce number of moves necessary
--- 853,859 ----
verify_flow_info ();
#endif
! timevar_pop (TV_GCSE_AFTER_RELOAD);
}
/* Register allocation pre-pass, to reduce number of moves necessary
Index: postreload-gcse.c
===================================================================
RCS file: postreload-gcse.c
diff -N postreload-gcse.c
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- postreload-gcse.c 18 Aug 2004 17:51:30 -0000
***************
*** 0 ****
--- 1,1379 ----
+ /* Post reload partially redundant load elimination
+ Copyright (C) 2004
+ Free Software Foundation, Inc.
+
+ This file is part of GCC.
+
+ GCC is free software; you can redistribute it and/or modify it under
+ the terms of the GNU General Public License as published by the Free
+ Software Foundation; either version 2, or (at your option) any later
+ version.
+
+ GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+ WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with GCC; see the file COPYING. If not, write to the Free
+ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+ 02111-1307, USA. */
+
+ #include "config.h"
+ #include "system.h"
+ #include "coretypes.h"
+ #include "tm.h"
+ #include "toplev.h"
+
+ #include "rtl.h"
+ #include "tree.h"
+ #include "tm_p.h"
+ #include "regs.h"
+ #include "hard-reg-set.h"
+ #include "flags.h"
+ #include "real.h"
+ #include "insn-config.h"
+ #include "recog.h"
+ #include "basic-block.h"
+ #include "output.h"
+ #include "function.h"
+ #include "expr.h"
+ #include "except.h"
+ #include "intl.h"
+ #include "obstack.h"
+ #include "hashtab.h"
+ #include "params.h"
+
+ /* The following code implements gcse after reload, the purpose of this
+ pass is to cleanup redundant loads generated by reload and other
+ optimizations that come after gcse. It searches for simple inter-block
+ redundancies and tries to eliminate them by adding moves and loads
+ in cold places.
+
+ Perform partially redundant load elimination, try to eliminate redundant
+ loads created by the reload pass. We try to look for full or partial
+ redundant loads fed by one or more loads/stores in predecessor BBs,
+ and try adding loads to make them fully redundant. We also check if
+ it's worth adding loads to be able to delete the redundant load.
+
+ Algorithm:
+ 1. Build available expressions hash table:
+ For each load/store instruction, if the loaded/stored memory didn't
+ change until the end of the basic block add this memory expression to
+ the hash table.
+ 2. Perform Redundancy elimination:
+ For each load instruction do the following:
+ perform partial redundancy elimination, check if it's worth adding
+ loads to make the load fully redundant. If so add loads and
+ register copies and delete the load.
+ 3. Delete instructions made redundant in step 2.
+
+ Future enhancement:
+ If the loaded register is used/defined between load and some store,
+ look for some other free register between load and all its stores,
+ and replace the load with a copy from this register to the loaded
+ register.
+ */
+
+
+ /* Keep statistics of this pass. */
+ static struct
+ {
+ int moves_inserted;
+ int copies_inserted;
+ int insns_deleted;
+ } stats;
+
+ /* We need to keep a hash table of expressions. The table entries are of
+ type 'struct expr', and for each expression there is a single linked
+ list of occurences. */
+
+ /* The table itself. */
+ static htab_t expr_table;
+
+ /* Expression elements in the hash table. */
+ struct expr
+ {
+ /* The expression (SET_SRC for expressions, PATTERN for assignments). */
+ rtx expr;
+
+ /* The same hash for this entry. */
+ hashval_t hash;
+
+ /* List of available occurrence in basic blocks in the function. */
+ struct occr *avail_occr;
+ };
+
+ static struct obstack expr_obstack;
+
+ /* Occurrence of an expression.
+ There is at most one occurence per basic block. If a pattern appears
+ more than once, the last appearance is used. */
+
+ struct occr
+ {
+ /* Next occurrence of this expression. */
+ struct occr *next;
+ /* The insn that computes the expression. */
+ rtx insn;
+ /* Nonzero if this [anticipatable] occurrence has been deleted. */
+ char deleted_p;
+ };
+
+ static struct obstack occr_obstack;
+
+ /* The following structure holds the information about the occurrences of
+ the redundant instructions. */
+ struct unoccr
+ {
+ struct unoccr *next;
+ edge pred;
+ rtx insn;
+ };
+
+ static struct obstack unoccr_obstack;
+
+ /* Array where each element is the CUID if the insn that last set the hard
+ register with the number of the element, since the start of the current
+ basic block. */
+ static int *reg_avail_info;
+
+ /* A list of insns that may modify memory within the current basic block. */
+ struct modifies_mem
+ {
+ rtx insn;
+ struct modifies_mem *next;
+ };
+ static struct modifies_mem *modifies_mem_list;
+
+ /* The modifies_mem structs also go on an obstack, only this obstack is
+ freed each time after completing the analysis or transformations on
+ a basic block. So we allocate a dummy modifies_mem_obstack_bottom
+ object on the obstack to keep track of the bottom of the obstack. */
+ static struct obstack modifies_mem_obstack;
+ static struct modifies_mem *modifies_mem_obstack_bottom;
+
+ /* Mapping of insn UIDs to CUIDs.
+ CUIDs are like UIDs except they increase monotonically in each basic
+ block, have no gaps, and only apply to real insns. */
+ static int *uid_cuid;
+ #define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
+
+
+ /* Helpers for memory allocation/freeing. */
+ static void alloc_mem (void);
+ static void free_mem (void);
+
+ /* Support for hash table construction and transformations. */
+ static bool oprs_unchanged_p (rtx, rtx, bool);
+ static void record_last_reg_set_info (rtx, int);
+ static void record_last_mem_set_info (rtx);
+ static void record_last_set_info (rtx, rtx, void *);
+ static void mark_call (rtx);
+ static void mark_set (rtx, rtx);
+ static void mark_clobber (rtx, rtx);
+ static void mark_oprs_set (rtx);
+
+ static void find_mem_conflicts (rtx, rtx, void *);
+ static int load_killed_in_block_p (int, rtx, bool);
+ static void reset_opr_set_tables (void);
+
+ /* Hash table support. */
+ static hashval_t hash_expr (rtx, int *);
+ static hashval_t hash_expr_for_htab (const void *);
+ static int expr_equiv_p (const void *, const void *);
+ static void insert_expr_in_table (rtx, rtx);
+ static struct expr *lookup_expr_in_table (rtx);
+ static int dump_hash_table_entry (void **, void *);
+ static void dump_hash_table (FILE *);
+
+ /* Helpers for eliminate_partially_redundant_load. */
+ static bool reg_killed_on_edge (rtx, edge);
+ static bool reg_used_on_edge (rtx, edge);
+
+ static rtx reg_set_between_after_reload_p (rtx, rtx, rtx);
+ static rtx reg_used_between_after_reload_p (rtx, rtx, rtx);
+ static rtx get_avail_load_store_reg (rtx);
+
+ static bool bb_has_well_behaved_predecessors (basic_block);
+ static struct occr* get_bb_avail_insn (basic_block, struct occr *);
+ static void hash_scan_set (rtx);
+ static void compute_hash_table (void);
+
+ /* The work horses of this pass. */
+ static void eliminate_partially_redundant_load (basic_block,
+ rtx,
+ struct expr *);
+ static void eliminate_partially_redundant_loads (void);
+
+
+ /* Allocate memory for the CUID mapping array and register/memory
+ tracking tables. */
+
+ static void
+ alloc_mem (void)
+ {
+ int i;
+ basic_block bb;
+ rtx insn;
+
+ /* Find the largest UID and create a mapping from UIDs to CUIDs. */
+ uid_cuid = xcalloc (get_max_uid () + 1, sizeof (int));
+ i = 0;
+ FOR_EACH_BB (bb)
+ FOR_BB_INSNS (bb, insn)
+ {
+ if (INSN_P (insn))
+ uid_cuid[INSN_UID (insn)] = i++;
+ else
+ uid_cuid[INSN_UID (insn)] = i;
+ }
+
+ /* Allocate the available expressions hash table. We don't want to
+ make the hash table too small, but unnecessarily making it too large
+ also doesn't help. The i/4 is a gcse.c relic, and seems like a
+ reasonable choice. */
+ expr_table = htab_create (MAX (i / 4, 13),
+ hash_expr_for_htab, expr_equiv_p, NULL);
+
+ /* We allocate everything on obstacks because we often can roll back
+ the whole obstack to some point. Freeing obstacks is very fast. */
+ gcc_obstack_init (&expr_obstack);
+ gcc_obstack_init (&occr_obstack);
+ gcc_obstack_init (&unoccr_obstack);
+ gcc_obstack_init (&modifies_mem_obstack);
+
+ /* Working array used to track the last set for each register
+ in the current block. */
+ reg_avail_info = (int *) xmalloc (FIRST_PSEUDO_REGISTER * sizeof (int));
+
+ /* Put a dummy modifies_mem object on the modifies_mem_obstack, so we
+ can roll it back in reset_opr_set_tables. */
+ modifies_mem_obstack_bottom =
+ (struct modifies_mem *) obstack_alloc (&modifies_mem_obstack,
+ sizeof (struct modifies_mem));
+ }
+
+ /* Free memory allocated by alloc_mem. */
+
+ static void
+ free_mem (void)
+ {
+ free (uid_cuid);
+
+ htab_delete (expr_table);
+
+ obstack_free (&expr_obstack, NULL);
+ obstack_free (&occr_obstack, NULL);
+ obstack_free (&unoccr_obstack, NULL);
+ obstack_free (&modifies_mem_obstack, NULL);
+
+ free (reg_avail_info);
+ }
+
+
+ /* Hash expression X.
+ DO_NOT_RECORD_P is a boolean indicating if a volatile operand is found
+ or if the expression contains something we don't want to insert in the
+ table. */
+
+ static hashval_t
+ hash_expr (rtx x, int *do_not_record_p)
+ {
+ *do_not_record_p = 0;
+ return hash_rtx (x, GET_MODE (x), do_not_record_p,
+ NULL, /*have_reg_qty=*/false);
+ }
+
+ /* Callback for hashtab.
+ Return the hash value for expression EXP. We don't actually hash
+ here, we just return the cached hash value. */
+
+ static hashval_t
+ hash_expr_for_htab (const void *expp)
+ {
+ struct expr *exp = (struct expr *) expp;
+ return exp->hash;
+ }
+
+ /* Callbach for hashtab.
+ Return nonzero if exp1 is equivalent to exp2. */
+
+ static int
+ expr_equiv_p (const void *exp1p, const void *exp2p)
+ {
+ struct expr *exp1 = (struct expr *) exp1p;
+ struct expr *exp2 = (struct expr *) exp2p;
+ int equiv_p = exp_equiv_p (exp1->expr, exp2->expr, 0, true);
+ if (equiv_p
+ && exp1->hash != exp2->hash)
+ abort ();
+ return equiv_p;
+ }
+
+
+ /* Insert expression X in INSN in the hash TABLE.
+ If it is already present, record it as the last occurrence in INSN's
+ basic block. */
+
+ static void
+ insert_expr_in_table (rtx x, rtx insn)
+ {
+ int do_not_record_p;
+ hashval_t hash;
+ struct expr *cur_expr, **slot;
+ struct occr *avail_occr, *last_occr = NULL;
+
+ hash = hash_expr (x, &do_not_record_p);
+
+ /* Do not insert expression in the table if it contains volatile operands,
+ or if hash_expr determines the expression is something we don't want
+ to or can't handle. */
+ if (do_not_record_p)
+ return;
+
+ /* We anticipate that redundant expressions are rare, so for convenience
+ allocate a new hash table element here already and set its fields.
+ If we don't do this, we need a hack with a static struct expr. Anyway,
+ obstack_free is really fast and one more obstack_alloc doesn't hurt if
+ we're going to see more expressions later on. */
+ cur_expr = (struct expr *) obstack_alloc (&expr_obstack,
+ sizeof (struct expr));
+ cur_expr->expr = x;
+ cur_expr->hash = hash;
+ cur_expr->avail_occr = NULL;
+
+ slot = (struct expr **) htab_find_slot_with_hash (expr_table, cur_expr,
+ hash, INSERT);
+
+ if (! (*slot))
+ /* The expression isn't found, so insert it. */
+ *slot = cur_expr;
+ else
+ {
+ /* The expression is already in the table, so roll back the
+ obstack and use the existing table entry. */
+ obstack_free (&expr_obstack, cur_expr);
+ cur_expr = *slot;
+ }
+
+ /* Search for another occurrence in the same basic block. */
+ avail_occr = cur_expr->avail_occr;
+ while (avail_occr && BLOCK_NUM (avail_occr->insn) != BLOCK_NUM (insn))
+ {
+ /* If an occurrence isn't found, save a pointer to the end of
+ the list. */
+ last_occr = avail_occr;
+ avail_occr = avail_occr->next;
+ }
+
+ if (avail_occr)
+ /* Found another instance of the expression in the same basic block.
+ Prefer this occurrence to the currently recorded one. We want
+ the last one in the block and the block is scanned from start
+ to end. */
+ avail_occr->insn = insn;
+ else
+ {
+ /* First occurrence of this expression in this basic block. */
+ avail_occr = (struct occr *) obstack_alloc (&occr_obstack,
+ sizeof (struct occr));
+
+ /* First occurrence of this expression in any block? */
+ if (cur_expr->avail_occr == NULL)
+ cur_expr->avail_occr = avail_occr;
+ else
+ last_occr->next = avail_occr;
+
+ avail_occr->insn = insn;
+ avail_occr->next = NULL;
+ avail_occr->deleted_p = 0;
+ }
+ }
+
+
+ /* Lookup pattern PAT in the expression hash table.
+ The result is a pointer to the table entry, or NULL if not found. */
+
+ static struct expr *
+ lookup_expr_in_table (rtx pat)
+ {
+ int do_not_record_p;
+ struct expr **slot, *tmp_expr;
+ hashval_t hash = hash_expr (pat, &do_not_record_p);
+
+ if (do_not_record_p)
+ return NULL;
+
+ tmp_expr = (struct expr *) obstack_alloc (&expr_obstack,
+ sizeof (struct expr));
+ tmp_expr->expr = pat;
+ tmp_expr->hash = hash;
+ tmp_expr->avail_occr = NULL;
+
+ slot = (struct expr **) htab_find_slot_with_hash (expr_table, tmp_expr,
+ hash, INSERT);
+ obstack_free (&expr_obstack, tmp_expr);
+
+ if (!slot)
+ return NULL;
+ else
+ return (*slot);
+ }
+
+
+ /* Dump all expressions and occurences that are currently in the
+ expression hash table to FILE. */
+
+ /* This helper is called via htab_traverse. */
+ static int
+ dump_hash_table_entry (void **slot, void *filep)
+ {
+ struct expr *expr = (struct expr *) *slot;
+ FILE *file = (FILE *) filep;
+ struct occr *occr;
+
+ fprintf (file, "expr: ");
+ print_rtl (file, expr->expr);
+ fprintf (file,"\nhashcode: %u\n", expr->hash);
+ fprintf (file,"list of occurences:\n");
+ occr = expr->avail_occr;
+ while (occr)
+ {
+ rtx insn = occr->insn;
+ print_rtl_single (file, insn);
+ fprintf (file, "\n");
+ occr = occr->next;
+ }
+ fprintf (file, "\n");
+ return 1;
+ }
+
+ static void
+ dump_hash_table (FILE *file)
+ {
+ fprintf (file, "\n\nexpression hash table\n");
+ fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
+ (long) htab_size (expr_table),
+ (long) htab_elements (expr_table),
+ htab_collisions (expr_table));
+ if (htab_elements (expr_table) > 0)
+ {
+ fprintf (file, "\n\ntable entries:\n");
+ htab_traverse (expr_table, dump_hash_table_entry, file);
+ }
+ fprintf (file, "\n");
+ }
+
+
+ /* Return nonzero if the operands of expression X are unchanged from the
+ start of INSN's basic block up to but not including INSN if AFTER_INSN
+ is false, or from INSN to the end of INSN's basic block if AFTER_INSN
+ is true. */
+
+ static bool
+ oprs_unchanged_p (rtx x, rtx insn, bool after_insn)
+ {
+ int i, j;
+ enum rtx_code code;
+ const char *fmt;
+
+ if (x == 0)
+ return 1;
+
+ code = GET_CODE (x);
+ switch (code)
+ {
+ case REG:
+ #ifdef ENABLE_CHECKING
+ /* We are called after register allocation. */
+ if (REGNO (x) >= FIRST_PSEUDO_REGISTER)
+ abort ();
+ #endif
+ if (after_insn)
+ /* If the last CUID setting the insn is less than the CUID of
+ INSN, then reg X is not changed in or after INSN. */
+ return reg_avail_info[REGNO (x)] < INSN_CUID (insn);
+ else
+ /* Reg X is not set before INSN in the current basic block if
+ we have not yet recorded the CUID of an insn that touches
+ the reg. */
+ return reg_avail_info[REGNO (x)] == 0;
+
+ case MEM:
+ if (load_killed_in_block_p (INSN_CUID (insn), x, after_insn))
+ return 0;
+ else
+ return oprs_unchanged_p (XEXP (x, 0), insn, after_insn);
+
+ case PC:
+ case CC0: /*FIXME*/
+ case CONST:
+ case CONST_INT:
+ case CONST_DOUBLE:
+ case CONST_VECTOR:
+ case SYMBOL_REF:
+ case LABEL_REF:
+ case ADDR_VEC:
+ case ADDR_DIFF_VEC:
+ return 1;
+
+ case PRE_DEC:
+ case PRE_INC:
+ case POST_DEC:
+ case POST_INC:
+ case PRE_MODIFY:
+ case POST_MODIFY:
+ if (after_insn)
+ return 0;
+ break;
+
+ default:
+ break;
+ }
+
+ for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
+ {
+ if (fmt[i] == 'e')
+ {
+ if (! oprs_unchanged_p (XEXP (x, i), insn, after_insn))
+ return 0;
+ }
+ else if (fmt[i] == 'E')
+ for (j = 0; j < XVECLEN (x, i); j++)
+ if (! oprs_unchanged_p (XVECEXP (x, i, j), insn, after_insn))
+ return 0;
+ }
+
+ return 1;
+ }
+
+
+ /* Used for communication between find_mem_conflicts and
+ load_killed_in_block_p. Nonzero if find_mem_conflicts finds a
+ conflict between two memory references.
+ This is a bit of a hack to work around the limitations of note_stores. */
+ static int mems_conflict_p;
+
+ /* DEST is the output of an instruction. If it is a memory reference, and
+ possibly conflicts with the load found in DATA, then set mems_conflict_p
+ to a nonzero value. */
+
+ static void
+ find_mem_conflicts (rtx dest, rtx setter ATTRIBUTE_UNUSED,
+ void *data)
+ {
+ rtx mem_op = (rtx) data;
+
+ while (GET_CODE (dest) == SUBREG
+ || GET_CODE (dest) == ZERO_EXTRACT
+ || GET_CODE (dest) == SIGN_EXTRACT
+ || GET_CODE (dest) == STRICT_LOW_PART)
+ dest = XEXP (dest, 0);
+
+ /* If DEST is not a MEM, then it will not conflict with the load. Note
+ that function calls are assumed to clobber memory, but are handled
+ elsewhere. */
+ if (! MEM_P (dest))
+ return;
+
+ if (true_dependence (dest, GET_MODE (dest), mem_op,
+ rtx_addr_varies_p))
+ mems_conflict_p = 1;
+ }
+
+
+ /* Return nonzero if the expression in X (a memory reference) is killed
+ in block BB before if (AFTER_INSN is false) or after (if AFTER_INSN
+ is true) the insn with the CUID in UID_LIMIT. */
+
+ static int
+ load_killed_in_block_p (int uid_limit, rtx x, bool after_insn)
+ {
+ struct modifies_mem *list_entry = modifies_mem_list;
+
+ while (list_entry)
+ {
+ rtx setter = list_entry->insn;
+
+ /* Ignore entries in the list that do not apply. */
+ if ((after_insn
+ && INSN_CUID (setter) < uid_limit)
+ || (! after_insn
+ && INSN_CUID (setter) > uid_limit))
+ {
+ list_entry = list_entry->next;
+ continue;
+ }
+
+ /* If SETTER is a call everything is clobbered. Note that calls
+ to pure functions are never put on the list, so we need not
+ worry about them. */
+ if (CALL_P (setter))
+ return 1;
+
+ /* SETTER must be an insn of some kind that sets memory. Call
+ note_stores to examine each hunk of memory that is modified.
+ It will set mems_conflict_p to nonzero if there may be a
+ conflict between X and SETTER. */
+ mems_conflict_p = 0;
+ note_stores (PATTERN (setter), find_mem_conflicts, x);
+ if (mems_conflict_p)
+ return 1;
+
+ list_entry = list_entry->next;
+ }
+ return 0;
+ }
+
+
+ /* Record register first/last/block set information for REGNO in INSN. */
+
+ static void
+ record_last_reg_set_info (rtx insn, int regno)
+ {
+ reg_avail_info[regno] = INSN_CUID (insn);
+ }
+
+
+ /* Record memory modification information for INSN. We do not actually care
+ about the memory location(s) that are set, or even how they are set (consider
+ a CALL_INSN). We merely need to record which insns modify memory. */
+
+ static void
+ record_last_mem_set_info (rtx insn)
+ {
+ struct modifies_mem *list_entry;
+
+ list_entry = (struct modifies_mem *) obstack_alloc (&modifies_mem_obstack,
+ sizeof (struct modifies_mem));
+ list_entry->insn = insn;
+ list_entry->next = modifies_mem_list;
+ modifies_mem_list = list_entry;
+ }
+
+ /* Called from compute_hash_table via note_stores to handle one
+ SET or CLOBBER in an insn. DATA is really the instruction in which
+ the SET is taking place. */
+
+ static void
+ record_last_set_info (rtx dest, rtx setter ATTRIBUTE_UNUSED, void *data)
+ {
+ rtx last_set_insn = (rtx) data;
+
+ if (GET_CODE (dest) == SUBREG)
+ dest = SUBREG_REG (dest);
+
+ if (REG_P (dest))
+ record_last_reg_set_info (last_set_insn, REGNO (dest));
+ else if (MEM_P (dest)
+ /* Ignore pushes, they clobber nothing. */
+ && ! push_operand (dest, GET_MODE (dest)))
+ record_last_mem_set_info (last_set_insn);
+ }
+
+
+ /* Reset tables used to keep track of what's still available since the
+ start of the block. */
+
+ static void
+ reset_opr_set_tables (void)
+ {
+ memset (reg_avail_info, 0, FIRST_PSEUDO_REGISTER * sizeof (int));
+ obstack_free (&modifies_mem_obstack, modifies_mem_obstack_bottom);
+ modifies_mem_list = NULL;
+ }
+
+ /* Mark things set by a CALL. */
+
+ static void
+ mark_call (rtx insn)
+ {
+ if (! CONST_OR_PURE_CALL_P (insn))
+ record_last_mem_set_info (insn);
+ }
+
+ /* Mark things set by a SET. */
+
+ static void
+ mark_set (rtx pat, rtx insn)
+ {
+ rtx dest = SET_DEST (pat);
+
+ while (GET_CODE (dest) == SUBREG
+ || GET_CODE (dest) == ZERO_EXTRACT
+ || GET_CODE (dest) == SIGN_EXTRACT
+ || GET_CODE (dest) == STRICT_LOW_PART)
+ dest = XEXP (dest, 0);
+
+ if (REG_P (dest))
+ record_last_reg_set_info (insn, REGNO (dest));
+ else if (MEM_P (dest))
+ record_last_mem_set_info (insn);
+
+ if (GET_CODE (SET_SRC (pat)) == CALL)
+ mark_call (insn);
+ }
+
+ /* Record things set by a CLOBBER. */
+
+ static void
+ mark_clobber (rtx pat, rtx insn)
+ {
+ rtx clob = XEXP (pat, 0);
+
+ while (GET_CODE (clob) == SUBREG
+ || GET_CODE (clob) == STRICT_LOW_PART)
+ clob = XEXP (clob, 0);
+
+ if (REG_P (clob))
+ record_last_reg_set_info (insn, REGNO (clob));
+ else
+ record_last_mem_set_info (insn);
+ }
+
+ /* Record things set by INSN.
+ This data is used by oprs_unchanged_p. */
+
+ static void
+ mark_oprs_set (rtx insn)
+ {
+ rtx pat = PATTERN (insn);
+ int i;
+
+ if (GET_CODE (pat) == SET)
+ mark_set (pat, insn);
+
+ else if (GET_CODE (pat) == PARALLEL)
+ for (i = 0; i < XVECLEN (pat, 0); i++)
+ {
+ rtx x = XVECEXP (pat, 0, i);
+
+ if (GET_CODE (x) == SET)
+ mark_set (x, insn);
+ else if (GET_CODE (x) == CLOBBER)
+ mark_clobber (x, insn);
+ else if (GET_CODE (x) == CALL)
+ mark_call (insn);
+ }
+
+ else if (GET_CODE (pat) == CLOBBER)
+ mark_clobber (pat, insn);
+
+ else if (GET_CODE (pat) == CALL)
+ mark_call (insn);
+ }
+
+
+ /* Scan the pattern of INSN and add an entry to the hash TABLE.
+ After reload we are interested in loads/stores only. */
+
+ static void
+ hash_scan_set (rtx insn)
+ {
+ rtx pat = PATTERN (insn);
+ rtx src = SET_SRC (pat);
+ rtx dest = SET_DEST (pat);
+
+ /* We are only interested in loads and stores. */
+ if (! MEM_P (src) && ! MEM_P (dest))
+ return;
+
+ /* Don't mess with jumps and nops. */
+ if (JUMP_P (insn) || set_noop_p (pat))
+ return;
+
+ #ifdef ENABLE_CHEKCING
+ /* We shouldn't have any EH_REGION notes post reload. */
+ if (find_reg_note (insn, REG_EH_REGION, NULL_RTX))
+ abort ();
+ #endif
+
+ if (REG_P (dest))
+ {
+ if (/* Don't GCSE something if we can't do a reg/reg copy. */
+ can_copy_p (GET_MODE (dest))
+ /* Is SET_SRC something we want to gcse? */
+ && general_operand (src, GET_MODE (src))
+ /* An expression is not available if its operands are
+ subsequently modified, including this insn. */
+ && oprs_unchanged_p (src, insn, true))
+ {
+ insert_expr_in_table (src, insn);
+ }
+ }
+ else if (REG_P (src))
+ {
+ /* Only record sets of pseudo-regs in the hash table. */
+ if (/* Don't GCSE something if we can't do a reg/reg copy. */
+ can_copy_p (GET_MODE (src))
+ /* Is SET_DEST something we want to gcse? */
+ && general_operand (dest, GET_MODE (dest))
+ && ! (flag_float_store && FLOAT_MODE_P (GET_MODE (dest)))
+ /* Check if the memory expression is killed after insn. */
+ && ! load_killed_in_block_p (INSN_CUID (insn) + 1, dest, true)
+ && oprs_unchanged_p (XEXP (dest, 0), insn, true))
+ {
+ insert_expr_in_table (dest, insn);
+ }
+ }
+ }
+
+ /* Create hash table of memory expressions available at end of basic
+ blocks. */
+
+ static void
+ compute_hash_table (void)
+ {
+ basic_block bb;
+
+ FOR_EACH_BB (bb)
+ {
+ rtx insn;
+ unsigned int regno;
+
+ reset_opr_set_tables ();
+
+ /* First pass over the instructions records information used to
+ determine when registers and memory are first and last set. */
+ FOR_BB_INSNS (bb, insn)
+ {
+ if (! INSN_P (insn))
+ continue;
+
+ if (CALL_P (insn))
+ {
+ bool clobbers_all = false;
+
+ #ifdef NON_SAVING_SETJMP
+ if (NON_SAVING_SETJMP
+ && find_reg_note (insn, REG_SETJMP, NULL_RTX))
+ clobbers_all = true;
+ #endif
+
+ for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
+ if (clobbers_all
+ || TEST_HARD_REG_BIT (regs_invalidated_by_call,
+ regno))
+ record_last_reg_set_info (insn, regno);
+
+ if (! CONST_OR_PURE_CALL_P (insn))
+ record_last_mem_set_info (insn);
+ }
+
+ note_stores (PATTERN (insn), record_last_set_info, insn);
+
+ if (GET_CODE (PATTERN (insn)) == SET)
+ {
+ rtx src, dest;
+
+ src = SET_SRC (PATTERN (insn));
+ dest = SET_DEST (PATTERN (insn));
+ if (MEM_P (src) && auto_inc_p (XEXP (src, 0)))
+ {
+ regno = REGNO (XEXP (XEXP (src, 0), 0));
+ record_last_reg_set_info (insn, regno);
+ }
+ if (MEM_P (dest) && auto_inc_p (XEXP (dest, 0)))
+ {
+ regno = REGNO (XEXP (XEXP (dest, 0), 0));
+ record_last_reg_set_info (insn, regno);
+ }
+ }
+ }
+
+ /* The next pass builds the hash table. */
+ FOR_BB_INSNS (bb, insn)
+ if (INSN_P (insn) && GET_CODE (PATTERN (insn)) == SET)
+ hash_scan_set (insn);
+ }
+ }
+
+
+ /* Check if register REG is killed in any insn waiting to be inserted on
+ edge E. This function is required to check that our data flow analysis
+ is still valid prior to commit_edge_insertions. */
+
+ static bool
+ reg_killed_on_edge (rtx reg, edge e)
+ {
+ rtx insn;
+
+ for (insn = e->insns.r; insn; insn = NEXT_INSN (insn))
+ if (INSN_P (insn) && reg_set_p (reg, insn))
+ return true;
+
+ return false;
+ }
+
+ /* Similar to above - check if register REG is used in any insn waiting
+ to be inserted on edge E.
+ Assumes no such insn can be a CALL_INSN; if so call reg_used_between_p
+ with PREV(insn),NEXT(insn) instead of calling reg_overlap_mentioned_p. */
+
+ static bool
+ reg_used_on_edge (rtx reg, edge e)
+ {
+ rtx insn;
+
+ for (insn = e->insns.r; insn; insn = NEXT_INSN (insn))
+ if (INSN_P (insn) && reg_overlap_mentioned_p (reg, PATTERN (insn)))
+ return true;
+
+ return false;
+ }
+
+
+ /* Return the insn that sets register REG or clobbers it in between
+ FROM_INSN and TO_INSN (exclusive of those two).
+ Just like reg_set_between but for hard registers and not pseudos. */
+
+ static rtx
+ reg_set_between_after_reload_p (rtx reg, rtx from_insn, rtx to_insn)
+ {
+ rtx insn;
+ int regno;
+
+ #ifdef ENABLE_CHECKING
+ /* We are called after register allocation. */
+ if (!REG_P (reg) || REGNO (reg) >= FIRST_PSEUDO_REGISTER)
+ abort ();
+ #endif
+
+ if (from_insn == to_insn)
+ return NULL_RTX;
+
+ regno = REGNO (reg);
+ for (insn = NEXT_INSN (from_insn);
+ insn != to_insn;
+ insn = NEXT_INSN (insn))
+ {
+ if (INSN_P (insn))
+ {
+ if (FIND_REG_INC_NOTE (insn, reg)
+ || (CALL_P (insn)
+ && call_used_regs[regno])
+ || find_reg_fusage (insn, CLOBBER, reg))
+ return insn;
+ }
+ if (set_of (reg, insn) != NULL_RTX)
+ return insn;
+ }
+
+ return NULL_RTX;
+ }
+
+ /* Return the insn that uses register REG in between FROM_INSN and TO_INSN
+ (exclusive of those two). Similar to reg_used_between but for hard
+ registers and not pseudos. */
+
+ static rtx
+ reg_used_between_after_reload_p (rtx reg, rtx from_insn, rtx to_insn)
+ {
+ rtx insn;
+ int regno;
+
+ #ifdef ENABLE_CHECKING
+ /* We are called after register allocation. */
+ if (!REG_P (reg) || REGNO (reg) >= FIRST_PSEUDO_REGISTER)
+ abort ();
+ #endif
+
+ if (from_insn == to_insn)
+ return NULL_RTX;
+
+ regno = REGNO (reg);
+ for (insn = NEXT_INSN (from_insn);
+ insn != to_insn;
+ insn = NEXT_INSN (insn))
+ if (INSN_P (insn)
+ && (reg_overlap_mentioned_p (reg, PATTERN (insn))
+ || (CALL_P (insn)
+ && call_used_regs[regno])
+ || find_reg_fusage (insn, USE, reg)
+ || find_reg_fusage (insn, CLOBBER, reg)))
+ return insn;
+
+ return NULL_RTX;
+ }
+
+ /* Return true if REG is used, set, or killed between the beginning of
+ basic block BB and UP_TO_INSN. Caches the result in reg_avail_info. */
+
+ static bool
+ reg_set_or_used_since_bb_start (rtx reg, basic_block bb, rtx up_to_insn)
+ {
+ rtx insn, start = PREV_INSN (BB_HEAD (bb));
+
+ if (reg_avail_info[REGNO (reg)] != 0)
+ return true;
+
+ insn = reg_used_between_after_reload_p (reg, start, up_to_insn);
+ if (! insn)
+ insn = reg_set_between_after_reload_p (reg, start, up_to_insn);
+
+ if (insn)
+ reg_avail_info[REGNO (reg)] = INSN_CUID (insn);
+
+ return insn != NULL_RTX;
+ }
+
+ /* Return the loaded/stored register of a load/store instruction. */
+
+ static rtx
+ get_avail_load_store_reg (rtx insn)
+ {
+ if (REG_P (SET_DEST (PATTERN (insn)))) /* A load. */
+ return SET_DEST(PATTERN(insn));
+ if (REG_P (SET_SRC (PATTERN (insn)))) /* A store. */
+ return SET_SRC (PATTERN (insn));
+ abort ();
+ }
+
+ /* Return nonzero if the predecessors of BB are "well behaved". */
+
+ static bool
+ bb_has_well_behaved_predecessors (basic_block bb)
+ {
+ edge pred;
+
+ if (! bb->pred)
+ return false;
+
+ for (pred = bb->pred; pred != NULL; pred = pred->pred_next)
+ {
+ if ((pred->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (pred))
+ return false;
+
+ if (JUMP_TABLE_DATA_P (BB_END (pred->src)))
+ return false;
+ }
+ return true;
+ }
+
+
+ /* Search for the occurrences of expression in BB. */
+
+ static struct occr*
+ get_bb_avail_insn (basic_block bb, struct occr *occr)
+ {
+ for (; occr != NULL; occr = occr->next)
+ if (BLOCK_FOR_INSN (occr->insn) == bb)
+ return occr;
+ return NULL;
+ }
+
+
+ /* This handles the case where several stores feed a partially redundant
+ load. It checks if the redundancy elimination is possible and if it's
+ worth it. */
+
+ static void
+ eliminate_partially_redundant_load (basic_block bb, rtx insn,
+ struct expr *expr)
+ {
+ edge pred;
+ rtx avail_insn = NULL_RTX;
+ rtx avail_reg;
+ rtx dest, pat;
+ struct occr *a_occr;
+ struct unoccr *occr, *avail_occrs = NULL;
+ struct unoccr *unoccr, *unavail_occrs = NULL, *rollback_unoccr = NULL;
+ int npred_ok = 0;
+ gcov_type ok_count = 0; /* Redundant load execution count. */
+ gcov_type critical_count = 0; /* Execution count of critical edges. */
+
+ /* The execution count of the loads to be added to make the
+ load fully redundant. */
+ gcov_type not_ok_count = 0;
+ basic_block pred_bb;
+
+ pat = PATTERN (insn);
+ dest = SET_DEST (pat);
+
+ /* Check that the loaded register is not used, set, or killed from the
+ beginning of the block. */
+ if (reg_set_or_used_since_bb_start (dest, bb, insn))
+ return;
+
+ /* Check potential for replacing load with copy for predecessors. */
+ for (pred = bb->pred; pred; pred = pred->pred_next)
+ {
+ rtx next_pred_bb_end;
+
+ avail_insn = NULL_RTX;
+ pred_bb = pred->src;
+ next_pred_bb_end = NEXT_INSN (BB_END (pred_bb));
+ for (a_occr = get_bb_avail_insn (pred_bb, expr->avail_occr); a_occr;
+ a_occr = get_bb_avail_insn (pred_bb, a_occr->next))
+ {
+ /* Check if the loaded register is not used. */
+ avail_insn = a_occr->insn;
+ if (! (avail_reg = get_avail_load_store_reg (avail_insn)))
+ abort ();
+ /* Make sure we can generate a move from register avail_reg to
+ dest. */
+ extract_insn (gen_move_insn (copy_rtx (dest),
+ copy_rtx (avail_reg)));
+ if (! constrain_operands (1)
+ || reg_killed_on_edge (avail_reg, pred)
+ || reg_used_on_edge (dest, pred))
+ {
+ avail_insn = NULL;
+ continue;
+ }
+ if (! reg_set_between_after_reload_p (avail_reg, avail_insn,
+ next_pred_bb_end))
+ /* AVAIL_INSN remains non-null. */
+ break;
+ else
+ avail_insn = NULL;
+ }
+
+ if (EDGE_CRITICAL_P (pred))
+ critical_count += pred->count;
+
+ if (avail_insn != NULL_RTX)
+ {
+ npred_ok++;
+ ok_count += pred->count;
+ occr = (struct unoccr *) obstack_alloc (&unoccr_obstack,
+ sizeof (struct occr));
+ occr->insn = avail_insn;
+ occr->pred = pred;
+ occr->next = avail_occrs;
+ avail_occrs = occr;
+ if (! rollback_unoccr)
+ rollback_unoccr = occr;
+ }
+ else
+ {
+ not_ok_count += pred->count;
+ unoccr = (struct unoccr *) obstack_alloc (&unoccr_obstack,
+ sizeof (struct unoccr));
+ unoccr->insn = NULL_RTX;
+ unoccr->pred = pred;
+ unoccr->next = unavail_occrs;
+ unavail_occrs = unoccr;
+ if (! rollback_unoccr)
+ rollback_unoccr = unoccr;
+ }
+ }
+
+ if (/* No load can be replaced by copy. */
+ npred_ok == 0
+ /* Prevent exploding the code. */
+ || (optimize_size && npred_ok > 1))
+ goto cleanup;
+
+ /* Check if it's worth applying the partial redundancy elimination. */
+ if (ok_count < GCSE_AFTER_RELOAD_PARTIAL_FRACTION * not_ok_count)
+ goto cleanup;
+ if (ok_count < GCSE_AFTER_RELOAD_CRITICAL_FRACTION * critical_count)
+ goto cleanup;
+
+ /* Generate moves to the loaded register from where
+ the memory is available. */
+ for (occr = avail_occrs; occr; occr = occr->next)
+ {
+ avail_insn = occr->insn;
+ pred = occr->pred;
+ /* Set avail_reg to be the register having the value of the
+ memory. */
+ avail_reg = get_avail_load_store_reg (avail_insn);
+ if (! avail_reg)
+ abort ();
+
+ insert_insn_on_edge (gen_move_insn (copy_rtx (dest),
+ copy_rtx (avail_reg)),
+ pred);
+ stats.moves_inserted++;
+
+ if (dump_file)
+ fprintf (dump_file,
+ "generating move from %d to %d on edge from %d to %d\n",
+ REGNO (avail_reg),
+ REGNO (dest),
+ pred->src->index,
+ pred->dest->index);
+ }
+
+ /* Regenerate loads where the memory is unavailable. */
+ for (unoccr = unavail_occrs; unoccr; unoccr = unoccr->next)
+ {
+ pred = unoccr->pred;
+ insert_insn_on_edge (copy_insn (PATTERN (insn)), pred);
+ stats.copies_inserted++;
+
+ if (dump_file)
+ {
+ fprintf (dump_file,
+ "generating on edge from %d to %d a copy of load: ",
+ pred->src->index,
+ pred->dest->index);
+ print_rtl (dump_file, PATTERN (insn));
+ fprintf (dump_file, "\n");
+ }
+ }
+
+ /* Delete the insn if it is not available in this block and mark it
+ for deletion if it is available. If insn is available it may help
+ discover additional redundancies, so mark it for later deletion. */
+ for (a_occr = get_bb_avail_insn (bb, expr->avail_occr);
+ a_occr && (a_occr->insn != insn);
+ a_occr = get_bb_avail_insn (bb, a_occr->next));
+
+ if (!a_occr)
+ delete_insn (insn);
+ else
+ a_occr->deleted_p = 1;
+
+ cleanup:
+ if (rollback_unoccr)
+ obstack_free (&unoccr_obstack, rollback_unoccr);
+ }
+
+ /* Performing the redundancy elimination as described before. */
+
+ static void
+ eliminate_partially_redundant_loads (void)
+ {
+ rtx insn;
+ basic_block bb;
+
+ /* Note we start at block 1. */
+
+ if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
+ return;
+
+ FOR_BB_BETWEEN (bb,
+ ENTRY_BLOCK_PTR->next_bb->next_bb,
+ EXIT_BLOCK_PTR,
+ next_bb)
+ {
+ if (! bb_has_well_behaved_predecessors (bb))
+ continue;
+
+ /* Do not try this optimization on cold basic blocks. */
+ if (probably_cold_bb_p (bb))
+ continue;
+
+ reset_opr_set_tables ();
+
+ FOR_BB_INSNS (bb, insn)
+ {
+ /* Is it a load - of the form (set (reg) (mem))? */
+ if (NONJUMP_INSN_P (insn)
+ && GET_CODE (PATTERN (insn)) == SET
+ && REG_P (SET_DEST (PATTERN (insn)))
+ && MEM_P (SET_SRC (PATTERN (insn))))
+ {
+ rtx pat = PATTERN (insn);
+ rtx src = SET_SRC (pat);
+ struct expr *expr;
+
+ if (!MEM_VOLATILE_P (src)
+ && GET_MODE (src) != BLKmode
+ && general_operand (src, GET_MODE (src))
+ /* Are the operands unchanged since the start of the
+ block? */
+ && oprs_unchanged_p (src, insn, false)
+ && !(flag_non_call_exceptions && may_trap_p (src))
+ && !side_effects_p (src)
+ /* Is the expression recorded? */
+ && (expr = lookup_expr_in_table (src)) != NULL)
+ {
+ /* We now have a load (insn) and an available memory at
+ its BB start (expr). Try to remove the loads if it is
+ redundant. */
+ eliminate_partially_redundant_load (bb, insn, expr);
+ }
+ }
+
+ /* Keep track of everything modified by this insn. */
+ if (INSN_P (insn))
+ mark_oprs_set (insn);
+ }
+ }
+
+ commit_edge_insertions ();
+ }
+
+ /* Go over the expression hash table and delete insns that were
+ marked for later deletion. */
+
+ /* This helper is called via htab_traverse. */
+ static int
+ delete_redundant_insns_1 (void **slot, void *data ATTRIBUTE_UNUSED)
+ {
+ struct expr *expr = (struct expr *) *slot;
+ struct occr *occr;
+
+ for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
+ {
+ if (occr->deleted_p)
+ {
+ delete_insn (occr->insn);
+ stats.insns_deleted++;
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "deleting insn:\n");
+ print_rtl_single (dump_file, occr->insn);
+ fprintf (dump_file, "\n");
+ }
+ }
+ }
+
+ return 1;
+ }
+
+ static void
+ delete_redundant_insns (void)
+ {
+ htab_traverse (expr_table, delete_redundant_insns_1, NULL);
+ if (dump_file)
+ fprintf (dump_file, "\n");
+ }
+
+ /* Main entry point of the GCSE after reload - clean some redundant loads
+ due to spilling. */
+
+ void
+ gcse_after_reload_main (rtx f ATTRIBUTE_UNUSED)
+ {
+ memset (&stats, 0, sizeof (stats));
+
+ /* Allocate ememory for this pass.
+ Also computes and initializes the insns' CUIDs. */
+ alloc_mem ();
+
+ /* We need alias analysis. */
+ init_alias_analysis ();
+
+ compute_hash_table ();
+
+ if (dump_file)
+ dump_hash_table (dump_file);
+
+ if (htab_elements (expr_table) > 0)
+ {
+ eliminate_partially_redundant_loads ();
+ delete_redundant_insns ();
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "GCSE AFTER RELOAD stats:\n");
+ fprintf (dump_file, "copies inserted: %d\n", stats.copies_inserted);
+ fprintf (dump_file, "moves inserted: %d\n", stats.moves_inserted);
+ fprintf (dump_file, "insns deleted: %d\n", stats.insns_deleted);
+ fprintf (dump_file, "\n\n");
+ }
+ }
+
+ /* We are finished with alias. */
+ end_alias_analysis ();
+
+ free_mem ();
+ }
+
Index: rtl.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/rtl.h,v
retrieving revision 1.502
diff -c -3 -p -r1.502 rtl.h
*** rtl.h 18 Aug 2004 08:24:11 -0000 1.502
--- rtl.h 18 Aug 2004 17:51:31 -0000
*************** extern int rtx_to_tree_code (enum rtx_co
*** 2119,2124 ****
--- 2119,2126 ----
extern int delete_trivially_dead_insns (rtx, int);
extern int cse_main (rtx, int, int, FILE *);
extern void cse_condition_code_reg (void);
+ extern int exp_equiv_p (rtx, rtx, int, bool);
+ extern unsigned hash_rtx (rtx x, enum machine_mode, int *, int *, bool);
/* In jump.c */
extern int comparison_dominates_p (enum rtx_code, enum rtx_code);
*************** extern bool can_copy_p (enum machine_mod
*** 2265,2271 ****
extern rtx fis_get_condition (rtx);
extern int gcse_main (rtx, FILE *);
extern int bypass_jumps (FILE *);
! extern void gcse_after_reload_main (rtx, FILE *);
/* In global.c */
extern void mark_elimination (int, int);
--- 2267,2275 ----
extern rtx fis_get_condition (rtx);
extern int gcse_main (rtx, FILE *);
extern int bypass_jumps (FILE *);
!
! /* In postreload-gcse.c */
! extern void gcse_after_reload_main (rtx);
/* In global.c */
extern void mark_elimination (int, int);
Index: timevar.def
===================================================================
RCS file: /cvs/gcc/gcc/gcc/timevar.def,v
retrieving revision 1.32
diff -c -3 -p -r1.32 timevar.def
*** timevar.def 17 Aug 2004 16:17:03 -0000 1.32
--- timevar.def 18 Aug 2004 17:51:31 -0000
*************** DEFTIMEVAR (TV_SCHED , "
*** 122,127 ****
--- 122,128 ----
DEFTIMEVAR (TV_LOCAL_ALLOC , "local alloc")
DEFTIMEVAR (TV_GLOBAL_ALLOC , "global alloc")
DEFTIMEVAR (TV_RELOAD_CSE_REGS , "reload CSE regs")
+ DEFTIMEVAR (TV_GCSE_AFTER_RELOAD , "load CSE after reload")
DEFTIMEVAR (TV_FLOW2 , "flow 2")
DEFTIMEVAR (TV_IFCVT2 , "if-conversion 2")
DEFTIMEVAR (TV_PEEPHOLE2 , "peephole 2")