[graphite] build_scops_conditions

[Tobias Grosser <grosser at fim dot uni-passau dot de>]

Hi graphities,

Adrien has written code to detect for every bb the conditions,
that restrict the execution of this code.

Example:

for (i = 0; i <= 20; i++)
  {
    A

    if (2i <= 8)
      B
  }

So for B there is a additional condition (2i <= 8).

At the moment, we just add the conditions to the gbbs, but I hope someone
will find the time, to add them to the domain matrix.

I would like to commit this code. Patch attached.

See you
Tobias

2008-06-11  Adrien Eliche  <aeliche@isty.uvsq.fr>

	* graphite.c (print_graphite_bb): Add condition printing.
	(dump_value): New.
	(dump_gbb_conditions): New.
	(build_scop_conditions_1): New.
	(build_scop_conditions): New.
	* graphite.h (graphite_bb): Add conditions.
diff --git a/gcc/graphite.c b/gcc/graphite.c
index 54086bf..1620a00 100644
--- a/gcc/graphite.c
+++ b/gcc/graphite.c
@@ -50,6 +50,8 @@ VEC (scop_p, heap) *current_scops;
 
 static tree harmful_stmt_in_bb (struct loop *outermost_loop, basic_block);
 static CloogMatrix *schedule_to_scattering (graphite_bb_p);
+static void dump_gbb_conditions (FILE * file, graphite_bb_p gbb);
+static graphite_bb_p graphite_bb_from_bb (basic_block bb, scop_p scop);
 
 /* Returns a new loop_to_cloog_loop_str structure.  */
 
@@ -116,6 +118,10 @@ print_graphite_bb (FILE *file, graphite_bb_p gb, int indent, int verbosity)
   cloog_matrix_print (file, schedule_to_scattering (gb));
   fprintf (file, "       )\n");
 
+  fprintf (file, "       (conditions: \n");
+  dump_gbb_conditions (dump_file, gb);
+  fprintf (file, "       )\n");
+
   fprintf (file, ")\n");
 }
 
@@ -1121,6 +1127,267 @@ build_scop_bbs (scop_p scop)
   sbitmap_free (visited);
 }
 
