/* Gimple Represented as Polyhedra.
|
/* Gimple Represented as Polyhedra.
|
Copyright (C) 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
|
Copyright (C) 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
|
Contributed by Sebastian Pop <sebastian.pop@inria.fr>.
|
Contributed by Sebastian Pop <sebastian.pop@inria.fr>.
|
|
|
This file is part of GCC.
|
This file is part of GCC.
|
|
|
GCC is free software; you can redistribute it and/or modify
|
GCC is free software; you can redistribute it and/or modify
|
it under the terms of the GNU General Public License as published by
|
it under the terms of the GNU General Public License as published by
|
the Free Software Foundation; either version 3, or (at your option)
|
the Free Software Foundation; either version 3, or (at your option)
|
any later version.
|
any later version.
|
|
|
GCC is distributed in the hope that it will be useful,
|
GCC is distributed in the hope that it will be useful,
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
GNU General Public License for more details.
|
GNU General Public License for more details.
|
|
|
You should have received a copy of the GNU General Public License
|
You should have received a copy of the GNU General Public License
|
along with GCC; see the file COPYING3. If not see
|
along with GCC; see the file COPYING3. If not see
|
<http://www.gnu.org/licenses/>. */
|
<http://www.gnu.org/licenses/>. */
|
|
|
/* This pass converts GIMPLE to GRAPHITE, performs some loop
|
/* This pass converts GIMPLE to GRAPHITE, performs some loop
|
transformations and then converts the resulting representation back
|
transformations and then converts the resulting representation back
|
to GIMPLE.
|
to GIMPLE.
|
|
|
An early description of this pass can be found in the GCC Summit'06
|
An early description of this pass can be found in the GCC Summit'06
|
paper "GRAPHITE: Polyhedral Analyses and Optimizations for GCC".
|
paper "GRAPHITE: Polyhedral Analyses and Optimizations for GCC".
|
The wiki page http://gcc.gnu.org/wiki/Graphite contains pointers to
|
The wiki page http://gcc.gnu.org/wiki/Graphite contains pointers to
|
the related work.
|
the related work.
|
|
|
One important document to read is CLooG's internal manual:
|
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
|
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
|
that describes the data structure of loops used in this file, and
|
the functions that are used for transforming the code. */
|
the functions that are used for transforming the code. */
|
|
|
#include "config.h"
|
#include "config.h"
|
#include "system.h"
|
#include "system.h"
|
#include "coretypes.h"
|
#include "coretypes.h"
|
#include "tm.h"
|
#include "tm.h"
|
#include "ggc.h"
|
#include "ggc.h"
|
#include "tree.h"
|
#include "tree.h"
|
#include "rtl.h"
|
#include "rtl.h"
|
#include "basic-block.h"
|
#include "basic-block.h"
|
#include "diagnostic.h"
|
#include "diagnostic.h"
|
#include "tree-flow.h"
|
#include "tree-flow.h"
|
#include "toplev.h"
|
#include "toplev.h"
|
#include "tree-dump.h"
|
#include "tree-dump.h"
|
#include "timevar.h"
|
#include "timevar.h"
|
#include "cfgloop.h"
|
#include "cfgloop.h"
|
#include "tree-chrec.h"
|
#include "tree-chrec.h"
|
#include "tree-data-ref.h"
|
#include "tree-data-ref.h"
|
#include "tree-scalar-evolution.h"
|
#include "tree-scalar-evolution.h"
|
#include "tree-pass.h"
|
#include "tree-pass.h"
|
#include "value-prof.h"
|
#include "value-prof.h"
|
#include "pointer-set.h"
|
#include "pointer-set.h"
|
#include "gimple.h"
|
#include "gimple.h"
|
#include "sese.h"
|
#include "sese.h"
|
#include "predict.h"
|
#include "predict.h"
|
|
|
#ifdef HAVE_cloog
|
#ifdef HAVE_cloog
|
|
|
#include "cloog/cloog.h"
|
#include "cloog/cloog.h"
|
#include "ppl_c.h"
|
#include "ppl_c.h"
|
#include "graphite-ppl.h"
|
#include "graphite-ppl.h"
|
#include "graphite.h"
|
#include "graphite.h"
|
#include "graphite-poly.h"
|
#include "graphite-poly.h"
|
#include "graphite-scop-detection.h"
|
#include "graphite-scop-detection.h"
|
#include "graphite-clast-to-gimple.h"
|
#include "graphite-clast-to-gimple.h"
|
#include "graphite-sese-to-poly.h"
|
#include "graphite-sese-to-poly.h"
|
|
|
/* Print global statistics to FILE. */
|
/* Print global statistics to FILE. */
|
|
|
static void
|
static void
|
print_global_statistics (FILE* file)
|
print_global_statistics (FILE* file)
|
{
|
{
|
long n_bbs = 0;
|
long n_bbs = 0;
|
long n_loops = 0;
|
long n_loops = 0;
|
long n_stmts = 0;
|
long n_stmts = 0;
|
long n_conditions = 0;
|
long n_conditions = 0;
|
long n_p_bbs = 0;
|
long n_p_bbs = 0;
|
long n_p_loops = 0;
|
long n_p_loops = 0;
|
long n_p_stmts = 0;
|
long n_p_stmts = 0;
|
long n_p_conditions = 0;
|
long n_p_conditions = 0;
|
|
|
basic_block bb;
|
basic_block bb;
|
|
|
FOR_ALL_BB (bb)
|
FOR_ALL_BB (bb)
|
{
|
{
|
gimple_stmt_iterator psi;
|
gimple_stmt_iterator psi;
|
|
|
n_bbs++;
|
n_bbs++;
|
n_p_bbs += bb->count;
|
n_p_bbs += bb->count;
|
|
|
/* Ignore artificial surrounding loop. */
|
/* Ignore artificial surrounding loop. */
|
if (bb == bb->loop_father->header
|
if (bb == bb->loop_father->header
|
&& bb->index != 0)
|
&& bb->index != 0)
|
{
|
{
|
n_loops++;
|
n_loops++;
|
n_p_loops += bb->count;
|
n_p_loops += bb->count;
|
}
|
}
|
|
|
if (VEC_length (edge, bb->succs) > 1)
|
if (VEC_length (edge, bb->succs) > 1)
|
{
|
{
|
n_conditions++;
|
n_conditions++;
|
n_p_conditions += bb->count;
|
n_p_conditions += bb->count;
|
}
|
}
|
|
|
for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
|
for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
|
{
|
{
|
n_stmts++;
|
n_stmts++;
|
n_p_stmts += bb->count;
|
n_p_stmts += bb->count;
|
}
|
}
|
}
|
}
|
|
|
fprintf (file, "\nGlobal statistics (");
|
fprintf (file, "\nGlobal statistics (");
|
fprintf (file, "BBS:%ld, ", n_bbs);
|
fprintf (file, "BBS:%ld, ", n_bbs);
|
fprintf (file, "LOOPS:%ld, ", n_loops);
|
fprintf (file, "LOOPS:%ld, ", n_loops);
|
fprintf (file, "CONDITIONS:%ld, ", n_conditions);
|
fprintf (file, "CONDITIONS:%ld, ", n_conditions);
|
fprintf (file, "STMTS:%ld)\n", n_stmts);
|
fprintf (file, "STMTS:%ld)\n", n_stmts);
|
fprintf (file, "\nGlobal profiling statistics (");
|
fprintf (file, "\nGlobal profiling statistics (");
|
fprintf (file, "BBS:%ld, ", n_p_bbs);
|
fprintf (file, "BBS:%ld, ", n_p_bbs);
|
fprintf (file, "LOOPS:%ld, ", n_p_loops);
|
fprintf (file, "LOOPS:%ld, ", n_p_loops);
|
fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
|
fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
|
fprintf (file, "STMTS:%ld)\n", n_p_stmts);
|
fprintf (file, "STMTS:%ld)\n", n_p_stmts);
|
}
|
}
|
|
|
/* Print statistics for SCOP to FILE. */
|
/* Print statistics for SCOP to FILE. */
|
|
|
static void
|
static void
|
print_graphite_scop_statistics (FILE* file, scop_p scop)
|
print_graphite_scop_statistics (FILE* file, scop_p scop)
|
{
|
{
|
long n_bbs = 0;
|
long n_bbs = 0;
|
long n_loops = 0;
|
long n_loops = 0;
|
long n_stmts = 0;
|
long n_stmts = 0;
|
long n_conditions = 0;
|
long n_conditions = 0;
|
long n_p_bbs = 0;
|
long n_p_bbs = 0;
|
long n_p_loops = 0;
|
long n_p_loops = 0;
|
long n_p_stmts = 0;
|
long n_p_stmts = 0;
|
long n_p_conditions = 0;
|
long n_p_conditions = 0;
|
|
|
basic_block bb;
|
basic_block bb;
|
|
|
FOR_ALL_BB (bb)
|
FOR_ALL_BB (bb)
|
{
|
{
|
gimple_stmt_iterator psi;
|
gimple_stmt_iterator psi;
|
loop_p loop = bb->loop_father;
|
loop_p loop = bb->loop_father;
|
|
|
if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
|
if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
|
continue;
|
continue;
|
|
|
n_bbs++;
|
n_bbs++;
|
n_p_bbs += bb->count;
|
n_p_bbs += bb->count;
|
|
|
if (VEC_length (edge, bb->succs) > 1)
|
if (VEC_length (edge, bb->succs) > 1)
|
{
|
{
|
n_conditions++;
|
n_conditions++;
|
n_p_conditions += bb->count;
|
n_p_conditions += bb->count;
|
}
|
}
|
|
|
for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
|
for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
|
{
|
{
|
n_stmts++;
|
n_stmts++;
|
n_p_stmts += bb->count;
|
n_p_stmts += bb->count;
|
}
|
}
|
|
|
if (loop->header == bb && loop_in_sese_p (loop, SCOP_REGION (scop)))
|
if (loop->header == bb && loop_in_sese_p (loop, SCOP_REGION (scop)))
|
{
|
{
|
n_loops++;
|
n_loops++;
|
n_p_loops += bb->count;
|
n_p_loops += bb->count;
|
}
|
}
|
}
|
}
|
|
|
fprintf (file, "\nSCoP statistics (");
|
fprintf (file, "\nSCoP statistics (");
|
fprintf (file, "BBS:%ld, ", n_bbs);
|
fprintf (file, "BBS:%ld, ", n_bbs);
|
fprintf (file, "LOOPS:%ld, ", n_loops);
|
fprintf (file, "LOOPS:%ld, ", n_loops);
|
fprintf (file, "CONDITIONS:%ld, ", n_conditions);
|
fprintf (file, "CONDITIONS:%ld, ", n_conditions);
|
fprintf (file, "STMTS:%ld)\n", n_stmts);
|
fprintf (file, "STMTS:%ld)\n", n_stmts);
|
fprintf (file, "\nSCoP profiling statistics (");
|
fprintf (file, "\nSCoP profiling statistics (");
|
fprintf (file, "BBS:%ld, ", n_p_bbs);
|
fprintf (file, "BBS:%ld, ", n_p_bbs);
|
fprintf (file, "LOOPS:%ld, ", n_p_loops);
|
fprintf (file, "LOOPS:%ld, ", n_p_loops);
|
fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
|
fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
|
fprintf (file, "STMTS:%ld)\n", n_p_stmts);
|
fprintf (file, "STMTS:%ld)\n", n_p_stmts);
|
}
|
}
|
|
|
/* Print statistics for SCOPS to FILE. */
|
/* Print statistics for SCOPS to FILE. */
|
|
|
static void
|
static void
|
print_graphite_statistics (FILE* file, VEC (scop_p, heap) *scops)
|
print_graphite_statistics (FILE* file, VEC (scop_p, heap) *scops)
|
{
|
{
|
int i;
|
int i;
|
|
|
scop_p scop;
|
scop_p scop;
|
|
|
for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
|
for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
|
print_graphite_scop_statistics (file, scop);
|
print_graphite_scop_statistics (file, scop);
|
}
|
}
|
|
|
/* Initialize graphite: when there are no loops returns false. */
|
/* Initialize graphite: when there are no loops returns false. */
|
|
|
static bool
|
static bool
|
graphite_initialize (void)
|
graphite_initialize (void)
|
{
|
{
|
if (number_of_loops () <= 1
|
if (number_of_loops () <= 1
|
/* FIXME: This limit on the number of basic blocks of a function
|
/* FIXME: This limit on the number of basic blocks of a function
|
should be removed when the SCOP detection is faster. */
|
should be removed when the SCOP detection is faster. */
|
|| n_basic_blocks > PARAM_VALUE (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION))
|
|| n_basic_blocks > PARAM_VALUE (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION))
|
{
|
{
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
print_global_statistics (dump_file);
|
print_global_statistics (dump_file);
|
|
|
return false;
|
return false;
|
}
|
}
|
|
|
recompute_all_dominators ();
|
recompute_all_dominators ();
|
initialize_original_copy_tables ();
|
initialize_original_copy_tables ();
|
cloog_initialize ();
|
cloog_initialize ();
|
|
|
if (dump_file && dump_flags)
|
if (dump_file && dump_flags)
|
dump_function_to_file (current_function_decl, dump_file, dump_flags);
|
dump_function_to_file (current_function_decl, dump_file, dump_flags);
|
|
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Finalize graphite: perform CFG cleanup when NEED_CFG_CLEANUP_P is
|
/* Finalize graphite: perform CFG cleanup when NEED_CFG_CLEANUP_P is
|
true. */
|
true. */
|
|
|
static void
|
static void
|
graphite_finalize (bool need_cfg_cleanup_p)
|
graphite_finalize (bool need_cfg_cleanup_p)
|
{
|
{
|
if (need_cfg_cleanup_p)
|
if (need_cfg_cleanup_p)
|
{
|
{
|
scev_reset ();
|
scev_reset ();
|
cleanup_tree_cfg ();
|
cleanup_tree_cfg ();
|
profile_status = PROFILE_ABSENT;
|
profile_status = PROFILE_ABSENT;
|
release_recorded_exits ();
|
release_recorded_exits ();
|
tree_estimate_probability ();
|
tree_estimate_probability ();
|
}
|
}
|
|
|
cloog_finalize ();
|
cloog_finalize ();
|
free_original_copy_tables ();
|
free_original_copy_tables ();
|
|
|
if (dump_file && dump_flags)
|
if (dump_file && dump_flags)
|
print_loops (dump_file, 3);
|
print_loops (dump_file, 3);
|
}
|
}
|
|
|
/* Perform a set of linear transforms on the loops of the current
|
/* Perform a set of linear transforms on the loops of the current
|
function. */
|
function. */
|
|
|
void
|
void
|
graphite_transform_loops (void)
|
graphite_transform_loops (void)
|
{
|
{
|
int i;
|
int i;
|
scop_p scop;
|
scop_p scop;
|
bool need_cfg_cleanup_p = false;
|
bool need_cfg_cleanup_p = false;
|
VEC (scop_p, heap) *scops = NULL;
|
VEC (scop_p, heap) *scops = NULL;
|
htab_t bb_pbb_mapping;
|
htab_t bb_pbb_mapping;
|
|
|
if (!graphite_initialize ())
|
if (!graphite_initialize ())
|
return;
|
return;
|
|
|
build_scops (&scops);
|
build_scops (&scops);
|
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
{
|
{
|
print_graphite_statistics (dump_file, scops);
|
print_graphite_statistics (dump_file, scops);
|
print_global_statistics (dump_file);
|
print_global_statistics (dump_file);
|
}
|
}
|
|
|
bb_pbb_mapping = htab_create (10, bb_pbb_map_hash, eq_bb_pbb_map, free);
|
bb_pbb_mapping = htab_create (10, bb_pbb_map_hash, eq_bb_pbb_map, free);
|
|
|
for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
|
for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
|
build_poly_scop (scop);
|
build_poly_scop (scop);
|
|
|
for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
|
for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
|
if (POLY_SCOP_P (scop)
|
if (POLY_SCOP_P (scop)
|
&& apply_poly_transforms (scop)
|
&& apply_poly_transforms (scop)
|
&& gloog (scop, scops, bb_pbb_mapping))
|
&& gloog (scop, scops, bb_pbb_mapping))
|
need_cfg_cleanup_p = true;
|
need_cfg_cleanup_p = true;
|
|
|
htab_delete (bb_pbb_mapping);
|
htab_delete (bb_pbb_mapping);
|
free_scops (scops);
|
free_scops (scops);
|
graphite_finalize (need_cfg_cleanup_p);
|
graphite_finalize (need_cfg_cleanup_p);
|
}
|
}
|
|
|
#else /* If Cloog is not available: #ifndef HAVE_cloog. */
|
#else /* If Cloog is not available: #ifndef HAVE_cloog. */
|
|
|
void
|
void
|
graphite_transform_loops (void)
|
graphite_transform_loops (void)
|
{
|
{
|
sorry ("Graphite loop optimizations cannot be used");
|
sorry ("Graphite loop optimizations cannot be used");
|
}
|
}
|
|
|
#endif
|
#endif
|
|
|
