2002-07-15 Michael Matz <matz@suse.de>,

            Daniel Berlin  <dberlin@dberlin.org>,
	    Denis Chertykov  <denisc@overta.ru>

	Add a new register allocator.

	* ra.c: New file.
	* ra.h: New file.
	* ra-build.c: New file.
	* ra-colorize.c: New file.
	* ra-debug.c: New file.
	* ra-rewrite.c: New file.

	* Makefile.in (ra.o, ra-build.o, ra-colorize.o, ra-debug.o,
	(ra-rewrite.o): New .o files for libbackend.a.
	(GTFILES): Add basic-block.h.

	* toplev.c (flag_new_regalloc): New.
	(f_options): New option "new-ra".
	(rest_of_compilation): Call initialize_uninitialized_subregs()
	only for the old allocator.  If flag_new_regalloc is set, call
	new allocator, instead of local_alloc(), global_alloc() and
	friends.

	* doc/invoke.texi: Document -fnew-ra.
	* basic-block.h (FOR_ALL_BB): New.
	* config/rs6000/rs6000.c (print_operand): Write small constants
	as @l+80.

	* df.c (read_modify_subreg_p): Narrow down cases for a rmw subreg.
	(df_reg_table_realloc): Make size at least as large as max_reg_num().
	(df_insn_table_realloc): Size argument now is absolute, not relative.
	Changed all callers.

	* gengtype.c (main): Add the pseudo-type "HARD_REG_SET".
	* regclass.c (reg_scan_mark_refs): Ignore NULL rtx's.

	2002-06-20  Michael Matz  <matz@suse.de>

	* df.h (struct ref.id): Make unsigned.
	* df.c (df_bb_reg_def_chain_create): Remove unsigned cast.

	2002-06-13  Michael Matz  <matz@suse.de>

	* df.h (DF_REF_MODE_CHANGE): New flag.
	* df.c (df_def_record_1, df_uses_record): Set this flag for refs
	involving subregs with invalid mode changes, when
	CLASS_CANNOT_CHANGE_MODE is defined.

	2002-05-07  Michael Matz  <matz@suse.de>

	* reload1.c (fixup_abnormal_edges): Don't insert on NULL edge.

	2002-05-03  Michael Matz  <matz@suse.de>

	* sbitmap.c (sbitmap_difference): Accept sbitmaps of different size.

	Sat Feb  2 18:58:07 2002  Denis Chertykov  <denisc@overta.ru>

	* regclass.c (regclass): Work with all regs which have sets or
	refs.
	(reg_scan_mark_refs): Count regs inside (clobber ...).

	2002-01-04  Michael Matz  <matzmich@cs.tu-berlin.de>

	* df.c (df_ref_record): Correctly calculate SUBREGs of hardregs.
	(df_bb_reg_def_chain_create, df_bb_reg_use_chain_create): Only
	add new refs.
	(df_bb_refs_update): Don't clear insns_modified here, ...
	(df_analyse): ... but here.

	* sbitmap.c (dump_sbitmap_file): New.
	(debug_sbitmap): Use it.

	* sbitmap.h (dump_sbitmap_file): Add prototype.

	2001-08-07  Daniel Berlin  <dan@cgsoftware.com>

	* df.c (df_insn_modify): Grow the UID table if necessary, rather
	than assume all emits go through df_insns_modify.

	2001-07-26  Daniel Berlin  <dan@cgsoftware.com>

	* regclass.c (reg_scan_mark_refs): When we increase REG_N_SETS,
	increase REG_N_REFS (like flow does), so that regclass doesn't
	think a reg is useless, and thus, not calculate a class, when it
	really should have.

	2001-01-28  Daniel Berlin  <dberlin@redhat.com>

	* sbitmap.h (EXECUTE_IF_SET_IN_SBITMAP_REV): New macro, needed for
	dataflow analysis.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@55458 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 624 insertions, 0 deletions

diff --git a/gcc/ra.h b/gcc/ra.h
new file mode 100644
index 00000000000..0da1bc3b9f5
--- /dev/null
+++ b/gcc/ra.h
@@ -0,0 +1,624 @@
+/* Graph coloring register allocator
+   Copyright (C) 2001, 2002 Free Software Foundation, Inc.
+   Contributed by Michael Matz <matz@suse.de>
+   and Daniel Berlin <dan@cgsoftware.com>.
+
+   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.  */
+
+/* Double linked list to implement the per-type lists of webs
+   and moves.  */
+struct dlist
+{
+  struct dlist *prev;
+  struct dlist *next;
+  union
+    {
+      struct web *web;
+      struct move *move;
+    } value;
+};
+/* Simple helper macros for ease of misuse.  */
+#define DLIST_WEB(l) ((l)->value.web)
+#define DLIST_MOVE(l) ((l)->value.move)
+
+/* Classification of a given node (i.e. what state it's in).  */
+enum node_type
+{
+  INITIAL = 0, FREE,
+  PRECOLORED,
+  SIMPLIFY, SIMPLIFY_SPILL, SIMPLIFY_FAT, FREEZE, SPILL,
+  SELECT,
+  SPILLED, COALESCED, COLORED,
+  LAST_NODE_TYPE
+};
+
+/* A list of conflict bitmaps, factorized on the exact part of
+   the source, which conflicts with the DEFs, whose ID are noted in
+   the bitmap.  This is used while building web-parts with conflicts.  */
+struct tagged_conflict
+{
+  struct tagged_conflict *next;
+  bitmap conflicts;
+
+  /* If the part of source identified by size S, byteoffset O conflicts,
+     then size_word == S | (O << 16).  */
+  unsigned int size_word;
+};
+
+/* Such a structure is allocated initially for each def and use.
+   In the process of building the interference graph web parts are
+   connected together, if they have common instructions and reference the
+   same register.  That way live ranges are build (by connecting defs and
+   uses) and implicitely complete webs (by connecting web parts in common
+   uses).  */
+struct web_part
+{
+  /* The def or use for this web part.  */
+  struct ref *ref;
+  /* The uplink implementing the disjoint set.  */
+  struct web_part *uplink;
+
+  /* Here dynamic information associated with each def/use is saved.
+     This all is only valid for root web parts (uplink==NULL).
+     That's the information we need to merge, if web parts are unioned.  */
+
+  /* Number of spanned insns containing any deaths.  */
+  unsigned int spanned_deaths;
+  /* The list of bitmaps of DEF ID's with which this part conflicts.  */
+  struct tagged_conflict *sub_conflicts;
+  /* If there's any call_insn, while this part is live.  */
+  unsigned int crosses_call : 1;
+};
+
+/* Web structure used to store info about connected live ranges.
+   This represents the nodes of the interference graph, which gets
+   colored.  It can also hold subwebs, which are contained in webs
+   and represent subregs.  */
+struct web
+{
+  /* Unique web ID.  */
+  unsigned int id;
+
+  /* Register number of the live range's variable.  */
+  unsigned int regno;
+
+  /* How many insns containing deaths do we span?  */
+  unsigned int span_deaths;
+
+  /* Spill_temp indicates if this web was part of a web spilled in the
+     last iteration, or or reasons why this shouldn't be spilled again.
+     1 spill web, can't be spilled.
+     2 big spill web (live over some deaths).  Discouraged, but not
+       impossible to spill again.
+     3 short web (spans no deaths), can't be spilled.  */
+  unsigned int spill_temp;
+
+  /* When coalescing we might change spill_temp.  If breaking aliases we
+     need to restore it.  */
+  unsigned int orig_spill_temp;
+
+  /* Cost of spilling.  */
+  unsigned HOST_WIDE_INT spill_cost;
+  unsigned HOST_WIDE_INT orig_spill_cost;
+
+  /* How many webs are aliased to us?  */
+  unsigned int num_aliased;
+
+  /* The color we got.  This is a hardreg number.  */
+  int color;
+  /* 1 + the color this web got in the last pass.  If it hadn't got a color,
+     or we are in the first pass, or this web is a new one, this is zero.  */
+  int old_color;
+
+  /* Now follow some flags characterizing the web.  */
+
+  /* Nonzero, if we should use usable_regs for this web, instead of
+     preferred_class() or alternate_class().  */
+  unsigned int use_my_regs:1;
+
+  /* Nonzero if we selected this web as possible spill candidate in
+     select_spill().  */
+  unsigned int was_spilled:1;
+
+  /* We need to distinguish also webs which are targets of coalescing
+     (all x with some y, so that x==alias(y)), but the alias field is
+     only set for sources of coalescing.  This flag is set for all webs
+     involved in coalescing in some way.  */
+  unsigned int is_coalesced:1;
+
+  /* Nonzero, if this web (or subweb) doesn't correspond with any of
+     the current functions actual use of reg rtx.  Happens e.g. with
+     conflicts to a web, of which only a part was still undefined at the
+     point of that conflict.  In this case we construct a subweb
+     representing these yet undefined bits to have a target for the
+     conflict.  Suppose e.g. this sequence:
+     (set (reg:DI x) ...)
+     (set (reg:SI y) ...)
+     (set (subreg:SI (reg:DI x) 0) ...)
+     (use (reg:DI x))
+     Here x only partly conflicts with y.  Namely only (subreg:SI (reg:DI x)
+     1) conflicts with it, but this rtx doesn't show up in the program.  For
+     such things an "artificial" subweb is built, and this flag is true for
+     them.  */
+  unsigned int artificial:1;
+
+  /* Nonzero if we span a call_insn.  */
+  unsigned int crosses_call:1;
+
+  /* Wether the web is involved in a move insn.  */
+  unsigned int move_related:1;
+
+  /* 1 when this web (or parts thereof) are live over an abnormal edge.  */
+  unsigned int live_over_abnormal:1;
+
+  /* Nonzero if this web is used in subregs where the mode change
+     was illegal for hardregs in CLASS_CANNOT_CHANGE_MODE.  */
+  unsigned int mode_changed:1;
+
+  /* Nonzero, when this web stems from the last pass of the allocator,
+     and all info is still valid (i.e. it wasn't spilled).  */
+  unsigned int old_web:1;
+
+  /* Used in rewrite_program2() to remember webs, which
+     are already marked for (re)loading.  */
+  unsigned int in_load:1;
+
+  /* If in_load is != 0, then this is nonzero, if only one use was seen
+     since insertion in loadlist.  Zero if more uses currently need a
+     reload.  Used to differentiate between inserting register loads or
+     directly substituting the stackref.  */
+  unsigned int one_load:1;
+
+  /* When using rewrite_program2() this flag gets set if some insns
+     were inserted on behalf of this web.  IR spilling might ignore some
+     deaths up to the def, so no code might be emitted and we need not to
+     spill such a web again.  */
+  unsigned int changed:1;
+
+  /* With interference region spilling it's sometimes the case, that a
+     bb border is also an IR border for webs, which were targets of moves,
+     which are already removed due to coalescing.  All webs, which are
+     a destination of such a removed move, have this flag set.  */
+  unsigned int target_of_spilled_move:1;
+
+  /* For optimistic coalescing we need to be able to break aliases, which
+     includes restoring conflicts to those before coalescing.  This flag
+     is set, if we have a list of conflicts before coalescing.  It's needed
+     because that list is lazily constructed only when actually needed.  */
+  unsigned int have_orig_conflicts:1;
+
+  /* Current state of the node.  */
+  ENUM_BITFIELD(node_type) type:5;
+
+  /* A regclass, combined from preferred and alternate class, or calculated
+     from usable_regs.  Used only for debugging, and to determine
+     add_hardregs.  */
+  ENUM_BITFIELD(reg_class) regclass:10;
+
+  /* Additional consecutive hardregs needed for this web.  */
+  int add_hardregs;
+
+  /* Number of conflicts currently.  */
+  int num_conflicts;
+
+  /* Numbers of uses and defs, which belong to this web.  */
+  unsigned int num_uses;
+  unsigned int num_defs;
+
+  /* The (reg:M a) or (subreg:M1 (reg:M2 a) x) rtx which this
+     web is based on.  This is used to distinguish subreg webs
+     from it's reg parents, and to get hold of the mode.  */
+  rtx orig_x;
+
+  /* If this web is a subweb, this point to the super web.  Otherwise
+     it's NULL.  */
+  struct web *parent_web;
+
+  /* If this web is a subweb, but not the last one, this points to the
+     next subweb of the same super web.  Otherwise it's NULL.  */
+  struct web *subreg_next;
+
+  /* The set of webs (or subwebs), this web conflicts with.  */
+  struct conflict_link *conflict_list;
+
+  /* If have_orig_conflicts is set this contains a copy of conflict_list,
+     as it was right after building the interference graph.
+     It's used for incremental i-graph building and for breaking
+     coalescings again.  */
+  struct conflict_link *orig_conflict_list;
+
+  /* Bitmap of all conflicts which don't count this pass, because of
+     non-intersecting hardregs of the conflicting webs.  See also
+     record_conflict().  */
+  bitmap useless_conflicts;
+
+  /* Different sets of hard registers, for all usable registers, ...  */
+  HARD_REG_SET usable_regs;
+  /* ... the same before coalescing, ...  */
+  HARD_REG_SET orig_usable_regs;
+  /* ... colors of all already colored neighbors (used when biased coloring
+     is active), and ...  */
+  HARD_REG_SET bias_colors;
+  /* ... colors of PRECOLORED webs this web is connected to by a move.  */
+  HARD_REG_SET prefer_colors;
+
+  /* Number of usable colors in usable_regs.  */
+  int num_freedom;
+
+  /* After successfull coloring the graph each web gets a new reg rtx,
+     with which the original uses and defs are replaced.  This is it.  */
+  rtx reg_rtx;
+
+  /* While spilling this is the rtx of the home of spilled webs.
+     It can be a mem ref (a stack slot), or a pseudo register.  */
+  rtx stack_slot;
+
+  /* Used in rewrite_program2() to remember the using
+     insn last seen for webs needing (re)loads.  */
+  rtx last_use_insn;
+
+  /* If this web is rematerializable, this contains the RTL pattern
+     usable as source for that.  Otherwise it's NULL.  */
+  rtx pattern;
+
+  /* All the defs and uses.  There are num_defs, resp.
+     num_uses elements.  */
+  struct ref **defs; /* [0..num_defs-1] */
+  struct ref **uses; /* [0..num_uses-1] */
+
+  /* The web to which this web is aliased (coalesced).  If NULL, this
+     web is not coalesced into some other (but might still be a target
+     for other webs).  */
+  struct web *alias;
+
+  /* With iterated coalescing this is a list of active moves this web
+     is involved in.  */
+  struct move_list *moves;
+
+  /* The list implementation.  */
+  struct dlist *dlink;
+
+  /* While building webs, out of web-parts, this holds a (partial)
+     list of all refs for this web seen so far.  */
+  struct df_link *temp_refs;
+};
+
+/* For implementing a single linked list.  */
+struct web_link
+{
+  struct web_link *next;
+  struct web *web;
+};
+
+/* A subconflict is part of an conflict edge to track precisely,
+   which parts of two webs conflict, in case not all of both webs do.  */
+struct sub_conflict
+{
+  /* The next partial conflict.  For one such list the parent-web of
+     all the S webs, resp. the parent of all the T webs are constant.  */
+  struct sub_conflict *next;
+  struct web *s;
+  struct web *t;
+};
+
+/* This represents an edge in the conflict graph.  */
+struct conflict_link
+{
+  struct conflict_link *next;
+
+  /* The web we conflict with (the Target of the edge).  */
+  struct web *t;
+
+  /* If not the complete source web and T conflict, this points to
+     the list of parts which really conflict.  */
+  struct sub_conflict *sub;
+};
+
+/* For iterated coalescing the moves can be in these states.  */
+enum move_type
+{
+  WORKLIST, MV_COALESCED, CONSTRAINED, FROZEN, ACTIVE,
+  LAST_MOVE_TYPE
+};
+
+/* Structure of a move we are considering coalescing.  */
+struct move
+{
+  rtx insn;
+  struct web *source_web;
+  struct web *target_web;
+  enum move_type type;
+  struct dlist *dlink;
+};
+
+/* List of moves.  */
+struct move_list
+{
+  struct move_list *next;
+  struct move *move;
+};
+
+/* To have fast access to the defs and uses per insn, we have one such
+   structure per insn.  The difference to the normal df.c structures is,
+   that it doesn't contain any NULL refs, which df.c produces in case
+   an insn was modified and it only contains refs to pseudo regs, or to
+   hardregs which matter for allocation, i.e. those not in
+   never_use_colors.  */
+struct ra_insn_info
+{
+  unsigned int num_defs, num_uses;
+  struct ref **defs, **uses;
+};
+
+/* The above structures are stored in this array, indexed by UID...  */
+extern struct ra_insn_info *insn_df;
+/* ... and the size of that array, as we add insn after setting it up.  */
+extern int insn_df_max_uid;
+
+/* The interference graph.  */
+extern sbitmap igraph;
+/* And how to access it.  I and J are web indices.  If the bit
+   igraph_index(I, J) is set, then they conflict.  Note, that
+   if only parts of webs conflict, then also only those parts
+   are noted in the I-graph (i.e. the parent webs not).  */
+#define igraph_index(i, j) ((i) < (j) ? ((j)*((j)-1)/2)+(i) : ((i)*((i)-1)/2)+(j))
+/* This is the bitmap of all (even partly) conflicting super webs.
+   If bit I*num_webs+J or J*num_webs+I is set, then I and J (both being
+   super web indices) conflict, maybe only partially.  Note the
+   assymetry.  */
+extern sbitmap sup_igraph;
+
+/* After the first pass, and when interference region spilling is
+   activated, bit I is set, when the insn with UID I contains some
+   refs to pseudos which die at the insn.  */
+extern sbitmap insns_with_deaths;
+/* The size of that sbitmap.  */
+extern int death_insns_max_uid;
+
+/* All the web-parts.  There are exactly as many web-parts as there
+   are register refs in the insn stream.  */
+extern struct web_part *web_parts;
+
+/* The number of all webs, including subwebs.  */
+extern unsigned int num_webs;
+/* The number of just the subwebs.  */
+extern unsigned int num_subwebs;
+/* The number of all webs, including subwebs.  */
+extern unsigned int num_allwebs;
+
+/* For easy access when given a web ID: id2web[W->id] == W.  */
+extern struct web **id2web;
+/* For each hardreg, the web which represents it.  */
+extern struct web *hardreg2web[FIRST_PSEUDO_REGISTER];
+
+/* Given the ID of a df_ref, which represent a DEF, def2web[ID] is
+   the web, to which this def belongs.  */
+extern struct web **def2web;
+/* The same as def2web, just for uses.  */
+extern struct web **use2web;
+
+/* The list of all recognized and coalescable move insns.  */
+extern struct move_list *wl_moves;
+
+
+/* Some parts of the compiler which we run after colorizing
+   clean reg_renumber[], so we need another place for the colors.
+   This is copied to reg_renumber[] just before returning to toplev.  */
+extern short *ra_reg_renumber;
+/* The size of that array.  Some passes after coloring might have created
+   new pseudos, which will get no color.  */
+extern int ra_max_regno;
+
+/* The dataflow structure of the current function, while regalloc
+   runs.  */
+extern struct df *df;
+
+/* For each basic block B we have a bitmap of DF_REF_ID's of uses,
+   which backward reach the end of B.  */
+extern bitmap *live_at_end;
+
+/* One pass is: collecting registers refs, buiding I-graph, spilling.
+   And this is how often we already ran that for the current function.  */
+extern int ra_pass;
+
+/* The maximum pseudo regno, just before register allocation starts.
+   While regalloc runs all pseudos with a larger number represent
+   potentially stack slots or hardregs.  I call them stackwebs or
+   stackpseudos.  */
+extern unsigned int max_normal_pseudo;
+
+/* One of the fixed colors.  It must be < FIRST_PSEUDO_REGISTER, because
+   we sometimes want to check the color against a HARD_REG_SET.  It must
+   be >= 0, because negative values mean "no color".
+   This color is used for the above stackwebs, when they can't be colored.
+   I.e. normally they would be spilled, but they already represent
+   stackslots.  So they are colored with an invalid color.  It has
+   the property that even webs which conflict can have that color at the
+   same time.  I.e. a stackweb with that color really represents a
+   stackslot.  */
+extern int an_unusable_color;
+
+/* While building the I-graph, every time insn UID is looked at,
+   number_seen[UID] is incremented.  For debugging.  */
+extern int *number_seen;
+
+/* The different lists on which a web can be (based on the type).  */
+extern struct dlist *web_lists[(int) LAST_NODE_TYPE];
+#define WEBS(type) (web_lists[(int)(type)])
+
+/* The largest DF_REF_ID of defs resp. uses, as it was in the
+   last pass.  In the first pass this is zero.  Used to distinguish new
+   from old refrences.  */
+extern unsigned int last_def_id;
+extern unsigned int last_use_id;
+
+/* Similar for UIDs and number of webs.  */
+extern int last_max_uid;
+extern unsigned int last_num_webs;
+
+/* If I is the ID of an old use, and last_check_uses[I] is set,
+   then we must reevaluate it's flow while building the new I-graph.  */
+extern sbitmap last_check_uses;
+
+/* If nonzero, record_conflict() saves the current conflict list of
+   webs in orig_conflict_list, when not already done so, and the conflict
+   list is going to be changed.  It is set, after initially building the
+   I-graph.  I.e. new conflicts due to coalescing trigger that copying.  */
+extern unsigned int remember_conflicts;
+
+/* The maximum UID right before calling regalloc().
+   Used to detect any instructions inserted by the allocator.  */
+extern int orig_max_uid;
+
+/* A HARD_REG_SET of those color, which can't be used for coalescing.
+   Includes e.g. fixed_regs.  */
+extern HARD_REG_SET never_use_colors;
+/* For each class C this is reg_class_contents[C] \ never_use_colors.  */
+extern HARD_REG_SET usable_regs[N_REG_CLASSES];
+/* For each class C the count of hardregs in usable_regs[C].  */
+extern unsigned int num_free_regs[N_REG_CLASSES];
+/* For each mode M the hardregs, which are MODE_OK for M, and have
+   enough space behind them to hold an M value.  Additinally
+   if reg R is OK for mode M, but it needs two hardregs, then R+1 will
+   also be set here, even if R+1 itself is not OK for M.  I.e. this
+   represent the possible resources which could be taken away be a value
+   in mode M.  */
+extern HARD_REG_SET hardregs_for_mode[NUM_MACHINE_MODES];
+/* For 0 <= I <= 255, the number of bits set in I.  Used to calculate
+   the number of set bits in a HARD_REG_SET.  */
+extern unsigned char byte2bitcount[256];
+
+/* Expressive helper macros.  */
+#define ID2WEB(I) id2web[I]
+#define NUM_REGS(W) (((W)->type == PRECOLORED) ? 1 : (W)->num_freedom)
+#define SUBWEB_P(W) (GET_CODE ((W)->orig_x) == SUBREG)
+
+/* Constant usable as debug area to ra_debug_msg.  */
+#define DUMP_COSTS		0x0001
+#define DUMP_WEBS		0x0002
+#define DUMP_IGRAPH		0x0004
+#define DUMP_PROCESS		0x0008
+#define DUMP_COLORIZE		0x0010
+#define DUMP_ASM		0x0020
+#define DUMP_CONSTRAINTS	0x0040
+#define DUMP_RESULTS		0x0080
+#define DUMP_DF			0x0100
+#define DUMP_RTL		0x0200
+#define DUMP_FINAL_RTL		0x0400
+#define DUMP_REGCLASS		0x0800
+#define DUMP_SM			0x1000
+#define DUMP_LAST_FLOW		0x2000
+#define DUMP_LAST_RTL		0x4000
+#define DUMP_REBUILD		0x8000
+#define DUMP_IGRAPH_M		0x10000
+#define DUMP_VALIDIFY		0x20000
+#define DUMP_EVER		((unsigned int)-1)
+#define DUMP_NEARLY_EVER	(DUMP_EVER - DUMP_COSTS - DUMP_IGRAPH_M)
+
+/* All the wanted debug levels as ORing of the various DUMP_xxx
+   constants.  */
+extern unsigned int debug_new_regalloc;
+
+/* Nonzero means we want biased coloring.  */
+extern int flag_ra_biased;
+
+/* Nonzero if we want to use improved (and slow) spilling.  This
+   includes also interference region spilling (see below).  */
+extern int flag_ra_improved_spilling;
+
+/* Nonzero for using interference region spilling.  Zero for improved
+   Chaintin style spilling (only at deaths).  */
+extern int flag_ra_ir_spilling;
+
+/* Nonzero if we use optimistic coalescing, zero for iterated
+   coalescing.  */
+extern int flag_ra_optimistic_coalescing;
+
+/* Nonzero if we want to break aliases of spilled webs.  Forced to
+   nonzero, when flag_ra_optimistic_coalescing is.  */
+extern int flag_ra_break_aliases;
+
+/* Nonzero if we want to merge the spill costs of webs which
+   are coalesced.  */
+extern int flag_ra_merge_spill_costs;
+
+/* Nonzero if we want to spill at every use, instead of at deaths,
+   or intereference region borders.  */
+extern int flag_ra_spill_every_use;
+
+/* Nonzero to output all notes in the debug dumps.  */
+extern int flag_ra_dump_notes;
+
+extern inline void * ra_alloc PARAMS ((size_t));
+extern inline void * ra_calloc PARAMS ((size_t));
+extern int hard_regs_count PARAMS ((HARD_REG_SET));
+extern rtx ra_emit_move_insn PARAMS ((rtx, rtx));
+extern void ra_debug_msg PARAMS ((unsigned int,
+			          const char *, ...)) ATTRIBUTE_PRINTF_2;
+extern int hard_regs_intersect_p PARAMS ((HARD_REG_SET *, HARD_REG_SET *));
+extern unsigned int rtx_to_bits PARAMS ((rtx));
+extern struct web * find_subweb PARAMS ((struct web *, rtx));
+extern struct web * find_subweb_2 PARAMS ((struct web *, unsigned int));
+extern struct web * find_web_for_subweb_1 PARAMS ((struct web *));
+
+#define find_web_for_subweb(w) (((w)->parent_web) \
+				? find_web_for_subweb_1 ((w)->parent_web) \
+				: (w))
+
+extern void ra_build_realloc PARAMS ((struct df *));
+extern void ra_build_free PARAMS ((void));
+extern void ra_build_free_all PARAMS ((struct df *));
+extern void ra_colorize_init PARAMS ((void));
+extern void ra_colorize_free_all PARAMS ((void));
+extern void ra_rewrite_init PARAMS ((void));
+
+extern void ra_print_rtx PARAMS ((FILE *, rtx, int));
+extern void ra_print_rtx_top PARAMS ((FILE *, rtx, int));
+extern void ra_debug_rtx PARAMS ((rtx));
+extern void ra_debug_insns PARAMS ((rtx, int));
+extern void ra_debug_bbi PARAMS ((int));
+extern void ra_print_rtl_with_bb PARAMS ((FILE *, rtx));
+extern void dump_igraph PARAMS ((struct df *));
+extern void dump_igraph_machine PARAMS ((void));
+extern void dump_constraints PARAMS ((void));
+extern void dump_cost PARAMS ((unsigned int));
+extern void dump_graph_cost PARAMS ((unsigned int, const char *));
+extern void dump_ra PARAMS ((struct df *));
+extern void dump_number_seen PARAMS ((void));
+extern void dump_static_insn_cost PARAMS ((FILE *, const char *,
+					   const char *));
+extern void dump_web_conflicts PARAMS ((struct web *));
+extern void dump_web_insns PARAMS ((struct web*));
+extern int web_conflicts_p PARAMS ((struct web *, struct web *));
+extern void debug_hard_reg_set PARAMS ((HARD_REG_SET));
+
+extern void remove_list PARAMS ((struct dlist *, struct dlist **));
+extern struct dlist * pop_list PARAMS ((struct dlist **));
+extern void record_conflict PARAMS ((struct web *, struct web *));
+extern int memref_is_stack_slot PARAMS ((rtx));
+extern void build_i_graph PARAMS ((struct df *));
+extern void put_web PARAMS ((struct web *, enum node_type));
+extern void remove_web_from_list PARAMS ((struct web *));
+extern void reset_lists PARAMS ((void));
+extern struct web * alias PARAMS ((struct web *));
+extern void merge_moves PARAMS ((struct web *, struct web *));
+extern void ra_colorize_graph PARAMS ((struct df *));
+
+extern void actual_spill PARAMS ((void));
+extern void emit_colors PARAMS ((struct df *));
+extern void delete_moves PARAMS ((void));
+extern void setup_renumber PARAMS ((int));
+extern void remove_suspicious_death_notes PARAMS ((void));