gcc/graphite.c

   1 /* Gimple Represented as Polyhedra.
   2    Copyright (C) 2006-2014 Free Software Foundation, Inc.
   3    Contributed by Sebastian Pop <sebastian.pop@inria.fr>.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 /* This pass converts GIMPLE to GRAPHITE, performs some loop
  22    transformations and then converts the resulting representation back
  23    to GIMPLE.
  24
  25    An early description of this pass can be found in the GCC Summit'06
  26    paper "GRAPHITE: Polyhedral Analyses and Optimizations for GCC".
  27    The wiki page http://gcc.gnu.org/wiki/Graphite contains pointers to
  28    the related work.
  29
  30    One important document to read is CLooG's internal manual:
  31    http://repo.or.cz/w/cloog-ppl.git?a=blob_plain;f=doc/cloog.texi;hb=HEAD
  32    that describes the data structure of loops used in this file, and
  33    the functions that are used for transforming the code.  */
  34
  35 #include "config.h"
  36
  37 #ifdef HAVE_isl
  38 #include <isl/set.h>
  39 #include <isl/map.h>
  40 #include <isl/options.h>
  41 #include <isl/union_map.h>
  42 #ifdef HAVE_cloog
  43 #include <cloog/cloog.h>
  44 #include <cloog/isl/domain.h>
  45 #include <cloog/isl/cloog.h>
  46 #endif
  47 #endif
  48
  49 #include "system.h"
  50 #include "coretypes.h"
  51 #include "diagnostic-core.h"
  52 #include "tree.h"
  53 #include "basic-block.h"
  54 #include "tree-ssa-alias.h"
  55 #include "internal-fn.h"
  56 #include "gimple-expr.h"
  57 #include "is-a.h"
  58 #include "gimple.h"
  59 #include "gimple-iterator.h"
  60 #include "tree-cfg.h"
  61 #include "tree-ssa-loop.h"
  62 #include "tree-dump.h"
  63 #include "cfgloop.h"
  64 #include "tree-chrec.h"
  65 #include "tree-data-ref.h"
  66 #include "tree-scalar-evolution.h"
  67 #include "sese.h"
  68 #include "dbgcnt.h"
  69 #include "tree-parloops.h"
  70 #include "tree-pass.h"
  71 #include "tree-cfgcleanup.h"
  72
  73 #ifdef HAVE_isl
  74
  75 #include "graphite-poly.h"
  76 #include "graphite-scop-detection.h"
  77 #include "graphite-isl-ast-to-gimple.h"
  78 #include "graphite-sese-to-poly.h"
  79 #include "graphite-htab.h"
  80
  81 #ifdef HAVE_cloog
  82 #include "graphite-clast-to-gimple.h"
  83
  84 CloogState *cloog_state;
  85 #endif
  86
  87 /* Print global statistics to FILE.  */
  88
  89 static void
  90 print_global_statistics (FILE* file)
  91 {
  92   long n_bbs = 0;
  93   long n_loops = 0;
  94   long n_stmts = 0;
  95   long n_conditions = 0;
  96   long n_p_bbs = 0;
  97   long n_p_loops = 0;
  98   long n_p_stmts = 0;
  99   long n_p_conditions = 0;
 100
 101   basic_block bb;
 102
 103   FOR_ALL_BB_FN (bb, cfun)
 104     {
 105       gimple_stmt_iterator psi;
 106
 107       n_bbs++;
 108       n_p_bbs += bb->count;
 109
 110       /* Ignore artificial surrounding loop.  */
 111       if (bb == bb->loop_father->header
 112           && bb->index != 0)
 113         {
 114           n_loops++;
 115           n_p_loops += bb->count;
 116         }
 117
 118       if (EDGE_COUNT (bb->succs) > 1)
 119         {
 120           n_conditions++;
 121           n_p_conditions += bb->count;
 122         }
 123
 124       for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
 125         {
 126           n_stmts++;
 127           n_p_stmts += bb->count;
 128         }
 129     }
 130
 131   fprintf (file, "\nGlobal statistics (");
 132   fprintf (file, "BBS:%ld, ", n_bbs);
 133   fprintf (file, "LOOPS:%ld, ", n_loops);
 134   fprintf (file, "CONDITIONS:%ld, ", n_conditions);
 135   fprintf (file, "STMTS:%ld)\n", n_stmts);
 136   fprintf (file, "\nGlobal profiling statistics (");
 137   fprintf (file, "BBS:%ld, ", n_p_bbs);
 138   fprintf (file, "LOOPS:%ld, ", n_p_loops);
 139   fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
 140   fprintf (file, "STMTS:%ld)\n", n_p_stmts);
 141 }
 142
 143 /* Print statistics for SCOP to FILE.  */
 144
 145 static void
 146 print_graphite_scop_statistics (FILE* file, scop_p scop)
 147 {
 148   long n_bbs = 0;
 149   long n_loops = 0;
 150   long n_stmts = 0;
 151   long n_conditions = 0;
 152   long n_p_bbs = 0;
 153   long n_p_loops = 0;
 154   long n_p_stmts = 0;
 155   long n_p_conditions = 0;
 156
 157   basic_block bb;
 158
 159   FOR_ALL_BB_FN (bb, cfun)
 160     {
 161       gimple_stmt_iterator psi;
 162       loop_p loop = bb->loop_father;
 163
 164       if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
 165         continue;
 166
 167       n_bbs++;
 168       n_p_bbs += bb->count;
 169
 170       if (EDGE_COUNT (bb->succs) > 1)
 171         {
 172           n_conditions++;
 173           n_p_conditions += bb->count;
 174         }
 175
 176       for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
 177         {
 178           n_stmts++;
 179           n_p_stmts += bb->count;
 180         }
 181
 182       if (loop->header == bb && loop_in_sese_p (loop, SCOP_REGION (scop)))
 183         {
 184           n_loops++;
 185           n_p_loops += bb->count;
 186         }
 187     }
 188
 189   fprintf (file, "\nSCoP statistics (");
 190   fprintf (file, "BBS:%ld, ", n_bbs);
 191   fprintf (file, "LOOPS:%ld, ", n_loops);
 192   fprintf (file, "CONDITIONS:%ld, ", n_conditions);
 193   fprintf (file, "STMTS:%ld)\n", n_stmts);
 194   fprintf (file, "\nSCoP profiling statistics (");
 195   fprintf (file, "BBS:%ld, ", n_p_bbs);
 196   fprintf (file, "LOOPS:%ld, ", n_p_loops);
 197   fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
 198   fprintf (file, "STMTS:%ld)\n", n_p_stmts);
 199 }
 200
 201 /* Print statistics for SCOPS to FILE.  */
 202
 203 static void
 204 print_graphite_statistics (FILE* file, vec<scop_p> scops)
 205 {
 206   int i;
 207
 208   scop_p scop;
 209
 210   FOR_EACH_VEC_ELT (scops, i, scop)
 211     print_graphite_scop_statistics (file, scop);
 212 }
 213
 214 /* Initialize graphite: when there are no loops returns false.  */
 215
 216 static bool
 217 graphite_initialize (isl_ctx *ctx)
 218 {
 219   if (number_of_loops (cfun) <= 1
 220       /* FIXME: This limit on the number of basic blocks of a function
 221          should be removed when the SCOP detection is faster.  */
 222       || (n_basic_blocks_for_fn (cfun) >
 223           PARAM_VALUE (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION)))
 224     {
 225       if (dump_file && (dump_flags & TDF_DETAILS))
 226         print_global_statistics (dump_file);
 227
 228       isl_ctx_free (ctx);
 229       return false;
 230     }
 231
 232   scev_reset ();
 233   recompute_all_dominators ();
 234   initialize_original_copy_tables ();
 235
 236 #ifdef HAVE_cloog
 237   cloog_state = cloog_isl_state_malloc (ctx);
 238 #endif
 239
 240   if (dump_file && dump_flags)
 241     dump_function_to_file (current_function_decl, dump_file, dump_flags);
 242
 243   return true;
 244 }
 245
 246 /* Finalize graphite: perform CFG cleanup when NEED_CFG_CLEANUP_P is
 247    true.  */
 248
 249 static void
 250 graphite_finalize (bool need_cfg_cleanup_p)
 251 {
 252   if (need_cfg_cleanup_p)
 253     {
 254       scev_reset ();
 255       cleanup_tree_cfg ();
 256       profile_status_for_fn (cfun) = PROFILE_ABSENT;
 257       release_recorded_exits ();
 258       tree_estimate_probability ();
 259     }
 260
 261 #ifdef HAVE_cloog
 262   cloog_state_free (cloog_state);
 263 #endif
 264   free_original_copy_tables ();
 265
 266   if (dump_file && dump_flags)
 267     print_loops (dump_file, 3);
 268 }
 269
 270 isl_ctx *the_isl_ctx;
 271
 272 /* Perform a set of linear transforms on the loops of the current
 273    function.  */
 274
 275 void
 276 graphite_transform_loops (void)
 277 {
 278   int i;
 279   scop_p scop;
 280   bool need_cfg_cleanup_p = false;
 281   vec<scop_p> scops = vNULL;
 282   isl_ctx *ctx;
 283
 284   /* If a function is parallel it was most probably already run through graphite
 285      once. No need to run again.  */
 286   if (parallelized_function_p (cfun->decl))
 287     return;
 288
 289   ctx = isl_ctx_alloc ();
 290   isl_options_set_on_error (ctx, ISL_ON_ERROR_ABORT);
 291   if (!graphite_initialize (ctx))
 292     return;
 293
 294   the_isl_ctx = ctx;
 295   build_scops (&scops);
 296
 297   if (dump_file && (dump_flags & TDF_DETAILS))
 298     {
 299       print_graphite_statistics (dump_file, scops);
 300       print_global_statistics (dump_file);
 301     }
 302
 303   bb_pbb_htab_type bb_pbb_mapping (10);
 304
 305 #ifndef HAVE_cloog
 306   if(flag_graphite_code_gen == FGRAPHITE_CODE_GEN_CLOOG)
 307     {
 308       flag_graphite_code_gen = FGRAPHITE_CODE_GEN_ISL;
 309       printf ("The CLooG code generator cannot be used (CLooG is not "
 310               "available). The ISL code generator was chosen.\n");
 311     }
 312 #endif
 313
 314   FOR_EACH_VEC_ELT (scops, i, scop)
 315     if (dbg_cnt (graphite_scop))
 316       {
 317         scop->ctx = ctx;
 318         build_poly_scop (scop);
 319
 320 #ifdef HAVE_cloog
 321         if (POLY_SCOP_P (scop)
 322             && apply_poly_transforms (scop)
 323             && (((flag_graphite_code_gen == FGRAPHITE_CODE_GEN_ISL)
 324             && graphite_regenerate_ast_isl (scop))
 325             || ((flag_graphite_code_gen == FGRAPHITE_CODE_GEN_CLOOG)
 326             && graphite_regenerate_ast_cloog (scop, &bb_pbb_mapping))))
 327           need_cfg_cleanup_p = true;
 328 #else
 329         if (POLY_SCOP_P (scop)
 330             && apply_poly_transforms (scop)
 331             && graphite_regenerate_ast_isl (scop))
 332           need_cfg_cleanup_p = true;
 333 #endif
 334
 335       }
 336
 337   free_scops (scops);
 338   graphite_finalize (need_cfg_cleanup_p);
 339   the_isl_ctx = NULL;
 340   isl_ctx_free (ctx);
 341 }
 342
 343 #else /* If ISL is not available: #ifndef HAVE_isl.  */
 344
 345 static void
 346 graphite_transform_loops (void)
 347 {
 348   sorry ("Graphite loop optimizations cannot be used (ISL is not available).");
 349 }
 350
 351 #endif
 352
 353
 354 static unsigned int
 355 graphite_transforms (struct function *fun)
 356 {
 357   if (number_of_loops (fun) <= 1)
 358     return 0;
 359
 360   graphite_transform_loops ();
 361
 362   return 0;
 363 }
 364
 365 static bool
 366 gate_graphite_transforms (void)
 367 {
 368   /* Enable -fgraphite pass if any one of the graphite optimization flags
 369      is turned on.  */
 370   if (flag_loop_block
 371       || flag_loop_interchange
 372       || flag_loop_strip_mine
 373       || flag_graphite_identity
 374       || flag_loop_parallelize_all
 375       || flag_loop_optimize_isl)
 376     flag_graphite = 1;
 377
 378   return flag_graphite != 0;
 379 }
 380
 381 namespace {
 382
 383 const pass_data pass_data_graphite =
 384 {
 385   GIMPLE_PASS, /* type */
 386   "graphite0", /* name */
 387   OPTGROUP_LOOP, /* optinfo_flags */
 388   TV_GRAPHITE, /* tv_id */
 389   ( PROP_cfg | PROP_ssa ), /* properties_required */
 390   0, /* properties_provided */
 391   0, /* properties_destroyed */
 392   0, /* todo_flags_start */
 393   0, /* todo_flags_finish */
 394 };
 395
 396 class pass_graphite : public gimple_opt_pass
 397 {
 398 public:
 399   pass_graphite (gcc::context *ctxt)
 400     : gimple_opt_pass (pass_data_graphite, ctxt)
 401   {}
 402
 403   /* opt_pass methods: */
 404   virtual bool gate (function *) { return gate_graphite_transforms (); }
 405
 406 }; // class pass_graphite
 407
 408 } // anon namespace
 409
 410 gimple_opt_pass *
 411 make_pass_graphite (gcc::context *ctxt)
 412 {
 413   return new pass_graphite (ctxt);
 414 }
 415
 416 namespace {
 417
 418 const pass_data pass_data_graphite_transforms =
 419 {
 420   GIMPLE_PASS, /* type */
 421   "graphite", /* name */
 422   OPTGROUP_LOOP, /* optinfo_flags */
 423   TV_GRAPHITE_TRANSFORMS, /* tv_id */
 424   ( PROP_cfg | PROP_ssa ), /* properties_required */
 425   0, /* properties_provided */
 426   0, /* properties_destroyed */
 427   0, /* todo_flags_start */
 428   0, /* todo_flags_finish */
 429 };
 430
 431 class pass_graphite_transforms : public gimple_opt_pass
 432 {
 433 public:
 434   pass_graphite_transforms (gcc::context *ctxt)
 435     : gimple_opt_pass (pass_data_graphite_transforms, ctxt)
 436   {}
 437
 438   /* opt_pass methods: */
 439   virtual bool gate (function *) { return gate_graphite_transforms (); }
 440   virtual unsigned int execute (function *fun) { return graphite_transforms (fun); }
 441
 442 }; // class pass_graphite_transforms
 443
 444 } // anon namespace
 445
 446 gimple_opt_pass *
 447 make_pass_graphite_transforms (gcc::context *ctxt)
 448 {
 449   return new pass_graphite_transforms (ctxt);
 450 }
 451
 452