+/* Dump  an integer constant or a SSA_NAME */
+
+static void
+dump_value (FILE * file, tree node)
+{
+  long val;
+  enum tree_code code = TREE_CODE (node);
+
+  switch (code)
+    {
+    case INTEGER_CST:
+      val = int_cst_value (node);
+      fprintf (file, "%ld", val);
+      break;
+
+    case SSA_NAME:
+      {
+	tree var = SSA_NAME_VAR (node);
+	if (DECL_NAME (var))
+	  fprintf (file, "%s", IDENTIFIER_POINTER (DECL_NAME (var)));
+	else
+	  {
+	    char c = TREE_CODE (var) == CONST_DECL ? 'C' : 'D';
+	    fprintf (file, "%c.%u", c, DECL_UID (var));
+	  }
+	fprintf (file, "_%d", SSA_NAME_VERSION (node));
+	break;
+      }
+    default:
+      fprintf (file, "?(%s)", tree_code_name[TREE_CODE (node)]);
+      break;
+    }
+}
+
+/* Dump conditions of a graphite basic block */
+
+static void
+dump_gbb_conditions (FILE * file, graphite_bb_p gbb)
+{
+  int i;
+  tree stmt;
+  tree cond;
+  VEC (tree, heap) * conditions = gbb->conditions;
+  VEC (tree, heap) * cases = gbb->condition_cases;
+
+  if (VEC_empty (tree, conditions))
+    return;
+
+  fprintf (file, "\n\tbb %d\t: cond = {", gbb->bb->index);
+  for (i = 0; VEC_iterate (tree, conditions, i, stmt); i++)
+    {
+      switch (TREE_CODE (stmt))
+	{
+	case COND_EXPR:
+	  if (VEC_index (tree, cases, i) == NULL_TREE)
+	    fprintf (file, "!(");
+	  cond = TREE_OPERAND (stmt, 0);
+	  dump_value (file, TREE_OPERAND (cond, 0));
+	  switch (TREE_CODE (cond))
+	    {
+	    case NE_EXPR:
+	      fprintf (file, " != ");
+	      break;
+	    case EQ_EXPR:
+	      fprintf (file, " == ");
+	      break;
+	    case LT_EXPR:
+	      fprintf (file, " < ");
+	      break;
+	    case GT_EXPR:
+	      fprintf (file, " > ");
+	      break;
+	    case LE_EXPR:
+	      fprintf (file, " <= ");
+	      break;
+	    case GE_EXPR:
+	      fprintf (file, " >= ");
+	      break;
+	    default:
+	      gcc_unreachable ();
+	      break;
+	    }
+	  dump_value (file, TREE_OPERAND (cond, 1));
+	  if (VEC_index (tree, cases, i) == NULL_TREE)
+	    fprintf (file, ")");
+	  break;
+
+	case SWITCH_EXPR:
+	  cond = VEC_index (tree, cases, i);
+	  if (CASE_LOW (cond) && CASE_HIGH (cond))
+	    {
+	      dump_value (file, TREE_OPERAND (stmt, 0));
+	      fprintf (file, " >= ");
+	      dump_value (file, CASE_LOW (cond));
+	      fprintf (file, "; ");
+	      dump_value (file, TREE_OPERAND (stmt, 0));
+	      fprintf (file, " <= ");
+	      dump_value (file, CASE_HIGH (cond));
+	    }
+	  else if (CASE_LOW (cond))
+	    {
+	      dump_value (file, TREE_OPERAND (stmt, 0));
+	      fprintf (file, " == ");
+	      dump_value (file, CASE_LOW (cond));
+	    }
+	  else
+	    fprintf (file, "default");
+	  break;
+	default:
+	  gcc_unreachable ();
+	  break;
+	}
+      fprintf (file, "; ");
+
+    }
+  fprintf (file, "}\n");
+}
+
+
+/* Helper recursive function */
+
+static void
+build_scop_conditions_1 (VEC (tree, heap) ** conditions,
+			 VEC (tree, heap) ** cases, basic_block bb,
+			 scop_p scop)
+{
+  unsigned i, j;
+  graphite_bb_p gbb;
+  block_stmt_iterator bsi;
+  basic_block bb_child, bb_iter;
+  VEC (basic_block, heap) * dom;
+
+  /* Make sure we are in the SCoP */
+  for (i = 0; VEC_iterate (graphite_bb_p, scop->bbs, i, gbb); i++)
+    if (gbb->bb == bb)
+      break;
+  if (i == VEC_length (graphite_bb_p, scop->bbs))
+    return;
+
+  /* record conditions in graphite_bb */
+  graphite_bb_from_bb (bb, scop)->conditions =
+      VEC_copy (tree, heap, *conditions);
+  graphite_bb_from_bb (bb, scop)->condition_cases =
+      VEC_copy (tree, heap, *cases);
+
+
+  dom = get_dominated_by (CDI_DOMINATORS, bb);
+
+  for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+    {
+      tree stmt = bsi_stmt (bsi);
+      VEC (edge, gc) * edges;
+      edge e;
+
+      switch (TREE_CODE (stmt))
+	{
+	case COND_EXPR:
+	  edges = bb->succs;
+	  for (i = 0; VEC_iterate (edge, edges, i, e); i++)
+	    if ((dominated_by_p (CDI_DOMINATORS, e->dest, bb))
+		&& VEC_length (edge, e->dest->preds) == 1)
+	      {
+		/* remove the scanned block from the dominator successors */
+		for (j = 0; VEC_iterate (basic_block, dom, j, bb_iter); j++)
+		  if (bb_iter == e->dest)
+		    {
+		      VEC_unordered_remove (basic_block, dom, j);
+		      break;
+		    }
+
+		/* recursively scan the then or else part */
+		if (e->flags & EDGE_TRUE_VALUE)
+		  VEC_safe_push (tree, heap, *cases, stmt);
+		else if (e->flags & EDGE_FALSE_VALUE)
+		  VEC_safe_push (tree, heap, *cases, NULL_TREE);
+		else
+		  gcc_unreachable ();
+
+		VEC_safe_push (tree, heap, *conditions, stmt);
+		build_scop_conditions_1 (conditions, cases, e->dest, scop);
+		VEC_pop (tree, *conditions);
+		VEC_pop (tree, *cases);
+	      }
+	  break;
+
+	case SWITCH_EXPR:
+	  {
+	    tree vec = SWITCH_LABELS (stmt);
+	    size_t n = TREE_VEC_LENGTH (vec);
+	    size_t n_cases = VEC_length (tree, *conditions);
+
+	    /* in this case switch is not handled */
+	    if (SWITCH_BODY (stmt))
+	      break;
+
+	    VEC_safe_grow (tree, heap, *cases, n_cases + 1);
+	    VEC_safe_push (tree, heap, *conditions, stmt);
+
+	    for (i = 0; i < n; i++)
+	      {
+		basic_block bb_iter;
+		size_t k;
+		bb_child = label_to_block (CASE_LABEL (TREE_VEC_ELT (vec, i)));
+
+		/* do not handled multiple values for the same block */
+		for (k = 0; k < n; k++)
+		  {
+		    if (label_to_block (CASE_LABEL (TREE_VEC_ELT (vec, k))) ==
+			bb_child && i != k)
+		      break;
+		  }
+		if (k != n)
+		  continue;
+
+		/* switch cases with more than one predecessor are not handled */
+		if (VEC_length (edge, bb_child->preds) != 1)
+		  continue;
+
+		/* recursively scan the corresponding 'case' block */
+		VEC_replace (tree, *cases, n_cases, TREE_VEC_ELT (vec, i));
+		build_scop_conditions_1 (conditions, cases, bb_child, scop);
+
+		/* remove the scanned block from the dominator successors */
+		for (j = 0; VEC_iterate (basic_block, dom, j, bb_iter); j++)
+		  if (bb_iter == bb_child)
+		    {
+		      VEC_unordered_remove (basic_block, dom, j);
+		      break;
+		    }
+	      }
+	    VEC_pop (tree, *conditions);
+	    VEC_pop (tree, *cases);
+	    break;
+	  }
+	default:
+	  break;
+	}
+    }
+
+
+  /* scan all immediate dominated successors */
+  for (i = 0; VEC_iterate (basic_block, dom, i, bb_child); i++)
+    build_scop_conditions_1 (conditions, cases, bb_child, scop);
+
+  VEC_free (basic_block, heap, dom);
+}
+
+/* Record all 'if' and 'switch' conditions in each gbb of SCOP */
+
+static void
+build_scop_conditions (scop_p scop)
+{
+  VEC (tree, heap) * conditions = NULL;
+  VEC (tree, heap) * cases = NULL;
+
+  build_scop_conditions_1 (&conditions, &cases, SCOP_ENTRY (scop), scop);
+
+  VEC_free (tree, heap, conditions);
+  VEC_free (tree, heap, cases);
+}
+
 /* Record LOOP as occuring in SCOP.  */
 
 static void
