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