]>
Commit | Line | Data |
---|---|---|
c6bb733d | 1 | /* Single entry single exit control flow regions. |
d353bf18 | 2 | Copyright (C) 2008-2015 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" | |
b20a8bb4 | 25 | #include "alias.h" |
9ef16211 | 26 | #include "backend.h" |
d040a5b0 | 27 | #include "cfghooks.h" |
0d9585ca | 28 | #include "tree.h" |
9ef16211 | 29 | #include "gimple.h" |
30 | #include "hard-reg-set.h" | |
31 | #include "ssa.h" | |
32 | #include "options.h" | |
b20a8bb4 | 33 | #include "fold-const.h" |
ce084dfc | 34 | #include "tree-pretty-print.h" |
bc61cadb | 35 | #include "internal-fn.h" |
36 | #include "gimple-fold.h" | |
37 | #include "tree-eh.h" | |
a8783bee | 38 | #include "gimplify.h" |
dcf1a1ec | 39 | #include "gimple-iterator.h" |
e795d6e1 | 40 | #include "gimplify-me.h" |
073c1fd5 | 41 | #include "tree-cfg.h" |
073c1fd5 | 42 | #include "tree-ssa-loop.h" |
43 | #include "tree-into-ssa.h" | |
c6bb733d | 44 | #include "cfgloop.h" |
45 | #include "tree-chrec.h" | |
46 | #include "tree-data-ref.h" | |
47 | #include "tree-scalar-evolution.h" | |
48 | #include "tree-pass.h" | |
c6bb733d | 49 | #include "value-prof.h" |
c6bb733d | 50 | #include "sese.h" |
0f4161b1 | 51 | #include "tree-ssa-propagate.h" |
ad7173b9 | 52 | #include "tree-hash-traits.h" |
c6bb733d | 53 | |
5358b152 | 54 | /* Helper function for debug_rename_map. */ |
c6bb733d | 55 | |
5358b152 | 56 | bool |
57 | debug_rename_map_1 (tree_node *const &old_name, tree_node *const &expr, | |
58 | void *) | |
c6bb733d | 59 | { |
60 | fprintf (stderr, "("); | |
5358b152 | 61 | print_generic_expr (stderr, old_name, 0); |
c6bb733d | 62 | fprintf (stderr, ", "); |
5358b152 | 63 | print_generic_expr (stderr, expr, 0); |
c6bb733d | 64 | fprintf (stderr, ")\n"); |
5358b152 | 65 | return true; |
c6bb733d | 66 | } |
d9dd21a8 | 67 | \f |
ee34b0e4 | 68 | typedef hash_map<tree_ssa_name_hash, tree> rename_map_type; |
d9dd21a8 | 69 | \f |
c6bb733d | 70 | |
97142493 | 71 | /* Print to stderr all the elements of RENAME_MAP. */ |
c6bb733d | 72 | |
4b987fac | 73 | DEBUG_FUNCTION void |
c1f445d2 | 74 | debug_rename_map (rename_map_type *rename_map) |
c6bb733d | 75 | { |
c1f445d2 | 76 | rename_map->traverse <void *, debug_rename_map_1> (NULL); |
c6bb733d | 77 | } |
c6bb733d | 78 | \f |
79 | ||
9d75589a | 80 | /* Record LOOP as occurring in REGION. */ |
c6bb733d | 81 | |
82 | static void | |
f032380c | 83 | sese_record_loop (sese_info_p region, loop_p loop) |
c6bb733d | 84 | { |
85 | if (sese_contains_loop (region, loop)) | |
86 | return; | |
87 | ||
88 | bitmap_set_bit (SESE_LOOPS (region), loop->num); | |
f1f41a6c | 89 | SESE_LOOP_NEST (region).safe_push (loop); |
c6bb733d | 90 | } |
91 | ||
92 | /* Build the loop nests contained in REGION. Returns true when the | |
93 | operation was successful. */ | |
94 | ||
95 | void | |
f032380c | 96 | build_sese_loop_nests (sese_info_p region) |
c6bb733d | 97 | { |
98 | unsigned i; | |
99 | basic_block bb; | |
100 | struct loop *loop0, *loop1; | |
101 | ||
fc00614f | 102 | FOR_EACH_BB_FN (bb, cfun) |
f032380c | 103 | if (bb_in_sese_p (bb, region->region)) |
c6bb733d | 104 | { |
105 | struct loop *loop = bb->loop_father; | |
106 | ||
107 | /* Only add loops if they are completely contained in the SCoP. */ | |
108 | if (loop->header == bb | |
f032380c | 109 | && bb_in_sese_p (loop->latch, region->region)) |
c6bb733d | 110 | sese_record_loop (region, loop); |
111 | } | |
112 | ||
113 | /* Make sure that the loops in the SESE_LOOP_NEST are ordered. It | |
114 | can be the case that an inner loop is inserted before an outer | |
115 | loop. To avoid this, semi-sort once. */ | |
f1f41a6c | 116 | FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region), i, loop0) |
c6bb733d | 117 | { |
f1f41a6c | 118 | if (SESE_LOOP_NEST (region).length () == i + 1) |
c6bb733d | 119 | break; |
120 | ||
f1f41a6c | 121 | loop1 = SESE_LOOP_NEST (region)[i + 1]; |
c6bb733d | 122 | if (loop0->num > loop1->num) |
123 | { | |
f1f41a6c | 124 | SESE_LOOP_NEST (region)[i] = loop1; |
125 | SESE_LOOP_NEST (region)[i + 1] = loop0; | |
c6bb733d | 126 | } |
127 | } | |
128 | } | |
129 | ||
130 | /* For a USE in BB, if BB is outside REGION, mark the USE in the | |
131 | LIVEOUTS set. */ | |
132 | ||
133 | static void | |
f032380c | 134 | sese_build_liveouts_use (sese_info_p region, bitmap liveouts, basic_block bb, |
c6bb733d | 135 | tree use) |
136 | { | |
f032380c | 137 | gcc_assert (!bb_in_sese_p (bb, region->region)); |
c6bb733d | 138 | if (TREE_CODE (use) != SSA_NAME) |
139 | return; | |
140 | ||
f1537fda | 141 | basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (use)); |
c6bb733d | 142 | |
f032380c | 143 | if (!def_bb || !bb_in_sese_p (def_bb, region->region)) |
c6bb733d | 144 | return; |
145 | ||
f1537fda | 146 | unsigned ver = SSA_NAME_VERSION (use); |
c6bb733d | 147 | bitmap_set_bit (liveouts, ver); |
148 | } | |
149 | ||
150 | /* Marks for rewrite all the SSA_NAMES defined in REGION and that are | |
151 | used in BB that is outside of the REGION. */ | |
152 | ||
153 | static void | |
f032380c | 154 | sese_build_liveouts_bb (sese_info_p region, bitmap liveouts, basic_block bb) |
c6bb733d | 155 | { |
c6bb733d | 156 | edge e; |
157 | edge_iterator ei; | |
158 | ssa_op_iter iter; | |
159 | use_operand_p use_p; | |
160 | ||
161 | FOR_EACH_EDGE (e, ei, bb->succs) | |
1a91d914 | 162 | for (gphi_iterator bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); |
163 | gsi_next (&bsi)) | |
c6bb733d | 164 | sese_build_liveouts_use (region, liveouts, bb, |
1a91d914 | 165 | PHI_ARG_DEF_FROM_EDGE (bsi.phi (), e)); |
c6bb733d | 166 | |
1a91d914 | 167 | for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi); |
168 | gsi_next (&bsi)) | |
3f6c0a40 | 169 | { |
42acab1c | 170 | gimple *stmt = gsi_stmt (bsi); |
3f6c0a40 | 171 | |
172 | if (is_gimple_debug (stmt)) | |
173 | continue; | |
174 | ||
175 | FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES) | |
176 | sese_build_liveouts_use (region, liveouts, bb, USE_FROM_PTR (use_p)); | |
177 | } | |
178 | } | |
179 | ||
180 | /* For a USE in BB, return true if BB is outside REGION and it's not | |
181 | in the LIVEOUTS set. */ | |
182 | ||
183 | static bool | |
f032380c | 184 | sese_bad_liveouts_use (sese_info_p region, bitmap liveouts, basic_block bb, |
3f6c0a40 | 185 | tree use) |
186 | { | |
f032380c | 187 | gcc_assert (!bb_in_sese_p (bb, region->region)); |
3f6c0a40 | 188 | |
189 | if (TREE_CODE (use) != SSA_NAME) | |
190 | return false; | |
191 | ||
f1537fda | 192 | unsigned ver = SSA_NAME_VERSION (use); |
3f6c0a40 | 193 | |
194 | /* If it's in liveouts, the variable will get a new PHI node, and | |
195 | the debug use will be properly adjusted. */ | |
196 | if (bitmap_bit_p (liveouts, ver)) | |
197 | return false; | |
198 | ||
f1537fda | 199 | basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (use)); |
3f6c0a40 | 200 | |
f032380c | 201 | if (!def_bb || !bb_in_sese_p (def_bb, region->region)) |
3f6c0a40 | 202 | return false; |
203 | ||
204 | return true; | |
205 | } | |
206 | ||
207 | /* Reset debug stmts that reference SSA_NAMES defined in REGION that | |
208 | are not marked as liveouts. */ | |
209 | ||
210 | static void | |
f032380c | 211 | sese_reset_debug_liveouts_bb (sese_info_p region, bitmap liveouts, basic_block bb) |
3f6c0a40 | 212 | { |
213 | gimple_stmt_iterator bsi; | |
214 | ssa_op_iter iter; | |
215 | use_operand_p use_p; | |
216 | ||
217 | for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) | |
218 | { | |
42acab1c | 219 | gimple *stmt = gsi_stmt (bsi); |
3f6c0a40 | 220 | |
221 | if (!is_gimple_debug (stmt)) | |
222 | continue; | |
223 | ||
224 | FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES) | |
225 | if (sese_bad_liveouts_use (region, liveouts, bb, | |
226 | USE_FROM_PTR (use_p))) | |
227 | { | |
228 | gimple_debug_bind_reset_value (stmt); | |
229 | update_stmt (stmt); | |
230 | break; | |
231 | } | |
232 | } | |
c6bb733d | 233 | } |
234 | ||
235 | /* Build the LIVEOUTS of REGION: the set of variables defined inside | |
236 | and used outside the REGION. */ | |
237 | ||
238 | static void | |
f032380c | 239 | sese_build_liveouts (sese_info_p region, bitmap liveouts) |
c6bb733d | 240 | { |
241 | basic_block bb; | |
242 | ||
f1537fda | 243 | /* FIXME: We could start iterating form the successor of sese. */ |
fc00614f | 244 | FOR_EACH_BB_FN (bb, cfun) |
f032380c | 245 | if (!bb_in_sese_p (bb, region->region)) |
f1537fda | 246 | sese_build_liveouts_bb (region, liveouts, bb); |
247 | ||
248 | /* FIXME: We could start iterating form the successor of sese. */ | |
aedb7bf8 | 249 | if (MAY_HAVE_DEBUG_STMTS) |
fc00614f | 250 | FOR_EACH_BB_FN (bb, cfun) |
f032380c | 251 | if (!bb_in_sese_p (bb, region->region)) |
f1537fda | 252 | sese_reset_debug_liveouts_bb (region, liveouts, bb); |
c6bb733d | 253 | } |
254 | ||
255 | /* Builds a new SESE region from edges ENTRY and EXIT. */ | |
256 | ||
f032380c | 257 | sese_info_p |
258 | new_sese_info (edge entry, edge exit) | |
c6bb733d | 259 | { |
f032380c | 260 | sese_info_p region = XNEW (struct sese_info_t); |
c6bb733d | 261 | |
f032380c | 262 | region->region.entry = entry; |
263 | region->region.exit = exit; | |
c6bb733d | 264 | SESE_LOOPS (region) = BITMAP_ALLOC (NULL); |
f1f41a6c | 265 | SESE_LOOP_NEST (region).create (3); |
f1f41a6c | 266 | SESE_PARAMS (region).create (3); |
fa4dba85 | 267 | region->parameter_rename_map = new parameter_rename_map_t; |
c6bb733d | 268 | |
269 | return region; | |
270 | } | |
271 | ||
272 | /* Deletes REGION. */ | |
273 | ||
274 | void | |
f032380c | 275 | free_sese_info (sese_info_p region) |
c6bb733d | 276 | { |
277 | if (SESE_LOOPS (region)) | |
278 | SESE_LOOPS (region) = BITMAP_ALLOC (NULL); | |
279 | ||
f1f41a6c | 280 | SESE_PARAMS (region).release (); |
281 | SESE_LOOP_NEST (region).release (); | |
fa4dba85 | 282 | delete region->parameter_rename_map; |
283 | region->parameter_rename_map = NULL; | |
c6bb733d | 284 | |
c6bb733d | 285 | XDELETE (region); |
286 | } | |
287 | ||
288 | /* Add exit phis for USE on EXIT. */ | |
289 | ||
290 | static void | |
291 | sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e) | |
292 | { | |
1a91d914 | 293 | gphi *phi = create_phi_node (NULL_TREE, exit); |
9c06f260 | 294 | create_new_def_for (use, phi, gimple_phi_result_ptr (phi)); |
60d535d2 | 295 | add_phi_arg (phi, use, false_e, UNKNOWN_LOCATION); |
296 | add_phi_arg (phi, use, true_e, UNKNOWN_LOCATION); | |
fa4dba85 | 297 | update_stmt (phi); |
c6bb733d | 298 | } |
299 | ||
300 | /* Insert in the block BB phi nodes for variables defined in REGION | |
301 | and used outside the REGION. The code generation moves REGION in | |
302 | the else clause of an "if (1)" and generates code in the then | |
303 | clause that is at this point empty: | |
304 | ||
305 | | if (1) | |
306 | | empty; | |
307 | | else | |
308 | | REGION; | |
309 | */ | |
310 | ||
311 | void | |
f032380c | 312 | sese_insert_phis_for_liveouts (sese_info_p region, basic_block bb, |
c6bb733d | 313 | edge false_e, edge true_e) |
314 | { | |
315 | unsigned i; | |
316 | bitmap_iterator bi; | |
317 | bitmap liveouts = BITMAP_ALLOC (NULL); | |
318 | ||
319 | update_ssa (TODO_update_ssa); | |
320 | ||
321 | sese_build_liveouts (region, liveouts); | |
322 | EXECUTE_IF_SET_IN_BITMAP (liveouts, 0, i, bi) | |
323 | sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e); | |
324 | BITMAP_FREE (liveouts); | |
325 | ||
326 | update_ssa (TODO_update_ssa); | |
327 | } | |
328 | ||
4ed27c8e | 329 | /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */ |
330 | ||
331 | edge | |
332 | get_true_edge_from_guard_bb (basic_block bb) | |
333 | { | |
334 | edge e; | |
335 | edge_iterator ei; | |
336 | ||
337 | FOR_EACH_EDGE (e, ei, bb->succs) | |
338 | if (e->flags & EDGE_TRUE_VALUE) | |
339 | return e; | |
340 | ||
341 | gcc_unreachable (); | |
342 | return NULL; | |
343 | } | |
344 | ||
345 | /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */ | |
346 | ||
347 | edge | |
348 | get_false_edge_from_guard_bb (basic_block bb) | |
349 | { | |
350 | edge e; | |
351 | edge_iterator ei; | |
352 | ||
353 | FOR_EACH_EDGE (e, ei, bb->succs) | |
354 | if (!(e->flags & EDGE_TRUE_VALUE)) | |
355 | return e; | |
356 | ||
357 | gcc_unreachable (); | |
358 | return NULL; | |
359 | } | |
360 | ||
97142493 | 361 | /* Returns the expression associated to OLD_NAME in RENAME_MAP. */ |
c6bb733d | 362 | |
363 | static tree | |
c1f445d2 | 364 | get_rename (rename_map_type *rename_map, tree old_name) |
c6bb733d | 365 | { |
27f9c4ff | 366 | gcc_assert (TREE_CODE (old_name) == SSA_NAME); |
5358b152 | 367 | tree *expr = rename_map->get (old_name); |
368 | if (expr) | |
369 | return *expr; | |
c6bb733d | 370 | |
4ed27c8e | 371 | return NULL_TREE; |
c6bb733d | 372 | } |
373 | ||
97142493 | 374 | /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR). */ |
c6bb733d | 375 | |
4ed27c8e | 376 | static void |
f032380c | 377 | set_rename (rename_map_type *rename_map, tree old_name, tree expr, |
378 | sese_info_p region) | |
c6bb733d | 379 | { |
c6bb733d | 380 | if (old_name == expr) |
381 | return; | |
382 | ||
5358b152 | 383 | rename_map->put (old_name, expr); |
fa4dba85 | 384 | |
385 | tree t; | |
386 | int i; | |
387 | /* For a parameter of a scop we dont want to rename it. */ | |
388 | FOR_EACH_VEC_ELT (SESE_PARAMS (region), i, t) | |
389 | if (old_name == t) | |
390 | region->parameter_rename_map->put(old_name, expr); | |
c6bb733d | 391 | } |
392 | ||
4ed27c8e | 393 | /* Renames the scalar uses of the statement COPY, using the |
394 | substitution map RENAME_MAP, inserting the gimplification code at | |
395 | GSI_TGT, for the translation REGION, with the original copied | |
396 | statement in LOOP, and using the induction variable renaming map | |
1034b719 | 397 | IV_MAP. Returns true when something has been renamed. GLOOG_ERROR |
398 | is set when the code generation cannot continue. */ | |
c6bb733d | 399 | |
40463847 | 400 | static bool |
42acab1c | 401 | rename_uses (gimple *copy, rename_map_type *rename_map, |
d9dd21a8 | 402 | gimple_stmt_iterator *gsi_tgt, |
f032380c | 403 | sese_info_p region, loop_p loop, vec<tree> iv_map, |
1034b719 | 404 | bool *gloog_error) |
c6bb733d | 405 | { |
c6bb733d | 406 | use_operand_p use_p; |
4ed27c8e | 407 | ssa_op_iter op_iter; |
40463847 | 408 | bool changed = false; |
c6bb733d | 409 | |
bac2de0b | 410 | if (is_gimple_debug (copy)) |
411 | { | |
412 | if (gimple_debug_bind_p (copy)) | |
413 | gimple_debug_bind_reset_value (copy); | |
841424cc | 414 | else if (gimple_debug_source_bind_p (copy)) |
415 | return false; | |
bac2de0b | 416 | else |
417 | gcc_unreachable (); | |
418 | ||
40463847 | 419 | return false; |
bac2de0b | 420 | } |
421 | ||
7c782c9b | 422 | FOR_EACH_SSA_USE_OPERAND (use_p, copy, op_iter, SSA_OP_USE) |
c6bb733d | 423 | { |
4ed27c8e | 424 | tree old_name = USE_FROM_PTR (use_p); |
425 | tree new_expr, scev; | |
c6bb733d | 426 | gimple_seq stmts; |
427 | ||
4ed27c8e | 428 | if (TREE_CODE (old_name) != SSA_NAME |
4ed27c8e | 429 | || SSA_NAME_IS_DEFAULT_DEF (old_name)) |
c6bb733d | 430 | continue; |
431 | ||
40463847 | 432 | changed = true; |
4ed27c8e | 433 | new_expr = get_rename (rename_map, old_name); |
434 | if (new_expr) | |
c6bb733d | 435 | { |
4ed27c8e | 436 | tree type_old_name = TREE_TYPE (old_name); |
437 | tree type_new_expr = TREE_TYPE (new_expr); | |
3f6c0a40 | 438 | |
4ed27c8e | 439 | if (type_old_name != type_new_expr |
7c782c9b | 440 | || TREE_CODE (new_expr) != SSA_NAME) |
3f6c0a40 | 441 | { |
bac2de0b | 442 | tree var = create_tmp_var (type_old_name, "var"); |
3f6c0a40 | 443 | |
d3a27ad5 | 444 | if (!useless_type_conversion_p (type_old_name, type_new_expr)) |
4ed27c8e | 445 | new_expr = fold_convert (type_old_name, new_expr); |
3f6c0a40 | 446 | |
d3a27ad5 | 447 | new_expr = force_gimple_operand (new_expr, &stmts, true, var); |
4ed27c8e | 448 | gsi_insert_seq_before (gsi_tgt, stmts, GSI_SAME_STMT); |
449 | } | |
c6bb733d | 450 | |
4ed27c8e | 451 | replace_exp (use_p, new_expr); |
452 | continue; | |
c6bb733d | 453 | } |
454 | ||
f032380c | 455 | scev = scalar_evolution_in_region (region->region, loop, old_name); |
c6bb733d | 456 | |
4ed27c8e | 457 | /* At this point we should know the exact scev for each |
458 | scalar SSA_NAME used in the scop: all the other scalar | |
459 | SSA_NAMEs should have been translated out of SSA using | |
460 | arrays with one element. */ | |
1034b719 | 461 | if (chrec_contains_undetermined (scev)) |
462 | { | |
463 | *gloog_error = true; | |
2a483856 | 464 | new_expr = build_zero_cst (TREE_TYPE (old_name)); |
1034b719 | 465 | } |
2a483856 | 466 | else |
467 | new_expr = chrec_apply_map (scev, iv_map); | |
c6bb733d | 468 | |
4ed27c8e | 469 | /* The apply should produce an expression tree containing |
470 | the uses of the new induction variables. We should be | |
471 | able to use new_expr instead of the old_name in the newly | |
472 | generated loop nest. */ | |
1034b719 | 473 | if (chrec_contains_undetermined (new_expr) |
474 | || tree_contains_chrecs (new_expr, NULL)) | |
475 | { | |
476 | *gloog_error = true; | |
2a483856 | 477 | new_expr = build_zero_cst (TREE_TYPE (old_name)); |
1034b719 | 478 | } |
2a483856 | 479 | else |
480 | /* Replace the old_name with the new_expr. */ | |
481 | new_expr = force_gimple_operand (unshare_expr (new_expr), &stmts, | |
482 | true, NULL_TREE); | |
48e1416a | 483 | |
4ed27c8e | 484 | gsi_insert_seq_before (gsi_tgt, stmts, GSI_SAME_STMT); |
485 | replace_exp (use_p, new_expr); | |
1f8cbcdd | 486 | |
40463847 | 487 | if (TREE_CODE (new_expr) == INTEGER_CST |
488 | && is_gimple_assign (copy)) | |
1f8cbcdd | 489 | { |
1f8cbcdd | 490 | tree rhs = gimple_assign_rhs1 (copy); |
491 | ||
1f8cbcdd | 492 | if (TREE_CODE (rhs) == ADDR_EXPR) |
493 | recompute_tree_invariant_for_addr_expr (rhs); | |
494 | } | |
495 | ||
fa4dba85 | 496 | set_rename (rename_map, old_name, new_expr, region); |
c6bb733d | 497 | } |
40463847 | 498 | |
499 | return changed; | |
c6bb733d | 500 | } |
501 | ||
4ed27c8e | 502 | /* Duplicates the statements of basic block BB into basic block NEW_BB |
1034b719 | 503 | and compute the new induction variables according to the IV_MAP. |
504 | GLOOG_ERROR is set when the code generation cannot continue. */ | |
c6bb733d | 505 | |
48e1416a | 506 | static void |
4ed27c8e | 507 | graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, |
c1f445d2 | 508 | rename_map_type *rename_map, |
f032380c | 509 | vec<tree> iv_map, sese_info_p region, |
1034b719 | 510 | bool *gloog_error) |
c6bb733d | 511 | { |
512 | gimple_stmt_iterator gsi, gsi_tgt; | |
4ed27c8e | 513 | loop_p loop = bb->loop_father; |
c6bb733d | 514 | |
515 | gsi_tgt = gsi_start_bb (new_bb); | |
516 | for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
517 | { | |
518 | def_operand_p def_p; | |
519 | ssa_op_iter op_iter; | |
42acab1c | 520 | gimple *stmt = gsi_stmt (gsi); |
521 | gimple *copy; | |
4ed27c8e | 522 | tree lhs; |
523 | ||
524 | /* Do not copy labels or conditions. */ | |
525 | if (gimple_code (stmt) == GIMPLE_LABEL | |
526 | || gimple_code (stmt) == GIMPLE_COND) | |
527 | continue; | |
c6bb733d | 528 | |
4ed27c8e | 529 | /* Do not copy induction variables. */ |
530 | if (is_gimple_assign (stmt) | |
531 | && (lhs = gimple_assign_lhs (stmt)) | |
532 | && TREE_CODE (lhs) == SSA_NAME | |
533 | && is_gimple_reg (lhs) | |
f032380c | 534 | && scev_analyzable_p (lhs, region->region)) |
c6bb733d | 535 | continue; |
536 | ||
fa4dba85 | 537 | /* Do not copy parameters that have been generated in the header of the |
538 | scop. */ | |
539 | if (is_gimple_assign (stmt) | |
540 | && (lhs = gimple_assign_lhs (stmt)) | |
541 | && TREE_CODE (lhs) == SSA_NAME | |
542 | && region->parameter_rename_map->get(lhs)) | |
543 | continue; | |
544 | ||
c6bb733d | 545 | /* Create a new copy of STMT and duplicate STMT's virtual |
546 | operands. */ | |
547 | copy = gimple_copy (stmt); | |
548 | gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT); | |
c6bb733d | 549 | |
e38def9c | 550 | maybe_duplicate_eh_stmt (copy, stmt); |
c6bb733d | 551 | gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt); |
552 | ||
553 | /* Create new names for all the definitions created by COPY and | |
554 | add replacement mappings for each new name. */ | |
555 | FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS) | |
4ed27c8e | 556 | { |
557 | tree old_name = DEF_FROM_PTR (def_p); | |
558 | tree new_name = create_new_def_for (old_name, copy, def_p); | |
fa4dba85 | 559 | set_rename (rename_map, old_name, new_name, region); |
4ed27c8e | 560 | } |
561 | ||
1034b719 | 562 | if (rename_uses (copy, rename_map, &gsi_tgt, region, loop, iv_map, |
563 | gloog_error)) | |
50aacf4c | 564 | { |
565 | gcc_assert (gsi_stmt (gsi_tgt) == copy); | |
566 | fold_stmt_inplace (&gsi_tgt); | |
567 | } | |
4ed27c8e | 568 | |
fa4dba85 | 569 | /* For each SSA_NAME in the parameter_rename_map rename their usage. */ |
570 | ssa_op_iter iter; | |
571 | use_operand_p use_p; | |
572 | if (!is_gimple_debug (copy)) | |
573 | FOR_EACH_SSA_USE_OPERAND (use_p, copy, iter, SSA_OP_USE) | |
574 | { | |
575 | tree old_name = USE_FROM_PTR (use_p); | |
576 | ||
577 | if (TREE_CODE (old_name) != SSA_NAME | |
578 | || SSA_NAME_IS_DEFAULT_DEF (old_name)) | |
579 | continue; | |
580 | ||
581 | tree *new_expr = region->parameter_rename_map->get (old_name); | |
582 | if (!new_expr) | |
583 | continue; | |
584 | ||
585 | replace_exp (use_p, *new_expr); | |
586 | } | |
587 | ||
4ed27c8e | 588 | update_stmt (copy); |
c6bb733d | 589 | } |
590 | } | |
591 | ||
592 | /* Copies BB and includes in the copied BB all the statements that can | |
593 | be reached following the use-def chains from the memory accesses, | |
1034b719 | 594 | and returns the next edge following this new block. GLOOG_ERROR is |
595 | set when the code generation cannot continue. */ | |
48e1416a | 596 | |
c6bb733d | 597 | edge |
f032380c | 598 | copy_bb_and_scalar_dependences (basic_block bb, sese_info_p region, |
f1f41a6c | 599 | edge next_e, vec<tree> iv_map, |
1034b719 | 600 | bool *gloog_error) |
c6bb733d | 601 | { |
602 | basic_block new_bb = split_edge (next_e); | |
c1f445d2 | 603 | rename_map_type rename_map (10); |
c6bb733d | 604 | |
605 | next_e = single_succ_edge (new_bb); | |
c1f445d2 | 606 | graphite_copy_stmts_from_block (bb, new_bb, &rename_map, iv_map, region, |
1034b719 | 607 | gloog_error); |
c6bb733d | 608 | remove_phi_nodes (new_bb); |
c6bb733d | 609 | |
610 | return next_e; | |
611 | } | |
612 | ||
613 | /* Returns the outermost loop in SCOP that contains BB. */ | |
614 | ||
615 | struct loop * | |
f032380c | 616 | outermost_loop_in_sese_1 (sese_l ®ion, basic_block bb) |
c6bb733d | 617 | { |
618 | struct loop *nest; | |
619 | ||
620 | nest = bb->loop_father; | |
621 | while (loop_outer (nest) | |
622 | && loop_in_sese_p (loop_outer (nest), region)) | |
623 | nest = loop_outer (nest); | |
624 | ||
625 | return nest; | |
626 | } | |
627 | ||
443b5bd0 | 628 | /* Same as outermost_loop_in_sese_1, returns the outermost loop |
629 | containing BB in REGION, but makes sure that the returned loop | |
630 | belongs to the REGION, and so this returns the first loop in the | |
631 | REGION when the loop containing BB does not belong to REGION. */ | |
632 | ||
633 | loop_p | |
f032380c | 634 | outermost_loop_in_sese (sese_l ®ion, basic_block bb) |
443b5bd0 | 635 | { |
636 | loop_p nest = outermost_loop_in_sese_1 (region, bb); | |
637 | ||
638 | if (loop_in_sese_p (nest, region)) | |
639 | return nest; | |
640 | ||
641 | /* When the basic block BB does not belong to a loop in the region, | |
642 | return the first loop in the region. */ | |
643 | nest = nest->inner; | |
644 | while (nest) | |
645 | if (loop_in_sese_p (nest, region)) | |
646 | break; | |
647 | else | |
648 | nest = nest->next; | |
649 | ||
650 | gcc_assert (nest); | |
651 | return nest; | |
652 | } | |
653 | ||
c6bb733d | 654 | /* Sets the false region of an IF_REGION to REGION. */ |
655 | ||
656 | void | |
f032380c | 657 | if_region_set_false_region (ifsese if_region, sese_info_p region) |
c6bb733d | 658 | { |
659 | basic_block condition = if_region_get_condition_block (if_region); | |
660 | edge false_edge = get_false_edge_from_guard_bb (condition); | |
661 | basic_block dummy = false_edge->dest; | |
f032380c | 662 | edge entry_region = region->region.entry; |
663 | edge exit_region = region->region.exit; | |
c6bb733d | 664 | basic_block before_region = entry_region->src; |
665 | basic_block last_in_region = exit_region->src; | |
2ef51f0e | 666 | hashval_t hash = htab_hash_pointer (exit_region); |
667 | loop_exit **slot | |
668 | = current_loops->exits->find_slot_with_hash (exit_region, hash, NO_INSERT); | |
c6bb733d | 669 | |
670 | entry_region->flags = false_edge->flags; | |
671 | false_edge->flags = exit_region->flags; | |
672 | ||
673 | redirect_edge_pred (entry_region, condition); | |
674 | redirect_edge_pred (exit_region, before_region); | |
675 | redirect_edge_pred (false_edge, last_in_region); | |
676 | redirect_edge_succ (false_edge, single_succ (dummy)); | |
677 | delete_basic_block (dummy); | |
678 | ||
679 | exit_region->flags = EDGE_FALLTHRU; | |
680 | recompute_all_dominators (); | |
681 | ||
f032380c | 682 | region->region.exit = false_edge; |
d996851c | 683 | |
dd045aee | 684 | free (if_region->false_region); |
c6bb733d | 685 | if_region->false_region = region; |
686 | ||
687 | if (slot) | |
688 | { | |
25a27413 | 689 | struct loop_exit *loop_exit = ggc_cleared_alloc<struct loop_exit> (); |
c6bb733d | 690 | |
691 | memcpy (loop_exit, *((struct loop_exit **) slot), sizeof (struct loop_exit)); | |
2ef51f0e | 692 | current_loops->exits->clear_slot (slot); |
c6bb733d | 693 | |
e0c0be18 | 694 | hashval_t hash = htab_hash_pointer (false_edge); |
2ef51f0e | 695 | slot = current_loops->exits->find_slot_with_hash (false_edge, hash, |
696 | INSERT); | |
c6bb733d | 697 | loop_exit->e = false_edge; |
698 | *slot = loop_exit; | |
699 | false_edge->src->loop_father->exits->next = loop_exit; | |
700 | } | |
701 | } | |
702 | ||
703 | /* Creates an IFSESE with CONDITION on edge ENTRY. */ | |
704 | ||
2bf96dd7 | 705 | static ifsese |
c6bb733d | 706 | create_if_region_on_edge (edge entry, tree condition) |
707 | { | |
708 | edge e; | |
709 | edge_iterator ei; | |
f032380c | 710 | sese_info_p sese_region = XNEW (struct sese_info_t); |
711 | sese_info_p true_region = XNEW (struct sese_info_t); | |
712 | sese_info_p false_region = XNEW (struct sese_info_t); | |
d996851c | 713 | ifsese if_region = XNEW (struct ifsese_s); |
c6bb733d | 714 | edge exit = create_empty_if_region_on_edge (entry, condition); |
715 | ||
716 | if_region->region = sese_region; | |
f032380c | 717 | if_region->region->region.entry = entry; |
718 | if_region->region->region.exit = exit; | |
c6bb733d | 719 | |
720 | FOR_EACH_EDGE (e, ei, entry->dest->succs) | |
721 | { | |
722 | if (e->flags & EDGE_TRUE_VALUE) | |
723 | { | |
f032380c | 724 | true_region->region.entry = e; |
725 | true_region->region.exit = single_succ_edge (e->dest); | |
c6bb733d | 726 | if_region->true_region = true_region; |
727 | } | |
728 | else if (e->flags & EDGE_FALSE_VALUE) | |
729 | { | |
f032380c | 730 | false_region->region.entry = e; |
731 | false_region->region.exit = single_succ_edge (e->dest); | |
c6bb733d | 732 | if_region->false_region = false_region; |
733 | } | |
734 | } | |
735 | ||
736 | return if_region; | |
737 | } | |
738 | ||
739 | /* Moves REGION in a condition expression: | |
740 | | if (1) | |
741 | | ; | |
742 | | else | |
743 | | REGION; | |
744 | */ | |
745 | ||
746 | ifsese | |
f032380c | 747 | move_sese_in_condition (sese_info_p region) |
c6bb733d | 748 | { |
f032380c | 749 | basic_block pred_block = split_edge (region->region.entry); |
d996851c | 750 | ifsese if_region; |
c6bb733d | 751 | |
f032380c | 752 | region->region.entry = single_succ_edge (pred_block); |
e0c0be18 | 753 | if_region = create_if_region_on_edge (single_pred_edge (pred_block), |
754 | integer_one_node); | |
c6bb733d | 755 | if_region_set_false_region (if_region, region); |
756 | ||
757 | return if_region; | |
758 | } | |
759 | ||
2487de19 | 760 | /* Replaces the condition of the IF_REGION with CONDITION: |
761 | | if (CONDITION) | |
762 | | true_region; | |
763 | | else | |
764 | | false_region; | |
765 | */ | |
766 | ||
767 | void | |
768 | set_ifsese_condition (ifsese if_region, tree condition) | |
769 | { | |
f032380c | 770 | sese_info_p region = if_region->region; |
771 | edge entry = region->region.entry; | |
2487de19 | 772 | basic_block bb = entry->dest; |
42acab1c | 773 | gimple *last = last_stmt (bb); |
2487de19 | 774 | gimple_stmt_iterator gsi = gsi_last_bb (bb); |
1a91d914 | 775 | gcond *cond_stmt; |
2487de19 | 776 | |
777 | gcc_assert (gimple_code (last) == GIMPLE_COND); | |
778 | ||
779 | gsi_remove (&gsi, true); | |
780 | gsi = gsi_last_bb (bb); | |
781 | condition = force_gimple_operand_gsi (&gsi, condition, true, NULL, | |
782 | false, GSI_NEW_STMT); | |
783 | cond_stmt = gimple_build_cond_from_tree (condition, NULL_TREE, NULL_TREE); | |
784 | gsi = gsi_last_bb (bb); | |
785 | gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT); | |
786 | } | |
787 | ||
9c0cc377 | 788 | /* Return true when T is defined outside REGION or when no definitions are |
789 | variant in REGION. */ | |
fa4dba85 | 790 | |
9c0cc377 | 791 | bool |
f032380c | 792 | invariant_in_sese_p_rec (tree t, sese_l ®ion) |
fa4dba85 | 793 | { |
794 | ssa_op_iter iter; | |
795 | use_operand_p use_p; | |
796 | if (!defined_in_sese_p (t, region)) | |
797 | return true; | |
798 | ||
42acab1c | 799 | gimple *stmt = SSA_NAME_DEF_STMT (t); |
fa4dba85 | 800 | |
801 | if (gimple_code (stmt) == GIMPLE_PHI | |
802 | || gimple_code (stmt) == GIMPLE_CALL) | |
803 | return false; | |
804 | ||
9c0cc377 | 805 | /* VDEF is variant when it is in the region. */ |
ec6135ce | 806 | if (gimple_vdef (stmt)) |
9c0cc377 | 807 | return false; |
808 | ||
809 | /* A VUSE may or may not be variant following the VDEFs. */ | |
810 | if (tree vuse = gimple_vuse (stmt)) | |
811 | return invariant_in_sese_p_rec (vuse, region); | |
812 | ||
fa4dba85 | 813 | FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE) |
814 | { | |
815 | tree use = USE_FROM_PTR (use_p); | |
9c0cc377 | 816 | |
fa4dba85 | 817 | if (!defined_in_sese_p (use, region)) |
818 | continue; | |
819 | ||
820 | if (!invariant_in_sese_p_rec (use, region)) | |
821 | return false; | |
822 | } | |
823 | ||
824 | return true; | |
825 | } | |
826 | ||
c6bb733d | 827 | /* Returns the scalar evolution of T in REGION. Every variable that |
828 | is not defined in the REGION is considered a parameter. */ | |
829 | ||
830 | tree | |
f032380c | 831 | scalar_evolution_in_region (sese_l ®ion, loop_p loop, tree t) |
c6bb733d | 832 | { |
42acab1c | 833 | gimple *def; |
c6bb733d | 834 | struct loop *def_loop; |
f032380c | 835 | basic_block before = region.entry->src; |
c6bb733d | 836 | |
ae6346fd | 837 | /* SCOP parameters. */ |
838 | if (TREE_CODE (t) == SSA_NAME | |
839 | && !defined_in_sese_p (t, region)) | |
840 | return t; | |
841 | ||
c6bb733d | 842 | if (TREE_CODE (t) != SSA_NAME |
843 | || loop_in_sese_p (loop, region)) | |
844 | return instantiate_scev (before, loop, | |
845 | analyze_scalar_evolution (loop, t)); | |
846 | ||
c6bb733d | 847 | def = SSA_NAME_DEF_STMT (t); |
848 | def_loop = loop_containing_stmt (def); | |
849 | ||
850 | if (loop_in_sese_p (def_loop, region)) | |
851 | { | |
852 | t = analyze_scalar_evolution (def_loop, t); | |
853 | def_loop = superloop_at_depth (def_loop, loop_depth (loop) + 1); | |
854 | t = compute_overall_effect_of_inner_loop (def_loop, t); | |
855 | return t; | |
856 | } | |
fa4dba85 | 857 | |
858 | if (invariant_in_sese_p_rec (t, region)) | |
859 | return t; | |
860 | ||
861 | return instantiate_scev (before, loop, t); | |
c6bb733d | 862 | } |