1/* Gimple Represented as Polyhedra.
2   Copyright (C) 2006-2015 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
37#ifdef HAVE_isl
38#include <isl/constraint.h>
39#include <isl/set.h>
40#include <isl/map.h>
41#include <isl/options.h>
42#include <isl/union_map.h>
43#endif
44
45#include "system.h"
46#include "coretypes.h"
47#include "diagnostic-core.h"
48#include "hash-set.h"
49#include "machmode.h"
50#include "vec.h"
51#include "double-int.h"
52#include "input.h"
53#include "alias.h"
54#include "symtab.h"
55#include "options.h"
56#include "wide-int.h"
57#include "inchash.h"
58#include "tree.h"
59#include "fold-const.h"
60#include "predict.h"
61#include "tm.h"
62#include "hard-reg-set.h"
63#include "input.h"
64#include "function.h"
65#include "dominance.h"
66#include "cfg.h"
67#include "basic-block.h"
68#include "tree-ssa-alias.h"
69#include "internal-fn.h"
70#include "gimple-expr.h"
71#include "is-a.h"
72#include "gimple.h"
73#include "gimple-iterator.h"
74#include "tree-cfg.h"
75#include "tree-ssa-loop.h"
76#include "tree-dump.h"
77#include "cfgloop.h"
78#include "tree-chrec.h"
79#include "tree-data-ref.h"
80#include "tree-scalar-evolution.h"
81#include "sese.h"
82#include "dbgcnt.h"
83#include "tree-parloops.h"
84#include "tree-pass.h"
85#include "tree-cfgcleanup.h"
86
87#ifdef HAVE_isl
88
89#include "graphite-poly.h"
90#include "graphite-scop-detection.h"
91#include "graphite-isl-ast-to-gimple.h"
92#include "graphite-sese-to-poly.h"
93
94/* Print global statistics to FILE.  */
95
96static void
97print_global_statistics (FILE* file)
98{
99  long n_bbs = 0;
100  long n_loops = 0;
101  long n_stmts = 0;
102  long n_conditions = 0;
103  long n_p_bbs = 0;
104  long n_p_loops = 0;
105  long n_p_stmts = 0;
106  long n_p_conditions = 0;
107
108  basic_block bb;
109
110  FOR_ALL_BB_FN (bb, cfun)
111    {
112      gimple_stmt_iterator psi;
113
114      n_bbs++;
115      n_p_bbs += bb->count;
116
117      /* Ignore artificial surrounding loop.  */
118      if (bb == bb->loop_father->header
119	  && bb->index != 0)
120	{
121	  n_loops++;
122	  n_p_loops += bb->count;
123	}
124
125      if (EDGE_COUNT (bb->succs) > 1)
126	{
127	  n_conditions++;
128	  n_p_conditions += bb->count;
129	}
130
131      for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
132	{
133	  n_stmts++;
134	  n_p_stmts += bb->count;
135	}
136    }
137
138  fprintf (file, "\nGlobal statistics (");
139  fprintf (file, "BBS:%ld, ", n_bbs);
140  fprintf (file, "LOOPS:%ld, ", n_loops);
141  fprintf (file, "CONDITIONS:%ld, ", n_conditions);
142  fprintf (file, "STMTS:%ld)\n", n_stmts);
143  fprintf (file, "\nGlobal profiling statistics (");
144  fprintf (file, "BBS:%ld, ", n_p_bbs);
145  fprintf (file, "LOOPS:%ld, ", n_p_loops);
146  fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
147  fprintf (file, "STMTS:%ld)\n", n_p_stmts);
148}
149
150/* Print statistics for SCOP to FILE.  */
151
152static void
153print_graphite_scop_statistics (FILE* file, scop_p scop)
154{
155  long n_bbs = 0;
156  long n_loops = 0;
157  long n_stmts = 0;
158  long n_conditions = 0;
159  long n_p_bbs = 0;
160  long n_p_loops = 0;
161  long n_p_stmts = 0;
162  long n_p_conditions = 0;
163
164  basic_block bb;
165
166  FOR_ALL_BB_FN (bb, cfun)
167    {
168      gimple_stmt_iterator psi;
169      loop_p loop = bb->loop_father;
170
171      if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
172	continue;
173
174      n_bbs++;
175      n_p_bbs += bb->count;
176
177      if (EDGE_COUNT (bb->succs) > 1)
178	{
179	  n_conditions++;
180	  n_p_conditions += bb->count;
181	}
182
183      for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
184	{
185	  n_stmts++;
186	  n_p_stmts += bb->count;
187	}
188
189      if (loop->header == bb && loop_in_sese_p (loop, SCOP_REGION (scop)))
190	{
191	  n_loops++;
192	  n_p_loops += bb->count;
193	}
194    }
195
196  fprintf (file, "\nSCoP statistics (");
197  fprintf (file, "BBS:%ld, ", n_bbs);
198  fprintf (file, "LOOPS:%ld, ", n_loops);
199  fprintf (file, "CONDITIONS:%ld, ", n_conditions);
200  fprintf (file, "STMTS:%ld)\n", n_stmts);
201  fprintf (file, "\nSCoP profiling statistics (");
202  fprintf (file, "BBS:%ld, ", n_p_bbs);
203  fprintf (file, "LOOPS:%ld, ", n_p_loops);
204  fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
205  fprintf (file, "STMTS:%ld)\n", n_p_stmts);
206}
207
208/* Print statistics for SCOPS to FILE.  */
209
210static void
211print_graphite_statistics (FILE* file, vec<scop_p> scops)
212{
213  int i;
214
215  scop_p scop;
216
217  FOR_EACH_VEC_ELT (scops, i, scop)
218    print_graphite_scop_statistics (file, scop);
219}
220
221/* Initialize graphite: when there are no loops returns false.  */
222
223static bool
224graphite_initialize (isl_ctx *ctx)
225{
226  if (number_of_loops (cfun) <= 1
227      /* FIXME: This limit on the number of basic blocks of a function
228	 should be removed when the SCOP detection is faster.  */
229      || (n_basic_blocks_for_fn (cfun) >
230	  PARAM_VALUE (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION)))
231    {
232      if (dump_file && (dump_flags & TDF_DETAILS))
233	print_global_statistics (dump_file);
234
235      isl_ctx_free (ctx);
236      return false;
237    }
238
239  scev_reset ();
240  recompute_all_dominators ();
241  initialize_original_copy_tables ();
242
243  if (dump_file && dump_flags)
244    dump_function_to_file (current_function_decl, dump_file, dump_flags);
245
246  return true;
247}
248
249/* Finalize graphite: perform CFG cleanup when NEED_CFG_CLEANUP_P is
250   true.  */
251
252static void
253graphite_finalize (bool need_cfg_cleanup_p)
254{
255  if (need_cfg_cleanup_p)
256    {
257      scev_reset ();
258      cleanup_tree_cfg ();
259      profile_status_for_fn (cfun) = PROFILE_ABSENT;
260      release_recorded_exits ();
261      tree_estimate_probability ();
262    }
263
264  free_original_copy_tables ();
265
266  if (dump_file && dump_flags)
267    print_loops (dump_file, 3);
268}
269
270isl_ctx *the_isl_ctx;
271
272/* Perform a set of linear transforms on the loops of the current
273   function.  */
274
275void
276graphite_transform_loops (void)
277{
278  int i;
279  scop_p scop;
280  bool need_cfg_cleanup_p = false;
281  vec<scop_p> scops = vNULL;
282  isl_ctx *ctx;
283
284  /* If a function is parallel it was most probably already run through graphite
285     once. No need to run again.  */
286  if (parallelized_function_p (cfun->decl))
287    return;
288
289  ctx = isl_ctx_alloc ();
290  isl_options_set_on_error (ctx, ISL_ON_ERROR_ABORT);
291  if (!graphite_initialize (ctx))
292    return;
293
294  the_isl_ctx = ctx;
295  build_scops (&scops);
296
297  if (dump_file && (dump_flags & TDF_DETAILS))
298    {
299      print_graphite_statistics (dump_file, scops);
300      print_global_statistics (dump_file);
301    }
302
303  FOR_EACH_VEC_ELT (scops, i, scop)
304    if (dbg_cnt (graphite_scop))
305      {
306	scop->ctx = ctx;
307	build_poly_scop (scop);
308
309	if (POLY_SCOP_P (scop)
310	    && apply_poly_transforms (scop)
311	    && graphite_regenerate_ast_isl (scop))
312	  need_cfg_cleanup_p = true;
313
314      }
315
316  free_scops (scops);
317  graphite_finalize (need_cfg_cleanup_p);
318  the_isl_ctx = NULL;
319  isl_ctx_free (ctx);
320}
321
322#else /* If ISL is not available: #ifndef HAVE_isl.  */
323
324static void
325graphite_transform_loops (void)
326{
327  sorry ("Graphite loop optimizations cannot be used (ISL is not available).");
328}
329
330#endif
331
332
333static unsigned int
334graphite_transforms (struct function *fun)
335{
336  if (number_of_loops (fun) <= 1)
337    return 0;
338
339  graphite_transform_loops ();
340
341  return 0;
342}
343
344static bool
345gate_graphite_transforms (void)
346{
347  /* Enable -fgraphite pass if any one of the graphite optimization flags
348     is turned on.  */
349  if (flag_loop_block
350      || flag_loop_interchange
351      || flag_loop_strip_mine
352      || flag_graphite_identity
353      || flag_loop_parallelize_all
354      || flag_loop_optimize_isl
355      || flag_loop_unroll_jam)
356    flag_graphite = 1;
357
358  return flag_graphite != 0;
359}
360
361namespace {
362
363const pass_data pass_data_graphite =
364{
365  GIMPLE_PASS, /* type */
366  "graphite0", /* name */
367  OPTGROUP_LOOP, /* optinfo_flags */
368  TV_GRAPHITE, /* tv_id */
369  ( PROP_cfg | PROP_ssa ), /* properties_required */
370  0, /* properties_provided */
371  0, /* properties_destroyed */
372  0, /* todo_flags_start */
373  0, /* todo_flags_finish */
374};
375
376class pass_graphite : public gimple_opt_pass
377{
378public:
379  pass_graphite (gcc::context *ctxt)
380    : gimple_opt_pass (pass_data_graphite, ctxt)
381  {}
382
383  /* opt_pass methods: */
384  virtual bool gate (function *) { return gate_graphite_transforms (); }
385
386}; // class pass_graphite
387
388} // anon namespace
389
390gimple_opt_pass *
391make_pass_graphite (gcc::context *ctxt)
392{
393  return new pass_graphite (ctxt);
394}
395
396namespace {
397
398const pass_data pass_data_graphite_transforms =
399{
400  GIMPLE_PASS, /* type */
401  "graphite", /* name */
402  OPTGROUP_LOOP, /* optinfo_flags */
403  TV_GRAPHITE_TRANSFORMS, /* tv_id */
404  ( PROP_cfg | PROP_ssa ), /* properties_required */
405  0, /* properties_provided */
406  0, /* properties_destroyed */
407  0, /* todo_flags_start */
408  0, /* todo_flags_finish */
409};
410
411class pass_graphite_transforms : public gimple_opt_pass
412{
413public:
414  pass_graphite_transforms (gcc::context *ctxt)
415    : gimple_opt_pass (pass_data_graphite_transforms, ctxt)
416  {}
417
418  /* opt_pass methods: */
419  virtual bool gate (function *) { return gate_graphite_transforms (); }
420  virtual unsigned int execute (function *fun) { return graphite_transforms (fun); }
421
422}; // class pass_graphite_transforms
423
424} // anon namespace
425
426gimple_opt_pass *
427make_pass_graphite_transforms (gcc::context *ctxt)
428{
429  return new pass_graphite_transforms (ctxt);
430}
431
432
433