[graphite] Fix PR37485

[graphite] Fix PR37485

[Harsha Jagasia]

This patch fixes PR37485 with the following:

- In tranlate_clast when clast stmt is a stmt_user, we can end up disconnecting
the edge that is the exit_edge of the scop that is transformed. This state
creates problems because the exit_edge no longer has a destination. Hence when
after translate_clast, the exit_edge is redirected with redirect_edge_succ, the
edge is already disconnected.

- Graphite does not handle clast user stmts with constant arguments.

- Graphite can create scops which overlap. This is an issue if one of the
overlapping scops is transformed which can cause some edges to be redirected.
When the successive overlapping scops are attempted to be transformed, the
basic blocks in the scop are no longer the same.



2008-09-16  Jan Sjodin  <jan.sjodin@amd.com>
            Harsha Jagasia  <harsha.jagasia@amd.com>

        * graphite.c (gmp_cst_to_tree): Moved.
        (iv_stack_entry_is_constant): New.
        (iv_stack_entry_is_iv): New.
        (loop_iv_stack_push): Renamed to loop_iv_stack_push_iv.
        (loop_iv_stack_insert_constant): New.
        (loop_iv_stack_pop): Use new datatpype.
        (loop_iv_stack_get_iv): Same.
        (loop_iv_stack_get_iv_from_name): Same.
        (loop_iv_stack_debug): Renamed to debug_loop_iv_stack.
        (loop_iv_stack_patch_for_consts): New.
        (loop_iv_stack_remove_constants): New.
        (graphite_create_new_loop): Use loop_iv_stack_push_iv.
        (translate_clast): Call loop_iv_stack_patch_for_consts and
        loop_iv_stack_remove_constants.
        (gloog): Use new datatype.  Redirect construction edge to end
        block to avoid accidental deletion.
        (limit_scops): Prevent overlapping scops.
        * graphite.h (enum iv_stack_entry_kind): New.  Tag for data in
        iv stack entry.
        (union iv_stack_entry_data): New.  Data in iv stack entry.
        (struct iv_stack_entry): New.  Datatype for iv stack entries.

	* gcc.dg/graphite/block-2.c: New



Index: testsuite/gcc.dg/graphite/block-2.c
===================================================================
--- testsuite/gcc.dg/graphite/block-2.c	(revision 0)
+++ testsuite/gcc.dg/graphite/block-2.c	(revision 0)
@@ -0,0 +1,33 @@
+/* { dg-options "-O2 -floop-block -fdump-tree-graphite-all" } */
+/* PR37485 fixed, but the test case triggers one more bug,
+   which will be reported seperately under bugzilla.  */
+
+typedef unsigned char   UChar;
+typedef int             Int32;
+typedef unsigned int    UInt32;
+
+void fallbackSort ( UInt32* fmap, 
+                    UInt32* eclass, 
+                    Int32   nblock,
+                    Int32   verb )
+{
+   Int32 ftab[257];
+   Int32 ftabCopy[256];
+   Int32 H, i, j, k, l, r, cc, cc1;
+   Int32 nNotDone;
+   Int32 nBhtab;
+   UChar* eclass8 = (UChar*)eclass;
+
+   if (verb >= 4)
+      VPrintf0 ( "        bucket sorting ...\n" );
+   for (i = 0; i < 257;    i++) ftab[i] = 0;
+   for (i = 0; i < nblock; i++) ftab[eclass8[i]]++;
+   for (i = 0; i < 256;    i++) ftabCopy[i] = ftab[i];
+   for (i = 1; i < 257;    i++) ftab[i] += ftab[i-1];
+
+   for (i = 0; i < nblock; i++) {
+      j = eclass8[i] + ftab [i];
+   }
+   AssertH ( j < 256, 1005 );
+}
+/* { dg-final { scan-tree-dump-times "Loop blocked" 1 "graphite" { xfail *-*-* }} } */
Index: graphite.c
===================================================================
--- graphite.c	(revision 140372)
+++ graphite.c	(working copy)
@@ -60,6 +60,14 @@
 
 static VEC (scop_p, heap) *current_scops;
 
+/* Converts a GMP constant value to a tree and returns it.  */
+
+static tree
+gmp_cst_to_tree (Value v)
+{
+  return build_int_cst (integer_type_node, value_get_si (v));
+}
+
 /* Debug the list of old induction variables for this SCOP.  */
 
 void
@@ -95,24 +103,59 @@
   fprintf (stderr, "\n");
 }
 
+/* Returns true if stack entry is a constant.  */
+
+static bool
+iv_stack_entry_is_constant (iv_stack_entry *entry)
+{
+  return entry->kind == iv_stack_entry_const;
+}
+
+/* Returns true if stack entry is a constant.  */
+
+static bool
+iv_stack_entry_is_iv (iv_stack_entry *entry)
+{
+  return entry->kind == iv_stack_entry_iv;
+}
+
 /* Push (IV, NAME) on STACK.  */
 
 static void 
-loop_iv_stack_push (loop_iv_stack stack, tree iv, const char *name)
+loop_iv_stack_push_iv (loop_iv_stack stack, tree iv, const char *name)
 {
+  iv_stack_entry* entry = XNEW (iv_stack_entry);
   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);
+
+  entry->kind = iv_stack_entry_iv;
+  entry->data.iv = named_iv;
+
+  VEC_safe_push (iv_stack_entry_p, heap, *stack, entry);
 }
 
+/* Inserts a CONSTANT in STACK at INDEX.  */
+
+static void
+loop_iv_stack_insert_constant (loop_iv_stack stack, int index,
+			       tree constant)
+{
+  iv_stack_entry* entry = XNEW (iv_stack_entry);
+  
+  entry->kind = iv_stack_entry_const;
+  entry->data.constant = constant;
+
+  VEC_safe_insert (iv_stack_entry_p, heap, *stack, index, entry);
+}
+
 /* Pops an element out of STACK.  */
 
 static void
 loop_iv_stack_pop (loop_iv_stack stack)
 {
-  VEC_pop (name_tree, *stack);
+  VEC_pop (iv_stack_entry_p, *stack);
 }
 
 /* Get the IV at INDEX in STACK.  */
@@ -120,7 +163,7 @@
 static tree
 loop_iv_stack_get_iv (loop_iv_stack stack, int index)
 {
-  name_tree named_iv = VEC_index (name_tree, *stack, index);
+  name_tree named_iv = VEC_index (iv_stack_entry_p, *stack, index)->data.iv;
 
   return named_iv->t;
 }
@@ -131,11 +174,14 @@
 loop_iv_stack_get_iv_from_name (loop_iv_stack stack, const char* name)
 {
   int i;
-  name_tree iv;
+  iv_stack_entry_p entry;
 
-  for (i = 0; VEC_iterate (name_tree, *stack, i, iv); i++)
-    if (!strcmp (name, iv->name))
-      return iv->t;
+  for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry); i++)
+    {
+      name_tree iv = entry->data.iv;
+      if (!strcmp (name, iv->name))
+	return iv->t;
+    }
 
   return NULL;
 }
@@ -143,27 +189,83 @@
 /* Prints on stderr the contents of STACK.  */
 
 void
-loop_iv_stack_debug (loop_iv_stack stack)
+debug_loop_iv_stack (loop_iv_stack stack)
 {
   int i;
-  name_tree iv;
+  iv_stack_entry_p entry;
   bool first = true;
 
   fprintf (stderr, "(");
 
-  for (i = 0; VEC_iterate (name_tree, *stack, i, iv); i++)
+  for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry); i++)
     {
       if (first) 
 	first = false;
       else
 	fprintf (stderr, " ");
-      fprintf (stderr, "%s:", iv->name);
-      print_generic_expr (stderr, iv->t, 0);
+
+      if (iv_stack_entry_is_iv (entry))
+	{
+	  name_tree iv = entry->data.iv;
+	  fprintf (stderr, "%s:", iv->name);
+	  print_generic_expr (stderr, iv->t, 0);
+	}
+      else 
+	{
+	  tree constant = entry->data.constant;
+	  print_generic_expr (stderr, constant, 0);
+	  fprintf (stderr, ":");
+	  print_generic_expr (stderr, constant, 0);
+	}
     }
 
   fprintf (stderr, ")\n");
 }
 
+/* Inserts constants derived from the USER_STMT argument list into the
+   STACK. This is needed to map old ivs to constants when loops have
+   been eliminated.  */
+
+static void 
+loop_iv_stack_patch_for_consts (loop_iv_stack stack,
+				struct clast_user_stmt *user_stmt)
+{
+  struct clast_stmt *t;
+  int index = 0;
+  for (t = user_stmt->substitutions; t; t = t->next) {
+    struct clast_term* term = (struct clast_term*) 
+      ((struct clast_assignment *)t)->RHS;
+
+    /* FIXME: What should be done with expr_bin, expr_red?  */
+    if (((struct clast_assignment *)t)->RHS->type != expr_term)
+      continue;
+
+    if (!term->var) 
+      {
+	tree value = gmp_cst_to_tree (term->val);
+	loop_iv_stack_insert_constant (stack, index, value);
+      }
+    index = index + 1;
+  }
+}
+
+/* Removes all constants in the iv STACK.  */
+
+static void
+loop_iv_stack_remove_constants (loop_iv_stack stack)
+{
+  int i;
+  iv_stack_entry* entry;
+  
+  for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry);)
+    {
+      if (iv_stack_entry_is_constant (entry))
+	VEC_ordered_remove (iv_stack_entry_p, *stack, i);
+      else
+	i++;
+    }
+}
+
 /* In SCOP, get the induction variable from NAME.  OLD is the original
    loop that contained the definition of NAME.  */
 
@@ -2745,14 +2847,6 @@
     }
 }
 
