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