OSDN Git Service

* config/s390/s390.c (s390_emit_epilogue): Always restore registers
[pf3gnuchains/gcc-fork.git] / gcc / rtlanal.c
index 52ff6a9..3d90ae7 100644 (file)
@@ -1,35 +1,41 @@
 /* Analyze RTL for C-Compiler
-   Copyright (C) 1987, 88, 92-98, 1999 Free Software Foundation, Inc.
+   Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
+   1999, 2000, 2001, 2002 Free Software Foundation, Inc.
 
-This file is part of GNU CC.
+This file is part of GCC.
 
-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.
+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 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.
+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 GNU CC; see the file COPYING.  If not, write to
-the Free Software Foundation, 59 Temple Place - Suite 330,
-Boston, MA 02111-1307, USA.  */
+along with GCC; see the file COPYING.  If not, write to the Free
+Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA.  */
 
 
 #include "config.h"
 #include "system.h"
+#include "toplev.h"
 #include "rtl.h"
-
-static int rtx_addr_can_trap_p PROTO((rtx));
-static void reg_set_p_1                PROTO((rtx, rtx));
-static void reg_set_last_1     PROTO((rtx, rtx));
-
+#include "hard-reg-set.h"
+#include "insn-config.h"
+#include "recog.h"
+#include "tm_p.h"
+#include "flags.h"
 
 /* Forward declarations */
-static int jmp_uses_reg_or_mem         PROTO((rtx));
+static int global_reg_mentioned_p_1 PARAMS ((rtx *, void *));
+static void set_of_1           PARAMS ((rtx, rtx, void *));
+static void insn_dependent_p_1 PARAMS ((rtx, rtx, void *));
+static int computed_jump_p_1   PARAMS ((rtx));
+static void parms_set          PARAMS ((rtx, rtx, void *));
 
 /* Bit flags that specify the machine subtype we are compiling for.
    Bits are tested using macros TARGET_... defined in the tm.h file
@@ -46,55 +52,99 @@ int
 rtx_unstable_p (x)
      rtx x;
 {
-  register RTX_CODE code = GET_CODE (x);
-  register int i;
-  register char *fmt;
+  RTX_CODE code = GET_CODE (x);
+  int i;
+  const char *fmt;
 
-  if (code == MEM)
-    return ! RTX_UNCHANGING_P (x);
+  switch (code)
+    {
+    case MEM:
+      return ! RTX_UNCHANGING_P (x) || rtx_unstable_p (XEXP (x, 0));
 
-  if (code == QUEUED)
-    return 1;
+    case QUEUED:
+      return 1;
 
-  if (code == CONST || code == CONST_INT)
-    return 0;
+    case ADDRESSOF:
+    case CONST:
+    case CONST_INT:
+    case CONST_DOUBLE:
+    case CONST_VECTOR:
+    case SYMBOL_REF:
+    case LABEL_REF:
+      return 0;
+
+    case REG:
+      /* As in rtx_varies_p, we have to use the actual rtx, not reg number.  */
+      if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
+         /* The arg pointer varies if it is not a fixed register.  */
+         || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM])
+         || RTX_UNCHANGING_P (x))
+       return 0;
+#ifndef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
+      /* ??? When call-clobbered, the value is stable modulo the restore
+        that must happen after a call.  This currently screws up local-alloc
+        into believing that the restore is not needed.  */
+      if (x == pic_offset_table_rtx)
+       return 0;
+#endif
+      return 1;
 
-  if (code == REG)
-    return ! (REGNO (x) == FRAME_POINTER_REGNUM
-             || REGNO (x) == HARD_FRAME_POINTER_REGNUM
-             || REGNO (x) == ARG_POINTER_REGNUM
-             || RTX_UNCHANGING_P (x));
+    case ASM_OPERANDS:
+      if (MEM_VOLATILE_P (x))
+       return 1;
+
+      /* FALLTHROUGH */
+
+    default:
+      break;
+    }
 
   fmt = GET_RTX_FORMAT (code);
   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
     if (fmt[i] == 'e')
-      if (rtx_unstable_p (XEXP (x, i)))
-       return 1;
+      {
+       if (rtx_unstable_p (XEXP (x, i)))
+         return 1;
+      }
+    else if (fmt[i] == 'E')
+      {
+       int j;
+       for (j = 0; j < XVECLEN (x, i); j++)
+         if (rtx_unstable_p (XVECEXP (x, i, j)))
+           return 1;
+      }
+
   return 0;
 }
 
 /* Return 1 if X has a value that can vary even between two
    executions of the program.  0 means X can be compared reliably
    against certain constants or near-constants.
+   FOR_ALIAS is nonzero if we are called from alias analysis; if it is
+   zero, we are slightly more conservative.
    The frame pointer and the arg pointer are considered constant.  */
 
 int
-rtx_varies_p (x)
+rtx_varies_p (x, for_alias)
      rtx x;
+     int for_alias;
 {
-  register RTX_CODE code = GET_CODE (x);
-  register int i;
-  register char *fmt;
+  RTX_CODE code = GET_CODE (x);
+  int i;
+  const char *fmt;
 
   switch (code)
     {
     case MEM:
+      return ! RTX_UNCHANGING_P (x) || rtx_varies_p (XEXP (x, 0), for_alias);
+
     case QUEUED:
       return 1;
 
     case CONST:
     case CONST_INT:
     case CONST_DOUBLE:
+    case CONST_VECTOR:
     case SYMBOL_REF:
     case LABEL_REF:
       return 0;
@@ -104,14 +154,35 @@ rtx_varies_p (x)
         and arg pointers and not just the register number in case we have
         eliminated the frame and/or arg pointer and are using it
         for pseudos.  */
-      return ! (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
-               || x == arg_pointer_rtx || x == pic_offset_table_rtx);
+      if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
+         /* The arg pointer varies if it is not a fixed register.  */
+         || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM]))
+       return 0;
+      if (x == pic_offset_table_rtx
+#ifdef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
+         /* ??? When call-clobbered, the value is stable modulo the restore
+            that must happen after a call.  This currently screws up
+            local-alloc into believing that the restore is not needed, so we
+            must return 0 only if we are called from alias analysis.  */
+         && for_alias
+#endif
+         )
+       return 0;
+      return 1;
 
     case LO_SUM:
       /* The operand 0 of a LO_SUM is considered constant
-        (in fact is it related specifically to operand 1).  */
-      return rtx_varies_p (XEXP (x, 1));
+        (in fact it is related specifically to operand 1)
+        during alias analysis.  */
+      return (! for_alias && rtx_varies_p (XEXP (x, 0), for_alias))
+            || rtx_varies_p (XEXP (x, 1), for_alias);
       
+    case ASM_OPERANDS:
+      if (MEM_VOLATILE_P (x))
+       return 1;
+
+      /* FALLTHROUGH */
+
     default:
       break;
     }
@@ -119,46 +190,73 @@ rtx_varies_p (x)
   fmt = GET_RTX_FORMAT (code);
   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
     if (fmt[i] == 'e')
-      if (rtx_varies_p (XEXP (x, i)))
-       return 1;
+      {
+       if (rtx_varies_p (XEXP (x, i), for_alias))
+         return 1;
+      }
+    else if (fmt[i] == 'E')
+      {
+       int j;
+       for (j = 0; j < XVECLEN (x, i); j++)
+         if (rtx_varies_p (XVECEXP (x, i, j), for_alias))
+           return 1;
+      }
+
   return 0;
 }
 
 /* Return 0 if the use of X as an address in a MEM can cause a trap.  */
 
-static int
+int
 rtx_addr_can_trap_p (x)
-     register rtx x;
+     rtx x;
 {
-  register enum rtx_code code = GET_CODE (x);
+  enum rtx_code code = GET_CODE (x);
 
   switch (code)
     {
     case SYMBOL_REF:
+      return SYMBOL_REF_WEAK (x);
+
     case LABEL_REF:
-      /* SYMBOL_REF is problematic due to the possible presence of
-        a #pragma weak, but to say that loads from symbols can trap is
-        *very* costly.  It's not at all clear what's best here.  For
-        now, we ignore the impact of #pragma weak.  */
       return 0;
 
     case REG:
       /* As in rtx_varies_p, we have to use the actual rtx, not reg number.  */
-      return ! (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
-               || x == stack_pointer_rtx || x == arg_pointer_rtx);
+      if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
+         || x == stack_pointer_rtx
+         /* The arg pointer varies if it is not a fixed register.  */
+         || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM]))
+       return 0;
+      /* All of the virtual frame registers are stack references.  */
+      if (REGNO (x) >= FIRST_VIRTUAL_REGISTER
+         && REGNO (x) <= LAST_VIRTUAL_REGISTER)
+       return 0;
+      return 1;
 
     case CONST:
       return rtx_addr_can_trap_p (XEXP (x, 0));
 
     case PLUS:
       /* An address is assumed not to trap if it is an address that can't
-        trap plus a constant integer.  */
-      return (rtx_addr_can_trap_p (XEXP (x, 0))
-             || GET_CODE (XEXP (x, 1)) != CONST_INT);
+        trap plus a constant integer or it is the pic register plus a
+        constant.  */
+      return ! ((! rtx_addr_can_trap_p (XEXP (x, 0))
+                && GET_CODE (XEXP (x, 1)) == CONST_INT)
+               || (XEXP (x, 0) == pic_offset_table_rtx
+                   && CONSTANT_P (XEXP (x, 1))));
 
     case LO_SUM:
+    case PRE_MODIFY:
       return rtx_addr_can_trap_p (XEXP (x, 1));
-      
+
+    case PRE_DEC:
+    case PRE_INC:
+    case POST_DEC:
+    case POST_INC:
+    case POST_MODIFY:
+      return rtx_addr_can_trap_p (XEXP (x, 0));
+
     default:
       break;
     }
@@ -169,35 +267,38 @@ rtx_addr_can_trap_p (x)
 
 /* Return 1 if X refers to a memory location whose address 
    cannot be compared reliably with constant addresses,
-   or if X refers to a BLKmode memory object.  */
+   or if X refers to a BLKmode memory object. 
+   FOR_ALIAS is nonzero if we are called from alias analysis; if it is
+   zero, we are slightly more conservative.  */
 
 int
-rtx_addr_varies_p (x)
+rtx_addr_varies_p (x, for_alias)
      rtx x;
