Re: RFA: patch to solve PR37859

[Vladimir Makarov <vmakarov at redhat dot com>]

Adam Nemet wrote:
> Vlad,
>
> Thanks for patch.  I think I understand the difference.  What you're saying is
> that the reason the change on r719 does not reach r696 because the loop with
> r719 flows directly into an adjacent loop instead of the parent loop.
>
> I will bootstrap the patch on mips64 overnight and report back.
>
> There are few comments below FWIW.
Here is the modified version of the patch.  I also decided to use a new 
attribute for ira_loop_tree_node because calculation of it for each 
store is a bit more expensive.

2008-11-14  Vladimir Makarov  <vmakarov@redhat.com>

   PR bootstrap/37859
   * ira-int.h (struct ira_loop_tree_node): New member
   entered_from_non_parent_p.

   * ira-color.c (print_loop_title): Print loop bbs.

   * ira-emit.c (entered_from_non_parent_p,
   setup_entered_from_non_parent_p): New functions.
   (not_modified_p): Rename to store_can_be_removed_p.  Check there
   is no side entries.
   (generate_edge_moves): Use store_can_be_removed_p instead of
   not_modified_p.
   (ira_emit): Call setup_entered_from_non_parent_p.
  
   * ira-build.c (copy_info_to_removed_store_destinations):
   Accumulate CALL_FREQ, CALL_CROSSED_NUM, and
   ALLOCNO_EXCESS_PRESSURE_POINTS_NUM.
   (ira_flattening): Don't CHECK MEM_OPTIMIZED_DEST[_P], always
   update all accumulated attributes.
  

Index: ira-int.h
===================================================================
--- ira-int.h	(revision 141823)
+++ ira-int.h	(working copy)
@@ -107,6 +107,11 @@ struct ira_loop_tree_node
      one cap with the same regno in a region).  */
   ira_allocno_t *regno_allocno_map;
 
+  /* True if there is an entry to given loop not from its parent (or
+     grandparent) basic block.  For example, it is possible for two
+     adjacent loops inside another loop.  */
+  bool entered_from_non_parent_p;
+
   /* Maximal register pressure inside loop for given register class
      (defined only for the cover classes).  */
   int reg_pressure[N_REG_CLASSES];