-/* Converts a GMP constant value to a tree and returns it.  */
-
-static tree
-gmp_cst_to_tree (Value v)
-{
-  return build_int_cst (integer_type_node, value_get_si (v));
-}
-
 /* Returns the tree variable from the name NAME that was given in
    Cloog representation.  All the parameters are stored in PARAMS, and
    all the loop induction variables are stored in IVSTACK.
@@ -3007,7 +3101,7 @@
 				    &iv_before, outer ? outer
 				    : entry_edge->src->loop_father);
 
-  loop_iv_stack_push (ivstack, iv_before, stmt->iterator);
+  loop_iv_stack_push_iv (ivstack, iv_before, stmt->iterator);
 
   return loop;
 }
@@ -3353,8 +3447,11 @@
       mark_virtual_ops_in_bb (bb);
       next_e = make_edge (bb,
 			  context_loop ? context_loop->latch : EXIT_BLOCK_PTR,
-			  EDGE_FALLTHRU);;
+			  EDGE_FALLTHRU);
+      loop_iv_stack_patch_for_consts (ivstack,
+				      (struct clast_user_stmt *) stmt);
       graphite_rename_ivs (gbb, scop, old_loop_father, ivstack);
+      loop_iv_stack_remove_constants (ivstack);
       return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
     }
 
@@ -3891,7 +3988,8 @@
   basic_block scop_exit = SCOP_EXIT (scop);
   VEC (tree, heap)* phi_args = 
     collect_scop_exit_phi_args (SESE_EXIT (SCOP_REGION (scop)));
-  VEC (name_tree, heap) *ivstack = VEC_alloc (name_tree, heap, 10);
+  VEC (iv_stack_entry_p, heap) *ivstack = 
+    VEC_alloc (iv_stack_entry_p, heap, 10);
   edge construction_edge = SESE_ENTRY (SCOP_REGION (scop));
   basic_block old_scop_exit_idom = get_immediate_dominator (CDI_DOMINATORS,
 							    scop_exit);
@@ -3902,10 +4000,14 @@
       return;
     }
 
+  redirect_edge_succ_nodup (construction_edge, EXIT_BLOCK_PTR);
+
   new_scop_exit_edge = translate_clast (scop, 
 					construction_edge->src->loop_father,
 					stmt, construction_edge, &ivstack);
+
   redirect_edge_succ (new_scop_exit_edge, scop_exit);
+
   if (!old_scop_exit_idom
       || !dominated_by_p (CDI_DOMINATORS, SCOP_ENTRY (scop),
 			  old_scop_exit_idom)
@@ -4711,20 +4813,35 @@
   VEC (scop_p, heap) *new_scops = VEC_alloc (scop_p, heap, 3);
   int i;
   scop_p scop;
+  struct pointer_set_t* entry_exit_ptrs = pointer_set_create ();
 
   for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
     {
       int j;
       loop_p loop;
+
       build_scop_bbs (scop);
       build_scop_loop_nests (scop);
 
       for (j = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), j, loop); j++) 
         if (!loop_in_scop_p (loop_outer (loop), scop))
           {
+	    edge scop_entry_edge;
+	    edge scop_exit_edge;
 	    scop_p n_scop = new_scop (loop_preheader_edge (loop));
+
 	    end_scop (n_scop, single_exit (loop), false);
-	    VEC_safe_push (scop_p, heap, new_scops, n_scop);
+	    scop_entry_edge = SESE_ENTRY (SCOP_REGION (n_scop));
+	    scop_exit_edge = SESE_EXIT (SCOP_REGION (n_scop));
+
+	    if (!pointer_set_contains (entry_exit_ptrs, scop_entry_edge)
+		&& !pointer_set_contains (entry_exit_ptrs, scop_exit_edge))
+	      {
+		pointer_set_insert (entry_exit_ptrs, scop_entry_edge);
+		pointer_set_insert (entry_exit_ptrs, scop_exit_edge);
+
+		VEC_safe_push (scop_p, heap, new_scops, n_scop);
+	      }
 	  }
     }
 
Index: graphite.h
===================================================================
--- graphite.h	(revision 140372)
+++ graphite.h	(working copy)
@@ -340,10 +340,36 @@
 extern void debug_loop_vec (graphite_bb_p gb);
 extern void debug_oldivs (scop_p);
 
-typedef VEC(name_tree, heap) **loop_iv_stack;
-extern void loop_iv_stack_debug (loop_iv_stack);
+/* Describes the type of an iv stack entry.  */
+typedef enum {
+  iv_stack_entry_unknown = 0,
+  iv_stack_entry_iv,
+  iv_stack_entry_const
+} iv_stack_entry_kind;
 
+/* Data contained in an iv stack entry.  */
+typedef union iv_stack_entry_data_union
+{
+  name_tree iv;
+  tree constant;
+} iv_stack_entry_data;
 
+/* Datatype for loop iv stack entry.  */
+typedef struct iv_stack_entry_struct
+{
+  iv_stack_entry_kind kind;
+  iv_stack_entry_data data;
+} iv_stack_entry;
+
+typedef iv_stack_entry* iv_stack_entry_p;
+
+DEF_VEC_P(iv_stack_entry_p);
+DEF_VEC_ALLOC_P(iv_stack_entry_p,heap);
+
+typedef VEC(iv_stack_entry_p, heap) **loop_iv_stack;
+extern void debug_loop_iv_stack (loop_iv_stack);
+
+
 /* Return the number of gimple loops contained in SCOP.  */
 
 static inline int

Re: [graphite] Fix PR37485

[Sebastian Pop]

[-- Attachment #1: Type: text/plain, Size: 382 bytes --]

On Tue, Sep 16, 2008 at 5:41 PM, Harsha Jagasia <harsha.jagasia@amd.com> wrote:
> This patch fixes PR37485 with the following:

The patch looks good.

As there is no maintainer for the graphite passes and the latency for
reviewing the graphite patches is too long, I will commit the attached
patch to trunk tomorrow after testing, unless somebody has a reason to
say no.

Sebastian

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 1221_pr37485.diff --]
[-- Type: text/x-patch; name=1221_pr37485.diff, Size: 12194 bytes --]

2008-09-16  Jan Sjodin  <jan.sjodin@amd.com>
            Harsha Jagasia  <harsha.jagasia@amd.com>

	PR tree-optimization/37485
	* gcc.dg/graphite/block-2.c: New
	* graphite.c (gmp_cst_to_tree): Moved.
	(iv_stack_entry_is_constant): New.
	(iv_stack_entry_is_iv): New.
	(loop_iv_stack_push): Renamed to loop_iv_stack_push_iv.
	(loop_iv_stack_insert_constant): New.
	(loop_iv_stack_pop): Use new datatpype.
	(loop_iv_stack_get_iv): Same.
	(loop_iv_stack_get_iv_from_name): Same.
	(loop_iv_stack_debug): Renamed to debug_loop_iv_stack.
	(loop_iv_stack_patch_for_consts): New.
	(loop_iv_stack_remove_constants): New.
	(graphite_create_new_loop): Use loop_iv_stack_push_iv.
	(translate_clast): Call loop_iv_stack_patch_for_consts and
	loop_iv_stack_remove_constants.
	(gloog): Use new datatype.  Redirect construction edge to end
	block to avoid accidental deletion.
	(limit_scops): Prevent overlapping scops.
	* graphite.h (enum iv_stack_entry_kind): New.  Tag for data in
	iv stack entry.
	(union iv_stack_entry_data): New.  Data in iv stack entry.
	(struct iv_stack_entry): New.  Datatype for iv stack entries.

Index: testsuite/gcc.dg/graphite/block-2.c
===================================================================
--- testsuite/gcc.dg/graphite/block-2.c	(revision 0)
+++ testsuite/gcc.dg/graphite/block-2.c	(revision 0)
@@ -0,0 +1,33 @@
+/* { dg-options "-O2 -floop-block -fdump-tree-graphite-all" } */
+/* PR37485 fixed, but the test case triggers one more bug,
+   which will be reported seperately under bugzilla.  */
+
+typedef unsigned char   UChar;
+typedef int             Int32;
+typedef unsigned int    UInt32;
+
+void fallbackSort ( UInt32* fmap, 
+                    UInt32* eclass, 
+                    Int32   nblock,
+                    Int32   verb )
+{
+   Int32 ftab[257];
+   Int32 ftabCopy[256];
+   Int32 H, i, j, k, l, r, cc, cc1;
+   Int32 nNotDone;
+   Int32 nBhtab;
+   UChar* eclass8 = (UChar*)eclass;
+
+   if (verb >= 4)
+      VPrintf0 ( "        bucket sorting ...\n" );
+   for (i = 0; i < 257;    i++) ftab[i] = 0;
+   for (i = 0; i < nblock; i++) ftab[eclass8[i]]++;
+   for (i = 0; i < 256;    i++) ftabCopy[i] = ftab[i];
+   for (i = 1; i < 257;    i++) ftab[i] += ftab[i-1];
+
+   for (i = 0; i < nblock; i++) {
+      j = eclass8[i] + ftab [i];
+   }
+   AssertH ( j < 256, 1005 );
+}
+/* { dg-final { scan-tree-dump-times "Loop blocked" 1 "graphite" { xfail *-*-* }} } */
Index: graphite.c
===================================================================
--- graphite.c	(revision 140668)
+++ graphite.c	(working copy)
@@ -60,6 +60,14 @@ along with GCC; see the file COPYING3.  
 
 static VEC (scop_p, heap) *current_scops;
 
+/* Converts a GMP constant value to a tree and returns it.  */
+
+static tree
+gmp_cst_to_tree (Value v)
+{
+  return build_int_cst (integer_type_node, value_get_si (v));
+}
+
 /* Debug the list of old induction variables for this SCOP.  */
 
 void
@@ -95,16 +103,51 @@ debug_loop_vec (graphite_bb_p gb)
   fprintf (stderr, "\n");
 }
 
+/* Returns true if stack entry is a constant.  */
+
+static bool
+iv_stack_entry_is_constant (iv_stack_entry *entry)
+{
+  return entry->kind == iv_stack_entry_const;
+}
+
+/* Returns true if stack entry is a constant.  */
+
+static bool
+iv_stack_entry_is_iv (iv_stack_entry *entry)
+{
+  return entry->kind == iv_stack_entry_iv;
+}
+
 /* Push (IV, NAME) on STACK.  */
 
 static void 
-loop_iv_stack_push (loop_iv_stack stack, tree iv, const char *name)
+loop_iv_stack_push_iv (loop_iv_stack stack, tree iv, const char *name)
 {
+  iv_stack_entry *entry = XNEW (iv_stack_entry);
   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);
+
+  entry->kind = iv_stack_entry_iv;
+  entry->data.iv = named_iv;
+
+  VEC_safe_push (iv_stack_entry_p, heap, *stack, entry);
+}
+
+/* Inserts a CONSTANT in STACK at INDEX.  */
+
+static void
+loop_iv_stack_insert_constant (loop_iv_stack stack, int index,
+			       tree constant)
+{
+  iv_stack_entry *entry = XNEW (iv_stack_entry);
+  
+  entry->kind = iv_stack_entry_const;
+  entry->data.constant = constant;
+
+  VEC_safe_insert (iv_stack_entry_p, heap, *stack, index, entry);
 }
 
 /* Pops an element out of STACK.  */
@@ -112,7 +155,7 @@ loop_iv_stack_push (loop_iv_stack stack,
 static void
 loop_iv_stack_pop (loop_iv_stack stack)
 {
-  VEC_pop (name_tree, *stack);
+  VEC_pop (iv_stack_entry_p, *stack);
 }
 
 /* Get the IV at INDEX in STACK.  */
@@ -120,7 +163,7 @@ loop_iv_stack_pop (loop_iv_stack stack)
 static tree
 loop_iv_stack_get_iv (loop_iv_stack stack, int index)
 {
-  name_tree named_iv = VEC_index (name_tree, *stack, index);
+  name_tree named_iv = VEC_index (iv_stack_entry_p, *stack, index)->data.iv;
 
   return named_iv->t;
 }
@@ -131,11 +174,14 @@ static tree
 loop_iv_stack_get_iv_from_name (loop_iv_stack stack, const char* name)
 {
   int i;
-  name_tree iv;
+  iv_stack_entry_p entry;
 
-  for (i = 0; VEC_iterate (name_tree, *stack, i, iv); i++)
-    if (!strcmp (name, iv->name))
-      return iv->t;
+  for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry); i++)
+    {
+      name_tree iv = entry->data.iv;
+      if (!strcmp (name, iv->name))
+	return iv->t;
+    }
 
   return NULL;
 }
