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 #ifdef HAVE_cloog
  60
  61 /* The CLooG header file is not -Wc++-compat ready as of 2009-05-11.
  62    This #pragma should be removed when it is ready.  */
  63 #if GCC_VERSION >= 4003
  64 #pragma GCC diagnostic warning "-Wc++-compat"
  65 #endif
  66
  67 #include "cloog/cloog.h"
  68 #include "ppl_c.h"
  69 #include "graphite-ppl.h"
  70 #include "graphite.h"
  71 #include "graphite-poly.h"
  72 #include "graphite-scop-detection.h"
  73 #include "graphite-clast-to-gimple.h"
  74 #include "graphite-sese-to-poly.h"
  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 (VEC_length (edge, 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 (VEC_length (edge, 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, heap) *scops)
 194 {
 195   int i;
 196
 197   scop_p scop;
 198
 199   for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
 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 (void)
 207 {
 208   if (number_of_loops () <= 1)
 209     {
 210       if (dump_file && (dump_flags & TDF_DETAILS))
 211         print_global_statistics (dump_file);
 212
 213       return false;
 214     }
 215
 216   recompute_all_dominators ();
 217   initialize_original_copy_tables ();
 218   cloog_initialize ();
 219
 220   if (dump_file && dump_flags)
 221     dump_function_to_file (current_function_decl, dump_file, dump_flags);
 222
 223   return true;
 224 }
 225
 226 /* Finalize graphite: perform CFG cleanup when NEED_CFG_CLEANUP_P is
 227    true.  */
 228
 229 static void
 230 graphite_finalize (bool need_cfg_cleanup_p)
 231 {
 232   if (need_cfg_cleanup_p)
 233     {
 234       cleanup_tree_cfg ();
 235       profile_status = PROFILE_ABSENT;
 236       release_recorded_exits ();
 237       tree_estimate_probability ();
 238     }
 239
 240   cloog_finalize ();
 241   free_original_copy_tables ();
 242   free_aux_in_new_loops ();
 243
 244   if (dump_file && dump_flags)
 245     print_loops (dump_file, 3);
 246 }
 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, heap) *scops = NULL;
 258   htab_t bb_pbb_mapping;
 259
 260   if (!graphite_initialize ())
 261     return;
 262
 263   build_scops (&scops);
 264
 265   if (dump_file && (dump_flags & TDF_DETAILS))
 266     {
 267       print_graphite_statistics (dump_file, scops);
 268       print_global_statistics (dump_file);
 269     }
 270
 271   bb_pbb_mapping = htab_create (10, bb_pbb_map_hash, eq_bb_pbb_map, free);
 272
 273   for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
 274     {
 275       bool transform_done = false;
 276
 277       if (!build_poly_scop (scop))
 278         continue;
 279
 280       if (apply_poly_transforms (scop))
 281         transform_done = gloog (scop, bb_pbb_mapping);
 282       else
 283         check_poly_representation (scop);
 284
 285       if (transform_done)
 286         {
 287           scev_reset ();
 288           need_cfg_cleanup_p = true;
 289         }
 290     }
 291
 292   if (flag_loop_parallelize_all)
 293     mark_loops_parallel (bb_pbb_mapping);
 294
 295   htab_delete (bb_pbb_mapping);
 296   free_scops (scops);
 297   graphite_finalize (need_cfg_cleanup_p);
 298 }
 299
 300 #else /* If Cloog is not available: #ifndef HAVE_cloog.  */
 301
 302 void
 303 graphite_transform_loops (void)
 304 {
 305   sorry ("Graphite loop optimizations cannot be used");
 306 }
 307
 308 #endif