gcc/graphite.c

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