+     int for_alias;
 {
-  register enum rtx_code code;
-  register int i;
-  register char *fmt;
+  enum rtx_code code;
+  int i;
+  const char *fmt;
 
   if (x == 0)
     return 0;
 
   code = GET_CODE (x);
   if (code == MEM)
-    return GET_MODE (x) == BLKmode || rtx_varies_p (XEXP (x, 0));
+    return GET_MODE (x) == BLKmode || rtx_varies_p (XEXP (x, 0), for_alias);
 
   fmt = GET_RTX_FORMAT (code);
   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
     if (fmt[i] == 'e')
       {
-       if (rtx_addr_varies_p (XEXP (x, i)))
+       if (rtx_addr_varies_p (XEXP (x, i), for_alias))
          return 1;
       }
     else if (fmt[i] == 'E')
       {
        int j;
        for (j = 0; j < XVECLEN (x, i); j++)
-         if (rtx_addr_varies_p (XVECEXP (x, i, j)))
+         if (rtx_addr_varies_p (XVECEXP (x, i, j), for_alias))
            return 1;
       }
   return 0;
@@ -206,7 +307,7 @@ rtx_addr_varies_p (x)
 /* Return the value of the integer term in X, if one is apparent;
    otherwise return 0.
    Only obvious integer terms are detected.
-   This is used in cse.c with the `related_value' field.*/
+   This is used in cse.c with the `related_value' field.  */
 
 HOST_WIDE_INT
 get_integer_term (x)
@@ -244,17 +345,297 @@ get_related_value (x)
   return 0;
 }
 \f
+/* Given a tablejump insn INSN, return the RTL expression for the offset
+   into the jump table.  If the offset cannot be determined, then return
+   NULL_RTX.
+
+   If EARLIEST is non-zero, it is a pointer to a place where the earliest
+   insn used in locating the offset was found.  */
+
+rtx
+get_jump_table_offset (insn, earliest)
+     rtx insn;
+     rtx *earliest;
+{
+  rtx label;
+  rtx table;
+  rtx set;
+  rtx old_insn;
+  rtx x;
+  rtx old_x;
+  rtx y;
+  rtx old_y;
+  int i;
+
+  if (GET_CODE (insn) != JUMP_INSN
+      || ! (label = JUMP_LABEL (insn))
+      || ! (table = NEXT_INSN (label))
+      || GET_CODE (table) != JUMP_INSN
+      || (GET_CODE (PATTERN (table)) != ADDR_VEC
+         && GET_CODE (PATTERN (table)) != ADDR_DIFF_VEC)
+      || ! (set = single_set (insn)))
+    return NULL_RTX;
+
+  x = SET_SRC (set);
+
+  /* Some targets (eg, ARM) emit a tablejump that also
+     contains the out-of-range target.  */
+  if (GET_CODE (x) == IF_THEN_ELSE
+      && GET_CODE (XEXP (x, 2)) == LABEL_REF)
+    x = XEXP (x, 1);
+
+  /* Search backwards and locate the expression stored in X.  */
+  for (old_x = NULL_RTX; GET_CODE (x) == REG && x != old_x;
+       old_x = x, x = find_last_value (x, &insn, NULL_RTX, 0))
+    ;
+
+  /* If X is an expression using a relative address then strip
+     off the addition / subtraction of PC, PIC_OFFSET_TABLE_REGNUM,
+     or the jump table label.  */
+  if (GET_CODE (PATTERN (table)) == ADDR_DIFF_VEC
+      && (GET_CODE (x) == PLUS || GET_CODE (x) == MINUS))
+    {
+      for (i = 0; i < 2; i++)
+       {
+         old_insn = insn;
+         y = XEXP (x, i);
+
+         if (y == pc_rtx || y == pic_offset_table_rtx)
+           break;
+
+         for (old_y = NULL_RTX; GET_CODE (y) == REG && y != old_y;
+              old_y = y, y = find_last_value (y, &old_insn, NULL_RTX, 0))
+           ;
+
+         if ((GET_CODE (y) == LABEL_REF && XEXP (y, 0) == label))
+           break;
+       }
+
+      if (i >= 2)
+       return NULL_RTX;
+
+      x = XEXP (x, 1 - i);
+
+      for (old_x = NULL_RTX; GET_CODE (x) == REG && x != old_x;
+          old_x = x, x = find_last_value (x, &insn, NULL_RTX, 0))
+       ;
+    }
+
+  /* Strip off any sign or zero extension.  */
+  if (GET_CODE (x) == SIGN_EXTEND || GET_CODE (x) == ZERO_EXTEND)
+    {
+      x = XEXP (x, 0);
+
+      for (old_x = NULL_RTX; GET_CODE (x) == REG && x != old_x;
+          old_x = x, x = find_last_value (x, &insn, NULL_RTX, 0))
+       ;
+    }
+
+  /* If X isn't a MEM then this isn't a tablejump we understand.  */
+  if (GET_CODE (x) != MEM)
+    return NULL_RTX;
+
+  /* Strip off the MEM.  */
+  x = XEXP (x, 0);
+
+  for (old_x = NULL_RTX; GET_CODE (x) == REG && x != old_x;
+       old_x = x, x = find_last_value (x, &insn, NULL_RTX, 0))
+    ;
+
+  /* If X isn't a PLUS than this isn't a tablejump we understand.  */
+  if (GET_CODE (x) != PLUS)
+    return NULL_RTX;
+
+  /* At this point we should have an expression representing the jump table
+     plus an offset.  Examine each operand in order to determine which one
+     represents the jump table.  Knowing that tells us that the other operand
+     must represent the offset.  */
+  for (i = 0; i < 2; i++)
+    {
+      old_insn = insn;
+      y = XEXP (x, i);
+
+      for (old_y = NULL_RTX; GET_CODE (y) == REG && y != old_y;
+          old_y = y, y = find_last_value (y, &old_insn, NULL_RTX, 0))
+       ;
+
+      if ((GET_CODE (y) == CONST || GET_CODE (y) == LABEL_REF)
+         && reg_mentioned_p (label, y))
+       break;
+    }
+
+  if (i >= 2)
+    return NULL_RTX;
+
+  x = XEXP (x, 1 - i);
+
+  /* Strip off the addition / subtraction of PIC_OFFSET_TABLE_REGNUM.  */
+  if (GET_CODE (x) == PLUS || GET_CODE (x) == MINUS)
+    for (i = 0; i < 2; i++)
+      if (XEXP (x, i) == pic_offset_table_rtx)
+       {
+         x = XEXP (x, 1 - i);
+         break;
+       }
+
+  if (earliest)
+    *earliest = insn;
+
+  /* Return the RTL expression representing the offset.  */
+  return x;
+}
+\f
+/* A subroutine of global_reg_mentioned_p, returns 1 if *LOC mentions
+   a global register.  */
+
+static int
+global_reg_mentioned_p_1 (loc, data)
+     rtx *loc;
+     void *data ATTRIBUTE_UNUSED;
+{
+  int regno;
+  rtx x = *loc;
+
+  if (! x)
+    return 0;
+
+  switch (GET_CODE (x))
+    {
+    case SUBREG:
+      if (GET_CODE (SUBREG_REG (x)) == REG)
+       {
+         if (REGNO (SUBREG_REG (x)) < FIRST_PSEUDO_REGISTER
+             && global_regs[subreg_regno (x)])
+           return 1;
+         return 0;
+       }
+      break;
+
+    case REG:
+      regno = REGNO (x);
+      if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
+       return 1;
+      return 0;
+
+    case SCRATCH:
+    case PC:
+    case CC0:
+    case CONST_INT:
+    case CONST_DOUBLE:
+    case CONST:
+    case LABEL_REF:
+      return 0;
+
+    case CALL:
+      /* A non-constant call might use a global register.  */
+      return 1;
+
+    default:
+      break;
+    }
+
+  return 0;
+}
+
+/* Returns non-zero if X mentions a global register.  */
+
+int
+global_reg_mentioned_p (x)
+     rtx x;
+{
+
+  if (INSN_P (x))
+    {
+      if (GET_CODE (x) == CALL_INSN)
+       {
+         if (! CONST_OR_PURE_CALL_P (x))
+           return 1;
+         x = CALL_INSN_FUNCTION_USAGE (x);
+         if (x == 0)
+           return 0;
+        }
+      else
+        x = PATTERN (x);
+    }
+
+  return for_each_rtx (&x, global_reg_mentioned_p_1, NULL);
+}
+\f
+/* Return the number of places FIND appears within X.  If COUNT_DEST is
+   zero, we do not count occurrences inside the destination of a SET.  */
+
+int
+count_occurrences (x, find, count_dest)
+     rtx x, find;
+     int count_dest;
+{
+  int i, j;
+  enum rtx_code code;
+  const char *format_ptr;
+  int count;
+
+  if (x == find)
+    return 1;
+
+  code = GET_CODE (x);
+
+  switch (code)
+    {
+    case REG:
+    case CONST_INT:
+    case CONST_DOUBLE:
+    case CONST_VECTOR:
+    case SYMBOL_REF:
+    case CODE_LABEL:
+    case PC:
+    case CC0:
+      return 0;
+
+    case MEM:
+      if (GET_CODE (find) == MEM && rtx_equal_p (x, find))
+       return 1;
+      break;
+
+    case SET:
+      if (SET_DEST (x) == find && ! count_dest)
+       return count_occurrences (SET_SRC (x), find, count_dest);
+      break;
+
+    default:
+      break;
+    }
+
+  format_ptr = GET_RTX_FORMAT (code);
+  count = 0;
+
+  for (i = 0; i < GET_RTX_LENGTH (code); i++)
+    {
+      switch (*format_ptr++)
+       {
+       case 'e':
+         count += count_occurrences (XEXP (x, i), find, count_dest);
+         break;
+
+       case 'E':
+         for (j = 0; j < XVECLEN (x, i); j++)
+           count += count_occurrences (XVECEXP (x, i, j), find, count_dest);
+         break;
+       }
+    }
+  return count;
+}
+\f
 /* Nonzero if register REG appears somewhere within IN.
    Also works if REG is not a register; in this case it checks
    for a subexpression of IN that is Lisp "equal" to REG.  */
 
 int
 reg_mentioned_p (reg, in)
-     register rtx reg, in;
+     rtx reg, in;
 {
-  register char *fmt;
-  register int i;
-  register enum rtx_code code;
+  const char *fmt;
+  int i;
+  enum rtx_code code;
 
   if (in == 0)
     return 0;
@@ -282,7 +663,8 @@ reg_mentioned_p (reg, in)
 
     case CONST_INT:
       return GET_CODE (reg) == CONST_INT && INTVAL (in) == INTVAL (reg);
-      
+
+    case CONST_VECTOR:
     case CONST_DOUBLE:
       /* These are kept unique for a given value.  */
       return 0;
@@ -300,7 +682,7 @@ reg_mentioned_p (reg, in)
     {
       if (fmt[i] == 'E')
        {
-         register int j;
+         int j;
          for (j = XVECLEN (in, i) - 1; j >= 0; j--)
            if (reg_mentioned_p (reg, XVECEXP (in, i, j)))
              return 1;
@@ -319,7 +701,9 @@ int
 no_labels_between_p (beg, end)
      rtx beg, end;
 {
-  register rtx p;
+  rtx p;
+  if (beg == end)
+    return 0;
   for (p = NEXT_INSN (beg); p != end; p = NEXT_INSN (p))
     if (GET_CODE (p) == CODE_LABEL)
       return 0;
@@ -333,7 +717,7 @@ int
 no_jumps_between_p (beg, end)
      rtx beg, end;
 {
-  register rtx p;
+  rtx p;
   for (p = NEXT_INSN (beg); p != end; p = NEXT_INSN (p))
     if (GET_CODE (p) == JUMP_INSN)
       return 0;
@@ -347,13 +731,13 @@ int
 reg_used_between_p (reg, from_insn, to_insn)
      rtx reg, from_insn, to_insn;
 {
-  register rtx insn;
+  rtx insn;
 
   if (from_insn == to_insn)
     return 0;
 
   for (insn = NEXT_INSN (from_insn); insn != to_insn; insn = NEXT_INSN (insn))
-    if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
+    if (INSN_P (insn)
        && (reg_overlap_mentioned_p (reg, PATTERN (insn))
           || (GET_CODE (insn) == CALL_INSN
              && (find_reg_fusage (insn, USE, reg)
@@ -403,11 +787,15 @@ reg_referenced_p (x, body)
 
     case CALL:
     case USE:
+    case IF_THEN_ELSE:
       return reg_overlap_mentioned_p (x, body);
 
     case TRAP_IF:
       return reg_overlap_mentioned_p (x, TRAP_CONDITION (body));
 
+    case PREFETCH:
+      return reg_overlap_mentioned_p (x, XEXP (body, 0));
+
     case UNSPEC:
     case UNSPEC_VOLATILE:
       for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
@@ -421,6 +809,17 @@ reg_referenced_p (x, body)
          return 1;
       return 0;
       
+    case CLOBBER:
+      if (GET_CODE (XEXP (body, 0)) == MEM)
+       if (reg_overlap_mentioned_p (x, XEXP (XEXP (body, 0), 0)))
+         return 1;
+      return 0;
+
+    case COND_EXEC:
+      if (reg_overlap_mentioned_p (x, COND_EXEC_TEST (body)))
+       return 1;
+      return reg_referenced_p (x, COND_EXEC_CODE (body));
+
     default:
       return 0;
     }
@@ -434,13 +833,13 @@ int
 reg_referenced_between_p (reg, from_insn, to_insn)
      rtx reg, from_insn, to_insn;
 {
-  register rtx insn;
+  rtx insn;
 
   if (from_insn == to_insn)
     return 0;
 
   for (insn = NEXT_INSN (from_insn); insn != to_insn; insn = NEXT_INSN (insn))
-    if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
+    if (INSN_P (insn)
        && (reg_referenced_p (reg, PATTERN (insn))
           || (GET_CODE (insn) == CALL_INSN
              && find_reg_fusage (insn, USE, reg))))
@@ -455,36 +854,18 @@ int
 reg_set_between_p (reg, from_insn, to_insn)
      rtx reg, from_insn, to_insn;
 {
-  register rtx insn;
+  rtx insn;
 
   if (from_insn == to_insn)
     return 0;
 
   for (insn = NEXT_INSN (from_insn); insn != to_insn; insn = NEXT_INSN (insn))
-    if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
-       && reg_set_p (reg, insn))
+    if (INSN_P (insn) && reg_set_p (reg, insn))
       return 1;
   return 0;
 }
 
 /* Internals of reg_set_between_p.  */
-
-static rtx reg_set_reg;
-static int reg_set_flag;
-
-static void
-reg_set_p_1 (x, pat)
-     rtx x;
-     rtx pat ATTRIBUTE_UNUSED;
-{
-  /* We don't want to return 1 if X is a MEM that contains a register
-     within REG_SET_REG.  */
-
-  if ((GET_CODE (x) != MEM)
-      && reg_overlap_mentioned_p (reg_set_reg, x))
-    reg_set_flag = 1;
-}
-
 int
 reg_set_p (reg, insn)
      rtx reg, insn;
@@ -493,7 +874,7 @@ reg_set_p (reg, insn)
 
   /* We can be passed an insn or part of one.  If we are passed an insn,
      check if a side-effect of the insn clobbers REG.  */
-  if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
+  if (INSN_P (insn))
     {
       if (FIND_REG_INC_NOTE (insn, reg)
          || (GET_CODE (insn) == CALL_INSN
@@ -512,10 +893,7 @@ reg_set_p (reg, insn)
       body = PATTERN (insn);
     }
 
-  reg_set_reg = reg;
-  reg_set_flag = 0;
-  note_stores (body, reg_set_p_1);
-  return reg_set_flag;
+  return set_of (reg, insn) != NULL_RTX;
 }
 
 /* Similar to reg_set_between_p, but check all registers in X.  Return 0
@@ -528,13 +906,14 @@ regs_set_between_p (x, start, end)
      rtx start, end;
 {
   enum rtx_code code = GET_CODE (x);
-  char *fmt;
+  const char *fmt;
   int i, j;
 
   switch (code)
     {
     case CONST_INT:
     case CONST_DOUBLE:
+    case CONST_VECTOR:
     case CONST:
     case SYMBOL_REF:
     case LABEL_REF:
@@ -574,13 +953,14 @@ modified_between_p (x, start, end)
      rtx start, end;
 {
   enum rtx_code code = GET_CODE (x);
-  char *fmt;
+  const char *fmt;
   int i, j;
 
   switch (code)
     {
     case CONST_INT:
     case CONST_DOUBLE:
+    case CONST_VECTOR:
     case CONST:
     case SYMBOL_REF:
     case LABEL_REF:
@@ -610,7 +990,7 @@ modified_between_p (x, start, end)
       if (fmt[i] == 'e' && modified_between_p (XEXP (x, i), start, end))
        return 1;
 
-      if (fmt[i] == 'E')
+      else if (fmt[i] == 'E')
        for (j = XVECLEN (x, i) - 1; j >= 0; j--)
          if (modified_between_p (XVECEXP (x, i, j), start, end))
            return 1;
@@ -629,13 +1009,14 @@ modified_in_p (x, insn)
      rtx insn;
 {
   enum rtx_code code = GET_CODE (x);
-  char *fmt;
+  const char *fmt;
   int i, j;
 
   switch (code)
     {
     case CONST_INT:
     case CONST_DOUBLE:
+    case CONST_VECTOR:
     case CONST:
     case SYMBOL_REF:
     case LABEL_REF:
@@ -665,7 +1046,7 @@ modified_in_p (x, insn)
       if (fmt[i] == 'e' && modified_in_p (XEXP (x, i), insn))
        return 1;
 
-      if (fmt[i] == 'E')
+      else if (fmt[i] == 'E')
        for (j = XVECLEN (x, i) - 1; j >= 0; j--)
          if (modified_in_p (XVECEXP (x, i, j), insn))
            return 1;
@@ -673,41 +1054,131 @@ modified_in_p (x, insn)
 
   return 0;
 }
-\f
+
+/* Return true if anything in insn X is (anti,output,true) dependent on
+   anything in insn Y.  */
+
+int
+insn_dependent_p (x, y)
+     rtx x, y;
+{
+  rtx tmp;
+
+  if (! INSN_P (x) || ! INSN_P (y))
+    abort ();
+
+  tmp = PATTERN (y);
+  note_stores (PATTERN (x), insn_dependent_p_1, &tmp);
+  if (tmp == NULL_RTX)
+    return 1;
+
+  tmp = PATTERN (x);
+  note_stores (PATTERN (y), insn_dependent_p_1, &tmp);
+  if (tmp == NULL_RTX)
+    return 1;
+
+  return 0;
+}
+
+/* A helper routine for insn_dependent_p called through note_stores.  */
+
+static void
+insn_dependent_p_1 (x, pat, data)
+     rtx x;
+     rtx pat ATTRIBUTE_UNUSED;
+     void *data;
+{
+  rtx * pinsn = (rtx *) data;
+
+  if (*pinsn && reg_mentioned_p (x, *pinsn))
+    *pinsn = NULL_RTX;
+}
+\f
+/* Helper function for set_of.  */
+struct set_of_data
+  {
+    rtx found;
+    rtx pat;
+  };
+
+static void
+set_of_1 (x, pat, data1)
+     rtx x;
+     rtx pat;
+     void *data1;
+{
+   struct set_of_data *data = (struct set_of_data *) (data1);
+   if (rtx_equal_p (x, data->pat)
+       || (GET_CODE (x) != MEM && reg_overlap_mentioned_p (data->pat, x)))
+     data->found = pat;
+}
+
+/* Give an INSN, return a SET or CLOBBER expression that does modify PAT
+   (either directly or via STRICT_LOW_PART and similar modifiers).  */
+rtx
+set_of (pat, insn)
+     rtx pat, insn;
+{
+  struct set_of_data data;
+  data.found = NULL_RTX;
+  data.pat = pat;
+  note_stores (INSN_P (insn) ? PATTERN (insn) : insn, set_of_1, &data);
+  return data.found;
+}
+\f
 /* Given an INSN, return a SET expression if this insn has only a single SET.
    It may also have CLOBBERs, USEs, or SET whose output
    will not be used, which we ignore.  */
 
 rtx
-single_set (insn)
-     rtx insn;
+single_set_2 (insn, pat)
+     rtx insn, pat;
 {
-  rtx set;
+  rtx set = NULL;
+  int set_verified = 1;
   int i;
-  
-  if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
-    return 0;
 
-  if (GET_CODE (PATTERN (insn)) == SET)
-    return PATTERN (insn);
-  
-  else if (GET_CODE (PATTERN (insn)) == PARALLEL)
+  if (GET_CODE (pat) == PARALLEL)
     {
-      for (i = 0, set = 0; i < XVECLEN (PATTERN (insn), 0); i++)
-       if (GET_CODE (XVECEXP (PATTERN (insn), 0, i)) == SET
-           && (! find_reg_note (insn, REG_UNUSED,
-                                SET_DEST (XVECEXP (PATTERN (insn), 0, i)))
-               || side_effects_p (XVECEXP (PATTERN (insn), 0, i))))
-         {
-           if (set)
-             return 0;
-           else
-             set = XVECEXP (PATTERN (insn), 0, i);
-         }
-      return set;
+      for (i = 0; i < XVECLEN (pat, 0); i++)
+       {
+         rtx sub = XVECEXP (pat, 0, i);
+         switch (GET_CODE (sub))
+           {
+           case USE:
+           case CLOBBER:
+             break;
+
+           case SET:
+             /* We can consider insns having multiple sets, where all
+                but one are dead as single set insns.  In common case
+                only single set is present in the pattern so we want
+                to avoid checking for REG_UNUSED notes unless necessary.
+
+                When we reach set first time, we just expect this is
+                the single set we are looking for and only when more
+                sets are found in the insn, we check them.  */
+             if (!set_verified)
+               {
+                 if (find_reg_note (insn, REG_UNUSED, SET_DEST (set))
+                     && !side_effects_p (set))
+                   set = NULL;
+                 else
+                   set_verified = 1;
+               }
+             if (!set)
+               set = sub, set_verified = 0;
+             else if (!find_reg_note (insn, REG_UNUSED, SET_DEST (sub))
+                      || side_effects_p (sub))
+               return NULL_RTX;
+             break;
+
+           default:
+             return NULL_RTX;
+           }
+       }
     }
-  
-  return 0;
+  return set;
 }
 
 /* Given an INSN, return nonzero if it has more than one SET, else return
@@ -721,7 +1192,7 @@ multiple_sets (insn)
   int i;
   
   /* INSN must be an insn.  */
-  if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
+  if (! INSN_P (insn))
     return 0;
 
   /* Only a PARALLEL can have multiple SETs.  */
@@ -742,11 +1213,98 @@ multiple_sets (insn)
   return 0;
 }
 \f
-/* Return the last thing that X was assigned from before *PINSN.  Verify that
-   the object is not modified up to VALID_TO.  If it was, if we hit
-   a partial assignment to X, or hit a CODE_LABEL first, return X.  If we
-   found an assignment, update *PINSN to point to it.  
-   ALLOW_HWREG is set to 1 if hardware registers are allowed to be the src.  */
+/* Return nonzero if the destination of SET equals the source
+   and there are no side effects.  */
+
+int
+set_noop_p (set)
+     rtx set;
+{
+  rtx src = SET_SRC (set);
+  rtx dst = SET_DEST (set);
+
+  if (side_effects_p (src) || side_effects_p (dst))
+    return 0;
+
+  if (GET_CODE (dst) == MEM && GET_CODE (src) == MEM)
+    return rtx_equal_p (dst, src);
+
+  if (dst == pc_rtx && src == pc_rtx)
+    return 1;
+
+  if (GET_CODE (dst) == SIGN_EXTRACT
+      || GET_CODE (dst) == ZERO_EXTRACT)
+    return rtx_equal_p (XEXP (dst, 0), src)
+          && ! BYTES_BIG_ENDIAN && XEXP (dst, 2) == const0_rtx;
+
+  if (GET_CODE (dst) == STRICT_LOW_PART)
+    dst = XEXP (dst, 0);
+
+  if (GET_CODE (src) == SUBREG && GET_CODE (dst) == SUBREG)
+    {
+      if (SUBREG_BYTE (src) != SUBREG_BYTE (dst))
+       return 0;
+      src = SUBREG_REG (src);
+      dst = SUBREG_REG (dst);
+    }
+
+  return (GET_CODE (src) == REG && GET_CODE (dst) == REG
+         && REGNO (src) == REGNO (dst));
+}
+\f
+/* Return nonzero if an insn consists only of SETs, each of which only sets a
+   value to itself.  */
+
+int
+noop_move_p (insn)
+     rtx insn;
+{
+  rtx pat = PATTERN (insn);
+
+  if (INSN_CODE (insn) == NOOP_MOVE_INSN_CODE)
+    return 1;
+
+  /* Insns carrying these notes are useful later on.  */
+  if (find_reg_note (insn, REG_EQUAL, NULL_RTX))
+    return 0;
+
+  /* For now treat an insn with a REG_RETVAL note as a
+     a special insn which should not be considered a no-op.  */
+  if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
+    return 0;
+
+  if (GET_CODE (pat) == SET && set_noop_p (pat))
+    return 1;
+
+  if (GET_CODE (pat) == PARALLEL)
+    {
+      int i;
+      /* If nothing but SETs of registers to themselves,
+        this insn can also be deleted.  */
+      for (i = 0; i < XVECLEN (pat, 0); i++)
+       {
+         rtx tem = XVECEXP (pat, 0, i);
+
+         if (GET_CODE (tem) == USE
+             || GET_CODE (tem) == CLOBBER)
+           continue;
+
+         if (GET_CODE (tem) != SET || ! set_noop_p (tem))
+           return 0;
+       }
+
+      return 1;
+    }
+  return 0;
+}
+\f
+
+/* Return the last thing that X was assigned from before *PINSN.  If VALID_TO
+   is not NULL_RTX then verify that the object is not modified up to VALID_TO.
+   If the object was modified, if we hit a partial assignment to X, or hit a
+   CODE_LABEL first, return X.  If we found an assignment, update *PINSN to
+   point to it.  ALLOW_HWREG is set to 1 if hardware registers are allowed to
+   be the src.  */
 
 rtx
 find_last_value (x, pinsn, valid_to, allow_hwreg)
@@ -759,7 +1317,7 @@ find_last_value (x, pinsn, valid_to, allow_hwreg)
 
   for (p = PREV_INSN (*pinsn); p && GET_CODE (p) != CODE_LABEL;
        p = PREV_INSN (p))
-    if (GET_RTX_CLASS (GET_CODE (p)) == 'i')
+    if (INSN_P (p))
       {
        rtx set = single_set (p);
        rtx note = find_reg_note (p, REG_EQUAL, NULL_RTX);
@@ -771,7 +1329,8 @@ find_last_value (x, pinsn, valid_to, allow_hwreg)
            if (note && GET_CODE (XEXP (note, 0)) != EXPR_LIST)
              src = XEXP (note, 0);
 
-           if (! modified_between_p (src, PREV_INSN (p), valid_to)
+           if ((valid_to == NULL_RTX
+                || ! modified_between_p (src, PREV_INSN (p), valid_to))
                /* Reject hard registers because we don't usually want
                   to use them; we'd rather use a pseudo.  */
                && (! (GET_CODE (src) == REG
@@ -799,13 +1358,14 @@ find_last_value (x, pinsn, valid_to, allow_hwreg)
 
 int
 refers_to_regno_p (regno, endregno, x, loc)
-     int regno, endregno;
+     unsigned int regno, endregno;
      rtx x;
      rtx *loc;
 {
-  register int i;
-  register RTX_CODE code;
-  register char *fmt;
+  int i;
+  unsigned int x_regno;
+  RTX_CODE code;
+  const char *fmt;
 
  repeat:
   /* The contents of a REG_NONNEG note is always zero, so we must come here
@@ -818,22 +1378,22 @@ refers_to_regno_p (regno, endregno, x, loc)
   switch (code)
     {
     case REG:
-      i = REGNO (x);
+      x_regno = REGNO (x);
 
       /* If we modifying the stack, frame, or argument pointer, it will
         clobber a virtual register.  In fact, we could be more precise,
         but it isn't worth it.  */
-      if ((i == STACK_POINTER_REGNUM
+      if ((x_regno == STACK_POINTER_REGNUM
 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
-          || i == ARG_POINTER_REGNUM
+          || x_regno == ARG_POINTER_REGNUM
 #endif
-          || i == FRAME_POINTER_REGNUM)
+          || x_regno == FRAME_POINTER_REGNUM)
          && regno >= FIRST_VIRTUAL_REGISTER && regno <= LAST_VIRTUAL_REGISTER)
        return 1;
 
-      return (endregno > i
-             && regno < i + (i < FIRST_PSEUDO_REGISTER 
-                             ? HARD_REGNO_NREGS (i, GET_MODE (x))
+      return (endregno > x_regno
+             && regno < x_regno + (x_regno < FIRST_PSEUDO_REGISTER 
+                                   ? HARD_REGNO_NREGS (x_regno, GET_MODE (x))
                              : 1));
 
     case SUBREG:
@@ -842,8 +1402,8 @@ refers_to_regno_p (regno, endregno, x, loc)
       if (GET_CODE (SUBREG_REG (x)) == REG
          && REGNO (SUBREG_REG (x)) < FIRST_PSEUDO_REGISTER)
        {
-         int inner_regno = REGNO (SUBREG_REG (x)) + SUBREG_WORD (x);
-         int inner_endregno
+         unsigned int inner_regno = subreg_regno (x);
+         unsigned int inner_endregno
            = inner_regno + (inner_regno < FIRST_PSEUDO_REGISTER
                             ? HARD_REGNO_NREGS (regno, GET_MODE (x)) : 1);
 
@@ -894,7 +1454,7 @@ refers_to_regno_p (regno, endregno, x, loc)
        }
       else if (fmt[i] == 'E')
        {
-         register int j;
+         int j;
          for (j = XVECLEN (x, i) - 1; j >=0; j--)
            if (loc != &XVECEXP (x, i, j)
                && refers_to_regno_p (regno, endregno, XVECEXP (x, i, j), loc))
@@ -914,7 +1474,7 @@ int
 reg_overlap_mentioned_p (x, in)
      rtx x, in;
 {
-  int regno, endregno;
+  unsigned int regno, endregno;
 
   /* Overly conservative.  */
   if (GET_CODE (x) == STRICT_LOW_PART)
@@ -923,92 +1483,62 @@ reg_overlap_mentioned_p (x, in)
   /* If either argument is a constant, then modifying X can not affect IN.  */
   if (CONSTANT_P (x) || CONSTANT_P (in))
     return 0;
-  else if (GET_CODE (x) == SUBREG)
+
+  switch (GET_CODE (x))
     {
+    case SUBREG:
       regno = REGNO (SUBREG_REG (x));
       if (regno < FIRST_PSEUDO_REGISTER)
-       regno += SUBREG_WORD (x);
-    }
-  else if (GET_CODE (x) == REG)
-    regno = REGNO (x);
-  else if (GET_CODE (x) == MEM)
-    {
-      char *fmt;
-      int i;
-
-      if (GET_CODE (in) == MEM)
-       return 1;
-
-      fmt = GET_RTX_FORMAT (GET_CODE (in));
+       regno = subreg_regno (x);
+      goto do_reg;
 
-      for (i = GET_RTX_LENGTH (GET_CODE (in)) - 1; i >= 0; i--)
-       if (fmt[i] == 'e' && reg_overlap_mentioned_p (x, XEXP (in, i)))
-         return 1;
+    case REG:
+      regno = REGNO (x);
+    do_reg:
+      endregno = regno + (regno < FIRST_PSEUDO_REGISTER
+                         ? HARD_REGNO_NREGS (regno, GET_MODE (x)) : 1);
+      return refers_to_regno_p (regno, endregno, in, (rtx*) 0);
 
-      return 0;
-    }
-  else if (GET_CODE (x) == SCRATCH || GET_CODE (x) == PC
-          || GET_CODE (x) == CC0)
-    return reg_mentioned_p (x, in);
-  else if (GET_CODE (x) == PARALLEL
-          && GET_MODE (x) == BLKmode)
-    {
-      register int i;
+    case MEM:
+      {
+       const char *fmt;
+       int i;
 
-      /* If any register in here refers to it
-        we return true.  */
-      for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
-       if (reg_overlap_mentioned_p (SET_DEST (XVECEXP (x, 0, i)), in))
+       if (GET_CODE (in) == MEM)
          return 1;
-      return 0;
-    }
-  else
-    abort ();
-
-  endregno = regno + (regno < FIRST_PSEUDO_REGISTER
-                     ? HARD_REGNO_NREGS (regno, GET_MODE (x)) : 1);
 
-  return refers_to_regno_p (regno, endregno, in, NULL_PTR);
-}
-\f
-/* Used for communications between the next few functions.  */
-
-static int reg_set_last_unknown;
-static rtx reg_set_last_value;
-static int reg_set_last_first_regno, reg_set_last_last_regno;
+       fmt = GET_RTX_FORMAT (GET_CODE (in));
+       for (i = GET_RTX_LENGTH (GET_CODE (in)) - 1; i >= 0; i--)
+         if (fmt[i] == 'e' && reg_overlap_mentioned_p (x, XEXP (in, i)))
+           return 1;
 
-/* Called via note_stores from reg_set_last.  */
+       return 0;
+      }
 
-static void
-reg_set_last_1 (x, pat)
-     rtx x;
-     rtx pat;
-{
-  int first, last;
+    case SCRATCH:
+    case PC:
+    case CC0:
+      return reg_mentioned_p (x, in);
 
-  /* If X is not a register, or is not one in the range we care
-     about, ignore.  */
-  if (GET_CODE (x) != REG)
-    return;
+    case PARALLEL:
+      {
+       int i;
 
-  first = REGNO (x);
-  last = first + (first < FIRST_PSEUDO_REGISTER
-                 ? HARD_REGNO_NREGS (first, GET_MODE (x)) : 1);
+       /* If any register in here refers to it we return true.  */
+       for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
+         if (XEXP (XVECEXP (x, 0, i), 0) != 0
+             && reg_overlap_mentioned_p (XEXP (XVECEXP (x, 0, i), 0), in))
+             return 1;
+       return 0;
+      }
 
-  if (first >= reg_set_last_last_regno
-      || last <= reg_set_last_first_regno)
-    return;
+    default:
+      break;
+    }
 
-  /* If this is a CLOBBER or is some complex LHS, or doesn't modify
-     exactly the registers we care about, show we don't know the value.  */
-  if (GET_CODE (pat) == CLOBBER || SET_DEST (pat) != x
-      || first != reg_set_last_first_regno
-      || last != reg_set_last_last_regno)
-    reg_set_last_unknown = 1;
-  else
-    reg_set_last_value = SET_SRC (pat);
+  abort ();
 }
-
+\f
 /* Return the last value to which REG was set prior to INSN.  If we can't
    find it easily, return 0.
 
@@ -1022,16 +1552,6 @@ reg_set_last (x, insn)
 {
   rtx orig_insn = insn;
 
-  reg_set_last_first_regno = REGNO (x);
-
-  reg_set_last_last_regno
-    = reg_set_last_first_regno
-      + (reg_set_last_first_regno < FIRST_PSEUDO_REGISTER
-        ? HARD_REGNO_NREGS (reg_set_last_first_regno, GET_MODE (x)) : 1);
-
-  reg_set_last_unknown = 0;
-  reg_set_last_value = 0;
-
   /* Scan backwards until reg_set_last_1 changed one of the above flags.
      Stop when we reach a label or X is a hard reg and we reach a
      CALL_INSN (if reg_set_last_last_regno is a hard reg).
@@ -1043,21 +1563,24 @@ reg_set_last (x, insn)
   for (;
        insn && GET_CODE (insn) != CODE_LABEL
        && ! (GET_CODE (insn) == CALL_INSN
-            && reg_set_last_last_regno <= FIRST_PSEUDO_REGISTER);
+            && REGNO (x) <= FIRST_PSEUDO_REGISTER);
        insn = PREV_INSN (insn))
-    if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
+    if (INSN_P (insn))
       {
-       note_stores (PATTERN (insn), reg_set_last_1);
-       if (reg_set_last_unknown)
-         return 0;
-       else if (reg_set_last_value)
+       rtx set = set_of (x, insn);
+       /* OK, this function modify our register.  See if we understand it.  */
+       if (set)
          {
-           if (CONSTANT_P (reg_set_last_value)
-               || ((GET_CODE (reg_set_last_value) == REG
-                    || GET_CODE (reg_set_last_value) == SUBREG)
-                   && ! reg_set_between_p (reg_set_last_value,
+           rtx last_value;
+           if (GET_CODE (set) != SET || SET_DEST (set) != x)
+             return 0;
+           last_value = SET_SRC (x);
+           if (CONSTANT_P (last_value)
+               || ((GET_CODE (last_value) == REG
+                    || GET_CODE (last_value) == SUBREG)
+                   && ! reg_set_between_p (last_value,
                                            insn, orig_insn)))
-             return reg_set_last_value;
+             return last_value;
            else
              return 0;
          }
@@ -1066,113 +1589,6 @@ reg_set_last (x, insn)
   return 0;
 }
 \f
-/* This is 1 until after the rtl generation pass.  */
-int rtx_equal_function_value_matters;
-
-/* Return 1 if X and Y are identical-looking rtx's.
-   This is the Lisp function EQUAL for rtx arguments.  */
-
-int
-rtx_equal_p (x, y)
-     rtx x, y;
-{
-  register int i;
-  register int j;
-  register enum rtx_code code;
-  register char *fmt;
-
-  if (x == y)
-    return 1;
-  if (x == 0 || y == 0)
-    return 0;
-
-  code = GET_CODE (x);
-  /* Rtx's of different codes cannot be equal.  */
-  if (code != GET_CODE (y))
-    return 0;
-
-  /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
-     (REG:SI x) and (REG:HI x) are NOT equivalent.  */
-
-  if (GET_MODE (x) != GET_MODE (y))
-    return 0;
-
-  /* REG, LABEL_REF, and SYMBOL_REF can be compared nonrecursively.  */
-
-  if (code == REG)
-    /* Until rtl generation is complete, don't consider a reference to the
-       return register of the current function the same as the return from a
-       called function.  This eases the job of function integration.  Once the
-       distinction is no longer needed, they can be considered equivalent.  */
-    return (REGNO (x) == REGNO (y)
-           && (! rtx_equal_function_value_matters
-               || REG_FUNCTION_VALUE_P (x) == REG_FUNCTION_VALUE_P (y)));
-  else if (code == LABEL_REF)
-    return XEXP (x, 0) == XEXP (y, 0);
-  else if (code == SYMBOL_REF)
-    return XSTR (x, 0) == XSTR (y, 0);
-  else if (code == SCRATCH || code == CONST_DOUBLE)
-    return 0;
-
-  /* Compare the elements.  If any pair of corresponding elements
-     fail to match, return 0 for the whole things.  */
-
-  fmt = GET_RTX_FORMAT (code);
-  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
-    {
-      switch (fmt[i])
-       {
-       case 'w':
-         if (XWINT (x, i) != XWINT (y, i))
-           return 0;
-         break;
-
-       case 'n':
-       case 'i':
-         if (XINT (x, i) != XINT (y, i))
-           return 0;
-         break;
-
-       case 'V':
-       case 'E':
-         /* Two vectors must have the same length.  */
-         if (XVECLEN (x, i) != XVECLEN (y, i))
-           return 0;
-
-         /* And the corresponding elements must match.  */
-         for (j = 0; j < XVECLEN (x, i); j++)
-           if (rtx_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j)) == 0)
-             return 0;
-         break;
-
-       case 'e':
-         if (rtx_equal_p (XEXP (x, i), XEXP (y, i)) == 0)
-           return 0;
-         break;
-
-       case 'S':
-       case 's':
-         if (strcmp (XSTR (x, i), XSTR (y, i)))
-           return 0;
-         break;
-
-       case 'u':
-         /* These are just backpointers, so they don't matter.  */
-         break;
-
-       case '0':
-         break;
-
-         /* It is believed that rtx's at this level will never
-            contain anything but integers and other rtx's,
-            except for within LABEL_REFs and SYMBOL_REFs.  */
-       default:
-         abort ();
-       }
-    }
-  return 1;
-}
-\f
 /* Call FUN on each register or MEM that is stored into or clobbered by X.
    (X would be the pattern of an insn).
    FUN receives two arguments:
@@ -1183,13 +1599,20 @@ rtx_equal_p (x, y)
   the SUBREG will be passed.  */
      
 void
-note_stores (x, fun)
-     register rtx x;
-     void (*fun) PROTO ((rtx, rtx));
+note_stores (x, fun, data)
+     rtx x;
+     void (*fun) PARAMS ((rtx, rtx, void *));
+     void *data;
 {
-  if ((GET_CODE (x) == SET || GET_CODE (x) == CLOBBER))
+  int i;
+
+  if (GET_CODE (x) == COND_EXEC)
+    x = COND_EXEC_CODE (x);
+
+  if (GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
     {
-      register rtx dest = SET_DEST (x);
+      rtx dest = SET_DEST (x);
+
       while ((GET_CODE (dest) == SUBREG
              && (GET_CODE (SUBREG_REG (dest)) != REG
                  || REGNO (SUBREG_REG (dest)) >= FIRST_PSEUDO_REGISTER))
@@ -1198,44 +1621,107 @@ note_stores (x, fun)
             || GET_CODE (dest) == STRICT_LOW_PART)
        dest = XEXP (dest, 0);
 
-      if (GET_CODE (dest) == PARALLEL
-         && GET_MODE (dest) == BLKmode)
-       {
-         register int i;
-         for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
-           (*fun) (SET_DEST (XVECEXP (dest, 0, i)), x);
-       }
-      else
-       (*fun) (dest, x);
-    }
-  else if (GET_CODE (x) == PARALLEL)
-    {
-      register int i;
-      for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
-       {
-         register rtx y = XVECEXP (x, 0, i);
-         if (GET_CODE (y) == SET || GET_CODE (y) == CLOBBER)
-           {
-             register rtx dest = SET_DEST (y);
-             while ((GET_CODE (dest) == SUBREG
-                     && (GET_CODE (SUBREG_REG (dest)) != REG
-                         || (REGNO (SUBREG_REG (dest))
-                             >= FIRST_PSEUDO_REGISTER)))
-                    || GET_CODE (dest) == ZERO_EXTRACT
-                    || GET_CODE (dest) == SIGN_EXTRACT
-                    || GET_CODE (dest) == STRICT_LOW_PART)
-               dest = XEXP (dest, 0);
-             if (GET_CODE (dest) == PARALLEL
-                 && GET_MODE (dest) == BLKmode)
-               {
-                 register int i;
-                 for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
-                   (*fun) (SET_DEST (XVECEXP (dest, 0, i)), y);
-               }
-             else
-               (*fun) (dest, y);
-           }
-       }
+      /* If we have a PARALLEL, SET_DEST is a list of EXPR_LIST expressions,
+        each of whose first operand is a register.  */
+      if (GET_CODE (dest) == PARALLEL)
+       {
+         for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
+           if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
+             (*fun) (XEXP (XVECEXP (dest, 0, i), 0), x, data);
+       }
+      else
+       (*fun) (dest, x, data);
+    }
+
+  else if (GET_CODE (x) == PARALLEL)
+    for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
+      note_stores (XVECEXP (x, 0, i), fun, data);
+}
+\f
+/* Like notes_stores, but call FUN for each expression that is being
+   referenced in PBODY, a pointer to the PATTERN of an insn.  We only call
+   FUN for each expression, not any interior subexpressions.  FUN receives a
+   pointer to the expression and the DATA passed to this function.
+
+   Note that this is not quite the same test as that done in reg_referenced_p
+   since that considers something as being referenced if it is being
+   partially set, while we do not.  */
+
+void
+note_uses (pbody, fun, data)
+     rtx *pbody;
+     void (*fun) PARAMS ((rtx *, void *));
+     void *data;
+{
+  rtx body = *pbody;
+  int i;
+
+  switch (GET_CODE (body))
+    {
+    case COND_EXEC:
+      (*fun) (&COND_EXEC_TEST (body), data);
+      note_uses (&COND_EXEC_CODE (body), fun, data);
+      return;
+
+    case PARALLEL:
+      for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
+       note_uses (&XVECEXP (body, 0, i), fun, data);
+      return;
+
+    case USE:
+      (*fun) (&XEXP (body, 0), data);
+      return;
+
+    case ASM_OPERANDS:
+      for (i = ASM_OPERANDS_INPUT_LENGTH (body) - 1; i >= 0; i--)
+       (*fun) (&ASM_OPERANDS_INPUT (body, i), data);
+      return;
+
+    case TRAP_IF:
+      (*fun) (&TRAP_CONDITION (body), data);
+      return;
+
+    case PREFETCH:
+      (*fun) (&XEXP (body, 0), data);
+      return;
+
+    case UNSPEC:
+    case UNSPEC_VOLATILE:
+      for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
+       (*fun) (&XVECEXP (body, 0, i), data);
+      return;
+
+    case CLOBBER:
+      if (GET_CODE (XEXP (body, 0)) == MEM)
+       (*fun) (&XEXP (XEXP (body, 0), 0), data);
+      return;
+
+    case SET:
+      {
+       rtx dest = SET_DEST (body);
+
+       /* For sets we replace everything in source plus registers in memory
+          expression in store and operands of a ZERO_EXTRACT.  */
+       (*fun) (&SET_SRC (body), data);
+
+       if (GET_CODE (dest) == ZERO_EXTRACT)
+         {
+           (*fun) (&XEXP (dest, 1), data);
+           (*fun) (&XEXP (dest, 2), data);
+         }
+
+       while (GET_CODE (dest) == SUBREG || GET_CODE (dest) == STRICT_LOW_PART)
+         dest = XEXP (dest, 0);
+
+       if (GET_CODE (dest) == MEM)
+         (*fun) (&XEXP (dest, 0), data);
+      }
+      return;
+
+    default:
+      /* All the other possibilities never store.  */
+      (*fun) (pbody, data);
+      return;
     }
 }
 \f
@@ -1261,8 +1747,8 @@ dead_or_set_p (insn, x)
      rtx insn;
      rtx x;
 {
-  register int regno, last_regno;
-  register int i;
+  unsigned int regno, last_regno;
+  unsigned int i;
 
   /* Can't use cc0_rtx below since this file is used by genattrtab.c.  */
   if (GET_CODE (x) == CC0)
@@ -1288,33 +1774,25 @@ dead_or_set_p (insn, x)
 int
 dead_or_set_regno_p (insn, test_regno)
      rtx insn;
-     int test_regno;
+     unsigned int test_regno;
 {
-  int regno, endregno;
-  rtx link;
-
-  /* See if there is a death note for something that includes
-     TEST_REGNO.  */
-  for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
-    {
-      if (REG_NOTE_KIND (link) != REG_DEAD
-         || GET_CODE (XEXP (link, 0)) != REG)
-       continue;
+  unsigned int regno, endregno;
+  rtx pattern;
 
-      regno = REGNO (XEXP (link, 0));
-      endregno = (regno >= FIRST_PSEUDO_REGISTER ? regno + 1
-                 : regno + HARD_REGNO_NREGS (regno,
-                                             GET_MODE (XEXP (link, 0))));
-
-      if (test_regno >= regno && test_regno < endregno)
-       return 1;
-    }
+  /* See if there is a death note for something that includes TEST_REGNO.  */
+  if (find_regno_note (insn, REG_DEAD, test_regno))
+    return 1;
 
   if (GET_CODE (insn) == CALL_INSN
       && find_regno_fusage (insn, CLOBBER, test_regno))
     return 1;
 
-  if (GET_CODE (PATTERN (insn)) == SET)
+  pattern = PATTERN (insn);
+
+  if (GET_CODE (pattern) == COND_EXEC)
+    pattern = COND_EXEC_CODE (pattern);
+
+  if (GET_CODE (pattern) == SET)
     {
       rtx dest = SET_DEST (PATTERN (insn));
  
@@ -1337,13 +1815,16 @@ dead_or_set_regno_p (insn, test_regno)
 
       return (test_regno >= regno && test_regno < endregno);
     }
-  else if (GET_CODE (PATTERN (insn)) == PARALLEL)
+  else if (GET_CODE (pattern) == PARALLEL)
     {
-      register int i;
+      int i;
 
-      for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
+      for (i = XVECLEN (pattern, 0) - 1; i >= 0; i--)
        {
-         rtx body = XVECEXP (PATTERN (insn), 0, i);
+         rtx body = XVECEXP (pattern, 0, i);
+
+         if (GET_CODE (body) == COND_EXEC)
+           body = COND_EXEC_CODE (body);
 
          if (GET_CODE (body) == SET || GET_CODE (body) == CLOBBER)
            {
@@ -1381,10 +1862,10 @@ find_reg_note (insn, kind, datum)
      enum reg_note kind;
      rtx datum;
 {
-  register rtx link;
+  rtx link;
 
   /* Ignore anything that is not an INSN, JUMP_INSN or CALL_INSN.  */
-  if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
+  if (! INSN_P (insn))
     return 0;
 
   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
@@ -1403,12 +1884,12 @@ rtx
 find_regno_note (insn, kind, regno)
      rtx insn;
      enum reg_note kind;
-     int regno;
+     unsigned int regno;
 {
-  register rtx link;
+  rtx link;
 
   /* Ignore anything that is not an INSN, JUMP_INSN or CALL_INSN.  */
-  if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
+  if (! INSN_P (insn))
     return 0;
 
   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
@@ -1426,6 +1907,23 @@ find_regno_note (insn, kind, regno)
   return 0;
 }
 
+/* Return a REG_EQUIV or REG_EQUAL note if insn has only a single set and
+   has such a note.  */
+
+rtx
+find_reg_equal_equiv_note (insn)
+     rtx insn;
+{
+  rtx note;
+
+  if (single_set (insn) == 0)
+    return 0;
+  else if ((note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != 0)
+    return note;
+  else
+    return find_reg_note (insn, REG_EQUAL, NULL_RTX);
+}
+
 /* Return true if DATUM, or any overlap of DATUM, of kind CODE is found
    in the CALL_INSN_FUNCTION_USAGE information of INSN.  */
 
@@ -1441,30 +1939,31 @@ find_reg_fusage (insn, code, datum)
     return 0;
 
   if (! datum)
-    abort();
+    abort ();
 
   if (GET_CODE (datum) != REG)
     {
-      register rtx link;
+      rtx link;
 
       for (link = CALL_INSN_FUNCTION_USAGE (insn);
            link;
           link = XEXP (link, 1))
         if (GET_CODE (XEXP (link, 0)) == code
-           && rtx_equal_p (datum, SET_DEST (XEXP (link, 0))))
+           && rtx_equal_p (datum, XEXP (XEXP (link, 0), 0)))
           return 1;
     }
   else
     {
-      register int regno = REGNO (datum);
+      unsigned int regno = REGNO (datum);
 
       /* CALL_INSN_FUNCTION_USAGE information cannot contain references
         to pseudo registers, so don't bother checking.  */
 
       if (regno < FIRST_PSEUDO_REGISTER)
         {
-         int end_regno = regno + HARD_REGNO_NREGS (regno, GET_MODE (datum));
-         int i;
+         unsigned int end_regno
+           = regno + HARD_REGNO_NREGS (regno, GET_MODE (datum));
+         unsigned int i;
 
          for (i = regno; i < end_regno; i++)
            if (find_regno_fusage (insn, code, i))
@@ -1482,9 +1981,9 @@ int
 find_regno_fusage (insn, code, regno)
      rtx insn;
      enum rtx_code code;
-     int regno;
+     unsigned int regno;
 {
-  register rtx link;
+  rtx link;
 
   /* CALL_INSN_FUNCTION_USAGE information cannot contain references
      to pseudo registers, so don't bother checking.  */
@@ -1494,18 +1993,41 @@ find_regno_fusage (insn, code, regno)
     return 0;
 
   for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
-   {
-    register int regnote;
-    register rtx op;
-
-    if (GET_CODE (op = XEXP (link, 0)) == code
-       && GET_CODE (SET_DEST (op)) == REG
-       && (regnote = REGNO (SET_DEST (op))) <= regno
-       && regnote
-               + HARD_REGNO_NREGS (regnote, GET_MODE (SET_DEST (op)))
-           > regno)
-      return 1;
-   }
+    {
+      unsigned int regnote;
+      rtx op, reg;
+
+      if (GET_CODE (op = XEXP (link, 0)) == code
+         && GET_CODE (reg = XEXP (op, 0)) == REG
+         && (regnote = REGNO (reg)) <= regno
+         && regnote + HARD_REGNO_NREGS (regnote, GET_MODE (reg)) > regno)
+       return 1;
+    }
+
+  return 0;
+}
+
+/* Return true if INSN is a call to a pure function.  */
+
+int
+pure_call_p (insn)
+     rtx insn;
+{
+  rtx link;
+
+  if (GET_CODE (insn) != CALL_INSN || ! CONST_OR_PURE_CALL_P (insn))
+    return 0;
+
+  /* Look for the note that differentiates const and pure functions.  */
+  for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
+    {
+      rtx u, m;
+
+      if (GET_CODE (u = XEXP (link, 0)) == USE
+         && GET_CODE (m = XEXP (u, 0)) == MEM && GET_MODE (m) == BLKmode
+         && GET_CODE (XEXP (m, 0)) == SCRATCH)
+       return 1;
+    }
 
   return 0;
 }
@@ -1514,10 +2036,13 @@ find_regno_fusage (insn, code, regno)
 
 void
 remove_note (insn, note)
-     register rtx note;
-     register rtx insn;
+     rtx insn;
+     rtx note;
 {
-  register rtx link;
+  rtx link;
+
+  if (note == NULL_RTX)
+    return;
 
   if (REG_NOTES (insn) == note)
     {
@@ -1535,11 +2060,28 @@ remove_note (insn, note)
   abort ();
 }
 
-/* Search LISTP (an EXPR_LIST) for NODE and remove NODE from the list
-   if it is found.
+/* Search LISTP (an EXPR_LIST) for an entry whose first operand is NODE and
+   return 1 if it is found.  A simple equality test is used to determine if
+   NODE matches.  */
+
+int
+in_expr_list_p (listp, node)
+     rtx listp;
+     rtx node;
+{
+  rtx x;
+
+  for (x = listp; x; x = XEXP (x, 1))
+    if (node == XEXP (x, 0))
+      return 1;
+
+  return 0;
+}
+
+/* Search LISTP (an EXPR_LIST) for an entry whose first operand is NODE and
+   remove that entry from the list if it is found.
 
-   A simple equality test is used to determine if NODE is on the
-   EXPR_LIST.  */
+   A simple equality test is used to determine if NODE matches.  */
 
 void
 remove_node_from_expr_list (node, listp)
@@ -1561,6 +2103,8 @@ remove_node_from_expr_list (node, listp)
 
          return;
        }
+
+      prev = temp;
       temp = XEXP (temp, 1);
     }
 }
@@ -1574,7 +2118,7 @@ int
 volatile_insn_p (x)
      rtx x;
 {
-  register RTX_CODE code;
+  RTX_CODE code;
 
   code = GET_CODE (x);
   switch (code)
@@ -1584,6 +2128,7 @@ volatile_insn_p (x)
     case CONST_INT:
     case CONST:
     case CONST_DOUBLE:
+    case CONST_VECTOR:
     case CC0:
     case PC:
     case REG:
@@ -1611,8 +2156,8 @@ volatile_insn_p (x)
   /* Recursively scan the operands of this expression.  */
 
   {
-    register char *fmt = GET_RTX_FORMAT (code);
-    register int i;
+    const char *fmt = GET_RTX_FORMAT (code);
+    int i;
     
     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
       {
@@ -1621,9 +2166,9 @@ volatile_insn_p (x)
            if (volatile_insn_p (XEXP (x, i)))
              return 1;
          }
-       if (fmt[i] == 'E')
+       else if (fmt[i] == 'E')
          {
-           register int j;
+           int j;
            for (j = 0; j < XVECLEN (x, i); j++)
              if (volatile_insn_p (XVECEXP (x, i, j)))
                return 1;
@@ -1640,7 +2185,7 @@ int
 volatile_refs_p (x)
      rtx x;
 {
-  register RTX_CODE code;
+  RTX_CODE code;
 
   code = GET_CODE (x);
   switch (code)
@@ -1650,6 +2195,7 @@ volatile_refs_p (x)
     case CONST_INT:
     case CONST:
     case CONST_DOUBLE:
+    case CONST_VECTOR:
     case CC0:
     case PC:
     case REG:
@@ -1677,8 +2223,8 @@ volatile_refs_p (x)
   /* Recursively scan the operands of this expression.  */
 
   {
-    register char *fmt = GET_RTX_FORMAT (code);
-    register int i;
+    const char *fmt = GET_RTX_FORMAT (code);
+    int i;
     
     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
       {
@@ -1687,9 +2233,9 @@ volatile_refs_p (x)
            if (volatile_refs_p (XEXP (x, i)))
              return 1;
          }
-       if (fmt[i] == 'E')
+       else if (fmt[i] == 'E')
          {
-           register int j;
+           int j;
            for (j = 0; j < XVECLEN (x, i); j++)
              if (volatile_refs_p (XVECEXP (x, i, j)))
                return 1;
@@ -1706,7 +2252,7 @@ int
 side_effects_p (x)
      rtx x;
 {
-  register RTX_CODE code;
+  RTX_CODE code;
 
   code = GET_CODE (x);
   switch (code)
@@ -1716,6 +2262,7 @@ side_effects_p (x)
     case CONST_INT:
     case CONST:
     case CONST_DOUBLE:
+    case CONST_VECTOR:
     case CC0:
     case PC:
     case REG:
@@ -1735,6 +2282,8 @@ side_effects_p (x)
     case PRE_DEC:
     case POST_INC:
     case POST_DEC:
+    case PRE_MODIFY:
+    case POST_MODIFY:
     case CALL:
     case UNSPEC_VOLATILE:
  /* case TRAP_IF: This isn't clear yet.  */
@@ -1752,8 +2301,8 @@ side_effects_p (x)
   /* Recursively scan the operands of this expression.  */
 
   {
-    register char *fmt = GET_RTX_FORMAT (code);
-    register int i;
+    const char *fmt = GET_RTX_FORMAT (code);
+    int i;
     
     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
       {
@@ -1762,9 +2311,9 @@ side_effects_p (x)
            if (side_effects_p (XEXP (x, i)))
              return 1;
          }
-       if (fmt[i] == 'E')
+       else if (fmt[i] == 'E')
          {
-           register int j;
+           int j;
            for (j = 0; j < XVECLEN (x, i); j++)
              if (side_effects_p (XVECEXP (x, i, j)))
                return 1;
@@ -1782,7 +2331,7 @@ may_trap_p (x)
 {
   int i;
   enum rtx_code code;
-  char *fmt;
+  const char *fmt;
 
   if (x == 0)
     return 0;
@@ -1792,6 +2341,7 @@ may_trap_p (x)
       /* Handle these cases quickly.  */
     case CONST_INT:
     case CONST_DOUBLE:
+    case CONST_VECTOR:
     case SYMBOL_REF:
     case LABEL_REF:
     case CONST:
@@ -1801,11 +2351,14 @@ may_trap_p (x)
     case SCRATCH:
       return 0;
 
-      /* Conditional trap can trap!  */
+    case ASM_INPUT:
     case UNSPEC_VOLATILE:
     case TRAP_IF:
       return 1;
 
+    case ASM_OPERANDS:
+      return MEM_VOLATILE_P (x);
+
       /* Memory ref can trap unless it's a static var or a stack slot.  */
     case MEM:
       return rtx_addr_can_trap_p (XEXP (x, 0));
@@ -1816,7 +2369,8 @@ may_trap_p (x)
     case UDIV:
     case UMOD:
       if (! CONSTANT_P (XEXP (x, 1))
-         || GET_MODE_CLASS (GET_MODE (x)) == MODE_FLOAT)
+         || (GET_MODE_CLASS (GET_MODE (x)) == MODE_FLOAT
+             && flag_trapping_math))
        return 1;
       /* This was const0_rtx, but by not using that,
         we can link this file into other programs.  */
@@ -1829,9 +2383,36 @@ may_trap_p (x)
         certainly may trap.  */
       return 1;
 
+    case GE:
+    case GT:
+    case LE:
+    case LT:
+    case COMPARE:
+      /* Some floating point comparisons may trap.  */
+      if (!flag_trapping_math)
+       break;
+      /* ??? There is no machine independent way to check for tests that trap
+        when COMPARE is used, though many targets do make this distinction.
+        For instance, sparc uses CCFPE for compares which generate exceptions
+        and CCFP for compares which do not generate exceptions.  */
+      if (GET_MODE_CLASS (GET_MODE (x)) == MODE_FLOAT)
+       return 1;
+      /* But often the compare has some CC mode, so check operand
+        modes as well.  */
+      if (GET_MODE_CLASS (GET_MODE (XEXP (x, 0))) == MODE_FLOAT
+         || GET_MODE_CLASS (GET_MODE (XEXP (x, 1))) == MODE_FLOAT)
+       return 1;
+      break;
+
+    case NEG:
+    case ABS:
+      /* These operations don't trap even with floating point.  */
+      break;
+
     default:
       /* Any floating arithmetic may trap.  */
-      if (GET_MODE_CLASS (GET_MODE (x)) == MODE_FLOAT)
+      if (GET_MODE_CLASS (GET_MODE (x)) == MODE_FLOAT
+         && flag_trapping_math)
        return 1;
     }
 
@@ -1845,7 +2426,7 @@ may_trap_p (x)
        }
       else if (fmt[i] == 'E')
        {
-         register int j;
+         int j;
          for (j = 0; j < XVECLEN (x, i); j++)
            if (may_trap_p (XVECEXP (x, i, j)))
              return 1;
@@ -1861,9 +2442,9 @@ int
 inequality_comparisons_p (x)
      rtx x;
 {
-  register char *fmt;
-  register int len, i;
-  register enum rtx_code code = GET_CODE (x);
+  const char *fmt;
+  int len, i;
+  enum rtx_code code = GET_CODE (x);
 
   switch (code)
     {
@@ -1873,6 +2454,7 @@ inequality_comparisons_p (x)
     case CC0:
     case CONST_INT:
     case CONST_DOUBLE:
+    case CONST_VECTOR:
     case CONST:
     case LABEL_REF:
     case SYMBOL_REF:
@@ -1904,7 +2486,7 @@ inequality_comparisons_p (x)
        }
       else if (fmt[i] == 'E')
        {
-         register int j;
+         int j;
          for (j = XVECLEN (x, i) - 1; j >= 0; j--)
            if (inequality_comparisons_p (XVECEXP (x, i, j)))
              return 1;
@@ -1924,11 +2506,11 @@ rtx
 replace_rtx (x, from, to)
      rtx x, from, to;
 {
-  register int i, j;
-  register char *fmt;
+  int i, j;
+  const char *fmt;
 
   /* The following prevents loops occurrence when we change MEM in
-     CONST_DOUBLE onto the same CONST_DOUBLE. */
+     CONST_DOUBLE onto the same CONST_DOUBLE.  */
   if (x != 0 && GET_CODE (x) == CONST_DOUBLE)
     return x;
 
@@ -1939,6 +2521,40 @@ replace_rtx (x, from, to)
   if (x == 0)
     return 0;
 
+  if (GET_CODE (x) == SUBREG)
+    {
+      rtx new = replace_rtx (SUBREG_REG (x), from, to);
+
+      if (GET_CODE (new) == CONST_INT)
+       {
+         x = simplify_subreg (GET_MODE (x), new,
+                              GET_MODE (SUBREG_REG (x)),
+                              SUBREG_BYTE (x));
+         if (! x)
+           abort ();
+       }
+      else
+       SUBREG_REG (x) = new;
+
+      return x;
+    }
+  else if (GET_CODE (x) == ZERO_EXTEND)
+    {
+      rtx new = replace_rtx (XEXP (x, 0), from, to);
+
+      if (GET_CODE (new) == CONST_INT)
+       {
+         x = simplify_unary_operation (ZERO_EXTEND, GET_MODE (x),
+                                       new, GET_MODE (XEXP (x, 0)));
+         if (! x)
+           abort ();
+       }
+      else
+       XEXP (x, 0) = new;
+
+      return x;
+    }
+
   fmt = GET_RTX_FORMAT (GET_CODE (x));
   for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
     {
@@ -1968,12 +2584,12 @@ rtx
 replace_regs (x, reg_map, nregs, replace_dest)
      rtx x;
      rtx *reg_map;
-     int nregs;
+     unsigned int nregs;
      int replace_dest;
 {
-  register enum rtx_code code;
-  register int i;
-  register char *fmt;
+  enum rtx_code code;
+  int i;
+  const char *fmt;
 
   if (x == 0)
     return x;
@@ -1986,6 +2602,7 @@ replace_regs (x, reg_map, nregs, replace_dest)
     case CC0:
     case CONST_INT:
     case CONST_DOUBLE:
+    case CONST_VECTOR:
     case CONST:
     case SYMBOL_REF:
     case LABEL_REF:
@@ -2011,26 +2628,9 @@ replace_regs (x, reg_map, nregs, replace_dest)
          && GET_CODE (reg_map[REGNO (SUBREG_REG (x))]) == SUBREG)
        {
          rtx map_val = reg_map[REGNO (SUBREG_REG (x))];
-         rtx map_inner = SUBREG_REG (map_val);
-
-         if (GET_MODE (x) == GET_MODE (map_inner))
-           return map_inner;
-         else
-           {
-             /* We cannot call gen_rtx here since we may be linked with
-                genattrtab.c.  */
-             /* Let's try clobbering the incoming SUBREG and see
-                if this is really safe.  */
-             SUBREG_REG (x) = map_inner;
-             SUBREG_WORD (x) += SUBREG_WORD (map_val);
-             return x;
-#if 0
-             rtx new = rtx_alloc (SUBREG);
-             PUT_MODE (new, GET_MODE (x));
-             SUBREG_REG (new) = map_inner;
-             SUBREG_WORD (new) = SUBREG_WORD (x) + SUBREG_WORD (map_val);
-#endif
-           }
+         return simplify_gen_subreg (GET_MODE (x), map_val,
+                                     GET_MODE (SUBREG_REG (x)), 
+                                     SUBREG_BYTE (x));
        }
       break;
 
@@ -2061,9 +2661,9 @@ replace_regs (x, reg_map, nregs, replace_dest)
     {
       if (fmt[i] == 'e')
        XEXP (x, i) = replace_regs (XEXP (x, i), reg_map, nregs, replace_dest);
-      if (fmt[i] == 'E')
+      else if (fmt[i] == 'E')
        {
-         register int j;
+         int j;
          for (j = 0; j < XVECLEN (x, i); j++)
            XVECEXP (x, i, j) = replace_regs (XVECEXP (x, i, j), reg_map,
                                              nregs, replace_dest);
@@ -2072,24 +2672,29 @@ replace_regs (x, reg_map, nregs, replace_dest)
   return x;
 }
 
-/* Return 1 if X, the SRC_SRC of  SET of (pc) contain a REG or MEM that is
-   not in the constant pool and not in the condition of an IF_THEN_ELSE.  */
+/* A subroutine of computed_jump_p, return 1 if X contains a REG or MEM or
+   constant that is not in the constant pool and not in the condition
+   of an IF_THEN_ELSE.  */
 
 static int
-jmp_uses_reg_or_mem (x)
+computed_jump_p_1 (x)
      rtx x;
 {
   enum rtx_code code = GET_CODE (x);
   int i, j;
-  char *fmt;
+  const char *fmt;
 
   switch (code)
     {
-    case CONST:
     case LABEL_REF:
     case PC:
       return 0;
 
+    case CONST:
+    case CONST_INT:
+    case CONST_DOUBLE:
+    case CONST_VECTOR:
+    case SYMBOL_REF:
     case REG:
       return 1;
 
@@ -2098,12 +2703,8 @@ jmp_uses_reg_or_mem (x)
                && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)));
 
     case IF_THEN_ELSE:
-      return (jmp_uses_reg_or_mem (XEXP (x, 1))
-             || jmp_uses_reg_or_mem (XEXP (x, 2)));
-
-    case PLUS:  case MINUS:  case MULT:
-      return (jmp_uses_reg_or_mem (XEXP (x, 0))
-             || jmp_uses_reg_or_mem (XEXP (x, 1)));
+      return (computed_jump_p_1 (XEXP (x, 1))
+             || computed_jump_p_1 (XEXP (x, 2)));
 
     default:
       break;
@@ -2113,12 +2714,12 @@ jmp_uses_reg_or_mem (x)
   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
     {
       if (fmt[i] == 'e'
-         && jmp_uses_reg_or_mem (XEXP (x, i)))
+         && computed_jump_p_1 (XEXP (x, i)))
        return 1;
 
-      if (fmt[i] == 'E')
+      else if (fmt[i] == 'E')
        for (j = 0; j < XVECLEN (x, i); j++)
-         if (jmp_uses_reg_or_mem (XVECEXP (x, i, j)))
+         if (computed_jump_p_1 (XVECEXP (x, i, j)))
            return 1;
     }
 
@@ -2128,7 +2729,7 @@ jmp_uses_reg_or_mem (x)
 /* Return nonzero if INSN is an indirect jump (aka computed jump).
 
    Tablejumps and casesi insns are not considered indirect jumps;
-   we can recognize them by a (use (lael_ref)).  */
+   we can recognize them by a (use (label_ref)).  */
 
 int
 computed_jump_p (insn)
@@ -2139,7 +2740,9 @@ computed_jump_p (insn)
     {
       rtx pat = PATTERN (insn);
 
-      if (GET_CODE (pat) == PARALLEL)
+      if (find_reg_note (insn, REG_LABEL, NULL_RTX))
+       return 0;
+      else if (GET_CODE (pat) == PARALLEL)
        {
          int len = XVECLEN (pat, 0);
          int has_use_labelref = 0;
@@ -2154,12 +2757,12 @@ computed_jump_p (insn)
            for (i = len - 1; i >= 0; i--)
              if (GET_CODE (XVECEXP (pat, 0, i)) == SET
                  && SET_DEST (XVECEXP (pat, 0, i)) == pc_rtx
-                 && jmp_uses_reg_or_mem (SET_SRC (XVECEXP (pat, 0, i))))
+                 && computed_jump_p_1 (SET_SRC (XVECEXP (pat, 0, i))))
                return 1;
        }
       else if (GET_CODE (pat) == SET
               && SET_DEST (pat) == pc_rtx
-              && jmp_uses_reg_or_mem (SET_SRC (pat)))
+              && computed_jump_p_1 (SET_SRC (pat)))
        return 1;
     }
   return 0;
@@ -2186,11 +2789,11 @@ for_each_rtx (x, f, data)
 {
   int result;
   int length;
-  char* format;
+  const char *format;
   int i;
 
   /* Call F on X.  */
-  result = (*f)(x, data);
+  result = (*f) (x, data);
   if (result == -1)
     /* Do not traverse sub-expressions.  */
     return 0;
@@ -2244,10 +2847,10 @@ for_each_rtx (x, f, data)
 
 rtx
 regno_use_in (regno, x)
-     int regno;
+     unsigned int regno;
      rtx x;
 {
-  register char *fmt;
+  const char *fmt;
   int i, j;
   rtx tem;
 
@@ -2271,6 +2874,54 @@ regno_use_in (regno, x)
   return NULL_RTX;
 }
 
+/* Return a value indicating whether OP, an operand of a commutative
+   operation, is preferred as the first or second operand.  The higher
+   the value, the stronger the preference for being the first operand.
+   We use negative values to indicate a preference for the first operand
+   and positive values for the second operand.  */
+
+int
+commutative_operand_precedence (op)
+     rtx op;
+{
+  /* Constants always come the second operand.  Prefer "nice" constants.  */
+  if (GET_CODE (op) == CONST_INT)
+    return -5;
+  if (GET_CODE (op) == CONST_DOUBLE)
+    return -4;
+  if (CONSTANT_P (op))
+    return -3;
+
+  /* SUBREGs of objects should come second.  */
+  if (GET_CODE (op) == SUBREG
+      && GET_RTX_CLASS (GET_CODE (SUBREG_REG (op))) == 'o')
+    return -2;
+
+  /* If only one operand is a `neg', `not',
+    `mult', `plus', or `minus' expression, it will be the first
+    operand.  */
+  if (GET_CODE (op) == NEG || GET_CODE (op) == NOT
+      || GET_CODE (op) == MULT || GET_CODE (op) == PLUS
+      || GET_CODE (op) == MINUS)
+    return 2;
+
+  /* Complex expressions should be the first, so decrease priority
+     of objects.  */
+  if (GET_RTX_CLASS (GET_CODE (op)) == 'o')
+    return -1;
+  return 0;
+}
+
+/* Return 1 iff it is necessary to swap operands of commutative operation
+   in order to canonicalize expression.  */
+
+int
+swap_commutative_operands_p (x, y)
+     rtx x, y;
+{
+  return (commutative_operand_precedence (x)
+         < commutative_operand_precedence (y));
+}
 
 /* Return 1 if X is an autoincrement side effect and the register is
    not the stack pointer.  */
