* Makefile.in (HOST_RTL): Add $(HOST_PREFIX)bitmap.o.

        (rtl.o, emit-rtl.o): Add dependency on bitmap.h.
        ($(HOST_PREFIX_1)rtl.o): Likewise.
        ($(HOST_PREFIX_1)bitmap.o): New host object.
        * emit-rtl.c (toplevel): Include bitmap.h.
        (gen_rtx): Handle 't' and 'b' nodes.
        * print-rtl.c (print_rtx): Handle printing NOTE_INSN_LIVE notes.
        Print block number for block begin/end notes.  Print 't' type
        nodes as a pointer.  Know that the 3rd argument of live range
        start/stop notes is really a range_info rtx.  If type is 'b', print
        out argument as a bitmap.
        * rtl.c: Include bitmap.c.
        (copy_rtx): Copy tree nodes as is.  Copy bitmaps if type is 'b'.
        (note_insn_name): Add NOTE_INSN_RANGE_{START,END}, NOTE_INSN_LIVE.
        * rtl.def (RANGE_LIVE): New node to hold live information while we
        recalculate the basic blocks.
        (RANGE_REG, RANGE_INFO): New rtl types for live range splitting.
        (RANGE_VAR): New node, to hold information saved in symbol node for New
        communicating live range information to the debug output functions.
        * rtl.h (rtunion_def): Add rttree and rtbit fields.
        (XBITMAP, XTREE): New accessor macros.
        (NOTE_LIVE_INFO): Overload NOTE_SOURCE_FILE for NOTE_INSN_LIVE notes.
        (NOTE_RANGE_INFO): Similarly for NOTE_INSN_RANGE_{START,END} notes.
        (NOTE_BLOCK_LIVE_RANGE_BLOCK): Define.
        (NOTE_INSN_RANGE_START, NOTE_INSN_RANGE_END, NOTE_INSN_LIVE): New notes.
        (RANGE_LIVE_{BITMAP,ORIG_BLOCK}): New accessor macros.
        (RANGE_REG_{SYMBOL,BLOCK}_NODE, RANGE_VAR_*): New accessor macros.
        (RANGE_INFO_*): Likewise.
        * sched.c (sched_analyze): Keep live range start/stop notes.
        (unlink_other_notes): Likewise.
        * haifa-sched.c (sched_analyze): Keep live range start/stop notes.
        (unlink_other_notes): Likewise.
        * tree.h (BLOCK_LIVE_RANGE_{START,END,VAR_FLAG}): New accessor macros.
        (BLOCK_LIVE_RANGE_FLAG): Likewise.
        (DECL_LIVE_RANGE_RTL): Likewise.
        (struct tree_block): Add live_range_flag, live_range_var_flag,
        live_range_start and live_range_end.
        (struct tree_decl): Add live_range_rtl field.
        * gengenrtl.c (type_from_format): Handle 'b' and 't'.
        (accessor_from_format): Likewise.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@19727 138bc75d-0d04-0410-961f-82ee72b054a4

11 files changed, 315 insertions, 12 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 0c0521ea9eb..ee3f8c5abf0 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -23,6 +23,48 @@ Wed May 13 13:09:19 1998  Jim Wilson  <wilson@cygnus.com>
 	TARGET_CMOVE support.
 
 Wed May 13 15:28:59 1998  Michael Meissner  <meissner@cygnus.com>
