comparison gcc/graphite-scop-detection.c @ 16:04ced10e8804

gcc 7
author kono
date Fri, 27 Oct 2017 22:46:09 +0900
parents f6334be47118
children 84e7813d76e9
comparison
equal deleted inserted replaced
15:561a7518be6b 16:04ced10e8804
1 /* Detection of Static Control Parts (SCoP) for Graphite. 1 /* Detection of Static Control Parts (SCoP) for Graphite.
2 Copyright (C) 2009, 2010 Free Software Foundation, Inc. 2 Copyright (C) 2009-2017 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@amd.com> and 3 Contributed by Sebastian Pop <sebastian.pop@amd.com> and
4 Tobias Grosser <grosser@fim.uni-passau.de>. 4 Tobias Grosser <grosser@fim.uni-passau.de>.
5 5
6 This file is part of GCC. 6 This file is part of GCC.
7 7
17 17
18 You should have received a copy of the GNU General Public License 18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see 19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */ 20 <http://www.gnu.org/licenses/>. */
21 21
22 #define USES_ISL
23
22 #include "config.h" 24 #include "config.h"
25
26 #ifdef HAVE_isl
27
23 #include "system.h" 28 #include "system.h"
24 #include "coretypes.h" 29 #include "coretypes.h"
25 #include "tree-flow.h" 30 #include "backend.h"
31 #include "cfghooks.h"
32 #include "domwalk.h"
33 #include "params.h"
34 #include "tree.h"
35 #include "gimple.h"
36 #include "ssa.h"
37 #include "fold-const.h"
38 #include "gimple-iterator.h"
39 #include "tree-cfg.h"
40 #include "tree-ssa-loop-manip.h"
41 #include "tree-ssa-loop-niter.h"
42 #include "tree-ssa-loop.h"
43 #include "tree-into-ssa.h"
44 #include "tree-ssa.h"
26 #include "cfgloop.h" 45 #include "cfgloop.h"
27 #include "tree-chrec.h"
28 #include "tree-data-ref.h" 46 #include "tree-data-ref.h"
29 #include "tree-scalar-evolution.h" 47 #include "tree-scalar-evolution.h"
30 #include "tree-pass.h" 48 #include "tree-pass.h"
31 #include "sese.h" 49 #include "tree-ssa-propagate.h"
32 50 #include "gimple-pretty-print.h"
33 #ifdef HAVE_cloog 51 #include "cfganal.h"
34 #include "ppl_c.h" 52 #include "graphite.h"
35 #include "graphite-ppl.h" 53
36 #include "graphite-poly.h" 54 class debug_printer
37 #include "graphite-scop-detection.h" 55 {
38 56 private:
39 /* The type of the analyzed basic block. */ 57 FILE *dump_file;
40 58
41 typedef enum gbb_type { 59 public:
42 GBB_UNKNOWN, 60 void
43 GBB_LOOP_SING_EXIT_HEADER, 61 set_dump_file (FILE *f)
44 GBB_LOOP_MULT_EXIT_HEADER, 62 {
45 GBB_LOOP_EXIT, 63 gcc_assert (f);
46 GBB_COND_HEADER, 64 dump_file = f;
47 GBB_SIMPLE, 65 }
48 GBB_LAST 66
49 } gbb_type; 67 friend debug_printer &
50 68 operator<< (debug_printer &output, int i)
51 /* Detect the type of BB. Loop headers are only marked, if they are 69 {
52 new. This means their loop_father is different to LAST_LOOP. 70 fprintf (output.dump_file, "%d", i);
53 Otherwise they are treated like any other bb and their type can be 71 return output;
54 any other type. */ 72 }
55 73 friend debug_printer &
56 static gbb_type 74 operator<< (debug_printer &output, const char *s)
57 get_bb_type (basic_block bb, struct loop *last_loop) 75 {
58 { 76 fprintf (output.dump_file, "%s", s);
59 VEC (basic_block, heap) *dom; 77 return output;
60 int nb_dom, nb_suc; 78 }
61 struct loop *loop = bb->loop_father; 79 } dp;
62 80
63 /* Check, if we entry into a new loop. */ 81 #define DEBUG_PRINT(args) do \
64 if (loop != last_loop) 82 { \
65 { 83 if (dump_file && (dump_flags & TDF_DETAILS)) { args; } \
66 if (single_exit (loop) != NULL) 84 } while (0);
67 return GBB_LOOP_SING_EXIT_HEADER;
68 else if (loop->num != 0)
69 return GBB_LOOP_MULT_EXIT_HEADER;
70 else
71 return GBB_COND_HEADER;
72 }
73
74 dom = get_dominated_by (CDI_DOMINATORS, bb);
75 nb_dom = VEC_length (basic_block, dom);
76 VEC_free (basic_block, heap, dom);
77
78 if (nb_dom == 0)
79 return GBB_LAST;
80
81 nb_suc = VEC_length (edge, bb->succs);
82
83 if (nb_dom == 1 && nb_suc == 1)
84 return GBB_SIMPLE;
85
86 return GBB_COND_HEADER;
87 }
88
89 /* A SCoP detection region, defined using bbs as borders.
90
91 All control flow touching this region, comes in passing basic_block
92 ENTRY and leaves passing basic_block EXIT. By using bbs instead of
93 edges for the borders we are able to represent also regions that do
94 not have a single entry or exit edge.
95
96 But as they have a single entry basic_block and a single exit
97 basic_block, we are able to generate for every sd_region a single
98 entry and exit edge.
99
100 1 2
101 \ /
102 3 <- entry
103 |
104 4
105 / \ This region contains: {3, 4, 5, 6, 7, 8}
106 5 6
107 | |
108 7 8
109 \ /
110 9 <- exit */
111
112
113 typedef struct sd_region_p
114 {
115 /* The entry bb dominates all bbs in the sd_region. It is part of
116 the region. */
117 basic_block entry;
118
119 /* The exit bb postdominates all bbs in the sd_region, but is not
120 part of the region. */
121 basic_block exit;
122 } sd_region;
123
124 DEF_VEC_O(sd_region);
125 DEF_VEC_ALLOC_O(sd_region, heap);
126
127
128 /* Moves the scops from SOURCE to TARGET and clean up SOURCE. */
129
130 static void
131 move_sd_regions (VEC (sd_region, heap) **source,
132 VEC (sd_region, heap) **target)
133 {
134 sd_region *s;
135 int i;
136
137 FOR_EACH_VEC_ELT (sd_region, *source, i, s)
138 VEC_safe_push (sd_region, heap, *target, s);
139
140 VEC_free (sd_region, heap, *source);
141 }
142
143 /* Something like "n * m" is not allowed. */
144
145 static bool
146 graphite_can_represent_init (tree e)
147 {
148 switch (TREE_CODE (e))
149 {
150 case POLYNOMIAL_CHREC:
151 return graphite_can_represent_init (CHREC_LEFT (e))
152 && graphite_can_represent_init (CHREC_RIGHT (e));
153
154 case MULT_EXPR:
155 if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
156 return graphite_can_represent_init (TREE_OPERAND (e, 0))
157 && host_integerp (TREE_OPERAND (e, 1), 0);
158 else
159 return graphite_can_represent_init (TREE_OPERAND (e, 1))
160 && host_integerp (TREE_OPERAND (e, 0), 0);
161
162 case PLUS_EXPR:
163 case POINTER_PLUS_EXPR:
164 case MINUS_EXPR:
165 return graphite_can_represent_init (TREE_OPERAND (e, 0))
166 && graphite_can_represent_init (TREE_OPERAND (e, 1));
167
168 case NEGATE_EXPR:
169 case BIT_NOT_EXPR:
170 CASE_CONVERT:
171 case NON_LVALUE_EXPR:
172 return graphite_can_represent_init (TREE_OPERAND (e, 0));
173
174 default:
175 break;
176 }
177
178 return true;
179 }
180
181 /* Return true when SCEV can be represented in the polyhedral model.
182
183 An expression can be represented, if it can be expressed as an
184 affine expression. For loops (i, j) and parameters (m, n) all
185 affine expressions are of the form:
186
187 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
188
189 1 i + 20 j + (-2) m + 25
190
191 Something like "i * n" or "n * m" is not allowed. */
192
193 static bool
194 graphite_can_represent_scev (tree scev)
195 {
196 if (chrec_contains_undetermined (scev))
197 return false;
198
199 switch (TREE_CODE (scev))
200 {
201 case PLUS_EXPR:
202 case MINUS_EXPR:
203 return graphite_can_represent_scev (TREE_OPERAND (scev, 0))
204 && graphite_can_represent_scev (TREE_OPERAND (scev, 1));
205
206 case MULT_EXPR:
207 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 0)))
208 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 1)))
209 && !(chrec_contains_symbols (TREE_OPERAND (scev, 0))
210 && chrec_contains_symbols (TREE_OPERAND (scev, 1)))
211 && graphite_can_represent_init (scev)
212 && graphite_can_represent_scev (TREE_OPERAND (scev, 0))
213 && graphite_can_represent_scev (TREE_OPERAND (scev, 1));
214
215 case POLYNOMIAL_CHREC:
216 /* Check for constant strides. With a non constant stride of
217 'n' we would have a value of 'iv * n'. Also check that the
218 initial value can represented: for example 'n * m' cannot be
219 represented. */
220 if (!evolution_function_right_is_integer_cst (scev)
221 || !graphite_can_represent_init (scev))
222 return false;
223
224 default:
225 break;
226 }
227
228 /* Only affine functions can be represented. */
229 if (!scev_is_linear_expression (scev))
230 return false;
231
232 return true;
233 }
234
235
236 /* Return true when EXPR can be represented in the polyhedral model.
237
238 This means an expression can be represented, if it is linear with
239 respect to the loops and the strides are non parametric.
240 LOOP is the place where the expr will be evaluated. SCOP_ENTRY defines the
241 entry of the region we analyse. */
242
243 static bool
244 graphite_can_represent_expr (basic_block scop_entry, loop_p loop,
245 tree expr)
246 {
247 tree scev = analyze_scalar_evolution (loop, expr);
248
249 scev = instantiate_scev (scop_entry, loop, scev);
250
251 return graphite_can_represent_scev (scev);
252 }
253
254 /* Return true if the data references of STMT can be represented by
255 Graphite. */
256
257 static bool
258 stmt_has_simple_data_refs_p (loop_p outermost_loop, gimple stmt)
259 {
260 data_reference_p dr;
261 unsigned i;
262 int j;
263 bool res = true;
264 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5);
265
266 graphite_find_data_references_in_stmt (outermost_loop,
267 loop_containing_stmt (stmt),
268 stmt, &drs);
269
270 FOR_EACH_VEC_ELT (data_reference_p, drs, j, dr)
271 for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
272 if (!graphite_can_represent_scev (DR_ACCESS_FN (dr, i)))
273 {
274 res = false;
275 goto done;
276 }
277
278 done:
279 free_data_refs (drs);
280 return res;
281 }
282
283 /* Return true only when STMT is simple enough for being handled by
284 Graphite. This depends on SCOP_ENTRY, as the parameters are
285 initialized relatively to this basic block, the linear functions
286 are initialized to OUTERMOST_LOOP and BB is the place where we try
287 to evaluate the STMT. */
288
289 static bool
290 stmt_simple_for_scop_p (basic_block scop_entry, loop_p outermost_loop,
291 gimple stmt, basic_block bb)
292 {
293 loop_p loop = bb->loop_father;
294
295 gcc_assert (scop_entry);
296
297 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
298 Calls have side-effects, except those to const or pure
299 functions. */
300 if (gimple_has_volatile_ops (stmt)
301 || (gimple_code (stmt) == GIMPLE_CALL
302 && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
303 || (gimple_code (stmt) == GIMPLE_ASM))
304 return false;
305
306 if (is_gimple_debug (stmt))
307 return true;
308
309 if (!stmt_has_simple_data_refs_p (outermost_loop, stmt))
310 return false;
311
312 switch (gimple_code (stmt))
313 {
314 case GIMPLE_RETURN:
315 case GIMPLE_LABEL:
316 return true;
317
318 case GIMPLE_COND:
319 {
320 tree op;
321 ssa_op_iter op_iter;
322 enum tree_code code = gimple_cond_code (stmt);
323
324 /* We can handle all binary comparisons. Inequalities are
325 also supported as they can be represented with union of
326 polyhedra. */
327 if (!(code == LT_EXPR
328 || code == GT_EXPR
329 || code == LE_EXPR
330 || code == GE_EXPR
331 || code == EQ_EXPR
332 || code == NE_EXPR))
333 return false;
334
335 FOR_EACH_SSA_TREE_OPERAND (op, stmt, op_iter, SSA_OP_ALL_USES)
336 if (!graphite_can_represent_expr (scop_entry, loop, op)
337 /* We can not handle REAL_TYPE. Failed for pr39260. */
338 || TREE_CODE (TREE_TYPE (op)) == REAL_TYPE)
339 return false;
340
341 return true;
342 }
343
344 case GIMPLE_ASSIGN:
345 case GIMPLE_CALL:
346 return true;
347
348 default:
349 /* These nodes cut a new scope. */
350 return false;
351 }
352
353 return false;
354 }
355
356 /* Returns the statement of BB that contains a harmful operation: that
357 can be a function call with side effects, the induction variables
358 are not linear with respect to SCOP_ENTRY, etc. The current open
359 scop should end before this statement. The evaluation is limited using
360 OUTERMOST_LOOP as outermost loop that may change. */
361
362 static gimple
363 harmful_stmt_in_bb (basic_block scop_entry, loop_p outer_loop, basic_block bb)
364 {
365 gimple_stmt_iterator gsi;
366
367 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
368 if (!stmt_simple_for_scop_p (scop_entry, outer_loop, gsi_stmt (gsi), bb))
369 return gsi_stmt (gsi);
370
371 return NULL;
372 }
373
374 /* Return true if LOOP can be represented in the polyhedral
375 representation. This is evaluated taking SCOP_ENTRY and
376 OUTERMOST_LOOP in mind. */
377
378 static bool
379 graphite_can_represent_loop (basic_block scop_entry, loop_p loop)
380 {
381 tree niter = number_of_latch_executions (loop);
382
383 /* Number of iterations unknown. */
384 if (chrec_contains_undetermined (niter))
385 return false;
386
387 /* Number of iterations not affine. */
388 if (!graphite_can_represent_expr (scop_entry, loop, niter))
389 return false;
390
391 return true;
392 }
393
394 /* Store information needed by scopdet_* functions. */
395
396 struct scopdet_info
397 {
398 /* Exit of the open scop would stop if the current BB is harmful. */
399 basic_block exit;
400
401 /* Where the next scop would start if the current BB is harmful. */
402 basic_block next;
403
404 /* The bb or one of its children contains open loop exits. That means
405 loop exit nodes that are not surrounded by a loop dominated by bb. */
406 bool exits;
407
408 /* The bb or one of its children contains only structures we can handle. */
409 bool difficult;
410 };
411
412 static struct scopdet_info build_scops_1 (basic_block, loop_p,
413 VEC (sd_region, heap) **, loop_p);
414
415 /* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB
416 to SCOPS. TYPE is the gbb_type of BB. */
417
418 static struct scopdet_info
419 scopdet_basic_block_info (basic_block bb, loop_p outermost_loop,
420 VEC (sd_region, heap) **scops, gbb_type type)
421 {
422 loop_p loop = bb->loop_father;
423 struct scopdet_info result;
424 gimple stmt;
425
426 /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps. */
427 basic_block entry_block = ENTRY_BLOCK_PTR;
428 stmt = harmful_stmt_in_bb (entry_block, outermost_loop, bb);
429 result.difficult = (stmt != NULL);
430 result.exit = NULL;
431
432 switch (type)
433 {
434 case GBB_LAST:
435 result.next = NULL;
436 result.exits = false;
437
438 /* Mark bbs terminating a SESE region difficult, if they start
439 a condition. */
440 if (!single_succ_p (bb))
441 result.difficult = true;
442 else
443 result.exit = single_succ (bb);
444
445 break;
446
447 case GBB_SIMPLE:
448 result.next = single_succ (bb);
449 result.exits = false;
450 result.exit = single_succ (bb);
451 break;
452
453 case GBB_LOOP_SING_EXIT_HEADER:
454 {
455 VEC (sd_region, heap) *regions = VEC_alloc (sd_region, heap, 3);
456 struct scopdet_info sinfo;
457 edge exit_e = single_exit (loop);
458
459 sinfo = build_scops_1 (bb, outermost_loop, &regions, loop);
460
461 if (!graphite_can_represent_loop (entry_block, loop))
462 result.difficult = true;
463
464 result.difficult |= sinfo.difficult;
465
466 /* Try again with another loop level. */
467 if (result.difficult
468 && loop_depth (outermost_loop) + 1 == loop_depth (loop))
469 {
470 outermost_loop = loop;
471
472 VEC_free (sd_region, heap, regions);
473 regions = VEC_alloc (sd_region, heap, 3);
474
475 sinfo = scopdet_basic_block_info (bb, outermost_loop, scops, type);
476
477 result = sinfo;
478 result.difficult = true;
479
480 if (sinfo.difficult)
481 move_sd_regions (&regions, scops);
482 else
483 {
484 sd_region open_scop;
485 open_scop.entry = bb;
486 open_scop.exit = exit_e->dest;
487 VEC_safe_push (sd_region, heap, *scops, &open_scop);
488 VEC_free (sd_region, heap, regions);
489 }
490 }
491 else
492 {
493 result.exit = exit_e->dest;
494 result.next = exit_e->dest;
495
496 /* If we do not dominate result.next, remove it. It's either
497 the EXIT_BLOCK_PTR, or another bb dominates it and will
498 call the scop detection for this bb. */
499 if (!dominated_by_p (CDI_DOMINATORS, result.next, bb))
500 result.next = NULL;
501
502 if (exit_e->src->loop_father != loop)
503 result.next = NULL;
504
505 result.exits = false;
506
507 if (result.difficult)
508 move_sd_regions (&regions, scops);
509 else
510 VEC_free (sd_region, heap, regions);
511 }
512
513 break;
514 }
515
516 case GBB_LOOP_MULT_EXIT_HEADER:
517 {
518 /* XXX: For now we just do not join loops with multiple exits. If the
519 exits lead to the same bb it may be possible to join the loop. */
520 VEC (sd_region, heap) *regions = VEC_alloc (sd_region, heap, 3);
521 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
522 edge e;
523 int i;
524 build_scops_1 (bb, loop, &regions, loop);
525
526 /* Scan the code dominated by this loop. This means all bbs, that are
527 are dominated by a bb in this loop, but are not part of this loop.
528
529 The easiest case:
530 - The loop exit destination is dominated by the exit sources.
531
532 TODO: We miss here the more complex cases:
533 - The exit destinations are dominated by another bb inside
534 the loop.
535 - The loop dominates bbs, that are not exit destinations. */
536 FOR_EACH_VEC_ELT (edge, exits, i, e)
537 if (e->src->loop_father == loop
538 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src))
539 {
540 if (loop_outer (outermost_loop))
541 outermost_loop = loop_outer (outermost_loop);
542
543 /* Pass loop_outer to recognize e->dest as loop header in
544 build_scops_1. */
545 if (e->dest->loop_father->header == e->dest)
546 build_scops_1 (e->dest, outermost_loop, &regions,
547 loop_outer (e->dest->loop_father));
548 else
549 build_scops_1 (e->dest, outermost_loop, &regions,
550 e->dest->loop_father);
551 }
552
553 result.next = NULL;
554 result.exit = NULL;
555 result.difficult = true;
556 result.exits = false;
557 move_sd_regions (&regions, scops);
558 VEC_free (edge, heap, exits);
559 break;
560 }
561 case GBB_COND_HEADER:
562 {
563 VEC (sd_region, heap) *regions = VEC_alloc (sd_region, heap, 3);
564 struct scopdet_info sinfo;
565 VEC (basic_block, heap) *dominated;
566 int i;
567 basic_block dom_bb;
568 basic_block last_exit = NULL;
569 edge e;
570 result.exits = false;
571
572 /* First check the successors of BB, and check if it is
573 possible to join the different branches. */
574 FOR_EACH_VEC_ELT (edge, bb->succs, i, e)
575 {
576 /* Ignore loop exits. They will be handled after the loop
577 body. */
578 if (loop_exits_to_bb_p (loop, e->dest))
579 {
580 result.exits = true;
581 continue;
582 }
583
584 /* Do not follow edges that lead to the end of the
585 conditions block. For example, in
586
587 | 0
588 | /|\
589 | 1 2 |
590 | | | |
591 | 3 4 |
592 | \|/
593 | 6
594
595 the edge from 0 => 6. Only check if all paths lead to
596 the same node 6. */
597
598 if (!single_pred_p (e->dest))
599 {
600 /* Check, if edge leads directly to the end of this
601 condition. */
602 if (!last_exit)
603 last_exit = e->dest;
604
605 if (e->dest != last_exit)
606 result.difficult = true;
607
608 continue;
609 }
610
611 if (!dominated_by_p (CDI_DOMINATORS, e->dest, bb))
612 {
613 result.difficult = true;
614 continue;
615 }
616
617 sinfo = build_scops_1 (e->dest, outermost_loop, &regions, loop);
618
619 result.exits |= sinfo.exits;
620 result.difficult |= sinfo.difficult;
621
622 /* Checks, if all branches end at the same point.
623 If that is true, the condition stays joinable.
624 Have a look at the example above. */
625 if (sinfo.exit)
626 {
627 if (!last_exit)
628 last_exit = sinfo.exit;
629
630 if (sinfo.exit != last_exit)
631 result.difficult = true;
632 }
633 else
634 result.difficult = true;
635 }
636
637 if (!last_exit)
638 result.difficult = true;
639
640 /* Join the branches of the condition if possible. */
641 if (!result.exits && !result.difficult)
642 {
643 /* Only return a next pointer if we dominate this pointer.
644 Otherwise it will be handled by the bb dominating it. */
645 if (dominated_by_p (CDI_DOMINATORS, last_exit, bb)
646 && last_exit != bb)
647 result.next = last_exit;
648 else
649 result.next = NULL;
650
651 result.exit = last_exit;
652
653 VEC_free (sd_region, heap, regions);
654 break;
655 }
656
657 /* Scan remaining bbs dominated by BB. */
658 dominated = get_dominated_by (CDI_DOMINATORS, bb);
659
660 FOR_EACH_VEC_ELT (basic_block, dominated, i, dom_bb)
661 {
662 /* Ignore loop exits: they will be handled after the loop body. */
663 if (loop_depth (find_common_loop (loop, dom_bb->loop_father))
664 < loop_depth (loop))
665 {
666 result.exits = true;
667 continue;
668 }
669
670 /* Ignore the bbs processed above. */
671 if (single_pred_p (dom_bb) && single_pred (dom_bb) == bb)
672 continue;
673
674 if (loop_depth (loop) > loop_depth (dom_bb->loop_father))
675 sinfo = build_scops_1 (dom_bb, outermost_loop, &regions,
676 loop_outer (loop));
677 else
678 sinfo = build_scops_1 (dom_bb, outermost_loop, &regions, loop);
679
680 result.exits |= sinfo.exits;
681 result.difficult = true;
682 result.exit = NULL;
683 }
684
685 VEC_free (basic_block, heap, dominated);
686
687 result.next = NULL;
688 move_sd_regions (&regions, scops);
689
690 break;
691 }
692
693 default:
694 gcc_unreachable ();
695 }
696
697 return result;
698 }
699
700 /* Starting from CURRENT we walk the dominance tree and add new sd_regions to
701 SCOPS. The analyse if a sd_region can be handled is based on the value
702 of OUTERMOST_LOOP. Only loops inside OUTERMOST loops may change. LOOP
703 is the loop in which CURRENT is handled.
704
705 TODO: These functions got a little bit big. They definitely should be cleaned
706 up. */
707
708 static struct scopdet_info
709 build_scops_1 (basic_block current, loop_p outermost_loop,
710 VEC (sd_region, heap) **scops, loop_p loop)
711 {
712 bool in_scop = false;
713 sd_region open_scop;
714 struct scopdet_info sinfo;
715
716 /* Initialize result. */
717 struct scopdet_info result;
718 result.exits = false;
719 result.difficult = false;
720 result.next = NULL;
721 result.exit = NULL;
722 open_scop.entry = NULL;
723 open_scop.exit = NULL;
724 sinfo.exit = NULL;
725
726 /* Loop over the dominance tree. If we meet a difficult bb, close
727 the current SCoP. Loop and condition header start a new layer,
728 and can only be added if all bbs in deeper layers are simple. */
729 while (current != NULL)
730 {
731 sinfo = scopdet_basic_block_info (current, outermost_loop, scops,
732 get_bb_type (current, loop));
733
734 if (!in_scop && !(sinfo.exits || sinfo.difficult))
735 {
736 open_scop.entry = current;
737 open_scop.exit = NULL;
738 in_scop = true;
739 }
740 else if (in_scop && (sinfo.exits || sinfo.difficult))
741 {
742 open_scop.exit = current;
743 VEC_safe_push (sd_region, heap, *scops, &open_scop);
744 in_scop = false;
745 }
746
747 result.difficult |= sinfo.difficult;
748 result.exits |= sinfo.exits;
749
750 current = sinfo.next;
751 }
752
753 /* Try to close open_scop, if we are still in an open SCoP. */
754 if (in_scop)
755 {
756 open_scop.exit = sinfo.exit;
757 gcc_assert (open_scop.exit);
758 VEC_safe_push (sd_region, heap, *scops, &open_scop);
759 }
760
761 result.exit = sinfo.exit;
762 return result;
763 }
764
765 /* Checks if a bb is contained in REGION. */
766
767 static bool
768 bb_in_sd_region (basic_block bb, sd_region *region)
769 {
770 return bb_in_region (bb, region->entry, region->exit);
771 }
772
773 /* Returns the single entry edge of REGION, if it does not exits NULL. */
774
775 static edge
776 find_single_entry_edge (sd_region *region)
777 {
778 edge e;
779 edge_iterator ei;
780 edge entry = NULL;
781
782 FOR_EACH_EDGE (e, ei, region->entry->preds)
783 if (!bb_in_sd_region (e->src, region))
784 {
785 if (entry)
786 {
787 entry = NULL;
788 break;
789 }
790
791 else
792 entry = e;
793 }
794
795 return entry;
796 }
797
798 /* Returns the single exit edge of REGION, if it does not exits NULL. */
799
800 static edge
801 find_single_exit_edge (sd_region *region)
802 {
803 edge e;
804 edge_iterator ei;
805 edge exit = NULL;
806
807 FOR_EACH_EDGE (e, ei, region->exit->preds)
808 if (bb_in_sd_region (e->src, region))
809 {
810 if (exit)
811 {
812 exit = NULL;
813 break;
814 }
815
816 else
817 exit = e;
818 }
819
820 return exit;
821 }
822
823 /* Create a single entry edge for REGION. */
824
825 static void
826 create_single_entry_edge (sd_region *region)
827 {
828 if (find_single_entry_edge (region))
829 return;
830
831 /* There are multiple predecessors for bb_3
832
833 | 1 2
834 | | /
835 | |/
836 | 3 <- entry
837 | |\
838 | | |
839 | 4 ^
840 | | |
841 | |/
842 | 5
843
844 There are two edges (1->3, 2->3), that point from outside into the region,
845 and another one (5->3), a loop latch, lead to bb_3.
846
847 We split bb_3.
848
849 | 1 2
850 | | /
851 | |/
852 |3.0
853 | |\ (3.0 -> 3.1) = single entry edge
854 |3.1 | <- entry
855 | | |
856 | | |
857 | 4 ^
858 | | |
859 | |/
860 | 5
861
862 If the loop is part of the SCoP, we have to redirect the loop latches.
863
864 | 1 2
865 | | /
866 | |/
867 |3.0
868 | | (3.0 -> 3.1) = entry edge
869 |3.1 <- entry
870 | |\
871 | | |
872 | 4 ^
873 | | |
874 | |/
875 | 5 */
876
877 if (region->entry->loop_father->header != region->entry
878 || dominated_by_p (CDI_DOMINATORS,
879 loop_latch_edge (region->entry->loop_father)->src,
880 region->exit))
881 {
882 edge forwarder = split_block_after_labels (region->entry);
883 region->entry = forwarder->dest;
884 }
885 else
886 /* This case is never executed, as the loop headers seem always to have a
887 single edge pointing from outside into the loop. */
888 gcc_unreachable ();
889
890 gcc_checking_assert (find_single_entry_edge (region));
891 }
892
893 /* Check if the sd_region, mentioned in EDGE, has no exit bb. */
894
895 static bool
896 sd_region_without_exit (edge e)
897 {
898 sd_region *r = (sd_region *) e->aux;
899
900 if (r)
901 return r->exit == NULL;
902 else
903 return false;
904 }
905
906 /* Create a single exit edge for REGION. */
907
908 static void
909 create_single_exit_edge (sd_region *region)
910 {
911 edge e;
912 edge_iterator ei;
913 edge forwarder = NULL;
914 basic_block exit;
915
916 /* We create a forwarder bb (5) for all edges leaving this region
917 (3->5, 4->5). All other edges leading to the same bb, are moved
918 to a new bb (6). If these edges where part of another region (2->5)
919 we update the region->exit pointer, of this region.
920
921 To identify which edge belongs to which region we depend on the e->aux
922 pointer in every edge. It points to the region of the edge or to NULL,
923 if the edge is not part of any region.
924
925 1 2 3 4 1->5 no region, 2->5 region->exit = 5,
926 \| |/ 3->5 region->exit = NULL, 4->5 region->exit = NULL
927 5 <- exit
928
929 changes to
930
931 1 2 3 4 1->6 no region, 2->6 region->exit = 6,
932 | | \/ 3->5 no region, 4->5 no region,
933 | | 5
934 \| / 5->6 region->exit = 6
935 6
936
937 Now there is only a single exit edge (5->6). */
938 exit = region->exit;
939 region->exit = NULL;
940 forwarder = make_forwarder_block (exit, &sd_region_without_exit, NULL);
941
942 /* Unmark the edges, that are no longer exit edges. */
943 FOR_EACH_EDGE (e, ei, forwarder->src->preds)
944 if (e->aux)
945 e->aux = NULL;
946
947 /* Mark the new exit edge. */
948 single_succ_edge (forwarder->src)->aux = region;
949
950 /* Update the exit bb of all regions, where exit edges lead to
951 forwarder->dest. */
952 FOR_EACH_EDGE (e, ei, forwarder->dest->preds)
953 if (e->aux)
954 ((sd_region *) e->aux)->exit = forwarder->dest;
955
956 gcc_checking_assert (find_single_exit_edge (region));
957 }
958
959 /* Unmark the exit edges of all REGIONS.
960 See comment in "create_single_exit_edge". */
961
962 static void
963 unmark_exit_edges (VEC (sd_region, heap) *regions)
964 {
965 int i;
966 sd_region *s;
967 edge e;
968 edge_iterator ei;
969
970 FOR_EACH_VEC_ELT (sd_region, regions, i, s)
971 FOR_EACH_EDGE (e, ei, s->exit->preds)
972 e->aux = NULL;
973 }
974
975
976 /* Mark the exit edges of all REGIONS.
977 See comment in "create_single_exit_edge". */
978
979 static void
980 mark_exit_edges (VEC (sd_region, heap) *regions)
981 {
982 int i;
983 sd_region *s;
984 edge e;
985 edge_iterator ei;
986
987 FOR_EACH_VEC_ELT (sd_region, regions, i, s)
988 FOR_EACH_EDGE (e, ei, s->exit->preds)
989 if (bb_in_sd_region (e->src, s))
990 e->aux = s;
991 }
992
993 /* Create for all scop regions a single entry and a single exit edge. */
994
995 static void
996 create_sese_edges (VEC (sd_region, heap) *regions)
997 {
998 int i;
999 sd_region *s;
1000
1001 FOR_EACH_VEC_ELT (sd_region, regions, i, s)
1002 create_single_entry_edge (s);
1003
1004 mark_exit_edges (regions);
1005
1006 FOR_EACH_VEC_ELT (sd_region, regions, i, s)
1007 /* Don't handle multiple edges exiting the function. */
1008 if (!find_single_exit_edge (s)
1009 && s->exit != EXIT_BLOCK_PTR)
1010 create_single_exit_edge (s);
1011
1012 unmark_exit_edges (regions);
1013
1014 fix_loop_structure (NULL);
1015
1016 #ifdef ENABLE_CHECKING
1017 verify_loop_structure ();
1018 verify_dominators (CDI_DOMINATORS);
1019 verify_ssa (false);
1020 #endif
1021 }
1022
1023 /* Create graphite SCoPs from an array of scop detection REGIONS. */
1024
1025 static void
1026 build_graphite_scops (VEC (sd_region, heap) *regions,
1027 VEC (scop_p, heap) **scops)
1028 {
1029 int i;
1030 sd_region *s;
1031
1032 FOR_EACH_VEC_ELT (sd_region, regions, i, s)
1033 {
1034 edge entry = find_single_entry_edge (s);
1035 edge exit = find_single_exit_edge (s);
1036 scop_p scop;
1037
1038 if (!exit)
1039 continue;
1040
1041 scop = new_scop (new_sese (entry, exit));
1042 VEC_safe_push (scop_p, heap, *scops, scop);
1043
1044 /* Are there overlapping SCoPs? */
1045 #ifdef ENABLE_CHECKING
1046 {
1047 int j;
1048 sd_region *s2;
1049
1050 FOR_EACH_VEC_ELT (sd_region, regions, j, s2)
1051 if (s != s2)
1052 gcc_assert (!bb_in_sd_region (s->entry, s2));
1053 }
1054 #endif
1055 }
1056 }
1057
1058 /* Returns true when BB contains only close phi nodes. */
1059
1060 static bool
1061 contains_only_close_phi_nodes (basic_block bb)
1062 {
1063 gimple_stmt_iterator gsi;
1064
1065 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1066 if (gimple_code (gsi_stmt (gsi)) != GIMPLE_LABEL)
1067 return false;
1068
1069 return true;
1070 }
1071
1072 /* Print statistics for SCOP to FILE. */
1073
1074 static void
1075 print_graphite_scop_statistics (FILE* file, scop_p scop)
1076 {
1077 long n_bbs = 0;
1078 long n_loops = 0;
1079 long n_stmts = 0;
1080 long n_conditions = 0;
1081 long n_p_bbs = 0;
1082 long n_p_loops = 0;
1083 long n_p_stmts = 0;
1084 long n_p_conditions = 0;
1085
1086 basic_block bb;
1087
1088 FOR_ALL_BB (bb)
1089 {
1090 gimple_stmt_iterator psi;
1091 loop_p loop = bb->loop_father;
1092
1093 if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
1094 continue;
1095
1096 n_bbs++;
1097 n_p_bbs += bb->count;
1098
1099 if (VEC_length (edge, bb->succs) > 1)
1100 {
1101 n_conditions++;
1102 n_p_conditions += bb->count;
1103 }
1104
1105 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
1106 {
1107 n_stmts++;
1108 n_p_stmts += bb->count;
1109 }
1110
1111 if (loop->header == bb && loop_in_sese_p (loop, SCOP_REGION (scop)))
1112 {
1113 n_loops++;
1114 n_p_loops += bb->count;
1115 }
1116
1117 }
1118
1119 fprintf (file, "\nBefore limit_scops SCoP statistics (");
1120 fprintf (file, "BBS:%ld, ", n_bbs);
1121 fprintf (file, "LOOPS:%ld, ", n_loops);
1122 fprintf (file, "CONDITIONS:%ld, ", n_conditions);
1123 fprintf (file, "STMTS:%ld)\n", n_stmts);
1124 fprintf (file, "\nBefore limit_scops SCoP profiling statistics (");
1125 fprintf (file, "BBS:%ld, ", n_p_bbs);
1126 fprintf (file, "LOOPS:%ld, ", n_p_loops);
1127 fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
1128 fprintf (file, "STMTS:%ld)\n", n_p_stmts);
1129 }
1130
1131 /* Print statistics for SCOPS to FILE. */
1132
1133 static void
1134 print_graphite_statistics (FILE* file, VEC (scop_p, heap) *scops)
1135 {
1136 int i;
1137 scop_p scop;
1138
1139 FOR_EACH_VEC_ELT (scop_p, scops, i, scop)
1140 print_graphite_scop_statistics (file, scop);
1141 }
1142
1143 /* We limit all SCoPs to SCoPs, that are completely surrounded by a loop.
1144
1145 Example:
1146
1147 for (i |
1148 { |
1149 for (j | SCoP 1
1150 for (k |
1151 } |
1152
1153 * SCoP frontier, as this line is not surrounded by any loop. *
1154
1155 for (l | SCoP 2
1156
1157 This is necessary as scalar evolution and parameter detection need a
1158 outermost loop to initialize parameters correctly.
1159
1160 TODO: FIX scalar evolution and parameter detection to allow more flexible
1161 SCoP frontiers. */
1162
1163 static void
1164 limit_scops (VEC (scop_p, heap) **scops)
1165 {
1166 VEC (sd_region, heap) *regions = VEC_alloc (sd_region, heap, 3);
1167
1168 int i;
1169 scop_p scop;
1170
1171 FOR_EACH_VEC_ELT (scop_p, *scops, i, scop)
1172 {
1173 int j;
1174 loop_p loop;
1175 sese region = SCOP_REGION (scop);
1176 build_sese_loop_nests (region);
1177
1178 FOR_EACH_VEC_ELT (loop_p, SESE_LOOP_NEST (region), j, loop)
1179 if (!loop_in_sese_p (loop_outer (loop), region)
1180 && single_exit (loop))
1181 {
1182 sd_region open_scop;
1183 open_scop.entry = loop->header;
1184 open_scop.exit = single_exit (loop)->dest;
1185
1186 /* This is a hack on top of the limit_scops hack. The
1187 limit_scops hack should disappear all together. */
1188 if (single_succ_p (open_scop.exit)
1189 && contains_only_close_phi_nodes (open_scop.exit))
1190 open_scop.exit = single_succ_edge (open_scop.exit)->dest;
1191
1192 VEC_safe_push (sd_region, heap, regions, &open_scop);
1193 }
1194 }
1195
1196 free_scops (*scops);
1197 *scops = VEC_alloc (scop_p, heap, 3);
1198
1199 create_sese_edges (regions);
1200 build_graphite_scops (regions, scops);
1201 VEC_free (sd_region, heap, regions);
1202 }
1203
1204 /* Returns true when P1 and P2 are close phis with the same
1205 argument. */
1206
1207 static inline bool
1208 same_close_phi_node (gimple p1, gimple p2)
1209 {
1210 return operand_equal_p (gimple_phi_arg_def (p1, 0),
1211 gimple_phi_arg_def (p2, 0), 0);
1212 }
1213
1214 /* Remove the close phi node at GSI and replace its rhs with the rhs
1215 of PHI. */
1216
1217 static void
1218 remove_duplicate_close_phi (gimple phi, gimple_stmt_iterator *gsi)
1219 {
1220 gimple use_stmt;
1221 use_operand_p use_p;
1222 imm_use_iterator imm_iter;
1223 tree res = gimple_phi_result (phi);
1224 tree def = gimple_phi_result (gsi_stmt (*gsi));
1225
1226 gcc_assert (same_close_phi_node (phi, gsi_stmt (*gsi)));
1227
1228 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
1229 {
1230 FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
1231 SET_USE (use_p, res);
1232
1233 update_stmt (use_stmt);
1234 }
1235
1236 remove_phi_node (gsi, true);
1237 }
1238
1239 /* Removes all the close phi duplicates from BB. */
1240
1241 static void
1242 make_close_phi_nodes_unique (basic_block bb)
1243 {
1244 gimple_stmt_iterator psi;
1245
1246 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
1247 {
1248 gimple_stmt_iterator gsi = psi;
1249 gimple phi = gsi_stmt (psi);
1250
1251 /* At this point, PHI should be a close phi in normal form. */
1252 gcc_assert (gimple_phi_num_args (phi) == 1);
1253
1254 /* Iterate over the next phis and remove duplicates. */
1255 gsi_next (&gsi);
1256 while (!gsi_end_p (gsi))
1257 if (same_close_phi_node (phi, gsi_stmt (gsi)))
1258 remove_duplicate_close_phi (phi, &gsi);
1259 else
1260 gsi_next (&gsi);
1261 }
1262 }
1263
1264 /* Transforms LOOP to the canonical loop closed SSA form. */
1265
1266 static void
1267 canonicalize_loop_closed_ssa (loop_p loop)
1268 {
1269 edge e = single_exit (loop);
1270 basic_block bb;
1271
1272 if (!e || e->flags & EDGE_ABNORMAL)
1273 return;
1274
1275 bb = e->dest;
1276
1277 if (VEC_length (edge, bb->preds) == 1)
1278 {
1279 e = split_block_after_labels (bb);
1280 make_close_phi_nodes_unique (e->src);
1281 }
1282 else
1283 {
1284 gimple_stmt_iterator psi;
1285 basic_block close = split_edge (e);
1286
1287 e = single_succ_edge (close);
1288
1289 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
1290 {
1291 gimple phi = gsi_stmt (psi);
1292 unsigned i;
1293
1294 for (i = 0; i < gimple_phi_num_args (phi); i++)
1295 if (gimple_phi_arg_edge (phi, i) == e)
1296 {
1297 tree res, arg = gimple_phi_arg_def (phi, i);
1298 use_operand_p use_p;
1299 gimple close_phi;
1300
1301 if (TREE_CODE (arg) != SSA_NAME)
1302 continue;
1303
1304 close_phi = create_phi_node (arg, close);
1305 res = create_new_def_for (gimple_phi_result (close_phi),
1306 close_phi,
1307 gimple_phi_result_ptr (close_phi));
1308 add_phi_arg (close_phi, arg,
1309 gimple_phi_arg_edge (close_phi, 0),
1310 UNKNOWN_LOCATION);
1311 use_p = gimple_phi_arg_imm_use_ptr (phi, i);
1312 replace_exp (use_p, res);
1313 update_stmt (phi);
1314 }
1315 }
1316
1317 make_close_phi_nodes_unique (close);
1318 }
1319
1320 /* The code above does not properly handle changes in the post dominance
1321 information (yet). */
1322 free_dominance_info (CDI_POST_DOMINATORS);
1323 }
1324
1325 /* Converts the current loop closed SSA form to a canonical form
1326 expected by the Graphite code generation.
1327
1328 The loop closed SSA form has the following invariant: a variable
1329 defined in a loop that is used outside the loop appears only in the
1330 phi nodes in the destination of the loop exit. These phi nodes are
1331 called close phi nodes.
1332
1333 The canonical loop closed SSA form contains the extra invariants:
1334
1335 - when the loop contains only one exit, the close phi nodes contain
1336 only one argument. That implies that the basic block that contains
1337 the close phi nodes has only one predecessor, that is a basic block
1338 in the loop.
1339
1340 - the basic block containing the close phi nodes does not contain
1341 other statements.
1342
1343 - there exist only one phi node per definition in the loop.
1344 */
1345
1346 static void
1347 canonicalize_loop_closed_ssa_form (void)
1348 {
1349 loop_iterator li;
1350 loop_p loop;
1351
1352 #ifdef ENABLE_CHECKING
1353 verify_loop_closed_ssa (true);
1354 #endif
1355
1356 FOR_EACH_LOOP (li, loop, 0)
1357 canonicalize_loop_closed_ssa (loop);
1358
1359 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1360 update_ssa (TODO_update_ssa);
1361
1362 #ifdef ENABLE_CHECKING
1363 verify_loop_closed_ssa (true);
1364 #endif
1365 }
1366
1367 /* Find Static Control Parts (SCoP) in the current function and pushes
1368 them to SCOPS. */
1369
1370 void
1371 build_scops (VEC (scop_p, heap) **scops)
1372 {
1373 struct loop *loop = current_loops->tree_root;
1374 VEC (sd_region, heap) *regions = VEC_alloc (sd_region, heap, 3);
1375
1376 canonicalize_loop_closed_ssa_form ();
1377 build_scops_1 (single_succ (ENTRY_BLOCK_PTR), ENTRY_BLOCK_PTR->loop_father,
1378 &regions, loop);
1379 create_sese_edges (regions);
1380 build_graphite_scops (regions, scops);
1381
1382 if (dump_file && (dump_flags & TDF_DETAILS))
1383 print_graphite_statistics (dump_file, *scops);
1384
1385 limit_scops (scops);
1386 VEC_free (sd_region, heap, regions);
1387
1388 if (dump_file && (dump_flags & TDF_DETAILS))
1389 fprintf (dump_file, "\nnumber of SCoPs: %d\n",
1390 VEC_length (scop_p, *scops));
1391 }
1392 85
1393 /* Pretty print to FILE all the SCoPs in DOT format and mark them with 86 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
1394 different colors. If there are not enough colors, paint the 87 different colors. If there are not enough colors, paint the
1395 remaining SCoPs in gray. 88 remaining SCoPs in gray.
1396 89
1398 - "*" after the node number denotes the entry of a SCoP, 91 - "*" after the node number denotes the entry of a SCoP,
1399 - "#" after the node number denotes the exit of a SCoP, 92 - "#" after the node number denotes the exit of a SCoP,
1400 - "()" around the node number denotes the entry or the 93 - "()" around the node number denotes the entry or the
1401 exit nodes of the SCOP. These are not part of SCoP. */ 94 exit nodes of the SCOP. These are not part of SCoP. */
1402 95
1403 static void 96 DEBUG_FUNCTION void
1404 dot_all_scops_1 (FILE *file, VEC (scop_p, heap) *scops) 97 dot_all_sese (FILE *file, vec<sese_l>& scops)
1405 { 98 {
99 /* Disable debugging while printing graph. */
100 dump_flags_t tmp_dump_flags = dump_flags;
101 dump_flags = TDF_NONE;
102
103 fprintf (file, "digraph all {\n");
104
1406 basic_block bb; 105 basic_block bb;
1407 edge e; 106 FOR_ALL_BB_FN (bb, cfun)
1408 edge_iterator ei;
1409 scop_p scop;
1410 const char* color;
1411 int i;
1412
1413 /* Disable debugging while printing graph. */
1414 int tmp_dump_flags = dump_flags;
1415 dump_flags = 0;
1416
1417 fprintf (file, "digraph all {\n");
1418
1419 FOR_ALL_BB (bb)
1420 { 107 {
1421 int part_of_scop = false; 108 int part_of_scop = false;
1422 109
1423 /* Use HTML for every bb label. So we are able to print bbs 110 /* Use HTML for every bb label. So we are able to print bbs
1424 which are part of two different SCoPs, with two different 111 which are part of two different SCoPs, with two different
1425 background colors. */ 112 background colors. */
1426 fprintf (file, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ", 113 fprintf (file, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
1427 bb->index); 114 bb->index);
1428 fprintf (file, "CELLSPACING=\"0\">\n"); 115 fprintf (file, "CELLSPACING=\"0\">\n");
1429 116
1430 /* Select color for SCoP. */ 117 /* Select color for SCoP. */
1431 FOR_EACH_VEC_ELT (scop_p, scops, i, scop) 118 sese_l *region;
119 int i;
120 FOR_EACH_VEC_ELT (scops, i, region)
1432 { 121 {
1433 sese region = SCOP_REGION (scop); 122 bool sese_in_region = bb_in_sese_p (bb, *region);
1434 if (bb_in_sese_p (bb, region) 123 if (sese_in_region || (region->exit->dest == bb)
1435 || (SESE_EXIT_BB (region) == bb) 124 || (region->entry->dest == bb))
1436 || (SESE_ENTRY_BB (region) == bb))
1437 { 125 {
126 const char *color;
1438 switch (i % 17) 127 switch (i % 17)
1439 { 128 {
1440 case 0: /* red */ 129 case 0: /* red */
1441 color = "#e41a1c"; 130 color = "#e41a1c";
1442 break; 131 break;
1490 break; 179 break;
1491 default: /* gray */ 180 default: /* gray */
1492 color = "#999999"; 181 color = "#999999";
1493 } 182 }
1494 183
1495 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color); 184 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">",
1496 185 color);
1497 if (!bb_in_sese_p (bb, region)) 186
187 if (!sese_in_region)
1498 fprintf (file, " ("); 188 fprintf (file, " (");
1499 189
1500 if (bb == SESE_ENTRY_BB (region) 190 if (bb == region->entry->dest && bb == region->exit->dest)
1501 && bb == SESE_EXIT_BB (region))
1502 fprintf (file, " %d*# ", bb->index); 191 fprintf (file, " %d*# ", bb->index);
1503 else if (bb == SESE_ENTRY_BB (region)) 192 else if (bb == region->entry->dest)
1504 fprintf (file, " %d* ", bb->index); 193 fprintf (file, " %d* ", bb->index);
1505 else if (bb == SESE_EXIT_BB (region)) 194 else if (bb == region->exit->dest)
1506 fprintf (file, " %d# ", bb->index); 195 fprintf (file, " %d# ", bb->index);
1507 else 196 else
1508 fprintf (file, " %d ", bb->index); 197 fprintf (file, " %d ", bb->index);
1509 198
1510 if (!bb_in_sese_p (bb,region)) 199 fprintf (file, "{lp_%d}", bb->loop_father->num);
200
201 if (!sese_in_region)
1511 fprintf (file, ")"); 202 fprintf (file, ")");
1512 203
1513 fprintf (file, "</TD></TR>\n"); 204 fprintf (file, "</TD></TR>\n");
1514 part_of_scop = true; 205 part_of_scop = true;
1515 } 206 }
1516 } 207 }
1517 208
1518 if (!part_of_scop) 209 if (!part_of_scop)
1519 { 210 {
1520 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">"); 211 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
1521 fprintf (file, " %d </TD></TR>\n", bb->index); 212 fprintf (file, " %d {lp_%d} </TD></TR>\n", bb->index,
1522 } 213 bb->loop_father->num);
1523 fprintf (file, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n"); 214 }
1524 } 215 fprintf (file, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
1525 216 }
1526 FOR_ALL_BB (bb) 217
1527 { 218 FOR_ALL_BB_FN (bb, cfun)
1528 FOR_EACH_EDGE (e, ei, bb->succs) 219 {
1529 fprintf (file, "%d -> %d;\n", bb->index, e->dest->index); 220 edge e;
1530 } 221 edge_iterator ei;
222 FOR_EACH_EDGE (e, ei, bb->succs)
223 fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
224 }
1531 225
1532 fputs ("}\n\n", file); 226 fputs ("}\n\n", file);
1533 227
1534 /* Enable debugging again. */ 228 /* Enable debugging again. */
1535 dump_flags = tmp_dump_flags; 229 dump_flags = tmp_dump_flags;
1536 } 230 }
1537 231
1538 /* Display all SCoPs using dotty. */ 232 /* Display SCoP on stderr. */
1539 233
1540 DEBUG_FUNCTION void 234 DEBUG_FUNCTION void
1541 dot_all_scops (VEC (scop_p, heap) *scops) 235 dot_sese (sese_l& scop)
1542 { 236 {
1543 /* When debugging, enable the following code. This cannot be used 237 vec<sese_l> scops;
1544 in production compilers because it calls "system". */ 238 scops.create (1);
1545 #if 0 239
1546 int x; 240 if (scop)
1547 FILE *stream = fopen ("/tmp/allscops.dot", "w"); 241 scops.safe_push (scop);
1548 gcc_assert (stream); 242
1549 243 dot_all_sese (stderr, scops);
1550 dot_all_scops_1 (stream, scops); 244
1551 fclose (stream); 245 scops.release ();
1552 246 }
1553 x = system ("dotty /tmp/allscops.dot &");
1554 #else
1555 dot_all_scops_1 (stderr, scops);
1556 #endif
1557 }
1558
1559 /* Display all SCoPs using dotty. */
1560 247
1561 DEBUG_FUNCTION void 248 DEBUG_FUNCTION void
1562 dot_scop (scop_p scop) 249 dot_cfg ()
1563 { 250 {
1564 VEC (scop_p, heap) *scops = NULL; 251 vec<sese_l> scops;
1565 252 scops.create (1);
1566 if (scop) 253 dot_all_sese (stderr, scops);
1567 VEC_safe_push (scop_p, heap, scops, scop); 254 scops.release ();
1568 255 }
1569 /* When debugging, enable the following code. This cannot be used 256
1570 in production compilers because it calls "system". */ 257 /* Returns a COND_EXPR statement when BB has a single predecessor, the
1571 #if 0 258 edge between BB and its predecessor is not a loop exit edge, and
259 the last statement of the single predecessor is a COND_EXPR. */
260
261 static gcond *
262 single_pred_cond_non_loop_exit (basic_block bb)
263 {
264 if (single_pred_p (bb))
265 {
266 edge e = single_pred_edge (bb);
267 basic_block pred = e->src;
268 gimple *stmt;
269
270 if (loop_depth (pred->loop_father) > loop_depth (bb->loop_father))
271 return NULL;
272
273 stmt = last_stmt (pred);
274
275 if (stmt && gimple_code (stmt) == GIMPLE_COND)
276 return as_a<gcond *> (stmt);
277 }
278
279 return NULL;
280 }
281
282 namespace
283 {
284
285 /* Build the maximal scop containing LOOPs and add it to SCOPS. */
286
287 class scop_detection
288 {
289 public:
290 scop_detection () : scops (vNULL) {}
291
292 ~scop_detection ()
1572 { 293 {
1573 int x; 294 scops.release ();
1574 FILE *stream = fopen ("/tmp/allscops.dot", "w");
1575 gcc_assert (stream);
1576
1577 dot_all_scops_1 (stream, scops);
1578 fclose (stream);
1579 x = system ("dotty /tmp/allscops.dot &");
1580 } 295 }
1581 #else 296
1582 dot_all_scops_1 (stderr, scops); 297 /* A marker for invalid sese_l. */
1583 #endif 298 static sese_l invalid_sese;
1584 299
1585 VEC_free (scop_p, heap, scops); 300 /* Return the SCOPS in this SCOP_DETECTION. */
1586 } 301
1587 302 vec<sese_l>
1588 #endif 303 get_scops ()
304 {
305 return scops;
306 }
307
308 /* Return an sese_l around the LOOP. */
309
310 sese_l get_sese (loop_p loop);
311
312 /* Return the closest dominator with a single entry edge. In case of a
313 back-loop the back-edge is not counted. */
314
315 static edge get_nearest_dom_with_single_entry (basic_block dom);
316
317 /* Return the closest post-dominator with a single exit edge. In case of a
318 back-loop the back-edge is not counted. */
319
320 static edge get_nearest_pdom_with_single_exit (basic_block dom);
321
322 /* Merge scops at same loop depth and returns the new sese.
323 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
324
325 sese_l merge_sese (sese_l first, sese_l second) const;
326
327 /* Build scop outer->inner if possible. */
328
329 void build_scop_depth (loop_p loop);
330
331 /* Return true when BEGIN is the preheader edge of a loop with a single exit
332 END. */
333
334 static bool region_has_one_loop (sese_l s);
335
336 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
337
338 void add_scop (sese_l s);
339
340 /* Returns true if S1 subsumes/surrounds S2. */
341 static bool subsumes (sese_l s1, sese_l s2);
342
343 /* Remove a SCoP which is subsumed by S1. */
344 void remove_subscops (sese_l s1);
345
346 /* Returns true if S1 intersects with S2. Since we already know that S1 does
347 not subsume S2 or vice-versa, we only check for entry bbs. */
348
349 static bool intersects (sese_l s1, sese_l s2);
350
351 /* Remove one of the scops when it intersects with any other. */
352
353 void remove_intersecting_scops (sese_l s1);
354
355 /* Return true when a statement in SCOP cannot be represented by Graphite. */
356
357 bool harmful_loop_in_region (sese_l scop) const;
358
359 /* Return true only when STMT is simple enough for being handled by Graphite.
360 This depends on SCOP, as the parameters are initialized relatively to
361 this basic block, the linear functions are initialized based on the
362 outermost loop containing STMT inside the SCOP. BB is the place where we
363 try to evaluate the STMT. */
364
365 bool stmt_simple_for_scop_p (sese_l scop, gimple *stmt,
366 basic_block bb) const;
367
368 /* Something like "n * m" is not allowed. */
369
370 static bool graphite_can_represent_init (tree e);
371
372 /* Return true when SCEV can be represented in the polyhedral model.
373
374 An expression can be represented, if it can be expressed as an
375 affine expression. For loops (i, j) and parameters (m, n) all
376 affine expressions are of the form:
377
378 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
379
380 1 i + 20 j + (-2) m + 25
381
382 Something like "i * n" or "n * m" is not allowed. */
383
384 static bool graphite_can_represent_scev (sese_l scop, tree scev);
385
386 /* Return true when EXPR can be represented in the polyhedral model.
387
388 This means an expression can be represented, if it is linear with respect
389 to the loops and the strides are non parametric. LOOP is the place where
390 the expr will be evaluated. SCOP defines the region we analyse. */
391
392 static bool graphite_can_represent_expr (sese_l scop, loop_p loop,
393 tree expr);
394
395 /* Return true if the data references of STMT can be represented by Graphite.
396 We try to analyze the data references in a loop contained in the SCOP. */
397
398 static bool stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt);
399
400 /* Remove the close phi node at GSI and replace its rhs with the rhs
401 of PHI. */
402
403 static void remove_duplicate_close_phi (gphi *phi, gphi_iterator *gsi);
404
405 /* Returns true when Graphite can represent LOOP in SCOP.
406 FIXME: For the moment, graphite cannot be used on loops that iterate using
407 induction variables that wrap. */
408
409 static bool can_represent_loop (loop_p loop, sese_l scop);
410
411 /* Returns the number of pbbs that are in loops contained in SCOP. */
412
413 static int nb_pbbs_in_loops (scop_p scop);
414
415 private:
416 vec<sese_l> scops;
417 };
418
419 sese_l scop_detection::invalid_sese (NULL, NULL);
420
421 /* Return an sese_l around the LOOP. */
422
423 sese_l
424 scop_detection::get_sese (loop_p loop)
425 {
426 if (!loop)
427 return invalid_sese;
428
429 edge scop_begin = loop_preheader_edge (loop);
430 edge scop_end = single_exit (loop);
431 if (!scop_end || (scop_end->flags & EDGE_COMPLEX))
432 return invalid_sese;
433 /* Include the BB with the loop-closed SSA PHI nodes.
434 canonicalize_loop_closed_ssa makes sure that is in proper shape. */
435 if (! single_pred_p (scop_end->dest)
436 || ! single_succ_p (scop_end->dest)
437 || ! sese_trivially_empty_bb_p (scop_end->dest))
438 gcc_unreachable ();
439 scop_end = single_succ_edge (scop_end->dest);
440
441 return sese_l (scop_begin, scop_end);
442 }
443
444 /* Return the closest dominator with a single entry edge. */
445
446 edge
447 scop_detection::get_nearest_dom_with_single_entry (basic_block dom)
448 {
449 if (!dom->preds)
450 return NULL;
451
452 /* If any of the dominators has two predecessors but one of them is a back
453 edge, then that basic block also qualifies as a dominator with single
454 entry. */
455 if (dom->preds->length () == 2)
456 {
457 /* If e1->src dominates e2->src then e1->src will also dominate dom. */
458 edge e1 = (*dom->preds)[0];
459 edge e2 = (*dom->preds)[1];
460 loop_p l = dom->loop_father;
461 loop_p l1 = e1->src->loop_father;
462 loop_p l2 = e2->src->loop_father;
463 if (l != l1 && l == l2
464 && dominated_by_p (CDI_DOMINATORS, e2->src, e1->src))
465 return e1;
466 if (l != l2 && l == l1
467 && dominated_by_p (CDI_DOMINATORS, e1->src, e2->src))
468 return e2;
469 }
470
471 while (dom->preds->length () != 1)
472 {
473 if (dom->preds->length () < 1)
474 return NULL;
475 dom = get_immediate_dominator (CDI_DOMINATORS, dom);
476 if (!dom->preds)
477 return NULL;
478 }
479 return (*dom->preds)[0];
480 }
481
482 /* Return the closest post-dominator with a single exit edge. In case of a
483 back-loop the back-edge is not counted. */
484
485 edge
486 scop_detection::get_nearest_pdom_with_single_exit (basic_block pdom)
487 {
488 if (!pdom->succs)
489 return NULL;
490
491 /* If any of the post-dominators has two successors but one of them is a back
492 edge, then that basic block also qualifies as a post-dominator with single
493 exit. */
494 if (pdom->succs->length () == 2)
495 {
496 /* If e1->dest post-dominates e2->dest then e1->dest will also
497 post-dominate pdom. */
498 edge e1 = (*pdom->succs)[0];
499 edge e2 = (*pdom->succs)[1];
500 loop_p l = pdom->loop_father;
501 loop_p l1 = e1->dest->loop_father;
502 loop_p l2 = e2->dest->loop_father;
503 if (l != l1 && l == l2
504 && dominated_by_p (CDI_POST_DOMINATORS, e2->dest, e1->dest))
505 return e1;
506 if (l != l2 && l == l1
507 && dominated_by_p (CDI_POST_DOMINATORS, e1->dest, e2->dest))
508 return e2;
509 }
510
511 while (pdom->succs->length () != 1)
512 {
513 if (pdom->succs->length () < 1)
514 return NULL;
515 pdom = get_immediate_dominator (CDI_POST_DOMINATORS, pdom);
516 if (!pdom->succs)
517 return NULL;
518 }
519
520 return (*pdom->succs)[0];
521 }
522
523 /* Merge scops at same loop depth and returns the new sese.
524 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
525
526 sese_l
527 scop_detection::merge_sese (sese_l first, sese_l second) const
528 {
529 /* In the trivial case first/second may be NULL. */
530 if (!first)
531 return second;
532 if (!second)
533 return first;
534
535 DEBUG_PRINT (dp << "[scop-detection] try merging sese s1: ";
536 print_sese (dump_file, first);
537 dp << "[scop-detection] try merging sese s2: ";
538 print_sese (dump_file, second));
539
540 /* Assumption: Both the sese's should be at the same loop depth or one scop
541 should subsume the other like in case of nested loops. */
542
543 /* Find the common dominators for entry,
544 and common post-dominators for the exit. */
545 basic_block dom = nearest_common_dominator (CDI_DOMINATORS,
546 get_entry_bb (first),
547 get_entry_bb (second));
548
549 edge entry = get_nearest_dom_with_single_entry (dom);
550
551 if (!entry || (entry->flags & EDGE_IRREDUCIBLE_LOOP))
552 return invalid_sese;
553
554 basic_block pdom = nearest_common_dominator (CDI_POST_DOMINATORS,
555 get_exit_bb (first),
556 get_exit_bb (second));
557 pdom = nearest_common_dominator (CDI_POST_DOMINATORS, dom, pdom);
558
559 edge exit = get_nearest_pdom_with_single_exit (pdom);
560
561 if (!exit || (exit->flags & EDGE_IRREDUCIBLE_LOOP))
562 return invalid_sese;
563
564 sese_l combined (entry, exit);
565
566 DEBUG_PRINT (dp << "[scop-detection] checking combined sese: ";
567 print_sese (dump_file, combined));
568
569 /* FIXME: We could iterate to find the dom which dominates pdom, and pdom
570 which post-dominates dom, until it stabilizes. Also, ENTRY->SRC and
571 EXIT->DEST should be in the same loop nest. */
572 if (!dominated_by_p (CDI_DOMINATORS, pdom, dom)
573 || loop_depth (entry->src->loop_father)
574 != loop_depth (exit->dest->loop_father))
575 return invalid_sese;
576
577 /* For now we just bail out when there is a loop exit in the region
578 that is not also the exit of the region. We could enlarge the
579 region to cover the loop that region exits to. See PR79977. */
580 if (loop_outer (entry->src->loop_father))
581 {
582 vec<edge> exits = get_loop_exit_edges (entry->src->loop_father);
583 for (unsigned i = 0; i < exits.length (); ++i)
584 {
585 if (exits[i] != exit
586 && bb_in_region (exits[i]->src, entry->dest, exit->src))
587 {
588 DEBUG_PRINT (dp << "[scop-detection-fail] cannot merge seses.\n");
589 exits.release ();
590 return invalid_sese;
591 }
592 }
593 exits.release ();
594 }
595
596 /* For now we just want to bail out when exit does not post-dominate entry.
597 TODO: We might just add a basic_block at the exit to make exit
598 post-dominate entry (the entire region). */
599 if (!dominated_by_p (CDI_POST_DOMINATORS, get_entry_bb (combined),
600 get_exit_bb (combined))
601 || !dominated_by_p (CDI_DOMINATORS, get_exit_bb (combined),
602 get_entry_bb (combined)))
603 {
604 DEBUG_PRINT (dp << "[scop-detection-fail] cannot merge seses.\n");
605 return invalid_sese;
606 }
607
608 DEBUG_PRINT (dp << "[merged-sese] s1: "; print_sese (dump_file, combined));
609
610 return combined;
611 }
612
613 /* Build scop outer->inner if possible. */
614
615 void
616 scop_detection::build_scop_depth (loop_p loop)
617 {
618 sese_l s = invalid_sese;
619 loop = loop->inner;
620 while (loop)
621 {
622 sese_l next = get_sese (loop);
623 if (! next
624 || harmful_loop_in_region (next))
625 {
626 if (s)
627 add_scop (s);
628 build_scop_depth (loop);
629 s = invalid_sese;
630 }
631 else if (! s)
632 s = next;
633 else
634 {
635 sese_l combined = merge_sese (s, next);
636 if (! combined
637 || harmful_loop_in_region (combined))
638 {
639 add_scop (s);
640 s = next;
641 }
642 else
643 s = combined;
644 }
645 loop = loop->next;
646 }
647 if (s)
648 add_scop (s);
649 }
650
651 /* Returns true when Graphite can represent LOOP in SCOP.
652 FIXME: For the moment, graphite cannot be used on loops that iterate using
653 induction variables that wrap. */
654
655 bool
656 scop_detection::can_represent_loop (loop_p loop, sese_l scop)
657 {
658 tree niter;
659 struct tree_niter_desc niter_desc;
660
661 return single_exit (loop)
662 && !(loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP)
663 && number_of_iterations_exit (loop, single_exit (loop), &niter_desc, false)
664 && niter_desc.control.no_overflow
665 && (niter = number_of_latch_executions (loop))
666 && !chrec_contains_undetermined (niter)
667 && !chrec_contains_undetermined (scalar_evolution_in_region (scop,
668 loop, niter))
669 && graphite_can_represent_expr (scop, loop, niter);
670 }
671
672 /* Return true when BEGIN is the preheader edge of a loop with a single exit
673 END. */
674
675 bool
676 scop_detection::region_has_one_loop (sese_l s)
677 {
678 edge begin = s.entry;
679 edge end = s.exit;
680 /* Check for a single perfectly nested loop. */
681 if (begin->dest->loop_father->inner)
682 return false;
683
684 /* Otherwise, check whether we have adjacent loops. */
685 return (single_pred_p (end->src)
686 && begin->dest->loop_father == single_pred (end->src)->loop_father);
687 }
688
689 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
690
691 void
692 scop_detection::add_scop (sese_l s)
693 {
694 gcc_assert (s);
695
696 /* Do not add scops with only one loop. */
697 if (region_has_one_loop (s))
698 {
699 DEBUG_PRINT (dp << "[scop-detection-fail] Discarding one loop SCoP: ";
700 print_sese (dump_file, s));
701 return;
702 }
703
704 if (get_exit_bb (s) == EXIT_BLOCK_PTR_FOR_FN (cfun))
705 {
706 DEBUG_PRINT (dp << "[scop-detection-fail] "
707 << "Discarding SCoP exiting to return: ";
708 print_sese (dump_file, s));
709 return;
710 }
711
712 /* Remove all the scops which are subsumed by s. */
713 remove_subscops (s);
714
715 /* Remove intersecting scops. FIXME: It will be a good idea to keep
716 the non-intersecting part of the scop already in the list. */
717 remove_intersecting_scops (s);
718
719 scops.safe_push (s);
720 DEBUG_PRINT (dp << "[scop-detection] Adding SCoP: "; print_sese (dump_file, s));
721 }
722
723 /* Return true when a statement in SCOP cannot be represented by Graphite. */
724
725 bool
726 scop_detection::harmful_loop_in_region (sese_l scop) const
727 {
728 basic_block exit_bb = get_exit_bb (scop);
729 basic_block entry_bb = get_entry_bb (scop);
730
731 DEBUG_PRINT (dp << "[checking-harmful-bbs] ";
732 print_sese (dump_file, scop));
733 gcc_assert (dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb));
734
735 auto_vec<basic_block> worklist;
736 auto_bitmap loops;
737
738 worklist.safe_push (entry_bb);
739 while (! worklist.is_empty ())
740 {
741 basic_block bb = worklist.pop ();
742 DEBUG_PRINT (dp << "Visiting bb_" << bb->index << "\n");
743
744 /* The basic block should not be part of an irreducible loop. */
745 if (bb->flags & BB_IRREDUCIBLE_LOOP)
746 return true;
747
748 /* Check for unstructured control flow: CFG not generated by structured
749 if-then-else. */
750 if (bb->succs->length () > 1)
751 {
752 edge e;
753 edge_iterator ei;
754 FOR_EACH_EDGE (e, ei, bb->succs)
755 if (!dominated_by_p (CDI_POST_DOMINATORS, bb, e->dest)
756 && !dominated_by_p (CDI_DOMINATORS, e->dest, bb))
757 return true;
758 }
759
760 /* Collect all loops in the current region. */
761 loop_p loop = bb->loop_father;
762 if (loop_in_sese_p (loop, scop))
763 bitmap_set_bit (loops, loop->num);
764
765 /* Check for harmful statements in basic blocks part of the region. */
766 for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
767 !gsi_end_p (gsi); gsi_next (&gsi))
768 if (!stmt_simple_for_scop_p (scop, gsi_stmt (gsi), bb))
769 return true;
770
771 if (bb != exit_bb)
772 for (basic_block dom = first_dom_son (CDI_DOMINATORS, bb);
773 dom;
774 dom = next_dom_son (CDI_DOMINATORS, dom))
775 worklist.safe_push (dom);
776 }
777
778 /* Go through all loops and check that they are still valid in the combined
779 scop. */
780 unsigned j;
781 bitmap_iterator bi;
782 EXECUTE_IF_SET_IN_BITMAP (loops, 0, j, bi)
783 {
784 loop_p loop = (*current_loops->larray)[j];
785 gcc_assert (loop->num == (int) j);
786
787 /* Check if the loop nests are to be optimized for speed. */
788 if (! loop->inner
789 && ! optimize_loop_for_speed_p (loop))
790 {
791 DEBUG_PRINT (dp << "[scop-detection-fail] loop_"
792 << loop->num << " is not on a hot path.\n");
793 return true;
794 }
795
796 if (! can_represent_loop (loop, scop))
797 {
798 DEBUG_PRINT (dp << "[scop-detection-fail] cannot represent loop_"
799 << loop->num << "\n");
800 return true;
801 }
802
803 /* Check if all loop nests have at least one data reference.
804 ??? This check is expensive and loops premature at this point.
805 If important to retain we can pre-compute this for all innermost
806 loops and reject those when we build a SESE region for a loop
807 during SESE discovery. */
808 if (! loop->inner
809 && ! loop_nest_has_data_refs (loop))
810 {
811 DEBUG_PRINT (dp << "[scop-detection-fail] loop_" << loop->num
812 << "does not have any data reference.\n");
813 return true;
814 }
815 }
816
817 return false;
818 }
819
820 /* Returns true if S1 subsumes/surrounds S2. */
821 bool
822 scop_detection::subsumes (sese_l s1, sese_l s2)
823 {
824 if (dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
825 get_entry_bb (s1))
826 && dominated_by_p (CDI_POST_DOMINATORS, s2.exit->dest,
827 s1.exit->dest))
828 return true;
829 return false;
830 }
831
832 /* Remove a SCoP which is subsumed by S1. */
833 void
834 scop_detection::remove_subscops (sese_l s1)
835 {
836 int j;
837 sese_l *s2;
838 FOR_EACH_VEC_ELT_REVERSE (scops, j, s2)
839 {
840 if (subsumes (s1, *s2))
841 {
842 DEBUG_PRINT (dp << "Removing sub-SCoP";
843 print_sese (dump_file, *s2));
844 scops.unordered_remove (j);
845 }
846 }
847 }
848
849 /* Returns true if S1 intersects with S2. Since we already know that S1 does
850 not subsume S2 or vice-versa, we only check for entry bbs. */
851
852 bool
853 scop_detection::intersects (sese_l s1, sese_l s2)
854 {
855 if (dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
856 get_entry_bb (s1))
857 && !dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
858 get_exit_bb (s1)))
859 return true;
860 if ((s1.exit == s2.entry) || (s2.exit == s1.entry))
861 return true;
862
863 return false;
864 }
865
866 /* Remove one of the scops when it intersects with any other. */
867
868 void
869 scop_detection::remove_intersecting_scops (sese_l s1)
870 {
871 int j;
872 sese_l *s2;
873 FOR_EACH_VEC_ELT_REVERSE (scops, j, s2)
874 {
875 if (intersects (s1, *s2))
876 {
877 DEBUG_PRINT (dp << "Removing intersecting SCoP";
878 print_sese (dump_file, *s2);
879 dp << "Intersects with:";
880 print_sese (dump_file, s1));
881 scops.unordered_remove (j);
882 }
883 }
884 }
885
886 /* Something like "n * m" is not allowed. */
887
888 bool
889 scop_detection::graphite_can_represent_init (tree e)
890 {
891 switch (TREE_CODE (e))
892 {
893 case POLYNOMIAL_CHREC:
894 return graphite_can_represent_init (CHREC_LEFT (e))
895 && graphite_can_represent_init (CHREC_RIGHT (e));
896
897 case MULT_EXPR:
898 if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
899 return graphite_can_represent_init (TREE_OPERAND (e, 0))
900 && tree_fits_shwi_p (TREE_OPERAND (e, 1));
901 else
902 return graphite_can_represent_init (TREE_OPERAND (e, 1))
903 && tree_fits_shwi_p (TREE_OPERAND (e, 0));
904
905 case PLUS_EXPR:
906 case POINTER_PLUS_EXPR:
907 case MINUS_EXPR:
908 return graphite_can_represent_init (TREE_OPERAND (e, 0))
909 && graphite_can_represent_init (TREE_OPERAND (e, 1));
910
911 case NEGATE_EXPR:
912 case BIT_NOT_EXPR:
913 CASE_CONVERT:
914 case NON_LVALUE_EXPR:
915 return graphite_can_represent_init (TREE_OPERAND (e, 0));
916
917 default:
918 break;
919 }
920
921 return true;
922 }
923
924 /* Return true when SCEV can be represented in the polyhedral model.
925
926 An expression can be represented, if it can be expressed as an
927 affine expression. For loops (i, j) and parameters (m, n) all
928 affine expressions are of the form:
929
930 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
931
932 1 i + 20 j + (-2) m + 25
933
934 Something like "i * n" or "n * m" is not allowed. */
935
936 bool
937 scop_detection::graphite_can_represent_scev (sese_l scop, tree scev)
938 {
939 if (chrec_contains_undetermined (scev))
940 return false;
941
942 switch (TREE_CODE (scev))
943 {
944 case NEGATE_EXPR:
945 case BIT_NOT_EXPR:
946 CASE_CONVERT:
947 case NON_LVALUE_EXPR:
948 return graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0));
949
950 case PLUS_EXPR:
951 case POINTER_PLUS_EXPR:
952 case MINUS_EXPR:
953 return graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0))
954 && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 1));
955
956 case MULT_EXPR:
957 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 0)))
958 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 1)))
959 && !(chrec_contains_symbols (TREE_OPERAND (scev, 0))
960 && chrec_contains_symbols (TREE_OPERAND (scev, 1)))
961 && graphite_can_represent_init (scev)
962 && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0))
963 && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 1));
964
965 case POLYNOMIAL_CHREC:
966 /* Check for constant strides. With a non constant stride of
967 'n' we would have a value of 'iv * n'. Also check that the
968 initial value can represented: for example 'n * m' cannot be
969 represented. */
970 gcc_assert (loop_in_sese_p (get_loop (cfun,
971 CHREC_VARIABLE (scev)), scop));
972 if (!evolution_function_right_is_integer_cst (scev)
973 || !graphite_can_represent_init (scev))
974 return false;
975 return graphite_can_represent_scev (scop, CHREC_LEFT (scev));
976
977 default:
978 break;
979 }
980
981 /* Only affine functions can be represented. */
982 if (tree_contains_chrecs (scev, NULL) || !scev_is_linear_expression (scev))
983 return false;
984
985 return true;
986 }
987
988 /* Return true when EXPR can be represented in the polyhedral model.
989
990 This means an expression can be represented, if it is linear with respect to
991 the loops and the strides are non parametric. LOOP is the place where the
992 expr will be evaluated. SCOP defines the region we analyse. */
993
994 bool
995 scop_detection::graphite_can_represent_expr (sese_l scop, loop_p loop,
996 tree expr)
997 {
998 tree scev = scalar_evolution_in_region (scop, loop, expr);
999 return graphite_can_represent_scev (scop, scev);
1000 }
1001
1002 /* Return true if the data references of STMT can be represented by Graphite.
1003 We try to analyze the data references in a loop contained in the SCOP. */
1004
1005 bool
1006 scop_detection::stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt)
1007 {
1008 edge nest = scop.entry;;
1009 loop_p loop = loop_containing_stmt (stmt);
1010 if (!loop_in_sese_p (loop, scop))
1011 loop = NULL;
1012
1013 auto_vec<data_reference_p> drs;
1014 if (! graphite_find_data_references_in_stmt (nest, loop, stmt, &drs))
1015 return false;
1016
1017 int j;
1018 data_reference_p dr;
1019 FOR_EACH_VEC_ELT (drs, j, dr)
1020 {
1021 for (unsigned i = 0; i < DR_NUM_DIMENSIONS (dr); ++i)
1022 if (! graphite_can_represent_scev (scop, DR_ACCESS_FN (dr, i)))
1023 return false;
1024 }
1025
1026 return true;
1027 }
1028
1029 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
1030 Calls have side-effects, except those to const or pure
1031 functions. */
1032
1033 static bool
1034 stmt_has_side_effects (gimple *stmt)
1035 {
1036 if (gimple_has_volatile_ops (stmt)
1037 || (gimple_code (stmt) == GIMPLE_CALL
1038 && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
1039 || (gimple_code (stmt) == GIMPLE_ASM))
1040 {
1041 DEBUG_PRINT (dp << "[scop-detection-fail] "
1042 << "Statement has side-effects:\n";
1043 print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS | TDF_MEMSYMS));
1044 return true;
1045 }
1046 return false;
1047 }
1048
1049 /* Return true only when STMT is simple enough for being handled by Graphite.
1050 This depends on SCOP, as the parameters are initialized relatively to
1051 this basic block, the linear functions are initialized based on the outermost
1052 loop containing STMT inside the SCOP. BB is the place where we try to
1053 evaluate the STMT. */
1054
1055 bool
1056 scop_detection::stmt_simple_for_scop_p (sese_l scop, gimple *stmt,
1057 basic_block bb) const
1058 {
1059 gcc_assert (scop);
1060
1061 if (is_gimple_debug (stmt))
1062 return true;
1063
1064 if (stmt_has_side_effects (stmt))
1065 return false;
1066
1067 if (!stmt_has_simple_data_refs_p (scop, stmt))
1068 {
1069 DEBUG_PRINT (dp << "[scop-detection-fail] "
1070 << "Graphite cannot handle data-refs in stmt:\n";
1071 print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS|TDF_MEMSYMS););
1072 return false;
1073 }
1074
1075 switch (gimple_code (stmt))
1076 {
1077 case GIMPLE_LABEL:
1078 return true;
1079
1080 case GIMPLE_COND:
1081 {
1082 /* We can handle all binary comparisons. Inequalities are
1083 also supported as they can be represented with union of
1084 polyhedra. */
1085 enum tree_code code = gimple_cond_code (stmt);
1086 if (!(code == LT_EXPR
1087 || code == GT_EXPR
1088 || code == LE_EXPR
1089 || code == GE_EXPR
1090 || code == EQ_EXPR
1091 || code == NE_EXPR))
1092 {
1093 DEBUG_PRINT (dp << "[scop-detection-fail] "
1094 << "Graphite cannot handle cond stmt:\n";
1095 print_gimple_stmt (dump_file, stmt, 0,
1096 TDF_VOPS | TDF_MEMSYMS));
1097 return false;
1098 }
1099
1100 loop_p loop = bb->loop_father;
1101 for (unsigned i = 0; i < 2; ++i)
1102 {
1103 tree op = gimple_op (stmt, i);
1104 if (!graphite_can_represent_expr (scop, loop, op)
1105 /* We can only constrain on integer type. */
1106 || ! INTEGRAL_TYPE_P (TREE_TYPE (op)))
1107 {
1108 DEBUG_PRINT (dp << "[scop-detection-fail] "
1109 << "Graphite cannot represent stmt:\n";
1110 print_gimple_stmt (dump_file, stmt, 0,
1111 TDF_VOPS | TDF_MEMSYMS));
1112 return false;
1113 }
1114 }
1115
1116 return true;
1117 }
1118
1119 case GIMPLE_ASSIGN:
1120 case GIMPLE_CALL:
1121 return true;
1122
1123 default:
1124 /* These nodes cut a new scope. */
1125 DEBUG_PRINT (
1126 dp << "[scop-detection-fail] "
1127 << "Gimple stmt not handled in Graphite:\n";
1128 print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS | TDF_MEMSYMS));
1129 return false;
1130 }
1131 }
1132
1133 /* Returns the number of pbbs that are in loops contained in SCOP. */
1134
1135 int
1136 scop_detection::nb_pbbs_in_loops (scop_p scop)
1137 {
1138 int i;
1139 poly_bb_p pbb;
1140 int res = 0;
1141
1142 FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
1143 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb)), scop->scop_info->region))
1144 res++;
1145
1146 return res;
1147 }
1148
1149 /* Assigns the parameter NAME an index in REGION. */
1150
1151 static void
1152 assign_parameter_index_in_region (tree name, sese_info_p region)
1153 {
1154 gcc_assert (TREE_CODE (name) == SSA_NAME
1155 && INTEGRAL_TYPE_P (TREE_TYPE (name))
1156 && ! defined_in_sese_p (name, region->region));
1157
1158 int i;
1159 tree p;
1160 FOR_EACH_VEC_ELT (region->params, i, p)
1161 if (p == name)
1162 return;
1163
1164 i = region->params.length ();
1165 region->params.safe_push (name);
1166 }
1167
1168 /* In the context of sese S, scan the expression E and translate it to
1169 a linear expression C. When parsing a symbolic multiplication, K
1170 represents the constant multiplier of an expression containing
1171 parameters. */
1172
1173 static void
1174 scan_tree_for_params (sese_info_p s, tree e)
1175 {
1176 if (e == chrec_dont_know)
1177 return;
1178
1179 switch (TREE_CODE (e))
1180 {
1181 case POLYNOMIAL_CHREC:
1182 scan_tree_for_params (s, CHREC_LEFT (e));
1183 break;
1184
1185 case MULT_EXPR:
1186 if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
1187 scan_tree_for_params (s, TREE_OPERAND (e, 0));
1188 else
1189 scan_tree_for_params (s, TREE_OPERAND (e, 1));
1190 break;
1191
1192 case PLUS_EXPR:
1193 case POINTER_PLUS_EXPR:
1194 case MINUS_EXPR:
1195 scan_tree_for_params (s, TREE_OPERAND (e, 0));
1196 scan_tree_for_params (s, TREE_OPERAND (e, 1));
1197 break;
1198
1199 case NEGATE_EXPR:
1200 case BIT_NOT_EXPR:
1201 CASE_CONVERT:
1202 case NON_LVALUE_EXPR:
1203 scan_tree_for_params (s, TREE_OPERAND (e, 0));
1204 break;
1205
1206 case SSA_NAME:
1207 assign_parameter_index_in_region (e, s);
1208 break;
1209
1210 case INTEGER_CST:
1211 case ADDR_EXPR:
1212 case REAL_CST:
1213 case COMPLEX_CST:
1214 case VECTOR_CST:
1215 break;
1216
1217 default:
1218 gcc_unreachable ();
1219 break;
1220 }
1221 }
1222
1223 /* Find parameters with respect to REGION in BB. We are looking in memory
1224 access functions, conditions and loop bounds. */
1225
1226 static void
1227 find_params_in_bb (sese_info_p region, gimple_poly_bb_p gbb)
1228 {
1229 /* Find parameters in the access functions of data references. */
1230 int i;
1231 data_reference_p dr;
1232 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb), i, dr)
1233 for (unsigned j = 0; j < DR_NUM_DIMENSIONS (dr); j++)
1234 scan_tree_for_params (region, DR_ACCESS_FN (dr, j));
1235
1236 /* Find parameters in conditional statements. */
1237 gimple *stmt;
1238 loop_p loop = GBB_BB (gbb)->loop_father;
1239 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb), i, stmt)
1240 {
1241 tree lhs = scalar_evolution_in_region (region->region, loop,
1242 gimple_cond_lhs (stmt));
1243 tree rhs = scalar_evolution_in_region (region->region, loop,
1244 gimple_cond_rhs (stmt));
1245
1246 scan_tree_for_params (region, lhs);
1247 scan_tree_for_params (region, rhs);
1248 }
1249 }
1250
1251 /* Record the parameters used in the SCOP BBs. A variable is a parameter
1252 in a scop if it does not vary during the execution of that scop. */
1253
1254 static void
1255 find_scop_parameters (scop_p scop)
1256 {
1257 unsigned i;
1258 sese_info_p region = scop->scop_info;
1259
1260 /* Parameters used in loop bounds are processed during gather_bbs. */
1261
1262 /* Find the parameters used in data accesses. */
1263 poly_bb_p pbb;
1264 FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
1265 find_params_in_bb (region, PBB_BLACK_BOX (pbb));
1266
1267 int nbp = sese_nb_params (region);
1268 scop_set_nb_params (scop, nbp);
1269 }
1270
1271 static void
1272 add_write (vec<tree> *writes, tree def)
1273 {
1274 writes->safe_push (def);
1275 DEBUG_PRINT (dp << "Adding scalar write: ";
1276 print_generic_expr (dump_file, def);
1277 dp << "\nFrom stmt: ";
1278 print_gimple_stmt (dump_file,
1279 SSA_NAME_DEF_STMT (def), 0));
1280 }
1281
1282 static void
1283 add_read (vec<scalar_use> *reads, tree use, gimple *use_stmt)
1284 {
1285 DEBUG_PRINT (dp << "Adding scalar read: ";
1286 print_generic_expr (dump_file, use);
1287 dp << "\nFrom stmt: ";
1288 print_gimple_stmt (dump_file, use_stmt, 0));
1289 reads->safe_push (std::make_pair (use_stmt, use));
1290 }
1291
1292
1293 /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP. */
1294
1295 static void
1296 build_cross_bb_scalars_def (scop_p scop, tree def, basic_block def_bb,
1297 vec<tree> *writes)
1298 {
1299 if (!is_gimple_reg (def))
1300 return;
1301
1302 bool scev_analyzable = scev_analyzable_p (def, scop->scop_info->region);
1303
1304 gimple *use_stmt;
1305 imm_use_iterator imm_iter;
1306 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
1307 /* Do not gather scalar variables that can be analyzed by SCEV as they can
1308 be generated out of the induction variables. */
1309 if ((! scev_analyzable
1310 /* But gather SESE liveouts as we otherwise fail to rewrite their
1311 exit PHIs. */
1312 || ! bb_in_sese_p (gimple_bb (use_stmt), scop->scop_info->region))
1313 && (def_bb != gimple_bb (use_stmt) && !is_gimple_debug (use_stmt)))
1314 {
1315 add_write (writes, def);
1316 /* This is required by the FOR_EACH_IMM_USE_STMT when we want to break
1317 before all the uses have been visited. */
1318 BREAK_FROM_IMM_USE_STMT (imm_iter);
1319 }
1320 }
1321
1322 /* Record USE if it is defined in other bbs different than USE_STMT
1323 in the SCOP. */
1324
1325 static void
1326 build_cross_bb_scalars_use (scop_p scop, tree use, gimple *use_stmt,
1327 vec<scalar_use> *reads)
1328 {
1329 if (!is_gimple_reg (use))
1330 return;
1331
1332 /* Do not gather scalar variables that can be analyzed by SCEV as they can be
1333 generated out of the induction variables. */
1334 if (scev_analyzable_p (use, scop->scop_info->region))
1335 return;
1336
1337 gimple *def_stmt = SSA_NAME_DEF_STMT (use);
1338 if (gimple_bb (def_stmt) != gimple_bb (use_stmt))
1339 add_read (reads, use, use_stmt);
1340 }
1341
1342 /* Generates a polyhedral black box only if the bb contains interesting
1343 information. */
1344
1345 static gimple_poly_bb_p
1346 try_generate_gimple_bb (scop_p scop, basic_block bb)
1347 {
1348 vec<data_reference_p> drs = vNULL;
1349 vec<tree> writes = vNULL;
1350 vec<scalar_use> reads = vNULL;
1351
1352 sese_l region = scop->scop_info->region;
1353 edge nest = region.entry;
1354 loop_p loop = bb->loop_father;
1355 if (!loop_in_sese_p (loop, region))
1356 loop = NULL;
1357
1358 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1359 gsi_next (&gsi))
1360 {
1361 gimple *stmt = gsi_stmt (gsi);
1362 if (is_gimple_debug (stmt))
1363 continue;
1364
1365 graphite_find_data_references_in_stmt (nest, loop, stmt, &drs);
1366
1367 tree def = gimple_get_lhs (stmt);
1368 if (def)
1369 build_cross_bb_scalars_def (scop, def, gimple_bb (stmt), &writes);
1370
1371 ssa_op_iter iter;
1372 tree use;
1373 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
1374 build_cross_bb_scalars_use (scop, use, stmt, &reads);
1375 }
1376
1377 /* Handle defs and uses in PHIs. Those need special treatment given
1378 that we have to present ISL with sth that looks like we've rewritten
1379 the IL out-of-SSA. */
1380 for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);
1381 gsi_next (&psi))
1382 {
1383 gphi *phi = psi.phi ();
1384 tree res = gimple_phi_result (phi);
1385 if (virtual_operand_p (res)
1386 || scev_analyzable_p (res, scop->scop_info->region))
1387 continue;
1388 /* To simulate out-of-SSA the block containing the PHI node has
1389 reads of the PHI destination. And to preserve SSA dependences
1390 we also write to it (the out-of-SSA decl and the SSA result
1391 are coalesced for dependence purposes which is good enough). */
1392 add_read (&reads, res, phi);
1393 add_write (&writes, res);
1394 }
1395 basic_block bb_for_succs = bb;
1396 if (bb_for_succs == bb_for_succs->loop_father->latch
1397 && bb_in_sese_p (bb_for_succs, scop->scop_info->region)
1398 && sese_trivially_empty_bb_p (bb_for_succs))
1399 bb_for_succs = NULL;
1400 while (bb_for_succs)
1401 {
1402 basic_block latch = NULL;
1403 edge_iterator ei;
1404 edge e;
1405 FOR_EACH_EDGE (e, ei, bb_for_succs->succs)
1406 {
1407 for (gphi_iterator psi = gsi_start_phis (e->dest); !gsi_end_p (psi);
1408 gsi_next (&psi))
1409 {
1410 gphi *phi = psi.phi ();
1411 tree res = gimple_phi_result (phi);
1412 if (virtual_operand_p (res))
1413 continue;
1414 /* To simulate out-of-SSA the predecessor of edges into PHI nodes
1415 has a copy from the PHI argument to the PHI destination. */
1416 if (! scev_analyzable_p (res, scop->scop_info->region))
1417 add_write (&writes, res);
1418 tree use = PHI_ARG_DEF_FROM_EDGE (phi, e);
1419 if (TREE_CODE (use) == SSA_NAME
1420 && ! SSA_NAME_IS_DEFAULT_DEF (use)
1421 && gimple_bb (SSA_NAME_DEF_STMT (use)) != bb_for_succs
1422 && ! scev_analyzable_p (use, scop->scop_info->region))
1423 add_read (&reads, use, phi);
1424 }
1425 if (e->dest == bb_for_succs->loop_father->latch
1426 && bb_in_sese_p (e->dest, scop->scop_info->region)
1427 && sese_trivially_empty_bb_p (e->dest))
1428 latch = e->dest;
1429 }
1430 /* Handle empty latch block PHIs here, otherwise we confuse ISL
1431 with extra conditional code where it then peels off the last
1432 iteration just because of that. It would be simplest if we
1433 just didn't force simple latches (thus remove the forwarder). */
1434 bb_for_succs = latch;
1435 }
1436
1437 /* For the region exit block add reads for all live-out vars. */
1438 if (bb == scop->scop_info->region.exit->src)
1439 {
1440 sese_build_liveouts (scop->scop_info);
1441 unsigned i;
1442 bitmap_iterator bi;
1443 EXECUTE_IF_SET_IN_BITMAP (scop->scop_info->liveout, 0, i, bi)
1444 {
1445 tree use = ssa_name (i);
1446 add_read (&reads, use, NULL);
1447 }
1448 }
1449
1450 if (drs.is_empty () && writes.is_empty () && reads.is_empty ())
1451 return NULL;
1452
1453 return new_gimple_poly_bb (bb, drs, reads, writes);
1454 }
1455
1456 /* Compute alias-sets for all data references in DRS. */
1457
1458 static bool
1459 build_alias_set (scop_p scop)
1460 {
1461 int num_vertices = scop->drs.length ();
1462 struct graph *g = new_graph (num_vertices);
1463 dr_info *dr1, *dr2;
1464 int i, j;
1465 int *all_vertices;
1466
1467 FOR_EACH_VEC_ELT (scop->drs, i, dr1)
1468 for (j = i+1; scop->drs.iterate (j, &dr2); j++)
1469 if (dr_may_alias_p (dr1->dr, dr2->dr, true))
1470 {
1471 /* Dependences in the same alias set need to be handled
1472 by just looking at DR_ACCESS_FNs. */
1473 if (DR_NUM_DIMENSIONS (dr1->dr) == 0
1474 || DR_NUM_DIMENSIONS (dr1->dr) != DR_NUM_DIMENSIONS (dr2->dr)
1475 || ! operand_equal_p (DR_BASE_OBJECT (dr1->dr),
1476 DR_BASE_OBJECT (dr2->dr),
1477 OEP_ADDRESS_OF)
1478 || ! types_compatible_p (TREE_TYPE (DR_BASE_OBJECT (dr1->dr)),
1479 TREE_TYPE (DR_BASE_OBJECT (dr2->dr))))
1480 {
1481 free_graph (g);
1482 return false;
1483 }
1484 add_edge (g, i, j);
1485 add_edge (g, j, i);
1486 }
1487
1488 all_vertices = XNEWVEC (int, num_vertices);
1489 for (i = 0; i < num_vertices; i++)
1490 all_vertices[i] = i;
1491
1492 scop->max_alias_set
1493 = graphds_dfs (g, all_vertices, num_vertices, NULL, true, NULL) + 1;
1494 free (all_vertices);
1495
1496 for (i = 0; i < g->n_vertices; i++)
1497 scop->drs[i].alias_set = g->vertices[i].component + 1;
1498
1499 free_graph (g);
1500 return true;
1501 }
1502
1503 /* Gather BBs and conditions for a SCOP. */
1504 class gather_bbs : public dom_walker
1505 {
1506 public:
1507 gather_bbs (cdi_direction, scop_p, int *);
1508
1509 virtual edge before_dom_children (basic_block);
1510 virtual void after_dom_children (basic_block);
1511
1512 private:
1513 auto_vec<gimple *, 3> conditions, cases;
1514 scop_p scop;
1515 };
1516 }
1517 gather_bbs::gather_bbs (cdi_direction direction, scop_p scop, int *bb_to_rpo)
1518 : dom_walker (direction, false, bb_to_rpo), scop (scop)
1519 {
1520 }
1521
1522 /* Call-back for dom_walk executed before visiting the dominated
1523 blocks. */
1524
1525 edge
1526 gather_bbs::before_dom_children (basic_block bb)
1527 {
1528 sese_info_p region = scop->scop_info;
1529 if (!bb_in_sese_p (bb, region->region))
1530 return dom_walker::STOP;
1531
1532 /* For loops fully contained in the region record parameters in the
1533 loop bounds. */
1534 loop_p loop = bb->loop_father;
1535 if (loop->header == bb
1536 && loop_in_sese_p (loop, region->region))
1537 {
1538 tree nb_iters = number_of_latch_executions (loop);
1539 if (chrec_contains_symbols (nb_iters))
1540 {
1541 nb_iters = scalar_evolution_in_region (region->region,
1542 loop, nb_iters);
1543 scan_tree_for_params (region, nb_iters);
1544 }
1545 }
1546
1547 gcond *stmt = single_pred_cond_non_loop_exit (bb);
1548
1549 if (stmt)
1550 {
1551 edge e = single_pred_edge (bb);
1552
1553 conditions.safe_push (stmt);
1554
1555 if (e->flags & EDGE_TRUE_VALUE)
1556 cases.safe_push (stmt);
1557 else
1558 cases.safe_push (NULL);
1559 }
1560
1561 scop->scop_info->bbs.safe_push (bb);
1562
1563 gimple_poly_bb_p gbb = try_generate_gimple_bb (scop, bb);
1564 if (!gbb)
1565 return NULL;
1566
1567 GBB_CONDITIONS (gbb) = conditions.copy ();
1568 GBB_CONDITION_CASES (gbb) = cases.copy ();
1569
1570 poly_bb_p pbb = new_poly_bb (scop, gbb);
1571 scop->pbbs.safe_push (pbb);
1572
1573 int i;
1574 data_reference_p dr;
1575 FOR_EACH_VEC_ELT (gbb->data_refs, i, dr)
1576 {
1577 DEBUG_PRINT (dp << "Adding memory ";
1578 if (dr->is_read)
1579 dp << "read: ";
1580 else
1581 dp << "write: ";
1582 print_generic_expr (dump_file, dr->ref);
1583 dp << "\nFrom stmt: ";
1584 print_gimple_stmt (dump_file, dr->stmt, 0));
1585
1586 scop->drs.safe_push (dr_info (dr, pbb));
1587 }
1588
1589 return NULL;
1590 }
1591
1592 /* Call-back for dom_walk executed after visiting the dominated
1593 blocks. */
1594
1595 void
1596 gather_bbs::after_dom_children (basic_block bb)
1597 {
1598 if (!bb_in_sese_p (bb, scop->scop_info->region))
1599 return;
1600
1601 if (single_pred_cond_non_loop_exit (bb))
1602 {
1603 conditions.pop ();
1604 cases.pop ();
1605 }
1606 }
1607
1608
1609 /* Compute sth like an execution order, dominator order with first executing
1610 edges that stay inside the current loop, delaying processing exit edges. */
1611
1612 static vec<unsigned> order;
1613
1614 static void
1615 get_order (scop_p scop, basic_block bb, vec<unsigned> *order, unsigned *dfs_num)
1616 {
1617 if (! bb_in_sese_p (bb, scop->scop_info->region))
1618 return;
1619
1620 (*order)[bb->index] = (*dfs_num)++;
1621 for (basic_block son = first_dom_son (CDI_DOMINATORS, bb);
1622 son;
1623 son = next_dom_son (CDI_DOMINATORS, son))
1624 if (flow_bb_inside_loop_p (bb->loop_father, son))
1625 get_order (scop, son, order, dfs_num);
1626 for (basic_block son = first_dom_son (CDI_DOMINATORS, bb);
1627 son;
1628 son = next_dom_son (CDI_DOMINATORS, son))
1629 if (! flow_bb_inside_loop_p (bb->loop_father, son))
1630 get_order (scop, son, order, dfs_num);
1631 }
1632
1633 /* Helper for qsort, sorting after order above. */
1634
1635 static int
1636 cmp_pbbs (const void *pa, const void *pb)
1637 {
1638 poly_bb_p bb1 = *((const poly_bb_p *)pa);
1639 poly_bb_p bb2 = *((const poly_bb_p *)pb);
1640 if (order[bb1->black_box->bb->index] < order[bb2->black_box->bb->index])
1641 return -1;
1642 else if (order[bb1->black_box->bb->index] > order[bb2->black_box->bb->index])
1643 return 1;
1644 else
1645 return 0;
1646 }
1647
1648 /* Find Static Control Parts (SCoP) in the current function and pushes
1649 them to SCOPS. */
1650
1651 void
1652 build_scops (vec<scop_p> *scops)
1653 {
1654 if (dump_file)
1655 dp.set_dump_file (dump_file);
1656
1657 scop_detection sb;
1658 sb.build_scop_depth (current_loops->tree_root);
1659
1660 /* Now create scops from the lightweight SESEs. */
1661 vec<sese_l> scops_l = sb.get_scops ();
1662
1663 /* Domwalk needs a bb to RPO mapping. Compute it once here. */
1664 int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
1665 int postorder_num = pre_and_rev_post_order_compute (NULL, postorder, true);
1666 int *bb_to_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun));
1667 for (int i = 0; i < postorder_num; ++i)
1668 bb_to_rpo[postorder[i]] = i;
1669 free (postorder);
1670
1671 int i;
1672 sese_l *s;
1673 FOR_EACH_VEC_ELT (scops_l, i, s)
1674 {
1675 scop_p scop = new_scop (s->entry, s->exit);
1676
1677 /* Record all basic blocks and their conditions in REGION. */
1678 gather_bbs (CDI_DOMINATORS, scop, bb_to_rpo).walk (s->entry->dest);
1679
1680 /* domwalk does not fulfil our code-generations constraints on the
1681 order of pbb which is to produce sth like execution order, delaying
1682 exection of loop exit edges. So compute such order and sort after
1683 that. */
1684 order.create (last_basic_block_for_fn (cfun));
1685 order.quick_grow (last_basic_block_for_fn (cfun));
1686 unsigned dfs_num = 0;
1687 get_order (scop, s->entry->dest, &order, &dfs_num);
1688 scop->pbbs.qsort (cmp_pbbs);
1689 order.release ();
1690
1691 if (! build_alias_set (scop))
1692 {
1693 DEBUG_PRINT (dp << "[scop-detection-fail] cannot handle dependences\n");
1694 free_scop (scop);
1695 continue;
1696 }
1697
1698 /* Do not optimize a scop containing only PBBs that do not belong
1699 to any loops. */
1700 if (sb.nb_pbbs_in_loops (scop) == 0)
1701 {
1702 DEBUG_PRINT (dp << "[scop-detection-fail] no data references.\n");
1703 free_scop (scop);
1704 continue;
1705 }
1706
1707 unsigned max_arrays = PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP);
1708 if (max_arrays > 0
1709 && scop->drs.length () >= max_arrays)
1710 {
1711 DEBUG_PRINT (dp << "[scop-detection-fail] too many data references: "
1712 << scop->drs.length ()
1713 << " is larger than --param graphite-max-arrays-per-scop="
1714 << max_arrays << ".\n");
1715 free_scop (scop);
1716 continue;
1717 }
1718
1719 find_scop_parameters (scop);
1720 graphite_dim_t max_dim = PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS);
1721 if (max_dim > 0
1722 && scop_nb_params (scop) > max_dim)
1723 {
1724 DEBUG_PRINT (dp << "[scop-detection-fail] too many parameters: "
1725 << scop_nb_params (scop)
1726 << " larger than --param graphite-max-nb-scop-params="
1727 << max_dim << ".\n");
1728 free_scop (scop);
1729 continue;
1730 }
1731
1732 scops->safe_push (scop);
1733 }
1734
1735 free (bb_to_rpo);
1736 DEBUG_PRINT (dp << "number of SCoPs: " << (scops ? scops->length () : 0););
1737 }
1738
1739 #endif /* HAVE_isl */