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>.
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
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. */
25 #include "insn-config.h"
28 #include "integrate.h"
32 #include "hard-reg-set.h"
33 #include "basic-block.h"
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.
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.
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),
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.
62 George, L., Appel, A.W. 1996. Iterated register coalescing.
63 ACM Trans. Program. Lang. Syst. 18, 3 (May), 300-324.
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). */
71 /* Things, one might do somewhen:
73 * Lattice based rematerialization
74 * create definitions of ever-life regs at the beginning of
76 * insert loads as soon, stores as late as possile
77 * insert spill insns as outward as possible (either looptree, or LCM)
79 * delete coalesced insns. Partly done. The rest can only go, when we get
81 * don't destroy coalescing information completely when spilling
82 * use the constraints from asms
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));
95 void reg_alloc
PARAMS ((void));
97 /* These global variables are "internal" to the register allocator.
98 They are all documented at their declarations in ra.h. */
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. */
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
;
115 struct web_part
*web_parts
;
117 unsigned int num_webs
;
118 unsigned int num_subwebs
;
119 unsigned int num_allwebs
;
121 struct web
*hardreg2web
[FIRST_PSEUDO_REGISTER
];
122 struct web
**def2web
;
123 struct web
**use2web
;
124 struct move_list
*wl_moves
;
126 short *ra_reg_renumber
;
130 unsigned int max_normal_pseudo
;
131 int an_unusable_color
;
133 /* The different lists on which a web can be (based on the type). */
134 struct dlist
*web_lists
[(int) LAST_NODE_TYPE
];
136 unsigned int last_def_id
;
137 unsigned int last_use_id
;
138 unsigned int last_num_webs
;
140 sbitmap last_check_uses
;
141 unsigned int remember_conflicts
;
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];
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;
161 /* Fast allocation of small objects, which live until the allocator
162 is done. Allocate an object of SIZE bytes. */
168 return obstack_alloc (&ra_obstack
, size
);
171 /* Like ra_alloc(), but clear the returned memory. */
177 void *p
= obstack_alloc (&ra_obstack
, size
);
182 /* Returns the number of hardregs in HARD_REG_SET RS. */
192 unsigned char byte
= rs
& 0xFF;
194 /* Avoid memory access, if nothing is set. */
196 count
+= byte2bitcount
[byte
];
200 for (ofs
= 0; ofs
< HARD_REG_SET_LONGS
; ofs
++)
202 HARD_REG_ELT_TYPE elt
= rs
[ofs
];
205 unsigned char byte
= elt
& 0xFF;
208 count
+= byte2bitcount
[byte
];
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 (x
, y
)
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
));
227 return emit_move_insn (x
, y
);
231 struct ra_insn_info
*insn_df
;
232 static struct ref
**refs_for_insn_df
;
234 /* Create the insn_df structure for each insn to have fast access to
235 all valid defs and uses in an insn. */
238 create_insn_info (df
)
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
))
251 int uid
= INSN_UID (insn
);
253 struct df_link
*link
;
256 for (n
= 0, link
= DF_INSN_DEFS (df
, insn
); link
; link
= link
->next
)
258 && (DF_REF_REGNO (link
->ref
) >= FIRST_PSEUDO_REGISTER
259 || !TEST_HARD_REG_BIT (never_use_colors
,
260 DF_REF_REGNO (link
->ref
))))
263 insn_df
[uid
].defs
= act_refs
;
264 insn_df
[uid
].defs
[n
++] = link
->ref
;
267 insn_df
[uid
].num_defs
= n
;
268 for (n
= 0, link
= DF_INSN_USES (df
, insn
); link
; link
= link
->next
)
270 && (DF_REF_REGNO (link
->ref
) >= FIRST_PSEUDO_REGISTER
271 || !TEST_HARD_REG_BIT (never_use_colors
,
272 DF_REF_REGNO (link
->ref
))))
275 insn_df
[uid
].uses
= act_refs
;
276 insn_df
[uid
].uses
[n
++] = link
->ref
;
279 insn_df
[uid
].num_uses
= n
;
281 if (refs_for_insn_df
+ (df
->def_id
+ df
->use_id
) < act_refs
)
285 /* Free the insn_df structures. */
290 free (refs_for_insn_df
);
291 refs_for_insn_df
= NULL
;
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. */
302 find_subweb (web
, reg
)
307 if (GET_CODE (reg
) != SUBREG
)
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
))
316 /* Similar to find_subweb(), but matches according to SIZE_WORD,
317 a collection of the needed size and offset (in bytes). */
320 find_subweb_2 (web
, size_word
)
322 unsigned int size_word
;
325 if (size_word
== GET_MODE_SIZE (GET_MODE (web
->orig_x
)))
326 /* size_word == size means BYTE_BEGIN(size_word) == 0. */
328 for (w
= web
->subreg_next
; w
; w
= w
->subreg_next
)
330 unsigned int bl
= rtx_to_bits (w
->orig_x
);
337 /* Returns the superweb for SUBWEB. */
340 find_web_for_subweb_1 (subweb
)
343 while (subweb
->parent_web
)
344 subweb
= subweb
->parent_web
;
348 /* Determine if two hard register sets intersect.
349 Return 1 if they do. */
352 hard_regs_intersect_p (a
, b
)
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
);
364 /* Allocate and initialize the memory necessary for one pass of the
365 register allocator. */
372 ra_build_realloc (df
);
375 live_at_end
= (bitmap
*) xmalloc ((last_basic_block
+ 2)
377 for (i
= 0; i
< last_basic_block
+ 2; i
++)
378 live_at_end
[i
] = BITMAP_XMALLOC ();
381 create_insn_info (df
);
384 /* Free the memory which isn't necessary for the next pass. */
388 struct df
*df ATTRIBUTE_UNUSED
;
394 /* Free all memory allocated for the register allocator. Used, when
403 for (i
= 0; i
< (unsigned)last_basic_block
+ 2; i
++)
404 BITMAP_XFREE (live_at_end
[i
]);
407 ra_colorize_free_all ();
408 ra_build_free_all (df
);
409 obstack_free (&ra_obstack
, NULL
);
412 static long ticks_build
;
413 static long ticks_rebuild
;
415 /* Perform one pass of allocation. Returns nonzero, if some spill code
416 was added, i.e. if the allocator needs to rerun. */
419 one_pass (df
, rebuild
)
423 long ticks
= clock ();
424 int something_spilled
;
425 remember_conflicts
= 0;
427 /* Build the complete interference graph, or if this is not the first
428 pass, rebuild it incrementally. */
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;
435 dump_igraph_machine ();
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
);
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
);
447 /* Add spill code if necessary. */
448 if (something_spilled
)
451 ticks
= clock () - ticks
;
453 ticks_rebuild
+= ticks
;
455 ticks_build
+= ticks
;
456 return something_spilled
;
459 /* Initialize various arrays for the register allocator. */
466 #ifdef ELIMINABLE_REGS
467 static const struct {const int from
, to
; } eliminables
[] = ELIMINABLE_REGS
;
471 = (! flag_omit_frame_pointer
472 #ifdef EXIT_IGNORE_STACK
473 || (current_function_calls_alloca
&& EXIT_IGNORE_STACK
)
475 || FRAME_POINTER_REQUIRED
);
479 /* We can't ever use any of the fixed regs. */
480 COPY_HARD_REG_SET (never_use_colors
, fixed_reg_set
);
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
++)
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
);
494 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
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
);
502 for (i
= HARD_REGNO_NREGS (FRAME_POINTER_REGNUM
, Pmode
); i
--;)
503 SET_HARD_REG_BIT (never_use_colors
, FRAME_POINTER_REGNUM
+ i
);
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
);
510 for (i
= HARD_REGNO_NREGS (ARG_POINTER_REGNUM
, Pmode
); i
--;)
511 SET_HARD_REG_BIT (never_use_colors
, ARG_POINTER_REGNUM
+ i
);
513 for (i
= 0; i
< 256; i
++)
515 unsigned char byte
= ((unsigned) i
) & 0xFF;
516 unsigned char count
= 0;
523 byte2bitcount
[i
] = count
;
526 for (i
= 0; i
< N_REG_CLASSES
; i
++)
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
);
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
540 for (i
= 0; i
< NUM_MACHINE_MODES
; i
++)
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
)
551 SET_HARD_REG_BIT (rs
, reg
+ size
);
553 COPY_HARD_REG_SET (hardregs_for_mode
[i
], rs
);
556 for (an_unusable_color
= 0; an_unusable_color
< FIRST_PSEUDO_REGISTER
;
558 if (TEST_HARD_REG_BIT (never_use_colors
, an_unusable_color
))
560 if (an_unusable_color
== FIRST_PSEUDO_REGISTER
)
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
);
572 /* Check the consistency of DF. This aborts if it violates some
573 invariances we expect. */
579 struct df_link
*link
;
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
++)
591 bitmap_set_bit (empty_defs
, ui
);
592 for (ui
= 0; ui
< df
->use_id
; 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
))
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
)))
608 bitmap_set_bit (b
, DF_REF_ID (link
->ref
));
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
)))
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
++)
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
)))
628 bitmap_set_bit (b
, DF_REF_ID (link
->ref
));
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
)))
636 bitmap_set_bit (b
, DF_REF_ID (link
->ref
));
639 BITMAP_XFREE (empty_uses
);
640 BITMAP_XFREE (empty_defs
);
644 /* Main register allocator entry point. */
650 FILE *ra_dump_file
= rtl_dump_file
;
651 rtx last
= get_last_insn ();
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 existance of the return value USE as
659 one of the last insns. Add it if it's not there anymore. */
663 for (e
= EXIT_BLOCK_PTR
->pred
; e
; e
= e
->pred_next
)
665 basic_block bb
= e
->src
;
667 if (!INSN_P (last
) || GET_CODE (PATTERN (last
)) != USE
)
671 use_return_register ();
672 insns
= get_insns ();
674 emit_insn_after (insns
, last
);
679 /* Setup debugging levels. */
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
;
689 case 5: debug_new_regalloc
= DUMP_FINAL_RTL
+ DUMP_COSTS
+
692 case 6: debug_new_regalloc
= DUMP_VALIDIFY
; break;
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 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
;
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. */
712 /* And some global variables. */
715 max_normal_pseudo
= (unsigned) max_reg_num ();
721 last_check_uses
= NULL
;
723 WEBS(INITIAL
) = 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. */
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. */
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
);
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_analyse (df
, (ra_pass
== 1) ? 0 : (bitmap
) -1,
756 DF_HARD_REGS
| DF_RD_CHAIN
| DF_RU_CHAIN
);
758 if ((debug_new_regalloc
& DUMP_DF
) != 0)
761 df_dump (df
, DF_HARD_REGS
, rtl_dump_file
);
762 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
764 df_insn_debug_regno (df
, insn
, rtl_dump_file
);
768 /* Now allocate the memory needed for this pass, or (if it's not the
769 first pass), reallocate only additional memory. */
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. */
779 /* Change the insns to refer to the new pseudos (one per web). */
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
788 /* Delete some more of the coalesced moves. */
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
);
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
;
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. */
820 if (changed
&& (debug_new_regalloc
& DUMP_RTL
) != 0)
822 ra_print_rtl_with_bb (rtl_dump_file
, get_insns ());
823 fflush (rtl_dump_file
);
826 /* Reset the web lists. */
832 /* We are done with allocation, free all memory and output some
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 ());
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
;
847 allocate_reg_info (max_reg_num (), FALSE
, FALSE
);
849 rtl_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 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
);
864 dump_flow_info (rtl_dump_file
);
865 rtl_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
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. */
878 sbitmap_free (insns_with_deaths
);
880 /* Remove REG_DEAD notes which are incorrectly set. See the docu
882 remove_suspicious_death_notes ();
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
);
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
);
898 vim:cinoptions={.5s,g0,p5,t0,(0,^-0.5s,n-0.5s:tw=78:cindent:sw=4: