graphite.c (bb_in_sese_p, [...]): Moved.

2009-02-04  Tobias Grosser  <grosser@fim.uni-passau.de> 

	* graphite.c (bb_in_sese_p, sese_build_livein_liveouts_use,
	sese_build_livein_liveouts_bb, sese_build_livein_liveouts,
	register_bb_in_sese, new_sese, free_sese): Moved.
	(dot_scop_1, build_scop_loop_nests, build_loop_iteration_domains,
	outermost_loop_in_scop, build_scop_iteration_domain,
	expand_scalar_variables_ssa_name, get_vdef_before_scop,
	limit_scops): Use bb_in_sese_p instead of bb_in_scop_p.
	Use loop_in_sese_p instead of loop_in_scop_p.
	(new_graphite_bb, gloog): Do not initialize SCOP_BBS_B.
	(new_scop, free_scop): Remove SCOP_LOOP2CLOOG_LOOP and SCOP_BBS_B.
	(scopdet_basic_block_info): Fix bug in scop detection.
	(new_loop_to_cloog_loop_str, hash_loop_to_cloog_loop,
	eq_loop_to_cloog_loop): Remove.
	(nb_loops_around_loop_in_scop, nb_loop
	ref_nb_loops): Moved here...
	* graphite.h (ref_nb_loops): ... from here.
	(struct scop): Remove bbs_b bitmap and loop2cloog_loop.
	(loop_domain_dim, loop_iteration_vector_dim): Remove.
	(SCOP_BBS_B, bb_in_scop_p, loop_in_scop_p): Removed.
	* testsuite/gcc.dg/graphite/scop-19.c: New

From-SVN: r143947

1 files changed, 197 insertions, 151 deletions

diff --git a/gcc/graphite.c b/gcc/graphite.c
index 3cb24b8..a4d5e36 100644
--- a/gcc/graphite.c
+++ b/gcc/graphite.c
@@ -69,6 +69,147 @@ gmp_cst_to_tree (tree type, Value v)
   return build_int_cst (type, value_get_si (v));
 }
 
+/* Returns true when BB is in REGION.  */
+
+static bool
+bb_in_sese_p (basic_block bb, sese region)
+{
+  return pointer_set_contains (SESE_REGION_BBS (region), bb);
+}
+
+/* Returns true when LOOP is in the SESE region R.  */
+
+static inline bool 
+loop_in_sese_p (struct loop *loop, sese r)
+{
+  return (bb_in_sese_p (loop->header, r)
+	  && bb_in_sese_p (loop->latch, r));
+}
+
+/* For a USE in BB, if BB is outside REGION, mark the USE in the
+   SESE_LIVEIN and SESE_LIVEOUT sets.  */
+
+static void
+sese_build_livein_liveouts_use (sese region, basic_block bb, tree use)
+{
+  unsigned ver;
+  basic_block def_bb;
+
+  if (TREE_CODE (use) != SSA_NAME)
+    return;
+
+  ver = SSA_NAME_VERSION (use);
+  def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
+  if (!def_bb
+      || !bb_in_sese_p (def_bb, region)
+      || bb_in_sese_p (bb, region))
+    return;
+
+  if (!SESE_LIVEIN_VER (region, ver))
+    SESE_LIVEIN_VER (region, ver) = BITMAP_ALLOC (NULL);
+
+  bitmap_set_bit (SESE_LIVEIN_VER (region, ver), bb->index);
+  bitmap_set_bit (SESE_LIVEOUT (region), ver);
+}
+
+/* Marks for rewrite all the SSA_NAMES defined in REGION and that are
+   used in BB that is outside of the REGION.  */
+
+static void
+sese_build_livein_liveouts_bb (sese region, basic_block bb)
+{
+  gimple_stmt_iterator bsi;
+  edge e;
+  edge_iterator ei;
+  ssa_op_iter iter;
+  tree var;
+
+  FOR_EACH_EDGE (e, ei, bb->succs)
+    for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi))
+      sese_build_livein_liveouts_use (region, bb,
+				      PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi), e));
+
+  for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+    FOR_EACH_SSA_TREE_OPERAND (var, gsi_stmt (bsi), iter, SSA_OP_ALL_USES)
+      sese_build_livein_liveouts_use (region, bb, var);
+}
+
+/* Build the SESE_LIVEIN and SESE_LIVEOUT for REGION.  */
+
+void
+sese_build_livein_liveouts (sese region)
+{
+  basic_block bb;
+
+  SESE_LIVEOUT (region) = BITMAP_ALLOC (NULL);
+  SESE_NUM_VER (region) = num_ssa_names;
+  SESE_LIVEIN (region) = XCNEWVEC (bitmap, SESE_NUM_VER (region));
+
+  FOR_EACH_BB (bb)
+    sese_build_livein_liveouts_bb (region, bb);
+}
+
+/* Register basic blocks belonging to a region in a pointer set.  */
+
+static void
+register_bb_in_sese (basic_block entry_bb, basic_block exit_bb, sese region)
+{
+  edge_iterator ei;
+  edge e;
+  basic_block bb = entry_bb;
+
+  FOR_EACH_EDGE (e, ei, bb->succs)
+    {
+      if (!pointer_set_contains (SESE_REGION_BBS (region), e->dest) &&
+	  e->dest->index != exit_bb->index)
+	{	
+	  pointer_set_insert (SESE_REGION_BBS (region), e->dest);
+	  register_bb_in_sese (e->dest, exit_bb, region);
+	}
+    }
+}
+
+/* Builds a new SESE region from edges ENTRY and EXIT.  */
+
+sese
+new_sese (edge entry, edge exit)
+{
+  sese res = XNEW (struct sese);
+
+  SESE_ENTRY (res) = entry;
+  SESE_EXIT (res) = exit;
+  SESE_REGION_BBS (res) = pointer_set_create ();
+  register_bb_in_sese (entry->dest, exit->dest, res);
+
+  SESE_LIVEOUT (res) = NULL;
+  SESE_NUM_VER (res) = 0;
+  SESE_LIVEIN (res) = NULL;
+
+  return res;
+}
+
+/* Deletes REGION.  */
+
+void
+free_sese (sese region)
+{
+  int i;
+
+  for (i = 0; i < SESE_NUM_VER (region); i++)
+    BITMAP_FREE (SESE_LIVEIN_VER (region, i));
+
+  if (SESE_LIVEIN (region))
+    free (SESE_LIVEIN (region));
+
+  if (SESE_LIVEOUT (region))
+    BITMAP_FREE (SESE_LIVEOUT (region));
+
+  pointer_set_destroy (SESE_REGION_BBS (region));
+  XDELETE (region);
+}
+
+
+
 /* Debug the list of old induction variables for this SCOP.  */
 
 void
@@ -701,7 +842,7 @@ dot_scop_1 (FILE *file, scop_p scop)
       if (bb == exit)
 	fprintf (file, "%d [shape=box];\n", bb->index);
 
-      if (bb_in_scop_p (bb, scop)) 
+      if (bb_in_sese_p (bb, SCOP_REGION (scop))) 
 	fprintf (file, "%d [color=red];\n", bb->index);
 
       FOR_EACH_EDGE (e, ei, bb->succs)
@@ -755,7 +896,7 @@ dot_all_scops_1 (FILE *file)
 
       /* Select color for SCoP.  */
       for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