@@ -2294,3 +2945,314 @@ auto_inc_p (x)
     }
   return 0;
 }
+
+/* Return 1 if the sequence of instructions beginning with FROM and up
+   to and including TO is safe to move.  If NEW_TO is non-NULL, and
+   the sequence is not already safe to move, but can be easily
+   extended to a sequence which is safe, then NEW_TO will point to the
+   end of the extended sequence.  
+   For now, this function only checks that the region contains whole
+   exception regions, but it could be extended to check additional
+   conditions as well.  */
+
+int
+insns_safe_to_move_p (from, to, new_to)
+     rtx from;
+     rtx to;
+     rtx *new_to;
+{
+  int eh_region_count = 0;
+  int past_to_p = 0;
+  rtx r = from;
+
+  /* By default, assume the end of the region will be what was
+     suggested.  */
+  if (new_to)
+    *new_to = to;
+
+  while (r)
+    {
+      if (GET_CODE (r) == NOTE)
+       {
+         switch (NOTE_LINE_NUMBER (r))
+           {
+           case NOTE_INSN_EH_REGION_BEG:
+             ++eh_region_count;
+             break;
+
+           case NOTE_INSN_EH_REGION_END:
+             if (eh_region_count == 0)
+               /* This sequence of instructions contains the end of
+                  an exception region, but not he beginning.  Moving
+                  it will cause chaos.  */
+               return 0;
+
+             --eh_region_count;
+             break;
+
+           default:
+             break;
+           }
+       }
+      else if (past_to_p)
+       /* If we've passed TO, and we see a non-note instruction, we
+          can't extend the sequence to a movable sequence.  */
+       return 0;
+
+      if (r == to)
+       {
+         if (!new_to)
+           /* It's OK to move the sequence if there were matched sets of
+              exception region notes.  */
+           return eh_region_count == 0;
+         
+         past_to_p = 1;
+       }
+
+      /* It's OK to move the sequence if there were matched sets of
+        exception region notes.  */
+      if (past_to_p && eh_region_count == 0)
+       {
+         *new_to = r;
+         return 1;
+       }
+
+      /* Go to the next instruction.  */
+      r = NEXT_INSN (r);
+    }
+  
+  return 0;
+}
+
+/* Return non-zero if IN contains a piece of rtl that has the address LOC */
+int
+loc_mentioned_in_p (loc, in)
+     rtx *loc, in;
+{
+  enum rtx_code code = GET_CODE (in);
+  const char *fmt = GET_RTX_FORMAT (code);
+  int i, j;
+
+  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+    {
+      if (loc == &in->fld[i].rtx)
+       return 1;
+      if (fmt[i] == 'e')
+       {
+         if (loc_mentioned_in_p (loc, XEXP (in, i)))
+           return 1;
+       }
+      else if (fmt[i] == 'E')
+       for (j = XVECLEN (in, i) - 1; j >= 0; j--)
+         if (loc_mentioned_in_p (loc, XVECEXP (in, i, j)))
+           return 1;
+    }
+  return 0;
+}
+
+/* Given a subreg X, return the bit offset where the subreg begins
+   (counting from the least significant bit of the reg).  */
+
+unsigned int
+subreg_lsb (x)
+     rtx x;
+{
+  enum machine_mode inner_mode = GET_MODE (SUBREG_REG (x));
+  enum machine_mode mode = GET_MODE (x);
+  unsigned int bitpos;
+  unsigned int byte;
+  unsigned int word;
+
+  /* A paradoxical subreg begins at bit position 0.  */
+  if (GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (inner_mode))
+    return 0;
+
+  if (WORDS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
+    /* If the subreg crosses a word boundary ensure that
+       it also begins and ends on a word boundary.  */
+    if ((SUBREG_BYTE (x) % UNITS_PER_WORD
+        + GET_MODE_SIZE (mode)) > UNITS_PER_WORD
+       && (SUBREG_BYTE (x) % UNITS_PER_WORD
+           || GET_MODE_SIZE (mode) % UNITS_PER_WORD))
+       abort ();
+
+  if (WORDS_BIG_ENDIAN)
+    word = (GET_MODE_SIZE (inner_mode)
+           - (SUBREG_BYTE (x) + GET_MODE_SIZE (mode))) / UNITS_PER_WORD;
+  else
+    word = SUBREG_BYTE (x) / UNITS_PER_WORD;
+  bitpos = word * BITS_PER_WORD;
+
+  if (BYTES_BIG_ENDIAN)
+    byte = (GET_MODE_SIZE (inner_mode)
+           - (SUBREG_BYTE (x) + GET_MODE_SIZE (mode))) % UNITS_PER_WORD;
+  else
+    byte = SUBREG_BYTE (x) % UNITS_PER_WORD;
+  bitpos += byte * BITS_PER_UNIT;
+
+  return bitpos;
+}
+
+/* This function returns the regno offset of a subreg expression.
+   xregno - A regno of an inner hard subreg_reg (or what will become one).
+   xmode  - The mode of xregno.
+   offset - The byte offset.
+   ymode  - The mode of a top level SUBREG (or what may become one).
+   RETURN - The regno offset which would be used.  */
+unsigned int
+subreg_regno_offset (xregno, xmode, offset, ymode)
+     unsigned int xregno;
+     enum machine_mode xmode;
+     unsigned int offset;
+     enum machine_mode ymode;
+{
+  int nregs_xmode, nregs_ymode;
+  int mode_multiple, nregs_multiple;
+  int y_offset;
+
+  if (xregno >= FIRST_PSEUDO_REGISTER)
+    abort ();
+
+  nregs_xmode = HARD_REGNO_NREGS (xregno, xmode);
+  nregs_ymode = HARD_REGNO_NREGS (xregno, ymode);
+  if (offset == 0 || nregs_xmode == nregs_ymode)
+    return 0;
+  
+  /* size of ymode must not be greater than the size of xmode.  */
+  mode_multiple = GET_MODE_SIZE (xmode) / GET_MODE_SIZE (ymode);
+  if (mode_multiple == 0)
+    abort ();
+
+  y_offset = offset / GET_MODE_SIZE (ymode);
+  nregs_multiple =  nregs_xmode / nregs_ymode;
+  return (y_offset / (mode_multiple / nregs_multiple)) * nregs_ymode;
+}
+
+/* Return the final regno that a subreg expression refers to.  */
+unsigned int 
+subreg_regno (x)
+     rtx x;
+{
+  unsigned int ret;
+  rtx subreg = SUBREG_REG (x);
+  int regno = REGNO (subreg);
+
+  ret = regno + subreg_regno_offset (regno, 
+                                    GET_MODE (subreg), 
+                                    SUBREG_BYTE (x),
+                                    GET_MODE (x));
+  return ret;
+
+}
+struct parms_set_data
+{
+  int nregs;
+  HARD_REG_SET regs;
+};
+
+/* Helper function for noticing stores to parameter registers.  */
+static void
+parms_set (x, pat, data)
+       rtx x, pat ATTRIBUTE_UNUSED;
+       void *data;
+{
+  struct parms_set_data *d = data;
+  if (REG_P (x) && REGNO (x) < FIRST_PSEUDO_REGISTER
+      && TEST_HARD_REG_BIT (d->regs, REGNO (x)))
+    {
+      CLEAR_HARD_REG_BIT (d->regs, REGNO (x));
+      d->nregs--;
+    }
+}
+
+/* Look backward for first parameter to be loaded.  
+   Do not skip BOUNDARY.  */
+rtx
+find_first_parameter_load (call_insn, boundary)
+     rtx call_insn, boundary;
+{
+  struct parms_set_data parm;
+  rtx p, before;
+
+  /* Since different machines initialize their parameter registers
+     in different orders, assume nothing.  Collect the set of all
+     parameter registers.  */
+  CLEAR_HARD_REG_SET (parm.regs);
+  parm.nregs = 0;
+  for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1))
+    if (GET_CODE (XEXP (p, 0)) == USE
+       && GET_CODE (XEXP (XEXP (p, 0), 0)) == REG)
+      {
+       if (REGNO (XEXP (XEXP (p, 0), 0)) >= FIRST_PSEUDO_REGISTER)
+         abort ();
+
+       /* We only care about registers which can hold function
+          arguments.  */
+       if (!FUNCTION_ARG_REGNO_P (REGNO (XEXP (XEXP (p, 0), 0))))
+         continue;
+
+       SET_HARD_REG_BIT (parm.regs, REGNO (XEXP (XEXP (p, 0), 0)));
+       parm.nregs++;
+      }
+  before = call_insn;
+
+  /* Search backward for the first set of a register in this set.  */
+  while (parm.nregs && before != boundary)
+    {
+      before = PREV_INSN (before);
+
+      /* It is possible that some loads got CSEed from one call to
+         another.  Stop in that case.  */
+      if (GET_CODE (before) == CALL_INSN)
+       break;
+
+      /* Our caller needs either ensure that we will find all sets
+         (in case code has not been optimized yet), or take care
+         for possible labels in a way by setting boundary to preceding
+         CODE_LABEL.  */
+      if (GET_CODE (before) == CODE_LABEL)
+       {
+         if (before != boundary)
+           abort ();
+         break;
+       }
+
+      if (INSN_P (before))
+        note_stores (PATTERN (before), parms_set, &parm);
+    }
+  return before;
+}
+
+/* Return true if we should avoid inserting code between INSN and preceeding
+   call instruction.  */
+
+bool
+keep_with_call_p (insn)
+     rtx insn;
+{
+  rtx set;
+
+  if (INSN_P (insn) && (set = single_set (insn)) != NULL)
+    {
+      if (GET_CODE (SET_DEST (set)) == REG
+         && fixed_regs[REGNO (SET_DEST (set))]
+         && general_operand (SET_SRC (set), VOIDmode))
+       return true;
+      if (GET_CODE (SET_SRC (set)) == REG
+         && FUNCTION_VALUE_REGNO_P (REGNO (SET_SRC (set)))
+         && GET_CODE (SET_DEST (set)) == REG
+         && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
+       return true;
+      /* There may be a stack pop just after the call and before the store
+        of the return register.  Search for the actual store when deciding
+        if we can break or not.  */
+      if (SET_DEST (set) == stack_pointer_rtx)
+       {
+         rtx i2 = next_nonnote_insn (insn);
+         if (i2 && keep_with_call_p (i2))
+           return true;
+       }
+    }
+  return false;
+}