]>
Commit | Line | Data |
---|---|---|
2abae5f1 | 1 | /* Detection of Static Control Parts (SCoP) for Graphite. |
a5544970 | 2 | Copyright (C) 2009-2019 Free Software Foundation, Inc. |
2abae5f1 SP |
3 | Contributed by Sebastian Pop <sebastian.pop@amd.com> and |
4 | Tobias Grosser <grosser@fim.uni-passau.de>. | |
5 | ||
6 | This file is part of GCC. | |
7 | ||
8 | GCC is free software; you can redistribute it and/or modify | |
9 | it under the terms of the GNU General Public License as published by | |
10 | the Free Software Foundation; either version 3, or (at your option) | |
11 | any later version. | |
12 | ||
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. | |
17 | ||
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/>. */ | |
21 | ||
4d776011 DE |
22 | #define USES_ISL |
23 | ||
2abae5f1 | 24 | #include "config.h" |
33ad93b9 | 25 | |
eae1a5d4 | 26 | #ifdef HAVE_isl |
33ad93b9 | 27 | |
2abae5f1 SP |
28 | #include "system.h" |
29 | #include "coretypes.h" | |
c7131fb2 | 30 | #include "backend.h" |
9fdcd34e | 31 | #include "cfghooks.h" |
076d564d | 32 | #include "domwalk.h" |
7009b073 | 33 | #include "params.h" |
40e23961 | 34 | #include "tree.h" |
c7131fb2 | 35 | #include "gimple.h" |
c7131fb2 | 36 | #include "ssa.h" |
c7131fb2 | 37 | #include "fold-const.h" |
5be5c238 | 38 | #include "gimple-iterator.h" |
076d564d | 39 | #include "tree-cfg.h" |
e28030cf AM |
40 | #include "tree-ssa-loop-manip.h" |
41 | #include "tree-ssa-loop-niter.h" | |
442b4905 AM |
42 | #include "tree-ssa-loop.h" |
43 | #include "tree-into-ssa.h" | |
7a300452 | 44 | #include "tree-ssa.h" |
2abae5f1 | 45 | #include "cfgloop.h" |
2abae5f1 SP |
46 | #include "tree-data-ref.h" |
47 | #include "tree-scalar-evolution.h" | |
48 | #include "tree-pass.h" | |
9c358739 | 49 | #include "tree-ssa-propagate.h" |
33df361a | 50 | #include "gimple-pretty-print.h" |
d2552094 | 51 | #include "cfganal.h" |
cf98f0f4 | 52 | #include "graphite.h" |
4d776011 | 53 | |
076d564d AK |
54 | class debug_printer |
55 | { | |
56 | private: | |
57 | FILE *dump_file; | |
58 | ||
59 | public: | |
60 | void | |
61 | set_dump_file (FILE *f) | |
62 | { | |
63 | gcc_assert (f); | |
64 | dump_file = f; | |
65 | } | |
66 | ||
67 | friend debug_printer & | |
68 | operator<< (debug_printer &output, int i) | |
69 | { | |
70 | fprintf (output.dump_file, "%d", i); | |
71 | return output; | |
72 | } | |
73 | friend debug_printer & | |
74 | operator<< (debug_printer &output, const char *s) | |
75 | { | |
76 | fprintf (output.dump_file, "%s", s); | |
77 | return output; | |
78 | } | |
79 | } dp; | |
80 | ||
81 | #define DEBUG_PRINT(args) do \ | |
82 | { \ | |
83 | if (dump_file && (dump_flags & TDF_DETAILS)) { args; } \ | |
f9c1b67a | 84 | } while (0) |
076d564d | 85 | |
1b38d3ec AK |
86 | /* Pretty print to FILE all the SCoPs in DOT format and mark them with |
87 | different colors. If there are not enough colors, paint the | |
88 | remaining SCoPs in gray. | |
89 | ||
90 | Special nodes: | |
91 | - "*" after the node number denotes the entry of a SCoP, | |
92 | - "#" after the node number denotes the exit of a SCoP, | |
93 | - "()" around the node number denotes the entry or the | |
94 | exit nodes of the SCOP. These are not part of SCoP. */ | |
95 | ||
15256e28 AK |
96 | DEBUG_FUNCTION void |
97 | dot_all_sese (FILE *file, vec<sese_l>& scops) | |
1b38d3ec | 98 | { |
1b38d3ec | 99 | /* Disable debugging while printing graph. */ |
1a817418 ML |
100 | dump_flags_t tmp_dump_flags = dump_flags; |
101 | dump_flags = TDF_NONE; | |
1b38d3ec AK |
102 | |
103 | fprintf (file, "digraph all {\n"); | |
104 | ||
15256e28 | 105 | basic_block bb; |
1b38d3ec AK |
106 | FOR_ALL_BB_FN (bb, cfun) |
107 | { | |
108 | int part_of_scop = false; | |
109 | ||
110 | /* Use HTML for every bb label. So we are able to print bbs | |
111 | which are part of two different SCoPs, with two different | |
112 | background colors. */ | |
113 | fprintf (file, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ", | |
114 | bb->index); | |
115 | fprintf (file, "CELLSPACING=\"0\">\n"); | |
116 | ||
117 | /* Select color for SCoP. */ | |
15256e28 AK |
118 | sese_l *region; |
119 | int i; | |
120 | FOR_EACH_VEC_ELT (scops, i, region) | |
1b38d3ec | 121 | { |
15256e28 AK |
122 | bool sese_in_region = bb_in_sese_p (bb, *region); |
123 | if (sese_in_region || (region->exit->dest == bb) | |
124 | || (region->entry->dest == bb)) | |
1b38d3ec | 125 | { |
15256e28 | 126 | const char *color; |
1b38d3ec AK |
127 | switch (i % 17) |
128 | { | |
129 | case 0: /* red */ | |
130 | color = "#e41a1c"; | |
131 | break; | |
132 | case 1: /* blue */ | |
133 | color = "#377eb8"; | |
134 | break; | |
135 | case 2: /* green */ | |
136 | color = "#4daf4a"; | |
137 | break; | |
138 | case 3: /* purple */ | |
139 | color = "#984ea3"; | |
140 | break; | |
141 | case 4: /* orange */ | |
142 | color = "#ff7f00"; | |
143 | break; | |
144 | case 5: /* yellow */ | |
145 | color = "#ffff33"; | |
146 | break; | |
147 | case 6: /* brown */ | |
148 | color = "#a65628"; | |
149 | break; | |
150 | case 7: /* rose */ | |
151 | color = "#f781bf"; | |
152 | break; | |
153 | case 8: | |
154 | color = "#8dd3c7"; | |
155 | break; | |
156 | case 9: | |
157 | color = "#ffffb3"; | |
158 | break; | |
159 | case 10: | |
160 | color = "#bebada"; | |
161 | break; | |
162 | case 11: | |
163 | color = "#fb8072"; | |
164 | break; | |
165 | case 12: | |
166 | color = "#80b1d3"; | |
167 | break; | |
168 | case 13: | |
169 | color = "#fdb462"; | |
170 | break; | |
171 | case 14: | |
172 | color = "#b3de69"; | |
173 | break; | |
174 | case 15: | |
175 | color = "#fccde5"; | |
176 | break; | |
177 | case 16: | |
178 | color = "#bc80bd"; | |
179 | break; | |
180 | default: /* gray */ | |
181 | color = "#999999"; | |
182 | } | |
183 | ||
184 | fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", | |
185 | color); | |
186 | ||
15256e28 | 187 | if (!sese_in_region) |
1b38d3ec AK |
188 | fprintf (file, " ("); |
189 | ||
15256e28 | 190 | if (bb == region->entry->dest && bb == region->exit->dest) |
1b38d3ec | 191 | fprintf (file, " %d*# ", bb->index); |
15256e28 | 192 | else if (bb == region->entry->dest) |
1b38d3ec | 193 | fprintf (file, " %d* ", bb->index); |
15256e28 | 194 | else if (bb == region->exit->dest) |
1b38d3ec AK |
195 | fprintf (file, " %d# ", bb->index); |
196 | else | |
197 | fprintf (file, " %d ", bb->index); | |
198 | ||
199 | fprintf (file, "{lp_%d}", bb->loop_father->num); | |
200 | ||
15256e28 | 201 | if (!sese_in_region) |
1b38d3ec AK |
202 | fprintf (file, ")"); |
203 | ||
204 | fprintf (file, "</TD></TR>\n"); | |
205 | part_of_scop = true; | |
206 | } | |
207 | } | |
208 | ||
209 | if (!part_of_scop) | |
210 | { | |
211 | fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">"); | |
212 | fprintf (file, " %d {lp_%d} </TD></TR>\n", bb->index, | |
213 | bb->loop_father->num); | |
214 | } | |
215 | fprintf (file, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n"); | |
216 | } | |
217 | ||
218 | FOR_ALL_BB_FN (bb, cfun) | |
219 | { | |
15256e28 AK |
220 | edge e; |
221 | edge_iterator ei; | |
1b38d3ec AK |
222 | FOR_EACH_EDGE (e, ei, bb->succs) |
223 | fprintf (file, "%d -> %d;\n", bb->index, e->dest->index); | |
224 | } | |
225 | ||
226 | fputs ("}\n\n", file); | |
227 | ||
228 | /* Enable debugging again. */ | |
229 | dump_flags = tmp_dump_flags; | |
230 | } | |
231 | ||
15256e28 | 232 | /* Display SCoP on stderr. */ |
1b38d3ec AK |
233 | |
234 | DEBUG_FUNCTION void | |
15256e28 | 235 | dot_sese (sese_l& scop) |
1b38d3ec | 236 | { |
15256e28 AK |
237 | vec<sese_l> scops; |
238 | scops.create (1); | |
1b38d3ec AK |
239 | |
240 | if (scop) | |
241 | scops.safe_push (scop); | |
242 | ||
15256e28 | 243 | dot_all_sese (stderr, scops); |
1b38d3ec | 244 | |
15256e28 AK |
245 | scops.release (); |
246 | } | |
247 | ||
248 | DEBUG_FUNCTION void | |
249 | dot_cfg () | |
250 | { | |
251 | vec<sese_l> scops; | |
252 | scops.create (1); | |
253 | dot_all_sese (stderr, scops); | |
254 | scops.release (); | |
1b38d3ec | 255 | } |
076d564d | 256 | |
076d564d AK |
257 | /* Returns a COND_EXPR statement when BB has a single predecessor, the |
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 | ||
ec17e433 ML |
292 | ~scop_detection () |
293 | { | |
294 | scops.release (); | |
295 | } | |
296 | ||
076d564d AK |
297 | /* A marker for invalid sese_l. */ |
298 | static sese_l invalid_sese; | |
299 | ||
300 | /* Return the SCOPS in this SCOP_DETECTION. */ | |
301 | ||
302 | vec<sese_l> | |
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 | ||
076d564d AK |
312 | /* Merge scops at same loop depth and returns the new sese. |
313 | Returns a new SESE when merge was successful, INVALID_SESE otherwise. */ | |
314 | ||
315 | sese_l merge_sese (sese_l first, sese_l second) const; | |
316 | ||
317 | /* Build scop outer->inner if possible. */ | |
318 | ||
ca617fd2 | 319 | void build_scop_depth (loop_p loop); |
076d564d AK |
320 | |
321 | /* Return true when BEGIN is the preheader edge of a loop with a single exit | |
322 | END. */ | |
323 | ||
324 | static bool region_has_one_loop (sese_l s); | |
325 | ||
326 | /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */ | |
327 | ||
328 | void add_scop (sese_l s); | |
329 | ||
330 | /* Returns true if S1 subsumes/surrounds S2. */ | |
331 | static bool subsumes (sese_l s1, sese_l s2); | |
332 | ||
333 | /* Remove a SCoP which is subsumed by S1. */ | |
334 | void remove_subscops (sese_l s1); | |
335 | ||
336 | /* Returns true if S1 intersects with S2. Since we already know that S1 does | |
337 | not subsume S2 or vice-versa, we only check for entry bbs. */ | |
338 | ||
339 | static bool intersects (sese_l s1, sese_l s2); | |
340 | ||
341 | /* Remove one of the scops when it intersects with any other. */ | |
342 | ||
343 | void remove_intersecting_scops (sese_l s1); | |
344 | ||
99124c31 | 345 | /* Return true when a statement in SCOP cannot be represented by Graphite. */ |
076d564d | 346 | |
d7eff5b2 | 347 | bool harmful_loop_in_region (sese_l scop) const; |
076d564d AK |
348 | |
349 | /* Return true only when STMT is simple enough for being handled by Graphite. | |
350 | This depends on SCOP, as the parameters are initialized relatively to | |
351 | this basic block, the linear functions are initialized based on the | |
352 | outermost loop containing STMT inside the SCOP. BB is the place where we | |
353 | try to evaluate the STMT. */ | |
354 | ||
355 | bool stmt_simple_for_scop_p (sese_l scop, gimple *stmt, | |
356 | basic_block bb) const; | |
357 | ||
358 | /* Something like "n * m" is not allowed. */ | |
359 | ||
360 | static bool graphite_can_represent_init (tree e); | |
361 | ||
362 | /* Return true when SCEV can be represented in the polyhedral model. | |
363 | ||
364 | An expression can be represented, if it can be expressed as an | |
365 | affine expression. For loops (i, j) and parameters (m, n) all | |
366 | affine expressions are of the form: | |
367 | ||
368 | x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z | |
369 | ||
370 | 1 i + 20 j + (-2) m + 25 | |
371 | ||
372 | Something like "i * n" or "n * m" is not allowed. */ | |
373 | ||
a68f286c | 374 | static bool graphite_can_represent_scev (sese_l scop, tree scev); |
076d564d AK |
375 | |
376 | /* Return true when EXPR can be represented in the polyhedral model. | |
377 | ||
378 | This means an expression can be represented, if it is linear with respect | |
379 | to the loops and the strides are non parametric. LOOP is the place where | |
380 | the expr will be evaluated. SCOP defines the region we analyse. */ | |
381 | ||
382 | static bool graphite_can_represent_expr (sese_l scop, loop_p loop, | |
383 | tree expr); | |
384 | ||
385 | /* Return true if the data references of STMT can be represented by Graphite. | |
386 | We try to analyze the data references in a loop contained in the SCOP. */ | |
387 | ||
388 | static bool stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt); | |
389 | ||
390 | /* Remove the close phi node at GSI and replace its rhs with the rhs | |
391 | of PHI. */ | |
392 | ||
393 | static void remove_duplicate_close_phi (gphi *phi, gphi_iterator *gsi); | |
394 | ||
395 | /* Returns true when Graphite can represent LOOP in SCOP. | |
396 | FIXME: For the moment, graphite cannot be used on loops that iterate using | |
397 | induction variables that wrap. */ | |
398 | ||
076d564d AK |
399 | static bool can_represent_loop (loop_p loop, sese_l scop); |
400 | ||
076d564d AK |
401 | /* Returns the number of pbbs that are in loops contained in SCOP. */ |
402 | ||
403 | static int nb_pbbs_in_loops (scop_p scop); | |
404 | ||
076d564d AK |
405 | private: |
406 | vec<sese_l> scops; | |
407 | }; | |
408 | ||
d37fc3aa | 409 | sese_l scop_detection::invalid_sese (NULL, NULL); |
076d564d AK |
410 | |
411 | /* Return an sese_l around the LOOP. */ | |
412 | ||
413 | sese_l | |
414 | scop_detection::get_sese (loop_p loop) | |
415 | { | |
416 | if (!loop) | |
417 | return invalid_sese; | |
418 | ||
3c16e99c | 419 | edge scop_begin = loop_preheader_edge (loop); |
076d564d | 420 | edge scop_end = single_exit (loop); |
b0bd3e52 | 421 | if (!scop_end || (scop_end->flags & (EDGE_COMPLEX|EDGE_FAKE))) |
076d564d | 422 | return invalid_sese; |
3c16e99c RB |
423 | |
424 | return sese_l (scop_begin, scop_end); | |
076d564d AK |
425 | } |
426 | ||
076d564d AK |
427 | /* Merge scops at same loop depth and returns the new sese. |
428 | Returns a new SESE when merge was successful, INVALID_SESE otherwise. */ | |
429 | ||
430 | sese_l | |
431 | scop_detection::merge_sese (sese_l first, sese_l second) const | |
432 | { | |
433 | /* In the trivial case first/second may be NULL. */ | |
434 | if (!first) | |
435 | return second; | |
436 | if (!second) | |
437 | return first; | |
438 | ||
d7eff5b2 AK |
439 | DEBUG_PRINT (dp << "[scop-detection] try merging sese s1: "; |
440 | print_sese (dump_file, first); | |
441 | dp << "[scop-detection] try merging sese s2: "; | |
076d564d AK |
442 | print_sese (dump_file, second)); |
443 | ||
7467ab42 RB |
444 | auto_bitmap worklist, in_sese_region; |
445 | bitmap_set_bit (worklist, get_entry_bb (first)->index); | |
446 | bitmap_set_bit (worklist, get_exit_bb (first)->index); | |
447 | bitmap_set_bit (worklist, get_entry_bb (second)->index); | |
448 | bitmap_set_bit (worklist, get_exit_bb (second)->index); | |
449 | edge entry = NULL, exit = NULL; | |
450 | ||
451 | /* We can optimize the case of adding a loop entry dest or exit | |
452 | src to the worklist (for single-exit loops) by skipping | |
453 | directly to the exit dest / entry src. in_sese_region | |
454 | doesn't have to cover all blocks in the region but merely | |
455 | its border it acts more like a visited bitmap. */ | |
456 | do | |
d721dc3c | 457 | { |
7467ab42 RB |
458 | int index = bitmap_first_set_bit (worklist); |
459 | bitmap_clear_bit (worklist, index); | |
460 | basic_block bb = BASIC_BLOCK_FOR_FN (cfun, index); | |
461 | edge_iterator ei; | |
462 | edge e; | |
463 | ||
464 | /* With fake exit edges we can end up with no possible exit. */ | |
465 | if (index == EXIT_BLOCK) | |
d721dc3c | 466 | { |
7467ab42 RB |
467 | DEBUG_PRINT (dp << "[scop-detection-fail] cannot merge seses.\n"); |
468 | return invalid_sese; | |
d721dc3c | 469 | } |
7467ab42 RB |
470 | |
471 | bitmap_set_bit (in_sese_region, bb->index); | |
472 | ||
473 | basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb); | |
474 | FOR_EACH_EDGE (e, ei, bb->preds) | |
475 | if (e->src == dom | |
476 | && (! entry | |
477 | || dominated_by_p (CDI_DOMINATORS, entry->dest, bb))) | |
478 | { | |
479 | if (entry | |
480 | && ! bitmap_bit_p (in_sese_region, entry->src->index)) | |
481 | bitmap_set_bit (worklist, entry->src->index); | |
482 | entry = e; | |
483 | } | |
484 | else if (! bitmap_bit_p (in_sese_region, e->src->index)) | |
485 | bitmap_set_bit (worklist, e->src->index); | |
486 | ||
487 | basic_block pdom = get_immediate_dominator (CDI_POST_DOMINATORS, bb); | |
488 | FOR_EACH_EDGE (e, ei, bb->succs) | |
489 | if (e->dest == pdom | |
490 | && (! exit | |
491 | || dominated_by_p (CDI_POST_DOMINATORS, exit->src, bb))) | |
492 | { | |
493 | if (exit | |
494 | && ! bitmap_bit_p (in_sese_region, exit->dest->index)) | |
495 | bitmap_set_bit (worklist, exit->dest->index); | |
496 | exit = e; | |
497 | } | |
498 | else if (! bitmap_bit_p (in_sese_region, e->dest->index)) | |
499 | bitmap_set_bit (worklist, e->dest->index); | |
d721dc3c | 500 | } |
7467ab42 | 501 | while (! bitmap_empty_p (worklist)); |
d721dc3c | 502 | |
7467ab42 RB |
503 | sese_l combined (entry, exit); |
504 | ||
076d564d AK |
505 | DEBUG_PRINT (dp << "[merged-sese] s1: "; print_sese (dump_file, combined)); |
506 | ||
507 | return combined; | |
508 | } | |
509 | ||
510 | /* Build scop outer->inner if possible. */ | |
511 | ||
ca617fd2 RB |
512 | void |
513 | scop_detection::build_scop_depth (loop_p loop) | |
076d564d | 514 | { |
ca617fd2 RB |
515 | sese_l s = invalid_sese; |
516 | loop = loop->inner; | |
517 | while (loop) | |
076d564d | 518 | { |
ca617fd2 RB |
519 | sese_l next = get_sese (loop); |
520 | if (! next | |
521 | || harmful_loop_in_region (next)) | |
d798497e | 522 | { |
ca617fd2 RB |
523 | if (s) |
524 | add_scop (s); | |
525 | build_scop_depth (loop); | |
526 | s = invalid_sese; | |
d798497e | 527 | } |
ca617fd2 RB |
528 | else if (! s) |
529 | s = next; | |
530 | else | |
531 | { | |
532 | sese_l combined = merge_sese (s, next); | |
533 | if (! combined | |
534 | || harmful_loop_in_region (combined)) | |
535 | { | |
536 | add_scop (s); | |
537 | s = next; | |
538 | } | |
539 | else | |
540 | s = combined; | |
541 | } | |
542 | loop = loop->next; | |
543 | } | |
544 | if (s) | |
545 | add_scop (s); | |
076d564d AK |
546 | } |
547 | ||
548 | /* Returns true when Graphite can represent LOOP in SCOP. | |
549 | FIXME: For the moment, graphite cannot be used on loops that iterate using | |
550 | induction variables that wrap. */ | |
551 | ||
552 | bool | |
ca617fd2 | 553 | scop_detection::can_represent_loop (loop_p loop, sese_l scop) |
076d564d AK |
554 | { |
555 | tree niter; | |
556 | struct tree_niter_desc niter_desc; | |
557 | ||
2ad04111 RB |
558 | /* We can only handle do {} while () style loops correctly. */ |
559 | edge exit = single_exit (loop); | |
560 | if (!exit | |
561 | || !single_pred_p (loop->latch) | |
562 | || exit->src != single_pred (loop->latch) | |
563 | || !empty_block_p (loop->latch)) | |
564 | return false; | |
565 | ||
566 | return !(loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP) | |
076d564d AK |
567 | && number_of_iterations_exit (loop, single_exit (loop), &niter_desc, false) |
568 | && niter_desc.control.no_overflow | |
569 | && (niter = number_of_latch_executions (loop)) | |
570 | && !chrec_contains_undetermined (niter) | |
571 | && graphite_can_represent_expr (scop, loop, niter); | |
572 | } | |
573 | ||
076d564d AK |
574 | /* Return true when BEGIN is the preheader edge of a loop with a single exit |
575 | END. */ | |
576 | ||
577 | bool | |
578 | scop_detection::region_has_one_loop (sese_l s) | |
579 | { | |
580 | edge begin = s.entry; | |
581 | edge end = s.exit; | |
582 | /* Check for a single perfectly nested loop. */ | |
583 | if (begin->dest->loop_father->inner) | |
584 | return false; | |
585 | ||
586 | /* Otherwise, check whether we have adjacent loops. */ | |
3c16e99c RB |
587 | return (single_pred_p (end->src) |
588 | && begin->dest->loop_father == single_pred (end->src)->loop_father); | |
076d564d AK |
589 | } |
590 | ||
591 | /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */ | |
592 | ||
593 | void | |
594 | scop_detection::add_scop (sese_l s) | |
595 | { | |
596 | gcc_assert (s); | |
597 | ||
0e0e545f RB |
598 | /* If the exit edge is fake discard the SCoP for now as we're removing the |
599 | fake edges again after analysis. */ | |
600 | if (s.exit->flags & EDGE_FAKE) | |
601 | { | |
602 | DEBUG_PRINT (dp << "[scop-detection-fail] Discarding infinite loop SCoP: "; | |
603 | print_sese (dump_file, s)); | |
604 | return; | |
605 | } | |
606 | ||
1dba94d4 RB |
607 | /* Include the BB with the loop-closed SSA PHI nodes, we need this |
608 | block in the region for code-generating out-of-SSA copies. | |
609 | canonicalize_loop_closed_ssa makes sure that is in proper shape. */ | |
610 | if (s.exit->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) | |
611 | && loop_exit_edge_p (s.exit->src->loop_father, s.exit)) | |
612 | { | |
613 | gcc_assert (single_pred_p (s.exit->dest) | |
614 | && single_succ_p (s.exit->dest) | |
615 | && sese_trivially_empty_bb_p (s.exit->dest)); | |
616 | s.exit = single_succ_edge (s.exit->dest); | |
617 | } | |
618 | ||
076d564d AK |
619 | /* Do not add scops with only one loop. */ |
620 | if (region_has_one_loop (s)) | |
621 | { | |
d7eff5b2 | 622 | DEBUG_PRINT (dp << "[scop-detection-fail] Discarding one loop SCoP: "; |
076d564d AK |
623 | print_sese (dump_file, s)); |
624 | return; | |
625 | } | |
626 | ||
bafcb153 | 627 | if (get_exit_bb (s) == EXIT_BLOCK_PTR_FOR_FN (cfun)) |
076d564d | 628 | { |
49385686 | 629 | DEBUG_PRINT (dp << "[scop-detection-fail] " |
d7eff5b2 | 630 | << "Discarding SCoP exiting to return: "; |
076d564d AK |
631 | print_sese (dump_file, s)); |
632 | return; | |
633 | } | |
634 | ||
635 | /* Remove all the scops which are subsumed by s. */ | |
636 | remove_subscops (s); | |
637 | ||
402cab17 AK |
638 | /* Remove intersecting scops. FIXME: It will be a good idea to keep |
639 | the non-intersecting part of the scop already in the list. */ | |
076d564d | 640 | remove_intersecting_scops (s); |
2abae5f1 | 641 | |
076d564d | 642 | scops.safe_push (s); |
d7eff5b2 | 643 | DEBUG_PRINT (dp << "[scop-detection] Adding SCoP: "; print_sese (dump_file, s)); |
7009b073 | 644 | } |
2abae5f1 | 645 | |
99124c31 | 646 | /* Return true when a statement in SCOP cannot be represented by Graphite. */ |
076d564d AK |
647 | |
648 | bool | |
d7eff5b2 | 649 | scop_detection::harmful_loop_in_region (sese_l scop) const |
2abae5f1 | 650 | { |
bafcb153 AK |
651 | basic_block exit_bb = get_exit_bb (scop); |
652 | basic_block entry_bb = get_entry_bb (scop); | |
2abae5f1 | 653 | |
49385686 | 654 | DEBUG_PRINT (dp << "[checking-harmful-bbs] "; |
076d564d AK |
655 | print_sese (dump_file, scop)); |
656 | gcc_assert (dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb)); | |
2abae5f1 | 657 | |
9c0c77d2 RB |
658 | auto_vec<basic_block> worklist; |
659 | auto_bitmap loops; | |
2abae5f1 | 660 | |
9c0c77d2 RB |
661 | worklist.safe_push (entry_bb); |
662 | while (! worklist.is_empty ()) | |
076d564d | 663 | { |
9c0c77d2 | 664 | basic_block bb = worklist.pop (); |
a378e922 | 665 | DEBUG_PRINT (dp << "Visiting bb_" << bb->index << "\n"); |
2abae5f1 | 666 | |
1167ebe7 AK |
667 | /* The basic block should not be part of an irreducible loop. */ |
668 | if (bb->flags & BB_IRREDUCIBLE_LOOP) | |
9c0c77d2 | 669 | return true; |
1167ebe7 | 670 | |
8f225262 AK |
671 | /* Check for unstructured control flow: CFG not generated by structured |
672 | if-then-else. */ | |
673 | if (bb->succs->length () > 1) | |
674 | { | |
675 | edge e; | |
676 | edge_iterator ei; | |
677 | FOR_EACH_EDGE (e, ei, bb->succs) | |
678 | if (!dominated_by_p (CDI_POST_DOMINATORS, bb, e->dest) | |
679 | && !dominated_by_p (CDI_DOMINATORS, e->dest, bb)) | |
680 | return true; | |
681 | } | |
682 | ||
d7eff5b2 AK |
683 | /* Collect all loops in the current region. */ |
684 | loop_p loop = bb->loop_father; | |
685 | if (loop_in_sese_p (loop, scop)) | |
686 | bitmap_set_bit (loops, loop->num); | |
ca617fd2 RB |
687 | |
688 | /* Check for harmful statements in basic blocks part of the region. */ | |
689 | for (gimple_stmt_iterator gsi = gsi_start_bb (bb); | |
690 | !gsi_end_p (gsi); gsi_next (&gsi)) | |
691 | if (!stmt_simple_for_scop_p (scop, gsi_stmt (gsi), bb)) | |
692 | return true; | |
d7eff5b2 | 693 | |
950d1cd9 RB |
694 | for (basic_block dom = first_dom_son (CDI_DOMINATORS, bb); |
695 | dom; | |
696 | dom = next_dom_son (CDI_DOMINATORS, dom)) | |
697 | if (dom != scop.exit->dest) | |
9c0c77d2 | 698 | worklist.safe_push (dom); |
d7eff5b2 AK |
699 | } |
700 | ||
701 | /* Go through all loops and check that they are still valid in the combined | |
702 | scop. */ | |
703 | unsigned j; | |
704 | bitmap_iterator bi; | |
705 | EXECUTE_IF_SET_IN_BITMAP (loops, 0, j, bi) | |
706 | { | |
707 | loop_p loop = (*current_loops->larray)[j]; | |
708 | gcc_assert (loop->num == (int) j); | |
709 | ||
ca617fd2 RB |
710 | /* Check if the loop nests are to be optimized for speed. */ |
711 | if (! loop->inner | |
712 | && ! optimize_loop_for_speed_p (loop)) | |
713 | { | |
714 | DEBUG_PRINT (dp << "[scop-detection-fail] loop_" | |
715 | << loop->num << " is not on a hot path.\n"); | |
716 | return true; | |
717 | } | |
718 | ||
719 | if (! can_represent_loop (loop, scop)) | |
720 | { | |
721 | DEBUG_PRINT (dp << "[scop-detection-fail] cannot represent loop_" | |
722 | << loop->num << "\n"); | |
723 | return true; | |
724 | } | |
725 | ||
ca617fd2 RB |
726 | /* Check if all loop nests have at least one data reference. |
727 | ??? This check is expensive and loops premature at this point. | |
728 | If important to retain we can pre-compute this for all innermost | |
729 | loops and reject those when we build a SESE region for a loop | |
730 | during SESE discovery. */ | |
731 | if (! loop->inner | |
732 | && ! loop_nest_has_data_refs (loop)) | |
733 | { | |
734 | DEBUG_PRINT (dp << "[scop-detection-fail] loop_" << loop->num | |
735 | << "does not have any data reference.\n"); | |
736 | return true; | |
737 | } | |
076d564d AK |
738 | } |
739 | ||
ec17e433 | 740 | return false; |
076d564d AK |
741 | } |
742 | ||
743 | /* Returns true if S1 subsumes/surrounds S2. */ | |
744 | bool | |
745 | scop_detection::subsumes (sese_l s1, sese_l s2) | |
2abae5f1 | 746 | { |
bafcb153 AK |
747 | if (dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2), |
748 | get_entry_bb (s1)) | |
749 | && dominated_by_p (CDI_POST_DOMINATORS, s2.exit->dest, | |
750 | s1.exit->dest)) | |
076d564d AK |
751 | return true; |
752 | return false; | |
753 | } | |
2abae5f1 | 754 | |
076d564d AK |
755 | /* Remove a SCoP which is subsumed by S1. */ |
756 | void | |
757 | scop_detection::remove_subscops (sese_l s1) | |
758 | { | |
759 | int j; | |
d37fc3aa | 760 | sese_l *s2; |
076d564d AK |
761 | FOR_EACH_VEC_ELT_REVERSE (scops, j, s2) |
762 | { | |
d37fc3aa | 763 | if (subsumes (s1, *s2)) |
076d564d | 764 | { |
49385686 | 765 | DEBUG_PRINT (dp << "Removing sub-SCoP"; |
d37fc3aa | 766 | print_sese (dump_file, *s2)); |
076d564d AK |
767 | scops.unordered_remove (j); |
768 | } | |
769 | } | |
770 | } | |
2abae5f1 | 771 | |
076d564d AK |
772 | /* Returns true if S1 intersects with S2. Since we already know that S1 does |
773 | not subsume S2 or vice-versa, we only check for entry bbs. */ | |
774 | ||
775 | bool | |
776 | scop_detection::intersects (sese_l s1, sese_l s2) | |
777 | { | |
bafcb153 AK |
778 | if (dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2), |
779 | get_entry_bb (s1)) | |
780 | && !dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2), | |
781 | get_exit_bb (s1))) | |
076d564d AK |
782 | return true; |
783 | if ((s1.exit == s2.entry) || (s2.exit == s1.entry)) | |
784 | return true; | |
785 | ||
786 | return false; | |
2abae5f1 SP |
787 | } |
788 | ||
076d564d | 789 | /* Remove one of the scops when it intersects with any other. */ |
7009b073 | 790 | |
076d564d AK |
791 | void |
792 | scop_detection::remove_intersecting_scops (sese_l s1) | |
793 | { | |
794 | int j; | |
d37fc3aa | 795 | sese_l *s2; |
076d564d AK |
796 | FOR_EACH_VEC_ELT_REVERSE (scops, j, s2) |
797 | { | |
d37fc3aa | 798 | if (intersects (s1, *s2)) |
076d564d | 799 | { |
49385686 AK |
800 | DEBUG_PRINT (dp << "Removing intersecting SCoP"; |
801 | print_sese (dump_file, *s2); | |
802 | dp << "Intersects with:"; | |
076d564d AK |
803 | print_sese (dump_file, s1)); |
804 | scops.unordered_remove (j); | |
805 | } | |
806 | } | |
807 | } | |
7009b073 | 808 | |
2abae5f1 SP |
809 | /* Something like "n * m" is not allowed. */ |
810 | ||
076d564d AK |
811 | bool |
812 | scop_detection::graphite_can_represent_init (tree e) | |
2abae5f1 SP |
813 | { |
814 | switch (TREE_CODE (e)) | |
815 | { | |
816 | case POLYNOMIAL_CHREC: | |
817 | return graphite_can_represent_init (CHREC_LEFT (e)) | |
818 | && graphite_can_represent_init (CHREC_RIGHT (e)); | |
819 | ||
820 | case MULT_EXPR: | |
821 | if (chrec_contains_symbols (TREE_OPERAND (e, 0))) | |
d505015a | 822 | return graphite_can_represent_init (TREE_OPERAND (e, 0)) |
9541ffee | 823 | && tree_fits_shwi_p (TREE_OPERAND (e, 1)); |
2abae5f1 | 824 | else |
d505015a | 825 | return graphite_can_represent_init (TREE_OPERAND (e, 1)) |
9541ffee | 826 | && tree_fits_shwi_p (TREE_OPERAND (e, 0)); |
2abae5f1 SP |
827 | |
828 | case PLUS_EXPR: | |
829 | case POINTER_PLUS_EXPR: | |
830 | case MINUS_EXPR: | |
831 | return graphite_can_represent_init (TREE_OPERAND (e, 0)) | |
832 | && graphite_can_represent_init (TREE_OPERAND (e, 1)); | |
833 | ||
834 | case NEGATE_EXPR: | |
835 | case BIT_NOT_EXPR: | |
836 | CASE_CONVERT: | |
837 | case NON_LVALUE_EXPR: | |
838 | return graphite_can_represent_init (TREE_OPERAND (e, 0)); | |
839 | ||
076d564d AK |
840 | default: |
841 | break; | |
2abae5f1 SP |
842 | } |
843 | ||
844 | return true; | |
845 | } | |
846 | ||
847 | /* Return true when SCEV can be represented in the polyhedral model. | |
848 | ||
849 | An expression can be represented, if it can be expressed as an | |
850 | affine expression. For loops (i, j) and parameters (m, n) all | |
851 | affine expressions are of the form: | |
852 | ||
853 | x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z | |
854 | ||
855 | 1 i + 20 j + (-2) m + 25 | |
856 | ||
56f30f65 | 857 | Something like "i * n" or "n * m" is not allowed. */ |
2abae5f1 | 858 | |
076d564d | 859 | bool |
a68f286c | 860 | scop_detection::graphite_can_represent_scev (sese_l scop, tree scev) |
2abae5f1 SP |
861 | { |
862 | if (chrec_contains_undetermined (scev)) | |
863 | return false; | |
864 | ||
4b216ab0 SP |
865 | switch (TREE_CODE (scev)) |
866 | { | |
033aa406 RB |
867 | case NEGATE_EXPR: |
868 | case BIT_NOT_EXPR: | |
869 | CASE_CONVERT: | |
870 | case NON_LVALUE_EXPR: | |
a68f286c | 871 | return graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0)); |
033aa406 | 872 | |
4b216ab0 | 873 | case PLUS_EXPR: |
033aa406 | 874 | case POINTER_PLUS_EXPR: |
4b216ab0 | 875 | case MINUS_EXPR: |
a68f286c RB |
876 | return graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0)) |
877 | && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 1)); | |
2abae5f1 | 878 | |
4b216ab0 SP |
879 | case MULT_EXPR: |
880 | return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 0))) | |
881 | && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 1))) | |
882 | && !(chrec_contains_symbols (TREE_OPERAND (scev, 0)) | |
883 | && chrec_contains_symbols (TREE_OPERAND (scev, 1))) | |
c4c4983e | 884 | && graphite_can_represent_init (scev) |
a68f286c RB |
885 | && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0)) |
886 | && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 1)); | |
2abae5f1 | 887 | |
4b216ab0 SP |
888 | case POLYNOMIAL_CHREC: |
889 | /* Check for constant strides. With a non constant stride of | |
890 | 'n' we would have a value of 'iv * n'. Also check that the | |
891 | initial value can represented: for example 'n * m' cannot be | |
892 | represented. */ | |
a68f286c RB |
893 | gcc_assert (loop_in_sese_p (get_loop (cfun, |
894 | CHREC_VARIABLE (scev)), scop)); | |
4b216ab0 SP |
895 | if (!evolution_function_right_is_integer_cst (scev) |
896 | || !graphite_can_represent_init (scev)) | |
897 | return false; | |
a68f286c | 898 | return graphite_can_represent_scev (scop, CHREC_LEFT (scev)); |
4b216ab0 | 899 | |
4c82aa3b RB |
900 | case ADDR_EXPR: |
901 | /* We cannot encode addresses for ISL. */ | |
902 | return false; | |
903 | ||
4b216ab0 SP |
904 | default: |
905 | break; | |
906 | } | |
2abae5f1 SP |
907 | |
908 | /* Only affine functions can be represented. */ | |
076d564d | 909 | if (tree_contains_chrecs (scev, NULL) || !scev_is_linear_expression (scev)) |
2abae5f1 SP |
910 | return false; |
911 | ||
d9ae7906 | 912 | return true; |
2abae5f1 SP |
913 | } |
914 | ||
2abae5f1 SP |
915 | /* Return true when EXPR can be represented in the polyhedral model. |
916 | ||
7009b073 SP |
917 | This means an expression can be represented, if it is linear with respect to |
918 | the loops and the strides are non parametric. LOOP is the place where the | |
919 | expr will be evaluated. SCOP defines the region we analyse. */ | |
2abae5f1 | 920 | |
076d564d AK |
921 | bool |
922 | scop_detection::graphite_can_represent_expr (sese_l scop, loop_p loop, | |
923 | tree expr) | |
2abae5f1 | 924 | { |
124f4f57 | 925 | tree scev = cached_scalar_evolution_in_region (scop, loop, expr); |
a68f286c | 926 | return graphite_can_represent_scev (scop, scev); |
2abae5f1 SP |
927 | } |
928 | ||
7009b073 SP |
929 | /* Return true if the data references of STMT can be represented by Graphite. |
930 | We try to analyze the data references in a loop contained in the SCOP. */ | |
2abae5f1 | 931 | |
076d564d AK |
932 | bool |
933 | scop_detection::stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt) | |
2abae5f1 | 934 | { |
5de73c05 | 935 | edge nest = scop.entry; |
95ad2417 | 936 | loop_p loop = loop_containing_stmt (stmt); |
72b03fde | 937 | if (!loop_in_sese_p (loop, scop)) |
92900aec | 938 | loop = NULL; |
390b24dc | 939 | |
72b03fde RB |
940 | auto_vec<data_reference_p> drs; |
941 | if (! graphite_find_data_references_in_stmt (nest, loop, stmt, &drs)) | |
942 | return false; | |
95ad2417 SP |
943 | |
944 | int j; | |
945 | data_reference_p dr; | |
946 | FOR_EACH_VEC_ELT (drs, j, dr) | |
390b24dc | 947 | { |
72b03fde | 948 | for (unsigned i = 0; i < DR_NUM_DIMENSIONS (dr); ++i) |
a68f286c | 949 | if (! graphite_can_represent_scev (scop, DR_ACCESS_FN (dr, i))) |
6652875f | 950 | return false; |
390b24dc | 951 | } |
2abae5f1 | 952 | |
72b03fde | 953 | return true; |
2abae5f1 SP |
954 | } |
955 | ||
9d85345a AK |
956 | /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects. |
957 | Calls have side-effects, except those to const or pure | |
958 | functions. */ | |
2abae5f1 SP |
959 | |
960 | static bool | |
9d85345a | 961 | stmt_has_side_effects (gimple *stmt) |
2abae5f1 | 962 | { |
2abae5f1 SP |
963 | if (gimple_has_volatile_ops (stmt) |
964 | || (gimple_code (stmt) == GIMPLE_CALL | |
965 | && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE))) | |
966 | || (gimple_code (stmt) == GIMPLE_ASM)) | |
33df361a | 967 | { |
7009b073 | 968 | DEBUG_PRINT (dp << "[scop-detection-fail] " |
9d85345a | 969 | << "Statement has side-effects:\n"; |
076d564d | 970 | print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS | TDF_MEMSYMS)); |
9d85345a | 971 | return true; |
33df361a | 972 | } |
9d85345a AK |
973 | return false; |
974 | } | |
2abae5f1 | 975 | |
ca617fd2 RB |
976 | /* Return true only when STMT is simple enough for being handled by Graphite. |
977 | This depends on SCOP, as the parameters are initialized relatively to | |
978 | this basic block, the linear functions are initialized based on the outermost | |
979 | loop containing STMT inside the SCOP. BB is the place where we try to | |
980 | evaluate the STMT. */ | |
2abae5f1 | 981 | |
076d564d | 982 | bool |
ca617fd2 RB |
983 | scop_detection::stmt_simple_for_scop_p (sese_l scop, gimple *stmt, |
984 | basic_block bb) const | |
9d85345a | 985 | { |
ca617fd2 RB |
986 | gcc_assert (scop); |
987 | ||
988 | if (is_gimple_debug (stmt)) | |
989 | return true; | |
990 | ||
991 | if (stmt_has_side_effects (stmt)) | |
992 | return false; | |
993 | ||
994 | if (!stmt_has_simple_data_refs_p (scop, stmt)) | |
995 | { | |
996 | DEBUG_PRINT (dp << "[scop-detection-fail] " | |
997 | << "Graphite cannot handle data-refs in stmt:\n"; | |
998 | print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS|TDF_MEMSYMS);); | |
999 | return false; | |
1000 | } | |
1001 | ||
2abae5f1 SP |
1002 | switch (gimple_code (stmt)) |
1003 | { | |
2abae5f1 SP |
1004 | case GIMPLE_LABEL: |
1005 | return true; | |
1006 | ||
1007 | case GIMPLE_COND: | |
1008 | { | |
2abae5f1 SP |
1009 | /* We can handle all binary comparisons. Inequalities are |
1010 | also supported as they can be represented with union of | |
1011 | polyhedra. */ | |
9d85345a AK |
1012 | enum tree_code code = gimple_cond_code (stmt); |
1013 | if (!(code == LT_EXPR | |
2abae5f1 SP |
1014 | || code == GT_EXPR |
1015 | || code == LE_EXPR | |
1016 | || code == GE_EXPR | |
1017 | || code == EQ_EXPR | |
1018 | || code == NE_EXPR)) | |
9d85345a AK |
1019 | { |
1020 | DEBUG_PRINT (dp << "[scop-detection-fail] " | |
7009b073 | 1021 | << "Graphite cannot handle cond stmt:\n"; |
076d564d AK |
1022 | print_gimple_stmt (dump_file, stmt, 0, |
1023 | TDF_VOPS | TDF_MEMSYMS)); | |
33df361a SP |
1024 | return false; |
1025 | } | |
2abae5f1 | 1026 | |
ca617fd2 | 1027 | loop_p loop = bb->loop_father; |
f16c88d2 RB |
1028 | for (unsigned i = 0; i < 2; ++i) |
1029 | { | |
1030 | tree op = gimple_op (stmt, i); | |
7009b073 | 1031 | if (!graphite_can_represent_expr (scop, loop, op) |
9ead801e | 1032 | /* We can only constrain on integer type. */ |
04612f7f | 1033 | || ! INTEGRAL_TYPE_P (TREE_TYPE (op))) |
33df361a | 1034 | { |
076d564d AK |
1035 | DEBUG_PRINT (dp << "[scop-detection-fail] " |
1036 | << "Graphite cannot represent stmt:\n"; | |
1037 | print_gimple_stmt (dump_file, stmt, 0, | |
1038 | TDF_VOPS | TDF_MEMSYMS)); | |
33df361a SP |
1039 | return false; |
1040 | } | |
f16c88d2 | 1041 | } |
2abae5f1 SP |
1042 | |
1043 | return true; | |
1044 | } | |
1045 | ||
1046 | case GIMPLE_ASSIGN: | |
2abae5f1 | 1047 | case GIMPLE_CALL: |
4cf55739 | 1048 | { |
c16d3e3c | 1049 | tree op, lhs = gimple_get_lhs (stmt); |
4cf55739 | 1050 | ssa_op_iter i; |
c16d3e3c RB |
1051 | /* If we are not going to instantiate the stmt do not require |
1052 | its operands to be instantiatable at this point. */ | |
1053 | if (lhs | |
1054 | && TREE_CODE (lhs) == SSA_NAME | |
1055 | && scev_analyzable_p (lhs, scop)) | |
1056 | return true; | |
4cf55739 RB |
1057 | /* Verify that if we can analyze operands at their def site we |
1058 | also can represent them when analyzed at their uses. */ | |
1059 | FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE) | |
1060 | if (scev_analyzable_p (op, scop) | |
c16d3e3c | 1061 | && chrec_contains_undetermined |
124f4f57 RB |
1062 | (cached_scalar_evolution_in_region (scop, |
1063 | bb->loop_father, op))) | |
4cf55739 RB |
1064 | { |
1065 | DEBUG_PRINT (dp << "[scop-detection-fail] " | |
c16d3e3c | 1066 | << "Graphite cannot code-gen stmt:\n"; |
4cf55739 RB |
1067 | print_gimple_stmt (dump_file, stmt, 0, |
1068 | TDF_VOPS | TDF_MEMSYMS)); | |
1069 | return false; | |
1070 | } | |
1071 | return true; | |
1072 | } | |
2abae5f1 SP |
1073 | |
1074 | default: | |
1075 | /* These nodes cut a new scope. */ | |
076d564d AK |
1076 | DEBUG_PRINT ( |
1077 | dp << "[scop-detection-fail] " | |
1078 | << "Gimple stmt not handled in Graphite:\n"; | |
1079 | print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS | TDF_MEMSYMS)); | |
2abae5f1 SP |
1080 | return false; |
1081 | } | |
9d85345a | 1082 | } |
2abae5f1 | 1083 | |
076d564d | 1084 | /* Returns the number of pbbs that are in loops contained in SCOP. */ |
7009b073 | 1085 | |
076d564d AK |
1086 | int |
1087 | scop_detection::nb_pbbs_in_loops (scop_p scop) | |
1088 | { | |
1089 | int i; | |
1090 | poly_bb_p pbb; | |
1091 | int res = 0; | |
7009b073 | 1092 | |
b0b5710c | 1093 | FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) |
d37fc3aa | 1094 | if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb)), scop->scop_info->region)) |
076d564d | 1095 | res++; |
7009b073 | 1096 | |
076d564d AK |
1097 | return res; |
1098 | } | |
7009b073 | 1099 | |
04612f7f | 1100 | /* Assigns the parameter NAME an index in REGION. */ |
87ccab5d | 1101 | |
04612f7f RB |
1102 | static void |
1103 | assign_parameter_index_in_region (tree name, sese_info_p region) | |
87ccab5d | 1104 | { |
04612f7f RB |
1105 | gcc_assert (TREE_CODE (name) == SSA_NAME |
1106 | && INTEGRAL_TYPE_P (TREE_TYPE (name)) | |
1107 | && ! defined_in_sese_p (name, region->region)); | |
87ccab5d AK |
1108 | int i; |
1109 | tree p; | |
65b016eb | 1110 | FOR_EACH_VEC_ELT (region->params, i, p) |
87ccab5d | 1111 | if (p == name) |
04612f7f | 1112 | return; |
87ccab5d | 1113 | |
65b016eb | 1114 | region->params.safe_push (name); |
87ccab5d AK |
1115 | } |
1116 | ||
1117 | /* In the context of sese S, scan the expression E and translate it to | |
1118 | a linear expression C. When parsing a symbolic multiplication, K | |
1119 | represents the constant multiplier of an expression containing | |
1120 | parameters. */ | |
1121 | ||
1122 | static void | |
bafcb153 | 1123 | scan_tree_for_params (sese_info_p s, tree e) |
87ccab5d AK |
1124 | { |
1125 | if (e == chrec_dont_know) | |
1126 | return; | |
1127 | ||
1128 | switch (TREE_CODE (e)) | |
1129 | { | |
1130 | case POLYNOMIAL_CHREC: | |
1131 | scan_tree_for_params (s, CHREC_LEFT (e)); | |
1132 | break; | |
1133 | ||
1134 | case MULT_EXPR: | |
1135 | if (chrec_contains_symbols (TREE_OPERAND (e, 0))) | |
1136 | scan_tree_for_params (s, TREE_OPERAND (e, 0)); | |
1137 | else | |
1138 | scan_tree_for_params (s, TREE_OPERAND (e, 1)); | |
1139 | break; | |
1140 | ||
1141 | case PLUS_EXPR: | |
1142 | case POINTER_PLUS_EXPR: | |
1143 | case MINUS_EXPR: | |
1144 | scan_tree_for_params (s, TREE_OPERAND (e, 0)); | |
1145 | scan_tree_for_params (s, TREE_OPERAND (e, 1)); | |
1146 | break; | |
1147 | ||
1148 | case NEGATE_EXPR: | |
1149 | case BIT_NOT_EXPR: | |
1150 | CASE_CONVERT: | |
1151 | case NON_LVALUE_EXPR: | |
1152 | scan_tree_for_params (s, TREE_OPERAND (e, 0)); | |
1153 | break; | |
1154 | ||
1155 | case SSA_NAME: | |
04612f7f | 1156 | assign_parameter_index_in_region (e, s); |
87ccab5d AK |
1157 | break; |
1158 | ||
1159 | case INTEGER_CST: | |
1160 | case ADDR_EXPR: | |
1161 | case REAL_CST: | |
1162 | case COMPLEX_CST: | |
1163 | case VECTOR_CST: | |
1164 | break; | |
1165 | ||
1166 | default: | |
1167 | gcc_unreachable (); | |
1168 | break; | |
1169 | } | |
1170 | } | |
1171 | ||
1172 | /* Find parameters with respect to REGION in BB. We are looking in memory | |
1173 | access functions, conditions and loop bounds. */ | |
1174 | ||
1175 | static void | |
bafcb153 | 1176 | find_params_in_bb (sese_info_p region, gimple_poly_bb_p gbb) |
87ccab5d | 1177 | { |
8e4dc590 | 1178 | /* Find parameters in the access functions of data references. */ |
87ccab5d | 1179 | int i; |
87ccab5d | 1180 | data_reference_p dr; |
87ccab5d | 1181 | FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb), i, dr) |
8e4dc590 | 1182 | for (unsigned j = 0; j < DR_NUM_DIMENSIONS (dr); j++) |
87ccab5d AK |
1183 | scan_tree_for_params (region, DR_ACCESS_FN (dr, j)); |
1184 | ||
1185 | /* Find parameters in conditional statements. */ | |
8e4dc590 | 1186 | gimple *stmt; |
87ccab5d AK |
1187 | FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb), i, stmt) |
1188 | { | |
b2bf8258 | 1189 | loop_p loop = gimple_bb (stmt)->loop_father; |
124f4f57 RB |
1190 | tree lhs = cached_scalar_evolution_in_region (region->region, loop, |
1191 | gimple_cond_lhs (stmt)); | |
1192 | tree rhs = cached_scalar_evolution_in_region (region->region, loop, | |
1193 | gimple_cond_rhs (stmt)); | |
b2bf8258 RB |
1194 | gcc_assert (!chrec_contains_undetermined (lhs) |
1195 | && !chrec_contains_undetermined (rhs)); | |
87ccab5d AK |
1196 | |
1197 | scan_tree_for_params (region, lhs); | |
1198 | scan_tree_for_params (region, rhs); | |
1199 | } | |
1200 | } | |
1201 | ||
6f0e6f08 | 1202 | /* Record the parameters used in the SCOP BBs. A variable is a parameter |
87ccab5d AK |
1203 | in a scop if it does not vary during the execution of that scop. */ |
1204 | ||
1205 | static void | |
1206 | find_scop_parameters (scop_p scop) | |
1207 | { | |
87ccab5d | 1208 | unsigned i; |
d37fc3aa | 1209 | sese_info_p region = scop->scop_info; |
87ccab5d | 1210 | |
6f0e6f08 | 1211 | /* Parameters used in loop bounds are processed during gather_bbs. */ |
87ccab5d AK |
1212 | |
1213 | /* Find the parameters used in data accesses. */ | |
8e4dc590 | 1214 | poly_bb_p pbb; |
b0b5710c | 1215 | FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) |
87ccab5d AK |
1216 | find_params_in_bb (region, PBB_BLACK_BOX (pbb)); |
1217 | ||
8e4dc590 | 1218 | int nbp = sese_nb_params (region); |
87ccab5d | 1219 | scop_set_nb_params (scop, nbp); |
87ccab5d AK |
1220 | } |
1221 | ||
bd8d431f RB |
1222 | static void |
1223 | add_write (vec<tree> *writes, tree def) | |
1224 | { | |
1225 | writes->safe_push (def); | |
1226 | DEBUG_PRINT (dp << "Adding scalar write: "; | |
1227 | print_generic_expr (dump_file, def); | |
1228 | dp << "\nFrom stmt: "; | |
1229 | print_gimple_stmt (dump_file, | |
1230 | SSA_NAME_DEF_STMT (def), 0)); | |
1231 | } | |
1232 | ||
1233 | static void | |
1234 | add_read (vec<scalar_use> *reads, tree use, gimple *use_stmt) | |
1235 | { | |
1236 | DEBUG_PRINT (dp << "Adding scalar read: "; | |
1237 | print_generic_expr (dump_file, use); | |
1238 | dp << "\nFrom stmt: "; | |
1239 | print_gimple_stmt (dump_file, use_stmt, 0)); | |
1240 | reads->safe_push (std::make_pair (use_stmt, use)); | |
1241 | } | |
1242 | ||
1243 | ||
65b016eb AK |
1244 | /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP. */ |
1245 | ||
1246 | static void | |
1247 | build_cross_bb_scalars_def (scop_p scop, tree def, basic_block def_bb, | |
1248 | vec<tree> *writes) | |
1249 | { | |
bd8d431f | 1250 | if (!is_gimple_reg (def)) |
65b016eb AK |
1251 | return; |
1252 | ||
73fe2f32 | 1253 | bool scev_analyzable = scev_analyzable_p (def, scop->scop_info->region); |
65b016eb AK |
1254 | |
1255 | gimple *use_stmt; | |
1256 | imm_use_iterator imm_iter; | |
1257 | FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def) | |
73fe2f32 RB |
1258 | /* Do not gather scalar variables that can be analyzed by SCEV as they can |
1259 | be generated out of the induction variables. */ | |
1260 | if ((! scev_analyzable | |
1261 | /* But gather SESE liveouts as we otherwise fail to rewrite their | |
1262 | exit PHIs. */ | |
1263 | || ! bb_in_sese_p (gimple_bb (use_stmt), scop->scop_info->region)) | |
bd8d431f | 1264 | && (def_bb != gimple_bb (use_stmt) && !is_gimple_debug (use_stmt))) |
65b016eb | 1265 | { |
bd8d431f | 1266 | add_write (writes, def); |
65b016eb AK |
1267 | /* This is required by the FOR_EACH_IMM_USE_STMT when we want to break |
1268 | before all the uses have been visited. */ | |
1269 | BREAK_FROM_IMM_USE_STMT (imm_iter); | |
1270 | } | |
1271 | } | |
1272 | ||
3d07d963 RB |
1273 | /* Record USE if it is defined in other bbs different than USE_STMT |
1274 | in the SCOP. */ | |
65b016eb AK |
1275 | |
1276 | static void | |
1277 | build_cross_bb_scalars_use (scop_p scop, tree use, gimple *use_stmt, | |
1278 | vec<scalar_use> *reads) | |
1279 | { | |
65b016eb AK |
1280 | if (!is_gimple_reg (use)) |
1281 | return; | |
1282 | ||
1283 | /* Do not gather scalar variables that can be analyzed by SCEV as they can be | |
1284 | generated out of the induction variables. */ | |
1285 | if (scev_analyzable_p (use, scop->scop_info->region)) | |
1286 | return; | |
1287 | ||
1288 | gimple *def_stmt = SSA_NAME_DEF_STMT (use); | |
bd8d431f RB |
1289 | if (gimple_bb (def_stmt) != gimple_bb (use_stmt)) |
1290 | add_read (reads, use, use_stmt); | |
65b016eb AK |
1291 | } |
1292 | ||
b0b5710c AK |
1293 | /* Generates a polyhedral black box only if the bb contains interesting |
1294 | information. */ | |
1295 | ||
1296 | static gimple_poly_bb_p | |
1297 | try_generate_gimple_bb (scop_p scop, basic_block bb) | |
1298 | { | |
ec17e433 ML |
1299 | vec<data_reference_p> drs = vNULL; |
1300 | vec<tree> writes = vNULL; | |
1301 | vec<scalar_use> reads = vNULL; | |
65b016eb | 1302 | |
d37fc3aa | 1303 | sese_l region = scop->scop_info->region; |
92900aec | 1304 | edge nest = region.entry; |
b0b5710c AK |
1305 | loop_p loop = bb->loop_father; |
1306 | if (!loop_in_sese_p (loop, region)) | |
92900aec | 1307 | loop = NULL; |
b0b5710c | 1308 | |
65b016eb AK |
1309 | for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); |
1310 | gsi_next (&gsi)) | |
b0b5710c AK |
1311 | { |
1312 | gimple *stmt = gsi_stmt (gsi); | |
1313 | if (is_gimple_debug (stmt)) | |
1314 | continue; | |
1315 | ||
1316 | graphite_find_data_references_in_stmt (nest, loop, stmt, &drs); | |
bd8d431f RB |
1317 | |
1318 | tree def = gimple_get_lhs (stmt); | |
1319 | if (def) | |
1320 | build_cross_bb_scalars_def (scop, def, gimple_bb (stmt), &writes); | |
1321 | ||
1322 | ssa_op_iter iter; | |
1323 | tree use; | |
1324 | FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) | |
1325 | build_cross_bb_scalars_use (scop, use, stmt, &reads); | |
b0b5710c AK |
1326 | } |
1327 | ||
bd8d431f RB |
1328 | /* Handle defs and uses in PHIs. Those need special treatment given |
1329 | that we have to present ISL with sth that looks like we've rewritten | |
1330 | the IL out-of-SSA. */ | |
65b016eb AK |
1331 | for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi); |
1332 | gsi_next (&psi)) | |
bd8d431f RB |
1333 | { |
1334 | gphi *phi = psi.phi (); | |
1335 | tree res = gimple_phi_result (phi); | |
1336 | if (virtual_operand_p (res) | |
1337 | || scev_analyzable_p (res, scop->scop_info->region)) | |
1338 | continue; | |
1339 | /* To simulate out-of-SSA the block containing the PHI node has | |
1340 | reads of the PHI destination. And to preserve SSA dependences | |
1341 | we also write to it (the out-of-SSA decl and the SSA result | |
1342 | are coalesced for dependence purposes which is good enough). */ | |
1343 | add_read (&reads, res, phi); | |
1344 | add_write (&writes, res); | |
1345 | } | |
1346 | basic_block bb_for_succs = bb; | |
1347 | if (bb_for_succs == bb_for_succs->loop_father->latch | |
1348 | && bb_in_sese_p (bb_for_succs, scop->scop_info->region) | |
1349 | && sese_trivially_empty_bb_p (bb_for_succs)) | |
1350 | bb_for_succs = NULL; | |
1351 | while (bb_for_succs) | |
1352 | { | |
1353 | basic_block latch = NULL; | |
1354 | edge_iterator ei; | |
1355 | edge e; | |
1356 | FOR_EACH_EDGE (e, ei, bb_for_succs->succs) | |
1357 | { | |
1358 | for (gphi_iterator psi = gsi_start_phis (e->dest); !gsi_end_p (psi); | |
1359 | gsi_next (&psi)) | |
1360 | { | |
1361 | gphi *phi = psi.phi (); | |
1362 | tree res = gimple_phi_result (phi); | |
1363 | if (virtual_operand_p (res)) | |
1364 | continue; | |
1365 | /* To simulate out-of-SSA the predecessor of edges into PHI nodes | |
1366 | has a copy from the PHI argument to the PHI destination. */ | |
1367 | if (! scev_analyzable_p (res, scop->scop_info->region)) | |
1368 | add_write (&writes, res); | |
1369 | tree use = PHI_ARG_DEF_FROM_EDGE (phi, e); | |
1370 | if (TREE_CODE (use) == SSA_NAME | |
1371 | && ! SSA_NAME_IS_DEFAULT_DEF (use) | |
1372 | && gimple_bb (SSA_NAME_DEF_STMT (use)) != bb_for_succs | |
1373 | && ! scev_analyzable_p (use, scop->scop_info->region)) | |
1374 | add_read (&reads, use, phi); | |
1375 | } | |
1376 | if (e->dest == bb_for_succs->loop_father->latch | |
1377 | && bb_in_sese_p (e->dest, scop->scop_info->region) | |
1378 | && sese_trivially_empty_bb_p (e->dest)) | |
1379 | latch = e->dest; | |
1380 | } | |
1381 | /* Handle empty latch block PHIs here, otherwise we confuse ISL | |
1382 | with extra conditional code where it then peels off the last | |
1383 | iteration just because of that. It would be simplest if we | |
1384 | just didn't force simple latches (thus remove the forwarder). */ | |
1385 | bb_for_succs = latch; | |
1386 | } | |
1387 | ||
1388 | /* For the region exit block add reads for all live-out vars. */ | |
1389 | if (bb == scop->scop_info->region.exit->src) | |
1390 | { | |
1391 | sese_build_liveouts (scop->scop_info); | |
1392 | unsigned i; | |
1393 | bitmap_iterator bi; | |
1394 | EXECUTE_IF_SET_IN_BITMAP (scop->scop_info->liveout, 0, i, bi) | |
1395 | { | |
1396 | tree use = ssa_name (i); | |
1397 | add_read (&reads, use, NULL); | |
1398 | } | |
1399 | } | |
65b016eb AK |
1400 | |
1401 | if (drs.is_empty () && writes.is_empty () && reads.is_empty ()) | |
1402 | return NULL; | |
1403 | ||
1404 | return new_gimple_poly_bb (bb, drs, reads, writes); | |
1405 | } | |
1406 | ||
1407 | /* Compute alias-sets for all data references in DRS. */ | |
1408 | ||
b6ab6ef8 | 1409 | static bool |
65b016eb AK |
1410 | build_alias_set (scop_p scop) |
1411 | { | |
1412 | int num_vertices = scop->drs.length (); | |
1413 | struct graph *g = new_graph (num_vertices); | |
1414 | dr_info *dr1, *dr2; | |
1415 | int i, j; | |
1416 | int *all_vertices; | |
1417 | ||
1d0b81c6 RB |
1418 | struct loop *nest |
1419 | = find_common_loop (scop->scop_info->region.entry->dest->loop_father, | |
1420 | scop->scop_info->region.exit->src->loop_father); | |
1421 | ||
65b016eb AK |
1422 | FOR_EACH_VEC_ELT (scop->drs, i, dr1) |
1423 | for (j = i+1; scop->drs.iterate (j, &dr2); j++) | |
1d0b81c6 | 1424 | if (dr_may_alias_p (dr1->dr, dr2->dr, nest)) |
65b016eb | 1425 | { |
b6ab6ef8 RB |
1426 | /* Dependences in the same alias set need to be handled |
1427 | by just looking at DR_ACCESS_FNs. */ | |
72b03fde RB |
1428 | if (DR_NUM_DIMENSIONS (dr1->dr) == 0 |
1429 | || DR_NUM_DIMENSIONS (dr1->dr) != DR_NUM_DIMENSIONS (dr2->dr) | |
b6ab6ef8 RB |
1430 | || ! operand_equal_p (DR_BASE_OBJECT (dr1->dr), |
1431 | DR_BASE_OBJECT (dr2->dr), | |
1432 | OEP_ADDRESS_OF) | |
1433 | || ! types_compatible_p (TREE_TYPE (DR_BASE_OBJECT (dr1->dr)), | |
1434 | TREE_TYPE (DR_BASE_OBJECT (dr2->dr)))) | |
1435 | { | |
1436 | free_graph (g); | |
1437 | return false; | |
1438 | } | |
65b016eb AK |
1439 | add_edge (g, i, j); |
1440 | add_edge (g, j, i); | |
1441 | } | |
1442 | ||
1443 | all_vertices = XNEWVEC (int, num_vertices); | |
1444 | for (i = 0; i < num_vertices; i++) | |
1445 | all_vertices[i] = i; | |
1446 | ||
99124c31 RB |
1447 | scop->max_alias_set |
1448 | = graphds_dfs (g, all_vertices, num_vertices, NULL, true, NULL) + 1; | |
65b016eb AK |
1449 | free (all_vertices); |
1450 | ||
1451 | for (i = 0; i < g->n_vertices; i++) | |
1452 | scop->drs[i].alias_set = g->vertices[i].component + 1; | |
1453 | ||
1454 | free_graph (g); | |
b6ab6ef8 | 1455 | return true; |
b0b5710c AK |
1456 | } |
1457 | ||
1458 | /* Gather BBs and conditions for a SCOP. */ | |
1459 | class gather_bbs : public dom_walker | |
076d564d AK |
1460 | { |
1461 | public: | |
d2552094 | 1462 | gather_bbs (cdi_direction, scop_p, int *); |
7009b073 | 1463 | |
3dec93d5 | 1464 | virtual edge before_dom_children (basic_block); |
076d564d | 1465 | virtual void after_dom_children (basic_block); |
7009b073 | 1466 | |
076d564d | 1467 | private: |
b0b5710c AK |
1468 | auto_vec<gimple *, 3> conditions, cases; |
1469 | scop_p scop; | |
076d564d AK |
1470 | }; |
1471 | } | |
d2552094 | 1472 | gather_bbs::gather_bbs (cdi_direction direction, scop_p scop, int *bb_to_rpo) |
9972bbbc | 1473 | : dom_walker (direction, ALL_BLOCKS, bb_to_rpo), scop (scop) |
076d564d AK |
1474 | { |
1475 | } | |
7009b073 | 1476 | |
076d564d AK |
1477 | /* Call-back for dom_walk executed before visiting the dominated |
1478 | blocks. */ | |
7009b073 | 1479 | |
3dec93d5 | 1480 | edge |
b0b5710c | 1481 | gather_bbs::before_dom_children (basic_block bb) |
076d564d | 1482 | { |
5431c9ea AK |
1483 | sese_info_p region = scop->scop_info; |
1484 | if (!bb_in_sese_p (bb, region->region)) | |
d2552094 | 1485 | return dom_walker::STOP; |
7009b073 | 1486 | |
6f0e6f08 RB |
1487 | /* For loops fully contained in the region record parameters in the |
1488 | loop bounds. */ | |
1489 | loop_p loop = bb->loop_father; | |
1490 | if (loop->header == bb | |
1491 | && loop_in_sese_p (loop, region->region)) | |
1492 | { | |
1493 | tree nb_iters = number_of_latch_executions (loop); | |
1494 | if (chrec_contains_symbols (nb_iters)) | |
1495 | { | |
124f4f57 RB |
1496 | nb_iters = cached_scalar_evolution_in_region (region->region, |
1497 | loop, nb_iters); | |
6f0e6f08 RB |
1498 | scan_tree_for_params (region, nb_iters); |
1499 | } | |
1500 | } | |
5431c9ea | 1501 | |
e4c73066 | 1502 | if (gcond *stmt = single_pred_cond_non_loop_exit (bb)) |
076d564d AK |
1503 | { |
1504 | edge e = single_pred_edge (bb); | |
e4c73066 RB |
1505 | /* Make sure the condition is in the region and thus was verified |
1506 | to be handled. */ | |
1507 | if (e != region->region.entry) | |
1508 | { | |
1509 | conditions.safe_push (stmt); | |
1510 | if (e->flags & EDGE_TRUE_VALUE) | |
1511 | cases.safe_push (stmt); | |
1512 | else | |
1513 | cases.safe_push (NULL); | |
1514 | } | |
076d564d | 1515 | } |
7009b073 | 1516 | |
d37fc3aa | 1517 | scop->scop_info->bbs.safe_push (bb); |
7009b073 | 1518 | |
b0b5710c | 1519 | gimple_poly_bb_p gbb = try_generate_gimple_bb (scop, bb); |
65b016eb | 1520 | if (!gbb) |
3dec93d5 | 1521 | return NULL; |
65b016eb | 1522 | |
b0b5710c AK |
1523 | GBB_CONDITIONS (gbb) = conditions.copy (); |
1524 | GBB_CONDITION_CASES (gbb) = cases.copy (); | |
1525 | ||
1526 | poly_bb_p pbb = new_poly_bb (scop, gbb); | |
1527 | scop->pbbs.safe_push (pbb); | |
65b016eb AK |
1528 | |
1529 | int i; | |
1530 | data_reference_p dr; | |
1531 | FOR_EACH_VEC_ELT (gbb->data_refs, i, dr) | |
040b0c97 AK |
1532 | { |
1533 | DEBUG_PRINT (dp << "Adding memory "; | |
1534 | if (dr->is_read) | |
1535 | dp << "read: "; | |
1536 | else | |
1537 | dp << "write: "; | |
ef6cb4c7 | 1538 | print_generic_expr (dump_file, dr->ref); |
040b0c97 | 1539 | dp << "\nFrom stmt: "; |
ef6cb4c7 | 1540 | print_gimple_stmt (dump_file, dr->stmt, 0)); |
040b0c97 AK |
1541 | |
1542 | scop->drs.safe_push (dr_info (dr, pbb)); | |
1543 | } | |
3dec93d5 UB |
1544 | |
1545 | return NULL; | |
076d564d | 1546 | } |
7009b073 | 1547 | |
076d564d AK |
1548 | /* Call-back for dom_walk executed after visiting the dominated |
1549 | blocks. */ | |
7009b073 | 1550 | |
076d564d | 1551 | void |
b0b5710c | 1552 | gather_bbs::after_dom_children (basic_block bb) |
076d564d | 1553 | { |
d37fc3aa | 1554 | if (!bb_in_sese_p (bb, scop->scop_info->region)) |
076d564d | 1555 | return; |
7009b073 | 1556 | |
076d564d AK |
1557 | if (single_pred_cond_non_loop_exit (bb)) |
1558 | { | |
e4c73066 RB |
1559 | edge e = single_pred_edge (bb); |
1560 | if (e != scop->scop_info->region.entry) | |
1561 | { | |
1562 | conditions.pop (); | |
1563 | cases.pop (); | |
1564 | } | |
076d564d AK |
1565 | } |
1566 | } | |
7009b073 | 1567 | |
6d1115c5 RB |
1568 | |
1569 | /* Compute sth like an execution order, dominator order with first executing | |
1570 | edges that stay inside the current loop, delaying processing exit edges. */ | |
1571 | ||
a365945b | 1572 | static int *bb_to_rpo; |
6d1115c5 RB |
1573 | |
1574 | /* Helper for qsort, sorting after order above. */ | |
1575 | ||
1576 | static int | |
1577 | cmp_pbbs (const void *pa, const void *pb) | |
1578 | { | |
1579 | poly_bb_p bb1 = *((const poly_bb_p *)pa); | |
1580 | poly_bb_p bb2 = *((const poly_bb_p *)pb); | |
a365945b RB |
1581 | if (bb_to_rpo[bb1->black_box->bb->index] |
1582 | < bb_to_rpo[bb2->black_box->bb->index]) | |
6d1115c5 | 1583 | return -1; |
a365945b RB |
1584 | else if (bb_to_rpo[bb1->black_box->bb->index] |
1585 | > bb_to_rpo[bb2->black_box->bb->index]) | |
6d1115c5 RB |
1586 | return 1; |
1587 | else | |
1588 | return 0; | |
1589 | } | |
1590 | ||
7009b073 SP |
1591 | /* Find Static Control Parts (SCoP) in the current function and pushes |
1592 | them to SCOPS. */ | |
1593 | ||
1594 | void | |
1595 | build_scops (vec<scop_p> *scops) | |
1596 | { | |
1597 | if (dump_file) | |
1598 | dp.set_dump_file (dump_file); | |
1599 | ||
076d564d | 1600 | scop_detection sb; |
ca617fd2 | 1601 | sb.build_scop_depth (current_loops->tree_root); |
0afd32be AK |
1602 | |
1603 | /* Now create scops from the lightweight SESEs. */ | |
1604 | vec<sese_l> scops_l = sb.get_scops (); | |
d2552094 RB |
1605 | |
1606 | /* Domwalk needs a bb to RPO mapping. Compute it once here. */ | |
1607 | int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun)); | |
1608 | int postorder_num = pre_and_rev_post_order_compute (NULL, postorder, true); | |
a365945b | 1609 | bb_to_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun)); |
d2552094 RB |
1610 | for (int i = 0; i < postorder_num; ++i) |
1611 | bb_to_rpo[postorder[i]] = i; | |
1612 | free (postorder); | |
1613 | ||
0afd32be | 1614 | int i; |
d37fc3aa | 1615 | sese_l *s; |
0afd32be | 1616 | FOR_EACH_VEC_ELT (scops_l, i, s) |
076d564d | 1617 | { |
d37fc3aa | 1618 | scop_p scop = new_scop (s->entry, s->exit); |
076d564d | 1619 | |
b0b5710c | 1620 | /* Record all basic blocks and their conditions in REGION. */ |
d2552094 | 1621 | gather_bbs (CDI_DOMINATORS, scop, bb_to_rpo).walk (s->entry->dest); |
6d1115c5 | 1622 | |
a365945b | 1623 | /* Sort pbbs after execution order for initial schedule generation. */ |
6d1115c5 | 1624 | scop->pbbs.qsort (cmp_pbbs); |
b0b5710c | 1625 | |
b6ab6ef8 RB |
1626 | if (! build_alias_set (scop)) |
1627 | { | |
1628 | DEBUG_PRINT (dp << "[scop-detection-fail] cannot handle dependences\n"); | |
1629 | free_scop (scop); | |
1630 | continue; | |
1631 | } | |
65b016eb | 1632 | |
076d564d AK |
1633 | /* Do not optimize a scop containing only PBBs that do not belong |
1634 | to any loops. */ | |
1635 | if (sb.nb_pbbs_in_loops (scop) == 0) | |
1636 | { | |
87ccab5d AK |
1637 | DEBUG_PRINT (dp << "[scop-detection-fail] no data references.\n"); |
1638 | free_scop (scop); | |
1639 | continue; | |
1640 | } | |
1641 | ||
028d4092 | 1642 | unsigned max_arrays = param_graphite_max_arrays_per_scop; |
99124c31 RB |
1643 | if (max_arrays > 0 |
1644 | && scop->drs.length () >= max_arrays) | |
8b76e7fe AK |
1645 | { |
1646 | DEBUG_PRINT (dp << "[scop-detection-fail] too many data references: " | |
1647 | << scop->drs.length () | |
1648 | << " is larger than --param graphite-max-arrays-per-scop=" | |
1649 | << max_arrays << ".\n"); | |
1650 | free_scop (scop); | |
1651 | continue; | |
1652 | } | |
1653 | ||
87ccab5d | 1654 | find_scop_parameters (scop); |
028d4092 | 1655 | graphite_dim_t max_dim = param_graphite_max_nb_scop_params; |
d2552094 RB |
1656 | if (max_dim > 0 |
1657 | && scop_nb_params (scop) > max_dim) | |
87ccab5d AK |
1658 | { |
1659 | DEBUG_PRINT (dp << "[scop-detection-fail] too many parameters: " | |
402cab17 AK |
1660 | << scop_nb_params (scop) |
1661 | << " larger than --param graphite-max-nb-scop-params=" | |
1662 | << max_dim << ".\n"); | |
076d564d AK |
1663 | free_scop (scop); |
1664 | continue; | |
1665 | } | |
1666 | ||
1667 | scops->safe_push (scop); | |
1668 | } | |
1669 | ||
d2552094 | 1670 | free (bb_to_rpo); |
a365945b | 1671 | bb_to_rpo = NULL; |
7009b073 SP |
1672 | DEBUG_PRINT (dp << "number of SCoPs: " << (scops ? scops->length () : 0);); |
1673 | } | |
1674 | ||
076d564d | 1675 | #endif /* HAVE_isl */ |