Google Git
Sign in
gnu / gcc / cd99b30c7cf1e68ef76ed2af7a41ac74c78116fe / . / gcc / graphite.c
blob: b732b40d214053a56fbad7106a6aefd49af90556 [file] [log] [blame]
/* 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);
}
/* 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);
}
/* 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);
}
/* 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);
}
/* 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;
}
/* 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:
{