/* Allocate registers for pseudo-registers that span basic blocks. Copyright (C) 2007 Free Software Foundation, Inc. Contributed by Kenneth Zadeck This file is part of GCC. GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see . */ #include "config.h" #include "system.h" #include "coretypes.h" #include "tm.h" #include "machmode.h" #include "hard-reg-set.h" #include "rtl.h" #include "tm_p.h" #include "flags.h" #include "regs.h" #include "function.h" #include "insn-config.h" #include "recog.h" #include "reload.h" #include "output.h" #include "toplev.h" #include "tree-pass.h" #include "timevar.h" #include "df.h" #include "vecprim.h" #include "ra.h" #include "sbitmap.h" #include "sparseset.h" /* Externs defined in regs.h. */ int max_allocno; struct allocno *allocno; HOST_WIDEST_FAST_INT *conflicts; int *reg_allocno; HOST_WIDE_INT *partial_bitnum; HOST_WIDE_INT max_bitnum; alloc_pool adjacency_pool; adjacency_t **adjacency; typedef struct df_ref * df_ref_t; DEF_VEC_P(df_ref_t); DEF_VEC_ALLOC_P(df_ref_t,heap); /* Macros to determine the bit number within the triangular bit matrix for the two allocnos Low and HIGH, with LOW strictly less than HIGH. */ #define CONFLICT_BITNUM(I, J) \ (((I) < (J)) ? (partial_bitnum[I] + (J)) : (partial_bitnum[J] + (I))) #define CONFLICT_BITNUM_FAST(I, I_PARTIAL_BITNUM, J) \ (((I) < (J)) ? ((I_PARTIAL_BITNUM) + (J)) : (partial_bitnum[J] + (I))) bool conflict_p (int allocno1, int allocno2) { HOST_WIDE_INT bitnum; HOST_WIDEST_FAST_INT word, mask; #ifdef ENABLE_CHECKING int blk1, blk2; gcc_assert (allocno1 >= 0 && allocno1 < max_allocno); gcc_assert (allocno2 >= 0 && allocno2 < max_allocno); blk1 = regno_basic_block (allocno[allocno1].reg); blk2 = regno_basic_block (allocno[allocno2].reg); gcc_assert (blk1 == 0 || blk2 == 0 || blk1 == blk2); #endif if (allocno1 == allocno2) /* By definition, an allocno does not conflict with itself. */ return 0; bitnum = CONFLICT_BITNUM (allocno1, allocno2); #ifdef ENABLE_CHECKING gcc_assert (bitnum >= 0 && bitnum < max_bitnum); #endif word = conflicts[bitnum / HOST_BITS_PER_WIDEST_FAST_INT]; mask = (HOST_WIDEST_FAST_INT) 1 << (bitnum % HOST_BITS_PER_WIDEST_FAST_INT); return (word & mask) != 0; } /* Add conflict edges between ALLOCNO1 and ALLOCNO2. */ static void set_conflict (int allocno1, int allocno2) { HOST_WIDE_INT bitnum, index; HOST_WIDEST_FAST_INT word, mask; #ifdef ENABLE_CHECKING int blk1, blk2; gcc_assert (allocno1 >= 0 && allocno1 < max_allocno); gcc_assert (allocno2 >= 0 && allocno2 < max_allocno); blk1 = regno_basic_block (allocno[allocno1].reg); blk2 = regno_basic_block (allocno[allocno2].reg); gcc_assert (blk1 == 0 || blk2 == 0 || blk1 == blk2); #endif /* By definition, an allocno does not conflict with itself. */ if (allocno1 == allocno2) return; bitnum = CONFLICT_BITNUM (allocno1, allocno2); #ifdef ENABLE_CHECKING gcc_assert (bitnum >= 0 && bitnum < max_bitnum); #endif index = bitnum / HOST_BITS_PER_WIDEST_FAST_INT; word = conflicts[index]; mask = (HOST_WIDEST_FAST_INT) 1 << (bitnum % HOST_BITS_PER_WIDEST_FAST_INT); if ((word & mask) == 0) { conflicts[index] = word | mask; add_neighbor (allocno1, allocno2); add_neighbor (allocno2, allocno1); } } /* Add conflict edges between ALLOCNO1 and all allocnos currently live. */ static void set_conflicts (int allocno1, sparseset live) { int i; HOST_WIDE_INT bitnum, index; HOST_WIDEST_FAST_INT word, mask; HOST_WIDE_INT partial_bitnum_allocno1; #ifdef ENABLE_CHECKING gcc_assert (allocno1 >= 0 && allocno1 < max_allocno); #endif partial_bitnum_allocno1 = partial_bitnum[allocno1]; EXECUTE_IF_SET_IN_SPARSESET (live, i) { /* By definition, an allocno does not conflict with itself. */ if (allocno1 == i) continue; #ifdef ENABLE_CHECKING gcc_assert (i >= 0 && i < max_allocno); #endif bitnum = CONFLICT_BITNUM_FAST (allocno1, partial_bitnum_allocno1, i); #ifdef ENABLE_CHECKING gcc_assert (bitnum >= 0 && bitnum < max_bitnum); #endif index = bitnum / HOST_BITS_PER_WIDEST_FAST_INT; word = conflicts[index]; mask = (HOST_WIDEST_FAST_INT) 1 << (bitnum % HOST_BITS_PER_WIDEST_FAST_INT); if ((word & mask) == 0) { conflicts[index] = word | mask; add_neighbor (allocno1, i); add_neighbor (i, allocno1); } } } /* Add a conflict between R1 and R2. */ static void record_one_conflict_between_regnos (enum machine_mode mode1, int r1, enum machine_mode mode2, int r2) { int allocno1 = reg_allocno[r1]; int allocno2 = reg_allocno[r2]; if (dump_file) fprintf (dump_file, " rocbr adding %d<=>%d\n", r1, r2); if (allocno1 >= 0 && allocno2 >= 0) set_conflict (allocno1, allocno2); else if (allocno1 >= 0) { if (r2 < FIRST_PSEUDO_REGISTER) add_to_hard_reg_set (&allocno[allocno1].hard_reg_conflicts, mode2, r2); } else if (allocno2 >= 0) { if (r1 < FIRST_PSEUDO_REGISTER) add_to_hard_reg_set (&allocno[allocno2].hard_reg_conflicts, mode1, r1); } /* Now, recursively handle the reg_renumber cases. */ if (reg_renumber[r1] >= 0) record_one_conflict_between_regnos (mode1, reg_renumber[r1], mode2, r2); if (reg_renumber[r2] >= 0) record_one_conflict_between_regnos (mode1, r1, mode2, reg_renumber[r2]); } /* Record a conflict between register REGNO and everything currently live. REGNO must not be a pseudo reg that was allocated by local_alloc; such numbers must be translated through reg_renumber before calling here. */ static void record_one_conflict (sparseset allocnos_live, HARD_REG_SET *hard_regs_live, int regno) { int i; if (regno < FIRST_PSEUDO_REGISTER) /* When a hard register becomes live, record conflicts with live pseudo regs. */ EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i) { SET_HARD_REG_BIT (allocno[i].hard_reg_conflicts, regno); if (dump_file) fprintf (dump_file, " roc adding %d<=>%d\n", allocno[i].reg, regno); } else /* When a pseudo-register becomes live, record conflicts first with hard regs, then with other pseudo regs. */ { int ialloc = reg_allocno[regno]; if (dump_file) { fprintf (dump_file, " roc adding %d<=>(", regno); for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) if (TEST_HARD_REG_BIT (*hard_regs_live, i) && !TEST_HARD_REG_BIT (allocno[ialloc].hard_reg_conflicts, i)) fprintf (dump_file, "%d ", i); EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i) { if (!conflict_p (ialloc, i)) fprintf (dump_file, "%d ", allocno[i].reg); } fprintf (dump_file, ")\n"); } IOR_HARD_REG_SET (allocno[ialloc].hard_reg_conflicts, *hard_regs_live); set_conflicts (ialloc, allocnos_live); } } /* Handle the case where REG is set by the insn being scanned, during the backward scan to accumulate conflicts. Record a conflict with all other registers already live. REG might actually be something other than a register; if so, we do nothing. */ static void mark_reg_store (sparseset allocnos_live, HARD_REG_SET *hard_regs_live, struct df_ref *ref) { rtx reg = DF_REF_REG (ref); unsigned int regno = DF_REF_REGNO (ref); enum machine_mode mode = GET_MODE (reg); /* Either this is one of the max_allocno pseudo regs not allocated, or it is or has a hardware reg. First handle the pseudo-regs. */ if (regno >= FIRST_PSEUDO_REGISTER && reg_allocno[regno] >= 0) record_one_conflict (allocnos_live, hard_regs_live, regno); if (reg_renumber[regno] >= 0) regno = reg_renumber[regno]; /* Handle hardware regs (and pseudos allocated to hard regs). */ if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno]) { unsigned int start = regno; unsigned int last = end_hard_regno (mode, regno); if ((GET_CODE (reg) == SUBREG) && !DF_REF_FLAGS_IS_SET (ref, DF_REF_EXTRACT)) { start += subreg_regno_offset (regno, GET_MODE (SUBREG_REG (reg)), SUBREG_BYTE (reg), GET_MODE (reg)); last = start + subreg_nregs_with_regno (regno, reg); } regno = start; while (regno < last) record_one_conflict (allocnos_live, hard_regs_live, regno++); } } /* Return true if REGNO with MODE can be assigned to a register in CL. */ static bool may_overlap_class_p (enum machine_mode mode, unsigned int regno, enum reg_class rc) { if (regno >= FIRST_PSEUDO_REGISTER) { enum reg_class pref_class = reg_preferred_class (regno); enum reg_class alt_class = reg_alternate_class (regno); return (reg_classes_intersect_p (rc, pref_class) || reg_classes_intersect_p (rc, alt_class)); } else return in_hard_reg_set_p (reg_class_contents[rc], mode, regno); } /* SRC is an input operand to an instruction in which register DEST is an output operand. SRC may be bound to a member of class SRC_CLASS and DEST may be bound to an earlyclobbered register that overlaps SRC_CLASS. If SRC is a register that might be allocated a member of SRC_CLASS, add a conflict between it and DEST. */ static void add_conflicts_for_earlyclobber (rtx dest, enum reg_class src_class, rtx src) { if (GET_CODE (src) == SUBREG) src = SUBREG_REG (src); if (REG_P (src) && may_overlap_class_p (GET_MODE (src), REGNO (src), src_class)) record_one_conflict_between_regnos (GET_MODE (src), REGNO (src), GET_MODE (dest), REGNO (dest)); } /* Look at the defs in INSN and determine if any of them are marked as early clobber. If they are marked as early clobber, add a conflict between any input operand that could be allocated to the same register. */ static void set_conflicts_for_earlyclobber (rtx insn) { int alt; int def; int use; extract_insn (insn); preprocess_constraints (); if (dump_file) fprintf (dump_file, " starting early clobber conflicts.\n"); for (alt = 0; alt < recog_data.n_alternatives; alt++) for (def = 0; def < recog_data.n_operands; def++) if ((recog_op_alt[def][alt].earlyclobber) && (recog_op_alt[def][alt].cl != NO_REGS)) { rtx dreg = recog_data.operand[def]; enum machine_mode dmode = recog_data.operand_mode[def]; if (GET_CODE (dreg) == SUBREG) dreg = SUBREG_REG (dreg); if (REG_P (dreg) && may_overlap_class_p (dmode, REGNO (dreg), recog_op_alt[def][alt].cl)) for (use = 0; use < recog_data.n_operands; use++) if (use != def && recog_data.operand_type[use] != OP_OUT && reg_classes_intersect_p (recog_op_alt[def][alt].cl, recog_op_alt[use][alt].cl)) { add_conflicts_for_earlyclobber (dreg, recog_op_alt[use][alt].cl, recog_data.operand[use]); /* Reload may end up swapping commutative operands, so you have to take both orderings into account. The constraints for the two operands can be completely different. (Indeed, if the constraints for the two operands are the same for all alternatives, there's no point marking them as commutative.) */ if (use < recog_data.n_operands + 1 && recog_data.constraints[use][0] == '%') add_conflicts_for_earlyclobber (dreg, recog_op_alt[use][alt].cl, recog_data.operand[use + 1]); } } } /* Init LIVE_SUBREGS[ALLOCNUM] and LIVE_SUBREGS_USED[ALLOCNUM] using REG to the the number of nregs, and INIT_VALUE to get the initialization. ALLOCNUM need not be the regno of REG. */ void ra_init_live_subregs (bool init_value, sbitmap *live_subregs, int *live_subregs_used, int allocnum, rtx reg) { unsigned int regno = REGNO (SUBREG_REG (reg)); int size = GET_MODE_SIZE (GET_MODE (regno_reg_rtx[regno])); gcc_assert (size > 0); /* Been there, done that. */ if (live_subregs_used[allocnum]) return; /* Create a new one with zeros. */ if (live_subregs[allocnum] == NULL) live_subregs[allocnum] = sbitmap_alloc (size); /* If the entire reg was live before blasting into subregs, we need to init all of the subregs to ones else init to 0. */ if (init_value) sbitmap_ones (live_subregs[allocnum]); else sbitmap_zero (live_subregs[allocnum]); /* Set the number of bits that we really want. */ live_subregs_used[allocnum] = size; } /* Set REG to be not live in the sets ALLOCNOS_LIVE, LIVE_SUBREGS, HARD_REGS_LIVE. DEF is the definition of the register. */ inline static void clear_reg_in_live (sparseset allocnos_live, sbitmap *live_subregs, int *live_subregs_used, HARD_REG_SET *hard_regs_live, rtx reg, struct df_ref *def) { unsigned int regno = (GET_CODE (reg) == SUBREG) ? REGNO (SUBREG_REG (reg)): REGNO (reg); int allocnum = reg_allocno[regno]; if (allocnum >= 0) { if (GET_CODE (reg) == SUBREG && !DF_REF_FLAGS_IS_SET (def, DF_REF_EXTRACT)) { unsigned int start = SUBREG_BYTE (reg); unsigned int last = start + GET_MODE_SIZE (GET_MODE (reg)); ra_init_live_subregs (sparseset_bit_p (allocnos_live, allocnum), live_subregs, live_subregs_used, allocnum, reg); if (!DF_REF_FLAGS_IS_SET (def, DF_REF_STRICT_LOWER_PART)) { /* Expand the range to cover entire words. Bytes added here are "don't care". */ start = start / UNITS_PER_WORD * UNITS_PER_WORD; last = ((last + UNITS_PER_WORD - 1) / UNITS_PER_WORD * UNITS_PER_WORD); } /* Ignore the paradoxical bits. */ if ((int)last > live_subregs_used[allocnum]) last = live_subregs_used[allocnum]; while (start < last) { RESET_BIT (live_subregs[allocnum], start); start++; } if (sbitmap_empty_p (live_subregs[allocnum])) { live_subregs_used[allocnum] = 0; sparseset_clear_bit (allocnos_live, allocnum); } else /* Set the allocnos live here because that bit has to be true to get us to look at the live_subregs fields. */ sparseset_set_bit (allocnos_live, allocnum); } else { /* Resetting the live_subregs_used is effectively saying do not use the subregs because we are writing the whole pseudo. */ live_subregs_used[allocnum] = 0; sparseset_clear_bit (allocnos_live, allocnum); } } if (regno >= FIRST_PSEUDO_REGISTER) return; /* Handle hardware regs (and pseudos allocated to hard regs). */ if (! fixed_regs[regno]) { unsigned int start = regno; if (GET_CODE (reg) == SUBREG && !DF_REF_FLAGS_IS_SET (def, DF_REF_EXTRACT)) { unsigned int last; start += SUBREG_BYTE (reg); last = start + subreg_nregs_with_regno (regno, reg); regno = start; while (regno < last) { CLEAR_HARD_REG_BIT (*hard_regs_live, regno); regno++; } } else remove_from_hard_reg_set (hard_regs_live, GET_MODE (reg), regno); } } /* Set REG to be live in the sets ALLOCNOS_LIVE, LIVE_SUBREGS, HARD_REGS_LIVE. If EXTRACT is false, assume that the entire reg is set live even if REG is a subreg. */ inline static void set_reg_in_live (sparseset allocnos_live, sbitmap *live_subregs, int *live_subregs_used, HARD_REG_SET *hard_regs_live, rtx reg, bool extract) { unsigned int regno = (GET_CODE (reg) == SUBREG) ? REGNO (SUBREG_REG (reg)): REGNO (reg); int allocnum = reg_allocno[regno]; if (allocnum >= 0) { if ((GET_CODE (reg) == SUBREG) && !extract) { unsigned int start = SUBREG_BYTE (reg); unsigned int last = start + GET_MODE_SIZE (GET_MODE (reg)); ra_init_live_subregs (sparseset_bit_p (allocnos_live, allocnum), live_subregs, live_subregs_used, allocnum, reg); /* Ignore the paradoxical bits. */ if ((int)last > live_subregs_used[allocnum]) last = live_subregs_used[allocnum]; while (start < last) { SET_BIT (live_subregs[allocnum], start); start++; } } else /* Resetting the live_subregs_used is effectively saying do not use the subregs because we are writing the whole pseudo. */ live_subregs_used[allocnum] = 0; sparseset_set_bit (allocnos_live, allocnum); } if (regno >= FIRST_PSEUDO_REGISTER) return; /* Handle hardware regs (and pseudos allocated to hard regs). */ if (! fixed_regs[regno]) { if ((GET_CODE (reg) == SUBREG) && !extract) { unsigned int start = regno; unsigned int last; start += subreg_regno_offset (regno, GET_MODE (SUBREG_REG (reg)), SUBREG_BYTE (reg), GET_MODE (reg)); last = start + subreg_nregs_with_regno (regno, reg); regno = start; while (regno < last) { SET_HARD_REG_BIT (*hard_regs_live, regno); regno++; } } else add_to_hard_reg_set (hard_regs_live, GET_MODE (reg), regno); } } /* Add hard reg conflicts to RENUMBERS_LIVE assuming that pseudo in allocno[ALLOCNUM] is allocated to a set of hard regs starting at RENUMBER. We are smart about the case where only subregs of REG have been set, as indicated by LIVE_SUBREGS[ALLOCNUM] and LIVE_SUBREGS_USED[ALLOCNUM]. See global_conflicts for description of LIVE_SUBREGS and LIVE_SUBREGS_USED. */ inline static void set_renumbers_live (HARD_REG_SET *renumbers_live, sbitmap *live_subregs, int *live_subregs_used, int allocnum, int renumber) { /* The width of the pseudo. */ int nbytes = live_subregs_used[allocnum]; int regno = allocno[allocnum].reg; enum machine_mode mode = GET_MODE (regno_reg_rtx[regno]); if (dump_file) fprintf (dump_file, " set_renumbers_live %d->%d ", regno, renumber); if (nbytes > 0) { int i; sbitmap live_subs = live_subregs[allocnum]; /* First figure out how many hard regs we are considering using. */ int target_nregs = hard_regno_nregs[renumber][mode]; /* Now figure out the number of bytes per hard reg. Note that this may be different that what would be obtained by looking at the mode in the pseudo. For instance, a complex number made up of 2 32-bit parts gets mapped to 2 hard regs, even if the hardregs are 64-bit floating point values. */ int target_width = nbytes / target_nregs; if (dump_file) fprintf (dump_file, "target_nregs=%d target_width=%d nbytes=%d", target_nregs, target_width, nbytes); for (i = 0; i < target_nregs; i++) { int j; bool set = false; for (j = 0; j < target_width; j++) { int reg_start = i * target_width; if (reg_start + j >= nbytes) break; set |= TEST_BIT (live_subs, reg_start + j); } if (set) SET_HARD_REG_BIT (*renumbers_live, renumber + i); } } else add_to_hard_reg_set (renumbers_live, mode, renumber); if (dump_file) fprintf (dump_file, "\n"); } /* Dump out a REF with its reg_renumber range to FILE using PREFIX. */ static void dump_ref (FILE *file, const char * prefix, const char * suffix, rtx reg, unsigned int regno, sbitmap *live_subregs, int *live_subregs_used ) { int allocnum = reg_allocno[regno]; fprintf (file, "%s %d", prefix, regno); if (allocnum >= 0 && live_subregs_used[allocnum] > 0) { int j; char s = '['; for (j = 0; j < live_subregs_used[allocnum]; j++) if (TEST_BIT (live_subregs[allocnum], j)) { fprintf (dump_file, "%c%d", s, j); s = ','; } fprintf (dump_file, "]"); } if (reg_renumber[regno] >= 0) { enum machine_mode mode = GET_MODE (reg); unsigned int start; unsigned int last; regno = reg_renumber[regno]; start = regno; last = end_hard_regno (mode, regno); if (GET_CODE (reg) == SUBREG) { start += subreg_regno_offset (regno, GET_MODE (SUBREG_REG (reg)), SUBREG_BYTE (reg), GET_MODE (reg)); last = start + subreg_nregs_with_regno (regno, reg); } if (start == last - 1) fprintf (file, "(%d)", start); else fprintf (file, "(%d:%d..%d)", regno, start, last-1); } fprintf (file, suffix); } /* Scan the rtl code and record all conflicts and register preferences in the conflict matrices and preference tables. */ void global_conflicts (void) { unsigned int i; basic_block bb; rtx insn; /* Regs that have allocnos can be in either hard_regs_live (if regno < FIRST_PSEUDO_REGISTER) or allocnos_live (if regno >= FIRST_PSEUDO_REGISTER) or both if local_alloc has preallocated it and reg_renumber >= 0. */ HARD_REG_SET hard_regs_live; HARD_REG_SET renumbers_live; sparseset allocnos_live; bitmap live = BITMAP_ALLOC (NULL); VEC (df_ref_t, heap) *clobbers = NULL; VEC (df_ref_t, heap) *dying_regs = NULL; /* live_subregs is a vector used to keep accurate information about which hardregs are live in multiword pseudos. live_subregs and live_subregs_used are indexed by reg_allocno. The live_subreg entry for a particular pseudo is a bitmap with one bit per byte of the register. It is only used if the corresponding element is non zero in live_subregs_used. The value in live_subregs_used is number of bytes that the pseudo can occupy. */ sbitmap *live_subregs = XCNEWVEC (sbitmap, max_allocno); int *live_subregs_used = XNEWVEC (int, max_allocno); if (dump_file) { fprintf (dump_file, "fixed registers : "); for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) if (fixed_regs[i]) fprintf (dump_file, "%d ", i); fprintf (dump_file, "\n"); } allocnos_live = sparseset_alloc (max_allocno); FOR_EACH_BB (bb) { bitmap_iterator bi; bitmap_copy (live, DF_LIVE_OUT (bb)); df_simulate_artificial_refs_at_end (bb, live); sparseset_clear (allocnos_live); memset (live_subregs_used, 0, max_allocno * sizeof (int)); CLEAR_HARD_REG_SET (hard_regs_live); CLEAR_HARD_REG_SET (renumbers_live); /* Initialize allocnos_live and hard_regs_live for bottom of block. */ EXECUTE_IF_SET_IN_BITMAP (live, 0, i, bi) { if (i >= FIRST_PSEUDO_REGISTER) break; if (! fixed_regs[i]) SET_HARD_REG_BIT (hard_regs_live, i); } EXECUTE_IF_SET_IN_BITMAP (live, FIRST_PSEUDO_REGISTER, i, bi) { int allocnum = reg_allocno[i]; if (allocnum >= 0) { int renumber = reg_renumber[i]; rtx reg = regno_reg_rtx[i]; set_reg_in_live (allocnos_live, live_subregs, live_subregs_used, &hard_regs_live, reg, false); if (renumber >= 0 && renumber < FIRST_PSEUDO_REGISTER) set_renumbers_live (&renumbers_live, live_subregs, live_subregs_used, allocnum, renumber); } } if (dump_file) fprintf (dump_file, "\nstarting basic block %d\n\n", bb->index); FOR_BB_INSNS_REVERSE (bb, insn) { unsigned int uid = INSN_UID (insn); struct df_ref **def_rec; struct df_ref **use_rec; if (!INSN_P (insn)) continue; if (dump_file) { fprintf (dump_file, "insn = %d live = hardregs [", uid); for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) if (TEST_HARD_REG_BIT (hard_regs_live, i)) fprintf (dump_file, "%d ", i); fprintf (dump_file, "] renumbered ["); for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) if (TEST_HARD_REG_BIT (renumbers_live, i)) fprintf (dump_file, "%d ", i); fprintf (dump_file, "] pseudos ["); EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i) { dump_ref (dump_file, " ", "", regno_reg_rtx[allocno[i].reg], allocno[i].reg, live_subregs, live_subregs_used); } fprintf (dump_file, "]\n"); } /* Add the defs into live. Most of them will already be there, the ones that are missing are the unused ones and the clobbers. We do this in order to make sure that interferences are added between every def and everything that is live across the insn. These defs will be removed later. */ for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++) { struct df_ref *def = *def_rec; /* FIXME: Ignoring may clobbers is technically the wrong thing to do. However the old version of the this code ignores may clobbers (and instead has many places in the register allocator to handle these constraints). It is quite likely that with a new allocator, the correct thing to do is to not ignore the constraints and then do not put in the large number of special checks. */ if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER)) { rtx reg = DF_REF_REG (def); set_reg_in_live (allocnos_live, live_subregs, live_subregs_used, &hard_regs_live, reg, DF_REF_FLAGS_IS_SET (def, DF_REF_EXTRACT)); if (dump_file) dump_ref (dump_file, " adding def", "\n", reg, DF_REF_REGNO (def), live_subregs, live_subregs_used); } } /* Add the hardregs into renumbers_live to build the interferences. Renumbers_live will be rebuilt in the next step from scratch, so corrupting it here is no problem. */ IOR_HARD_REG_SET (renumbers_live, hard_regs_live); /* Add the interferences for the defs. */ for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++) { struct df_ref *def = *def_rec; if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER)) mark_reg_store (allocnos_live, &renumbers_live, def); } /* Remove the defs from the live sets. Leave the partial and conditional defs in the set because they do not kill. */ VEC_truncate (df_ref_t, clobbers, 0); for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++) { struct df_ref *def = *def_rec; if (!DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL)) { rtx reg = DF_REF_REG (def); clear_reg_in_live (allocnos_live, live_subregs, live_subregs_used, &hard_regs_live, reg, def); if (dump_file) dump_ref (dump_file, " clearing def", "\n", reg, DF_REF_REGNO (def), live_subregs, live_subregs_used); } if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER)) VEC_safe_push (df_ref_t, heap, clobbers, def); } /* Go thru all of the live pseudos and reset renumbers_live. We must start from scratch here because there could have been several pseudos alive that have the same reg_renumber and if we see a clobber for one of them, we cannot not want to kill the renumbers from the other pseudos. */ CLEAR_HARD_REG_SET (renumbers_live); EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i) { unsigned int regno = allocno[i].reg; int renumber = reg_renumber[regno]; if (renumber >= 0 && renumber < FIRST_PSEUDO_REGISTER) set_renumbers_live (&renumbers_live, live_subregs, live_subregs_used, i, renumber); } /* Add the uses to the live sets. Keep track of the regs that are dying inside the insn, this set will be useful later. */ VEC_truncate (df_ref_t, dying_regs, 0); for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++) { struct df_ref *use = *use_rec; unsigned int regno = DF_REF_REGNO (use); bool added = false; int renumber = reg_renumber[regno]; int allocnum = reg_allocno[regno]; bool renumbering = false; rtx reg = DF_REF_REG (use); /* DF_REF_READ_WRITE on a use means that this use is fabricated from a def that is a partial set to a multiword reg. Here, we only model the subreg case precisely so we do not need to look at the fabricated use unless that set also happens to wrapped in a ZERO_EXTRACT. */ if (DF_REF_FLAGS_IS_SET (use, DF_REF_READ_WRITE) && (!DF_REF_FLAGS_IS_SET (use, DF_REF_EXTRACT)) && DF_REF_FLAGS_IS_SET (use, DF_REF_SUBREG)) continue; if (dump_file) dump_ref (dump_file, " seeing use", "\n", reg, regno, live_subregs, live_subregs_used); if (allocnum >= 0) { if (GET_CODE (reg) == SUBREG && !DF_REF_FLAGS_IS_SET (use, DF_REF_EXTRACT)) { unsigned int start = SUBREG_BYTE (reg); unsigned int last = start + GET_MODE_SIZE (GET_MODE (reg)); ra_init_live_subregs (sparseset_bit_p (allocnos_live, allocnum), live_subregs, live_subregs_used, allocnum, reg); /* Ignore the paradoxical bits. */ if ((int)last > live_subregs_used[allocnum]) last = live_subregs_used[allocnum]; while (start < last) { if (!TEST_BIT (live_subregs[allocnum], start)) { if (dump_file) fprintf (dump_file, " dying pseudo subreg %d[%d]\n", regno, start); SET_BIT (live_subregs[allocnum], start); added = true; } start++; } sparseset_set_bit (allocnos_live, allocnum); if (renumber >= 0 && renumber < FIRST_PSEUDO_REGISTER) set_renumbers_live (&renumbers_live, live_subregs, live_subregs_used, allocnum, renumber); } else if (live_subregs_used[allocnum] > 0 || !sparseset_bit_p (allocnos_live, allocnum)) { if (dump_file) fprintf (dump_file, " %sdying pseudo\n", (live_subregs_used[allocnum] > 0) ? "partially ": ""); /* Resetting the live_subregs_used is effectively saying do not use the subregs because we are reading the whole pseudo. */ live_subregs_used[allocnum] = 0; sparseset_set_bit (allocnos_live, allocnum); if (renumber >= 0 && renumber < FIRST_PSEUDO_REGISTER) set_renumbers_live (&renumbers_live, live_subregs, live_subregs_used, allocnum, renumber); added = true; } } if (renumber >= 0 && renumber < FIRST_PSEUDO_REGISTER) { regno = renumber; renumbering = true; } if (regno < FIRST_PSEUDO_REGISTER) { unsigned int start = regno; unsigned int last; if (GET_CODE (reg) == SUBREG) { start += subreg_regno_offset (regno, GET_MODE (SUBREG_REG (reg)), SUBREG_BYTE (reg), GET_MODE (reg)); last = start + subreg_nregs_with_regno (regno, reg); } else last = end_hard_regno (GET_MODE (reg), regno); regno = start; while (regno < last) { if ((!TEST_HARD_REG_BIT (hard_regs_live, regno)) && (!TEST_HARD_REG_BIT (renumbers_live, regno)) && ! fixed_regs[regno]) { if (dump_file) fprintf (dump_file, " dying hard reg %d\n", regno); if (renumbering) SET_HARD_REG_BIT (renumbers_live, regno); else SET_HARD_REG_BIT (hard_regs_live, regno); added = true; } regno++; } } if (added) VEC_safe_push (df_ref_t, heap, dying_regs, use); } /* These three cases are all closely related, they all deal with some set of outputs of the insn need to conflict with some of the registers that are used by the insn but die within the insn. If no registers die within the insn, the tests can be skipped. */ if (VEC_length (df_ref_t, dying_regs) > 0) { int k; /* There appears to be an ambiguity as to what a clobber means in an insn. In some cases, the clobber happens within the processing of the insn and in some cases it happens at the end of processing the insn. There is currently no way to distinguish these two cases so this code causes real clobbers to interfere with registers that die within an insn. This is consistent with the prior version of interference graph builder but is was discovered while developing this version of the code, that on some architectures such as the x86-64, the clobbers only appear to happen at the end of the insn. However, the ppc-32 contains clobbers for which these interferences are necessary. FIXME: We should consider either adding a new kind of clobber, or adding a flag to the clobber distinguish these two cases. */ if (dump_file && VEC_length (df_ref_t, clobbers)) fprintf (dump_file, " clobber conflicts\n"); for (k = VEC_length (df_ref_t, clobbers) - 1; k >= 0; k--) { struct df_ref *def = VEC_index (df_ref_t, clobbers, k); int j; for (j = VEC_length (df_ref_t, dying_regs) - 1; j >= 0; j--) { struct df_ref *use = VEC_index (df_ref_t, dying_regs, j); record_one_conflict_between_regnos (GET_MODE (DF_REF_REG (def)), DF_REF_REGNO (def), GET_MODE (DF_REF_REG (use)), DF_REF_REGNO (use)); } } /* Early clobbers, by definition, need to not only clobber the registers that are live across the insn but need to clobber the registers that die within the insn. The clobbering for registers live across the insn is handled above. */ set_conflicts_for_earlyclobber (insn); /* If INSN is a store with multiple outputs, then any reg that dies here and is used inside of the address of the output must conflict with the other outputs. FIXME: There has been some discussion as to whether this is right place to handle this issue. This is a hold over from an early version global conflicts. 1) There is some evidence that code only deals with a bug that is only on the m68k. The conditions of this test are such that this case only triggers for a very peculiar insn, one that is a parallel where one of the sets is a store and the other sets a reg that is used in the address of the store. See http://gcc.gnu.org/ml/gcc-patches/1998-12/msg00259.html 2) The situation that this is addressing is a bug in the part of reload that handles stores, adding this conflict only hides the problem. (Of course no one really wants to fix reload so it is understandable why a bandaid was just added here.) Just because an output is unused does not mean the compiler can assume the side effect will not occur. Consider if REG appears in the address of an output and we reload the output. If we allocate REG to the same hard register as an unused output we could set the hard register before the output reload insn. 3) This could actually be handled by making the other (non store) operand of the insn be an early clobber. This would insert the same conflict, even if it is not technically an early clobber. */ /* It is unsafe to use !single_set here since it will ignore an unused output. */ if (GET_CODE (PATTERN (insn)) == PARALLEL && multiple_sets (insn)) { int j; if (dump_file) fprintf (dump_file, " multiple sets\n"); for (j = VEC_length (df_ref_t, dying_regs) - 1; j >= 0; j--) { int used_in_output = 0; struct df_ref *use = VEC_index (df_ref_t, dying_regs, j); rtx reg = DF_REF_REG (use); int uregno = DF_REF_REGNO (use); enum machine_mode umode = GET_MODE (DF_REF_REG (use)); int k; for (k = XVECLEN (PATTERN (insn), 0) - 1; k >= 0; k--) { rtx set = XVECEXP (PATTERN (insn), 0, k); if (GET_CODE (set) == SET && !REG_P (SET_DEST (set)) && !rtx_equal_p (reg, SET_DEST (set)) && reg_overlap_mentioned_p (reg, SET_DEST (set))) used_in_output = 1; } if (used_in_output) for (k = XVECLEN (PATTERN (insn), 0) - 1; k >= 0; k--) { rtx set = XVECEXP (PATTERN (insn), 0, k); if (GET_CODE (set) == SET && REG_P (SET_DEST (set)) && !rtx_equal_p (reg, SET_DEST (set))) record_one_conflict_between_regnos (GET_MODE (SET_DEST (set)), REGNO (SET_DEST (set)), umode, uregno); } } } } } /* Add the renumbers live to the hard_regs_live for the next few calls. All of this gets recomputed at the top of the loop so there is no harm. */ IOR_HARD_REG_SET (hard_regs_live, renumbers_live); #ifdef EH_RETURN_DATA_REGNO if (bb_has_eh_pred (bb)) { unsigned int i; for (i = 0; ; ++i) { unsigned int regno = EH_RETURN_DATA_REGNO (i); if (regno == INVALID_REGNUM) break; record_one_conflict (allocnos_live, &hard_regs_live, regno); } EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i) { allocno[i].no_eh_reg = 1; } } #endif if (bb_has_abnormal_pred (bb)) { unsigned int i; #ifdef STACK_REGS /* Pseudos can't go in stack regs at the start of a basic block that is reached by an abnormal edge. Likewise for call clobbered regs, because caller-save, fixup_abnormal_edges and possibly the table driven EH machinery are not quite ready to handle such regs live across such edges. */ EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i) { allocno[i].no_stack_reg = 1; } for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++) record_one_conflict (allocnos_live, &hard_regs_live, i); #endif /* No need to record conflicts for call clobbered regs if we have nonlocal labels around, as we don't ever try to allocate such regs in this case. */ if (! current_function_has_nonlocal_label) for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) if (call_used_regs [i]) record_one_conflict (allocnos_live, &hard_regs_live, i); } } for (i = 0; i < (unsigned int)max_allocno; i++) if (live_subregs[i]) free (live_subregs[i]); /* Clean up. */ free (allocnos_live); free (live_subregs); free (live_subregs_used); VEC_free (df_ref_t, heap, dying_regs); VEC_free (df_ref_t, heap, clobbers); BITMAP_FREE (live); }