* tree.h (TYPE_OVERFLOW_SANITIZED): Define.
[official-gcc.git] / gcc / graphite-scop-detection.c
bloba22837a6027dae33a9470ec483b302c05716004d
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_isl
25 #include <isl/set.h>
26 #include <isl/map.h>
27 #include <isl/union_map.h>
28 #endif
30 #include "system.h"
31 #include "coretypes.h"
32 #include "tree.h"
33 #include "predict.h"
34 #include "vec.h"
35 #include "hashtab.h"
36 #include "hash-set.h"
37 #include "machmode.h"
38 #include "tm.h"
39 #include "hard-reg-set.h"
40 #include "input.h"
41 #include "function.h"
42 #include "dominance.h"
43 #include "cfg.h"
44 #include "basic-block.h"
45 #include "tree-ssa-alias.h"
46 #include "internal-fn.h"
47 #include "gimple-expr.h"
48 #include "is-a.h"
49 #include "gimple.h"
50 #include "gimple-iterator.h"
51 #include "gimple-ssa.h"
52 #include "tree-phinodes.h"
53 #include "ssa-iterators.h"
54 #include "tree-ssa-loop-manip.h"
55 #include "tree-ssa-loop-niter.h"
56 #include "tree-ssa-loop.h"
57 #include "tree-into-ssa.h"
58 #include "tree-ssa.h"
59 #include "cfgloop.h"
60 #include "tree-chrec.h"
61 #include "tree-data-ref.h"
62 #include "tree-scalar-evolution.h"
63 #include "tree-pass.h"
64 #include "sese.h"
65 #include "tree-ssa-propagate.h"
66 #include "cp/cp-tree.h"
68 #ifdef HAVE_isl
69 #include "graphite-poly.h"
70 #include "graphite-scop-detection.h"
72 /* Forward declarations. */
73 static void make_close_phi_nodes_unique (basic_block);
75 /* The type of the analyzed basic block. */
77 typedef enum gbb_type {
78 GBB_UNKNOWN,
79 GBB_LOOP_SING_EXIT_HEADER,
80 GBB_LOOP_MULT_EXIT_HEADER,
81 GBB_LOOP_EXIT,
82 GBB_COND_HEADER,
83 GBB_SIMPLE,
84 GBB_LAST
85 } gbb_type;
87 /* Detect the type of BB. Loop headers are only marked, if they are
88 new. This means their loop_father is different to LAST_LOOP.
89 Otherwise they are treated like any other bb and their type can be
90 any other type. */
92 static gbb_type
93 get_bb_type (basic_block bb, struct loop *last_loop)
95 vec<basic_block> dom;
96 int nb_dom;
97 struct loop *loop = bb->loop_father;
99 /* Check, if we entry into a new loop. */
100 if (loop != last_loop)
102 if (single_exit (loop) != NULL)
103 return GBB_LOOP_SING_EXIT_HEADER;
104 else if (loop->num != 0)
105 return GBB_LOOP_MULT_EXIT_HEADER;
106 else
107 return GBB_COND_HEADER;
110 dom = get_dominated_by (CDI_DOMINATORS, bb);
111 nb_dom = dom.length ();
112 dom.release ();
114 if (nb_dom == 0)
115 return GBB_LAST;
117 if (nb_dom == 1 && single_succ_p (bb))
118 return GBB_SIMPLE;
120 return GBB_COND_HEADER;
123 /* A SCoP detection region, defined using bbs as borders.
125 All control flow touching this region, comes in passing basic_block
126 ENTRY and leaves passing basic_block EXIT. By using bbs instead of
127 edges for the borders we are able to represent also regions that do
128 not have a single entry or exit edge.
130 But as they have a single entry basic_block and a single exit
131 basic_block, we are able to generate for every sd_region a single
132 entry and exit edge.
136 3 <- entry
139 / \ This region contains: {3, 4, 5, 6, 7, 8}
144 9 <- exit */
147 typedef struct sd_region_p
149 /* The entry bb dominates all bbs in the sd_region. It is part of
150 the region. */
151 basic_block entry;
153 /* The exit bb postdominates all bbs in the sd_region, but is not
154 part of the region. */
155 basic_block exit;
156 } sd_region;
160 /* Moves the scops from SOURCE to TARGET and clean up SOURCE. */
162 static void
163 move_sd_regions (vec<sd_region> *source, vec<sd_region> *target)
165 sd_region *s;
166 int i;
168 FOR_EACH_VEC_ELT (*source, i, s)
169 target->safe_push (*s);
171 source->release ();
174 /* Something like "n * m" is not allowed. */
176 static bool
177 graphite_can_represent_init (tree e)
179 switch (TREE_CODE (e))
181 case POLYNOMIAL_CHREC:
182 return graphite_can_represent_init (CHREC_LEFT (e))
183 && graphite_can_represent_init (CHREC_RIGHT (e));
185 case MULT_EXPR:
186 if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
187 return graphite_can_represent_init (TREE_OPERAND (e, 0))
188 && tree_fits_shwi_p (TREE_OPERAND (e, 1));
189 else
190 return graphite_can_represent_init (TREE_OPERAND (e, 1))
191 && tree_fits_shwi_p (TREE_OPERAND (e, 0));
193 case PLUS_EXPR:
194 case POINTER_PLUS_EXPR:
195 case MINUS_EXPR:
196 return graphite_can_represent_init (TREE_OPERAND (e, 0))
197 && graphite_can_represent_init (TREE_OPERAND (e, 1));
199 case NEGATE_EXPR:
200 case BIT_NOT_EXPR:
201 CASE_CONVERT:
202 case NON_LVALUE_EXPR:
203 return graphite_can_represent_init (TREE_OPERAND (e, 0));
205 default:
206 break;
209 return true;
212 /* Return true when SCEV can be represented in the polyhedral model.
214 An expression can be represented, if it can be expressed as an
215 affine expression. For loops (i, j) and parameters (m, n) all
216 affine expressions are of the form:
218 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
220 1 i + 20 j + (-2) m + 25
222 Something like "i * n" or "n * m" is not allowed. */
224 static bool
225 graphite_can_represent_scev (tree scev)
227 if (chrec_contains_undetermined (scev))
228 return false;
230 /* We disable the handling of pointer types, because it’s currently not
231 supported by Graphite with the ISL AST generator. SSA_NAME nodes are
232 the only nodes, which are disabled in case they are pointers to object
233 types, but this can be changed. */
235 if (TYPE_PTROB_P (TREE_TYPE (scev)) && TREE_CODE (scev) == SSA_NAME)
236 return false;
238 switch (TREE_CODE (scev))
240 case NEGATE_EXPR:
241 case BIT_NOT_EXPR:
242 CASE_CONVERT:
243 case NON_LVALUE_EXPR:
244 return graphite_can_represent_scev (TREE_OPERAND (scev, 0));
246 case PLUS_EXPR:
247 case POINTER_PLUS_EXPR:
248 case MINUS_EXPR:
249 return graphite_can_represent_scev (TREE_OPERAND (scev, 0))
250 && graphite_can_represent_scev (TREE_OPERAND (scev, 1));
252 case MULT_EXPR:
253 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 0)))
254 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 1)))
255 && !(chrec_contains_symbols (TREE_OPERAND (scev, 0))
256 && chrec_contains_symbols (TREE_OPERAND (scev, 1)))
257 && graphite_can_represent_init (scev)
258 && graphite_can_represent_scev (TREE_OPERAND (scev, 0))
259 && graphite_can_represent_scev (TREE_OPERAND (scev, 1));
261 case POLYNOMIAL_CHREC:
262 /* Check for constant strides. With a non constant stride of
263 'n' we would have a value of 'iv * n'. Also check that the
264 initial value can represented: for example 'n * m' cannot be
265 represented. */
266 if (!evolution_function_right_is_integer_cst (scev)
267 || !graphite_can_represent_init (scev))
268 return false;
269 return graphite_can_represent_scev (CHREC_LEFT (scev));
271 default:
272 break;
275 /* Only affine functions can be represented. */
276 if (tree_contains_chrecs (scev, NULL)
277 || !scev_is_linear_expression (scev))
278 return false;
280 return true;
284 /* Return true when EXPR can be represented in the polyhedral model.
286 This means an expression can be represented, if it is linear with
287 respect to the loops and the strides are non parametric.
288 LOOP is the place where the expr will be evaluated. SCOP_ENTRY defines the
289 entry of the region we analyse. */
291 static bool
292 graphite_can_represent_expr (basic_block scop_entry, loop_p loop,
293 tree expr)
295 tree scev = analyze_scalar_evolution (loop, expr);
297 scev = instantiate_scev (scop_entry, loop, scev);
299 return graphite_can_represent_scev (scev);
302 /* Return true if the data references of STMT can be represented by
303 Graphite. */
305 static bool
306 stmt_has_simple_data_refs_p (loop_p outermost_loop ATTRIBUTE_UNUSED,
307 gimple stmt)
309 data_reference_p dr;
310 unsigned i;
311 int j;
312 bool res = true;
313 vec<data_reference_p> drs = vNULL;
314 loop_p outer;
316 for (outer = loop_containing_stmt (stmt); outer; outer = loop_outer (outer))
318 graphite_find_data_references_in_stmt (outer,
319 loop_containing_stmt (stmt),
320 stmt, &drs);
322 FOR_EACH_VEC_ELT (drs, j, dr)
323 for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
324 if (!graphite_can_represent_scev (DR_ACCESS_FN (dr, i)))
326 res = false;
327 goto done;
330 free_data_refs (drs);
331 drs.create (0);
334 done:
335 free_data_refs (drs);
336 return res;
339 /* Return true only when STMT is simple enough for being handled by
340 Graphite. This depends on SCOP_ENTRY, as the parameters are
341 initialized relatively to this basic block, the linear functions
342 are initialized to OUTERMOST_LOOP and BB is the place where we try
343 to evaluate the STMT. */
345 static bool
346 stmt_simple_for_scop_p (basic_block scop_entry, loop_p outermost_loop,
347 gimple stmt, basic_block bb)
349 loop_p loop = bb->loop_father;
351 gcc_assert (scop_entry);
353 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
354 Calls have side-effects, except those to const or pure
355 functions. */
356 if (gimple_has_volatile_ops (stmt)
357 || (gimple_code (stmt) == GIMPLE_CALL
358 && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
359 || (gimple_code (stmt) == GIMPLE_ASM))
360 return false;
362 if (is_gimple_debug (stmt))
363 return true;
365 if (!stmt_has_simple_data_refs_p (outermost_loop, stmt))
366 return false;
368 switch (gimple_code (stmt))
370 case GIMPLE_RETURN:
371 case GIMPLE_LABEL:
372 return true;
374 case GIMPLE_COND:
376 /* We can handle all binary comparisons. Inequalities are
377 also supported as they can be represented with union of
378 polyhedra. */
379 enum tree_code code = gimple_cond_code (stmt);
380 if (!(code == LT_EXPR
381 || code == GT_EXPR
382 || code == LE_EXPR
383 || code == GE_EXPR
384 || code == EQ_EXPR
385 || code == NE_EXPR))
386 return false;
388 for (unsigned i = 0; i < 2; ++i)
390 tree op = gimple_op (stmt, i);
391 if (!graphite_can_represent_expr (scop_entry, loop, op)
392 /* We can not handle REAL_TYPE. Failed for pr39260. */
393 || TREE_CODE (TREE_TYPE (op)) == REAL_TYPE)
394 return false;
397 return true;
400 case GIMPLE_ASSIGN:
401 case GIMPLE_CALL:
402 return true;
404 default:
405 /* These nodes cut a new scope. */
406 return false;
409 return false;
412 /* Returns the statement of BB that contains a harmful operation: that
413 can be a function call with side effects, the induction variables
414 are not linear with respect to SCOP_ENTRY, etc. The current open
415 scop should end before this statement. The evaluation is limited using
416 OUTERMOST_LOOP as outermost loop that may change. */
418 static gimple
419 harmful_stmt_in_bb (basic_block scop_entry, loop_p outer_loop, basic_block bb)
421 gimple_stmt_iterator gsi;
423 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
424 if (!stmt_simple_for_scop_p (scop_entry, outer_loop, gsi_stmt (gsi), bb))
425 return gsi_stmt (gsi);
427 return NULL;
430 /* Return true if LOOP can be represented in the polyhedral
431 representation. This is evaluated taking SCOP_ENTRY and
432 OUTERMOST_LOOP in mind. */
434 static bool
435 graphite_can_represent_loop (basic_block scop_entry, loop_p loop)
437 tree niter;
438 struct tree_niter_desc niter_desc;
440 /* FIXME: For the moment, graphite cannot be used on loops that
441 iterate using induction variables that wrap. */
443 return number_of_iterations_exit (loop, single_exit (loop), &niter_desc, false)
444 && niter_desc.control.no_overflow
445 && (niter = number_of_latch_executions (loop))
446 && !chrec_contains_undetermined (niter)
447 && graphite_can_represent_expr (scop_entry, loop, niter);
450 /* Store information needed by scopdet_* functions. */
452 struct scopdet_info
454 /* Exit of the open scop would stop if the current BB is harmful. */
455 basic_block exit;
457 /* Where the next scop would start if the current BB is harmful. */
458 basic_block next;
460 /* The bb or one of its children contains open loop exits. That means
461 loop exit nodes that are not surrounded by a loop dominated by bb. */
462 bool exits;
464 /* The bb or one of its children contains only structures we can handle. */
465 bool difficult;
468 static struct scopdet_info build_scops_1 (basic_block, loop_p,
469 vec<sd_region> *, loop_p);
471 /* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB
472 to SCOPS. TYPE is the gbb_type of BB. */
474 static struct scopdet_info
475 scopdet_basic_block_info (basic_block bb, loop_p outermost_loop,
476 vec<sd_region> *scops, gbb_type type)
478 loop_p loop = bb->loop_father;
479 struct scopdet_info result;
480 gimple stmt;
482 /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps. */
483 basic_block entry_block = ENTRY_BLOCK_PTR_FOR_FN (cfun);
484 stmt = harmful_stmt_in_bb (entry_block, outermost_loop, bb);
485 result.difficult = (stmt != NULL);
486 result.exit = NULL;
488 switch (type)
490 case GBB_LAST:
491 result.next = NULL;
492 result.exits = false;
494 /* Mark bbs terminating a SESE region difficult, if they start
495 a condition or if the block it exits to cannot be split
496 with make_forwarder_block. */
497 if (!single_succ_p (bb)
498 || bb_has_abnormal_pred (single_succ (bb)))
499 result.difficult = true;
500 else
501 result.exit = single_succ (bb);
503 break;
505 case GBB_SIMPLE:
506 result.next = single_succ (bb);
507 result.exits = false;
508 result.exit = single_succ (bb);
509 break;
511 case GBB_LOOP_SING_EXIT_HEADER:
513 auto_vec<sd_region, 3> regions;
514 struct scopdet_info sinfo;
515 edge exit_e = single_exit (loop);
517 sinfo = build_scops_1 (bb, outermost_loop, &regions, loop);
519 if (!graphite_can_represent_loop (entry_block, loop))
520 result.difficult = true;
522 result.difficult |= sinfo.difficult;
524 /* Try again with another loop level. */
525 if (result.difficult
526 && loop_depth (outermost_loop) + 1 == loop_depth (loop))
528 outermost_loop = loop;
530 regions.release ();
531 regions.create (3);
533 sinfo = scopdet_basic_block_info (bb, outermost_loop, scops, type);
535 result = sinfo;
536 result.difficult = true;
538 if (sinfo.difficult)
539 move_sd_regions (&regions, scops);
540 else
542 sd_region open_scop;
543 open_scop.entry = bb;
544 open_scop.exit = exit_e->dest;
545 scops->safe_push (open_scop);
546 regions.release ();
549 else
551 result.exit = exit_e->dest;
552 result.next = exit_e->dest;
554 /* If we do not dominate result.next, remove it. It's either
555 the exit block, or another bb dominates it and will
556 call the scop detection for this bb. */
557 if (!dominated_by_p (CDI_DOMINATORS, result.next, bb))
558 result.next = NULL;
560 if (exit_e->src->loop_father != loop)
561 result.next = NULL;
563 result.exits = false;
565 if (result.difficult)
566 move_sd_regions (&regions, scops);
567 else
568 regions.release ();
571 break;
574 case GBB_LOOP_MULT_EXIT_HEADER:
576 /* XXX: For now we just do not join loops with multiple exits. If the
577 exits lead to the same bb it may be possible to join the loop. */
578 auto_vec<sd_region, 3> regions;
579 vec<edge> exits = get_loop_exit_edges (loop);
580 edge e;
581 int i;
582 build_scops_1 (bb, loop, &regions, loop);
584 /* Scan the code dominated by this loop. This means all bbs, that are
585 are dominated by a bb in this loop, but are not part of this loop.
587 The easiest case:
588 - The loop exit destination is dominated by the exit sources.
590 TODO: We miss here the more complex cases:
591 - The exit destinations are dominated by another bb inside
592 the loop.
593 - The loop dominates bbs, that are not exit destinations. */
594 FOR_EACH_VEC_ELT (exits, i, e)
595 if (e->src->loop_father == loop
596 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src))
598 if (loop_outer (outermost_loop))
599 outermost_loop = loop_outer (outermost_loop);
601 /* Pass loop_outer to recognize e->dest as loop header in
602 build_scops_1. */
603 if (e->dest->loop_father->header == e->dest)
604 build_scops_1 (e->dest, outermost_loop, &regions,
605 loop_outer (e->dest->loop_father));
606 else
607 build_scops_1 (e->dest, outermost_loop, &regions,
608 e->dest->loop_father);
611 result.next = NULL;
612 result.exit = NULL;
613 result.difficult = true;
614 result.exits = false;
615 move_sd_regions (&regions, scops);
616 exits.release ();
617 break;
619 case GBB_COND_HEADER:
621 auto_vec<sd_region, 3> regions;
622 struct scopdet_info sinfo;
623 vec<basic_block> dominated;
624 int i;
625 basic_block dom_bb;
626 basic_block last_exit = NULL;
627 edge e;
628 result.exits = false;
630 /* First check the successors of BB, and check if it is
631 possible to join the different branches. */
632 FOR_EACH_VEC_SAFE_ELT (bb->succs, i, e)
634 /* Ignore loop exits. They will be handled after the loop
635 body. */
636 if (loop_exits_to_bb_p (loop, e->dest))
638 result.exits = true;
639 continue;
642 /* Do not follow edges that lead to the end of the
643 conditions block. For example, in
646 | /|\
647 | 1 2 |
648 | | | |
649 | 3 4 |
650 | \|/
653 the edge from 0 => 6. Only check if all paths lead to
654 the same node 6. */
656 if (!single_pred_p (e->dest))
658 /* Check, if edge leads directly to the end of this
659 condition. */
660 if (!last_exit)
661 last_exit = e->dest;
663 if (e->dest != last_exit)
664 result.difficult = true;
666 continue;
669 if (!dominated_by_p (CDI_DOMINATORS, e->dest, bb))
671 result.difficult = true;
672 continue;
675 sinfo = build_scops_1 (e->dest, outermost_loop, &regions, loop);
677 result.exits |= sinfo.exits;
678 result.difficult |= sinfo.difficult;
680 /* Checks, if all branches end at the same point.
681 If that is true, the condition stays joinable.
682 Have a look at the example above. */
683 if (sinfo.exit)
685 if (!last_exit)
686 last_exit = sinfo.exit;
688 if (sinfo.exit != last_exit)
689 result.difficult = true;
691 else
692 result.difficult = true;
695 if (!last_exit)
696 result.difficult = true;
698 /* Join the branches of the condition if possible. */
699 if (!result.exits && !result.difficult)
701 /* Only return a next pointer if we dominate this pointer.
702 Otherwise it will be handled by the bb dominating it. */
703 if (dominated_by_p (CDI_DOMINATORS, last_exit, bb)
704 && last_exit != bb)
705 result.next = last_exit;
706 else
707 result.next = NULL;
709 result.exit = last_exit;
711 regions.release ();
712 break;
715 /* Scan remaining bbs dominated by BB. */
716 dominated = get_dominated_by (CDI_DOMINATORS, bb);
718 FOR_EACH_VEC_ELT (dominated, i, dom_bb)
720 /* Ignore loop exits: they will be handled after the loop body. */
721 if (loop_depth (find_common_loop (loop, dom_bb->loop_father))
722 < loop_depth (loop))
724 result.exits = true;
725 continue;
728 /* Ignore the bbs processed above. */
729 if (single_pred_p (dom_bb) && single_pred (dom_bb) == bb)
730 continue;
732 if (loop_depth (loop) > loop_depth (dom_bb->loop_father))
733 sinfo = build_scops_1 (dom_bb, outermost_loop, &regions,
734 loop_outer (loop));
735 else
736 sinfo = build_scops_1 (dom_bb, outermost_loop, &regions, loop);
738 result.exits |= sinfo.exits;
739 result.difficult = true;
740 result.exit = NULL;
743 dominated.release ();
745 result.next = NULL;
746 move_sd_regions (&regions, scops);
748 break;
751 default:
752 gcc_unreachable ();
755 return result;
758 /* Starting from CURRENT we walk the dominance tree and add new sd_regions to
759 SCOPS. The analyse if a sd_region can be handled is based on the value
760 of OUTERMOST_LOOP. Only loops inside OUTERMOST loops may change. LOOP
761 is the loop in which CURRENT is handled.
763 TODO: These functions got a little bit big. They definitely should be cleaned
764 up. */
766 static struct scopdet_info
767 build_scops_1 (basic_block current, loop_p outermost_loop,
768 vec<sd_region> *scops, loop_p loop)
770 bool in_scop = false;
771 sd_region open_scop;
772 struct scopdet_info sinfo;
774 /* Initialize result. */
775 struct scopdet_info result;
776 result.exits = false;
777 result.difficult = false;
778 result.next = NULL;
779 result.exit = NULL;
780 open_scop.entry = NULL;
781 open_scop.exit = NULL;
782 sinfo.exit = NULL;
784 /* Loop over the dominance tree. If we meet a difficult bb, close
785 the current SCoP. Loop and condition header start a new layer,
786 and can only be added if all bbs in deeper layers are simple. */
787 while (current != NULL)
789 sinfo = scopdet_basic_block_info (current, outermost_loop, scops,
790 get_bb_type (current, loop));
792 if (!in_scop && !(sinfo.exits || sinfo.difficult))
794 open_scop.entry = current;
795 open_scop.exit = NULL;
796 in_scop = true;
798 else if (in_scop && (sinfo.exits || sinfo.difficult))
800 open_scop.exit = current;
801 scops->safe_push (open_scop);
802 in_scop = false;
805 result.difficult |= sinfo.difficult;
806 result.exits |= sinfo.exits;
808 current = sinfo.next;
811 /* Try to close open_scop, if we are still in an open SCoP. */
812 if (in_scop)
814 open_scop.exit = sinfo.exit;
815 gcc_assert (open_scop.exit);
816 scops->safe_push (open_scop);
819 result.exit = sinfo.exit;
820 return result;
823 /* Checks if a bb is contained in REGION. */
825 static bool
826 bb_in_sd_region (basic_block bb, sd_region *region)
828 return bb_in_region (bb, region->entry, region->exit);
831 /* Returns the single entry edge of REGION, if it does not exits NULL. */
833 static edge
834 find_single_entry_edge (sd_region *region)
836 edge e;
837 edge_iterator ei;
838 edge entry = NULL;
840 FOR_EACH_EDGE (e, ei, region->entry->preds)
841 if (!bb_in_sd_region (e->src, region))
843 if (entry)
845 entry = NULL;
846 break;
849 else
850 entry = e;
853 return entry;
856 /* Returns the single exit edge of REGION, if it does not exits NULL. */
858 static edge
859 find_single_exit_edge (sd_region *region)
861 edge e;
862 edge_iterator ei;
863 edge exit = NULL;
865 FOR_EACH_EDGE (e, ei, region->exit->preds)
866 if (bb_in_sd_region (e->src, region))
868 if (exit)
870 exit = NULL;
871 break;
874 else
875 exit = e;
878 return exit;
881 /* Create a single entry edge for REGION. */
883 static void
884 create_single_entry_edge (sd_region *region)
886 if (find_single_entry_edge (region))
887 return;
889 /* There are multiple predecessors for bb_3
891 | 1 2
892 | | /
893 | |/
894 | 3 <- entry
895 | |\
896 | | |
897 | 4 ^
898 | | |
899 | |/
902 There are two edges (1->3, 2->3), that point from outside into the region,
903 and another one (5->3), a loop latch, lead to bb_3.
905 We split bb_3.
907 | 1 2
908 | | /
909 | |/
910 |3.0
911 | |\ (3.0 -> 3.1) = single entry edge
912 |3.1 | <- entry
913 | | |
914 | | |
915 | 4 ^
916 | | |
917 | |/
920 If the loop is part of the SCoP, we have to redirect the loop latches.
922 | 1 2
923 | | /
924 | |/
925 |3.0
926 | | (3.0 -> 3.1) = entry edge
927 |3.1 <- entry
928 | |\
929 | | |
930 | 4 ^
931 | | |
932 | |/
933 | 5 */
935 if (region->entry->loop_father->header != region->entry
936 || dominated_by_p (CDI_DOMINATORS,
937 loop_latch_edge (region->entry->loop_father)->src,
938 region->exit))
940 edge forwarder = split_block_after_labels (region->entry);
941 region->entry = forwarder->dest;
943 else
944 /* This case is never executed, as the loop headers seem always to have a
945 single edge pointing from outside into the loop. */
946 gcc_unreachable ();
948 gcc_checking_assert (find_single_entry_edge (region));
951 /* Check if the sd_region, mentioned in EDGE, has no exit bb. */
953 static bool
954 sd_region_without_exit (edge e)
956 sd_region *r = (sd_region *) e->aux;
958 if (r)
959 return r->exit == NULL;
960 else
961 return false;
964 /* Create a single exit edge for REGION. */
966 static void
967 create_single_exit_edge (sd_region *region)
969 edge e;
970 edge_iterator ei;
971 edge forwarder = NULL;
972 basic_block exit;
974 /* We create a forwarder bb (5) for all edges leaving this region
975 (3->5, 4->5). All other edges leading to the same bb, are moved
976 to a new bb (6). If these edges where part of another region (2->5)
977 we update the region->exit pointer, of this region.
979 To identify which edge belongs to which region we depend on the e->aux
980 pointer in every edge. It points to the region of the edge or to NULL,
981 if the edge is not part of any region.
983 1 2 3 4 1->5 no region, 2->5 region->exit = 5,
984 \| |/ 3->5 region->exit = NULL, 4->5 region->exit = NULL
985 5 <- exit
987 changes to
989 1 2 3 4 1->6 no region, 2->6 region->exit = 6,
990 | | \/ 3->5 no region, 4->5 no region,
991 | | 5
992 \| / 5->6 region->exit = 6
995 Now there is only a single exit edge (5->6). */
996 exit = region->exit;
997 region->exit = NULL;
998 forwarder = make_forwarder_block (exit, &sd_region_without_exit, NULL);
1000 /* Unmark the edges, that are no longer exit edges. */
1001 FOR_EACH_EDGE (e, ei, forwarder->src->preds)
1002 if (e->aux)
1003 e->aux = NULL;
1005 /* Mark the new exit edge. */
1006 single_succ_edge (forwarder->src)->aux = region;
1008 /* Update the exit bb of all regions, where exit edges lead to
1009 forwarder->dest. */
1010 FOR_EACH_EDGE (e, ei, forwarder->dest->preds)
1011 if (e->aux)
1012 ((sd_region *) e->aux)->exit = forwarder->dest;
1014 gcc_checking_assert (find_single_exit_edge (region));
1017 /* Unmark the exit edges of all REGIONS.
1018 See comment in "create_single_exit_edge". */
1020 static void
1021 unmark_exit_edges (vec<sd_region> regions)
1023 int i;
1024 sd_region *s;
1025 edge e;
1026 edge_iterator ei;
1028 FOR_EACH_VEC_ELT (regions, i, s)
1029 FOR_EACH_EDGE (e, ei, s->exit->preds)
1030 e->aux = NULL;
1034 /* Mark the exit edges of all REGIONS.
1035 See comment in "create_single_exit_edge". */
1037 static void
1038 mark_exit_edges (vec<sd_region> regions)
1040 int i;
1041 sd_region *s;
1042 edge e;
1043 edge_iterator ei;
1045 FOR_EACH_VEC_ELT (regions, i, s)
1046 FOR_EACH_EDGE (e, ei, s->exit->preds)
1047 if (bb_in_sd_region (e->src, s))
1048 e->aux = s;
1051 /* Create for all scop regions a single entry and a single exit edge. */
1053 static void
1054 create_sese_edges (vec<sd_region> regions)
1056 int i;
1057 sd_region *s;
1059 FOR_EACH_VEC_ELT (regions, i, s)
1060 create_single_entry_edge (s);
1062 mark_exit_edges (regions);
1064 FOR_EACH_VEC_ELT (regions, i, s)
1065 /* Don't handle multiple edges exiting the function. */
1066 if (!find_single_exit_edge (s)
1067 && s->exit != EXIT_BLOCK_PTR_FOR_FN (cfun))
1068 create_single_exit_edge (s);
1070 unmark_exit_edges (regions);
1072 calculate_dominance_info (CDI_DOMINATORS);
1073 fix_loop_structure (NULL);
1075 #ifdef ENABLE_CHECKING
1076 verify_loop_structure ();
1077 verify_ssa (false, true);
1078 #endif
1081 /* Create graphite SCoPs from an array of scop detection REGIONS. */
1083 static void
1084 build_graphite_scops (vec<sd_region> regions,
1085 vec<scop_p> *scops)
1087 int i;
1088 sd_region *s;
1090 FOR_EACH_VEC_ELT (regions, i, s)
1092 edge entry = find_single_entry_edge (s);
1093 edge exit = find_single_exit_edge (s);
1094 scop_p scop;
1096 if (!exit)
1097 continue;
1099 scop = new_scop (new_sese (entry, exit));
1100 scops->safe_push (scop);
1102 /* Are there overlapping SCoPs? */
1103 #ifdef ENABLE_CHECKING
1105 int j;
1106 sd_region *s2;
1108 FOR_EACH_VEC_ELT (regions, j, s2)
1109 if (s != s2)
1110 gcc_assert (!bb_in_sd_region (s->entry, s2));
1112 #endif
1116 /* Returns true when BB contains only close phi nodes. */
1118 static bool
1119 contains_only_close_phi_nodes (basic_block bb)
1121 gimple_stmt_iterator gsi;
1123 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1124 if (gimple_code (gsi_stmt (gsi)) != GIMPLE_LABEL)
1125 return false;
1127 return true;
1130 /* Print statistics for SCOP to FILE. */
1132 static void
1133 print_graphite_scop_statistics (FILE* file, scop_p scop)
1135 long n_bbs = 0;
1136 long n_loops = 0;
1137 long n_stmts = 0;
1138 long n_conditions = 0;
1139 long n_p_bbs = 0;
1140 long n_p_loops = 0;
1141 long n_p_stmts = 0;
1142 long n_p_conditions = 0;
1144 basic_block bb;
1146 FOR_ALL_BB_FN (bb, cfun)
1148 gimple_stmt_iterator psi;
1149 loop_p loop = bb->loop_father;
1151 if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
1152 continue;
1154 n_bbs++;
1155 n_p_bbs += bb->count;
1157 if (EDGE_COUNT (bb->succs) > 1)
1159 n_conditions++;
1160 n_p_conditions += bb->count;
1163 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
1165 n_stmts++;
1166 n_p_stmts += bb->count;
1169 if (loop->header == bb && loop_in_sese_p (loop, SCOP_REGION (scop)))
1171 n_loops++;
1172 n_p_loops += bb->count;
1177 fprintf (file, "\nBefore limit_scops SCoP statistics (");
1178 fprintf (file, "BBS:%ld, ", n_bbs);
1179 fprintf (file, "LOOPS:%ld, ", n_loops);
1180 fprintf (file, "CONDITIONS:%ld, ", n_conditions);
1181 fprintf (file, "STMTS:%ld)\n", n_stmts);
1182 fprintf (file, "\nBefore limit_scops SCoP profiling statistics (");
1183 fprintf (file, "BBS:%ld, ", n_p_bbs);
1184 fprintf (file, "LOOPS:%ld, ", n_p_loops);
1185 fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
1186 fprintf (file, "STMTS:%ld)\n", n_p_stmts);
1189 /* Print statistics for SCOPS to FILE. */
1191 static void
1192 print_graphite_statistics (FILE* file, vec<scop_p> scops)
1194 int i;
1195 scop_p scop;
1197 FOR_EACH_VEC_ELT (scops, i, scop)
1198 print_graphite_scop_statistics (file, scop);
1201 /* We limit all SCoPs to SCoPs, that are completely surrounded by a loop.
1203 Example:
1205 for (i |
1207 for (j | SCoP 1
1208 for (k |
1211 * SCoP frontier, as this line is not surrounded by any loop. *
1213 for (l | SCoP 2
1215 This is necessary as scalar evolution and parameter detection need a
1216 outermost loop to initialize parameters correctly.
1218 TODO: FIX scalar evolution and parameter detection to allow more flexible
1219 SCoP frontiers. */
1221 static void
1222 limit_scops (vec<scop_p> *scops)
1224 auto_vec<sd_region, 3> regions;
1226 int i;
1227 scop_p scop;
1229 FOR_EACH_VEC_ELT (*scops, i, scop)
1231 int j;
1232 loop_p loop;
1233 sese region = SCOP_REGION (scop);
1234 build_sese_loop_nests (region);
1236 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region), j, loop)
1237 if (!loop_in_sese_p (loop_outer (loop), region)
1238 && single_exit (loop))
1240 sd_region open_scop;
1241 open_scop.entry = loop->header;
1242 open_scop.exit = single_exit (loop)->dest;
1244 /* This is a hack on top of the limit_scops hack. The
1245 limit_scops hack should disappear all together. */
1246 if (single_succ_p (open_scop.exit)
1247 && contains_only_close_phi_nodes (open_scop.exit))
1248 open_scop.exit = single_succ_edge (open_scop.exit)->dest;
1250 regions.safe_push (open_scop);
1254 free_scops (*scops);
1255 scops->create (3);
1257 create_sese_edges (regions);
1258 build_graphite_scops (regions, scops);
1261 /* Returns true when P1 and P2 are close phis with the same
1262 argument. */
1264 static inline bool
1265 same_close_phi_node (gimple p1, gimple p2)
1267 return operand_equal_p (gimple_phi_arg_def (p1, 0),
1268 gimple_phi_arg_def (p2, 0), 0);
1271 /* Remove the close phi node at GSI and replace its rhs with the rhs
1272 of PHI. */
1274 static void
1275 remove_duplicate_close_phi (gimple phi, gimple_stmt_iterator *gsi)
1277 gimple use_stmt;
1278 use_operand_p use_p;
1279 imm_use_iterator imm_iter;
1280 tree res = gimple_phi_result (phi);
1281 tree def = gimple_phi_result (gsi_stmt (*gsi));
1283 gcc_assert (same_close_phi_node (phi, gsi_stmt (*gsi)));
1285 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
1287 FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
1288 SET_USE (use_p, res);
1290 update_stmt (use_stmt);
1292 /* It is possible that we just created a duplicate close-phi
1293 for an already-processed containing loop. Check for this
1294 case and clean it up. */
1295 if (gimple_code (use_stmt) == GIMPLE_PHI
1296 && gimple_phi_num_args (use_stmt) == 1)
1297 make_close_phi_nodes_unique (gimple_bb (use_stmt));
1300 remove_phi_node (gsi, true);
1303 /* Removes all the close phi duplicates from BB. */
1305 static void
1306 make_close_phi_nodes_unique (basic_block bb)
1308 gimple_stmt_iterator psi;
1310 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
1312 gimple_stmt_iterator gsi = psi;
1313 gimple phi = gsi_stmt (psi);
1315 /* At this point, PHI should be a close phi in normal form. */
1316 gcc_assert (gimple_phi_num_args (phi) == 1);
1318 /* Iterate over the next phis and remove duplicates. */
1319 gsi_next (&gsi);
1320 while (!gsi_end_p (gsi))
1321 if (same_close_phi_node (phi, gsi_stmt (gsi)))
1322 remove_duplicate_close_phi (phi, &gsi);
1323 else
1324 gsi_next (&gsi);
1328 /* Transforms LOOP to the canonical loop closed SSA form. */
1330 static void
1331 canonicalize_loop_closed_ssa (loop_p loop)
1333 edge e = single_exit (loop);
1334 basic_block bb;
1336 if (!e || e->flags & EDGE_ABNORMAL)
1337 return;
1339 bb = e->dest;
1341 if (single_pred_p (bb))
1343 e = split_block_after_labels (bb);
1344 make_close_phi_nodes_unique (e->src);
1346 else
1348 gimple_stmt_iterator psi;
1349 basic_block close = split_edge (e);
1351 e = single_succ_edge (close);
1353 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
1355 gimple phi = gsi_stmt (psi);
1356 unsigned i;
1358 for (i = 0; i < gimple_phi_num_args (phi); i++)
1359 if (gimple_phi_arg_edge (phi, i) == e)
1361 tree res, arg = gimple_phi_arg_def (phi, i);
1362 use_operand_p use_p;
1363 gimple close_phi;
1365 if (TREE_CODE (arg) != SSA_NAME)
1366 continue;
1368 close_phi = create_phi_node (NULL_TREE, close);
1369 res = create_new_def_for (arg, close_phi,
1370 gimple_phi_result_ptr (close_phi));
1371 add_phi_arg (close_phi, arg,
1372 gimple_phi_arg_edge (close_phi, 0),
1373 UNKNOWN_LOCATION);
1374 use_p = gimple_phi_arg_imm_use_ptr (phi, i);
1375 replace_exp (use_p, res);
1376 update_stmt (phi);
1380 make_close_phi_nodes_unique (close);
1383 /* The code above does not properly handle changes in the post dominance
1384 information (yet). */
1385 free_dominance_info (CDI_POST_DOMINATORS);
1388 /* Converts the current loop closed SSA form to a canonical form
1389 expected by the Graphite code generation.
1391 The loop closed SSA form has the following invariant: a variable
1392 defined in a loop that is used outside the loop appears only in the
1393 phi nodes in the destination of the loop exit. These phi nodes are
1394 called close phi nodes.
1396 The canonical loop closed SSA form contains the extra invariants:
1398 - when the loop contains only one exit, the close phi nodes contain
1399 only one argument. That implies that the basic block that contains
1400 the close phi nodes has only one predecessor, that is a basic block
1401 in the loop.
1403 - the basic block containing the close phi nodes does not contain
1404 other statements.
1406 - there exist only one phi node per definition in the loop.
1409 static void
1410 canonicalize_loop_closed_ssa_form (void)
1412 loop_p loop;
1414 #ifdef ENABLE_CHECKING
1415 verify_loop_closed_ssa (true);
1416 #endif
1418 FOR_EACH_LOOP (loop, 0)
1419 canonicalize_loop_closed_ssa (loop);
1421 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1422 update_ssa (TODO_update_ssa);
1424 #ifdef ENABLE_CHECKING
1425 verify_loop_closed_ssa (true);
1426 #endif
1429 /* Find Static Control Parts (SCoP) in the current function and pushes
1430 them to SCOPS. */
1432 void
1433 build_scops (vec<scop_p> *scops)
1435 struct loop *loop = current_loops->tree_root;
1436 auto_vec<sd_region, 3> regions;
1438 canonicalize_loop_closed_ssa_form ();
1439 build_scops_1 (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)),
1440 ENTRY_BLOCK_PTR_FOR_FN (cfun)->loop_father,
1441 &regions, loop);
1442 create_sese_edges (regions);
1443 build_graphite_scops (regions, scops);
1445 if (dump_file && (dump_flags & TDF_DETAILS))
1446 print_graphite_statistics (dump_file, *scops);
1448 limit_scops (scops);
1449 regions.release ();
1451 if (dump_file && (dump_flags & TDF_DETAILS))
1452 fprintf (dump_file, "\nnumber of SCoPs: %d\n",
1453 scops ? scops->length () : 0);
1456 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
1457 different colors. If there are not enough colors, paint the
1458 remaining SCoPs in gray.
1460 Special nodes:
1461 - "*" after the node number denotes the entry of a SCoP,
1462 - "#" after the node number denotes the exit of a SCoP,
1463 - "()" around the node number denotes the entry or the
1464 exit nodes of the SCOP. These are not part of SCoP. */
1466 static void
1467 dot_all_scops_1 (FILE *file, vec<scop_p> scops)
1469 basic_block bb;
1470 edge e;
1471 edge_iterator ei;
1472 scop_p scop;
1473 const char* color;
1474 int i;
1476 /* Disable debugging while printing graph. */
1477 int tmp_dump_flags = dump_flags;
1478 dump_flags = 0;
1480 fprintf (file, "digraph all {\n");
1482 FOR_ALL_BB_FN (bb, cfun)
1484 int part_of_scop = false;
1486 /* Use HTML for every bb label. So we are able to print bbs
1487 which are part of two different SCoPs, with two different
1488 background colors. */
1489 fprintf (file, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
1490 bb->index);
1491 fprintf (file, "CELLSPACING=\"0\">\n");
1493 /* Select color for SCoP. */
1494 FOR_EACH_VEC_ELT (scops, i, scop)
1496 sese region = SCOP_REGION (scop);
1497 if (bb_in_sese_p (bb, region)
1498 || (SESE_EXIT_BB (region) == bb)
1499 || (SESE_ENTRY_BB (region) == bb))
1501 switch (i % 17)
1503 case 0: /* red */
1504 color = "#e41a1c";
1505 break;
1506 case 1: /* blue */
1507 color = "#377eb8";
1508 break;
1509 case 2: /* green */
1510 color = "#4daf4a";
1511 break;
1512 case 3: /* purple */
1513 color = "#984ea3";
1514 break;
1515 case 4: /* orange */
1516 color = "#ff7f00";
1517 break;
1518 case 5: /* yellow */
1519 color = "#ffff33";
1520 break;
1521 case 6: /* brown */
1522 color = "#a65628";
1523 break;
1524 case 7: /* rose */
1525 color = "#f781bf";
1526 break;
1527 case 8:
1528 color = "#8dd3c7";
1529 break;
1530 case 9:
1531 color = "#ffffb3";
1532 break;
1533 case 10:
1534 color = "#bebada";
1535 break;
1536 case 11:
1537 color = "#fb8072";
1538 break;
1539 case 12:
1540 color = "#80b1d3";
1541 break;
1542 case 13:
1543 color = "#fdb462";
1544 break;
1545 case 14:
1546 color = "#b3de69";
1547 break;
1548 case 15:
1549 color = "#fccde5";
1550 break;
1551 case 16:
1552 color = "#bc80bd";
1553 break;
1554 default: /* gray */
1555 color = "#999999";
1558 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color);
1560 if (!bb_in_sese_p (bb, region))
1561 fprintf (file, " (");
1563 if (bb == SESE_ENTRY_BB (region)
1564 && bb == SESE_EXIT_BB (region))
1565 fprintf (file, " %d*# ", bb->index);
1566 else if (bb == SESE_ENTRY_BB (region))
1567 fprintf (file, " %d* ", bb->index);
1568 else if (bb == SESE_EXIT_BB (region))
1569 fprintf (file, " %d# ", bb->index);
1570 else
1571 fprintf (file, " %d ", bb->index);
1573 if (!bb_in_sese_p (bb,region))
1574 fprintf (file, ")");
1576 fprintf (file, "</TD></TR>\n");
1577 part_of_scop = true;
1581 if (!part_of_scop)
1583 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
1584 fprintf (file, " %d </TD></TR>\n", bb->index);
1586 fprintf (file, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
1589 FOR_ALL_BB_FN (bb, cfun)
1591 FOR_EACH_EDGE (e, ei, bb->succs)
1592 fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
1595 fputs ("}\n\n", file);
1597 /* Enable debugging again. */
1598 dump_flags = tmp_dump_flags;
1601 /* Display all SCoPs using dotty. */
1603 DEBUG_FUNCTION void
1604 dot_all_scops (vec<scop_p> scops)
1606 /* When debugging, enable the following code. This cannot be used
1607 in production compilers because it calls "system". */
1608 #if 0
1609 int x;
1610 FILE *stream = fopen ("/tmp/allscops.dot", "w");
1611 gcc_assert (stream);
1613 dot_all_scops_1 (stream, scops);
1614 fclose (stream);
1616 x = system ("dotty /tmp/allscops.dot &");
1617 #else
1618 dot_all_scops_1 (stderr, scops);
1619 #endif
1622 /* Display all SCoPs using dotty. */
1624 DEBUG_FUNCTION void
1625 dot_scop (scop_p scop)
1627 auto_vec<scop_p, 1> scops;
1629 if (scop)
1630 scops.safe_push (scop);
1632 /* When debugging, enable the following code. This cannot be used
1633 in production compilers because it calls "system". */
1634 #if 0
1636 int x;
1637 FILE *stream = fopen ("/tmp/allscops.dot", "w");
1638 gcc_assert (stream);
1640 dot_all_scops_1 (stream, scops);
1641 fclose (stream);
1642 x = system ("dotty /tmp/allscops.dot &");
1644 #else
1645 dot_all_scops_1 (stderr, scops);
1646 #endif
1649 #endif