gcc/graphite.c

   1 /* Gimple Represented as Polyhedra.
   2    Copyright (C) 2006-2013 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_cloog
  38 #include <isl/set.h>
  39 #include <isl/map.h>
  40 #include <isl/options.h>
  41 #include <isl/union_map.h>
  42 #include <cloog/cloog.h>
  43 #include <cloog/isl/domain.h>
  44 #include <cloog/isl/cloog.h>
  45 #endif
  46
  47 #include "system.h"
  48 #include "coretypes.h"
  49 #include "diagnostic-core.h"
  50 #include "tree-ssa.h"
  51 #include "tree-dump.h"
  52 #include "cfgloop.h"
  53 #include "tree-chrec.h"
  54 #include "tree-data-ref.h"
  55 #include "tree-scalar-evolution.h"
  56 #include "sese.h"
  57 #include "dbgcnt.h"
  58 #include "tree-parloops.h"
  59 #include "tree-pass.h"
  60
  61 #ifdef HAVE_cloog
  62
  63 #include "graphite-poly.h"
  64 #include "graphite-scop-detection.h"
  65 #include "graphite-clast-to-gimple.h"
  66 #include "graphite-sese-to-poly.h"
  67 #include "graphite-htab.h"
  68
  69 CloogState *cloog_state;
  70
  71 /* Print global statistics to FILE.  */
  72
  73 static void
  74 print_global_statistics (FILE* file)
  75 {
  76   long n_bbs = 0;
  77   long n_loops = 0;
  78   long n_stmts = 0;
  79   long n_conditions = 0;
  80   long n_p_bbs = 0;
  81   long n_p_loops = 0;
  82   long n_p_stmts = 0;
  83   long n_p_conditions = 0;
  84
  85   basic_block bb;
  86
  87   FOR_ALL_BB (bb)
  88     {
  89       gimple_stmt_iterator psi;
  90
  91       n_bbs++;
  92       n_p_bbs += bb->count;
  93
  94       /* Ignore artificial surrounding loop.  */
  95       if (bb == bb->loop_father->header
  96           && bb->index != 0)
  97         {
  98           n_loops++;
  99           n_p_loops += bb->count;
 100         }
 101
 102       if (EDGE_COUNT (bb->succs) > 1)
 103         {
 104           n_conditions++;
 105           n_p_conditions += bb->count;
 106         }
 107
 108       for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
 109         {
 110           n_stmts++;
 111           n_p_stmts += bb->count;
 112         }
 113     }
 114
 115   fprintf (file, "\nGlobal statistics (");
 116   fprintf (file, "BBS:%ld, ", n_bbs);
 117   fprintf (file, "LOOPS:%ld, ", n_loops);
 118   fprintf (file, "CONDITIONS:%ld, ", n_conditions);
 119   fprintf (file, "STMTS:%ld)\n", n_stmts);
 120   fprintf (file, "\nGlobal profiling statistics (");
 121   fprintf (file, "BBS:%ld, ", n_p_bbs);
 122   fprintf (file, "LOOPS:%ld, ", n_p_loops);
 123   fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
 124   fprintf (file, "STMTS:%ld)\n", n_p_stmts);
 125 }
 126
 127 /* Print statistics for SCOP to FILE.  */
 128
 129 static void
 130 print_graphite_scop_statistics (FILE* file, scop_p scop)
 131 {
 132   long n_bbs = 0;
 133   long n_loops = 0;
 134   long n_stmts = 0;
 135   long n_conditions = 0;
 136   long n_p_bbs = 0;
 137   long n_p_loops = 0;
 138   long n_p_stmts = 0;
 139   long n_p_conditions = 0;
 140
 141   basic_block bb;
 142
 143   FOR_ALL_BB (bb)
 144     {
 145       gimple_stmt_iterator psi;
 146       loop_p loop = bb->loop_father;
 147
 148       if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
 149         continue;
 150
 151       n_bbs++;
 152       n_p_bbs += bb->count;
 153
 154       if (EDGE_COUNT (bb->succs) > 1)
 155         {
 156           n_conditions++;
 157           n_p_conditions += bb->count;
 158         }
 159
 160       for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
 161         {
 162           n_stmts++;
 163           n_p_stmts += bb->count;
 164         }
 165
 166       if (loop->header == bb && loop_in_sese_p (loop, SCOP_REGION (scop)))
 167         {
 168           n_loops++;
 169           n_p_loops += bb->count;
 170         }
 171     }
 172
 173   fprintf (file, "\nSCoP statistics (");
 174   fprintf (file, "BBS:%ld, ", n_bbs);
 175   fprintf (file, "LOOPS:%ld, ", n_loops);
 176   fprintf (file, "CONDITIONS:%ld, ", n_conditions);
 177   fprintf (file, "STMTS:%ld)\n", n_stmts);
 178   fprintf (file, "\nSCoP profiling statistics (");
 179   fprintf (file, "BBS:%ld, ", n_p_bbs);
 180   fprintf (file, "LOOPS:%ld, ", n_p_loops);
 181   fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
 182   fprintf (file, "STMTS:%ld)\n", n_p_stmts);
 183 }
 184
 185 /* Print statistics for SCOPS to FILE.  */
 186
 187 static void
 188 print_graphite_statistics (FILE* file, vec<scop_p> scops)
 189 {
 190   int i;
 191
 192   scop_p scop;
 193
 194   FOR_EACH_VEC_ELT (scops, i, scop)
 195     print_graphite_scop_statistics (file, scop);
 196 }
 197
 198 /* Initialize graphite: when there are no loops returns false.  */
 199
 200 static bool
 201 graphite_initialize (isl_ctx *ctx)
 202 {
 203   if (number_of_loops (cfun) <= 1
 204       /* FIXME: This limit on the number of basic blocks of a function
 205          should be removed when the SCOP detection is faster.  */
 206       || n_basic_blocks > PARAM_VALUE (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION))
 207     {
 208       if (dump_file && (dump_flags & TDF_DETAILS))
 209         print_global_statistics (dump_file);
 210
 211       isl_ctx_free (ctx);
 212       return false;
 213     }
 214
 215   scev_reset ();
 216   recompute_all_dominators ();
 217   initialize_original_copy_tables ();
 218
 219   cloog_state = cloog_isl_state_malloc (ctx);
 220
 221   if (dump_file && dump_flags)
 222     dump_function_to_file (current_function_decl, dump_file, dump_flags);
 223
 224   return true;
 225 }
 226
 227 /* Finalize graphite: perform CFG cleanup when NEED_CFG_CLEANUP_P is
 228    true.  */
 229
 230 static void
 231 graphite_finalize (bool need_cfg_cleanup_p)
 232 {
 233   if (need_cfg_cleanup_p)
 234     {
 235       scev_reset ();
 236       cleanup_tree_cfg ();
 237       profile_status = PROFILE_ABSENT;
 238       release_recorded_exits ();
 239       tree_estimate_probability ();
 240     }
 241
 242   cloog_state_free (cloog_state);
 243   free_original_copy_tables ();
 244
 245   if (dump_file && dump_flags)
 246     print_loops (dump_file, 3);
 247 }
 248
 249 isl_ctx *the_isl_ctx;
 250
 251 /* Perform a set of linear transforms on the loops of the current
 252    function.  */
 253
 254 void
 255 graphite_transform_loops (void)
 256 {
 257   int i;
 258   scop_p scop;
 259   bool need_cfg_cleanup_p = false;
 260   vec<scop_p> scops = vNULL;
 261   bb_pbb_htab_type bb_pbb_mapping;
 262   isl_ctx *ctx;
 263
 264   /* If a function is parallel it was most probably already run through graphite
 265      once. No need to run again.  */
 266   if (parallelized_function_p (cfun->decl))
 267     return;
 268
 269   ctx = isl_ctx_alloc ();
 270   isl_options_set_on_error (ctx, ISL_ON_ERROR_ABORT);
 271   if (!graphite_initialize (ctx))
 272     return;
 273
 274   the_isl_ctx = ctx;
 275   build_scops (&scops);
 276
 277   if (dump_file && (dump_flags & TDF_DETAILS))
 278     {
 279       print_graphite_statistics (dump_file, scops);
 280       print_global_statistics (dump_file);
 281     }
 282
 283   bb_pbb_mapping.create (10);
 284
 285   FOR_EACH_VEC_ELT (scops, i, scop)
 286     if (dbg_cnt (graphite_scop))
 287       {
 288         scop->ctx = ctx;
 289         build_poly_scop (scop);
 290
 291         if (POLY_SCOP_P (scop)
 292             && apply_poly_transforms (scop)
 293             && gloog (scop, bb_pbb_mapping))
 294           need_cfg_cleanup_p = true;
 295       }
 296
 297   bb_pbb_mapping.dispose ();
 298   free_scops (scops);
 299   graphite_finalize (need_cfg_cleanup_p);
 300   the_isl_ctx = NULL;
 301   isl_ctx_free (ctx);
 302 }
 303
 304 #else /* If Cloog is not available: #ifndef HAVE_cloog.  */
 305
 306 static void
 307 graphite_transform_loops (void)
 308 {
 309   sorry ("Graphite loop optimizations cannot be used");
 310 }
 311
 312 #endif
 313
 314
 315 static unsigned int
 316 graphite_transforms (void)
 317 {
 318   if (!current_loops)
 319     return 0;
 320
 321   graphite_transform_loops ();
 322
 323   return 0;
 324 }
 325
 326 static bool
 327 gate_graphite_transforms (void)
 328 {
 329   /* Enable -fgraphite pass if any one of the graphite optimization flags
 330      is turned on.  */
 331   if (flag_loop_block
 332       || flag_loop_interchange
 333       || flag_loop_strip_mine
 334       || flag_graphite_identity
 335       || flag_loop_parallelize_all
 336       || flag_loop_optimize_isl)
 337     flag_graphite = 1;
 338
 339   return flag_graphite != 0;
 340 }
 341
 342 namespace {
 343
 344 const pass_data pass_data_graphite =
 345 {
 346   GIMPLE_PASS, /* type */
 347   "graphite0", /* name */
 348   OPTGROUP_LOOP, /* optinfo_flags */
 349   true, /* has_gate */
 350   false, /* has_execute */
 351   TV_GRAPHITE, /* tv_id */
 352   ( PROP_cfg | PROP_ssa ), /* properties_required */
 353   0, /* properties_provided */
 354   0, /* properties_destroyed */
 355   0, /* todo_flags_start */
 356   0, /* todo_flags_finish */
 357 };
 358
 359 class pass_graphite : public gimple_opt_pass
 360 {
 361 public:
 362   pass_graphite (gcc::context *ctxt)
 363     : gimple_opt_pass (pass_data_graphite, ctxt)
 364   {}
 365
 366   /* opt_pass methods: */
 367   bool gate () { return gate_graphite_transforms (); }
 368
 369 }; // class pass_graphite
 370
 371 } // anon namespace
 372
 373 gimple_opt_pass *
 374 make_pass_graphite (gcc::context *ctxt)
 375 {
 376   return new pass_graphite (ctxt);
 377 }
 378
 379 namespace {
 380
 381 const pass_data pass_data_graphite_transforms =
 382 {
 383   GIMPLE_PASS, /* type */
 384   "graphite", /* name */
 385   OPTGROUP_LOOP, /* optinfo_flags */
 386   true, /* has_gate */
 387   true, /* has_execute */
 388   TV_GRAPHITE_TRANSFORMS, /* 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_transforms : public gimple_opt_pass
 397 {
 398 public:
 399   pass_graphite_transforms (gcc::context *ctxt)
 400     : gimple_opt_pass (pass_data_graphite_transforms, ctxt)
 401   {}
 402
 403   /* opt_pass methods: */
 404   bool gate () { return gate_graphite_transforms (); }
 405   unsigned int execute () { return graphite_transforms (); }
 406
 407 }; // class pass_graphite_transforms
 408
 409 } // anon namespace
 410
 411 gimple_opt_pass *
 412 make_pass_graphite_transforms (gcc::context *ctxt)
 413 {
 414   return new pass_graphite_transforms (ctxt);
 415 }
 416
 417