gcc/graphite.c

   1 /* Gimple Represented as Polyhedra.
   2    Copyright (C) 2006, 2007, 2008, 2009 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 /* ICI internal interface.  */
  60 #include "highlev-plugin-internal.h"
  61
  62 #ifdef HAVE_cloog
  63
  64 #include "cloog/cloog.h"
  65 #include "ppl_c.h"
  66 #include "graphite-ppl.h"
  67 #include "graphite.h"
  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
  73 /* Print global statistics to FILE.  */
  74
  75 static void
  76 print_global_statistics (FILE* file)
  77 {
  78   long n_bbs = 0;
  79   long n_loops = 0;
  80   long n_stmts = 0;
  81   long n_conditions = 0;
  82   long n_p_bbs = 0;
  83   long n_p_loops = 0;
  84   long n_p_stmts = 0;
  85   long n_p_conditions = 0;
  86
  87   basic_block bb;
  88
  89   FOR_ALL_BB (bb)
  90     {
  91       gimple_stmt_iterator psi;
  92
  93       n_bbs++;
  94       n_p_bbs += bb->count;
  95
  96       /* Ignore artificial surrounding loop.  */
  97       if (bb == bb->loop_father->header
  98           && bb->index != 0)
  99         {
 100           n_loops++;
 101           n_p_loops += bb->count;
 102         }
 103
 104       if (VEC_length (edge, bb->succs) > 1)
 105         {
 106           n_conditions++;
 107           n_p_conditions += bb->count;
 108         }
 109
 110       for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
 111         {
 112           n_stmts++;
 113           n_p_stmts += bb->count;
 114         }
 115     }
 116
 117   fprintf (file, "\nGlobal statistics (");
 118   fprintf (file, "BBS:%ld, ", n_bbs);
 119   fprintf (file, "LOOPS:%ld, ", n_loops);
 120   fprintf (file, "CONDITIONS:%ld, ", n_conditions);
 121   fprintf (file, "STMTS:%ld)\n", n_stmts);
 122   fprintf (file, "\nGlobal profiling statistics (");
 123   fprintf (file, "BBS:%ld, ", n_p_bbs);
 124   fprintf (file, "LOOPS:%ld, ", n_p_loops);
 125   fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
 126   fprintf (file, "STMTS:%ld)\n", n_p_stmts);
 127 }
 128
 129 /* Print statistics for SCOP to FILE.  */
 130
 131 static void
 132 print_graphite_scop_statistics (FILE* file, scop_p scop)
 133 {
 134   long n_bbs = 0;
 135   long n_loops = 0;
 136   long n_stmts = 0;
 137   long n_conditions = 0;
 138   long n_p_bbs = 0;
 139   long n_p_loops = 0;
 140   long n_p_stmts = 0;
 141   long n_p_conditions = 0;
 142
 143   basic_block bb;
 144
 145   FOR_ALL_BB (bb)
 146     {
 147       gimple_stmt_iterator psi;
 148       loop_p loop = bb->loop_father;
 149
 150       if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
 151         continue;
 152
 153       n_bbs++;
 154       n_p_bbs += bb->count;
 155
 156       if (VEC_length (edge, bb->succs) > 1)
 157         {
 158           n_conditions++;
 159           n_p_conditions += bb->count;
 160         }
 161
 162       for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
 163         {
 164           n_stmts++;
 165           n_p_stmts += bb->count;
 166         }
 167
 168       if (loop->header == bb && loop_in_sese_p (loop, SCOP_REGION (scop)))
 169         {
 170           n_loops++;
 171           n_p_loops += bb->count;
 172         }
 173     }
 174
 175   fprintf (file, "\nSCoP statistics (");
 176   fprintf (file, "BBS:%ld, ", n_bbs);
 177   fprintf (file, "LOOPS:%ld, ", n_loops);
 178   fprintf (file, "CONDITIONS:%ld, ", n_conditions);
 179   fprintf (file, "STMTS:%ld)\n", n_stmts);
 180   fprintf (file, "\nSCoP profiling statistics (");
 181   fprintf (file, "BBS:%ld, ", n_p_bbs);
 182   fprintf (file, "LOOPS:%ld, ", n_p_loops);
 183   fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
 184   fprintf (file, "STMTS:%ld)\n", n_p_stmts);
 185 }
 186
 187 /* Print statistics for SCOPS to FILE.  */
 188
 189 static void
 190 print_graphite_statistics (FILE* file, VEC (scop_p, heap) *scops)
 191 {
 192   int i;
 193
 194   scop_p scop;
 195
 196   for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
 197     print_graphite_scop_statistics (file, scop);
 198 }
 199
 200 /* Initialize graphite: when there are no loops returns false.  */
 201
 202 static bool
 203 graphite_initialize (void)
 204 {
 205   if (number_of_loops () <= 1)
 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       cleanup_tree_cfg ();
 232       profile_status = PROFILE_ABSENT;
 233       release_recorded_exits ();
 234       tree_estimate_probability ();
 235     }
 236
 237   cloog_finalize ();
 238   free_original_copy_tables ();
 239   free_aux_in_new_loops ();
 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
 257   if (!graphite_initialize ())
 258     return;
 259
 260   build_scops (&scops);
 261
 262   if (dump_file && (dump_flags & TDF_DETAILS))
 263     {
 264       print_graphite_statistics (dump_file, scops);
 265       print_global_statistics (dump_file);
 266     }
 267
 268   bb_pbb_mapping = htab_create (10, bb_pbb_map_hash, eq_bb_pbb_map, free);
 269
 270   for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
 271     {
 272       bool transform_done = false;
 273
 274       if (!build_poly_scop (scop))
 275         continue;
 276
 277       if (apply_poly_transforms (scop))
 278         transform_done = gloog (scop, bb_pbb_mapping);
 279       else
 280         check_poly_representation (scop);
 281
 282       if (transform_done)
 283         {
 284           scev_reset ();
 285           need_cfg_cleanup_p = true;
 286         }
 287     }
 288
 289   if (flag_loop_parallelize_all)
 290     mark_loops_parallel (bb_pbb_mapping);
 291
 292   htab_delete (bb_pbb_mapping);
 293   free_scops (scops);
 294   graphite_finalize (need_cfg_cleanup_p);
 295 }
 296
 297 #else /* If Cloog is not available: #ifndef HAVE_cloog.  */
 298
 299 void
 300 graphite_transform_loops (void)
 301 {
 302   sorry ("Graphite loop optimizations cannot be used");
 303 }
 304
 305 #endif