1/* Gimple Represented as Polyhedra.
2 Copyright (C) 2006-2017 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#define USES_ISL
31
32#include "config.h"
33#include "system.h"
34#include "coretypes.h"
35#include "backend.h"
36#include "diagnostic-core.h"
37#include "cfgloop.h"
38#include "tree-pass.h"
39#include "params.h"
40#include "pretty-print.h"
41
42#ifdef HAVE_isl
43#include "cfghooks.h"
44#include "tree.h"
45#include "gimple.h"
46#include "ssa.h"
47#include "fold-const.h"
48#include "gimple-iterator.h"
49#include "tree-cfg.h"
50#include "tree-ssa-loop.h"
51#include "tree-data-ref.h"
52#include "tree-scalar-evolution.h"
53#include "dbgcnt.h"
54#include "tree-parloops.h"
55#include "tree-cfgcleanup.h"
56#include "tree-vectorizer.h"
57#include "tree-ssa-loop-manip.h"
58#include "tree-ssa.h"
59#include "tree-into-ssa.h"
60#include "graphite.h"
61
62/* Print global statistics to FILE. */
63
64static void
65print_global_statistics (FILE* file)
66{
67 long n_bbs = 0;
68 long n_loops = 0;
69 long n_stmts = 0;
70 long n_conditions = 0;
71 profile_count n_p_bbs = profile_count::zero ();
72 profile_count n_p_loops = profile_count::zero ();
73 profile_count n_p_stmts = profile_count::zero ();
74 profile_count n_p_conditions = profile_count::zero ();
75
76 basic_block bb;
77
78 FOR_ALL_BB_FN (bb, cfun)
79 {
80 gimple_stmt_iterator psi;
81
82 n_bbs++;
83 if (bb->count.initialized_p ())
84 n_p_bbs += bb->count;
85
86 /* Ignore artificial surrounding loop. */
87 if (bb == bb->loop_father->header
88 && bb->index != 0)
89 {
90 n_loops++;
91 n_p_loops += bb->count;
92 }
93
94 if (EDGE_COUNT (bb->succs) > 1)
95 {
96 n_conditions++;
97 if (bb->count.initialized_p ())
98 n_p_conditions += bb->count;
99 }
100
101 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
102 {
103 n_stmts++;
104 if (bb->count.initialized_p ())
105 n_p_stmts += bb->count;
106 }
107 }
108
109 fprintf (file, "\nGlobal statistics (");
110 fprintf (file, "BBS:%ld, ", n_bbs);
111 fprintf (file, "LOOPS:%ld, ", n_loops);
112 fprintf (file, "CONDITIONS:%ld, ", n_conditions);
113 fprintf (file, "STMTS:%ld)\n", n_stmts);
114 fprintf (file, "Global profiling statistics (");
115 fprintf (file, "BBS:");
116 n_p_bbs.dump (file);
117 fprintf (file, ", LOOPS:");
118 n_p_loops.dump (file);
119 fprintf (file, ", CONDITIONS:");
120 n_p_conditions.dump (file);
121 fprintf (file, ", STMTS:");
122 n_p_stmts.dump (file);
123 fprintf (file, ")\n\n");
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 profile_count n_p_bbs = profile_count::zero ();
136 profile_count n_p_loops = profile_count::zero ();
137 profile_count n_p_stmts = profile_count::zero ();
138 profile_count n_p_conditions = profile_count::zero ();
139
140 basic_block bb;
141
142 FOR_ALL_BB_FN (bb, cfun)
143 {
144 gimple_stmt_iterator psi;
145 loop_p loop = bb->loop_father;
146
147 if (!bb_in_sese_p (bb, scop->scop_info->region))
148 continue;
149
150 n_bbs++;
151 if (bb->count.initialized_p ())
152 n_p_bbs += bb->count;
153
154 if (EDGE_COUNT (bb->succs) > 1)
155 {
156 n_conditions++;
157 n_p_conditions += bb->count;
158 }
159
160 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
161 {
162 n_stmts++;
163 n_p_stmts += bb->count;
164 }
165
166 if (loop->header == bb && loop_in_sese_p (loop, scop->scop_info->region))
167 {
168 n_loops++;
169 n_p_loops += bb->count;
170 }
171 }
172
173 fprintf (file, "\nFunction Name: %s\n", current_function_name ());
174
175 edge scop_begin = scop->scop_info->region.entry;
176 edge scop_end = scop->scop_info->region.exit;
177
178 fprintf (file, "\nSCoP (entry_edge (bb_%d, bb_%d), ",
179 scop_begin->src->index, scop_begin->dest->index);
180 fprintf (file, "exit_edge (bb_%d, bb_%d))",
181 scop_end->src->index, scop_end->dest->index);
182
183 fprintf (file, "\nSCoP statistics (");
184 fprintf (file, "BBS:%ld, ", n_bbs);
185 fprintf (file, "LOOPS:%ld, ", n_loops);
186 fprintf (file, "CONDITIONS:%ld, ", n_conditions);
187 fprintf (file, "STMTS:%ld)\n", n_stmts);
188 fprintf (file, "SCoP profiling statistics (");
189 fprintf (file, "BBS:");
190 n_p_bbs.dump (file);
191 fprintf (file, ", LOOPS:");
192 n_p_loops.dump (file);
193 fprintf (file, ", CONDITIONS:");
194 n_p_conditions.dump (file);
195 fprintf (file, ", STMTS:");
196 n_p_stmts.dump (file);
197 fprintf (file, ")\n\n");
198}
199
200/* Print statistics for SCOPS to FILE. */
201
202static void
203print_graphite_statistics (FILE* file, vec<scop_p> scops)
204{
205 int i;
206 scop_p scop;
207
208 FOR_EACH_VEC_ELT (scops, i, scop)
209 print_graphite_scop_statistics (file, scop);
210}
211
212/* Deletes all scops in SCOPS. */
213
214static void
215free_scops (vec<scop_p> scops)
216{
217 int i;
218 scop_p scop;
219
220 FOR_EACH_VEC_ELT (scops, i, scop)
221 free_scop (scop);
222
223 scops.release ();
224}
225
226/* Transforms LOOP to the canonical loop closed SSA form. */
227
228static void
229canonicalize_loop_closed_ssa (loop_p loop)
230{
231 edge e = single_exit (loop);
232 basic_block bb;
233 gphi_iterator psi;
234
235 if (!e || (e->flags & EDGE_COMPLEX))
236 return;
237
238 bb = e->dest;
239
240 /* Make the loop-close PHI node BB contain only PHIs and have a
241 single predecessor. */
242 if (single_pred_p (bb))
243 {
244 e = split_block_after_labels (bb);
245 bb = e->src;
246 }
247 else
248 {
249 basic_block close = split_edge (e);
250 e = single_succ_edge (close);
251 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
252 {
253 gphi *phi = psi.phi ();
254 use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
255 tree arg = USE_FROM_PTR (use_p);
256
257 /* Only add close phi nodes for SSA_NAMEs defined in LOOP. */
258 if (TREE_CODE (arg) != SSA_NAME
259 || SSA_NAME_IS_DEFAULT_DEF (arg)
260 || ! flow_bb_inside_loop_p (loop,
261 gimple_bb (SSA_NAME_DEF_STMT (arg))))
262 continue;
263
264 tree res = copy_ssa_name (arg);
265 gphi *close_phi = create_phi_node (res, close);
266 add_phi_arg (close_phi, arg, gimple_phi_arg_edge (close_phi, 0),
267 UNKNOWN_LOCATION);
268 SET_USE (use_p, res);
269 }
270 bb = close;
271 }
272
273 /* Eliminate duplicates. This relies on processing loops from
274 innermost to outer. */
275 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
276 {
277 gphi_iterator gsi = psi;
278 gphi *phi = psi.phi ();
279
280 /* At this point, PHI should be a close phi in normal form. */
281 gcc_assert (gimple_phi_num_args (phi) == 1);
282
283 /* Iterate over the next phis and remove duplicates. */
284 gsi_next (&gsi);
285 while (!gsi_end_p (gsi))
286 if (gimple_phi_arg_def (phi, 0) == gimple_phi_arg_def (gsi.phi (), 0))
287 {
288 replace_uses_by (gimple_phi_result (gsi.phi ()),
289 gimple_phi_result (phi));
290 remove_phi_node (&gsi, true);
291 }
292 else
293 gsi_next (&gsi);
294 }
295}
296
297/* Converts the current loop closed SSA form to a canonical form
298 expected by the Graphite code generation.
299
300 The loop closed SSA form has the following invariant: a variable
301 defined in a loop that is used outside the loop appears only in the
302 phi nodes in the destination of the loop exit. These phi nodes are
303 called close phi nodes.
304
305 The canonical loop closed SSA form contains the extra invariants:
306
307 - when the loop contains only one exit, the close phi nodes contain
308 only one argument. That implies that the basic block that contains
309 the close phi nodes has only one predecessor, that is a basic block
310 in the loop.
311
312 - the basic block containing the close phi nodes does not contain
313 other statements.
314
315 - there exist only one phi node per definition in the loop.
316*/
317
318static void
319canonicalize_loop_closed_ssa_form (void)
320{
321 loop_p loop;
322 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
323 canonicalize_loop_closed_ssa (loop);
324
325 checking_verify_loop_closed_ssa (true);
326}
327
328isl_ctx *the_isl_ctx;
329
330/* Perform a set of linear transforms on the loops of the current
331 function. */
332
333void
334graphite_transform_loops (void)
335{
336 int i;
337 scop_p scop;
338 bool changed = false;
339 vec<scop_p> scops = vNULL;
340 isl_ctx *ctx;
341
342 /* If a function is parallel it was most probably already run through graphite
343 once. No need to run again. */
344 if (parallelized_function_p (cfun->decl))
345 return;
346
347 calculate_dominance_info (CDI_DOMINATORS);
348
349 ctx = isl_ctx_alloc ();
350 isl_options_set_on_error (ctx, ISL_ON_ERROR_ABORT);
351 the_isl_ctx = ctx;
352
353 sort_sibling_loops (cfun);
354 canonicalize_loop_closed_ssa_form ();
355
356 /* Print the loop structure. */
357 if (dump_file && (dump_flags & TDF_DETAILS))
358 {
359 print_loops (dump_file, 2);
360 print_loops (dump_file, 3);
361 }
362
363 calculate_dominance_info (CDI_POST_DOMINATORS);
364 build_scops (&scops);
365 free_dominance_info (CDI_POST_DOMINATORS);
366
367 if (dump_file && (dump_flags & TDF_DETAILS))
368 {
369 print_graphite_statistics (dump_file, scops);
370 print_global_statistics (dump_file);
371 }
372
373 FOR_EACH_VEC_ELT (scops, i, scop)
374 if (dbg_cnt (graphite_scop))
375 {
376 scop->isl_context = ctx;
377 if (!build_poly_scop (scop))
378 continue;
379
380 if (!apply_poly_transforms (scop))
381 continue;
382
383 changed = true;
384 if (graphite_regenerate_ast_isl (scop))
385 {
386 location_t loc = find_loop_location
387 (scops[i]->scop_info->region.entry->dest->loop_father);
388 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc,
389 "loop nest optimized\n");
390 }
391 }
392
393 if (changed)
394 {
395 mark_virtual_operands_for_renaming (cfun);
396 update_ssa (TODO_update_ssa);
397 checking_verify_ssa (true, true);
398 rewrite_into_loop_closed_ssa (NULL, 0);
399 scev_reset ();
400 checking_verify_loop_structure ();
401 }
402
403 if (dump_file && (dump_flags & TDF_DETAILS))
404 {
405 loop_p loop;
406 int num_no_dependency = 0;
407
408 FOR_EACH_LOOP (loop, 0)
409 if (loop->can_be_parallel)
410 num_no_dependency++;
411
412 fprintf (dump_file, "%d loops carried no dependency.\n",
413 num_no_dependency);
414 }
415
416 free_scops (scops);
417 the_isl_ctx = NULL;
418 isl_ctx_free (ctx);
419
420 if (changed)
421 {
422 cleanup_tree_cfg ();
423 profile_status_for_fn (cfun) = PROFILE_ABSENT;
424 release_recorded_exits (cfun);
425 tree_estimate_probability (false);
426 }
427
428}
429
430#else /* If isl is not available: #ifndef HAVE_isl. */
431
432static void
433graphite_transform_loops (void)
434{
435 sorry ("Graphite loop optimizations cannot be used (isl is not available).");
436}
437
438#endif
439
440
441static unsigned int
442graphite_transforms (struct function *fun)
443{
444 if (number_of_loops (fun) <= 1)
445 return 0;
446
447 graphite_transform_loops ();
448
449 return 0;
450}
451
452static bool
453gate_graphite_transforms (void)
454{
455 /* Enable -fgraphite pass if any one of the graphite optimization flags
456 is turned on. */
457 if (flag_graphite_identity
458 || flag_loop_parallelize_all
459 || flag_loop_nest_optimize)
460 flag_graphite = 1;
461
462 return flag_graphite != 0;
463}
464
465namespace {
466
467const pass_data pass_data_graphite =
468{
469 GIMPLE_PASS, /* type */
470 "graphite0", /* name */
471 OPTGROUP_LOOP, /* optinfo_flags */
472 TV_GRAPHITE, /* tv_id */
473 ( PROP_cfg | PROP_ssa ), /* properties_required */
474 0, /* properties_provided */
475 0, /* properties_destroyed */
476 0, /* todo_flags_start */
477 0, /* todo_flags_finish */
478};
479
480class pass_graphite : public gimple_opt_pass
481{
482public:
483 pass_graphite (gcc::context *ctxt)
484 : gimple_opt_pass (pass_data_graphite, ctxt)
485 {}
486
487 /* opt_pass methods: */
488 virtual bool gate (function *) { return gate_graphite_transforms (); }
489
490}; // class pass_graphite
491
492} // anon namespace
493
494gimple_opt_pass *
495make_pass_graphite (gcc::context *ctxt)
496{
497 return new pass_graphite (ctxt);
498}
499
500namespace {
501
502const pass_data pass_data_graphite_transforms =
503{
504 GIMPLE_PASS, /* type */
505 "graphite", /* name */
506 OPTGROUP_LOOP, /* optinfo_flags */
507 TV_GRAPHITE_TRANSFORMS, /* tv_id */
508 ( PROP_cfg | PROP_ssa ), /* properties_required */
509 0, /* properties_provided */
510 0, /* properties_destroyed */
511 0, /* todo_flags_start */
512 0, /* todo_flags_finish */
513};
514
515class pass_graphite_transforms : public gimple_opt_pass
516{
517public:
518 pass_graphite_transforms (gcc::context *ctxt)
519 : gimple_opt_pass (pass_data_graphite_transforms, ctxt)
520 {}
521
522 /* opt_pass methods: */
523 virtual bool gate (function *) { return gate_graphite_transforms (); }
524 virtual unsigned int execute (function *fun) { return graphite_transforms (fun); }
525
526}; // class pass_graphite_transforms
527
528} // anon namespace
529
530gimple_opt_pass *
531make_pass_graphite_transforms (gcc::context *ctxt)
532{
533 return new pass_graphite_transforms (ctxt);
534}
535
536
537