gcc/graphite.c

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