gcc/graphite.c

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