--- /dev/null
+/* Gimple Represented as Polyhedra.
+ Copyright (C) 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
+ Contributed by Sebastian Pop <sebastian.pop@inria.fr>.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
+
+/* This pass converts GIMPLE to GRAPHITE, performs some loop
+ transformations and then converts the resulting representation back
+ to GIMPLE.
+
+ An early description of this pass can be found in the GCC Summit'06
+ paper "GRAPHITE: Polyhedral Analyses and Optimizations for GCC".
+ The wiki page http://gcc.gnu.org/wiki/Graphite contains pointers to
+ the related work.
+
+ One important document to read is CLooG's internal manual:
+ http://repo.or.cz/w/cloog-ppl.git?a=blob_plain;f=doc/cloog.texi;hb=HEAD
+ that describes the data structure of loops used in this file, and
+ the functions that are used for transforming the code. */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "ggc.h"
+#include "tree.h"
+#include "rtl.h"
+#include "basic-block.h"
+#include "diagnostic.h"
+#include "tree-flow.h"
+#include "toplev.h"
+#include "tree-dump.h"
+#include "timevar.h"
+#include "cfgloop.h"
+#include "tree-chrec.h"
+#include "tree-data-ref.h"
+#include "tree-scalar-evolution.h"
+#include "tree-pass.h"
+#include "domwalk.h"
+#include "value-prof.h"
+#include "pointer-set.h"
+#include "gimple.h"
+
+#ifdef HAVE_cloog
+#include "cloog/cloog.h"
+#include "graphite.h"
+
+static VEC (scop_p, heap) *current_scops;
+
+/* Converts a GMP constant V to a tree and returns it. */
+
+static tree
+gmp_cst_to_tree (tree type, Value v)
+{
+ return build_int_cst (type, value_get_si (v));
+}
+
+/* Returns true when BB is in REGION. */
+
+static bool
+bb_in_sese_p (basic_block bb, sese region)
+{
+ return pointer_set_contains (SESE_REGION_BBS (region), bb);
+}
+
+/* Returns true when LOOP is in the SESE region R. */
+
+static inline bool
+loop_in_sese_p (struct loop *loop, sese r)
+{
+ return (bb_in_sese_p (loop->header, r)
+ && bb_in_sese_p (loop->latch, r));
+}
+
+/* For a USE in BB, if BB is outside REGION, mark the USE in the
+ SESE_LIVEIN and SESE_LIVEOUT sets. */
+
+static void
+sese_build_livein_liveouts_use (sese region, basic_block bb, tree use)
+{
+ unsigned ver;
+ basic_block def_bb;
+
+ if (TREE_CODE (use) != SSA_NAME)
+ return;
+
+ ver = SSA_NAME_VERSION (use);
+ def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
+ if (!def_bb
+ || !bb_in_sese_p (def_bb, region)
+ || bb_in_sese_p (bb, region))
+ return;
+
+ if (!SESE_LIVEIN_VER (region, ver))
+ SESE_LIVEIN_VER (region, ver) = BITMAP_ALLOC (NULL);
+
+ bitmap_set_bit (SESE_LIVEIN_VER (region, ver), bb->index);
+ bitmap_set_bit (SESE_LIVEOUT (region), ver);
+}
+
+/* Marks for rewrite all the SSA_NAMES defined in REGION and that are
+ used in BB that is outside of the REGION. */
+
+static void
+sese_build_livein_liveouts_bb (sese region, basic_block bb)
+{
+ gimple_stmt_iterator bsi;
+ edge e;
+ edge_iterator ei;
+ ssa_op_iter iter;
+ tree var;
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi))
+ sese_build_livein_liveouts_use (region, bb,
+ PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi), e));
+
+ for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+ FOR_EACH_SSA_TREE_OPERAND (var, gsi_stmt (bsi), iter, SSA_OP_ALL_USES)
+ sese_build_livein_liveouts_use (region, bb, var);
+}
+
+/* Build the SESE_LIVEIN and SESE_LIVEOUT for REGION. */
+
+void
+sese_build_livein_liveouts (sese region)
+{
+ basic_block bb;
+
+ SESE_LIVEOUT (region) = BITMAP_ALLOC (NULL);
+ SESE_NUM_VER (region) = num_ssa_names;
+ SESE_LIVEIN (region) = XCNEWVEC (bitmap, SESE_NUM_VER (region));
+
+ FOR_EACH_BB (bb)
+ sese_build_livein_liveouts_bb (region, bb);
+}
+
+/* Register basic blocks belonging to a region in a pointer set. */
+
+static void
+register_bb_in_sese (basic_block entry_bb, basic_block exit_bb, sese region)
+{
+ edge_iterator ei;
+ edge e;
+ basic_block bb = entry_bb;
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ if (!pointer_set_contains (SESE_REGION_BBS (region), e->dest) &&
+ e->dest->index != exit_bb->index)
+ {
+ pointer_set_insert (SESE_REGION_BBS (region), e->dest);
+ register_bb_in_sese (e->dest, exit_bb, region);
+ }
+ }
+}
+
+/* Builds a new SESE region from edges ENTRY and EXIT. */
+
+sese
+new_sese (edge entry, edge exit)
+{
+ sese res = XNEW (struct sese);
+
+ SESE_ENTRY (res) = entry;
+ SESE_EXIT (res) = exit;
+ SESE_REGION_BBS (res) = pointer_set_create ();
+ register_bb_in_sese (entry->dest, exit->dest, res);
+
+ SESE_LIVEOUT (res) = NULL;
+ SESE_NUM_VER (res) = 0;
+ SESE_LIVEIN (res) = NULL;
+
+ return res;
+}
+
+/* Deletes REGION. */
+
+void
+free_sese (sese region)
+{
+ int i;
+
+ for (i = 0; i < SESE_NUM_VER (region); i++)
+ BITMAP_FREE (SESE_LIVEIN_VER (region, i));
+
+ if (SESE_LIVEIN (region))
+ free (SESE_LIVEIN (region));
+
+ if (SESE_LIVEOUT (region))
+ BITMAP_FREE (SESE_LIVEOUT (region));
+
+ pointer_set_destroy (SESE_REGION_BBS (region));
+ XDELETE (region);
+}
+
+\f
+
+/* Debug the list of old induction variables for this SCOP. */
+
+void
+debug_oldivs (scop_p scop)
+{
+ int i;
+ name_tree oldiv;
+
+ fprintf (stderr, "Old IVs:");
+
+ for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, oldiv); i++)
+ {
+ fprintf (stderr, "(");
+ print_generic_expr (stderr, oldiv->t, 0);
+ fprintf (stderr, ", %s, %d)\n", oldiv->name, oldiv->loop->num);
+ }
+ fprintf (stderr, "\n");
+}
+
+/* Debug the loops around basic block GB. */
+
+void
+debug_loop_vec (graphite_bb_p gb)
+{
+ int i;
+ loop_p loop;
+
+ fprintf (stderr, "Loop Vec:");
+
+ for (i = 0; VEC_iterate (loop_p, GBB_LOOPS (gb), i, loop); i++)
+ fprintf (stderr, "%d: %d, ", i, loop ? loop->num : -1);
+
+ 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_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;
+
+ 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 and frees an element out of STACK. */
+
+static void
+loop_iv_stack_pop (loop_iv_stack stack)
+{
+ iv_stack_entry_p entry = VEC_pop (iv_stack_entry_p, *stack);
+
+ free (entry->data.iv);
+ free (entry);
+}
+
+/* Get the IV at INDEX in STACK. */
+
+static tree
+loop_iv_stack_get_iv (loop_iv_stack stack, int index)
+{
+ iv_stack_entry_p entry = VEC_index (iv_stack_entry_p, *stack, index);
+ iv_stack_entry_data data = entry->data;
+
+ return iv_stack_entry_is_iv (entry) ? data.iv->t : data.constant;
+}
+
+/* Get the IV from its NAME in STACK. */
+
+static tree
+loop_iv_stack_get_iv_from_name (loop_iv_stack stack, const char* name)
+{
+ int i;
+ iv_stack_entry_p entry;
+
+ 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;
+}
+
+/* Prints on stderr the contents of STACK. */
+
+void
+debug_loop_iv_stack (loop_iv_stack stack)
+{
+ int i;
+ iv_stack_entry_p entry;
+ bool first = true;
+
+ fprintf (stderr, "(");
+
+ for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry); i++)
+ {
+ if (first)
+ first = false;
+ else
+ fprintf (stderr, " ");
+
+ 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->data.iv);
+ free (entry);
+ }
+
+ 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. */
+
+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;
+ 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_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 (expr->type == expr_term
+ && !term->var)
+ {
+ 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;
+ }
+}
+
+/* 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++;
+ }
+}
+
+/* Returns a new loop_to_cloog_loop_str structure. */
+
+static inline struct loop_to_cloog_loop_str *
+new_loop_to_cloog_loop_str (int loop_num,
+ int loop_position,
+ CloogLoop *cloog_loop)
+{
+ struct loop_to_cloog_loop_str *result;
+
+ result = XNEW (struct loop_to_cloog_loop_str);
+ result->loop_num = loop_num;
+ result->cloog_loop = cloog_loop;
+ result->loop_position = loop_position;
+
+ return result;
+}
+
+/* Hash function for SCOP_LOOP2CLOOG_LOOP hash table. */
+
+static hashval_t
+hash_loop_to_cloog_loop (const void *elt)
+{
+ return ((const struct loop_to_cloog_loop_str *) elt)->loop_num;
+}
+
+/* Equality function for SCOP_LOOP2CLOOG_LOOP hash table. */
+
+static int
+eq_loop_to_cloog_loop (const void *el1, const void *el2)
+{
+ const struct loop_to_cloog_loop_str *elt1, *elt2;
+
+ elt1 = (const struct loop_to_cloog_loop_str *) el1;
+ elt2 = (const struct loop_to_cloog_loop_str *) el2;
+ return elt1->loop_num == elt2->loop_num;
+}
+
+/* Compares two graphite bbs and returns an integer less than, equal to, or
+ greater than zero if the first argument is considered to be respectively
+ less than, equal to, or greater than the second.
+ We compare using the lexicographic order of the static schedules. */
+
+static int
+gbb_compare (const void *p_1, const void *p_2)
+{
+ const struct graphite_bb *const gbb_1
+ = *(const struct graphite_bb *const*) p_1;
+ const struct graphite_bb *const gbb_2
+ = *(const struct graphite_bb *const*) p_2;
+
+ return lambda_vector_compare (GBB_STATIC_SCHEDULE (gbb_1),
+ gbb_nb_loops (gbb_1) + 1,
+ GBB_STATIC_SCHEDULE (gbb_2),
+ gbb_nb_loops (gbb_2) + 1);
+}
+
+/* Sort graphite bbs in SCOP. */
+
+static void
+graphite_sort_gbbs (scop_p scop)
+{
+ VEC (graphite_bb_p, heap) *bbs = SCOP_BBS (scop);
+
+ qsort (VEC_address (graphite_bb_p, bbs),
+ VEC_length (graphite_bb_p, bbs),
+ sizeof (graphite_bb_p), gbb_compare);
+}
+
+/* Dump conditions of a graphite basic block GBB on FILE. */
+
+static void
+dump_gbb_conditions (FILE *file, graphite_bb_p gbb)
+{
+ int i;
+ gimple stmt;
+ VEC (gimple, heap) *conditions = GBB_CONDITIONS (gbb);
+
+ if (VEC_empty (gimple, conditions))
+ return;
+
+ fprintf (file, "\tbb %d\t: cond = {", GBB_BB (gbb)->index);
+
+ for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
+ print_gimple_stmt (file, stmt, 0, 0);
+
+ fprintf (file, "}\n");
+}
+
+/* Converts the graphite scheduling function into a cloog scattering
+ matrix. This scattering matrix is used to limit the possible cloog
+ output to valid programs in respect to the scheduling function.
+
+ SCATTERING_DIMENSIONS specifies the dimensionality of the scattering
+ matrix. CLooG 0.14.0 and previous versions require, that all scattering
+ functions of one CloogProgram have the same dimensionality, therefore we
+ allow to specify it. (Should be removed in future versions) */
+
+static CloogMatrix *
+schedule_to_scattering (graphite_bb_p gb, int scattering_dimensions)
+{
+ int i;
+ scop_p scop = GBB_SCOP (gb);
+
+ int nb_iterators = gbb_nb_loops (gb);
+
+ /* The cloog scattering matrix consists of these colums:
+ 1 col = Eq/Inq,
+ scattering_dimensions cols = Scattering dimensions,
+ nb_iterators cols = bb's iterators,
+ scop_nb_params cols = Parameters,
+ 1 col = Constant 1.
+
+ Example:
+
+ scattering_dimensions = 5
+ max_nb_iterators = 2
+ nb_iterators = 1
+ scop_nb_params = 2
+
+ Schedule:
+ ? i
+ 4 5
+
+ Scattering Matrix:
+ s1 s2 s3 s4 s5 i p1 p2 1
+ 1 0 0 0 0 0 0 0 -4 = 0
+ 0 1 0 0 0 -1 0 0 0 = 0
+ 0 0 1 0 0 0 0 0 -5 = 0 */
+ int nb_params = scop_nb_params (scop);
+ int nb_cols = 1 + scattering_dimensions + nb_iterators + nb_params + 1;
+ int col_const = nb_cols - 1;
+ int col_iter_offset = 1 + scattering_dimensions;
+
+ CloogMatrix *scat = cloog_matrix_alloc (scattering_dimensions, nb_cols);
+
+ gcc_assert (scattering_dimensions >= nb_iterators * 2 + 1);
+
+ /* Initialize the identity matrix. */
+ for (i = 0; i < scattering_dimensions; i++)
+ value_set_si (scat->p[i][i + 1], 1);
+
+ /* Textual order outside the first loop */
+ value_set_si (scat->p[0][col_const], -GBB_STATIC_SCHEDULE (gb)[0]);
+
+ /* For all surrounding loops. */
+ for (i = 0; i < nb_iterators; i++)
+ {
+ int schedule = GBB_STATIC_SCHEDULE (gb)[i + 1];
+
+ /* Iterations of this loop. */
+ value_set_si (scat->p[2 * i + 1][col_iter_offset + i], -1);
+
+ /* Textual order inside this loop. */
+ value_set_si (scat->p[2 * i + 2][col_const], -schedule);
+ }
+
+ return scat;
+}
+
+/* Print the schedules of GB to FILE with INDENT white spaces before.
+ VERBOSITY determines how verbose the code pretty printers are. */
+
+void
+print_graphite_bb (FILE *file, graphite_bb_p gb, int indent, int verbosity)
+{
+ CloogMatrix *scattering;
+ int i;
+ loop_p loop;
+ fprintf (file, "\nGBB (\n");
+
+ print_loops_bb (file, GBB_BB (gb), indent+2, verbosity);
+
+ if (GBB_DOMAIN (gb))
+ {
+ fprintf (file, " (domain: \n");
+ cloog_matrix_print (file, GBB_DOMAIN (gb));
+ fprintf (file, " )\n");
+ }
+
+ if (GBB_STATIC_SCHEDULE (gb))
+ {
+ fprintf (file, " (static schedule: ");
+ print_lambda_vector (file, GBB_STATIC_SCHEDULE (gb),
+ gbb_nb_loops (gb) + 1);
+ fprintf (file, " )\n");
+ }
+
+ if (GBB_LOOPS (gb))
+ {
+ fprintf (file, " (contained loops: \n");
+ for (i = 0; VEC_iterate (loop_p, GBB_LOOPS (gb), i, loop); i++)
+ if (loop == NULL)
+ fprintf (file, " iterator %d => NULL \n", i);
+ else
+ fprintf (file, " iterator %d => loop %d \n", i,
+ loop->num);
+ fprintf (file, " )\n");
+ }
+
+ if (GBB_DATA_REFS (gb))
+ dump_data_references (file, GBB_DATA_REFS (gb));
+
+ if (GBB_CONDITIONS (gb))
+ {
+ fprintf (file, " (conditions: \n");
+ dump_gbb_conditions (file, gb);
+ fprintf (file, " )\n");
+ }
+
+ if (GBB_SCOP (gb)
+ && GBB_STATIC_SCHEDULE (gb))
+ {
+ fprintf (file, " (scattering: \n");
+ scattering = schedule_to_scattering (gb, 2 * gbb_nb_loops (gb) + 1);
+ cloog_matrix_print (file, scattering);
+ cloog_matrix_free (scattering);
+ fprintf (file, " )\n");
+ }
+
+ fprintf (file, ")\n");
+}
+
+/* Print to STDERR the schedules of GB with VERBOSITY level. */
+
+void
+debug_gbb (graphite_bb_p gb, int verbosity)
+{
+ print_graphite_bb (stderr, gb, 0, verbosity);
+}
+
+
+/* Print SCOP to FILE. VERBOSITY determines how verbose the pretty
+ printers are. */
+
+static void
+print_scop (FILE *file, scop_p scop, int verbosity)
+{
+ if (scop == NULL)
+ return;
+
+ fprintf (file, "\nSCoP_%d_%d (\n",
+ SCOP_ENTRY (scop)->index, SCOP_EXIT (scop)->index);
+
+ fprintf (file, " (cloog: \n");
+ cloog_program_print (file, SCOP_PROG (scop));
+ fprintf (file, " )\n");
+
+ if (SCOP_BBS (scop))
+ {
+ graphite_bb_p gb;
+ int i;
+
+ for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
+ print_graphite_bb (file, gb, 0, verbosity);
+ }
+
+ fprintf (file, ")\n");
+}
+
+/* Print all the SCOPs to FILE. VERBOSITY determines how verbose the
+ code pretty printers are. */
+
+static void
+print_scops (FILE *file, int verbosity)
+{
+ int i;
+ scop_p scop;
+
+ for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
+ print_scop (file, scop, verbosity);
+}
+
+/* Debug SCOP. VERBOSITY determines how verbose the code pretty
+ printers are. */
+
+void
+debug_scop (scop_p scop, int verbosity)
+{
+ print_scop (stderr, scop, verbosity);
+}
+
+/* Debug all SCOPs from CURRENT_SCOPS. VERBOSITY determines how
+ verbose the code pretty printers are. */
+
+void
+debug_scops (int verbosity)
+{
+ print_scops (stderr, verbosity);
+}
+
+/* Pretty print to FILE the SCOP in DOT format. */
+
+static void
+dot_scop_1 (FILE *file, scop_p scop)
+{
+ edge e;
+ edge_iterator ei;
+ basic_block bb;
+ basic_block entry = SCOP_ENTRY (scop);
+ basic_block exit = SCOP_EXIT (scop);
+
+ fprintf (file, "digraph SCoP_%d_%d {\n", entry->index,
+ exit->index);
+
+ FOR_ALL_BB (bb)
+ {
+ if (bb == entry)
+ fprintf (file, "%d [shape=triangle];\n", bb->index);
+
+ if (bb == exit)
+ fprintf (file, "%d [shape=box];\n", bb->index);
+
+ if (bb_in_sese_p (bb, SCOP_REGION (scop)))
+ fprintf (file, "%d [color=red];\n", bb->index);
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
+ }
+
+ fputs ("}\n\n", file);
+}
+
+/* Display SCOP using dotty. */
+
+void
+dot_scop (scop_p scop)
+{
+ dot_scop_1 (stderr, scop);
+}
+
+/* Pretty print all SCoPs in DOT format and mark them with different colors.
+ If there are not enough colors, paint later SCoPs gray.
+ Special nodes:
+ - "*" after the node number: entry of a SCoP,
+ - "#" after the node number: exit of a SCoP,
+ - "()" entry or exit not part of SCoP. */
+
+static void
+dot_all_scops_1 (FILE *file)
+{
+ basic_block bb;
+ edge e;
+ edge_iterator ei;
+ scop_p scop;
+ const char* color;
+ int i;
+
+ /* Disable debugging while printing graph. */
+ int tmp_dump_flags = dump_flags;
+ dump_flags = 0;
+
+ fprintf (file, "digraph all {\n");
+
+ FOR_ALL_BB (bb)
+ {
+ int part_of_scop = false;
+
+ /* Use HTML for every bb label. So we are able to print bbs
+ which are part of two different SCoPs, with two different
+ background colors. */
+ fprintf (file, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
+ bb->index);
+ fprintf (file, "CELLSPACING=\"0\">\n");
+
+ /* Select color for SCoP. */
+ for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
+ if (bb_in_sese_p (bb, SCOP_REGION (scop))
+ || (SCOP_EXIT (scop) == bb)
+ || (SCOP_ENTRY (scop) == bb))
+ {
+ switch (i % 17)
+ {
+ case 0: /* red */
+ color = "#e41a1c";
+ break;
+ case 1: /* blue */
+ color = "#377eb8";
+ break;
+ case 2: /* green */
+ color = "#4daf4a";
+ break;
+ case 3: /* purple */
+ color = "#984ea3";
+ break;
+ case 4: /* orange */
+ color = "#ff7f00";
+ break;
+ case 5: /* yellow */
+ color = "#ffff33";
+ break;
+ case 6: /* brown */
+ color = "#a65628";
+ break;
+ case 7: /* rose */
+ color = "#f781bf";
+ break;
+ case 8:
+ color = "#8dd3c7";
+ break;
+ case 9:
+ color = "#ffffb3";
+ break;
+ case 10:
+ color = "#bebada";
+ break;
+ case 11:
+ color = "#fb8072";
+ break;
+ case 12:
+ color = "#80b1d3";
+ break;
+ case 13:
+ color = "#fdb462";
+ break;
+ case 14:
+ color = "#b3de69";
+ break;
+ case 15:
+ color = "#fccde5";
+ break;
+ case 16:
+ color = "#bc80bd";
+ break;
+ default: /* gray */
+ color = "#999999";
+ }
+
+ fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color);
+
+ if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
+ fprintf (file, " (");
+
+ if (bb == SCOP_ENTRY (scop)
+ && bb == SCOP_EXIT (scop))
+ fprintf (file, " %d*# ", bb->index);
+ else if (bb == SCOP_ENTRY (scop))
+ fprintf (file, " %d* ", bb->index);
+ else if (bb == SCOP_EXIT (scop))
+ fprintf (file, " %d# ", bb->index);
+ else
+ fprintf (file, " %d ", bb->index);
+
+ if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
+ fprintf (file, ")");
+
+ fprintf (file, "</TD></TR>\n");
+ part_of_scop = true;
+ }
+
+ if (!part_of_scop)
+ {
+ fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
+ fprintf (file, " %d </TD></TR>\n", bb->index);
+ }
+
+ fprintf (file, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
+ }
+
+ FOR_ALL_BB (bb)
+ {
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
+ }
+
+ fputs ("}\n\n", file);
+
+ /* Enable debugging again. */
+ dump_flags = tmp_dump_flags;
+}
+
+/* Display all SCoPs using dotty. */
+
+void
+dot_all_scops (void)
+{
+ /* When debugging, enable the following code. This cannot be used
+ in production compilers because it calls "system". */
+#if 0
+ FILE *stream = fopen ("/tmp/allscops.dot", "w");
+ gcc_assert (stream);
+
+ dot_all_scops_1 (stream);
+ fclose (stream);
+
+ system ("dotty /tmp/allscops.dot");
+#else
+ dot_all_scops_1 (stderr);
+#endif
+}
+
+/* Returns the outermost loop in SCOP that contains BB. */
+
+static struct loop *
+outermost_loop_in_scop (scop_p scop, basic_block bb)
+{
+ struct loop *nest;
+
+ nest = bb->loop_father;
+ while (loop_outer (nest)
+ && loop_in_sese_p (loop_outer (nest), SCOP_REGION (scop)))
+ nest = loop_outer (nest);
+
+ return nest;
+}
+
+/* Returns the block preceding the entry of SCOP. */
+
+static basic_block
+block_before_scop (scop_p scop)
+{
+ return SESE_ENTRY (SCOP_REGION (scop))->src;
+}
+
+/* Return true when EXPR is an affine function in LOOP with parameters
+ instantiated relative to SCOP_ENTRY. */
+
+static bool
+loop_affine_expr (basic_block scop_entry, struct loop *loop, tree expr)
+{
+ int n = loop->num;
+ tree scev = analyze_scalar_evolution (loop, expr);
+
+ scev = instantiate_scev (scop_entry, loop, scev);
+
+ return (evolution_function_is_invariant_p (scev, n)
+ || evolution_function_is_affine_multivariate_p (scev, n));
+}
+
+/* Return true if REF or any of its subtrees contains a
+ component_ref. */
+
+static bool
+contains_component_ref_p (tree ref)
+{
+ if (!ref)
+ return false;
+
+ while (handled_component_p (ref))
+ {
+ if (TREE_CODE (ref) == COMPONENT_REF)
+ return true;
+
+ ref = TREE_OPERAND (ref, 0);
+ }
+
+ return false;
+}
+
+/* Return true if the operand OP is simple. */
+
+static bool
+is_simple_operand (loop_p loop, gimple stmt, tree op)
+{
+ /* It is not a simple operand when it is a declaration, */
+ if (DECL_P (op)
+ /* or a structure, */
+ || AGGREGATE_TYPE_P (TREE_TYPE (op))
+ /* or a COMPONENT_REF, */
+ || contains_component_ref_p (op)
+ /* or a memory access that cannot be analyzed by the data
+ reference analysis. */
+ || ((handled_component_p (op) || INDIRECT_REF_P (op))
+ && !stmt_simple_memref_p (loop, stmt, op)))
+ return false;
+
+ return true;
+}
+
+/* Return true only when STMT is simple enough for being handled by
+ Graphite. This depends on SCOP_ENTRY, as the parametetrs are
+ initialized relatively to this basic block. */
+
+static bool
+stmt_simple_for_scop_p (basic_block scop_entry, gimple stmt)
+{
+ basic_block bb = gimple_bb (stmt);
+ struct loop *loop = bb->loop_father;
+
+ /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
+ Calls have side-effects, except those to const or pure
+ functions. */
+ if (gimple_has_volatile_ops (stmt)
+ || (gimple_code (stmt) == GIMPLE_CALL
+ && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
+ || (gimple_code (stmt) == GIMPLE_ASM))
+ return false;
+
+ switch (gimple_code (stmt))
+ {
+ case GIMPLE_RETURN:
+ case GIMPLE_LABEL:
+ return true;
+
+ case GIMPLE_COND:
+ {
+ tree op;
+ ssa_op_iter op_iter;
+ enum tree_code code = gimple_cond_code (stmt);
+
+ /* We can only handle this kind of conditional expressions.
+ For inequalities like "if (i != 3 * k)" we need unions of
+ polyhedrons. Expressions like "if (a)" or "if (a == 15)" need
+ them for the else branch. */
+ if (!(code == LT_EXPR
+ || code == GT_EXPR
+ || code == LE_EXPR
+ || code == GE_EXPR))
+ return false;
+
+ if (!scop_entry)
+ return false;
+
+ FOR_EACH_SSA_TREE_OPERAND (op, stmt, op_iter, SSA_OP_ALL_USES)
+ if (!loop_affine_expr (scop_entry, loop, op))
+ return false;
+
+ return true;
+ }
+
+ case GIMPLE_ASSIGN:
+ {
+ enum tree_code code = gimple_assign_rhs_code (stmt);
+
+ switch (get_gimple_rhs_class (code))
+ {
+ case GIMPLE_UNARY_RHS:
+ case GIMPLE_SINGLE_RHS:
+ return (is_simple_operand (loop, stmt, gimple_assign_lhs (stmt))
+ && is_simple_operand (loop, stmt, gimple_assign_rhs1 (stmt)));
+
+ case GIMPLE_BINARY_RHS:
+ return (is_simple_operand (loop, stmt, gimple_assign_lhs (stmt))
+ && is_simple_operand (loop, stmt, gimple_assign_rhs1 (stmt))
+ && is_simple_operand (loop, stmt, gimple_assign_rhs2 (stmt)));
+
+ case GIMPLE_INVALID_RHS:
+ default:
+ gcc_unreachable ();
+ }
+ }
+
+ case GIMPLE_CALL:
+ {
+ size_t i;
+ size_t n = gimple_call_num_args (stmt);
+ tree lhs = gimple_call_lhs (stmt);
+
+ if (lhs && !is_simple_operand (loop, stmt, lhs))
+ return false;
+
+ for (i = 0; i < n; i++)
+ if (!is_simple_operand (loop, stmt, gimple_call_arg (stmt, i)))
+ return false;
+
+ return true;
+ }
+
+ default:
+ /* These nodes cut a new scope. */
+ return false;
+ }
+
+ return false;
+}
+
+/* Returns the statement of BB that contains a harmful operation: that
+ can be a function call with side effects, the induction variables
+ are not linear with respect to SCOP_ENTRY, etc. The current open
+ scop should end before this statement. */
+
+static gimple
+harmful_stmt_in_bb (basic_block scop_entry, basic_block bb)
+{
+ gimple_stmt_iterator gsi;
+ gimple stmt;
+
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ if (!stmt_simple_for_scop_p (scop_entry, gsi_stmt (gsi)))
+ return gsi_stmt (gsi);
+
+ stmt = last_stmt (bb);
+ if (stmt && gimple_code (stmt) == GIMPLE_COND)
+ {
+ tree lhs = gimple_cond_lhs (stmt);
+ tree rhs = gimple_cond_rhs (stmt);
+
+ if (TREE_CODE (TREE_TYPE (lhs)) == REAL_TYPE
+ || TREE_CODE (TREE_TYPE (rhs)) == REAL_TYPE)
+ return stmt;
+ }
+
+ return NULL;
+}
+
+/* Returns true when BB will be represented in graphite. Return false
+ for the basic blocks that contain code eliminated in the code
+ generation pass: i.e. induction variables and exit conditions. */
+
+static bool
+graphite_stmt_p (scop_p scop, basic_block bb,
+ VEC (data_reference_p, heap) *drs)
+{
+ gimple_stmt_iterator gsi;
+ loop_p loop = bb->loop_father;
+
+ if (VEC_length (data_reference_p, drs) > 0)
+ return true;
+
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gimple stmt = gsi_stmt (gsi);
+
+ switch (gimple_code (stmt))
+ {
+ /* Control flow expressions can be ignored, as they are
+ represented in the iteration domains and will be
+ regenerated by graphite. */
+ case GIMPLE_COND:
+ case GIMPLE_GOTO:
+ case GIMPLE_SWITCH:
+ break;
+
+ case GIMPLE_ASSIGN:
+ {
+ tree var = gimple_assign_lhs (stmt);
+ var = analyze_scalar_evolution (loop, var);
+ var = instantiate_scev (block_before_scop (scop), loop, var);
+
+ if (chrec_contains_undetermined (var))
+ return true;
+
+ break;
+ }
+
+ default:
+ return true;
+ }
+ }
+
+ return false;
+}
+
+/* Store the GRAPHITE representation of BB. */
+
+static void
+new_graphite_bb (scop_p scop, basic_block bb)
+{
+ struct graphite_bb *gbb;
+ VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5);
+ struct loop *nest = outermost_loop_in_scop (scop, bb);
+ gimple_stmt_iterator gsi;
+
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ find_data_references_in_stmt (nest, gsi_stmt (gsi), &drs);
+
+ if (!graphite_stmt_p (scop, bb, drs))
+ {
+ free_data_refs (drs);
+ return;
+ }
+
+ gbb = XNEW (struct graphite_bb);
+ bb->aux = gbb;
+ GBB_BB (gbb) = bb;
+ GBB_SCOP (gbb) = scop;
+ GBB_DATA_REFS (gbb) = drs;
+ GBB_DOMAIN (gbb) = NULL;
+ 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);
+}
+
+/* Frees GBB. */
+
+static void
+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));
+ GBB_BB (gbb)->aux = 0;
+ XDELETE (gbb);
+}
+
+\f
+
+/* Structure containing the mapping between the old names and the new
+ names used after block copy in the new loop context. */
+typedef struct rename_map_elt
+{
+ tree old_name, new_name;
+} *rename_map_elt;
+
+
+/* Print to stderr the element ELT. */
+
+static void
+debug_rename_elt (rename_map_elt elt)
+{
+ fprintf (stderr, "(");
+ print_generic_expr (stderr, elt->old_name, 0);
+ fprintf (stderr, ", ");
+ print_generic_expr (stderr, elt->new_name, 0);
+ fprintf (stderr, ")\n");
+}
+
+/* Helper function for debug_rename_map. */
+
+static int
+debug_rename_map_1 (void **slot, void *s ATTRIBUTE_UNUSED)
+{
+ struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
+ debug_rename_elt (entry);
+ return 1;
+}
+
+/* Print to stderr all the elements of MAP. */
+
+void
+debug_rename_map (htab_t map)
+{
+ htab_traverse (map, debug_rename_map_1, NULL);
+}
+
+/* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
+
+static inline rename_map_elt
+new_rename_map_elt (tree old_name, tree new_name)
+{
+ rename_map_elt res;
+
+ res = XNEW (struct rename_map_elt);
+ res->old_name = old_name;
+ res->new_name = new_name;
+
+ return res;
+}
+
+/* Computes a hash function for database element ELT. */
+
+static hashval_t
+rename_map_elt_info (const void *elt)
+{
+ return htab_hash_pointer (((const struct rename_map_elt *) elt)->old_name);
+}
+
+/* Compares database elements E1 and E2. */
+
+static int
+eq_rename_map_elts (const void *e1, const void *e2)
+{
+ const struct rename_map_elt *elt1 = (const struct rename_map_elt *) e1;
+ const struct rename_map_elt *elt2 = (const struct rename_map_elt *) e2;
+
+ return (elt1->old_name == elt2->old_name);
+}
+
+/* Returns the new name associated to OLD_NAME in MAP. */
+
+static tree
+get_new_name_from_old_name (htab_t map, tree old_name)
+{
+ struct rename_map_elt tmp;
+ PTR *slot;
+
+ tmp.old_name = old_name;
+ slot = htab_find_slot (map, &tmp, NO_INSERT);
+
+ if (slot && *slot)
+ return ((rename_map_elt) *slot)->new_name;
+
+ return old_name;
+}
+
+\f
+
+/* Creates a new scop starting with ENTRY. */
+
+static scop_p
+new_scop (edge entry, edge exit)
+{
+ scop_p scop = XNEW (struct scop);
+
+ gcc_assert (entry && exit);
+
+ SCOP_REGION (scop) = new_sese (entry, exit);
+ SCOP_BBS (scop) = VEC_alloc (graphite_bb_p, heap, 3);
+ SCOP_OLDIVS (scop) = VEC_alloc (name_tree, heap, 3);
+ SCOP_LOOPS (scop) = BITMAP_ALLOC (NULL);
+ SCOP_LOOP_NEST (scop) = VEC_alloc (loop_p, heap, 3);
+ SCOP_ADD_PARAMS (scop) = true;
+ SCOP_PARAMS (scop) = VEC_alloc (name_tree, heap, 3);
+ SCOP_PROG (scop) = cloog_program_malloc ();
+ cloog_program_set_names (SCOP_PROG (scop), cloog_names_malloc ());
+ SCOP_LOOP2CLOOG_LOOP (scop) = htab_create (10, hash_loop_to_cloog_loop,
+ eq_loop_to_cloog_loop,
+ free);
+ SCOP_LIVEOUT_RENAMES (scop) = htab_create (10, rename_map_elt_info,
+ eq_rename_map_elts, free);
+ return scop;
+}
+
+/* Deletes SCOP. */
+
+static void
+free_scop (scop_p scop)
+{
+ int i;
+ name_tree p;
+ struct graphite_bb *gb;
+ name_tree iv;
+
+ for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
+ free_graphite_bb (gb);
+
+ VEC_free (graphite_bb_p, heap, SCOP_BBS (scop));
+ BITMAP_FREE (SCOP_LOOPS (scop));
+ VEC_free (loop_p, heap, SCOP_LOOP_NEST (scop));
+
+ for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, iv); i++)
+ free (iv);
+ VEC_free (name_tree, heap, SCOP_OLDIVS (scop));
+
+ for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++)
+ free (p);
+
+ VEC_free (name_tree, heap, SCOP_PARAMS (scop));
+ cloog_program_free (SCOP_PROG (scop));
+ htab_delete (SCOP_LOOP2CLOOG_LOOP (scop));
+ htab_delete (SCOP_LIVEOUT_RENAMES (scop));
+ free_sese (SCOP_REGION (scop));
+ XDELETE (scop);
+}
+
+/* Deletes all scops in SCOPS. */
+
+static void
+free_scops (VEC (scop_p, heap) *scops)
+{
+ int i;
+ scop_p scop;
+
+ for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
+ free_scop (scop);
+
+ VEC_free (scop_p, heap, scops);
+}
+
+typedef enum gbb_type {
+ GBB_UNKNOWN,
+ GBB_LOOP_SING_EXIT_HEADER,
+ GBB_LOOP_MULT_EXIT_HEADER,
+ GBB_LOOP_EXIT,
+ GBB_COND_HEADER,
+ GBB_SIMPLE,
+ GBB_LAST
+} gbb_type;
+
+/* Detect the type of BB. Loop headers are only marked, if they are
+ new. This means their loop_father is different to LAST_LOOP.
+ Otherwise they are treated like any other bb and their type can be
+ any other type. */
+
+static gbb_type
+get_bb_type (basic_block bb, struct loop *last_loop)
+{
+ VEC (basic_block, heap) *dom;
+ int nb_dom, nb_suc;
+ struct loop *loop = bb->loop_father;
+
+ /* Check, if we entry into a new loop. */
+ if (loop != last_loop)
+ {
+ if (single_exit (loop) != NULL)
+ return GBB_LOOP_SING_EXIT_HEADER;
+ else if (loop->num != 0)
+ return GBB_LOOP_MULT_EXIT_HEADER;
+ else
+ return GBB_COND_HEADER;
+ }
+
+ dom = get_dominated_by (CDI_DOMINATORS, bb);
+ nb_dom = VEC_length (basic_block, dom);
+ VEC_free (basic_block, heap, dom);
+
+ if (nb_dom == 0)
+ return GBB_LAST;
+
+ nb_suc = VEC_length (edge, bb->succs);
+
+ if (nb_dom == 1 && nb_suc == 1)
+ return GBB_SIMPLE;
+
+ return GBB_COND_HEADER;
+}
+
+/* A SCoP detection region, defined using bbs as borders.
+ All control flow touching this region, comes in passing basic_block ENTRY and
+ leaves passing basic_block EXIT. By using bbs instead of edges for the
+ borders we are able to represent also regions that do not have a single
+ entry or exit edge.
+ But as they have a single entry basic_block and a single exit basic_block, we
+ are able to generate for every sd_region a single entry and exit edge.
+
+ 1 2
+ \ /
+ 3 <- entry
+ |
+ 4
+ / \ This region contains: {3, 4, 5, 6, 7, 8}
+ 5 6
+ | |
+ 7 8
+ \ /
+ 9 <- exit */
+
+
+typedef struct sd_region_p
+{
+ /* The entry bb dominates all bbs in the sd_region. It is part of the
+ region. */
+ basic_block entry;
+
+ /* The exit bb postdominates all bbs in the sd_region, but is not
+ part of the region. */
+ basic_block exit;
+} sd_region;
+
+DEF_VEC_O(sd_region);
+DEF_VEC_ALLOC_O(sd_region, heap);
+
+
+/* Moves the scops from SOURCE to TARGET and clean up SOURCE. */
+
+static void
+move_sd_regions (VEC (sd_region, heap) **source, VEC (sd_region, heap) **target)
+{
+ sd_region *s;
+ int i;
+
+ for (i = 0; VEC_iterate (sd_region, *source, i, s); i++)
+ VEC_safe_push (sd_region, heap, *target, s);
+
+ VEC_free (sd_region, heap, *source);
+}
+
+/* Return true when it is not possible to represent the upper bound of
+ LOOP in the polyhedral representation. */
+
+static bool
+graphite_cannot_represent_loop_niter (loop_p loop)
+{
+ tree niter = number_of_latch_executions (loop);
+
+ return chrec_contains_undetermined (niter)
+ || !scev_is_linear_expression (niter);
+}
+/* Store information needed by scopdet_* functions. */
+
+struct scopdet_info
+{
+ /* Where the last open scop would stop if the current BB is harmful. */
+ basic_block last;
+
+ /* Where the next scop would start if the current BB is harmful. */
+ basic_block next;
+
+ /* The bb or one of its children contains open loop exits. That means
+ loop exit nodes that are not surrounded by a loop dominated by bb. */
+ bool exits;
+
+ /* The bb or one of its children contains only structures we can handle. */
+ bool difficult;
+};
+
+
+static struct scopdet_info build_scops_1 (basic_block, VEC (sd_region, heap) **,
+ loop_p);
+
+/* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB
+ to SCOPS. TYPE is the gbb_type of BB. */
+
+static struct scopdet_info
+scopdet_basic_block_info (basic_block bb, VEC (sd_region, heap) **scops,
+ gbb_type type)
+{
+ struct loop *loop = bb->loop_father;
+ struct scopdet_info result;
+ gimple stmt;
+
+ /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps. */
+ stmt = harmful_stmt_in_bb (ENTRY_BLOCK_PTR, bb);
+ result.difficult = (stmt != NULL);
+ result.last = NULL;
+
+ switch (type)
+ {
+ case GBB_LAST:
+ result.next = NULL;
+ result.exits = false;
+ result.last = bb;
+
+ /* Mark bbs terminating a SESE region difficult, if they start
+ a condition. */
+ if (VEC_length (edge, bb->succs) > 1)
+ result.difficult = true;
+
+ break;
+
+ case GBB_SIMPLE:
+ result.next = single_succ (bb);
+ result.exits = false;
+ result.last = bb;
+ break;
+
+ case GBB_LOOP_SING_EXIT_HEADER:
+ {
+ VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap,3);
+ struct scopdet_info sinfo;
+
+ sinfo = build_scops_1 (bb, &tmp_scops, loop);
+
+ result.last = single_exit (bb->loop_father)->src;
+ result.next = single_exit (bb->loop_father)->dest;
+
+ /* If we do not dominate result.next, remove it. It's either
+ the EXIT_BLOCK_PTR, or another bb dominates it and will
+ call the scop detection for this bb. */
+ if (!dominated_by_p (CDI_DOMINATORS, result.next, bb))
+ result.next = NULL;
+
+ if (result.last->loop_father != loop)
+ result.next = NULL;
+
+ if (graphite_cannot_represent_loop_niter (loop))
+ result.difficult = true;
+
+ if (sinfo.difficult)
+ move_sd_regions (&tmp_scops, scops);
+ else
+ VEC_free (sd_region, heap, tmp_scops);
+
+ result.exits = false;
+ result.difficult |= sinfo.difficult;
+ break;
+ }
+
+ case GBB_LOOP_MULT_EXIT_HEADER:
+ {
+ /* XXX: For now we just do not join loops with multiple exits. If the
+ exits lead to the same bb it may be possible to join the loop. */
+ VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
+ VEC (edge, heap) *exits = get_loop_exit_edges (loop);
+ edge e;
+ int i;
+ build_scops_1 (bb, &tmp_scops, loop);
+
+ /* Scan the code dominated by this loop. This means all bbs, that are
+ are dominated by a bb in this loop, but are not part of this loop.
+
+ The easiest case:
+ - The loop exit destination is dominated by the exit sources.
+
+ TODO: We miss here the more complex cases:
+ - The exit destinations are dominated by another bb inside the
+ loop.
+ - The loop dominates bbs, that are not exit destinations. */
+ for (i = 0; VEC_iterate (edge, exits, i, e); i++)
+ if (e->src->loop_father == loop
+ && dominated_by_p (CDI_DOMINATORS, e->dest, e->src))
+ {
+ /* Pass loop_outer to recognize e->dest as loop header in
+ build_scops_1. */
+ if (e->dest->loop_father->header == e->dest)
+ build_scops_1 (e->dest, &tmp_scops,
+ loop_outer (e->dest->loop_father));
+ else
+ build_scops_1 (e->dest, &tmp_scops, e->dest->loop_father);
+ }
+
+ result.next = NULL;
+ result.last = NULL;
+ result.difficult = true;
+ result.exits = false;
+ move_sd_regions (&tmp_scops, scops);
+ VEC_free (edge, heap, exits);
+ break;
+ }
+ case GBB_COND_HEADER:
+ {
+ VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
+ struct scopdet_info sinfo;
+ VEC (basic_block, heap) *dominated;
+ int i;
+ basic_block dom_bb;
+ basic_block last_bb = NULL;
+ edge e;
+ result.exits = false;
+
+ /* First check the successors of BB, and check if it is possible to join
+ the different branches. */
+ for (i = 0; VEC_iterate (edge, bb->succs, i, e); i++)
+ {
+ /* Ignore loop exits. They will be handled after the loop body. */
+ if (is_loop_exit (loop, e->dest))
+ {
+ result.exits = true;
+ continue;
+ }
+
+ /* Do not follow edges that lead to the end of the
+ conditions block. For example, in
+
+ | 0
+ | /|\
+ | 1 2 |
+ | | | |
+ | 3 4 |
+ | \|/
+ | 6
+
+ the edge from 0 => 6. Only check if all paths lead to
+ the same node 6. */
+
+ if (!single_pred_p (e->dest))
+ {
+ /* Check, if edge leads directly to the end of this
+ condition. */
+ if (!last_bb)
+ {
+ last_bb = e->dest;
+ }
+
+ if (e->dest != last_bb)
+ result.difficult = true;
+
+ continue;
+ }
+
+ if (!dominated_by_p (CDI_DOMINATORS, e->dest, bb))
+ {
+ result.difficult = true;
+ continue;
+ }
+
+ sinfo = build_scops_1 (e->dest, &tmp_scops, loop);
+
+ result.exits |= sinfo.exits;
+ result.last = sinfo.last;
+ result.difficult |= sinfo.difficult;
+
+ /* Checks, if all branches end at the same point.
+ If that is true, the condition stays joinable.
+ Have a look at the example above. */
+ if (sinfo.last && single_succ_p (sinfo.last))
+ {
+ basic_block next_tmp = single_succ (sinfo.last);
+
+ if (!last_bb)
+ last_bb = next_tmp;
+
+ if (next_tmp != last_bb)
+ result.difficult = true;
+ }
+ else
+ result.difficult = true;
+ }
+
+ /* If the condition is joinable. */
+ if (!result.exits && !result.difficult)
+ {
+ /* Only return a next pointer if we dominate this pointer.
+ Otherwise it will be handled by the bb dominating it. */
+ if (dominated_by_p (CDI_DOMINATORS, last_bb, bb) && last_bb != bb)
+ result.next = last_bb;
+ else
+ result.next = NULL;
+
+ VEC_free (sd_region, heap, tmp_scops);
+ break;
+ }
+
+ /* Scan remaining bbs dominated by BB. */
+ dominated = get_dominated_by (CDI_DOMINATORS, bb);
+
+ for (i = 0; VEC_iterate (basic_block, dominated, i, dom_bb); i++)
+ {
+ /* Ignore loop exits: they will be handled after the loop body. */
+ if (loop_depth (find_common_loop (loop, dom_bb->loop_father))
+ < loop_depth (loop))
+ {
+ result.exits = true;
+ continue;
+ }
+
+ /* Ignore the bbs processed above. */
+ if (single_pred_p (dom_bb) && single_pred (dom_bb) == bb)
+ continue;
+
+ if (loop_depth (loop) > loop_depth (dom_bb->loop_father))
+ sinfo = build_scops_1 (dom_bb, &tmp_scops, loop_outer (loop));
+ else
+ sinfo = build_scops_1 (dom_bb, &tmp_scops, loop);
+
+
+ result.exits |= sinfo.exits;
+ result.difficult = true;
+ result.last = NULL;
+ }
+
+ VEC_free (basic_block, heap, dominated);
+
+ result.next = NULL;
+ move_sd_regions (&tmp_scops, scops);
+
+ break;
+ }
+
+ default:
+ gcc_unreachable ();
+ }
+
+ return result;
+}
+
+/* Creates the SCoPs and writes entry and exit points for every SCoP. */
+
+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;
+
+ /* Initialize result. */
+ struct scopdet_info result;
+ result.exits = false;
+ result.difficult = false;
+ result.next = NULL;
+ result.last = NULL;
+ open_scop.entry = NULL;
+ open_scop.exit = NULL;
+ sinfo.last = NULL;
+
+ /* Loop over the dominance tree. If we meet a difficult bb, close
+ the current SCoP. Loop and condition header start a new layer,
+ and can only be added if all bbs in deeper layers are simple. */
+ while (current != NULL)
+ {
+ sinfo = scopdet_basic_block_info (current, scops, get_bb_type (current,
+ loop));
+
+ if (!in_scop && !(sinfo.exits || sinfo.difficult))
+ {
+ open_scop.entry = current;
+ open_scop.exit = NULL;
+ in_scop = true;
+ }
+ else if (in_scop && (sinfo.exits || sinfo.difficult))
+ {
+ open_scop.exit = current;
+ VEC_safe_push (sd_region, heap, *scops, &open_scop);
+ in_scop = false;
+ }
+
+ result.difficult |= sinfo.difficult;
+ result.exits |= sinfo.exits;
+
+ current = sinfo.next;
+ }
+
+ /* Try to close open_scop, if we are still in an open SCoP. */
+ if (in_scop)
+ {
+ int i;
+ edge e;
+
+ for (i = 0; VEC_iterate (edge, sinfo.last->succs, i, e); i++)
+ if (dominated_by_p (CDI_POST_DOMINATORS, sinfo.last, e->dest))
+ open_scop.exit = e->dest;
+
+ if (!open_scop.exit && open_scop.entry != sinfo.last)
+ open_scop.exit = sinfo.last;
+
+ if (open_scop.exit)
+ VEC_safe_push (sd_region, heap, *scops, &open_scop);
+
+ }
+
+ result.last = sinfo.last;
+ return result;
+}
+
+/* Checks if a bb is contained in REGION. */
+
+static bool
+bb_in_sd_region (basic_block bb, sd_region *region)
+{
+ return dominated_by_p (CDI_DOMINATORS, bb, region->entry)
+ && !(dominated_by_p (CDI_DOMINATORS, bb, region->exit)
+ && !dominated_by_p (CDI_DOMINATORS, region->entry,
+ region->exit));
+}
+
+/* Returns the single entry edge of REGION, if it does not exits NULL. */
+
+static edge
+find_single_entry_edge (sd_region *region)
+{
+ edge e;
+ edge_iterator ei;
+ edge entry = NULL;
+
+ FOR_EACH_EDGE (e, ei, region->entry->preds)
+ if (!bb_in_sd_region (e->src, region))
+ {
+ if (entry)
+ {
+ entry = NULL;
+ break;
+ }
+
+ else
+ entry = e;
+ }
+
+ return entry;
+}
+
+/* Returns the single exit edge of REGION, if it does not exits NULL. */
+
+static edge
+find_single_exit_edge (sd_region *region)
+{
+ edge e;
+ edge_iterator ei;
+ edge exit = NULL;
+
+ FOR_EACH_EDGE (e, ei, region->exit->preds)
+ if (bb_in_sd_region (e->src, region))
+ {
+ if (exit)
+ {
+ exit = NULL;
+ break;
+ }
+
+ else
+ exit = e;
+ }
+
+ return exit;
+}
+
+/* Create a single entry edge for REGION. */
+
+static void
+create_single_entry_edge (sd_region *region)
+{
+ if (find_single_entry_edge (region))
+ return;
+
+ /* There are multiple predecessors for bb_3
+
+ | 1 2
+ | | /
+ | |/
+ | 3 <- entry
+ | |\
+ | | |
+ | 4 ^
+ | | |
+ | |/
+ | 5
+
+ There are two edges (1->3, 2->3), that point from outside into the region,
+ and another one (5->3), a loop latch, lead to bb_3.
+
+ We split bb_3.
+
+ | 1 2
+ | | /
+ | |/
+ |3.0
+ | |\ (3.0 -> 3.1) = single entry edge
+ |3.1 | <- entry
+ | | |
+ | | |
+ | 4 ^
+ | | |
+ | |/
+ | 5
+
+ If the loop is part of the SCoP, we have to redirect the loop latches.
+
+ | 1 2
+ | | /
+ | |/
+ |3.0
+ | | (3.0 -> 3.1) = entry edge
+ |3.1 <- entry
+ | |\
+ | | |
+ | 4 ^
+ | | |
+ | |/
+ | 5 */
+
+ if (region->entry->loop_father->header != region->entry
+ || dominated_by_p (CDI_DOMINATORS,
+ loop_latch_edge (region->entry->loop_father)->src,
+ region->exit))
+ {
+ edge forwarder = split_block_after_labels (region->entry);
+ region->entry = forwarder->dest;
+ }
+ else
+ /* This case is never executed, as the loop headers seem always to have a
+ single edge pointing from outside into the loop. */
+ gcc_unreachable ();
+
+#ifdef ENABLE_CHECKING
+ gcc_assert (find_single_entry_edge (region));
+#endif
+}
+
+/* Check if the sd_region, mentioned in EDGE, has no exit bb. */
+
+static bool
+sd_region_without_exit (edge e)
+{
+ sd_region *r = (sd_region *) e->aux;
+
+ if (r)
+ return r->exit == NULL;
+ else
+ return false;
+}
+
+/* Create a single exit edge for REGION. */
+
+static void
+create_single_exit_edge (sd_region *region)
+{
+ edge e;
+ edge_iterator ei;
+ edge forwarder = NULL;
+ basic_block exit;
+
+ if (find_single_exit_edge (region))
+ return;
+
+ /* We create a forwarder bb (5) for all edges leaving this region
+ (3->5, 4->5). All other edges leading to the same bb, are moved
+ to a new bb (6). If these edges where part of another region (2->5)
+ we update the region->exit pointer, of this region.
+
+ To identify which edge belongs to which region we depend on the e->aux
+ pointer in every edge. It points to the region of the edge or to NULL,
+ if the edge is not part of any region.
+
+ 1 2 3 4 1->5 no region, 2->5 region->exit = 5,
+ \| |/ 3->5 region->exit = NULL, 4->5 region->exit = NULL
+ 5 <- exit
+
+ changes to
+
+ 1 2 3 4 1->6 no region, 2->6 region->exit = 6,
+ | | \/ 3->5 no region, 4->5 no region,
+ | | 5
+ \| / 5->6 region->exit = 6
+ 6
+
+ Now there is only a single exit edge (5->6). */
+ exit = region->exit;
+ region->exit = NULL;
+ forwarder = make_forwarder_block (exit, &sd_region_without_exit, NULL);
+
+ /* Unmark the edges, that are no longer exit edges. */
+ FOR_EACH_EDGE (e, ei, forwarder->src->preds)
+ if (e->aux)
+ e->aux = NULL;
+
+ /* Mark the new exit edge. */
+ single_succ_edge (forwarder->src)->aux = region;
+
+ /* Update the exit bb of all regions, where exit edges lead to
+ forwarder->dest. */
+ FOR_EACH_EDGE (e, ei, forwarder->dest->preds)
+ if (e->aux)
+ ((sd_region *) e->aux)->exit = forwarder->dest;
+
+#ifdef ENABLE_CHECKING
+ gcc_assert (find_single_exit_edge (region));
+#endif
+}
+
+/* Unmark the exit edges of all REGIONS.
+ See comment in "create_single_exit_edge". */
+
+static void
+unmark_exit_edges (VEC (sd_region, heap) *regions)
+{
+ int i;
+ sd_region *s;
+ edge e;
+ edge_iterator ei;
+
+ for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
+ FOR_EACH_EDGE (e, ei, s->exit->preds)
+ e->aux = NULL;
+}
+
+
+/* Mark the exit edges of all REGIONS.
+ See comment in "create_single_exit_edge". */
+
+static void
+mark_exit_edges (VEC (sd_region, heap) *regions)
+{
+ int i;
+ sd_region *s;
+ edge e;
+ edge_iterator ei;
+
+ for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
+ FOR_EACH_EDGE (e, ei, s->exit->preds)
+ if (bb_in_sd_region (e->src, s))
+ e->aux = s;
+}
+
+/* Free and compute again all the dominators information. */
+
+static inline void
+recompute_all_dominators (void)
+{
+ mark_irreducible_loops ();
+ free_dominance_info (CDI_DOMINATORS);
+ free_dominance_info (CDI_POST_DOMINATORS);
+ calculate_dominance_info (CDI_DOMINATORS);
+ calculate_dominance_info (CDI_POST_DOMINATORS);
+}
+
+/* Verifies properties that GRAPHITE should maintain during translation. */
+
+static inline void
+graphite_verify (void)
+{
+#ifdef ENABLE_CHECKING
+ verify_loop_structure ();
+ verify_dominators (CDI_DOMINATORS);
+ verify_dominators (CDI_POST_DOMINATORS);
+ verify_ssa (false);
+ verify_loop_closed_ssa ();
+#endif
+}
+
+/* Create for all scop regions a single entry and a single exit edge. */
+
+static void
+create_sese_edges (VEC (sd_region, heap) *regions)
+{
+ int i;
+ sd_region *s;
+
+ for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
+ create_single_entry_edge (s);
+
+ mark_exit_edges (regions);
+
+ for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
+ create_single_exit_edge (s);
+
+ unmark_exit_edges (regions);
+
+ fix_loop_structure (NULL);
+
+#ifdef ENABLE_CHECKING
+ verify_loop_structure ();
+ verify_dominators (CDI_DOMINATORS);
+ verify_ssa (false);
+#endif
+}
+
+/* Create graphite SCoPs from an array of scop detection regions. */
+
+static void
+build_graphite_scops (VEC (sd_region, heap) *scop_regions)
+{
+ int i;
+ sd_region *s;
+
+ for (i = 0; VEC_iterate (sd_region, scop_regions, i, s); i++)
+ {
+ edge entry = find_single_entry_edge (s);
+ edge exit = find_single_exit_edge (s);
+ scop_p scop = new_scop (entry, exit);
+ VEC_safe_push (scop_p, heap, current_scops, scop);
+
+ /* Are there overlapping SCoPs? */
+#ifdef ENABLE_CHECKING
+ {
+ int j;
+ sd_region *s2;
+
+ for (j = 0; VEC_iterate (sd_region, scop_regions, j, s2); j++)
+ if (s != s2)
+ gcc_assert (!bb_in_sd_region (s->entry, s2));
+ }
+#endif
+ }
+}
+
+/* Find static control parts. */
+
+static void
+build_scops (void)
+{
+ struct loop *loop = current_loops->tree_root;
+ VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
+
+ build_scops_1 (single_succ (ENTRY_BLOCK_PTR), &tmp_scops, loop);
+ create_sese_edges (tmp_scops);
+ build_graphite_scops (tmp_scops);
+ VEC_free (sd_region, heap, tmp_scops);
+}
+
+/* Gather the basic blocks belonging to the SCOP. */
+
+static void
+build_scop_bbs (scop_p scop)
+{
+ basic_block *stack = XNEWVEC (basic_block, n_basic_blocks + 1);
+ sbitmap visited = sbitmap_alloc (last_basic_block);
+ int sp = 0;
+
+ sbitmap_zero (visited);
+ stack[sp++] = SCOP_ENTRY (scop);
+
+ while (sp)
+ {
+ basic_block bb = stack[--sp];
+ int depth = loop_depth (bb->loop_father);
+ int num = bb->loop_father->num;
+ edge_iterator ei;
+ edge e;
+
+ /* Scop's exit is not in the scop. Exclude also bbs, which are
+ dominated by the SCoP exit. These are e.g. loop latches. */
+ if (TEST_BIT (visited, bb->index)
+ || dominated_by_p (CDI_DOMINATORS, bb, SCOP_EXIT (scop))
+ /* Every block in the scop is dominated by scop's entry. */
+ || !dominated_by_p (CDI_DOMINATORS, bb, SCOP_ENTRY (scop)))
+ continue;
+
+ new_graphite_bb (scop, bb);
+ SET_BIT (visited, bb->index);
+
+ /* First push the blocks that have to be processed last. Note
+ that this means that the order in which the code is organized
+ below is important: do not reorder the following code. */
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (! TEST_BIT (visited, e->dest->index)
+ && (int) loop_depth (e->dest->loop_father) < depth)
+ stack[sp++] = e->dest;
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (! TEST_BIT (visited, e->dest->index)
+ && (int) loop_depth (e->dest->loop_father) == depth
+ && e->dest->loop_father->num != num)
+ stack[sp++] = e->dest;
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (! TEST_BIT (visited, e->dest->index)
+ && (int) loop_depth (e->dest->loop_father) == depth
+ && e->dest->loop_father->num == num
+ && EDGE_COUNT (e->dest->preds) > 1)
+ stack[sp++] = e->dest;
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (! TEST_BIT (visited, e->dest->index)
+ && (int) loop_depth (e->dest->loop_father) == depth
+ && e->dest->loop_father->num == num
+ && EDGE_COUNT (e->dest->preds) == 1)
+ stack[sp++] = e->dest;
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (! TEST_BIT (visited, e->dest->index)
+ && (int) loop_depth (e->dest->loop_father) > depth)
+ stack[sp++] = e->dest;
+ }
+
+ free (stack);
+ sbitmap_free (visited);
+}
+
+/* Returns the number of reduction phi nodes in LOOP. */
+
+static int
+nb_reductions_in_loop (loop_p loop)
+{
+ int res = 0;
+ gimple_stmt_iterator gsi;
+
+ for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gimple phi = gsi_stmt (gsi);
+ tree scev;
+ affine_iv iv;
+
+ if (!is_gimple_reg (PHI_RESULT (phi)))
+ continue;
+
+ scev = analyze_scalar_evolution (loop, PHI_RESULT (phi));
+ scev = instantiate_parameters (loop, scev);
+ if (!simple_iv (loop, loop, PHI_RESULT (phi), &iv, true))
+ res++;
+ }
+
+ return res;
+}
+
+/* A LOOP is in normal form when it contains only one scalar phi node
+ that defines the main induction variable of the loop, only one
+ increment of the IV, and only one exit condition. */
+
+static tree
+graphite_loop_normal_form (loop_p loop)
+{
+ struct tree_niter_desc niter;
+ tree nit;
+ gimple_seq stmts;
+ edge exit = single_dom_exit (loop);
+ bool known_niter = number_of_iterations_exit (loop, exit, &niter, false);
+
+ gcc_assert (known_niter);
+
+ nit = force_gimple_operand (unshare_expr (niter.niter), &stmts, true,
+ NULL_TREE);
+ if (stmts)
+ gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
+
+ /* One IV per loop. */
+ if (nb_reductions_in_loop (loop) > 0)
+ return NULL_TREE;
+
+ return canonicalize_loop_ivs (loop, NULL, &nit);
+}
+
+/* Record LOOP as occuring in SCOP. Returns true when the operation
+ was successful. */
+
+static bool
+scop_record_loop (scop_p scop, loop_p loop)
+{
+ tree induction_var;
+ name_tree oldiv;
+
+ if (bitmap_bit_p (SCOP_LOOPS (scop), loop->num))
+ return true;
+
+ bitmap_set_bit (SCOP_LOOPS (scop), loop->num);
+ VEC_safe_push (loop_p, heap, SCOP_LOOP_NEST (scop), loop);
+
+ induction_var = graphite_loop_normal_form (loop);
+ if (!induction_var)
+ return false;
+
+ oldiv = XNEW (struct name_tree);
+ oldiv->t = induction_var;
+ oldiv->name = get_name (SSA_NAME_VAR (oldiv->t));
+ oldiv->loop = loop;
+ VEC_safe_push (name_tree, heap, SCOP_OLDIVS (scop), oldiv);
+ return true;
+}
+
+/* Build the loop nests contained in SCOP. Returns true when the
+ operation was successful. */
+
+static bool
+build_scop_loop_nests (scop_p scop)
+{
+ unsigned i;
+ basic_block bb;
+ struct loop *loop0, *loop1;
+
+ FOR_EACH_BB (bb)
+ if (bb_in_sese_p (bb, SCOP_REGION (scop)))
+ {
+ struct loop *loop = bb->loop_father;
+
+ /* Only add loops if they are completely contained in the SCoP. */
+ if (loop->header == bb
+ && bb_in_sese_p (loop->latch, SCOP_REGION (scop)))
+ {
+ if (!scop_record_loop (scop, loop))
+ return false;
+ }
+ }
+
+ /* Make sure that the loops in the SCOP_LOOP_NEST are ordered. It
+ can be the case that an inner loop is inserted before an outer
+ loop. To avoid this, semi-sort once. */
+ for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop0); i++)
+ {
+ if (VEC_length (loop_p, SCOP_LOOP_NEST (scop)) == i + 1)
+ break;
+
+ loop1 = VEC_index (loop_p, SCOP_LOOP_NEST (scop), i + 1);
+ if (loop0->num > loop1->num)
+ {
+ VEC_replace (loop_p, SCOP_LOOP_NEST (scop), i, loop1);
+ VEC_replace (loop_p, SCOP_LOOP_NEST (scop), i + 1, loop0);
+ }
+ }
+
+ return true;
+}
+
+/* Calculate the number of loops around LOOP in the SCOP. */
+
+static inline int
+nb_loops_around_loop_in_scop (struct loop *l, scop_p scop)
+{
+ int d = 0;
+
+ for (; loop_in_sese_p (l, SCOP_REGION (scop)); d++, l = loop_outer (l));
+
+ return d;
+}
+
+/* Calculate the number of loops around GB in the current SCOP. */
+
+int
+nb_loops_around_gb (graphite_bb_p gb)
+{
+ return nb_loops_around_loop_in_scop (gbb_loop (gb), GBB_SCOP (gb));
+}
+
+/* Returns the dimensionality of an enclosing loop iteration domain
+ with respect to enclosing SCoP for a given data reference REF. The
+ returned dimensionality is homogeneous (depth of loop nest + number
+ of SCoP parameters + const). */
+
+int
+ref_nb_loops (data_reference_p ref)
+{
+ loop_p loop = loop_containing_stmt (DR_STMT (ref));
+ scop_p scop = DR_SCOP (ref);
+
+ return nb_loops_around_loop_in_scop (loop, scop) + scop_nb_params (scop) + 2;
+}
+
+/* Build dynamic schedules for all the BBs. */
+
+static void
+build_scop_dynamic_schedules (scop_p scop)
+{
+ int i, dim, loop_num, row, col;
+ graphite_bb_p gb;
+
+ for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
+ {
+ loop_num = GBB_BB (gb)->loop_father->num;
+
+ if (loop_num != 0)
+ {
+ dim = nb_loops_around_gb (gb);
+ GBB_DYNAMIC_SCHEDULE (gb) = cloog_matrix_alloc (dim, dim);
+
+ for (row = 0; row < GBB_DYNAMIC_SCHEDULE (gb)->NbRows; row++)
+ for (col = 0; col < GBB_DYNAMIC_SCHEDULE (gb)->NbColumns; col++)
+ if (row == col)
+ value_set_si (GBB_DYNAMIC_SCHEDULE (gb)->p[row][col], 1);
+ else
+ value_set_si (GBB_DYNAMIC_SCHEDULE (gb)->p[row][col], 0);
+ }
+ else
+ GBB_DYNAMIC_SCHEDULE (gb) = NULL;
+ }
+}
+
+/* Returns the number of loops that are identical at the beginning of
+ the vectors A and B. */
+
+static int
+compare_prefix_loops (VEC (loop_p, heap) *a, VEC (loop_p, heap) *b)
+{
+ int i;
+ loop_p ea;
+ int lb;
+
+ if (!a || !b)
+ return 0;
+
+ lb = VEC_length (loop_p, b);
+
+ for (i = 0; VEC_iterate (loop_p, a, i, ea); i++)
+ if (i >= lb
+ || ea != VEC_index (loop_p, b, i))
+ return i;
+
+ return 0;
+}
+
+/* Build for BB the static schedule.
+
+ The STATIC_SCHEDULE is defined like this:
+
+ A
+ for (i: ...)
+ {
+ for (j: ...)
+ {
+ B
+ C
+ }
+
+ for (k: ...)
+ {
+ D
+ E
+ }
+ }
+ F
+
+ Static schedules for A to F:
+
+ DEPTH
+ 0 1 2
+ A 0
+ B 1 0 0
+ C 1 0 1
+ D 1 1 0
+ E 1 1 1
+ F 2
+*/
+
+static void
+build_scop_canonical_schedules (scop_p scop)
+{
+ int i;
+ graphite_bb_p gb;
+ int nb_loops = scop_nb_loops (scop);
+ lambda_vector static_schedule = lambda_vector_new (nb_loops + 1);
+ VEC (loop_p, heap) *loops_previous = NULL;
+
+ /* We have to start schedules at 0 on the first component and
+ because we cannot compare_prefix_loops against a previous loop,
+ prefix will be equal to zero, and that index will be
+ incremented before copying. */
+ static_schedule[0] = -1;
+
+ for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
+ {
+ int prefix = compare_prefix_loops (loops_previous, GBB_LOOPS (gb));
+ int nb = gbb_nb_loops (gb);
+
+ loops_previous = GBB_LOOPS (gb);
+ memset (&(static_schedule[prefix + 1]), 0, sizeof (int) * (nb_loops - prefix));
+ ++static_schedule[prefix];
+ GBB_STATIC_SCHEDULE (gb) = lambda_vector_new (nb + 1);
+ lambda_vector_copy (static_schedule,
+ GBB_STATIC_SCHEDULE (gb), nb + 1);
+ }
+}
+
+/* Build the LOOPS vector for all bbs in SCOP. */
+
+static void
+build_bb_loops (scop_p scop)
+{
+ graphite_bb_p gb;
+ int i;
+
+ for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
+ {
+ loop_p loop;
+ int depth;
+
+ depth = nb_loops_around_gb (gb) - 1;
+
+ GBB_LOOPS (gb) = VEC_alloc (loop_p, heap, 3);
+ VEC_safe_grow_cleared (loop_p, heap, GBB_LOOPS (gb), depth + 1);
+
+ loop = GBB_BB (gb)->loop_father;
+
+ while (scop_contains_loop (scop, loop))
+ {
+ VEC_replace (loop_p, GBB_LOOPS (gb), depth, loop);
+ loop = loop_outer (loop);
+ depth--;
+ }
+ }
+}
+
+/* Get the index for parameter VAR in SCOP. */
+
+static int
+param_index (tree var, scop_p scop)
+{
+ int i;
+ name_tree p;
+ name_tree nvar;
+
+ gcc_assert (TREE_CODE (var) == SSA_NAME);
+
+ for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++)
+ if (p->t == var)
+ return i;
+
+ gcc_assert (SCOP_ADD_PARAMS (scop));
+
+ nvar = XNEW (struct name_tree);
+ nvar->t = var;
+ nvar->name = NULL;
+ VEC_safe_push (name_tree, heap, SCOP_PARAMS (scop), nvar);
+ return VEC_length (name_tree, SCOP_PARAMS (scop)) - 1;
+}
+
+/* Scan EXPR and translate it to an inequality vector INEQ that will
+ be added, or subtracted, in the constraint domain matrix C at row
+ R. K is the number of columns for loop iterators in C. */
+
+static void
+scan_tree_for_params (scop_p s, tree e, CloogMatrix *c, int r, Value k,
+ bool subtract)
+{
+ int cst_col, param_col;
+
+ if (e == chrec_dont_know)
+ return;
+
+ switch (TREE_CODE (e))
+ {
+ case POLYNOMIAL_CHREC:
+ {
+ tree left = CHREC_LEFT (e);
+ tree right = CHREC_RIGHT (e);
+ int var = CHREC_VARIABLE (e);
+
+ if (TREE_CODE (right) != INTEGER_CST)
+ return;
+
+ if (c)
+ {
+ int loop_col = scop_gimple_loop_depth (s, get_loop (var)) + 1;
+
+ if (subtract)
+ value_sub_int (c->p[r][loop_col], c->p[r][loop_col],
+ int_cst_value (right));
+ else
+ value_add_int (c->p[r][loop_col], c->p[r][loop_col],
+ int_cst_value (right));
+ }
+
+ switch (TREE_CODE (left))
+ {
+ case POLYNOMIAL_CHREC:
+ scan_tree_for_params (s, left, c, r, k, subtract);
+ return;
+
+ case INTEGER_CST:
+ /* Constant part. */
+ if (c)
+ {
+ int v = int_cst_value (left);
+ cst_col = c->NbColumns - 1;
+
+ if (v < 0)
+ {
+ v = -v;
+ subtract = subtract ? false : true;
+ }
+
+ if (subtract)
+ value_sub_int (c->p[r][cst_col], c->p[r][cst_col], v);
+ else
+ value_add_int (c->p[r][cst_col], c->p[r][cst_col], v);
+ }
+ return;
+
+ default:
+ scan_tree_for_params (s, left, c, r, k, subtract);
+ return;
+ }
+ }
+ break;
+
+ case MULT_EXPR:
+ if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
+ {
+ if (c)
+ {
+ Value val;
+ gcc_assert (host_integerp (TREE_OPERAND (e, 1), 0));
+ value_init (val);
+ value_set_si (val, int_cst_value (TREE_OPERAND (e, 1)));
+ value_multiply (k, k, val);
+ value_clear (val);
+ }
+ scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
+ }
+ else
+ {
+ if (c)
+ {
+ Value val;
+ gcc_assert (host_integerp (TREE_OPERAND (e, 0), 0));
+ value_init (val);
+ value_set_si (val, int_cst_value (TREE_OPERAND (e, 0)));
+ value_multiply (k, k, val);
+ value_clear (val);
+ }
+ scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, subtract);
+ }
+ break;
+
+ case PLUS_EXPR:
+ case POINTER_PLUS_EXPR:
+ scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
+ scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, subtract);
+ break;
+
+ case MINUS_EXPR:
+ scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
+ scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, !subtract);
+ break;
+
+ case NEGATE_EXPR:
+ scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, !subtract);
+ break;
+
+ case SSA_NAME:
+ param_col = param_index (e, s);
+
+ if (c)
+ {
+ param_col += c->NbColumns - scop_nb_params (s) - 1;
+
+ if (subtract)
+ value_subtract (c->p[r][param_col], c->p[r][param_col], k);
+ else
+ value_addto (c->p[r][param_col], c->p[r][param_col], k);
+ }
+ break;
+
+ case INTEGER_CST:
+ if (c)
+ {
+ int v = int_cst_value (e);
+ cst_col = c->NbColumns - 1;
+
+ if (v < 0)
+ {
+ v = -v;
+ subtract = subtract ? false : true;
+ }
+
+ if (subtract)
+ value_sub_int (c->p[r][cst_col], c->p[r][cst_col], v);
+ else
+ value_add_int (c->p[r][cst_col], c->p[r][cst_col], v);
+ }
+ break;
+
+ CASE_CONVERT:
+ case NON_LVALUE_EXPR:
+ scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
+ break;
+
+ default:
+ gcc_unreachable ();
+ break;
+ }
+}
+
+/* Data structure for idx_record_params. */
+
+struct irp_data
+{
+ struct loop *loop;
+ scop_p scop;
+};
+
+/* For a data reference with an ARRAY_REF as its BASE, record the
+ parameters occurring in IDX. DTA is passed in as complementary
+ information, and is used by the automatic walker function. This
+ function is a callback for for_each_index. */
+
+static bool
+idx_record_params (tree base, tree *idx, void *dta)
+{
+ struct irp_data *data = (struct irp_data *) dta;
+
+ if (TREE_CODE (base) != ARRAY_REF)
+ return true;
+
+ if (TREE_CODE (*idx) == SSA_NAME)
+ {
+ tree scev;
+ scop_p scop = data->scop;
+ struct loop *loop = data->loop;
+ Value one;
+
+ scev = analyze_scalar_evolution (loop, *idx);
+ scev = instantiate_scev (block_before_scop (scop), loop, scev);
+
+ value_init (one);
+ value_set_si (one, 1);
+ scan_tree_for_params (scop, scev, NULL, 0, one, false);
+ value_clear (one);
+ }
+
+ return true;
+}
+
+/* Find parameters with respect to SCOP in BB. We are looking in memory
+ access functions, conditions and loop bounds. */
+
+static void
+find_params_in_bb (scop_p scop, graphite_bb_p gb)
+{
+ int i;
+ data_reference_p dr;
+ gimple stmt;
+ loop_p father = GBB_BB (gb)->loop_father;
+
+ for (i = 0; VEC_iterate (data_reference_p, GBB_DATA_REFS (gb), i, dr); i++)
+ {
+ struct irp_data irp;
+
+ irp.loop = father;
+ irp.scop = scop;
+ for_each_index (&dr->ref, idx_record_params, &irp);
+ }
+
+ /* Find parameters in conditional statements. */
+ for (i = 0; VEC_iterate (gimple, GBB_CONDITIONS (gb), i, stmt); i++)
+ {
+ Value one;
+ loop_p loop = father;
+
+ tree lhs, rhs;
+
+ lhs = gimple_cond_lhs (stmt);
+ lhs = analyze_scalar_evolution (loop, lhs);
+ lhs = instantiate_scev (block_before_scop (scop), loop, lhs);
+
+ rhs = gimple_cond_rhs (stmt);
+ rhs = analyze_scalar_evolution (loop, rhs);
+ rhs = instantiate_scev (block_before_scop (scop), loop, rhs);
+
+ value_init (one);
+ scan_tree_for_params (scop, lhs, NULL, 0, one, false);
+ value_set_si (one, 1);
+ scan_tree_for_params (scop, rhs, NULL, 0, one, false);
+ value_clear (one);
+ }
+}
+
+/* Saves in NV the name of variable P->T. */
+
+static void
+save_var_name (char **nv, int i, name_tree p)
+{
+ const char *name = get_name (SSA_NAME_VAR (p->t));
+
+ if (name)
+ {
+ int len = strlen (name) + 16;
+ nv[i] = XNEWVEC (char, len);
+ snprintf (nv[i], len, "%s_%d", name, SSA_NAME_VERSION (p->t));
+ }
+ else
+ {
+ nv[i] = XNEWVEC (char, 16);
+ snprintf (nv[i], 2 + 16, "T_%d", SSA_NAME_VERSION (p->t));
+ }
+
+ p->name = nv[i];
+}
+
+/* Return the maximal loop depth in SCOP. */
+
+static int
+scop_max_loop_depth (scop_p scop)
+{
+ int i;
+ graphite_bb_p gbb;
+ int max_nb_loops = 0;
+
+ for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
+ {
+ int nb_loops = gbb_nb_loops (gbb);
+ if (max_nb_loops < nb_loops)
+ max_nb_loops = nb_loops;
+ }
+
+ return max_nb_loops;
+}
+
+/* Initialize Cloog's parameter names from the names used in GIMPLE.
+ Initialize Cloog's iterator names, using 'graphite_iterator_%d'
+ from 0 to scop_nb_loops (scop). */
+
+static void
+initialize_cloog_names (scop_p scop)
+{
+ int i, nb_params = VEC_length (name_tree, SCOP_PARAMS (scop));
+ char **params = XNEWVEC (char *, nb_params);
+ int nb_iterators = scop_max_loop_depth (scop);
+ int nb_scattering= cloog_program_nb_scattdims (SCOP_PROG (scop));
+ char **iterators = XNEWVEC (char *, nb_iterators * 2);
+ char **scattering = XNEWVEC (char *, nb_scattering);
+ name_tree p;
+
+ for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++)
+ save_var_name (params, i, p);
+
+ cloog_names_set_nb_parameters (cloog_program_names (SCOP_PROG (scop)),
+ nb_params);
+ cloog_names_set_parameters (cloog_program_names (SCOP_PROG (scop)),
+ params);
+
+ for (i = 0; i < nb_iterators; i++)
+ {
+ int len = 18 + 16;
+ iterators[i] = XNEWVEC (char, len);
+ snprintf (iterators[i], len, "graphite_iterator_%d", i);
+ }
+
+ cloog_names_set_nb_iterators (cloog_program_names (SCOP_PROG (scop)),
+ nb_iterators);
+ cloog_names_set_iterators (cloog_program_names (SCOP_PROG (scop)),
+ iterators);
+
+ for (i = 0; i < nb_scattering; i++)
+ {
+ int len = 2 + 16;
+ scattering[i] = XNEWVEC (char, len);
+ snprintf (scattering[i], len, "s_%d", i);
+ }
+
+ cloog_names_set_nb_scattering (cloog_program_names (SCOP_PROG (scop)),
+ nb_scattering);
+ cloog_names_set_scattering (cloog_program_names (SCOP_PROG (scop)),
+ scattering);
+}
+
+/* Record the parameters used in the SCOP. A variable is a parameter
+ in a scop if it does not vary during the execution of that scop. */
+
+static void
+find_scop_parameters (scop_p scop)
+{
+ graphite_bb_p gb;
+ unsigned i;
+ struct loop *loop;
+ Value one;
+
+ value_init (one);
+ value_set_si (one, 1);
+
+ /* Find the parameters used in the loop bounds. */
+ for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop); i++)
+ {
+ tree nb_iters = number_of_latch_executions (loop);
+
+ if (!chrec_contains_symbols (nb_iters))
+ continue;
+
+ nb_iters = analyze_scalar_evolution (loop, nb_iters);
+ nb_iters = instantiate_scev (block_before_scop (scop), loop, nb_iters);
+ scan_tree_for_params (scop, nb_iters, NULL, 0, one, false);
+ }
+
+ value_clear (one);
+
+ /* Find the parameters used in data accesses. */
+ for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
+ find_params_in_bb (scop, gb);
+
+ SCOP_ADD_PARAMS (scop) = false;
+}
+
+/* Build the context constraints for SCOP: constraints and relations
+ on parameters. */
+
+static void
+build_scop_context (scop_p scop)
+{
+ int nb_params = scop_nb_params (scop);
+ CloogMatrix *matrix = cloog_matrix_alloc (1, nb_params + 2);
+
+ /* Insert '0 >= 0' in the context matrix, as it is not allowed to be
+ empty. */
+
+ value_set_si (matrix->p[0][0], 1);
+
+ value_set_si (matrix->p[0][nb_params + 1], 0);
+
+ cloog_program_set_context (SCOP_PROG (scop),
+ cloog_domain_matrix2domain (matrix));
+ cloog_matrix_free (matrix);
+}
+
+/* Returns a graphite_bb from BB. */
+
+static inline graphite_bb_p
+gbb_from_bb (basic_block bb)
+{
+ return (graphite_bb_p) bb->aux;
+}
+
+/* Builds the constraint matrix for LOOP in SCOP. NB_OUTER_LOOPS is the
+ number of loops surrounding LOOP in SCOP. OUTER_CSTR gives the
+ constraints matrix for the surrounding loops. */
+
+static void
+build_loop_iteration_domains (scop_p scop, struct loop *loop,
+ CloogMatrix *outer_cstr, int nb_outer_loops)
+{
+ int i, j, row;
+ CloogMatrix *cstr;
+ graphite_bb_p gb;
+
+ int nb_rows = outer_cstr->NbRows + 1;
+ int nb_cols = outer_cstr->NbColumns + 1;
+
+ /* Last column of CSTR is the column of constants. */
+ int cst_col = nb_cols - 1;
+
+ /* The column for the current loop is just after the columns of
+ other outer loops. */
+ int loop_col = nb_outer_loops + 1;
+
+ tree nb_iters = number_of_latch_executions (loop);
+
+ /* When the number of iterations is a constant or a parameter, we
+ add a constraint for the upper bound of the loop. So add a row
+ to the constraint matrix before allocating it. */
+ if (TREE_CODE (nb_iters) == INTEGER_CST
+ || !chrec_contains_undetermined (nb_iters))
+ nb_rows++;
+
+ cstr = cloog_matrix_alloc (nb_rows, nb_cols);
+
+ /* Copy the outer constraints. */
+ for (i = 0; i < outer_cstr->NbRows; i++)
+ {
+ /* Copy the eq/ineq and loops columns. */
+ for (j = 0; j < loop_col; j++)
+ value_assign (cstr->p[i][j], outer_cstr->p[i][j]);
+
+ /* Leave an empty column in CSTR for the current loop, and then
+ copy the parameter columns. */
+ for (j = loop_col; j < outer_cstr->NbColumns; j++)
+ value_assign (cstr->p[i][j + 1], outer_cstr->p[i][j]);
+ }
+
+ /* 0 <= loop_i */
+ row = outer_cstr->NbRows;
+ value_set_si (cstr->p[row][0], 1);
+ value_set_si (cstr->p[row][loop_col], 1);
+
+ /* loop_i <= nb_iters */
+ if (TREE_CODE (nb_iters) == INTEGER_CST)
+ {
+ row++;
+ value_set_si (cstr->p[row][0], 1);
+ value_set_si (cstr->p[row][loop_col], -1);
+
+ value_set_si (cstr->p[row][cst_col],
+ int_cst_value (nb_iters));
+ }
+ else if (!chrec_contains_undetermined (nb_iters))
+ {
+ /* Otherwise nb_iters contains parameters: scan the nb_iters
+ expression and build its matrix representation. */
+ Value one;
+
+ row++;
+ value_set_si (cstr->p[row][0], 1);
+ value_set_si (cstr->p[row][loop_col], -1);
+
+ nb_iters = analyze_scalar_evolution (loop, nb_iters);
+ nb_iters = instantiate_scev (block_before_scop (scop), loop, nb_iters);
+
+ value_init (one);
+ value_set_si (one, 1);
+ scan_tree_for_params (scop, nb_iters, cstr, row, one, false);
+ value_clear (one);
+ }
+ else
+ gcc_unreachable ();
+
+ if (loop->inner && loop_in_sese_p (loop->inner, SCOP_REGION (scop)))
+ build_loop_iteration_domains (scop, loop->inner, cstr, nb_outer_loops + 1);
+
+ /* Only go to the next loops, if we are not at the outermost layer. These
+ have to be handled seperately, as we can be sure, that the chain at this
+ layer will be connected. */
+ if (nb_outer_loops != 0 && loop->next && loop_in_sese_p (loop->next,
+ SCOP_REGION (scop)))
+ build_loop_iteration_domains (scop, loop->next, outer_cstr, nb_outer_loops);
+
+ for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
+ if (gbb_loop (gb) == loop)
+ GBB_DOMAIN (gb) = cloog_matrix_copy (cstr);
+
+ cloog_matrix_free (cstr);
+}
+
+/* Add conditions to the domain of GB. */
+
+static void
+add_conditions_to_domain (graphite_bb_p gb)
+{
+ unsigned int i,j;
+ gimple stmt;
+ VEC (gimple, heap) *conditions = GBB_CONDITIONS (gb);
+ CloogMatrix *domain = GBB_DOMAIN (gb);
+ scop_p scop = GBB_SCOP (gb);
+
+ unsigned nb_rows;
+ unsigned nb_cols;
+ unsigned nb_new_rows = 0;
+ unsigned row;
+
+ if (VEC_empty (gimple, conditions))
+ return;
+
+ if (domain)
+ {
+ nb_rows = domain->NbRows;
+ nb_cols = domain->NbColumns;
+ }
+ else
+ {
+ nb_rows = 0;
+ nb_cols = nb_loops_around_gb (gb) + scop_nb_params (scop) + 2;
+ }
+
+ /* Count number of necessary new rows to add the conditions to the
+ domain. */
+ for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
+ {
+ switch (gimple_code (stmt))
+ {
+ case GIMPLE_COND:
+ {
+ enum tree_code code = gimple_cond_code (stmt);
+
+ switch (code)
+ {
+ case NE_EXPR:
+ case EQ_EXPR:
+ /* NE and EQ statements are not supported right know. */
+ gcc_unreachable ();
+ break;
+ case LT_EXPR:
+ case GT_EXPR:
+ case LE_EXPR:
+ case GE_EXPR:
+ nb_new_rows++;
+ break;
+ default:
+ gcc_unreachable ();
+ break;
+ }
+ break;
+ }
+ case SWITCH_EXPR:
+ /* Switch statements are not supported right know. */
+ gcc_unreachable ();
+ break;
+
+ default:
+ gcc_unreachable ();
+ break;
+ }
+ }
+
+
+ /* Enlarge the matrix. */
+ {
+ CloogMatrix *new_domain;
+ new_domain = cloog_matrix_alloc (nb_rows + nb_new_rows, nb_cols);
+
+ if (domain)
+ {
+ for (i = 0; i < nb_rows; i++)
+ for (j = 0; j < nb_cols; j++)
+ value_assign (new_domain->p[i][j], domain->p[i][j]);
+
+ cloog_matrix_free (domain);
+ }
+
+ domain = new_domain;
+ GBB_DOMAIN (gb) = new_domain;
+ }
+
+ /* Add the conditions to the new enlarged domain matrix. */
+ row = nb_rows;
+ for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
+ {
+ switch (gimple_code (stmt))
+ {
+ case GIMPLE_COND:
+ {
+ Value one;
+ enum tree_code code;
+ tree left;
+ tree right;
+ loop_p loop = GBB_BB (gb)->loop_father;
+
+ left = gimple_cond_lhs (stmt);
+ right = gimple_cond_rhs (stmt);
+
+ left = analyze_scalar_evolution (loop, left);
+ right = analyze_scalar_evolution (loop, right);
+
+ left = instantiate_scev (block_before_scop (scop), loop, left);
+ right = instantiate_scev (block_before_scop (scop), loop, right);
+
+ code = gimple_cond_code (stmt);
+
+ /* The conditions for ELSE-branches are inverted. */
+ if (VEC_index (gimple, gb->condition_cases, i) == NULL)
+ code = invert_tree_comparison (code, false);
+
+ switch (code)
+ {
+ case NE_EXPR:
+ /* NE statements are not supported right know. */
+ gcc_unreachable ();
+ break;
+ case EQ_EXPR:
+ value_set_si (domain->p[row][0], 1);
+ value_init (one);
+ value_set_si (one, 1);
+ scan_tree_for_params (scop, left, domain, row, one, true);
+ value_set_si (one, 1);
+ scan_tree_for_params (scop, right, domain, row, one, false);
+ row++;
+ value_set_si (domain->p[row][0], 1);
+ value_set_si (one, 1);
+ scan_tree_for_params (scop, left, domain, row, one, false);
+ value_set_si (one, 1);
+ scan_tree_for_params (scop, right, domain, row, one, true);
+ value_clear (one);
+ row++;
+ break;
+ case LT_EXPR:
+ value_set_si (domain->p[row][0], 1);
+ value_init (one);
+ value_set_si (one, 1);
+ scan_tree_for_params (scop, left, domain, row, one, true);
+ value_set_si (one, 1);
+ scan_tree_for_params (scop, right, domain, row, one, false);
+ value_sub_int (domain->p[row][nb_cols - 1],
+ domain->p[row][nb_cols - 1], 1);
+ value_clear (one);
+ row++;
+ break;
+ case GT_EXPR:
+ value_set_si (domain->p[row][0], 1);
+ value_init (one);
+ value_set_si (one, 1);
+ scan_tree_for_params (scop, left, domain, row, one, false);
+ value_set_si (one, 1);
+ scan_tree_for_params (scop, right, domain, row, one, true);
+ value_sub_int (domain->p[row][nb_cols - 1],
+ domain->p[row][nb_cols - 1], 1);
+ value_clear (one);
+ row++;
+ break;
+ case LE_EXPR:
+ value_set_si (domain->p[row][0], 1);
+ value_init (one);
+ value_set_si (one, 1);
+ scan_tree_for_params (scop, left, domain, row, one, true);
+ value_set_si (one, 1);
+ scan_tree_for_params (scop, right, domain, row, one, false);
+ value_clear (one);
+ row++;
+ break;
+ case GE_EXPR:
+ value_set_si (domain->p[row][0], 1);
+ value_init (one);
+ value_set_si (one, 1);
+ scan_tree_for_params (scop, left, domain, row, one, false);
+ value_set_si (one, 1);
+ scan_tree_for_params (scop, right, domain, row, one, true);
+ value_clear (one);
+ row++;
+ break;
+ default:
+ gcc_unreachable ();
+ break;
+ }
+ break;
+ }
+ case GIMPLE_SWITCH:
+ /* Switch statements are not supported right know. */
+ gcc_unreachable ();
+ break;
+
+ default:
+ gcc_unreachable ();
+ break;
+ }
+ }
+}
+
+/* Returns true when PHI defines an induction variable in the loop
+ containing the PHI node. */
+
+static bool
+phi_node_is_iv (gimple phi)
+{
+ loop_p loop = gimple_bb (phi)->loop_father;
+ tree scev = analyze_scalar_evolution (loop, gimple_phi_result (phi));
+
+ return tree_contains_chrecs (scev, NULL);
+}
+
+/* Returns true when BB contains scalar phi nodes that are not an
+ induction variable of a loop. */
+
+static bool
+bb_contains_non_iv_scalar_phi_nodes (basic_block bb)
+{
+ gimple phi = NULL;
+ gimple_stmt_iterator si;
+
+ for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
+ if (is_gimple_reg (gimple_phi_result (gsi_stmt (si))))
+ {
+ /* Store the unique scalar PHI node: at this point, loops
+ should be in cannonical form, so we expect to see at most
+ one scalar phi node in the loop header. */
+ if (phi
+ || bb != bb->loop_father->header)
+ return true;
+
+ phi = gsi_stmt (si);
+ }
+
+ if (!phi
+ || phi_node_is_iv (phi))
+ return false;
+
+ return true;
+}
+
+/* Helper recursive function. Record in CONDITIONS and CASES all
+ conditions from 'if's and 'switch'es occurring in BB from SCOP.
+
+ Returns false when the conditions contain scalar computations that
+ depend on the condition, i.e. when there are scalar phi nodes on
+ the junction after the condition. Only the computations occurring
+ on memory can be handled in the polyhedral model: operations that
+ define scalar evolutions in conditions, that can potentially be
+ used to index memory, can't be handled by the polyhedral model. */
+
+static bool
+build_scop_conditions_1 (VEC (gimple, heap) **conditions,
+ VEC (gimple, heap) **cases, basic_block bb,
+ scop_p scop)
+{
+ bool res = true;
+ int i, j;
+ graphite_bb_p gbb;
+ basic_block bb_child, bb_iter;
+ VEC (basic_block, heap) *dom;
+ gimple stmt;
+
+ /* Make sure we are in the SCoP. */
+ if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
+ return true;
+
+ if (bb_contains_non_iv_scalar_phi_nodes (bb))
+ return false;
+
+ gbb = gbb_from_bb (bb);
+ if (gbb)
+ {
+ GBB_CONDITIONS (gbb) = VEC_copy (gimple, heap, *conditions);
+ GBB_CONDITION_CASES (gbb) = VEC_copy (gimple, heap, *cases);
+ }
+
+ dom = get_dominated_by (CDI_DOMINATORS, bb);
+
+ stmt = last_stmt (bb);
+ if (stmt)
+ {
+ VEC (edge, gc) *edges;
+ edge e;
+
+ switch (gimple_code (stmt))
+ {
+ case GIMPLE_COND:
+ edges = bb->succs;
+ for (i = 0; VEC_iterate (edge, edges, i, e); i++)
+ if ((dominated_by_p (CDI_DOMINATORS, e->dest, bb))
+ && VEC_length (edge, e->dest->preds) == 1)
+ {
+ /* Remove the scanned block from the dominator successors. */
+ for (j = 0; VEC_iterate (basic_block, dom, j, bb_iter); j++)
+ if (bb_iter == e->dest)
+ {
+ VEC_unordered_remove (basic_block, dom, j);
+ break;
+ }
+
+ /* Recursively scan the then or else part. */
+ if (e->flags & EDGE_TRUE_VALUE)
+ VEC_safe_push (gimple, heap, *cases, stmt);
+ else
+ {
+ gcc_assert (e->flags & EDGE_FALSE_VALUE);
+ VEC_safe_push (gimple, heap, *cases, NULL);
+ }
+
+ VEC_safe_push (gimple, heap, *conditions, stmt);
+ if (!build_scop_conditions_1 (conditions, cases, e->dest, scop))
+ {
+ res = false;
+ goto done;
+ }
+ VEC_pop (gimple, *conditions);
+ VEC_pop (gimple, *cases);
+ }
+ break;
+
+ case GIMPLE_SWITCH:
+ {
+ unsigned i;
+ gimple_stmt_iterator gsi_search_gimple_label;
+
+ for (i = 0; i < gimple_switch_num_labels (stmt); ++i)
+ {
+ basic_block bb_iter;
+ size_t k;
+ size_t n_cases = VEC_length (gimple, *conditions);
+ unsigned n = gimple_switch_num_labels (stmt);
+
+ bb_child = label_to_block
+ (CASE_LABEL (gimple_switch_label (stmt, i)));
+
+ for (k = 0; k < n; k++)
+ if (i != k
+ && label_to_block
+ (CASE_LABEL (gimple_switch_label (stmt, k))) == bb_child)
+ break;
+
+ /* Switches with multiple case values for the same
+ block are not handled. */
+ if (k != n
+ /* Switch cases with more than one predecessor are
+ not handled. */
+ || VEC_length (edge, bb_child->preds) != 1)
+ {
+ res = false;
+ goto done;
+ }
+
+ /* Recursively scan the corresponding 'case' block. */
+ for (gsi_search_gimple_label = gsi_start_bb (bb_child);
+ !gsi_end_p (gsi_search_gimple_label);
+ gsi_next (&gsi_search_gimple_label))
+ {
+ gimple label = gsi_stmt (gsi_search_gimple_label);
+
+ if (gimple_code (label) == GIMPLE_LABEL)
+ {
+ tree t = gimple_label_label (label);
+
+ gcc_assert (t == gimple_switch_label (stmt, i));
+ VEC_replace (gimple, *cases, n_cases, label);
+ break;
+ }
+ }
+
+ if (!build_scop_conditions_1 (conditions, cases, bb_child, scop))
+ {
+ res = false;
+ goto done;
+ }
+
+ /* Remove the scanned block from the dominator successors. */
+ for (j = 0; VEC_iterate (basic_block, dom, j, bb_iter); j++)
+ if (bb_iter == bb_child)
+ {
+ VEC_unordered_remove (basic_block, dom, j);
+ break;
+ }
+ }
+
+ VEC_pop (gimple, *conditions);
+ VEC_pop (gimple, *cases);
+ break;
+ }
+
+ default:
+ break;
+ }
+ }
+
+ /* Scan all immediate dominated successors. */
+ for (i = 0; VEC_iterate (basic_block, dom, i, bb_child); i++)
+ if (!build_scop_conditions_1 (conditions, cases, bb_child, scop))
+ {
+ res = false;
+ goto done;
+ }
+
+ done:
+ VEC_free (basic_block, heap, dom);
+ return res;
+}
+
+/* Record all conditions from SCOP.
+
+ Returns false when the conditions contain scalar computations that
+ depend on the condition, i.e. when there are scalar phi nodes on
+ the junction after the condition. Only the computations occurring
+ on memory can be handled in the polyhedral model: operations that
+ define scalar evolutions in conditions, that can potentially be
+ used to index memory, can't be handled by the polyhedral model. */
+
+static bool
+build_scop_conditions (scop_p scop)
+{
+ bool res;
+ VEC (gimple, heap) *conditions = NULL;
+ VEC (gimple, heap) *cases = NULL;
+
+ res = build_scop_conditions_1 (&conditions, &cases, SCOP_ENTRY (scop), scop);
+
+ VEC_free (gimple, heap, conditions);
+ VEC_free (gimple, heap, cases);
+ return res;
+}
+
+/* Traverses all the GBBs of the SCOP and add their constraints to the
+ iteration domains. */
+
+static void
+add_conditions_to_constraints (scop_p scop)
+{
+ int i;
+ graphite_bb_p gbb;
+
+ for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
+ add_conditions_to_domain (gbb);
+}
+
+/* Build the current domain matrix: the loops belonging to the current
+ SCOP, and that vary for the execution of the current basic block.
+ Returns false if there is no loop in SCOP. */
+
+static bool
+build_scop_iteration_domain (scop_p scop)
+{
+ struct loop *loop;
+ CloogMatrix *outer_cstr;
+ int i;
+
+ /* Build cloog loop for all loops, that are in the uppermost loop layer of
+ this SCoP. */
+ for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop); i++)
+ if (!loop_in_sese_p (loop_outer (loop), SCOP_REGION (scop)))
+ {
+ /* The outermost constraints is a matrix that has:
+ -first column: eq/ineq boolean
+ -last column: a constant
+ -scop_nb_params columns for the parameters used in the scop. */
+ outer_cstr = cloog_matrix_alloc (0, scop_nb_params (scop) + 2);
+ build_loop_iteration_domains (scop, loop, outer_cstr, 0);
+ cloog_matrix_free (outer_cstr);
+ }
+
+ return (i != 0);
+}
+
+/* Initializes an equation CY of the access matrix using the
+ information for a subscript from AF, relatively to the loop
+ indexes from LOOP_NEST and parameter indexes from PARAMS. NDIM is
+ the dimension of the array access, i.e. the number of
+ subscripts. Returns true when the operation succeeds. */
+
+static bool
+build_access_matrix_with_af (tree af, lambda_vector cy,
+ scop_p scop, int ndim)
+{
+ int param_col;
+
+ switch (TREE_CODE (af))
+ {
+ case POLYNOMIAL_CHREC:
+ {
+ struct loop *outer_loop;
+ tree left = CHREC_LEFT (af);
+ tree right = CHREC_RIGHT (af);
+ int var;
+
+ if (TREE_CODE (right) != INTEGER_CST)
+ return false;
+
+ outer_loop = get_loop (CHREC_VARIABLE (af));
+ var = nb_loops_around_loop_in_scop (outer_loop, scop);
+ cy[var] = int_cst_value (right);
+
+ switch (TREE_CODE (left))
+ {
+ case POLYNOMIAL_CHREC:
+ return build_access_matrix_with_af (left, cy, scop, ndim);
+
+ case INTEGER_CST:
+ cy[ndim - 1] = int_cst_value (left);
+ return true;
+
+ default:
+ return build_access_matrix_with_af (left, cy, scop, ndim);
+ }
+ }
+
+ case PLUS_EXPR:
+ build_access_matrix_with_af (TREE_OPERAND (af, 0), cy, scop, ndim);
+ build_access_matrix_with_af (TREE_OPERAND (af, 1), cy, scop, ndim);
+ return true;
+
+ case MINUS_EXPR:
+ build_access_matrix_with_af (TREE_OPERAND (af, 0), cy, scop, ndim);
+ build_access_matrix_with_af (TREE_OPERAND (af, 1), cy, scop, ndim);
+ return true;
+
+ case INTEGER_CST:
+ cy[ndim - 1] = int_cst_value (af);
+ return true;
+
+ case SSA_NAME:
+ param_col = param_index (af, scop);
+ cy [ndim - scop_nb_params (scop) + param_col - 1] = 1;
+ return true;
+
+ default:
+ /* FIXME: access_fn can have parameters. */
+ return false;
+ }
+}
+
+/* Initialize the access matrix in the data reference REF with respect
+ to the loop nesting LOOP_NEST. Return true when the operation
+ succeeded. */
+
+static bool
+build_access_matrix (data_reference_p ref, graphite_bb_p gb)
+{
+ int i, ndim = DR_NUM_DIMENSIONS (ref);
+ struct access_matrix *am = GGC_NEW (struct access_matrix);
+
+ AM_MATRIX (am) = VEC_alloc (lambda_vector, gc, ndim);
+ DR_SCOP (ref) = GBB_SCOP (gb);
+
+ for (i = 0; i < ndim; i++)
+ {
+ lambda_vector v = lambda_vector_new (ref_nb_loops (ref));
+ scop_p scop = GBB_SCOP (gb);
+ tree af = DR_ACCESS_FN (ref, i);
+
+ if (!build_access_matrix_with_af (af, v, scop, ref_nb_loops (ref)))
+ return false;
+
+ VEC_quick_push (lambda_vector, AM_MATRIX (am), v);
+ }
+
+ DR_ACCESS_MATRIX (ref) = am;
+ return true;
+}
+
+/* Build the access matrices for the data references in the SCOP. */
+
+static void
+build_scop_data_accesses (scop_p scop)
+{
+ int i;
+ graphite_bb_p gb;
+
+ /* FIXME: Construction of access matrix is disabled until some
+ pass, like the data dependence analysis, is using it. */
+ return;
+
+ for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
+ {
+ int j;
+ data_reference_p dr;
+
+ /* Construct the access matrix for each data ref, with respect to
+ the loop nest of the current BB in the considered SCOP. */
+ for (j = 0;
+ VEC_iterate (data_reference_p, GBB_DATA_REFS (gb), j, dr);
+ j++)
+ {
+ bool res = build_access_matrix (dr, gb);
+
+ /* FIXME: At this point the DRs should always have an affine
+ form. For the moment this fails as build_access_matrix
+ does not build matrices with parameters. */
+ gcc_assert (res);
+ }
+ }
+}
+
+/* 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.
+
+ FIXME: This is a hack, and Cloog should be fixed to not work with
+ variable names represented as "char *string", but with void
+ pointers that could be casted back to a tree. The only problem in
+ doing that is that Cloog's pretty printer still assumes that
+ variable names are char *strings. The solution would be to have a
+ function pointer for pretty-printing that can be redirected to be
+ print_generic_stmt in our case, or fprintf by default.
+ ??? Too ugly to live. */
+
+static tree
+clast_name_to_gcc (const char *name, VEC (name_tree, heap) *params,
+ loop_iv_stack ivstack)
+{
+ int i;
+ name_tree t;
+ tree iv;
+
+ 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)
+ return iv;
+
+ gcc_unreachable ();
+}
+
+/* Returns the maximal precision type for expressions E1 and E2. */
+
+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;
+}
+
+static tree
+clast_to_gcc_expression (tree, struct clast_expr *, VEC (name_tree, heap) *,
+ loop_iv_stack);
+
+/* Converts a Cloog reduction expression R with reduction operation OP
+ to a GCC expression tree of type TYPE. PARAMS is a vector of
+ parameters of the scop, and IVSTACK contains the stack of induction
+ variables. */
+
+static tree
+clast_to_gcc_expression_red (tree type, enum tree_code op,
+ struct clast_reduction *r,
+ VEC (name_tree, heap) *params,
+ loop_iv_stack ivstack)
+{
+ int i;
+ tree res = clast_to_gcc_expression (type, r->elts[0], params, ivstack);
+
+ for (i = 1; i < r->n; i++)
+ {
+ tree t = clast_to_gcc_expression (type, r->elts[i], params, ivstack);
+ res = fold_build2 (op, type, res, t);
+ }
+ return res;
+}
+
+/* Converts a Cloog AST expression E back to a GCC expression tree of
+ type TYPE. PARAMS is a vector of parameters of the scop, and
+ IVSTACK contains the stack of induction variables. */
+
+static tree
+clast_to_gcc_expression (tree type, 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)
+ {
+ if (value_one_p (t->val))
+ {
+ tree name = clast_name_to_gcc (t->var, params, ivstack);
+ return fold_convert (type, name);
+ }
+
+ else if (value_mone_p (t->val))
+ {
+ tree name = clast_name_to_gcc (t->var, params, ivstack);
+ name = fold_convert (type, name);
+ return fold_build1 (NEGATE_EXPR, type, name);
+ }
+ else
+ {
+ 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 (type, t->val);
+ }
+
+ case expr_red:
+ {
+ struct clast_reduction *r = (struct clast_reduction *) e;
+
+ switch (r->type)
+ {
+ case clast_red_sum:
+ return clast_to_gcc_expression_red (type, PLUS_EXPR, r, params, ivstack);
+
+ case clast_red_min:
+ return clast_to_gcc_expression_red (type, MIN_EXPR, r, params, ivstack);
+
+ case clast_red_max:
+ return clast_to_gcc_expression_red (type, MAX_EXPR, r, params, ivstack);
+
+ default:
+ gcc_unreachable ();
+ }
+ break;
+ }
+
+ case expr_bin:
+ {
+ struct clast_binary *b = (struct clast_binary *) e;
+ struct clast_expr *lhs = (struct clast_expr *) b->LHS;
+ tree tl = clast_to_gcc_expression (type, lhs, params, ivstack);
+ tree tr = gmp_cst_to_tree (type, b->RHS);
+
+ switch (b->type)
+ {
+ case clast_bin_fdiv:
+ return fold_build2 (FLOOR_DIV_EXPR, type, tl, tr);
+
+ case clast_bin_cdiv:
+ return fold_build2 (CEIL_DIV_EXPR, type, tl, tr);
+
+ case clast_bin_div:
+ return fold_build2 (EXACT_DIV_EXPR, type, tl, tr);
+
+ case clast_bin_mod:
+ return fold_build2 (TRUNC_MOD_EXPR, type, tl, tr);
+
+ default:
+ gcc_unreachable ();
+ }
+ }
+
+ default:
+ gcc_unreachable ();
+ }
+
+ 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
+graphite_translate_clast_equation (scop_p scop,
+ struct clast_equation *cleq,
+ loop_iv_stack ivstack)
+{
+ enum tree_code comp;
+ 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;
+
+ else if (cleq->sign > 0)
+ comp = GE_EXPR;
+
+ else
+ comp = LE_EXPR;
+
+ return fold_build2 (comp, type, lhs, rhs);
+}
+
+/* Creates the test for the condition in STMT. */
+
+static tree
+graphite_create_guard_cond_expr (scop_p scop, struct clast_guard *stmt,
+ loop_iv_stack ivstack)
+{
+ tree cond = NULL;
+ int i;
+
+ for (i = 0; i < stmt->n; i++)
+ {
+ tree eq = graphite_translate_clast_equation (scop, &stmt->eq[i], ivstack);
+
+ if (cond)
+ cond = fold_build2 (TRUTH_AND_EXPR, TREE_TYPE (eq), cond, eq);
+ else
+ cond = eq;
+ }
+
+ return cond;
+}
+
+/* Creates a new if region corresponding to Cloog's guard. */
+
+static edge
+graphite_create_new_guard (scop_p scop, edge entry_edge,
+ struct clast_guard *stmt,
+ loop_iv_stack ivstack)
+{
+ tree cond_expr = graphite_create_guard_cond_expr (scop, stmt, ivstack);
+ edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
+ 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
+ ENTRY_EDGE. LOOP is inserted into the loop tree and becomes the child
+ loop of the OUTER_LOOP. */
+
+static struct loop *
+graphite_create_new_loop (scop_p scop, edge entry_edge,
+ struct clast_for *stmt, loop_iv_stack ivstack,
+ loop_p outer)
+{
+ 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);
+
+ add_referenced_var (ivvar);
+ loop_iv_stack_push_iv (ivstack, iv_before, stmt->iterator);
+ return loop;
+}
+
+/* Rename the SSA_NAMEs used in STMT and that appear in IVSTACK. */
+
+static void
+rename_variables_in_stmt (gimple stmt, htab_t map)
+{
+ ssa_op_iter iter;
+ use_operand_p use_p;
+
+ FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
+ {
+ tree use = USE_FROM_PTR (use_p);
+ tree new_name = get_new_name_from_old_name (map, use);
+
+ replace_exp (use_p, new_name);
+ }
+
+ update_stmt (stmt);
+}
+
+/* Returns true if SSA_NAME is a parameter of SCOP. */
+
+static bool
+is_parameter (scop_p scop, tree ssa_name)
+{
+ int i;
+ VEC (name_tree, heap) *params = SCOP_PARAMS (scop);
+ name_tree param;
+
+ for (i = 0; VEC_iterate (name_tree, params, i, param); i++)
+ if (param->t == ssa_name)
+ return true;
+
+ return false;
+}
+
+/* Returns true if NAME is an induction variable. */
+
+static bool
+is_iv (tree name)
+{
+ return gimple_code (SSA_NAME_DEF_STMT (name)) == GIMPLE_PHI;
+}
+
+static void expand_scalar_variables_stmt (gimple, basic_block, scop_p,
+ htab_t);
+static tree
+expand_scalar_variables_expr (tree, tree, enum tree_code, tree, basic_block,
+ scop_p, htab_t, gimple_stmt_iterator *);
+
+/* Copies at GSI all the scalar computations on which the ssa_name OP0
+ depends on in the SCOP: these are all the scalar variables used in
+ the definition of OP0, that are defined outside BB and still in the
+ SCOP, i.e. not a parameter of the SCOP. The expression that is
+ returned contains only induction variables from the generated code:
+ MAP contains the induction variables renaming mapping, and is used
+ to translate the names of induction variables. */
+
+static tree
+expand_scalar_variables_ssa_name (tree op0, basic_block bb,
+ scop_p scop, htab_t map,
+ gimple_stmt_iterator *gsi)
+{
+ tree var0, var1, type;
+ gimple def_stmt;
+ enum tree_code subcode;
+
+ if (is_parameter (scop, op0)
+ || is_iv (op0))
+ return get_new_name_from_old_name (map, op0);
+
+ def_stmt = SSA_NAME_DEF_STMT (op0);
+
+ if (gimple_bb (def_stmt) == bb)
+ {
+ /* If the defining statement is in the basic block already
+ we do not need to create a new expression for it, we
+ only need to ensure its operands are expanded. */
+ expand_scalar_variables_stmt (def_stmt, bb, scop, map);
+ return get_new_name_from_old_name (map, op0);
+ }
+ else
+ {
+ if (gimple_code (def_stmt) != GIMPLE_ASSIGN
+ || !bb_in_sese_p (gimple_bb (def_stmt), SCOP_REGION (scop)))
+ return get_new_name_from_old_name (map, op0);
+
+ var0 = gimple_assign_rhs1 (def_stmt);
+ subcode = gimple_assign_rhs_code (def_stmt);
+ var1 = gimple_assign_rhs2 (def_stmt);
+ type = gimple_expr_type (def_stmt);
+
+ return expand_scalar_variables_expr (type, var0, subcode, var1, bb, scop,
+ map, gsi);
+ }
+}
+
+/* Copies at GSI all the scalar computations on which the expression
+ OP0 CODE OP1 depends on in the SCOP: these are all the scalar
+ variables used in OP0 and OP1, defined outside BB and still defined
+ in the SCOP, i.e. not a parameter of the SCOP. The expression that
+ is returned contains only induction variables from the generated
+ code: MAP contains the induction variables renaming mapping, and is
+ used to translate the names of induction variables. */
+
+static tree
+expand_scalar_variables_expr (tree type, tree op0, enum tree_code code,
+ tree op1, basic_block bb, scop_p scop,
+ htab_t map, gimple_stmt_iterator *gsi)
+{
+ if (TREE_CODE_CLASS (code) == tcc_constant
+ || TREE_CODE_CLASS (code) == tcc_declaration)
+ return op0;
+
+ /* For data references we have to duplicate also its memory
+ indexing. */
+ if (TREE_CODE_CLASS (code) == tcc_reference)
+ {
+ switch (code)
+ {
+ case INDIRECT_REF:
+ {
+ tree old_name = TREE_OPERAND (op0, 0);
+ tree expr = expand_scalar_variables_ssa_name
+ (old_name, bb, scop, map, gsi);
+ tree new_name = force_gimple_operand_gsi (gsi, expr, true, NULL,
+ true, GSI_SAME_STMT);
+
+ set_symbol_mem_tag (SSA_NAME_VAR (new_name),
+ symbol_mem_tag (SSA_NAME_VAR (old_name)));
+ return fold_build1 (code, type, new_name);
+ }
+
+ case ARRAY_REF:
+ {
+ tree op00 = TREE_OPERAND (op0, 0);
+ tree op01 = TREE_OPERAND (op0, 1);
+ tree op02 = TREE_OPERAND (op0, 2);
+ tree op03 = TREE_OPERAND (op0, 3);
+ tree base = expand_scalar_variables_expr
+ (TREE_TYPE (op00), op00, TREE_CODE (op00), NULL, bb, scop,
+ map, gsi);
+ tree subscript = expand_scalar_variables_expr
+ (TREE_TYPE (op01), op01, TREE_CODE (op01), NULL, bb, scop,
+ map, gsi);
+
+ return build4 (ARRAY_REF, type, base, subscript, op02, op03);
+ }
+
+ default:
+ /* The above cases should catch everything. */
+ gcc_unreachable ();
+ }
+ }
+
+ if (TREE_CODE_CLASS (code) == tcc_unary)
+ {
+ tree op0_type = TREE_TYPE (op0);
+ enum tree_code op0_code = TREE_CODE (op0);
+ tree op0_expr = expand_scalar_variables_expr (op0_type, op0, op0_code,
+ NULL, bb, scop, map, gsi);
+
+ return fold_build1 (code, type, op0_expr);
+ }
+
+ if (TREE_CODE_CLASS (code) == tcc_binary)
+ {
+ tree op0_type = TREE_TYPE (op0);
+ enum tree_code op0_code = TREE_CODE (op0);
+ tree op0_expr = expand_scalar_variables_expr (op0_type, op0, op0_code,
+ NULL, bb, scop, map, gsi);
+ tree op1_type = TREE_TYPE (op1);
+ enum tree_code op1_code = TREE_CODE (op1);
+ tree op1_expr = expand_scalar_variables_expr (op1_type, op1, op1_code,
+ NULL, bb, scop, map, gsi);
+
+ return fold_build2 (code, type, op0_expr, op1_expr);
+ }
+
+ if (code == SSA_NAME)
+ return expand_scalar_variables_ssa_name (op0, bb, scop, map, gsi);
+
+ gcc_unreachable ();
+ return NULL;
+}
+
+/* Copies at the beginning of BB all the scalar computations on which
+ STMT depends on in the SCOP: these are all the scalar variables used
+ in STMT, defined outside BB and still defined in the SCOP, i.e. not a
+ parameter of the SCOP. The expression that is returned contains
+ only induction variables from the generated code: MAP contains the
+ induction variables renaming mapping, and is used to translate the
+ names of induction variables. */
+
+static void
+expand_scalar_variables_stmt (gimple stmt, basic_block bb, scop_p scop,
+ htab_t map)
+{
+ ssa_op_iter iter;
+ use_operand_p use_p;
+ gimple_stmt_iterator gsi = gsi_after_labels (bb);
+
+ FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
+ {
+ tree use = USE_FROM_PTR (use_p);
+ tree type = TREE_TYPE (use);
+ enum tree_code code = TREE_CODE (use);
+ tree use_expr = expand_scalar_variables_expr (type, use, code, NULL, bb,
+ scop, map, &gsi);
+ if (use_expr != use)
+ {
+ tree new_use =
+ force_gimple_operand_gsi (&gsi, use_expr, true, NULL,
+ true, GSI_NEW_STMT);
+ replace_exp (use_p, new_use);
+ }
+ }
+
+ update_stmt (stmt);
+}
+
+/* Copies at the beginning of BB all the scalar computations on which
+ BB depends on in the SCOP: these are all the scalar variables used
+ in BB, defined outside BB and still defined in the SCOP, i.e. not a
+ parameter of the SCOP. The expression that is returned contains
+ only induction variables from the generated code: MAP contains the
+ induction variables renaming mapping, and is used to translate the
+ names of induction variables. */
+
+static void
+expand_scalar_variables (basic_block bb, scop_p scop, htab_t map)
+{
+ gimple_stmt_iterator gsi;
+
+ for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi);)
+ {
+ gimple stmt = gsi_stmt (gsi);
+ expand_scalar_variables_stmt (stmt, bb, scop, map);
+ gsi_next (&gsi);
+ }
+}
+
+/* Rename all the SSA_NAMEs from block BB according to the MAP. */
+
+static void
+rename_variables (basic_block bb, htab_t map)
+{
+ gimple_stmt_iterator gsi;
+
+ for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ rename_variables_in_stmt (gsi_stmt (gsi), map);
+}
+
+/* Remove condition from BB. */
+
+static void
+remove_condition (basic_block bb)
+{
+ gimple last = last_stmt (bb);
+
+ if (last && gimple_code (last) == GIMPLE_COND)
+ {
+ gimple_stmt_iterator gsi = gsi_last_bb (bb);
+ gsi_remove (&gsi, true);
+ }
+}
+
+/* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */
+
+static edge
+get_true_edge_from_guard_bb (basic_block bb)
+{
+ edge e;
+ edge_iterator ei;
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (e->flags & EDGE_TRUE_VALUE)
+ return e;
+
+ gcc_unreachable ();
+ return NULL;
+}
+
+/* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */
+
+static edge
+get_false_edge_from_guard_bb (basic_block bb)
+{
+ edge e;
+ edge_iterator ei;
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (!(e->flags & EDGE_TRUE_VALUE))
+ return e;
+
+ gcc_unreachable ();
+ return NULL;
+}
+
+/* Inserts in MAP a tuple (OLD_NAME, NEW_NAME) for the induction
+ variables of the loops around GBB in SCOP, i.e. GBB_LOOPS.
+ NEW_NAME is obtained from IVSTACK. IVSTACK has the same stack
+ ordering as GBB_LOOPS. */
+
+static void
+build_iv_mapping (loop_iv_stack ivstack, htab_t map, gbb_p gbb, scop_p scop)
+{
+ int i;
+ name_tree iv;
+ PTR *slot;
+
+ for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, iv); i++)
+ {
+ struct rename_map_elt tmp;
+
+ if (!flow_bb_inside_loop_p (iv->loop, GBB_BB (gbb)))
+ continue;
+
+ tmp.old_name = iv->t;
+ slot = htab_find_slot (map, &tmp, INSERT);
+
+ if (!*slot)
+ {
+ tree new_name = loop_iv_stack_get_iv (ivstack,
+ gbb_loop_index (gbb, iv->loop));
+ *slot = new_rename_map_elt (iv->t, new_name);
+ }
+ }
+}
+
+/* Register in MAP the tuple (old_name, new_name). */
+
+static void
+register_old_and_new_names (htab_t map, tree old_name, tree new_name)
+{
+ struct rename_map_elt tmp;
+ PTR *slot;
+
+ tmp.old_name = old_name;
+ slot = htab_find_slot (map, &tmp, INSERT);
+
+ if (!*slot)
+ *slot = new_rename_map_elt (old_name, new_name);
+}
+
+/* Create a duplicate of the basic block BB. NOTE: This does not
+ preserve SSA form. */
+
+static void
+graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, htab_t map)
+{
+ gimple_stmt_iterator gsi, gsi_tgt;
+
+ gsi_tgt = gsi_start_bb (new_bb);
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ def_operand_p def_p;
+ ssa_op_iter op_iter;
+ int region;
+ gimple stmt = gsi_stmt (gsi);
+ gimple copy;
+
+ if (gimple_code (stmt) == GIMPLE_LABEL)
+ continue;
+
+ /* Create a new copy of STMT and duplicate STMT's virtual
+ operands. */
+ copy = gimple_copy (stmt);
+ gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
+ mark_symbols_for_renaming (copy);
+
+ region = lookup_stmt_eh_region (stmt);
+ if (region >= 0)
+ add_stmt_to_eh_region (copy, region);
+ gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
+
+ /* Create new names for all the definitions created by COPY and
+ add replacement mappings for each new name. */
+ FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_DEF)
+ {
+ tree old_name = DEF_FROM_PTR (def_p);
+ tree new_name = create_new_def_for (old_name, copy, def_p);
+ register_old_and_new_names (map, old_name, new_name);
+ }
+ }
+}
+
+/* Records in SCOP_LIVEOUT_RENAMES the names that are live out of
+ the SCOP and that appear in the RENAME_MAP. */
+
+static void
+register_scop_liveout_renames (scop_p scop, htab_t rename_map)
+{
+ int i;
+ sese region = SCOP_REGION (scop);
+
+ for (i = 0; i < SESE_NUM_VER (region); i++)
+ if (bitmap_bit_p (SESE_LIVEOUT (region), i)
+ && is_gimple_reg (ssa_name (i)))
+ {
+ tree old_name = ssa_name (i);
+ tree new_name = get_new_name_from_old_name (rename_map, old_name);
+
+ register_old_and_new_names (SCOP_LIVEOUT_RENAMES (scop),
+ old_name, new_name);
+ }
+}
+
+/* Copies BB and includes in the copied BB all the statements that can
+ be reached following the use-def chains from the memory accesses,
+ and returns the next edge following this new block. */
+
+static edge
+copy_bb_and_scalar_dependences (basic_block bb, scop_p scop,
+ edge next_e, htab_t map)
+{
+ basic_block new_bb = split_edge (next_e);
+
+ next_e = single_succ_edge (new_bb);
+ graphite_copy_stmts_from_block (bb, new_bb, map);
+ remove_condition (new_bb);
+ rename_variables (new_bb, map);
+ remove_phi_nodes (new_bb);
+ expand_scalar_variables (new_bb, scop, map);
+ register_scop_liveout_renames (scop, map);
+
+ return next_e;
+}
+
+/* Helper function for htab_traverse in insert_loop_close_phis. */
+
+static int
+add_loop_exit_phis (void **slot, void *s)
+{
+ struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
+ tree new_name = entry->new_name;
+ basic_block bb = (basic_block) s;
+ gimple phi = create_phi_node (new_name, bb);
+ tree res = create_new_def_for (gimple_phi_result (phi), phi,
+ gimple_phi_result_ptr (phi));
+
+ add_phi_arg (phi, new_name, single_pred_edge (bb));
+
+ entry->new_name = res;
+ *slot = entry;
+ return 1;
+}
+
+/* Iterate over the SCOP_LIVEOUT_RENAMES (SCOP) and get tuples of the
+ form (OLD_NAME, NEW_NAME). Insert in BB "RES = phi (NEW_NAME)",
+ and finally register in SCOP_LIVEOUT_RENAMES (scop) the tuple
+ (OLD_NAME, RES). */
+
+static void
+insert_loop_close_phis (scop_p scop, basic_block bb)
+{
+ update_ssa (TODO_update_ssa);
+ htab_traverse (SCOP_LIVEOUT_RENAMES (scop), add_loop_exit_phis, bb);
+ update_ssa (TODO_update_ssa);
+}
+
+/* Helper structure for htab_traverse in insert_guard_phis. */
+
+struct igp {
+ basic_block bb;
+ edge true_edge, false_edge;
+ htab_t liveout_before_guard;
+};
+
+/* Return the default name that is before the guard. */
+
+static tree
+default_liveout_before_guard (htab_t liveout_before_guard, tree old_name)
+{
+ tree res = get_new_name_from_old_name (liveout_before_guard, old_name);
+
+ if (res == old_name)
+ {
+ if (is_gimple_reg (res))
+ return fold_convert (TREE_TYPE (res), integer_zero_node);
+ return gimple_default_def (cfun, res);
+ }
+
+ return res;
+}
+
+/* Helper function for htab_traverse in insert_guard_phis. */
+
+static int
+add_guard_exit_phis (void **slot, void *s)
+{
+ struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
+ struct igp *i = (struct igp *) s;
+ basic_block bb = i->bb;
+ edge true_edge = i->true_edge;
+ edge false_edge = i->false_edge;
+ tree name1 = entry->new_name;
+ tree name2 = default_liveout_before_guard (i->liveout_before_guard,
+ entry->old_name);
+ gimple phi = create_phi_node (name1, bb);
+ tree res = create_new_def_for (gimple_phi_result (phi), phi,
+ gimple_phi_result_ptr (phi));
+
+ add_phi_arg (phi, name1, true_edge);
+ add_phi_arg (phi, name2, false_edge);
+
+ entry->new_name = res;
+ *slot = entry;
+ return 1;
+}
+
+/* Iterate over the SCOP_LIVEOUT_RENAMES (SCOP) and get tuples of the
+ form (OLD_NAME, NAME1). If there is a correspondent tuple of
+ OLD_NAME in LIVEOUT_BEFORE_GUARD, i.e. (OLD_NAME, NAME2) then
+ insert in BB
+
+ | RES = phi (NAME1 (on TRUE_EDGE), NAME2 (on FALSE_EDGE))"
+
+ if there is no tuple for OLD_NAME in LIVEOUT_BEFORE_GUARD, insert
+
+ | RES = phi (NAME1 (on TRUE_EDGE),
+ | DEFAULT_DEFINITION of NAME1 (on FALSE_EDGE))".
+
+ Finally register in SCOP_LIVEOUT_RENAMES (scop) the tuple
+ (OLD_NAME, RES). */
+
+static void
+insert_guard_phis (scop_p scop, basic_block bb, edge true_edge,
+ edge false_edge, htab_t liveout_before_guard)
+{
+ struct igp i;
+ i.bb = bb;
+ i.true_edge = true_edge;
+ i.false_edge = false_edge;
+ i.liveout_before_guard = liveout_before_guard;
+
+ update_ssa (TODO_update_ssa);
+ htab_traverse (SCOP_LIVEOUT_RENAMES (scop), add_guard_exit_phis, &i);
+ update_ssa (TODO_update_ssa);
+}
+
+/* Helper function for htab_traverse. */
+
+static int
+copy_renames (void **slot, void *s)
+{
+ struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
+ htab_t res = (htab_t) s;
+ tree old_name = entry->old_name;
+ tree new_name = entry->new_name;
+ struct rename_map_elt tmp;
+ PTR *x;
+
+ tmp.old_name = old_name;
+ x = htab_find_slot (res, &tmp, INSERT);
+
+ if (!*x)
+ *x = new_rename_map_elt (old_name, new_name);
+
+ return 1;
+}
+
+/* Translates a CLAST statement STMT to GCC representation in the
+ context of a SCOP.
+
+ - NEXT_E is the edge where new generated code should be attached.
+ - CONTEXT_LOOP is the loop in which the generated code will be placed
+ (might be NULL).
+ - IVSTACK contains the surrounding loops around the statement to be
+ translated.
+*/
+
+static edge
+translate_clast (scop_p scop, struct loop *context_loop,
+ struct clast_stmt *stmt, edge next_e, loop_iv_stack ivstack)
+{
+ if (!stmt)
+ return next_e;
+
+ if (CLAST_STMT_IS_A (stmt, stmt_root))
+ return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
+
+ if (CLAST_STMT_IS_A (stmt, stmt_user))
+ {
+ htab_t map;
+ CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
+ graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
+
+ if (GBB_BB (gbb) == ENTRY_BLOCK_PTR)
+ return next_e;
+
+ map = htab_create (10, rename_map_elt_info, eq_rename_map_elts, free);
+ loop_iv_stack_patch_for_consts (ivstack, (struct clast_user_stmt *) stmt);
+ build_iv_mapping (ivstack, map, gbb, scop);
+ next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), scop,
+ next_e, map);
+ htab_delete (map);
+ loop_iv_stack_remove_constants (ivstack);
+ update_ssa (TODO_update_ssa);
+ recompute_all_dominators ();
+ graphite_verify ();
+ return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
+ }
+
+ if (CLAST_STMT_IS_A (stmt, stmt_for))
+ {
+ struct loop *loop
+ = graphite_create_new_loop (scop, next_e, (struct clast_for *) stmt,
+ ivstack, context_loop ? context_loop
+ : get_loop (0));
+ edge last_e = single_exit (loop);
+
+ next_e = translate_clast (scop, loop, ((struct clast_for *) stmt)->body,
+ single_pred_edge (loop->latch), ivstack);
+ redirect_edge_succ_nodup (next_e, loop->latch);
+
+ set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
+ loop_iv_stack_pop (ivstack);
+ last_e = single_succ_edge (split_edge (last_e));
+ insert_loop_close_phis (scop, last_e->src);
+
+ recompute_all_dominators ();
+ graphite_verify ();
+ return translate_clast (scop, context_loop, stmt->next, last_e, ivstack);
+ }
+
+ if (CLAST_STMT_IS_A (stmt, stmt_guard))
+ {
+ htab_t liveout_before_guard = htab_create (10, rename_map_elt_info,
+ eq_rename_map_elts, free);
+ edge last_e = graphite_create_new_guard (scop, next_e,
+ ((struct clast_guard *) stmt),
+ ivstack);
+ edge true_e = get_true_edge_from_guard_bb (next_e->dest);
+ edge false_e = get_false_edge_from_guard_bb (next_e->dest);
+ edge exit_true_e = single_succ_edge (true_e->dest);
+ edge exit_false_e = single_succ_edge (false_e->dest);
+
+ htab_traverse (SCOP_LIVEOUT_RENAMES (scop), copy_renames,
+ liveout_before_guard);
+
+ next_e = translate_clast (scop, context_loop,
+ ((struct clast_guard *) stmt)->then,
+ true_e, ivstack);
+ insert_guard_phis (scop, last_e->src, exit_true_e, exit_false_e,
+ liveout_before_guard);
+ htab_delete (liveout_before_guard);
+ recompute_all_dominators ();
+ graphite_verify ();
+
+ return translate_clast (scop, context_loop, stmt->next, last_e, ivstack);
+ }
+
+ if (CLAST_STMT_IS_A (stmt, stmt_block))
+ {
+ next_e = translate_clast (scop, context_loop,
+ ((struct clast_block *) stmt)->body,
+ next_e, ivstack);
+ recompute_all_dominators ();
+ graphite_verify ();
+ return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
+ }
+
+ gcc_unreachable ();
+}
+
+/* Free the SCATTERING domain list. */
+
+static void
+free_scattering (CloogDomainList *scattering)
+{
+ while (scattering)
+ {
+ CloogDomain *dom = cloog_domain (scattering);
+ CloogDomainList *next = cloog_next_domain (scattering);
+
+ cloog_domain_free (dom);
+ free (scattering);
+ scattering = next;
+ }
+}
+
+/* Build cloog program for SCoP. */
+
+static void
+build_cloog_prog (scop_p scop)
+{
+ int i;
+ int max_nb_loops = scop_max_loop_depth (scop);
+ graphite_bb_p gbb;
+ CloogLoop *loop_list = NULL;
+ CloogBlockList *block_list = NULL;
+ CloogDomainList *scattering = NULL;
+ CloogProgram *prog = SCOP_PROG (scop);
+ int nbs = 2 * max_nb_loops + 1;
+ int *scaldims = (int *) xmalloc (nbs * (sizeof (int)));
+
+ cloog_program_set_nb_scattdims (prog, nbs);
+ initialize_cloog_names (scop);
+
+ for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
+ {
+ /* Build new block. */
+ CloogMatrix *domain = GBB_DOMAIN (gbb);
+ CloogStatement *stmt = cloog_statement_alloc (GBB_BB (gbb)->index);
+ CloogBlock *block = cloog_block_alloc (stmt, 0, NULL,
+ nb_loops_around_gb (gbb));
+ cloog_statement_set_usr (stmt, gbb);
+
+ /* Add empty domain to all bbs, which do not yet have a domain, as they
+ are not part of any loop. */
+ if (domain == NULL)
+ {
+ domain = cloog_matrix_alloc (0, scop_nb_params (scop) + 2);
+ GBB_DOMAIN (gbb) = domain;
+ }
+
+ /* Build loop list. */
+ {
+ CloogLoop *new_loop_list = cloog_loop_malloc ();
+ cloog_loop_set_next (new_loop_list, loop_list);
+ cloog_loop_set_domain (new_loop_list,
+ cloog_domain_matrix2domain (domain));
+ cloog_loop_set_block (new_loop_list, block);
+ loop_list = new_loop_list;
+ }
+
+ /* Build block list. */
+ {
+ CloogBlockList *new_block_list = cloog_block_list_malloc ();
+
+ cloog_block_list_set_next (new_block_list, block_list);
+ cloog_block_list_set_block (new_block_list, block);
+ block_list = new_block_list;
+ }
+
+ /* Build scattering list. */
+ {
+ /* XXX: Replace with cloog_domain_list_alloc(), when available. */
+ CloogDomainList *new_scattering
+ = (CloogDomainList *) xmalloc (sizeof (CloogDomainList));
+ CloogMatrix *scat_mat = schedule_to_scattering (gbb, nbs);
+
+ cloog_set_next_domain (new_scattering, scattering);
+ cloog_set_domain (new_scattering,
+ cloog_domain_matrix2domain (scat_mat));
+ scattering = new_scattering;
+ cloog_matrix_free (scat_mat);
+ }
+ }
+
+ cloog_program_set_loop (prog, loop_list);
+ cloog_program_set_blocklist (prog, block_list);
+
+ for (i = 0; i < nbs; i++)
+ scaldims[i] = 0 ;
+
+ cloog_program_set_scaldims (prog, scaldims);
+
+ /* Extract scalar dimensions to simplify the code generation problem. */
+ cloog_program_extract_scalars (prog, scattering);
+
+ /* Apply scattering. */
+ cloog_program_scatter (prog, scattering);
+ free_scattering (scattering);
+
+ /* Iterators corresponding to scalar dimensions have to be extracted. */
+ cloog_names_scalarize (cloog_program_names (prog), nbs,
+ cloog_program_scaldims (prog));
+
+ /* Free blocklist. */
+ {
+ CloogBlockList *next = cloog_program_blocklist (prog);
+
+ while (next)
+ {
+ CloogBlockList *toDelete = next;
+ next = cloog_block_list_next (next);
+ cloog_block_list_set_next (toDelete, NULL);
+ cloog_block_list_set_block (toDelete, NULL);
+ cloog_block_list_free (toDelete);
+ }
+ cloog_program_set_blocklist (prog, NULL);
+ }
+}
+
+/* Return the options that will be used in GLOOG. */
+
+static CloogOptions *
+set_cloog_options (void)
+{
+ CloogOptions *options = cloog_options_malloc ();
+
+ /* Change cloog output language to C. If we do use FORTRAN instead, cloog
+ will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if
+ we pass an incomplete program to cloog. */
+ options->language = LANGUAGE_C;
+
+ /* Enable complex equality spreading: removes dummy statements
+ (assignments) in the generated code which repeats the
+ substitution equations for statements. This is useless for
+ GLooG. */
+ options->esp = 1;
+
+ /* Enable C pretty-printing mode: normalizes the substitution
+ equations for statements. */
+ options->cpp = 1;
+
+ /* Allow cloog to build strides with a stride width different to one.
+ This example has stride = 4:
+
+ for (i = 0; i < 20; i += 4)
+ A */
+ options->strides = 1;
+
+ /* Disable optimizations and make cloog generate source code closer to the
+ input. This is useful for debugging, but later we want the optimized
+ code.
+
+ XXX: We can not disable optimizations, as loop blocking is not working
+ without them. */
+ if (0)
+ {
+ options->f = -1;
+ options->l = INT_MAX;
+ }
+
+ return options;
+}
+
+/* Prints STMT to STDERR. */
+
+void
+debug_clast_stmt (struct clast_stmt *stmt)
+{
+ CloogOptions *options = set_cloog_options ();
+
+ pprint (stderr, stmt, 0, options);
+}
+
+/* Find the right transform for the SCOP, and return a Cloog AST
+ representing the new form of the program. */
+
+static struct clast_stmt *
+find_transform (scop_p scop)
+{
+ struct clast_stmt *stmt;
+ CloogOptions *options = set_cloog_options ();
+
+ /* Connect new cloog prog generation to graphite. */
+ build_cloog_prog (scop);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Cloog Input [\n");
+ cloog_program_print (dump_file, SCOP_PROG(scop));
+ fprintf (dump_file, "]\n");
+ }
+
+ SCOP_PROG (scop) = cloog_program_generate (SCOP_PROG (scop), options);
+ stmt = cloog_clast_create (SCOP_PROG (scop), options);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Cloog Output[\n");
+ pprint (dump_file, stmt, 0, options);
+ cloog_program_dump_cloog (dump_file, SCOP_PROG (scop));
+ fprintf (dump_file, "]\n");
+ }
+
+ cloog_options_free (options);
+ return stmt;
+}
+
+/* Remove from the CFG the REGION. */
+
+static inline void
+remove_sese_region (sese region)
+{
+ VEC (basic_block, heap) *bbs = NULL;
+ basic_block entry_bb = SESE_ENTRY (region)->dest;
+ basic_block exit_bb = SESE_EXIT (region)->dest;
+ basic_block bb;
+ int i;
+
+ VEC_safe_push (basic_block, heap, bbs, entry_bb);
+ gather_blocks_in_sese_region (entry_bb, exit_bb, &bbs);
+
+ for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
+ delete_basic_block (bb);
+
+ VEC_free (basic_block, heap, bbs);
+}
+
+typedef struct ifsese {
+ sese region;
+ sese true_region;
+ sese false_region;
+} *ifsese;
+
+static inline edge
+if_region_entry (ifsese if_region)
+{
+ return SESE_ENTRY (if_region->region);
+}
+
+static inline edge
+if_region_exit (ifsese if_region)
+{
+ return SESE_EXIT (if_region->region);
+}
+
+static inline basic_block
+if_region_get_condition_block (ifsese if_region)
+{
+ return if_region_entry (if_region)->dest;
+}
+
+static inline void
+if_region_set_false_region (ifsese if_region, sese region)
+{
+ basic_block condition = if_region_get_condition_block (if_region);
+ edge false_edge = get_false_edge_from_guard_bb (condition);
+ basic_block dummy = false_edge->dest;
+ edge entry_region = SESE_ENTRY (region);
+ edge exit_region = SESE_EXIT (region);
+ basic_block before_region = entry_region->src;
+ basic_block last_in_region = exit_region->src;
+ void **slot = htab_find_slot_with_hash (current_loops->exits, exit_region,
+ htab_hash_pointer (exit_region),
+ NO_INSERT);
+
+ entry_region->flags = false_edge->flags;
+ false_edge->flags = exit_region->flags;
+
+ redirect_edge_pred (entry_region, condition);
+ redirect_edge_pred (exit_region, before_region);
+ redirect_edge_pred (false_edge, last_in_region);
+ redirect_edge_succ (false_edge, single_succ (dummy));
+ delete_basic_block (dummy);
+
+ exit_region->flags = EDGE_FALLTHRU;
+ recompute_all_dominators ();
+
+ SESE_EXIT (region) = false_edge;
+ if_region->false_region = region;
+
+ if (slot)
+ {
+ struct loop_exit *loop_exit = GGC_CNEW (struct loop_exit);
+
+ memcpy (loop_exit, *((struct loop_exit **) slot), sizeof (struct loop_exit));
+ htab_clear_slot (current_loops->exits, slot);
+
+ slot = htab_find_slot_with_hash (current_loops->exits, false_edge,
+ htab_hash_pointer (false_edge),
+ INSERT);
+ loop_exit->e = false_edge;
+ *slot = loop_exit;
+ false_edge->src->loop_father->exits->next = loop_exit;
+ }
+}
+
+static ifsese
+create_if_region_on_edge (edge entry, tree condition)
+{
+ edge e;
+ edge_iterator ei;
+ sese sese_region = GGC_NEW (struct sese);
+ sese true_region = GGC_NEW (struct sese);
+ sese false_region = GGC_NEW (struct sese);
+ ifsese if_region = GGC_NEW (struct ifsese);
+ edge exit = create_empty_if_region_on_edge (entry, condition);
+
+ if_region->region = sese_region;
+ if_region->region->entry = entry;
+ if_region->region->exit = exit;
+
+ FOR_EACH_EDGE (e, ei, entry->dest->succs)
+ {
+ if (e->flags & EDGE_TRUE_VALUE)
+ {
+ true_region->entry = e;
+ true_region->exit = single_succ_edge (e->dest);
+ if_region->true_region = true_region;
+ }
+ else if (e->flags & EDGE_FALSE_VALUE)
+ {
+ false_region->entry = e;
+ false_region->exit = single_succ_edge (e->dest);
+ if_region->false_region = false_region;
+ }
+ }
+
+ return if_region;
+}
+
+/* Moves REGION in a condition expression:
+ | if (1)
+ | ;
+ | else
+ | REGION;
+*/
+
+static ifsese
+move_sese_in_condition (sese region)
+{
+ basic_block pred_block = split_edge (SESE_ENTRY (region));
+ ifsese if_region = NULL;
+
+ SESE_ENTRY (region) = single_succ_edge (pred_block);
+ if_region = create_if_region_on_edge (single_pred_edge (pred_block), integer_one_node);
+ if_region_set_false_region (if_region, region);
+
+ return if_region;
+}
+
+/* Add exit phis for USE on EXIT. */
+
+static void
+scop_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e)
+{
+ gimple phi = create_phi_node (use, exit);
+
+ 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, use, true_e);
+}
+
+/* Add phi nodes for VAR that is used in LIVEIN. Phi nodes are
+ inserted in block BB. */
+
+static void
+scop_add_exit_phis_var (basic_block bb, tree var, bitmap livein,
+ edge false_e, edge true_e)
+{
+ bitmap def;
+ basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
+
+ if (is_gimple_reg (var))
+ bitmap_clear_bit (livein, def_bb->index);
+ else
+ bitmap_set_bit (livein, def_bb->index);
+
+ def = BITMAP_ALLOC (NULL);
+ bitmap_set_bit (def, def_bb->index);
+ compute_global_livein (livein, def);
+ BITMAP_FREE (def);
+
+ scop_add_exit_phis_edge (bb, var, false_e, true_e);
+}
+
+/* Insert in the block BB phi nodes for variables defined in REGION
+ and used outside the REGION. The code generation moves REGION in
+ the else clause of an "if (1)" and generates code in the then
+ clause that is at this point empty:
+
+ | if (1)
+ | empty;
+ | else
+ | REGION;
+*/
+
+static void
+scop_insert_phis_for_liveouts (sese region, basic_block bb,
+ edge false_e, edge true_e)
+{
+ unsigned i;
+ bitmap_iterator bi;
+
+ update_ssa (TODO_update_ssa);
+
+ EXECUTE_IF_SET_IN_BITMAP (SESE_LIVEOUT (region), 0, i, bi)
+ scop_add_exit_phis_var (bb, ssa_name (i), SESE_LIVEIN_VER (region, i),
+ false_e, true_e);
+
+ update_ssa (TODO_update_ssa);
+}
+
+/* Get the definition of NAME before the SCOP. Keep track of the
+ basic blocks that have been VISITED in a bitmap. */
+
+static tree
+get_vdef_before_scop (scop_p scop, tree name, sbitmap visited)
+{
+ unsigned i;
+ gimple def_stmt = SSA_NAME_DEF_STMT (name);
+ basic_block def_bb = gimple_bb (def_stmt);
+
+ if (!def_bb
+ || !bb_in_sese_p (def_bb, SCOP_REGION (scop)))
+ return name;
+
+ if (TEST_BIT (visited, def_bb->index))
+ return NULL_TREE;
+
+ SET_BIT (visited, def_bb->index);
+
+ switch (gimple_code (def_stmt))
+ {
+ case GIMPLE_PHI:
+ for (i = 0; i < gimple_phi_num_args (def_stmt); i++)
+ {
+ tree arg = gimple_phi_arg_def (def_stmt, i);
+ tree res = get_vdef_before_scop (scop, arg, visited);
+ if (res)
+ return res;
+ }
+ return NULL_TREE;
+
+ default:
+ return NULL_TREE;
+ }
+}
+
+/* Adjust a virtual phi node PHI that is placed at the end of the
+ generated code for SCOP:
+
+ | if (1)
+ | generated code from REGION;
+ | else
+ | REGION;
+
+ The FALSE_E edge comes from the original code, TRUE_E edge comes
+ from the code generated for the SCOP. */
+
+static void
+scop_adjust_vphi (scop_p scop, gimple phi, edge true_e)
+{
+ unsigned i;
+
+ gcc_assert (gimple_phi_num_args (phi) == 2);
+
+ for (i = 0; i < gimple_phi_num_args (phi); i++)
+ if (gimple_phi_arg_edge (phi, i) == true_e)
+ {
+ tree true_arg, false_arg, before_scop_arg;
+ sbitmap visited;
+
+ true_arg = gimple_phi_arg_def (phi, i);
+ if (!SSA_NAME_IS_DEFAULT_DEF (true_arg))
+ return;
+
+ false_arg = gimple_phi_arg_def (phi, i == 0 ? 1 : 0);
+ if (SSA_NAME_IS_DEFAULT_DEF (false_arg))
+ return;
+
+ visited = sbitmap_alloc (last_basic_block);
+ sbitmap_zero (visited);
+ before_scop_arg = get_vdef_before_scop (scop, false_arg, visited);
+ gcc_assert (before_scop_arg != NULL_TREE);
+ SET_PHI_ARG_DEF (phi, i, before_scop_arg);
+ sbitmap_free (visited);
+ }
+}
+
+/* Adjusts the phi nodes in the block BB for variables defined in
+ SCOP_REGION and used outside the SCOP_REGION. The code generation
+ moves SCOP_REGION in the else clause of an "if (1)" and generates
+ code in the then clause:
+
+ | if (1)
+ | generated code from REGION;
+ | else
+ | REGION;
+
+ To adjust the phi nodes after the condition, SCOP_LIVEOUT_RENAMES
+ hash table is used: this stores for a name that is part of the
+ LIVEOUT of SCOP_REGION its new name in the generated code. */
+
+static void
+scop_adjust_phis_for_liveouts (scop_p scop, basic_block bb, edge false_e,
+ edge true_e)
+{
+ gimple_stmt_iterator si;
+
+ for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
+ {
+ unsigned i;
+ unsigned false_i = 0;
+ gimple phi = gsi_stmt (si);
+
+ if (!is_gimple_reg (PHI_RESULT (phi)))
+ {
+ scop_adjust_vphi (scop, phi, true_e);
+ continue;
+ }
+
+ for (i = 0; i < gimple_phi_num_args (phi); i++)
+ if (gimple_phi_arg_edge (phi, i) == false_e)
+ {
+ false_i = i;
+ break;
+ }
+
+ for (i = 0; i < gimple_phi_num_args (phi); i++)
+ if (gimple_phi_arg_edge (phi, i) == true_e)
+ {
+ tree old_name = gimple_phi_arg_def (phi, false_i);
+ tree new_name = get_new_name_from_old_name
+ (SCOP_LIVEOUT_RENAMES (scop), old_name);
+
+ gcc_assert (old_name != new_name);
+ SET_PHI_ARG_DEF (phi, i, new_name);
+ }
+ }
+}
+
+/* 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. Return true if code generation succeeded. */
+
+static bool
+gloog (scop_p scop, struct clast_stmt *stmt)
+{
+ edge new_scop_exit_edge = NULL;
+ VEC (iv_stack_entry_p, heap) *ivstack = VEC_alloc (iv_stack_entry_p, heap,
+ 10);
+ loop_p context_loop;
+ ifsese if_region = NULL;
+
+ recompute_all_dominators ();
+ graphite_verify ();
+ if_region = move_sese_in_condition (SCOP_REGION (scop));
+ sese_build_livein_liveouts (SCOP_REGION (scop));
+ scop_insert_phis_for_liveouts (SCOP_REGION (scop),
+ if_region->region->exit->src,
+ if_region->false_region->exit,
+ if_region->true_region->exit);
+ recompute_all_dominators ();
+ 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);
+ free_loop_iv_stack (&ivstack);
+ cloog_clast_free (stmt);
+
+ graphite_verify ();
+ scop_adjust_phis_for_liveouts (scop,
+ if_region->region->exit->src,
+ if_region->false_region->exit,
+ if_region->true_region->exit);
+
+ recompute_all_dominators ();
+ graphite_verify ();
+ return true;
+}
+
+/* Returns the number of data references in SCOP. */
+
+static int
+nb_data_refs_in_scop (scop_p scop)
+{
+ int i;
+ graphite_bb_p gbb;
+ int res = 0;
+
+ for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
+ res += VEC_length (data_reference_p, GBB_DATA_REFS (gbb));
+
+ return res;
+}
+
+/* Move the loop at index LOOP and insert it before index NEW_LOOP_POS.
+ This transformartion is only valid, if the loop nest between i and k is
+ perfectly nested. Therefore we do not need to change the static schedule.
+
+ Example:
+
+ for (i = 0; i < 50; i++)
+ for (j ...)
+ for (k = 5; k < 100; k++)
+ A
+
+ To move k before i use:
+
+ graphite_trans_bb_move_loop (A, 2, 0)
+
+ for (k = 5; k < 100; k++)
+ for (i = 0; i < 50; i++)
+ for (j ...)
+ A
+
+ And to move k back:
+
+ graphite_trans_bb_move_loop (A, 0, 2)
+
+ This function does not check the validity of interchanging loops.
+ This should be checked before calling this function. */
+
+static void
+graphite_trans_bb_move_loop (graphite_bb_p gb, int loop,
+ int new_loop_pos)
+{
+ CloogMatrix *domain = GBB_DOMAIN (gb);
+ int row, j;
+ loop_p tmp_loop_p;
+
+ gcc_assert (loop < gbb_nb_loops (gb)
+ && new_loop_pos < gbb_nb_loops (gb));
+
+ /* Update LOOPS vector. */
+ tmp_loop_p = VEC_index (loop_p, GBB_LOOPS (gb), loop);
+ VEC_ordered_remove (loop_p, GBB_LOOPS (gb), loop);
+ VEC_safe_insert (loop_p, heap, GBB_LOOPS (gb), new_loop_pos, tmp_loop_p);
+
+ /* Move the domain columns. */
+ if (loop < new_loop_pos)
+ for (row = 0; row < domain->NbRows; row++)
+ {
+ Value tmp;
+ value_init (tmp);
+ value_assign (tmp, domain->p[row][loop + 1]);
+
+ for (j = loop ; j < new_loop_pos - 1; j++)
+ value_assign (domain->p[row][j + 1], domain->p[row][j + 2]);
+
+ value_assign (domain->p[row][new_loop_pos], tmp);
+ value_clear (tmp);
+ }
+ else
+ for (row = 0; row < domain->NbRows; row++)
+ {
+ Value tmp;
+ value_init (tmp);
+ value_assign (tmp, domain->p[row][loop + 1]);
+
+ for (j = loop ; j > new_loop_pos; j--)
+ value_assign (domain->p[row][j + 1], domain->p[row][j]);
+
+ value_assign (domain->p[row][new_loop_pos + 1], tmp);
+ value_clear (tmp);
+ }
+}
+
+/* Get the index of the column representing constants in the DOMAIN
+ matrix. */
+
+static int
+const_column_index (CloogMatrix *domain)
+{
+ return domain->NbColumns - 1;
+}
+
+
+/* Get the first index that is positive or negative, determined
+ following the value of POSITIVE, in matrix DOMAIN in COLUMN. */
+
+static int
+get_first_matching_sign_row_index (CloogMatrix *domain, int column,
+ bool positive)
+{
+ int row;
+
+ for (row = 0; row < domain->NbRows; row++)
+ {
+ int val = value_get_si (domain->p[row][column]);
+
+ if (val > 0 && positive)
+ return row;
+
+ else if (val < 0 && !positive)
+ return row;
+ }
+
+ gcc_unreachable ();
+}
+
+/* Get the lower bound of COLUMN in matrix DOMAIN. */
+
+static int
+get_lower_bound_row (CloogMatrix *domain, int column)
+{
+ return get_first_matching_sign_row_index (domain, column, true);
+}
+
+/* Get the upper bound of COLUMN in matrix DOMAIN. */
+
+static int
+get_upper_bound_row (CloogMatrix *domain, int column)
+{
+ return get_first_matching_sign_row_index (domain, column, false);
+}
+
+/* Copies the OLD_ROW constraint from OLD_DOMAIN to the NEW_DOMAIN at
+ row NEW_ROW. */
+
+static void
+copy_constraint (CloogMatrix *old_domain, CloogMatrix *new_domain,
+ int old_row, int new_row)
+{
+ int i;
+
+ gcc_assert (old_domain->NbColumns == new_domain->NbColumns
+ && old_row < old_domain->NbRows
+ && new_row < new_domain->NbRows);
+
+ for (i = 0; i < old_domain->NbColumns; i++)
+ value_assign (new_domain->p[new_row][i], old_domain->p[old_row][i]);
+}
+
+/* Swap coefficients of variables X and Y on row R. */
+
+static void
+swap_constraint_variables (CloogMatrix *domain,
+ int r, int x, int y)
+{
+ value_swap (domain->p[r][x], domain->p[r][y]);
+}
+
+/* Scale by X the coefficient C of constraint at row R in DOMAIN. */
+
+static void
+scale_constraint_variable (CloogMatrix *domain,
+ int r, int c, int x)
+{
+ Value strip_size_value;
+ value_init (strip_size_value);
+ value_set_si (strip_size_value, x);
+ value_multiply (domain->p[r][c], domain->p[r][c], strip_size_value);
+ value_clear (strip_size_value);
+}
+
+/* Strip mines the loop of BB at the position LOOP_DEPTH with STRIDE.
+ Always valid, but not always a performance improvement. */
+
+static void
+graphite_trans_bb_strip_mine (graphite_bb_p gb, int loop_depth, int stride)
+{
+ int row, col;
+
+ CloogMatrix *domain = GBB_DOMAIN (gb);
+ CloogMatrix *new_domain = cloog_matrix_alloc (domain->NbRows + 3,
+ domain->NbColumns + 1);
+
+ int col_loop_old = loop_depth + 2;
+ int col_loop_strip = col_loop_old - 1;
+
+ gcc_assert (loop_depth <= gbb_nb_loops (gb) - 1);
+
+ VEC_safe_insert (loop_p, heap, GBB_LOOPS (gb), loop_depth, NULL);
+
+ GBB_DOMAIN (gb) = new_domain;
+
+ for (row = 0; row < domain->NbRows; row++)
+ for (col = 0; col < domain->NbColumns; col++)
+ if (col <= loop_depth)
+ value_assign (new_domain->p[row][col], domain->p[row][col]);
+ else
+ value_assign (new_domain->p[row][col + 1], domain->p[row][col]);
+
+ row = domain->NbRows;
+
+ /* Lower bound of the outer stripped loop. */
+ copy_constraint (new_domain, new_domain,
+ get_lower_bound_row (new_domain, col_loop_old), row);
+ swap_constraint_variables (new_domain, row, col_loop_old, col_loop_strip);
+ row++;
+
+ /* Upper bound of the outer stripped loop. */
+ copy_constraint (new_domain, new_domain,
+ get_upper_bound_row (new_domain, col_loop_old), row);
+ swap_constraint_variables (new_domain, row, col_loop_old, col_loop_strip);
+ scale_constraint_variable (new_domain, row, col_loop_strip, stride);
+ row++;
+
+ /* Lower bound of a tile starts at "stride * outer_iv". */
+ row = get_lower_bound_row (new_domain, col_loop_old);
+ value_set_si (new_domain->p[row][0], 1);
+ value_set_si (new_domain->p[row][const_column_index (new_domain)], 0);
+ value_set_si (new_domain->p[row][col_loop_old], 1);
+ value_set_si (new_domain->p[row][col_loop_strip], -1 * stride);
+
+ /* Upper bound of a tile stops at "stride * outer_iv + stride - 1",
+ or at the old upper bound that is not modified. */
+ row = new_domain->NbRows - 1;
+ value_set_si (new_domain->p[row][0], 1);
+ value_set_si (new_domain->p[row][col_loop_old], -1);
+ value_set_si (new_domain->p[row][col_loop_strip], stride);
+ value_set_si (new_domain->p[row][const_column_index (new_domain)],
+ stride - 1);
+
+ cloog_matrix_free (domain);
+
+ /* Update static schedule. */
+ {
+ int i;
+ int nb_loops = gbb_nb_loops (gb);
+ lambda_vector new_schedule = lambda_vector_new (nb_loops + 1);
+
+ for (i = 0; i <= loop_depth; i++)
+ new_schedule[i] = GBB_STATIC_SCHEDULE (gb)[i];
+
+ for (i = loop_depth + 1; i <= nb_loops - 2; i++)
+ new_schedule[i + 2] = GBB_STATIC_SCHEDULE (gb)[i];
+
+ GBB_STATIC_SCHEDULE (gb) = new_schedule;
+ }
+}
+
+/* Returns true when the strip mining of LOOP_INDEX by STRIDE is
+ profitable or undecidable. GB is the statement around which the
+ loops will be strip mined. */
+
+static bool
+strip_mine_profitable_p (graphite_bb_p gb, int stride,
+ int loop_index)
+{
+ bool res = true;
+ edge exit = NULL;
+ tree niter;
+ loop_p loop;
+ long niter_val;
+
+ loop = VEC_index (loop_p, GBB_LOOPS (gb), loop_index);
+ exit = single_exit (loop);
+
+ niter = find_loop_niter (loop, &exit);
+ if (niter == chrec_dont_know
+ || TREE_CODE (niter) != INTEGER_CST)
+ return true;
+
+ niter_val = int_cst_value (niter);
+
+ if (niter_val < stride)
+ {
+ res = false;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "\nStrip Mining is not profitable for loop %d:",
+ loop->num);
+ fprintf (dump_file, "number of iterations is too low.\n");
+ }
+ }
+
+ return res;
+}
+
+/* Determines when the interchange of LOOP_A and LOOP_B belonging to
+ SCOP is legal. DEPTH is the number of loops around. */
+
+static bool
+is_interchange_valid (scop_p scop, int loop_a, int loop_b, int depth)
+{
+ bool res;
+ VEC (ddr_p, heap) *dependence_relations;
+ VEC (data_reference_p, heap) *datarefs;
+
+ struct loop *nest = VEC_index (loop_p, SCOP_LOOP_NEST (scop), loop_a);
+ lambda_trans_matrix trans;
+
+ gcc_assert (loop_a < loop_b);
+
+ dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10);
+ datarefs = VEC_alloc (data_reference_p, heap, 10);
+
+ if (!compute_data_dependences_for_loop (nest, true, &datarefs,
+ &dependence_relations))
+ return false;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ dump_ddrs (dump_file, dependence_relations);
+
+ trans = lambda_trans_matrix_new (depth, depth);
+ lambda_matrix_id (LTM_MATRIX (trans), depth);
+
+ lambda_matrix_row_exchange (LTM_MATRIX (trans), 0, loop_b - loop_a);
+
+ if (!lambda_transform_legal_p (trans, depth, dependence_relations))
+ {
+ lambda_matrix_row_exchange (LTM_MATRIX (trans), 0, loop_b - loop_a);
+ res = false;
+ }
+ else
+ res = true;
+
+ free_dependence_relations (dependence_relations);
+ free_data_refs (datarefs);
+ return res;
+}
+
+/* Loop block the LOOPS innermost loops of GB with stride size STRIDE.
+
+ Example
+
+ for (i = 0; i <= 50; i++=4)
+ for (k = 0; k <= 100; k++=4)
+ for (l = 0; l <= 200; l++=4)
+ A
+
+ To strip mine the two inner most loops with stride = 4 call:
+
+ graphite_trans_bb_block (A, 4, 2)
+
+ for (i = 0; i <= 50; i++)
+ for (kk = 0; kk <= 100; kk+=4)
+ for (ll = 0; ll <= 200; ll+=4)
+ for (k = kk; k <= min (100, kk + 3); k++)
+ for (l = ll; l <= min (200, ll + 3); l++)
+ A
+*/
+
+static bool
+graphite_trans_bb_block (graphite_bb_p gb, int stride, int loops)
+{
+ int i, j;
+ int nb_loops = gbb_nb_loops (gb);
+ int start = nb_loops - loops;
+ scop_p scop = GBB_SCOP (gb);
+
+ gcc_assert (scop_contains_loop (scop, gbb_loop (gb)));
+
+ for (i = start ; i < nb_loops; i++)
+ for (j = i + 1; j < nb_loops; j++)
+ if (!is_interchange_valid (scop, i, j, nb_loops))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file,
+ "\nInterchange not valid for loops %d and %d:\n", i, j);
+ return false;
+ }
+ else if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file,
+ "\nInterchange valid for loops %d and %d:\n", i, j);
+
+ /* Check if strip mining is profitable for every loop. */
+ for (i = 0; i < nb_loops - start; i++)
+ if (!strip_mine_profitable_p (gb, stride, start + i))
+ return false;
+
+ /* Strip mine loops. */
+ for (i = 0; i < nb_loops - start; i++)
+ graphite_trans_bb_strip_mine (gb, start + 2 * i, stride);
+
+ /* Interchange loops. */
+ for (i = 1; i < nb_loops - start; i++)
+ graphite_trans_bb_move_loop (gb, start + 2 * i, start + i);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "\nLoops containing BB %d will be loop blocked.\n",
+ GBB_BB (gb)->index);
+
+ return true;
+}
+
+/* Loop block LOOPS innermost loops of a loop nest. BBS represent the
+ basic blocks that belong to the loop nest to be blocked. */
+
+static bool
+graphite_trans_loop_block (VEC (graphite_bb_p, heap) *bbs, int loops)
+{
+ graphite_bb_p gb;
+ int i;
+ bool transform_done = false;
+
+ /* TODO: - Calculate the stride size automatically. */
+ int stride_size = 51;
+
+ for (i = 0; VEC_iterate (graphite_bb_p, bbs, i, gb); i++)
+ transform_done |= graphite_trans_bb_block (gb, stride_size, loops);
+
+ return transform_done;
+}
+
+/* Loop block all basic blocks of SCOP. Return false when the
+ transform is not performed. */
+
+static bool
+graphite_trans_scop_block (scop_p scop)
+{
+ graphite_bb_p gb;
+ int i, j;
+ int last_nb_loops;
+ int nb_loops;
+ bool perfect = true;
+ bool transform_done = false;
+
+ VEC (graphite_bb_p, heap) *bbs = VEC_alloc (graphite_bb_p, heap, 3);
+ int max_schedule = scop_max_loop_depth (scop) + 1;
+ lambda_vector last_schedule = lambda_vector_new (max_schedule);
+
+ if (VEC_length (graphite_bb_p, SCOP_BBS (scop)) == 0)
+ return false;
+
+ /* Get the data of the first bb. */
+ gb = VEC_index (graphite_bb_p, SCOP_BBS (scop), 0);
+ last_nb_loops = gbb_nb_loops (gb);
+ lambda_vector_copy (GBB_STATIC_SCHEDULE (gb), last_schedule,
+ last_nb_loops + 1);
+ VEC_safe_push (graphite_bb_p, heap, bbs, gb);
+
+ for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
+ {
+ /* We did the first bb before. */
+ if (i == 0)
+ continue;
+
+ nb_loops = gbb_nb_loops (gb);
+
+ /* If the number of loops is unchanged and only the last element of the
+ schedule changes, we stay in the loop nest. */
+ if (nb_loops == last_nb_loops
+ && (last_schedule [nb_loops + 1]
+ != GBB_STATIC_SCHEDULE (gb)[nb_loops + 1]))
+ {
+ VEC_safe_push (graphite_bb_p, heap, bbs, gb);
+ continue;
+ }
+
+ /* Otherwise, we left the innermost loop. So check, if the last bb was in
+ a perfect loop nest and how many loops are contained in this perfect
+ loop nest.
+
+ Count the number of zeros from the end of the schedule. They are the
+ number of surrounding loops.
+
+ Example:
+ last_bb 2 3 2 0 0 0 0 3
+ bb 2 4 0
+ <------ j = 4
+
+ last_bb 2 3 2 0 0 0 0 3
+ bb 2 3 2 0 1
+ <-- j = 2
+
+ If there is no zero, there were other bbs in outer loops and the loop
+ nest is not perfect. */
+ for (j = last_nb_loops - 1; j >= 0; j--)
+ {
+ if (last_schedule [j] != 0
+ || (j <= nb_loops && GBB_STATIC_SCHEDULE (gb)[j] == 1))
+ {
+ j--;
+ break;
+ }
+ }
+
+ j++;
+
+ /* Found perfect loop nest. */
+ if (perfect && last_nb_loops - j >= 2)
+ transform_done |= graphite_trans_loop_block (bbs, last_nb_loops - j);
+
+ /* Check if we start with a new loop.
+
+ Example:
+
+ last_bb 2 3 2 0 0 0 0 3
+ bb 2 3 2 0 0 1 0
+
+ Here we start with the loop "2 3 2 0 0 1"
+
+ last_bb 2 3 2 0 0 0 0 3
+ bb 2 3 2 0 0 1
+
+ But here not, so the loop nest can never be perfect. */
+
+ perfect = (GBB_STATIC_SCHEDULE (gb)[nb_loops] == 0);
+
+ /* Update the last_bb infos. We do not do that for the bbs in the same
+ loop, as the data we use is not changed. */
+ last_nb_loops = nb_loops;
+ lambda_vector_copy (GBB_STATIC_SCHEDULE (gb), last_schedule,
+ nb_loops + 1);
+ VEC_truncate (graphite_bb_p, bbs, 0);
+ VEC_safe_push (graphite_bb_p, heap, bbs, gb);
+ }
+
+ /* Check if the last loop nest was perfect. It is the same check as above,
+ but the comparison with the next bb is missing. */
+ for (j = last_nb_loops - 1; j >= 0; j--)
+ if (last_schedule [j] != 0)
+ {
+ j--;
+ break;
+ }
+
+ j++;
+
+ /* Found perfect loop nest. */
+ if (last_nb_loops - j >= 2)
+ transform_done |= graphite_trans_loop_block (bbs, last_nb_loops - j);
+ VEC_free (graphite_bb_p, heap, bbs);
+
+ return transform_done;
+}
+
+/* Apply graphite transformations to all the basic blocks of SCOP. */
+
+static bool
+graphite_apply_transformations (scop_p scop)
+{
+ bool transform_done = false;
+
+ /* Sort the list of bbs. Keep them always sorted. */
+ graphite_sort_gbbs (scop);
+
+ if (flag_loop_block)
+ transform_done = graphite_trans_scop_block (scop);
+
+ /* Generate code even if we did not apply any real transformation.
+ This also allows to check the performance for the identity
+ transformation: GIMPLE -> GRAPHITE -> GIMPLE
+ Keep in mind that CLooG optimizes in control, so the loop structure
+ may change, even if we only use -fgraphite-identity. */
+ if (flag_graphite_identity)
+ transform_done = true;
+
+ return transform_done;
+}
+
+/* We limit all SCoPs to SCoPs, that are completely surrounded by a loop.
+
+ Example:
+
+ for (i |
+ { |
+ for (j | SCoP 1
+ for (k |
+ } |
+
+ * SCoP frontier, as this line is not surrounded by any loop. *
+
+ for (l | SCoP 2
+
+ This is necessary as scalar evolution and parameter detection need a
+ outermost loop to initialize parameters correctly.
+
+ TODO: FIX scalar evolution and parameter detection to allow more flexible
+ SCoP frontiers. */
+
+static void
+limit_scops (void)
+{
+ VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
+
+ int i;
+ scop_p scop;
+
+ for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
+ {
+ int j;
+ loop_p loop;
+ build_scop_bbs (scop);
+
+ if (!build_scop_loop_nests (scop))
+ continue;
+
+ for (j = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), j, loop); j++)
+ if (!loop_in_sese_p (loop_outer (loop), SCOP_REGION (scop)))
+ {
+ sd_region open_scop;
+ open_scop.entry = loop->header;
+ open_scop.exit = single_exit (loop)->dest;
+ VEC_safe_push (sd_region, heap, tmp_scops, &open_scop);
+ }
+ }
+
+ free_scops (current_scops);
+ current_scops = VEC_alloc (scop_p, heap, 3);
+
+ create_sese_edges (tmp_scops);
+ build_graphite_scops (tmp_scops);
+ VEC_free (sd_region, heap, tmp_scops);
+}
+
+/* Perform a set of linear transforms on the loops of the current
+ function. */
+
+void
+graphite_transform_loops (void)
+{
+ int i;
+ scop_p scop;
+ bool transform_done = false;
+
+ if (number_of_loops () <= 1)
+ return;
+
+ current_scops = VEC_alloc (scop_p, heap, 3);
+ recompute_all_dominators ();
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Graphite loop transformations \n");
+
+ initialize_original_copy_tables ();
+ cloog_initialize ();
+ build_scops ();
+ limit_scops ();
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "\nnumber of SCoPs: %d\n",
+ VEC_length (scop_p, current_scops));
+
+ for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
+ {
+ build_scop_bbs (scop);
+ if (!build_scop_loop_nests (scop))
+ continue;
+
+ build_bb_loops (scop);
+
+ if (!build_scop_conditions (scop))
+ continue;
+
+ find_scop_parameters (scop);
+ build_scop_context (scop);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "\n(In SCoP %d:\n", i);
+ fprintf (dump_file, "\nnumber of bbs: %d\n",
+ VEC_length (graphite_bb_p, SCOP_BBS (scop)));
+ fprintf (dump_file, "\nnumber of loops: %d)\n",
+ VEC_length (loop_p, SCOP_LOOP_NEST (scop)));
+ }
+
+ if (!build_scop_iteration_domain (scop))
+ continue;
+
+ add_conditions_to_constraints (scop);
+ build_scop_canonical_schedules (scop);
+
+ build_scop_data_accesses (scop);
+ build_scop_dynamic_schedules (scop);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ int nbrefs = nb_data_refs_in_scop (scop);
+ fprintf (dump_file, "\nnumber of data refs: %d\n", nbrefs);
+ }
+
+ if (graphite_apply_transformations (scop))
+ transform_done = gloog (scop, find_transform (scop));
+#ifdef ENABLE_CHECKING
+ else
+ {
+ struct clast_stmt *stmt = find_transform (scop);
+ cloog_clast_free (stmt);
+ }
+#endif
+ }
+
+ /* Cleanup. */
+ if (transform_done)
+ cleanup_tree_cfg ();
+
+ free_scops (current_scops);
+ cloog_finalize ();
+ free_original_copy_tables ();
+}
+
+#else /* If Cloog is not available: #ifndef HAVE_cloog. */
+
+void
+graphite_transform_loops (void)
+{
+ sorry ("Graphite loop optimizations cannot be used");
+}
+
+#endif