2005-01-20 Michael Koch <konqueror@gmx.de>
[official-gcc.git] / gcc / ra.c
blobacc1be57e335fab43d08c9545825d0599677a33a
1 /* Graph coloring register allocator
2 Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
3 Contributed by Michael Matz <matz@suse.de>
4 and Daniel Berlin <dan@cgsoftware.com>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under the
9 terms of the GNU General Public License as published by the Free Software
10 Foundation; either version 2, or (at your option) any later version.
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
14 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
15 details.
17 You should have received a copy of the GNU General Public License along
18 with GCC; see the file COPYING. If not, write to the Free Software
19 Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "rtl.h"
26 #include "tm_p.h"
27 #include "insn-config.h"
28 #include "recog.h"
29 #include "reload.h"
30 #include "integrate.h"
31 #include "function.h"
32 #include "regs.h"
33 #include "obstack.h"
34 #include "hard-reg-set.h"
35 #include "basic-block.h"
36 #include "df.h"
37 #include "expr.h"
38 #include "output.h"
39 #include "toplev.h"
40 #include "flags.h"
41 #include "ra.h"
43 /* This is the toplevel file of a graph coloring register allocator.
44 It is able to act like a George & Appel allocator, i.e. with iterative
45 coalescing plus spill coalescing/propagation.
46 And it can act as a traditional Briggs allocator, although with
47 optimistic coalescing. Additionally it has a custom pass, which
48 tries to reduce the overall cost of the colored graph.
50 We support two modes of spilling: spill-everywhere, which is extremely
51 fast, and interference region spilling, which reduces spill code to a
52 large extent, but is slower.
54 Helpful documents:
56 Briggs, P., Cooper, K. D., and Torczon, L. 1994. Improvements to graph
57 coloring register allocation. ACM Trans. Program. Lang. Syst. 16, 3 (May),
58 428-455.
60 Bergner, P., Dahl, P., Engebretsen, D., and O'Keefe, M. 1997. Spill code
61 minimization via interference region spilling. In Proc. ACM SIGPLAN '97
62 Conf. on Prog. Language Design and Implementation. ACM, 287-295.
64 George, L., Appel, A.W. 1996. Iterated register coalescing.
65 ACM Trans. Program. Lang. Syst. 18, 3 (May), 300-324.
69 /* This file contains the main entry point (reg_alloc), some helper routines
70 used by more than one file of the register allocator, and the toplevel
71 driver procedure (one_pass). */
73 /* Things, one might do somewhen:
75 * Lattice based rematerialization
76 * create definitions of ever-life regs at the beginning of
77 the insn chain
78 * insert loads as soon, stores as late as possible
79 * insert spill insns as outward as possible (either looptree, or LCM)
80 * reuse stack-slots
81 * delete coalesced insns. Partly done. The rest can only go, when we get
82 rid of reload.
83 * don't destroy coalescing information completely when spilling
84 * use the constraints from asms
87 static struct obstack ra_obstack;
88 static void create_insn_info (struct df *);
89 static void free_insn_info (void);
90 static void alloc_mem (struct df *);
91 static void free_mem (struct df *);
92 static void free_all_mem (struct df *df);
93 static int one_pass (struct df *, int);
94 static void check_df (struct df *);
95 static void init_ra (void);
97 void reg_alloc (void);
99 /* These global variables are "internal" to the register allocator.
100 They are all documented at their declarations in ra.h. */
102 /* Somewhen we want to get rid of one of those sbitmaps.
103 (for now I need the sup_igraph to note if there is any conflict between
104 parts of webs at all. I can't use igraph for this, as there only the real
105 conflicts are noted.) This is only used to prevent coalescing two
106 conflicting webs, were only parts of them are in conflict. */
107 sbitmap igraph;
108 sbitmap sup_igraph;
110 /* Note the insns not inserted by the allocator, where we detected any
111 deaths of pseudos. It is used to detect closeness of defs and uses.
112 In the first pass this is empty (we could initialize it from REG_DEAD
113 notes), in the other passes it is left from the pass before. */
114 sbitmap insns_with_deaths;
115 int death_insns_max_uid;
117 struct web_part *web_parts;
119 unsigned int num_webs;
120 unsigned int num_subwebs;
121 unsigned int num_allwebs;
122 struct web **id2web;
123 struct web *hardreg2web[FIRST_PSEUDO_REGISTER];
124 struct web **def2web;
125 struct web **use2web;
126 struct move_list *wl_moves;
127 int ra_max_regno;
128 short *ra_reg_renumber;
129 struct df *df;
130 bitmap *live_at_end;
131 int ra_pass;
132 unsigned int max_normal_pseudo;
133 int an_unusable_color;
135 /* The different lists on which a web can be (based on the type). */
136 struct dlist *web_lists[(int) LAST_NODE_TYPE];
138 unsigned int last_def_id;
139 unsigned int last_use_id;
140 unsigned int last_num_webs;
141 int last_max_uid;
142 sbitmap last_check_uses;
143 unsigned int remember_conflicts;
145 int orig_max_uid;
147 HARD_REG_SET never_use_colors;
148 HARD_REG_SET usable_regs[N_REG_CLASSES];
149 unsigned int num_free_regs[N_REG_CLASSES];
150 HARD_REG_SET hardregs_for_mode[NUM_MACHINE_MODES];
151 HARD_REG_SET invalid_mode_change_regs;
152 unsigned char byte2bitcount[256];
154 unsigned int debug_new_regalloc = -1;
155 int flag_ra_biased = 0;
156 int flag_ra_improved_spilling = 0;
157 int flag_ra_ir_spilling = 0;
158 int flag_ra_optimistic_coalescing = 0;
159 int flag_ra_break_aliases = 0;
160 int flag_ra_merge_spill_costs = 0;
161 int flag_ra_spill_every_use = 0;
162 int flag_ra_dump_notes = 0;
164 /* Fast allocation of small objects, which live until the allocator
165 is done. Allocate an object of SIZE bytes. */
167 void *
168 ra_alloc (size_t size)
170 return obstack_alloc (&ra_obstack, size);
173 /* Like ra_alloc(), but clear the returned memory. */
175 void *
176 ra_calloc (size_t size)
178 void *p = obstack_alloc (&ra_obstack, size);
179 memset (p, 0, size);
180 return p;
183 /* Returns the number of hardregs in HARD_REG_SET RS. */
186 hard_regs_count (HARD_REG_SET rs)
188 int count = 0;
189 #ifdef HARD_REG_SET
190 while (rs)
192 unsigned char byte = rs & 0xFF;
193 rs >>= 8;
194 /* Avoid memory access, if nothing is set. */
195 if (byte)
196 count += byte2bitcount[byte];
198 #else
199 unsigned int ofs;
200 for (ofs = 0; ofs < HARD_REG_SET_LONGS; ofs++)
202 HARD_REG_ELT_TYPE elt = rs[ofs];
203 while (elt)
205 unsigned char byte = elt & 0xFF;
206 elt >>= 8;
207 if (byte)
208 count += byte2bitcount[byte];
211 #endif
212 return count;
215 /* Basically like emit_move_insn (i.e. validifies constants and such),
216 but also handle MODE_CC moves (but then the operands must already
217 be basically valid. */
220 ra_emit_move_insn (rtx x, rtx y)
222 enum machine_mode mode = GET_MODE (x);
223 if (GET_MODE_CLASS (mode) == MODE_CC)
224 return emit_insn (gen_move_insn (x, y));
225 else
226 return emit_move_insn (x, y);
229 int insn_df_max_uid;
230 struct ra_insn_info *insn_df;
231 static struct ref **refs_for_insn_df;
233 /* Create the insn_df structure for each insn to have fast access to
234 all valid defs and uses in an insn. */
236 static void
237 create_insn_info (struct df *df)
239 rtx insn;
240 struct ref **act_refs;
241 insn_df_max_uid = get_max_uid ();
242 insn_df = xcalloc (insn_df_max_uid, sizeof (insn_df[0]));
243 refs_for_insn_df = xcalloc (df->def_id + df->use_id, sizeof (struct ref *));
244 act_refs = refs_for_insn_df;
245 /* We create those things backwards to mimic the order in which
246 the insns are visited in rewrite_program2() and live_in(). */
247 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
249 int uid = INSN_UID (insn);
250 unsigned int n;
251 struct df_link *link;
252 if (!INSN_P (insn))
253 continue;
254 for (n = 0, link = DF_INSN_DEFS (df, insn); link; link = link->next)
255 if (link->ref
256 && (DF_REF_REGNO (link->ref) >= FIRST_PSEUDO_REGISTER
257 || !TEST_HARD_REG_BIT (never_use_colors,
258 DF_REF_REGNO (link->ref))))
260 if (n == 0)
261 insn_df[uid].defs = act_refs;
262 insn_df[uid].defs[n++] = link->ref;
264 act_refs += n;
265 insn_df[uid].num_defs = n;
266 for (n = 0, link = DF_INSN_USES (df, insn); link; link = link->next)
267 if (link->ref
268 && (DF_REF_REGNO (link->ref) >= FIRST_PSEUDO_REGISTER
269 || !TEST_HARD_REG_BIT (never_use_colors,
270 DF_REF_REGNO (link->ref))))
272 if (n == 0)
273 insn_df[uid].uses = act_refs;
274 insn_df[uid].uses[n++] = link->ref;
276 act_refs += n;
277 insn_df[uid].num_uses = n;
279 if (refs_for_insn_df + (df->def_id + df->use_id) < act_refs)
280 abort ();
283 /* Free the insn_df structures. */
285 static void
286 free_insn_info (void)
288 free (refs_for_insn_df);
289 refs_for_insn_df = NULL;
290 free (insn_df);
291 insn_df = NULL;
292 insn_df_max_uid = 0;
295 /* Search WEB for a subweb, which represents REG. REG needs to
296 be a SUBREG, and the inner reg of it needs to be the one which is
297 represented by WEB. Returns the matching subweb or NULL. */
299 struct web *
300 find_subweb (struct web *web, rtx reg)
302 struct web *w;
303 if (GET_CODE (reg) != SUBREG)
304 abort ();
305 for (w = web->subreg_next; w; w = w->subreg_next)
306 if (GET_MODE (w->orig_x) == GET_MODE (reg)
307 && SUBREG_BYTE (w->orig_x) == SUBREG_BYTE (reg))
308 return w;
309 return NULL;
312 /* Similar to find_subweb(), but matches according to SIZE_WORD,
313 a collection of the needed size and offset (in bytes). */
315 struct web *
316 find_subweb_2 (struct web *web, unsigned int size_word)
318 struct web *w = web;
319 if (size_word == GET_MODE_SIZE (GET_MODE (web->orig_x)))
320 /* size_word == size means BYTE_BEGIN(size_word) == 0. */
321 return web;
322 for (w = web->subreg_next; w; w = w->subreg_next)
324 unsigned int bl = rtx_to_bits (w->orig_x);
325 if (size_word == bl)
326 return w;
328 return NULL;
331 /* Returns the superweb for SUBWEB. */
333 struct web *
334 find_web_for_subweb_1 (struct web *subweb)
336 while (subweb->parent_web)
337 subweb = subweb->parent_web;
338 return subweb;
341 /* Determine if two hard register sets intersect.
342 Return 1 if they do. */
345 hard_regs_intersect_p (HARD_REG_SET *a, HARD_REG_SET *b)
347 HARD_REG_SET c;
348 COPY_HARD_REG_SET (c, *a);
349 AND_HARD_REG_SET (c, *b);
350 GO_IF_HARD_REG_SUBSET (c, reg_class_contents[(int) NO_REGS], lose);
351 return 1;
352 lose:
353 return 0;
356 /* Allocate and initialize the memory necessary for one pass of the
357 register allocator. */
359 static void
360 alloc_mem (struct df *df)
362 int i;
363 ra_build_realloc (df);
364 if (!live_at_end)
366 live_at_end = xmalloc ((last_basic_block + 2) * sizeof (bitmap));
367 for (i = 0; i < last_basic_block + 2; i++)
368 live_at_end[i] = BITMAP_XMALLOC ();
369 live_at_end += 2;
371 create_insn_info (df);
374 /* Free the memory which isn't necessary for the next pass. */
376 static void
377 free_mem (struct df *df ATTRIBUTE_UNUSED)
379 free_insn_info ();
380 ra_build_free ();
383 /* Free all memory allocated for the register allocator. Used, when
384 it's done. */
386 static void
387 free_all_mem (struct df *df)
389 unsigned int i;
390 live_at_end -= 2;
391 for (i = 0; i < (unsigned)last_basic_block + 2; i++)
392 BITMAP_XFREE (live_at_end[i]);
393 free (live_at_end);
395 ra_colorize_free_all ();
396 ra_build_free_all (df);
397 obstack_free (&ra_obstack, NULL);
400 static long ticks_build;
401 static long ticks_rebuild;
403 /* Perform one pass of allocation. Returns nonzero, if some spill code
404 was added, i.e. if the allocator needs to rerun. */
406 static int
407 one_pass (struct df *df, int rebuild)
409 long ticks = clock ();
410 int something_spilled;
411 remember_conflicts = 0;
413 /* Build the complete interference graph, or if this is not the first
414 pass, rebuild it incrementally. */
415 build_i_graph (df);
417 /* From now on, if we create new conflicts, we need to remember the
418 initial list of conflicts per web. */
419 remember_conflicts = 1;
420 if (!rebuild)
421 dump_igraph_machine ();
423 /* Colorize the I-graph. This results in either a list of
424 spilled_webs, in which case we need to run the spill phase, and
425 rerun the allocator, or that list is empty, meaning we are done. */
426 ra_colorize_graph (df);
428 last_max_uid = get_max_uid ();
429 /* actual_spill() might change WEBS(SPILLED) and even empty it,
430 so we need to remember it's state. */
431 something_spilled = !!WEBS(SPILLED);
433 /* Add spill code if necessary. */
434 if (something_spilled)
435 actual_spill ();
437 ticks = clock () - ticks;
438 if (rebuild)
439 ticks_rebuild += ticks;
440 else
441 ticks_build += ticks;
442 return something_spilled;
445 /* Initialize various arrays for the register allocator. */
447 static void
448 init_ra (void)
450 int i;
451 HARD_REG_SET rs;
452 #ifdef ELIMINABLE_REGS
453 static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
454 unsigned int j;
455 #endif
456 int need_fp
457 = (! flag_omit_frame_pointer
458 || (current_function_calls_alloca && EXIT_IGNORE_STACK)
459 || FRAME_POINTER_REQUIRED);
461 ra_colorize_init ();
463 /* We can't ever use any of the fixed regs. */
464 COPY_HARD_REG_SET (never_use_colors, fixed_reg_set);
466 /* Additionally don't even try to use hardregs, which we already
467 know are not eliminable. This includes also either the
468 hard framepointer or all regs which are eliminable into the
469 stack pointer, if need_fp is set. */
470 #ifdef ELIMINABLE_REGS
471 for (j = 0; j < ARRAY_SIZE (eliminables); j++)
473 if (! CAN_ELIMINATE (eliminables[j].from, eliminables[j].to)
474 || (eliminables[j].to == STACK_POINTER_REGNUM && need_fp))
475 for (i = hard_regno_nregs[eliminables[j].from][Pmode]; i--;)
476 SET_HARD_REG_BIT (never_use_colors, eliminables[j].from + i);
478 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
479 if (need_fp)
480 for (i = hard_regno_nregs[HARD_FRAME_POINTER_REGNUM][Pmode]; i--;)
481 SET_HARD_REG_BIT (never_use_colors, HARD_FRAME_POINTER_REGNUM + i);
482 #endif
484 #else
485 if (need_fp)
486 for (i = hard_regno_nregs[FRAME_POINTER_REGNUM][Pmode]; i--;)
487 SET_HARD_REG_BIT (never_use_colors, FRAME_POINTER_REGNUM + i);
488 #endif
490 /* Stack and argument pointer are also rather useless to us. */
491 for (i = hard_regno_nregs[STACK_POINTER_REGNUM][Pmode]; i--;)
492 SET_HARD_REG_BIT (never_use_colors, STACK_POINTER_REGNUM + i);
494 for (i = hard_regno_nregs[ARG_POINTER_REGNUM][Pmode]; i--;)
495 SET_HARD_REG_BIT (never_use_colors, ARG_POINTER_REGNUM + i);
497 for (i = 0; i < 256; i++)
499 unsigned char byte = ((unsigned) i) & 0xFF;
500 unsigned char count = 0;
501 while (byte)
503 if (byte & 1)
504 count++;
505 byte >>= 1;
507 byte2bitcount[i] = count;
510 for (i = 0; i < N_REG_CLASSES; i++)
512 int size;
513 COPY_HARD_REG_SET (rs, reg_class_contents[i]);
514 AND_COMPL_HARD_REG_SET (rs, never_use_colors);
515 size = hard_regs_count (rs);
516 num_free_regs[i] = size;
517 COPY_HARD_REG_SET (usable_regs[i], rs);
520 /* Setup hardregs_for_mode[].
521 We are not interested only in the beginning of a multi-reg, but in
522 all the hardregs involved. Maybe HARD_REGNO_MODE_OK() only ok's
523 for beginnings. */
524 for (i = 0; i < NUM_MACHINE_MODES; i++)
526 int reg, size;
527 CLEAR_HARD_REG_SET (rs);
528 for (reg = 0; reg < FIRST_PSEUDO_REGISTER; reg++)
529 if (HARD_REGNO_MODE_OK (reg, i)
530 /* Ignore VOIDmode and similar things. */
531 && (size = hard_regno_nregs[reg][i]) != 0
532 && (reg + size) <= FIRST_PSEUDO_REGISTER)
534 while (size--)
535 SET_HARD_REG_BIT (rs, reg + size);
537 COPY_HARD_REG_SET (hardregs_for_mode[i], rs);
540 CLEAR_HARD_REG_SET (invalid_mode_change_regs);
541 #ifdef CANNOT_CHANGE_MODE_CLASS
542 if (0)
543 for (i = 0; i < NUM_MACHINE_MODES; i++)
545 enum machine_mode from = (enum machine_mode) i;
546 enum machine_mode to;
547 for (to = VOIDmode; to < MAX_MACHINE_MODE; ++to)
549 int r;
550 for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
551 if (REG_CANNOT_CHANGE_MODE_P (from, to, r))
552 SET_HARD_REG_BIT (invalid_mode_change_regs, r);
555 #endif
557 for (an_unusable_color = 0; an_unusable_color < FIRST_PSEUDO_REGISTER;
558 an_unusable_color++)
559 if (TEST_HARD_REG_BIT (never_use_colors, an_unusable_color))
560 break;
561 if (an_unusable_color == FIRST_PSEUDO_REGISTER)
562 abort ();
564 orig_max_uid = get_max_uid ();
565 compute_bb_for_insn ();
566 ra_reg_renumber = NULL;
567 insns_with_deaths = sbitmap_alloc (orig_max_uid);
568 death_insns_max_uid = orig_max_uid;
569 sbitmap_ones (insns_with_deaths);
570 gcc_obstack_init (&ra_obstack);
573 /* Check the consistency of DF. This aborts if it violates some
574 invariances we expect. */
576 static void
577 check_df (struct df *df)
579 struct df_link *link;
580 rtx insn;
581 int regno;
582 unsigned int ui;
583 bitmap b = BITMAP_XMALLOC ();
584 bitmap empty_defs = BITMAP_XMALLOC ();
585 bitmap empty_uses = BITMAP_XMALLOC ();
587 /* Collect all the IDs of NULL references in the ID->REF arrays,
588 as df.c leaves them when updating the df structure. */
589 for (ui = 0; ui < df->def_id; ui++)
590 if (!df->defs[ui])
591 bitmap_set_bit (empty_defs, ui);
592 for (ui = 0; ui < df->use_id; ui++)
593 if (!df->uses[ui])
594 bitmap_set_bit (empty_uses, ui);
596 /* For each insn we check if the chain of references contain each
597 ref only once, doesn't contain NULL refs, or refs whose ID is invalid
598 (it df->refs[id] element is NULL). */
599 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
600 if (INSN_P (insn))
602 bitmap_clear (b);
603 for (link = DF_INSN_DEFS (df, insn); link; link = link->next)
604 if (!link->ref || bitmap_bit_p (empty_defs, DF_REF_ID (link->ref))
605 || bitmap_bit_p (b, DF_REF_ID (link->ref)))
606 abort ();
607 else
608 bitmap_set_bit (b, DF_REF_ID (link->ref));
610 bitmap_clear (b);
611 for (link = DF_INSN_USES (df, insn); link; link = link->next)
612 if (!link->ref || bitmap_bit_p (empty_uses, DF_REF_ID (link->ref))
613 || bitmap_bit_p (b, DF_REF_ID (link->ref)))
614 abort ();
615 else
616 bitmap_set_bit (b, DF_REF_ID (link->ref));
619 /* Now the same for the chains per register number. */
620 for (regno = 0; regno < max_reg_num (); regno++)
622 bitmap_clear (b);
623 for (link = df->regs[regno].defs; link; link = link->next)
624 if (!link->ref || bitmap_bit_p (empty_defs, DF_REF_ID (link->ref))
625 || bitmap_bit_p (b, DF_REF_ID (link->ref)))
626 abort ();
627 else
628 bitmap_set_bit (b, DF_REF_ID (link->ref));
630 bitmap_clear (b);
631 for (link = df->regs[regno].uses; link; link = link->next)
632 if (!link->ref || bitmap_bit_p (empty_uses, DF_REF_ID (link->ref))
633 || bitmap_bit_p (b, DF_REF_ID (link->ref)))
634 abort ();
635 else
636 bitmap_set_bit (b, DF_REF_ID (link->ref));
639 BITMAP_XFREE (empty_uses);
640 BITMAP_XFREE (empty_defs);
641 BITMAP_XFREE (b);
644 /* Main register allocator entry point. */
646 void
647 reg_alloc (void)
649 int changed;
650 FILE *ra_dump_file = dump_file;
651 rtx last = get_last_insn ();
653 if (! INSN_P (last))
654 last = prev_real_insn (last);
655 /* If this is an empty function we shouldn't do all the following,
656 but instead just setup what's necessary, and return. */
658 /* We currently rely on the existence of the return value USE as
659 one of the last insns. Add it if it's not there anymore. */
660 if (last)
662 edge e;
663 for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
665 basic_block bb = e->src;
666 last = BB_END (bb);
667 if (!INSN_P (last) || GET_CODE (PATTERN (last)) != USE)
669 rtx insns;
670 start_sequence ();
671 use_return_register ();
672 insns = get_insns ();
673 end_sequence ();
674 emit_insn_after (insns, last);
679 /* Setup debugging levels. */
680 switch (0)
682 /* Some useful presets of the debug level, I often use. */
683 case 0: debug_new_regalloc = DUMP_EVER; break;
684 case 1: debug_new_regalloc = DUMP_COSTS; break;
685 case 2: debug_new_regalloc = DUMP_IGRAPH_M; break;
686 case 3: debug_new_regalloc = DUMP_COLORIZE + DUMP_COSTS; break;
687 case 4: debug_new_regalloc = DUMP_COLORIZE + DUMP_COSTS + DUMP_WEBS;
688 break;
689 case 5: debug_new_regalloc = DUMP_FINAL_RTL + DUMP_COSTS +
690 DUMP_CONSTRAINTS;
691 break;
692 case 6: debug_new_regalloc = DUMP_VALIDIFY; break;
694 if (!dump_file)
695 debug_new_regalloc = 0;
697 /* Run regclass first, so we know the preferred and alternate classes
698 for each pseudo. Deactivate emitting of debug info, if it's not
699 explicitly requested. */
700 if ((debug_new_regalloc & DUMP_REGCLASS) == 0)
701 dump_file = NULL;
702 regclass (get_insns (), max_reg_num (), dump_file);
703 dump_file = ra_dump_file;
705 /* We don't use those NOTEs, and as we anyway change all registers,
706 they only make problems later. */
707 count_or_remove_death_notes (NULL, 1);
709 /* Initialize the different global arrays and regsets. */
710 init_ra ();
712 /* And some global variables. */
713 ra_pass = 0;
714 no_new_pseudos = 0;
715 max_normal_pseudo = (unsigned) max_reg_num ();
716 ra_rewrite_init ();
717 last_def_id = 0;
718 last_use_id = 0;
719 last_num_webs = 0;
720 last_max_uid = 0;
721 last_check_uses = NULL;
722 live_at_end = NULL;
723 WEBS(INITIAL) = NULL;
724 WEBS(FREE) = NULL;
725 memset (hardreg2web, 0, sizeof (hardreg2web));
726 ticks_build = ticks_rebuild = 0;
728 /* The default is to use optimistic coalescing with interference
729 region spilling, without biased coloring. */
730 flag_ra_biased = 0;
731 flag_ra_spill_every_use = 0;
732 flag_ra_improved_spilling = 1;
733 flag_ra_ir_spilling = 1;
734 flag_ra_break_aliases = 0;
735 flag_ra_optimistic_coalescing = 1;
736 flag_ra_merge_spill_costs = 1;
737 if (flag_ra_optimistic_coalescing)
738 flag_ra_break_aliases = 1;
739 flag_ra_dump_notes = 0;
741 /* Allocate the global df structure. */
742 df = df_init ();
744 /* This is the main loop, calling one_pass as long as there are still
745 some spilled webs. */
748 ra_debug_msg (DUMP_NEARLY_EVER, "RegAlloc Pass %d\n\n", ra_pass);
749 if (ra_pass++ > 40)
750 internal_error ("Didn't find a coloring.\n");
752 /* First collect all the register refs and put them into
753 chains per insn, and per regno. In later passes only update
754 that info from the new and modified insns. */
755 df_analyze (df, (ra_pass == 1) ? 0 : (bitmap) -1,
756 DF_HARD_REGS | DF_RD_CHAIN | DF_RU_CHAIN | DF_FOR_REGALLOC);
758 if ((debug_new_regalloc & DUMP_DF) != 0)
760 rtx insn;
761 df_dump (df, DF_HARD_REGS, dump_file);
762 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
763 if (INSN_P (insn))
764 df_insn_debug_regno (df, insn, dump_file);
766 check_df (df);
768 /* Now allocate the memory needed for this pass, or (if it's not the
769 first pass), reallocate only additional memory. */
770 alloc_mem (df);
772 /* Build and colorize the interference graph, and possibly emit
773 spill insns. This also might delete certain move insns. */
774 changed = one_pass (df, ra_pass > 1);
776 /* If that produced no changes, the graph was colorizable. */
777 if (!changed)
779 /* Change the insns to refer to the new pseudos (one per web). */
780 emit_colors (df);
781 /* Already setup a preliminary reg_renumber[] array, but don't
782 free our own version. reg_renumber[] will again be destroyed
783 later. We right now need it in dump_constraints() for
784 constrain_operands(1) whose subproc sometimes reference
785 it (because we are checking strictly, i.e. as if
786 after reload). */
787 setup_renumber (0);
788 /* Delete some more of the coalesced moves. */
789 delete_moves ();
790 dump_constraints ();
792 else
794 /* If there were changes, this means spill code was added,
795 therefore repeat some things, including some initialization
796 of global data structures. */
797 if ((debug_new_regalloc & DUMP_REGCLASS) == 0)
798 dump_file = NULL;
799 /* We have new pseudos (the stackwebs). */
800 allocate_reg_info (max_reg_num (), FALSE, FALSE);
801 /* And new insns. */
802 compute_bb_for_insn ();
803 /* Some of them might be dead. */
804 delete_trivially_dead_insns (get_insns (), max_reg_num ());
805 /* Those new pseudos need to have their REFS count set. */
806 reg_scan_update (get_insns (), NULL, max_regno);
807 max_regno = max_reg_num ();
808 /* And they need useful classes too. */
809 regclass (get_insns (), max_reg_num (), dump_file);
810 dump_file = ra_dump_file;
812 /* Remember the number of defs and uses, so we can distinguish
813 new from old refs in the next pass. */
814 last_def_id = df->def_id;
815 last_use_id = df->use_id;
818 /* Output the graph, and possibly the current insn sequence. */
819 dump_ra (df);
820 if (changed && (debug_new_regalloc & DUMP_RTL) != 0)
822 ra_print_rtl_with_bb (dump_file, get_insns ());
823 fflush (dump_file);
826 /* Reset the web lists. */
827 reset_lists ();
828 free_mem (df);
830 while (changed);
832 /* We are done with allocation, free all memory and output some
833 debug info. */
834 free_all_mem (df);
835 df_finish (df);
836 if ((debug_new_regalloc & DUMP_RESULTS) == 0)
837 dump_cost (DUMP_COSTS);
838 ra_debug_msg (DUMP_COSTS, "ticks for build-phase: %ld\n", ticks_build);
839 ra_debug_msg (DUMP_COSTS, "ticks for rebuild-phase: %ld\n", ticks_rebuild);
840 if ((debug_new_regalloc & (DUMP_FINAL_RTL | DUMP_RTL)) != 0)
841 ra_print_rtl_with_bb (dump_file, get_insns ());
843 /* We might have new pseudos, so allocate the info arrays for them. */
844 if ((debug_new_regalloc & DUMP_SM) == 0)
845 dump_file = NULL;
846 no_new_pseudos = 0;
847 allocate_reg_info (max_reg_num (), FALSE, FALSE);
848 no_new_pseudos = 1;
849 dump_file = ra_dump_file;
851 /* Some spill insns could've been inserted after trapping calls, i.e.
852 at the end of a basic block, which really ends at that call.
853 Fixup that breakages by adjusting basic block boundaries. */
854 fixup_abnormal_edges ();
856 /* Cleanup the flow graph. */
857 if ((debug_new_regalloc & DUMP_LAST_FLOW) == 0)
858 dump_file = NULL;
859 life_analysis (dump_file,
860 PROP_DEATH_NOTES | PROP_LOG_LINKS | PROP_REG_INFO);
861 cleanup_cfg (CLEANUP_EXPENSIVE);
862 recompute_reg_usage (get_insns (), TRUE);
863 if (dump_file)
864 dump_flow_info (dump_file);
865 dump_file = ra_dump_file;
867 /* update_equiv_regs() can't be called after register allocation.
868 It might delete some pseudos, and insert other insns setting
869 up those pseudos in different places. This of course screws up
870 the allocation because that may destroy a hardreg for another
871 pseudo.
872 XXX we probably should do something like that on our own. I.e.
873 creating REG_EQUIV notes. */
874 /*update_equiv_regs ();*/
876 /* Setup the reg_renumber[] array for reload. */
877 setup_renumber (1);
878 sbitmap_free (insns_with_deaths);
880 /* Remove REG_DEAD notes which are incorrectly set. See the docu
881 of that function. */
882 remove_suspicious_death_notes ();
884 if ((debug_new_regalloc & DUMP_LAST_RTL) != 0)
885 ra_print_rtl_with_bb (dump_file, get_insns ());
886 dump_static_insn_cost (dump_file,
887 "after allocation/spilling, before reload", NULL);
889 /* Allocate the reg_equiv_memory_loc array for reload. */
890 VARRAY_GROW (reg_equiv_memory_loc_varray, max_regno);
891 reg_equiv_memory_loc = &VARRAY_RTX (reg_equiv_memory_loc_varray, 0);
892 /* And possibly initialize it. */
893 allocate_initial_values (reg_equiv_memory_loc);
894 /* And one last regclass pass just before reload. */
895 regclass (get_insns (), max_reg_num (), dump_file);
899 vim:cinoptions={.5s,g0,p5,t0,(0,^-0.5s,n-0.5s:tw=78:cindent:sw=4: