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-flow.h"
  51 #include "tree-dump.h"
  52 #include "cfgloop.h"
  53 #include "tree-chrec.h"
  54 #include "tree-data-ref.h"
  55 #include "tree-scalar-evolution.h"
  56 #include "sese.h"
  57 #include "dbgcnt.h"
  58
  59 #ifdef HAVE_cloog
  60
  61 #include "graphite-poly.h"
  62 #include "graphite-scop-detection.h"
  63 #include "graphite-clast-to-gimple.h"
  64 #include "graphite-sese-to-poly.h"
  65
  66 CloogState *cloog_state;
  67
  68 /* Print global statistics to FILE.  */
  69
  70 static void
  71 print_global_statistics (FILE* file)
  72 {
  73   long n_bbs = 0;
  74   long n_loops = 0;
  75   long n_stmts = 0;
  76   long n_conditions = 0;
  77   long n_p_bbs = 0;
  78   long n_p_loops = 0;
  79   long n_p_stmts = 0;
  80   long n_p_conditions = 0;
  81
  82   basic_block bb;
  83
  84   FOR_ALL_BB (bb)
  85     {
  86       gimple_stmt_iterator psi;
  87
  88       n_bbs++;
  89       n_p_bbs += bb->count;
  90
  91       /* Ignore artificial surrounding loop.  */
  92       if (bb == bb->loop_father->header
  93           && bb->index != 0)
  94         {
  95           n_loops++;
  96           n_p_loops += bb->count;
  97         }
  98
  99       if (EDGE_COUNT (bb->succs) > 1)
 100         {
 101           n_conditions++;
 102           n_p_conditions += bb->count;
 103         }
 104
 105       for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
 106         {
 107           n_stmts++;
 108           n_p_stmts += bb->count;
 109         }
 110     }
 111
 112   fprintf (file, "\nGlobal statistics (");
 113   fprintf (file, "BBS:%ld, ", n_bbs);
 114   fprintf (file, "LOOPS:%ld, ", n_loops);
 115   fprintf (file, "CONDITIONS:%ld, ", n_conditions);
 116   fprintf (file, "STMTS:%ld)\n", n_stmts);
 117   fprintf (file, "\nGlobal profiling statistics (");
 118   fprintf (file, "BBS:%ld, ", n_p_bbs);
 119   fprintf (file, "LOOPS:%ld, ", n_p_loops);
 120   fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
 121   fprintf (file, "STMTS:%ld)\n", n_p_stmts);
 122 }
 123
 124 /* Print statistics for SCOP to FILE.  */
 125
 126 static void
 127 print_graphite_scop_statistics (FILE* file, scop_p scop)
 128 {
 129   long n_bbs = 0;
 130   long n_loops = 0;
 131   long n_stmts = 0;
 132   long n_conditions = 0;
 133   long n_p_bbs = 0;
 134   long n_p_loops = 0;
 135   long n_p_stmts = 0;
 136   long n_p_conditions = 0;
 137
 138   basic_block bb;
 139
 140   FOR_ALL_BB (bb)
 141     {
 142       gimple_stmt_iterator psi;
 143       loop_p loop = bb->loop_father;
 144
 145       if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
 146         continue;
 147
 148       n_bbs++;
 149       n_p_bbs += bb->count;
 150
 151       if (EDGE_COUNT (bb->succs) > 1)
 152         {
 153           n_conditions++;
 154           n_p_conditions += bb->count;
 155         }
 156
 157       for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
 158         {
 159           n_stmts++;
 160           n_p_stmts += bb->count;
 161         }
 162
 163       if (loop->header == bb && loop_in_sese_p (loop, SCOP_REGION (scop)))
 164         {
 165           n_loops++;
 166           n_p_loops += bb->count;
 167         }
 168     }
 169
 170   fprintf (file, "\nSCoP statistics (");
 171   fprintf (file, "BBS:%ld, ", n_bbs);
 172   fprintf (file, "LOOPS:%ld, ", n_loops);
 173   fprintf (file, "CONDITIONS:%ld, ", n_conditions);
 174   fprintf (file, "STMTS:%ld)\n", n_stmts);
 175   fprintf (file, "\nSCoP profiling statistics (");
 176   fprintf (file, "BBS:%ld, ", n_p_bbs);
 177   fprintf (file, "LOOPS:%ld, ", n_p_loops);
 178   fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
 179   fprintf (file, "STMTS:%ld)\n", n_p_stmts);
 180 }
 181
 182 /* Print statistics for SCOPS to FILE.  */
 183
 184 static void
 185 print_graphite_statistics (FILE* file, vec<scop_p> scops)
 186 {
 187   int i;
 188
 189   scop_p scop;
 190
 191   FOR_EACH_VEC_ELT (scops, i, scop)
 192     print_graphite_scop_statistics (file, scop);
 193 }
 194
 195 /* Initialize graphite: when there are no loops returns false.  */
 196
 197 static bool
 198 graphite_initialize (isl_ctx *ctx)
 199 {
 200   if (number_of_loops () <= 1
 201       /* FIXME: This limit on the number of basic blocks of a function
 202          should be removed when the SCOP detection is faster.  */
 203       || n_basic_blocks > PARAM_VALUE (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION))
 204     {
 205       if (dump_file && (dump_flags & TDF_DETAILS))
 206         print_global_statistics (dump_file);
 207
 208       isl_ctx_free (ctx);
 209       return false;
 210     }
 211
 212   scev_reset ();
 213   recompute_all_dominators ();
 214   initialize_original_copy_tables ();
 215
 216   cloog_state = cloog_isl_state_malloc (ctx);
 217
 218   if (dump_file && dump_flags)
 219     dump_function_to_file (current_function_decl, dump_file, dump_flags);
 220
 221   return true;
 222 }
 223
 224 /* Finalize graphite: perform CFG cleanup when NEED_CFG_CLEANUP_P is
 225    true.  */
 226
 227 static void
 228 graphite_finalize (bool need_cfg_cleanup_p)
 229 {
 230   if (need_cfg_cleanup_p)
 231     {
 232       scev_reset ();
 233       cleanup_tree_cfg ();
 234       profile_status = PROFILE_ABSENT;
 235       release_recorded_exits ();
 236       tree_estimate_probability ();
 237     }
 238
 239   cloog_state_free (cloog_state);
 240   free_original_copy_tables ();
 241
 242   if (dump_file && dump_flags)
 243     print_loops (dump_file, 3);
 244 }
 245
 246 isl_ctx *the_isl_ctx;
 247
 248 /* Perform a set of linear transforms on the loops of the current
 249    function.  */
 250
 251 void
 252 graphite_transform_loops (void)
 253 {
 254   int i;
 255   scop_p scop;
 256   bool need_cfg_cleanup_p = false;
 257   vec<scop_p> scops = vNULL;
 258   htab_t bb_pbb_mapping;
 259   isl_ctx *ctx;
 260
 261   /* If a function is parallel it was most probably already run through graphite
 262      once. No need to run again.  */
 263   if (parallelized_function_p (cfun->decl))
 264     return;
 265
 266   ctx = isl_ctx_alloc ();
 267   isl_options_set_on_error(ctx, ISL_ON_ERROR_ABORT);
 268   if (!graphite_initialize (ctx))
 269     return;
 270
 271   the_isl_ctx = ctx;
 272   build_scops (&scops);
 273
 274   if (dump_file && (dump_flags & TDF_DETAILS))
 275     {
 276       print_graphite_statistics (dump_file, scops);
 277       print_global_statistics (dump_file);
 278     }
 279
 280   bb_pbb_mapping = htab_create (10, bb_pbb_map_hash, eq_bb_pbb_map, free);
 281
 282   FOR_EACH_VEC_ELT (scops, i, scop)
 283     if (dbg_cnt (graphite_scop))
 284       {
 285         scop->ctx = ctx;
 286         build_poly_scop (scop);
 287
 288         if (POLY_SCOP_P (scop)
 289             && apply_poly_transforms (scop)
 290             && gloog (scop, bb_pbb_mapping))
 291           need_cfg_cleanup_p = true;
 292       }
 293
 294   htab_delete (bb_pbb_mapping);
 295   free_scops (scops);
 296   graphite_finalize (need_cfg_cleanup_p);
 297   the_isl_ctx = NULL;
 298   isl_ctx_free (ctx);
 299 }
 300
 301 #else /* If Cloog is not available: #ifndef HAVE_cloog.  */
 302
 303 void
 304 graphite_transform_loops (void)
 305 {
 306   sorry ("Graphite loop optimizations cannot be used");
 307 }
 308
 309 #endif