Graphite review, graphite parts [1/n]

[Richard Guenther <rguenther at suse dot de>]

This is part one (from unknown N) of the graphite parts review
http://cri.ensmp.fr/people/pop/gcc/1142_graphite.diff

Find comments inline.


+#include "graphite.h"
+#include "pointer-set.h"
+
+VEC (scop_p, heap) *current_scops;

Make that static?


+/* For each block, the PHI nodes that need to be rewritten are stored into
+   these vectors.  */
+typedef VEC(gimple, heap) *gimple_vec;
+DEF_VEC_P (gimple_vec);
+DEF_VEC_ALLOC_P (gimple_vec, heap);

The same exists in tree-into-ssa.c.  Please move it to gimple.h instead
and remove the copy from tree-into-ssa.c.


+/* Creates an empty mapping.  */
+
+static graphite_loops_mapping
+create_loops_mapping (void)
+{
+  graphite_loops_mapping node = GGC_NEW (struct graphite_loop_node);
+  node->num = -1;
+  node->children = VEC_alloc (graphite_loops_mapping, heap, 3);
+  return node;
+}
+
+/* Creates a mapping for loop number NUM.  */
+
+static graphite_loops_mapping
+create_loops_mapping_num (int num)
+{
+  graphite_loops_mapping new_mapping = create_loops_mapping ();
+  new_mapping->num = num;
+  return new_mapping;
+}
+
+/* Debug recursive helper.  */
+
+static void
+debug_loop_mapping_1 (graphite_loops_mapping node, int depth)
+{
+  if (node != NULL)
+    {
+      int i;
+      graphite_loops_mapping child;
+
+      if (node->num != -1)
+	fprintf (stderr, "%d: %d\n", node->num , depth);
+
+      for (i = 0; VEC_iterate (graphite_loops_mapping, node->children, i, child); i++)
+	debug_loop_mapping_1 (child, depth+1);
+    }
+}
+
+/* Debugs the loop mapping for SCOP.  */
+
+void
+debug_loop_mapping (scop_p scop)
+{
+  graphite_loops_mapping mapping = SCOP_LOOPS_MAPPING (scop);
+
+  fprintf (stderr, "Mapping:\n");
+  debug_loop_mapping_1 (mapping, -1);
+  fprintf (stderr, "\n");
+}
+
+/* Get maximum loop num in mapping.  */
+
+static int
+graphite_loops_mapping_max_loop_num (graphite_loops_mapping mapping)
+{
+  int result = -1;
+  int i;
+
+  if (mapping != NULL)
+    {
+      graphite_loops_mapping child;
+
+      result = mapping->num;
+
+      for (i = 0; VEC_iterate (graphite_loops_mapping, mapping->children, i, child); i++)
+	{
+	  int max_child = graphite_loops_mapping_max_loop_num(child);
+
+	  result = result < max_child ? max_child : result;
+	}
+    }
+  return result;
+}
+
+/* Gets the loop mapping for loop number NUM.  */
+
+static graphite_loops_mapping
+get_loop_mapping_for_num (graphite_loops_mapping mapping, int num)
+{
+  graphite_loops_mapping result = NULL;
+
+  if (mapping->num == num)
+    return mapping;
+  else 
+    {
+      int i;
+      graphite_loops_mapping child;
+
+      for (i = 0; VEC_iterate (graphite_loops_mapping, mapping->children, i, child); i++)
+	{
+	  result = get_loop_mapping_for_num (child, num);
+	  if (result)
+	    return result;
+	}
+    }
+
+  return NULL;
+}
+
+/* Add CHILD mapping to PARENT.  */
+
+static void
+graphite_loops_mapping_add_child (graphite_loops_mapping parent, graphite_loops_mapping child)
+{
+  VEC_safe_push (graphite_loops_mapping, heap, parent->children, child);
+}
+
+/* Adds CHILD_NUM under PARENT.  */
+
+static void
+graphite_loops_mapping_add_child_num (graphite_loops_mapping parent, int child_num)
+{
+  graphite_loops_mapping child = create_loops_mapping_num (child_num);
+  graphite_loops_mapping_add_child (parent, child);
+}
+
+/* Insert NEW_CHILD_NUM under PARENT_NUM in the SCOP loop mapping.  */
+
+static void
+graphite_loops_mapping_insert_child (scop_p scop, int parent_num, int new_child_num)
+{
+  graphite_loops_mapping parent = SCOP_LOOPS_MAPPING (scop);
+  if (parent_num != -1) 
+    parent = get_loop_mapping_for_num (parent, parent_num);
+  graphite_loops_mapping_add_child_num (parent, new_child_num);
+}
+
+/* Returns the mapping for the parent of CHILD_NUM.  */
+
+static graphite_loops_mapping
+graphite_loops_mapping_parent (graphite_loops_mapping mapping, int child_num)
+{
+  graphite_loops_mapping result;
+  if (mapping == NULL)
+    return NULL;
+  else
+    {
+      int i;
+      graphite_loops_mapping child;
+      
+      for (i = 0; VEC_iterate (graphite_loops_mapping, mapping->children, i, child); i++)
+	{
+	  if (child->num  == child_num)
+	    return mapping;
+	  result = 
+	    graphite_loops_mapping_parent (child, child_num);
+	  if (result != NULL)
+	    return result;
+	}
+      return NULL;
+    }
+}
+
+/* Returns the mapped index of the loop NUM.  */
+
+static int 
+get_loop_mapped_depth_for_num (graphite_loops_mapping mapping, int num)
+{
+  if (mapping == NULL)
+    return -1;
+  else if (mapping->num == num)
+    return 0;
+  else
+    {
+      int result = -1;
+      int i;
+      graphite_loops_mapping child;
+      
+      for (i = 0; VEC_iterate (graphite_loops_mapping, mapping->children, i, child); i++)
+	if (result == -1)
+	  result = get_loop_mapped_depth_for_num (child, num);
+      
+      return (result == -1) ? result : result + 1;
+    }
+  return -1;
+}
+
+/* Get the mapped depth for LOOP.  */
+
+static int
+get_loop_mapped_depth (scop_p scop, struct loop *loop)
+{
+  int num = loop->num;
+  int depth = get_loop_mapped_depth_for_num (SCOP_LOOPS_MAPPING (scop), num);
+
+  if (depth == -1)
+    return loop_depth(loop)-1;
+  else
+    /* Compensate for root node */
+    return depth-1;
+}
+
+/* Set the mapping NUM for loop at DEPTH.  */
+
+static void
+split_loop_mapped_depth_for_num (graphite_loops_mapping mapping, int new_num, int num, 
+				 graphite_loops_mapping pred, int child_index)
+{
+  
+  if(mapping->num == num)
+    {
+      graphite_loops_mapping new_node = create_loops_mapping ();
+      graphite_loops_mapping split_node = VEC_index (graphite_loops_mapping, pred->children, child_index);
+      graphite_loops_mapping_add_child (new_node, split_node);
+      new_node->num = new_num;
+      VEC_replace (graphite_loops_mapping, pred->children, child_index, new_node);
+    }
+  else
+    {
+      int i;
+      graphite_loops_mapping child;
+
+      for (i = 0; VEC_iterate (graphite_loops_mapping, mapping->children, i, child); i++)
+	split_loop_mapped_depth_for_num (child, new_num, num, mapping, i);
+    }
+}
+
+static void
+loop_mapped_depth_split_loop (scop_p scop, int new_num, loop_p loop)
+{
+  split_loop_mapped_depth_for_num (SCOP_LOOPS_MAPPING (scop), new_num, loop->num, NULL, false);
+}
+
+/* Swap mapped locations for loops NUM1 and NUM2.  */
+
+static void swap_loop_mapped_depth_for_num (scop_p scop, int num1, int num2)
+{
+  graphite_loops_mapping mapping = SCOP_LOOPS_MAPPING (scop);
+  graphite_loops_mapping num1_node = get_loop_mapping_for_num (mapping, num1);
+  graphite_loops_mapping num2_node = get_loop_mapping_for_num (mapping, num2);
+  num1_node->num = num2;
+  num2_node->num = num1;
+}


