PATCH: Share all CONST_INTs
Mark Mitchell
mark@codesourcery.com
Fri Mar 31 01:03:00 GMT 2000
I've been analyzing the absurd memory usage in CSE I discussed
previously. (As noted, there is second fault which triggered this
investigation: the overzealousness of builtin expansion made the CSE
behavior appear even in the relatively simple init_obstacks function
in gcc/tree.c.)
Of the 250MB used during CSE, some 60MB is eliminated by this patch,
which causes us to share all CONST_INTs, not just those with absolute
value less than 64. This is a win in time as well: finding the
CONST_INTs in the hash table takes no more time (empirically measured)
than creating new ones, plus we save the overhead of collecting them
later, plus we reduce the frequency of collection. So, this trims the
peak memory usage from 250MB to 192MB, and the compilation time from
80s to 74s, even on my 512MB machine (meaning that swapping is not
really a factor).
A side-effect is that comparisons (like that in rtx_equal_p) get a
little faster for CONST_INTs: pointer equality is now value equality
as well.
I've got more patches coming to further reduce the CSE memory usage;
stay tuned. :-)
--
Mark Mitchell mark@codesourcery.com
CodeSourcery, LLC http://www.codesourcery.com
2000-03-30 Mark Mitchell <mark@codesourcery.com>
* Makefile.in (emit-rtl.o): Depend on HASHTAB_H.
* alias.c (reg_known_value): Add comments.
(init_alias_analysis): Likewise.
* cse.c (exp_equiv_p): CONST_INTs are equal iff they have the same
address.
(cse_basic_block): Fix typo in comment.
* emit-rtl.c: Include hashtab.h.
(const_int_htab): New variable.
(const_int_htab_hash): New function.
(const_int_htab_eq): Likewise.
(rtx_htab_mark_1): Likewise.
(rtx_htab_mark): Likewise.
(gen_rtx_CONST_INT): Cache all CONST_INTs.
(unshare_all_rtx): Fix formatting.
(init_emit_once): Initialize const_int_htab.
* rtl.c (rtx_equal_p): CONST_INTs are equal iff they have the same
address.
* rtl.texi: Document the fact that all CONST_INTs with the same
value are shared.
Index: gcc/Makefile.in
===================================================================
RCS file: /cvs/gcc/egcs/gcc/Makefile.in,v
retrieving revision 1.407
diff -c -p -r1.407 Makefile.in
*** Makefile.in 2000/03/23 00:20:37 1.407
--- Makefile.in 2000/03/31 07:00:08
*************** xcoffout.o : xcoffout.c $(CONFIG_H) syst
*** 1546,1552 ****
flags.h toplev.h output.h dbxout.h ggc.h
emit-rtl.o : emit-rtl.c $(CONFIG_H) system.h $(RTL_H) $(TREE_H) flags.h \
function.h $(REGS_H) insn-config.h $(RECOG_H) real.h ggc.h \
! $(EXPR_H) $(srcdir)/../include/obstack.h hard-reg-set.h bitmap.h toplev.h
real.o : real.c $(CONFIG_H) system.h $(TREE_H) toplev.h
integrate.o : integrate.c $(CONFIG_H) system.h $(RTL_H) $(TREE_H) flags.h \
$(INTEGRATE_H) insn-flags.h insn-config.h $(EXPR_H) real.h $(REGS_H) \
--- 1546,1553 ----
flags.h toplev.h output.h dbxout.h ggc.h
emit-rtl.o : emit-rtl.c $(CONFIG_H) system.h $(RTL_H) $(TREE_H) flags.h \
function.h $(REGS_H) insn-config.h $(RECOG_H) real.h ggc.h \
! $(EXPR_H) $(srcdir)/../include/obstack.h hard-reg-set.h bitmap.h toplev.h \
! $(HASHTAB_H)
real.o : real.c $(CONFIG_H) system.h $(TREE_H) toplev.h
integrate.o : integrate.c $(CONFIG_H) system.h $(RTL_H) $(TREE_H) flags.h \
$(INTEGRATE_H) insn-flags.h insn-config.h $(EXPR_H) real.h $(REGS_H) \
Index: gcc/alias.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/alias.c,v
retrieving revision 1.73
diff -c -p -r1.73 alias.c
*** alias.c 2000/03/25 18:34:00 1.73
--- alias.c 2000/03/31 07:00:10
*************** static unsigned int reg_base_value_size;
*** 153,160 ****
after reload. */
static rtx *alias_invariant;
! /* Vector indexed by N giving the initial (unchanging) value known
! for pseudo-register N. */
rtx *reg_known_value;
/* Indicates number of valid entries in reg_known_value. */
--- 153,162 ----
after reload. */
static rtx *alias_invariant;
! /* Vector indexed by N giving the initial (unchanging) value known for
! pseudo-register N. This array is initialized in
! init_alias_analysis, and does not change until end_alias_analysis
! is called. */
rtx *reg_known_value;
/* Indicates number of valid entries in reg_known_value. */
*************** init_alias_once ()
*** 1569,1574 ****
--- 1571,1579 ----
alias_sets = splay_tree_new (splay_tree_compare_ints, 0, 0);
}
+
+ /* Initialize the aliasing machinery. Initialize the REG_KNOWN_VALUE
+ array. */
void
init_alias_analysis ()
Index: gcc/cse.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/cse.c,v
retrieving revision 1.134
diff -c -p -r1.134 cse.c
*** cse.c 2000/03/25 18:34:01 1.134
--- cse.c 2000/03/31 07:00:21
*************** exp_equiv_p (x, y, validate, equal_value
*** 2367,2376 ****
{
case PC:
case CC0:
- return x == y;
-
case CONST_INT:
! return INTVAL (x) == INTVAL (y);
case LABEL_REF:
return XEXP (x, 0) == XEXP (y, 0);
--- 2367,2374 ----
{
case PC:
case CC0:
case CONST_INT:
! return x == y;
case LABEL_REF:
return XEXP (x, 0) == XEXP (y, 0);
*************** cse_basic_block (from, to, next_branch,
*** 6898,6904 ****
/* If we have processed 1,000 insns, flush the hash table to
avoid extreme quadratic behavior. We must not include NOTEs
! in the count since there may be more or them when generating
debugging information. If we clear the table at different
times, code generated with -g -O might be different than code
generated with -O but not -g.
--- 6896,6902 ----
/* If we have processed 1,000 insns, flush the hash table to
avoid extreme quadratic behavior. We must not include NOTEs
! in the count since there may be more of them when generating
debugging information. If we clear the table at different
times, code generated with -g -O might be different than code
generated with -O but not -g.
Index: gcc/emit-rtl.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/emit-rtl.c,v
retrieving revision 1.120
diff -c -p -r1.120 emit-rtl.c
*** emit-rtl.c 2000/03/30 13:46:05 1.120
--- emit-rtl.c 2000/03/31 07:00:22
*************** Boston, MA 02111-1307, USA. */
*** 46,51 ****
--- 46,52 ----
#include "expr.h"
#include "regs.h"
#include "hard-reg-set.h"
+ #include "hashtab.h"
#include "insn-config.h"
#include "recog.h"
#include "real.h"
*************** rtx return_address_pointer_rtx; /* (REG:
*** 137,142 ****
--- 138,148 ----
rtx const_int_rtx[MAX_SAVED_CONST_INT * 2 + 1];
+ /* A hash table storing CONST_INTs whose absolute value is greater
+ than MAX_SAVED_CONST_INT. */
+
+ static htab_t const_int_htab;
+
/* start_sequence and gen_sequence can make a lot of rtx expressions which are
shortly thrown away. We use two mechanisms to prevent this waste:
*************** static rtx make_call_insn_raw PARAMS ((
*** 172,187 ****
static rtx find_line_note PARAMS ((rtx));
static void mark_sequence_stack PARAMS ((struct sequence_stack *));
static void unshare_all_rtl_1 PARAMS ((rtx));
/* There are some RTL codes that require special attention; the generation
functions do the raw handling. If you add to this list, modify
special_rtx in gengenrtl.c as well. */
rtx
gen_rtx_CONST_INT (mode, arg)
! enum machine_mode mode;
HOST_WIDE_INT arg;
{
if (arg >= - MAX_SAVED_CONST_INT && arg <= MAX_SAVED_CONST_INT)
return const_int_rtx[arg + MAX_SAVED_CONST_INT];
--- 178,244 ----
static rtx find_line_note PARAMS ((rtx));
static void mark_sequence_stack PARAMS ((struct sequence_stack *));
static void unshare_all_rtl_1 PARAMS ((rtx));
+ static hashval_t const_int_htab_hash PARAMS ((const void *));
+ static int const_int_htab_eq PARAMS ((const void *,
+ const void *));
+ static int rtx_htab_mark_1 PARAMS ((void **, void *));
+ static void rtx_htab_mark PARAMS ((void *));
+
+ /* Returns a hash code for X (which is a really a CONST_INT). */
+
+ static hashval_t
+ const_int_htab_hash (x)
+ const void *x;
+ {
+ return (hashval_t) INTVAL ((rtx) x);
+ }
+
+ /* Returns non-zero if the value represented by X (which is really a
+ CONST_INT) is the same as that given by Y (which is really a
+ HOST_WIDE_INT *). */
+
+ static int
+ const_int_htab_eq (x, y)
+ const void *x;
+ const void *y;
+ {
+ return (INTVAL ((rtx) x) == *((HOST_WIDE_INT *) y));
+ }
+
+ /* Mark the hash-table element X (which is really a pointer to an
+ rtx). */
+
+ static int
+ rtx_htab_mark_1 (x, data)
+ void **x;
+ void *data ATTRIBUTE_UNUSED;
+ {
+ ggc_mark_rtx (*x);
+ return 1;
+ }
+
+ /* Mark all the elements of HTAB (which is really an htab_t full of
+ rtxs). */
+
+ static void
+ rtx_htab_mark (htab)
+ void *htab;
+ {
+ htab_traverse (*((htab_t *) htab), rtx_htab_mark_1, NULL);
+ }
+
/* There are some RTL codes that require special attention; the generation
functions do the raw handling. If you add to this list, modify
special_rtx in gengenrtl.c as well. */
rtx
gen_rtx_CONST_INT (mode, arg)
! enum machine_mode mode ATTRIBUTE_UNUSED;
HOST_WIDE_INT arg;
{
+ void **slot;
+
if (arg >= - MAX_SAVED_CONST_INT && arg <= MAX_SAVED_CONST_INT)
return const_int_rtx[arg + MAX_SAVED_CONST_INT];
*************** gen_rtx_CONST_INT (mode, arg)
*** 189,196 ****
if (const_true_rtx && arg == STORE_FLAG_VALUE)
return const_true_rtx;
#endif
! return gen_rtx_raw_CONST_INT (mode, arg);
}
/* CONST_DOUBLEs needs special handling because its length is known
--- 246,261 ----
if (const_true_rtx && arg == STORE_FLAG_VALUE)
return const_true_rtx;
#endif
+
+ /* Look up the CONST_INT in the hash table. */
+ slot = htab_find_slot_with_hash (const_int_htab,
+ &arg,
+ (hashval_t) arg,
+ /*insert=*/1);
+ if (!*slot)
+ *slot = gen_rtx_raw_CONST_INT (VOIDmode, arg);
! return (rtx) *slot;
}
/* CONST_DOUBLEs needs special handling because its length is known
*************** unshare_all_rtl (fndecl, insn)
*** 1627,1635 ****
/* Make sure that virtual parameters are not shared. */
for (decl = DECL_ARGUMENTS (fndecl); decl; decl = TREE_CHAIN (decl))
! {
! copy_rtx_if_shared (DECL_RTL (decl));
! }
/* Unshare just about everything else. */
unshare_all_rtl_1 (insn);
--- 1692,1698 ----
/* Make sure that virtual parameters are not shared. */
for (decl = DECL_ARGUMENTS (fndecl); decl; decl = TREE_CHAIN (decl))
! copy_rtx_if_shared (DECL_RTL (decl));
/* Unshare just about everything else. */
unshare_all_rtl_1 (insn);
*************** init_emit_once (line_numbers)
*** 4083,4088 ****
--- 4146,4159 ----
ggc_add_rtx_root (&static_chain_rtx, 1);
ggc_add_rtx_root (&static_chain_incoming_rtx, 1);
ggc_add_rtx_root (&return_address_pointer_rtx, 1);
+
+ /* Initialize the CONST_INT hash table. */
+ const_int_htab = htab_create (37,
+ const_int_htab_hash,
+ const_int_htab_eq,
+ NULL);
+ ggc_add_root (&const_int_htab, 1, sizeof (const_int_htab),
+ rtx_htab_mark);
}
/* Query and clear/ restore no_line_numbers. This is used by the
Index: gcc/rtl.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/rtl.c,v
retrieving revision 1.65
diff -c -p -r1.65 rtl.c
*** rtl.c 2000/03/29 01:56:04 1.65
--- rtl.c 2000/03/31 07:00:24
*************** rtx_equal_p (x, y)
*** 613,634 ****
if (GET_MODE (x) != GET_MODE (y))
return 0;
! /* REG, LABEL_REF, and SYMBOL_REF can be compared nonrecursively. */
! if (code == REG)
! /* Until rtl generation is complete, don't consider a reference to the
! return register of the current function the same as the return from a
! called function. This eases the job of function integration. Once the
! distinction is no longer needed, they can be considered equivalent. */
! return (REGNO (x) == REGNO (y)
! && (! rtx_equal_function_value_matters
! || REG_FUNCTION_VALUE_P (x) == REG_FUNCTION_VALUE_P (y)));
! else if (code == LABEL_REF)
! return XEXP (x, 0) == XEXP (y, 0);
! else if (code == SYMBOL_REF)
! return XSTR (x, 0) == XSTR (y, 0);
! else if (code == SCRATCH || code == CONST_DOUBLE)
! return 0;
/* Compare the elements. If any pair of corresponding elements
fail to match, return 0 for the whole things. */
--- 613,644 ----
if (GET_MODE (x) != GET_MODE (y))
return 0;
! /* Some RTL can be compared nonrecursively. */
! switch (code)
! {
! case REG:
! /* Until rtl generation is complete, don't consider a reference to the
! return register of the current function the same as the return from a
! called function. This eases the job of function integration. Once the
! distinction is no longer needed, they can be considered equivalent. */
! return (REGNO (x) == REGNO (y)
! && (! rtx_equal_function_value_matters
! || REG_FUNCTION_VALUE_P (x) == REG_FUNCTION_VALUE_P (y)));
! case LABEL_REF:
! return XEXP (x, 0) == XEXP (y, 0);
!
! case SYMBOL_REF:
! return XSTR (x, 0) == XSTR (y, 0);
!
! case SCRATCH:
! case CONST_DOUBLE:
! case CONST_INT:
! return 0;
!
! default:
! break;
! }
/* Compare the elements. If any pair of corresponding elements
fail to match, return 0 for the whole things. */
Index: gcc/rtl.texi
===================================================================
RCS file: /cvs/gcc/egcs/gcc/rtl.texi,v
retrieving revision 1.25
diff -c -p -r1.25 rtl.texi
*** rtl.texi 2000/02/26 01:50:50 1.25
--- rtl.texi 2000/03/31 07:00:27
***************
*** 1,4 ****
! @c Copyright (C) 1988, 89, 92, 94, 97, 1998, 1999 Free Software Foundation, Inc.
@c This is part of the GCC manual.
@c For copying conditions, see the file gcc.texi.
--- 1,4 ----
! @c Copyright (C) 1988, 89, 92, 94, 97, 1998, 1999, 2000 Free Software Foundation, Inc.
@c This is part of the GCC manual.
@c For copying conditions, see the file gcc.texi.
*************** referring to it.
*** 2917,2925 ****
@cindex @code{const_int}, RTL sharing
@item
! There is only one @code{const_int} expression with value 0, only
! one with value 1, and only one with value @minus{}1.
! Some other integer values are also stored uniquely.
@cindex @code{pc}, RTL sharing
@item
--- 2917,2923 ----
@cindex @code{const_int}, RTL sharing
@item
! All @code{const_int} expressions with equal values are shared.
@cindex @code{pc}, RTL sharing
@item
More information about the Gcc-patches
mailing list