+			  Jeff Law <law@cygnus.com>
+
+	* Makefile.in (HOST_RTL): Add $(HOST_PREFIX)bitmap.o.
+	(rtl.o, emit-rtl.o): Add dependency on bitmap.h.
+	($(HOST_PREFIX_1)rtl.o): Likewise.
+	($(HOST_PREFIX_1)bitmap.o): New host object.
+	* emit-rtl.c (toplevel): Include bitmap.h.
+	(gen_rtx): Handle 't' and 'b' nodes.
+	* print-rtl.c (print_rtx): Handle printing NOTE_INSN_LIVE notes.
+	Print block number for block begin/end notes.  Print 't' type
+	nodes as a pointer.  Know that the 3rd argument of live range
+	start/stop notes is really a range_info rtx.  If type is 'b', print
+	out argument as a bitmap.
+	* rtl.c: Include bitmap.c.
+	(copy_rtx): Copy tree nodes as is.  Copy bitmaps if type is 'b'.
+	(note_insn_name): Add NOTE_INSN_RANGE_{START,END}, NOTE_INSN_LIVE.
+	* rtl.def (RANGE_LIVE): New node to hold live information while we
+	recalculate the basic blocks.
+	(RANGE_REG, RANGE_INFO): New rtl types for live range splitting.
+        (RANGE_VAR): New node, to hold information saved in symbol node for New 
+        communicating live range information to the debug output functions.
+	* rtl.h (rtunion_def): Add rttree and rtbit fields.
+	(XBITMAP, XTREE): New accessor macros.
+ 	(NOTE_LIVE_INFO): Overload NOTE_SOURCE_FILE for NOTE_INSN_LIVE notes.
+	(NOTE_RANGE_INFO): Similarly for NOTE_INSN_RANGE_{START,END} notes.
+	(NOTE_BLOCK_LIVE_RANGE_BLOCK): Define.
+	(NOTE_INSN_RANGE_START, NOTE_INSN_RANGE_END, NOTE_INSN_LIVE): New notes.
+	(RANGE_LIVE_{BITMAP,ORIG_BLOCK}): New accessor macros.
+	(RANGE_REG_{SYMBOL,BLOCK}_NODE, RANGE_VAR_*): New accessor macros.
+	(RANGE_INFO_*): Likewise.
+	* sched.c (sched_analyze): Keep live range start/stop notes.
+	(unlink_other_notes): Likewise.
+	* haifa-sched.c (sched_analyze): Keep live range start/stop notes.
+	(unlink_other_notes): Likewise.
+	* tree.h (BLOCK_LIVE_RANGE_{START,END,VAR_FLAG}): New accessor macros.
+	(BLOCK_LIVE_RANGE_FLAG): Likewise.
+	(DECL_LIVE_RANGE_RTL): Likewise.
+	(struct tree_block): Add live_range_flag, live_range_var_flag,
+	live_range_start and live_range_end.
+	(struct tree_decl): Add live_range_rtl field.
+	* gengenrtl.c (type_from_format): Handle 'b' and 't'.
+	(accessor_from_format): Likewise.
 
 	* haifa-sched.c (schedule_block): Make verbose output line up.
 	Also add a blank line in printing the individual ready lists.
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 48ea6304061..0b787453de4 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -521,7 +521,7 @@ LIBS = $(OBSTACK) $(USE_ALLOCA) $(MALLOC) $(VFPRINTF) $(DOPRINT) $(CLIB)
 HOST_LIBS = $(USE_HOST_OBSTACK) $(USE_HOST_ALLOCA) $(USE_HOST_MALLOC)  \
 	    $(USE_HOST_VFPRINTF) $(USE_HOST_DOPRINT) $(HOST_CLIB)
 
-HOST_RTL = $(HOST_PREFIX)rtl.o
+HOST_RTL = $(HOST_PREFIX)rtl.o $(HOST_PREFIX)bitmap.o
 HOST_RTLANAL = $(HOST_PREFIX)rtlanal.o
 HOST_PRINT = $(HOST_PREFIX)print-rtl.o
 
@@ -1342,7 +1342,7 @@ toplev.o : toplev.c $(CONFIG_H) system.h $(TREE_H) $(RTL_H) \
 	  -DTARGET_NAME=\"$(target_alias)\" \
 	  -c `echo $(srcdir)/toplev.c | sed 's,^\./,,'`
 
-rtl.o : rtl.c $(CONFIG_H) system.h $(RTL_H)
+rtl.o : rtl.c $(CONFIG_H) system.h $(RTL_H) bitmap.h
 
 print-rtl.o : print-rtl.c $(CONFIG_H) system.h $(RTL_H)
 rtlanal.o : rtlanal.c $(CONFIG_H) system.h $(RTL_H)
@@ -1384,7 +1384,7 @@ xcoffout.o : xcoffout.c $(CONFIG_H) system.h $(TREE_H) $(RTL_H) xcoffout.h \
    flags.h
 emit-rtl.o : emit-rtl.c $(CONFIG_H) system.h $(RTL_H) $(TREE_H) flags.h \
    except.h function.h regs.h insn-config.h insn-codes.h $(RECOG_H) real.h \
-   expr.h obstack.h hard-reg-set.h
+   expr.h obstack.h hard-reg-set.h bitmap.h
 real.o : real.c $(CONFIG_H) system.h $(TREE_H) toplev.h
 getpwd.o : getpwd.c $(CONFIG_H) system.h
 