With all this new code I miss an overall description on what this
"loop mapping" stuff is, what it is used for and how its representation
looks like.  Without that I cannot reasonably review it.  But from a
quick look it has some long lines that need splitting and it has some
linear walks over arrays that look potentially slow.

Please put a page of description in front of these functions.

More long lines follow.  Please go over graphite.[ch] and split them
appropriately so they fit 80 columns.

+
+/* Create a new loop num for GB.  */
+
+static int
+create_num_from_index (graphite_bb_p gb, int index)
+{
+  int max_num = graphite_loops_mapping_max_loop_num (SCOP_LOOPS_MAPPING (GBB_SCOP (gb)));
+  int new_num = max_num + 1;
+  num_map_p new_index_num = GGC_NEW (struct num_map);
+  if (GBB_INDEX_TO_NUM_MAP(gb) == NULL)
+    GBB_INDEX_TO_NUM_MAP(gb) = VEC_alloc (num_map_p, heap, 3);
+  
+  new_index_num->index = index;
+  new_index_num->num = new_num;
+  VEC_safe_push (num_map_p, heap, GBB_INDEX_TO_NUM_MAP (gb), new_index_num);
+  return new_num;
+}
+
+/* Get the id number of a loop from its INDEX.  */
+
+static int
+get_num_from_index (graphite_bb_p gb, int index)
+{
+  int i;
+  num_map_p index_num;
+
+  for (i = 0; VEC_iterate (num_map_p, GBB_INDEX_TO_NUM_MAP (gb), i, index_num); i++)
+    if (index == index_num->index)
+      return index_num->num;
+
+  gcc_unreachable();
+}
+
+/* Swap mapped locations for loops at DEPTH1 and DEPTH2.  */
+
+static void 
+swap_loop_mapped_depth (scop_p scop, graphite_bb_p gb, int depth1, int depth2)
+{
+  loop_p loop1 = gbb_loop_at_index (gb, depth1);
+  loop_p loop2 = gbb_loop_at_index (gb, depth2);
+  int num1 = (loop1 == NULL) ? get_num_from_index (gb, depth1 + 1) : loop1->num;
+  int num2 = (loop2 == NULL) ? get_num_from_index (gb, depth2 + 1) : loop2->num;
+
+  swap_loop_mapped_depth_for_num (scop, num1, num2);
+}
+
+typedef VEC(name_tree, heap) **loop_iv_stack;
+void loop_iv_stack_debug (loop_iv_stack);
+
+/* Push (IV, NAME) on STACK.  */
+
+static void 
+loop_iv_stack_push (loop_iv_stack stack, tree iv, const char *name)
+{
+  name_tree named_iv = XNEW (struct name_tree);
+  named_iv->t = iv;
+  named_iv->name = name;
+  VEC_safe_push (name_tree, heap, *stack, named_iv);
+}