-	if (bb_in_scop_p (bb, scop)
+	if (bb_in_sese_p (bb, SCOP_REGION (scop))
 	    || (SCOP_EXIT (scop) == bb)
 	    || (SCOP_ENTRY (scop) == bb))
 	  {
@@ -818,7 +959,7 @@ dot_all_scops_1 (FILE *file)
 
 	    fprintf (file, "    <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color);
         
-	    if (!bb_in_scop_p (bb, scop))
+	    if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
 	      fprintf (file, " ("); 
 
 	    if (bb == SCOP_ENTRY (scop)
@@ -831,7 +972,7 @@ dot_all_scops_1 (FILE *file)
 	    else
 	      fprintf (file, " %d ", bb->index);
 
-	    if (!bb_in_scop_p (bb, scop))
+	    if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
 	      fprintf (file, ")");
 
 	    fprintf (file, "</TD></TR>\n");
@@ -887,7 +1028,8 @@ outermost_loop_in_scop (scop_p scop, basic_block bb)
   struct loop *nest;
 
   nest = bb->loop_father;
-  while (loop_outer (nest) && loop_in_scop_p (loop_outer (nest), scop))
+  while (loop_outer (nest)
+	 && loop_in_sese_p (loop_outer (nest), SCOP_REGION (scop)))
     nest = loop_outer (nest);
 
   return nest;
@@ -1133,8 +1275,6 @@ new_graphite_bb (scop_p scop, basic_block bb)
   struct loop *nest = outermost_loop_in_scop (scop, bb);
   gimple_stmt_iterator gsi;
 
-  bitmap_set_bit (SCOP_BBS_B (scop), bb->index);
-
   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
     find_data_references_in_stmt (nest, gsi_stmt (gsi), &drs);
 
@@ -1273,138 +1413,6 @@ get_new_name_from_old_name (htab_t map, tree old_name)
 
 
 
-/* Returns true when BB is in REGION.  */
-
-static bool
-bb_in_sese_p (basic_block bb, sese region)
-{
-  return pointer_set_contains (SESE_REGION_BBS (region), bb);
-}
-
-/* For a USE in BB, if BB is outside REGION, mark the USE in the
-   SESE_LIVEIN and SESE_LIVEOUT sets.  */
-
-static void
-sese_build_livein_liveouts_use (sese region, basic_block bb, tree use)
-{
-  unsigned ver;
-  basic_block def_bb;
-
-  if (TREE_CODE (use) != SSA_NAME)
-    return;
-
-  ver = SSA_NAME_VERSION (use);
-  def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
-  if (!def_bb
-      || !bb_in_sese_p (def_bb, region)
-      || bb_in_sese_p (bb, region))
-    return;
-
-  if (!SESE_LIVEIN_VER (region, ver))
-    SESE_LIVEIN_VER (region, ver) = BITMAP_ALLOC (NULL);
-
-  bitmap_set_bit (SESE_LIVEIN_VER (region, ver), bb->index);
-  bitmap_set_bit (SESE_LIVEOUT (region), ver);
-}
-
-/* Marks for rewrite all the SSA_NAMES defined in REGION and that are
-   used in BB that is outside of the REGION.  */
-
-static void
-sese_build_livein_liveouts_bb (sese region, basic_block bb)
-{
-  gimple_stmt_iterator bsi;
-  edge e;
-  edge_iterator ei;
-  ssa_op_iter iter;
-  tree var;
-
-  FOR_EACH_EDGE (e, ei, bb->succs)
-    for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi))
-      sese_build_livein_liveouts_use (region, bb,
-				      PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi), e));
-
-  for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
-    FOR_EACH_SSA_TREE_OPERAND (var, gsi_stmt (bsi), iter, SSA_OP_ALL_USES)
-      sese_build_livein_liveouts_use (region, bb, var);
-}
-
-/* Build the SESE_LIVEIN and SESE_LIVEOUT for REGION.  */
-
-void
-sese_build_livein_liveouts (sese region)
-{
-  basic_block bb;
-
-  SESE_LIVEOUT (region) = BITMAP_ALLOC (NULL);
-  SESE_NUM_VER (region) = num_ssa_names;
-  SESE_LIVEIN (region) = XCNEWVEC (bitmap, SESE_NUM_VER (region));
-
-  FOR_EACH_BB (bb)
-    sese_build_livein_liveouts_bb (region, bb);
-}
-
-/* Register basic blocks belonging to a region in a pointer set.  */
-
-static void
-register_bb_in_sese (basic_block entry_bb, basic_block exit_bb, sese region)
-{
-  edge_iterator ei;
-  edge e;
-  basic_block bb = entry_bb;
-
-  FOR_EACH_EDGE (e, ei, bb->succs)
-    {
-      if (!pointer_set_contains (SESE_REGION_BBS (region), e->dest) &&
-	  e->dest->index != exit_bb->index)
-	{	
-	  pointer_set_insert (SESE_REGION_BBS (region), e->dest);
-	  register_bb_in_sese (e->dest, exit_bb, region);
-	}
-    }
-}
-
-/* Builds a new SESE region from edges ENTRY and EXIT.  */
-
-sese
-new_sese (edge entry, edge exit)
-{
-  sese res = XNEW (struct sese);
-
-  SESE_ENTRY (res) = entry;
-  SESE_EXIT (res) = exit;
-  SESE_REGION_BBS (res) = pointer_set_create ();
-  register_bb_in_sese (entry->dest, exit->dest, res);
-
-  SESE_LIVEOUT (res) = NULL;
-  SESE_NUM_VER (res) = 0;
-  SESE_LIVEIN (res) = NULL;
-
-  return res;
-}
-
-/* Deletes REGION.  */
-
-void
-free_sese (sese region)
-{
-  int i;
-
-  for (i = 0; i < SESE_NUM_VER (region); i++)
-    BITMAP_FREE (SESE_LIVEIN_VER (region, i));
-
-  if (SESE_LIVEIN (region))
-    free (SESE_LIVEIN (region));
-
-  if (SESE_LIVEOUT (region))
-    BITMAP_FREE (SESE_LIVEOUT (region));
-
-  pointer_set_destroy (SESE_REGION_BBS (region));
-  XDELETE (region);
-}
-
-
-
 /* Creates a new scop starting with ENTRY.  */
 
 static scop_p
