RFA: DSE replace_read revisited

RFA: DSE replace_read revisited

[Richard Sandiford]

A few weeks ago, I posted a patch to fix some problems in the
new RTL DSE replace_read code:

    http://gcc.gnu.org/ml/gcc-patches/2007-09/msg01316.html

However, I found that the testcase added there still fails for some
MIPS targets, and investigating that led me to some wrong-code and
pessimisation issues too.  There seem to be several problems:

  (1) As I complained about in the message above, find_shift_sequence
      does the shift in the mode class of the stored value, rather than
      MODE_INT.  So if we have a V4HI store and a V2HI read (say), we'd
      use a vector shift rather than an integer shift.  We'd therefore
      shift the individual HI elements right, rather than shift the
      whole bit pattern.

  (2) When reading the low end of a stored value, the original code used
      gen_lowpart to do the mode punning:

        emit_move_insn (read_reg, gen_lowpart (read_mode, store_info->rhs));

      This ICEd when a DFmode store was followed by an SFmode move, as in:

        union u { double d; float f[2]; };

        float
        foo (union u *u, double d)
        {
          u->d = d;
          return u->f[1];
        }

      for big-endian targets, because SFmode subregs of DFmode values
      are not allowed.  My attempt to fix the integer cases for MIPS
      meant that we'd now convert the DFmode value into SFmode instead,
      which is of course also wrong.

      (Although this particular example isn't very realistic,
      the equivalent TFmode/DFmode one matters for targets with
      IEEE long doubles.)

  (3) The code triggers for cases where it is a pessimisation.
      E.g. on hard-float MIPS targets, if a DFmode value is stored in
      an FPR (as we hope most DFmode values are), we cannot directly
      treat the low part as an SFmode value.  The sequence generated
      for a lowpart would involve a move into and then out of integer
      registers, and it would have been better to keep the original load.

      However, on soft-float MIPS targets, replacing an SFmode load
      of a DFmode store is the right thing to do.

  (4) The code requires the store and read to have the same mode class:

        if (GET_MODE_CLASS (read_mode) != GET_MODE_CLASS (store_mode))
          return false;

      This seems unnecessarily restrictive.  I guess it was meant to
      be a simplifying assumption, but as per (1) and (2) above,
      it isn't really.

  (5) The shift case can't deal with floats, even though it would be
      profitable to do so on some soft-float targets.

  (6) The code only deals with REGs:

        if (store_info->is_set 
            /* No place to keep the value after ra.  */
            && !reload_completed
            /* The careful reviewer may wish to comment my checking that the
               rhs of a store is always a reg.  */
            && REG_P (SET_SRC (body))
            /* Sometimes the store and reload is used for truncation and
              rounding.  */
            && !(FLOAT_MODE_P (GET_MODE (mem)) && (flag_float_store)))

      This does indeed seem unnecessarily restrictive, and is the cause of
      the dse-1.c failures that led me here originally.  The code could
      easily handle subregs and constants as well.

Addressing (1)-(5) together, I think part of the problem is that the
code has too many special exceptions.  From a high-level perspective,
I think we need two things:

  (a) a way of telling whether a mode change is profitable

  (b) a way of extracting the low bits of a value of one arbitrary mode
      into a value of another arbitrary mode

(a) we already have in the form of MODES_TIEABLE_P.  So rather than
check whether the two modes are the same class, I think we should check
whether each individual mode change we make is profitable accordingly to
MODES_TIEABLE_P.

(b) we don't have (AFAIK), so I added a new routine called extract_low_bits.
Quoting the function's comment:

   Try to read the low bits of SRC as an rvalue of mode MODE, preserving
   the bit pattern.  SRC_MODE is the mode of SRC; if this is smaller than
   MODE, fill the upper bits with zeros.  Fail if the layout of either
   mode is unknown (as for CC modes) or if the extraction would involve
   unprofitable mode punning.  Return the value on success, otherwise
   return null.

   This is different from gen_lowpart* in these respects:

     - the returned value must always be considered an rvalue

     - when MODE is wider than SRC_MODE, the extraction involves
       a zero extension

     - when MODE is smaller than SRC_MODE, the extraction involves
       a truncation (and is thus subject to TRULY_NOOP_TRUNCATION).

   In other words, this routine performs a computation, whereas the
   gen_lowpart* routines are conceptually lvalue or rvalue subreg
   operations.

We don't need the extension case for DSE -- MODE is never bigger than
SRC_MODE -- but it falls out of the wash.  We might one day need to do
something like this even if the extraction _would_ involve unprofitable
mode punning; not in DSE, but elsewhere.  If that happens, we can always
add a parameter to control the check.

The patch below therefore:

  - allows the two modes to have different classes, fixing (4)

  - allows the stored value to be a SUBREG or a constant, fixing (6)

  - always does the shift in MODE_INT, fixing (1)

  - makes find_shift_sequence iterate on the shift mode rather than
    access_size, which is more efficient and IMO a little clearer

  - uses MODES_TIEABLE_P to decide whether it is profitable to convert
    the stored value into the shift mode

  - uses gen_simplify_subreg to convert the stored value into the shift
    mode; this is a paradoxical subreg operation, and is allowed to
    fail if the mode change is not valid

  - uses extract_low_bits to convert the shifted value into the read value

  - uses extract_low_bits to convert the store value into the read value
    when no shift is needed, fixing (2) and (3)

  - removes:

      if (access_size > UNITS_PER_WORD || FLOAT_MODE_P (store_mode))
        return false;

    the first check is redundant with find_shift_sequence and removing
    the second fixes (4)

  - computes the nonshift sequence as well as the shift sequence
    before trying the replacement, since the nonshift sequence
    can now fail as well.

FWIW, I tested the patch on CSiBE for mipsisa64-elf at -Os.
The results were:

jikespg:src/spacetab                             21540    21532 :   99.96%
jikespg:src/produce                              12664    12640 :   99.81%
jikespg:src/mkfirst                              17024    17012 :   99.93%
jikespg:src/remsp                                 9036     9024 :   99.87%
libmspack:test/md5                                4812     4808 :   99.92%
linux:kernel/sched                                5992     5988 :   99.93%
lwip:src/core/tcp_output                          3284     3272 :   99.63%
OpenTCP:tcp                                       7230     7242 :  100.17%
teem:src/limn/cam                                 3780     3772 :   99.79%
teem:src/dye/methodsDye                           2844     2820 :   99.16%
teem:src/gage/sclanswer                           4692     4684 :   99.83%
unrarlib:unrarlib/unrarlib                       15672    15676 :  100.03%
zlib:deflate                                      8460     8464 :  100.05%
----------------------------------------------------------------
Total                                          3605989  3605893 :  100.00%

The three increases are due to cases in which we convert a sign-extending
SImode load into a register extension; the former is a single instruction
whereas the latter takes two.  This is something that DSE could do for
REG arguments even before the patch, and it might suggest that we need
to check whether the new instruction is more expensive than the old.
However, the MIPS port gives the two instructions the same cost anyway,
even for -Os, so it wouldn't make any difference as things stand.

I'm afraid that giving a load or store a cost of 1 instruction will lead
to some silly optimisation decisions.  It might be worthwhile if we've
being very aggressive about optimising for size (as is usually the case
for MIPS16) but it seems dangerous otherwise.  I'm therefore not too
worried about the three extra instructions, given that the net saving
is much higher.

The TCP increase is 3 instructions rather than 1 because of a missed
SIGN_EXTEND optimisation in simplify-rtx.c.  I have a separate patch
for that, but I'm not convinced it's stage 3 material.

Bootstrapped & regression-tested on x86_64-linux-gnu.  Also
regression-tested on mipsisa64-elf and mipsisa32-elf, fixing
dse-1.c for the former.  I've added a case that shows why
handling constants is worthwhile.  OK to install?

Richard


gcc/
	* Makefile.in (dse.o): Depend on $(TM_P_H).
	* optabs.h (extract_low_bits): Declare.
	* optabs.c (extract_low_bits): New function.
	* rtlhooks.c (gen_lowpart_general): Generalize SUBREG handling.
	* dse.c: Include tm_p.h.
	(find_shift_sequence): Remove the read_reg argument and return the
	read value.  Emit the instructions instead of returning them.
	Iterate on new_mode rather than calculating it each time.
	Check MODES_TIEABLE_P.  Use simplify_gen_subreg to convert the
	source to NEW_MODE and extract_low_bits to convert the shifted
	value to READ_MODE.
	(replace_read): Allow the load and store to have different mode
	classes.  Use extract_low_bits when SHIFT == 0.  Create the shift
	or extraction instructions before trying the replacement.  Update
	dump-file code accordingly, avoiding use of REGNO (store_info->rhs).

