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
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along 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#include "cloog/cloog.h"
62#include "ppl_c.h"
63#include "graphite-ppl.h"
64#include "graphite.h"
65#include "graphite-poly.h"
66#include "graphite-scop-detection.h"
67#include "graphite-clast-to-gimple.h"
68#include "graphite-sese-to-poly.h"
69
70/* Print global statistics to FILE.  */
71
72static void
73print_global_statistics (FILE* file)
74{
75  long n_bbs = 0;
76  long n_loops = 0;
77  long n_stmts = 0;
78  long n_conditions = 0;
79  long n_p_bbs = 0;
80  long n_p_loops = 0;
81  long n_p_stmts = 0;
82  long n_p_conditions = 0;
83
84  basic_block bb;
85
86  FOR_ALL_BB (bb)
87    {
88      gimple_stmt_iterator psi;
89
90      n_bbs++;
91      n_p_bbs += bb->count;
92
93      /* Ignore artificial surrounding loop.  */
94      if (bb == bb->loop_father->header
95	  && bb->index != 0)
96	{
97	  n_loops++;
98	  n_p_loops += bb->count;
99	}
100
101      if (VEC_length (edge, bb->succs) > 1)
102	{
103	  n_conditions++;
104	  n_p_conditions += bb->count;
105	}
106
107      for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
108	{
109	  n_stmts++;
110	  n_p_stmts += bb->count;
111	}
112    }
113
114  fprintf (file, "\nGlobal statistics (");
115  fprintf (file, "BBS:%ld, ", n_bbs);
116  fprintf (file, "LOOPS:%ld, ", n_loops);
117  fprintf (file, "CONDITIONS:%ld, ", n_conditions);
118  fprintf (file, "STMTS:%ld)\n", n_stmts);
119  fprintf (file, "\nGlobal profiling statistics (");
120  fprintf (file, "BBS:%ld, ", n_p_bbs);
121  fprintf (file, "LOOPS:%ld, ", n_p_loops);
122  fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
123  fprintf (file, "STMTS:%ld)\n", n_p_stmts);
124}
125
126/* Print statistics for SCOP to FILE.  */
127
128static void
129print_graphite_scop_statistics (FILE* file, scop_p scop)
130{
131  long n_bbs = 0;
132  long n_loops = 0;
133  long n_stmts = 0;
134  long n_conditions = 0;
135  long n_p_bbs = 0;
136  long n_p_loops = 0;
137  long n_p_stmts = 0;
138  long n_p_conditions = 0;
139
140  basic_block bb;
141
142  FOR_ALL_BB (bb)
143    {
144      gimple_stmt_iterator psi;
145      loop_p loop = bb->loop_father;
146
147      if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
148	continue;
149
150      n_bbs++;
151      n_p_bbs += bb->count;
152
153      if (VEC_length (edge, bb->succs) > 1)
154	{
155	  n_conditions++;
156	  n_p_conditions += bb->count;
157	}
158
159      for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
160	{
161	  n_stmts++;
162	  n_p_stmts += bb->count;
163	}
164
165      if (loop->header == bb && loop_in_sese_p (loop, SCOP_REGION (scop)))
166	{
167	  n_loops++;
168	  n_p_loops += bb->count;
169	}
170    }
171
172  fprintf (file, "\nSCoP statistics (");
173  fprintf (file, "BBS:%ld, ", n_bbs);
174  fprintf (file, "LOOPS:%ld, ", n_loops);
175  fprintf (file, "CONDITIONS:%ld, ", n_conditions);
176  fprintf (file, "STMTS:%ld)\n", n_stmts);
177  fprintf (file, "\nSCoP profiling statistics (");
178  fprintf (file, "BBS:%ld, ", n_p_bbs);
179  fprintf (file, "LOOPS:%ld, ", n_p_loops);
180  fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
181  fprintf (file, "STMTS:%ld)\n", n_p_stmts);
182}
183
184/* Print statistics for SCOPS to FILE.  */
185
186static void
187print_graphite_statistics (FILE* file, VEC (scop_p, heap) *scops)
188{
189  int i;
190
191  scop_p scop;
192
193  for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
194    print_graphite_scop_statistics (file, scop);
195}
196
197/* Initialize graphite: when there are no loops returns false.  */
198
199static bool
200graphite_initialize (void)
201{
202  if (number_of_loops () <= 1
203      /* FIXME: This limit on the number of basic blocks of a function
204	 should be removed when the SCOP detection is faster.  */
205      || n_basic_blocks > PARAM_VALUE (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION))
206    {
207      if (dump_file && (dump_flags & TDF_DETAILS))
208	print_global_statistics (dump_file);
209
210      return false;
211    }
212
213  scev_reset ();
214  recompute_all_dominators ();
215  initialize_original_copy_tables ();
216  cloog_initialize ();
217
218  if (dump_file && dump_flags)
219    dump_function_to_file (current_function_decl, dump_file, dump_flags);
220
221  return true;
222}
223
224/* Finalize graphite: perform CFG cleanup when NEED_CFG_CLEANUP_P is
225   true.  */
226
227static void
228graphite_finalize (bool need_cfg_cleanup_p)
229{
230  if (need_cfg_cleanup_p)
231    {
232      scev_reset ();
233      cleanup_tree_cfg ();
234      profile_status = PROFILE_ABSENT;
235      release_recorded_exits ();
236      tree_estimate_probability ();
237    }
238
239  cloog_finalize ();
240  free_original_copy_tables ();
241
242  if (dump_file && dump_flags)
243    print_loops (dump_file, 3);
244}
245
246/* Perform a set of linear transforms on the loops of the current
247   function.  */
248
249void
250graphite_transform_loops (void)
251{
252  int i;
253  scop_p scop;
254  bool need_cfg_cleanup_p = false;
255  VEC (scop_p, heap) *scops = NULL;
256  htab_t bb_pbb_mapping;
257
258  if (!graphite_initialize ())
259    return;
260
261  build_scops (&scops);
262
263  if (dump_file && (dump_flags & TDF_DETAILS))
264    {
265      print_graphite_statistics (dump_file, scops);
266      print_global_statistics (dump_file);
267    }
268
269  bb_pbb_mapping = htab_create (10, bb_pbb_map_hash, eq_bb_pbb_map, free);
270
271  for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
272    build_poly_scop (scop);
273
274  for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
275    if (POLY_SCOP_P (scop)
276	&& apply_poly_transforms (scop)
277	&& gloog (scop, scops, bb_pbb_mapping))
278      need_cfg_cleanup_p = true;
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
287void
288graphite_transform_loops (void)
289{
290  sorry ("Graphite loop optimizations cannot be used");
291}
292
293#endif
294