2008-12-11 Harsha Jagasia <harsha.jagasia@amd.com>
authorspop <spop@138bc75d-0d04-0410-961f-82ee72b054a4>
Thu, 11 Dec 2008 19:35:41 +0000 (19:35 +0000)
committerspop <spop@138bc75d-0d04-0410-961f-82ee72b054a4>
Thu, 11 Dec 2008 19:35:41 +0000 (19:35 +0000)
PR tree-optimization/38446
* graphite.c (register_bb_in_sese): New.
(bb_in_sese_p): Check if bb belongs to sese region by explicitly
looking at the bbs in the region.
* graphite.h (sese): Add region_basic_blocks pointer set to
structure and initialize at the time of defining new scop.

2008-12-11  Tobias Grosser  <grosser@fim.uni-passau.de>

* graphite.c (new_graphite_bb): Initialize GBB_STATIC_SCHEDULE.
(find_params_in_bb): Do not free data refs.
(free_graphite_bb): Add FIXME on disabled free_data_refs.

2008-12-11  Sebastian Pop  <sebastian.pop@amd.com>

* graphite.c (struct ivtype_map_elt): New.
(debug_ivtype_elt, debug_ivtype_map_1, debug_ivtype_map,
new_ivtype_map_elt, ivtype_map_elt_info, eq_ivtype_map_elts,
gcc_type_for_cloog_iv): New.
(loop_iv_stack_patch_for_consts): Use the type of the induction
variable from the original loop, except for the automatically
generated loops, i.e., in the case of a strip-mined loop, in
which case there is no original loop: in that case just use
integer_type_node.
(new_graphite_bb): Initialize GBB_CLOOG_IV_TYPES.
(free_graphite_bb): Free GBB_CLOOG_IV_TYPES.
(clast_name_to_gcc): Accept params to be NULL.
(clast_to_gcc_expression): Take an extra parameter for the type.
Convert to that type all the expressions built by this function.
(gcc_type_for_clast_expr, gcc_type_for_clast_eq): New.
(graphite_translate_clast_equation): Compute the type of the
clast_equation before translating its LHS and RHS.
(clast_get_body_of_loop, gcc_type_for_iv_of_clast_loop): New.
(graphite_create_new_loop): Compute the type of the induction
variable before translating the lower and upper bounds and before
creating the induction variable.
(rename_variables_from_edge, rename_phis_end_scop): New.
(copy_bb_and_scalar_dependences): Call rename_phis_end_scop.
(sese_add_exit_phis_edge): Do not use integer_zero_node.
(find_cloog_iv_in_expr, compute_cloog_iv_types_1,
compute_cloog_iv_types): New.
(gloog): Call compute_cloog_iv_types before starting the
translation of the clast.

* graphite.h (struct graphite_bb): New field cloog_iv_types.
(GBB_CLOOG_IV_TYPES): New.
(debug_ivtype_map): Declared.
(oldiv_for_loop): New.

2008-12-10  Tobias Grosser  <grosser@fim.uni-passau.de>

PR middle-end/38459
* graphite.c (new_scop): Initialize SCOP_ADD_PARAMS.
(param_index): Assert if parameter is not know after parameter
detection.
(find_params_in_bb): Detect params directly in GBB_CONDITIONS.
(find_scop_parameters): Mark, that we have finished parameter
detection.
(graphite_transform_loops): Move condition detection before parameter
detection.
* graphite.h (struct scop): Add SCOP_ADD_PARAMS.

2008-12-11  Harsha Jagasia  <harsha.jagasia@amd.com>

PR tree-optimization/38446
* gcc.dg/graphite/pr38446.c: New.

2008-12-11  Sebastian Pop  <sebastian.pop@amd.com>

* gcc.dg/graphite/scop-16.c: Test only scop specific info.
* gcc.dg/graphite/scop-17.c: Same.
* gcc.dg/graphite/block-5.c: New.
* gcc.dg/graphite/block-6.c: New.
* gcc.dg/graphite/pr37485.c: Clean dump file after.
* gcc.dg/graphite/pr37684.c: Same.
* gcc.dg/graphite/block-2.c: Same.

2008-12-10  Tobias Grosser  <grosser@fim.uni-passau.de>

PR middle-end/38459
* gfortran.dg/graphite/pr38459.f90: New.

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

14 files changed:
gcc/ChangeLog
gcc/graphite.c
gcc/graphite.h
gcc/testsuite/ChangeLog
gcc/testsuite/gcc.dg/graphite/block-2.c [new file with mode: 0644]
gcc/testsuite/gcc.dg/graphite/block-5.c [new file with mode: 0644]
gcc/testsuite/gcc.dg/graphite/block-6.c [new file with mode: 0644]
gcc/testsuite/gcc.dg/graphite/pr37485.c
gcc/testsuite/gcc.dg/graphite/pr37684.c
gcc/testsuite/gcc.dg/graphite/pr38446.c [new file with mode: 0644]
gcc/testsuite/gcc.dg/graphite/scop-15.c
gcc/testsuite/gcc.dg/graphite/scop-16.c
gcc/testsuite/gcc.dg/graphite/scop-17.c
gcc/testsuite/gfortran.dg/graphite/pr38459.f90 [new file with mode: 0644]

