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