@@ -1716,7 +1716,7 @@ gengenrtl.o : gengenrtl.c $(RTL_BASE_H) system.h
 # If we are not cross-building, gen* use the same .o's that cc1 will use,
 # and HOST_PREFIX_1 is `foobar', just to ensure these rules don't conflict
 # with the rules for rtl.o, alloca.o, etc.
-$(HOST_PREFIX_1)rtl.o: $(srcdir)/rtl.c $(CONFIG_H) $(RTL_H)
+$(HOST_PREFIX_1)rtl.o: $(srcdir)/rtl.c $(CONFIG_H) system.h $(RTL_H) bitmap.h
 	rm -f $(HOST_PREFIX)rtl.c
 	sed -e 's/config[.]h/hconfig.h/' $(srcdir)/rtl.c > $(HOST_PREFIX)rtl.c
 	$(HOST_CC) -c $(HOST_CFLAGS) $(HOST_CPPFLAGS) $(INCLUDES) $(HOST_PREFIX)rtl.c
@@ -1726,6 +1726,12 @@ $(HOST_PREFIX_1)print-rtl.o: $(srcdir)/print-rtl.c $(CONFIG_H) $(RTL_H)
 	sed -e 's/config[.]h/hconfig.h/' $(srcdir)/print-rtl.c > $(HOST_PREFIX)print-rtl.c
 	$(HOST_CC) -c $(HOST_CFLAGS) $(HOST_CPPFLAGS) $(INCLUDES) $(HOST_PREFIX)print-rtl.c
 
+$(HOST_PREFIX_1)bitmap.o: $(srcdir)/bitmap.c $(CONFIG_H) system.h $(RTL_H) \
+  flags.h $(BASIC_BLOCK_H) regs.h
+	rm -f $(HOST_PREFIX)bitmap.c
+	sed -e 's/config[.]h/hconfig.h/' $(srcdir)/bitmap.c > $(HOST_PREFIX)bitmap.c
+	$(HOST_CC) -c $(HOST_CFLAGS) $(HOST_CPPFLAGS) $(INCLUDES) $(HOST_PREFIX)bitmap.c
+
 $(HOST_PREFIX_1)rtlanal.o: $(srcdir)/rtlanal.c $(CONFIG_H) $(RTL_H)
 	rm -f $(HOST_PREFIX)rtlanal.c
 	sed -e 's/config[.]h/hconfig.h/' $(srcdir)/rtlanal.c > $(HOST_PREFIX)rtlanal.c
diff --git a/gcc/emit-rtl.c b/gcc/emit-rtl.c
index 0516927b161..854b9892e2b 100644
--- a/gcc/emit-rtl.c
+++ b/gcc/emit-rtl.c
@@ -53,6 +53,7 @@ Boston, MA 02111-1307, USA.  */
 #include "recog.h"
 #include "real.h"
 #include "obstack.h"
+#include "bitmap.h"
 
 /* Commonly used modes.  */
 
@@ -384,6 +385,14 @@ gen_rtx VPROTO((enum rtx_code code, enum machine_mode mode, ...))
 	      XVEC (rt_val, i) = va_arg (p, rtvec);
 	      break;
 
+	    case 'b':           /* A bitmap? */
+	      XBITMAP (rt_val, i) = va_arg (p, bitmap);
+	      break;
+
+	    case 't':           /* A tree? */
+	      XTREE (rt_val, i) = va_arg (p, tree);
+	      break;
+
 	    default:
 	      abort ();
 	    }
diff --git a/gcc/gengenrtl.c b/gcc/gengenrtl.c
index 419ed31d5f8..d9e55eb0164 100644
--- a/gcc/gengenrtl.c
+++ b/gcc/gengenrtl.c
@@ -73,6 +73,16 @@ type_from_format (c)
       return "rtx";
     case 'E':
       return "rtvec";
+    /* ?!? These should be bitmap and tree respectively, but those types
+       are not available in many of the files which include the output
+       of gengenrtl.
+
+       These are only used in prototypes, so I think we can assume that
+       void * is useable.  */
+    case 'b':
+      return "void *";
+    case 't':
+      return "void *";
     default:
       abort ();
     }
@@ -95,6 +105,10 @@ accessor_from_format (c)
       return "XEXP";
     case 'E':
       return "XVEC";
+    case 'b':
+      return "XBITMAP";
+    case 't':
+      return "XTREE";
     default:
       abort ();
     }
