]>
Commit | Line | Data |
---|---|---|
ed8d2920 | 1 | /* Graph coloring register allocator |
e146f815 | 2 | Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc. |
ed8d2920 MM |
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" | |
4977bab6 ZW |
23 | #include "coretypes.h" |
24 | #include "tm.h" | |
ed8d2920 MM |
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" | |
42 | ||
ed8d2920 MM |
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. | |
49 | ||
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. | |
53 | ||
54 | Helpful documents: | |
55 | ||
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. | |
59 | ||
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. | |
63 | ||
64 | George, L., Appel, A.W. 1996. Iterated register coalescing. | |
65 | ACM Trans. Program. Lang. Syst. 18, 3 (May), 300-324. | |
66 | ||
67 | */ | |
68 | ||
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). */ | |
72 | ||
73 | /* Things, one might do somewhen: | |
74 | ||
75 | * Lattice based rematerialization | |
76 | * create definitions of ever-life regs at the beginning of | |
77 | the insn chain | |
d55d8fc7 | 78 | * insert loads as soon, stores as late as possible |
ed8d2920 MM |
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 | |
85 | */ | |
86 | ||
87 | static struct obstack ra_obstack; | |
93bad80e SB |
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); | |
ed8d2920 | 96 | |
93bad80e | 97 | void reg_alloc (void); |
ed8d2920 MM |
98 | |
99 | /* These global variables are "internal" to the register allocator. | |
100 | They are all documented at their declarations in ra.h. */ | |
101 | ||
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; | |
109 | ||
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; | |
116 | ||
117 | struct web_part *web_parts; | |
118 | ||
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; | |
134 | ||
135 | /* The different lists on which a web can be (based on the type). */ | |
136 | struct dlist *web_lists[(int) LAST_NODE_TYPE]; | |
137 | ||
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; | |
144 | ||
145 | int orig_max_uid; | |
146 | ||
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]; | |
50aac998 | 151 | HARD_REG_SET invalid_mode_change_regs; |
ed8d2920 MM |
152 | unsigned char byte2bitcount[256]; |
153 | ||
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; | |
163 | ||
164 | /* Fast allocation of small objects, which live until the allocator | |
165 | is done. Allocate an object of SIZE bytes. */ | |
166 | ||
167 | void * | |
93bad80e | 168 | ra_alloc (size_t size) |
ed8d2920 MM |
169 | { |
170 | return obstack_alloc (&ra_obstack, size); | |
171 | } | |
172 | ||
173 | /* Like ra_alloc(), but clear the returned memory. */ | |
174 | ||
175 | void * | |
93bad80e | 176 | ra_calloc (size_t size) |
ed8d2920 MM |
177 | { |
178 | void *p = obstack_alloc (&ra_obstack, size); | |
179 | memset (p, 0, size); | |
180 | return p; | |
181 | } | |
182 | ||
183 | /* Returns the number of hardregs in HARD_REG_SET RS. */ | |
184 | ||
185 | int | |
93bad80e | 186 | hard_regs_count (HARD_REG_SET rs) |
ed8d2920 MM |
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 | |
93bad80e | 220 | ra_emit_move_insn (rtx x, rtx y) |
ed8d2920 MM |
221 | { |
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); | |
227 | } | |
228 | ||
229 | int insn_df_max_uid; | |
230 | struct ra_insn_info *insn_df; | |
231 | static struct ref **refs_for_insn_df; | |
232 | ||
233 | /* Create the insn_df structure for each insn to have fast access to | |
234 | all valid defs and uses in an insn. */ | |
235 | ||
236 | static void | |
93bad80e | 237 | create_insn_info (struct df *df) |
ed8d2920 MM |
238 | { |
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)) | |
248 | { | |
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)))) | |
259 | { | |
260 | if (n == 0) | |
261 | insn_df[uid].defs = act_refs; | |
262 | insn_df[uid].defs[n++] = link->ref; | |
263 | } | |
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)))) | |
271 | { | |
272 | if (n == 0) | |
273 | insn_df[uid].uses = act_refs; | |
274 | insn_df[uid].uses[n++] = link->ref; | |
275 | } | |
276 | act_refs += n; | |
277 | insn_df[uid].num_uses = n; | |
278 | } | |
279 | if (refs_for_insn_df + (df->def_id + df->use_id) < act_refs) | |
280 | abort (); | |
281 | } | |
282 | ||
283 | /* Free the insn_df structures. */ | |
284 | ||
285 | static void | |
93bad80e | 286 | free_insn_info (void) |
ed8d2920 MM |
287 | { |
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; | |
293 | } | |
294 | ||
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. */ | |
298 | ||
299 | struct web * | |
93bad80e | 300 | find_subweb (struct web *web, rtx reg) |
ed8d2920 MM |
301 | { |
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; | |
310 | } | |
311 | ||
312 | /* Similar to find_subweb(), but matches according to SIZE_WORD, | |
313 | a collection of the needed size and offset (in bytes). */ | |
314 | ||
315 | struct web * | |
93bad80e | 316 | find_subweb_2 (struct web *web, unsigned int size_word) |
ed8d2920 MM |
317 | { |
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) | |
323 | { | |
324 | unsigned int bl = rtx_to_bits (w->orig_x); | |
325 | if (size_word == bl) | |
326 | return w; | |
327 | } | |
328 | return NULL; | |
329 | } | |
330 | ||
331 | /* Returns the superweb for SUBWEB. */ | |
332 | ||
333 | struct web * | |
93bad80e | 334 | find_web_for_subweb_1 (struct web *subweb) |
ed8d2920 MM |
335 | { |
336 | while (subweb->parent_web) | |
337 | subweb = subweb->parent_web; | |
338 | return subweb; | |
339 | } | |
340 | ||
341 | /* Determine if two hard register sets intersect. | |
342 | Return 1 if they do. */ | |
343 | ||
344 | int | |
93bad80e | 345 | hard_regs_intersect_p (HARD_REG_SET *a, HARD_REG_SET *b) |
ed8d2920 MM |
346 | { |
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; | |
354 | } | |
355 | ||
356 | /* Allocate and initialize the memory necessary for one pass of the | |
357 | register allocator. */ | |
358 | ||
359 | static void | |
93bad80e | 360 | alloc_mem (struct df *df) |
ed8d2920 MM |
361 | { |
362 | int i; | |
363 | ra_build_realloc (df); | |
364 | if (!live_at_end) | |
365 | { | |
703ad42b | 366 | live_at_end = xmalloc ((last_basic_block + 2) * sizeof (bitmap)); |
ed8d2920 MM |
367 | for (i = 0; i < last_basic_block + 2; i++) |
368 | live_at_end[i] = BITMAP_XMALLOC (); | |
369 | live_at_end += 2; | |
370 | } | |
371 | create_insn_info (df); | |
372 | } | |
373 | ||
374 | /* Free the memory which isn't necessary for the next pass. */ | |
375 | ||
376 | static void | |
93bad80e | 377 | free_mem (struct df *df ATTRIBUTE_UNUSED) |
ed8d2920 MM |
378 | { |
379 | free_insn_info (); | |
380 | ra_build_free (); | |
381 | } | |
382 | ||
383 | /* Free all memory allocated for the register allocator. Used, when | |
384 | it's done. */ | |
385 | ||
386 | static void | |
93bad80e | 387 | free_all_mem (struct df *df) |
ed8d2920 MM |
388 | { |
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); | |
394 | ||
395 | ra_colorize_free_all (); | |
396 | ra_build_free_all (df); | |
397 | obstack_free (&ra_obstack, NULL); | |
398 | } | |
399 | ||
400 | static long ticks_build; | |
401 | static long ticks_rebuild; | |
402 | ||
403 | /* Perform one pass of allocation. Returns nonzero, if some spill code | |
404 | was added, i.e. if the allocator needs to rerun. */ | |
405 | ||
406 | static int | |
93bad80e | 407 | one_pass (struct df *df, int rebuild) |
ed8d2920 MM |
408 | { |
409 | long ticks = clock (); | |
410 | int something_spilled; | |
411 | remember_conflicts = 0; | |
412 | ||
413 | /* Build the complete interference graph, or if this is not the first | |
414 | pass, rebuild it incrementally. */ | |
415 | build_i_graph (df); | |
416 | ||
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 (); | |
422 | ||
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); | |
427 | ||
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); | |
432 | ||
433 | /* Add spill code if necessary. */ | |
434 | if (something_spilled) | |
435 | actual_spill (); | |
436 | ||
437 | ticks = clock () - ticks; | |
438 | if (rebuild) | |
439 | ticks_rebuild += ticks; | |
440 | else | |
441 | ticks_build += ticks; | |
442 | return something_spilled; | |
443 | } | |
444 | ||
445 | /* Initialize various arrays for the register allocator. */ | |
446 | ||
447 | static void | |
93bad80e | 448 | init_ra (void) |
ed8d2920 MM |
449 | { |
450 | int i; | |
451 | HARD_REG_SET rs; | |
452 | #ifdef ELIMINABLE_REGS | |
d3969c34 | 453 | static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS; |
ed8d2920 MM |
454 | unsigned int j; |
455 | #endif | |
456 | int need_fp | |
457 | = (! flag_omit_frame_pointer | |
ed8d2920 | 458 | || (current_function_calls_alloca && EXIT_IGNORE_STACK) |
ed8d2920 MM |
459 | || FRAME_POINTER_REQUIRED); |
460 | ||
461 | ra_colorize_init (); | |
462 | ||
463 | /* We can't ever use any of the fixed regs. */ | |
464 | COPY_HARD_REG_SET (never_use_colors, fixed_reg_set); | |
465 | ||
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++) | |
472 | { | |
473 | if (! CAN_ELIMINATE (eliminables[j].from, eliminables[j].to) | |
474 | || (eliminables[j].to == STACK_POINTER_REGNUM && need_fp)) | |
66fd46b6 | 475 | for (i = hard_regno_nregs[eliminables[j].from][Pmode]; i--;) |
ed8d2920 MM |
476 | SET_HARD_REG_BIT (never_use_colors, eliminables[j].from + i); |
477 | } | |
478 | #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM | |
479 | if (need_fp) | |
66fd46b6 | 480 | for (i = hard_regno_nregs[HARD_FRAME_POINTER_REGNUM][Pmode]; i--;) |
ed8d2920 MM |
481 | SET_HARD_REG_BIT (never_use_colors, HARD_FRAME_POINTER_REGNUM + i); |
482 | #endif | |
483 | ||
484 | #else | |
485 | if (need_fp) | |
66fd46b6 | 486 | for (i = hard_regno_nregs[FRAME_POINTER_REGNUM][Pmode]; i--;) |
ed8d2920 MM |
487 | SET_HARD_REG_BIT (never_use_colors, FRAME_POINTER_REGNUM + i); |
488 | #endif | |
489 | ||
490 | /* Stack and argument pointer are also rather useless to us. */ | |
66fd46b6 | 491 | for (i = hard_regno_nregs[STACK_POINTER_REGNUM][Pmode]; i--;) |
ed8d2920 MM |
492 | SET_HARD_REG_BIT (never_use_colors, STACK_POINTER_REGNUM + i); |
493 | ||
66fd46b6 | 494 | for (i = hard_regno_nregs[ARG_POINTER_REGNUM][Pmode]; i--;) |
ed8d2920 MM |
495 | SET_HARD_REG_BIT (never_use_colors, ARG_POINTER_REGNUM + i); |
496 | ||
497 | for (i = 0; i < 256; i++) | |
498 | { | |
499 | unsigned char byte = ((unsigned) i) & 0xFF; | |
500 | unsigned char count = 0; | |
501 | while (byte) | |
502 | { | |
503 | if (byte & 1) | |
504 | count++; | |
505 | byte >>= 1; | |
506 | } | |
507 | byte2bitcount[i] = count; | |
508 | } | |
509 | ||
510 | for (i = 0; i < N_REG_CLASSES; i++) | |
511 | { | |
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); | |
518 | } | |
519 | ||
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++) | |
525 | { | |
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. */ | |
66fd46b6 | 531 | && (size = hard_regno_nregs[reg][i]) != 0 |
ed8d2920 MM |
532 | && (reg + size) <= FIRST_PSEUDO_REGISTER) |
533 | { | |
534 | while (size--) | |
535 | SET_HARD_REG_BIT (rs, reg + size); | |
536 | } | |
537 | COPY_HARD_REG_SET (hardregs_for_mode[i], rs); | |
538 | } | |
539 | ||
50aac998 MM |
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++) | |
544 | { | |
545 | enum machine_mode from = (enum machine_mode) i; | |
546 | enum machine_mode to; | |
547 | for (to = VOIDmode; to < MAX_MACHINE_MODE; ++to) | |
548 | { | |
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); | |
553 | } | |
554 | } | |
555 | #endif | |
556 | ||
ed8d2920 MM |
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 (); | |
563 | ||
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); | |
571 | } | |
572 | ||
573 | /* Check the consistency of DF. This aborts if it violates some | |
574 | invariances we expect. */ | |
575 | ||
576 | static void | |
93bad80e | 577 | check_df (struct df *df) |
ed8d2920 MM |
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 | |
93bad80e | 647 | reg_alloc (void) |
ed8d2920 MM |
648 | { |
649 | int changed; | |
c263766c | 650 | FILE *ra_dump_file = dump_file; |
ed8d2920 MM |
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 | ||
d55d8fc7 | 658 | /* We currently rely on the existence of the return value USE as |
ed8d2920 MM |
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; | |
a813c111 | 666 | last = BB_END (bb); |
ed8d2920 MM |
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 | { | |
3d042e77 | 682 | /* Some useful presets of the debug level, I often use. */ |
ed8d2920 MM |
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 | } | |
c263766c | 694 | if (!dump_file) |
ed8d2920 MM |
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 | |
d55d8fc7 | 699 | explicitly requested. */ |
ed8d2920 | 700 | if ((debug_new_regalloc & DUMP_REGCLASS) == 0) |
c263766c RH |
701 | dump_file = NULL; |
702 | regclass (get_insns (), max_reg_num (), dump_file); | |
703 | dump_file = ra_dump_file; | |
ed8d2920 MM |
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. */ | |
b57f2e10 | 755 | df_analyze (df, (ra_pass == 1) ? 0 : (bitmap) -1, |
50aac998 | 756 | DF_HARD_REGS | DF_RD_CHAIN | DF_RU_CHAIN | DF_FOR_REGALLOC); |
ed8d2920 MM |
757 | |
758 | if ((debug_new_regalloc & DUMP_DF) != 0) | |
759 | { | |
760 | rtx insn; | |
c263766c | 761 | df_dump (df, DF_HARD_REGS, dump_file); |
ed8d2920 MM |
762 | for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) |
763 | if (INSN_P (insn)) | |
c263766c | 764 | df_insn_debug_regno (df, insn, dump_file); |
ed8d2920 MM |
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) | |
c263766c | 798 | dump_file = NULL; |
ed8d2920 MM |
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 (); | |
3d042e77 | 808 | /* And they need useful classes too. */ |
c263766c RH |
809 | regclass (get_insns (), max_reg_num (), dump_file); |
810 | dump_file = ra_dump_file; | |
ed8d2920 MM |
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 | { | |
c263766c RH |
822 | ra_print_rtl_with_bb (dump_file, get_insns ()); |
823 | fflush (dump_file); | |
ed8d2920 MM |
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) | |
c263766c | 841 | ra_print_rtl_with_bb (dump_file, get_insns ()); |
ed8d2920 MM |
842 | |
843 | /* We might have new pseudos, so allocate the info arrays for them. */ | |
844 | if ((debug_new_regalloc & DUMP_SM) == 0) | |
c263766c | 845 | dump_file = NULL; |
ed8d2920 MM |
846 | no_new_pseudos = 0; |
847 | allocate_reg_info (max_reg_num (), FALSE, FALSE); | |
848 | no_new_pseudos = 1; | |
c263766c | 849 | dump_file = ra_dump_file; |
ed8d2920 MM |
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) | |
c263766c RH |
858 | dump_file = NULL; |
859 | life_analysis (get_insns (), dump_file, | |
ed8d2920 MM |
860 | PROP_DEATH_NOTES | PROP_LOG_LINKS | PROP_REG_INFO); |
861 | cleanup_cfg (CLEANUP_EXPENSIVE); | |
862 | recompute_reg_usage (get_insns (), TRUE); | |
c263766c RH |
863 | if (dump_file) |
864 | dump_flow_info (dump_file); | |
865 | dump_file = ra_dump_file; | |
ed8d2920 MM |
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) | |
c263766c RH |
885 | ra_print_rtl_with_bb (dump_file, get_insns ()); |
886 | dump_static_insn_cost (dump_file, | |
ed8d2920 MM |
887 | "after allocation/spilling, before reload", NULL); |
888 | ||
889 | /* Allocate the reg_equiv_memory_loc array for reload. */ | |
703ad42b | 890 | reg_equiv_memory_loc = xcalloc (max_regno, sizeof (rtx)); |
ed8d2920 MM |
891 | /* And possibly initialize it. */ |
892 | allocate_initial_values (reg_equiv_memory_loc); | |
893 | /* And one last regclass pass just before reload. */ | |
c263766c | 894 | regclass (get_insns (), max_reg_num (), dump_file); |
ed8d2920 MM |
895 | } |
896 | ||
897 | /* | |
898 | vim:cinoptions={.5s,g0,p5,t0,(0,^-0.5s,n-0.5s:tw=78:cindent:sw=4: | |
899 | */ |