Index: ira-color.c
===================================================================
--- ira-color.c	(revision 141823)
+++ ira-color.c	(working copy)
@@ -1656,15 +1656,32 @@ print_loop_title (ira_loop_tree_node_t l
 {
   unsigned int j;
   bitmap_iterator bi;
+  ira_loop_tree_node_t subloop_node, dest_loop_node;
+  edge e;
+  edge_iterator ei;
 
   ira_assert (loop_tree_node->loop != NULL);
   fprintf (ira_dump_file,
-	   "\n  Loop %d (parent %d, header bb%d, depth %d)\n    all:",
+	   "\n  Loop %d (parent %d, header bb%d, depth %d)\n    bbs:",
 	   loop_tree_node->loop->num,
 	   (loop_tree_node->parent == NULL
 	    ? -1 : loop_tree_node->parent->loop->num),
 	   loop_tree_node->loop->header->index,
 	   loop_depth (loop_tree_node->loop));
+  for (subloop_node = loop_tree_node->children;
+       subloop_node != NULL;
+       subloop_node = subloop_node->next)
+    if (subloop_node->bb != NULL)
+      {
+	fprintf (ira_dump_file, " %d", subloop_node->bb->index);
+	FOR_EACH_EDGE (e, ei, subloop_node->bb->succs)
+	  if (e->dest != EXIT_BLOCK_PTR
+	      && ((dest_loop_node = IRA_BB_NODE (e->dest)->parent)
+		  != loop_tree_node))
+	    fprintf (ira_dump_file, "(->%d:l%d)",
+		     e->dest->index, dest_loop_node->loop->num);
+      }
+  fprintf (ira_dump_file, "\n    all:");
   EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
     fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
   fprintf (ira_dump_file, "\n    modified regnos:");
Index: ira-emit.c
===================================================================
--- ira-emit.c	(revision 141823)
+++ ira-emit.c	(working copy)
@@ -260,12 +260,63 @@ set_allocno_reg (ira_allocno_t allocno, 
     }
 }
 
-/* Return TRUE if move of SRC_ALLOCNO to DEST_ALLOCNO does not change
-   value of the destination.  One possible reason for this is the
-   situation when SRC_ALLOCNO is not modified in the corresponding
-   loop.  */
+/* Return true if there is an entry to given loop not from its parent
+   (or grandparent) block.  For example, it is possible for two
+   adjacent loops inside another loop.  */
 static bool
-not_modified_p (ira_allocno_t src_allocno, ira_allocno_t dest_allocno)
+entered_from_non_parent_p (ira_loop_tree_node_t loop_node)
+{
+  ira_loop_tree_node_t bb_node, src_loop_node, parent;
+  edge e;
+  edge_iterator ei;
+
+  for (bb_node = loop_node->children; bb_node != NULL; bb_node = bb_node->next)
+    if (bb_node->bb != NULL)
+      {
+	FOR_EACH_EDGE (e, ei, bb_node->bb->preds)
+	  if (e->src != ENTRY_BLOCK_PTR
+	      && (src_loop_node = IRA_BB_NODE (e->src)->parent) != loop_node)
+	    {
+	      for (parent = src_loop_node->parent;
+		   parent != NULL;
+		   parent = parent->parent)
+		if (parent == loop_node)
+		  break;
+	      if (parent != NULL)
+		/* That is an exit from a nested loop -- skip it.  */
+		continue;
+	      for (parent = loop_node->parent;
+		   parent != NULL;
+		   parent = parent->parent)
+		if (src_loop_node == parent)
+		  break;
+	      if (parent == NULL)
+		return true;
+	    }
+      }
+  return false;
+}
+
+/* Set up ENTERED_FROM_NON_PARENT_P for each loop region.  */
+static void
+setup_entered_from_non_parent_p (void)
+{
+  unsigned int i;
+  loop_p loop;
+
+  for (i = 0; VEC_iterate (loop_p, ira_loops.larray, i, loop); i++)
+    if (ira_loop_nodes[i].regno_allocno_map != NULL)
+      ira_loop_nodes[i].entered_from_non_parent_p
+	= entered_from_non_parent_p (&ira_loop_nodes[i]);
+}
+
+/* Return TRUE if move of SRC_ALLOCNO (assigned to hard register) to
+   DEST_ALLOCNO (assigned to memory) can be removed beacuse it does
+   not change value of the destination.  One possible reason for this
+   is the situation when SRC_ALLOCNO is not modified in the
+   corresponding loop.  */
+static bool
+store_can_be_removed_p (ira_allocno_t src_allocno, ira_allocno_t dest_allocno)
 {
   int regno, orig_regno;
   ira_allocno_t a;
@@ -278,13 +329,26 @@ not_modified_p (ira_allocno_t src_allocn
   for (node = ALLOCNO_LOOP_TREE_NODE (src_allocno);
        node != NULL;
        node = node->parent)
-    if ((a = node->regno_allocno_map[orig_regno]) == NULL)
-      break;
-    else if (REGNO (ALLOCNO_REG (a)) == (unsigned) regno)
-      return true;
-    else if (bitmap_bit_p (node->modified_regnos, orig_regno))
-      return false;
-  return node != NULL;
+    {
+      a = node->regno_allocno_map[orig_regno];
+      ira_assert (a != NULL);
+      if (REGNO (ALLOCNO_REG (a)) == (unsigned) regno)
+	/* We achieved the destination and everything is ok.  */
+	return true;
+      else if (bitmap_bit_p (node->modified_regnos, orig_regno))
+	return false;
+      else if (node->entered_from_non_parent_p)
+	/* If there is a path from a destination loop block to the
+	   source loop header containing basic blocks of non-parents
+	   (grandparents) of the source loop, we should have checked
+	   modifications of the pseudo on this path too to decide
+	   about possibility to remove the store.  It could be done by
+	   solving a data-flow problem.  Unfortunately such global
+	   solution would complicate IR flattening.  Therefore we just
+	   prohibit removal of the store in such complicated case.  */
+	return false;
+    }
+  gcc_unreachable ();
 }
 
 /* Generate and attach moves to the edge E.  This looks at the final
@@ -322,7 +386,7 @@ generate_edge_moves (edge e)
 	   change_loop).  */
  	if (ALLOCNO_HARD_REGNO (dest_allocno) < 0
 	    && ALLOCNO_HARD_REGNO (src_allocno) >= 0
-	    && not_modified_p (src_allocno, dest_allocno))
+	    && store_can_be_removed_p (src_allocno, dest_allocno))
 	  {
 	    ALLOCNO_MEM_OPTIMIZED_DEST (src_allocno) = dest_allocno;
 	    ALLOCNO_MEM_OPTIMIZED_DEST_P (dest_allocno) = true;
@@ -983,6 +1047,7 @@ ira_emit (bool loops_p)
   ira_free_bitmap (used_regno_bitmap);
   ira_free_bitmap (renamed_regno_bitmap);
   ira_free_bitmap (local_allocno_bitmap);
+  setup_entered_from_non_parent_p ();
   FOR_EACH_BB (bb)
     {
       at_bb_start[bb->index] = NULL;
Index: ira-build.c
===================================================================
--- ira-build.c	(revision 141823)
+++ ira-build.c	(working copy)
@@ -2096,6 +2096,11 @@ copy_info_to_removed_store_destinations 
       if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
 	ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a) = true;
 #endif
+      ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
+      ALLOCNO_CALLS_CROSSED_NUM (parent_a)
+	+= ALLOCNO_CALLS_CROSSED_NUM (a);
+      ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
+	+= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
       merged_p = true;
     }
   return merged_p;
@@ -2111,7 +2116,7 @@ void
 ira_flattening (int max_regno_before_emit, int ira_max_point_before_emit)
 {
   int i, j, num;
-  bool stop_p, keep_p;
+  bool keep_p;
   int hard_regs_num;
   bool new_pseudos_p, merged_p, mem_dest_p;
   unsigned int n;
@@ -2196,26 +2201,15 @@ ira_flattening (int max_regno_before_emi
 	      continue;
 	    }
 	  new_pseudos_p = true;
-	  first = ALLOCNO_MEM_OPTIMIZED_DEST (a) == NULL ? NULL : a;
-	  stop_p = false;
 	  for (;;)
 	    {
-	      if (first == NULL
-		  && ALLOCNO_MEM_OPTIMIZED_DEST (parent_a) != NULL)
-		first = parent_a;
 	      ALLOCNO_NREFS (parent_a) -= ALLOCNO_NREFS (a);
 	      ALLOCNO_FREQ (parent_a) -= ALLOCNO_FREQ (a);
-	      if (first != NULL
-		  && ALLOCNO_MEM_OPTIMIZED_DEST (first) == parent_a)
-		stop_p = true;
-	      else if (!stop_p)
-		{
-		  ALLOCNO_CALL_FREQ (parent_a) -= ALLOCNO_CALL_FREQ (a);
-		  ALLOCNO_CALLS_CROSSED_NUM (parent_a)
-		    -= ALLOCNO_CALLS_CROSSED_NUM (a);
-		  ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
-		    -= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
-		}
+	      ALLOCNO_CALL_FREQ (parent_a) -= ALLOCNO_CALL_FREQ (a);
+	      ALLOCNO_CALLS_CROSSED_NUM (parent_a)
+		-= ALLOCNO_CALLS_CROSSED_NUM (a);
+	      ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
+		-= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
 	      ira_assert (ALLOCNO_CALLS_CROSSED_NUM (parent_a) >= 0
 			  && ALLOCNO_NREFS (parent_a) >= 0
 			  && ALLOCNO_FREQ (parent_a) >= 0);