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