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