@@ -2866,6 +3133,7 @@ graphite_transform_loops (void)
   for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
     {
       build_scop_bbs (scop);
+      build_scop_conditions (scop);
       build_scop_loop_nests (scop);
       build_scop_canonical_schedules (scop);
       find_scop_parameters (scop);
@@ -2910,3 +3178,4 @@ graphite_transform_loops (void)
 
   free_scops (current_scops);
 }
+
diff --git a/gcc/graphite.h b/gcc/graphite.h
index 2ec5c31..1a95de7 100644
--- a/gcc/graphite.h
+++ b/gcc/graphite.h
@@ -37,6 +37,20 @@ struct graphite_bb
   lambda_vector compressed_alpha_matrix;
   CloogMatrix *domain;
   CloogMatrix *dynamic_schedule;
+  
+  /* Lists containing the restrictions of the conditional statements
+     dominating this bb. This bb can only be executed, if all conditions
+     are true.
+
+     TODO: Add this restrictions to the domain matrix.
+     
+     List of COND_EXPR and SWITCH_EXPR. A COND_EXPR is true only if the 
+     corresponding element in CONDITION_CASES is not NULL_TREE. For a 
+     SWITCH_EXPR the corresponding element in CONDITION_CASES is a 
+     CASE_LABEL_EXPR.  */
+  VEC (tree, heap) *conditions;
+  VEC (tree, heap) *condition_cases;
+
   VEC (data_reference_p, heap) *data_refs;
 };