diff --git a/gcc/haifa-sched.c b/gcc/haifa-sched.c
index 1e2bc53d9e7..d10a743f46a 100644
--- a/gcc/haifa-sched.c
+++ b/gcc/haifa-sched.c
@@ -3899,6 +3899,8 @@ sched_analyze (head, tail)
 		   || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
 		   || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
 		   || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END
+		   || NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_START
+		   || NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_END
 		   || (NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP
 		       && GET_CODE (PREV_INSN (insn)) != CALL_INSN)))
 	{
@@ -4656,6 +4658,8 @@ unlink_other_notes (insn, tail)
       if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_SETJMP
 	  && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG
 	  && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_END
+	  && NOTE_LINE_NUMBER (insn) != NOTE_INSN_RANGE_START
+	  && NOTE_LINE_NUMBER (insn) != NOTE_INSN_RANGE_END
 	  && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
 	  && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END)
 	{
diff --git a/gcc/print-rtl.c b/gcc/print-rtl.c
index 2bdc6122c8d..ba239d19d00 100644
--- a/gcc/print-rtl.c
+++ b/gcc/print-rtl.c
@@ -110,12 +110,37 @@ print_rtx (in_rtx)
       case 's':
 	if (i == 3 && GET_CODE (in_rtx) == NOTE
 	    && (NOTE_LINE_NUMBER (in_rtx) == NOTE_INSN_EH_REGION_BEG
-		|| NOTE_LINE_NUMBER (in_rtx) == NOTE_INSN_EH_REGION_END))
+		|| NOTE_LINE_NUMBER (in_rtx) == NOTE_INSN_EH_REGION_END
+		|| NOTE_LINE_NUMBER (in_rtx) == NOTE_INSN_BLOCK_BEG
+		|| NOTE_LINE_NUMBER (in_rtx) == NOTE_INSN_BLOCK_END))
 	  {
 	    fprintf (outfile, " %d", NOTE_BLOCK_NUMBER (in_rtx));
 	    sawclose = 1;
 	    break;
 	  }
+
+	if (i == 3 && GET_CODE (in_rtx) == NOTE
+	    && (NOTE_LINE_NUMBER (in_rtx) == NOTE_INSN_RANGE_START
+		|| NOTE_LINE_NUMBER (in_rtx) == NOTE_INSN_RANGE_END))
+	  {
+	    indent += 2;
+	    if (!sawclose)
+	      fprintf (outfile, " ");
+	    print_rtx (NOTE_RANGE_INFO (in_rtx));
+	    indent -= 2;
+	    break;
+	  }
+
+	if (i == 3 && GET_CODE (in_rtx) == NOTE
+	    && NOTE_LINE_NUMBER (in_rtx) == NOTE_INSN_LIVE)
+	  {
+	    if (XBITMAP (in_rtx, i) == NULL)
+	      fprintf (outfile, " {null}");
+	    else
+	      bitmap_print (outfile, XBITMAP (in_rtx, i), " {", "}");
+	    sawclose = 0;
+	  }
+
 	if (XSTR (in_rtx, i) == 0)
 	  fprintf (outfile, " \"\"");
 	else
@@ -207,6 +232,20 @@ print_rtx (in_rtx)
 	sawclose = 0;
 	break;
 
+      case 'b':
+	if (XBITMAP (in_rtx, i) == NULL)
+	  fprintf (outfile, " {null}");
+	else
+	  bitmap_print (outfile, XBITMAP (in_rtx, i), " {", "}");
+	sawclose = 0;
+	break;
+
+      case 't':
+	putc (' ', outfile);
+	fprintf (outfile, HOST_WIDE_INT_PRINT_HEX,
+		 (HOST_WIDE_INT) XTREE (in_rtx, i));
+	break;
+
       case '*':
 	fprintf (outfile, " Unknown");
 	sawclose = 0;
diff --git a/gcc/rtl.c b/gcc/rtl.c
index 712a9c5cc53..396566d36a7 100644
--- a/gcc/rtl.c
+++ b/gcc/rtl.c
@@ -23,6 +23,7 @@ Boston, MA 02111-1307, USA.  */
 #include "system.h"
 #include "rtl.h"
 #include "real.h"
+#include "bitmap.h"
 
 #include "obstack.h"
 #define	obstack_chunk_alloc	xmalloc