gcc/testsuite/
	* gcc.target/mips/dse-1.c: Add checks for zeros.

Index: gcc/Makefile.in
===================================================================
--- gcc/Makefile.in	2007-10-27 09:25:22.000000000 +0100
+++ gcc/Makefile.in	2007-10-27 09:34:07.000000000 +0100
@@ -2537,8 +2537,8 @@ dce.o : dce.c $(CONFIG_H) $(SYSTEM_H) co
    $(TREE_H) $(REGS_H) hard-reg-set.h $(FLAGS_H) $(DF_H) cselib.h \
    $(DBGCNT_H) dce.h timevar.h tree-pass.h $(DBGCNT_H)
 dse.o : dse.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
-   $(TREE_H) $(REGS_H) hard-reg-set.h $(FLAGS_H) insn-config.h $(RECOG_H) \
-   $(EXPR_H) $(DF_H) cselib.h $(DBGCNT_H) timevar.h tree-pass.h \
+   $(TREE_H) $(TM_P_H) $(REGS_H) hard-reg-set.h $(FLAGS_H) insn-config.h \
+   $(RECOG_H) $(EXPR_H) $(DF_H) cselib.h $(DBGCNT_H) timevar.h tree-pass.h \
    alloc-pool.h $(ALIAS_H) dse.h
 fwprop.o : fwprop.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
    toplev.h insn-config.h $(RECOG_H) $(FLAGS_H) $(OBSTACK_H) $(BASIC_BLOCK_H) \
Index: gcc/optabs.h
===================================================================
--- gcc/optabs.h	2007-10-27 09:25:22.000000000 +0100
+++ gcc/optabs.h	2007-10-27 09:34:07.000000000 +0100
@@ -770,6 +770,8 @@ extern rtx expand_vec_cond_expr (tree, r
 /* Generate code for VEC_LSHIFT_EXPR and VEC_RSHIFT_EXPR.  */
 extern rtx expand_vec_shift_expr (tree, rtx);
 
+extern rtx extract_low_bits (enum machine_mode, enum machine_mode, rtx);
+
 #define optab_handler(optab,mode) (&(optab)->handlers[(int) (mode)])
 #define convert_optab_handler(optab,mode,mode2) \
 	(&(optab)->handlers[(int) (mode)][(int) (mode2)])
Index: gcc/optabs.c
===================================================================
--- gcc/optabs.c	2007-10-27 09:25:22.000000000 +0100
+++ gcc/optabs.c	2007-10-28 09:26:43.000000000 +0000
@@ -4984,6 +4984,58 @@ gen_move_insn (rtx x, rtx y)
   end_sequence ();
   return seq;
 }
