1 /* Detection of Static Control Parts (SCoP) for Graphite.
2 Copyright (C) 2009-2019 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/>. */
29 #include "coretypes.h"
36 #include "fold-const.h"
37 #include "gimple-iterator.h"
39 #include "tree-ssa-loop-manip.h"
40 #include "tree-ssa-loop-niter.h"
41 #include "tree-ssa-loop.h"
42 #include "tree-into-ssa.h"
45 #include "tree-data-ref.h"
46 #include "tree-scalar-evolution.h"
47 #include "tree-pass.h"
48 #include "tree-ssa-propagate.h"
49 #include "gimple-pretty-print.h"
60 set_dump_file (FILE *f
)
66 friend debug_printer
&
67 operator<< (debug_printer
&output
, int i
)
69 fprintf (output
.dump_file
, "%d", i
);
72 friend debug_printer
&
73 operator<< (debug_printer
&output
, const char *s
)
75 fprintf (output
.dump_file
, "%s", s
);
80 #define DEBUG_PRINT(args) do \
82 if (dump_file && (dump_flags & TDF_DETAILS)) { args; } \
85 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
86 different colors. If there are not enough colors, paint the
87 remaining SCoPs in gray.
90 - "*" after the node number denotes the entry of a SCoP,
91 - "#" after the node number denotes the exit of a SCoP,
92 - "()" around the node number denotes the entry or the
93 exit nodes of the SCOP. These are not part of SCoP. */
96 dot_all_sese (FILE *file
, vec
<sese_l
>& scops
)
98 /* Disable debugging while printing graph. */
99 dump_flags_t tmp_dump_flags
= dump_flags
;
100 dump_flags
= TDF_NONE
;
102 fprintf (file
, "digraph all {\n");
105 FOR_ALL_BB_FN (bb
, cfun
)
107 int part_of_scop
= false;
109 /* Use HTML for every bb label. So we are able to print bbs
110 which are part of two different SCoPs, with two different
111 background colors. */
112 fprintf (file
, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
114 fprintf (file
, "CELLSPACING=\"0\">\n");
116 /* Select color for SCoP. */
119 FOR_EACH_VEC_ELT (scops
, i
, region
)
121 bool sese_in_region
= bb_in_sese_p (bb
, *region
);
122 if (sese_in_region
|| (region
->exit
->dest
== bb
)
123 || (region
->entry
->dest
== bb
))
183 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">",
187 fprintf (file
, " (");
189 if (bb
== region
->entry
->dest
&& bb
== region
->exit
->dest
)
190 fprintf (file
, " %d*# ", bb
->index
);
191 else if (bb
== region
->entry
->dest
)
192 fprintf (file
, " %d* ", bb
->index
);
193 else if (bb
== region
->exit
->dest
)
194 fprintf (file
, " %d# ", bb
->index
);
196 fprintf (file
, " %d ", bb
->index
);
198 fprintf (file
, "{lp_%d}", bb
->loop_father
->num
);
203 fprintf (file
, "</TD></TR>\n");
210 fprintf (file
, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
211 fprintf (file
, " %d {lp_%d} </TD></TR>\n", bb
->index
,
212 bb
->loop_father
->num
);
214 fprintf (file
, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
217 FOR_ALL_BB_FN (bb
, cfun
)
221 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
222 fprintf (file
, "%d -> %d;\n", bb
->index
, e
->dest
->index
);
225 fputs ("}\n\n", file
);
227 /* Enable debugging again. */
228 dump_flags
= tmp_dump_flags
;
231 /* Display SCoP on stderr. */
234 dot_sese (sese_l
& scop
)
240 scops
.safe_push (scop
);
242 dot_all_sese (stderr
, scops
);
252 dot_all_sese (stderr
, scops
);
256 /* Returns a COND_EXPR statement when BB has a single predecessor, the
257 edge between BB and its predecessor is not a loop exit edge, and
258 the last statement of the single predecessor is a COND_EXPR. */
261 single_pred_cond_non_loop_exit (basic_block bb
)
263 if (single_pred_p (bb
))
265 edge e
= single_pred_edge (bb
);
266 basic_block pred
= e
->src
;
269 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
272 stmt
= last_stmt (pred
);
274 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
275 return as_a
<gcond
*> (stmt
);
284 /* Build the maximal scop containing LOOPs and add it to SCOPS. */
289 scop_detection () : scops (vNULL
) {}
296 /* A marker for invalid sese_l. */
297 static sese_l invalid_sese
;
299 /* Return the SCOPS in this SCOP_DETECTION. */
307 /* Return an sese_l around the LOOP. */
309 sese_l
get_sese (loop_p loop
);
311 /* Merge scops at same loop depth and returns the new sese.
312 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
314 sese_l
merge_sese (sese_l first
, sese_l second
) const;
316 /* Build scop outer->inner if possible. */
318 void build_scop_depth (loop_p loop
);
320 /* Return true when BEGIN is the preheader edge of a loop with a single exit
323 static bool region_has_one_loop (sese_l s
);
325 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
327 void add_scop (sese_l s
);
329 /* Returns true if S1 subsumes/surrounds S2. */
330 static bool subsumes (sese_l s1
, sese_l s2
);
332 /* Remove a SCoP which is subsumed by S1. */
333 void remove_subscops (sese_l s1
);
335 /* Returns true if S1 intersects with S2. Since we already know that S1 does
336 not subsume S2 or vice-versa, we only check for entry bbs. */
338 static bool intersects (sese_l s1
, sese_l s2
);
340 /* Remove one of the scops when it intersects with any other. */
342 void remove_intersecting_scops (sese_l s1
);
344 /* Return true when a statement in SCOP cannot be represented by Graphite. */
346 bool harmful_loop_in_region (sese_l scop
) const;
348 /* Return true only when STMT is simple enough for being handled by Graphite.
349 This depends on SCOP, as the parameters are initialized relatively to
350 this basic block, the linear functions are initialized based on the
351 outermost loop containing STMT inside the SCOP. BB is the place where we
352 try to evaluate the STMT. */
354 bool stmt_simple_for_scop_p (sese_l scop
, gimple
*stmt
,
355 basic_block bb
) const;
357 /* Something like "n * m" is not allowed. */
359 static bool graphite_can_represent_init (tree e
);
361 /* Return true when SCEV can be represented in the polyhedral model.
363 An expression can be represented, if it can be expressed as an
364 affine expression. For loops (i, j) and parameters (m, n) all
365 affine expressions are of the form:
367 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
369 1 i + 20 j + (-2) m + 25
371 Something like "i * n" or "n * m" is not allowed. */
373 static bool graphite_can_represent_scev (sese_l scop
, tree scev
);
375 /* Return true when EXPR can be represented in the polyhedral model.
377 This means an expression can be represented, if it is linear with respect
378 to the loops and the strides are non parametric. LOOP is the place where
379 the expr will be evaluated. SCOP defines the region we analyse. */
381 static bool graphite_can_represent_expr (sese_l scop
, loop_p loop
,
384 /* Return true if the data references of STMT can be represented by Graphite.
385 We try to analyze the data references in a loop contained in the SCOP. */
387 static bool stmt_has_simple_data_refs_p (sese_l scop
, gimple
*stmt
);
389 /* Remove the close phi node at GSI and replace its rhs with the rhs
392 static void remove_duplicate_close_phi (gphi
*phi
, gphi_iterator
*gsi
);
394 /* Returns true when Graphite can represent LOOP in SCOP.
395 FIXME: For the moment, graphite cannot be used on loops that iterate using
396 induction variables that wrap. */
398 static bool can_represent_loop (loop_p loop
, sese_l scop
);
400 /* Returns the number of pbbs that are in loops contained in SCOP. */
402 static int nb_pbbs_in_loops (scop_p scop
);
408 sese_l
scop_detection::invalid_sese (NULL
, NULL
);
410 /* Return an sese_l around the LOOP. */
413 scop_detection::get_sese (loop_p loop
)
418 edge scop_begin
= loop_preheader_edge (loop
);
419 edge scop_end
= single_exit (loop
);
420 if (!scop_end
|| (scop_end
->flags
& (EDGE_COMPLEX
|EDGE_FAKE
)))
423 return sese_l (scop_begin
, scop_end
);
426 /* Merge scops at same loop depth and returns the new sese.
427 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
430 scop_detection::merge_sese (sese_l first
, sese_l second
) const
432 /* In the trivial case first/second may be NULL. */
438 DEBUG_PRINT (dp
<< "[scop-detection] try merging sese s1: ";
439 print_sese (dump_file
, first
);
440 dp
<< "[scop-detection] try merging sese s2: ";
441 print_sese (dump_file
, second
));
443 auto_bitmap worklist
, in_sese_region
;
444 bitmap_set_bit (worklist
, get_entry_bb (first
)->index
);
445 bitmap_set_bit (worklist
, get_exit_bb (first
)->index
);
446 bitmap_set_bit (worklist
, get_entry_bb (second
)->index
);
447 bitmap_set_bit (worklist
, get_exit_bb (second
)->index
);
448 edge entry
= NULL
, exit
= NULL
;
450 /* We can optimize the case of adding a loop entry dest or exit
451 src to the worklist (for single-exit loops) by skipping
452 directly to the exit dest / entry src. in_sese_region
453 doesn't have to cover all blocks in the region but merely
454 its border it acts more like a visited bitmap. */
457 int index
= bitmap_first_set_bit (worklist
);
458 bitmap_clear_bit (worklist
, index
);
459 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, index
);
463 /* With fake exit edges we can end up with no possible exit. */
464 if (index
== EXIT_BLOCK
)
466 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot merge seses.\n");
470 bitmap_set_bit (in_sese_region
, bb
->index
);
472 basic_block dom
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
473 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
476 || dominated_by_p (CDI_DOMINATORS
, entry
->dest
, bb
)))
479 && ! bitmap_bit_p (in_sese_region
, entry
->src
->index
))
480 bitmap_set_bit (worklist
, entry
->src
->index
);
483 else if (! bitmap_bit_p (in_sese_region
, e
->src
->index
))
484 bitmap_set_bit (worklist
, e
->src
->index
);
486 basic_block pdom
= get_immediate_dominator (CDI_POST_DOMINATORS
, bb
);
487 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
490 || dominated_by_p (CDI_POST_DOMINATORS
, exit
->src
, bb
)))
493 && ! bitmap_bit_p (in_sese_region
, exit
->dest
->index
))
494 bitmap_set_bit (worklist
, exit
->dest
->index
);
497 else if (! bitmap_bit_p (in_sese_region
, e
->dest
->index
))
498 bitmap_set_bit (worklist
, e
->dest
->index
);
500 while (! bitmap_empty_p (worklist
));
502 sese_l
combined (entry
, exit
);
504 DEBUG_PRINT (dp
<< "[merged-sese] s1: "; print_sese (dump_file
, combined
));
509 /* Build scop outer->inner if possible. */
512 scop_detection::build_scop_depth (loop_p loop
)
514 sese_l s
= invalid_sese
;
518 sese_l next
= get_sese (loop
);
520 || harmful_loop_in_region (next
))
524 build_scop_depth (loop
);
531 sese_l combined
= merge_sese (s
, next
);
533 || harmful_loop_in_region (combined
))
547 /* Returns true when Graphite can represent LOOP in SCOP.
548 FIXME: For the moment, graphite cannot be used on loops that iterate using
549 induction variables that wrap. */
552 scop_detection::can_represent_loop (loop_p loop
, sese_l scop
)
555 struct tree_niter_desc niter_desc
;
557 /* We can only handle do {} while () style loops correctly. */
558 edge exit
= single_exit (loop
);
560 || !single_pred_p (loop
->latch
)
561 || exit
->src
!= single_pred (loop
->latch
)
562 || !empty_block_p (loop
->latch
))
565 return !(loop_preheader_edge (loop
)->flags
& EDGE_IRREDUCIBLE_LOOP
)
566 && number_of_iterations_exit (loop
, single_exit (loop
), &niter_desc
, false)
567 && niter_desc
.control
.no_overflow
568 && (niter
= number_of_latch_executions (loop
))
569 && !chrec_contains_undetermined (niter
)
570 && graphite_can_represent_expr (scop
, loop
, niter
);
573 /* Return true when BEGIN is the preheader edge of a loop with a single exit
577 scop_detection::region_has_one_loop (sese_l s
)
579 edge begin
= s
.entry
;
581 /* Check for a single perfectly nested loop. */
582 if (begin
->dest
->loop_father
->inner
)
585 /* Otherwise, check whether we have adjacent loops. */
586 return (single_pred_p (end
->src
)
587 && begin
->dest
->loop_father
== single_pred (end
->src
)->loop_father
);
590 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
593 scop_detection::add_scop (sese_l s
)
597 /* If the exit edge is fake discard the SCoP for now as we're removing the
598 fake edges again after analysis. */
599 if (s
.exit
->flags
& EDGE_FAKE
)
601 DEBUG_PRINT (dp
<< "[scop-detection-fail] Discarding infinite loop SCoP: ";
602 print_sese (dump_file
, s
));
606 /* Include the BB with the loop-closed SSA PHI nodes, we need this
607 block in the region for code-generating out-of-SSA copies.
608 canonicalize_loop_closed_ssa makes sure that is in proper shape. */
609 if (s
.exit
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
610 && loop_exit_edge_p (s
.exit
->src
->loop_father
, s
.exit
))
612 gcc_assert (single_pred_p (s
.exit
->dest
)
613 && single_succ_p (s
.exit
->dest
)
614 && sese_trivially_empty_bb_p (s
.exit
->dest
));
615 s
.exit
= single_succ_edge (s
.exit
->dest
);
618 /* Do not add scops with only one loop. */
619 if (region_has_one_loop (s
))
621 DEBUG_PRINT (dp
<< "[scop-detection-fail] Discarding one loop SCoP: ";
622 print_sese (dump_file
, s
));
626 if (get_exit_bb (s
) == EXIT_BLOCK_PTR_FOR_FN (cfun
))
628 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
629 << "Discarding SCoP exiting to return: ";
630 print_sese (dump_file
, s
));
634 /* Remove all the scops which are subsumed by s. */
637 /* Remove intersecting scops. FIXME: It will be a good idea to keep
638 the non-intersecting part of the scop already in the list. */
639 remove_intersecting_scops (s
);
642 DEBUG_PRINT (dp
<< "[scop-detection] Adding SCoP: "; print_sese (dump_file
, s
));
645 /* Return true when a statement in SCOP cannot be represented by Graphite. */
648 scop_detection::harmful_loop_in_region (sese_l scop
) const
650 basic_block exit_bb
= get_exit_bb (scop
);
651 basic_block entry_bb
= get_entry_bb (scop
);
653 DEBUG_PRINT (dp
<< "[checking-harmful-bbs] ";
654 print_sese (dump_file
, scop
));
655 gcc_assert (dominated_by_p (CDI_DOMINATORS
, exit_bb
, entry_bb
));
657 auto_vec
<basic_block
> worklist
;
660 worklist
.safe_push (entry_bb
);
661 while (! worklist
.is_empty ())
663 basic_block bb
= worklist
.pop ();
664 DEBUG_PRINT (dp
<< "Visiting bb_" << bb
->index
<< "\n");
666 /* The basic block should not be part of an irreducible loop. */
667 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
670 /* Check for unstructured control flow: CFG not generated by structured
672 if (bb
->succs
->length () > 1)
676 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
677 if (!dominated_by_p (CDI_POST_DOMINATORS
, bb
, e
->dest
)
678 && !dominated_by_p (CDI_DOMINATORS
, e
->dest
, bb
))
682 /* Collect all loops in the current region. */
683 loop_p loop
= bb
->loop_father
;
684 if (loop_in_sese_p (loop
, scop
))
685 bitmap_set_bit (loops
, loop
->num
);
687 /* Check for harmful statements in basic blocks part of the region. */
688 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
689 !gsi_end_p (gsi
); gsi_next (&gsi
))
690 if (!stmt_simple_for_scop_p (scop
, gsi_stmt (gsi
), bb
))
693 for (basic_block dom
= first_dom_son (CDI_DOMINATORS
, bb
);
695 dom
= next_dom_son (CDI_DOMINATORS
, dom
))
696 if (dom
!= scop
.exit
->dest
)
697 worklist
.safe_push (dom
);
700 /* Go through all loops and check that they are still valid in the combined
704 EXECUTE_IF_SET_IN_BITMAP (loops
, 0, j
, bi
)
706 loop_p loop
= (*current_loops
->larray
)[j
];
707 gcc_assert (loop
->num
== (int) j
);
709 /* Check if the loop nests are to be optimized for speed. */
711 && ! optimize_loop_for_speed_p (loop
))
713 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_"
714 << loop
->num
<< " is not on a hot path.\n");
718 if (! can_represent_loop (loop
, scop
))
720 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot represent loop_"
721 << loop
->num
<< "\n");
725 /* Check if all loop nests have at least one data reference.
726 ??? This check is expensive and loops premature at this point.
727 If important to retain we can pre-compute this for all innermost
728 loops and reject those when we build a SESE region for a loop
729 during SESE discovery. */
731 && ! loop_nest_has_data_refs (loop
))
733 DEBUG_PRINT (dp
<< "[scop-detection-fail] loop_" << loop
->num
734 << "does not have any data reference.\n");
742 /* Returns true if S1 subsumes/surrounds S2. */
744 scop_detection::subsumes (sese_l s1
, sese_l s2
)
746 if (dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
748 && dominated_by_p (CDI_POST_DOMINATORS
, s2
.exit
->dest
,
754 /* Remove a SCoP which is subsumed by S1. */
756 scop_detection::remove_subscops (sese_l s1
)
760 FOR_EACH_VEC_ELT_REVERSE (scops
, j
, s2
)
762 if (subsumes (s1
, *s2
))
764 DEBUG_PRINT (dp
<< "Removing sub-SCoP";
765 print_sese (dump_file
, *s2
));
766 scops
.unordered_remove (j
);
771 /* Returns true if S1 intersects with S2. Since we already know that S1 does
772 not subsume S2 or vice-versa, we only check for entry bbs. */
775 scop_detection::intersects (sese_l s1
, sese_l s2
)
777 if (dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
779 && !dominated_by_p (CDI_DOMINATORS
, get_entry_bb (s2
),
782 if ((s1
.exit
== s2
.entry
) || (s2
.exit
== s1
.entry
))
788 /* Remove one of the scops when it intersects with any other. */
791 scop_detection::remove_intersecting_scops (sese_l s1
)
795 FOR_EACH_VEC_ELT_REVERSE (scops
, j
, s2
)
797 if (intersects (s1
, *s2
))
799 DEBUG_PRINT (dp
<< "Removing intersecting SCoP";
800 print_sese (dump_file
, *s2
);
801 dp
<< "Intersects with:";
802 print_sese (dump_file
, s1
));
803 scops
.unordered_remove (j
);
808 /* Something like "n * m" is not allowed. */
811 scop_detection::graphite_can_represent_init (tree e
)
813 switch (TREE_CODE (e
))
815 case POLYNOMIAL_CHREC
:
816 return graphite_can_represent_init (CHREC_LEFT (e
))
817 && graphite_can_represent_init (CHREC_RIGHT (e
));
820 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
821 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
822 && tree_fits_shwi_p (TREE_OPERAND (e
, 1));
824 return graphite_can_represent_init (TREE_OPERAND (e
, 1))
825 && tree_fits_shwi_p (TREE_OPERAND (e
, 0));
828 case POINTER_PLUS_EXPR
:
830 return graphite_can_represent_init (TREE_OPERAND (e
, 0))
831 && graphite_can_represent_init (TREE_OPERAND (e
, 1));
836 case NON_LVALUE_EXPR
:
837 return graphite_can_represent_init (TREE_OPERAND (e
, 0));
846 /* Return true when SCEV can be represented in the polyhedral model.
848 An expression can be represented, if it can be expressed as an
849 affine expression. For loops (i, j) and parameters (m, n) all
850 affine expressions are of the form:
852 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
854 1 i + 20 j + (-2) m + 25
856 Something like "i * n" or "n * m" is not allowed. */
859 scop_detection::graphite_can_represent_scev (sese_l scop
, tree scev
)
861 if (chrec_contains_undetermined (scev
))
864 switch (TREE_CODE (scev
))
869 case NON_LVALUE_EXPR
:
870 return graphite_can_represent_scev (scop
, TREE_OPERAND (scev
, 0));
873 case POINTER_PLUS_EXPR
:
875 return graphite_can_represent_scev (scop
, TREE_OPERAND (scev
, 0))
876 && graphite_can_represent_scev (scop
, TREE_OPERAND (scev
, 1));
879 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 0)))
880 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev
, 1)))
881 && !(chrec_contains_symbols (TREE_OPERAND (scev
, 0))
882 && chrec_contains_symbols (TREE_OPERAND (scev
, 1)))
883 && graphite_can_represent_init (scev
)
884 && graphite_can_represent_scev (scop
, TREE_OPERAND (scev
, 0))
885 && graphite_can_represent_scev (scop
, TREE_OPERAND (scev
, 1));
887 case POLYNOMIAL_CHREC
:
888 /* Check for constant strides. With a non constant stride of
889 'n' we would have a value of 'iv * n'. Also check that the
890 initial value can represented: for example 'n * m' cannot be
892 gcc_assert (loop_in_sese_p (get_loop (cfun
,
893 CHREC_VARIABLE (scev
)), scop
));
894 if (!evolution_function_right_is_integer_cst (scev
)
895 || !graphite_can_represent_init (scev
))
897 return graphite_can_represent_scev (scop
, CHREC_LEFT (scev
));
900 /* We cannot encode addresses for ISL. */
907 /* Only affine functions can be represented. */
908 if (tree_contains_chrecs (scev
, NULL
) || !scev_is_linear_expression (scev
))
914 /* Return true when EXPR can be represented in the polyhedral model.
916 This means an expression can be represented, if it is linear with respect to
917 the loops and the strides are non parametric. LOOP is the place where the
918 expr will be evaluated. SCOP defines the region we analyse. */
921 scop_detection::graphite_can_represent_expr (sese_l scop
, loop_p loop
,
924 tree scev
= cached_scalar_evolution_in_region (scop
, loop
, expr
);
925 return graphite_can_represent_scev (scop
, scev
);
928 /* Return true if the data references of STMT can be represented by Graphite.
929 We try to analyze the data references in a loop contained in the SCOP. */
932 scop_detection::stmt_has_simple_data_refs_p (sese_l scop
, gimple
*stmt
)
934 edge nest
= scop
.entry
;
935 loop_p loop
= loop_containing_stmt (stmt
);
936 if (!loop_in_sese_p (loop
, scop
))
939 auto_vec
<data_reference_p
> drs
;
940 if (! graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
))
945 FOR_EACH_VEC_ELT (drs
, j
, dr
)
947 for (unsigned i
= 0; i
< DR_NUM_DIMENSIONS (dr
); ++i
)
948 if (! graphite_can_represent_scev (scop
, DR_ACCESS_FN (dr
, i
)))
955 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
956 Calls have side-effects, except those to const or pure
960 stmt_has_side_effects (gimple
*stmt
)
962 if (gimple_has_volatile_ops (stmt
)
963 || (gimple_code (stmt
) == GIMPLE_CALL
964 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
965 || (gimple_code (stmt
) == GIMPLE_ASM
))
967 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
968 << "Statement has side-effects:\n";
969 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
));
975 /* Return true only when STMT is simple enough for being handled by Graphite.
976 This depends on SCOP, as the parameters are initialized relatively to
977 this basic block, the linear functions are initialized based on the outermost
978 loop containing STMT inside the SCOP. BB is the place where we try to
979 evaluate the STMT. */
982 scop_detection::stmt_simple_for_scop_p (sese_l scop
, gimple
*stmt
,
983 basic_block bb
) const
987 if (is_gimple_debug (stmt
))
990 if (stmt_has_side_effects (stmt
))
993 if (!stmt_has_simple_data_refs_p (scop
, stmt
))
995 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
996 << "Graphite cannot handle data-refs in stmt:\n";
997 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
|TDF_MEMSYMS
););
1001 switch (gimple_code (stmt
))
1008 /* We can handle all binary comparisons. Inequalities are
1009 also supported as they can be represented with union of
1011 enum tree_code code
= gimple_cond_code (stmt
);
1012 if (!(code
== LT_EXPR
1017 || code
== NE_EXPR
))
1019 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1020 << "Graphite cannot handle cond stmt:\n";
1021 print_gimple_stmt (dump_file
, stmt
, 0,
1022 TDF_VOPS
| TDF_MEMSYMS
));
1026 loop_p loop
= bb
->loop_father
;
1027 for (unsigned i
= 0; i
< 2; ++i
)
1029 tree op
= gimple_op (stmt
, i
);
1030 if (!graphite_can_represent_expr (scop
, loop
, op
)
1031 /* We can only constrain on integer type. */
1032 || ! INTEGRAL_TYPE_P (TREE_TYPE (op
)))
1034 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1035 << "Graphite cannot represent stmt:\n";
1036 print_gimple_stmt (dump_file
, stmt
, 0,
1037 TDF_VOPS
| TDF_MEMSYMS
));
1048 tree op
, lhs
= gimple_get_lhs (stmt
);
1050 /* If we are not going to instantiate the stmt do not require
1051 its operands to be instantiatable at this point. */
1053 && TREE_CODE (lhs
) == SSA_NAME
1054 && scev_analyzable_p (lhs
, scop
))
1056 /* Verify that if we can analyze operands at their def site we
1057 also can represent them when analyzed at their uses. */
1058 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, i
, SSA_OP_USE
)
1059 if (scev_analyzable_p (op
, scop
)
1060 && chrec_contains_undetermined
1061 (cached_scalar_evolution_in_region (scop
,
1062 bb
->loop_father
, op
)))
1064 DEBUG_PRINT (dp
<< "[scop-detection-fail] "
1065 << "Graphite cannot code-gen stmt:\n";
1066 print_gimple_stmt (dump_file
, stmt
, 0,
1067 TDF_VOPS
| TDF_MEMSYMS
));
1074 /* These nodes cut a new scope. */
1076 dp
<< "[scop-detection-fail] "
1077 << "Gimple stmt not handled in Graphite:\n";
1078 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
));
1083 /* Returns the number of pbbs that are in loops contained in SCOP. */
1086 scop_detection::nb_pbbs_in_loops (scop_p scop
)
1092 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
1093 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), scop
->scop_info
->region
))
1099 /* Assigns the parameter NAME an index in REGION. */
1102 assign_parameter_index_in_region (tree name
, sese_info_p region
)
1104 gcc_assert (TREE_CODE (name
) == SSA_NAME
1105 && INTEGRAL_TYPE_P (TREE_TYPE (name
))
1106 && ! defined_in_sese_p (name
, region
->region
));
1109 FOR_EACH_VEC_ELT (region
->params
, i
, p
)
1113 region
->params
.safe_push (name
);
1116 /* In the context of sese S, scan the expression E and translate it to
1117 a linear expression C. When parsing a symbolic multiplication, K
1118 represents the constant multiplier of an expression containing
1122 scan_tree_for_params (sese_info_p s
, tree e
)
1124 if (e
== chrec_dont_know
)
1127 switch (TREE_CODE (e
))
1129 case POLYNOMIAL_CHREC
:
1130 scan_tree_for_params (s
, CHREC_LEFT (e
));
1134 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
1135 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1137 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
1141 case POINTER_PLUS_EXPR
:
1143 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1144 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
1150 case NON_LVALUE_EXPR
:
1151 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
1155 assign_parameter_index_in_region (e
, s
);
1171 /* Find parameters with respect to REGION in BB. We are looking in memory
1172 access functions, conditions and loop bounds. */
1175 find_params_in_bb (sese_info_p region
, gimple_poly_bb_p gbb
)
1177 /* Find parameters in the access functions of data references. */
1179 data_reference_p dr
;
1180 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
1181 for (unsigned j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
1182 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
));
1184 /* Find parameters in conditional statements. */
1186 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
1188 loop_p loop
= gimple_bb (stmt
)->loop_father
;
1189 tree lhs
= cached_scalar_evolution_in_region (region
->region
, loop
,
1190 gimple_cond_lhs (stmt
));
1191 tree rhs
= cached_scalar_evolution_in_region (region
->region
, loop
,
1192 gimple_cond_rhs (stmt
));
1193 gcc_assert (!chrec_contains_undetermined (lhs
)
1194 && !chrec_contains_undetermined (rhs
));
1196 scan_tree_for_params (region
, lhs
);
1197 scan_tree_for_params (region
, rhs
);
1201 /* Record the parameters used in the SCOP BBs. A variable is a parameter
1202 in a scop if it does not vary during the execution of that scop. */
1205 find_scop_parameters (scop_p scop
)
1208 sese_info_p region
= scop
->scop_info
;
1210 /* Parameters used in loop bounds are processed during gather_bbs. */
1212 /* Find the parameters used in data accesses. */
1214 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
1215 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
1217 int nbp
= sese_nb_params (region
);
1218 scop_set_nb_params (scop
, nbp
);
1222 add_write (vec
<tree
> *writes
, tree def
)
1224 writes
->safe_push (def
);
1225 DEBUG_PRINT (dp
<< "Adding scalar write: ";
1226 print_generic_expr (dump_file
, def
);
1227 dp
<< "\nFrom stmt: ";
1228 print_gimple_stmt (dump_file
,
1229 SSA_NAME_DEF_STMT (def
), 0));
1233 add_read (vec
<scalar_use
> *reads
, tree use
, gimple
*use_stmt
)
1235 DEBUG_PRINT (dp
<< "Adding scalar read: ";
1236 print_generic_expr (dump_file
, use
);
1237 dp
<< "\nFrom stmt: ";
1238 print_gimple_stmt (dump_file
, use_stmt
, 0));
1239 reads
->safe_push (std::make_pair (use_stmt
, use
));
1243 /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP. */
1246 build_cross_bb_scalars_def (scop_p scop
, tree def
, basic_block def_bb
,
1249 if (!is_gimple_reg (def
))
1252 bool scev_analyzable
= scev_analyzable_p (def
, scop
->scop_info
->region
);
1255 imm_use_iterator imm_iter
;
1256 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1257 /* Do not gather scalar variables that can be analyzed by SCEV as they can
1258 be generated out of the induction variables. */
1259 if ((! scev_analyzable
1260 /* But gather SESE liveouts as we otherwise fail to rewrite their
1262 || ! bb_in_sese_p (gimple_bb (use_stmt
), scop
->scop_info
->region
))
1263 && (def_bb
!= gimple_bb (use_stmt
) && !is_gimple_debug (use_stmt
)))
1265 add_write (writes
, def
);
1266 /* This is required by the FOR_EACH_IMM_USE_STMT when we want to break
1267 before all the uses have been visited. */
1268 BREAK_FROM_IMM_USE_STMT (imm_iter
);
1272 /* Record USE if it is defined in other bbs different than USE_STMT
1276 build_cross_bb_scalars_use (scop_p scop
, tree use
, gimple
*use_stmt
,
1277 vec
<scalar_use
> *reads
)
1279 if (!is_gimple_reg (use
))
1282 /* Do not gather scalar variables that can be analyzed by SCEV as they can be
1283 generated out of the induction variables. */
1284 if (scev_analyzable_p (use
, scop
->scop_info
->region
))
1287 gimple
*def_stmt
= SSA_NAME_DEF_STMT (use
);
1288 if (gimple_bb (def_stmt
) != gimple_bb (use_stmt
))
1289 add_read (reads
, use
, use_stmt
);
1292 /* Generates a polyhedral black box only if the bb contains interesting
1295 static gimple_poly_bb_p
1296 try_generate_gimple_bb (scop_p scop
, basic_block bb
)
1298 vec
<data_reference_p
> drs
= vNULL
;
1299 vec
<tree
> writes
= vNULL
;
1300 vec
<scalar_use
> reads
= vNULL
;
1302 sese_l region
= scop
->scop_info
->region
;
1303 edge nest
= region
.entry
;
1304 loop_p loop
= bb
->loop_father
;
1305 if (!loop_in_sese_p (loop
, region
))
1308 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1311 gimple
*stmt
= gsi_stmt (gsi
);
1312 if (is_gimple_debug (stmt
))
1315 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
1317 tree def
= gimple_get_lhs (stmt
);
1319 build_cross_bb_scalars_def (scop
, def
, gimple_bb (stmt
), &writes
);
1323 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
1324 build_cross_bb_scalars_use (scop
, use
, stmt
, &reads
);
1327 /* Handle defs and uses in PHIs. Those need special treatment given
1328 that we have to present ISL with sth that looks like we've rewritten
1329 the IL out-of-SSA. */
1330 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1333 gphi
*phi
= psi
.phi ();
1334 tree res
= gimple_phi_result (phi
);
1335 if (virtual_operand_p (res
)
1336 || scev_analyzable_p (res
, scop
->scop_info
->region
))
1338 /* To simulate out-of-SSA the block containing the PHI node has
1339 reads of the PHI destination. And to preserve SSA dependences
1340 we also write to it (the out-of-SSA decl and the SSA result
1341 are coalesced for dependence purposes which is good enough). */
1342 add_read (&reads
, res
, phi
);
1343 add_write (&writes
, res
);
1345 basic_block bb_for_succs
= bb
;
1346 if (bb_for_succs
== bb_for_succs
->loop_father
->latch
1347 && bb_in_sese_p (bb_for_succs
, scop
->scop_info
->region
)
1348 && sese_trivially_empty_bb_p (bb_for_succs
))
1349 bb_for_succs
= NULL
;
1350 while (bb_for_succs
)
1352 basic_block latch
= NULL
;
1355 FOR_EACH_EDGE (e
, ei
, bb_for_succs
->succs
)
1357 for (gphi_iterator psi
= gsi_start_phis (e
->dest
); !gsi_end_p (psi
);
1360 gphi
*phi
= psi
.phi ();
1361 tree res
= gimple_phi_result (phi
);
1362 if (virtual_operand_p (res
))
1364 /* To simulate out-of-SSA the predecessor of edges into PHI nodes
1365 has a copy from the PHI argument to the PHI destination. */
1366 if (! scev_analyzable_p (res
, scop
->scop_info
->region
))
1367 add_write (&writes
, res
);
1368 tree use
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
1369 if (TREE_CODE (use
) == SSA_NAME
1370 && ! SSA_NAME_IS_DEFAULT_DEF (use
)
1371 && gimple_bb (SSA_NAME_DEF_STMT (use
)) != bb_for_succs
1372 && ! scev_analyzable_p (use
, scop
->scop_info
->region
))
1373 add_read (&reads
, use
, phi
);
1375 if (e
->dest
== bb_for_succs
->loop_father
->latch
1376 && bb_in_sese_p (e
->dest
, scop
->scop_info
->region
)
1377 && sese_trivially_empty_bb_p (e
->dest
))
1380 /* Handle empty latch block PHIs here, otherwise we confuse ISL
1381 with extra conditional code where it then peels off the last
1382 iteration just because of that. It would be simplest if we
1383 just didn't force simple latches (thus remove the forwarder). */
1384 bb_for_succs
= latch
;
1387 /* For the region exit block add reads for all live-out vars. */
1388 if (bb
== scop
->scop_info
->region
.exit
->src
)
1390 sese_build_liveouts (scop
->scop_info
);
1393 EXECUTE_IF_SET_IN_BITMAP (scop
->scop_info
->liveout
, 0, i
, bi
)
1395 tree use
= ssa_name (i
);
1396 add_read (&reads
, use
, NULL
);
1400 if (drs
.is_empty () && writes
.is_empty () && reads
.is_empty ())
1403 return new_gimple_poly_bb (bb
, drs
, reads
, writes
);
1406 /* Compute alias-sets for all data references in DRS. */
1409 build_alias_set (scop_p scop
)
1411 int num_vertices
= scop
->drs
.length ();
1412 struct graph
*g
= new_graph (num_vertices
);
1418 = find_common_loop (scop
->scop_info
->region
.entry
->dest
->loop_father
,
1419 scop
->scop_info
->region
.exit
->src
->loop_father
);
1421 FOR_EACH_VEC_ELT (scop
->drs
, i
, dr1
)
1422 for (j
= i
+1; scop
->drs
.iterate (j
, &dr2
); j
++)
1423 if (dr_may_alias_p (dr1
->dr
, dr2
->dr
, nest
))
1425 /* Dependences in the same alias set need to be handled
1426 by just looking at DR_ACCESS_FNs. */
1427 if (DR_NUM_DIMENSIONS (dr1
->dr
) == 0
1428 || DR_NUM_DIMENSIONS (dr1
->dr
) != DR_NUM_DIMENSIONS (dr2
->dr
)
1429 || ! operand_equal_p (DR_BASE_OBJECT (dr1
->dr
),
1430 DR_BASE_OBJECT (dr2
->dr
),
1432 || ! types_compatible_p (TREE_TYPE (DR_BASE_OBJECT (dr1
->dr
)),
1433 TREE_TYPE (DR_BASE_OBJECT (dr2
->dr
))))
1442 all_vertices
= XNEWVEC (int, num_vertices
);
1443 for (i
= 0; i
< num_vertices
; i
++)
1444 all_vertices
[i
] = i
;
1447 = graphds_dfs (g
, all_vertices
, num_vertices
, NULL
, true, NULL
) + 1;
1448 free (all_vertices
);
1450 for (i
= 0; i
< g
->n_vertices
; i
++)
1451 scop
->drs
[i
].alias_set
= g
->vertices
[i
].component
+ 1;
1457 /* Gather BBs and conditions for a SCOP. */
1458 class gather_bbs
: public dom_walker
1461 gather_bbs (cdi_direction
, scop_p
, int *);
1463 virtual edge
before_dom_children (basic_block
);
1464 virtual void after_dom_children (basic_block
);
1467 auto_vec
<gimple
*, 3> conditions
, cases
;
1471 gather_bbs::gather_bbs (cdi_direction direction
, scop_p scop
, int *bb_to_rpo
)
1472 : dom_walker (direction
, ALL_BLOCKS
, bb_to_rpo
), scop (scop
)
1476 /* Call-back for dom_walk executed before visiting the dominated
1480 gather_bbs::before_dom_children (basic_block bb
)
1482 sese_info_p region
= scop
->scop_info
;
1483 if (!bb_in_sese_p (bb
, region
->region
))
1484 return dom_walker::STOP
;
1486 /* For loops fully contained in the region record parameters in the
1488 loop_p loop
= bb
->loop_father
;
1489 if (loop
->header
== bb
1490 && loop_in_sese_p (loop
, region
->region
))
1492 tree nb_iters
= number_of_latch_executions (loop
);
1493 if (chrec_contains_symbols (nb_iters
))
1495 nb_iters
= cached_scalar_evolution_in_region (region
->region
,
1497 scan_tree_for_params (region
, nb_iters
);
1501 if (gcond
*stmt
= single_pred_cond_non_loop_exit (bb
))
1503 edge e
= single_pred_edge (bb
);
1504 /* Make sure the condition is in the region and thus was verified
1506 if (e
!= region
->region
.entry
)
1508 conditions
.safe_push (stmt
);
1509 if (e
->flags
& EDGE_TRUE_VALUE
)
1510 cases
.safe_push (stmt
);
1512 cases
.safe_push (NULL
);
1516 scop
->scop_info
->bbs
.safe_push (bb
);
1518 gimple_poly_bb_p gbb
= try_generate_gimple_bb (scop
, bb
);
1522 GBB_CONDITIONS (gbb
) = conditions
.copy ();
1523 GBB_CONDITION_CASES (gbb
) = cases
.copy ();
1525 poly_bb_p pbb
= new_poly_bb (scop
, gbb
);
1526 scop
->pbbs
.safe_push (pbb
);
1529 data_reference_p dr
;
1530 FOR_EACH_VEC_ELT (gbb
->data_refs
, i
, dr
)
1532 DEBUG_PRINT (dp
<< "Adding memory ";
1537 print_generic_expr (dump_file
, dr
->ref
);
1538 dp
<< "\nFrom stmt: ";
1539 print_gimple_stmt (dump_file
, dr
->stmt
, 0));
1541 scop
->drs
.safe_push (dr_info (dr
, pbb
));
1547 /* Call-back for dom_walk executed after visiting the dominated
1551 gather_bbs::after_dom_children (basic_block bb
)
1553 if (!bb_in_sese_p (bb
, scop
->scop_info
->region
))
1556 if (single_pred_cond_non_loop_exit (bb
))
1558 edge e
= single_pred_edge (bb
);
1559 if (e
!= scop
->scop_info
->region
.entry
)
1568 /* Compute sth like an execution order, dominator order with first executing
1569 edges that stay inside the current loop, delaying processing exit edges. */
1571 static int *bb_to_rpo
;
1573 /* Helper for qsort, sorting after order above. */
1576 cmp_pbbs (const void *pa
, const void *pb
)
1578 poly_bb_p bb1
= *((const poly_bb_p
*)pa
);
1579 poly_bb_p bb2
= *((const poly_bb_p
*)pb
);
1580 if (bb_to_rpo
[bb1
->black_box
->bb
->index
]
1581 < bb_to_rpo
[bb2
->black_box
->bb
->index
])
1583 else if (bb_to_rpo
[bb1
->black_box
->bb
->index
]
1584 > bb_to_rpo
[bb2
->black_box
->bb
->index
])
1590 /* Find Static Control Parts (SCoP) in the current function and pushes
1594 build_scops (vec
<scop_p
> *scops
)
1597 dp
.set_dump_file (dump_file
);
1600 sb
.build_scop_depth (current_loops
->tree_root
);
1602 /* Now create scops from the lightweight SESEs. */
1603 vec
<sese_l
> scops_l
= sb
.get_scops ();
1605 /* Domwalk needs a bb to RPO mapping. Compute it once here. */
1606 int *postorder
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
1607 int postorder_num
= pre_and_rev_post_order_compute (NULL
, postorder
, true);
1608 bb_to_rpo
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
1609 for (int i
= 0; i
< postorder_num
; ++i
)
1610 bb_to_rpo
[postorder
[i
]] = i
;
1615 FOR_EACH_VEC_ELT (scops_l
, i
, s
)
1617 scop_p scop
= new_scop (s
->entry
, s
->exit
);
1619 /* Record all basic blocks and their conditions in REGION. */
1620 gather_bbs (CDI_DOMINATORS
, scop
, bb_to_rpo
).walk (s
->entry
->dest
);
1622 /* Sort pbbs after execution order for initial schedule generation. */
1623 scop
->pbbs
.qsort (cmp_pbbs
);
1625 if (! build_alias_set (scop
))
1627 DEBUG_PRINT (dp
<< "[scop-detection-fail] cannot handle dependences\n");
1632 /* Do not optimize a scop containing only PBBs that do not belong
1634 if (sb
.nb_pbbs_in_loops (scop
) == 0)
1636 DEBUG_PRINT (dp
<< "[scop-detection-fail] no data references.\n");
1641 unsigned max_arrays
= param_graphite_max_arrays_per_scop
;
1643 && scop
->drs
.length () >= max_arrays
)
1645 DEBUG_PRINT (dp
<< "[scop-detection-fail] too many data references: "
1646 << scop
->drs
.length ()
1647 << " is larger than --param graphite-max-arrays-per-scop="
1648 << max_arrays
<< ".\n");
1653 find_scop_parameters (scop
);
1654 graphite_dim_t max_dim
= param_graphite_max_nb_scop_params
;
1656 && scop_nb_params (scop
) > max_dim
)
1658 DEBUG_PRINT (dp
<< "[scop-detection-fail] too many parameters: "
1659 << scop_nb_params (scop
)
1660 << " larger than --param graphite-max-nb-scop-params="
1661 << max_dim
<< ".\n");
1666 scops
->safe_push (scop
);
1671 DEBUG_PRINT (dp
<< "number of SCoPs: " << (scops
? scops
->length () : 0););
1674 #endif /* HAVE_isl */