1/* Graphite polyhedral representation.
2   Copyright (C) 2009-2020 Free Software Foundation, Inc.
3   Contributed by Sebastian Pop <sebastian.pop@amd.com> and
4   Tobias Grosser <grosser@fim.uni-passau.de>.
5
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify
9it under the terms of the GNU General Public License as published by
10the Free Software Foundation; either version 3, or (at your option)
11any later version.
12
13GCC is distributed in the hope that it will be useful,
14but WITHOUT ANY WARRANTY; without even the implied warranty of
15MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16GNU General Public License for more details.
17
18You should have received a copy of the GNU General Public License
19along with GCC; see the file COPYING3.  If not see
20<http://www.gnu.org/licenses/>.  */
21
22#define USES_ISL
23
24#include "config.h"
25
26#ifdef HAVE_isl
27
28#include "system.h"
29#include "coretypes.h"
30#include "backend.h"
31#include "tree.h"
32#include "gimple.h"
33#include "cfghooks.h"
34#include "diagnostic-core.h"
35#include "fold-const.h"
36#include "gimple-iterator.h"
37#include "tree-ssa-loop.h"
38#include "cfgloop.h"
39#include "tree-data-ref.h"
40#include "pretty-print.h"
41#include "gimple-pretty-print.h"
42#include "graphite.h"
43#include "dumpfile.h"
44
45/* Print to STDERR the GMP value VAL.  */
46
47DEBUG_FUNCTION void
48debug_gmp_value (mpz_t val)
49{
50  gmp_fprintf (stderr, "%Zd", val);
51}
52
53/* Prints to FILE the iteration domain of PBB.  */
54
55void
56print_iteration_domain (FILE *file, poly_bb_p pbb)
57{
58  print_pbb_domain (file, pbb);
59}
60
61/* Prints to FILE the iteration domains of every PBB of SCOP.  */
62
63void
64print_iteration_domains (FILE *file, scop_p scop)
65{
66  int i;
67  poly_bb_p pbb;
68
69  FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
70    print_iteration_domain (file, pbb);
71}
72
73/* Prints to STDERR the iteration domain of PBB.  */
74
75DEBUG_FUNCTION void
76debug_iteration_domain (poly_bb_p pbb)
77{
78  print_iteration_domain (stderr, pbb);
79}
80
81/* Prints to STDERR the iteration domains of every PBB of SCOP.  */
82
83DEBUG_FUNCTION void
84debug_iteration_domains (scop_p scop)
85{
86  print_iteration_domains (stderr, scop);
87}
88
89/* Create a new polyhedral data reference and add it to PBB.  It is
90   defined by its ACCESSES, its TYPE, and the number of subscripts
91   NB_SUBSCRIPTS.  */
92
93void
94new_poly_dr (poly_bb_p pbb, gimple *stmt, enum poly_dr_type type,
95	     isl_map *acc, isl_set *subscript_sizes)
96{
97  static int id = 0;
98  poly_dr_p pdr = XNEW (struct poly_dr);
99
100  pdr->stmt = stmt;
101  PDR_ID (pdr) = id++;
102  PDR_NB_REFS (pdr) = 1;
103  PDR_PBB (pdr) = pbb;
104  pdr->accesses = acc;
105  pdr->subscript_sizes = subscript_sizes;
106  PDR_TYPE (pdr) = type;
107  PBB_DRS (pbb).safe_push (pdr);
108
109  if (dump_file)
110    {
111      fprintf (dump_file, "Converting dr: ");
112      print_pdr (dump_file, pdr);
113      fprintf (dump_file, "To polyhedral representation:\n");
114      fprintf (dump_file, "  - access functions: ");
115      print_isl_map (dump_file, acc);
116      fprintf (dump_file, "  - subscripts: ");
117      print_isl_set (dump_file, subscript_sizes);
118    }
119}
120
121/* Free polyhedral data reference PDR.  */
122
123static void
124free_poly_dr (poly_dr_p pdr)
125{
126  isl_map_free (pdr->accesses);
127  isl_set_free (pdr->subscript_sizes);
128  XDELETE (pdr);
129}
130
131/* Create a new polyhedral black box.  */
132
133poly_bb_p
134new_poly_bb (scop_p scop, gimple_poly_bb_p black_box)
135{
136  poly_bb_p pbb = XNEW (struct poly_bb);
137
138  pbb->domain = NULL;
139  pbb->iterators = NULL;
140  PBB_SCOP (pbb) = scop;
141  pbb_set_black_box (pbb, black_box);
142  PBB_DRS (pbb).create (3);
143  GBB_PBB ((gimple_poly_bb_p) black_box) = pbb;
144
145  return pbb;
146}
147
148/* Free polyhedral black box.  */
149
150static void
151free_poly_bb (poly_bb_p pbb)
152{
153  int i;
154  poly_dr_p pdr;
155
156  isl_set_free (pbb->domain);
157  pbb->domain = NULL;
158  isl_set_free (pbb->iterators);
159  pbb->iterators = NULL;
160
161  if (PBB_DRS (pbb).exists ())
162    FOR_EACH_VEC_ELT (PBB_DRS (pbb), i, pdr)
163      free_poly_dr (pdr);
164
165  PBB_DRS (pbb).release ();
166  XDELETE (pbb);
167}
168
169/* Prints to FILE the polyhedral data reference PDR.  */
170
171void
172print_pdr (FILE *file, poly_dr_p pdr)
173{
174  fprintf (file, "pdr_%d (", PDR_ID (pdr));
175
176  switch (PDR_TYPE (pdr))
177    {
178    case PDR_READ:
179      fprintf (file, "read \n");
180      break;
181
182    case PDR_WRITE:
183      fprintf (file, "write \n");
184      break;
185
186    case PDR_MAY_WRITE:
187      fprintf (file, "may_write \n");
188      break;
189
190    default:
191      gcc_unreachable ();
192    }
193
194  fprintf (file, "in gimple stmt: ");
195  print_gimple_stmt (file, pdr->stmt, 0);
196  fprintf (file, "data accesses: ");
197  print_isl_map (file, pdr->accesses);
198  fprintf (file, "subscript sizes: ");
199  print_isl_set (file, pdr->subscript_sizes);
200  fprintf (file, ")\n");
201}
202
203/* Prints to STDERR the polyhedral data reference PDR.  */
204
205DEBUG_FUNCTION void
206debug_pdr (poly_dr_p pdr)
207{
208  print_pdr (stderr, pdr);
209}
210
211/* Store the GRAPHITE representation of BB.  */
212
213gimple_poly_bb_p
214new_gimple_poly_bb (basic_block bb, vec<data_reference_p> drs,
215		    vec<scalar_use> reads, vec<tree> writes)
216{
217  gimple_poly_bb_p gbb = XNEW (struct gimple_poly_bb);
218  GBB_BB (gbb) = bb;
219  GBB_DATA_REFS (gbb) = drs;
220  gbb->read_scalar_refs = reads;
221  gbb->write_scalar_refs = writes;
222  GBB_CONDITIONS (gbb).create (0);
223  GBB_CONDITION_CASES (gbb).create (0);
224
225  return gbb;
226}
227
228/* Frees GBB.  */
229
230static void
231free_gimple_poly_bb (gimple_poly_bb_p gbb)
232{
233  free_data_refs (GBB_DATA_REFS (gbb));
234  GBB_CONDITIONS (gbb).release ();
235  GBB_CONDITION_CASES (gbb).release ();
236  gbb->read_scalar_refs.release ();
237  gbb->write_scalar_refs.release ();
238  XDELETE (gbb);
239}
240
241/* Deletes all gimple bbs in SCOP.  */
242
243static void
244remove_gbbs_in_scop (scop_p scop)
245{
246  int i;
247  poly_bb_p pbb;
248
249  FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
250    free_gimple_poly_bb (PBB_BLACK_BOX (pbb));
251}
252
253/* Creates a new SCOP containing the region (ENTRY, EXIT).  */
254
255scop_p
256new_scop (edge entry, edge exit)
257{
258  sese_info_p region = new_sese_info (entry, exit);
259  scop_p s = XNEW (struct scop);
260
261  s->original_schedule = NULL;
262  s->transformed_schedule = NULL;
263  s->param_context = NULL;
264  scop_set_region (s, region);
265  s->pbbs.create (3);
266  s->drs.create (3);
267  s->dependence = NULL;
268  return s;
269}
270
271/* Deletes SCOP.  */
272
273void
274free_scop (scop_p scop)
275{
276  int i;
277  poly_bb_p pbb;
278
279  remove_gbbs_in_scop (scop);
280  free_sese_info (scop->scop_info);
281
282  FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
283    free_poly_bb (pbb);
284
285  scop->pbbs.release ();
286  scop->drs.release ();
287
288  isl_set_free (scop->param_context);
289  scop->param_context = NULL;
290  isl_union_map_free (scop->dependence);
291  scop->dependence = NULL;
292  isl_schedule_free (scop->original_schedule);
293  scop->original_schedule = NULL;
294  isl_schedule_free (scop->transformed_schedule);
295  scop->transformed_schedule = NULL;
296  XDELETE (scop);
297}
298
299/* Print to FILE the domain of PBB.  */
300
301void
302print_pbb_domain (FILE *file, poly_bb_p pbb)
303{
304  print_isl_set (file, pbb->domain);
305}
306
307/* Dump the cases of a graphite basic block GBB on FILE.  */
308
309static void
310dump_gbb_cases (FILE *file, gimple_poly_bb_p gbb)
311{
312  int i;
313  gimple *stmt;
314  vec<gimple *> cases;
315
316  if (!gbb)
317    return;
318
319  cases = GBB_CONDITION_CASES (gbb);
320  if (cases.is_empty ())
321    return;
322
323  fprintf (file, "cases bb_%d (\n", GBB_BB (gbb)->index);
324
325  FOR_EACH_VEC_ELT (cases, i, stmt)
326    print_gimple_stmt (file, stmt, 0);
327
328  fprintf (file, ")\n");
329}
330
331/* Dump conditions of a graphite basic block GBB on FILE.  */
332
333static void
334dump_gbb_conditions (FILE *file, gimple_poly_bb_p gbb)
335{
336  int i;
337  gimple *stmt;
338  vec<gimple *> conditions;
339
340  if (!gbb)
341    return;
342
343  conditions = GBB_CONDITIONS (gbb);
344  if (conditions.is_empty ())
345    return;
346
347  fprintf (file, "conditions bb_%d (\n", GBB_BB (gbb)->index);
348
349  FOR_EACH_VEC_ELT (conditions, i, stmt)
350    print_gimple_stmt (file, stmt, 0);
351
352  fprintf (file, ")\n");
353}
354
355/* Print to FILE all the data references of PBB.  */
356
357void
358print_pdrs (FILE *file, poly_bb_p pbb)
359{
360  int i;
361  poly_dr_p pdr;
362  int nb_reads = 0;
363  int nb_writes = 0;
364
365  if (PBB_DRS (pbb).is_empty ())
366    return;
367
368  fprintf (file, "Data references (\n");
369
370  FOR_EACH_VEC_ELT (PBB_DRS (pbb), i, pdr)
371    if (PDR_TYPE (pdr) == PDR_READ)
372      nb_reads++;
373    else
374      nb_writes++;
375
376  fprintf (file, "Read data references (\n");
377
378  FOR_EACH_VEC_ELT (PBB_DRS (pbb), i, pdr)
379    if (PDR_TYPE (pdr) == PDR_READ)
380      print_pdr (file, pdr);
381
382  fprintf (file, ")\n");
383  fprintf (file, "Write data references (\n");
384  FOR_EACH_VEC_ELT (PBB_DRS (pbb), i, pdr)
385    if (PDR_TYPE (pdr) != PDR_READ)
386      print_pdr (file, pdr);
387  fprintf (file, ")\n");
388  fprintf (file, ")\n");
389}
390
391/* Print to STDERR all the data references of PBB.  */
392
393DEBUG_FUNCTION void
394debug_pdrs (poly_bb_p pbb)
395{
396  print_pdrs (stderr, pbb);
397}
398
399/* Print to FILE the body of PBB.  */
400
401static void
402print_pbb_body (FILE *file, poly_bb_p pbb)
403{
404  fprintf (file, "Body (\n");
405  dump_bb (file, pbb_bb (pbb), 0, TDF_NONE);
406  fprintf (file, ")\n");
407}
408
409/* Print to FILE the domain and scattering function of PBB.  */
410
411void
412print_pbb (FILE *file, poly_bb_p pbb)
413{
414  fprintf (file, "pbb_%d (\n", pbb_index (pbb));
415  dump_gbb_conditions (file, PBB_BLACK_BOX (pbb));
416  dump_gbb_cases (file, PBB_BLACK_BOX (pbb));
417
418  print_pbb_domain (file, pbb);
419  print_pdrs (file, pbb);
420  print_pbb_body (file, pbb);
421
422  fprintf (file, ")\n");
423}
424
425/* Print to FILE the parameters of SCOP.  */
426
427void
428print_scop_params (FILE *file, scop_p scop)
429{
430  if (scop->scop_info->params.is_empty ())
431    return;
432
433  int i;
434  tree t;
435  fprintf (file, "parameters (");
436  FOR_EACH_VEC_ELT (scop->scop_info->params, i, t)
437    {
438      print_generic_expr (file, t);
439      fprintf (file, ", ");
440    }
441  fprintf (file, ")\n");
442}
443
444/* Print to FILE the context of SCoP.  */
445
446void
447print_scop_context (FILE *file, scop_p scop)
448{
449  if (!scop->param_context)
450    return;
451
452  fprintf (file, "Context (\n");
453  print_isl_set (file, scop->param_context);
454  fprintf (file, ")\n");
455}
456
457/* Print to FILE the SCOP.  */
458
459void
460print_scop (FILE *file, scop_p scop)
461{
462  int i;
463  poly_bb_p pbb;
464
465  fprintf (file, "SCoP (\n");
466  print_scop_context (file, scop);
467  print_scop_params (file, scop);
468
469  fprintf (file, "Number of statements: ");
470  fprintf (file, "%d\n", scop->pbbs.length ());
471
472  FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
473    print_pbb (file, pbb);
474
475  fprintf (file, ")\n");
476}
477
478/* Print to STDERR the domain of PBB.  */
479
480DEBUG_FUNCTION void
481debug_pbb_domain (poly_bb_p pbb)
482{
483  print_pbb_domain (stderr, pbb);
484}
485
486/* Print to FILE the domain and scattering function of PBB.  */
487
488DEBUG_FUNCTION void
489debug_pbb (poly_bb_p pbb)
490{
491  print_pbb (stderr, pbb);
492}
493
494/* Print to STDERR the context of SCOP.  */
495
496DEBUG_FUNCTION void
497debug_scop_context (scop_p scop)
498{
499  print_scop_context (stderr, scop);
500}
501
502/* Print to STDERR the SCOP.  */
503
504DEBUG_FUNCTION void
505debug_scop (scop_p scop)
506{
507  print_scop (stderr, scop);
508}
509
510/* Print to STDERR the parameters of SCOP.  */
511
512DEBUG_FUNCTION void
513debug_scop_params (scop_p scop)
514{
515  print_scop_params (stderr, scop);
516}
517
518extern isl_ctx *the_isl_ctx;
519void
520print_isl_set (FILE *f, __isl_keep isl_set *set)
521{
522  isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
523  p = isl_printer_set_yaml_style (p, ISL_YAML_STYLE_BLOCK);
524  p = isl_printer_print_set (p, set);
525  p = isl_printer_print_str (p, "\n");
526  isl_printer_free (p);
527}
528
529DEBUG_FUNCTION void
530debug_isl_set (__isl_keep isl_set *set)
531{
532  print_isl_set (stderr, set);
533}
534
535void
536print_isl_map (FILE *f, __isl_keep isl_map *map)
537{
538  isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
539  p = isl_printer_set_yaml_style (p, ISL_YAML_STYLE_BLOCK);
540  p = isl_printer_print_map (p, map);
541  p = isl_printer_print_str (p, "\n");
542  isl_printer_free (p);
543}
544
545DEBUG_FUNCTION void
546debug_isl_map (__isl_keep isl_map *map)
547{
548  print_isl_map (stderr, map);
549}
550
551void
552print_isl_union_map (FILE *f, __isl_keep isl_union_map *map)
553{
554  isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
555  p = isl_printer_set_yaml_style (p, ISL_YAML_STYLE_BLOCK);
556  p = isl_printer_print_union_map (p, map);
557  p = isl_printer_print_str (p, "\n");
558  isl_printer_free (p);
559}
560
561DEBUG_FUNCTION void
562debug_isl_union_map (__isl_keep isl_union_map *map)
563{
564  print_isl_union_map (stderr, map);
565}
566
567void
568print_isl_aff (FILE *f, __isl_keep isl_aff *aff)
569{
570  isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
571  p = isl_printer_print_aff (p, aff);
572  p = isl_printer_print_str (p, "\n");
573  isl_printer_free (p);
574}
575
576DEBUG_FUNCTION void
577debug_isl_aff (__isl_keep isl_aff *aff)
578{
579  print_isl_aff (stderr, aff);
580}
581
582void
583print_isl_constraint (FILE *f, __isl_keep isl_constraint *c)
584{
585  isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
586  p = isl_printer_print_constraint (p, c);
587  p = isl_printer_print_str (p, "\n");
588  isl_printer_free (p);
589}
590
591DEBUG_FUNCTION void
592debug_isl_constraint (__isl_keep isl_constraint *c)
593{
594  print_isl_constraint (stderr, c);
595}
596
597void
598print_isl_schedule (FILE *f, __isl_keep isl_schedule *s)
599{
600  isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
601  p = isl_printer_set_yaml_style (p, ISL_YAML_STYLE_BLOCK);
602  p = isl_printer_print_schedule (p, s);
603  p = isl_printer_print_str (p, "\n");
604  isl_printer_free (p);
605}
606
607DEBUG_FUNCTION void
608debug_isl_schedule (__isl_keep isl_schedule *s)
609{
610  print_isl_schedule (stderr, s);
611}
612
613void
614print_isl_ast (FILE *file, __isl_keep isl_ast_node *n)
615{
616  isl_printer *prn = isl_printer_to_file (the_isl_ctx, file);
617  prn = isl_printer_set_output_format (prn, ISL_FORMAT_C);
618  prn = isl_printer_print_ast_node (prn, n);
619  prn = isl_printer_print_str (prn, "\n");
620  isl_printer_free (prn);
621}
622
623DEBUG_FUNCTION void
624debug_isl_ast (isl_ast_node *n)
625{
626  print_isl_ast (stderr, n);
627}
628
629DEBUG_FUNCTION void
630debug_scop_pbb (scop_p scop, int i)
631{
632  debug_pbb (scop->pbbs[i]);
633}
634
635#endif  /* HAVE_isl */
636
637