1 /* Graph coloring register allocator
2 Copyright (C) 2001, 2002 Free Software Foundation, Inc.
3 Contributed by Michael Matz <matz@suse.de>
4 and Daniel Berlin <dan@cgsoftware.com>.
5
6 This file is part of GCC.
7
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.
11
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.
16
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. */
20
21 #include "config.h"
22 #include "system.h"
23 #include "rtl.h"
24 #include "tm_p.h"
25 #include "insn-config.h"
26 #include "recog.h"
27 #include "reload.h"
28 #include "integrate.h"
29 #include "function.h"
30 #include "regs.h"
31 #include "obstack.h"
32 #include "hard-reg-set.h"
33 #include "basic-block.h"
34 #include "df.h"
35 #include "expr.h"
36 #include "output.h"
37 #include "toplev.h"
38 #include "flags.h"
39 #include "ra.h"
40
41 /* This is the toplevel file of a graph coloring register allocator.
42 It is able to act like a George & Appel allocator, i.e. with iterative
43 coalescing plus spill coalescing/propagation.
44 And it can act as a traditional Briggs allocator, although with
45 optimistic coalescing. Additionally it has a custom pass, which
46 tries to reduce the overall cost of the colored graph.
47
48 We support two modes of spilling: spill-everywhere, which is extremely
49 fast, and interference region spilling, which reduces spill code to a
50 large extent, but is slower.
51
52 Helpful documents:
53
54 Briggs, P., Cooper, K. D., and Torczon, L. 1994. Improvements to graph
55 coloring register allocation. ACM Trans. Program. Lang. Syst. 16, 3 (May),
56 428-455.
57
58 Bergner, P., Dahl, P., Engebretsen, D., and O'Keefe, M. 1997. Spill code
59 minimization via interference region spilling. In Proc. ACM SIGPLAN '97
60 Conf. on Prog. Language Design and Implementation. ACM, 287-295.
61
62 George, L., Appel, A.W. 1996. Iterated register coalescing.
63 ACM Trans. Program. Lang. Syst. 18, 3 (May), 300-324.
64
65 */
66
67 /* This file contains the main entry point (reg_alloc), some helper routines
68 used by more than one file of the register allocator, and the toplevel
69 driver procedure (one_pass). */
70
71 /* Things, one might do somewhen:
72
73 * Lattice based rematerialization
74 * create definitions of ever-life regs at the beginning of
75 the insn chain
76 * insert loads as soon, stores as late as possile
77 * insert spill insns as outward as possible (either looptree, or LCM)
78 * reuse stack-slots
79 * delete coalesced insns. Partly done. The rest can only go, when we get
80 rid of reload.
81 * don't destroy coalescing information completely when spilling
82 * use the constraints from asms
83 */
84
85 static struct obstack ra_obstack;
86 static void create_insn_info PARAMS ((struct df *));
87 static void free_insn_info PARAMS ((void));
88 static void alloc_mem PARAMS ((struct df *));
89 static void free_mem PARAMS ((struct df *));
90 static void free_all_mem PARAMS ((struct df *df));
91 static int one_pass PARAMS ((struct df *, int));
92 static void check_df PARAMS ((struct df *));
93 static void init_ra PARAMS ((void));
94
95 void reg_alloc PARAMS ((void));
96
97 /* These global variables are "internal" to the register allocator.
98 They are all documented at their declarations in ra.h. */
99
100 /* Somewhen we want to get rid of one of those sbitmaps.
101 (for now I need the sup_igraph to note if there is any conflict between
102 parts of webs at all. I can't use igraph for this, as there only the real
103 conflicts are noted.) This is only used to prevent coalescing two
104 conflicting webs, were only parts of them are in conflict. */
105 sbitmap igraph;
106 sbitmap sup_igraph;
107
108 /* Note the insns not inserted by the allocator, where we detected any
109 deaths of pseudos. It is used to detect closeness of defs and uses.
110 In the first pass this is empty (we could initialize it from REG_DEAD
111 notes), in the other passes it is left from the pass before. */
112 sbitmap insns_with_deaths;
113 int death_insns_max_uid;
114
115 struct web_part *web_parts;
116
117 unsigned int num_webs;
118 unsigned int num_subwebs;
119 unsigned int num_allwebs;
120 struct web **id2web;
121 struct web *hardreg2web[FIRST_PSEUDO_REGISTER];
122 struct web **def2web;
123 struct web **use2web;
124 struct move_list *wl_moves;
125 int ra_max_regno;
126 short *ra_reg_renumber;
127 struct df *df;
128 bitmap *live_at_end;
129 int ra_pass;
130 unsigned int max_normal_pseudo;
131 int an_unusable_color;
132
133 /* The different lists on which a web can be (based on the type). */
134 struct dlist *web_lists[(int) LAST_NODE_TYPE];
135
136 unsigned int last_def_id;
137 unsigned int last_use_id;
138 unsigned int last_num_webs;
139 int last_max_uid;
140 sbitmap last_check_uses;
141 unsigned int remember_conflicts;
142
143 int orig_max_uid;
144
145 HARD_REG_SET never_use_colors;
146 HARD_REG_SET usable_regs[N_REG_CLASSES];
147 unsigned int num_free_regs[N_REG_CLASSES];
148 HARD_REG_SET hardregs_for_mode[NUM_MACHINE_MODES];
149 unsigned char byte2bitcount[256];
150
151 unsigned int debug_new_regalloc = -1;
152 int flag_ra_biased = 0;
153 int flag_ra_improved_spilling = 0;
154 int flag_ra_ir_spilling = 0;
155 int flag_ra_optimistic_coalescing = 0;
156 int flag_ra_break_aliases = 0;
157 int flag_ra_merge_spill_costs = 0;
158 int flag_ra_spill_every_use = 0;
159 int flag_ra_dump_notes = 0;
160
161 /* Fast allocation of small objects, which live until the allocator
162 is done. Allocate an object of SIZE bytes. */
163
164 void *
ra_alloc(size)165 ra_alloc (size)
166 size_t size;
167 {
168 return obstack_alloc (&ra_obstack, size);
169 }
170
171 /* Like ra_alloc(), but clear the returned memory. */
172
173 void *
ra_calloc(size)174 ra_calloc (size)
175 size_t size;
176 {
177 void *p = obstack_alloc (&ra_obstack, size);
178 memset (p, 0, size);
179 return p;
180 }
181
182 /* Returns the number of hardregs in HARD_REG_SET RS. */
183
184 int
hard_regs_count(rs)185 hard_regs_count (rs)
186 HARD_REG_SET rs;
187 {
188 int count = 0;
189 #ifdef HARD_REG_SET
190 while (rs)
191 {
192 unsigned char byte = rs & 0xFF;
193 rs >>= 8;
194 /* Avoid memory access, if nothing is set. */
195 if (byte)
196 count += byte2bitcount[byte];
197 }
198 #else
199 unsigned int ofs;
200 for (ofs = 0; ofs < HARD_REG_SET_LONGS; ofs++)
201 {
202 HARD_REG_ELT_TYPE elt = rs[ofs];
203 while (elt)
204 {
205 unsigned char byte = elt & 0xFF;
206 elt >>= 8;
207 if (byte)
208 count += byte2bitcount[byte];
209 }
210 }
211 #endif
212 return count;
213 }
214
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. */
218
219 rtx
ra_emit_move_insn(x,y)220 ra_emit_move_insn (x, y)
221 rtx x, y;
222 {
223 enum machine_mode mode = GET_MODE (x);
224 if (GET_MODE_CLASS (mode) == MODE_CC)
225 return emit_insn (gen_move_insn (x, y));
226 else
227 return emit_move_insn (x, y);
228 }
229
230 int insn_df_max_uid;
231 struct ra_insn_info *insn_df;
232 static struct ref **refs_for_insn_df;
233
234 /* Create the insn_df structure for each insn to have fast access to
235 all valid defs and uses in an insn. */
236
237 static void
create_insn_info(df)238 create_insn_info (df)
239 struct df *df;
240 {
241 rtx insn;
242 struct ref **act_refs;
243 insn_df_max_uid = get_max_uid ();
244 insn_df = xcalloc (insn_df_max_uid, sizeof (insn_df[0]));
245 refs_for_insn_df = xcalloc (df->def_id + df->use_id, sizeof (struct ref *));
246 act_refs = refs_for_insn_df;
247 /* We create those things backwards to mimic the order in which
248 the insns are visited in rewrite_program2() and live_in(). */
249 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
250 {
251 int uid = INSN_UID (insn);
252 unsigned int n;
253 struct df_link *link;
254 if (!INSN_P (insn))
255 continue;
256 for (n = 0, link = DF_INSN_DEFS (df, insn); link; link = link->next)
257 if (link->ref
258 && (DF_REF_REGNO (link->ref) >= FIRST_PSEUDO_REGISTER
259 || !TEST_HARD_REG_BIT (never_use_colors,
260 DF_REF_REGNO (link->ref))))
261 {
262 if (n == 0)
263 insn_df[uid].defs = act_refs;
264 insn_df[uid].defs[n++] = link->ref;
265 }
266 act_refs += n;
267 insn_df[uid].num_defs = n;
268 for (n = 0, link = DF_INSN_USES (df, insn); link; link = link->next)
269 if (link->ref
270 && (DF_REF_REGNO (link->ref) >= FIRST_PSEUDO_REGISTER
271 || !TEST_HARD_REG_BIT (never_use_colors,
272 DF_REF_REGNO (link->ref))))
273 {
274 if (n == 0)
275 insn_df[uid].uses = act_refs;
276 insn_df[uid].uses[n++] = link->ref;
277 }
278 act_refs += n;
279 insn_df[uid].num_uses = n;
280 }
281 if (refs_for_insn_df + (df->def_id + df->use_id) < act_refs)
282 abort ();
283 }
284
285 /* Free the insn_df structures. */
286
287 static void
free_insn_info()288 free_insn_info ()
289 {
290 free (refs_for_insn_df);
291 refs_for_insn_df = NULL;
292 free (insn_df);
293 insn_df = NULL;
294 insn_df_max_uid = 0;
295 }
296
297 /* Search WEB for a subweb, which represents REG. REG needs to
298 be a SUBREG, and the inner reg of it needs to be the one which is
299 represented by WEB. Returns the matching subweb or NULL. */
300
301 struct web *
find_subweb(web,reg)302 find_subweb (web, reg)
303 struct web *web;
304 rtx reg;
305 {
306 struct web *w;
307 if (GET_CODE (reg) != SUBREG)
308 abort ();
309 for (w = web->subreg_next; w; w = w->subreg_next)
310 if (GET_MODE (w->orig_x) == GET_MODE (reg)
311 && SUBREG_BYTE (w->orig_x) == SUBREG_BYTE (reg))
312 return w;
313 return NULL;
314 }
315
316 /* Similar to find_subweb(), but matches according to SIZE_WORD,
317 a collection of the needed size and offset (in bytes). */
318
319 struct web *
find_subweb_2(web,size_word)320 find_subweb_2 (web, size_word)
321 struct web *web;
322 unsigned int size_word;
323 {
324 struct web *w = web;
325 if (size_word == GET_MODE_SIZE (GET_MODE (web->orig_x)))
326 /* size_word == size means BYTE_BEGIN(size_word) == 0. */
327 return web;
328 for (w = web->subreg_next; w; w = w->subreg_next)
329 {
330 unsigned int bl = rtx_to_bits (w->orig_x);
331 if (size_word == bl)
332 return w;
333 }
334 return NULL;
335 }
336
337 /* Returns the superweb for SUBWEB. */
338
339 struct web *
find_web_for_subweb_1(subweb)340 find_web_for_subweb_1 (subweb)
341 struct web *subweb;
342 {
343 while (subweb->parent_web)
344 subweb = subweb->parent_web;
345 return subweb;
346 }
347
348 /* Determine if two hard register sets intersect.
349 Return 1 if they do. */
350
351 int
hard_regs_intersect_p(a,b)352 hard_regs_intersect_p (a, b)
353 HARD_REG_SET *a, *b;
354 {
355 HARD_REG_SET c;
356 COPY_HARD_REG_SET (c, *a);
357 AND_HARD_REG_SET (c, *b);
358 GO_IF_HARD_REG_SUBSET (c, reg_class_contents[(int) NO_REGS], lose);
359 return 1;
360 lose:
361 return 0;
362 }
363
364 /* Allocate and initialize the memory necessary for one pass of the
365 register allocator. */
366
367 static void
alloc_mem(df)368 alloc_mem (df)
369 struct df *df;
370 {
371 int i;
372 ra_build_realloc (df);
373 if (!live_at_end)
374 {
375 live_at_end = (bitmap *) xmalloc ((last_basic_block + 2)
376 * sizeof (bitmap));
377 for (i = 0; i < last_basic_block + 2; i++)
378 live_at_end[i] = BITMAP_XMALLOC ();
379 live_at_end += 2;
380 }
381 create_insn_info (df);
382 }
383
384 /* Free the memory which isn't necessary for the next pass. */
385
386 static void
free_mem(df)387 free_mem (df)
388 struct df *df ATTRIBUTE_UNUSED;
389 {
390 free_insn_info ();
391 ra_build_free ();
392 }
393
394 /* Free all memory allocated for the register allocator. Used, when
395 it's done. */
396
397 static void
free_all_mem(df)398 free_all_mem (df)
399 struct df *df;
400 {
401 unsigned int i;
402 live_at_end -= 2;
403 for (i = 0; i < (unsigned)last_basic_block + 2; i++)
404 BITMAP_XFREE (live_at_end[i]);
405 free (live_at_end);
406
407 ra_colorize_free_all ();
408 ra_build_free_all (df);
409 obstack_free (&ra_obstack, NULL);
410 }
411
412 static long ticks_build;
413 static long ticks_rebuild;
414
415 /* Perform one pass of allocation. Returns nonzero, if some spill code
416 was added, i.e. if the allocator needs to rerun. */
417
418 static int
one_pass(df,rebuild)419 one_pass (df, rebuild)
420 struct df *df;
421 int rebuild;
422 {
423 long ticks = clock ();
424 int something_spilled;
425 remember_conflicts = 0;
426
427 /* Build the complete interference graph, or if this is not the first
428 pass, rebuild it incrementally. */
429 build_i_graph (df);
430
431 /* From now on, if we create new conflicts, we need to remember the
432 initial list of conflicts per web. */
433 remember_conflicts = 1;
434 if (!rebuild)
435 dump_igraph_machine ();
436
437 /* Colorize the I-graph. This results in either a list of
438 spilled_webs, in which case we need to run the spill phase, and
439 rerun the allocator, or that list is empty, meaning we are done. */
440 ra_colorize_graph (df);
441
442 last_max_uid = get_max_uid ();
443 /* actual_spill() might change WEBS(SPILLED) and even empty it,
444 so we need to remember it's state. */
445 something_spilled = !!WEBS(SPILLED);
446
447 /* Add spill code if necessary. */
448 if (something_spilled)
449 actual_spill ();
450
451 ticks = clock () - ticks;
452 if (rebuild)
453 ticks_rebuild += ticks;
454 else
455 ticks_build += ticks;
456 return something_spilled;
457 }
458
459 /* Initialize various arrays for the register allocator. */
460
461 static void
init_ra()462 init_ra ()
463 {
464 int i;
465 HARD_REG_SET rs;
466 #ifdef ELIMINABLE_REGS
467 static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
468 unsigned int j;
469 #endif
470 int need_fp
471 = (! flag_omit_frame_pointer
472 #ifdef EXIT_IGNORE_STACK
473 || (current_function_calls_alloca && EXIT_IGNORE_STACK)
474 #endif
475 || FRAME_POINTER_REQUIRED);
476
477 ra_colorize_init ();
478
479 /* We can't ever use any of the fixed regs. */
480 COPY_HARD_REG_SET (never_use_colors, fixed_reg_set);
481
482 /* Additionally don't even try to use hardregs, which we already
483 know are not eliminable. This includes also either the
484 hard framepointer or all regs which are eliminable into the
485 stack pointer, if need_fp is set. */
486 #ifdef ELIMINABLE_REGS
487 for (j = 0; j < ARRAY_SIZE (eliminables); j++)
488 {
489 if (! CAN_ELIMINATE (eliminables[j].from, eliminables[j].to)
490 || (eliminables[j].to == STACK_POINTER_REGNUM && need_fp))
491 for (i = HARD_REGNO_NREGS (eliminables[j].from, Pmode); i--;)
492 SET_HARD_REG_BIT (never_use_colors, eliminables[j].from + i);
493 }
494 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
495 if (need_fp)
496 for (i = HARD_REGNO_NREGS (HARD_FRAME_POINTER_REGNUM, Pmode); i--;)
497 SET_HARD_REG_BIT (never_use_colors, HARD_FRAME_POINTER_REGNUM + i);
498 #endif
499
500 #else
501 if (need_fp)
502 for (i = HARD_REGNO_NREGS (FRAME_POINTER_REGNUM, Pmode); i--;)
503 SET_HARD_REG_BIT (never_use_colors, FRAME_POINTER_REGNUM + i);
504 #endif
505
506 /* Stack and argument pointer are also rather useless to us. */
507 for (i = HARD_REGNO_NREGS (STACK_POINTER_REGNUM, Pmode); i--;)
508 SET_HARD_REG_BIT (never_use_colors, STACK_POINTER_REGNUM + i);
509
510 for (i = HARD_REGNO_NREGS (ARG_POINTER_REGNUM, Pmode); i--;)
511 SET_HARD_REG_BIT (never_use_colors, ARG_POINTER_REGNUM + i);
512
513 for (i = 0; i < 256; i++)
514 {
515 unsigned char byte = ((unsigned) i) & 0xFF;
516 unsigned char count = 0;
517 while (byte)
518 {
519 if (byte & 1)
520 count++;
521 byte >>= 1;
522 }
523 byte2bitcount[i] = count;
524 }
525
526 for (i = 0; i < N_REG_CLASSES; i++)
527 {
528 int size;
529 COPY_HARD_REG_SET (rs, reg_class_contents[i]);
530 AND_COMPL_HARD_REG_SET (rs, never_use_colors);
531 size = hard_regs_count (rs);
532 num_free_regs[i] = size;
533 COPY_HARD_REG_SET (usable_regs[i], rs);
534 }
535
536 /* Setup hardregs_for_mode[].
537 We are not interested only in the beginning of a multi-reg, but in
538 all the hardregs involved. Maybe HARD_REGNO_MODE_OK() only ok's
539 for beginnings. */
540 for (i = 0; i < NUM_MACHINE_MODES; i++)
541 {
542 int reg, size;
543 CLEAR_HARD_REG_SET (rs);
544 for (reg = 0; reg < FIRST_PSEUDO_REGISTER; reg++)
545 if (HARD_REGNO_MODE_OK (reg, i)
546 /* Ignore VOIDmode and similar things. */
547 && (size = HARD_REGNO_NREGS (reg, i)) != 0
548 && (reg + size) <= FIRST_PSEUDO_REGISTER)
549 {
550 while (size--)
551 SET_HARD_REG_BIT (rs, reg + size);
552 }
553 COPY_HARD_REG_SET (hardregs_for_mode[i], rs);
554 }
555
556 for (an_unusable_color = 0; an_unusable_color < FIRST_PSEUDO_REGISTER;
557 an_unusable_color++)
558 if (TEST_HARD_REG_BIT (never_use_colors, an_unusable_color))
559 break;
560 if (an_unusable_color == FIRST_PSEUDO_REGISTER)
561 abort ();
562
563 orig_max_uid = get_max_uid ();
564 compute_bb_for_insn ();
565 ra_reg_renumber = NULL;
566 insns_with_deaths = sbitmap_alloc (orig_max_uid);
567 death_insns_max_uid = orig_max_uid;
568 sbitmap_ones (insns_with_deaths);
569 gcc_obstack_init (&ra_obstack);
570 }
571
572 /* Check the consistency of DF. This aborts if it violates some
573 invariances we expect. */
574
575 static void
check_df(df)576 check_df (df)
577 struct df *df;
578 {
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 ();
586
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);
595
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))
601 {
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));
609
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));
617 }
618
619 /* Now the same for the chains per register number. */
620 for (regno = 0; regno < max_reg_num (); regno++)
621 {
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));
629
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));
637 }
638
639 BITMAP_XFREE (empty_uses);
640 BITMAP_XFREE (empty_defs);
641 BITMAP_XFREE (b);
642 }
643
644 /* Main register allocator entry point. */
645
646 void
reg_alloc()647 reg_alloc ()
648 {
649 int changed;
650 FILE *ra_dump_file = rtl_dump_file;
651 rtx last = get_last_insn ();
652
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. */
657
658 /* We currently rely on the existance of the return value USE as
659 one of the last insns. Add it if it's not there anymore. */
660 if (last)
661 {
662 edge e;
663 for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
664 {
665 basic_block bb = e->src;
666 last = bb->end;
667 if (!INSN_P (last) || GET_CODE (PATTERN (last)) != USE)
668 {
669 rtx insns;
670 start_sequence ();
671 use_return_register ();
672 insns = get_insns ();
673 end_sequence ();
674 emit_insn_after (insns, last);
675 }
676 }
677 }
678
679 /* Setup debugging levels. */
680 switch (0)
681 {
682 /* Some usefull 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;
693 }
694 if (!rtl_dump_file)
695 debug_new_regalloc = 0;
696
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 explicitely requested. */
700 if ((debug_new_regalloc & DUMP_REGCLASS) == 0)
701 rtl_dump_file = NULL;
702 regclass (get_insns (), max_reg_num (), rtl_dump_file);
703 rtl_dump_file = ra_dump_file;
704
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);
708
709 /* Initialize the different global arrays and regsets. */
710 init_ra ();
711
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;
727
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;
740
741 /* Allocate the global df structure. */
742 df = df_init ();
743
744 /* This is the main loop, calling one_pass as long as there are still
745 some spilled webs. */
746 do
747 {
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");
751
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_analyse (df, (ra_pass == 1) ? 0 : (bitmap) -1,
756 DF_HARD_REGS | DF_RD_CHAIN | DF_RU_CHAIN);
757
758 if ((debug_new_regalloc & DUMP_DF) != 0)
759 {
760 rtx insn;
761 df_dump (df, DF_HARD_REGS, rtl_dump_file);
762 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
763 if (INSN_P (insn))
764 df_insn_debug_regno (df, insn, rtl_dump_file);
765 }
766 check_df (df);
767
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);
771
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);
775
776 /* If that produced no changes, the graph was colorizable. */
777 if (!changed)
778 {
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 ();
791 }
792 else
793 {
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 rtl_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 usefull classes too. */
809 regclass (get_insns (), max_reg_num (), rtl_dump_file);
810 rtl_dump_file = ra_dump_file;
811
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;
816 }
817
818 /* Output the graph, and possibly the current insn sequence. */
819 dump_ra (df);
820 if (changed && (debug_new_regalloc & DUMP_RTL) != 0)
821 {
822 ra_print_rtl_with_bb (rtl_dump_file, get_insns ());
823 fflush (rtl_dump_file);
824 }
825
826 /* Reset the web lists. */
827 reset_lists ();
828 free_mem (df);
829 }
830 while (changed);
831
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 (rtl_dump_file, get_insns ());
842
843 /* We might have new pseudos, so allocate the info arrays for them. */
844 if ((debug_new_regalloc & DUMP_SM) == 0)
845 rtl_dump_file = NULL;
846 no_new_pseudos = 0;
847 allocate_reg_info (max_reg_num (), FALSE, FALSE);
848 no_new_pseudos = 1;
849 rtl_dump_file = ra_dump_file;
850
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 ();
855
856 /* Cleanup the flow graph. */
857 if ((debug_new_regalloc & DUMP_LAST_FLOW) == 0)
858 rtl_dump_file = NULL;
859 life_analysis (get_insns (), rtl_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 (rtl_dump_file)
864 dump_flow_info (rtl_dump_file);
865 rtl_dump_file = ra_dump_file;
866
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 ();*/
875
876 /* Setup the reg_renumber[] array for reload. */
877 setup_renumber (1);
878 sbitmap_free (insns_with_deaths);
879
880 /* Remove REG_DEAD notes which are incorrectly set. See the docu
881 of that function. */
882 remove_suspicious_death_notes ();
883
884 if ((debug_new_regalloc & DUMP_LAST_RTL) != 0)
885 ra_print_rtl_with_bb (rtl_dump_file, get_insns ());
886 dump_static_insn_cost (rtl_dump_file,
887 "after allocation/spilling, before reload", NULL);
888
889 /* Allocate the reg_equiv_memory_loc array for reload. */
890 reg_equiv_memory_loc = (rtx *) xcalloc (max_regno, sizeof (rtx));
891 /* And possibly initialize it. */
892 allocate_initial_values (reg_equiv_memory_loc);
893 /* And one last regclass pass just before reload. */
894 regclass (get_insns (), max_reg_num (), rtl_dump_file);
895 }
896
897 /*
898 vim:cinoptions={.5s,g0,p5,t0,(0,^-0.5s,n-0.5s:tw=78:cindent:sw=4:
899 */
900