@@ -143,27 +189,84 @@ loop_iv_stack_get_iv_from_name (loop_iv_
 /* Prints on stderr the contents of STACK.  */
 
 void
-loop_iv_stack_debug (loop_iv_stack stack)
+debug_loop_iv_stack (loop_iv_stack stack)
 {
   int i;
-  name_tree iv;
+  iv_stack_entry_p entry;
   bool first = true;
 
   fprintf (stderr, "(");
 
-  for (i = 0; VEC_iterate (name_tree, *stack, i, iv); i++)
+  for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry); i++)
     {
       if (first) 
 	first = false;
       else
 	fprintf (stderr, " ");
-      fprintf (stderr, "%s:", iv->name);
-      print_generic_expr (stderr, iv->t, 0);
+
+      if (iv_stack_entry_is_iv (entry))
+	{
+	  name_tree iv = entry->data.iv;
+	  fprintf (stderr, "%s:", iv->name);
+	  print_generic_expr (stderr, iv->t, 0);
+	}
+      else 
+	{
+	  tree constant = entry->data.constant;
+	  print_generic_expr (stderr, constant, 0);
+	  fprintf (stderr, ":");
+	  print_generic_expr (stderr, constant, 0);
+	}
     }
 
   fprintf (stderr, ")\n");
 }
 
+/* Inserts constants derived from the USER_STMT argument list into the
+   STACK.  This is needed to map old ivs to constants when loops have
+   been eliminated.  */
+
+static void 
+loop_iv_stack_patch_for_consts (loop_iv_stack stack,
+				struct clast_user_stmt *user_stmt)
+{
+  struct clast_stmt *t;
+  int index = 0;
+  for (t = user_stmt->substitutions; t; t = t->next) 
+    {
+      struct clast_term *term = (struct clast_term*) 
+	((struct clast_assignment *)t)->RHS;
+
+      /* FIXME: What should be done with expr_bin, expr_red?  */
+      if (((struct clast_assignment *)t)->RHS->type != expr_term)
+	continue;
+
+      if (!term->var) 
+	{
+	  tree value = gmp_cst_to_tree (term->val);
+	  loop_iv_stack_insert_constant (stack, index, value);
+	}
+      index = index + 1;
+    }
+}
+
+/* Removes all constants in the iv STACK.  */
+
+static void
+loop_iv_stack_remove_constants (loop_iv_stack stack)
+{
+  int i;
+  iv_stack_entry* entry;
+  
+  for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry);)
+    {
+      if (iv_stack_entry_is_constant (entry))
+	VEC_ordered_remove (iv_stack_entry_p, *stack, i);
+      else
+	i++;
+    }
+}
+
 /* In SCOP, get the induction variable from NAME.  OLD is the original
    loop that contained the definition of NAME.  */
 
@@ -2745,14 +2848,6 @@ build_scop_data_accesses (scop_p scop)
     }
 }
 
-/* Converts a GMP constant value to a tree and returns it.  */
-
-static tree
-gmp_cst_to_tree (Value v)
-{
-  return build_int_cst (integer_type_node, value_get_si (v));
-}
-
 /* Returns the tree variable from the name NAME that was given in
    Cloog representation.  All the parameters are stored in PARAMS, and
    all the loop induction variables are stored in IVSTACK.
@@ -3007,7 +3102,7 @@ graphite_create_new_loop (scop_p scop, e
 				    &iv_before, outer ? outer
 				    : entry_edge->src->loop_father);
 
-  loop_iv_stack_push (ivstack, iv_before, stmt->iterator);
+  loop_iv_stack_push_iv (ivstack, iv_before, stmt->iterator);
 
   return loop;
 }
@@ -3353,8 +3448,11 @@ translate_clast (scop_p scop, struct loo
       mark_virtual_ops_in_bb (bb);
       next_e = make_edge (bb,
 			  context_loop ? context_loop->latch : EXIT_BLOCK_PTR,
-			  EDGE_FALLTHRU);;
+			  EDGE_FALLTHRU);
+      loop_iv_stack_patch_for_consts (ivstack,
+				      (struct clast_user_stmt *) stmt);
       graphite_rename_ivs (gbb, scop, old_loop_father, ivstack);
+      loop_iv_stack_remove_constants (ivstack);
       return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
     }
 
@@ -3891,7 +3989,8 @@ gloog (scop_p scop, struct clast_stmt *s
   basic_block scop_exit = SCOP_EXIT (scop);
   VEC (tree, heap)* phi_args = 
     collect_scop_exit_phi_args (SESE_EXIT (SCOP_REGION (scop)));
-  VEC (name_tree, heap) *ivstack = VEC_alloc (name_tree, heap, 10);
+  VEC (iv_stack_entry_p, heap) *ivstack = 
+    VEC_alloc (iv_stack_entry_p, heap, 10);
   edge construction_edge = SESE_ENTRY (SCOP_REGION (scop));
   basic_block old_scop_exit_idom = get_immediate_dominator (CDI_DOMINATORS,
 							    scop_exit);
@@ -3902,10 +4001,12 @@ gloog (scop_p scop, struct clast_stmt *s
       return;
     }
 
+  redirect_edge_succ_nodup (construction_edge, EXIT_BLOCK_PTR);
   new_scop_exit_edge = translate_clast (scop, 
 					construction_edge->src->loop_father,
 					stmt, construction_edge, &ivstack);
   redirect_edge_succ (new_scop_exit_edge, scop_exit);
+
   if (!old_scop_exit_idom
       || !dominated_by_p (CDI_DOMINATORS, SCOP_ENTRY (scop),
 			  old_scop_exit_idom)
@@ -4711,20 +4812,35 @@ limit_scops (void)
   VEC (scop_p, heap) *new_scops = VEC_alloc (scop_p, heap, 3);
   int i;
   scop_p scop;
+  struct pointer_set_t *entry_exit_ptrs = pointer_set_create ();
 
   for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
     {
       int j;
       loop_p loop;
+
       build_scop_bbs (scop);
       build_scop_loop_nests (scop);
 
       for (j = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), j, loop); j++) 
         if (!loop_in_scop_p (loop_outer (loop), scop))
           {
+	    edge scop_entry_edge;
+	    edge scop_exit_edge;
 	    scop_p n_scop = new_scop (loop_preheader_edge (loop));
+
 	    end_scop (n_scop, single_exit (loop), false);
-	    VEC_safe_push (scop_p, heap, new_scops, n_scop);
+	    scop_entry_edge = SESE_ENTRY (SCOP_REGION (n_scop));
+	    scop_exit_edge = SESE_EXIT (SCOP_REGION (n_scop));
+
+	    if (!pointer_set_contains (entry_exit_ptrs, scop_entry_edge)
+		&& !pointer_set_contains (entry_exit_ptrs, scop_exit_edge))
+	      {
+		pointer_set_insert (entry_exit_ptrs, scop_entry_edge);
+		pointer_set_insert (entry_exit_ptrs, scop_exit_edge);
+
+		VEC_safe_push (scop_p, heap, new_scops, n_scop);
+	      }
 	  }
     }
 
Index: graphite.h
===================================================================
--- graphite.h	(revision 140668)
+++ graphite.h	(working copy)
@@ -340,8 +340,34 @@ extern void debug_clast_stmt (struct cla
 extern void debug_loop_vec (graphite_bb_p gb);
 extern void debug_oldivs (scop_p);
 
-typedef VEC(name_tree, heap) **loop_iv_stack;
-extern void loop_iv_stack_debug (loop_iv_stack);
+/* Describes the type of an iv stack entry.  */
+typedef enum {
+  iv_stack_entry_unknown = 0,
+  iv_stack_entry_iv,
+  iv_stack_entry_const
+} iv_stack_entry_kind;
+
+/* Data contained in an iv stack entry.  */
+typedef union iv_stack_entry_data_union
+{
+  name_tree iv;
+  tree constant;
+} iv_stack_entry_data;
+
+/* Datatype for loop iv stack entry.  */
+typedef struct iv_stack_entry_struct
+{
+  iv_stack_entry_kind kind;
+  iv_stack_entry_data data;
+} iv_stack_entry;
+
+typedef iv_stack_entry* iv_stack_entry_p;
+
+DEF_VEC_P(iv_stack_entry_p);
+DEF_VEC_ALLOC_P(iv_stack_entry_p,heap);
+
+typedef VEC(iv_stack_entry_p, heap) **loop_iv_stack;
+extern void debug_loop_iv_stack (loop_iv_stack);
 
 
 /* Return the number of gimple loops contained in SCOP.  */

Re: [graphite] Fix PR37485

[Diego Novillo]

On Tue, Sep 16, 2008 at 18:41, Harsha Jagasia <harsha.jagasia@amd.com> wrote:

> Index: testsuite/gcc.dg/graphite/block-2.c
> ===================================================================
> --- testsuite/gcc.dg/graphite/block-2.c (revision 0)
> +++ testsuite/gcc.dg/graphite/block-2.c (revision 0)
> @@ -0,0 +1,33 @@
> +/* { dg-options "-O2 -floop-block -fdump-tree-graphite-all" } */
> +/* PR37485 fixed, but the test case triggers one more bug,
> +   which will be reported seperately under bugzilla.  */

Do you have the new bugzilla PR?  Otherwise, this comment will
make little sense in a few months.

> +/* Converts a GMP constant value to a tree and returns it.  */
> +
> +static tree
> +gmp_cst_to_tree (Value v)

s/a GMP constant value/GMP constant V/

> +/* Returns true if stack entry is a constant.  */
> +
> +static bool
> +iv_stack_entry_is_constant (iv_stack_entry *entry)

ENTRY needs documenting.

> +{
> +  return entry->kind == iv_stack_entry_const;
> +}
> +
> +/* Returns true if stack entry is a constant.  */
> +
> +static bool
> +iv_stack_entry_is_iv (iv_stack_entry *entry)

Likewise.

>  static void
> -loop_iv_stack_push (loop_iv_stack stack, tree iv, const char *name)
> +loop_iv_stack_push_iv (loop_iv_stack stack, tree iv, const char *name)
>  {
> +  iv_stack_entry* entry = XNEW (iv_stack_entry);

s/iv_stack_entry*/iv_stack_entry */

> +static void
> +loop_iv_stack_insert_constant (loop_iv_stack stack, int index,
> +                              tree constant)
> +{
> +  iv_stack_entry* entry = XNEW (iv_stack_entry);

Likewise.

> +static void
> +loop_iv_stack_remove_constants (loop_iv_stack stack)
> +{
> +  int i;
> +  iv_stack_entry* entry;

s/iv_stack_entry*/iv_stack_entry */

> +
> +  for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry);)
> +    {
> +      if (iv_stack_entry_is_constant (entry))
> +       VEC_ordered_remove (iv_stack_entry_p, *stack, i);
> +      else
> +       i++;
> +    }

This is leaking memory.  You should free the object removed by
VEC_ordered_remove.

> @@ -3353,8 +3447,11 @@
>       mark_virtual_ops_in_bb (bb);
>       next_e = make_edge (bb,
>                          context_loop ? context_loop->latch : EXIT_BLOCK_PTR,
> -                         EDGE_FALLTHRU);;
> +                         EDGE_FALLTHRU);
> +      loop_iv_stack_patch_for_consts (ivstack,
> +                                     (struct clast_user_stmt *) stmt);
>       graphite_rename_ivs (gbb, scop, old_loop_father, ivstack);
> +      loop_iv_stack_remove_constants (ivstack);

