libfuncs.h (LTI_synchronize): New libfunc_index.
[official-gcc.git] / gcc / ra-conflict.c
blobc693bc4d8b344d28495b85b78bbde60203ff543e
1 /* Allocate registers for pseudo-registers that span basic blocks.
2 Copyright (C) 2007, 2008 Free Software Foundation, Inc.
3 Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 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
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "machmode.h"
27 #include "hard-reg-set.h"
28 #include "rtl.h"
29 #include "tm_p.h"
30 #include "flags.h"
31 #include "regs.h"
32 #include "function.h"
33 #include "insn-config.h"
34 #include "recog.h"
35 #include "reload.h"
36 #include "output.h"
37 #include "toplev.h"
38 #include "tree-pass.h"
39 #include "timevar.h"
40 #include "df.h"
41 #include "vecprim.h"
42 #include "ra.h"
43 #include "sbitmap.h"
44 #include "sparseset.h"
46 /* Externs defined in regs.h. */
48 int max_allocno;
49 struct allocno *allocno;
50 HOST_WIDEST_FAST_INT *conflicts;
51 int *reg_allocno;
52 HOST_WIDE_INT *partial_bitnum;
53 HOST_WIDE_INT max_bitnum;
54 alloc_pool adjacency_pool;
55 adjacency_t **adjacency;
57 typedef struct df_ref * df_ref_t;
58 DEF_VEC_P(df_ref_t);
59 DEF_VEC_ALLOC_P(df_ref_t,heap);
61 /* Macros to determine the bit number within the triangular bit matrix for
62 the two allocnos Low and HIGH, with LOW strictly less than HIGH. */
64 #define CONFLICT_BITNUM(I, J) \
65 (((I) < (J)) ? (partial_bitnum[I] + (J)) : (partial_bitnum[J] + (I)))
67 #define CONFLICT_BITNUM_FAST(I, I_PARTIAL_BITNUM, J) \
68 (((I) < (J)) ? ((I_PARTIAL_BITNUM) + (J)) : (partial_bitnum[J] + (I)))
70 bool
71 conflict_p (int allocno1, int allocno2)
73 HOST_WIDE_INT bitnum;
74 HOST_WIDEST_FAST_INT word, mask;
76 #ifdef ENABLE_CHECKING
77 int blk1, blk2;
79 gcc_assert (allocno1 >= 0 && allocno1 < max_allocno);
80 gcc_assert (allocno2 >= 0 && allocno2 < max_allocno);
82 blk1 = regno_basic_block (allocno[allocno1].reg);
83 blk2 = regno_basic_block (allocno[allocno2].reg);
84 gcc_assert (blk1 == 0 || blk2 == 0 || blk1 == blk2);
85 #endif
87 if (allocno1 == allocno2)
88 /* By definition, an allocno does not conflict with itself. */
89 return 0;
91 bitnum = CONFLICT_BITNUM (allocno1, allocno2);
93 #ifdef ENABLE_CHECKING
94 gcc_assert (bitnum >= 0 && bitnum < max_bitnum);
95 #endif
97 word = conflicts[bitnum / HOST_BITS_PER_WIDEST_FAST_INT];
98 mask = (HOST_WIDEST_FAST_INT) 1 << (bitnum % HOST_BITS_PER_WIDEST_FAST_INT);
99 return (word & mask) != 0;
102 /* Add conflict edges between ALLOCNO1 and ALLOCNO2. */
104 static void
105 set_conflict (int allocno1, int allocno2)
107 HOST_WIDE_INT bitnum, index;
108 HOST_WIDEST_FAST_INT word, mask;
110 #ifdef ENABLE_CHECKING
111 int blk1, blk2;
113 gcc_assert (allocno1 >= 0 && allocno1 < max_allocno);
114 gcc_assert (allocno2 >= 0 && allocno2 < max_allocno);
116 blk1 = regno_basic_block (allocno[allocno1].reg);
117 blk2 = regno_basic_block (allocno[allocno2].reg);
118 gcc_assert (blk1 == 0 || blk2 == 0 || blk1 == blk2);
119 #endif
121 /* By definition, an allocno does not conflict with itself. */
122 if (allocno1 == allocno2)
123 return;
125 bitnum = CONFLICT_BITNUM (allocno1, allocno2);
127 #ifdef ENABLE_CHECKING
128 gcc_assert (bitnum >= 0 && bitnum < max_bitnum);
129 #endif
131 index = bitnum / HOST_BITS_PER_WIDEST_FAST_INT;
132 word = conflicts[index];
133 mask = (HOST_WIDEST_FAST_INT) 1 << (bitnum % HOST_BITS_PER_WIDEST_FAST_INT);
135 if ((word & mask) == 0)
137 conflicts[index] = word | mask;
138 add_neighbor (allocno1, allocno2);
139 add_neighbor (allocno2, allocno1);
143 /* Add conflict edges between ALLOCNO1 and all allocnos currently live. */
145 static void
146 set_conflicts (int allocno1, sparseset live)
148 int i;
149 HOST_WIDE_INT bitnum, index;
150 HOST_WIDEST_FAST_INT word, mask;
151 HOST_WIDE_INT partial_bitnum_allocno1;
153 #ifdef ENABLE_CHECKING
154 gcc_assert (allocno1 >= 0 && allocno1 < max_allocno);
155 #endif
157 partial_bitnum_allocno1 = partial_bitnum[allocno1];
159 EXECUTE_IF_SET_IN_SPARSESET (live, i)
161 /* By definition, an allocno does not conflict with itself. */
162 if (allocno1 == i)
163 continue;
165 #ifdef ENABLE_CHECKING
166 gcc_assert (i >= 0 && i < max_allocno);
167 #endif
169 bitnum = CONFLICT_BITNUM_FAST (allocno1, partial_bitnum_allocno1, i);
171 #ifdef ENABLE_CHECKING
172 gcc_assert (bitnum >= 0 && bitnum < max_bitnum);
173 #endif
175 index = bitnum / HOST_BITS_PER_WIDEST_FAST_INT;
176 word = conflicts[index];
177 mask = (HOST_WIDEST_FAST_INT) 1 << (bitnum % HOST_BITS_PER_WIDEST_FAST_INT);
179 if ((word & mask) == 0)
181 conflicts[index] = word | mask;
182 add_neighbor (allocno1, i);
183 add_neighbor (i, allocno1);
189 /* Add a conflict between R1 and R2. */
191 static void
192 record_one_conflict_between_regnos (enum machine_mode mode1, int r1,
193 enum machine_mode mode2, int r2)
195 int allocno1 = reg_allocno[r1];
196 int allocno2 = reg_allocno[r2];
198 if (dump_file)
199 fprintf (dump_file, " rocbr adding %d<=>%d\n", r1, r2);
201 if (allocno1 >= 0 && allocno2 >= 0)
202 set_conflict (allocno1, allocno2);
203 else if (allocno1 >= 0)
205 if (r2 < FIRST_PSEUDO_REGISTER)
206 add_to_hard_reg_set (&allocno[allocno1].hard_reg_conflicts, mode2, r2);
208 else if (allocno2 >= 0)
210 if (r1 < FIRST_PSEUDO_REGISTER)
211 add_to_hard_reg_set (&allocno[allocno2].hard_reg_conflicts, mode1, r1);
214 /* Now, recursively handle the reg_renumber cases. */
215 if (reg_renumber[r1] >= 0)
216 record_one_conflict_between_regnos (mode1, reg_renumber[r1], mode2, r2);
218 if (reg_renumber[r2] >= 0)
219 record_one_conflict_between_regnos (mode1, r1, mode2, reg_renumber[r2]);
223 /* Record a conflict between register REGNO and everything currently
224 live. REGNO must not be a pseudo reg that was allocated by
225 local_alloc; such numbers must be translated through reg_renumber
226 before calling here. */
228 static void
229 record_one_conflict (sparseset allocnos_live,
230 HARD_REG_SET *hard_regs_live, int regno)
232 int i;
234 if (regno < FIRST_PSEUDO_REGISTER)
235 /* When a hard register becomes live, record conflicts with live
236 pseudo regs. */
237 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
239 SET_HARD_REG_BIT (allocno[i].hard_reg_conflicts, regno);
240 if (dump_file)
241 fprintf (dump_file, " roc adding %d<=>%d\n", allocno[i].reg, regno);
243 else
244 /* When a pseudo-register becomes live, record conflicts first
245 with hard regs, then with other pseudo regs. */
247 int ialloc = reg_allocno[regno];
249 if (dump_file)
251 fprintf (dump_file, " roc adding %d<=>(", regno);
252 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
253 if (TEST_HARD_REG_BIT (*hard_regs_live, i)
254 && !TEST_HARD_REG_BIT (allocno[ialloc].hard_reg_conflicts, i))
255 fprintf (dump_file, "%d ", i);
257 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
259 if (!conflict_p (ialloc, i))
260 fprintf (dump_file, "%d ", allocno[i].reg);
262 fprintf (dump_file, ")\n");
265 IOR_HARD_REG_SET (allocno[ialloc].hard_reg_conflicts, *hard_regs_live);
266 set_conflicts (ialloc, allocnos_live);
271 /* Handle the case where REG is set by the insn being scanned, during
272 the backward scan to accumulate conflicts. Record a conflict with
273 all other registers already live.
275 REG might actually be something other than a register; if so, we do
276 nothing. */
278 static void
279 mark_reg_store (sparseset allocnos_live,
280 HARD_REG_SET *hard_regs_live,
281 struct df_ref *ref)
283 rtx reg = DF_REF_REG (ref);
284 unsigned int regno = DF_REF_REGNO (ref);
285 enum machine_mode mode = GET_MODE (reg);
287 /* Either this is one of the max_allocno pseudo regs not allocated,
288 or it is or has a hardware reg. First handle the pseudo-regs. */
289 if (regno >= FIRST_PSEUDO_REGISTER && reg_allocno[regno] >= 0)
290 record_one_conflict (allocnos_live, hard_regs_live, regno);
292 if (reg_renumber[regno] >= 0)
293 regno = reg_renumber[regno];
295 /* Handle hardware regs (and pseudos allocated to hard regs). */
296 if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
298 unsigned int start = regno;
299 unsigned int last = end_hard_regno (mode, regno);
300 if ((GET_CODE (reg) == SUBREG) && !DF_REF_FLAGS_IS_SET (ref, DF_REF_ZERO_EXTRACT))
302 start += subreg_regno_offset (regno, GET_MODE (SUBREG_REG (reg)),
303 SUBREG_BYTE (reg), GET_MODE (reg));
304 last = start + subreg_nregs_with_regno (regno, reg);
307 regno = start;
308 while (regno < last)
309 record_one_conflict (allocnos_live, hard_regs_live, regno++);
314 /* Return true if REGNO with MODE can be assigned to a register in
315 CL. */
317 static bool
318 may_overlap_class_p (enum machine_mode mode, unsigned int regno,
319 enum reg_class rc)
321 if (regno >= FIRST_PSEUDO_REGISTER)
323 enum reg_class pref_class = reg_preferred_class (regno);
324 enum reg_class alt_class = reg_alternate_class (regno);
325 return (reg_classes_intersect_p (rc, pref_class)
326 || reg_classes_intersect_p (rc, alt_class));
328 else
329 return in_hard_reg_set_p (reg_class_contents[rc], mode, regno);
333 /* SRC is an input operand to an instruction in which register DEST is
334 an output operand. SRC may be bound to a member of class SRC_CLASS
335 and DEST may be bound to an earlyclobbered register that overlaps
336 SRC_CLASS. If SRC is a register that might be allocated a member
337 of SRC_CLASS, add a conflict between it and DEST. */
339 static void
340 add_conflicts_for_earlyclobber (rtx dest, enum reg_class src_class, rtx src)
342 if (GET_CODE (src) == SUBREG)
343 src = SUBREG_REG (src);
344 if (REG_P (src)
345 && may_overlap_class_p (GET_MODE (src), REGNO (src), src_class))
346 record_one_conflict_between_regnos (GET_MODE (src), REGNO (src),
347 GET_MODE (dest), REGNO (dest));
351 /* Look at the defs in INSN and determine if any of them are marked as
352 early clobber. If they are marked as early clobber, add a conflict
353 between any input operand that could be allocated to the same
354 register. */
356 static void
357 set_conflicts_for_earlyclobber (rtx insn)
359 int alt;
360 int def;
361 int use;
363 extract_insn (insn);
364 preprocess_constraints ();
366 if (dump_file)
367 fprintf (dump_file, " starting early clobber conflicts.\n");
369 for (alt = 0; alt < recog_data.n_alternatives; alt++)
370 for (def = 0; def < recog_data.n_operands; def++)
371 if ((recog_op_alt[def][alt].earlyclobber)
372 && (recog_op_alt[def][alt].cl != NO_REGS))
374 rtx dreg = recog_data.operand[def];
375 enum machine_mode dmode = recog_data.operand_mode[def];
376 if (GET_CODE (dreg) == SUBREG)
377 dreg = SUBREG_REG (dreg);
378 if (REG_P (dreg)
379 && may_overlap_class_p (dmode, REGNO (dreg), recog_op_alt[def][alt].cl))
381 for (use = 0; use < recog_data.n_operands; use++)
382 if (use != def
383 && recog_data.operand_type[use] != OP_OUT
384 && reg_classes_intersect_p (recog_op_alt[def][alt].cl,
385 recog_op_alt[use][alt].cl))
387 add_conflicts_for_earlyclobber (dreg,
388 recog_op_alt[use][alt].cl,
389 recog_data.operand[use]);
390 /* Reload may end up swapping commutative operands,
391 so you have to take both orderings into account.
392 The constraints for the two operands can be
393 completely different. (Indeed, if the
394 constraints for the two operands are the same
395 for all alternatives, there's no point marking
396 them as commutative.) */
397 if (use < recog_data.n_operands + 1
398 && recog_data.constraints[use][0] == '%')
399 add_conflicts_for_earlyclobber (dreg,
400 recog_op_alt[use][alt].cl,
401 recog_data.operand[use + 1]);
407 /* Init LIVE_SUBREGS[ALLOCNUM] and LIVE_SUBREGS_USED[ALLOCNUM] using
408 REG to the number of nregs, and INIT_VALUE to get the
409 initialization. ALLOCNUM need not be the regno of REG. */
411 void
412 ra_init_live_subregs (bool init_value,
413 sbitmap *live_subregs,
414 int *live_subregs_used,
415 int allocnum,
416 rtx reg)
418 unsigned int regno = REGNO (SUBREG_REG (reg));
419 int size = GET_MODE_SIZE (GET_MODE (regno_reg_rtx[regno]));
421 gcc_assert (size > 0);
423 /* Been there, done that. */
424 if (live_subregs_used[allocnum])
425 return;
427 /* Create a new one with zeros. */
428 if (live_subregs[allocnum] == NULL)
429 live_subregs[allocnum] = sbitmap_alloc (size);
431 /* If the entire reg was live before blasting into subregs, we need
432 to init all of the subregs to ones else init to 0. */
433 if (init_value)
434 sbitmap_ones (live_subregs[allocnum]);
435 else
436 sbitmap_zero (live_subregs[allocnum]);
438 /* Set the number of bits that we really want. */
439 live_subregs_used[allocnum] = size;
443 /* Set REG to be not live in the sets ALLOCNOS_LIVE, LIVE_SUBREGS,
444 HARD_REGS_LIVE. DEF is the definition of the register. */
446 inline static void
447 clear_reg_in_live (sparseset allocnos_live,
448 sbitmap *live_subregs,
449 int *live_subregs_used,
450 HARD_REG_SET *hard_regs_live,
451 rtx reg, struct df_ref *def)
453 unsigned int regno = (GET_CODE (reg) == SUBREG)
454 ? REGNO (SUBREG_REG (reg)): REGNO (reg);
455 int allocnum = reg_allocno[regno];
457 if (allocnum >= 0)
459 if (GET_CODE (reg) == SUBREG
460 && !DF_REF_FLAGS_IS_SET (def, DF_REF_ZERO_EXTRACT))
462 unsigned int start = SUBREG_BYTE (reg);
463 unsigned int last = start + GET_MODE_SIZE (GET_MODE (reg));
465 ra_init_live_subregs (sparseset_bit_p (allocnos_live, allocnum),
466 live_subregs, live_subregs_used, allocnum, reg);
468 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_STRICT_LOW_PART))
470 /* Expand the range to cover entire words.
471 Bytes added here are "don't care". */
472 start = start / UNITS_PER_WORD * UNITS_PER_WORD;
473 last = ((last + UNITS_PER_WORD - 1)
474 / UNITS_PER_WORD * UNITS_PER_WORD);
477 /* Ignore the paradoxical bits. */
478 if ((int)last > live_subregs_used[allocnum])
479 last = live_subregs_used[allocnum];
481 while (start < last)
483 RESET_BIT (live_subregs[allocnum], start);
484 start++;
487 if (sbitmap_empty_p (live_subregs[allocnum]))
489 live_subregs_used[allocnum] = 0;
490 sparseset_clear_bit (allocnos_live, allocnum);
492 else
493 /* Set the allocnos live here because that bit has to be
494 true to get us to look at the live_subregs fields. */
495 sparseset_set_bit (allocnos_live, allocnum);
497 else
499 /* Resetting the live_subregs_used is effectively saying do not use the
500 subregs because we are writing the whole pseudo. */
501 live_subregs_used[allocnum] = 0;
502 sparseset_clear_bit (allocnos_live, allocnum);
506 if (regno >= FIRST_PSEUDO_REGISTER)
507 return;
509 /* Handle hardware regs (and pseudos allocated to hard regs). */
510 if (! fixed_regs[regno])
512 unsigned int start = regno;
513 if (GET_CODE (reg) == SUBREG
514 && !DF_REF_FLAGS_IS_SET (def, DF_REF_ZERO_EXTRACT))
516 unsigned int last;
517 start += SUBREG_BYTE (reg);
518 last = start + subreg_nregs_with_regno (regno, reg);
519 regno = start;
521 while (regno < last)
523 CLEAR_HARD_REG_BIT (*hard_regs_live, regno);
524 regno++;
527 else
528 remove_from_hard_reg_set (hard_regs_live, GET_MODE (reg), regno);
534 /* Set REG to be live in the sets ALLOCNOS_LIVE, LIVE_SUBREGS,
535 HARD_REGS_LIVE. If EXTRACT is false, assume that the entire reg is
536 set live even if REG is a subreg. */
538 inline static void
539 set_reg_in_live (sparseset allocnos_live,
540 sbitmap *live_subregs,
541 int *live_subregs_used,
542 HARD_REG_SET *hard_regs_live,
543 rtx reg,
544 bool extract)
546 unsigned int regno = (GET_CODE (reg) == SUBREG)
547 ? REGNO (SUBREG_REG (reg)): REGNO (reg);
548 int allocnum = reg_allocno[regno];
550 if (allocnum >= 0)
552 if ((GET_CODE (reg) == SUBREG) && !extract)
554 unsigned int start = SUBREG_BYTE (reg);
555 unsigned int last = start + GET_MODE_SIZE (GET_MODE (reg));
557 ra_init_live_subregs (sparseset_bit_p (allocnos_live, allocnum),
558 live_subregs, live_subregs_used, allocnum, reg);
560 /* Ignore the paradoxical bits. */
561 if ((int)last > live_subregs_used[allocnum])
562 last = live_subregs_used[allocnum];
564 while (start < last)
566 SET_BIT (live_subregs[allocnum], start);
567 start++;
570 else
571 /* Resetting the live_subregs_used is effectively saying do not use the
572 subregs because we are writing the whole pseudo. */
573 live_subregs_used[allocnum] = 0;
575 sparseset_set_bit (allocnos_live, allocnum);
578 if (regno >= FIRST_PSEUDO_REGISTER)
579 return;
581 /* Handle hardware regs (and pseudos allocated to hard regs). */
582 if (! fixed_regs[regno])
584 if ((GET_CODE (reg) == SUBREG) && !extract)
586 unsigned int start = regno;
587 unsigned int last;
589 start += subreg_regno_offset (regno, GET_MODE (SUBREG_REG (reg)),
590 SUBREG_BYTE (reg), GET_MODE (reg));
591 last = start + subreg_nregs_with_regno (regno, reg);
592 regno = start;
594 while (regno < last)
596 SET_HARD_REG_BIT (*hard_regs_live, regno);
597 regno++;
600 else
601 add_to_hard_reg_set (hard_regs_live, GET_MODE (reg), regno);
606 /* Add hard reg conflicts to RENUMBERS_LIVE assuming that pseudo in
607 allocno[ALLOCNUM] is allocated to a set of hard regs starting at
608 RENUMBER.
610 We are smart about the case where only subregs of REG have been
611 set, as indicated by LIVE_SUBREGS[ALLOCNUM] and
612 LIVE_SUBREGS_USED[ALLOCNUM]. See global_conflicts for description
613 of LIVE_SUBREGS and LIVE_SUBREGS_USED. */
615 inline static void
616 set_renumbers_live (HARD_REG_SET *renumbers_live,
617 sbitmap *live_subregs,
618 int *live_subregs_used,
619 int allocnum, int renumber)
621 /* The width of the pseudo. */
622 int nbytes = live_subregs_used[allocnum];
623 int regno = allocno[allocnum].reg;
624 enum machine_mode mode = GET_MODE (regno_reg_rtx[regno]);
626 if (dump_file)
627 fprintf (dump_file, " set_renumbers_live %d->%d ",
628 regno, renumber);
630 if (nbytes > 0)
632 int i;
633 sbitmap live_subs = live_subregs[allocnum];
635 /* First figure out how many hard regs we are considering using. */
636 int target_nregs = hard_regno_nregs[renumber][mode];
638 /* Now figure out the number of bytes per hard reg. Note that
639 this may be different that what would be obtained by looking
640 at the mode in the pseudo. For instance, a complex number
641 made up of 2 32-bit parts gets mapped to 2 hard regs, even if
642 the hardregs are 64-bit floating point values. */
643 int target_width = nbytes / target_nregs;
645 if (dump_file)
646 fprintf (dump_file, "target_nregs=%d target_width=%d nbytes=%d",
647 target_nregs, target_width, nbytes);
649 for (i = 0; i < target_nregs; i++)
651 int j;
652 bool set = false;
653 for (j = 0; j < target_width; j++)
655 int reg_start = i * target_width;
656 if (reg_start + j >= nbytes)
657 break;
658 set |= TEST_BIT (live_subs, reg_start + j);
661 if (set)
662 SET_HARD_REG_BIT (*renumbers_live, renumber + i);
665 else
666 add_to_hard_reg_set (renumbers_live, mode, renumber);
668 if (dump_file)
669 fprintf (dump_file, "\n");
672 /* Dump out a REF with its reg_renumber range to FILE using
673 PREFIX. */
675 static void
676 dump_ref (FILE *file,
677 const char * prefix,
678 const char * suffix,
679 rtx reg,
680 unsigned int regno,
681 sbitmap *live_subregs,
682 int *live_subregs_used
685 int allocnum = reg_allocno[regno];
687 fprintf (file, "%s %d", prefix, regno);
688 if (allocnum >= 0
689 && live_subregs_used[allocnum] > 0)
691 int j;
692 char s = '[';
694 for (j = 0; j < live_subregs_used[allocnum]; j++)
695 if (TEST_BIT (live_subregs[allocnum], j))
697 fprintf (dump_file, "%c%d", s, j);
698 s = ',';
700 fprintf (dump_file, "]");
703 if (reg_renumber[regno] >= 0)
705 enum machine_mode mode = GET_MODE (reg);
706 unsigned int start;
707 unsigned int last;
709 regno = reg_renumber[regno];
711 start = regno;
712 last = end_hard_regno (mode, regno);
713 if (GET_CODE (reg) == SUBREG)
715 start += subreg_regno_offset (regno, GET_MODE (SUBREG_REG (reg)),
716 SUBREG_BYTE (reg), GET_MODE (reg));
717 last = start + subreg_nregs_with_regno (regno, reg);
720 if (start == last - 1)
721 fprintf (file, "(%d)", start);
722 else
723 fprintf (file, "(%d:%d..%d)", regno, start, last-1);
725 fprintf (file, suffix);
729 /* Scan the rtl code and record all conflicts and register preferences in the
730 conflict matrices and preference tables. */
732 void
733 global_conflicts (void)
735 unsigned int i;
736 basic_block bb;
737 rtx insn;
739 /* Regs that have allocnos can be in either
740 hard_regs_live (if regno < FIRST_PSEUDO_REGISTER) or
741 allocnos_live (if regno >= FIRST_PSEUDO_REGISTER) or
742 both if local_alloc has preallocated it and reg_renumber >= 0. */
744 HARD_REG_SET hard_regs_live;
745 HARD_REG_SET renumbers_live;
746 sparseset allocnos_live;
747 bitmap live = BITMAP_ALLOC (NULL);
748 VEC (df_ref_t, heap) *clobbers = NULL;
749 VEC (df_ref_t, heap) *dying_regs = NULL;
751 /* live_subregs is a vector used to keep accurate information about
752 which hardregs are live in multiword pseudos. live_subregs and
753 live_subregs_used are indexed by reg_allocno. The live_subreg
754 entry for a particular pseudo is a bitmap with one bit per byte
755 of the register. It is only used if the corresponding element is
756 non zero in live_subregs_used. The value in live_subregs_used is
757 number of bytes that the pseudo can occupy. */
758 sbitmap *live_subregs = XCNEWVEC (sbitmap, max_allocno);
759 int *live_subregs_used = XNEWVEC (int, max_allocno);
761 if (dump_file)
763 fprintf (dump_file, "fixed registers : ");
764 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
765 if (fixed_regs[i])
766 fprintf (dump_file, "%d ", i);
767 fprintf (dump_file, "\n");
770 allocnos_live = sparseset_alloc (max_allocno);
772 FOR_EACH_BB (bb)
774 bitmap_iterator bi;
776 bitmap_copy (live, DF_LIVE_OUT (bb));
777 df_simulate_artificial_refs_at_end (bb, live);
779 sparseset_clear (allocnos_live);
780 memset (live_subregs_used, 0, max_allocno * sizeof (int));
781 CLEAR_HARD_REG_SET (hard_regs_live);
782 CLEAR_HARD_REG_SET (renumbers_live);
784 /* Initialize allocnos_live and hard_regs_live for bottom of block. */
785 EXECUTE_IF_SET_IN_BITMAP (live, 0, i, bi)
787 if (i >= FIRST_PSEUDO_REGISTER)
788 break;
789 if (! fixed_regs[i])
790 SET_HARD_REG_BIT (hard_regs_live, i);
793 EXECUTE_IF_SET_IN_BITMAP (live, FIRST_PSEUDO_REGISTER, i, bi)
795 int allocnum = reg_allocno[i];
797 if (allocnum >= 0)
799 int renumber = reg_renumber[i];
800 rtx reg = regno_reg_rtx[i];
802 set_reg_in_live (allocnos_live, live_subregs, live_subregs_used,
803 &hard_regs_live, reg, false);
804 if (renumber >= 0 && renumber < FIRST_PSEUDO_REGISTER)
805 set_renumbers_live (&renumbers_live, live_subregs, live_subregs_used,
806 allocnum, renumber);
810 if (dump_file)
811 fprintf (dump_file, "\nstarting basic block %d\n\n", bb->index);
813 FOR_BB_INSNS_REVERSE (bb, insn)
815 unsigned int uid = INSN_UID (insn);
816 struct df_ref **def_rec;
817 struct df_ref **use_rec;
819 if (!INSN_P (insn))
820 continue;
822 if (dump_file)
824 fprintf (dump_file, "insn = %d live = hardregs [", uid);
826 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
827 if (TEST_HARD_REG_BIT (hard_regs_live, i))
828 fprintf (dump_file, "%d ", i);
830 fprintf (dump_file, "] renumbered [");
831 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
832 if (TEST_HARD_REG_BIT (renumbers_live, i))
833 fprintf (dump_file, "%d ", i);
835 fprintf (dump_file, "] pseudos [");
836 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
838 dump_ref (dump_file, " ", "", regno_reg_rtx[allocno[i].reg],
839 allocno[i].reg, live_subregs, live_subregs_used);
841 fprintf (dump_file, "]\n");
844 /* Add the defs into live. Most of them will already be
845 there, the ones that are missing are the unused ones and
846 the clobbers. We do this in order to make sure that
847 interferences are added between every def and everything
848 that is live across the insn. These defs will be removed
849 later. */
850 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
852 struct df_ref *def = *def_rec;
854 /* FIXME: Ignoring may clobbers is technically the wrong
855 thing to do. However the old version of the this
856 code ignores may clobbers (and instead has many
857 places in the register allocator to handle these
858 constraints). It is quite likely that with a new
859 allocator, the correct thing to do is to not ignore
860 the constraints and then do not put in the large
861 number of special checks. */
862 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
864 rtx reg = DF_REF_REG (def);
865 set_reg_in_live (allocnos_live, live_subregs, live_subregs_used,
866 &hard_regs_live, reg,
867 DF_REF_FLAGS_IS_SET (def, DF_REF_ZERO_EXTRACT));
868 if (dump_file)
869 dump_ref (dump_file, " adding def", "\n",
870 reg, DF_REF_REGNO (def), live_subregs, live_subregs_used);
874 /* Add the hardregs into renumbers_live to build the
875 interferences. Renumbers_live will be rebuilt in the
876 next step from scratch, so corrupting it here is no
877 problem. */
878 IOR_HARD_REG_SET (renumbers_live, hard_regs_live);
880 /* Add the interferences for the defs. */
881 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
883 struct df_ref *def = *def_rec;
884 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
885 mark_reg_store (allocnos_live, &renumbers_live, def);
888 /* Remove the defs from the live sets. Leave the partial
889 and conditional defs in the set because they do not
890 kill. */
891 VEC_truncate (df_ref_t, clobbers, 0);
892 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
894 struct df_ref *def = *def_rec;
896 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL))
898 rtx reg = DF_REF_REG (def);
900 clear_reg_in_live (allocnos_live, live_subregs, live_subregs_used,
901 &hard_regs_live, reg, def);
902 if (dump_file)
903 dump_ref (dump_file, " clearing def", "\n",
904 reg, DF_REF_REGNO (def), live_subregs, live_subregs_used);
907 if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER))
908 VEC_safe_push (df_ref_t, heap, clobbers, def);
911 /* Go thru all of the live pseudos and reset renumbers_live.
912 We must start from scratch here because there could have
913 been several pseudos alive that have the same
914 reg_renumber and if we see a clobber for one of them, we
915 cannot not want to kill the renumbers from the other
916 pseudos. */
917 CLEAR_HARD_REG_SET (renumbers_live);
918 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
920 unsigned int regno = allocno[i].reg;
921 int renumber = reg_renumber[regno];
923 if (renumber >= 0 && renumber < FIRST_PSEUDO_REGISTER)
924 set_renumbers_live (&renumbers_live, live_subregs, live_subregs_used,
925 i, renumber);
928 /* Add the uses to the live sets. Keep track of the regs
929 that are dying inside the insn, this set will be useful
930 later. */
931 VEC_truncate (df_ref_t, dying_regs, 0);
932 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
934 struct df_ref *use = *use_rec;
935 unsigned int regno = DF_REF_REGNO (use);
936 bool added = false;
937 int renumber = reg_renumber[regno];
938 int allocnum = reg_allocno[regno];
939 bool renumbering = false;
940 rtx reg = DF_REF_REG (use);
942 /* DF_REF_READ_WRITE on a use means that this use is
943 fabricated from a def that is a partial set to a
944 multiword reg. Here, we only model the subreg case
945 precisely so we do not need to look at the fabricated
946 use unless that set also happens to wrapped in a
947 ZERO_EXTRACT. */
948 if (DF_REF_FLAGS_IS_SET (use, DF_REF_READ_WRITE)
949 && (!DF_REF_FLAGS_IS_SET (use, DF_REF_ZERO_EXTRACT))
950 && DF_REF_FLAGS_IS_SET (use, DF_REF_SUBREG))
951 continue;
953 if (dump_file)
954 dump_ref (dump_file, " seeing use", "\n",
955 reg, regno, live_subregs, live_subregs_used);
957 if (allocnum >= 0)
959 if (GET_CODE (reg) == SUBREG
960 && !DF_REF_FLAGS_IS_SET (use, DF_REF_ZERO_EXTRACT))
962 unsigned int start = SUBREG_BYTE (reg);
963 unsigned int last = start + GET_MODE_SIZE (GET_MODE (reg));
965 ra_init_live_subregs (sparseset_bit_p (allocnos_live, allocnum),
966 live_subregs, live_subregs_used, allocnum, reg);
968 /* Ignore the paradoxical bits. */
969 if ((int)last > live_subregs_used[allocnum])
970 last = live_subregs_used[allocnum];
972 while (start < last)
974 if (!TEST_BIT (live_subregs[allocnum], start))
976 if (dump_file)
977 fprintf (dump_file, " dying pseudo subreg %d[%d]\n", regno, start);
978 SET_BIT (live_subregs[allocnum], start);
980 added = true;
982 start++;
985 sparseset_set_bit (allocnos_live, allocnum);
986 if (renumber >= 0 && renumber < FIRST_PSEUDO_REGISTER)
987 set_renumbers_live (&renumbers_live, live_subregs, live_subregs_used,
988 allocnum, renumber);
990 else if (live_subregs_used[allocnum] > 0
991 || !sparseset_bit_p (allocnos_live, allocnum))
993 if (dump_file)
994 fprintf (dump_file, " %sdying pseudo\n",
995 (live_subregs_used[allocnum] > 0) ? "partially ": "");
996 /* Resetting the live_subregs_used is
997 effectively saying do not use the subregs
998 because we are reading the whole pseudo. */
999 live_subregs_used[allocnum] = 0;
1000 sparseset_set_bit (allocnos_live, allocnum);
1001 if (renumber >= 0 && renumber < FIRST_PSEUDO_REGISTER)
1002 set_renumbers_live (&renumbers_live, live_subregs, live_subregs_used,
1003 allocnum, renumber);
1004 added = true;
1008 if (renumber >= 0 && renumber < FIRST_PSEUDO_REGISTER)
1010 regno = renumber;
1011 renumbering = true;
1014 if (regno < FIRST_PSEUDO_REGISTER)
1016 unsigned int start = regno;
1017 unsigned int last;
1018 if (GET_CODE (reg) == SUBREG)
1020 start += subreg_regno_offset (regno, GET_MODE (SUBREG_REG (reg)),
1021 SUBREG_BYTE (reg), GET_MODE (reg));
1022 last = start + subreg_nregs_with_regno (regno, reg);
1024 else
1025 last = end_hard_regno (GET_MODE (reg), regno);
1027 regno = start;
1028 while (regno < last)
1030 if ((!TEST_HARD_REG_BIT (hard_regs_live, regno))
1031 && (!TEST_HARD_REG_BIT (renumbers_live, regno))
1032 && ! fixed_regs[regno])
1034 if (dump_file)
1035 fprintf (dump_file, " dying hard reg %d\n", regno);
1036 if (renumbering)
1037 SET_HARD_REG_BIT (renumbers_live, regno);
1038 else
1039 SET_HARD_REG_BIT (hard_regs_live, regno);
1041 added = true;
1043 regno++;
1046 if (added)
1047 VEC_safe_push (df_ref_t, heap, dying_regs, use);
1050 /* These three cases are all closely related, they all deal
1051 with some set of outputs of the insn need to conflict
1052 with some of the registers that are used by the insn but
1053 die within the insn. If no registers die within the insn,
1054 the tests can be skipped. */
1056 if (VEC_length (df_ref_t, dying_regs) > 0)
1058 int k;
1059 /* There appears to be an ambiguity as to what a clobber
1060 means in an insn. In some cases, the clobber happens
1061 within the processing of the insn and in some cases
1062 it happens at the end of processing the insn. There
1063 is currently no way to distinguish these two cases so
1064 this code causes real clobbers to interfere with
1065 registers that die within an insn.
1067 This is consistent with the prior version of
1068 interference graph builder but is was discovered
1069 while developing this version of the code, that on
1070 some architectures such as the x86-64, the clobbers
1071 only appear to happen at the end of the insn.
1072 However, the ppc-32 contains clobbers for which these
1073 interferences are necessary.
1075 FIXME: We should consider either adding a new kind of
1076 clobber, or adding a flag to the clobber distinguish
1077 these two cases. */
1078 if (dump_file && VEC_length (df_ref_t, clobbers))
1079 fprintf (dump_file, " clobber conflicts\n");
1080 for (k = VEC_length (df_ref_t, clobbers) - 1; k >= 0; k--)
1082 struct df_ref *def = VEC_index (df_ref_t, clobbers, k);
1083 int j;
1085 for (j = VEC_length (df_ref_t, dying_regs) - 1; j >= 0; j--)
1087 struct df_ref *use = VEC_index (df_ref_t, dying_regs, j);
1088 record_one_conflict_between_regnos (GET_MODE (DF_REF_REG (def)),
1089 DF_REF_REGNO (def),
1090 GET_MODE (DF_REF_REG (use)),
1091 DF_REF_REGNO (use));
1095 /* Early clobbers, by definition, need to not only
1096 clobber the registers that are live across the insn
1097 but need to clobber the registers that die within the
1098 insn. The clobbering for registers live across the
1099 insn is handled above. */
1100 set_conflicts_for_earlyclobber (insn);
1102 /* If INSN is a store with multiple outputs, then any
1103 reg that dies here and is used inside of the address
1104 of the output must conflict with the other outputs.
1106 FIXME: There has been some discussion as to whether
1107 this is right place to handle this issue. This is a
1108 hold over from an early version global conflicts.
1110 1) There is some evidence that code only deals with a
1111 bug that is only on the m68k. The conditions of this
1112 test are such that this case only triggers for a very
1113 peculiar insn, one that is a parallel where one of
1114 the sets is a store and the other sets a reg that is
1115 used in the address of the store. See
1116 http://gcc.gnu.org/ml/gcc-patches/1998-12/msg00259.html
1118 2) The situation that this is addressing is a bug in
1119 the part of reload that handles stores, adding this
1120 conflict only hides the problem. (Of course no one
1121 really wants to fix reload so it is understandable
1122 why a bandaid was just added here.)
1124 Just because an output is unused does not mean the
1125 compiler can assume the side effect will not occur.
1126 Consider if REG appears in the address of an output
1127 and we reload the output. If we allocate REG to the
1128 same hard register as an unused output we could set
1129 the hard register before the output reload insn.
1131 3) This could actually be handled by making the other
1132 (non store) operand of the insn be an early clobber.
1133 This would insert the same conflict, even if it is
1134 not technically an early clobber. */
1136 /* It is unsafe to use !single_set here since it will ignore an
1137 unused output. */
1138 if (GET_CODE (PATTERN (insn)) == PARALLEL && multiple_sets (insn))
1140 int j;
1141 if (dump_file)
1142 fprintf (dump_file, " multiple sets\n");
1143 for (j = VEC_length (df_ref_t, dying_regs) - 1; j >= 0; j--)
1145 int used_in_output = 0;
1146 struct df_ref *use = VEC_index (df_ref_t, dying_regs, j);
1147 rtx reg = DF_REF_REG (use);
1148 int uregno = DF_REF_REGNO (use);
1149 enum machine_mode umode = GET_MODE (DF_REF_REG (use));
1150 int k;
1152 for (k = XVECLEN (PATTERN (insn), 0) - 1; k >= 0; k--)
1154 rtx set = XVECEXP (PATTERN (insn), 0, k);
1155 if (GET_CODE (set) == SET
1156 && !REG_P (SET_DEST (set))
1157 && !rtx_equal_p (reg, SET_DEST (set))
1158 && reg_overlap_mentioned_p (reg, SET_DEST (set)))
1159 used_in_output = 1;
1161 if (used_in_output)
1162 for (k = XVECLEN (PATTERN (insn), 0) - 1; k >= 0; k--)
1164 rtx set = XVECEXP (PATTERN (insn), 0, k);
1165 if (GET_CODE (set) == SET
1166 && REG_P (SET_DEST (set))
1167 && !rtx_equal_p (reg, SET_DEST (set)))
1168 record_one_conflict_between_regnos (GET_MODE (SET_DEST (set)),
1169 REGNO (SET_DEST (set)),
1170 umode, uregno);
1177 /* Add the renumbers live to the hard_regs_live for the next few
1178 calls. All of this gets recomputed at the top of the loop so
1179 there is no harm. */
1180 IOR_HARD_REG_SET (hard_regs_live, renumbers_live);
1182 #ifdef EH_RETURN_DATA_REGNO
1183 if (bb_has_eh_pred (bb))
1185 unsigned int i;
1187 for (i = 0; ; ++i)
1189 unsigned int regno = EH_RETURN_DATA_REGNO (i);
1190 if (regno == INVALID_REGNUM)
1191 break;
1192 record_one_conflict (allocnos_live, &hard_regs_live, regno);
1195 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
1197 allocno[i].no_eh_reg = 1;
1200 #endif
1202 if (bb_has_abnormal_pred (bb))
1204 unsigned int i;
1205 #ifdef STACK_REGS
1206 /* Pseudos can't go in stack regs at the start of a basic block that
1207 is reached by an abnormal edge. Likewise for call clobbered regs,
1208 because caller-save, fixup_abnormal_edges and possibly the table
1209 driven EH machinery are not quite ready to handle such regs live
1210 across such edges. */
1211 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
1213 allocno[i].no_stack_reg = 1;
1216 for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
1217 record_one_conflict (allocnos_live, &hard_regs_live, i);
1218 #endif
1220 /* No need to record conflicts for call clobbered regs if we have
1221 nonlocal labels around, as we don't ever try to allocate such
1222 regs in this case. */
1223 if (! cfun->has_nonlocal_label)
1224 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1225 if (call_used_regs [i])
1226 record_one_conflict (allocnos_live, &hard_regs_live, i);
1230 for (i = 0; i < (unsigned int)max_allocno; i++)
1231 if (live_subregs[i])
1232 free (live_subregs[i]);
1234 /* Clean up. */
1235 free (allocnos_live);
1236 free (live_subregs);
1237 free (live_subregs_used);
1238 VEC_free (df_ref_t, heap, dying_regs);
1239 VEC_free (df_ref_t, heap, clobbers);
1240 BITMAP_FREE (live);