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