We are leaking memory through ivstack.  It's being allocated in
gloog() but never released (VEC_ordered_remove in
loop_iv_stack_remove_constants does not free the removed object).
The individual elements from ivstack don't seem to be released
anywhere either.  Perhaps loop_iv_stack_pop should do this?


> @@ -4711,20 +4813,35 @@
>   VEC (scop_p, heap) *new_scops = VEC_alloc (scop_p, heap, 3);
>   int i;
>   scop_p scop;
> +  struct pointer_set_t* entry_exit_ptrs = pointer_set_create ();

s/pointer_set_t* entry_exit_ptrs/pointer_set_t *entry_exit_ptrs/

A call to pointer_set_destroy() is needed to free up the memory
used by this set.

> +typedef iv_stack_entry* iv_stack_entry_p;

s/iv_stack_entry*/iv_stack_entry */

OK with those changes.


Diego.

Re: [graphite] Fix PR37485

[Sebastian Pop]

[-- Attachment #1: Type: text/plain, Size: 1539 bytes --]

Hello,

On Fri, Sep 26, 2008 at 6:02 AM, Diego Novillo <dnovillo@google.com> wrote:
> On Tue, Sep 16, 2008 at 18:41, Harsha Jagasia <harsha.jagasia@amd.com> wrote:
>
>> Index: testsuite/gcc.dg/graphite/block-2.c
>> ===================================================================
>> --- testsuite/gcc.dg/graphite/block-2.c (revision 0)
>> +++ testsuite/gcc.dg/graphite/block-2.c (revision 0)
>> @@ -0,0 +1,33 @@
>> +/* { dg-options "-O2 -floop-block -fdump-tree-graphite-all" } */
>> +/* PR37485 fixed, but the test case triggers one more bug,
>> +   which will be reported seperately under bugzilla.  */
>
> Do you have the new bugzilla PR?  Otherwise, this comment will
> make little sense in a few months.
>

Here is the updated patch for fixing this PR, and also two patches
that fix the compilation of block-2.c.

The first bug is due to the fact that IVOPTs is assuming that the loop
is iterating at least once, so the patch modifies the creation of
empty loops to match the expected form of IVOPTs.

The second bug fix is in IVOPTs.  The ICE happens in VRP where scev
two variables have to be compared, but they have incompatible types.
This is due to the fact that we generate a statement like this:

ivtmp.50_147 = graphiteIV.44_127;

with _147 of pointer type, and _127 of integer type.  The fix makes
IVOPTs to generate the necessary convert when the types are different:

ivtmp.50_147 = (Int32 *) graphiteIV.44_127;

I'm testing all the patches on x86_64-linux.  Okay if they pass?

Thanks,
Sebastian Pop
--
AMD - GNU Tools

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 1230_fix_ivopts.diff --]
[-- Type: text/x-patch; name=1230_fix_ivopts.diff, Size: 673 bytes --]


	* tree-ssa-loop-ivopts.c (rewrite_use_nonlinear_expr): Convert
	operand type when copying the operand to a variable of different type.