index a697b51..64a7b92 100644 (file)
@@ -1,3 +1,67 @@
+2008-12-11  Harsha Jagasia  <harsha.jagasia@amd.com>
+
+       PR tree-optimization/38446
+       * graphite.c (register_bb_in_sese): New.
+       (bb_in_sese_p): Check if bb belongs to sese region by explicitly
+       looking at the bbs in the region.
+       * graphite.h (sese): Add region_basic_blocks pointer set to
+       structure and initialize at the time of defining new scop.
+
+2008-12-11  Tobias Grosser  <grosser@fim.uni-passau.de>
+
+       * graphite.c (new_graphite_bb): Initialize GBB_STATIC_SCHEDULE.
+       (find_params_in_bb): Do not free data refs.
+       (free_graphite_bb): Add FIXME on disabled free_data_refs.
+
+2008-12-11  Sebastian Pop  <sebastian.pop@amd.com>
+
+       * graphite.c (struct ivtype_map_elt): New.
+       (debug_ivtype_elt, debug_ivtype_map_1, debug_ivtype_map,
+       new_ivtype_map_elt, ivtype_map_elt_info, eq_ivtype_map_elts,
+       gcc_type_for_cloog_iv): New.
+       (loop_iv_stack_patch_for_consts): Use the type of the induction
+       variable from the original loop, except for the automatically
+       generated loops, i.e., in the case of a strip-mined loop, in
+       which case there is no original loop: in that case just use
+       integer_type_node.
+       (new_graphite_bb): Initialize GBB_CLOOG_IV_TYPES.
+       (free_graphite_bb): Free GBB_CLOOG_IV_TYPES.
+       (clast_name_to_gcc): Accept params to be NULL.
+       (clast_to_gcc_expression): Take an extra parameter for the type.
+       Convert to that type all the expressions built by this function.
+       (gcc_type_for_clast_expr, gcc_type_for_clast_eq): New.
+       (graphite_translate_clast_equation): Compute the type of the
+       clast_equation before translating its LHS and RHS.
+       (clast_get_body_of_loop, gcc_type_for_iv_of_clast_loop): New.
+       (graphite_create_new_loop): Compute the type of the induction
+       variable before translating the lower and upper bounds and before
+       creating the induction variable.
+       (rename_variables_from_edge, rename_phis_end_scop): New.
+       (copy_bb_and_scalar_dependences): Call rename_phis_end_scop.
+       (sese_add_exit_phis_edge): Do not use integer_zero_node.
+       (find_cloog_iv_in_expr, compute_cloog_iv_types_1,
+       compute_cloog_iv_types): New.
+       (gloog): Call compute_cloog_iv_types before starting the
+       translation of the clast.
+
+       * graphite.h (struct graphite_bb): New field cloog_iv_types.
+       (GBB_CLOOG_IV_TYPES): New.
+       (debug_ivtype_map): Declared.
+       (oldiv_for_loop): New.
+
+2008-12-10  Tobias Grosser  <grosser@fim.uni-passau.de>
+
+       PR middle-end/38459
+       * graphite.c (new_scop): Initialize SCOP_ADD_PARAMS.
+       (param_index): Assert if parameter is not know after parameter
+       detection.
+       (find_params_in_bb): Detect params directly in GBB_CONDITIONS.
+       (find_scop_parameters): Mark, that we have finished parameter
+       detection.
+       (graphite_transform_loops): Move condition detection before parameter
+       detection.
+       * graphite.h (struct scop): Add SCOP_ADD_PARAMS.
+
 2008-12-11  John David Anglin  <dave.anglin@nrc-cnrc.gc.ca>
 
        PR testsuite/35677
index 7c2b8da..877dffe 100644 (file)
@@ -64,9 +64,9 @@ 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)
+gmp_cst_to_tree (tree type, Value v)
 {
-  return build_int_cst (integer_type_node, value_get_si (v));
+  return build_int_cst (type, value_get_si (v));
 }
 
 /* Debug the list of old induction variables for this SCOP.  */
@@ -244,6 +244,98 @@ free_loop_iv_stack (loop_iv_stack stack)
   VEC_free (iv_stack_entry_p, heap, *stack);
 }
 
+\f
+
+/* Structure containing the mapping between the CLooG's induction
+   variable and the type of the old induction variable.  */
+typedef struct ivtype_map_elt
+{
+  tree type;
+  const char *cloog_iv;
+} *ivtype_map_elt;
+
+/* Print to stderr the element ELT.  */
+
+static void
+debug_ivtype_elt (ivtype_map_elt elt)
+{
+  fprintf (stderr, "(%s, ", elt->cloog_iv);
+  print_generic_expr (stderr, elt->type, 0);
+  fprintf (stderr, ")\n");
+}
+
+/* Helper function for debug_ivtype_map.  */
+
+static int
+debug_ivtype_map_1 (void **slot, void *s ATTRIBUTE_UNUSED)
+{
+  struct ivtype_map_elt *entry = (struct ivtype_map_elt *) *slot;
+  debug_ivtype_elt (entry);
+  return 1;
+}
+
+/* Print to stderr all the elements of MAP.  */
+
+void
+debug_ivtype_map (htab_t map)
+{
+  htab_traverse (map, debug_ivtype_map_1, NULL);
+}
+
+/* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW.  */
+
+static inline ivtype_map_elt
+new_ivtype_map_elt (const char *cloog_iv, tree type)
+{
+  ivtype_map_elt res;
+  
+  res = XNEW (struct ivtype_map_elt);
+  res->cloog_iv = cloog_iv;
+  res->type = type;
+
+  return res;
+}
+
+/* Computes a hash function for database element ELT.  */
+
+static hashval_t
+ivtype_map_elt_info (const void *elt)
+{
+  return htab_hash_pointer (((const struct ivtype_map_elt *) elt)->cloog_iv);
+}
+
+/* Compares database elements E1 and E2.  */
+
+static int
+eq_ivtype_map_elts (const void *e1, const void *e2)
+{
+  const struct ivtype_map_elt *elt1 = (const struct ivtype_map_elt *) e1;
+  const struct ivtype_map_elt *elt2 = (const struct ivtype_map_elt *) e2;
+
+  return (elt1->cloog_iv == elt2->cloog_iv);
+}
+
+\f
+
+/* Given a CLOOG_IV, returns the type that it should have in GCC land.
+   If the information is not available, i.e. in the case one of the
+   transforms created the loop, just return integer_type_node.  */
+
+static tree
+gcc_type_for_cloog_iv (const char *cloog_iv, graphite_bb_p gbb)
+{
+  struct ivtype_map_elt tmp;
+  PTR *slot;
+
+  tmp.cloog_iv = cloog_iv;
+  slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, NO_INSERT);
+
+  if (slot && *slot)
+    return ((ivtype_map_elt) *slot)->type;
+
+  return integer_type_node;
+}
+
 /* 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.  */
