summaryrefslogtreecommitdiffstats
path: root/contrib/gcc/ra.c
diff options
context:
space:
mode:
Diffstat (limited to 'contrib/gcc/ra.c')
-rw-r--r--contrib/gcc/ra.c899
1 files changed, 0 insertions, 899 deletions
diff --git a/contrib/gcc/ra.c b/contrib/gcc/ra.c
deleted file mode 100644
index 5884197..0000000
--- a/contrib/gcc/ra.c
+++ /dev/null
@@ -1,899 +0,0 @@
-/* Graph coloring register allocator
- Copyright (C) 2001, 2002, 2003 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. */
-
-#include "config.h"
-#include "system.h"
-#include "coretypes.h"
-#include "tm.h"
-#include "rtl.h"
-#include "tm_p.h"
-#include "insn-config.h"
-#include "recog.h"
-#include "reload.h"
-#include "integrate.h"
-#include "function.h"
-#include "regs.h"
-#include "obstack.h"
-#include "hard-reg-set.h"
-#include "basic-block.h"
-#include "df.h"
-#include "expr.h"
-#include "output.h"
-#include "toplev.h"
-#include "flags.h"
-#include "ra.h"
-
-/* This is the toplevel file of a graph coloring register allocator.
- It is able to act like a George & Appel allocator, i.e. with iterative
- coalescing plus spill coalescing/propagation.
- And it can act as a traditional Briggs allocator, although with
- optimistic coalescing. Additionally it has a custom pass, which
- tries to reduce the overall cost of the colored graph.
-
- We support two modes of spilling: spill-everywhere, which is extremely
- fast, and interference region spilling, which reduces spill code to a
- large extent, but is slower.
-
- Helpful documents:
-
- Briggs, P., Cooper, K. D., and Torczon, L. 1994. Improvements to graph
- coloring register allocation. ACM Trans. Program. Lang. Syst. 16, 3 (May),
- 428-455.
-
- Bergner, P., Dahl, P., Engebretsen, D., and O'Keefe, M. 1997. Spill code
- minimization via interference region spilling. In Proc. ACM SIGPLAN '97
- Conf. on Prog. Language Design and Implementation. ACM, 287-295.
-
- George, L., Appel, A.W. 1996. Iterated register coalescing.
- ACM Trans. Program. Lang. Syst. 18, 3 (May), 300-324.
-
-*/
-
-/* This file contains the main entry point (reg_alloc), some helper routines
- used by more than one file of the register allocator, and the toplevel
- driver procedure (one_pass). */
-
-/* Things, one might do somewhen:
-
- * Lattice based rematerialization
- * create definitions of ever-life regs at the beginning of
- the insn chain
- * insert loads as soon, stores as late as possible
- * insert spill insns as outward as possible (either looptree, or LCM)
- * reuse stack-slots
- * delete coalesced insns. Partly done. The rest can only go, when we get
- rid of reload.
- * don't destroy coalescing information completely when spilling
- * use the constraints from asms
- */
-
-static struct obstack ra_obstack;
-static void create_insn_info (struct df *);
-static void free_insn_info (void);
-static void alloc_mem (struct df *);
-static void free_mem (struct df *);
-static void free_all_mem (struct df *df);
-static int one_pass (struct df *, int);
-static void check_df (struct df *);
-static void init_ra (void);
-
-void reg_alloc (void);
-
-/* These global variables are "internal" to the register allocator.
- They are all documented at their declarations in ra.h. */
-
-/* Somewhen we want to get rid of one of those sbitmaps.
- (for now I need the sup_igraph to note if there is any conflict between
- parts of webs at all. I can't use igraph for this, as there only the real
- conflicts are noted.) This is only used to prevent coalescing two
- conflicting webs, were only parts of them are in conflict. */
-sbitmap igraph;
-sbitmap sup_igraph;
-
-/* Note the insns not inserted by the allocator, where we detected any
- deaths of pseudos. It is used to detect closeness of defs and uses.
- In the first pass this is empty (we could initialize it from REG_DEAD
- notes), in the other passes it is left from the pass before. */
-sbitmap insns_with_deaths;
-int death_insns_max_uid;
-
-struct web_part *web_parts;
-
-unsigned int num_webs;
-unsigned int num_subwebs;
-unsigned int num_allwebs;
-struct web **id2web;
-struct web *hardreg2web[FIRST_PSEUDO_REGISTER];
-struct web **def2web;
-struct web **use2web;
-struct move_list *wl_moves;
-int ra_max_regno;
-short *ra_reg_renumber;
-struct df *df;
-bitmap *live_at_end;
-int ra_pass;
-unsigned int max_normal_pseudo;
-int an_unusable_color;
-
-/* The different lists on which a web can be (based on the type). */
-struct dlist *web_lists[(int) LAST_NODE_TYPE];
-
-unsigned int last_def_id;
-unsigned int last_use_id;
-unsigned int last_num_webs;
-int last_max_uid;
-sbitmap last_check_uses;
-unsigned int remember_conflicts;
-
-int orig_max_uid;
-
-HARD_REG_SET never_use_colors;
-HARD_REG_SET usable_regs[N_REG_CLASSES];
-unsigned int num_free_regs[N_REG_CLASSES];
-HARD_REG_SET hardregs_for_mode[NUM_MACHINE_MODES];
-HARD_REG_SET invalid_mode_change_regs;
-unsigned char byte2bitcount[256];
-
-unsigned int debug_new_regalloc = -1;
-int flag_ra_biased = 0;
-int flag_ra_improved_spilling = 0;
-int flag_ra_ir_spilling = 0;
-int flag_ra_optimistic_coalescing = 0;
-int flag_ra_break_aliases = 0;
-int flag_ra_merge_spill_costs = 0;
-int flag_ra_spill_every_use = 0;
-int flag_ra_dump_notes = 0;
-
-/* Fast allocation of small objects, which live until the allocator
- is done. Allocate an object of SIZE bytes. */
-
-void *
-ra_alloc (size_t size)
-{
- return obstack_alloc (&ra_obstack, size);
-}
-
-/* Like ra_alloc(), but clear the returned memory. */
-
-void *
-ra_calloc (size_t size)
-{
- void *p = obstack_alloc (&ra_obstack, size);
- memset (p, 0, size);
- return p;
-}
-
-/* Returns the number of hardregs in HARD_REG_SET RS. */
-
-int
-hard_regs_count (HARD_REG_SET rs)
-{
- int count = 0;
-#ifdef HARD_REG_SET
- while (rs)
- {
- unsigned char byte = rs & 0xFF;
- rs >>= 8;
- /* Avoid memory access, if nothing is set. */
- if (byte)
- count += byte2bitcount[byte];
- }
-#else
- unsigned int ofs;
- for (ofs = 0; ofs < HARD_REG_SET_LONGS; ofs++)
- {
- HARD_REG_ELT_TYPE elt = rs[ofs];
- while (elt)
- {
- unsigned char byte = elt & 0xFF;
- elt >>= 8;
- if (byte)
- count += byte2bitcount[byte];
- }
- }
-#endif
- return count;
-}
-
-/* Basically like emit_move_insn (i.e. validifies constants and such),
- but also handle MODE_CC moves (but then the operands must already
- be basically valid. */
-
-rtx
-ra_emit_move_insn (rtx x, rtx y)
-{
- enum machine_mode mode = GET_MODE (x);
- if (GET_MODE_CLASS (mode) == MODE_CC)
- return emit_insn (gen_move_insn (x, y));
- else
- return emit_move_insn (x, y);
-}
-
-int insn_df_max_uid;
-struct ra_insn_info *insn_df;
-static struct ref **refs_for_insn_df;
-
-/* Create the insn_df structure for each insn to have fast access to
- all valid defs and uses in an insn. */
-
-static void
-create_insn_info (struct df *df)
-{
- rtx insn;
- struct ref **act_refs;
- insn_df_max_uid = get_max_uid ();
- insn_df = xcalloc (insn_df_max_uid, sizeof (insn_df[0]));
- refs_for_insn_df = xcalloc (df->def_id + df->use_id, sizeof (struct ref *));
- act_refs = refs_for_insn_df;
- /* We create those things backwards to mimic the order in which
- the insns are visited in rewrite_program2() and live_in(). */
- for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
- {
- int uid = INSN_UID (insn);
- unsigned int n;
- struct df_link *link;
- if (!INSN_P (insn))
- continue;
- for (n = 0, link = DF_INSN_DEFS (df, insn); link; link = link->next)
- if (link->ref
- && (DF_REF_REGNO (link->ref) >= FIRST_PSEUDO_REGISTER
- || !TEST_HARD_REG_BIT (never_use_colors,
- DF_REF_REGNO (link->ref))))
- {
- if (n == 0)
- insn_df[uid].defs = act_refs;
- insn_df[uid].defs[n++] = link->ref;
- }
- act_refs += n;
- insn_df[uid].num_defs = n;
- for (n = 0, link = DF_INSN_USES (df, insn); link; link = link->next)
- if (link->ref
- && (DF_REF_REGNO (link->ref) >= FIRST_PSEUDO_REGISTER
- || !TEST_HARD_REG_BIT (never_use_colors,
- DF_REF_REGNO (link->ref))))
- {
- if (n == 0)
- insn_df[uid].uses = act_refs;
- insn_df[uid].uses[n++] = link->ref;
- }
- act_refs += n;
- insn_df[uid].num_uses = n;
- }
- if (refs_for_insn_df + (df->def_id + df->use_id) < act_refs)
- abort ();
-}
-
-/* Free the insn_df structures. */
-
-static void
-free_insn_info (void)
-{
- free (refs_for_insn_df);
- refs_for_insn_df = NULL;
- free (insn_df);
- insn_df = NULL;
- insn_df_max_uid = 0;
-}
-
-/* Search WEB for a subweb, which represents REG. REG needs to
- be a SUBREG, and the inner reg of it needs to be the one which is
- represented by WEB. Returns the matching subweb or NULL. */
-
-struct web *
-find_subweb (struct web *web, rtx reg)
-{
- struct web *w;
- if (GET_CODE (reg) != SUBREG)
- abort ();
- for (w = web->subreg_next; w; w = w->subreg_next)
- if (GET_MODE (w->orig_x) == GET_MODE (reg)
- && SUBREG_BYTE (w->orig_x) == SUBREG_BYTE (reg))
- return w;
- return NULL;
-}
-
-/* Similar to find_subweb(), but matches according to SIZE_WORD,
- a collection of the needed size and offset (in bytes). */
-
-struct web *
-find_subweb_2 (struct web *web, unsigned int size_word)
-{
- struct web *w = web;
- if (size_word == GET_MODE_SIZE (GET_MODE (web->orig_x)))
- /* size_word == size means BYTE_BEGIN(size_word) == 0. */
- return web;
- for (w = web->subreg_next; w; w = w->subreg_next)
- {
- unsigned int bl = rtx_to_bits (w->orig_x);
- if (size_word == bl)
- return w;
- }
- return NULL;
-}
-
-/* Returns the superweb for SUBWEB. */
-
-struct web *
-find_web_for_subweb_1 (struct web *subweb)
-{
- while (subweb->parent_web)
- subweb = subweb->parent_web;
- return subweb;
-}
-
-/* Determine if two hard register sets intersect.
- Return 1 if they do. */
-
-int
-hard_regs_intersect_p (HARD_REG_SET *a, HARD_REG_SET *b)
-{
- HARD_REG_SET c;
- COPY_HARD_REG_SET (c, *a);
- AND_HARD_REG_SET (c, *b);
- GO_IF_HARD_REG_SUBSET (c, reg_class_contents[(int) NO_REGS], lose);
- return 1;
-lose:
- return 0;
-}
-
-/* Allocate and initialize the memory necessary for one pass of the
- register allocator. */
-
-static void
-alloc_mem (struct df *df)
-{
- int i;
- ra_build_realloc (df);
- if (!live_at_end)
- {
- live_at_end = xmalloc ((last_basic_block + 2) * sizeof (bitmap));
- for (i = 0; i < last_basic_block + 2; i++)
- live_at_end[i] = BITMAP_XMALLOC ();
- live_at_end += 2;
- }
- create_insn_info (df);
-}
-
-/* Free the memory which isn't necessary for the next pass. */
-
-static void
-free_mem (struct df *df ATTRIBUTE_UNUSED)
-{
- free_insn_info ();
- ra_build_free ();
-}
-
-/* Free all memory allocated for the register allocator. Used, when
- it's done. */
-
-static void
-free_all_mem (struct df *df)
-{
- unsigned int i;
- live_at_end -= 2;
- for (i = 0; i < (unsigned)last_basic_block + 2; i++)
- BITMAP_XFREE (live_at_end[i]);
- free (live_at_end);
-
- ra_colorize_free_all ();
- ra_build_free_all (df);
- obstack_free (&ra_obstack, NULL);
-}
-
-static long ticks_build;
-static long ticks_rebuild;
-
-/* Perform one pass of allocation. Returns nonzero, if some spill code
- was added, i.e. if the allocator needs to rerun. */
-
-static int
-one_pass (struct df *df, int rebuild)
-{
- long ticks = clock ();
- int something_spilled;
- remember_conflicts = 0;
-
- /* Build the complete interference graph, or if this is not the first
- pass, rebuild it incrementally. */
- build_i_graph (df);
-
- /* From now on, if we create new conflicts, we need to remember the
- initial list of conflicts per web. */
- remember_conflicts = 1;
- if (!rebuild)
- dump_igraph_machine ();
-
- /* Colorize the I-graph. This results in either a list of
- spilled_webs, in which case we need to run the spill phase, and
- rerun the allocator, or that list is empty, meaning we are done. */
- ra_colorize_graph (df);
-
- last_max_uid = get_max_uid ();
- /* actual_spill() might change WEBS(SPILLED) and even empty it,
- so we need to remember it's state. */
- something_spilled = !!WEBS(SPILLED);
-
- /* Add spill code if necessary. */
- if (something_spilled)
- actual_spill ();
-
- ticks = clock () - ticks;
- if (rebuild)
- ticks_rebuild += ticks;
- else
- ticks_build += ticks;
- return something_spilled;
-}
-
-/* Initialize various arrays for the register allocator. */
-
-static void
-init_ra (void)
-{
- int i;
- HARD_REG_SET rs;
-#ifdef ELIMINABLE_REGS
- static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
- unsigned int j;
-#endif
- int need_fp
- = (! flag_omit_frame_pointer
- || (current_function_calls_alloca && EXIT_IGNORE_STACK)
- || FRAME_POINTER_REQUIRED);
-
- ra_colorize_init ();
-
- /* We can't ever use any of the fixed regs. */
- COPY_HARD_REG_SET (never_use_colors, fixed_reg_set);
-
- /* Additionally don't even try to use hardregs, which we already
- know are not eliminable. This includes also either the
- hard framepointer or all regs which are eliminable into the
- stack pointer, if need_fp is set. */
-#ifdef ELIMINABLE_REGS
- for (j = 0; j < ARRAY_SIZE (eliminables); j++)
- {
- if (! CAN_ELIMINATE (eliminables[j].from, eliminables[j].to)
- || (eliminables[j].to == STACK_POINTER_REGNUM && need_fp))
- for (i = HARD_REGNO_NREGS (eliminables[j].from, Pmode); i--;)
- SET_HARD_REG_BIT (never_use_colors, eliminables[j].from + i);
- }
-#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
- if (need_fp)
- for (i = HARD_REGNO_NREGS (HARD_FRAME_POINTER_REGNUM, Pmode); i--;)
- SET_HARD_REG_BIT (never_use_colors, HARD_FRAME_POINTER_REGNUM + i);
-#endif
-
-#else
- if (need_fp)
- for (i = HARD_REGNO_NREGS (FRAME_POINTER_REGNUM, Pmode); i--;)
- SET_HARD_REG_BIT (never_use_colors, FRAME_POINTER_REGNUM + i);
-#endif
-
- /* Stack and argument pointer are also rather useless to us. */
- for (i = HARD_REGNO_NREGS (STACK_POINTER_REGNUM, Pmode); i--;)
- SET_HARD_REG_BIT (never_use_colors, STACK_POINTER_REGNUM + i);
-
- for (i = HARD_REGNO_NREGS (ARG_POINTER_REGNUM, Pmode); i--;)
- SET_HARD_REG_BIT (never_use_colors, ARG_POINTER_REGNUM + i);
-
- for (i = 0; i < 256; i++)
- {
- unsigned char byte = ((unsigned) i) & 0xFF;
- unsigned char count = 0;
- while (byte)
- {
- if (byte & 1)
- count++;
- byte >>= 1;
- }
- byte2bitcount[i] = count;
- }
-
- for (i = 0; i < N_REG_CLASSES; i++)
- {
- int size;
- COPY_HARD_REG_SET (rs, reg_class_contents[i]);
- AND_COMPL_HARD_REG_SET (rs, never_use_colors);
- size = hard_regs_count (rs);
- num_free_regs[i] = size;
- COPY_HARD_REG_SET (usable_regs[i], rs);
- }
-
- /* Setup hardregs_for_mode[].
- We are not interested only in the beginning of a multi-reg, but in
- all the hardregs involved. Maybe HARD_REGNO_MODE_OK() only ok's
- for beginnings. */
- for (i = 0; i < NUM_MACHINE_MODES; i++)
- {
- int reg, size;
- CLEAR_HARD_REG_SET (rs);
- for (reg = 0; reg < FIRST_PSEUDO_REGISTER; reg++)
- if (HARD_REGNO_MODE_OK (reg, i)
- /* Ignore VOIDmode and similar things. */
- && (size = HARD_REGNO_NREGS (reg, i)) != 0
- && (reg + size) <= FIRST_PSEUDO_REGISTER)
- {
- while (size--)
- SET_HARD_REG_BIT (rs, reg + size);
- }
- COPY_HARD_REG_SET (hardregs_for_mode[i], rs);
- }
-
- CLEAR_HARD_REG_SET (invalid_mode_change_regs);
-#ifdef CANNOT_CHANGE_MODE_CLASS
- if (0)
- for (i = 0; i < NUM_MACHINE_MODES; i++)
- {
- enum machine_mode from = (enum machine_mode) i;
- enum machine_mode to;
- for (to = VOIDmode; to < MAX_MACHINE_MODE; ++to)
- {
- int r;
- for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
- if (REG_CANNOT_CHANGE_MODE_P (from, to, r))
- SET_HARD_REG_BIT (invalid_mode_change_regs, r);
- }
- }
-#endif
-
- for (an_unusable_color = 0; an_unusable_color < FIRST_PSEUDO_REGISTER;
- an_unusable_color++)
- if (TEST_HARD_REG_BIT (never_use_colors, an_unusable_color))
- break;
- if (an_unusable_color == FIRST_PSEUDO_REGISTER)
- abort ();
-
- orig_max_uid = get_max_uid ();
- compute_bb_for_insn ();
- ra_reg_renumber = NULL;
- insns_with_deaths = sbitmap_alloc (orig_max_uid);
- death_insns_max_uid = orig_max_uid;
- sbitmap_ones (insns_with_deaths);
- gcc_obstack_init (&ra_obstack);
-}
-
-/* Check the consistency of DF. This aborts if it violates some
- invariances we expect. */
-
-static void
-check_df (struct df *df)
-{
- struct df_link *link;
- rtx insn;
- int regno;
- unsigned int ui;
- bitmap b = BITMAP_XMALLOC ();
- bitmap empty_defs = BITMAP_XMALLOC ();
- bitmap empty_uses = BITMAP_XMALLOC ();
-
- /* Collect all the IDs of NULL references in the ID->REF arrays,
- as df.c leaves them when updating the df structure. */
- for (ui = 0; ui < df->def_id; ui++)
- if (!df->defs[ui])
- bitmap_set_bit (empty_defs, ui);
- for (ui = 0; ui < df->use_id; ui++)
- if (!df->uses[ui])
- bitmap_set_bit (empty_uses, ui);
-
- /* For each insn we check if the chain of references contain each
- ref only once, doesn't contain NULL refs, or refs whose ID is invalid
- (it df->refs[id] element is NULL). */
- for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
- if (INSN_P (insn))
- {
- bitmap_clear (b);
- for (link = DF_INSN_DEFS (df, insn); link; link = link->next)
- if (!link->ref || bitmap_bit_p (empty_defs, DF_REF_ID (link->ref))
- || bitmap_bit_p (b, DF_REF_ID (link->ref)))
- abort ();
- else
- bitmap_set_bit (b, DF_REF_ID (link->ref));
-
- bitmap_clear (b);
- for (link = DF_INSN_USES (df, insn); link; link = link->next)
- if (!link->ref || bitmap_bit_p (empty_uses, DF_REF_ID (link->ref))
- || bitmap_bit_p (b, DF_REF_ID (link->ref)))
- abort ();
- else
- bitmap_set_bit (b, DF_REF_ID (link->ref));
- }
-
- /* Now the same for the chains per register number. */
- for (regno = 0; regno < max_reg_num (); regno++)
- {
- bitmap_clear (b);
- for (link = df->regs[regno].defs; link; link = link->next)
- if (!link->ref || bitmap_bit_p (empty_defs, DF_REF_ID (link->ref))
- || bitmap_bit_p (b, DF_REF_ID (link->ref)))
- abort ();
- else
- bitmap_set_bit (b, DF_REF_ID (link->ref));
-
- bitmap_clear (b);
- for (link = df->regs[regno].uses; link; link = link->next)
- if (!link->ref || bitmap_bit_p (empty_uses, DF_REF_ID (link->ref))
- || bitmap_bit_p (b, DF_REF_ID (link->ref)))
- abort ();
- else
- bitmap_set_bit (b, DF_REF_ID (link->ref));
- }
-
- BITMAP_XFREE (empty_uses);
- BITMAP_XFREE (empty_defs);
- BITMAP_XFREE (b);
-}
-
-/* Main register allocator entry point. */
-
-void
-reg_alloc (void)
-{
- int changed;
- FILE *ra_dump_file = rtl_dump_file;
- rtx last = get_last_insn ();
-
- if (! INSN_P (last))
- last = prev_real_insn (last);
- /* If this is an empty function we shouldn't do all the following,
- but instead just setup what's necessary, and return. */
-
- /* We currently rely on the existence of the return value USE as
- one of the last insns. Add it if it's not there anymore. */
- if (last)
- {
- edge e;
- for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
- {
- basic_block bb = e->src;
- last = BB_END (bb);
- if (!INSN_P (last) || GET_CODE (PATTERN (last)) != USE)
- {
- rtx insns;
- start_sequence ();
- use_return_register ();
- insns = get_insns ();
- end_sequence ();
- emit_insn_after (insns, last);
- }
- }
- }
-
- /* Setup debugging levels. */
- switch (0)
- {
- /* Some useful presets of the debug level, I often use. */
- case 0: debug_new_regalloc = DUMP_EVER; break;
- case 1: debug_new_regalloc = DUMP_COSTS; break;
- case 2: debug_new_regalloc = DUMP_IGRAPH_M; break;
- case 3: debug_new_regalloc = DUMP_COLORIZE + DUMP_COSTS; break;
- case 4: debug_new_regalloc = DUMP_COLORIZE + DUMP_COSTS + DUMP_WEBS;
- break;
- case 5: debug_new_regalloc = DUMP_FINAL_RTL + DUMP_COSTS +
- DUMP_CONSTRAINTS;
- break;
- case 6: debug_new_regalloc = DUMP_VALIDIFY; break;
- }
- if (!rtl_dump_file)
- debug_new_regalloc = 0;
-
- /* Run regclass first, so we know the preferred and alternate classes
- for each pseudo. Deactivate emitting of debug info, if it's not
- explicitly requested. */
- if ((debug_new_regalloc & DUMP_REGCLASS) == 0)
- rtl_dump_file = NULL;
- regclass (get_insns (), max_reg_num (), rtl_dump_file);
- rtl_dump_file = ra_dump_file;
-
- /* We don't use those NOTEs, and as we anyway change all registers,
- they only make problems later. */
- count_or_remove_death_notes (NULL, 1);
-
- /* Initialize the different global arrays and regsets. */
- init_ra ();
-
- /* And some global variables. */
- ra_pass = 0;
- no_new_pseudos = 0;
- max_normal_pseudo = (unsigned) max_reg_num ();
- ra_rewrite_init ();
- last_def_id = 0;
- last_use_id = 0;
- last_num_webs = 0;
- last_max_uid = 0;
- last_check_uses = NULL;
- live_at_end = NULL;
- WEBS(INITIAL) = NULL;
- WEBS(FREE) = NULL;
- memset (hardreg2web, 0, sizeof (hardreg2web));
- ticks_build = ticks_rebuild = 0;
-
- /* The default is to use optimistic coalescing with interference
- region spilling, without biased coloring. */
- flag_ra_biased = 0;
- flag_ra_spill_every_use = 0;
- flag_ra_improved_spilling = 1;
- flag_ra_ir_spilling = 1;
- flag_ra_break_aliases = 0;
- flag_ra_optimistic_coalescing = 1;
- flag_ra_merge_spill_costs = 1;
- if (flag_ra_optimistic_coalescing)
- flag_ra_break_aliases = 1;
- flag_ra_dump_notes = 0;
-
- /* Allocate the global df structure. */
- df = df_init ();
-
- /* This is the main loop, calling one_pass as long as there are still
- some spilled webs. */
- do
- {
- ra_debug_msg (DUMP_NEARLY_EVER, "RegAlloc Pass %d\n\n", ra_pass);
- if (ra_pass++ > 40)
- internal_error ("Didn't find a coloring.\n");
-
- /* First collect all the register refs and put them into
- chains per insn, and per regno. In later passes only update
- that info from the new and modified insns. */
- df_analyse (df, (ra_pass == 1) ? 0 : (bitmap) -1,
- DF_HARD_REGS | DF_RD_CHAIN | DF_RU_CHAIN | DF_FOR_REGALLOC);
-
- if ((debug_new_regalloc & DUMP_DF) != 0)
- {
- rtx insn;
- df_dump (df, DF_HARD_REGS, rtl_dump_file);
- for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
- if (INSN_P (insn))
- df_insn_debug_regno (df, insn, rtl_dump_file);
- }
- check_df (df);
-
- /* Now allocate the memory needed for this pass, or (if it's not the
- first pass), reallocate only additional memory. */
- alloc_mem (df);
-
- /* Build and colorize the interference graph, and possibly emit
- spill insns. This also might delete certain move insns. */
- changed = one_pass (df, ra_pass > 1);
-
- /* If that produced no changes, the graph was colorizable. */
- if (!changed)
- {
- /* Change the insns to refer to the new pseudos (one per web). */
- emit_colors (df);
- /* Already setup a preliminary reg_renumber[] array, but don't
- free our own version. reg_renumber[] will again be destroyed
- later. We right now need it in dump_constraints() for
- constrain_operands(1) whose subproc sometimes reference
- it (because we are checking strictly, i.e. as if
- after reload). */
- setup_renumber (0);
- /* Delete some more of the coalesced moves. */
- delete_moves ();
- dump_constraints ();
- }
- else
- {
- /* If there were changes, this means spill code was added,
- therefore repeat some things, including some initialization
- of global data structures. */
- if ((debug_new_regalloc & DUMP_REGCLASS) == 0)
- rtl_dump_file = NULL;
- /* We have new pseudos (the stackwebs). */
- allocate_reg_info (max_reg_num (), FALSE, FALSE);
- /* And new insns. */
- compute_bb_for_insn ();
- /* Some of them might be dead. */
- delete_trivially_dead_insns (get_insns (), max_reg_num ());
- /* Those new pseudos need to have their REFS count set. */
- reg_scan_update (get_insns (), NULL, max_regno);
- max_regno = max_reg_num ();
- /* And they need useful classes too. */
- regclass (get_insns (), max_reg_num (), rtl_dump_file);
- rtl_dump_file = ra_dump_file;
-
- /* Remember the number of defs and uses, so we can distinguish
- new from old refs in the next pass. */
- last_def_id = df->def_id;
- last_use_id = df->use_id;
- }
-
- /* Output the graph, and possibly the current insn sequence. */
- dump_ra (df);
- if (changed && (debug_new_regalloc & DUMP_RTL) != 0)
- {
- ra_print_rtl_with_bb (rtl_dump_file, get_insns ());
- fflush (rtl_dump_file);
- }
-
- /* Reset the web lists. */
- reset_lists ();
- free_mem (df);
- }
- while (changed);
-
- /* We are done with allocation, free all memory and output some
- debug info. */
- free_all_mem (df);
- df_finish (df);
- if ((debug_new_regalloc & DUMP_RESULTS) == 0)
- dump_cost (DUMP_COSTS);
- ra_debug_msg (DUMP_COSTS, "ticks for build-phase: %ld\n", ticks_build);
- ra_debug_msg (DUMP_COSTS, "ticks for rebuild-phase: %ld\n", ticks_rebuild);
- if ((debug_new_regalloc & (DUMP_FINAL_RTL | DUMP_RTL)) != 0)
- ra_print_rtl_with_bb (rtl_dump_file, get_insns ());
-
- /* We might have new pseudos, so allocate the info arrays for them. */
- if ((debug_new_regalloc & DUMP_SM) == 0)
- rtl_dump_file = NULL;
- no_new_pseudos = 0;
- allocate_reg_info (max_reg_num (), FALSE, FALSE);
- no_new_pseudos = 1;
- rtl_dump_file = ra_dump_file;
-
- /* Some spill insns could've been inserted after trapping calls, i.e.
- at the end of a basic block, which really ends at that call.
- Fixup that breakages by adjusting basic block boundaries. */
- fixup_abnormal_edges ();
-
- /* Cleanup the flow graph. */
- if ((debug_new_regalloc & DUMP_LAST_FLOW) == 0)
- rtl_dump_file = NULL;
- life_analysis (get_insns (), rtl_dump_file,
- PROP_DEATH_NOTES | PROP_LOG_LINKS | PROP_REG_INFO);
- cleanup_cfg (CLEANUP_EXPENSIVE);
- recompute_reg_usage (get_insns (), TRUE);
- if (rtl_dump_file)
- dump_flow_info (rtl_dump_file);
- rtl_dump_file = ra_dump_file;
-
- /* update_equiv_regs() can't be called after register allocation.
- It might delete some pseudos, and insert other insns setting
- up those pseudos in different places. This of course screws up
- the allocation because that may destroy a hardreg for another
- pseudo.
- XXX we probably should do something like that on our own. I.e.
- creating REG_EQUIV notes. */
- /*update_equiv_regs ();*/
-
- /* Setup the reg_renumber[] array for reload. */
- setup_renumber (1);
- sbitmap_free (insns_with_deaths);
-
- /* Remove REG_DEAD notes which are incorrectly set. See the docu
- of that function. */
- remove_suspicious_death_notes ();
-
- if ((debug_new_regalloc & DUMP_LAST_RTL) != 0)
- ra_print_rtl_with_bb (rtl_dump_file, get_insns ());
- dump_static_insn_cost (rtl_dump_file,
- "after allocation/spilling, before reload", NULL);
-
- /* Allocate the reg_equiv_memory_loc array for reload. */
- reg_equiv_memory_loc = xcalloc (max_regno, sizeof (rtx));
- /* And possibly initialize it. */
- allocate_initial_values (reg_equiv_memory_loc);
- /* And one last regclass pass just before reload. */
- regclass (get_insns (), max_reg_num (), rtl_dump_file);
-}
-
-/*
-vim:cinoptions={.5s,g0,p5,t0,(0,^-0.5s,n-0.5s:tw=78:cindent:sw=4:
-*/
OpenPOWER on IntegriCloud