@@ -1417,7 +1425,6 @@ new_scop (edge entry, edge exit)
   SCOP_REGION (scop) = new_sese (entry, exit);
   SCOP_BBS (scop) = VEC_alloc (graphite_bb_p, heap, 3);
   SCOP_OLDIVS (scop) = VEC_alloc (name_tree, heap, 3);
-  SCOP_BBS_B (scop) = BITMAP_ALLOC (NULL);
   SCOP_LOOPS (scop) = BITMAP_ALLOC (NULL);
   SCOP_LOOP_NEST (scop) = VEC_alloc (loop_p, heap, 3);
   SCOP_ADD_PARAMS (scop) = true;
@@ -1446,7 +1453,6 @@ free_scop (scop_p scop)
     free_graphite_bb (gb);
 
   VEC_free (graphite_bb_p, heap, SCOP_BBS (scop));
-  BITMAP_FREE (SCOP_BBS_B (scop));
   BITMAP_FREE (SCOP_LOOPS (scop));
   VEC_free (loop_p, heap, SCOP_LOOP_NEST (scop));
 
@@ -1632,6 +1638,12 @@ scopdet_basic_block_info (basic_block bb, VEC (sd_region, heap) **scops,
       result.next = NULL;
       result.exits = false;
       result.last = bb;
+
+      /* Mark bbs terminating a SESE region difficult, if they start
+	 a condition.  */
+      if (VEC_length (edge, bb->succs) > 1)
+	result.difficult = true; 
+
       break;
 
     case GBB_SIMPLE:
@@ -2410,13 +2422,13 @@ build_scop_loop_nests (scop_p scop)
   struct loop *loop0, *loop1;
 
   FOR_EACH_BB (bb)
-    if (bb_in_scop_p (bb, scop))
+    if (bb_in_sese_p (bb, SCOP_REGION (scop)))
       {
 	struct loop *loop = bb->loop_father;
 
 	/* Only add loops if they are completely contained in the SCoP.  */
 	if (loop->header == bb
-	    && bb_in_scop_p (loop->latch, scop))
+	    && bb_in_sese_p (loop->latch, SCOP_REGION (scop)))
 	  {
 	    if (!scop_record_loop (scop, loop))
 	      return false;
@@ -2442,6 +2454,40 @@ build_scop_loop_nests (scop_p scop)
   return true;
 }
 
+/* Calculate the number of loops around LOOP in the SCOP.  */
+
+static inline int
+nb_loops_around_loop_in_scop (struct loop *l, scop_p scop)
+{
+  int d = 0;
+
+  for (; loop_in_sese_p (l, SCOP_REGION (scop)); d++, l = loop_outer (l));
+
+  return d;
+}
+
+/* Calculate the number of loops around GB in the current SCOP.  */
+
+int
+nb_loops_around_gb (graphite_bb_p gb)
+{
+  return nb_loops_around_loop_in_scop (gbb_loop (gb), GBB_SCOP (gb));
+}
+
+/* Returns the dimensionality of an enclosing loop iteration domain
+   with respect to enclosing SCoP for a given data reference REF.  The
+   returned dimensionality is homogeneous (depth of loop nest + number
+   of SCoP parameters + const).  */
+
+int
+ref_nb_loops (data_reference_p ref)
+{
+  loop_p loop = loop_containing_stmt (DR_STMT (ref));
+  scop_p scop = DR_SCOP (ref);
+
+  return nb_loops_around_loop_in_scop (loop, scop) + scop_nb_params (scop) + 2;
+}
+
 /* Build dynamic schedules for all the BBs. */
 
 static void
@@ -3086,13 +3132,14 @@ build_loop_iteration_domains (scop_p scop, struct loop *loop,
   else
     gcc_unreachable ();
 
-  if (loop->inner && loop_in_scop_p (loop->inner, scop))
+  if (loop->inner && loop_in_sese_p (loop->inner, SCOP_REGION (scop)))
     build_loop_iteration_domains (scop, loop->inner, cstr, nb_outer_loops + 1);
 
   /* Only go to the next loops, if we are not at the outermost layer.  These
      have to be handled seperately, as we can be sure, that the chain at this
      layer will be connected.  */
-  if (nb_outer_loops != 0 && loop->next && loop_in_scop_p (loop->next, scop))
+  if (nb_outer_loops != 0 && loop->next && loop_in_sese_p (loop->next,
+							   SCOP_REGION (scop)))
     build_loop_iteration_domains (scop, loop->next, outer_cstr, nb_outer_loops);
 
   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
@@ -3368,7 +3415,7 @@ build_scop_conditions_1 (VEC (gimple, heap) **conditions,
   VEC (basic_block, heap) *dom;
   
   /* Make sure we are in the SCoP.  */
-  if (!bb_in_scop_p (bb, scop))
+  if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
     return true;
 
   if (bb_contains_non_iv_scalar_phi_nodes (bb))
@@ -3562,7 +3609,7 @@ build_scop_iteration_domain (scop_p scop)
   /* Build cloog loop for all loops, that are in the uppermost loop layer of
      this SCoP.  */
   for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop); i++)
-    if (!loop_in_scop_p (loop_outer (loop), scop))
+    if (!loop_in_sese_p (loop_outer (loop), SCOP_REGION (scop)))
       {
         /* The outermost constraints is a matrix that has:
            -first column: eq/ineq boolean
@@ -4138,7 +4185,7 @@ expand_scalar_variables_ssa_name (tree op0, basic_block bb,
   else
     {
       if (gimple_code (def_stmt) != GIMPLE_ASSIGN
-	  || !bb_in_scop_p (gimple_bb (def_stmt), scop))
+	  || !bb_in_sese_p (gimple_bb (def_stmt), SCOP_REGION (scop)))
 	return get_new_name_from_old_name (map, op0);
 
       var0 = gimple_assign_rhs1 (def_stmt);
@@ -5142,7 +5189,7 @@ get_vdef_before_scop (scop_p scop, tree name, sbitmap visited)
   basic_block def_bb = gimple_bb (def_stmt);
 
   if (!def_bb
-      || !bb_in_scop_p (def_bb, scop))
+      || !bb_in_sese_p (def_bb, SCOP_REGION (scop)))
     return name;
 
   if (TEST_BIT (visited, def_bb->index))
@@ -5396,7 +5443,6 @@ gloog (scop_p scop, struct clast_stmt *stmt)
     {
       basic_block bb = SESE_EXIT (SCOP_REGION (scop))->dest;
       SESE_EXIT (SCOP_REGION (scop)) = split_block_after_labels (bb);
-      bitmap_set_bit (SCOP_BBS_B (scop), bb->index);
       pointer_set_insert (SESE_REGION_BBS (SCOP_REGION (scop)), bb);
     }
 
@@ -6031,7 +6077,7 @@ limit_scops (void)
 	continue;
 
       for (j = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), j, loop); j++) 
-        if (!loop_in_scop_p (loop_outer (loop), scop))
+        if (!loop_in_sese_p (loop_outer (loop), SCOP_REGION (scop)))
           {
 	    sd_region open_scop;
 	    open_scop.entry = loop->header;