+
+/* Try to read the low bits of SRC as an rvalue of mode MODE, preserving
+   the bit pattern.  SRC_MODE is the mode of SRC; if this is smaller than
+   MODE, fill the upper bits with zeros.  Fail if the layout of either
+   mode is unknown (as for CC modes) or if the extraction would involve
+   unprofitable mode punning.  Return the value on success, otherwise
+   return null.
+
+   This is different from gen_lowpart* in these respects:
+
+     - the returned value must always be considered an rvalue
+
+     - when MODE is wider than SRC_MODE, the extraction involves
+       a zero extension
+
+     - when MODE is smaller than SRC_MODE, the extraction involves
+       a truncation (and is thus subject to TRULY_NOOP_TRUNCATION).
+
+   In other words, this routine performs a computation, whereas the
+   gen_lowpart* routines are conceptually lvalue or rvalue subreg
+   operations.  */
+
+rtx
+extract_low_bits (enum machine_mode mode, enum machine_mode src_mode, rtx src)
+{
+  enum machine_mode int_mode, src_int_mode;
+
+  if (mode == src_mode)
+    return src;
+
+  if (CONSTANT_P (src))
+    return simplify_gen_subreg (mode, src, src_mode,
+				subreg_lowpart_offset (mode, src_mode));
+
+  if (GET_MODE_CLASS (mode) == MODE_CC || GET_MODE_CLASS (src_mode) == MODE_CC)
+    return NULL_RTX;
+
+  src_int_mode = int_mode_for_mode (src_mode);
+  int_mode = int_mode_for_mode (mode);
+  if (src_int_mode == BLKmode || int_mode == BLKmode)
+    return NULL_RTX;
+
+  if (!MODES_TIEABLE_P (src_int_mode, src_mode))
+    return NULL_RTX;
+  if (!MODES_TIEABLE_P (int_mode, mode))
+    return NULL_RTX;
+
+  src = gen_lowpart (src_int_mode, src);
+  src = convert_modes (int_mode, src_int_mode, src, true);
+  src = gen_lowpart (mode, src);
+  return src;
+}
 \f
 /* Return the insn code used to extend FROM_MODE to TO_MODE.
    UNSIGNEDP specifies zero-extension instead of sign-extension.  If
Index: gcc/rtlhooks.c
===================================================================
--- gcc/rtlhooks.c	2007-10-27 09:25:22.000000000 +0100
+++ gcc/rtlhooks.c	2007-10-27 09:34:07.000000000 +0100
@@ -43,11 +43,9 @@ gen_lowpart_general (enum machine_mode m
 
   if (result)
     return result;
-  /* If it's a REG, it must be a hard reg that's not valid in MODE.  */
-  else if (REG_P (x)
-	   /* Or we could have a subreg of a floating point value.  */
-	   || (GET_CODE (x) == SUBREG
-	       && FLOAT_MODE_P (GET_MODE (SUBREG_REG (x)))))
+  /* Handle SUBREGs and hard REGs that were rejected by
+     simplify_gen_subreg.  */
+  else if (REG_P (x) || GET_CODE (x) == SUBREG)
     {
       result = gen_lowpart_common (mode, copy_to_reg (x));
       gcc_assert (result != 0);
Index: gcc/dse.c
===================================================================
--- gcc/dse.c	2007-10-27 09:25:22.000000000 +0100
+++ gcc/dse.c	2007-10-27 09:34:07.000000000 +0100
@@ -29,6 +29,7 @@ Software Foundation; either version 3, o
 #include "tm.h"
 #include "rtl.h"
 #include "tree.h"
+#include "tm_p.h"
 #include "regs.h"
 #include "hard-reg-set.h"
 #include "flags.h"
@@ -1381,9 +1382,9 @@ record_store (rtx body, bb_info_t bb_inf
   if (store_info->is_set 
       /* No place to keep the value after ra.  */
       && !reload_completed
-      /* The careful reviewer may wish to comment my checking that the
-	 rhs of a store is always a reg.  */
-      && REG_P (SET_SRC (body))
+      && (REG_P (SET_SRC (body))
+	  || GET_CODE (SET_SRC (body)) == SUBREG
+	  || CONSTANT_P (SET_SRC (body)))
       /* Sometimes the store and reload is used for truncation and
 	 rounding.  */
       && !(FLOAT_MODE_P (GET_MODE (mem)) && (flag_float_store)))
@@ -1416,15 +1417,15 @@ dump_insn_info (const char * start, insn
    shift.  */
 
 static rtx
-find_shift_sequence (rtx read_reg,
-		     int access_size,
+find_shift_sequence (int access_size,
 		     store_info_t store_info,
 		     read_info_t read_info,
 		     int shift)
 {
   enum machine_mode store_mode = GET_MODE (store_info->mem);
   enum machine_mode read_mode = GET_MODE (read_info->mem);
-  rtx chosen_seq = NULL;
+  enum machine_mode new_mode;
+  rtx read_reg = NULL;
 
   /* Some machines like the x86 have shift insns for each size of
      operand.  Other machines like the ppc or the ia-64 may only have
@@ -1433,21 +1434,31 @@ find_shift_sequence (rtx read_reg,
      justify the value we want to read but is available in one insn on
      the machine.  */
 
-  for (; access_size <= UNITS_PER_WORD; access_size *= 2)
+  for (new_mode = smallest_mode_for_size (access_size * BITS_PER_UNIT,
+					  MODE_INT);
+       GET_MODE_BITSIZE (new_mode) <= BITS_PER_WORD;
+       new_mode = GET_MODE_WIDER_MODE (new_mode))
     {
-      rtx target, new_reg, shift_seq, insn;
-      enum machine_mode new_mode;
+      rtx target, new_reg, shift_seq, insn, new_lhs;
       int cost;
 
-      /* Try a wider mode if truncating the store mode to ACCESS_SIZE
-	 bytes requires a real instruction.  */
-      if (access_size < GET_MODE_SIZE (store_mode)
-	  && !TRULY_NOOP_TRUNCATION (access_size * BITS_PER_UNIT,
+      /* Try a wider mode if truncating the store mode to NEW_MODE
+	 requires a real instruction.  */
+      if (GET_MODE_BITSIZE (new_mode) < GET_MODE_BITSIZE (store_mode)
+	  && !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (new_mode),
 				     GET_MODE_BITSIZE (store_mode)))
 	continue;
 
-      new_mode = smallest_mode_for_size (access_size * BITS_PER_UNIT,
-					 GET_MODE_CLASS (read_mode));
+      /* Also try a wider mode if the necessary punning is either not
+	 desirable or not possible.  */
+      if (!CONSTANT_P (store_info->rhs)
+	  && !MODES_TIEABLE_P (new_mode, store_mode))
+	continue;
+      new_lhs = simplify_gen_subreg (new_mode, copy_rtx (store_info->rhs),
+				     store_mode, 0);
+      if (new_lhs == NULL_RTX)
+	continue;
+
       new_reg = gen_reg_rtx (new_mode);
 
       start_sequence ();
@@ -1484,31 +1495,13 @@ find_shift_sequence (rtx read_reg,
 	 take the value from the store and put it into the
 	 shift pseudo, then shift it, then generate another
 	 move to put in into the target of the read.  */
-      start_sequence ();
-      emit_move_insn (new_reg, gen_lowpart (new_mode, store_info->rhs));
+      emit_move_insn (new_reg, new_lhs);
       emit_insn (shift_seq);
-      convert_move (read_reg, new_reg, 1);
-		  
-      if (dump_file)
-	{
-	  fprintf (dump_file, " -- adding extract insn r%d:%s = r%d:%s\n",
-		   REGNO (new_reg), GET_MODE_NAME (new_mode),
-		   REGNO (store_info->rhs), GET_MODE_NAME (store_mode));
-		      
-	  fprintf (dump_file, " -- with shift of r%d by %d\n",
-		   REGNO(new_reg), shift);
-	  fprintf (dump_file, " -- and second extract insn r%d:%s = r%d:%s\n",
-		   REGNO (read_reg), GET_MODE_NAME (read_mode),
-		   REGNO (new_reg), GET_MODE_NAME (new_mode));
-	}
-		  
-      /* Get the three insn sequence and return it.  */
-      chosen_seq = get_insns ();
-      end_sequence ();
+      read_reg = extract_low_bits (read_mode, new_mode, new_reg);
       break;
     }
 
-  return chosen_seq;
+  return read_reg;
 }
 
 
@@ -1551,15 +1544,11 @@ replace_read (store_info_t store_info, i
   enum machine_mode read_mode = GET_MODE (read_info->mem);
   int shift;
   int access_size; /* In bytes.  */
-  rtx read_reg = gen_reg_rtx (read_mode);
-  rtx shift_seq = NULL;
+  rtx insns, read_reg;
 
   if (!dbg_cnt (dse))
     return false;
 
-  if (GET_MODE_CLASS (read_mode) != GET_MODE_CLASS (store_mode))
-    return false;
-
   /* To get here the read is within the boundaries of the write so
      shift will never be negative.  Start out with the shift being in
      bytes.  */
@@ -1573,62 +1562,43 @@ replace_read (store_info_t store_info, i
   /* From now on it is bits.  */
   shift *= BITS_PER_UNIT;
 
-  /* We need to keep this in perspective.  We are replacing a read
+  /* Create a sequence of instructions to set up the read register.
+     This sequence goes immediately before the store and its result
+     is read by the load.
+
+     We need to keep this in perspective.  We are replacing a read
      with a sequence of insns, but the read will almost certainly be
      in cache, so it is not going to be an expensive one.  Thus, we
      are not willing to do a multi insn shift or worse a subroutine
      call to get rid of the read.  */
+  if (dump_file)
+    fprintf (dump_file, "trying to replace %smode load in insn %d"
+	     " from %smode store in insn %d\n",
+	     GET_MODE_NAME (read_mode), INSN_UID (read_insn->insn),
+	     GET_MODE_NAME (store_mode), INSN_UID (store_insn->insn));
+  start_sequence ();
   if (shift)
+    read_reg = find_shift_sequence (access_size, store_info, read_info, shift);
+  else
+    read_reg = extract_low_bits (read_mode, store_mode,
+				 copy_rtx (store_info->rhs));
+  if (read_reg == NULL_RTX)
     {
-      if (access_size > UNITS_PER_WORD || FLOAT_MODE_P (store_mode))
-	return false;
-
-      shift_seq = find_shift_sequence (read_reg, access_size, store_info,
-				       read_info, shift);
-      if (!shift_seq)
-	return false;
+      end_sequence ();
+      if (dump_file)
+	fprintf (dump_file, " -- could not extract bits of stored value\n");
+      return false;
     }
-
-  if (dump_file)
-    fprintf (dump_file, "replacing load at %d from store at %d\n",
-	     INSN_UID (read_insn->insn), INSN_UID (store_insn->insn)); 
+  /* Force the value into a new register so that it won't be clobbered
+     between the store and the load.  */
+  read_reg = copy_to_mode_reg (read_mode, read_reg);
+  insns = get_insns ();
+  end_sequence ();
 
   if (validate_change (read_insn->insn, loc, read_reg, 0))
     {
-      rtx insns;
       deferred_change_t deferred_change = pool_alloc (deferred_change_pool);
       
-      if (read_mode == store_mode)
-	{
-	  start_sequence ();
-	  
-	  /* The modes are the same and everything lines up.  Just
-	     generate a simple move.  */
-	  emit_move_insn (read_reg, store_info->rhs);
-	  if (dump_file)
-	    fprintf (dump_file, " -- adding move insn r%d = r%d\n",
-		     REGNO (read_reg), REGNO (store_info->rhs));
-	  insns = get_insns ();
-	  end_sequence ();
-	}
-      else if (shift)
-	insns = shift_seq;
-      else
-	{
-	  /* The modes are different but the lsb are in the same
-	     place, we need to extract the value in the right from the
-	     rhs of the store.  */
-	  start_sequence ();
-	  convert_move (read_reg, store_info->rhs, 1);
-	  
-	  if (dump_file)
-	    fprintf (dump_file, " -- adding extract insn r%d:%s = r%d:%s\n",
-		     REGNO (read_reg), GET_MODE_NAME (read_mode),
-		     REGNO (store_info->rhs), GET_MODE_NAME (store_mode));
-	  insns = get_insns ();
-	  end_sequence ();
-	}
-
       /* Insert this right before the store insn where it will be safe
 	 from later insns that might change it before the read.  */
       emit_insn_before (insns, store_insn->insn);
@@ -1666,12 +1636,22 @@ replace_read (store_info_t store_info, i
 	 rest of dse, play like this read never happened.  */
       read_insn->read_rec = read_info->next;
       pool_free (read_info_pool, read_info);
+      if (dump_file)
+	{
+	  fprintf (dump_file, " -- replaced the loaded MEM with ");
+	  print_simple_rtl (dump_file, read_reg);
+	  fprintf (dump_file, "\n");
+	}
       return true;
     }
   else 
     {
       if (dump_file)
-	fprintf (dump_file, " -- validation failure\n"); 
+	{
+	  fprintf (dump_file, " -- replacing the loaded MEM with ");
+	  print_simple_rtl (dump_file, read_reg);
+	  fprintf (dump_file, " led to an invalid instruction\n");
+	}
       return false;
     }
 }
Index: gcc/testsuite/gcc.target/mips/dse-1.c
===================================================================
--- gcc/testsuite/gcc.target/mips/dse-1.c	2007-10-27 09:25:22.000000000 +0100
+++ gcc/testsuite/gcc.target/mips/dse-1.c	2007-10-27 09:34:07.000000000 +0100
@@ -14,6 +14,13 @@ #define TEST(ID, TYPE1, TYPE2)					\
     u->m2 = x;							\
     return (u->m1[0]						\
 	    + u->m1[sizeof (TYPE2) / sizeof (TYPE1) - 1]);	\
+  }								\
+								\
+  TYPE1 __attribute__((nomips16))				\
+  g##ID (union u##ID *u)					\
+  {								\
+    u->m2 = 0;							\
+    return (u->m1[0] | u->m1[1]);				\
   }
 
 TEST (1, unsigned int, unsigned long long);

Re: RFA: DSE replace_read revisited

[Andrew Pinski]

On 10/28/07, Richard Sandiford <rsandifo@nildram.co.uk> wrote:
>   (4) The code requires the store and read to have the same mode class:
>
>         if (GET_MODE_CLASS (read_mode) != GET_MODE_CLASS (store_mode))
>           return false;
>
>       This seems unnecessarily restrictive.  I guess it was meant to
>       be a simplifying assumption, but as per (1) and (2) above,
>       it isn't really.

Does this part fix PR 33927 where we have V4SI and V4SF?

Thanks,
Andrew Pinski

Re: RFA: DSE replace_read revisited

[Richard Sandiford]

"Andrew Pinski" <pinskia@gmail.com> writes:
> On 10/28/07, Richard Sandiford <rsandifo@nildram.co.uk> wrote:
>>   (4) The code requires the store and read to have the same mode class:
>>
>>         if (GET_MODE_CLASS (read_mode) != GET_MODE_CLASS (store_mode))
>>           return false;
>>
>>       This seems unnecessarily restrictive.  I guess it was meant to
>>       be a simplifying assumption, but as per (1) and (2) above,
>>       it isn't really.
>
> Does this part fix PR 33927 where we have V4SI and V4SF?

It should, subject to MODES_TIEABLE_P allowing the necessary mode changes
(to and from TImode in this case).

It appears from validate_subreg that direct subregs between V4SI and
V4SF are allowed, so we could also add an extra case to extract_low_bits:

  if (GET_MODE_BITSIZE (mode) == GET_MODE_BITSIZE (src_mode)
      && MODES_TIEABLE_P (mode, src_mode))
    {
      rtx x = gen_lowpart (mode, src);
      if (x)
        return x;
    }

Someone with access to powerpc64-linux-gnu or spu-elf might like
to try that.

Richard

Re: RFA: DSE replace_read revisited

[Richard Sandiford]

Richard Sandiford <rsandifo@nildram.co.uk> writes:
>   (2) When reading the low end of a stored value, the original code used
>       gen_lowpart to do the mode punning:
>
>         emit_move_insn (read_reg, gen_lowpart (read_mode, store_info->rhs));
>
>       This ICEd when a DFmode store was followed by an SFmode move, as in:
>
>         union u { double d; float f[2]; };
>
>         float
>         foo (union u *u, double d)
>         {
>           u->d = d;
>           return u->f[1];
>         }
>
>       for big-endian targets, because SFmode subregs of DFmode values
>       are not allowed.  My attempt to fix the integer cases for MIPS
>       meant that we'd now convert the DFmode value into SFmode instead,
>       which is of course also wrong.
>
>       (Although this particular example isn't very realistic,
>       the equivalent TFmode/DFmode one matters for targets with
>       IEEE long doubles.)

Er, I did of course mean IBM long doubles here...

Richard

Re: RFA: DSE replace_read revisited

[Richard Sandiford]

Richard Sandiford <rsandifo@nildram.co.uk> writes:
> "Andrew Pinski" <pinskia@gmail.com> writes:
>> On 10/28/07, Richard Sandiford <rsandifo@nildram.co.uk> wrote:
>>>   (4) The code requires the store and read to have the same mode class:
>>>
>>>         if (GET_MODE_CLASS (read_mode) != GET_MODE_CLASS (store_mode))
>>>           return false;
>>>
>>>       This seems unnecessarily restrictive.  I guess it was meant to
>>>       be a simplifying assumption, but as per (1) and (2) above,
>>>       it isn't really.
>>
>> Does this part fix PR 33927 where we have V4SI and V4SF?
>
> It should, subject to MODES_TIEABLE_P allowing the necessary mode changes
> (to and from TImode in this case).
>
> It appears from validate_subreg that direct subregs between V4SI and
> V4SF are allowed, so we could also add an extra case to extract_low_bits:
>
>   if (GET_MODE_BITSIZE (mode) == GET_MODE_BITSIZE (src_mode)
>       && MODES_TIEABLE_P (mode, src_mode))
>     {
>       rtx x = gen_lowpart (mode, src);
>       if (x)
>         return x;
>     }

Sorry, this should have been gen_lowpart_common, not gen_lowpart.

Richard

Re: RFA: DSE replace_read revisited

[Paolo Bonzini]

> The TCP increase is 3 instructions rather than 1 because of a missed
> SIGN_EXTEND optimisation in simplify-rtx.c.  I have a separate patch
> for that, but I'm not convinced it's stage 3 material.

It might be worth submitting anyway, since it is in some sense a regression.

Paolo

Re: RFA: DSE replace_read revisited

[Richard Sandiford]

Paolo Bonzini <bonzini@gnu.org> writes:
>> The TCP increase is 3 instructions rather than 1 because of a missed
>> SIGN_EXTEND optimisation in simplify-rtx.c.  I have a separate patch
>> for that, but I'm not convinced it's stage 3 material.
>
> It might be worth submitting anyway, since it is in some sense a regression.

Yeah, I suppose it is.  You might have seen it by now, but I ended up
posting it for comments:

    http://gcc.gnu.org/ml/gcc-patches/2007-10/msg01667.html

Do you think it's OK, and safe enough under the circumstances?

Richard

Re: RFA: DSE replace_read revisited

[Paolo Bonzini]

[-- Attachment #1: Type: text/plain, Size: 431 bytes --]


>     http://gcc.gnu.org/ml/gcc-patches/2007-10/msg01667.html
> 
> Do you think it's OK

Except for using gen_lowpart_no_emit instead of gen_lowpart_common, yes.

BTW, do you know the circumstances under which you get a subreg/s/v?  It 
seems like dead code to me and the attached patch bootstraps.

> , and safe enough under the circumstances?

Probably, though a small C test case would help judging its importance, too.

Paolo

[-- Attachment #2: no-subreg-v.patch --]
[-- Type: text/plain, Size: 875 bytes --]

Index: gcc-test/peak-gcc-src/gcc/rtl.h
===================================================================
--- gcc-test/peak-gcc-src/gcc/rtl.h	(revision 129768)
+++ gcc-test/peak-gcc-src/gcc/rtl.h	(working copy)
@@ -1085,7 +1085,7 @@ extern bool truncated_to_mode (enum mach
 do {									\
   rtx const _rtx = RTL_FLAG_CHECK1("SUBREG_PROMOTED_UNSIGNED_SET", (RTX), SUBREG); \
   if ((VAL) < 0)							\
-    _rtx->volatil = 1;							\
+    gcc_unreachable ();							\
   else {								\
     _rtx->volatil = 0;							\
     _rtx->unchanging = (VAL);						\
@@ -1093,7 +1093,7 @@ do {									\
 } while (0)
 #define SUBREG_PROMOTED_UNSIGNED_P(RTX)	\
   ((RTL_FLAG_CHECK1("SUBREG_PROMOTED_UNSIGNED_P", (RTX), SUBREG)->volatil) \
-     ? -1 : (RTX)->unchanging)
+     ? (gcc_unreachable(), -1) : (RTX)->unchanging)
 
 /* Access various components of an ASM_OPERANDS rtx.  */
 

Re: RFA: DSE replace_read revisited

[Richard Sandiford]

Paolo Bonzini <paolo.bonzini@lu.unisi.ch> writes:
> BTW, do you know the circumstances under which you get a subreg/s/v?  It 
> seems like dead code to me and the attached patch bootstraps.

It's for ptr_extend promotion AIUI.

Richard

Re: RFA: DSE replace_read revisited

[Andrew Pinski]

On 10/31/07, Richard Sandiford <rsandifo@nildram.co.uk> wrote:
> Paolo Bonzini <paolo.bonzini@lu.unisi.ch> writes:
> > BTW, do you know the circumstances under which you get a subreg/s/v?  It
> > seems like dead code to me and the attached patch bootstraps.
>
> It's for ptr_extend promotion AIUI.

And also for targets where unsigned types smaller than the natural
register size.  For an example on PowerPC64-linux-gnu, unsigned int is
passed as a 64bit zero extended.  But ptr_extend promotion is another
use of it (ppu-lv2 [PS3] is such a target).

Thanks,
Andrew Pinski

Re: RFA: DSE replace_read revisited

[Richard Sandiford]

"Andrew Pinski" <pinskia@gmail.com> writes:
> On 10/31/07, Richard Sandiford <rsandifo@nildram.co.uk> wrote:
>> Paolo Bonzini <paolo.bonzini@lu.unisi.ch> writes:
>> > BTW, do you know the circumstances under which you get a subreg/s/v?  It
>> > seems like dead code to me and the attached patch bootstraps.
>>
>> It's for ptr_extend promotion AIUI.
>
> And also for targets where unsigned types smaller than the natural
> register size.  For an example on PowerPC64-linux-gnu, unsigned int is
> passed as a 64bit zero extended.

I'm probably misunderstanding, but isn't that subreg/s/u rather
than subreg/s/v?

Richard

Re: RFA: DSE replace_read revisited

[Andrew Pinski]

On 10/31/07, Richard Sandiford <rsandifo@nildram.co.uk> wrote:
> I'm probably misunderstanding, but isn't that subreg/s/u rather
> than subreg/s/v?

You are correct, this is why I should not reply to emails after drinking :).

-- Pinski

Re: RFA: DSE replace_read revisited

[Richard Sandiford]

Richard Sandiford <rsandifo@nildram.co.uk> writes:
> Richard Sandiford <rsandifo@nildram.co.uk> writes:
>> "Andrew Pinski" <pinskia@gmail.com> writes:
>>> On 10/28/07, Richard Sandiford <rsandifo@nildram.co.uk> wrote:
>>>>   (4) The code requires the store and read to have the same mode class:
>>>>
>>>>         if (GET_MODE_CLASS (read_mode) != GET_MODE_CLASS (store_mode))
>>>>           return false;
>>>>
>>>>       This seems unnecessarily restrictive.  I guess it was meant to
>>>>       be a simplifying assumption, but as per (1) and (2) above,
>>>>       it isn't really.
>>>
>>> Does this part fix PR 33927 where we have V4SI and V4SF?
>>
>> It should, subject to MODES_TIEABLE_P allowing the necessary mode changes
>> (to and from TImode in this case).
>>
>> It appears from validate_subreg that direct subregs between V4SI and
>> V4SF are allowed, so we could also add an extra case to extract_low_bits:
>>
>>   if (GET_MODE_BITSIZE (mode) == GET_MODE_BITSIZE (src_mode)
>>       && MODES_TIEABLE_P (mode, src_mode))
>>     {
>>       rtx x = gen_lowpart (mode, src);
>>       if (x)
>>         return x;
>>     }
>
> Sorry, this should have been gen_lowpart_common, not gen_lowpart.

Where do we stand on this patch?  Is anyone testing on SPU?

For avoidance of doubt, here's the patch with the extra code above.
Bootstrapped & regression-tested on x86_64-linux-gnu and
regression-tested on mipsisa64-elf.

Richard


gcc/
	* Makefile.in (dse.o): Depend on $(TM_P_H).
	* optabs.h (extract_low_bits): Declare.
	* optabs.c (extract_low_bits): New function.
	* rtlhooks.c (gen_lowpart_general): Generalize SUBREG handling.
	* dse.c: Include tm_p.h.
	(find_shift_sequence): Remove the read_reg argument and return the
	read value.  Emit the instructions instead of returning them.
	Iterate on new_mode rather than calculating it each time.
	Check MODES_TIEABLE_P.  Use simplify_gen_subreg to convert the
	source to NEW_MODE and extract_low_bits to convert the shifted
	value to READ_MODE.
	(replace_read): Allow the load and store to have different mode
	classes.  Use extract_low_bits when SHIFT == 0.  Create the shift
	or extraction instructions before trying the replacement.  Update
	dump-file code accordingly, avoiding use of REGNO (store_info->rhs).

gcc/testsuite/
	* gcc.target/mips/dse-1.c: Add checks for zeros.

Index: gcc/Makefile.in
===================================================================
--- gcc/Makefile.in	2007-10-31 08:23:05.000000000 +0000
+++ gcc/Makefile.in	2007-11-04 22:52:29.000000000 +0000
@@ -2538,8 +2538,8 @@ dce.o : dce.c $(CONFIG_H) $(SYSTEM_H) co
    $(TREE_H) $(REGS_H) hard-reg-set.h $(FLAGS_H) $(DF_H) cselib.h \
    $(DBGCNT_H) dce.h timevar.h tree-pass.h $(DBGCNT_H)
 dse.o : dse.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
-   $(TREE_H) $(REGS_H) hard-reg-set.h $(FLAGS_H) insn-config.h $(RECOG_H) \
-   $(EXPR_H) $(DF_H) cselib.h $(DBGCNT_H) timevar.h tree-pass.h \
+   $(TREE_H) $(TM_P_H) $(REGS_H) hard-reg-set.h $(FLAGS_H) insn-config.h \
+   $(RECOG_H) $(EXPR_H) $(DF_H) cselib.h $(DBGCNT_H) timevar.h tree-pass.h \
    alloc-pool.h $(ALIAS_H) dse.h $(OPTABS_H) $(RECOG_H)
 fwprop.o : fwprop.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
    toplev.h insn-config.h $(RECOG_H) $(FLAGS_H) $(OBSTACK_H) $(BASIC_BLOCK_H) \
Index: gcc/optabs.h
===================================================================
--- gcc/optabs.h	2007-10-28 10:57:51.000000000 +0000
+++ gcc/optabs.h	2007-11-04 22:51:58.000000000 +0000
@@ -770,6 +770,8 @@ extern rtx expand_vec_cond_expr (tree, r
 /* Generate code for VEC_LSHIFT_EXPR and VEC_RSHIFT_EXPR.  */
 extern rtx expand_vec_shift_expr (tree, rtx);
 
+extern rtx extract_low_bits (enum machine_mode, enum machine_mode, rtx);
+
 #define optab_handler(optab,mode) (&(optab)->handlers[(int) (mode)])
 #define convert_optab_handler(optab,mode,mode2) \
 	(&(optab)->handlers[(int) (mode)][(int) (mode2)])
Index: gcc/optabs.c
===================================================================
--- gcc/optabs.c	2007-11-04 22:51:10.000000000 +0000
+++ gcc/optabs.c	2007-11-05 13:02:45.000000000 +0000
@@ -4983,6 +4983,66 @@ gen_move_insn (rtx x, rtx y)
   end_sequence ();
   return seq;
 }
+
+/* Try to read the low bits of SRC as an rvalue of mode MODE, preserving
+   the bit pattern.  SRC_MODE is the mode of SRC; if this is smaller than
+   MODE, fill the upper bits with zeros.  Fail if the layout of either
+   mode is unknown (as for CC modes) or if the extraction would involve
+   unprofitable mode punning.  Return the value on success, otherwise
+   return null.
+
+   This is different from gen_lowpart* in these respects:
+
+     - the returned value must always be considered an rvalue
+
+     - when MODE is wider than SRC_MODE, the extraction involves
+       a zero extension
+
+     - when MODE is smaller than SRC_MODE, the extraction involves
+       a truncation (and is thus subject to TRULY_NOOP_TRUNCATION).
+
+   In other words, this routine performs a computation, whereas the
+   gen_lowpart* routines are conceptually lvalue or rvalue subreg
+   operations.  */
+
+rtx
+extract_low_bits (enum machine_mode mode, enum machine_mode src_mode, rtx src)
+{
+  enum machine_mode int_mode, src_int_mode;
+
+  if (mode == src_mode)
+    return src;
+
+  if (CONSTANT_P (src))
+    return simplify_gen_subreg (mode, src, src_mode,
+				subreg_lowpart_offset (mode, src_mode));
+
+  if (GET_MODE_CLASS (mode) == MODE_CC || GET_MODE_CLASS (src_mode) == MODE_CC)
+    return NULL_RTX;
+
+  if (GET_MODE_BITSIZE (mode) == GET_MODE_BITSIZE (src_mode)
+      && MODES_TIEABLE_P (mode, src_mode))
+    {
+      rtx x = gen_lowpart_common (mode, src);
+      if (x)
+        return x;
+    }
+
+  src_int_mode = int_mode_for_mode (src_mode);
+  int_mode = int_mode_for_mode (mode);
+  if (src_int_mode == BLKmode || int_mode == BLKmode)
+    return NULL_RTX;
+
+  if (!MODES_TIEABLE_P (src_int_mode, src_mode))
+    return NULL_RTX;
+  if (!MODES_TIEABLE_P (int_mode, mode))
+    return NULL_RTX;
+
+  src = gen_lowpart (src_int_mode, src);
+  src = convert_modes (int_mode, src_int_mode, src, true);
+  src = gen_lowpart (mode, src);
+  return src;
+}
 \f
 /* Return the insn code used to extend FROM_MODE to TO_MODE.
    UNSIGNEDP specifies zero-extension instead of sign-extension.  If
Index: gcc/rtlhooks.c
===================================================================
--- gcc/rtlhooks.c	2007-10-28 10:57:51.000000000 +0000
+++ gcc/rtlhooks.c	2007-11-04 22:51:58.000000000 +0000
@@ -43,11 +43,9 @@ gen_lowpart_general (enum machine_mode m
 
   if (result)
     return result;
-  /* If it's a REG, it must be a hard reg that's not valid in MODE.  */
-  else if (REG_P (x)
-	   /* Or we could have a subreg of a floating point value.  */
-	   || (GET_CODE (x) == SUBREG
-	       && FLOAT_MODE_P (GET_MODE (SUBREG_REG (x)))))
+  /* Handle SUBREGs and hard REGs that were rejected by
+     simplify_gen_subreg.  */
+  else if (REG_P (x) || GET_CODE (x) == SUBREG)
     {
       result = gen_lowpart_common (mode, copy_to_reg (x));
       gcc_assert (result != 0);
Index: gcc/dse.c
===================================================================
--- gcc/dse.c	2007-10-28 10:57:51.000000000 +0000
+++ gcc/dse.c	2007-11-04 22:51:58.000000000 +0000
@@ -29,6 +29,7 @@ Software Foundation; either version 3, o
 #include "tm.h"
 #include "rtl.h"
 #include "tree.h"
+#include "tm_p.h"
 #include "regs.h"
 #include "hard-reg-set.h"
 #include "flags.h"
@@ -1381,9 +1382,9 @@ record_store (rtx body, bb_info_t bb_inf
   if (store_info->is_set 
       /* No place to keep the value after ra.  */
       && !reload_completed
-      /* The careful reviewer may wish to comment my checking that the
-	 rhs of a store is always a reg.  */
-      && REG_P (SET_SRC (body))
+      && (REG_P (SET_SRC (body))
+	  || GET_CODE (SET_SRC (body)) == SUBREG
+	  || CONSTANT_P (SET_SRC (body)))
       /* Sometimes the store and reload is used for truncation and
 	 rounding.  */
       && !(FLOAT_MODE_P (GET_MODE (mem)) && (flag_float_store)))
@@ -1416,15 +1417,15 @@ dump_insn_info (const char * start, insn
    shift.  */
 
 static rtx
-find_shift_sequence (rtx read_reg,
-		     int access_size,
+find_shift_sequence (int access_size,
 		     store_info_t store_info,
 		     read_info_t read_info,
 		     int shift)
 {
   enum machine_mode store_mode = GET_MODE (store_info->mem);
   enum machine_mode read_mode = GET_MODE (read_info->mem);
-  rtx chosen_seq = NULL;
+  enum machine_mode new_mode;
+  rtx read_reg = NULL;
 
   /* Some machines like the x86 have shift insns for each size of
      operand.  Other machines like the ppc or the ia-64 may only have
@@ -1433,21 +1434,31 @@ find_shift_sequence (rtx read_reg,
      justify the value we want to read but is available in one insn on
      the machine.  */
 
-  for (; access_size <= UNITS_PER_WORD; access_size *= 2)
+  for (new_mode = smallest_mode_for_size (access_size * BITS_PER_UNIT,
+					  MODE_INT);
+       GET_MODE_BITSIZE (new_mode) <= BITS_PER_WORD;
+       new_mode = GET_MODE_WIDER_MODE (new_mode))
     {
-      rtx target, new_reg, shift_seq, insn;
-      enum machine_mode new_mode;
+      rtx target, new_reg, shift_seq, insn, new_lhs;
       int cost;
 
-      /* Try a wider mode if truncating the store mode to ACCESS_SIZE
-	 bytes requires a real instruction.  */
-      if (access_size < GET_MODE_SIZE (store_mode)
-	  && !TRULY_NOOP_TRUNCATION (access_size * BITS_PER_UNIT,
+      /* Try a wider mode if truncating the store mode to NEW_MODE
+	 requires a real instruction.  */
+      if (GET_MODE_BITSIZE (new_mode) < GET_MODE_BITSIZE (store_mode)
+	  && !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (new_mode),
 				     GET_MODE_BITSIZE (store_mode)))
 	continue;
 
-      new_mode = smallest_mode_for_size (access_size * BITS_PER_UNIT,
-					 GET_MODE_CLASS (read_mode));
+      /* Also try a wider mode if the necessary punning is either not
+	 desirable or not possible.  */
+      if (!CONSTANT_P (store_info->rhs)
+	  && !MODES_TIEABLE_P (new_mode, store_mode))
+	continue;
+      new_lhs = simplify_gen_subreg (new_mode, copy_rtx (store_info->rhs),
+				     store_mode, 0);
+      if (new_lhs == NULL_RTX)
+	continue;
+
       new_reg = gen_reg_rtx (new_mode);
 
       start_sequence ();
@@ -1484,31 +1495,13 @@ find_shift_sequence (rtx read_reg,
 	 take the value from the store and put it into the
 	 shift pseudo, then shift it, then generate another
 	 move to put in into the target of the read.  */
-      start_sequence ();
-      emit_move_insn (new_reg, gen_lowpart (new_mode, store_info->rhs));
+      emit_move_insn (new_reg, new_lhs);
       emit_insn (shift_seq);
-      convert_move (read_reg, new_reg, 1);
-		  
-      if (dump_file)
-	{
-	  fprintf (dump_file, " -- adding extract insn r%d:%s = r%d:%s\n",
-		   REGNO (new_reg), GET_MODE_NAME (new_mode),
-		   REGNO (store_info->rhs), GET_MODE_NAME (store_mode));
-		      
-	  fprintf (dump_file, " -- with shift of r%d by %d\n",
-		   REGNO(new_reg), shift);
-	  fprintf (dump_file, " -- and second extract insn r%d:%s = r%d:%s\n",
-		   REGNO (read_reg), GET_MODE_NAME (read_mode),
-		   REGNO (new_reg), GET_MODE_NAME (new_mode));
-	}
-		  
-      /* Get the three insn sequence and return it.  */
-      chosen_seq = get_insns ();
-      end_sequence ();
+      read_reg = extract_low_bits (read_mode, new_mode, new_reg);
       break;
     }
 
-  return chosen_seq;
+  return read_reg;
 }
 
 
@@ -1551,15 +1544,11 @@ replace_read (store_info_t store_info, i
   enum machine_mode read_mode = GET_MODE (read_info->mem);
   int shift;
   int access_size; /* In bytes.  */
-  rtx read_reg = gen_reg_rtx (read_mode);
-  rtx shift_seq = NULL;
+  rtx insns, read_reg;
 
   if (!dbg_cnt (dse))
     return false;
 
-  if (GET_MODE_CLASS (read_mode) != GET_MODE_CLASS (store_mode))
-    return false;
-
   /* To get here the read is within the boundaries of the write so
      shift will never be negative.  Start out with the shift being in
      bytes.  */
@@ -1573,62 +1562,43 @@ replace_read (store_info_t store_info, i
   /* From now on it is bits.  */
   shift *= BITS_PER_UNIT;
 
-  /* We need to keep this in perspective.  We are replacing a read
+  /* Create a sequence of instructions to set up the read register.
+     This sequence goes immediately before the store and its result
+     is read by the load.
+
+     We need to keep this in perspective.  We are replacing a read
      with a sequence of insns, but the read will almost certainly be
      in cache, so it is not going to be an expensive one.  Thus, we
      are not willing to do a multi insn shift or worse a subroutine
      call to get rid of the read.  */
+  if (dump_file)
+    fprintf (dump_file, "trying to replace %smode load in insn %d"
+	     " from %smode store in insn %d\n",
+	     GET_MODE_NAME (read_mode), INSN_UID (read_insn->insn),
+	     GET_MODE_NAME (store_mode), INSN_UID (store_insn->insn));
+  start_sequence ();
   if (shift)
+    read_reg = find_shift_sequence (access_size, store_info, read_info, shift);
+  else
+    read_reg = extract_low_bits (read_mode, store_mode,
+				 copy_rtx (store_info->rhs));
+  if (read_reg == NULL_RTX)
     {
-      if (access_size > UNITS_PER_WORD || FLOAT_MODE_P (store_mode))
-	return false;
-
-      shift_seq = find_shift_sequence (read_reg, access_size, store_info,
-				       read_info, shift);
-      if (!shift_seq)
-	return false;
+      end_sequence ();
+      if (dump_file)
+	fprintf (dump_file, " -- could not extract bits of stored value\n");
+      return false;
     }
-
-  if (dump_file)
-    fprintf (dump_file, "replacing load at %d from store at %d\n",
-	     INSN_UID (read_insn->insn), INSN_UID (store_insn->insn)); 
+  /* Force the value into a new register so that it won't be clobbered
+     between the store and the load.  */
+  read_reg = copy_to_mode_reg (read_mode, read_reg);
+  insns = get_insns ();
+  end_sequence ();
 
   if (validate_change (read_insn->insn, loc, read_reg, 0))
     {
-      rtx insns;
       deferred_change_t deferred_change = pool_alloc (deferred_change_pool);
       
-      if (read_mode == store_mode)
-	{
-	  start_sequence ();
-	  
-	  /* The modes are the same and everything lines up.  Just
-	     generate a simple move.  */
-	  emit_move_insn (read_reg, store_info->rhs);
-	  if (dump_file)
-	    fprintf (dump_file, " -- adding move insn r%d = r%d\n",
-		     REGNO (read_reg), REGNO (store_info->rhs));
-	  insns = get_insns ();
-	  end_sequence ();
-	}
-      else if (shift)
-	insns = shift_seq;
-      else
-	{
-	  /* The modes are different but the lsb are in the same
-	     place, we need to extract the value in the right from the
-	     rhs of the store.  */
-	  start_sequence ();
-	  convert_move (read_reg, store_info->rhs, 1);
-	  
-	  if (dump_file)
-	    fprintf (dump_file, " -- adding extract insn r%d:%s = r%d:%s\n",
-		     REGNO (read_reg), GET_MODE_NAME (read_mode),
-		     REGNO (store_info->rhs), GET_MODE_NAME (store_mode));
-	  insns = get_insns ();
-	  end_sequence ();
-	}
-
       /* Insert this right before the store insn where it will be safe
 	 from later insns that might change it before the read.  */
       emit_insn_before (insns, store_insn->insn);
@@ -1666,12 +1636,22 @@ replace_read (store_info_t store_info, i
 	 rest of dse, play like this read never happened.  */
       read_insn->read_rec = read_info->next;
       pool_free (read_info_pool, read_info);
+      if (dump_file)
+	{
+	  fprintf (dump_file, " -- replaced the loaded MEM with ");
+	  print_simple_rtl (dump_file, read_reg);
+	  fprintf (dump_file, "\n");
+	}
       return true;
     }
   else 
     {
       if (dump_file)
-	fprintf (dump_file, " -- validation failure\n"); 
+	{
+	  fprintf (dump_file, " -- replacing the loaded MEM with ");
+	  print_simple_rtl (dump_file, read_reg);
+	  fprintf (dump_file, " led to an invalid instruction\n");
+	}
       return false;
     }
 }
Index: gcc/testsuite/gcc.target/mips/dse-1.c
===================================================================
--- gcc/testsuite/gcc.target/mips/dse-1.c	2007-10-28 10:57:51.000000000 +0000
+++ gcc/testsuite/gcc.target/mips/dse-1.c	2007-11-04 22:51:58.000000000 +0000
@@ -14,6 +14,13 @@ #define TEST(ID, TYPE1, TYPE2)					\
     u->m2 = x;							\
     return (u->m1[0]						\
 	    + u->m1[sizeof (TYPE2) / sizeof (TYPE1) - 1]);	\
+  }								\
+								\
+  TYPE1 __attribute__((nomips16))				\
+  g##ID (union u##ID *u)					\
+  {								\
+    u->m2 = 0;							\
+    return (u->m1[0] | u->m1[1]);				\
   }
 
 TEST (1, unsigned int, unsigned long long);

Re: RFA: DSE replace_read revisited

[Eric Botcazou]

> A few weeks ago, I posted a patch to fix some problems in the
> new RTL DSE replace_read code:
>
>     http://gcc.gnu.org/ml/gcc-patches/2007-09/msg01316.html
>
> However, I found that the testcase added there still fails for some
> MIPS targets, and investigating that led me to some wrong-code and
> pessimisation issues too.

Thanks for following up on this.  While I agree that fixing the wrong code 
bugs is necessary, I'm less sure about the pessimisation issues for now.

> There seem to be several problems: 
>
>   (1) As I complained about in the message above, find_shift_sequence
>       does the shift in the mode class of the stored value, rather than
>       MODE_INT.  So if we have a V4HI store and a V2HI read (say), we'd
>       use a vector shift rather than an integer shift.  We'd therefore
>       shift the individual HI elements right, rather than shift the
>       whole bit pattern.

That seems indeed wrong.

>   (2) When reading the low end of a stored value, the original code used
>       gen_lowpart to do the mode punning:
>
>         emit_move_insn (read_reg, gen_lowpart (read_mode, store_info->rhs));
>
>       This ICEd when a DFmode store was followed by an SFmode move, as in:
>
>         union u { double d; float f[2]; };
>
>         float
>         foo (union u *u, double d)
>         {
>           u->d = d;
>           return u->f[1];
>         }
>
>       for big-endian targets, because SFmode subregs of DFmode values
>       are not allowed.  My attempt to fix the integer cases for MIPS
>       meant that we'd now convert the DFmode value into SFmode instead,
>       which is of course also wrong.
>
>       (Although this particular example isn't very realistic,
>       the equivalent TFmode/DFmode one matters for targets with
>       IEEE long doubles.)

Can't we simply punt if we cannot form the lowpart?

>   (4) The code requires the store and read to have the same mode class:
>
>         if (GET_MODE_CLASS (read_mode) != GET_MODE_CLASS (store_mode))
>           return false;
>
>       This seems unnecessarily restrictive.  I guess it was meant to
>       be a simplifying assumption, but as per (1) and (2) above,
>       it isn't really.

However let's keep it for 4.3 I'd think.

>   (5) The shift case can't deal with floats, even though it would be
>       profitable to do so on some soft-float targets.

Let's keep this limitation for now too.

>   (6) The code only deals with REGs:
>
>         if (store_info->is_set
>             /* No place to keep the value after ra.  */
>             && !reload_completed
>             /* The careful reviewer may wish to comment my checking that
> the rhs of a store is always a reg.  */
>             && REG_P (SET_SRC (body))
>             /* Sometimes the store and reload is used for truncation and
>               rounding.  */
>             && !(FLOAT_MODE_P (GET_MODE (mem)) && (flag_float_store)))
>
>       This does indeed seem unnecessarily restrictive, and is the cause of
>       the dse-1.c failures that led me here originally.  The code could
>       easily handle subregs and constants as well.

Yes, I think that we can try and lift this one.

> Addressing (1)-(5) together, I think part of the problem is that the
> code has too many special exceptions.  From a high-level perspective,
> I think we need two things:
>
>   (a) a way of telling whether a mode change is profitable
>
>   (b) a way of extracting the low bits of a value of one arbitrary mode
>       into a value of another arbitrary mode
>
> (a) we already have in the form of MODES_TIEABLE_P.  So rather than
> check whether the two modes are the same class, I think we should check
> whether each individual mode change we make is profitable accordingly to
> MODES_TIEABLE_P.
>
> (b) we don't have (AFAIK), so I added a new routine called
> extract_low_bits. Quoting the function's comment:
>
>    Try to read the low bits of SRC as an rvalue of mode MODE, preserving
>    the bit pattern.  SRC_MODE is the mode of SRC; if this is smaller than
>    MODE, fill the upper bits with zeros.  Fail if the layout of either
>    mode is unknown (as for CC modes) or if the extraction would involve
>    unprofitable mode punning.  Return the value on success, otherwise
>    return null.
>
>    This is different from gen_lowpart* in these respects:
>
>      - the returned value must always be considered an rvalue
>
>      - when MODE is wider than SRC_MODE, the extraction involves
>        a zero extension
>
>      - when MODE is smaller than SRC_MODE, the extraction involves
>        a truncation (and is thus subject to TRULY_NOOP_TRUNCATION).
>
>    In other words, this routine performs a computation, whereas the
>    gen_lowpart* routines are conceptually lvalue or rvalue subreg
>    operations.

I'm a little reluctant to introduce this machinery at this point.  So I'd try 
to fix the wrong-code code as long as extract_low_bits is not required; if it 
is, I'd punt for now.

What do you think?

-- 
Eric Botcazou

Re: RFA: DSE replace_read revisited

[Richard Sandiford]

Eric Botcazou <ebotcazou@libertysurf.fr> writes:
> I'm a little reluctant to introduce this machinery at this point.  So
> I'd try to fix the wrong-code code as long as extract_low_bits is not
> required; if it is, I'd punt for now.
>
> What do you think?

The reason I didn't do that is that it would mean adding even more
special cases.  GCC has a history of bolting on "except for this
special case" conditions, which makes the code even harder to work
with when you next need to change it.  (And we might we need to change
this code during the 4.3 maintanence period.)

IMO, adding extract_low_bits makes the DSE code conceptually simpler,
and I imagine is what Eric and Kenny would have used from the outset
had extract_low_bits existed at that point.

Kenny, what do you think?

Richard

Re: RFA: DSE replace_read revisited

[Kenneth Zadeck]

Richard Sandiford wrote:
> Eric Botcazou <ebotcazou@libertysurf.fr> writes:
>   
>> I'm a little reluctant to introduce this machinery at this point.  So
>> I'd try to fix the wrong-code code as long as extract_low_bits is not
>> required; if it is, I'd punt for now.
>>
>> What do you think?
>>     
>
> The reason I didn't do that is that it would mean adding even more
> special cases.  GCC has a history of bolting on "except for this
> special case" conditions, which makes the code even harder to work
> with when you next need to change it.  (And we might we need to change
> this code during the 4.3 maintanence period.)
>
> IMO, adding extract_low_bits makes the DSE code conceptually simpler,
> and I imagine is what Eric and Kenny would have used from the outset
> had extract_low_bits existed at that point.
>
> Kenny, what do you think?
>
> Richard
>   
The truth is that eric christopher and i completely underestimated how
hard removing read after writes really was.  Had we understood what we
were getting into, i would have gone to either you, iant, or bonzini
from the start. 

in fact my plan for reviewing this patch is to ask bonzini or one of the
middle end maintainers to review it when this spu issue is resolved (or
else to just trust you).  Even after writing the interference graph
scanner, this is still way over my skill level. 

Re: RFA: DSE replace_read revisited

[Richard Sandiford]

Kenneth Zadeck <zadeck@naturalbridge.com> writes:
> Richard Sandiford wrote:
>> Eric Botcazou <ebotcazou@libertysurf.fr> writes:
>>   
>>> I'm a little reluctant to introduce this machinery at this point.  So
>>> I'd try to fix the wrong-code code as long as extract_low_bits is not
>>> required; if it is, I'd punt for now.
>>>
>>> What do you think?
>>>     
>>
>> The reason I didn't do that is that it would mean adding even more
>> special cases.  GCC has a history of bolting on "except for this
>> special case" conditions, which makes the code even harder to work
>> with when you next need to change it.  (And we might we need to change
>> this code during the 4.3 maintanence period.)
>>
>> IMO, adding extract_low_bits makes the DSE code conceptually simpler,
>> and I imagine is what Eric and Kenny would have used from the outset
>> had extract_low_bits existed at that point.
>>
>> Kenny, what do you think?
>>
>> Richard
>>   
> The truth is that eric christopher and i completely underestimated how
> hard removing read after writes really was.  Had we understood what we
> were getting into, i would have gone to either you, iant, or bonzini
> from the start. 
>
> in fact my plan for reviewing this patch is to ask bonzini or one of the
> middle end maintainers to review it when this spu issue is resolved (or
> else to just trust you).

Fair enough.  Since one of them has already objected, and no-one else
has spoken in favour of it, how about we simply limit the optimisation
to MODE_INT?

Richard

Re: RFA: DSE replace_read revisited

[Eric Botcazou]

> Fair enough.  Since one of them has already objected, and no-one else
> has spoken in favour of it, how about we simply limit the optimisation
> to MODE_INT?

Fine with me for now.  This of course can be revisited for 4.4.

-- 
Eric Botcazou

Re: RFA: DSE replace_read revisited

[Richard Sandiford]

Eric Botcazou <ebotcazou@libertysurf.fr> writes:
>> Fair enough.  Since one of them has already objected, and no-one else
>> has spoken in favour of it, how about we simply limit the optimisation
>> to MODE_INT?
>
> Fine with me for now.

OK, I've bootstrapped & regression-tested the attached patch on
x86_64-linux-gnu.  I've also disabled the dse-1.c test for the
reasons stated in the comment.  OK to install?

Richard


gcc/
	* dse.c (find_shift_sequence): Always choose an integer mode for
	new_mode.
	(replace_read): Require both the read and store mode to be
	integer ones.  Remove a then-redundant FLOAT_P check.

gcc/testsuite/
	* gcc.target/mips/dse-1.c: Disable.

Index: gcc/dse.c
===================================================================
--- gcc/dse.c	(revision 129887)
+++ gcc/dse.c	(working copy)
@@ -1447,7 +1447,7 @@ find_shift_sequence (rtx read_reg,
 	continue;
 
       new_mode = smallest_mode_for_size (access_size * BITS_PER_UNIT,
-					 GET_MODE_CLASS (read_mode));
+					 MODE_INT);
       new_reg = gen_reg_rtx (new_mode);
 
       start_sequence ();
@@ -1473,9 +1473,8 @@ find_shift_sequence (rtx read_reg,
 	 of the arguments and could be precomputed.  It may
 	 not be worth doing so.  We could precompute if
 	 worthwhile or at least cache the results.  The result
-	 technically depends on SHIFT, ACCESS_SIZE, and
-	 GET_MODE_CLASS (READ_MODE).  But in practice the
-	 answer will depend only on ACCESS_SIZE.  */
+	 technically depends on both SHIFT and ACCESS_SIZE,
+	 but in practice the answer will depend only on ACCESS_SIZE.  */
 
       if (cost > COSTS_N_INSNS (1))
 	continue;
@@ -1557,7 +1556,8 @@ replace_read (store_info_t store_info, i
   if (!dbg_cnt (dse))
     return false;
 
-  if (GET_MODE_CLASS (read_mode) != GET_MODE_CLASS (store_mode))
+  if (GET_MODE_CLASS (read_mode) != MODE_INT
+      || GET_MODE_CLASS (store_mode) != MODE_INT)
     return false;
 
   /* To get here the read is within the boundaries of the write so
@@ -1580,7 +1580,7 @@ replace_read (store_info_t store_info, i
      call to get rid of the read.  */
   if (shift)
     {
-      if (access_size > UNITS_PER_WORD || FLOAT_MODE_P (store_mode))
+      if (access_size > UNITS_PER_WORD)
 	return false;
 
       shift_seq = find_shift_sequence (read_reg, access_size, store_info,
Index: gcc/testsuite/gcc.target/mips/dse-1.c
===================================================================
--- gcc/testsuite/gcc.target/mips/dse-1.c	(revision 129887)
+++ gcc/testsuite/gcc.target/mips/dse-1.c	(working copy)
@@ -1,3 +1,7 @@
+/* ??? Further to the subreg comment below, we can't rely on any of the
+   tests passing unless we handle subregs, and the patch to do so has
+   been rejected for the time being.  */
+/* { dg-do compile { target { ! *-*-* } } } */
 /* { dg-mips-options "-mgp64 -O" } */
 
 #define TEST(ID, TYPE1, TYPE2)					\

Re: RFA: DSE replace_read revisited

[Eric Botcazou]

> OK, I've bootstrapped & regression-tested the attached patch on
> x86_64-linux-gnu.  I've also disabled the dse-1.c test for the
> reasons stated in the comment.  OK to install?

OK, thanks.  Send me a ping for the original patch when Stage 1 re-opens.

-- 
Eric Botcazou