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