@@ -143,7 +144,9 @@ char *rtx_format[] = {
      "V" like "E", but optional:
 	 the containing rtx may end before this operand
      "u" a pointer to another insn
-         prints the uid of the insn.  */
+         prints the uid of the insn.
+     "b" is a pointer to a bitmap header.
+     "t" is a tree pointer. */
 
 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)   FORMAT ,
 #include "rtl.def"		/* rtl expressions are defined here */
@@ -169,7 +172,8 @@ char *note_insn_name[] = { 0                    , "NOTE_INSN_DELETED",
 			   "NOTE_INSN_PROLOGUE_END", "NOTE_INSN_EPILOGUE_BEG",
 			   "NOTE_INSN_DELETED_LABEL", "NOTE_INSN_FUNCTION_BEG",
 			   "NOTE_INSN_EH_REGION_BEG", "NOTE_INSN_EH_REGION_END",
-			   "NOTE_REPEATED_LINE_NUMBER" };
+			   "NOTE_REPEATED_LINE_NUMBER", "NOTE_INSN_RANGE_START",
+			   "NOTE_INSN_RANGE_END", "NOTE_INSN_LIVE" };
 
 char *reg_note_name[] = { "", "REG_DEAD", "REG_INC", "REG_EQUIV", "REG_WAS_0",
 			  "REG_EQUAL", "REG_RETVAL", "REG_LIBCALL",
@@ -338,6 +342,18 @@ copy_rtx (orig)
 	    }
 	  break;
 
+	case 'b':
+	  {
+	    bitmap new_bits = BITMAP_OBSTACK_ALLOC (rtl_obstack);
+	    bitmap_copy (new_bits, XBITMAP (orig, i));
+	    XBITMAP (copy, i) = new_bits;
+	    break;
+	  }
+
+	case 't':
+	  XTREE (copy, i) = XTREE (orig, i);
+	  break;
+
 	case 'w':
 	  XWINT (copy, i) = XWINT (orig, i);
 	  break;
diff --git a/gcc/rtl.def b/gcc/rtl.def
index 8eef0bab122..6d02c61e29e 100644
--- a/gcc/rtl.def
+++ b/gcc/rtl.def
@@ -796,6 +796,44 @@ DEF_RTL_EXPR(HIGH, "high", "e", 'o')
    of a constant expression.  */
 DEF_RTL_EXPR(LO_SUM, "lo_sum", "ee", 'o')
 
+/* Header for range information.  Operand 0 is the NOTE_INSN_RANGE_START insn.
+   Operand 1 is the NOTE_INSN_RANGE_END insn.  Operand 2 is a vector of all of
+   the registers that can be substituted within this range.  Operand 3 is the
+   number of calls in the range.  Operand 4 is the number of insns in the
+   range.  Operand 5 is the unique range number for this range.  Operand 6 is
+   the basic block # of the start of the live range.  Operand 7 is the basic
+   block # of the end of the live range.  Operand 8 is the loop depth.  Operand
+   9 is a bitmap of the registers live at the start of the range.  Operand 10
+   is a bitmap of the registers live at the end of the range.  Operand 11 is
+   marker number for the start of the range.  Operand 12 is the marker number
+   for the end of the range.  */
+DEF_RTL_EXPR(RANGE_INFO, "range_info", "uuEiiiiiibbii", 'x')
+
+/* Registers that can be substituted within the range.  Operand 0 is the
+   original pseudo register number.  Operand 1 will be filled in with the
+   pseudo register the value is copied for the duration of the range.  Operand
+   2 is the number of references within the range to the register.  Operand 3
+   is the number of sets or clobbers of the register in the range.  Operand 4
+   is the number of deaths the register has.  Operand 5 is the copy flags that
+   give the status of whether a copy is needed from the original register to
+   the new register at the beginning of the range, or whether a copy from the
+   new register back to the original at the end of the range.  Operand 6 is the
+   live length.  Operand 7 is the number of calls that this register is live
+   across.  Operand 8 is the symbol node of the variable if the register is a
+   user variable.  Operand 9 is the block node that the variable is declared
+   in if the register is a user variable. */
+DEF_RTL_EXPR(RANGE_REG, "range_reg", "iiiiiiiitt", 'x')
+
+/* Information about a local variable's ranges.  Operand 0 is an EXPR_LIST of
+   the different ranges a variable is in where it is copied to a different
+   pseudo register.  Operand 1 is the block that the variable is declared in.
+   Operand 2 is the number of distinct ranges.  */
+DEF_RTL_EXPR(RANGE_VAR, "range_var", "eti", 'x')
+
+/* Information about the registers that are live at the current point.  Operand
+   0 is the live bitmap.  Operand 1 is the original block number.  */
+DEF_RTL_EXPR(RANGE_LIVE, "range_live", "bi", 'x')
+
 /*
 Local variables:
 mode:c
diff --git a/gcc/rtl.h b/gcc/rtl.h
index 0d8b9b46891..597b79f07b6 100644
--- a/gcc/rtl.h
+++ b/gcc/rtl.h
@@ -89,6 +89,8 @@ typedef union rtunion_def
   struct rtvec_def *rtvec;
   enum machine_mode rttype;
   addr_diff_vec_flags rt_addr_diff_vec_flags;
+  struct bitmap_head_def *rtbit;
+  union tree_node *rttree;
 } rtunion;
 
 /* RTL expression ("rtx").  */