@@ -254,16 +346,23 @@ loop_iv_stack_patch_for_consts (loop_iv_stack stack,
 {
   struct clast_stmt *t;
   int index = 0;
+  CloogStatement *cs = user_stmt->statement;
+  graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
+
   for (t = user_stmt->substitutions; t; t = t->next) 
     {
-      struct clast_term *term = (struct clast_term*) 
+      struct clast_expr *expr = (struct clast_expr *) 
        ((struct clast_assignment *)t)->RHS;
+      struct clast_term *term = (struct clast_term *) expr;
 
       /* FIXME: What should be done with expr_bin, expr_red?  */
-      if (((struct clast_assignment *)t)->RHS->type == expr_term
+      if (expr->type == expr_term
          && !term->var)
        {
-         tree value = gmp_cst_to_tree (term->val);
+         loop_p loop = gbb_loop_at_index (gbb, index);
+         tree oldiv = oldiv_for_loop (GBB_SCOP (gbb), loop);
+         tree type = oldiv ? TREE_TYPE (oldiv) : integer_type_node;
+         tree value = gmp_cst_to_tree (type, term->val);
          loop_iv_stack_insert_constant (stack, index, value);
        }
       index = index + 1;
@@ -1056,6 +1155,8 @@ new_graphite_bb (scop_p scop, basic_block bb)
   GBB_CONDITIONS (gbb) = NULL;
   GBB_CONDITION_CASES (gbb) = NULL;
   GBB_LOOPS (gbb) = NULL;
+  GBB_STATIC_SCHEDULE (gbb) = NULL;
+  GBB_CLOOG_IV_TYPES (gbb) = NULL;
   VEC_safe_push (graphite_bb_p, heap, SCOP_BBS (scop), gbb);
 }
 
@@ -1067,6 +1168,14 @@ free_graphite_bb (struct graphite_bb *gbb)
   if (GBB_DOMAIN (gbb))
     cloog_matrix_free (GBB_DOMAIN (gbb));
 
+  if (GBB_CLOOG_IV_TYPES (gbb))
+    htab_delete (GBB_CLOOG_IV_TYPES (gbb));
+
+  /* FIXME: free_data_refs is disabled for the moment, but should be
+     enabled.
+
+     free_data_refs (GBB_DATA_REFS (gbb)); */
+
   VEC_free (gimple, heap, GBB_CONDITIONS (gbb));
   VEC_free (gimple, heap, GBB_CONDITION_CASES (gbb));
   VEC_free (loop_p, heap, GBB_LOOPS (gbb));
@@ -1074,6 +1183,26 @@ free_graphite_bb (struct graphite_bb *gbb)
   XDELETE (gbb);
 }
 
+/* Register basic blocks belonging to a region in a pointer set.  */
+
+static void
+register_bb_in_sese (basic_block entry_bb, basic_block exit_bb, sese region)
+{
+  edge_iterator ei;
+  edge e;
+  basic_block bb = entry_bb;
+
+  FOR_EACH_EDGE (e, ei, bb->succs)
+    {
+      if (!pointer_set_contains (SESE_REGION_BBS (region), e->dest) &&
+         e->dest->index != exit_bb->index)
+       {       
+         pointer_set_insert (SESE_REGION_BBS (region), e->dest);
+         register_bb_in_sese (e->dest, exit_bb, region);
+       }
+    }
+}
+
 /* Creates a new scop starting with ENTRY.  */
 
 static scop_p
@@ -1086,6 +1215,9 @@ new_scop (edge entry, edge exit)
   SCOP_REGION (scop) = XNEW (struct sese);
   SESE_ENTRY (SCOP_REGION (scop)) = entry;
   SESE_EXIT (SCOP_REGION (scop)) = exit;
+  SESE_REGION_BBS (SCOP_REGION (scop)) = pointer_set_create ();
+  register_bb_in_sese (SCOP_ENTRY (scop), SCOP_EXIT (scop),
+                      SCOP_REGION (scop));
   SCOP_BBS (scop) = VEC_alloc (graphite_bb_p, heap, 3);
   SCOP_OLDIVS (scop) = VEC_alloc (name_tree, heap, 3);
   SCOP_BBS_B (scop) = BITMAP_ALLOC (NULL);
@@ -1513,7 +1645,6 @@ scopdet_basic_block_info (basic_block bb, VEC (sd_region, heap) **scops,
 static struct scopdet_info 
 build_scops_1 (basic_block current, VEC (sd_region, heap) **scops, loop_p loop)
 {
-
   bool in_scop = false;
   sd_region open_scop;
   struct scopdet_info sinfo;
@@ -2465,7 +2596,6 @@ find_params_in_bb (scop_p scop, graphite_bb_p gb)
       irp.loop = father;
       irp.scop = scop;
       for_each_index (&dr->ref, idx_record_params, &irp);
-      free_data_ref (dr);
     }
 
   /* Find parameters in conditional statements.  */ 
@@ -3277,9 +3407,10 @@ clast_name_to_gcc (const char *name, VEC (name_tree, heap) *params,
   name_tree t;
   tree iv;
 
-  for (i = 0; VEC_iterate (name_tree, params, i, t); i++)
-    if (!strcmp (name, t->name))
-      return t->t;
+  if (params)
+    for (i = 0; VEC_iterate (name_tree, params, i, t); i++)
+      if (!strcmp (name, t->name))
+       return t->t;
 
   iv = loop_iv_stack_get_iv_from_name (ivstack, name);
   if (iv)
@@ -3288,24 +3419,24 @@ clast_name_to_gcc (const char *name, VEC (name_tree, heap) *params,
   gcc_unreachable ();
 }
 
-/* A union needed to convert from CLAST expressions to GMP values.  */
+/* Returns the maximal precision type for expressions E1 and E2.  */
 
-typedef union {
-  struct clast_expr *c;
-  Value v;
-} value_clast;
+static inline tree
+max_precision_type (tree e1, tree e2)
+{
+  tree type1 = TREE_TYPE (e1);
+  tree type2 = TREE_TYPE (e2);
+  return TYPE_PRECISION (type1) > TYPE_PRECISION (type2) ? type1 : type2;
+}
 
-/* Converts a Cloog AST expression E back to a GCC expression tree.   */
+/* Converts a Cloog AST expression E back to a GCC expression tree
+   of type TYPE.  */
 
 static tree
-clast_to_gcc_expression (struct clast_expr *e,
+clast_to_gcc_expression (tree type, struct clast_expr *e,
                         VEC (name_tree, heap) *params,
                         loop_iv_stack ivstack)
 {
-  tree type = integer_type_node;
-
-  gcc_assert (e);
-
   switch (e->type)
     {
     case expr_term:
@@ -3315,53 +3446,62 @@ clast_to_gcc_expression (struct clast_expr *e,
        if (t->var)
          {
            if (value_one_p (t->val))
-             return clast_name_to_gcc (t->var, params, ivstack);
+             {
+               tree name = clast_name_to_gcc (t->var, params, ivstack);
+               return fold_convert (type, name);
+             }
 
            else if (value_mone_p (t->val))
-             return fold_build1 (NEGATE_EXPR, type,
-                                 clast_name_to_gcc (t->var, params, ivstack));
+             {
+               tree name = clast_name_to_gcc (t->var, params, ivstack);
+               name = fold_convert (type, name);
+               return fold_build1 (NEGATE_EXPR, type, name);
+             }
            else
-             return fold_build2 (MULT_EXPR, type,
-                                 gmp_cst_to_tree (t->val),
-                                 clast_name_to_gcc (t->var, params, ivstack));
+             {
+               tree name = clast_name_to_gcc (t->var, params, ivstack);
+               tree cst = gmp_cst_to_tree (type, t->val);
+               name = fold_convert (type, name);
+               return fold_build2 (MULT_EXPR, type, cst, name);
+             }
          }
        else
-         return gmp_cst_to_tree (t->val);
+         return gmp_cst_to_tree (type, t->val);
       }
 
     case expr_red:
       {
         struct clast_reduction *r = (struct clast_reduction *) e;
-        tree left, right;
 
         switch (r->type)
           {
          case clast_red_sum:
            if (r->n == 1)
-             return clast_to_gcc_expression (r->elts[0], params, ivstack);
+             return clast_to_gcc_expression (type, r->elts[0], params, ivstack);
 
            else 
              {
+               tree tl = clast_to_gcc_expression (type, r->elts[0], params, ivstack);
+               tree tr = clast_to_gcc_expression (type, r->elts[1], params, ivstack);
+
                gcc_assert (r->n >= 1
                            && r->elts[0]->type == expr_term
                            && r->elts[1]->type == expr_term);
 
-               left = clast_to_gcc_expression (r->elts[0], params, ivstack);
-               right = clast_to_gcc_expression (r->elts[1], params, ivstack);
-               return fold_build2 (PLUS_EXPR, type, left, right);
+               return fold_build2 (PLUS_EXPR, type, tl, tr);
              }
 
            break;
 
          case clast_red_min:
            if (r->n == 1)
-             return clast_to_gcc_expression (r->elts[0], params, ivstack);
+             return clast_to_gcc_expression (type, r->elts[0], params, ivstack);
 
            else if (r->n == 2)
              {
-               left = clast_to_gcc_expression (r->elts[0], params, ivstack);
-               right = clast_to_gcc_expression (r->elts[1], params, ivstack);
-               return fold_build2 (MIN_EXPR, type, left, right);
+               tree tl = clast_to_gcc_expression (type, r->elts[0], params, ivstack);
+               tree tr = clast_to_gcc_expression (type, r->elts[1], params, ivstack);
+               return fold_build2 (MIN_EXPR, type, tl, tr);
              }
 
            else
@@ -3371,13 +3511,13 @@ clast_to_gcc_expression (struct clast_expr *e,
 
          case clast_red_max:
            if (r->n == 1)
-             return clast_to_gcc_expression (r->elts[0], params, ivstack);
+             return clast_to_gcc_expression (type, r->elts[0], params, ivstack);
 
            else if (r->n == 2)
              {
-               left = clast_to_gcc_expression (r->elts[0], params, ivstack);
-               right = clast_to_gcc_expression (r->elts[1], params, ivstack);
-               return fold_build2 (MAX_EXPR, type, left, right);
+               tree tl = clast_to_gcc_expression (type, r->elts[0], params, ivstack);
+               tree tr = clast_to_gcc_expression (type, r->elts[1], params, ivstack);
+               return fold_build2 (MAX_EXPR, type, tl, tr);
              }
 
            else
@@ -3395,12 +3535,8 @@ clast_to_gcc_expression (struct clast_expr *e,
       {
        struct clast_binary *b = (struct clast_binary *) e;
        struct clast_expr *lhs = (struct clast_expr *) b->LHS;
-       tree tl = clast_to_gcc_expression (lhs, params, ivstack);
-       value_clast r;
-       tree tr;
-
-       r.c = (struct clast_expr *) b->RHS;
-       tr = gmp_cst_to_tree (r.v);
+       tree tl = clast_to_gcc_expression (type, lhs, params, ivstack);
+       tree tr = gmp_cst_to_tree (type, b->RHS);
 
        switch (b->type)
          {
@@ -3428,6 +3564,72 @@ clast_to_gcc_expression (struct clast_expr *e,
   return NULL_TREE;
 }
 
+/* Returns the type for the expression E.  */
+
+static tree
+gcc_type_for_clast_expr (struct clast_expr *e,
+                        VEC (name_tree, heap) *params,
+                        loop_iv_stack ivstack)
+{
+  switch (e->type)
+    {
+    case expr_term:
+      {
+       struct clast_term *t = (struct clast_term *) e;
+
+       if (t->var)
+         return TREE_TYPE (clast_name_to_gcc (t->var, params, ivstack));
+       else
+         return NULL_TREE;
+      }
+
+    case expr_red:
+      {
+        struct clast_reduction *r = (struct clast_reduction *) e;
+
+       if (r->n == 1)
+         return gcc_type_for_clast_expr (r->elts[0], params, ivstack);
+       else 
+         {
+           int i;
+           for (i = 0; i < r->n; i++)
+             {
+               tree type = gcc_type_for_clast_expr (r->elts[i], params, ivstack);
+               if (type)
+                 return type;
+             }
+           return NULL_TREE;
+         }
+      }
+
+    case expr_bin:
+      {
+       struct clast_binary *b = (struct clast_binary *) e;
+       struct clast_expr *lhs = (struct clast_expr *) b->LHS;
+       return gcc_type_for_clast_expr (lhs, params, ivstack);
+      }
+
+    default:
+      gcc_unreachable ();
+    }
+
+  return NULL_TREE;
+}
+
+/* Returns the type for the equation CLEQ.  */
+
+static tree
+gcc_type_for_clast_eq (struct clast_equation *cleq,
+                      VEC (name_tree, heap) *params,
+                      loop_iv_stack ivstack)
+{
+  tree type = gcc_type_for_clast_expr (cleq->LHS, params, ivstack);
+  if (type)
+    return type;
+
+  return gcc_type_for_clast_expr (cleq->RHS, params, ivstack);
+}
+
 /* Translates a clast equation CLEQ to a tree.  */
 
 static tree
@@ -3436,8 +3638,9 @@ graphite_translate_clast_equation (scop_p scop,
                                   loop_iv_stack ivstack)
 {
   enum tree_code comp;
-  tree lhs = clast_to_gcc_expression (cleq->LHS, SCOP_PARAMS (scop), ivstack);
-  tree rhs = clast_to_gcc_expression (cleq->RHS, SCOP_PARAMS (scop), ivstack);
+  tree type = gcc_type_for_clast_eq (cleq, SCOP_PARAMS (scop), ivstack);
+  tree lhs = clast_to_gcc_expression (type, cleq->LHS, SCOP_PARAMS (scop), ivstack);
+  tree rhs = clast_to_gcc_expression (type, cleq->RHS, SCOP_PARAMS (scop), ivstack);
 
   if (cleq->sign == 0)
     comp = EQ_EXPR;
@@ -3448,7 +3651,7 @@ graphite_translate_clast_equation (scop_p scop,
   else
     comp = LE_EXPR;
 
-  return fold_build2 (comp, integer_type_node, lhs, rhs);
+  return fold_build2 (comp, type, lhs, rhs);
 }
 
 /* Creates the test for the condition in STMT.  */
@@ -3465,7 +3668,7 @@ graphite_create_guard_cond_expr (scop_p scop, struct clast_guard *stmt,
       tree eq = graphite_translate_clast_equation (scop, &stmt->eq[i], ivstack);
 
       if (cond)
-       cond = fold_build2 (TRUTH_AND_EXPR, integer_type_node, cond, eq);
+       cond = fold_build2 (TRUTH_AND_EXPR, TREE_TYPE (eq), cond, eq);
       else
        cond = eq;
     }
@@ -3485,6 +3688,41 @@ graphite_create_new_guard (scop_p scop, edge entry_edge,
   return exit_edge;
 }
 
+/* Walks a CLAST and returns the first statement in the body of a
+   loop.  */
+
+static struct clast_user_stmt *
+clast_get_body_of_loop (struct clast_stmt *stmt)
+{
+  if (!stmt
+      || CLAST_STMT_IS_A (stmt, stmt_user))
+    return (struct clast_user_stmt *) stmt;
+
+  if (CLAST_STMT_IS_A (stmt, stmt_for))
+    return clast_get_body_of_loop (((struct clast_for *) stmt)->body);
+
+  if (CLAST_STMT_IS_A (stmt, stmt_guard))
+    return clast_get_body_of_loop (((struct clast_guard *) stmt)->then);
+
+  if (CLAST_STMT_IS_A (stmt, stmt_block))
+    return clast_get_body_of_loop (((struct clast_block *) stmt)->body);
+
+  gcc_unreachable ();
+}
+
+/* Returns the induction variable for the loop that gets translated to
+   STMT.  */
+
+static tree
+gcc_type_for_iv_of_clast_loop (struct clast_for *stmt_for)
+{
+  struct clast_user_stmt *stmt = clast_get_body_of_loop ((struct clast_stmt *) stmt_for);
+  const char *cloog_iv = stmt_for->iterator;
+  CloogStatement *cs = stmt->statement;
+  graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
+
+  return gcc_type_for_cloog_iv (cloog_iv, gbb);
+}
 
 /* Creates a new LOOP corresponding to Cloog's STMT.  Inserts an induction 
    variable for the new LOOP.  New LOOP is attached to CFG starting at
@@ -3496,26 +3734,19 @@ graphite_create_new_loop (scop_p scop, edge entry_edge,
                          struct clast_for *stmt, loop_iv_stack ivstack,
                          loop_p outer)
 {
-  struct loop *loop;
-  tree ivvar;
-  tree stride, lowb, upb;
+  tree type = gcc_type_for_iv_of_clast_loop (stmt);
+  VEC (name_tree, heap) *params = SCOP_PARAMS (scop);
+  tree lb = clast_to_gcc_expression (type, stmt->LB, params, ivstack);
+  tree ub = clast_to_gcc_expression (type, stmt->UB, params, ivstack);
+  tree stride = gmp_cst_to_tree (type, stmt->stride);
+  tree ivvar = create_tmp_var (type, "graphiteIV");
   tree iv_before;
+  loop_p loop = create_empty_loop_on_edge
+    (entry_edge, lb, stride, ub, ivvar, &iv_before,
+     outer ? outer : entry_edge->src->loop_father);
 
-  gcc_assert (stmt->LB
-             && stmt->UB);
-
-  stride = gmp_cst_to_tree (stmt->stride);
-  lowb = clast_to_gcc_expression (stmt->LB, SCOP_PARAMS (scop), ivstack);
-  ivvar = create_tmp_var (integer_type_node, "graphiteIV");
   add_referenced_var (ivvar);
-
-  upb = clast_to_gcc_expression (stmt->UB, SCOP_PARAMS (scop), ivstack);
-  loop = create_empty_loop_on_edge (entry_edge, lowb, stride, upb, ivvar,
-                                   &iv_before, outer ? outer
-                                   : entry_edge->src->loop_father);
-
   loop_iv_stack_push_iv (ivstack, iv_before, stmt->iterator);
-
   return loop;
 }
 
@@ -3786,9 +4017,7 @@ expand_scalar_variables (basic_block bb, scop_p scop,
     }
 }
 
-/* Rename all the SSA_NAMEs from block BB that appear in IVSTACK in
-   terms of new induction variables.  OLD is the original loop that
-   contained BB.  */
+/* Rename all the SSA_NAMEs from block BB according to the MAP.  */
 
 static void 
 rename_variables (basic_block bb, htab_t map)
@@ -3799,6 +4028,38 @@ rename_variables (basic_block bb, htab_t map)
     rename_variables_in_stmt (gsi_stmt (gsi), map);
 }
 
+/* Rename following the information from MAP the PHI node argument
+   corresponding to the edge E.  In order to allow several renames of
+   that argument, we match the original SSA_NAME on the argument
+   coming from the edge different than E.  */
+
+static void
+rename_variables_from_edge (edge e, gimple phi, htab_t map)
+{
+  int n = e->dest_idx == 0 ? 1 : 0;
+  tree old_name = gimple_phi_arg_def (phi, n);
+  tree new_name = get_new_name_from_old_name (map, old_name);
+
+  gcc_assert (gimple_phi_num_args (phi) == 2
+             && gimple_phi_arg_edge (phi, e->dest_idx) == e);
+
+  SET_PHI_ARG_DEF (phi, n, new_name);
+}
+
+/* Rename all the phi arguments for the edges comming from the scop
+   according to the MAP.  */
+
+static void
+rename_phis_end_scop (scop_p scop, htab_t map)
+{
+  basic_block after_scop = SCOP_EXIT (scop);
+  edge e = SESE_EXIT (SCOP_REGION (scop));
+  gimple_stmt_iterator gsi;
+
+  for (gsi = gsi_start_phis (after_scop); !gsi_end_p (gsi); gsi_next (&gsi))
+    rename_variables_from_edge (e, gsi_stmt (gsi), map);
+}
+
 /* Remove condition from BB.  */
 
 static void
@@ -3950,6 +4211,7 @@ copy_bb_and_scalar_dependences (basic_block bb, scop_p scop,
   rename_variables (new_bb, map);
   remove_phi_nodes (new_bb);
   expand_scalar_variables (new_bb, scop, context_loop, map);
+  rename_phis_end_scop (scop, map);
 
   return next_e;
 }
@@ -4447,8 +4709,7 @@ move_sese_in_condition (sese region)
 static bool
 bb_in_sese_p (basic_block bb, sese region)
 {
-  return (dominated_by_p (CDI_DOMINATORS, bb, SESE_ENTRY (region)->src)
-         && dominated_by_p (CDI_POST_DOMINATORS, bb, SESE_EXIT (region)->dest));
+  return pointer_set_contains (SESE_REGION_BBS (region), bb);
 }
 
 /* For USE in BB, if it is used outside of the REGION it is defined in,
@@ -4505,7 +4766,7 @@ sese_find_uses_to_rename_bb (sese region, basic_block bb,
       sese_find_uses_to_rename_use (region, bb, var, use_blocks, need_phis);
 }
 
-/* Add exit phis for the USE on EXIT.  */
+/* Add exit phis for USE on EXIT.  */
 
 static void
 sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e)
@@ -4515,7 +4776,7 @@ sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e)
   create_new_def_for (gimple_phi_result (phi), phi,
                      gimple_phi_result_ptr (phi));
   add_phi_arg (phi, use, false_e);
-  add_phi_arg (phi, integer_zero_node, true_e);
+  add_phi_arg (phi, use, true_e);
 }
 
 /* Add phi nodes for VAR that is used in LIVEIN.  Phi nodes are
@@ -4573,6 +4834,123 @@ rewrite_into_sese_closed_ssa (sese region, basic_block where,
   BITMAP_FREE (names_to_rename);
 }
 
+/* Returns the first cloog name used in EXPR.  */
+
+static const char *
+find_cloog_iv_in_expr (struct clast_expr *expr)
+{
+  struct clast_term *term = (struct clast_term *) expr;
+
+  if (expr->type == expr_term
+      && !term->var)
+    return NULL;
+
+  if (expr->type == expr_term)
+    return term->var;
+
+  if (expr->type == expr_red)
+    {
+      int i;
+      struct clast_reduction *red = (struct clast_reduction *) expr;
+
+      for (i = 0; i < red->n; i++)
+       {
+         const char *res = find_cloog_iv_in_expr ((red)->elts[i]);
+
+         if (res)
+           return res;
+       }
+    }
+
+  return NULL;
+}
+
+/* Build for a clast_user_stmt USER_STMT a map between the CLAST
+   induction variables and the corresponding GCC old induction
+   variables.  This information is stored on each GRAPHITE_BB.  */
+
+static void
+compute_cloog_iv_types_1 (graphite_bb_p gbb,
+                         struct clast_user_stmt *user_stmt)
+{
+  struct clast_stmt *t;
+  int index = 0;
+
+  for (t = user_stmt->substitutions; t; t = t->next, index++)
+    {
+      PTR *slot;
+      struct ivtype_map_elt tmp;
+      struct clast_expr *expr = (struct clast_expr *) 
+       ((struct clast_assignment *)t)->RHS;
+
+      /* Create an entry (clast_var, type).  */
+      tmp.cloog_iv = find_cloog_iv_in_expr (expr);
+      if (!tmp.cloog_iv)
+       continue;
+
+      slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, INSERT);
+
+      if (!*slot)
+       {
+         loop_p loop = gbb_loop_at_index (gbb, index);
+         tree oldiv = oldiv_for_loop (GBB_SCOP (gbb), loop);
+         tree type = oldiv ? TREE_TYPE (oldiv) : integer_type_node;
+         *slot = new_ivtype_map_elt (tmp.cloog_iv, type);
+       }
+    }
+}
+
+/* Walk the CLAST tree starting from STMT and build for each
+   clast_user_stmt a map between the CLAST induction variables and the
+   corresponding GCC old induction variables.  This information is
+   stored on each GRAPHITE_BB.  */
+
+static void
+compute_cloog_iv_types (struct clast_stmt *stmt)
+{
+  if (!stmt)
+    return;
+
+  if (CLAST_STMT_IS_A (stmt, stmt_root))
+    goto next;
+
+  if (CLAST_STMT_IS_A (stmt, stmt_user))
+    {
+      CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
+      graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
+      GBB_CLOOG_IV_TYPES (gbb) = htab_create (10, ivtype_map_elt_info,
+                                             eq_ivtype_map_elts, free);
+      compute_cloog_iv_types_1 (gbb, (struct clast_user_stmt *) stmt);
+      goto next;
+    }
+
+  if (CLAST_STMT_IS_A (stmt, stmt_for))
+    {
+      struct clast_stmt *s = ((struct clast_for *) stmt)->body;
+      compute_cloog_iv_types (s);
+      goto next;
+    }
+
+  if (CLAST_STMT_IS_A (stmt, stmt_guard))
+    {
+      struct clast_stmt *s = ((struct clast_guard *) stmt)->then;
+      compute_cloog_iv_types (s);
+      goto next;
+    }
+
+  if (CLAST_STMT_IS_A (stmt, stmt_block))
+    {
+      struct clast_stmt *s = ((struct clast_block *) stmt)->body;
+      compute_cloog_iv_types (s);
+      goto next;
+    }
+
+  gcc_unreachable ();
+
+ next:
+  compute_cloog_iv_types (stmt->next);
+}
+
 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
    the given SCOP.  */
 
@@ -4598,6 +4976,7 @@ gloog (scop_p scop, struct clast_stmt *stmt)
                                if_region->true_region->exit);
   graphite_verify ();
   context_loop = SESE_ENTRY (SCOP_REGION (scop))->src->loop_father;
+  compute_cloog_iv_types (stmt);
   new_scop_exit_edge = translate_clast (scop, context_loop,
                                        stmt, if_region->true_region->entry,
                                        &ivstack);
index faae009..92a6816 100644 (file)
@@ -193,6 +193,7 @@ typedef struct graphite_bb
   lambda_vector compressed_alpha_matrix;
   CloogMatrix *dynamic_schedule;
   VEC (data_reference_p, heap) *data_refs;
+  htab_t cloog_iv_types;
 } *gbb_p;
 
 #define GBB_BB(GBB) GBB->bb
@@ -205,6 +206,7 @@ typedef struct graphite_bb
 #define GBB_CONDITIONS(GBB) GBB->conditions
 #define GBB_CONDITION_CASES(GBB) GBB->condition_cases
 #define GBB_LOOPS(GBB) GBB->loops
+#define GBB_CLOOG_IV_TYPES(GBB) GBB->cloog_iv_types
 
 /* Return the loop that contains the basic block GBB.  */
 
@@ -274,10 +276,12 @@ DEF_VEC_ALLOC_P (name_tree, heap);
 typedef struct sese
 {
   edge entry, exit;
+  struct pointer_set_t *region_basic_blocks;
 } *sese;
 
 #define SESE_ENTRY(S) (S->entry)
 #define SESE_EXIT(S) (S->exit)
+#define SESE_REGION_BBS(S) (S->region_basic_blocks)
 
 /* A SCOP is a Static Control Part of the program, simple enough to be
    represented in polyhedral form.  */
@@ -327,6 +331,7 @@ struct scop
    but just a boundary.  SCOP_ENTRY is considered part of the scop.  */
 #define SCOP_ENTRY(S) (SESE_ENTRY (SCOP_REGION (S))->dest)
 #define SCOP_EXIT(S) (SESE_EXIT (SCOP_REGION (S))->dest)
+#define SCOP_REGION_BBS(S) (SESE_REGION_BBS (SCOP_REGION (S)))
 #define SCOP_STATIC_SCHEDULE(S) S->static_schedule
 #define SCOP_LOOPS(S) S->loops
 #define SCOP_LOOP_NEST(S) S->loop_nest
@@ -345,7 +350,8 @@ extern void dot_scop (scop_p);
 extern void dot_all_scops (void);
 extern void debug_clast_stmt (struct clast_stmt *);
 extern void debug_rename_map (htab_t);
-extern void debug_loop_vec (graphite_bb_p gb);
+extern void debug_ivtype_map (htab_t);
+extern void debug_loop_vec (graphite_bb_p);
 extern void debug_oldivs (scop_p);
 
 /* Describes the type of an iv stack entry.  */
@@ -377,6 +383,25 @@ 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 old induction variable of the LOOP that is in normal
+   form in SCOP.  */
+
+static inline tree
+oldiv_for_loop (scop_p scop, loop_p loop)
+{
+  int i;
+  name_tree iv;
+
+  if (!loop)
+    return NULL_TREE;
+
+  for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, iv); i++)
+    if (iv->loop == loop)
+      return iv->t;
+
+  return NULL_TREE;
+}
+
 /* Return the number of gimple loops contained in SCOP.  */
 
 static inline int
index 207da42..cdf137f 100644 (file)
@@ -1,3 +1,23 @@
+2008-12-11  Harsha Jagasia  <harsha.jagasia@amd.com>
+
+       PR tree-optimization/38446
+       * gcc.dg/graphite/pr38446.c: New.
+
+2008-12-11  Sebastian Pop  <sebastian.pop@amd.com>
+
+       * gcc.dg/graphite/scop-16.c: Test only scop specific info.
+       * gcc.dg/graphite/scop-17.c: Same.
+       * gcc.dg/graphite/block-5.c: New.
+       * gcc.dg/graphite/block-6.c: New.
+       * gcc.dg/graphite/pr37485.c: Clean dump file after.
+       * gcc.dg/graphite/pr37684.c: Same.
+       * gcc.dg/graphite/block-2.c: Same.
+
+2008-12-10  Tobias Grosser  <grosser@fim.uni-passau.de>
+
+       PR middle-end/38459
+       * gfortran.dg/graphite/pr38459.f90: New.
+
 2008-12-11  Sebastian Pop  <sebastian.pop@amd.com>
 
        PR middle-end/37852
diff --git a/gcc/testsuite/gcc.dg/graphite/block-2.c b/gcc/testsuite/gcc.dg/graphite/block-2.c
new file mode 100644 (file)
index 0000000..cf0969b
--- /dev/null
@@ -0,0 +1,32 @@
+/* { 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 *-*-* }} } */
+/* { dg-final { cleanup-tree-dump "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/block-5.c b/gcc/testsuite/gcc.dg/graphite/block-5.c
new file mode 100644 (file)
index 0000000..e0bd468
--- /dev/null
@@ -0,0 +1,26 @@
+/* { dg-options "-O2 -floop-block -fdump-tree-graphite-all" } */
+
+#define N 10000
+void foo (int);
+int test ()
+{
+  int a[N][N];
+  int b[N][N];
+  unsigned i, j;
+
+  for (i = 0; i < N; i++) 
+    for (j = 0; j < N; j++)
+      a[i][j] = i*j;
+
+  for (j = 1; j < N; j++) 
+    for (i = 0; i < N; i++)
+      a[i][j] = a[i][j-1] + b[i][j];
+
+  for (i = 0; i < N; i++) 
+    for (j = 0; j < N; j++) 
+      foo (a[i][j]); 
+}
+
+/* Interchange is legal for loops 0 and 1 of the first two SCoPs */
+/* { dg-final { scan-tree-dump-times "Interchange valid for loops 0 and 1:" 2 "graphite"} } */
+/* { dg-final { cleanup-tree-dump "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/block-6.c b/gcc/testsuite/gcc.dg/graphite/block-6.c
new file mode 100644 (file)
index 0000000..77429f1
--- /dev/null
@@ -0,0 +1,25 @@
+/* { dg-options "-O2 -floop-block -fdump-tree-graphite-all" } */
+
+#define N 10000
+void foo (int);
+int test ()
+{
+  int a[N][N];
+  unsigned i, j;
+
+  for (i = 0; i < N; i++) 
+    for (j = 0; j < N; j++)
+       a[i][j] = i*j;
+
+  for (i = 1; i < N; i++) 
+    for (j = 1; j < (N-1) ; j++)
+       a[i][j] = a[i-1][j+1] * a[i-1][j+1]/2;
+
+  for (i = 0; i < N; i++) 
+    for (j = 0; j < N; j++)
+      foo (a[i][j]); 
+}
+
+/* Interchange is not legal for loops 0 and 1 of SCoP 2.  */
+/* { dg-final { scan-tree-dump-times "Interchange not valid for loops 0 and 1:" 1 "graphite"} } */
+/* { dg-final { cleanup-tree-dump "graphite" } } */