[PATCH, 2/2] shrink wrap a function with a single loop: split live_edge

[Zhenqiang Chen <zhenqiang dot chen at linaro dot org>]

Hi,

The patch splits the live_edge for move_insn_for_shrink_wrap to sink
the copy out of the entry block.

Bootstrap and no make check regression on X86-64 and ARM.

OK for trunk?

Thanks!
-Zhenqiang

ChangeLog:
2014-05-08  Zhenqiang Chen  <zhenqiang.chen@linaro.org>

        * function.c (next_block_for_reg): Allow live_edge->dest has two
        predecessors.
        (move_insn_for_shrink_wrap): Split live_edge.
        (prepre_shrink_wrap): One more parameter for move_insn_for_shrink_wrap.


diff --git a/gcc/function.c b/gcc/function.c
index 764ac82..0be58e2 100644
--- a/gcc/function.c
+++ b/gcc/function.c
@@ -5381,7 +5381,7 @@ requires_stack_frame_p (rtx insn, HARD_REG_SET
prologue_used,
    and if BB is its only predecessor.  Return that block if so,
    otherwise return null.  */

-static basic_block
+static edge
 next_block_for_reg (basic_block bb, int regno, int end_regno)
 {
   edge e, live_edge;
@@ -5415,10 +5415,12 @@ next_block_for_reg (basic_block bb, int regno,
int end_regno)
   if (live_edge->flags & EDGE_ABNORMAL)
     return NULL;

-  if (EDGE_COUNT (live_edge->dest->preds) > 1)
+  /* When live_edge->dest->preds == 2, we can create a new block on
+     the edge to make it meet the requirement.  */
+  if (EDGE_COUNT (live_edge->dest->preds) > 2)
     return NULL;

-  return live_edge->dest;
+  return live_edge;
 }

 /* Check whether INSN is the last insn in BB or
@@ -5545,20 +5547,25 @@ try_copy_prop (basic_block bb, rtx insn, rtx
src, rtx dest,
   return ret;
 }

- /* Try to move INSN from BB to a successor.  Return true on success.
-    USES and DEFS are the set of registers that are used and defined
-    after INSN in BB.  */
+/* Try to move INSN from BB to a successor.  Return true on success.
+   LAST_USES is the set of registers that are used by the COMPARE or JUMP
+   instructions in the block.  USES is the set of registers that are used
+   by others after INSN except COMARE and JUMP.  DEFS are the set of registers
+   that are used and defined others after INSN.  SPLIT_P indicates whether
+   a live edge from BB is splitted or not.  */

 static bool
 move_insn_for_shrink_wrap (basic_block bb, rtx insn,
                           const HARD_REG_SET uses,
                           const HARD_REG_SET defs,
-                          HARD_REG_SET *last_uses)
+                          HARD_REG_SET *last_uses,
+                          bool *split_p)
{
   rtx set, src, dest;
   bitmap live_out, live_in, bb_uses, bb_defs;
   unsigned int i, dregno, end_dregno, sregno, end_sregno;
   basic_block next_block;
+  edge live_edge;

   /* Look for a simple register copy.  */
   set = single_set (insn);
@@ -5582,17 +5589,31 @@ move_insn_for_shrink_wrap (basic_block bb, rtx insn,
       || overlaps_hard_reg_set_p (defs, GET_MODE (dest), dregno))
     return false;

-  /* See whether there is a successor block to which we could move INSN.  */
-  next_block = next_block_for_reg (bb, dregno, end_dregno);
-  if (!next_block)
+  live_edge = next_block_for_reg (bb, dregno, end_dregno);
+  if (!live_edge)
      return false;

+  next_block = live_edge->dest;
+
   /* If the destination register is referred in later insn,
      try to forward it.  */
   if (overlaps_hard_reg_set_p (*last_uses, GET_MODE (dest), dregno)
       && !try_copy_prop (bb, insn, src, dest, last_uses))
     return false;

+  /* Create a new basic block on the edge.  */
+  if (EDGE_COUNT (next_block->preds) == 2)
+    {
+      next_block = split_edge (live_edge);
+
+      bitmap_copy (df_get_live_in (next_block), df_get_live_out (bb));
+      df_set_bb_dirty (next_block);
+
+      /* We should not split more than once for a function.  */
+      gcc_assert (!(*split_p));
+      *split_p = true;
+    }
+
   /* At this point we are committed to moving INSN, but let's try to
      move it as far as we can.  */
   do
@@ -5610,7 +5631,10 @@ move_insn_for_shrink_wrap (basic_block bb, rtx insn,
        {
          for (i = dregno; i < end_dregno; i++)
            {
-             if (REGNO_REG_SET_P (bb_uses, i) || REGNO_REG_SET_P (bb_defs, i)
+
+             if (*split_p
+                 || REGNO_REG_SET_P (bb_uses, i)
+                 || REGNO_REG_SET_P (bb_defs, i)
                  || REGNO_REG_SET_P (&DF_LIVE_BB_INFO (bb)->gen, i))
                next_block = NULL;
              CLEAR_REGNO_REG_SET (live_out, i);
@@ -5621,7 +5645,8 @@ move_insn_for_shrink_wrap (basic_block bb, rtx insn,
             Either way, SRC is now live on entry.  */
          for (i = sregno; i < end_sregno; i++)
            {
-             if (REGNO_REG_SET_P (bb_defs, i)
+             if (*split_p
+                 || REGNO_REG_SET_P (bb_defs, i)
                  || REGNO_REG_SET_P (&DF_LIVE_BB_INFO (bb)->gen, i))
                next_block = NULL;
              SET_REGNO_REG_SET (live_out, i);
@@ -5650,21 +5675,31 @@ move_insn_for_shrink_wrap (basic_block bb, rtx insn,
       /* If we don't need to add the move to BB, look for a single
         successor block.  */
       if (next_block)
-       next_block = next_block_for_reg (next_block, dregno, end_dregno);
+       {
+         live_edge = next_block_for_reg (next_block, dregno, end_dregno);
+         if (!live_edge || EDGE_COUNT (live_edge->dest->preds) > 1)
+           break;
+         next_block = live_edge->dest;
+       }
     }
   while (next_block);

-  /* BB now defines DEST.  It only uses the parts of DEST that overlap SRC
-     (next loop).  */
-  for (i = dregno; i < end_dregno; i++)
+  /* For the new created basic block, there is no dataflow info at all.
+     So skip the following dataflow update and check.  */
+  if (!(*split_p))
     {
-      CLEAR_REGNO_REG_SET (bb_uses, i);
-      SET_REGNO_REG_SET (bb_defs, i);
-    }
+      /* BB now defines DEST.  It only uses the parts of DEST that overlap SRC
+        (next loop).  */
+      for (i = dregno; i < end_dregno; i++)
+       {
+         CLEAR_REGNO_REG_SET (bb_uses, i);
+         SET_REGNO_REG_SET (bb_defs, i);
+       }

-  /* BB now uses SRC.  */
-  for (i = sregno; i < end_sregno; i++)
-    SET_REGNO_REG_SET (bb_uses, i);
+      /* BB now uses SRC.  */
+      for (i = sregno; i < end_sregno; i++)
+       SET_REGNO_REG_SET (bb_uses, i);
+    }

   emit_insn_after (PATTERN (insn), bb_note (bb));
   delete_insn (insn);
@@ -5684,6 +5719,7 @@ prepare_shrink_wrap (basic_block entry_block)
   rtx insn, curr, x;
   HARD_REG_SET uses, defs, last_uses;
   df_ref *ref;
+  bool split_p = false;

   if (!JUMP_P (BB_END (entry_block)))
     return;
@@ -5693,7 +5729,7 @@ prepare_shrink_wrap (basic_block entry_block)
   FOR_BB_INSNS_REVERSE_SAFE (entry_block, insn, curr)
     if (NONDEBUG_INSN_P (insn)
        && !move_insn_for_shrink_wrap (entry_block, insn, uses, defs,
-                                      &last_uses))
+                                      &last_uses, &split_p))
       {
        /* Add all defined registers to DEFs.  */
        for (ref = DF_INSN_DEFS (insn); *ref; ref++)