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