]>
Commit | Line | Data |
---|---|---|
c6bb733d | 1 | /* Single entry single exit control flow regions. |
aad93da1 | 2 | Copyright (C) 2008-2017 Free Software Foundation, Inc. |
c6bb733d | 3 | Contributed by Jan Sjodin <jan.sjodin@amd.com> and |
4 | Sebastian Pop <sebastian.pop@amd.com>. | |
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 | ||
22 | #include "config.h" | |
23 | #include "system.h" | |
24 | #include "coretypes.h" | |
9ef16211 | 25 | #include "backend.h" |
0d9585ca | 26 | #include "tree.h" |
9ef16211 | 27 | #include "gimple.h" |
7c29e30e | 28 | #include "cfghooks.h" |
29 | #include "tree-pass.h" | |
9ef16211 | 30 | #include "ssa.h" |
ce084dfc | 31 | #include "tree-pretty-print.h" |
7c29e30e | 32 | #include "fold-const.h" |
a8783bee | 33 | #include "gimplify.h" |
dcf1a1ec | 34 | #include "gimple-iterator.h" |
30162daa | 35 | #include "gimple-pretty-print.h" |
e795d6e1 | 36 | #include "gimplify-me.h" |
073c1fd5 | 37 | #include "tree-cfg.h" |
073c1fd5 | 38 | #include "tree-ssa-loop.h" |
39 | #include "tree-into-ssa.h" | |
c6bb733d | 40 | #include "cfgloop.h" |
c6bb733d | 41 | #include "tree-data-ref.h" |
42 | #include "tree-scalar-evolution.h" | |
c6bb733d | 43 | #include "sese.h" |
0f4161b1 | 44 | #include "tree-ssa-propagate.h" |
c6bb733d | 45 | |
c6bb733d | 46 | /* For a USE in BB, if BB is outside REGION, mark the USE in the |
47 | LIVEOUTS set. */ | |
48 | ||
49 | static void | |
f032380c | 50 | sese_build_liveouts_use (sese_info_p region, bitmap liveouts, basic_block bb, |
c6bb733d | 51 | tree use) |
52 | { | |
f032380c | 53 | gcc_assert (!bb_in_sese_p (bb, region->region)); |
c6bb733d | 54 | if (TREE_CODE (use) != SSA_NAME) |
55 | return; | |
56 | ||
f1537fda | 57 | basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (use)); |
c6bb733d | 58 | |
f032380c | 59 | if (!def_bb || !bb_in_sese_p (def_bb, region->region)) |
c6bb733d | 60 | return; |
61 | ||
f1537fda | 62 | unsigned ver = SSA_NAME_VERSION (use); |
c6bb733d | 63 | bitmap_set_bit (liveouts, ver); |
64 | } | |
65 | ||
66 | /* Marks for rewrite all the SSA_NAMES defined in REGION and that are | |
67 | used in BB that is outside of the REGION. */ | |
68 | ||
69 | static void | |
f032380c | 70 | sese_build_liveouts_bb (sese_info_p region, bitmap liveouts, basic_block bb) |
c6bb733d | 71 | { |
c6bb733d | 72 | edge e; |
73 | edge_iterator ei; | |
74 | ssa_op_iter iter; | |
75 | use_operand_p use_p; | |
76 | ||
77 | FOR_EACH_EDGE (e, ei, bb->succs) | |
1a91d914 | 78 | for (gphi_iterator bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); |
79 | gsi_next (&bsi)) | |
c6bb733d | 80 | sese_build_liveouts_use (region, liveouts, bb, |
1a91d914 | 81 | PHI_ARG_DEF_FROM_EDGE (bsi.phi (), e)); |
c6bb733d | 82 | |
1a91d914 | 83 | for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi); |
84 | gsi_next (&bsi)) | |
3f6c0a40 | 85 | { |
42acab1c | 86 | gimple *stmt = gsi_stmt (bsi); |
3f6c0a40 | 87 | |
88 | if (is_gimple_debug (stmt)) | |
89 | continue; | |
90 | ||
91 | FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES) | |
92 | sese_build_liveouts_use (region, liveouts, bb, USE_FROM_PTR (use_p)); | |
93 | } | |
94 | } | |
95 | ||
96 | /* For a USE in BB, return true if BB is outside REGION and it's not | |
97 | in the LIVEOUTS set. */ | |
98 | ||
99 | static bool | |
f032380c | 100 | sese_bad_liveouts_use (sese_info_p region, bitmap liveouts, basic_block bb, |
3f6c0a40 | 101 | tree use) |
102 | { | |
f032380c | 103 | gcc_assert (!bb_in_sese_p (bb, region->region)); |
3f6c0a40 | 104 | |
105 | if (TREE_CODE (use) != SSA_NAME) | |
106 | return false; | |
107 | ||
f1537fda | 108 | unsigned ver = SSA_NAME_VERSION (use); |
3f6c0a40 | 109 | |
110 | /* If it's in liveouts, the variable will get a new PHI node, and | |
111 | the debug use will be properly adjusted. */ | |
112 | if (bitmap_bit_p (liveouts, ver)) | |
113 | return false; | |
114 | ||
f1537fda | 115 | basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (use)); |
3f6c0a40 | 116 | |
f032380c | 117 | if (!def_bb || !bb_in_sese_p (def_bb, region->region)) |
3f6c0a40 | 118 | return false; |
119 | ||
120 | return true; | |
121 | } | |
122 | ||
123 | /* Reset debug stmts that reference SSA_NAMES defined in REGION that | |
124 | are not marked as liveouts. */ | |
125 | ||
126 | static void | |
c604a230 | 127 | sese_reset_debug_liveouts_bb (sese_info_p region, bitmap liveouts, |
128 | basic_block bb) | |
3f6c0a40 | 129 | { |
130 | gimple_stmt_iterator bsi; | |
131 | ssa_op_iter iter; | |
132 | use_operand_p use_p; | |
133 | ||
134 | for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) | |
135 | { | |
42acab1c | 136 | gimple *stmt = gsi_stmt (bsi); |
3f6c0a40 | 137 | |
138 | if (!is_gimple_debug (stmt)) | |
139 | continue; | |
140 | ||
141 | FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES) | |
142 | if (sese_bad_liveouts_use (region, liveouts, bb, | |
143 | USE_FROM_PTR (use_p))) | |
144 | { | |
145 | gimple_debug_bind_reset_value (stmt); | |
146 | update_stmt (stmt); | |
147 | break; | |
148 | } | |
149 | } | |
c6bb733d | 150 | } |
151 | ||
152 | /* Build the LIVEOUTS of REGION: the set of variables defined inside | |
153 | and used outside the REGION. */ | |
154 | ||
155 | static void | |
f032380c | 156 | sese_build_liveouts (sese_info_p region, bitmap liveouts) |
c6bb733d | 157 | { |
158 | basic_block bb; | |
159 | ||
f1537fda | 160 | /* FIXME: We could start iterating form the successor of sese. */ |
fc00614f | 161 | FOR_EACH_BB_FN (bb, cfun) |
f032380c | 162 | if (!bb_in_sese_p (bb, region->region)) |
f1537fda | 163 | sese_build_liveouts_bb (region, liveouts, bb); |
164 | ||
165 | /* FIXME: We could start iterating form the successor of sese. */ | |
aedb7bf8 | 166 | if (MAY_HAVE_DEBUG_STMTS) |
fc00614f | 167 | FOR_EACH_BB_FN (bb, cfun) |
f032380c | 168 | if (!bb_in_sese_p (bb, region->region)) |
f1537fda | 169 | sese_reset_debug_liveouts_bb (region, liveouts, bb); |
c6bb733d | 170 | } |
171 | ||
172 | /* Builds a new SESE region from edges ENTRY and EXIT. */ | |
173 | ||
f032380c | 174 | sese_info_p |
175 | new_sese_info (edge entry, edge exit) | |
c6bb733d | 176 | { |
f032380c | 177 | sese_info_p region = XNEW (struct sese_info_t); |
c6bb733d | 178 | |
f032380c | 179 | region->region.entry = entry; |
180 | region->region.exit = exit; | |
30162daa | 181 | region->loop_nest.create (3); |
182 | region->params.create (3); | |
183 | region->rename_map = new rename_map_t; | |
c3a14714 | 184 | region->parameter_rename_map = new parameter_rename_map_t; |
30162daa | 185 | region->copied_bb_map = new bb_map_t; |
0e526381 | 186 | region->bbs.create (3); |
30162daa | 187 | region->incomplete_phis.create (3); |
c6bb733d | 188 | |
c3a14714 | 189 | |
c6bb733d | 190 | return region; |
191 | } | |
192 | ||
193 | /* Deletes REGION. */ | |
194 | ||
195 | void | |
f032380c | 196 | free_sese_info (sese_info_p region) |
c6bb733d | 197 | { |
30162daa | 198 | region->params.release (); |
199 | region->loop_nest.release (); | |
200 | ||
201 | for (rename_map_t::iterator it = region->rename_map->begin (); | |
ba0f85a5 | 202 | it != region->rename_map->end (); ++it) |
30162daa | 203 | (*it).second.release (); |
204 | ||
205 | for (bb_map_t::iterator it = region->copied_bb_map->begin (); | |
ba0f85a5 | 206 | it != region->copied_bb_map->end (); ++it) |
30162daa | 207 | (*it).second.release (); |
c6bb733d | 208 | |
30162daa | 209 | delete region->rename_map; |
c3a14714 | 210 | delete region->parameter_rename_map; |
30162daa | 211 | delete region->copied_bb_map; |
212 | ||
213 | region->rename_map = NULL; | |
c3a14714 | 214 | region->parameter_rename_map = NULL; |
30162daa | 215 | region->copied_bb_map = NULL; |
216 | ||
217 | region->bbs.release (); | |
218 | region->incomplete_phis.release (); | |
c6bb733d | 219 | |
c6bb733d | 220 | XDELETE (region); |
221 | } | |
222 | ||
223 | /* Add exit phis for USE on EXIT. */ | |
224 | ||
225 | static void | |
226 | sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e) | |
227 | { | |
1a91d914 | 228 | gphi *phi = create_phi_node (NULL_TREE, exit); |
9c06f260 | 229 | create_new_def_for (use, phi, gimple_phi_result_ptr (phi)); |
60d535d2 | 230 | add_phi_arg (phi, use, false_e, UNKNOWN_LOCATION); |
231 | add_phi_arg (phi, use, true_e, UNKNOWN_LOCATION); | |
fa4dba85 | 232 | update_stmt (phi); |
c6bb733d | 233 | } |
234 | ||
235 | /* Insert in the block BB phi nodes for variables defined in REGION | |
236 | and used outside the REGION. The code generation moves REGION in | |
237 | the else clause of an "if (1)" and generates code in the then | |
238 | clause that is at this point empty: | |
239 | ||
240 | | if (1) | |
241 | | empty; | |
242 | | else | |
243 | | REGION; | |
244 | */ | |
245 | ||
246 | void | |
f032380c | 247 | sese_insert_phis_for_liveouts (sese_info_p region, basic_block bb, |
c6bb733d | 248 | edge false_e, edge true_e) |
249 | { | |
250 | unsigned i; | |
251 | bitmap_iterator bi; | |
252 | bitmap liveouts = BITMAP_ALLOC (NULL); | |
253 | ||
c6bb733d | 254 | sese_build_liveouts (region, liveouts); |
30162daa | 255 | |
c6bb733d | 256 | EXECUTE_IF_SET_IN_BITMAP (liveouts, 0, i, bi) |
30162daa | 257 | if (!virtual_operand_p (ssa_name (i))) |
258 | sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e); | |
259 | ||
c6bb733d | 260 | BITMAP_FREE (liveouts); |
c6bb733d | 261 | } |
262 | ||
30162daa | 263 | /* Returns the outermost loop in SCOP that contains BB. */ |
c6bb733d | 264 | |
265 | struct loop * | |
f032380c | 266 | outermost_loop_in_sese_1 (sese_l ®ion, basic_block bb) |
c6bb733d | 267 | { |
268 | struct loop *nest; | |
269 | ||
270 | nest = bb->loop_father; | |
271 | while (loop_outer (nest) | |
272 | && loop_in_sese_p (loop_outer (nest), region)) | |
273 | nest = loop_outer (nest); | |
274 | ||
275 | return nest; | |
276 | } | |
277 | ||
443b5bd0 | 278 | /* Same as outermost_loop_in_sese_1, returns the outermost loop |
279 | containing BB in REGION, but makes sure that the returned loop | |
280 | belongs to the REGION, and so this returns the first loop in the | |
281 | REGION when the loop containing BB does not belong to REGION. */ | |
282 | ||
283 | loop_p | |
f032380c | 284 | outermost_loop_in_sese (sese_l ®ion, basic_block bb) |
443b5bd0 | 285 | { |
286 | loop_p nest = outermost_loop_in_sese_1 (region, bb); | |
287 | ||
288 | if (loop_in_sese_p (nest, region)) | |
289 | return nest; | |
290 | ||
291 | /* When the basic block BB does not belong to a loop in the region, | |
292 | return the first loop in the region. */ | |
293 | nest = nest->inner; | |
294 | while (nest) | |
295 | if (loop_in_sese_p (nest, region)) | |
296 | break; | |
297 | else | |
298 | nest = nest->next; | |
299 | ||
300 | gcc_assert (nest); | |
301 | return nest; | |
302 | } | |
303 | ||
2bca9286 | 304 | /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */ |
305 | ||
306 | edge | |
307 | get_true_edge_from_guard_bb (basic_block bb) | |
308 | { | |
309 | edge e; | |
310 | edge_iterator ei; | |
311 | ||
312 | FOR_EACH_EDGE (e, ei, bb->succs) | |
313 | if (e->flags & EDGE_TRUE_VALUE) | |
314 | return e; | |
315 | ||
316 | gcc_unreachable (); | |
317 | return NULL; | |
318 | } | |
319 | ||
320 | /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */ | |
321 | ||
322 | edge | |
323 | get_false_edge_from_guard_bb (basic_block bb) | |
324 | { | |
325 | edge e; | |
326 | edge_iterator ei; | |
327 | ||
328 | FOR_EACH_EDGE (e, ei, bb->succs) | |
329 | if (!(e->flags & EDGE_TRUE_VALUE)) | |
330 | return e; | |
331 | ||
332 | gcc_unreachable (); | |
333 | return NULL; | |
334 | } | |
335 | ||
c6bb733d | 336 | /* Sets the false region of an IF_REGION to REGION. */ |
337 | ||
d76166e6 | 338 | static void |
f032380c | 339 | if_region_set_false_region (ifsese if_region, sese_info_p region) |
c6bb733d | 340 | { |
d76166e6 | 341 | free_dominance_info (CDI_DOMINATORS); |
342 | ||
c6bb733d | 343 | basic_block condition = if_region_get_condition_block (if_region); |
344 | edge false_edge = get_false_edge_from_guard_bb (condition); | |
345 | basic_block dummy = false_edge->dest; | |
f032380c | 346 | edge entry_region = region->region.entry; |
347 | edge exit_region = region->region.exit; | |
c6bb733d | 348 | basic_block before_region = entry_region->src; |
349 | basic_block last_in_region = exit_region->src; | |
2ef51f0e | 350 | hashval_t hash = htab_hash_pointer (exit_region); |
351 | loop_exit **slot | |
352 | = current_loops->exits->find_slot_with_hash (exit_region, hash, NO_INSERT); | |
d76166e6 | 353 | bool latch_p |
354 | = exit_region->dest->loop_father->latch == exit_region->src; | |
c6bb733d | 355 | |
356 | entry_region->flags = false_edge->flags; | |
357 | false_edge->flags = exit_region->flags; | |
358 | ||
359 | redirect_edge_pred (entry_region, condition); | |
360 | redirect_edge_pred (exit_region, before_region); | |
361 | redirect_edge_pred (false_edge, last_in_region); | |
362 | redirect_edge_succ (false_edge, single_succ (dummy)); | |
363 | delete_basic_block (dummy); | |
364 | ||
365 | exit_region->flags = EDGE_FALLTHRU; | |
c6bb733d | 366 | |
f032380c | 367 | region->region.exit = false_edge; |
d996851c | 368 | |
dd045aee | 369 | free (if_region->false_region); |
c6bb733d | 370 | if_region->false_region = region; |
371 | ||
372 | if (slot) | |
373 | { | |
25a27413 | 374 | struct loop_exit *loop_exit = ggc_cleared_alloc<struct loop_exit> (); |
c6bb733d | 375 | |
c604a230 | 376 | memcpy (loop_exit, *((struct loop_exit **) slot), |
377 | sizeof (struct loop_exit)); | |
2ef51f0e | 378 | current_loops->exits->clear_slot (slot); |
c6bb733d | 379 | |
e0c0be18 | 380 | hashval_t hash = htab_hash_pointer (false_edge); |
2ef51f0e | 381 | slot = current_loops->exits->find_slot_with_hash (false_edge, hash, |
382 | INSERT); | |
c6bb733d | 383 | loop_exit->e = false_edge; |
384 | *slot = loop_exit; | |
385 | false_edge->src->loop_father->exits->next = loop_exit; | |
386 | } | |
d76166e6 | 387 | if (latch_p) |
388 | exit_region->dest->loop_father->latch = before_region; | |
389 | ||
390 | calculate_dominance_info (CDI_DOMINATORS); | |
c6bb733d | 391 | } |
392 | ||
393 | /* Creates an IFSESE with CONDITION on edge ENTRY. */ | |
394 | ||
2bf96dd7 | 395 | static ifsese |
c6bb733d | 396 | create_if_region_on_edge (edge entry, tree condition) |
397 | { | |
398 | edge e; | |
399 | edge_iterator ei; | |
f032380c | 400 | sese_info_p sese_region = XNEW (struct sese_info_t); |
401 | sese_info_p true_region = XNEW (struct sese_info_t); | |
402 | sese_info_p false_region = XNEW (struct sese_info_t); | |
d996851c | 403 | ifsese if_region = XNEW (struct ifsese_s); |
c6bb733d | 404 | edge exit = create_empty_if_region_on_edge (entry, condition); |
405 | ||
406 | if_region->region = sese_region; | |
f032380c | 407 | if_region->region->region.entry = entry; |
408 | if_region->region->region.exit = exit; | |
c6bb733d | 409 | |
410 | FOR_EACH_EDGE (e, ei, entry->dest->succs) | |
411 | { | |
412 | if (e->flags & EDGE_TRUE_VALUE) | |
413 | { | |
f032380c | 414 | true_region->region.entry = e; |
415 | true_region->region.exit = single_succ_edge (e->dest); | |
c6bb733d | 416 | if_region->true_region = true_region; |
417 | } | |
418 | else if (e->flags & EDGE_FALSE_VALUE) | |
419 | { | |
f032380c | 420 | false_region->region.entry = e; |
421 | false_region->region.exit = single_succ_edge (e->dest); | |
c6bb733d | 422 | if_region->false_region = false_region; |
423 | } | |
424 | } | |
425 | ||
426 | return if_region; | |
427 | } | |
428 | ||
429 | /* Moves REGION in a condition expression: | |
430 | | if (1) | |
431 | | ; | |
432 | | else | |
433 | | REGION; | |
434 | */ | |
435 | ||
436 | ifsese | |
f032380c | 437 | move_sese_in_condition (sese_info_p region) |
c6bb733d | 438 | { |
d76166e6 | 439 | gcc_assert (! dom_info_available_p (cfun, CDI_POST_DOMINATORS)); |
f032380c | 440 | basic_block pred_block = split_edge (region->region.entry); |
d996851c | 441 | ifsese if_region; |
c6bb733d | 442 | |
f032380c | 443 | region->region.entry = single_succ_edge (pred_block); |
e0c0be18 | 444 | if_region = create_if_region_on_edge (single_pred_edge (pred_block), |
445 | integer_one_node); | |
c6bb733d | 446 | if_region_set_false_region (if_region, region); |
447 | ||
448 | return if_region; | |
449 | } | |
450 | ||
2487de19 | 451 | /* Replaces the condition of the IF_REGION with CONDITION: |
452 | | if (CONDITION) | |
453 | | true_region; | |
454 | | else | |
455 | | false_region; | |
456 | */ | |
457 | ||
458 | void | |
459 | set_ifsese_condition (ifsese if_region, tree condition) | |
460 | { | |
f032380c | 461 | sese_info_p region = if_region->region; |
462 | edge entry = region->region.entry; | |
2487de19 | 463 | basic_block bb = entry->dest; |
42acab1c | 464 | gimple *last = last_stmt (bb); |
2487de19 | 465 | gimple_stmt_iterator gsi = gsi_last_bb (bb); |
1a91d914 | 466 | gcond *cond_stmt; |
2487de19 | 467 | |
468 | gcc_assert (gimple_code (last) == GIMPLE_COND); | |
469 | ||
470 | gsi_remove (&gsi, true); | |
471 | gsi = gsi_last_bb (bb); | |
472 | condition = force_gimple_operand_gsi (&gsi, condition, true, NULL, | |
473 | false, GSI_NEW_STMT); | |
474 | cond_stmt = gimple_build_cond_from_tree (condition, NULL_TREE, NULL_TREE); | |
475 | gsi = gsi_last_bb (bb); | |
476 | gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT); | |
477 | } | |
478 | ||
9c0cc377 | 479 | /* Return true when T is defined outside REGION or when no definitions are |
13f421d5 | 480 | variant in REGION. When HAS_VDEFS is a valid pointer, sets HAS_VDEFS to true |
481 | when T depends on memory that may change in REGION. */ | |
fa4dba85 | 482 | |
9c0cc377 | 483 | bool |
d523d0c4 | 484 | invariant_in_sese_p_rec (tree t, const sese_l ®ion, bool *has_vdefs) |
fa4dba85 | 485 | { |
fa4dba85 | 486 | if (!defined_in_sese_p (t, region)) |
487 | return true; | |
488 | ||
42acab1c | 489 | gimple *stmt = SSA_NAME_DEF_STMT (t); |
fa4dba85 | 490 | |
491 | if (gimple_code (stmt) == GIMPLE_PHI | |
492 | || gimple_code (stmt) == GIMPLE_CALL) | |
493 | return false; | |
494 | ||
9c0cc377 | 495 | /* VDEF is variant when it is in the region. */ |
ec6135ce | 496 | if (gimple_vdef (stmt)) |
13f421d5 | 497 | { |
498 | if (has_vdefs) | |
499 | *has_vdefs = true; | |
500 | return false; | |
501 | } | |
9c0cc377 | 502 | |
503 | /* A VUSE may or may not be variant following the VDEFs. */ | |
504 | if (tree vuse = gimple_vuse (stmt)) | |
13f421d5 | 505 | return invariant_in_sese_p_rec (vuse, region, has_vdefs); |
9c0cc377 | 506 | |
30162daa | 507 | ssa_op_iter iter; |
508 | use_operand_p use_p; | |
fa4dba85 | 509 | FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE) |
510 | { | |
511 | tree use = USE_FROM_PTR (use_p); | |
9c0cc377 | 512 | |
fa4dba85 | 513 | if (!defined_in_sese_p (use, region)) |
514 | continue; | |
515 | ||
13f421d5 | 516 | if (!invariant_in_sese_p_rec (use, region, has_vdefs)) |
fa4dba85 | 517 | return false; |
518 | } | |
519 | ||
520 | return true; | |
521 | } | |
522 | ||
c604a230 | 523 | /* Return true when DEF can be analyzed in REGION by the scalar |
524 | evolution analyzer. */ | |
525 | ||
526 | bool | |
527 | scev_analyzable_p (tree def, sese_l ®ion) | |
528 | { | |
529 | loop_p loop; | |
530 | tree scev; | |
531 | tree type = TREE_TYPE (def); | |
532 | ||
533 | /* When Graphite generates code for a scev, the code generator | |
534 | expresses the scev in function of a single induction variable. | |
535 | This is unsafe for floating point computations, as it may replace | |
536 | a floating point sum reduction with a multiplication. The | |
537 | following test returns false for non integer types to avoid such | |
538 | problems. */ | |
539 | if (!INTEGRAL_TYPE_P (type) | |
540 | && !POINTER_TYPE_P (type)) | |
541 | return false; | |
542 | ||
543 | loop = loop_containing_stmt (SSA_NAME_DEF_STMT (def)); | |
544 | scev = scalar_evolution_in_region (region, loop, def); | |
545 | ||
546 | return !chrec_contains_undetermined (scev) | |
547 | && (TREE_CODE (scev) != SSA_NAME | |
548 | || !defined_in_sese_p (scev, region)) | |
549 | && (tree_does_not_contain_chrecs (scev) | |
550 | || evolution_function_is_affine_p (scev)); | |
551 | } | |
552 | ||
c6bb733d | 553 | /* Returns the scalar evolution of T in REGION. Every variable that |
554 | is not defined in the REGION is considered a parameter. */ | |
555 | ||
556 | tree | |
d523d0c4 | 557 | scalar_evolution_in_region (const sese_l ®ion, loop_p loop, tree t) |
c6bb733d | 558 | { |
42acab1c | 559 | gimple *def; |
c6bb733d | 560 | struct loop *def_loop; |
f032380c | 561 | basic_block before = region.entry->src; |
c6bb733d | 562 | |
ae6346fd | 563 | /* SCOP parameters. */ |
564 | if (TREE_CODE (t) == SSA_NAME | |
565 | && !defined_in_sese_p (t, region)) | |
566 | return t; | |
567 | ||
c6bb733d | 568 | if (TREE_CODE (t) != SSA_NAME |
569 | || loop_in_sese_p (loop, region)) | |
0a3e9578 | 570 | /* FIXME: we would need instantiate SCEV to work on a region, and be more |
571 | flexible wrt. memory loads that may be invariant in the region. */ | |
c6bb733d | 572 | return instantiate_scev (before, loop, |
573 | analyze_scalar_evolution (loop, t)); | |
574 | ||
c6bb733d | 575 | def = SSA_NAME_DEF_STMT (t); |
576 | def_loop = loop_containing_stmt (def); | |
577 | ||
578 | if (loop_in_sese_p (def_loop, region)) | |
579 | { | |
580 | t = analyze_scalar_evolution (def_loop, t); | |
581 | def_loop = superloop_at_depth (def_loop, loop_depth (loop) + 1); | |
582 | t = compute_overall_effect_of_inner_loop (def_loop, t); | |
583 | return t; | |
584 | } | |
fa4dba85 | 585 | |
13f421d5 | 586 | bool has_vdefs = false; |
587 | if (invariant_in_sese_p_rec (t, region, &has_vdefs)) | |
fa4dba85 | 588 | return t; |
589 | ||
13f421d5 | 590 | /* T variates in REGION. */ |
591 | if (has_vdefs) | |
592 | return chrec_dont_know; | |
593 | ||
fa4dba85 | 594 | return instantiate_scev (before, loop, t); |
c6bb733d | 595 | } |
c1616982 | 596 | |
597 | /* Pretty print edge E to FILE. */ | |
598 | ||
599 | void | |
600 | print_edge (FILE *file, const_edge e) | |
601 | { | |
602 | fprintf (file, "edge (bb_%d, bb_%d)", e->src->index, e->dest->index); | |
603 | } | |
604 | ||
605 | /* Pretty print sese S to FILE. */ | |
606 | ||
607 | void | |
608 | print_sese (FILE *file, const sese_l &s) | |
609 | { | |
610 | fprintf (file, "(entry_"); print_edge (file, s.entry); | |
611 | fprintf (file, ", exit_"); print_edge (file, s.exit); | |
612 | fprintf (file, ")\n"); | |
613 | } | |
614 | ||
615 | /* Pretty print edge E to STDERR. */ | |
616 | ||
617 | DEBUG_FUNCTION void | |
618 | debug_edge (const_edge e) | |
619 | { | |
620 | print_edge (stderr, e); | |
621 | } | |
622 | ||
623 | /* Pretty print sese S to STDERR. */ | |
624 | ||
625 | DEBUG_FUNCTION void | |
626 | debug_sese (const sese_l &s) | |
627 | { | |
628 | print_sese (stderr, s); | |
629 | } |