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)
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/>. */
27 #include <isl/union_map.h>
29 #include <cloog/cloog.h>
30 #include <cloog/isl/domain.h>
35 #include "coretypes.h"
43 #include "hard-reg-set.h"
46 #include "dominance.h"
48 #include "basic-block.h"
49 #include "tree-ssa-alias.h"
50 #include "internal-fn.h"
51 #include "gimple-expr.h"
54 #include "gimple-iterator.h"
55 #include "gimple-ssa.h"
56 #include "tree-phinodes.h"
57 #include "ssa-iterators.h"
58 #include "tree-ssa-loop-manip.h"
59 #include "tree-ssa-loop-niter.h"
60 #include "tree-ssa-loop.h"
61 #include "tree-into-ssa.h"
64 #include "tree-chrec.h"
65 #include "tree-data-ref.h"
66 #include "tree-scalar-evolution.h"
67 #include "tree-pass.h"
69 #include "tree-ssa-propagate.h"
70 #include "cp/cp-tree.h"
73 #include "graphite-poly.h"
74 #include "graphite-scop-detection.h"
76 /* Forward declarations. */
77 static void make_close_phi_nodes_unique (basic_block
);
79 /* The type of the analyzed basic block. */
81 typedef enum gbb_type
{
83 GBB_LOOP_SING_EXIT_HEADER
,
84 GBB_LOOP_MULT_EXIT_HEADER
,
91 /* Detect the type of BB. Loop headers are only marked, if they are
92 new. This means their loop_father is different to LAST_LOOP.
93 Otherwise they are treated like any other bb and their type can be
97 get_bb_type (basic_block bb
, struct loop
*last_loop
)
101 struct loop
*loop
= bb
->loop_father
;
103 /* Check, if we entry into a new loop. */
104 if (loop
!= last_loop
)
106 if (single_exit (loop
) != NULL
)
107 return GBB_LOOP_SING_EXIT_HEADER
;
108 else if (loop
->num
!= 0)
109 return GBB_LOOP_MULT_EXIT_HEADER
;
111 return GBB_COND_HEADER
;
114 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
115 nb_dom
= dom
.length ();
121 if (nb_dom
== 1 && single_succ_p (bb
))
124 return GBB_COND_HEADER
;
127 /* A SCoP detection region, defined using bbs as borders.
129 All control flow touching this region, comes in passing basic_block
130 ENTRY and leaves passing basic_block EXIT. By using bbs instead of
131 edges for the borders we are able to represent also regions that do
132 not have a single entry or exit edge.
134 But as they have a single entry basic_block and a single exit
135 basic_block, we are able to generate for every sd_region a single
143 / \ This region contains: {3, 4, 5, 6, 7, 8}
151 typedef struct sd_region_p
153 /* The entry bb dominates all bbs in the sd_region. It is part of
157 /* The exit bb postdominates all bbs in the sd_region, but is not
158 part of the region. */
164 /* Moves the scops from SOURCE to TARGET and clean up SOURCE. */
167 move_sd_regions (vec
<sd_region
> *source
, vec
<sd_region
> *target
)
172 FOR_EACH_VEC_ELT (*source
, i
, s
)
173 target
->safe_push (*s
);
178 /* Something like "n * m" is not allowed. */
181 graphite_can_represent_init (tree e
)
183 switch (TREE_CODE (e
))
185 case POLYNOMIAL_CHREC
:
186 return graphite_can_represent_init (CHREC_LEFT (e
))
187 && graphite_can_represent_init (CHREC_RIGHT (e
));
190 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
191 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
192 && tree_fits_shwi_p (TREE_OPERAND (e
, 1));
194 return graphite_can_represent_init (TREE_OPERAND (e
, 1))
195 && tree_fits_shwi_p (TREE_OPERAND (e
, 0));
198 case POINTER_PLUS_EXPR
:
200 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
201 && graphite_can_represent_init (TREE_OPERAND (e
, 1));
206 case NON_LVALUE_EXPR
:
207 return graphite_can_represent_init (TREE_OPERAND (e
, 0));
216 /* Return true when SCEV can be represented in the polyhedral model.
218 An expression can be represented, if it can be expressed as an
219 affine expression. For loops (i, j) and parameters (m, n) all
220 affine expressions are of the form:
222 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
224 1 i + 20 j + (-2) m + 25
226 Something like "i * n" or "n * m" is not allowed. */
229 graphite_can_represent_scev (tree scev
)
231 if (chrec_contains_undetermined (scev
))
234 /* We disable the handling of pointer types, because it’s currently not
235 supported by Graphite with the ISL AST generator. SSA_NAME nodes are
236 the only nodes, which are disabled in case they are pointers to object
237 types, but this can be changed. */
239 if (TYPE_PTROB_P (TREE_TYPE (scev
)) && TREE_CODE (scev
) == SSA_NAME
)
242 switch (TREE_CODE (scev
))
247 case NON_LVALUE_EXPR
:
248 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0));
251 case POINTER_PLUS_EXPR
:
253 return graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
254 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
257 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 0)))
258 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 1)))
259 && !(chrec_contains_symbols (TREE_OPERAND (scev
, 0))
260 && chrec_contains_symbols (TREE_OPERAND (scev
, 1)))
261 && graphite_can_represent_init (scev
)
262 && graphite_can_represent_scev (TREE_OPERAND (scev
, 0))
263 && graphite_can_represent_scev (TREE_OPERAND (scev
, 1));
265 case POLYNOMIAL_CHREC
:
266 /* Check for constant strides. With a non constant stride of
267 'n' we would have a value of 'iv * n'. Also check that the
268 initial value can represented: for example 'n * m' cannot be
270 if (!evolution_function_right_is_integer_cst (scev
)
271 || !graphite_can_represent_init (scev
))
273 return graphite_can_represent_scev (CHREC_LEFT (scev
));
279 /* Only affine functions can be represented. */
280 if (tree_contains_chrecs (scev
, NULL
)
281 || !scev_is_linear_expression (scev
))
288 /* Return true when EXPR can be represented in the polyhedral model.
290 This means an expression can be represented, if it is linear with
291 respect to the loops and the strides are non parametric.
292 LOOP is the place where the expr will be evaluated. SCOP_ENTRY defines the
293 entry of the region we analyse. */
296 graphite_can_represent_expr (basic_block scop_entry
, loop_p loop
,
299 tree scev
= analyze_scalar_evolution (loop
, expr
);
301 scev
= instantiate_scev (scop_entry
, loop
, scev
);
303 return graphite_can_represent_scev (scev
);
306 /* Return true if the data references of STMT can be represented by
310 stmt_has_simple_data_refs_p (loop_p outermost_loop ATTRIBUTE_UNUSED
,
317 vec
<data_reference_p
> drs
= vNULL
;
320 for (outer
= loop_containing_stmt (stmt
); outer
; outer
= loop_outer (outer
))
322 graphite_find_data_references_in_stmt (outer
,
323 loop_containing_stmt (stmt
),
326 FOR_EACH_VEC_ELT (drs
, j
, dr
)
327 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
328 if (!graphite_can_represent_scev (DR_ACCESS_FN (dr
, i
)))
334 free_data_refs (drs
);
339 free_data_refs (drs
);
343 /* Return true only when STMT is simple enough for being handled by
344 Graphite. This depends on SCOP_ENTRY, as the parameters are
345 initialized relatively to this basic block, the linear functions
346 are initialized to OUTERMOST_LOOP and BB is the place where we try
347 to evaluate the STMT. */
350 stmt_simple_for_scop_p (basic_block scop_entry
, loop_p outermost_loop
,
351 gimple stmt
, basic_block bb
)
353 loop_p loop
= bb
->loop_father
;
355 gcc_assert (scop_entry
);
357 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
358 Calls have side-effects, except those to const or pure
360 if (gimple_has_volatile_ops (stmt
)
361 || (gimple_code (stmt
) == GIMPLE_CALL
362 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
363 || (gimple_code (stmt
) == GIMPLE_ASM
))
366 if (is_gimple_debug (stmt
))
369 if (!stmt_has_simple_data_refs_p (outermost_loop
, stmt
))
372 switch (gimple_code (stmt
))
380 /* We can handle all binary comparisons. Inequalities are
381 also supported as they can be represented with union of
383 enum tree_code code
= gimple_cond_code (stmt
);
384 if (!(code
== LT_EXPR
392 for (unsigned i
= 0; i
< 2; ++i
)
394 tree op
= gimple_op (stmt
, i
);
395 if (!graphite_can_represent_expr (scop_entry
, loop
, op
)
396 /* We can not handle REAL_TYPE. Failed for pr39260. */
397 || TREE_CODE (TREE_TYPE (op
)) == REAL_TYPE
)
409 /* These nodes cut a new scope. */
416 /* Returns the statement of BB that contains a harmful operation: that
417 can be a function call with side effects, the induction variables
418 are not linear with respect to SCOP_ENTRY, etc. The current open
419 scop should end before this statement. The evaluation is limited using
420 OUTERMOST_LOOP as outermost loop that may change. */
423 harmful_stmt_in_bb (basic_block scop_entry
, loop_p outer_loop
, basic_block bb
)
425 gimple_stmt_iterator gsi
;
427 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
428 if (!stmt_simple_for_scop_p (scop_entry
, outer_loop
, gsi_stmt (gsi
), bb
))
429 return gsi_stmt (gsi
);
434 /* Return true if LOOP can be represented in the polyhedral
435 representation. This is evaluated taking SCOP_ENTRY and
436 OUTERMOST_LOOP in mind. */
439 graphite_can_represent_loop (basic_block scop_entry
, loop_p loop
)
442 struct tree_niter_desc niter_desc
;
444 /* FIXME: For the moment, graphite cannot be used on loops that
445 iterate using induction variables that wrap. */
447 return number_of_iterations_exit (loop
, single_exit (loop
), &niter_desc
, false)
448 && niter_desc
.control
.no_overflow
449 && (niter
= number_of_latch_executions (loop
))
450 && !chrec_contains_undetermined (niter
)
451 && graphite_can_represent_expr (scop_entry
, loop
, niter
);
454 /* Store information needed by scopdet_* functions. */
458 /* Exit of the open scop would stop if the current BB is harmful. */
461 /* Where the next scop would start if the current BB is harmful. */
464 /* The bb or one of its children contains open loop exits. That means
465 loop exit nodes that are not surrounded by a loop dominated by bb. */
468 /* The bb or one of its children contains only structures we can handle. */
472 static struct scopdet_info
build_scops_1 (basic_block
, loop_p
,
473 vec
<sd_region
> *, loop_p
);
475 /* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB
476 to SCOPS. TYPE is the gbb_type of BB. */
478 static struct scopdet_info
479 scopdet_basic_block_info (basic_block bb
, loop_p outermost_loop
,
480 vec
<sd_region
> *scops
, gbb_type type
)
482 loop_p loop
= bb
->loop_father
;
483 struct scopdet_info result
;
486 /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps. */
487 basic_block entry_block
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
488 stmt
= harmful_stmt_in_bb (entry_block
, outermost_loop
, bb
);
489 result
.difficult
= (stmt
!= NULL
);
496 result
.exits
= false;
498 /* Mark bbs terminating a SESE region difficult, if they start
499 a condition or if the block it exits to cannot be split
500 with make_forwarder_block. */
501 if (!single_succ_p (bb
)
502 || bb_has_abnormal_pred (single_succ (bb
)))
503 result
.difficult
= true;
505 result
.exit
= single_succ (bb
);
510 result
.next
= single_succ (bb
);
511 result
.exits
= false;
512 result
.exit
= single_succ (bb
);
515 case GBB_LOOP_SING_EXIT_HEADER
:
517 auto_vec
<sd_region
, 3> regions
;
518 struct scopdet_info sinfo
;
519 edge exit_e
= single_exit (loop
);
521 sinfo
= build_scops_1 (bb
, outermost_loop
, ®ions
, loop
);
523 if (!graphite_can_represent_loop (entry_block
, loop
))
524 result
.difficult
= true;
526 result
.difficult
|= sinfo
.difficult
;
528 /* Try again with another loop level. */
530 && loop_depth (outermost_loop
) + 1 == loop_depth (loop
))
532 outermost_loop
= loop
;
537 sinfo
= scopdet_basic_block_info (bb
, outermost_loop
, scops
, type
);
540 result
.difficult
= true;
543 move_sd_regions (®ions
, scops
);
547 open_scop
.entry
= bb
;
548 open_scop
.exit
= exit_e
->dest
;
549 scops
->safe_push (open_scop
);
555 result
.exit
= exit_e
->dest
;
556 result
.next
= exit_e
->dest
;
558 /* If we do not dominate result.next, remove it. It's either
559 the exit block, or another bb dominates it and will
560 call the scop detection for this bb. */
561 if (!dominated_by_p (CDI_DOMINATORS
, result
.next
, bb
))
564 if (exit_e
->src
->loop_father
!= loop
)
567 result
.exits
= false;
569 if (result
.difficult
)
570 move_sd_regions (®ions
, scops
);
578 case GBB_LOOP_MULT_EXIT_HEADER
:
580 /* XXX: For now we just do not join loops with multiple exits. If the
581 exits lead to the same bb it may be possible to join the loop. */
582 auto_vec
<sd_region
, 3> regions
;
583 vec
<edge
> exits
= get_loop_exit_edges (loop
);
586 build_scops_1 (bb
, loop
, ®ions
, loop
);
588 /* Scan the code dominated by this loop. This means all bbs, that are
589 are dominated by a bb in this loop, but are not part of this loop.
592 - The loop exit destination is dominated by the exit sources.
594 TODO: We miss here the more complex cases:
595 - The exit destinations are dominated by another bb inside
597 - The loop dominates bbs, that are not exit destinations. */
598 FOR_EACH_VEC_ELT (exits
, i
, e
)
599 if (e
->src
->loop_father
== loop
600 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
))
602 if (loop_outer (outermost_loop
))
603 outermost_loop
= loop_outer (outermost_loop
);
605 /* Pass loop_outer to recognize e->dest as loop header in
607 if (e
->dest
->loop_father
->header
== e
->dest
)
608 build_scops_1 (e
->dest
, outermost_loop
, ®ions
,
609 loop_outer (e
->dest
->loop_father
));
611 build_scops_1 (e
->dest
, outermost_loop
, ®ions
,
612 e
->dest
->loop_father
);
617 result
.difficult
= true;
618 result
.exits
= false;
619 move_sd_regions (®ions
, scops
);
623 case GBB_COND_HEADER
:
625 auto_vec
<sd_region
, 3> regions
;
626 struct scopdet_info sinfo
;
627 vec
<basic_block
> dominated
;
630 basic_block last_exit
= NULL
;
632 result
.exits
= false;
634 /* First check the successors of BB, and check if it is
635 possible to join the different branches. */
636 FOR_EACH_VEC_SAFE_ELT (bb
->succs
, i
, e
)
638 /* Ignore loop exits. They will be handled after the loop
640 if (loop_exits_to_bb_p (loop
, e
->dest
))
646 /* Do not follow edges that lead to the end of the
647 conditions block. For example, in
657 the edge from 0 => 6. Only check if all paths lead to
660 if (!single_pred_p (e
->dest
))
662 /* Check, if edge leads directly to the end of this
667 if (e
->dest
!= last_exit
)
668 result
.difficult
= true;
673 if (!dominated_by_p (CDI_DOMINATORS
, e
->dest
, bb
))
675 result
.difficult
= true;
679 sinfo
= build_scops_1 (e
->dest
, outermost_loop
, ®ions
, loop
);
681 result
.exits
|= sinfo
.exits
;
682 result
.difficult
|= sinfo
.difficult
;
684 /* Checks, if all branches end at the same point.
685 If that is true, the condition stays joinable.
686 Have a look at the example above. */
690 last_exit
= sinfo
.exit
;
692 if (sinfo
.exit
!= last_exit
)
693 result
.difficult
= true;
696 result
.difficult
= true;
700 result
.difficult
= true;
702 /* Join the branches of the condition if possible. */
703 if (!result
.exits
&& !result
.difficult
)
705 /* Only return a next pointer if we dominate this pointer.
706 Otherwise it will be handled by the bb dominating it. */
707 if (dominated_by_p (CDI_DOMINATORS
, last_exit
, bb
)
709 result
.next
= last_exit
;
713 result
.exit
= last_exit
;
719 /* Scan remaining bbs dominated by BB. */
720 dominated
= get_dominated_by (CDI_DOMINATORS
, bb
);
722 FOR_EACH_VEC_ELT (dominated
, i
, dom_bb
)
724 /* Ignore loop exits: they will be handled after the loop body. */
725 if (loop_depth (find_common_loop (loop
, dom_bb
->loop_father
))
732 /* Ignore the bbs processed above. */
733 if (single_pred_p (dom_bb
) && single_pred (dom_bb
) == bb
)
736 if (loop_depth (loop
) > loop_depth (dom_bb
->loop_father
))
737 sinfo
= build_scops_1 (dom_bb
, outermost_loop
, ®ions
,
740 sinfo
= build_scops_1 (dom_bb
, outermost_loop
, ®ions
, loop
);
742 result
.exits
|= sinfo
.exits
;
743 result
.difficult
= true;
747 dominated
.release ();
750 move_sd_regions (®ions
, scops
);
762 /* Starting from CURRENT we walk the dominance tree and add new sd_regions to
763 SCOPS. The analyse if a sd_region can be handled is based on the value
764 of OUTERMOST_LOOP. Only loops inside OUTERMOST loops may change. LOOP
765 is the loop in which CURRENT is handled.
767 TODO: These functions got a little bit big. They definitely should be cleaned
770 static struct scopdet_info
771 build_scops_1 (basic_block current
, loop_p outermost_loop
,
772 vec
<sd_region
> *scops
, loop_p loop
)
774 bool in_scop
= false;
776 struct scopdet_info sinfo
;
778 /* Initialize result. */
779 struct scopdet_info result
;
780 result
.exits
= false;
781 result
.difficult
= false;
784 open_scop
.entry
= NULL
;
785 open_scop
.exit
= NULL
;
788 /* Loop over the dominance tree. If we meet a difficult bb, close
789 the current SCoP. Loop and condition header start a new layer,
790 and can only be added if all bbs in deeper layers are simple. */
791 while (current
!= NULL
)
793 sinfo
= scopdet_basic_block_info (current
, outermost_loop
, scops
,
794 get_bb_type (current
, loop
));
796 if (!in_scop
&& !(sinfo
.exits
|| sinfo
.difficult
))
798 open_scop
.entry
= current
;
799 open_scop
.exit
= NULL
;
802 else if (in_scop
&& (sinfo
.exits
|| sinfo
.difficult
))
804 open_scop
.exit
= current
;
805 scops
->safe_push (open_scop
);
809 result
.difficult
|= sinfo
.difficult
;
810 result
.exits
|= sinfo
.exits
;
812 current
= sinfo
.next
;
815 /* Try to close open_scop, if we are still in an open SCoP. */
818 open_scop
.exit
= sinfo
.exit
;
819 gcc_assert (open_scop
.exit
);
820 scops
->safe_push (open_scop
);
823 result
.exit
= sinfo
.exit
;
827 /* Checks if a bb is contained in REGION. */
830 bb_in_sd_region (basic_block bb
, sd_region
*region
)
832 return bb_in_region (bb
, region
->entry
, region
->exit
);
835 /* Returns the single entry edge of REGION, if it does not exits NULL. */
838 find_single_entry_edge (sd_region
*region
)
844 FOR_EACH_EDGE (e
, ei
, region
->entry
->preds
)
845 if (!bb_in_sd_region (e
->src
, region
))
860 /* Returns the single exit edge of REGION, if it does not exits NULL. */
863 find_single_exit_edge (sd_region
*region
)
869 FOR_EACH_EDGE (e
, ei
, region
->exit
->preds
)
870 if (bb_in_sd_region (e
->src
, region
))
885 /* Create a single entry edge for REGION. */
888 create_single_entry_edge (sd_region
*region
)
890 if (find_single_entry_edge (region
))
893 /* There are multiple predecessors for bb_3
906 There are two edges (1->3, 2->3), that point from outside into the region,
907 and another one (5->3), a loop latch, lead to bb_3.
915 | |\ (3.0 -> 3.1) = single entry edge
924 If the loop is part of the SCoP, we have to redirect the loop latches.
930 | | (3.0 -> 3.1) = entry edge
939 if (region
->entry
->loop_father
->header
!= region
->entry
940 || dominated_by_p (CDI_DOMINATORS
,
941 loop_latch_edge (region
->entry
->loop_father
)->src
,
944 edge forwarder
= split_block_after_labels (region
->entry
);
945 region
->entry
= forwarder
->dest
;
948 /* This case is never executed, as the loop headers seem always to have a
949 single edge pointing from outside into the loop. */
952 gcc_checking_assert (find_single_entry_edge (region
));
955 /* Check if the sd_region, mentioned in EDGE, has no exit bb. */
958 sd_region_without_exit (edge e
)
960 sd_region
*r
= (sd_region
*) e
->aux
;
963 return r
->exit
== NULL
;
968 /* Create a single exit edge for REGION. */
971 create_single_exit_edge (sd_region
*region
)
975 edge forwarder
= NULL
;
978 /* We create a forwarder bb (5) for all edges leaving this region
979 (3->5, 4->5). All other edges leading to the same bb, are moved
980 to a new bb (6). If these edges where part of another region (2->5)
981 we update the region->exit pointer, of this region.
983 To identify which edge belongs to which region we depend on the e->aux
984 pointer in every edge. It points to the region of the edge or to NULL,
985 if the edge is not part of any region.
987 1 2 3 4 1->5 no region, 2->5 region->exit = 5,
988 \| |/ 3->5 region->exit = NULL, 4->5 region->exit = NULL
993 1 2 3 4 1->6 no region, 2->6 region->exit = 6,
994 | | \/ 3->5 no region, 4->5 no region,
996 \| / 5->6 region->exit = 6
999 Now there is only a single exit edge (5->6). */
1000 exit
= region
->exit
;
1001 region
->exit
= NULL
;
1002 forwarder
= make_forwarder_block (exit
, &sd_region_without_exit
, NULL
);
1004 /* Unmark the edges, that are no longer exit edges. */
1005 FOR_EACH_EDGE (e
, ei
, forwarder
->src
->preds
)
1009 /* Mark the new exit edge. */
1010 single_succ_edge (forwarder
->src
)->aux
= region
;
1012 /* Update the exit bb of all regions, where exit edges lead to
1014 FOR_EACH_EDGE (e
, ei
, forwarder
->dest
->preds
)
1016 ((sd_region
*) e
->aux
)->exit
= forwarder
->dest
;
1018 gcc_checking_assert (find_single_exit_edge (region
));
1021 /* Unmark the exit edges of all REGIONS.
1022 See comment in "create_single_exit_edge". */
1025 unmark_exit_edges (vec
<sd_region
> regions
)
1032 FOR_EACH_VEC_ELT (regions
, i
, s
)
1033 FOR_EACH_EDGE (e
, ei
, s
->exit
->preds
)
1038 /* Mark the exit edges of all REGIONS.
1039 See comment in "create_single_exit_edge". */
1042 mark_exit_edges (vec
<sd_region
> regions
)
1049 FOR_EACH_VEC_ELT (regions
, i
, s
)
1050 FOR_EACH_EDGE (e
, ei
, s
->exit
->preds
)
1051 if (bb_in_sd_region (e
->src
, s
))
1055 /* Create for all scop regions a single entry and a single exit edge. */
1058 create_sese_edges (vec
<sd_region
> regions
)
1063 FOR_EACH_VEC_ELT (regions
, i
, s
)
1064 create_single_entry_edge (s
);
1066 mark_exit_edges (regions
);
1068 FOR_EACH_VEC_ELT (regions
, i
, s
)
1069 /* Don't handle multiple edges exiting the function. */
1070 if (!find_single_exit_edge (s
)
1071 && s
->exit
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1072 create_single_exit_edge (s
);
1074 unmark_exit_edges (regions
);
1076 calculate_dominance_info (CDI_DOMINATORS
);
1077 fix_loop_structure (NULL
);
1079 #ifdef ENABLE_CHECKING
1080 verify_loop_structure ();
1081 verify_ssa (false, true);
1085 /* Create graphite SCoPs from an array of scop detection REGIONS. */
1088 build_graphite_scops (vec
<sd_region
> regions
,
1094 FOR_EACH_VEC_ELT (regions
, i
, s
)
1096 edge entry
= find_single_entry_edge (s
);
1097 edge exit
= find_single_exit_edge (s
);
1103 scop
= new_scop (new_sese (entry
, exit
));
1104 scops
->safe_push (scop
);
1106 /* Are there overlapping SCoPs? */
1107 #ifdef ENABLE_CHECKING
1112 FOR_EACH_VEC_ELT (regions
, j
, s2
)
1114 gcc_assert (!bb_in_sd_region (s
->entry
, s2
));
1120 /* Returns true when BB contains only close phi nodes. */
1123 contains_only_close_phi_nodes (basic_block bb
)
1125 gimple_stmt_iterator gsi
;
1127 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1128 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_LABEL
)
1134 /* Print statistics for SCOP to FILE. */
1137 print_graphite_scop_statistics (FILE* file
, scop_p scop
)
1142 long n_conditions
= 0;
1146 long n_p_conditions
= 0;
1150 FOR_ALL_BB_FN (bb
, cfun
)
1152 gimple_stmt_iterator psi
;
1153 loop_p loop
= bb
->loop_father
;
1155 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
1159 n_p_bbs
+= bb
->count
;
1161 if (EDGE_COUNT (bb
->succs
) > 1)
1164 n_p_conditions
+= bb
->count
;
1167 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1170 n_p_stmts
+= bb
->count
;
1173 if (loop
->header
== bb
&& loop_in_sese_p (loop
, SCOP_REGION (scop
)))
1176 n_p_loops
+= bb
->count
;
1181 fprintf (file
, "\nBefore limit_scops SCoP statistics (");
1182 fprintf (file
, "BBS:%ld, ", n_bbs
);
1183 fprintf (file
, "LOOPS:%ld, ", n_loops
);
1184 fprintf (file
, "CONDITIONS:%ld, ", n_conditions
);
1185 fprintf (file
, "STMTS:%ld)\n", n_stmts
);
1186 fprintf (file
, "\nBefore limit_scops SCoP profiling statistics (");
1187 fprintf (file
, "BBS:%ld, ", n_p_bbs
);
1188 fprintf (file
, "LOOPS:%ld, ", n_p_loops
);
1189 fprintf (file
, "CONDITIONS:%ld, ", n_p_conditions
);
1190 fprintf (file
, "STMTS:%ld)\n", n_p_stmts
);
1193 /* Print statistics for SCOPS to FILE. */
1196 print_graphite_statistics (FILE* file
, vec
<scop_p
> scops
)
1201 FOR_EACH_VEC_ELT (scops
, i
, scop
)
1202 print_graphite_scop_statistics (file
, scop
);
1205 /* We limit all SCoPs to SCoPs, that are completely surrounded by a loop.
1215 * SCoP frontier, as this line is not surrounded by any loop. *
1219 This is necessary as scalar evolution and parameter detection need a
1220 outermost loop to initialize parameters correctly.
1222 TODO: FIX scalar evolution and parameter detection to allow more flexible
1226 limit_scops (vec
<scop_p
> *scops
)
1228 auto_vec
<sd_region
, 3> regions
;
1233 FOR_EACH_VEC_ELT (*scops
, i
, scop
)
1237 sese region
= SCOP_REGION (scop
);
1238 build_sese_loop_nests (region
);
1240 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), j
, loop
)
1241 if (!loop_in_sese_p (loop_outer (loop
), region
)
1242 && single_exit (loop
))
1244 sd_region open_scop
;
1245 open_scop
.entry
= loop
->header
;
1246 open_scop
.exit
= single_exit (loop
)->dest
;
1248 /* This is a hack on top of the limit_scops hack. The
1249 limit_scops hack should disappear all together. */
1250 if (single_succ_p (open_scop
.exit
)
1251 && contains_only_close_phi_nodes (open_scop
.exit
))
1252 open_scop
.exit
= single_succ_edge (open_scop
.exit
)->dest
;
1254 regions
.safe_push (open_scop
);
1258 free_scops (*scops
);
1261 create_sese_edges (regions
);
1262 build_graphite_scops (regions
, scops
);
1265 /* Returns true when P1 and P2 are close phis with the same
1269 same_close_phi_node (gimple p1
, gimple p2
)
1271 return operand_equal_p (gimple_phi_arg_def (p1
, 0),
1272 gimple_phi_arg_def (p2
, 0), 0);
1275 /* Remove the close phi node at GSI and replace its rhs with the rhs
1279 remove_duplicate_close_phi (gimple phi
, gimple_stmt_iterator
*gsi
)
1282 use_operand_p use_p
;
1283 imm_use_iterator imm_iter
;
1284 tree res
= gimple_phi_result (phi
);
1285 tree def
= gimple_phi_result (gsi_stmt (*gsi
));
1287 gcc_assert (same_close_phi_node (phi
, gsi_stmt (*gsi
)));
1289 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1291 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
1292 SET_USE (use_p
, res
);
1294 update_stmt (use_stmt
);
1296 /* It is possible that we just created a duplicate close-phi
1297 for an already-processed containing loop. Check for this
1298 case and clean it up. */
1299 if (gimple_code (use_stmt
) == GIMPLE_PHI
1300 && gimple_phi_num_args (use_stmt
) == 1)
1301 make_close_phi_nodes_unique (gimple_bb (use_stmt
));
1304 remove_phi_node (gsi
, true);
1307 /* Removes all the close phi duplicates from BB. */
1310 make_close_phi_nodes_unique (basic_block bb
)
1312 gimple_stmt_iterator psi
;
1314 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1316 gimple_stmt_iterator gsi
= psi
;
1317 gimple phi
= gsi_stmt (psi
);
1319 /* At this point, PHI should be a close phi in normal form. */
1320 gcc_assert (gimple_phi_num_args (phi
) == 1);
1322 /* Iterate over the next phis and remove duplicates. */
1324 while (!gsi_end_p (gsi
))
1325 if (same_close_phi_node (phi
, gsi_stmt (gsi
)))
1326 remove_duplicate_close_phi (phi
, &gsi
);
1332 /* Transforms LOOP to the canonical loop closed SSA form. */
1335 canonicalize_loop_closed_ssa (loop_p loop
)
1337 edge e
= single_exit (loop
);
1340 if (!e
|| e
->flags
& EDGE_ABNORMAL
)
1345 if (single_pred_p (bb
))
1347 e
= split_block_after_labels (bb
);
1348 make_close_phi_nodes_unique (e
->src
);
1352 gimple_stmt_iterator psi
;
1353 basic_block close
= split_edge (e
);
1355 e
= single_succ_edge (close
);
1357 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1359 gimple phi
= gsi_stmt (psi
);
1362 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1363 if (gimple_phi_arg_edge (phi
, i
) == e
)
1365 tree res
, arg
= gimple_phi_arg_def (phi
, i
);
1366 use_operand_p use_p
;
1369 if (TREE_CODE (arg
) != SSA_NAME
)
1372 close_phi
= create_phi_node (NULL_TREE
, close
);
1373 res
= create_new_def_for (arg
, close_phi
,
1374 gimple_phi_result_ptr (close_phi
));
1375 add_phi_arg (close_phi
, arg
,
1376 gimple_phi_arg_edge (close_phi
, 0),
1378 use_p
= gimple_phi_arg_imm_use_ptr (phi
, i
);
1379 replace_exp (use_p
, res
);
1384 make_close_phi_nodes_unique (close
);
1387 /* The code above does not properly handle changes in the post dominance
1388 information (yet). */
1389 free_dominance_info (CDI_POST_DOMINATORS
);
1392 /* Converts the current loop closed SSA form to a canonical form
1393 expected by the Graphite code generation.
1395 The loop closed SSA form has the following invariant: a variable
1396 defined in a loop that is used outside the loop appears only in the
1397 phi nodes in the destination of the loop exit. These phi nodes are
1398 called close phi nodes.
1400 The canonical loop closed SSA form contains the extra invariants:
1402 - when the loop contains only one exit, the close phi nodes contain
1403 only one argument. That implies that the basic block that contains
1404 the close phi nodes has only one predecessor, that is a basic block
1407 - the basic block containing the close phi nodes does not contain
1410 - there exist only one phi node per definition in the loop.
1414 canonicalize_loop_closed_ssa_form (void)
1418 #ifdef ENABLE_CHECKING
1419 verify_loop_closed_ssa (true);
1422 FOR_EACH_LOOP (loop
, 0)
1423 canonicalize_loop_closed_ssa (loop
);
1425 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1426 update_ssa (TODO_update_ssa
);
1428 #ifdef ENABLE_CHECKING
1429 verify_loop_closed_ssa (true);
1433 /* Find Static Control Parts (SCoP) in the current function and pushes
1437 build_scops (vec
<scop_p
> *scops
)
1439 struct loop
*loop
= current_loops
->tree_root
;
1440 auto_vec
<sd_region
, 3> regions
;
1442 canonicalize_loop_closed_ssa_form ();
1443 build_scops_1 (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
)),
1444 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->loop_father
,
1446 create_sese_edges (regions
);
1447 build_graphite_scops (regions
, scops
);
1449 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1450 print_graphite_statistics (dump_file
, *scops
);
1452 limit_scops (scops
);
1455 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1456 fprintf (dump_file
, "\nnumber of SCoPs: %d\n",
1457 scops
? scops
->length () : 0);
1460 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
1461 different colors. If there are not enough colors, paint the
1462 remaining SCoPs in gray.
1465 - "*" after the node number denotes the entry of a SCoP,
1466 - "#" after the node number denotes the exit of a SCoP,
1467 - "()" around the node number denotes the entry or the
1468 exit nodes of the SCOP. These are not part of SCoP. */
1471 dot_all_scops_1 (FILE *file
, vec
<scop_p
> scops
)
1480 /* Disable debugging while printing graph. */
1481 int tmp_dump_flags
= dump_flags
;
1484 fprintf (file
, "digraph all {\n");
1486 FOR_ALL_BB_FN (bb
, cfun
)
1488 int part_of_scop
= false;
1490 /* Use HTML for every bb label. So we are able to print bbs
1491 which are part of two different SCoPs, with two different
1492 background colors. */
1493 fprintf (file
, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
1495 fprintf (file
, "CELLSPACING=\"0\">\n");
1497 /* Select color for SCoP. */
1498 FOR_EACH_VEC_ELT (scops
, i
, scop
)
1500 sese region
= SCOP_REGION (scop
);
1501 if (bb_in_sese_p (bb
, region
)
1502 || (SESE_EXIT_BB (region
) == bb
)
1503 || (SESE_ENTRY_BB (region
) == bb
))
1516 case 3: /* purple */
1519 case 4: /* orange */
1522 case 5: /* yellow */
1562 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color
);
1564 if (!bb_in_sese_p (bb
, region
))
1565 fprintf (file
, " (");
1567 if (bb
== SESE_ENTRY_BB (region
)
1568 && bb
== SESE_EXIT_BB (region
))
1569 fprintf (file
, " %d*# ", bb
->index
);
1570 else if (bb
== SESE_ENTRY_BB (region
))
1571 fprintf (file
, " %d* ", bb
->index
);
1572 else if (bb
== SESE_EXIT_BB (region
))
1573 fprintf (file
, " %d# ", bb
->index
);
1575 fprintf (file
, " %d ", bb
->index
);
1577 if (!bb_in_sese_p (bb
,region
))
1578 fprintf (file
, ")");
1580 fprintf (file
, "</TD></TR>\n");
1581 part_of_scop
= true;
1587 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
1588 fprintf (file
, " %d </TD></TR>\n", bb
->index
);
1590 fprintf (file
, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
1593 FOR_ALL_BB_FN (bb
, cfun
)
1595 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1596 fprintf (file
, "%d -> %d;\n", bb
->index
, e
->dest
->index
);
1599 fputs ("}\n\n", file
);
1601 /* Enable debugging again. */
1602 dump_flags
= tmp_dump_flags
;
1605 /* Display all SCoPs using dotty. */
1608 dot_all_scops (vec
<scop_p
> scops
)
1610 /* When debugging, enable the following code. This cannot be used
1611 in production compilers because it calls "system". */
1614 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
1615 gcc_assert (stream
);
1617 dot_all_scops_1 (stream
, scops
);
1620 x
= system ("dotty /tmp/allscops.dot &");
1622 dot_all_scops_1 (stderr
, scops
);
1626 /* Display all SCoPs using dotty. */
1629 dot_scop (scop_p scop
)
1631 auto_vec
<scop_p
, 1> scops
;
1634 scops
.safe_push (scop
);
1636 /* When debugging, enable the following code. This cannot be used
1637 in production compilers because it calls "system". */
1641 FILE *stream
= fopen ("/tmp/allscops.dot", "w");
1642 gcc_assert (stream
);
1644 dot_all_scops_1 (stream
, scops
);
1646 x
= system ("dotty /tmp/allscops.dot &");
1649 dot_all_scops_1 (stderr
, scops
);