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