Note that you can have vectors of structs - that avoids allocating
each (very small) element separately.  Just use DEF_VEC_O (name_tree_s).
That simplifies allocation and deallocation and even speeds up stuff.

+
+/* Pops an element out of STACK.  */
+
+static void
+loop_iv_stack_pop (loop_iv_stack stack)
+{
+  VEC_pop (name_tree, *stack);
+}
+
+/* Get the IV at INDEX in STACK.  */
+
+static tree
+loop_iv_stack_get_iv (loop_iv_stack stack, int index)
+{
+  name_tree named_iv = VEC_index (name_tree, *stack, index);
+  return named_iv->t;
+}
+
+/* Get the IV from its NAME in STACK.  */
+
+static tree
+loop_iv_stack_get_iv_from_name (loop_iv_stack stack, const char* name)
+{
+  int i;
+  name_tree iv;
+  for (i = 0; VEC_iterate (name_tree, *stack, i, iv); i++)
+    if (!strcmp (name, iv->name))
+      return iv->t;

Sorry - but this doesn't scale.  Didn't you want to fix Cloog instead
so this isn't necessary?  Otherwise may I suggest you create IV names
like "Inum" and just use atoi(&name[1]) as index into the stack?  Or
use a hashtable - but I guess the names are not meaningful enough
that the Inum trick would not work.

+
+  return NULL;
+}
+
+/* Prints on stderr the contents of STACK.  */
+
+void
+loop_iv_stack_debug (loop_iv_stack stack)
+{
+  int i;
+  name_tree iv;
+  bool first = true;
+
+  fprintf (stderr, "(");
+
+  for (i = 0; VEC_iterate (name_tree, *stack, i, iv); i++)
+    {
+      if (first) 
+	first = false;
+      else
+	fprintf (stderr, " ");
+      fprintf (stderr, "%s:", iv->name);
+      print_generic_expr (stderr, iv->t, 0);
+    }
+
+  fprintf (stderr, ")\n");
+}
+
+/* Get the IV from its SSA_NAME.  */
+
+static name_tree
+get_old_iv_from_ssa_name (scop_p scop, loop_p old_loop_father, tree ssa_name)
+{
+  tree var = SSA_NAME_VAR (ssa_name);
+  int i;
+  name_tree oldiv;
+  
+  for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, oldiv); i++)
+    {
+      loop_p current_loop_father = old_loop_father;
+      while (current_loop_father)
+	{
+	  if(var == oldiv->t && oldiv->loop == current_loop_father) 
+	    return oldiv;
+	  current_loop_father = loop_outer (current_loop_father);
+	}

I don't follow this logic.  What role does old_loop_father play here
(you don't mention that in the function description).  The function
name suggests that you can simply use a VEC indexed by SSA_NAME
(which we allocate densely) and do
  return VEC_index (..., SSA_NAME_VERSION (ssa_name));

+    }
+  return NULL;
+
+}
+
+static CloogMatrix *schedule_to_scattering (graphite_bb_p, int);
+static inline int nb_loops_around_gb (graphite_bb_p gb);
+
+/* Returns a new loop_to_cloog_loop_str structure.  */
+
+static inline struct loop_to_cloog_loop_str *
+new_loop_to_cloog_loop_str (int loop_num,
+                            int loop_position,
+                            CloogLoop *cloog_loop)
+{
+  struct loop_to_cloog_loop_str *result;
+
+  result = XNEWVEC (struct loop_to_cloog_loop_str, 1);

XNEW (struct loop_to_cloog_loop_str)

+  result->loop_num = loop_num;
+  result->cloog_loop = cloog_loop;
+  result->loop_position = loop_position;
+
+  return result;
+}
+
+/* Hash function for SCOP_LOOP2CLOOG_LOOP hash table.  */
+
+static hashval_t
+hash_loop_to_cloog_loop (const void *elt)
+{
+  return ((const struct loop_to_cloog_loop_str *) elt)->loop_num;
+}
+
+/* Equality function for SCOP_LOOP2CLOOG_LOOP hash table.  */
+
+static int
+eq_loop_to_cloog_loop (const void *el1, const void *el2)
+{
+  const struct loop_to_cloog_loop_str *elt1, *elt2;
+
+  elt1 = (const struct loop_to_cloog_loop_str *) el1;
+  elt2 = (const struct loop_to_cloog_loop_str *) el2;
+  return elt1->loop_num == elt2->loop_num;
+}
>
+/* Free function for SCOP_LOOP2CLOOG_LOOP.  */
+
+static void
+del_loop_to_cloog_loop (void *e)
+{
+  free (e);
+}

You can simply use free itself in htab_create.

I got tired and stopped reviewing here.  To be continued... ;)

Richard.