RFC/RFA: Fix bug with REE optimization corrupting extended registers

[Nick Clifton <nickc at redhat dot com>]

Hi Guys,

  I recently discovered a bug in the current Redundant Extension
  Elimination optimization.  If the candidate extension instruction
  increases the number of hard registers used, the pass does not check
  to see if these extra registers are live between the definition and
  the extension.

  For example:

    (insn  44 (set (reg:QI r11) (mem:QI (reg:HI r20))) 
    (insn  45 (set (reg:QI r10) (mem:QI (reg:HI r18))) 
    [...]
    (insn  71 (set (reg:HI r14) (zero_extend:HI (reg:QI r11)))
    [...]                                                  
    (insn  88 (set (reg:HI r10) (zero_extend:HI (reg:QI r10)))

  (This is on the RL78 target where HImode values occupy two hard
  registers and QImode values only one.  The bug however is generic, not
  RL78 specific).
  
  The REE pass transforms this into:

    (insn  44 (set (reg:QI r11) (mem:QI (reg:HI r20))) 
    (insn  45 (set (reg:HI r10) (zero_extend:HI (mem:QI (reg:HI r18)))) 
    [...]
    (insn  71 (set (reg:HI r14) (zero_extend:HI (reg:QI r11)))
    [...]
    (insn  88 deleted)

  Note how the new set at insn 45 clobbers the value loaded by insn 44
  into r11.

  The patch below is my attempt to fix this.  It is not correct
  however.  I could not work out how to determine if a given hard
  register is live at any point between two insns.  So instead I used
  the liveness information associated with the basic block containing
  the definition.  If one of the extended registers is live or becomes
  live in this block, and this block is not the same block as the one
  containing the extension insn, then I stop the optimization.  This
  works for the RL78 for all of the cases that I could find.

  So ... comments please ?

  Will gcc ever generate a single basic block that contains both the
  definition and the extension instructions, but also where the extra
  hard registers are used for another purpose as well ?

  Tested with no regressions (or fixes) on an x86-pc-linux-gnu target.
  Also tested with no regression and 7 fixes on an rl78-elf target.

Cheers
  Nick

gcc/ChangeLog
2015-11-18  Nick Clifton  <nickc@redhat.com>

	* ree.c (regs_live_between): New function.
        (add_removable_extension): If the extension uses more hard
        registers than the definition then check that the extra hard
        registers are not live between the definition and the
        extension.

Index: gcc/ree.c
===================================================================
--- gcc/ree.c	(revision 230517)
+++ gcc/ree.c	(working copy)
@@ -952,6 +952,49 @@
   return false;
 }
 
+/* Returns TRUE if any of the registers [start, stop) are live between DEF and up
+   to, but not including, INSN.  */
+
+static bool
+regs_live_between (rtx_insn * insn,
+		   struct df_link * def,
+		   unsigned int start,
+		   unsigned int stop)
+{
+  basic_block bb;
+
+  /* FIXME: This is an incomplete test.  It only checks the DEF and USE states of the
+     registers in basic block of DEF.  If any of them match the start-stop range and
+     the INSN is not in the same block, then it is assumed that the registers must be
+     live.  */
+  /* These first few checks are just paranoia... */
+  if (def != NULL
+      && def->ref != NULL
+      && def->ref->base.insn_info != NULL
+      && def->ref->base.insn_info->insn != NULL
+      && (bb = BLOCK_FOR_INSN (def->ref->base.insn_info->insn)) != NULL
+      && bb != BLOCK_FOR_INSN (insn))
+    {
+      struct df_lr_bb_info * bb_info = df_lr_get_bb_info (bb->index);
+      bitmap_iterator bi;
+      unsigned int reg;
+
+      EXECUTE_IF_SET_IN_BITMAP (& bb_info->def, 0, reg, bi)
+	{
+	  if (reg >= start && reg < stop)
+	    return true;
+	}
+
+      EXECUTE_IF_SET_IN_BITMAP (& bb_info->out, 0, reg, bi)
+	{
+	  if (reg >= start && reg < stop)
+	    return true;
+	}
+    }
+
+  return false;
+}
+
 /* Add an extension pattern that could be eliminated.  */
 
 static void
@@ -1080,6 +1123,30 @@
 	      }
 	  }
 
+      /* Fourth, if the extended version occupies more registers than
+	 the original version then make sure that these extra registers
+	 are not live between the definition and the extension.  */
+      if (HARD_REGNO_NREGS (REGNO (dest), mode)
+	  > HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg)))
+	{
+	  unsigned int start_reg = REGNO (reg) + HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg));
+	  unsigned int stop_reg  = REGNO (reg) + HARD_REGNO_NREGS (REGNO (dest), mode);
+
+	  for (def = defs; def; def = def->next)
+	    {
+	      if (regs_live_between (insn, def, start_reg, stop_reg))
+		{
+		  if (dump_file)
+		    {
+		      fprintf (dump_file, "Cannot eliminate extension:\n");
+		      print_rtl_single (dump_file, insn);
+		      fprintf (dump_file, " because extended register(s) are already used\n");
+		    }
+		  return;
+		}
+	    }
+	}
+
       /* Then add the candidate to the list and insert the reaching definitions
          into the definition map.  */
       ext_cand e = {expr, code, mode, insn};