1 /* Conversion of SESE regions to Polyhedra.
2 Copyright (C) 2009-2015 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@amd.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
24 /* Workaround for GMP 5.1.3 bug, see PR56019. */
27 #include <isl/constraint.h>
30 #include <isl/union_map.h>
31 #include <isl/constraint.h>
35 /* Since ISL-0.13, the extern is in val_gmp.h. */
36 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
39 #include <isl/val_gmp.h>
40 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
45 #include "coretypes.h"
52 #include "fold-const.h"
53 #include "gimple-iterator.h"
55 #include "gimplify-me.h"
57 #include "tree-ssa-loop-manip.h"
58 #include "tree-ssa-loop-niter.h"
59 #include "tree-ssa-loop.h"
60 #include "tree-into-ssa.h"
61 #include "tree-pass.h"
63 #include "tree-data-ref.h"
64 #include "tree-scalar-evolution.h"
66 #include "graphite-poly.h"
67 #include "tree-ssa-propagate.h"
68 #include "graphite-sese-to-poly.h"
71 /* Assigns to RES the value of the INTEGER_CST T. */
74 tree_int_to_gmp (tree t
, mpz_t res
)
76 wi::to_mpz (t
, res
, TYPE_SIGN (TREE_TYPE (t
)));
79 /* Returns the index of the PHI argument defined in the outermost
83 phi_arg_in_outermost_loop (gphi
*phi
)
85 loop_p loop
= gimple_bb (phi
)->loop_father
;
88 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
89 if (!flow_bb_inside_loop_p (loop
, gimple_phi_arg_edge (phi
, i
)->src
))
91 loop
= gimple_phi_arg_edge (phi
, i
)->src
->loop_father
;
98 /* Removes a simple copy phi node "RES = phi (INIT, RES)" at position
99 PSI by inserting on the loop ENTRY edge assignment "RES = INIT". */
102 remove_simple_copy_phi (gphi_iterator
*psi
)
104 gphi
*phi
= psi
->phi ();
105 tree res
= gimple_phi_result (phi
);
106 size_t entry
= phi_arg_in_outermost_loop (phi
);
107 tree init
= gimple_phi_arg_def (phi
, entry
);
108 gassign
*stmt
= gimple_build_assign (res
, init
);
109 edge e
= gimple_phi_arg_edge (phi
, entry
);
111 remove_phi_node (psi
, false);
112 gsi_insert_on_edge_immediate (e
, stmt
);
115 /* Removes an invariant phi node at position PSI by inserting on the
116 loop ENTRY edge the assignment RES = INIT. */
119 remove_invariant_phi (sese region
, gphi_iterator
*psi
)
121 gphi
*phi
= psi
->phi ();
122 loop_p loop
= loop_containing_stmt (phi
);
123 tree res
= gimple_phi_result (phi
);
124 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
125 size_t entry
= phi_arg_in_outermost_loop (phi
);
126 edge e
= gimple_phi_arg_edge (phi
, entry
);
129 gimple_seq stmts
= NULL
;
131 if (tree_contains_chrecs (scev
, NULL
))
132 scev
= gimple_phi_arg_def (phi
, entry
);
134 var
= force_gimple_operand (scev
, &stmts
, true, NULL_TREE
);
135 stmt
= gimple_build_assign (res
, var
);
136 remove_phi_node (psi
, false);
138 gimple_seq_add_stmt (&stmts
, stmt
);
139 gsi_insert_seq_on_edge (e
, stmts
);
140 gsi_commit_edge_inserts ();
141 SSA_NAME_DEF_STMT (res
) = stmt
;
144 /* Returns true when the phi node at PSI is of the form "a = phi (a, x)". */
147 simple_copy_phi_p (gphi
*phi
)
151 if (gimple_phi_num_args (phi
) != 2)
154 res
= gimple_phi_result (phi
);
155 return (res
== gimple_phi_arg_def (phi
, 0)
156 || res
== gimple_phi_arg_def (phi
, 1));
159 /* Returns true when the phi node at position PSI is a reduction phi
160 node in REGION. Otherwise moves the pointer PSI to the next phi to
164 reduction_phi_p (sese region
, gphi_iterator
*psi
)
167 gphi
*phi
= psi
->phi ();
168 tree res
= gimple_phi_result (phi
);
170 loop
= loop_containing_stmt (phi
);
172 if (simple_copy_phi_p (phi
))
174 /* PRE introduces phi nodes like these, for an example,
175 see id-5.f in the fortran graphite testsuite:
177 # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
179 remove_simple_copy_phi (psi
);
183 if (scev_analyzable_p (res
, region
))
185 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
187 if (evolution_function_is_invariant_p (scev
, loop
->num
))
188 remove_invariant_phi (region
, psi
);
195 /* All the other cases are considered reductions. */
199 /* Store the GRAPHITE representation of BB. */
201 static gimple_poly_bb_p
202 new_gimple_poly_bb (basic_block bb
, vec
<data_reference_p
> drs
)
204 gimple_poly_bb_p gbb
;
206 gbb
= XNEW (struct gimple_poly_bb
);
209 GBB_DATA_REFS (gbb
) = drs
;
210 GBB_CONDITIONS (gbb
).create (0);
211 GBB_CONDITION_CASES (gbb
).create (0);
217 free_data_refs_aux (vec
<data_reference_p
> datarefs
)
222 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
225 base_alias_pair_p bap
= (base_alias_pair_p
)(dr
->aux
);
227 free (bap
->alias_set
);
236 free_gimple_poly_bb (gimple_poly_bb_p gbb
)
238 free_data_refs_aux (GBB_DATA_REFS (gbb
));
239 free_data_refs (GBB_DATA_REFS (gbb
));
241 GBB_CONDITIONS (gbb
).release ();
242 GBB_CONDITION_CASES (gbb
).release ();
243 GBB_BB (gbb
)->aux
= 0;
247 /* Deletes all gimple bbs in SCOP. */
250 remove_gbbs_in_scop (scop_p scop
)
255 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
256 free_gimple_poly_bb (PBB_BLACK_BOX (pbb
));
259 /* Deletes all scops in SCOPS. */
262 free_scops (vec
<scop_p
> scops
)
267 FOR_EACH_VEC_ELT (scops
, i
, scop
)
269 remove_gbbs_in_scop (scop
);
270 free_sese (SCOP_REGION (scop
));
277 /* Return an ISL identifier for the polyhedral basic block PBB. */
280 isl_id_for_pbb (scop_p s
, poly_bb_p pbb
)
283 snprintf (name
, sizeof (name
), "S_%d", pbb_index (pbb
));
284 return isl_id_alloc (s
->ctx
, name
, pbb
);
287 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
288 We generate SCATTERING_DIMENSIONS scattering dimensions.
290 The scattering polyhedron consists of these dimensions: scattering,
291 loop_iterators, parameters.
295 | scattering_dimensions = 5
303 | Scattering polyhedron:
305 | scattering: {s1, s2, s3, s4, s5}
306 | loop_iterators: {i}
307 | parameters: {p1, p2}
309 | s1 s2 s3 s4 s5 i p1 p2 1
310 | 1 0 0 0 0 0 0 0 -4 = 0
311 | 0 1 0 0 0 -1 0 0 0 = 0
312 | 0 0 1 0 0 0 0 0 -5 = 0 */
315 build_pbb_scattering_polyhedrons (isl_aff
*static_sched
,
322 int scattering_dimensions
= isl_set_dim (pbb
->domain
, isl_dim_set
) * 2 + 1;
324 dc
= isl_set_get_space (pbb
->domain
);
325 dm
= isl_space_add_dims (isl_space_from_domain (dc
),
326 isl_dim_out
, scattering_dimensions
);
327 pbb
->schedule
= isl_map_universe (dm
);
329 for (i
= 0; i
< scattering_dimensions
; i
++)
331 /* Textual order inside this loop. */
334 isl_constraint
*c
= isl_equality_alloc
335 (isl_local_space_from_space (isl_map_get_space (pbb
->schedule
)));
337 val
= isl_aff_get_coefficient_val (static_sched
, isl_dim_in
, i
/ 2);
338 gcc_assert (val
&& isl_val_is_int (val
));
340 val
= isl_val_neg (val
);
341 c
= isl_constraint_set_constant_val (c
, val
);
342 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, i
, 1);
343 pbb
->schedule
= isl_map_add_constraint (pbb
->schedule
, c
);
346 /* Iterations of this loop. */
347 else /* if ((i % 2) == 1) */
349 int loop
= (i
- 1) / 2;
350 pbb
->schedule
= isl_map_equate (pbb
->schedule
, isl_dim_in
, loop
,
355 pbb
->transformed
= isl_map_copy (pbb
->schedule
);
358 /* Build for BB the static schedule.
360 The static schedule is a Dewey numbering of the abstract syntax
361 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
363 The following example informally defines the static schedule:
382 Static schedules for A to F:
395 build_scop_scattering (scop_p scop
)
399 gimple_poly_bb_p previous_gbb
= NULL
;
400 isl_space
*dc
= isl_set_get_space (scop
->context
);
401 isl_aff
*static_sched
;
403 dc
= isl_space_add_dims (dc
, isl_dim_set
, number_of_loops (cfun
));
404 static_sched
= isl_aff_zero_on_domain (isl_local_space_from_space (dc
));
406 /* We have to start schedules at 0 on the first component and
407 because we cannot compare_prefix_loops against a previous loop,
408 prefix will be equal to zero, and that index will be
409 incremented before copying. */
410 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
, 0, -1);
412 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
414 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
418 prefix
= nb_common_loops (SCOP_REGION (scop
), previous_gbb
, gbb
);
424 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
,
426 build_pbb_scattering_polyhedrons (static_sched
, pbb
);
429 isl_aff_free (static_sched
);
432 static isl_pw_aff
*extract_affine (scop_p
, tree
, __isl_take isl_space
*space
);
434 /* Extract an affine expression from the chain of recurrence E. */
437 extract_affine_chrec (scop_p s
, tree e
, __isl_take isl_space
*space
)
439 isl_pw_aff
*lhs
= extract_affine (s
, CHREC_LEFT (e
), isl_space_copy (space
));
440 isl_pw_aff
*rhs
= extract_affine (s
, CHREC_RIGHT (e
), isl_space_copy (space
));
441 isl_local_space
*ls
= isl_local_space_from_space (space
);
442 unsigned pos
= sese_loop_depth (SCOP_REGION (s
), get_chrec_loop (e
)) - 1;
443 isl_aff
*loop
= isl_aff_set_coefficient_si
444 (isl_aff_zero_on_domain (ls
), isl_dim_in
, pos
, 1);
445 isl_pw_aff
*l
= isl_pw_aff_from_aff (loop
);
447 /* Before multiplying, make sure that the result is affine. */
448 gcc_assert (isl_pw_aff_is_cst (rhs
)
449 || isl_pw_aff_is_cst (l
));
451 return isl_pw_aff_add (lhs
, isl_pw_aff_mul (rhs
, l
));
454 /* Extract an affine expression from the mult_expr E. */
457 extract_affine_mul (scop_p s
, tree e
, __isl_take isl_space
*space
)
459 isl_pw_aff
*lhs
= extract_affine (s
, TREE_OPERAND (e
, 0),
460 isl_space_copy (space
));
461 isl_pw_aff
*rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
463 if (!isl_pw_aff_is_cst (lhs
)
464 && !isl_pw_aff_is_cst (rhs
))
466 isl_pw_aff_free (lhs
);
467 isl_pw_aff_free (rhs
);
471 return isl_pw_aff_mul (lhs
, rhs
);
474 /* Return an ISL identifier from the name of the ssa_name E. */
477 isl_id_for_ssa_name (scop_p s
, tree e
)
479 const char *name
= get_name (e
);
483 id
= isl_id_alloc (s
->ctx
, name
, e
);
487 snprintf (name1
, sizeof (name1
), "P_%d", SSA_NAME_VERSION (e
));
488 id
= isl_id_alloc (s
->ctx
, name1
, e
);
494 /* Return an ISL identifier for the data reference DR. */
497 isl_id_for_dr (scop_p s
, data_reference_p dr ATTRIBUTE_UNUSED
)
499 /* Data references all get the same isl_id. They need to be comparable
500 and are distinguished through the first dimension, which contains the
502 return isl_id_alloc (s
->ctx
, "", 0);
505 /* Extract an affine expression from the ssa_name E. */
508 extract_affine_name (scop_p s
, tree e
, __isl_take isl_space
*space
)
515 id
= isl_id_for_ssa_name (s
, e
);
516 dimension
= isl_space_find_dim_by_id (space
, isl_dim_param
, id
);
518 dom
= isl_set_universe (isl_space_copy (space
));
519 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
520 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_param
, dimension
, 1);
521 return isl_pw_aff_alloc (dom
, aff
);
524 /* Extract an affine expression from the gmp constant G. */
527 extract_affine_gmp (mpz_t g
, __isl_take isl_space
*space
)
529 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
530 isl_aff
*aff
= isl_aff_zero_on_domain (ls
);
531 isl_set
*dom
= isl_set_universe (space
);
535 ct
= isl_aff_get_ctx (aff
);
536 v
= isl_val_int_from_gmp (ct
, g
);
537 aff
= isl_aff_add_constant_val (aff
, v
);
539 return isl_pw_aff_alloc (dom
, aff
);
542 /* Extract an affine expression from the integer_cst E. */
545 extract_affine_int (tree e
, __isl_take isl_space
*space
)
551 tree_int_to_gmp (e
, g
);
552 res
= extract_affine_gmp (g
, space
);
558 /* Compute pwaff mod 2^width. */
561 wrap (isl_pw_aff
*pwaff
, unsigned width
)
565 mod
= isl_val_int_from_ui (isl_pw_aff_get_ctx (pwaff
), width
);
566 mod
= isl_val_2exp (mod
);
567 pwaff
= isl_pw_aff_mod_val (pwaff
, mod
);
572 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
573 Otherwise returns -1. */
576 parameter_index_in_region_1 (tree name
, sese region
)
581 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
583 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, p
)
590 /* When the parameter NAME is in REGION, returns its index in
591 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
592 and returns the index of NAME. */
595 parameter_index_in_region (tree name
, sese region
)
599 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
601 /* Cannot constrain on anything else than INTEGER_TYPE parameters. */
602 if (TREE_CODE (TREE_TYPE (name
)) != INTEGER_TYPE
)
605 if (!invariant_in_sese_p_rec (name
, region
))
608 i
= parameter_index_in_region_1 (name
, region
);
612 gcc_assert (SESE_ADD_PARAMS (region
));
614 i
= SESE_PARAMS (region
).length ();
615 SESE_PARAMS (region
).safe_push (name
);
619 /* Extract an affine expression from the tree E in the scop S. */
622 extract_affine (scop_p s
, tree e
, __isl_take isl_space
*space
)
624 isl_pw_aff
*lhs
, *rhs
, *res
;
627 if (e
== chrec_dont_know
) {
628 isl_space_free (space
);
632 switch (TREE_CODE (e
))
634 case POLYNOMIAL_CHREC
:
635 res
= extract_affine_chrec (s
, e
, space
);
639 res
= extract_affine_mul (s
, e
, space
);
643 case POINTER_PLUS_EXPR
:
644 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
645 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
646 res
= isl_pw_aff_add (lhs
, rhs
);
650 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
651 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
652 res
= isl_pw_aff_sub (lhs
, rhs
);
657 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
658 rhs
= extract_affine (s
, integer_minus_one_node
, space
);
659 res
= isl_pw_aff_mul (lhs
, rhs
);
663 gcc_assert (-1 != parameter_index_in_region_1 (e
, s
->region
)
664 || !invariant_in_sese_p_rec (e
, s
->region
));
665 res
= extract_affine_name (s
, e
, space
);
669 res
= extract_affine_int (e
, space
);
670 /* No need to wrap a single integer. */
674 case NON_LVALUE_EXPR
:
675 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
683 type
= TREE_TYPE (e
);
684 if (TYPE_UNSIGNED (type
))
685 res
= wrap (res
, TYPE_PRECISION (type
));
690 /* In the context of sese S, scan the expression E and translate it to
691 a linear expression C. When parsing a symbolic multiplication, K
692 represents the constant multiplier of an expression containing
696 scan_tree_for_params (sese s
, tree e
)
698 if (e
== chrec_dont_know
)
701 switch (TREE_CODE (e
))
703 case POLYNOMIAL_CHREC
:
704 scan_tree_for_params (s
, CHREC_LEFT (e
));
708 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
709 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
711 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
715 case POINTER_PLUS_EXPR
:
717 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
718 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
724 case NON_LVALUE_EXPR
:
725 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
729 parameter_index_in_region (e
, s
);
745 /* Find parameters with respect to REGION in BB. We are looking in memory
746 access functions, conditions and loop bounds. */
749 find_params_in_bb (sese region
, gimple_poly_bb_p gbb
)
755 loop_p loop
= GBB_BB (gbb
)->loop_father
;
757 /* Find parameters in the access functions of data references. */
758 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
759 for (j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
760 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
));
762 /* Find parameters in conditional statements. */
763 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
765 tree lhs
= scalar_evolution_in_region (region
, loop
,
766 gimple_cond_lhs (stmt
));
767 tree rhs
= scalar_evolution_in_region (region
, loop
,
768 gimple_cond_rhs (stmt
));
770 scan_tree_for_params (region
, lhs
);
771 scan_tree_for_params (region
, rhs
);
775 /* Record the parameters used in the SCOP. A variable is a parameter
776 in a scop if it does not vary during the execution of that scop. */
779 find_scop_parameters (scop_p scop
)
783 sese region
= SCOP_REGION (scop
);
787 /* Find the parameters used in the loop bounds. */
788 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
790 tree nb_iters
= number_of_latch_executions (loop
);
792 if (!chrec_contains_symbols (nb_iters
))
795 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
796 scan_tree_for_params (region
, nb_iters
);
799 /* Find the parameters used in data accesses. */
800 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
801 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
803 nbp
= sese_nb_params (region
);
804 scop_set_nb_params (scop
, nbp
);
805 SESE_ADD_PARAMS (region
) = false;
808 /* Assign dimension for each parameter in SCOP. */
811 set_scop_parameter_dim (scop_p scop
)
813 sese region
= SCOP_REGION (scop
);
814 unsigned nbp
= sese_nb_params (region
);
815 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, nbp
, 0);
819 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, e
)
820 space
= isl_space_set_dim_id (space
, isl_dim_param
, i
,
821 isl_id_for_ssa_name (scop
, e
));
823 scop
->context
= isl_set_universe (space
);
826 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
827 the constraints for the surrounding loops. */
830 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
832 isl_set
*outer
, isl_set
**doms
)
834 tree nb_iters
= number_of_latch_executions (loop
);
835 sese region
= SCOP_REGION (scop
);
837 isl_set
*inner
= isl_set_copy (outer
);
840 int pos
= isl_set_dim (outer
, isl_dim_set
);
846 inner
= isl_set_add_dims (inner
, isl_dim_set
, 1);
847 space
= isl_set_get_space (inner
);
850 c
= isl_inequality_alloc
851 (isl_local_space_from_space (isl_space_copy (space
)));
852 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, 1);
853 inner
= isl_set_add_constraint (inner
, c
);
855 /* loop_i <= cst_nb_iters */
856 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
858 c
= isl_inequality_alloc
859 (isl_local_space_from_space (isl_space_copy (space
)));
860 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
861 tree_int_to_gmp (nb_iters
, g
);
862 v
= isl_val_int_from_gmp (scop
->ctx
, g
);
863 c
= isl_constraint_set_constant_val (c
, v
);
864 inner
= isl_set_add_constraint (inner
, c
);
867 /* loop_i <= expr_nb_iters */
868 else if (!chrec_contains_undetermined (nb_iters
))
877 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
879 aff
= extract_affine (scop
, nb_iters
, isl_set_get_space (inner
));
880 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff
));
881 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
882 isl_set_dim (valid
, isl_dim_set
));
883 scop
->context
= isl_set_intersect (scop
->context
, valid
);
885 ls
= isl_local_space_from_space (isl_space_copy (space
));
886 al
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
888 le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (al
),
889 isl_pw_aff_copy (aff
));
890 inner
= isl_set_intersect (inner
, le
);
892 if (max_stmt_executions (loop
, &nit
))
894 /* Insert in the context the constraints from the
895 estimation of the number of iterations NIT and the
896 symbolic number of iterations (involving parameter
897 names) NB_ITERS. First, build the affine expression
898 "NIT - NB_ITERS" and then say that it is positive,
899 i.e., NIT approximates NB_ITERS: "NIT >= NB_ITERS". */
906 wi::to_mpz (nit
, g
, SIGNED
);
907 mpz_sub_ui (g
, g
, 1);
908 approx
= extract_affine_gmp (g
, isl_set_get_space (inner
));
909 x
= isl_pw_aff_ge_set (approx
, aff
);
910 x
= isl_set_project_out (x
, isl_dim_set
, 0,
911 isl_set_dim (x
, isl_dim_set
));
912 scop
->context
= isl_set_intersect (scop
->context
, x
);
914 c
= isl_inequality_alloc
915 (isl_local_space_from_space (isl_space_copy (space
)));
916 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
917 v
= isl_val_int_from_gmp (scop
->ctx
, g
);
919 c
= isl_constraint_set_constant_val (c
, v
);
920 inner
= isl_set_add_constraint (inner
, c
);
923 isl_pw_aff_free (aff
);
928 if (loop
->inner
&& loop_in_sese_p (loop
->inner
, region
))
929 build_loop_iteration_domains (scop
, loop
->inner
, nb
+ 1,
930 isl_set_copy (inner
), doms
);
934 && loop_in_sese_p (loop
->next
, region
))
935 build_loop_iteration_domains (scop
, loop
->next
, nb
,
936 isl_set_copy (outer
), doms
);
938 doms
[loop
->num
] = inner
;
940 isl_set_free (outer
);
941 isl_space_free (space
);
945 /* Returns a linear expression for tree T evaluated in PBB. */
948 create_pw_aff_from_tree (poly_bb_p pbb
, tree t
)
950 scop_p scop
= PBB_SCOP (pbb
);
952 t
= scalar_evolution_in_region (SCOP_REGION (scop
), pbb_loop (pbb
), t
);
953 gcc_assert (!automatically_generated_chrec_p (t
));
955 return extract_affine (scop
, t
, isl_set_get_space (pbb
->domain
));
958 /* Add conditional statement STMT to pbb. CODE is used as the comparison
959 operator. This allows us to invert the condition or to handle
963 add_condition_to_pbb (poly_bb_p pbb
, gcond
*stmt
, enum tree_code code
)
965 isl_pw_aff
*lhs
= create_pw_aff_from_tree (pbb
, gimple_cond_lhs (stmt
));
966 isl_pw_aff
*rhs
= create_pw_aff_from_tree (pbb
, gimple_cond_rhs (stmt
));
972 cond
= isl_pw_aff_lt_set (lhs
, rhs
);
976 cond
= isl_pw_aff_gt_set (lhs
, rhs
);
980 cond
= isl_pw_aff_le_set (lhs
, rhs
);
984 cond
= isl_pw_aff_ge_set (lhs
, rhs
);
988 cond
= isl_pw_aff_eq_set (lhs
, rhs
);
992 cond
= isl_pw_aff_ne_set (lhs
, rhs
);
996 isl_pw_aff_free (lhs
);
997 isl_pw_aff_free (rhs
);
1001 cond
= isl_set_coalesce (cond
);
1002 cond
= isl_set_set_tuple_id (cond
, isl_set_get_tuple_id (pbb
->domain
));
1003 pbb
->domain
= isl_set_intersect (pbb
->domain
, cond
);
1006 /* Add conditions to the domain of PBB. */
1009 add_conditions_to_domain (poly_bb_p pbb
)
1013 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1015 if (GBB_CONDITIONS (gbb
).is_empty ())
1018 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
1019 switch (gimple_code (stmt
))
1023 /* Don't constrain on anything else than INTEGER_TYPE. */
1024 if (TREE_CODE (TREE_TYPE (gimple_cond_lhs (stmt
))) != INTEGER_TYPE
)
1027 gcond
*cond_stmt
= as_a
<gcond
*> (stmt
);
1028 enum tree_code code
= gimple_cond_code (cond_stmt
);
1030 /* The conditions for ELSE-branches are inverted. */
1031 if (!GBB_CONDITION_CASES (gbb
)[i
])
1032 code
= invert_tree_comparison (code
, false);
1034 add_condition_to_pbb (pbb
, cond_stmt
, code
);
1039 /* Switch statements are not supported right now - fall through. */
1047 /* Traverses all the GBBs of the SCOP and add their constraints to the
1048 iteration domains. */
1051 add_conditions_to_constraints (scop_p scop
)
1056 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1057 add_conditions_to_domain (pbb
);
1060 /* Returns a COND_EXPR statement when BB has a single predecessor, the
1061 edge between BB and its predecessor is not a loop exit edge, and
1062 the last statement of the single predecessor is a COND_EXPR. */
1065 single_pred_cond_non_loop_exit (basic_block bb
)
1067 if (single_pred_p (bb
))
1069 edge e
= single_pred_edge (bb
);
1070 basic_block pred
= e
->src
;
1073 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
1076 stmt
= last_stmt (pred
);
1078 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1079 return as_a
<gcond
*> (stmt
);
1085 class sese_dom_walker
: public dom_walker
1088 sese_dom_walker (cdi_direction
, sese
);
1090 virtual void before_dom_children (basic_block
);
1091 virtual void after_dom_children (basic_block
);
1094 auto_vec
<gimple
*, 3> m_conditions
, m_cases
;
1098 sese_dom_walker::sese_dom_walker (cdi_direction direction
, sese region
)
1099 : dom_walker (direction
), m_region (region
)
1103 /* Call-back for dom_walk executed before visiting the dominated
1107 sese_dom_walker::before_dom_children (basic_block bb
)
1109 gimple_poly_bb_p gbb
;
1112 if (!bb_in_sese_p (bb
, m_region
))
1115 stmt
= single_pred_cond_non_loop_exit (bb
);
1119 edge e
= single_pred_edge (bb
);
1121 m_conditions
.safe_push (stmt
);
1123 if (e
->flags
& EDGE_TRUE_VALUE
)
1124 m_cases
.safe_push (stmt
);
1126 m_cases
.safe_push (NULL
);
1129 gbb
= gbb_from_bb (bb
);
1133 GBB_CONDITIONS (gbb
) = m_conditions
.copy ();
1134 GBB_CONDITION_CASES (gbb
) = m_cases
.copy ();
1138 /* Call-back for dom_walk executed after visiting the dominated
1142 sese_dom_walker::after_dom_children (basic_block bb
)
1144 if (!bb_in_sese_p (bb
, m_region
))
1147 if (single_pred_cond_non_loop_exit (bb
))
1149 m_conditions
.pop ();
1154 /* Add constraints on the possible values of parameter P from the type
1158 add_param_constraints (scop_p scop
, graphite_dim_t p
)
1160 tree parameter
= SESE_PARAMS (SCOP_REGION (scop
))[p
];
1161 tree type
= TREE_TYPE (parameter
);
1162 tree lb
= NULL_TREE
;
1163 tree ub
= NULL_TREE
;
1165 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
1166 lb
= lower_bound_in_type (type
, type
);
1168 lb
= TYPE_MIN_VALUE (type
);
1170 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
1171 ub
= upper_bound_in_type (type
, type
);
1173 ub
= TYPE_MAX_VALUE (type
);
1177 isl_space
*space
= isl_set_get_space (scop
->context
);
1182 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1184 tree_int_to_gmp (lb
, g
);
1185 v
= isl_val_int_from_gmp (scop
->ctx
, g
);
1186 v
= isl_val_neg (v
);
1188 c
= isl_constraint_set_constant_val (c
, v
);
1189 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, 1);
1191 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1196 isl_space
*space
= isl_set_get_space (scop
->context
);
1201 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1204 tree_int_to_gmp (ub
, g
);
1205 v
= isl_val_int_from_gmp (scop
->ctx
, g
);
1207 c
= isl_constraint_set_constant_val (c
, v
);
1208 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, -1);
1210 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1214 /* Build the context of the SCOP. The context usually contains extra
1215 constraints that are added to the iteration domains that constrain
1219 build_scop_context (scop_p scop
)
1221 graphite_dim_t p
, n
= scop_nb_params (scop
);
1223 for (p
= 0; p
< n
; p
++)
1224 add_param_constraints (scop
, p
);
1227 /* Build the iteration domains: the loops belonging to the current
1228 SCOP, and that vary for the execution of the current basic block.
1229 Returns false if there is no loop in SCOP. */
1232 build_scop_iteration_domain (scop_p scop
)
1235 sese region
= SCOP_REGION (scop
);
1238 int nb_loops
= number_of_loops (cfun
);
1239 isl_set
**doms
= XCNEWVEC (isl_set
*, nb_loops
);
1241 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
1242 if (!loop_in_sese_p (loop_outer (loop
), region
))
1243 build_loop_iteration_domains (scop
, loop
, 0,
1244 isl_set_copy (scop
->context
), doms
);
1246 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1248 loop
= pbb_loop (pbb
);
1250 if (doms
[loop
->num
])
1251 pbb
->domain
= isl_set_copy (doms
[loop
->num
]);
1253 pbb
->domain
= isl_set_copy (scop
->context
);
1255 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
1256 isl_id_for_pbb (scop
, pbb
));
1259 for (i
= 0; i
< nb_loops
; i
++)
1261 isl_set_free (doms
[i
]);
1266 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1267 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1268 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1272 pdr_add_alias_set (isl_map
*acc
, data_reference_p dr
)
1275 int alias_set_num
= 0;
1276 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1278 if (bap
&& bap
->alias_set
)
1279 alias_set_num
= *(bap
->alias_set
);
1281 c
= isl_equality_alloc
1282 (isl_local_space_from_space (isl_map_get_space (acc
)));
1283 c
= isl_constraint_set_constant_si (c
, -alias_set_num
);
1284 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
1286 return isl_map_add_constraint (acc
, c
);
1289 /* Assign the affine expression INDEX to the output dimension POS of
1290 MAP and return the result. */
1293 set_index (isl_map
*map
, int pos
, isl_pw_aff
*index
)
1296 int len
= isl_map_dim (map
, isl_dim_out
);
1299 index_map
= isl_map_from_pw_aff (index
);
1300 index_map
= isl_map_insert_dims (index_map
, isl_dim_out
, 0, pos
);
1301 index_map
= isl_map_add_dims (index_map
, isl_dim_out
, len
- pos
- 1);
1303 id
= isl_map_get_tuple_id (map
, isl_dim_out
);
1304 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_out
, id
);
1305 id
= isl_map_get_tuple_id (map
, isl_dim_in
);
1306 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_in
, id
);
1308 return isl_map_intersect (map
, index_map
);
1311 /* Add to ACCESSES polyhedron equalities defining the access functions
1312 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1313 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1314 PBB is the poly_bb_p that contains the data reference DR. */
1317 pdr_add_memory_accesses (isl_map
*acc
, data_reference_p dr
, poly_bb_p pbb
)
1319 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1320 scop_p scop
= PBB_SCOP (pbb
);
1322 for (i
= 0; i
< nb_subscripts
; i
++)
1325 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1327 aff
= extract_affine (scop
, afn
,
1328 isl_space_domain (isl_map_get_space (acc
)));
1329 acc
= set_index (acc
, i
+ 1, aff
);
1335 /* Add constrains representing the size of the accessed data to the
1336 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1337 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1341 pdr_add_data_dimensions (isl_set
*subscript_sizes
, scop_p scop
,
1342 data_reference_p dr
)
1344 tree ref
= DR_REF (dr
);
1346 int nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1347 for (int i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1349 if (TREE_CODE (ref
) != ARRAY_REF
)
1350 return subscript_sizes
;
1352 tree low
= array_ref_low_bound (ref
);
1353 tree high
= array_ref_up_bound (ref
);
1355 /* XXX The PPL code dealt separately with
1356 subscript - low >= 0 and high - subscript >= 0 in case one of
1357 the two bounds isn't known. Do the same here? */
1359 if (tree_fits_shwi_p (low
)
1361 && tree_fits_shwi_p (high
)
1362 /* 1-element arrays at end of structures may extend over
1363 their declared size. */
1364 && !(array_at_struct_end_p (ref
)
1365 && operand_equal_p (low
, high
, 0)))
1369 isl_set
*univ
, *lbs
, *ubs
;
1372 isl_space
*space
= isl_set_get_space (subscript_sizes
);
1373 isl_pw_aff
*lb
= extract_affine_int (low
, isl_space_copy (space
));
1374 isl_pw_aff
*ub
= extract_affine_int (high
, isl_space_copy (space
));
1377 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub
));
1378 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1379 isl_set_dim (valid
, isl_dim_set
));
1380 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1382 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
1383 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_in
, i
+ 1, 1);
1384 univ
= isl_set_universe (isl_space_domain (isl_aff_get_space (aff
)));
1385 index
= isl_pw_aff_alloc (univ
, aff
);
1387 id
= isl_set_get_tuple_id (subscript_sizes
);
1388 lb
= isl_pw_aff_set_tuple_id (lb
, isl_dim_in
, isl_id_copy (id
));
1389 ub
= isl_pw_aff_set_tuple_id (ub
, isl_dim_in
, id
);
1391 /* low <= sub_i <= high */
1392 lbs
= isl_pw_aff_ge_set (isl_pw_aff_copy (index
), lb
);
1393 ubs
= isl_pw_aff_le_set (index
, ub
);
1394 subscript_sizes
= isl_set_intersect (subscript_sizes
, lbs
);
1395 subscript_sizes
= isl_set_intersect (subscript_sizes
, ubs
);
1399 return subscript_sizes
;
1402 /* Build data accesses for DR in PBB. */
1405 build_poly_dr (data_reference_p dr
, poly_bb_p pbb
)
1407 int dr_base_object_set
;
1409 isl_set
*subscript_sizes
;
1410 scop_p scop
= PBB_SCOP (pbb
);
1413 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
1414 int nb_out
= 1 + DR_NUM_DIMENSIONS (dr
);
1415 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
1416 isl_dim_out
, nb_out
);
1418 acc
= isl_map_universe (space
);
1419 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, isl_id_for_dr (scop
, dr
));
1422 acc
= pdr_add_alias_set (acc
, dr
);
1423 acc
= pdr_add_memory_accesses (acc
, dr
, pbb
);
1426 isl_id
*id
= isl_id_for_dr (scop
, dr
);
1427 int nb
= 1 + DR_NUM_DIMENSIONS (dr
);
1428 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, 0, nb
);
1429 int alias_set_num
= 0;
1430 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1432 if (bap
&& bap
->alias_set
)
1433 alias_set_num
= *(bap
->alias_set
);
1435 space
= isl_space_set_tuple_id (space
, isl_dim_set
, id
);
1436 subscript_sizes
= isl_set_nat_universe (space
);
1437 subscript_sizes
= isl_set_fix_si (subscript_sizes
, isl_dim_set
, 0,
1439 subscript_sizes
= pdr_add_data_dimensions (subscript_sizes
, scop
, dr
);
1442 gcc_assert (dr
->aux
);
1443 dr_base_object_set
= ((base_alias_pair
*)(dr
->aux
))->base_obj_set
;
1445 new_poly_dr (pbb
, dr_base_object_set
,
1446 DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1447 dr
, DR_NUM_DIMENSIONS (dr
), acc
, subscript_sizes
);
1450 /* Write to FILE the alias graph of data references in DIMACS format. */
1453 write_alias_graph_to_ascii_dimacs (FILE *file
, char *comment
,
1454 vec
<data_reference_p
> drs
)
1456 int num_vertex
= drs
.length ();
1458 data_reference_p dr1
, dr2
;
1461 if (num_vertex
== 0)
1464 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1465 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1466 if (dr_may_alias_p (dr1
, dr2
, true))
1469 fprintf (file
, "$\n");
1472 fprintf (file
, "c %s\n", comment
);
1474 fprintf (file
, "p edge %d %d\n", num_vertex
, edge_num
);
1476 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1477 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1478 if (dr_may_alias_p (dr1
, dr2
, true))
1479 fprintf (file
, "e %d %d\n", i
+ 1, j
+ 1);
1484 /* Write to FILE the alias graph of data references in DOT format. */
1487 write_alias_graph_to_ascii_dot (FILE *file
, char *comment
,
1488 vec
<data_reference_p
> drs
)
1490 int num_vertex
= drs
.length ();
1491 data_reference_p dr1
, dr2
;
1494 if (num_vertex
== 0)
1497 fprintf (file
, "$\n");
1500 fprintf (file
, "c %s\n", comment
);
1502 /* First print all the vertices. */
1503 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1504 fprintf (file
, "n%d;\n", i
);
1506 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1507 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1508 if (dr_may_alias_p (dr1
, dr2
, true))
1509 fprintf (file
, "n%d n%d\n", i
, j
);
1514 /* Write to FILE the alias graph of data references in ECC format. */
1517 write_alias_graph_to_ascii_ecc (FILE *file
, char *comment
,
1518 vec
<data_reference_p
> drs
)
1520 int num_vertex
= drs
.length ();
1521 data_reference_p dr1
, dr2
;
1524 if (num_vertex
== 0)
1527 fprintf (file
, "$\n");
1530 fprintf (file
, "c %s\n", comment
);
1532 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1533 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1534 if (dr_may_alias_p (dr1
, dr2
, true))
1535 fprintf (file
, "%d %d\n", i
, j
);
1540 /* Check if DR1 and DR2 are in the same object set. */
1543 dr_same_base_object_p (const struct data_reference
*dr1
,
1544 const struct data_reference
*dr2
)
1546 return operand_equal_p (DR_BASE_OBJECT (dr1
), DR_BASE_OBJECT (dr2
), 0);
1549 /* Uses DFS component number as representative of alias-sets. Also tests for
1550 optimality by verifying if every connected component is a clique. Returns
1551 true (1) if the above test is true, and false (0) otherwise. */
1554 build_alias_set_optimal_p (vec
<data_reference_p
> drs
)
1556 int num_vertices
= drs
.length ();
1557 struct graph
*g
= new_graph (num_vertices
);
1558 data_reference_p dr1
, dr2
;
1560 int num_connected_components
;
1561 int v_indx1
, v_indx2
, num_vertices_in_component
;
1564 struct graph_edge
*e
;
1565 int this_component_is_clique
;
1566 int all_components_are_cliques
= 1;
1568 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1569 for (j
= i
+1; drs
.iterate (j
, &dr2
); j
++)
1570 if (dr_may_alias_p (dr1
, dr2
, true))
1576 all_vertices
= XNEWVEC (int, num_vertices
);
1577 vertices
= XNEWVEC (int, num_vertices
);
1578 for (i
= 0; i
< num_vertices
; i
++)
1579 all_vertices
[i
] = i
;
1581 num_connected_components
= graphds_dfs (g
, all_vertices
, num_vertices
,
1583 for (i
= 0; i
< g
->n_vertices
; i
++)
1585 data_reference_p dr
= drs
[i
];
1586 base_alias_pair
*bap
;
1588 gcc_assert (dr
->aux
);
1589 bap
= (base_alias_pair
*)(dr
->aux
);
1591 bap
->alias_set
= XNEW (int);
1592 *(bap
->alias_set
) = g
->vertices
[i
].component
+ 1;
1595 /* Verify if the DFS numbering results in optimal solution. */
1596 for (i
= 0; i
< num_connected_components
; i
++)
1598 num_vertices_in_component
= 0;
1599 /* Get all vertices whose DFS component number is the same as i. */
1600 for (j
= 0; j
< num_vertices
; j
++)
1601 if (g
->vertices
[j
].component
== i
)
1602 vertices
[num_vertices_in_component
++] = j
;
1604 /* Now test if the vertices in 'vertices' form a clique, by testing
1605 for edges among each pair. */
1606 this_component_is_clique
= 1;
1607 for (v_indx1
= 0; v_indx1
< num_vertices_in_component
; v_indx1
++)
1609 for (v_indx2
= v_indx1
+1; v_indx2
< num_vertices_in_component
; v_indx2
++)
1611 /* Check if the two vertices are connected by iterating
1612 through all the edges which have one of these are source. */
1613 e
= g
->vertices
[vertices
[v_indx2
]].pred
;
1616 if (e
->src
== vertices
[v_indx1
])
1622 this_component_is_clique
= 0;
1626 if (!this_component_is_clique
)
1627 all_components_are_cliques
= 0;
1631 free (all_vertices
);
1634 return all_components_are_cliques
;
1637 /* Group each data reference in DRS with its base object set num. */
1640 build_base_obj_set_for_drs (vec
<data_reference_p
> drs
)
1642 int num_vertex
= drs
.length ();
1643 struct graph
*g
= new_graph (num_vertex
);
1644 data_reference_p dr1
, dr2
;
1648 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1649 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1650 if (dr_same_base_object_p (dr1
, dr2
))
1656 queue
= XNEWVEC (int, num_vertex
);
1657 for (i
= 0; i
< num_vertex
; i
++)
1660 graphds_dfs (g
, queue
, num_vertex
, NULL
, true, NULL
);
1662 for (i
= 0; i
< g
->n_vertices
; i
++)
1664 data_reference_p dr
= drs
[i
];
1665 base_alias_pair
*bap
;
1667 gcc_assert (dr
->aux
);
1668 bap
= (base_alias_pair
*)(dr
->aux
);
1670 bap
->base_obj_set
= g
->vertices
[i
].component
+ 1;
1677 /* Build the data references for PBB. */
1680 build_pbb_drs (poly_bb_p pbb
)
1683 data_reference_p dr
;
1684 vec
<data_reference_p
> gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
1686 FOR_EACH_VEC_ELT (gbb_drs
, j
, dr
)
1687 build_poly_dr (dr
, pbb
);
1690 /* Dump to file the alias graphs for the data references in DRS. */
1693 dump_alias_graphs (vec
<data_reference_p
> drs
)
1696 FILE *file_dimacs
, *file_ecc
, *file_dot
;
1698 file_dimacs
= fopen ("/tmp/dr_alias_graph_dimacs", "ab");
1701 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1702 current_function_name ());
1703 write_alias_graph_to_ascii_dimacs (file_dimacs
, comment
, drs
);
1704 fclose (file_dimacs
);
1707 file_ecc
= fopen ("/tmp/dr_alias_graph_ecc", "ab");
1710 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1711 current_function_name ());
1712 write_alias_graph_to_ascii_ecc (file_ecc
, comment
, drs
);
1716 file_dot
= fopen ("/tmp/dr_alias_graph_dot", "ab");
1719 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1720 current_function_name ());
1721 write_alias_graph_to_ascii_dot (file_dot
, comment
, drs
);
1726 /* Build data references in SCOP. */
1729 build_scop_drs (scop_p scop
)
1733 data_reference_p dr
;
1734 auto_vec
<data_reference_p
, 3> drs
;
1736 /* Remove all the PBBs that do not have data references: these basic
1737 blocks are not handled in the polyhedral representation. */
1738 for (i
= 0; SCOP_BBS (scop
).iterate (i
, &pbb
); i
++)
1739 if (GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).is_empty ())
1741 free_gimple_poly_bb (PBB_BLACK_BOX (pbb
));
1743 SCOP_BBS (scop
).ordered_remove (i
);
1747 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1748 for (j
= 0; GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).iterate (j
, &dr
); j
++)
1751 FOR_EACH_VEC_ELT (drs
, i
, dr
)
1752 dr
->aux
= XNEW (base_alias_pair
);
1754 if (!build_alias_set_optimal_p (drs
))
1756 /* TODO: Add support when building alias set is not optimal. */
1760 build_base_obj_set_for_drs (drs
);
1762 /* When debugging, enable the following code. This cannot be used
1763 in production compilers. */
1765 dump_alias_graphs (drs
);
1769 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1770 build_pbb_drs (pbb
);
1773 /* Analyze all the data references of STMTS and add them to the
1774 GBB_DATA_REFS vector of BB. */
1777 analyze_drs_in_stmts (scop_p scop
, basic_block bb
, vec
<gimple
*> stmts
)
1780 gimple_poly_bb_p gbb
;
1783 sese region
= SCOP_REGION (scop
);
1785 if (!bb_in_sese_p (bb
, region
))
1788 nest
= outermost_loop_in_sese (region
, bb
);
1790 loop_p loop
= bb
->loop_father
;
1791 if (!loop_in_sese_p (loop
, region
))
1794 gbb
= gbb_from_bb (bb
);
1796 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
1798 if (is_gimple_debug (stmt
))
1801 graphite_find_data_references_in_stmt (nest
, loop
, stmt
,
1802 &GBB_DATA_REFS (gbb
));
1806 /* Insert STMT at the end of the STMTS sequence and then insert the
1807 statements from STMTS at INSERT_GSI and call analyze_drs_in_stmts
1811 insert_stmts (scop_p scop
, gimple
*stmt
, gimple_seq stmts
,
1812 gimple_stmt_iterator insert_gsi
)
1814 gimple_stmt_iterator gsi
;
1815 auto_vec
<gimple
*, 3> x
;
1817 gimple_seq_add_stmt (&stmts
, stmt
);
1818 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1819 x
.safe_push (gsi_stmt (gsi
));
1821 gsi_insert_seq_before (&insert_gsi
, stmts
, GSI_SAME_STMT
);
1822 analyze_drs_in_stmts (scop
, gsi_bb (insert_gsi
), x
);
1825 /* Insert the assignment "RES := EXPR" just after AFTER_STMT. */
1828 insert_out_of_ssa_copy (scop_p scop
, tree res
, tree expr
, gimple
*after_stmt
)
1831 gimple_stmt_iterator gsi
;
1832 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
1833 gassign
*stmt
= gimple_build_assign (unshare_expr (res
), var
);
1834 auto_vec
<gimple
*, 3> x
;
1836 gimple_seq_add_stmt (&stmts
, stmt
);
1837 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1838 x
.safe_push (gsi_stmt (gsi
));
1840 if (gimple_code (after_stmt
) == GIMPLE_PHI
)
1842 gsi
= gsi_after_labels (gimple_bb (after_stmt
));
1843 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
1847 gsi
= gsi_for_stmt (after_stmt
);
1848 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
1851 analyze_drs_in_stmts (scop
, gimple_bb (after_stmt
), x
);
1854 /* Creates a poly_bb_p for basic_block BB from the existing PBB. */
1857 new_pbb_from_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
)
1859 vec
<data_reference_p
> drs
;
1861 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1862 gimple_poly_bb_p gbb1
= new_gimple_poly_bb (bb
, drs
);
1863 poly_bb_p pbb1
= new_poly_bb (scop
, gbb1
);
1864 int index
, n
= SCOP_BBS (scop
).length ();
1866 /* The INDEX of PBB in SCOP_BBS. */
1867 for (index
= 0; index
< n
; index
++)
1868 if (SCOP_BBS (scop
)[index
] == pbb
)
1871 pbb1
->domain
= isl_set_copy (pbb
->domain
);
1872 pbb1
->domain
= isl_set_set_tuple_id (pbb1
->domain
,
1873 isl_id_for_pbb (scop
, pbb1
));
1875 GBB_PBB (gbb1
) = pbb1
;
1876 GBB_CONDITIONS (gbb1
) = GBB_CONDITIONS (gbb
).copy ();
1877 GBB_CONDITION_CASES (gbb1
) = GBB_CONDITION_CASES (gbb
).copy ();
1878 SCOP_BBS (scop
).safe_insert (index
+ 1, pbb1
);
1881 /* Insert on edge E the assignment "RES := EXPR". */
1884 insert_out_of_ssa_copy_on_edge (scop_p scop
, edge e
, tree res
, tree expr
)
1886 gimple_stmt_iterator gsi
;
1887 gimple_seq stmts
= NULL
;
1888 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
1889 gimple
*stmt
= gimple_build_assign (unshare_expr (res
), var
);
1891 auto_vec
<gimple
*, 3> x
;
1893 gimple_seq_add_stmt (&stmts
, stmt
);
1894 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1895 x
.safe_push (gsi_stmt (gsi
));
1897 gsi_insert_seq_on_edge (e
, stmts
);
1898 gsi_commit_edge_inserts ();
1899 bb
= gimple_bb (stmt
);
1901 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
1904 if (!gbb_from_bb (bb
))
1905 new_pbb_from_pbb (scop
, pbb_from_bb (e
->src
), bb
);
1907 analyze_drs_in_stmts (scop
, bb
, x
);
1910 /* Creates a zero dimension array of the same type as VAR. */
1913 create_zero_dim_array (tree var
, const char *base_name
)
1915 tree index_type
= build_index_type (integer_zero_node
);
1916 tree elt_type
= TREE_TYPE (var
);
1917 tree array_type
= build_array_type (elt_type
, index_type
);
1918 tree base
= create_tmp_var (array_type
, base_name
);
1920 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
1924 /* Returns true when PHI is a loop close phi node. */
1927 scalar_close_phi_node_p (gimple
*phi
)
1929 if (gimple_code (phi
) != GIMPLE_PHI
1930 || virtual_operand_p (gimple_phi_result (phi
)))
1933 /* Note that loop close phi nodes should have a single argument
1934 because we translated the representation into a canonical form
1935 before Graphite: see canonicalize_loop_closed_ssa_form. */
1936 return (gimple_phi_num_args (phi
) == 1);
1939 /* For a definition DEF in REGION, propagates the expression EXPR in
1940 all the uses of DEF outside REGION. */
1943 propagate_expr_outside_region (tree def
, tree expr
, sese region
)
1945 imm_use_iterator imm_iter
;
1948 bool replaced_once
= false;
1950 gcc_assert (TREE_CODE (def
) == SSA_NAME
);
1952 expr
= force_gimple_operand (unshare_expr (expr
), &stmts
, true,
1955 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1956 if (!is_gimple_debug (use_stmt
)
1957 && !bb_in_sese_p (gimple_bb (use_stmt
), region
))
1960 use_operand_p use_p
;
1962 FOR_EACH_PHI_OR_STMT_USE (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
1963 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0)
1964 && (replaced_once
= true))
1965 replace_exp (use_p
, expr
);
1967 update_stmt (use_stmt
);
1972 gsi_insert_seq_on_edge (SESE_ENTRY (region
), stmts
);
1973 gsi_commit_edge_inserts ();
1977 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
1978 dimension array for it. */
1981 rewrite_close_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
1983 sese region
= SCOP_REGION (scop
);
1984 gimple
*phi
= gsi_stmt (*psi
);
1985 tree res
= gimple_phi_result (phi
);
1986 basic_block bb
= gimple_bb (phi
);
1987 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
1988 tree arg
= gimple_phi_arg_def (phi
, 0);
1991 /* Note that loop close phi nodes should have a single argument
1992 because we translated the representation into a canonical form
1993 before Graphite: see canonicalize_loop_closed_ssa_form. */
1994 gcc_assert (gimple_phi_num_args (phi
) == 1);
1996 /* The phi node can be a non close phi node, when its argument is
1997 invariant, or a default definition. */
1998 if (is_gimple_min_invariant (arg
)
1999 || SSA_NAME_IS_DEFAULT_DEF (arg
))
2001 propagate_expr_outside_region (res
, arg
, region
);
2006 else if (gimple_bb (SSA_NAME_DEF_STMT (arg
))->loop_father
== bb
->loop_father
)
2008 propagate_expr_outside_region (res
, arg
, region
);
2009 stmt
= gimple_build_assign (res
, arg
);
2010 remove_phi_node (psi
, false);
2011 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2015 /* If res is scev analyzable and is not a scalar value, it is safe
2016 to ignore the close phi node: it will be code generated in the
2017 out of Graphite pass. */
2018 else if (scev_analyzable_p (res
, region
))
2020 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (res
));
2023 if (!loop_in_sese_p (loop
, region
))
2025 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2026 scev
= scalar_evolution_in_region (region
, loop
, arg
);
2027 scev
= compute_overall_effect_of_inner_loop (loop
, scev
);
2030 scev
= scalar_evolution_in_region (region
, loop
, res
);
2032 if (tree_does_not_contain_chrecs (scev
))
2033 propagate_expr_outside_region (res
, scev
, region
);
2040 tree zero_dim_array
= create_zero_dim_array (res
, "Close_Phi");
2042 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2044 if (TREE_CODE (arg
) == SSA_NAME
)
2045 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2046 SSA_NAME_DEF_STMT (arg
));
2048 insert_out_of_ssa_copy_on_edge (scop
, single_pred_edge (bb
),
2049 zero_dim_array
, arg
);
2052 remove_phi_node (psi
, false);
2053 SSA_NAME_DEF_STMT (res
) = stmt
;
2055 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2058 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2059 dimension array for it. */
2062 rewrite_phi_out_of_ssa (scop_p scop
, gphi_iterator
*psi
)
2065 gphi
*phi
= psi
->phi ();
2066 basic_block bb
= gimple_bb (phi
);
2067 tree res
= gimple_phi_result (phi
);
2068 tree zero_dim_array
= create_zero_dim_array (res
, "phi_out_of_ssa");
2071 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2073 tree arg
= gimple_phi_arg_def (phi
, i
);
2074 edge e
= gimple_phi_arg_edge (phi
, i
);
2076 /* Avoid the insertion of code in the loop latch to please the
2077 pattern matching of the vectorizer. */
2078 if (TREE_CODE (arg
) == SSA_NAME
2079 && !SSA_NAME_IS_DEFAULT_DEF (arg
)
2080 && e
->src
== bb
->loop_father
->latch
)
2081 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2082 SSA_NAME_DEF_STMT (arg
));
2084 insert_out_of_ssa_copy_on_edge (scop
, e
, zero_dim_array
, arg
);
2087 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2088 remove_phi_node (psi
, false);
2089 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2092 /* Rewrite the degenerate phi node at position PSI from the degenerate
2093 form "x = phi (y, y, ..., y)" to "x = y". */
2096 rewrite_degenerate_phi (gphi_iterator
*psi
)
2100 gimple_stmt_iterator gsi
;
2101 gphi
*phi
= psi
->phi ();
2102 tree res
= gimple_phi_result (phi
);
2105 bb
= gimple_bb (phi
);
2106 rhs
= degenerate_phi_result (phi
);
2109 stmt
= gimple_build_assign (res
, rhs
);
2110 remove_phi_node (psi
, false);
2112 gsi
= gsi_after_labels (bb
);
2113 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2116 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2119 rewrite_reductions_out_of_ssa (scop_p scop
)
2123 sese region
= SCOP_REGION (scop
);
2125 FOR_EACH_BB_FN (bb
, cfun
)
2126 if (bb_in_sese_p (bb
, region
))
2127 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
2129 gphi
*phi
= psi
.phi ();
2131 if (virtual_operand_p (gimple_phi_result (phi
)))
2137 if (gimple_phi_num_args (phi
) > 1
2138 && degenerate_phi_result (phi
))
2139 rewrite_degenerate_phi (&psi
);
2141 else if (scalar_close_phi_node_p (phi
))
2142 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2144 else if (reduction_phi_p (region
, &psi
))
2145 rewrite_phi_out_of_ssa (scop
, &psi
);
2148 update_ssa (TODO_update_ssa
);
2149 #ifdef ENABLE_CHECKING
2150 verify_loop_closed_ssa (true);
2154 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2155 read from ZERO_DIM_ARRAY. */
2158 rewrite_cross_bb_scalar_dependence (scop_p scop
, tree zero_dim_array
,
2159 tree def
, gimple
*use_stmt
)
2164 use_operand_p use_p
;
2166 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
2168 name
= copy_ssa_name (def
);
2169 name_stmt
= gimple_build_assign (name
, zero_dim_array
);
2171 gimple_assign_set_lhs (name_stmt
, name
);
2172 insert_stmts (scop
, name_stmt
, NULL
, gsi_for_stmt (use_stmt
));
2174 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2175 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
2176 replace_exp (use_p
, name
);
2178 update_stmt (use_stmt
);
2181 /* For every definition DEF in the SCOP that is used outside the scop,
2182 insert a closing-scop definition in the basic block just after this
2186 handle_scalar_deps_crossing_scop_limits (scop_p scop
, tree def
, gimple
*stmt
)
2188 tree var
= create_tmp_reg (TREE_TYPE (def
));
2189 tree new_name
= make_ssa_name (var
, stmt
);
2190 bool needs_copy
= false;
2191 use_operand_p use_p
;
2192 imm_use_iterator imm_iter
;
2194 sese region
= SCOP_REGION (scop
);
2196 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2198 if (!bb_in_sese_p (gimple_bb (use_stmt
), region
))
2200 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
2202 SET_USE (use_p
, new_name
);
2204 update_stmt (use_stmt
);
2209 /* Insert in the empty BB just after the scop a use of DEF such
2210 that the rewrite of cross_bb_scalar_dependences won't insert
2211 arrays everywhere else. */
2214 gimple
*assign
= gimple_build_assign (new_name
, def
);
2215 gimple_stmt_iterator psi
= gsi_after_labels (SESE_EXIT (region
)->dest
);
2217 update_stmt (assign
);
2218 gsi_insert_before (&psi
, assign
, GSI_SAME_STMT
);
2222 /* Rewrite the scalar dependences crossing the boundary of the BB
2223 containing STMT with an array. Return true when something has been
2227 rewrite_cross_bb_scalar_deps (scop_p scop
, gimple_stmt_iterator
*gsi
)
2229 sese region
= SCOP_REGION (scop
);
2230 gimple
*stmt
= gsi_stmt (*gsi
);
2231 imm_use_iterator imm_iter
;
2234 tree zero_dim_array
= NULL_TREE
;
2238 switch (gimple_code (stmt
))
2241 def
= gimple_assign_lhs (stmt
);
2245 def
= gimple_call_lhs (stmt
);
2253 || !is_gimple_reg (def
))
2256 if (scev_analyzable_p (def
, region
))
2258 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (def
));
2259 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
2261 if (tree_contains_chrecs (scev
, NULL
))
2264 propagate_expr_outside_region (def
, scev
, region
);
2268 def_bb
= gimple_bb (stmt
);
2270 handle_scalar_deps_crossing_scop_limits (scop
, def
, stmt
);
2272 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2273 if (gphi
*phi
= dyn_cast
<gphi
*> (use_stmt
))
2276 gphi_iterator psi
= gsi_for_phi (phi
);
2278 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
2279 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2281 rewrite_phi_out_of_ssa (scop
, &psi
);
2284 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2285 if (gimple_code (use_stmt
) != GIMPLE_PHI
2286 && def_bb
!= gimple_bb (use_stmt
)
2287 && !is_gimple_debug (use_stmt
)
2290 if (!zero_dim_array
)
2292 zero_dim_array
= create_zero_dim_array
2293 (def
, "Cross_BB_scalar_dependence");
2294 insert_out_of_ssa_copy (scop
, zero_dim_array
, def
,
2295 SSA_NAME_DEF_STMT (def
));
2299 rewrite_cross_bb_scalar_dependence (scop
, unshare_expr (zero_dim_array
),
2303 update_ssa (TODO_update_ssa
);
2308 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2311 rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop
)
2314 gimple_stmt_iterator psi
;
2315 sese region
= SCOP_REGION (scop
);
2316 bool changed
= false;
2318 /* Create an extra empty BB after the scop. */
2319 split_edge (SESE_EXIT (region
));
2321 FOR_EACH_BB_FN (bb
, cfun
)
2322 if (bb_in_sese_p (bb
, region
))
2323 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2324 changed
|= rewrite_cross_bb_scalar_deps (scop
, &psi
);
2329 update_ssa (TODO_update_ssa
);
2330 #ifdef ENABLE_CHECKING
2331 verify_loop_closed_ssa (true);
2336 /* Builds the polyhedral representation for a SESE region. */
2339 build_poly_scop (scop_p scop
)
2341 find_scop_parameters (scop
);
2343 graphite_dim_t max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
2344 if (scop_nb_params (scop
) > max_dim
)
2346 set_scop_parameter_dim (scop
);
2347 build_scop_iteration_domain (scop
);
2348 build_scop_context (scop
);
2349 add_conditions_to_constraints (scop
);
2351 /* Rewrite out of SSA only after having translated the
2352 representation to the polyhedral representation to avoid scev
2353 analysis failures. That means that these functions will insert
2354 new data references that they create in the right place. */
2355 rewrite_reductions_out_of_ssa (scop
);
2356 rewrite_cross_bb_scalar_deps_out_of_ssa (scop
);
2358 build_scop_drs (scop
);
2359 build_scop_scattering (scop
);
2361 /* This SCoP has been translated to the polyhedral
2363 POLY_SCOP_P (scop
) = true;
2365 #endif /* HAVE_isl */