gcc/graphite.c

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