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