gcc/graphite.c

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