2013-03-21 Richard Biener <rguenther@suse.de>

	PR tree-optimization/39326
	* tree-ssa-loop-im.c (bb_loop_postorder): New global static.
	(sort_bbs_in_loop_postorder_cmp): New function.
	(gather_mem_refs_in_loops): Assign mem-ref IDs in loop
	postorder.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@196874 138bc75d-0d04-0410-961f-82ee72b054a4

2 files changed, 49 insertions, 6 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 0058ae75c1b..be4b87fea2a 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,13 @@
 2013-03-21  Richard Biener  <rguenther@suse.de>
 
+	PR tree-optimization/39326
+	* tree-ssa-loop-im.c (bb_loop_postorder): New global static.
+	(sort_bbs_in_loop_postorder_cmp): New function.
+	(gather_mem_refs_in_loops): Assign mem-ref IDs in loop
+	postorder.
+
+2013-03-21  Richard Biener  <rguenther@suse.de>
+
 	* tree-vect-data-refs.c (vect_update_interleaving_chain): Remove.
 	(vect_insert_into_interleaving_chain): Likewise.
 	(vect_drs_dependent_in_basic_block): Inline ...
diff --git a/gcc/tree-ssa-loop-im.c b/gcc/tree-ssa-loop-im.c
index 2557542f09e..0945d266c12 100644
--- a/gcc/tree-ssa-loop-im.c
+++ b/gcc/tree-ssa-loop-im.c
@@ -1622,27 +1622,62 @@ gather_mem_refs_stmt (struct loop *loop, gimple stmt)
   return;
 }
 
+static unsigned *bb_loop_postorder;
+
+/* qsort sort function to sort blocks after their loop fathers postorder.  */
+
+static int
+sort_bbs_in_loop_postorder_cmp (const void *bb1_, const void *bb2_)
+{
+  basic_block bb1 = *(basic_block *)const_cast<void *>(bb1_);
+  basic_block bb2 = *(basic_block *)const_cast<void *>(bb2_);
+  struct loop *loop1 = bb1->loop_father;
+  struct loop *loop2 = bb2->loop_father;
+  if (loop1->num == loop2->num)
+    return 0;
+  return bb_loop_postorder[loop1->num] < bb_loop_postorder[loop2->num] ? -1 : 1;
+}
+
 /* Gathers memory references in loops.  */
 
 static void
 gather_mem_refs_in_loops (void)
 {
   gimple_stmt_iterator bsi;
-  basic_block bb;
+  basic_block bb, *bbs;
   struct loop *loop;
   loop_iterator li;
   bitmap lrefs, alrefs, alrefso;
+  unsigned i, n;
 
+  /* Initialize bb_loop_postorder with a mapping from loop->num to
+     its postorder index.  */
+  i = 0;
+  bb_loop_postorder = XNEWVEC (unsigned, number_of_loops ());
+  FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
+    bb_loop_postorder[loop->num] = i++;
+  /* Collect all basic-blocks in loops and sort them after their
+     loops postorder.  */
+  i = 0;
+  bbs = XNEWVEC (basic_block, n_basic_blocks - NUM_FIXED_BLOCKS);
   FOR_EACH_BB (bb)
+    if (bb->loop_father != current_loops->tree_root)
+      bbs[i++] = bb;
+  n = i;
+  qsort (bbs, n, sizeof (basic_block), sort_bbs_in_loop_postorder_cmp);
+  free (bb_loop_postorder);
+
+  /* Visit blocks in loop postorder and assign mem-ref IDs in that order.
+     That results in better locality for all the bitmaps.  */
+  for (i = 0; i < n; ++i)
     {
-      loop = bb->loop_father;
-      if (loop == current_loops->tree_root)
-	continue;
-
+      basic_block bb = bbs[i];
       for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
-	gather_mem_refs_stmt (loop, gsi_stmt (bsi));
+        gather_mem_refs_stmt (bb->loop_father, gsi_stmt (bsi));
     }
 
+  free (bbs);
+
   /* Propagate the information about accessed memory references up
      the loop hierarchy.  */
   FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)