diff options
Diffstat (limited to 'gcc_arm/range.c')
| -rwxr-xr-x | gcc_arm/range.c | 1932 |
1 files changed, 1932 insertions, 0 deletions
diff --git a/gcc_arm/range.c b/gcc_arm/range.c new file mode 100755 index 0000000..d96caca --- /dev/null +++ b/gcc_arm/range.c @@ -0,0 +1,1932 @@ +/* CYGNUS LOCAL LRS */ +/* Allocate registers within a basic block, for GNU compiler. + Copyright (C) 1997, 1998 Free Software Foundation, Inc. + +This file is part of GNU CC. + +GNU CC 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 2, or (at your option) +any later version. + +GNU CC 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 GNU CC; see the file COPYING. If not, write to +the Free Software Foundation, 59 Temple Place - Suite 330, +Boston, MA 02111-1307, USA. */ + +/* Live range support that splits a variable that is spilled to the stack into + smaller ranges so that at least the middle of small loops the variable will + be run in registers. This is run after global allocation if one or more + variables were denied a register, and then global allocation is done once + again. */ + +#include "config.h" +#include "system.h" +#include "rtl.h" +#include "tree.h" +#include "flags.h" +#include "basic-block.h" +#include "regs.h" +#include "hard-reg-set.h" +#include "insn-config.h" +#include "recog.h" +#include "output.h" +#include "expr.h" +#include "except.h" +#include "function.h" +#include "obstack.h" +#include "range.h" +#include "toplev.h" + +extern struct obstack *rtl_obstack; + +/* Information that we gather about registers */ +typedef struct rinfo_def { + rtx reg; /* Register insn */ + int refs; /* # of register references */ + int sets; /* # of register sets/clobbers */ + int deaths; /* # of register deaths */ + int live_length; /* # of insns in range value is live */ + int n_calls; /* # of calls this reg crosses */ + int copy_flags; /* copy {in,out} flags */ +} rinfo; + +/* Basic blocks expressed as a linked list */ +typedef struct bb_link_def { + int block; /* block number or -1 */ + rtx first_insn; /* first insn in block */ + rtx last_insn; /* last insn in block */ + regset live_at_start; /* live information */ +} bb_link; + +/* Symbol/block node that a variable is declared in and whether a register + only holds constants. */ +typedef struct var_info_def { + tree symbol; /* DECL_NODE of the symbol */ + tree block; /* BLOCK_NODE variable is declared in */ + rtx constant_value; /* what value a register always holds */ +} var_info; + +int range_max_unique; /* Range #, monotonically increasing */ + +static rinfo *range_info; /* Register information */ +static var_info *range_vars; /* Map regno -> variable */ +static int *range_regs; /* Registers used in the loop */ +static int range_num_regs; /* # of registers in range_regs */ +static int range_loop_depth; /* current loop depth */ +static int range_update_used_p; /* whether range_used should be set */ +static regset range_used; /* regs used in the current range */ +static regset range_set; /* regs set in the current range */ +static regset range_live; /* regs currently live */ +static regset range_mixed_mode; /* regs that use different modes */ +static regset range_no_move; /* regs that don't have simple moves */ +static unsigned range_max_uid; /* Size of UID->basic block mapping */ +static bb_link **range_block_insn; /* Map INSN # to basic block # */ +static bb_link *range_block_orig; /* original basic blocks */ + +/* Linked list of live ranges to try allocating registers in first before + allocating all of the remaining registers. */ +rtx live_range_list; + +#define RANGE_BLOCK_NUM(INSN) \ +(((unsigned)INSN_UID (INSN) < (unsigned)range_max_uid \ + && range_block_insn[INSN_UID (INSN)]) \ + ? range_block_insn[INSN_UID (INSN)]->block : -1) + +/* Forward references */ +static void range_mark PROTO((rtx, int, rtx)); +static void range_basic_mark PROTO((rtx, regset, rtx)); +static void range_basic_insn PROTO((rtx, regset, int)); +static void range_bad_insn PROTO((FILE *, char *, rtx)); +static void range_print_flags PROTO((FILE *, int, char *)); +static void print_blocks_internal PROTO((FILE *, tree, int)); +static int range_inner PROTO((FILE *, rtx, rtx, rtx, rtx, + regset, regset, int)); +static void range_update_basic_block PROTO((FILE *, rtx, bb_link *, + int, int)); +static void range_finish PROTO((FILE *, rtx, int, int)); +static void range_scan_blocks PROTO((tree, tree)); +static int range_compare PROTO((const GENERIC_PTR, + const GENERIC_PTR)); + + +/* Determine which registers are used/set */ + +static void +range_mark (x, set_p, insn) + rtx x; + int set_p; + rtx insn; +{ + register RTX_CODE code = GET_CODE (x); + register int i, regno; + register char *fmt; + +restart: + + switch (code) + { + default: + break; + + /* Make sure we mark the registers that are set */ + case SET: + range_mark (SET_DEST (x), TRUE, insn); + range_mark (SET_SRC (x), FALSE, insn); + return; + + /* Treat clobber like a set. */ + /* Pre-increment and friends always update as well as reference. */ + case CLOBBER: + case PRE_INC: + case PRE_DEC: + case POST_INC: + case POST_DEC: + range_mark (XEXP (x, 0), TRUE, insn); + return; + + /* Memory addresses just reference the register, even if this is a SET */ + case MEM: + range_mark (XEXP (x, 0), FALSE, insn); + return; + + /* Treat subregs as using/modifying the whole register. */ + case SUBREG: + x = SUBREG_REG (x); + code = GET_CODE (x); + goto restart; + + /* Actual registers, skip hard registers */ + case REG: + regno = REGNO (x); + if (regno >= FIRST_PSEUDO_REGISTER) + { + if (!range_info[regno].reg) + range_info[regno].reg = x; + else if (GET_MODE (x) != GET_MODE (range_info[regno].reg)) + SET_REGNO_REG_SET (range_mixed_mode, regno); + + range_info[regno].refs += 2*range_loop_depth; + SET_REGNO_REG_SET (range_live, regno); + if (range_update_used_p) + SET_REGNO_REG_SET (range_used, regno); + + /* If there isn't a simple move pattern for the mode, skip it */ + if (mov_optab->handlers[(int) GET_MODE (x)].insn_code + == CODE_FOR_nothing) + SET_REGNO_REG_SET (range_no_move, regno); + + if (set_p) + { + range_info[regno].sets++; + SET_REGNO_REG_SET (range_set, regno); + } + } + + return; + } + + fmt = GET_RTX_FORMAT (code); + for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) + { + if (fmt[i] == 'e') + range_mark (XEXP (x, i), set_p, insn); + + else if (fmt[i] == 'E') + { + register unsigned j; + for (j = 0; j < XVECLEN (x, i); j++) + range_mark (XVECEXP (x, i, j), set_p, insn); + } + } +} + + +/* Like range_mark, except more stripped down, to just care about what + registers are currently live. */ + +static void +range_basic_mark (x, live, insn) + rtx x; + regset live; + rtx insn; +{ + register RTX_CODE code = GET_CODE (x); + register int i, regno, lim; + register char *fmt; + +restart: + switch (code) + { + default: + break; + + /* Treat subregs as using/modifying the whole register. */ + case SUBREG: + x = SUBREG_REG (x); + code = GET_CODE (x); + goto restart; + + /* Actual registers */ + case REG: + regno = REGNO (x); + lim = regno + ((regno >= FIRST_PSEUDO_REGISTER) + ? 1 + : HARD_REGNO_NREGS (regno, GET_MODE (x))); + + for (i = regno; i < lim; i++) + SET_REGNO_REG_SET (live, i); + return; + } + + fmt = GET_RTX_FORMAT (code); + for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) + { + if (fmt[i] == 'e') + range_basic_mark (XEXP (x, i), live, insn); + + else if (fmt[i] == 'E') + { + register unsigned j; + for (j = 0; j < XVECLEN (x, i); j++) + range_basic_mark (XVECEXP (x, i, j), live, insn); + } + } +} + +/* For an INSN, CALL_INSN, or JUMP_INSN, update basic live/dead information. */ + +static void +range_basic_insn (insn, live, range_max_regno) + rtx insn; + regset live; + int range_max_regno; +{ + rtx note, x; + int i; + + range_basic_mark (PATTERN (insn), live, insn); + + /* Remember if the value is only set to one constant. */ + if (GET_CODE (insn) == INSN + && (x = single_set (insn)) != NULL_RTX + && (GET_CODE (SET_DEST (x)) == REG + && REG_N_SETS (REGNO (SET_DEST (x))) == 1 + && CONSTANT_P (SET_SRC (x))) + && REGNO (SET_DEST (x)) < range_max_regno) + range_vars[ REGNO (SET_DEST (x))].constant_value = SET_SRC (x); + + /* figure out which registers are now dead. */ + for (note = REG_NOTES (insn); note != NULL_RTX; note = XEXP (note, 1)) + { + if (REG_NOTE_KIND (note) == REG_DEAD + && GET_CODE (XEXP (note, 0)) == REG) + { + rtx reg = XEXP (note, 0); + int regno = REGNO (reg); + int lim = regno + ((regno >= FIRST_PSEUDO_REGISTER) + ? 1 + : HARD_REGNO_NREGS (regno, GET_MODE (reg))); + + for (i = regno; i < lim; i++) + CLEAR_REGNO_REG_SET (live, i); + } + } +} + + +/* Sort the registers by number of uses */ + +static int +range_compare (v1p, v2p) + const GENERIC_PTR v1p; + const GENERIC_PTR v2p; +{ + int i1 = *(int *)v1p; + int i2 = *(int *)v2p; + int r1 = range_info[i1].refs; + int r2 = range_info[i2].refs; + + if (r2 - r1) + return r2 - r1; + + /* Make sure that range_compare always is stable, so if the values are equal, + compare based on pseduo register number. */ + return REGNO (range_info[i2].reg) - REGNO (range_info[i1].reg); +} + + +/* If writing a .range file, print a message and an rtl. */ + +static void +range_bad_insn (stream, msg, insn) + FILE *stream; + char *msg; + rtx insn; +{ + if (stream) + { + fputs (msg, stream); + print_rtl (stream, PATTERN (insn)); + putc ('\n', stream); + } +} + + +/* Print out to STREAM the copyin/copyout flags. */ + +static void +range_print_flags (stream, flags, prefix) + FILE *stream; + int flags; + char *prefix; +{ + if ((flags & LIVE_RANGE_COPYIN) != 0) + { + fprintf (stream, "%scopyin", prefix); + prefix = ", "; + } + + if ((flags & LIVE_RANGE_COPYIN_CONST) != 0) + { + fprintf (stream, "%sconst", prefix); + prefix = ", "; + } + + if ((flags & LIVE_RANGE_COPYOUT) != 0) + fprintf (stream, "%scopyout", prefix); + +} + + +/* Print out range information to STREAM, using RANGE as the range_info rtx, + printing TAB and COMMENT at the beginning of each line. */ + +void +live_range_print (stream, range, tab, comment) + FILE *stream; + rtx range; + char *tab; + char *comment; +{ + int i; + + fprintf (stream, + "%s%s range #%d start, %d calls, basic block {start/end} %d/%d, loop depth %d\n", + tab, comment, + RANGE_INFO_UNIQUE (range), RANGE_INFO_NCALLS (range), + RANGE_INFO_BB_START (range), RANGE_INFO_BB_END (range), + RANGE_INFO_LOOP_DEPTH (range)); + + for (i = 0; i < (int)RANGE_INFO_NUM_REGS (range); i++) + { + int pseudo = RANGE_REG_PSEUDO (range, i); + int copy = RANGE_REG_COPY (range, i); + + fprintf (stream, "%s%s reg %d", tab, comment, pseudo); + if (reg_renumber) + { + if ((unsigned)pseudo >= (unsigned)max_regno) + fprintf (stream, " (illegal)"); + else if (reg_renumber[pseudo] >= 0) + fprintf (stream, " (%s)", reg_names[ reg_renumber[pseudo]]); + } + + fprintf (stream, ", copy %d", copy); + if (reg_renumber) + { + if ((unsigned)copy >= (unsigned)max_regno) + fprintf (stream, " (illegal)"); + else if (reg_renumber[copy] >= 0) + fprintf (stream, " (%s)", reg_names[ reg_renumber[copy]]); + } + + fprintf (stream, + ", %d ref(s), %d set(s), %d death(s), %d live length, %d calls", + RANGE_REG_REFS (range, i), + RANGE_REG_SETS (range, i), + RANGE_REG_DEATHS (range, i), + RANGE_REG_LIVE_LENGTH (range, i), + RANGE_REG_N_CALLS (range, i)); + + range_print_flags (stream, RANGE_REG_COPY_FLAGS (range, i), ", "); + if (REG_USERVAR_P (regno_reg_rtx[pseudo])) + { + fprintf (stream, ", user"); + if (RANGE_REG_SYMBOL_NODE (range, i)) + { + tree name = DECL_NAME (RANGE_REG_SYMBOL_NODE (range, i)); + if (name) + fprintf (stream, " [%s]", IDENTIFIER_POINTER (name)); + } + } + + if (REGNO_POINTER_FLAG (pseudo)) + fprintf (stream, ", ptr"); + + putc ('\n', stream); + } +} + + +/* CYGNUS LOCAL -- meissner/live range */ +/* Print the scoping blocks in the current function */ + +static void +print_blocks_internal (stream, block, level) + FILE *stream; + tree block; + int level; +{ + /* Loop over all blocks */ + for (; block != NULL_TREE; block = BLOCK_CHAIN (block)) + { + int i; + tree vars_types[2]; + static char *vars_types_name[] = {"vars: ", "types:"}; + + fprintf (stream, "%*sBlock ", level*4, ""); + fprintf (stream, HOST_WIDE_INT_PRINT_HEX, (HOST_WIDE_INT) block); + + if (BLOCK_CHAIN (block)) + { + fprintf (stream, ", chain "); + fprintf (stream, HOST_WIDE_INT_PRINT_HEX, + (HOST_WIDE_INT) BLOCK_CHAIN (block)); + } + + if (BLOCK_VARS (block)) + { + fprintf (stream, ", vars "); + fprintf (stream, HOST_WIDE_INT_PRINT_HEX, + (HOST_WIDE_INT) BLOCK_VARS (block)); + } + + if (BLOCK_TYPE_TAGS (block)) + { + fprintf (stream, ", types "); + fprintf (stream, HOST_WIDE_INT_PRINT_HEX, + (HOST_WIDE_INT) BLOCK_TYPE_TAGS (block)); + } + + if (BLOCK_SUBBLOCKS (block)) + { + fprintf (stream, ", subblocks "); + fprintf (stream, HOST_WIDE_INT_PRINT_HEX, + (HOST_WIDE_INT) BLOCK_SUBBLOCKS (block)); + } + + if (BLOCK_ABSTRACT_ORIGIN (block)) + { + fprintf (stream, ", abstract origin "); + fprintf (stream, HOST_WIDE_INT_PRINT_HEX, + (HOST_WIDE_INT) BLOCK_ABSTRACT_ORIGIN (block)); + } + + if (BLOCK_ABSTRACT (block)) + fprintf (stream, ", abstract"); + + if (BLOCK_LIVE_RANGE_FLAG (block)) + fprintf (stream, ", live-range"); + + if (BLOCK_LIVE_RANGE_VAR_FLAG (block)) + fprintf (stream, ", live-range-vars"); + + if (BLOCK_HANDLER_BLOCK (block)) + fprintf (stream, ", handler"); + + if (TREE_USED (block)) + fprintf (stream, ", used"); + + if (TREE_ASM_WRITTEN (block)) + fprintf (stream, ", asm-written"); + + fprintf (stream, "\n"); + vars_types[0] = BLOCK_VARS (block); + vars_types[1] = BLOCK_TYPE_TAGS (block); + for (i = 0; i < 2; i++) + if (vars_types[i]) + { + tree vars; + int indent = ((level < 4) ? 16 : (level*4) + 4) - 1; + int len = 0; + + for (vars = BLOCK_VARS (block); + vars != NULL_TREE; + vars = TREE_CHAIN (vars)) + { + if (DECL_NAME (vars) && IDENTIFIER_POINTER (DECL_NAME (vars))) + { + if (len == 0) + { + len = indent + 1 + strlen (vars_types_name[i]); + fprintf (stream, "%*s%s", indent+1, "", + vars_types_name[i]); + } + + len += IDENTIFIER_LENGTH (DECL_NAME (vars)) + 1; + if (len >= 80 && len > indent) + { + len = indent; + fprintf (stream, "\n%*s", indent, ""); + } + + fprintf (stream, " %.*s", + IDENTIFIER_LENGTH (DECL_NAME (vars)), + IDENTIFIER_POINTER (DECL_NAME (vars))); + } + } + + fprintf (stream, "\n\n"); + } + + print_blocks_internal (stream, BLOCK_SUBBLOCKS (block), level+1); + } +} + +void +print_all_blocks () +{ + fprintf (stderr, "\n"); + print_blocks_internal (stderr, DECL_INITIAL (current_function_decl), 0); +} + + +/* Function with debugging output to STREAM that handles a sequence of insns + that goes from RANGE_START to RANGE_END, splitting the range of variables + used between INNER_START and INNER_END. Registers in LIVE_AT_START are live + at the first insn. BB_{START,END} holds the basic block numbers of the + first and last insns. Return the number of variables that had their ranges + split into a new pseudo variable used only within the loop. */ + +static int +range_inner (stream, range_start, range_end, inner_start, inner_end, + live_at_start, live_at_end, loop_depth) + FILE *stream; + rtx range_start; + rtx range_end; + rtx inner_start; + rtx inner_end; + regset live_at_start; + regset live_at_end; + int loop_depth; +{ + rtx insn; + rtx pattern; + rtx label_ref; + rtx label_chain; + rtx start; + rtx end; + rtx *regs; + rtvec regs_rtvec; + rtx note; + int first_label = get_first_label_num (); + int last_label = max_label_num (); + unsigned num_labels = last_label - first_label + 1; + unsigned indx; + int i; + int regno; + int block; + int *loop_label_ref = (int *) alloca (sizeof (int) * num_labels); + int *all_label_ref = (int *) alloca (sizeof (int) * num_labels); + char *found_label_ref = (char *) alloca (sizeof (char) * num_labels); + int ok_p = TRUE; + int n_insns; + int n_calls; + regset live_at_start_copy; + regset live_at_end_copy; + int bb_start; + int bb_end; + char *nl; + rtx ri; + + bzero ((char *)loop_label_ref, sizeof (int) * num_labels); + bzero ((char *)all_label_ref, sizeof (int) * num_labels); + bzero ((char *) range_info, sizeof (rinfo) * max_reg_num ()); + CLEAR_REG_SET (range_used); + CLEAR_REG_SET (range_set); + CLEAR_REG_SET (range_mixed_mode); + CLEAR_REG_SET (range_no_move); + COPY_REG_SET (range_live, live_at_start); + range_num_regs = 0; + range_loop_depth = loop_depth; + + if (stream) + fprintf (stream, "\nPossible range from %d to %d (inner range %d to %d)\nLive at start: ", + INSN_UID (range_start), INSN_UID (range_end), + INSN_UID (inner_start), INSN_UID (inner_end)); + + /* Mark the live registers as needing copies to the tmp register from the + original value. */ + EXECUTE_IF_SET_IN_REG_SET (live_at_start, FIRST_PSEUDO_REGISTER, i, + { + range_info[i].copy_flags |= LIVE_RANGE_COPYIN; + if (stream) + fprintf (stream, " %d", i); + if (range_vars[i].constant_value) + { + range_info[i].copy_flags + |= LIVE_RANGE_COPYIN_CONST; + + if (stream) + fprintf (stream, " [constant]"); + } + }); + + if (stream) + { + fprintf (stream, "\nLive at end: "); + EXECUTE_IF_SET_IN_REG_SET (live_at_end, FIRST_PSEUDO_REGISTER, i, + { + fprintf (stream, " %d", i); + }); + + putc ('\n', stream); + } + + /* Calculate basic block start and end */ + bb_start = -1; + for (insn = range_start; + insn && insn != range_end && (bb_start = RANGE_BLOCK_NUM (insn)) < 0; + insn = NEXT_INSN (insn)) + ; + + bb_end = -1; + for (insn = range_end; + insn && insn != range_start && (bb_end = RANGE_BLOCK_NUM (insn)) < 0; + insn = PREV_INSN (insn)) + ; + + if (bb_start < 0) + { + ok_p = FALSE; + if (stream) + fprintf (stream, "Cannot find basic block start\n"); + } + + if (bb_end < 0) + { + ok_p = FALSE; + if (stream) + fprintf (stream, "Cannot find basic block end\n"); + } + + /* Scan the loop, looking for jumps outside/inside of the loop. If the + loop has such jumps, we ignore it. */ + n_insns = n_calls = block = 0; + range_update_used_p = FALSE; + for (insn = range_start; insn && insn != range_end; insn = NEXT_INSN (insn)) + { + enum rtx_code code = GET_CODE (insn); + int block_tmp = RANGE_BLOCK_NUM (insn); + if (block_tmp >= 0 && block != block_tmp) + { + block = block_tmp; + COPY_REG_SET (range_live, basic_block_live_at_start[block]); + } + + /* Only mark registers that appear between INNER_START and INNER_END */ + if (insn == inner_start) + range_update_used_p = TRUE; + else if (insn == inner_end) + range_update_used_p = FALSE; + + if (GET_RTX_CLASS (code) == 'i') + { + n_insns++; + /* Mark used registers */ + range_mark (PATTERN (insn), FALSE, insn); + + /* Update live length, & number of calls that the insn crosses */ + EXECUTE_IF_SET_IN_REG_SET (range_live, FIRST_PSEUDO_REGISTER, i, + { + range_info[i].live_length++; + if (GET_CODE (insn) == CALL_INSN) + range_info[i].n_calls++; + }); + + /* figure out which ones will be dead by the end of the region */ + for (note = REG_NOTES (insn); note != NULL_RTX; note = XEXP (note, 1)) + { + if (REG_NOTE_KIND (note) == REG_DEAD + && GET_CODE (XEXP (note, 0)) == REG + && REGNO (XEXP (note, 0)) > FIRST_PSEUDO_REGISTER) + { + CLEAR_REGNO_REG_SET (range_live, REGNO (XEXP (note, 0))); + range_info[ REGNO (XEXP (note, 0)) ].deaths++; + } + } + } + + switch (code) + { + default: + break; + + /* Update loop_depth */ + case NOTE: + if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG) + range_loop_depth++; + else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END) + range_loop_depth++; + break; + + /* Record whether there was a call. */ + case CALL_INSN: + n_calls++; + break; + + /* Found a label, record the number of uses */ + case CODE_LABEL: + indx = CODE_LABEL_NUMBER (insn) - first_label; + if (indx >= num_labels) + { + if (stream) + fprintf (stream, "Code label %d doesn't fit in label table", + CODE_LABEL_NUMBER (insn)); + + ok_p = FALSE; + continue; + } + + all_label_ref[indx] = LABEL_NUSES (insn); + break; + + /* Found a jump of some sort, see where the jump goes. */ + case JUMP_INSN: + pattern = PATTERN (insn); + + /* Switch statement, process all labels */ + if (GET_CODE (pattern) == ADDR_VEC + || GET_CODE (pattern) == ADDR_DIFF_VEC) + { + int vec_num = (GET_CODE (PATTERN (insn)) == ADDR_VEC) ? 0 : 1; + int len = XVECLEN (pattern, vec_num); + bzero ((char *)found_label_ref, sizeof (char) * num_labels); + + for (i = 0; i < len; i++) + { + label_ref = XEXP (XVECEXP (pattern, vec_num, i), 0); + indx = CODE_LABEL_NUMBER (label_ref) - first_label; + + if (indx >= num_labels) + { + range_bad_insn (stream, + "Label ref doesn't fit in label table\n", + label_ref); + ok_p = FALSE; + } + + /* Only process duplicated labels once, since the LABEL_REF + chain only includes it once. */ + else if (!found_label_ref[indx]) + { + found_label_ref[indx] = TRUE; + loop_label_ref[indx]++; + } + } + } + + else + { + label_ref = JUMP_LABEL (insn); + if (!label_ref) + { + rtx sset; + range_bad_insn + (stream, + (((sset = single_set (insn)) != NULL_RTX + && (GET_CODE (SET_SRC (sset)) == REG + || GET_CODE (SET_SRC (sset)) == SUBREG + || GET_CODE (SET_SRC (sset)) == MEM)) + ? "Jump to indeterminate label in inner loop\n" + : "JUMP_LABEL (insn) is null.\n"), + insn); + + ok_p = FALSE; + continue; + } + + if (GET_CODE (label_ref) != CODE_LABEL) + { + range_bad_insn (stream, + "JUMP_LABEL (insn) is not a CODE_LABEL.\n", + insn); + + ok_p = FALSE; + continue; + } + + indx = CODE_LABEL_NUMBER (label_ref) - first_label; + if (indx >= num_labels) + { + range_bad_insn (stream, + "Label ref doesn't fit in label table\n", + insn); + + ok_p = FALSE; + continue; + } + + loop_label_ref[indx]++; + } + + break; + } + } + + /* Now that we've scanned the loop, check for any jumps into or out of + the loop, and if we've found them, don't do live range splitting. + If there are no registers used in the loop, there is nothing to do. */ + nl = (char *)0; + if (ok_p) + { + for (i = 0; i < (int)num_labels; i++) + if (loop_label_ref[i] != all_label_ref[i]) + { + ok_p = FALSE; + if (stream) + { + nl = "\n"; + if (!all_label_ref[i]) + fprintf (stream, "label %d was outside of the loop.\n", i+first_label); + else + fprintf (stream, "label %d had %d references, only %d were in loop.\n", + i+first_label, all_label_ref[i], loop_label_ref[i]); + } + } + + /* ignore any registers that use different modes, or that don't have simple + move instructions. */ + if (stream) + { + EXECUTE_IF_SET_IN_REG_SET (range_mixed_mode, FIRST_PSEUDO_REGISTER, regno, + { + nl = "\n"; + fprintf (stream, + "Skipping register %d used with different types\n", + regno); + }); + + EXECUTE_IF_SET_IN_REG_SET (range_no_move, FIRST_PSEUDO_REGISTER, regno, + { + nl = "\n"; + fprintf (stream, + "Skipping register %d that needs complex moves\n", + regno); + }); + } + + IOR_REG_SET (range_mixed_mode, range_no_move); + AND_COMPL_REG_SET (range_used, range_mixed_mode); + AND_COMPL_REG_SET (range_set, range_mixed_mode); + EXECUTE_IF_SET_IN_REG_SET(range_used, FIRST_PSEUDO_REGISTER, regno, + { + /* If the register isn't live at the end, + indicate that it must have died. */ + if (REGNO_REG_SET_P (live_at_end, regno)) + range_info[regno].copy_flags + |= LIVE_RANGE_COPYOUT; + + /* If the register is only used in a single + basic block, let local-alloc allocate + a register for it. */ + if (REG_BASIC_BLOCK (regno) >= 0) + { + nl = "\n"; + if (stream) + fprintf (stream, + "Skipping %d due to being used in a single basic block\n", + regno); + continue; + } + + /* If the register is live only within the + range, don't bother with it. */ + if (REG_LIVE_LENGTH (regno) + <= range_info[regno].live_length) + { + nl = "\n"; + if (stream) + fprintf (stream, + "Skipping %d due to being used only in range\n", + regno); + continue; + } + + range_regs[range_num_regs++] = regno; + }); + + if (range_num_regs == 0) + { + ok_p = FALSE; + if (stream) + fprintf (stream, "No registers found in loop\n"); + } + } + + if (stream && nl) + fputs (nl, stream); + + if (!ok_p) + return 0; + + qsort (range_regs, range_num_regs, sizeof (int), range_compare); + + CLEAR_REG_SET (range_used); + for (i = 0; i < range_num_regs; i++) + SET_REGNO_REG_SET (range_used, range_regs[i]); + +#if 0 + /* Narrow down range_start so that we include only those insns that reference + one of the live range variables. */ + regs_ref = ALLOCA_REG_SET (); + regs_set = ALLOCA_REG_SET (); + regs_tmp = ALLOCA_REG_SET (); + + uses_regs = inner_start; + for (insn = inner_start; insn; insn = PREV_INSN (insn)) + { + if (GET_RTX_CLASS (GET_CODE (insn)) == 'i' + && regset_mentioned_p (range_used, PATTERN (insn), FALSE, regs_ref, + regs_set)) + { + uses_regs = insn; + } + + if (insn == range_start) + break; + } + range_start = uses_regs; + + /* Narrow down range_end so that we include only those insns that reference + one of the live range variables. */ + CLEAR_REG_SET (regs_ref); + uses_regs = inner_end; + for (insn = inner_end; insn; insn = NEXT_INSN (insn)) + { + if (GET_RTX_CLASS (GET_CODE (insn)) == 'i' + && regset_mentioned_p (range_used, PATTERN (insn), FALSE, regs_ref, + regs_set)) + { + uses_regs = insn; + } + + if (insn == range_end) + break; + } + range_end = uses_regs; + + FREE_REG_SET (regs_ref); + FREE_REG_SET (regs_set); + FREE_REG_SET (regs_tmp); +#endif + + /* Mark the live range region. */ + regs = (rtx *) alloca (sizeof (rtx) * range_num_regs); + for (i = 0; i < range_num_regs; i++) + { + int r = range_regs[i]; + rinfo *ri = &range_info[r]; + + if (range_vars[r].block) + BLOCK_LIVE_RANGE_VAR_FLAG (range_vars[r].block) = TRUE; + + REG_N_RANGE_CANDIDATE_P (r) = 1; + regs[i] = gen_rtx (RANGE_REG, VOIDmode, + r, -1, ri->refs, ri->sets, ri->deaths, + ri->copy_flags, ri->live_length, ri->n_calls, + range_vars[r].symbol, range_vars[r].block); + } + + live_at_start_copy = OBSTACK_ALLOC_REG_SET (rtl_obstack); + live_at_end_copy = OBSTACK_ALLOC_REG_SET (rtl_obstack); + COPY_REG_SET (live_at_start_copy, live_at_start); + COPY_REG_SET (live_at_end_copy, live_at_end); + + regs_rtvec = gen_rtvec_v (range_num_regs, regs); + start = emit_note_before (NOTE_INSN_RANGE_START, range_start); + end = emit_note_after (NOTE_INSN_RANGE_END, range_end); + + ri = gen_rtx (RANGE_INFO, VOIDmode, start, end, regs_rtvec, n_calls, n_insns, + range_max_unique++, bb_start, bb_end, loop_depth, + live_at_start_copy, live_at_end_copy, 0, 0); + + NOTE_RANGE_INFO (start) = ri; + NOTE_RANGE_INFO (end) = ri; + + live_range_list = gen_rtx (INSN_LIST, VOIDmode, start, live_range_list); + return range_num_regs; +} + + +/* Scan all blocks looking for user variables so that we can map from + register number back to the appropriate DECL_NODE and BLOCK_NODE. */ + +static void +range_scan_blocks (block, args) + tree block; + tree args; +{ + tree var; + + /* Scan arguments */ + for (var = args; var != NULL_TREE; var = TREE_CHAIN (var)) + { + if (DECL_RTL (var) && GET_CODE (DECL_RTL (var)) == REG) + { + int regno = REGNO (DECL_RTL (var)); + if ((unsigned)regno >= (unsigned)max_regno) + abort (); + + range_vars[regno].symbol = var; + range_vars[regno].block = block; + } + } + + /* Loop over all blocks */ + for (; block != NULL_TREE; block = BLOCK_CHAIN (block)) + if (TREE_USED (block)) + { + /* Record all symbols in the block */ + for (var = BLOCK_VARS (block); var != NULL_TREE; var = TREE_CHAIN (var)) + { + if (DECL_RTL (var) && GET_CODE (DECL_RTL (var)) == REG) + { + int regno = REGNO (DECL_RTL (var)); + if ((unsigned)regno >= (unsigned)max_regno) + abort (); + + range_vars[regno].symbol = var; + range_vars[regno].block = block; + } + } + + /* Record the subblocks, and their subblocks... */ + range_scan_blocks (BLOCK_SUBBLOCKS (block), NULL_TREE); + } +} + + +/* Recalculate the basic blocks due to adding copyins and copyouts. */ + +static void +range_update_basic_block (stream, first_insn, new_bb, + new_bb_count, range_max_regno) + FILE *stream; + rtx first_insn; + bb_link *new_bb; + int new_bb_count; + int range_max_regno; +{ + int i; + rtx insn; + rtx range; + rtx block_end; + rtx block_start; + int block; + int in_block_p; + int old_n_basic_blocks = n_basic_blocks; + int *map_bb = (int *) alloca (sizeof (int) * n_basic_blocks); + regset live = ALLOCA_REG_SET (); + + COPY_REG_SET (live, basic_block_live_at_start[0]); + + /* Go through and add NOTE_INSN_LIVE notes for each current basic block. */ + for (i = 0; i < old_n_basic_blocks; i++) + { + rtx p = emit_note_before (NOTE_INSN_LIVE, BLOCK_HEAD (i)); + NOTE_LIVE_INFO (p) = gen_rtx (RANGE_LIVE, VOIDmode, + basic_block_live_at_start[i], i); + map_bb[i] = -1; + + if (stream) + { + fprintf (stream, + "Old basic block #%d, first insn %d, last insn %d, live", + i, + INSN_UID (BLOCK_HEAD (i)), + INSN_UID (BLOCK_END (i))); + bitmap_print (stream, basic_block_live_at_start[i], " {", "}\n"); + } + } + + if (stream) + putc ('\n', stream); + + /* Recalculate the basic blocks. */ + free ((char *)x_basic_block_head); + free ((char *)x_basic_block_end); + x_basic_block_head = x_basic_block_end = (rtx *)0; + find_basic_blocks (first_insn, max_regno, stream); + free_basic_block_vars (TRUE); + + /* Restore the live information. We assume that flow will find either a + previous start of a basic block, or the newly created insn blocks as + the start of the new basic blocks. */ + + if (old_n_basic_blocks != n_basic_blocks) + basic_block_live_at_start + = (regset *) oballoc (sizeof (regset) * n_basic_blocks); + + init_regset_vector (basic_block_live_at_start, n_basic_blocks, + rtl_obstack); + + block = 0; + in_block_p = FALSE; + block_start = BLOCK_HEAD (0); + block_end = BLOCK_END (0); + for (insn = first_insn; insn; insn = NEXT_INSN (insn)) + { + /* If this is the start of a basic block update live information. */ + if (insn == block_start) + { + int i; + in_block_p = TRUE; + + /* See if this was the start of one of the "new" basic + blocks. If so, get register livetime information from + the data we saved when we created the range. */ + for (i = 0; i < new_bb_count; i++) + if (new_bb[i].first_insn == insn) + break; + + if (i < new_bb_count) + COPY_REG_SET (live, new_bb[i].live_at_start); + + COPY_REG_SET (basic_block_live_at_start[block], live); + } + + if (GET_CODE (insn) == NOTE) + { + /* Is this where an old basic block began? */ + if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LIVE) + { + rtx info = NOTE_LIVE_INFO (insn); + COPY_REG_SET (live, RANGE_LIVE_BITMAP (info)); + map_bb[RANGE_LIVE_ORIG_BLOCK (info)] = block; + FREE_REG_SET (RANGE_LIVE_BITMAP (info)); + NOTE_LIVE_INFO (insn) = NULL_RTX; + if (stream) + fprintf (stream, "Old basic block #%d is now %d.\n", + RANGE_LIVE_ORIG_BLOCK (info), block); + } + + /* If a range start/end, use stored live information. */ + else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_START) + { + rtx ri = NOTE_RANGE_INFO (insn); + int old_block = RANGE_INFO_BB_START (ri); + + RANGE_INFO_BB_START (ri) = block; + COPY_REG_SET (live, RANGE_INFO_LIVE_START (ri)); + if (stream) + fprintf (stream, + "Changing range start basic block from %d to %d\n", + old_block, block); + } + + else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_END) + { + rtx ri = NOTE_RANGE_INFO (insn); + int old_block = RANGE_INFO_BB_END (ri); + int new_block = (in_block_p) ? block : block-1; + + RANGE_INFO_BB_END (ri) = new_block; + COPY_REG_SET (live, RANGE_INFO_LIVE_END (ri)); + if (stream) + fprintf (stream, + "Changing range end basic block from %d to %d\n", + old_block, new_block); + } + } + + /* Update live/dead information. */ + if (GET_RTX_CLASS (GET_CODE (insn)) == 'i') + range_basic_insn (insn, live, range_max_regno); + + /* Advance basic block if at end. */ + if (insn == block_end) + { + block++; + in_block_p = FALSE; + if (block < n_basic_blocks) + { + block_start = BLOCK_HEAD (block); + block_end = BLOCK_END (block); + } + else + block_start = block_end = NULL_RTX; + } + } + + if (stream) + { + putc ('\n', stream); + fflush (stream); + } + + /* Update REG_BASIC_BLOCK field now. */ + for (i = 0; i < max_regno; i++) + { + if (REG_BASIC_BLOCK (i) >= 0) + REG_BASIC_BLOCK (i) = map_bb[REG_BASIC_BLOCK (i)]; + } +} + + +/* Allocate the new registers for live range splitting. Do this after we've + scanned all of the insns, so that we grow the tables only once. */ + +static void +range_finish (stream, first_insn, count, range_max_regno) + FILE *stream; + rtx first_insn; + int count; + int range_max_regno; +{ + rtx range; + int new_max_regno = max_reg_num () + count; + rtx *replacements = (rtx *) alloca (new_max_regno * sizeof (rtx)); + regset old_dead = ALLOCA_REG_SET (); + regset new_live = ALLOCA_REG_SET (); + regset copyouts = ALLOCA_REG_SET (); + rtx insn; + int i; + tree *block_list /* set up NOTE_BLOCK_NUM field */ + = ((write_symbols == NO_DEBUG) + ? (tree *)0 + : identify_blocks (DECL_INITIAL (current_function_decl), first_insn)); + + bb_link *new_bb; + int new_bb_count = 0; + int max_bb_count = 0; + + no_new_pseudos = 0; + for (range = live_range_list; range; range = XEXP (range, 1)) + max_bb_count += 2; + + new_bb = (bb_link *) alloca (sizeof (bb_link) * max_bb_count); + bzero ((char *)new_bb, sizeof (bb_link) * max_bb_count); + + if (stream) + putc ('\n', stream); + + /* Grow the register tables */ + allocate_reg_info (new_max_regno, FALSE, FALSE); + + for (range = live_range_list; range; range = XEXP (range, 1)) + { + rtx range_start = XEXP (range, 0); + rtx ri = NOTE_RANGE_INFO (range_start); + rtx range_end = RANGE_INFO_NOTE_END (ri); + int bb_start = RANGE_INFO_BB_START (ri); + int bb_end = RANGE_INFO_BB_END (ri); + int bb = (bb_start >= 0 && bb_start == bb_end) ? bb_start : -2; + rtx after; + rtx before; + int new_scope_p = (write_symbols != NO_DEBUG /* create new scope */ + && flag_live_range_scope /* block for vars? */ + && (write_symbols != DBX_DEBUG + || !LIVE_RANGE_GDBSTAB_P ())); + + after = range_start; + before = range_end; + + bzero ((char *)replacements, new_max_regno * sizeof (rtx)); + CLEAR_REG_SET (old_dead); + CLEAR_REG_SET (copyouts); + + /* Allocate new registers, set up the fields needed. */ + for (i = 0; i < (int)RANGE_INFO_NUM_REGS (ri); i++) + { + int old_regno = RANGE_REG_PSEUDO (ri, i); + rtx old_reg = regno_reg_rtx[old_regno]; + enum machine_mode mode = GET_MODE (old_reg); + rtx new_reg = gen_reg_rtx (mode); + int new_regno = REGNO (new_reg); + + replacements[old_regno] = new_reg; + + RANGE_REG_COPY (ri, i) = new_regno; + REG_N_RANGE_COPY_P (new_regno) = TRUE; + REG_N_REFS (new_regno) = RANGE_REG_REFS (ri, i); + REG_N_SETS (new_regno) = RANGE_REG_SETS (ri, i); + REG_N_DEATHS (new_regno) = RANGE_REG_DEATHS (ri, i); + REG_LIVE_LENGTH (new_regno) = RANGE_REG_LIVE_LENGTH (ri, i); + REG_N_CALLS_CROSSED (new_regno) = RANGE_REG_N_CALLS (ri, i); + REG_CHANGES_SIZE (new_regno) = 0; + REG_BASIC_BLOCK (new_regno) = bb; + REGNO_POINTER_FLAG (new_regno) = REGNO_POINTER_FLAG (old_regno); + REGNO_POINTER_ALIGN (new_regno) = REGNO_POINTER_ALIGN (old_regno); + REG_FUNCTION_VALUE_P (new_reg) = REG_FUNCTION_VALUE_P (old_reg); + REG_USERVAR_P (new_reg) = REG_USERVAR_P (old_reg); + REG_LOOP_TEST_P (new_reg) = REG_LOOP_TEST_P (old_reg); + RTX_UNCHANGING_P (new_reg) = RTX_UNCHANGING_P (old_reg); + +#if 0 + /* Until we can make sure we get this right, don't update the + reference counts on the old register. */ + REG_N_REFS (old_regno) -= REG_N_REFS (new_regno); + REG_N_SETS (old_regno) -= REG_N_SETS (new_regno); + REG_N_DEATHS (old_regno) -= REG_N_DEATHS (new_regno); + REG_N_CALLS_CROSSED (old_regno) -= REG_N_CALLS_CROSSED (new_regno); + REG_LIVE_LENGTH (old_regno) -= REG_LIVE_LENGTH (new_regno); + + if (REG_N_REFS (old_regno) <= 0) + error ("Setting # references of register %d to %d\n", + old_regno, REG_N_REFS (old_regno)); + + if (REG_N_SETS (old_regno) < 0) + error ("Setting # sets of register %d to %d\n", + old_regno, REG_N_SETS (old_regno)); + + if (REG_N_CALLS_CROSSED (old_regno) < 0) + error ("Setting # calls crossed of register %d to %d\n", + old_regno, REG_N_CALLS_CROSSED (old_regno)); + + if (REG_N_DEATHS (old_regno) < 0) + error ("Setting # deaths of register %d to %d\n", + old_regno, REG_N_SETS (old_regno)); + + if (REG_LIVE_LENGTH (old_regno) <= 0) + error ("Setting live length of register %d to %d\n", + old_regno, REG_LIVE_LENGTH (old_regno)); +#endif + + SET_REGNO_REG_SET (old_dead, old_regno); + + /* If this is a user variable, add the range into the list of + different ranges the variable spans. */ + if (RANGE_REG_SYMBOL_NODE (ri, i)) + { + tree sym = RANGE_REG_SYMBOL_NODE (ri, i); + rtx var = DECL_LIVE_RANGE_RTL (sym); + + if (!var) + DECL_LIVE_RANGE_RTL (sym) = var + = gen_rtx (RANGE_VAR, VOIDmode, NULL_RTX, + RANGE_REG_BLOCK_NODE (ri, i), 0); + + RANGE_VAR_NUM (var)++; + RANGE_VAR_LIST (var) = gen_rtx (EXPR_LIST, VOIDmode, ri, + RANGE_VAR_LIST (var)); + } + +#if 0 + /* global.c implements regs_may_share as requiring the registers + to share the same hard register. */ + regs_may_share = gen_rtx (EXPR_LIST, VOIDmode, old_reg, + gen_rtx (EXPR_LIST, VOIDmode, new_reg, + regs_may_share)); +#endif + + /* Create a new scoping block for debug information if needed. */ + if (new_scope_p + && RANGE_REG_SYMBOL_NODE (ri, i) != NULL_TREE + && RANGE_REG_BLOCK_NODE (ri, i) != NULL_TREE) + { + new_scope_p = FALSE; + range_start = emit_note_after (NOTE_INSN_BLOCK_BEG, range_start); + NOTE_BLOCK_NUMBER (range_start) = NOTE_BLOCK_LIVE_RANGE_BLOCK; + + range_end = emit_note_before (NOTE_INSN_BLOCK_END, range_end); + NOTE_BLOCK_NUMBER (range_end) = NOTE_BLOCK_LIVE_RANGE_BLOCK; + + if (stream) + fprintf (stream, "Creating new scoping block\n"); + } + + /* If needed, generate the appropriate copies into and out of + the new register. Tell global.c that we want to share registers + if possible. Since we might be creating a new basic block + for the copyin or copyout, tell local alloc to keep its grubby + paws off of the registers that need copies. */ + if ((RANGE_REG_COPY_FLAGS (ri, i) & LIVE_RANGE_COPYIN) != 0) + { + after + = emit_insn_after (GEN_FCN (mov_optab->handlers[(int) mode].insn_code) + (new_reg, old_reg), after); + + RANGE_REG_LIVE_LENGTH (ri, i)++; + REG_LIVE_LENGTH (old_regno)++; + REG_LIVE_LENGTH (new_regno)++; + REG_N_REFS (old_regno)++; + REG_N_REFS (new_regno)++; + REG_N_SETS (new_regno)++; + REG_N_DEATHS (old_regno)++; + REG_BASIC_BLOCK (new_regno) = REG_BLOCK_GLOBAL; + REG_NOTES (after) = gen_rtx (EXPR_LIST, REG_EQUAL /* REG_EQUIV */, old_reg, + gen_rtx (EXPR_LIST, REG_DEAD, + old_reg, + REG_NOTES (after))); + } + + if ((RANGE_REG_COPY_FLAGS (ri, i) & LIVE_RANGE_COPYOUT) != 0) + { + before + = emit_insn_before (GEN_FCN (mov_optab->handlers[(int) mode].insn_code) + (old_reg, new_reg), before); + + RANGE_REG_LIVE_LENGTH (ri, i)++; + REG_LIVE_LENGTH (old_regno)++; + REG_LIVE_LENGTH (new_regno)++; + REG_N_REFS (old_regno)++; + REG_N_REFS (new_regno)++; + REG_N_SETS (old_regno)++; + REG_N_DEATHS (new_regno)++; + REG_BASIC_BLOCK (new_regno) = REG_BLOCK_GLOBAL; + REG_NOTES (before) = gen_rtx (EXPR_LIST, REG_DEAD, new_reg, + REG_NOTES (before)); + SET_REGNO_REG_SET (copyouts, new_regno); + } + } + + /* Add insns created for copyins to new basic block list, if new copyins + were created, and the insns aren't already part of a basic block. */ + if (range_start != after) + { + int in_bb_p; + rtx end; + + /* If the insns created are the first, add them to the beginning + of the basic block. */ + if (bb_start == 0) + { + rtx temp = get_insns (); + /* Search forward until we hit a CODE_LABEL or real insn. */ + while (! (GET_CODE (temp) == CODE_LABEL + || GET_RTX_CLASS (GET_CODE (temp)) == 'i')) + temp = NEXT_INSN (temp); + BLOCK_HEAD (0) = temp; + } + + + /* Check if the insns are already in the basic block */ + in_bb_p = FALSE; + end = BLOCK_END (bb_start); + for (insn = BLOCK_HEAD (bb_start); + insn && insn != end; + insn = NEXT_INSN (insn)) + { + if (insn == after) + { + in_bb_p = TRUE; + break; + } + } + + /* If needed, create a new basic block. */ + if (!in_bb_p) + { + bb_link *p = &new_bb[new_bb_count++]; + p->first_insn = NEXT_INSN (range_start); + p->last_insn = after; + p->live_at_start = RANGE_INFO_LIVE_START (ri); + } + } + + /* Add insns created for copyouts to new basic block list, if new + copyouts were created, and the insns aren't already part of a basic + block, or can be added to a basic block trivally. */ + if (range_end != before) + { + int in_bb_p = FALSE; + rtx end = BLOCK_END (bb_end); + + /* Check if the insns are already in the basic block */ + for (insn = BLOCK_HEAD (bb_end); + insn && insn != end; + insn = NEXT_INSN (insn)) + { + if (insn == before) + { + in_bb_p = TRUE; + break; + } + } + + /* If needed, create a new basic block. */ + if (!in_bb_p) + { + bb_link *p = &new_bb[new_bb_count++]; + p->first_insn = before; + p->last_insn = PREV_INSN (range_end); + p->live_at_start = OBSTACK_ALLOC_REG_SET (rtl_obstack); + IOR_REG_SET (p->live_at_start, RANGE_INFO_LIVE_END (ri)); + IOR_REG_SET (p->live_at_start, copyouts); + AND_COMPL_REG_SET (p->live_at_start, old_dead); + } + } + + /* Replace the registers */ + for (insn = NEXT_INSN (after); + insn != NULL_RTX && insn != before; + insn = NEXT_INSN (insn)) + { + enum rtx_code code = GET_CODE (insn); + + if (GET_RTX_CLASS (code) == 'i') + { + rtx note; + PATTERN (insn) = replace_regs (PATTERN (insn), replacements, + new_max_regno, TRUE); + + for (note = REG_NOTES (insn); + note != NULL_RTX; + note = XEXP (note, 1)) + { + if ((REG_NOTE_KIND (note) == REG_DEAD + || REG_NOTE_KIND (note) == REG_UNUSED) + && GET_CODE (XEXP (note, 0)) == REG + && replacements[ REGNO (XEXP (note, 0))] != NULL_RTX) + XEXP (note, 0) = replacements[ REGNO (XEXP (note, 0))]; + } + } + } + } + + if (stream) + fflush (stream); + + /* Update # registers */ + max_regno = new_max_regno; + + /* Recalculate basic blocks if we need to. */ + if (new_bb_count) + range_update_basic_block (stream, first_insn, new_bb, + new_bb_count, range_max_regno); + + /* After recreating the basic block, update the live information, + replacing the old registers with the new copies. */ + for (range = live_range_list; range; range = XEXP (range, 1)) + { + rtx range_start = XEXP (range, 0); + rtx ri = NOTE_RANGE_INFO (range_start); + int bb_start = RANGE_INFO_BB_START (ri); + int bb_end = RANGE_INFO_BB_END (ri); + int block; + + bzero ((char *)replacements, new_max_regno * sizeof (rtx)); + CLEAR_REG_SET (old_dead); + for (i = 0; i < (int)RANGE_INFO_NUM_REGS (ri); i++) + { + int old_regno = RANGE_REG_PSEUDO (ri, i); + int new_regno = RANGE_REG_COPY (ri, i); + if (new_regno >= 0) + { + replacements[old_regno] = regno_reg_rtx[new_regno]; + SET_REGNO_REG_SET (old_dead, old_regno); + } + } + + /* Update live information */ + for (block = bb_start+1; block <= bb_end; block++) + { + regset bits = basic_block_live_at_start[block]; + + CLEAR_REG_SET (new_live); + EXECUTE_IF_AND_IN_REG_SET (bits, old_dead, + FIRST_PSEUDO_REGISTER, i, + { + int n = REGNO (replacements[i]); + SET_REGNO_REG_SET (new_live, n); + }); + + AND_COMPL_REG_SET (bits, old_dead); + IOR_REG_SET (bits, new_live); + basic_block_live_at_start[block] = bits; + } + + if (stream) + { + putc ('\n', stream); + live_range_print (stream, ri, "::", ""); + } + } + + /* Add new scoping blocks and reset NOTE_BLOCK_NUMBER field. */ + if (write_symbols != NO_DEBUG) + { + reorder_blocks (block_list, DECL_INITIAL (current_function_decl), + first_insn); + free ((char *)block_list); + } + + /* Release any storage allocated */ + FREE_REG_SET (old_dead); + FREE_REG_SET (new_live); + FREE_REG_SET (copyouts); + + if (stream) + { + putc ('\n', stream); + print_blocks_internal (stream, DECL_INITIAL (current_function_decl), 0); + putc ('\n', stream); + fflush (stream); + } + no_new_pseudos = 1; +} + +/* Main function for live_range support. Return the number of variables that + were spilled to the stack were used in small loops and were copied into new + pseudo registers for the run of that loop. Since we are run after + flow_analysis and local_alloc, we have to set up the appropriate tables for + any new pseudo variables we create. */ + +int +live_range (first_insn, stream) + rtx first_insn; + FILE *stream; +{ + rtx insn; + rtx prev; + rtx next; + rtx loop_start = NULL_RTX; + rtx loop_prefix = NULL_RTX; + int count = 0; + int i; + int basic_block; + int user_block; + int loop_user_block; + int loop_depth; + int range_max_regno; + regset live; + regset simple_insns_live; + regset loop_live; + rtx simple_insns = NULL_RTX; + int *insn_ruid; + int ruid; + + struct skip_flags { + int *flag; + char *reason; + }; + + /* Awkward cases we don't want to handle. */ + static struct skip_flags skip[] = { + { ¤t_function_has_nonlocal_label, "nonlocal label" }, + { ¤t_function_has_nonlocal_goto, "nonlocal goto" }, + { ¤t_function_calls_setjmp, "calls setjmp" }, + { ¤t_function_calls_longjmp, "calls longjmp" } + }; + + for (i = 0; i < (int)(sizeof (skip) / sizeof (skip[0])); i++) + if (*skip[i].flag) + { + if (stream) + fprintf (stream, "Function has %s, skipping live range splitting\n", + skip[i].reason); + + return 0; + } + + if (n_basic_blocks <= 0) + { + if (stream) + fprintf (stream, "Function has no more than 1 basic block, skipping live range splitting\n"); + + return 0; + } + + live_range_list = NULL_RTX; + range_set = ALLOCA_REG_SET (); + range_used = ALLOCA_REG_SET (); + range_mixed_mode = ALLOCA_REG_SET (); + range_no_move = ALLOCA_REG_SET (); + range_live = ALLOCA_REG_SET (); + live = ALLOCA_REG_SET (); + simple_insns_live = ALLOCA_REG_SET (); + loop_live = ALLOCA_REG_SET (); + range_max_regno = max_regno; + range_info = (rinfo *) alloca (sizeof (rinfo) * max_regno); + range_regs = (int *) alloca (sizeof (int) * max_regno); + range_max_uid = (unsigned)get_max_uid (); + range_vars = (var_info *) alloca (sizeof (var_info) * max_regno); + range_block_insn = (bb_link **) alloca (sizeof (bb_link *) * range_max_uid); + range_block_orig = (bb_link *) alloca (sizeof (bb_link) * n_basic_blocks); + bzero ((char *)range_vars, sizeof (var_info) * max_regno); + bzero ((char *)range_block_insn, sizeof (bb_link *) * range_max_uid); + bzero ((char *)range_block_orig, sizeof (bb_link) * n_basic_blocks); + + /* Figure out which basic block things are in. */ + for (i = 0; i < n_basic_blocks; i++) + { + rtx end = BLOCK_END (i); + rtx head = BLOCK_HEAD (i); + range_block_orig[i].block = i; + range_block_orig[i].first_insn = head; + range_block_orig[i].last_insn = end; + range_block_orig[i].live_at_start = basic_block_live_at_start[i]; + + range_block_insn[INSN_UID (end)] = &range_block_orig[i]; + for (insn = head; insn && insn != end; insn = NEXT_INSN (insn)) + range_block_insn[INSN_UID (insn)] = &range_block_orig[i]; + } + + /* Map user variables to their pseudo register */ + range_scan_blocks (DECL_INITIAL (current_function_decl), + DECL_ARGUMENTS (current_function_decl)); + + /* Search for inner loops that do not span logical block boundaries. + Include an non-jump INSNs before the loop to include any setup for the + loop that is not included within the LOOP_BEG note. */ + basic_block = loop_user_block = loop_depth = 0; + user_block = 0; + COPY_REG_SET (live, basic_block_live_at_start[0]); + + insn_ruid = (int *) alloca ((range_max_uid + 1) * sizeof (int)); + bzero ((char *) insn_ruid, (range_max_uid + 1) * sizeof (int)); + ruid = 0; + + for (insn = first_insn; insn; insn = NEXT_INSN (insn)) + { + int block_tmp; + enum rtx_code code = GET_CODE (insn); + + /* This might be a note insn emitted by range_inner, in which case we + can't put it in insn_ruid because that will give an out-of-range + array access. Since we only use it for JUMP_INSNs this should be + OK. */ + + if (INSN_UID (insn) <= range_max_uid) + insn_ruid[INSN_UID (insn)] = ++ruid; + + /* If this is a different basic block, update live variables. */ + block_tmp = RANGE_BLOCK_NUM (insn); + if (block_tmp >= 0 && basic_block != block_tmp) + { + basic_block = block_tmp; + COPY_REG_SET (live, basic_block_live_at_start[basic_block]); + } + + /* Keep track of liveness for simple insns that might preceed LOOP_BEG */ + if (GET_CODE (insn) == INSN && simple_insns == NULL_RTX) + { +#ifdef HAVE_cc0 + if (reg_referenced_p (cc0_rtx, PATTERN (insn))) + simple_insns = NULL_RTX; + else +#endif + { + simple_insns = insn; + COPY_REG_SET (simple_insns_live, live); + } + } + else if (GET_CODE (insn) != INSN) + { + /* Allow simple notes to not zap the simple_insns block */ + if (GET_CODE (insn) != NOTE + || (NOTE_LINE_NUMBER (insn) < 0 + && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG + && NOTE_LINE_NUMBER (insn) != NOTE_INSN_DELETED)) + simple_insns = NULL_RTX; + } + + /* Update live/dead information. */ + if (GET_RTX_CLASS (code) == 'i') + range_basic_insn (insn, live, range_max_regno); + + /* Look for inner loops */ + else if (code == NOTE) + { + if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG) + { + /* Add simple insns that occur before the loop begins */ + if (simple_insns) + { + loop_prefix = simple_insns; + COPY_REG_SET (loop_live, simple_insns_live); + } + else + { + loop_prefix = insn; + COPY_REG_SET (loop_live, live); + } + + loop_start = insn; + loop_user_block = user_block; + loop_depth++; + } + + else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END) + { + loop_depth--; + if (loop_start && loop_user_block == user_block) + { + rtx scan_start; + + /* See whether a new basic block begins with the + next insn -- if so, use its live information. */ + rtx follow_insn, p; + for (follow_insn = NEXT_INSN (insn); + (follow_insn + && ((block_tmp = RANGE_BLOCK_NUM (follow_insn)) < 0 + || block_tmp == basic_block) + && GET_CODE (follow_insn) == NOTE); + follow_insn = NEXT_INSN (follow_insn)) + ; + + if (!follow_insn) + CLEAR_REG_SET (live); + else if (block_tmp >= 0 && block_tmp != basic_block) + COPY_REG_SET (live, basic_block_live_at_start[block_tmp]); + + /* Do not create live ranges for phony loops. The code to + detect phony loops was mostly lifted from scan_loop. + + Try to find the label for the start of the loop. */ + for (p = NEXT_INSN (loop_start); + (p != insn + && GET_CODE (p) != CODE_LABEL + && GET_RTX_CLASS (GET_CODE (p)) != 'i' + && (GET_CODE (p) != NOTE + || (NOTE_LINE_NUMBER (p) != NOTE_INSN_LOOP_BEG + && NOTE_LINE_NUMBER (p) != NOTE_INSN_LOOP_END))); + p = NEXT_INSN (p)) + ; + + scan_start = p; + + /* Detect a jump to the bottom of the loop. */ + if (GET_CODE (p) == JUMP_INSN) + { + if (simplejump_p (p) + && JUMP_LABEL (p) != 0 + /* Check to see whether the jump actually + jumps out of the loop (meaning it's no loop). + This case can happen for things like do + do {..} while (0). */ + && insn_ruid[INSN_UID (JUMP_LABEL (p))] > 0 + && (insn_ruid[INSN_UID (loop_start)] + <= insn_ruid[INSN_UID (JUMP_LABEL (p))]) + && (insn_ruid[INSN_UID (insn)] + >= insn_ruid[INSN_UID (JUMP_LABEL (p))])) + scan_start = JUMP_LABEL (p); + } + + /* If we did not find the CODE_LABEL for the start of this + loop, then we either have a phony loop or something very + strange has happened. Do not perform LRS opts on such + a loop. */ + if (GET_CODE (scan_start) == CODE_LABEL) + count += range_inner (stream, loop_prefix, insn, loop_start, + insn, loop_live, live, loop_depth); + } + + loop_start = NULL_RTX; + loop_prefix = NULL_RTX; + } + + else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_BEG) + user_block++; + + else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END) + user_block--; + } + } + + /* Reverse list of live ranges so that it goes forwards, not backwards. */ + prev = next = NULL_RTX; + for (insn = live_range_list; insn != NULL_RTX; insn = next) + { + next = XEXP (insn, 1); + XEXP (insn, 1) = prev; + prev = insn; + } + live_range_list = prev; + + /* If we discovered any live ranges, create them now */ + if (count) + range_finish (stream, first_insn, count, range_max_regno); + + FREE_REG_SET (range_set); + FREE_REG_SET (range_used); + FREE_REG_SET (range_live); + FREE_REG_SET (range_mixed_mode); + FREE_REG_SET (range_no_move); + FREE_REG_SET (simple_insns_live); + FREE_REG_SET (loop_live); + FREE_REG_SET (live); + range_block_insn = (bb_link **)0; + range_block_orig = (bb_link *)0; + range_info = (rinfo *)0; + range_regs = (int *)0; + + return count; +} + + +/* Initialize live_range information */ + +void +init_live_range () +{ + live_range_list = NULL_RTX; +} +/* END CYGNUS LOCAL */ |