gcc/graphite.c

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