gcc/graphite.c

   1 /* Gimple Represented as Polyhedra.
   2    Copyright (C) 2006, 2007, 2008, 2009, 2010, 2011
   3    Free Software Foundation, Inc.
   4    Contributed by Sebastian Pop <sebastian.pop@inria.fr>.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 3, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 /* This pass converts GIMPLE to GRAPHITE, performs some loop
  23    transformations and then converts the resulting representation back
  24    to GIMPLE.
  25
  26    An early description of this pass can be found in the GCC Summit'06
  27    paper "GRAPHITE: Polyhedral Analyses and Optimizations for GCC".
  28    The wiki page http://gcc.gnu.org/wiki/Graphite contains pointers to
  29    the related work.
  30
  31    One important document to read is CLooG's internal manual:
  32    http://repo.or.cz/w/cloog-ppl.git?a=blob_plain;f=doc/cloog.texi;hb=HEAD
  33    that describes the data structure of loops used in this file, and
  34    the functions that are used for transforming the code.  */
  35
  36 #include "config.h"
  37
  38 #ifdef HAVE_cloog
  39 #include <isl/set.h>
  40 #include <isl/map.h>
  41 #include <isl/options.h>
  42 #include <isl/union_map.h>
  43 #include <cloog/cloog.h>
  44 #include <cloog/isl/domain.h>
  45 #include <cloog/isl/cloog.h>
  46 #endif
  47
  48 #include "system.h"
  49 #include "coretypes.h"
  50 #include "diagnostic-core.h"
  51 #include "tree-flow.h"
  52 #include "tree-dump.h"
  53 #include "cfgloop.h"
  54 #include "tree-chrec.h"
  55 #include "tree-data-ref.h"
  56 #include "tree-scalar-evolution.h"
  57 #include "sese.h"
  58 #include "dbgcnt.h"
  59
  60 #ifdef HAVE_cloog
  61
  62 #include "graphite-poly.h"
  63 #include "graphite-scop-detection.h"
  64 #include "graphite-clast-to-gimple.h"
  65 #include "graphite-sese-to-poly.h"
  66
  67 CloogState *cloog_state;
  68
  69 /* Print global statistics to FILE.  */
  70
  71 static void
  72 print_global_statistics (FILE* file)
  73 {
  74   long n_bbs = 0;
  75   long n_loops = 0;
  76   long n_stmts = 0;
  77   long n_conditions = 0;
  78   long n_p_bbs = 0;
  79   long n_p_loops = 0;
  80   long n_p_stmts = 0;
  81   long n_p_conditions = 0;
  82
  83   basic_block bb;
  84
  85   FOR_ALL_BB (bb)
  86     {
  87       gimple_stmt_iterator psi;
  88
  89       n_bbs++;
  90       n_p_bbs += bb->count;
  91
  92       /* Ignore artificial surrounding loop.  */
  93       if (bb == bb->loop_father->header
  94           && bb->index != 0)
  95         {
  96           n_loops++;
  97           n_p_loops += bb->count;
  98         }
  99
 100       if (EDGE_COUNT (bb->succs) > 1)
 101         {
 102           n_conditions++;
 103           n_p_conditions += bb->count;
 104         }
 105
 106       for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
 107         {
 108           n_stmts++;
 109           n_p_stmts += bb->count;
 110         }
 111     }
 112
 113   fprintf (file, "\nGlobal statistics (");
 114   fprintf (file, "BBS:%ld, ", n_bbs);
 115   fprintf (file, "LOOPS:%ld, ", n_loops);
 116   fprintf (file, "CONDITIONS:%ld, ", n_conditions);
 117   fprintf (file, "STMTS:%ld)\n", n_stmts);
 118   fprintf (file, "\nGlobal profiling statistics (");
 119   fprintf (file, "BBS:%ld, ", n_p_bbs);
 120   fprintf (file, "LOOPS:%ld, ", n_p_loops);
 121   fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
 122   fprintf (file, "STMTS:%ld)\n", n_p_stmts);
 123 }
 124
 125 /* Print statistics for SCOP to FILE.  */
 126
 127 static void
 128 print_graphite_scop_statistics (FILE* file, scop_p scop)
 129 {
 130   long n_bbs = 0;
 131   long n_loops = 0;
 132   long n_stmts = 0;
 133   long n_conditions = 0;
 134   long n_p_bbs = 0;
 135   long n_p_loops = 0;
 136   long n_p_stmts = 0;
 137   long n_p_conditions = 0;
 138
 139   basic_block bb;
 140
 141   FOR_ALL_BB (bb)
 142     {
 143       gimple_stmt_iterator psi;
 144       loop_p loop = bb->loop_father;
 145
 146       if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
 147         continue;
 148
 149       n_bbs++;
 150       n_p_bbs += bb->count;
 151
 152       if (EDGE_COUNT (bb->succs) > 1)
 153         {
 154           n_conditions++;
 155           n_p_conditions += bb->count;
 156         }
 157
 158       for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
 159         {
 160           n_stmts++;
 161           n_p_stmts += bb->count;
 162         }
 163
 164       if (loop->header == bb && loop_in_sese_p (loop, SCOP_REGION (scop)))
 165         {
 166           n_loops++;
 167           n_p_loops += bb->count;
 168         }
 169     }
 170
 171   fprintf (file, "\nSCoP statistics (");
 172   fprintf (file, "BBS:%ld, ", n_bbs);
 173   fprintf (file, "LOOPS:%ld, ", n_loops);
 174   fprintf (file, "CONDITIONS:%ld, ", n_conditions);
 175   fprintf (file, "STMTS:%ld)\n", n_stmts);
 176   fprintf (file, "\nSCoP profiling statistics (");
 177   fprintf (file, "BBS:%ld, ", n_p_bbs);
 178   fprintf (file, "LOOPS:%ld, ", n_p_loops);
 179   fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
 180   fprintf (file, "STMTS:%ld)\n", n_p_stmts);
 181 }
 182
 183 /* Print statistics for SCOPS to FILE.  */
 184
 185 static void
 186 print_graphite_statistics (FILE* file, VEC (scop_p, heap) *scops)
 187 {
 188   int i;
 189
 190   scop_p scop;
 191
 192   FOR_EACH_VEC_ELT (scop_p, scops, i, scop)
 193     print_graphite_scop_statistics (file, scop);
 194 }
 195
 196 /* Initialize graphite: when there are no loops returns false.  */
 197
 198 static bool
 199 graphite_initialize (isl_ctx *ctx)
 200 {
 201   if (number_of_loops () <= 1
 202       /* FIXME: This limit on the number of basic blocks of a function
 203          should be removed when the SCOP detection is faster.  */
 204       || n_basic_blocks > PARAM_VALUE (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION))
 205     {
 206       if (dump_file && (dump_flags & TDF_DETAILS))
 207         print_global_statistics (dump_file);
 208
 209       isl_ctx_free (ctx);
 210       return false;
 211     }
 212
 213   scev_reset ();
 214   recompute_all_dominators ();
 215   initialize_original_copy_tables ();
 216
 217   cloog_state = cloog_isl_state_malloc (ctx);
 218
 219   if (dump_file && dump_flags)
 220     dump_function_to_file (current_function_decl, dump_file, dump_flags);
 221
 222   return true;
 223 }
 224
 225 /* Finalize graphite: perform CFG cleanup when NEED_CFG_CLEANUP_P is
 226    true.  */
 227
 228 static void
 229 graphite_finalize (bool need_cfg_cleanup_p)
 230 {
 231   if (need_cfg_cleanup_p)
 232     {
 233       scev_reset ();
 234       cleanup_tree_cfg ();
 235       profile_status = PROFILE_ABSENT;
 236       release_recorded_exits ();
 237       tree_estimate_probability ();
 238     }
 239
 240   cloog_state_free (cloog_state);
 241   free_original_copy_tables ();
 242
 243   if (dump_file && dump_flags)
 244     print_loops (dump_file, 3);
 245 }
 246
 247 isl_ctx *the_isl_ctx;
 248
 249 /* Perform a set of linear transforms on the loops of the current
 250    function.  */
 251
 252 void
 253 graphite_transform_loops (void)
 254 {
 255   int i;
 256   scop_p scop;
 257   bool need_cfg_cleanup_p = false;
 258   VEC (scop_p, heap) *scops = NULL;
 259   htab_t bb_pbb_mapping;
 260   isl_ctx *ctx;
 261
 262   /* If a function is parallel it was most probably already run through graphite
 263      once. No need to run again.  */
 264   if (parallelized_function_p (cfun->decl))
 265     return;
 266
 267   ctx = isl_ctx_alloc ();
 268   isl_options_set_on_error(ctx, ISL_ON_ERROR_ABORT);
 269   if (!graphite_initialize (ctx))
 270     return;
 271
 272   the_isl_ctx = ctx;
 273   build_scops (&scops);
 274
 275   if (dump_file && (dump_flags & TDF_DETAILS))
 276     {
 277       print_graphite_statistics (dump_file, scops);
 278       print_global_statistics (dump_file);
 279     }
 280
 281   bb_pbb_mapping = htab_create (10, bb_pbb_map_hash, eq_bb_pbb_map, free);
 282
 283   FOR_EACH_VEC_ELT (scop_p, scops, i, scop)
 284     if (dbg_cnt (graphite_scop))
 285       {
 286         scop->ctx = ctx;
 287         build_poly_scop (scop);
 288
 289         if (POLY_SCOP_P (scop)
 290             && apply_poly_transforms (scop)
 291             && gloog (scop, bb_pbb_mapping))
 292           need_cfg_cleanup_p = true;
 293       }
 294
 295   htab_delete (bb_pbb_mapping);
 296   free_scops (scops);
 297   graphite_finalize (need_cfg_cleanup_p);
 298   the_isl_ctx = NULL;
 299   isl_ctx_free (ctx);
 300 }
 301
 302 #else /* If Cloog is not available: #ifndef HAVE_cloog.  */
 303
 304 void
 305 graphite_transform_loops (void)
 306 {
 307   sorry ("Graphite loop optimizations cannot be used");
 308 }
 309
 310 #endif