PR target/47230
[official-gcc.git] / gcc / graphite-scop-detection.c
blob5d1c96e353da6a433b9a936b006a090eaee5456f
1 /* Detection of Static Control Parts (SCoP) for Graphite.
2 Copyright (C) 2009-2014 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@amd.com> and
4 Tobias Grosser <grosser@fim.uni-passau.de>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
11 any later version.
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 #include "config.h"
24 #ifdef HAVE_cloog
25 #include <isl/set.h>
26 #include <isl/map.h>
27 #include <isl/union_map.h>
28 #include <cloog/cloog.h>
29 #include <cloog/isl/domain.h>
30 #endif
32 #include "system.h"
33 #include "coretypes.h"
34 #include "tree.h"
35 #include "basic-block.h"
36 #include "tree-ssa-alias.h"
37 #include "internal-fn.h"
38 #include "gimple-expr.h"
39 #include "is-a.h"
40 #include "gimple.h"
41 #include "gimple-iterator.h"
42 #include "gimple-ssa.h"
43 #include "tree-phinodes.h"
44 #include "ssa-iterators.h"
45 #include "tree-ssa-loop-manip.h"
46 #include "tree-ssa-loop-niter.h"
47 #include "tree-ssa-loop.h"
48 #include "tree-into-ssa.h"
49 #include "tree-ssa.h"
50 #include "cfgloop.h"
51 #include "tree-chrec.h"
52 #include "tree-data-ref.h"
53 #include "tree-scalar-evolution.h"
54 #include "tree-pass.h"
55 #include "sese.h"
56 #include "tree-ssa-propagate.h"
58 #ifdef HAVE_cloog
59 #include "graphite-poly.h"
60 #include "graphite-scop-detection.h"
62 /* Forward declarations. */
63 static void make_close_phi_nodes_unique (basic_block);
65 /* The type of the analyzed basic block. */
67 typedef enum gbb_type {
68 GBB_UNKNOWN,
69 GBB_LOOP_SING_EXIT_HEADER,
70 GBB_LOOP_MULT_EXIT_HEADER,
71 GBB_LOOP_EXIT,
72 GBB_COND_HEADER,
73 GBB_SIMPLE,
74 GBB_LAST
75 } gbb_type;
77 /* Detect the type of BB. Loop headers are only marked, if they are
78 new. This means their loop_father is different to LAST_LOOP.
79 Otherwise they are treated like any other bb and their type can be
80 any other type. */
82 static gbb_type
83 get_bb_type (basic_block bb, struct loop *last_loop)
85 vec<basic_block> dom;
86 int nb_dom;
87 struct loop *loop = bb->loop_father;
89 /* Check, if we entry into a new loop. */
90 if (loop != last_loop)
92 if (single_exit (loop) != NULL)
93 return GBB_LOOP_SING_EXIT_HEADER;
94 else if (loop->num != 0)
95 return GBB_LOOP_MULT_EXIT_HEADER;
96 else
97 return GBB_COND_HEADER;
100 dom = get_dominated_by (CDI_DOMINATORS, bb);
101 nb_dom = dom.length ();
102 dom.release ();
104 if (nb_dom == 0)
105 return GBB_LAST;
107 if (nb_dom == 1 && single_succ_p (bb))
108 return GBB_SIMPLE;
110 return GBB_COND_HEADER;
113 /* A SCoP detection region, defined using bbs as borders.
115 All control flow touching this region, comes in passing basic_block
116 ENTRY and leaves passing basic_block EXIT. By using bbs instead of
117 edges for the borders we are able to represent also regions that do
118 not have a single entry or exit edge.
120 But as they have a single entry basic_block and a single exit
121 basic_block, we are able to generate for every sd_region a single
122 entry and exit edge.
126 3 <- entry
129 / \ This region contains: {3, 4, 5, 6, 7, 8}
134 9 <- exit */
137 typedef struct sd_region_p
139 /* The entry bb dominates all bbs in the sd_region. It is part of
140 the region. */
141 basic_block entry;
143 /* The exit bb postdominates all bbs in the sd_region, but is not
144 part of the region. */
145 basic_block exit;
146 } sd_region;
150 /* Moves the scops from SOURCE to TARGET and clean up SOURCE. */
152 static void
153 move_sd_regions (vec<sd_region> *source, vec<sd_region> *target)
155 sd_region *s;
156 int i;
158 FOR_EACH_VEC_ELT (*source, i, s)
159 target->safe_push (*s);
161 source->release ();
164 /* Something like "n * m" is not allowed. */
166 static bool
167 graphite_can_represent_init (tree e)
169 switch (TREE_CODE (e))
171 case POLYNOMIAL_CHREC:
172 return graphite_can_represent_init (CHREC_LEFT (e))
173 && graphite_can_represent_init (CHREC_RIGHT (e));
175 case MULT_EXPR:
176 if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
177 return graphite_can_represent_init (TREE_OPERAND (e, 0))
178 && tree_fits_shwi_p (TREE_OPERAND (e, 1));
179 else
180 return graphite_can_represent_init (TREE_OPERAND (e, 1))
181 && tree_fits_shwi_p (TREE_OPERAND (e, 0));
183 case PLUS_EXPR:
184 case POINTER_PLUS_EXPR:
185 case MINUS_EXPR:
186 return graphite_can_represent_init (TREE_OPERAND (e, 0))
187 && graphite_can_represent_init (TREE_OPERAND (e, 1));
189 case NEGATE_EXPR:
190 case BIT_NOT_EXPR:
191 CASE_CONVERT:
192 case NON_LVALUE_EXPR:
193 return graphite_can_represent_init (TREE_OPERAND (e, 0));
195 default:
196 break;
199 return true;
202 /* Return true when SCEV can be represented in the polyhedral model.
204 An expression can be represented, if it can be expressed as an
205 affine expression. For loops (i, j) and parameters (m, n) all
206 affine expressions are of the form:
208 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
210 1 i + 20 j + (-2) m + 25
212 Something like "i * n" or "n * m" is not allowed. */
214 static bool
215 graphite_can_represent_scev (tree scev)
217 if (chrec_contains_undetermined (scev))
218 return false;
220 switch (TREE_CODE (scev))
222 case NEGATE_EXPR:
223 case BIT_NOT_EXPR:
224 CASE_CONVERT:
225 case NON_LVALUE_EXPR:
226 return graphite_can_represent_scev (TREE_OPERAND (scev, 0));
228 case PLUS_EXPR:
229 case POINTER_PLUS_EXPR:
230 case MINUS_EXPR:
231 return graphite_can_represent_scev (TREE_OPERAND (scev, 0))
232 && graphite_can_represent_scev (TREE_OPERAND (scev, 1));
234 case MULT_EXPR:
235 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 0)))
236 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 1)))
237 && !(chrec_contains_symbols (TREE_OPERAND (scev, 0))
238 && chrec_contains_symbols (TREE_OPERAND (scev, 1)))
239 && graphite_can_represent_init (scev)
240 && graphite_can_represent_scev (TREE_OPERAND (scev, 0))
241 && graphite_can_represent_scev (TREE_OPERAND (scev, 1));
243 case POLYNOMIAL_CHREC:
244 /* Check for constant strides. With a non constant stride of
245 'n' we would have a value of 'iv * n'. Also check that the
246 initial value can represented: for example 'n * m' cannot be
247 represented. */
248 if (!evolution_function_right_is_integer_cst (scev)
249 || !graphite_can_represent_init (scev))
250 return false;
251 return graphite_can_represent_scev (CHREC_LEFT (scev));
253 default:
254 break;
257 /* Only affine functions can be represented. */
258 if (tree_contains_chrecs (scev, NULL)
259 || !scev_is_linear_expression (scev))
260 return false;
262 return true;
266 /* Return true when EXPR can be represented in the polyhedral model.
268 This means an expression can be represented, if it is linear with
269 respect to the loops and the strides are non parametric.
270 LOOP is the place where the expr will be evaluated. SCOP_ENTRY defines the
271 entry of the region we analyse. */
273 static bool
274 graphite_can_represent_expr (basic_block scop_entry, loop_p loop,
275 tree expr)
277 tree scev = analyze_scalar_evolution (loop, expr);
279 scev = instantiate_scev (scop_entry, loop, scev);
281 return graphite_can_represent_scev (scev);
284 /* Return true if the data references of STMT can be represented by
285 Graphite. */
287 static bool
288 stmt_has_simple_data_refs_p (loop_p outermost_loop ATTRIBUTE_UNUSED,
289 gimple stmt)
291 data_reference_p dr;
292 unsigned i;
293 int j;
294 bool res = true;
295 vec<data_reference_p> drs = vNULL;
296 loop_p outer;
298 for (outer = loop_containing_stmt (stmt); outer; outer = loop_outer (outer))
300 graphite_find_data_references_in_stmt (outer,
301 loop_containing_stmt (stmt),
302 stmt, &drs);
304 FOR_EACH_VEC_ELT (drs, j, dr)
305 for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
306 if (!graphite_can_represent_scev (DR_ACCESS_FN (dr, i)))
308 res = false;
309 goto done;
312 free_data_refs (drs);
313 drs.create (0);
316 done:
317 free_data_refs (drs);
318 return res;
321 /* Return true only when STMT is simple enough for being handled by
322 Graphite. This depends on SCOP_ENTRY, as the parameters are
323 initialized relatively to this basic block, the linear functions
324 are initialized to OUTERMOST_LOOP and BB is the place where we try
325 to evaluate the STMT. */
327 static bool
328 stmt_simple_for_scop_p (basic_block scop_entry, loop_p outermost_loop,
329 gimple stmt, basic_block bb)
331 loop_p loop = bb->loop_father;
333 gcc_assert (scop_entry);
335 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
336 Calls have side-effects, except those to const or pure
337 functions. */
338 if (gimple_has_volatile_ops (stmt)
339 || (gimple_code (stmt) == GIMPLE_CALL
340 && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
341 || (gimple_code (stmt) == GIMPLE_ASM))
342 return false;
344 if (is_gimple_debug (stmt))
345 return true;
347 if (!stmt_has_simple_data_refs_p (outermost_loop, stmt))
348 return false;
350 switch (gimple_code (stmt))
352 case GIMPLE_RETURN:
353 case GIMPLE_LABEL:
354 return true;
356 case GIMPLE_COND:
358 /* We can handle all binary comparisons. Inequalities are
359 also supported as they can be represented with union of
360 polyhedra. */
361 enum tree_code code = gimple_cond_code (stmt);
362 if (!(code == LT_EXPR
363 || code == GT_EXPR
364 || code == LE_EXPR
365 || code == GE_EXPR
366 || code == EQ_EXPR
367 || code == NE_EXPR))
368 return false;
370 for (unsigned i = 0; i < 2; ++i)
372 tree op = gimple_op (stmt, i);
373 if (!graphite_can_represent_expr (scop_entry, loop, op)
374 /* We can not handle REAL_TYPE. Failed for pr39260. */
375 || TREE_CODE (TREE_TYPE (op)) == REAL_TYPE)
376 return false;
379 return true;
382 case GIMPLE_ASSIGN:
383 case GIMPLE_CALL:
384 return true;
386 default:
387 /* These nodes cut a new scope. */
388 return false;
391 return false;
394 /* Returns the statement of BB that contains a harmful operation: that
395 can be a function call with side effects, the induction variables
396 are not linear with respect to SCOP_ENTRY, etc. The current open
397 scop should end before this statement. The evaluation is limited using
398 OUTERMOST_LOOP as outermost loop that may change. */
400 static gimple
401 harmful_stmt_in_bb (basic_block scop_entry, loop_p outer_loop, basic_block bb)
403 gimple_stmt_iterator gsi;
405 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
406 if (!stmt_simple_for_scop_p (scop_entry, outer_loop, gsi_stmt (gsi), bb))
407 return gsi_stmt (gsi);
409 return NULL;
412 /* Return true if LOOP can be represented in the polyhedral
413 representation. This is evaluated taking SCOP_ENTRY and
414 OUTERMOST_LOOP in mind. */
416 static bool
417 graphite_can_represent_loop (basic_block scop_entry, loop_p loop)
419 tree niter;
420 struct tree_niter_desc niter_desc;
422 /* FIXME: For the moment, graphite cannot be used on loops that
423 iterate using induction variables that wrap. */
425 return number_of_iterations_exit (loop, single_exit (loop), &niter_desc, false)
426 && niter_desc.control.no_overflow
427 && (niter = number_of_latch_executions (loop))
428 && !chrec_contains_undetermined (niter)
429 && graphite_can_represent_expr (scop_entry, loop, niter);
432 /* Store information needed by scopdet_* functions. */
434 struct scopdet_info
436 /* Exit of the open scop would stop if the current BB is harmful. */
437 basic_block exit;
439 /* Where the next scop would start if the current BB is harmful. */
440 basic_block next;
442 /* The bb or one of its children contains open loop exits. That means
443 loop exit nodes that are not surrounded by a loop dominated by bb. */
444 bool exits;
446 /* The bb or one of its children contains only structures we can handle. */
447 bool difficult;
450 static struct scopdet_info build_scops_1 (basic_block, loop_p,
451 vec<sd_region> *, loop_p);
453 /* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB
454 to SCOPS. TYPE is the gbb_type of BB. */
456 static struct scopdet_info
457 scopdet_basic_block_info (basic_block bb, loop_p outermost_loop,
458 vec<sd_region> *scops, gbb_type type)
460 loop_p loop = bb->loop_father;
461 struct scopdet_info result;
462 gimple stmt;
464 /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps. */
465 basic_block entry_block = ENTRY_BLOCK_PTR_FOR_FN (cfun);
466 stmt = harmful_stmt_in_bb (entry_block, outermost_loop, bb);
467 result.difficult = (stmt != NULL);
468 result.exit = NULL;
470 switch (type)
472 case GBB_LAST:
473 result.next = NULL;
474 result.exits = false;
476 /* Mark bbs terminating a SESE region difficult, if they start
477 a condition or if the block it exits to cannot be split
478 with make_forwarder_block. */
479 if (!single_succ_p (bb)
480 || bb_has_abnormal_pred (single_succ (bb)))
481 result.difficult = true;
482 else
483 result.exit = single_succ (bb);
485 break;
487 case GBB_SIMPLE:
488 result.next = single_succ (bb);
489 result.exits = false;
490 result.exit = single_succ (bb);
491 break;
493 case GBB_LOOP_SING_EXIT_HEADER:
495 auto_vec<sd_region, 3> regions;
496 struct scopdet_info sinfo;
497 edge exit_e = single_exit (loop);
499 sinfo = build_scops_1 (bb, outermost_loop, &regions, loop);
501 if (!graphite_can_represent_loop (entry_block, loop))
502 result.difficult = true;
504 result.difficult |= sinfo.difficult;
506 /* Try again with another loop level. */
507 if (result.difficult
508 && loop_depth (outermost_loop) + 1 == loop_depth (loop))
510 outermost_loop = loop;
512 regions.release ();
513 regions.create (3);
515 sinfo = scopdet_basic_block_info (bb, outermost_loop, scops, type);
517 result = sinfo;
518 result.difficult = true;
520 if (sinfo.difficult)
521 move_sd_regions (&regions, scops);
522 else
524 sd_region open_scop;
525 open_scop.entry = bb;
526 open_scop.exit = exit_e->dest;
527 scops->safe_push (open_scop);
528 regions.release ();
531 else
533 result.exit = exit_e->dest;
534 result.next = exit_e->dest;
536 /* If we do not dominate result.next, remove it. It's either
537 the exit block, or another bb dominates it and will
538 call the scop detection for this bb. */
539 if (!dominated_by_p (CDI_DOMINATORS, result.next, bb))
540 result.next = NULL;
542 if (exit_e->src->loop_father != loop)
543 result.next = NULL;
545 result.exits = false;
547 if (result.difficult)
548 move_sd_regions (&regions, scops);
549 else
550 regions.release ();
553 break;
556 case GBB_LOOP_MULT_EXIT_HEADER:
558 /* XXX: For now we just do not join loops with multiple exits. If the
559 exits lead to the same bb it may be possible to join the loop. */
560 auto_vec<sd_region, 3> regions;
561 vec<edge> exits = get_loop_exit_edges (loop);
562 edge e;
563 int i;
564 build_scops_1 (bb, loop, &regions, loop);
566 /* Scan the code dominated by this loop. This means all bbs, that are
567 are dominated by a bb in this loop, but are not part of this loop.
569 The easiest case:
570 - The loop exit destination is dominated by the exit sources.
572 TODO: We miss here the more complex cases:
573 - The exit destinations are dominated by another bb inside
574 the loop.
575 - The loop dominates bbs, that are not exit destinations. */
576 FOR_EACH_VEC_ELT (exits, i, e)
577 if (e->src->loop_father == loop
578 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src))
580 if (loop_outer (outermost_loop))
581 outermost_loop = loop_outer (outermost_loop);
583 /* Pass loop_outer to recognize e->dest as loop header in
584 build_scops_1. */
585 if (e->dest->loop_father->header == e->dest)
586 build_scops_1 (e->dest, outermost_loop, &regions,
587 loop_outer (e->dest->loop_father));
588 else
589 build_scops_1 (e->dest, outermost_loop, &regions,
590 e->dest->loop_father);
593 result.next = NULL;
594 result.exit = NULL;
595 result.difficult = true;
596 result.exits = false;
597 move_sd_regions (&regions, scops);
598 exits.release ();
599 break;
601 case GBB_COND_HEADER:
603 auto_vec<sd_region, 3> regions;
604 struct scopdet_info sinfo;
605 vec<basic_block> dominated;
606 int i;
607 basic_block dom_bb;
608 basic_block last_exit = NULL;
609 edge e;
610 result.exits = false;
612 /* First check the successors of BB, and check if it is
613 possible to join the different branches. */
614 FOR_EACH_VEC_SAFE_ELT (bb->succs, i, e)
616 /* Ignore loop exits. They will be handled after the loop
617 body. */
618 if (loop_exits_to_bb_p (loop, e->dest))
620 result.exits = true;
621 continue;
624 /* Do not follow edges that lead to the end of the
625 conditions block. For example, in
628 | /|\
629 | 1 2 |
630 | | | |
631 | 3 4 |
632 | \|/
635 the edge from 0 => 6. Only check if all paths lead to
636 the same node 6. */
638 if (!single_pred_p (e->dest))
640 /* Check, if edge leads directly to the end of this
641 condition. */
642 if (!last_exit)
643 last_exit = e->dest;
645 if (e->dest != last_exit)
646 result.difficult = true;
648 continue;
651 if (!dominated_by_p (CDI_DOMINATORS, e->dest, bb))
653 result.difficult = true;
654 continue;
657 sinfo = build_scops_1 (e->dest, outermost_loop, &regions, loop);
659 result.exits |= sinfo.exits;
660 result.difficult |= sinfo.difficult;
662 /* Checks, if all branches end at the same point.
663 If that is true, the condition stays joinable.
664 Have a look at the example above. */
665 if (sinfo.exit)
667 if (!last_exit)
668 last_exit = sinfo.exit;
670 if (sinfo.exit != last_exit)
671 result.difficult = true;
673 else
674 result.difficult = true;
677 if (!last_exit)
678 result.difficult = true;
680 /* Join the branches of the condition if possible. */
681 if (!result.exits && !result.difficult)
683 /* Only return a next pointer if we dominate this pointer.
684 Otherwise it will be handled by the bb dominating it. */
685 if (dominated_by_p (CDI_DOMINATORS, last_exit, bb)
686 && last_exit != bb)
687 result.next = last_exit;
688 else
689 result.next = NULL;
691 result.exit = last_exit;
693 regions.release ();
694 break;
697 /* Scan remaining bbs dominated by BB. */
698 dominated = get_dominated_by (CDI_DOMINATORS, bb);
700 FOR_EACH_VEC_ELT (dominated, i, dom_bb)
702 /* Ignore loop exits: they will be handled after the loop body. */
703 if (loop_depth (find_common_loop (loop, dom_bb->loop_father))
704 < loop_depth (loop))
706 result.exits = true;
707 continue;
710 /* Ignore the bbs processed above. */
711 if (single_pred_p (dom_bb) && single_pred (dom_bb) == bb)
712 continue;
714 if (loop_depth (loop) > loop_depth (dom_bb->loop_father))
715 sinfo = build_scops_1 (dom_bb, outermost_loop, &regions,
716 loop_outer (loop));
717 else
718 sinfo = build_scops_1 (dom_bb, outermost_loop, &regions, loop);
720 result.exits |= sinfo.exits;
721 result.difficult = true;
722 result.exit = NULL;
725 dominated.release ();
727 result.next = NULL;
728 move_sd_regions (&regions, scops);
730 break;
733 default:
734 gcc_unreachable ();
737 return result;
740 /* Starting from CURRENT we walk the dominance tree and add new sd_regions to
741 SCOPS. The analyse if a sd_region can be handled is based on the value
742 of OUTERMOST_LOOP. Only loops inside OUTERMOST loops may change. LOOP
743 is the loop in which CURRENT is handled.
745 TODO: These functions got a little bit big. They definitely should be cleaned
746 up. */
748 static struct scopdet_info
749 build_scops_1 (basic_block current, loop_p outermost_loop,
750 vec<sd_region> *scops, loop_p loop)
752 bool in_scop = false;
753 sd_region open_scop;
754 struct scopdet_info sinfo;
756 /* Initialize result. */
757 struct scopdet_info result;
758 result.exits = false;
759 result.difficult = false;
760 result.next = NULL;
761 result.exit = NULL;
762 open_scop.entry = NULL;
763 open_scop.exit = NULL;
764 sinfo.exit = NULL;
766 /* Loop over the dominance tree. If we meet a difficult bb, close
767 the current SCoP. Loop and condition header start a new layer,
768 and can only be added if all bbs in deeper layers are simple. */
769 while (current != NULL)
771 sinfo = scopdet_basic_block_info (current, outermost_loop, scops,
772 get_bb_type (current, loop));
774 if (!in_scop && !(sinfo.exits || sinfo.difficult))
776 open_scop.entry = current;
777 open_scop.exit = NULL;
778 in_scop = true;
780 else if (in_scop && (sinfo.exits || sinfo.difficult))
782 open_scop.exit = current;
783 scops->safe_push (open_scop);
784 in_scop = false;
787 result.difficult |= sinfo.difficult;
788 result.exits |= sinfo.exits;
790 current = sinfo.next;
793 /* Try to close open_scop, if we are still in an open SCoP. */
794 if (in_scop)
796 open_scop.exit = sinfo.exit;
797 gcc_assert (open_scop.exit);
798 scops->safe_push (open_scop);
801 result.exit = sinfo.exit;
802 return result;
805 /* Checks if a bb is contained in REGION. */
807 static bool
808 bb_in_sd_region (basic_block bb, sd_region *region)
810 return bb_in_region (bb, region->entry, region->exit);
813 /* Returns the single entry edge of REGION, if it does not exits NULL. */
815 static edge
816 find_single_entry_edge (sd_region *region)
818 edge e;
819 edge_iterator ei;
820 edge entry = NULL;
822 FOR_EACH_EDGE (e, ei, region->entry->preds)
823 if (!bb_in_sd_region (e->src, region))
825 if (entry)
827 entry = NULL;
828 break;
831 else
832 entry = e;
835 return entry;
838 /* Returns the single exit edge of REGION, if it does not exits NULL. */
840 static edge
841 find_single_exit_edge (sd_region *region)
843 edge e;
844 edge_iterator ei;
845 edge exit = NULL;
847 FOR_EACH_EDGE (e, ei, region->exit->preds)
848 if (bb_in_sd_region (e->src, region))
850 if (exit)
852 exit = NULL;
853 break;
856 else
857 exit = e;
860 return exit;
863 /* Create a single entry edge for REGION. */
865 static void
866 create_single_entry_edge (sd_region *region)
868 if (find_single_entry_edge (region))
869 return;
871 /* There are multiple predecessors for bb_3
873 | 1 2
874 | | /
875 | |/
876 | 3 <- entry
877 | |\
878 | | |
879 | 4 ^
880 | | |
881 | |/
884 There are two edges (1->3, 2->3), that point from outside into the region,
885 and another one (5->3), a loop latch, lead to bb_3.
887 We split bb_3.
889 | 1 2
890 | | /
891 | |/
892 |3.0
893 | |\ (3.0 -> 3.1) = single entry edge
894 |3.1 | <- entry
895 | | |
896 | | |
897 | 4 ^
898 | | |
899 | |/
902 If the loop is part of the SCoP, we have to redirect the loop latches.
904 | 1 2
905 | | /
906 | |/
907 |3.0
908 | | (3.0 -> 3.1) = entry edge
909 |3.1 <- entry
910 | |\
911 | | |
912 | 4 ^
913 | | |
914 | |/
915 | 5 */
917 if (region->entry->loop_father->header != region->entry
918 || dominated_by_p (CDI_DOMINATORS,
919 loop_latch_edge (region->entry->loop_father)->src,
920 region->exit))
922 edge forwarder = split_block_after_labels (region->entry);
923 region->entry = forwarder->dest;
925 else
926 /* This case is never executed, as the loop headers seem always to have a
927 single edge pointing from outside into the loop. */
928 gcc_unreachable ();
930 gcc_checking_assert (find_single_entry_edge (region));
933 /* Check if the sd_region, mentioned in EDGE, has no exit bb. */
935 static bool
936 sd_region_without_exit (edge e)
938 sd_region *r = (sd_region *) e->aux;
940 if (r)
941 return r->exit == NULL;
942 else
943 return false;
946 /* Create a single exit edge for REGION. */
948 static void
949 create_single_exit_edge (sd_region *region)
951 edge e;
952 edge_iterator ei;
953 edge forwarder = NULL;
954 basic_block exit;
956 /* We create a forwarder bb (5) for all edges leaving this region
957 (3->5, 4->5). All other edges leading to the same bb, are moved
958 to a new bb (6). If these edges where part of another region (2->5)
959 we update the region->exit pointer, of this region.
961 To identify which edge belongs to which region we depend on the e->aux
962 pointer in every edge. It points to the region of the edge or to NULL,
963 if the edge is not part of any region.
965 1 2 3 4 1->5 no region, 2->5 region->exit = 5,
966 \| |/ 3->5 region->exit = NULL, 4->5 region->exit = NULL
967 5 <- exit
969 changes to
971 1 2 3 4 1->6 no region, 2->6 region->exit = 6,
972 | | \/ 3->5 no region, 4->5 no region,
973 | | 5
974 \| / 5->6 region->exit = 6
977 Now there is only a single exit edge (5->6). */
978 exit = region->exit;
979 region->exit = NULL;
980 forwarder = make_forwarder_block (exit, &sd_region_without_exit, NULL);
982 /* Unmark the edges, that are no longer exit edges. */
983 FOR_EACH_EDGE (e, ei, forwarder->src->preds)
984 if (e->aux)
985 e->aux = NULL;
987 /* Mark the new exit edge. */
988 single_succ_edge (forwarder->src)->aux = region;
990 /* Update the exit bb of all regions, where exit edges lead to
991 forwarder->dest. */
992 FOR_EACH_EDGE (e, ei, forwarder->dest->preds)
993 if (e->aux)
994 ((sd_region *) e->aux)->exit = forwarder->dest;
996 gcc_checking_assert (find_single_exit_edge (region));
999 /* Unmark the exit edges of all REGIONS.
1000 See comment in "create_single_exit_edge". */
1002 static void
1003 unmark_exit_edges (vec<sd_region> regions)
1005 int i;
1006 sd_region *s;
1007 edge e;
1008 edge_iterator ei;
1010 FOR_EACH_VEC_ELT (regions, i, s)
1011 FOR_EACH_EDGE (e, ei, s->exit->preds)
1012 e->aux = NULL;
1016 /* Mark the exit edges of all REGIONS.
1017 See comment in "create_single_exit_edge". */
1019 static void
1020 mark_exit_edges (vec<sd_region> regions)
1022 int i;
1023 sd_region *s;
1024 edge e;
1025 edge_iterator ei;
1027 FOR_EACH_VEC_ELT (regions, i, s)
1028 FOR_EACH_EDGE (e, ei, s->exit->preds)
1029 if (bb_in_sd_region (e->src, s))
1030 e->aux = s;
1033 /* Create for all scop regions a single entry and a single exit edge. */
1035 static void
1036 create_sese_edges (vec<sd_region> regions)
1038 int i;
1039 sd_region *s;
1041 FOR_EACH_VEC_ELT (regions, i, s)
1042 create_single_entry_edge (s);
1044 mark_exit_edges (regions);
1046 FOR_EACH_VEC_ELT (regions, i, s)
1047 /* Don't handle multiple edges exiting the function. */
1048 if (!find_single_exit_edge (s)
1049 && s->exit != EXIT_BLOCK_PTR_FOR_FN (cfun))
1050 create_single_exit_edge (s);
1052 unmark_exit_edges (regions);
1054 calculate_dominance_info (CDI_DOMINATORS);
1055 fix_loop_structure (NULL);
1057 #ifdef ENABLE_CHECKING
1058 verify_loop_structure ();
1059 verify_ssa (false, true);
1060 #endif
1063 /* Create graphite SCoPs from an array of scop detection REGIONS. */
1065 static void
1066 build_graphite_scops (vec<sd_region> regions,
1067 vec<scop_p> *scops)
1069 int i;
1070 sd_region *s;
1072 FOR_EACH_VEC_ELT (regions, i, s)
1074 edge entry = find_single_entry_edge (s);
1075 edge exit = find_single_exit_edge (s);
1076 scop_p scop;
1078 if (!exit)
1079 continue;
1081 scop = new_scop (new_sese (entry, exit));
1082 scops->safe_push (scop);
1084 /* Are there overlapping SCoPs? */
1085 #ifdef ENABLE_CHECKING
1087 int j;
1088 sd_region *s2;
1090 FOR_EACH_VEC_ELT (regions, j, s2)
1091 if (s != s2)
1092 gcc_assert (!bb_in_sd_region (s->entry, s2));
1094 #endif
1098 /* Returns true when BB contains only close phi nodes. */
1100 static bool
1101 contains_only_close_phi_nodes (basic_block bb)
1103 gimple_stmt_iterator gsi;
1105 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1106 if (gimple_code (gsi_stmt (gsi)) != GIMPLE_LABEL)
1107 return false;
1109 return true;
1112 /* Print statistics for SCOP to FILE. */
1114 static void
1115 print_graphite_scop_statistics (FILE* file, scop_p scop)
1117 long n_bbs = 0;
1118 long n_loops = 0;
1119 long n_stmts = 0;
1120 long n_conditions = 0;
1121 long n_p_bbs = 0;
1122 long n_p_loops = 0;
1123 long n_p_stmts = 0;
1124 long n_p_conditions = 0;
1126 basic_block bb;
1128 FOR_ALL_BB_FN (bb, cfun)
1130 gimple_stmt_iterator psi;
1131 loop_p loop = bb->loop_father;
1133 if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
1134 continue;
1136 n_bbs++;
1137 n_p_bbs += bb->count;
1139 if (EDGE_COUNT (bb->succs) > 1)
1141 n_conditions++;
1142 n_p_conditions += bb->count;
1145 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
1147 n_stmts++;
1148 n_p_stmts += bb->count;
1151 if (loop->header == bb && loop_in_sese_p (loop, SCOP_REGION (scop)))
1153 n_loops++;
1154 n_p_loops += bb->count;
1159 fprintf (file, "\nBefore limit_scops SCoP statistics (");
1160 fprintf (file, "BBS:%ld, ", n_bbs);
1161 fprintf (file, "LOOPS:%ld, ", n_loops);
1162 fprintf (file, "CONDITIONS:%ld, ", n_conditions);
1163 fprintf (file, "STMTS:%ld)\n", n_stmts);
1164 fprintf (file, "\nBefore limit_scops SCoP profiling statistics (");
1165 fprintf (file, "BBS:%ld, ", n_p_bbs);
1166 fprintf (file, "LOOPS:%ld, ", n_p_loops);
1167 fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
1168 fprintf (file, "STMTS:%ld)\n", n_p_stmts);
1171 /* Print statistics for SCOPS to FILE. */
1173 static void
1174 print_graphite_statistics (FILE* file, vec<scop_p> scops)
1176 int i;
1177 scop_p scop;
1179 FOR_EACH_VEC_ELT (scops, i, scop)
1180 print_graphite_scop_statistics (file, scop);
1183 /* We limit all SCoPs to SCoPs, that are completely surrounded by a loop.
1185 Example:
1187 for (i |
1189 for (j | SCoP 1
1190 for (k |
1193 * SCoP frontier, as this line is not surrounded by any loop. *
1195 for (l | SCoP 2
1197 This is necessary as scalar evolution and parameter detection need a
1198 outermost loop to initialize parameters correctly.
1200 TODO: FIX scalar evolution and parameter detection to allow more flexible
1201 SCoP frontiers. */
1203 static void
1204 limit_scops (vec<scop_p> *scops)
1206 auto_vec<sd_region, 3> regions;
1208 int i;
1209 scop_p scop;
1211 FOR_EACH_VEC_ELT (*scops, i, scop)
1213 int j;
1214 loop_p loop;
1215 sese region = SCOP_REGION (scop);
1216 build_sese_loop_nests (region);
1218 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region), j, loop)
1219 if (!loop_in_sese_p (loop_outer (loop), region)
1220 && single_exit (loop))
1222 sd_region open_scop;
1223 open_scop.entry = loop->header;
1224 open_scop.exit = single_exit (loop)->dest;
1226 /* This is a hack on top of the limit_scops hack. The
1227 limit_scops hack should disappear all together. */
1228 if (single_succ_p (open_scop.exit)
1229 && contains_only_close_phi_nodes (open_scop.exit))
1230 open_scop.exit = single_succ_edge (open_scop.exit)->dest;
1232 regions.safe_push (open_scop);
1236 free_scops (*scops);
1237 scops->create (3);
1239 create_sese_edges (regions);
1240 build_graphite_scops (regions, scops);
1243 /* Returns true when P1 and P2 are close phis with the same
1244 argument. */
1246 static inline bool
1247 same_close_phi_node (gimple p1, gimple p2)
1249 return operand_equal_p (gimple_phi_arg_def (p1, 0),
1250 gimple_phi_arg_def (p2, 0), 0);
1253 /* Remove the close phi node at GSI and replace its rhs with the rhs
1254 of PHI. */
1256 static void
1257 remove_duplicate_close_phi (gimple phi, gimple_stmt_iterator *gsi)
1259 gimple use_stmt;
1260 use_operand_p use_p;
1261 imm_use_iterator imm_iter;
1262 tree res = gimple_phi_result (phi);
1263 tree def = gimple_phi_result (gsi_stmt (*gsi));
1265 gcc_assert (same_close_phi_node (phi, gsi_stmt (*gsi)));
1267 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
1269 FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
1270 SET_USE (use_p, res);
1272 update_stmt (use_stmt);
1274 /* It is possible that we just created a duplicate close-phi
1275 for an already-processed containing loop. Check for this
1276 case and clean it up. */
1277 if (gimple_code (use_stmt) == GIMPLE_PHI
1278 && gimple_phi_num_args (use_stmt) == 1)
1279 make_close_phi_nodes_unique (gimple_bb (use_stmt));
1282 remove_phi_node (gsi, true);
1285 /* Removes all the close phi duplicates from BB. */
1287 static void
1288 make_close_phi_nodes_unique (basic_block bb)
1290 gimple_stmt_iterator psi;
1292 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
1294 gimple_stmt_iterator gsi = psi;
1295 gimple phi = gsi_stmt (psi);
1297 /* At this point, PHI should be a close phi in normal form. */
1298 gcc_assert (gimple_phi_num_args (phi) == 1);
1300 /* Iterate over the next phis and remove duplicates. */
1301 gsi_next (&gsi);
1302 while (!gsi_end_p (gsi))
1303 if (same_close_phi_node (phi, gsi_stmt (gsi)))
1304 remove_duplicate_close_phi (phi, &gsi);
1305 else
1306 gsi_next (&gsi);
1310 /* Transforms LOOP to the canonical loop closed SSA form. */
1312 static void
1313 canonicalize_loop_closed_ssa (loop_p loop)
1315 edge e = single_exit (loop);
1316 basic_block bb;
1318 if (!e || e->flags & EDGE_ABNORMAL)
1319 return;
1321 bb = e->dest;
1323 if (single_pred_p (bb))
1325 e = split_block_after_labels (bb);
1326 make_close_phi_nodes_unique (e->src);
1328 else
1330 gimple_stmt_iterator psi;
1331 basic_block close = split_edge (e);
1333 e = single_succ_edge (close);
1335 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
1337 gimple phi = gsi_stmt (psi);
1338 unsigned i;
1340 for (i = 0; i < gimple_phi_num_args (phi); i++)
1341 if (gimple_phi_arg_edge (phi, i) == e)
1343 tree res, arg = gimple_phi_arg_def (phi, i);
1344 use_operand_p use_p;
1345 gimple close_phi;
1347 if (TREE_CODE (arg) != SSA_NAME)
1348 continue;
1350 close_phi = create_phi_node (NULL_TREE, close);
1351 res = create_new_def_for (arg, close_phi,
1352 gimple_phi_result_ptr (close_phi));
1353 add_phi_arg (close_phi, arg,
1354 gimple_phi_arg_edge (close_phi, 0),
1355 UNKNOWN_LOCATION);
1356 use_p = gimple_phi_arg_imm_use_ptr (phi, i);
1357 replace_exp (use_p, res);
1358 update_stmt (phi);
1362 make_close_phi_nodes_unique (close);
1365 /* The code above does not properly handle changes in the post dominance
1366 information (yet). */
1367 free_dominance_info (CDI_POST_DOMINATORS);
1370 /* Converts the current loop closed SSA form to a canonical form
1371 expected by the Graphite code generation.
1373 The loop closed SSA form has the following invariant: a variable
1374 defined in a loop that is used outside the loop appears only in the
1375 phi nodes in the destination of the loop exit. These phi nodes are
1376 called close phi nodes.
1378 The canonical loop closed SSA form contains the extra invariants:
1380 - when the loop contains only one exit, the close phi nodes contain
1381 only one argument. That implies that the basic block that contains
1382 the close phi nodes has only one predecessor, that is a basic block
1383 in the loop.
1385 - the basic block containing the close phi nodes does not contain
1386 other statements.
1388 - there exist only one phi node per definition in the loop.
1391 static void
1392 canonicalize_loop_closed_ssa_form (void)
1394 loop_p loop;
1396 #ifdef ENABLE_CHECKING
1397 verify_loop_closed_ssa (true);
1398 #endif
1400 FOR_EACH_LOOP (loop, 0)
1401 canonicalize_loop_closed_ssa (loop);
1403 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1404 update_ssa (TODO_update_ssa);
1406 #ifdef ENABLE_CHECKING
1407 verify_loop_closed_ssa (true);
1408 #endif
1411 /* Find Static Control Parts (SCoP) in the current function and pushes
1412 them to SCOPS. */
1414 void
1415 build_scops (vec<scop_p> *scops)
1417 struct loop *loop = current_loops->tree_root;
1418 auto_vec<sd_region, 3> regions;
1420 canonicalize_loop_closed_ssa_form ();
1421 build_scops_1 (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)),
1422 ENTRY_BLOCK_PTR_FOR_FN (cfun)->loop_father,
1423 &regions, loop);
1424 create_sese_edges (regions);
1425 build_graphite_scops (regions, scops);
1427 if (dump_file && (dump_flags & TDF_DETAILS))
1428 print_graphite_statistics (dump_file, *scops);
1430 limit_scops (scops);
1431 regions.release ();
1433 if (dump_file && (dump_flags & TDF_DETAILS))
1434 fprintf (dump_file, "\nnumber of SCoPs: %d\n",
1435 scops ? scops->length () : 0);
1438 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
1439 different colors. If there are not enough colors, paint the
1440 remaining SCoPs in gray.
1442 Special nodes:
1443 - "*" after the node number denotes the entry of a SCoP,
1444 - "#" after the node number denotes the exit of a SCoP,
1445 - "()" around the node number denotes the entry or the
1446 exit nodes of the SCOP. These are not part of SCoP. */
1448 static void
1449 dot_all_scops_1 (FILE *file, vec<scop_p> scops)
1451 basic_block bb;
1452 edge e;
1453 edge_iterator ei;
1454 scop_p scop;
1455 const char* color;
1456 int i;
1458 /* Disable debugging while printing graph. */
1459 int tmp_dump_flags = dump_flags;
1460 dump_flags = 0;
1462 fprintf (file, "digraph all {\n");
1464 FOR_ALL_BB_FN (bb, cfun)
1466 int part_of_scop = false;
1468 /* Use HTML for every bb label. So we are able to print bbs
1469 which are part of two different SCoPs, with two different
1470 background colors. */
1471 fprintf (file, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
1472 bb->index);
1473 fprintf (file, "CELLSPACING=\"0\">\n");
1475 /* Select color for SCoP. */
1476 FOR_EACH_VEC_ELT (scops, i, scop)
1478 sese region = SCOP_REGION (scop);
1479 if (bb_in_sese_p (bb, region)
1480 || (SESE_EXIT_BB (region) == bb)
1481 || (SESE_ENTRY_BB (region) == bb))
1483 switch (i % 17)
1485 case 0: /* red */
1486 color = "#e41a1c";
1487 break;
1488 case 1: /* blue */
1489 color = "#377eb8";
1490 break;
1491 case 2: /* green */
1492 color = "#4daf4a";
1493 break;
1494 case 3: /* purple */
1495 color = "#984ea3";
1496 break;
1497 case 4: /* orange */
1498 color = "#ff7f00";
1499 break;
1500 case 5: /* yellow */
1501 color = "#ffff33";
1502 break;
1503 case 6: /* brown */
1504 color = "#a65628";
1505 break;
1506 case 7: /* rose */
1507 color = "#f781bf";
1508 break;
1509 case 8:
1510 color = "#8dd3c7";
1511 break;
1512 case 9:
1513 color = "#ffffb3";
1514 break;
1515 case 10:
1516 color = "#bebada";
1517 break;
1518 case 11:
1519 color = "#fb8072";
1520 break;
1521 case 12:
1522 color = "#80b1d3";
1523 break;
1524 case 13:
1525 color = "#fdb462";
1526 break;
1527 case 14:
1528 color = "#b3de69";
1529 break;
1530 case 15:
1531 color = "#fccde5";
1532 break;
1533 case 16:
1534 color = "#bc80bd";
1535 break;
1536 default: /* gray */
1537 color = "#999999";
1540 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color);
1542 if (!bb_in_sese_p (bb, region))
1543 fprintf (file, " (");
1545 if (bb == SESE_ENTRY_BB (region)
1546 && bb == SESE_EXIT_BB (region))
1547 fprintf (file, " %d*# ", bb->index);
1548 else if (bb == SESE_ENTRY_BB (region))
1549 fprintf (file, " %d* ", bb->index);
1550 else if (bb == SESE_EXIT_BB (region))
1551 fprintf (file, " %d# ", bb->index);
1552 else
1553 fprintf (file, " %d ", bb->index);
1555 if (!bb_in_sese_p (bb,region))
1556 fprintf (file, ")");
1558 fprintf (file, "</TD></TR>\n");
1559 part_of_scop = true;
1563 if (!part_of_scop)
1565 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
1566 fprintf (file, " %d </TD></TR>\n", bb->index);
1568 fprintf (file, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
1571 FOR_ALL_BB_FN (bb, cfun)
1573 FOR_EACH_EDGE (e, ei, bb->succs)
1574 fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
1577 fputs ("}\n\n", file);
1579 /* Enable debugging again. */
1580 dump_flags = tmp_dump_flags;
1583 /* Display all SCoPs using dotty. */
1585 DEBUG_FUNCTION void
1586 dot_all_scops (vec<scop_p> scops)
1588 /* When debugging, enable the following code. This cannot be used
1589 in production compilers because it calls "system". */
1590 #if 0
1591 int x;
1592 FILE *stream = fopen ("/tmp/allscops.dot", "w");
1593 gcc_assert (stream);
1595 dot_all_scops_1 (stream, scops);
1596 fclose (stream);
1598 x = system ("dotty /tmp/allscops.dot &");
1599 #else
1600 dot_all_scops_1 (stderr, scops);
1601 #endif
1604 /* Display all SCoPs using dotty. */
1606 DEBUG_FUNCTION void
1607 dot_scop (scop_p scop)
1609 auto_vec<scop_p, 1> scops;
1611 if (scop)
1612 scops.safe_push (scop);
1614 /* When debugging, enable the following code. This cannot be used
1615 in production compilers because it calls "system". */
1616 #if 0
1618 int x;
1619 FILE *stream = fopen ("/tmp/allscops.dot", "w");
1620 gcc_assert (stream);
1622 dot_all_scops_1 (stream, scops);
1623 fclose (stream);
1624 x = system ("dotty /tmp/allscops.dot &");
1626 #else
1627 dot_all_scops_1 (stderr, scops);
1628 #endif
1631 #endif