Index: tree-ssa-loop-ivopts.c
===================================================================
--- tree-ssa-loop-ivopts.c	(revision 140668)
+++ tree-ssa-loop-ivopts.c	(working copy)
@@ -5157,6 +5157,9 @@ rewrite_use_nonlinear_expr (struct ivopt
 
   if (gimple_code (use->stmt) == GIMPLE_PHI)
     {
+      if (TREE_TYPE (op) != TREE_TYPE (tgt))
+	op = fold_convert (TREE_TYPE (tgt), op);
+
       ass = gimple_build_assign (tgt, op);
       gsi_insert_before (&bsi, ass, GSI_SAME_STMT);
       remove_statement (use->stmt, false);

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #3: 1231_fix_empty_loop.diff --]
[-- Type: text/x-patch; name=1231_fix_empty_loop.diff, Size: 3438 bytes --]


	* cfgloopmanip.c (create_empty_loop_on_edge): Write exit condition with 
	the IV name after increment.

Index: cfgloopmanip.c
===================================================================
--- cfgloopmanip.c	(revision 140668)
+++ cfgloopmanip.c	(working copy)
@@ -597,22 +597,26 @@ create_empty_if_region_on_edge (edge ent
    |           |             ====>   |     -----------------------------
    |           |                     |     | IV_BEFORE = phi (IV_0, IV) |
    |           |                     |     | loop_header                |
-   |           V                     |     | IV_BEFORE <= UPPER_BOUND   |
+   |           |                     |     | IV_AFTER = IV_BEFORE + STRIDE
+   |           V                     |     | IV_AFTER <= UPPER_BOUND   |
    |     -------------               |     -----------------------\-----
    |     |  succ_bb  |               |         |                   \
    |     -------------               |         |                    \ exit_e
    |                                 |         V                     V---------
    |                                 |      --------------           | succ_bb |
    |                                 |      | loop_latch  |          ----------
-   |                                 |      |IV = IV_BEFORE + STRIDE
    |                                 |      --------------
    |                                  \       /
    |                                   \ ___ /
 
    Creates an empty loop as shown above, the IV_BEFORE is the SSA_NAME
-   that is used before the increment of IV. IV_BEFORE should be used for 
+   that is used before the increment of IV.  IV_BEFORE should be used for 
    adding code to the body that uses the IV.  OUTER is the outer loop in
-   which the new loop should be inserted.  */
+   which the new loop should be inserted.  
+
+   The IVOPTS pass expects the exit condition to be an expression of
+   IV_AFTER.
+*/
 
 struct loop *
 create_empty_loop_on_edge (edge entry_edge, 
@@ -627,13 +631,13 @@ create_empty_loop_on_edge (edge entry_ed
   int freq;
   gcov_type cnt;
   gimple_stmt_iterator gsi;
-  bool insert_after;
   gimple_seq stmts;
   gimple cond_expr;
   tree exit_test;
   edge exit_e;
   int prob;
   tree upper_bound_gimplified;
+  tree iv_after;
   
   gcc_assert (entry_edge && initial_value && stride && upper_bound && iv);
 
@@ -675,16 +679,14 @@ create_empty_loop_on_edge (edge entry_ed
       gsi_commit_edge_inserts ();
     }
 
-  standard_iv_increment_position (loop, &gsi, &insert_after);
-  create_iv (initial_value, stride, iv, loop, &gsi, insert_after,
-	     iv_before, NULL);
-
   /* Modify edge flags.  */
   exit_e = single_exit (loop);
   exit_e->flags = EDGE_LOOP_EXIT | EDGE_FALSE_VALUE;
   single_pred_edge (loop_latch)->flags = EDGE_TRUE_VALUE;
 
   gsi = gsi_last_bb (exit_e->src);
+  create_iv (initial_value, stride, iv, loop, &gsi, true,
+	     iv_before, &iv_after);
 
   upper_bound_gimplified = 
     force_gimple_operand_gsi (&gsi, upper_bound, true, NULL,
@@ -692,7 +694,7 @@ create_empty_loop_on_edge (edge entry_ed
   gsi = gsi_last_bb (exit_e->src);
   
   cond_expr = gimple_build_cond 
-    (LE_EXPR, *iv_before, upper_bound_gimplified, NULL_TREE, NULL_TREE);
+    (LE_EXPR, iv_after, upper_bound_gimplified, NULL_TREE, NULL_TREE);
 
   exit_test = gimple_cond_lhs (cond_expr);
   exit_test = force_gimple_operand_gsi (&gsi, exit_test, true, NULL,

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #4: 1232_pr37485.diff --]
[-- Type: text/x-patch; name=1232_pr37485.diff, Size: 15329 bytes --]

Index: cfgloopmanip.c
===================================================================
--- cfgloopmanip.c	(revision 140668)
+++ cfgloopmanip.c	(working copy)
@@ -597,22 +597,26 @@ create_empty_if_region_on_edge (edge ent
    |           |             ====>   |     -----------------------------
    |           |                     |     | IV_BEFORE = phi (IV_0, IV) |
    |           |                     |     | loop_header                |
-   |           V                     |     | IV_BEFORE <= UPPER_BOUND   |
+   |           |                     |     | IV_AFTER = IV_BEFORE + STRIDE
+   |           V                     |     | IV_AFTER <= UPPER_BOUND   |
    |     -------------               |     -----------------------\-----
    |     |  succ_bb  |               |         |                   \
    |     -------------               |         |                    \ exit_e
    |                                 |         V                     V---------
    |                                 |      --------------           | succ_bb |
    |                                 |      | loop_latch  |          ----------
-   |                                 |      |IV = IV_BEFORE + STRIDE
    |                                 |      --------------
    |                                  \       /
    |                                   \ ___ /
 
    Creates an empty loop as shown above, the IV_BEFORE is the SSA_NAME
-   that is used before the increment of IV. IV_BEFORE should be used for 
+   that is used before the increment of IV.  IV_BEFORE should be used for 
    adding code to the body that uses the IV.  OUTER is the outer loop in
-   which the new loop should be inserted.  */
+   which the new loop should be inserted.  
+
+   The IVOPTS pass expects the exit condition to be an expression of
+   IV_AFTER.
+*/
 
 struct loop *
 create_empty_loop_on_edge (edge entry_edge, 
@@ -627,13 +631,13 @@ create_empty_loop_on_edge (edge entry_ed
   int freq;
   gcov_type cnt;
   gimple_stmt_iterator gsi;
-  bool insert_after;
   gimple_seq stmts;
   gimple cond_expr;
   tree exit_test;
   edge exit_e;
   int prob;
   tree upper_bound_gimplified;
+  tree iv_after;
   
   gcc_assert (entry_edge && initial_value && stride && upper_bound && iv);
 
@@ -675,16 +679,14 @@ create_empty_loop_on_edge (edge entry_ed
       gsi_commit_edge_inserts ();
     }
 
-  standard_iv_increment_position (loop, &gsi, &insert_after);
-  create_iv (initial_value, stride, iv, loop, &gsi, insert_after,
-	     iv_before, NULL);
-
   /* Modify edge flags.  */
   exit_e = single_exit (loop);
   exit_e->flags = EDGE_LOOP_EXIT | EDGE_FALSE_VALUE;
   single_pred_edge (loop_latch)->flags = EDGE_TRUE_VALUE;
 
   gsi = gsi_last_bb (exit_e->src);
+  create_iv (initial_value, stride, iv, loop, &gsi, true,
+	     iv_before, &iv_after);
 
   upper_bound_gimplified = 
     force_gimple_operand_gsi (&gsi, upper_bound, true, NULL,
@@ -692,7 +694,7 @@ create_empty_loop_on_edge (edge entry_ed
   gsi = gsi_last_bb (exit_e->src);
   
   cond_expr = gimple_build_cond 
-    (LE_EXPR, *iv_before, upper_bound_gimplified, NULL_TREE, NULL_TREE);
+    (LE_EXPR, iv_after, upper_bound_gimplified, NULL_TREE, NULL_TREE);
 
   exit_test = gimple_cond_lhs (cond_expr);
   exit_test = force_gimple_operand_gsi (&gsi, exit_test, true, NULL,
Index: testsuite/gcc.dg/graphite/block-2.c
===================================================================
--- testsuite/gcc.dg/graphite/block-2.c	(revision 0)
+++ testsuite/gcc.dg/graphite/block-2.c	(revision 0)
@@ -0,0 +1,31 @@
+/* { dg-options "-O2 -floop-block -fdump-tree-graphite-all" } */
+
+typedef unsigned char   UChar;
+typedef int             Int32;
+typedef unsigned int    UInt32;
+
+void fallbackSort ( UInt32* fmap, 
+                    UInt32* eclass, 
+                    Int32   nblock,
+                    Int32   verb )
+{
+   Int32 ftab[257];
+   Int32 ftabCopy[256];
+   Int32 H, i, j, k, l, r, cc, cc1;
+   Int32 nNotDone;
+   Int32 nBhtab;
+   UChar* eclass8 = (UChar*)eclass;
+
+   if (verb >= 4)
+      VPrintf0 ( "        bucket sorting ...\n" );
+   for (i = 0; i < 257;    i++) ftab[i] = 0;
+   for (i = 0; i < nblock; i++) ftab[eclass8[i]]++;
+   for (i = 0; i < 256;    i++) ftabCopy[i] = ftab[i];
+   for (i = 1; i < 257;    i++) ftab[i] += ftab[i-1];
+
+   for (i = 0; i < nblock; i++) {
+      j = eclass8[i] + ftab [i];
+   }
+   AssertH ( j < 256, 1005 );
+}
+/* { dg-final { scan-tree-dump-times "Loop blocked" 1 "graphite" { xfail *-*-* }} } */
Index: tree-ssa-loop-ivopts.c
===================================================================
--- tree-ssa-loop-ivopts.c	(revision 140668)
+++ tree-ssa-loop-ivopts.c	(working copy)
@@ -5157,6 +5157,9 @@ rewrite_use_nonlinear_expr (struct ivopt
 
   if (gimple_code (use->stmt) == GIMPLE_PHI)
     {
+      if (TREE_TYPE (op) != TREE_TYPE (tgt))
+	op = fold_convert (TREE_TYPE (tgt), op);
+
       ass = gimple_build_assign (tgt, op);
       gsi_insert_before (&bsi, ass, GSI_SAME_STMT);
       remove_statement (use->stmt, false);
Index: graphite.c
===================================================================
--- graphite.c	(revision 140668)
+++ graphite.c	(working copy)
@@ -60,6 +60,14 @@ along with GCC; see the file COPYING3.  
 
 static VEC (scop_p, heap) *current_scops;
 
+/* Converts a GMP constant V to a tree and returns it.  */
+
+static tree
+gmp_cst_to_tree (Value v)
+{
+  return build_int_cst (integer_type_node, value_get_si (v));
+}
+
 /* Debug the list of old induction variables for this SCOP.  */
 
 void
@@ -95,24 +103,60 @@ debug_loop_vec (graphite_bb_p gb)
   fprintf (stderr, "\n");
 }
 
+/* Returns true if stack ENTRY is a constant.  */
+
+static bool
+iv_stack_entry_is_constant (iv_stack_entry *entry)
+{
+  return entry->kind == iv_stack_entry_const;
+}
+
+/* Returns true if stack ENTRY is an induction variable.  */
+
+static bool
+iv_stack_entry_is_iv (iv_stack_entry *entry)
+{
+  return entry->kind == iv_stack_entry_iv;
+}
+
 /* Push (IV, NAME) on STACK.  */
 
 static void 
-loop_iv_stack_push (loop_iv_stack stack, tree iv, const char *name)
+loop_iv_stack_push_iv (loop_iv_stack stack, tree iv, const char *name)
 {
+  iv_stack_entry *entry = XNEW (iv_stack_entry);
   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);
+
+  entry->kind = iv_stack_entry_iv;
+  entry->data.iv = named_iv;
+
+  VEC_safe_push (iv_stack_entry_p, heap, *stack, entry);
+}
+
+/* Inserts a CONSTANT in STACK at INDEX.  */
+
+static void
+loop_iv_stack_insert_constant (loop_iv_stack stack, int index,
+			       tree constant)
+{
+  iv_stack_entry *entry = XNEW (iv_stack_entry);
+  
+  entry->kind = iv_stack_entry_const;
+  entry->data.constant = constant;
+
+  VEC_safe_insert (iv_stack_entry_p, heap, *stack, index, entry);
 }
 
-/* Pops an element out of STACK.  */
+/* Pops and frees an element out of STACK.  */
 
 static void
 loop_iv_stack_pop (loop_iv_stack stack)
 {
-  VEC_pop (name_tree, *stack);
+  iv_stack_entry_p e = VEC_pop (iv_stack_entry_p, *stack);
+  free (e);
 }
 
 /* Get the IV at INDEX in STACK.  */
@@ -120,7 +164,7 @@ loop_iv_stack_pop (loop_iv_stack stack)
 static tree
 loop_iv_stack_get_iv (loop_iv_stack stack, int index)
 {
-  name_tree named_iv = VEC_index (name_tree, *stack, index);
+  name_tree named_iv = VEC_index (iv_stack_entry_p, *stack, index)->data.iv;
 
   return named_iv->t;
 }
@@ -131,11 +175,14 @@ static tree
 loop_iv_stack_get_iv_from_name (loop_iv_stack stack, const char* name)
 {
   int i;
-  name_tree iv;
+  iv_stack_entry_p entry;
 
-  for (i = 0; VEC_iterate (name_tree, *stack, i, iv); i++)
-    if (!strcmp (name, iv->name))
-      return iv->t;
+  for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry); i++)
+    {
+      name_tree iv = entry->data.iv;
+      if (!strcmp (name, iv->name))
+	return iv->t;
+    }
 
   return NULL;
 }
@@ -143,27 +190,101 @@ loop_iv_stack_get_iv_from_name (loop_iv_
 /* Prints on stderr the contents of STACK.  */
 
 void
-loop_iv_stack_debug (loop_iv_stack stack)
+debug_loop_iv_stack (loop_iv_stack stack)
 {
   int i;
-  name_tree iv;
+  iv_stack_entry_p entry;
   bool first = true;
 
   fprintf (stderr, "(");
 
-  for (i = 0; VEC_iterate (name_tree, *stack, i, iv); i++)
+  for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry); i++)
     {
       if (first) 
 	first = false;
       else
 	fprintf (stderr, " ");
-      fprintf (stderr, "%s:", iv->name);
-      print_generic_expr (stderr, iv->t, 0);
+
+      if (iv_stack_entry_is_iv (entry))
+	{
+	  name_tree iv = entry->data.iv;
+	  fprintf (stderr, "%s:", iv->name);
+	  print_generic_expr (stderr, iv->t, 0);
+	}
+      else 
+	{
+	  tree constant = entry->data.constant;
+	  print_generic_expr (stderr, constant, 0);
+	  fprintf (stderr, ":");
+	  print_generic_expr (stderr, constant, 0);
+	}
     }
 
   fprintf (stderr, ")\n");
 }
 
+/* Frees STACK.  */
+
+static void
+free_loop_iv_stack (loop_iv_stack stack)
+{
+  int i;
+  iv_stack_entry_p entry;
+
+  for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry); i++)
+    free (entry);
+
+  VEC_free (iv_stack_entry_p, heap, *stack);
+}
+
+/* Inserts constants derived from the USER_STMT argument list into the
+   STACK.  This is needed to map old ivs to constants when loops have
+   been eliminated.  */
+
+static void 
+loop_iv_stack_patch_for_consts (loop_iv_stack stack,
+				struct clast_user_stmt *user_stmt)
+{
+  struct clast_stmt *t;
+  int index = 0;
+  for (t = user_stmt->substitutions; t; t = t->next) 
+    {
+      struct clast_term *term = (struct clast_term*) 
+	((struct clast_assignment *)t)->RHS;
+
+      /* FIXME: What should be done with expr_bin, expr_red?  */
+      if (((struct clast_assignment *)t)->RHS->type != expr_term)
+	continue;
+
+      if (!term->var) 
+	{
+	  tree value = gmp_cst_to_tree (term->val);
+	  loop_iv_stack_insert_constant (stack, index, value);
+	}
+      index = index + 1;
+    }
+}
+
+/* Removes all constants in the iv STACK.  */
+
+static void
+loop_iv_stack_remove_constants (loop_iv_stack stack)
+{
+  int i;
+  iv_stack_entry *entry;
+  
+  for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry);)
+    {
+      if (iv_stack_entry_is_constant (entry))
+	{
+	  free (VEC_index (iv_stack_entry_p, *stack, i));
+	  VEC_ordered_remove (iv_stack_entry_p, *stack, i);
+	}
+      else
+	i++;
+    }
+}
+
 /* In SCOP, get the induction variable from NAME.  OLD is the original
    loop that contained the definition of NAME.  */
 
@@ -2745,14 +2866,6 @@ build_scop_data_accesses (scop_p scop)
     }
 }
 
-/* Converts a GMP constant value to a tree and returns it.  */
-
-static tree
-gmp_cst_to_tree (Value v)
-{
-  return build_int_cst (integer_type_node, value_get_si (v));
-}
-
 /* Returns the tree variable from the name NAME that was given in
    Cloog representation.  All the parameters are stored in PARAMS, and
    all the loop induction variables are stored in IVSTACK.
@@ -3007,7 +3120,7 @@ graphite_create_new_loop (scop_p scop, e
 				    &iv_before, outer ? outer
 				    : entry_edge->src->loop_father);
 
-  loop_iv_stack_push (ivstack, iv_before, stmt->iterator);
+  loop_iv_stack_push_iv (ivstack, iv_before, stmt->iterator);
 
   return loop;
 }
@@ -3353,8 +3466,11 @@ translate_clast (scop_p scop, struct loo
       mark_virtual_ops_in_bb (bb);
       next_e = make_edge (bb,
 			  context_loop ? context_loop->latch : EXIT_BLOCK_PTR,
-			  EDGE_FALLTHRU);;
+			  EDGE_FALLTHRU);
+      loop_iv_stack_patch_for_consts (ivstack,
+				      (struct clast_user_stmt *) stmt);
       graphite_rename_ivs (gbb, scop, old_loop_father, ivstack);
+      loop_iv_stack_remove_constants (ivstack);
       return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
     }
 
@@ -3891,7 +4007,8 @@ gloog (scop_p scop, struct clast_stmt *s
   basic_block scop_exit = SCOP_EXIT (scop);
   VEC (tree, heap)* phi_args = 
     collect_scop_exit_phi_args (SESE_EXIT (SCOP_REGION (scop)));
-  VEC (name_tree, heap) *ivstack = VEC_alloc (name_tree, heap, 10);
+  VEC (iv_stack_entry_p, heap) *ivstack = 
+    VEC_alloc (iv_stack_entry_p, heap, 10);
   edge construction_edge = SESE_ENTRY (SCOP_REGION (scop));
   basic_block old_scop_exit_idom = get_immediate_dominator (CDI_DOMINATORS,
 							    scop_exit);
@@ -3902,10 +4019,13 @@ gloog (scop_p scop, struct clast_stmt *s
       return;
     }
 
+  redirect_edge_succ_nodup (construction_edge, EXIT_BLOCK_PTR);
   new_scop_exit_edge = translate_clast (scop, 
 					construction_edge->src->loop_father,
 					stmt, construction_edge, &ivstack);
+  free_loop_iv_stack (&ivstack);
   redirect_edge_succ (new_scop_exit_edge, scop_exit);
+
   if (!old_scop_exit_idom
       || !dominated_by_p (CDI_DOMINATORS, SCOP_ENTRY (scop),
 			  old_scop_exit_idom)
@@ -4711,23 +4831,39 @@ limit_scops (void)
   VEC (scop_p, heap) *new_scops = VEC_alloc (scop_p, heap, 3);
   int i;
   scop_p scop;
+  struct pointer_set_t *entry_exit_ptrs = pointer_set_create ();
 
   for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
     {
       int j;
       loop_p loop;
+
       build_scop_bbs (scop);
       build_scop_loop_nests (scop);
 
       for (j = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), j, loop); j++) 
         if (!loop_in_scop_p (loop_outer (loop), scop))
           {
+	    edge scop_entry_edge;
+	    edge scop_exit_edge;
 	    scop_p n_scop = new_scop (loop_preheader_edge (loop));
+
 	    end_scop (n_scop, single_exit (loop), false);
-	    VEC_safe_push (scop_p, heap, new_scops, n_scop);
+	    scop_entry_edge = SESE_ENTRY (SCOP_REGION (n_scop));
+	    scop_exit_edge = SESE_EXIT (SCOP_REGION (n_scop));
+
+	    if (!pointer_set_contains (entry_exit_ptrs, scop_entry_edge)
+		&& !pointer_set_contains (entry_exit_ptrs, scop_exit_edge))
+	      {
+		pointer_set_insert (entry_exit_ptrs, scop_entry_edge);
+		pointer_set_insert (entry_exit_ptrs, scop_exit_edge);
+
+		VEC_safe_push (scop_p, heap, new_scops, n_scop);
+	      }
 	  }
     }
 
+  pointer_set_destroy (entry_exit_ptrs);
   free_scops (current_scops);
   current_scops = new_scops;
 }
Index: graphite.h
===================================================================
--- graphite.h	(revision 140668)
+++ graphite.h	(working copy)
@@ -340,8 +340,34 @@ extern void debug_clast_stmt (struct cla
 extern void debug_loop_vec (graphite_bb_p gb);
 extern void debug_oldivs (scop_p);
 
-typedef VEC(name_tree, heap) **loop_iv_stack;
-extern void loop_iv_stack_debug (loop_iv_stack);
+/* Describes the type of an iv stack entry.  */
+typedef enum {
+  iv_stack_entry_unknown = 0,
+  iv_stack_entry_iv,
+  iv_stack_entry_const
+} iv_stack_entry_kind;
+
+/* Data contained in an iv stack entry.  */
+typedef union iv_stack_entry_data_union
+{
+  name_tree iv;
+  tree constant;
+} iv_stack_entry_data;
+
+/* Datatype for loop iv stack entry.  */
+typedef struct iv_stack_entry_struct
+{
+  iv_stack_entry_kind kind;
+  iv_stack_entry_data data;
+} iv_stack_entry;
+
+typedef iv_stack_entry* iv_stack_entry_p;
+
+DEF_VEC_P(iv_stack_entry_p);
+DEF_VEC_ALLOC_P(iv_stack_entry_p,heap);
+
+typedef VEC(iv_stack_entry_p, heap) **loop_iv_stack;
+extern void debug_loop_iv_stack (loop_iv_stack);
 
 
 /* Return the number of gimple loops contained in SCOP.  */

Re: [graphite] Fix PR37485

[Sebastian Pop]

[-- Attachment #1: Type: text/plain, Size: 1802 bytes --]

Ping patches.

FYI, I've merged the graphite branch, and I've committed the
attached fixes to the graphite branch.

Sebastian

On Tue, Sep 30, 2008 at 7:15 PM, Sebastian Pop <sebpop@gmail.com> wrote:
> Hello,
>
> On Fri, Sep 26, 2008 at 6:02 AM, Diego Novillo <dnovillo@google.com> wrote:
>> On Tue, Sep 16, 2008 at 18:41, Harsha Jagasia <harsha.jagasia@amd.com> wrote:
>>
>>> Index: testsuite/gcc.dg/graphite/block-2.c
>>> ===================================================================
>>> --- testsuite/gcc.dg/graphite/block-2.c (revision 0)
>>> +++ testsuite/gcc.dg/graphite/block-2.c (revision 0)
>>> @@ -0,0 +1,33 @@
>>> +/* { dg-options "-O2 -floop-block -fdump-tree-graphite-all" } */
>>> +/* PR37485 fixed, but the test case triggers one more bug,
>>> +   which will be reported seperately under bugzilla.  */
>>
>> Do you have the new bugzilla PR?  Otherwise, this comment will
>> make little sense in a few months.
>>
>
> Here is the updated patch for fixing this PR, and also two patches
> that fix the compilation of block-2.c.
>
> The first bug is due to the fact that IVOPTs is assuming that the loop
> is iterating at least once, so the patch modifies the creation of
> empty loops to match the expected form of IVOPTs.
>
> The second bug fix is in IVOPTs.  The ICE happens in VRP where scev
> two variables have to be compared, but they have incompatible types.
> This is due to the fact that we generate a statement like this:
>
> ivtmp.50_147 = graphiteIV.44_127;
>
> with _147 of pointer type, and _127 of integer type.  The fix makes
> IVOPTs to generate the necessary convert when the types are different:
>
> ivtmp.50_147 = (Int32 *) graphiteIV.44_127;
>
> I'm testing all the patches on x86_64-linux.  Okay if they pass?
>
> Thanks,
> Sebastian Pop
> --
> AMD - GNU Tools
>

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 1230_fix_ivopts.diff --]
[-- Type: text/x-patch; name=1230_fix_ivopts.diff, Size: 673 bytes --]


	* tree-ssa-loop-ivopts.c (rewrite_use_nonlinear_expr): Convert
	operand type when copying the operand to a variable of different type.

Index: tree-ssa-loop-ivopts.c
===================================================================
--- tree-ssa-loop-ivopts.c	(revision 140668)
+++ tree-ssa-loop-ivopts.c	(working copy)
@@ -5157,6 +5157,9 @@ rewrite_use_nonlinear_expr (struct ivopt
 
   if (gimple_code (use->stmt) == GIMPLE_PHI)
     {
+      if (TREE_TYPE (op) != TREE_TYPE (tgt))
+	op = fold_convert (TREE_TYPE (tgt), op);
+
       ass = gimple_build_assign (tgt, op);
       gsi_insert_before (&bsi, ass, GSI_SAME_STMT);
       remove_statement (use->stmt, false);

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #3: 1231_fix_empty_loop.diff --]
[-- Type: text/x-patch; name=1231_fix_empty_loop.diff, Size: 3438 bytes --]


	* cfgloopmanip.c (create_empty_loop_on_edge): Write exit condition with 
	the IV name after increment.

Index: cfgloopmanip.c
===================================================================
--- cfgloopmanip.c	(revision 140668)
+++ cfgloopmanip.c	(working copy)
@@ -597,22 +597,26 @@ create_empty_if_region_on_edge (edge ent
    |           |             ====>   |     -----------------------------
    |           |                     |     | IV_BEFORE = phi (IV_0, IV) |
    |           |                     |     | loop_header                |
-   |           V                     |     | IV_BEFORE <= UPPER_BOUND   |
+   |           |                     |     | IV_AFTER = IV_BEFORE + STRIDE
+   |           V                     |     | IV_AFTER <= UPPER_BOUND   |
    |     -------------               |     -----------------------\-----
    |     |  succ_bb  |               |         |                   \
    |     -------------               |         |                    \ exit_e
    |                                 |         V                     V---------
    |                                 |      --------------           | succ_bb |
    |                                 |      | loop_latch  |          ----------
-   |                                 |      |IV = IV_BEFORE + STRIDE
    |                                 |      --------------
    |                                  \       /
    |                                   \ ___ /
 
    Creates an empty loop as shown above, the IV_BEFORE is the SSA_NAME
-   that is used before the increment of IV. IV_BEFORE should be used for 
+   that is used before the increment of IV.  IV_BEFORE should be used for 
    adding code to the body that uses the IV.  OUTER is the outer loop in
-   which the new loop should be inserted.  */
+   which the new loop should be inserted.  
+
+   The IVOPTS pass expects the exit condition to be an expression of
+   IV_AFTER.
+*/
 
 struct loop *
 create_empty_loop_on_edge (edge entry_edge, 
@@ -627,13 +631,13 @@ create_empty_loop_on_edge (edge entry_ed
   int freq;
   gcov_type cnt;
   gimple_stmt_iterator gsi;
-  bool insert_after;
   gimple_seq stmts;
   gimple cond_expr;
   tree exit_test;
   edge exit_e;
   int prob;
   tree upper_bound_gimplified;
+  tree iv_after;
   
   gcc_assert (entry_edge && initial_value && stride && upper_bound && iv);
 
@@ -675,16 +679,14 @@ create_empty_loop_on_edge (edge entry_ed
       gsi_commit_edge_inserts ();
     }
 
-  standard_iv_increment_position (loop, &gsi, &insert_after);
-  create_iv (initial_value, stride, iv, loop, &gsi, insert_after,
-	     iv_before, NULL);
-
   /* Modify edge flags.  */
   exit_e = single_exit (loop);
   exit_e->flags = EDGE_LOOP_EXIT | EDGE_FALSE_VALUE;
   single_pred_edge (loop_latch)->flags = EDGE_TRUE_VALUE;
 
   gsi = gsi_last_bb (exit_e->src);
+  create_iv (initial_value, stride, iv, loop, &gsi, true,
+	     iv_before, &iv_after);
 
   upper_bound_gimplified = 
     force_gimple_operand_gsi (&gsi, upper_bound, true, NULL,
@@ -692,7 +694,7 @@ create_empty_loop_on_edge (edge entry_ed
   gsi = gsi_last_bb (exit_e->src);
   
   cond_expr = gimple_build_cond 
-    (LE_EXPR, *iv_before, upper_bound_gimplified, NULL_TREE, NULL_TREE);
+    (LE_EXPR, iv_after, upper_bound_gimplified, NULL_TREE, NULL_TREE);
 
   exit_test = gimple_cond_lhs (cond_expr);
   exit_test = force_gimple_operand_gsi (&gsi, exit_test, true, NULL,

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #4: 1232_pr37485.diff --]
[-- Type: text/x-patch; name=1232_pr37485.diff, Size: 15329 bytes --]

Index: cfgloopmanip.c
===================================================================
--- cfgloopmanip.c	(revision 140668)
+++ cfgloopmanip.c	(working copy)
@@ -597,22 +597,26 @@ create_empty_if_region_on_edge (edge ent
    |           |             ====>   |     -----------------------------
    |           |                     |     | IV_BEFORE = phi (IV_0, IV) |
    |           |                     |     | loop_header                |
-   |           V                     |     | IV_BEFORE <= UPPER_BOUND   |
+   |           |                     |     | IV_AFTER = IV_BEFORE + STRIDE
+   |           V                     |     | IV_AFTER <= UPPER_BOUND   |
    |     -------------               |     -----------------------\-----
    |     |  succ_bb  |               |         |                   \
    |     -------------               |         |                    \ exit_e
    |                                 |         V                     V---------
    |                                 |      --------------           | succ_bb |
    |                                 |      | loop_latch  |          ----------
-   |                                 |      |IV = IV_BEFORE + STRIDE
    |                                 |      --------------
    |                                  \       /
    |                                   \ ___ /
 
    Creates an empty loop as shown above, the IV_BEFORE is the SSA_NAME
-   that is used before the increment of IV. IV_BEFORE should be used for 
+   that is used before the increment of IV.  IV_BEFORE should be used for 
    adding code to the body that uses the IV.  OUTER is the outer loop in
-   which the new loop should be inserted.  */
+   which the new loop should be inserted.  
+
+   The IVOPTS pass expects the exit condition to be an expression of
+   IV_AFTER.
+*/
 
 struct loop *
 create_empty_loop_on_edge (edge entry_edge, 
@@ -627,13 +631,13 @@ create_empty_loop_on_edge (edge entry_ed
   int freq;
   gcov_type cnt;
   gimple_stmt_iterator gsi;
-  bool insert_after;
   gimple_seq stmts;
   gimple cond_expr;
   tree exit_test;
   edge exit_e;
   int prob;
   tree upper_bound_gimplified;
+  tree iv_after;
   
   gcc_assert (entry_edge && initial_value && stride && upper_bound && iv);
 
@@ -675,16 +679,14 @@ create_empty_loop_on_edge (edge entry_ed
       gsi_commit_edge_inserts ();
     }
 
-  standard_iv_increment_position (loop, &gsi, &insert_after);
-  create_iv (initial_value, stride, iv, loop, &gsi, insert_after,
-	     iv_before, NULL);
-
   /* Modify edge flags.  */
   exit_e = single_exit (loop);
   exit_e->flags = EDGE_LOOP_EXIT | EDGE_FALSE_VALUE;
   single_pred_edge (loop_latch)->flags = EDGE_TRUE_VALUE;
 
   gsi = gsi_last_bb (exit_e->src);
+  create_iv (initial_value, stride, iv, loop, &gsi, true,
+	     iv_before, &iv_after);
 
   upper_bound_gimplified = 
     force_gimple_operand_gsi (&gsi, upper_bound, true, NULL,
@@ -692,7 +694,7 @@ create_empty_loop_on_edge (edge entry_ed
   gsi = gsi_last_bb (exit_e->src);
   
   cond_expr = gimple_build_cond 
-    (LE_EXPR, *iv_before, upper_bound_gimplified, NULL_TREE, NULL_TREE);
+    (LE_EXPR, iv_after, upper_bound_gimplified, NULL_TREE, NULL_TREE);
 
   exit_test = gimple_cond_lhs (cond_expr);
   exit_test = force_gimple_operand_gsi (&gsi, exit_test, true, NULL,
Index: testsuite/gcc.dg/graphite/block-2.c
===================================================================
--- testsuite/gcc.dg/graphite/block-2.c	(revision 0)
+++ testsuite/gcc.dg/graphite/block-2.c	(revision 0)
@@ -0,0 +1,31 @@
+/* { dg-options "-O2 -floop-block -fdump-tree-graphite-all" } */
+
+typedef unsigned char   UChar;
+typedef int             Int32;
+typedef unsigned int    UInt32;
+
+void fallbackSort ( UInt32* fmap, 
+                    UInt32* eclass, 
+                    Int32   nblock,
+                    Int32   verb )
+{
+   Int32 ftab[257];
+   Int32 ftabCopy[256];
+   Int32 H, i, j, k, l, r, cc, cc1;
+   Int32 nNotDone;
+   Int32 nBhtab;
+   UChar* eclass8 = (UChar*)eclass;
+
+   if (verb >= 4)
+      VPrintf0 ( "        bucket sorting ...\n" );
+   for (i = 0; i < 257;    i++) ftab[i] = 0;
+   for (i = 0; i < nblock; i++) ftab[eclass8[i]]++;
+   for (i = 0; i < 256;    i++) ftabCopy[i] = ftab[i];
+   for (i = 1; i < 257;    i++) ftab[i] += ftab[i-1];
+
+   for (i = 0; i < nblock; i++) {
+      j = eclass8[i] + ftab [i];
+   }
+   AssertH ( j < 256, 1005 );
+}
+/* { dg-final { scan-tree-dump-times "Loop blocked" 1 "graphite" { xfail *-*-* }} } */
Index: tree-ssa-loop-ivopts.c
===================================================================
--- tree-ssa-loop-ivopts.c	(revision 140668)
+++ tree-ssa-loop-ivopts.c	(working copy)
@@ -5157,6 +5157,9 @@ rewrite_use_nonlinear_expr (struct ivopt
 
   if (gimple_code (use->stmt) == GIMPLE_PHI)
     {
+      if (TREE_TYPE (op) != TREE_TYPE (tgt))
+	op = fold_convert (TREE_TYPE (tgt), op);
+
       ass = gimple_build_assign (tgt, op);
       gsi_insert_before (&bsi, ass, GSI_SAME_STMT);
       remove_statement (use->stmt, false);
Index: graphite.c
===================================================================
--- graphite.c	(revision 140668)
+++ graphite.c	(working copy)
@@ -60,6 +60,14 @@ along with GCC; see the file COPYING3.  
 
 static VEC (scop_p, heap) *current_scops;
 
+/* Converts a GMP constant V to a tree and returns it.  */
+
+static tree
+gmp_cst_to_tree (Value v)
+{
+  return build_int_cst (integer_type_node, value_get_si (v));
+}
+
 /* Debug the list of old induction variables for this SCOP.  */
 
 void
@@ -95,24 +103,60 @@ debug_loop_vec (graphite_bb_p gb)
   fprintf (stderr, "\n");
 }
 
+/* Returns true if stack ENTRY is a constant.  */
+
+static bool
+iv_stack_entry_is_constant (iv_stack_entry *entry)
+{
+  return entry->kind == iv_stack_entry_const;
+}
+
+/* Returns true if stack ENTRY is an induction variable.  */
+
+static bool
+iv_stack_entry_is_iv (iv_stack_entry *entry)
+{
+  return entry->kind == iv_stack_entry_iv;
+}
+
 /* Push (IV, NAME) on STACK.  */
 
 static void 
-loop_iv_stack_push (loop_iv_stack stack, tree iv, const char *name)
+loop_iv_stack_push_iv (loop_iv_stack stack, tree iv, const char *name)
 {
+  iv_stack_entry *entry = XNEW (iv_stack_entry);
   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);
+
+  entry->kind = iv_stack_entry_iv;
+  entry->data.iv = named_iv;
+
+  VEC_safe_push (iv_stack_entry_p, heap, *stack, entry);
+}
+
+/* Inserts a CONSTANT in STACK at INDEX.  */
+
+static void
+loop_iv_stack_insert_constant (loop_iv_stack stack, int index,
+			       tree constant)
+{
+  iv_stack_entry *entry = XNEW (iv_stack_entry);
+  
+  entry->kind = iv_stack_entry_const;
+  entry->data.constant = constant;
+
+  VEC_safe_insert (iv_stack_entry_p, heap, *stack, index, entry);
 }
 
-/* Pops an element out of STACK.  */
+/* Pops and frees an element out of STACK.  */
 
 static void
 loop_iv_stack_pop (loop_iv_stack stack)
 {
-  VEC_pop (name_tree, *stack);
+  iv_stack_entry_p e = VEC_pop (iv_stack_entry_p, *stack);
+  free (e);
 }
 
 /* Get the IV at INDEX in STACK.  */
@@ -120,7 +164,7 @@ loop_iv_stack_pop (loop_iv_stack stack)
 static tree
 loop_iv_stack_get_iv (loop_iv_stack stack, int index)
 {
-  name_tree named_iv = VEC_index (name_tree, *stack, index);
+  name_tree named_iv = VEC_index (iv_stack_entry_p, *stack, index)->data.iv;
 
   return named_iv->t;
 }
@@ -131,11 +175,14 @@ static tree
 loop_iv_stack_get_iv_from_name (loop_iv_stack stack, const char* name)
 {
   int i;
-  name_tree iv;
+  iv_stack_entry_p entry;
 
-  for (i = 0; VEC_iterate (name_tree, *stack, i, iv); i++)
-    if (!strcmp (name, iv->name))
-      return iv->t;
+  for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry); i++)
+    {
+      name_tree iv = entry->data.iv;
+      if (!strcmp (name, iv->name))
+	return iv->t;
+    }
 
   return NULL;
 }
@@ -143,27 +190,101 @@ loop_iv_stack_get_iv_from_name (loop_iv_
 /* Prints on stderr the contents of STACK.  */
 
 void
-loop_iv_stack_debug (loop_iv_stack stack)
+debug_loop_iv_stack (loop_iv_stack stack)
 {
   int i;
-  name_tree iv;
+  iv_stack_entry_p entry;
   bool first = true;
 
   fprintf (stderr, "(");
 
-  for (i = 0; VEC_iterate (name_tree, *stack, i, iv); i++)
+  for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry); i++)
     {
       if (first) 
 	first = false;
       else
 	fprintf (stderr, " ");
-      fprintf (stderr, "%s:", iv->name);
-      print_generic_expr (stderr, iv->t, 0);
+
+      if (iv_stack_entry_is_iv (entry))
+	{
+	  name_tree iv = entry->data.iv;
+	  fprintf (stderr, "%s:", iv->name);
+	  print_generic_expr (stderr, iv->t, 0);
+	}
+      else 
+	{
+	  tree constant = entry->data.constant;
+	  print_generic_expr (stderr, constant, 0);
+	  fprintf (stderr, ":");
+	  print_generic_expr (stderr, constant, 0);
+	}
     }
 
   fprintf (stderr, ")\n");
 }
 
+/* Frees STACK.  */
+
+static void
+free_loop_iv_stack (loop_iv_stack stack)
+{
+  int i;
+  iv_stack_entry_p entry;
+
+  for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry); i++)
+    free (entry);
+
+  VEC_free (iv_stack_entry_p, heap, *stack);
+}
+
+/* Inserts constants derived from the USER_STMT argument list into the
+   STACK.  This is needed to map old ivs to constants when loops have
+   been eliminated.  */
+
+static void 
+loop_iv_stack_patch_for_consts (loop_iv_stack stack,
+				struct clast_user_stmt *user_stmt)
+{
+  struct clast_stmt *t;
+  int index = 0;
+  for (t = user_stmt->substitutions; t; t = t->next) 
+    {
+      struct clast_term *term = (struct clast_term*) 
+	((struct clast_assignment *)t)->RHS;
+
+      /* FIXME: What should be done with expr_bin, expr_red?  */
+      if (((struct clast_assignment *)t)->RHS->type != expr_term)
+	continue;
+
+      if (!term->var) 
+	{
+	  tree value = gmp_cst_to_tree (term->val);
+	  loop_iv_stack_insert_constant (stack, index, value);
+	}
+      index = index + 1;
+    }
+}
+
+/* Removes all constants in the iv STACK.  */
+
+static void
+loop_iv_stack_remove_constants (loop_iv_stack stack)
+{
+  int i;
+  iv_stack_entry *entry;
+  
+  for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry);)
+    {
+      if (iv_stack_entry_is_constant (entry))
+	{
+	  free (VEC_index (iv_stack_entry_p, *stack, i));
+	  VEC_ordered_remove (iv_stack_entry_p, *stack, i);
+	}
+      else
+	i++;
+    }
+}
+
 /* In SCOP, get the induction variable from NAME.  OLD is the original
    loop that contained the definition of NAME.  */
 
@@ -2745,14 +2866,6 @@ build_scop_data_accesses (scop_p scop)
     }
 }
 
-/* Converts a GMP constant value to a tree and returns it.  */
-
-static tree
-gmp_cst_to_tree (Value v)
-{
-  return build_int_cst (integer_type_node, value_get_si (v));
-}
-
 /* Returns the tree variable from the name NAME that was given in
    Cloog representation.  All the parameters are stored in PARAMS, and
    all the loop induction variables are stored in IVSTACK.
@@ -3007,7 +3120,7 @@ graphite_create_new_loop (scop_p scop, e
 				    &iv_before, outer ? outer
 				    : entry_edge->src->loop_father);
 
-  loop_iv_stack_push (ivstack, iv_before, stmt->iterator);
+  loop_iv_stack_push_iv (ivstack, iv_before, stmt->iterator);
 
   return loop;
 }
@@ -3353,8 +3466,11 @@ translate_clast (scop_p scop, struct loo
       mark_virtual_ops_in_bb (bb);
       next_e = make_edge (bb,
 			  context_loop ? context_loop->latch : EXIT_BLOCK_PTR,
-			  EDGE_FALLTHRU);;
+			  EDGE_FALLTHRU);
+      loop_iv_stack_patch_for_consts (ivstack,
+				      (struct clast_user_stmt *) stmt);
       graphite_rename_ivs (gbb, scop, old_loop_father, ivstack);
+      loop_iv_stack_remove_constants (ivstack);
       return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
     }
 
@@ -3891,7 +4007,8 @@ gloog (scop_p scop, struct clast_stmt *s
   basic_block scop_exit = SCOP_EXIT (scop);
   VEC (tree, heap)* phi_args = 
     collect_scop_exit_phi_args (SESE_EXIT (SCOP_REGION (scop)));
-  VEC (name_tree, heap) *ivstack = VEC_alloc (name_tree, heap, 10);
+  VEC (iv_stack_entry_p, heap) *ivstack = 
+    VEC_alloc (iv_stack_entry_p, heap, 10);
   edge construction_edge = SESE_ENTRY (SCOP_REGION (scop));
   basic_block old_scop_exit_idom = get_immediate_dominator (CDI_DOMINATORS,
 							    scop_exit);
@@ -3902,10 +4019,13 @@ gloog (scop_p scop, struct clast_stmt *s
       return;
     }
 
+  redirect_edge_succ_nodup (construction_edge, EXIT_BLOCK_PTR);
   new_scop_exit_edge = translate_clast (scop, 
 					construction_edge->src->loop_father,
 					stmt, construction_edge, &ivstack);
+  free_loop_iv_stack (&ivstack);
   redirect_edge_succ (new_scop_exit_edge, scop_exit);
+
   if (!old_scop_exit_idom
       || !dominated_by_p (CDI_DOMINATORS, SCOP_ENTRY (scop),
 			  old_scop_exit_idom)
@@ -4711,23 +4831,39 @@ limit_scops (void)
   VEC (scop_p, heap) *new_scops = VEC_alloc (scop_p, heap, 3);
   int i;
   scop_p scop;
+  struct pointer_set_t *entry_exit_ptrs = pointer_set_create ();
 
   for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
     {
       int j;
       loop_p loop;
+
       build_scop_bbs (scop);
       build_scop_loop_nests (scop);
 
       for (j = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), j, loop); j++) 
         if (!loop_in_scop_p (loop_outer (loop), scop))
           {
+	    edge scop_entry_edge;
+	    edge scop_exit_edge;
 	    scop_p n_scop = new_scop (loop_preheader_edge (loop));
+
 	    end_scop (n_scop, single_exit (loop), false);
-	    VEC_safe_push (scop_p, heap, new_scops, n_scop);
+	    scop_entry_edge = SESE_ENTRY (SCOP_REGION (n_scop));
+	    scop_exit_edge = SESE_EXIT (SCOP_REGION (n_scop));
+
+	    if (!pointer_set_contains (entry_exit_ptrs, scop_entry_edge)
+		&& !pointer_set_contains (entry_exit_ptrs, scop_exit_edge))
+	      {
+		pointer_set_insert (entry_exit_ptrs, scop_entry_edge);
+		pointer_set_insert (entry_exit_ptrs, scop_exit_edge);
+
+		VEC_safe_push (scop_p, heap, new_scops, n_scop);
+	      }
 	  }
     }
 
+  pointer_set_destroy (entry_exit_ptrs);
   free_scops (current_scops);
   current_scops = new_scops;
 }
Index: graphite.h
===================================================================
--- graphite.h	(revision 140668)
+++ graphite.h	(working copy)
@@ -340,8 +340,34 @@ extern void debug_clast_stmt (struct cla
 extern void debug_loop_vec (graphite_bb_p gb);
 extern void debug_oldivs (scop_p);
 
-typedef VEC(name_tree, heap) **loop_iv_stack;
-extern void loop_iv_stack_debug (loop_iv_stack);
+/* Describes the type of an iv stack entry.  */
+typedef enum {
+  iv_stack_entry_unknown = 0,
+  iv_stack_entry_iv,
+  iv_stack_entry_const
+} iv_stack_entry_kind;
+
+/* Data contained in an iv stack entry.  */
+typedef union iv_stack_entry_data_union
+{
+  name_tree iv;
+  tree constant;
+} iv_stack_entry_data;
+
+/* Datatype for loop iv stack entry.  */
+typedef struct iv_stack_entry_struct
+{
+  iv_stack_entry_kind kind;
+  iv_stack_entry_data data;
+} iv_stack_entry;
+
+typedef iv_stack_entry* iv_stack_entry_p;
+
+DEF_VEC_P(iv_stack_entry_p);
+DEF_VEC_ALLOC_P(iv_stack_entry_p,heap);
+
+typedef VEC(iv_stack_entry_p, heap) **loop_iv_stack;
+extern void debug_loop_iv_stack (loop_iv_stack);
 
 
 /* Return the number of gimple loops contained in SCOP.  */

Re: [graphite] Fix PR37485

[Richard Guenther]

On Thu, 2 Oct 2008, Sebastian Pop wrote:

> Ping patches.
> 
> FYI, I've merged the graphite branch, and I've committed the
> attached fixes to the graphite branch.

IMHO the tree-ssa-loop-ivopts.c patch is wrong.  Which path
do we go to the failure?  It looks like we should instead
fix the type of comp earlier.  At least

      /* Otherwise, add the necessary computations to express
         the iv.  */
      op = fold_convert (ctype, cand->var_before);
      comp = fold_convert (utype,
                           build2 (incr_code, ctype, op,
                                   unshare_expr (step)));

doesn't look completely correct.

But you may want to try the following to detect latent type
problems with the testcase.

Richard.

2008-09-11  Richard Guenther  <rguenther@suse.de>

	* tree-cfg.c (remove_useless_stmts): Verify stmts afterwards.
	(verify_stmts): Dispatch to gimple/type verification code.

Index: trunk/gcc/tree-cfg.c
===================================================================
*** trunk.orig/gcc/tree-cfg.c
--- trunk/gcc/tree-cfg.c
*************** remove_useless_stmts (void)
*** 2024,2029 ****
--- 2024,2034 ----
        remove_useless_stmts_1 (&gsi, &data);
      }
    while (data.repeat);
+ 
+ #ifdef ENABLE_TYPES_CHECKING
+   verify_types_in_gimple_seq (gimple_body (current_function_decl));
+ #endif
+ 
    return 0;
  }
  
*************** verify_stmts (void)
*** 4153,4158 ****
--- 4210,4221 ----
  		  err |= true;
  		}
  	    }
+ 
+ 	  if (verify_gimple_phi (phi))
+ 	    {
+ 	      debug_gimple_stmt (phi);
+ 	      err |= true;
+ 	    }
  	}
  
        for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
*************** verify_stmts (void)
*** 4189,4194 ****
--- 4252,4263 ----
  	    }
  
  	  err |= verify_stmt (&gsi);
+ 
+ 	  if (verify_types_in_gimple_stmt (gsi_stmt (gsi)))
+ 	    {
+ 	      debug_gimple_stmt (stmt);
+ 	      err |= true;
+ 	    }
  	  addr = walk_gimple_op (gsi_stmt (gsi), verify_node_sharing, &wi);
  	  if (addr)
  	    {

Re: [graphite] Fix PR37485

[Richard Guenther]

On Thu, 2 Oct 2008, Sebastian Pop wrote:

> Ping patches.
> 
> FYI, I've merged the graphite branch, and I've committed the
> attached fixes to the graphite branch.

The graphite.[ch] parts are ok.

Thanks,
Richard.

Re: [graphite] Fix PR37485

[Sebastian Pop]

On Fri, Oct 3, 2008 at 5:06 PM, Richard Guenther <rguenther@suse.de> wrote:
> On Thu, 2 Oct 2008, Sebastian Pop wrote:
>
>> Ping patches.
>>
>> FYI, I've merged the graphite branch, and I've committed the
>> attached fixes to the graphite branch.
>
> IMHO the tree-ssa-loop-ivopts.c patch is wrong.  Which path
> do we go to the failure?

I was trying to reproduce the ivopts bug but I cannot anymore, so I
will have to find the right version of trunk that did triggered the
bug.  The testcase in the bug report passes without the extra
tree-ssa-loop-ivopts.c part, so I will commit the fix without it, and
then will investigate the ivopts problem.

Sebastian

Re: [graphite] Fix PR37485

[Daniel Berlin]

Do we consider graphite to fall under loop optimizers?
IE can either Zdenek or I review it?

On Thu, Sep 25, 2008 at 5:41 PM, Sebastian Pop <sebpop@gmail.com> wrote:
> On Thu, Sep 25, 2008 at 4:13 PM, David Edelsohn <dje.gcc@gmail.com> wrote:
>> You are not have the authority to approve and commit this patch.
>
> I will wait until somebody steps up to say ok to the patch.
>
> Sebastian
>

Re: [graphite] Fix PR37485

[Sebastian Pop]

On Thu, Sep 25, 2008 at 4:13 PM, David Edelsohn <dje.gcc@gmail.com> wrote:
> You are not have the authority to approve and commit this patch.

I will wait until somebody steps up to say ok to the patch.

Sebastian

Re: [graphite] Fix PR37485

[David Edelsohn]

>>>>> Sebastian Pop writes:

> As there is no maintainer for the graphite passes and the latency for
> reviewing the graphite patches is too long, I will commit the attached
> patch to trunk tomorrow after testing, unless somebody has a reason to
> say no.

You are not have the authority to approve and commit this patch.

David