@@ -228,6 +230,9 @@ typedef struct rtvec_def{
 #define XVEC(RTX, N)	((RTX)->fld[N].rtvec)
 #define XVECLEN(RTX, N)	((RTX)->fld[N].rtvec->num_elem)
 #define XVECEXP(RTX,N,M)((RTX)->fld[N].rtvec->elem[M].rtx)
+#define XBITMAP(RTX, N) ((RTX)->fld[N].rtbit)
+#define XTREE(RTX, N)   ((RTX)->fld[N].rttree)
+
 
 /* ACCESS MACROS for particular fields of insns.  */
 
@@ -375,14 +380,21 @@ extern char *reg_note_name[];
 
 #define LINE_NUMBER NOTE
 
-/* In a NOTE that is a line number, this is a string for the file name
-   that the line is in.  We use the same field to record block numbers
-   temporarily in NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes.
-   (We avoid lots of casts between ints and pointers if we use a
-   different macro for the bock number.)  */
+/* In a NOTE that is a line number, this is a string for the file name that the
+   line is in.  We use the same field to record block numbers temporarily in
+   NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes.  (We avoid lots of casts
+   between ints and pointers if we use a different macro for the block number.)
+   The NOTE_INSN_RANGE_{START,END} and NOTE_INSN_LIVE notes record their
+   information as a rtx in the field.  */
 
 #define NOTE_SOURCE_FILE(INSN)  ((INSN)->fld[3].rtstr)
 #define NOTE_BLOCK_NUMBER(INSN) ((INSN)->fld[3].rtint)
+#define NOTE_RANGE_INFO(INSN)   ((INSN)->fld[3].rtx)
+#define NOTE_LIVE_INFO(INSN)    ((INSN)->fld[3].rtx)
+
+/* If the NOTE_BLOCK_NUMBER field gets a -1, it means create a new
+   block node for a live range block.  */
+#define NOTE_BLOCK_LIVE_RANGE_BLOCK -1
 
 /* In a NOTE that is a line number, this is the line number.
    Other kinds of NOTEs are identified by negative numbers here.  */
@@ -438,6 +450,12 @@ extern char *reg_note_name[];
    the line containing the inline call from being counted twice in gcov. */
 #define NOTE_REPEATED_LINE_NUMBER -16
 
+/* Start/end of a live range region, where pseudos allocated on the stack can
+   be allocated to temporary registers.  */
+#define NOTE_INSN_RANGE_START -17
+#define NOTE_INSN_RANGE_END -18
+/* Record which registers are currently live.  */
+#define NOTE_INSN_LIVE -19
 
 #if 0 /* These are not used, and I don't know what they were for. --rms.  */
 #define NOTE_DECL_NAME(INSN) ((INSN)->fld[3].rtstr)
@@ -666,6 +684,99 @@ extern char *note_insn_name[];
 #if (defined (HAVE_PRE_INCREMENT) || defined (HAVE_PRE_DECREMENT) || defined (HAVE_POST_INCREMENT) || defined (HAVE_POST_DECREMENT))
 #define AUTO_INC_DEC
 #endif
+
+/* Accessors for RANGE_INFO.  */
+/* For RANGE_{START,END} notes return the RANGE_START note.  */
+#define RANGE_INFO_NOTE_START(INSN) (XEXP (INSN, 0))
+
+/* For RANGE_{START,END} notes return the RANGE_START note.  */
+#define RANGE_INFO_NOTE_END(INSN) (XEXP (INSN, 1))
+
+/* For RANGE_{START,END} notes, return the vector containing the registers used
+   in the range.  */
+#define RANGE_INFO_REGS(INSN) (XVEC (INSN, 2))
+#define RANGE_INFO_REGS_REG(INSN, N) (XVECEXP (INSN, 2, N))
+#define RANGE_INFO_NUM_REGS(INSN) (XVECLEN (INSN, 2))
+
+/* For RANGE_{START,END} notes, the number of calls within the range.  */
+#define RANGE_INFO_NCALLS(INSN) (XINT (INSN, 3))
+
+/* For RANGE_{START,END} notes, the number of insns within the range.  */
+#define RANGE_INFO_NINSNS(INSN) (XINT (INSN, 4))
+
+/* For RANGE_{START,END} notes, a unique # to identify this range.  */
+#define RANGE_INFO_UNIQUE(INSN) (XINT (INSN, 5))
+
+/* For RANGE_{START,END} notes, the basic block # the range starts with. */
+#define RANGE_INFO_BB_START(INSN) (XINT (INSN, 6))
+
+/* For RANGE_{START,END} notes, the basic block # the range ends with. */
+#define RANGE_INFO_BB_END(INSN) (XINT (INSN, 7))
+
+/* For RANGE_{START,END} notes, the loop depth the range is in.  */
+#define RANGE_INFO_LOOP_DEPTH(INSN) (XINT (INSN, 8))
+
+/* For RANGE_{START,END} notes, the bitmap of live registers at the start
+   of the range.  */
+#define RANGE_INFO_LIVE_START(INSN) (XBITMAP (INSN, 9))
+
+/* For RANGE_{START,END} notes, the bitmap of live registers at the end
+   of the range.  */
+#define RANGE_INFO_LIVE_END(INSN) (XBITMAP (INSN, 10))
+
+/* For RANGE_START notes, the marker # of the start of the range.  */
+#define RANGE_INFO_MARKER_START(INSN) (XINT (INSN, 11))
+
+/* For RANGE_START notes, the marker # of the end of the range.  */
+#define RANGE_INFO_MARKER_END(INSN) (XINT (INSN, 12))
+
+/* Original pseudo register # for a live range note.  */
+#define RANGE_REG_PSEUDO(INSN,N) (XINT (XVECEXP (INSN, 2, N), 0))
+
+/* Pseudo register # original register is copied into or -1.  */
+#define RANGE_REG_COPY(INSN,N) (XINT (XVECEXP (INSN, 2, N), 1))
+
+/* How many times a register in a live range note was referenced.  */
+#define RANGE_REG_REFS(INSN,N) (XINT (XVECEXP (INSN, 2, N), 2))
+
+/* How many times a register in a live range note was set.  */
+#define RANGE_REG_SETS(INSN,N) (XINT (XVECEXP (INSN, 2, N), 3))
+
+/* How many times a register in a live range note died.  */
+#define RANGE_REG_DEATHS(INSN,N) (XINT (XVECEXP (INSN, 2, N), 4))
+
+/* Whether the original value is needed to be copied into the range register at
+   the start of the range. */
+#define RANGE_REG_COPY_FLAGS(INSN,N) (XINT (XVECEXP (INSN, 2, N), 5))
+
+/* # of insns the register copy is live over.  */
+#define RANGE_REG_LIVE_LENGTH(INSN,N) (XINT (XVECEXP (INSN, 2, N), 6))
+
+/* # of calls the register copy is live over.  */
+#define RANGE_REG_N_CALLS(INSN,N) (XINT (XVECEXP (INSN, 2, N), 7))
+
+/* DECL_NODE pointer of the declaration if the register is a user defined
+   variable.  */
+#define RANGE_REG_SYMBOL_NODE(INSN,N) (XTREE (XVECEXP (INSN, 2, N), 8))
+
+/* BLOCK_NODE pointer to the block the variable is declared in if the
+   register is a user defined variable.  */
+#define RANGE_REG_BLOCK_NODE(INSN,N) (XTREE (XVECEXP (INSN, 2, N), 9))
+
+/* EXPR_LIST of the distinct ranges a variable is in.  */
+#define RANGE_VAR_LIST(INSN) (XEXP (INSN, 0))
+
+/* Block a variable is declared in.  */
+#define RANGE_VAR_BLOCK(INSN) (XTREE (INSN, 1))
+
+/* # of distinct ranges a variable is in.  */
+#define RANGE_VAR_NUM(INSN) (XINT (INSN, 2))
+
+/* For a NOTE_INSN_LIVE note, the registers which are currently live.  */
+#define RANGE_LIVE_BITMAP(INSN) (XBITMAP (INSN, 0))
+
+/* For a NOTE_INSN_LIVE note, the original basic block number.  */
+#define RANGE_LIVE_ORIG_BLOCK(INSN) (XINT (INSN, 1))
 
 /* Generally useful functions.  */
 
diff --git a/gcc/sched.c b/gcc/sched.c
index a51d1281ed9..2cd9d12911c 100644
--- a/gcc/sched.c
+++ b/gcc/sched.c
@@ -1737,6 +1737,8 @@ sched_analyze (head, tail)
 		   || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
 		   || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
 		   || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END
+		   || NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_START
+		   || NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_END
 		   || (NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP
 		       && GET_CODE (PREV_INSN (insn)) != CALL_INSN)))
 	{
@@ -2516,6 +2518,8 @@ unlink_notes (insn, tail)
       else if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_SETJMP
 	       && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG
 	       && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_END
+	       && NOTE_LINE_NUMBER (insn) != NOTE_INSN_RANGE_START
+	       && NOTE_LINE_NUMBER (insn) != NOTE_INSN_RANGE_END
 	       && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
 	       && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END)
 	{
diff --git a/gcc/tree.h b/gcc/tree.h
index 15b9a8af02e..7b7e4cf8215 100644
--- a/gcc/tree.h
+++ b/gcc/tree.h
@@ -671,6 +671,18 @@ struct tree_exp
 #define BLOCK_ABSTRACT_ORIGIN(NODE) ((NODE)->block.abstract_origin)
 #define BLOCK_ABSTRACT(NODE) ((NODE)->block.abstract_flag)
 #define BLOCK_END_NOTE(NODE) ((NODE)->block.end_note)
+/* Nonzero means that this block has separate live range regions */
+#define BLOCK_LIVE_RANGE_FLAG(NOTE) ((NOTE)->block.live_range_flag)
+
+/* Nonzero means that this block has a variable declared in it
+   that is split into separate live ranges.  */
+#define BLOCK_LIVE_RANGE_VAR_FLAG(NOTE) ((NOTE)->block.live_range_var_flag)
+
+/* Index for marking the start of the block for live ranges.  */
+#define BLOCK_LIVE_RANGE_START(NOTE) ((NOTE)->block.live_range_start)
+
+/* Index for marking the end of the block for live ranges.  */
+#define BLOCK_LIVE_RANGE_END(NOTE) ((NOTE)->block.live_range_end)
 
 /* Nonzero means that this block is prepared to handle exceptions
    listed in the BLOCK_VARS slot.  */
@@ -682,6 +694,8 @@ struct tree_block
 
   unsigned handler_block_flag : 1;
   unsigned abstract_flag : 1;
+  unsigned live_range_flag : 1;
+  unsigned live_range_var_flag : 1;
 
   union tree_node *vars;
   union tree_node *type_tags;
@@ -689,6 +703,8 @@ struct tree_block
   union tree_node *supercontext;
   union tree_node *abstract_origin;
   struct rtx_def *end_note;
+  int live_range_start;
+  int live_range_end;
 };
 
 /* Define fields and accessors for nodes representing data types.  */
@@ -971,6 +987,9 @@ struct tree_type
    to the variable's data type, while the mode
    of DECL_RTL is the mode actually used to contain the data.  */
 #define DECL_RTL(NODE) ((NODE)->decl.rtl)
+/* Holds an INSN_LIST of all of the live ranges in which the variable
+   has been moved to a possibly different register.  */
+#define DECL_LIVE_RANGE_RTL(NODE) ((NODE)->decl.live_range_rtl)
 /* For PARM_DECL, holds an RTL for the stack slot or register
    where the data was actually passed.  */
 #define DECL_INCOMING_RTL(NODE) ((NODE)->decl.saved_insns.r)
@@ -1191,6 +1210,7 @@ struct tree_decl
   union tree_node *machine_attributes;
   struct rtx_def *rtl;	/* acts as link to register transfer language
 				   (rtl) info */
+  struct rtx_def *live_range_rtl;
   /* For FUNCTION_DECLs: points to insn that constitutes its definition
      on the permanent obstack.  For FIELD_DECL, this is DECL_FIELD_SIZE.  */
   union {