Mercurial > hg > CbC > CbC_gcc

comparison gcc/sese.c @ 111:04ced10e8804

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
gcc 7
author kono
date Fri, 27 Oct 2017 22:46:09 +0900
parents f6334be47118
children 84e7813d76e9
comparison
equal deleted inserted replaced
68:561a7518be6b 111:04ced10e8804
1 /* Single entry single exit control flow regions. 1 /* Single entry single exit control flow regions.
2 Copyright (C) 2008, 2009, 2010 2 Copyright (C) 2008-2017 Free Software Foundation, Inc.
3 Free Software Foundation, Inc.
4 Contributed by Jan Sjodin <jan.sjodin@amd.com> and 3 Contributed by Jan Sjodin <jan.sjodin@amd.com> and
5 Sebastian Pop <sebastian.pop@amd.com>. 4 Sebastian Pop <sebastian.pop@amd.com>.
6 5
7 This file is part of GCC. 6 This file is part of GCC.
8 7
21 <http://www.gnu.org/licenses/>. */ 20 <http://www.gnu.org/licenses/>. */
22 21
23 #include "config.h" 22 #include "config.h"
24 #include "system.h" 23 #include "system.h"
25 #include "coretypes.h" 24 #include "coretypes.h"
25 #include "backend.h"
26 #include "tree.h"
27 #include "gimple.h"
28 #include "cfghooks.h"
29 #include "tree-pass.h"
30 #include "ssa.h"
26 #include "tree-pretty-print.h" 31 #include "tree-pretty-print.h"
27 #include "tree-flow.h" 32 #include "fold-const.h"
33 #include "gimplify.h"
34 #include "gimple-iterator.h"
35 #include "gimple-pretty-print.h"
36 #include "gimplify-me.h"
37 #include "tree-cfg.h"
38 #include "tree-ssa-loop.h"
39 #include "tree-into-ssa.h"
28 #include "cfgloop.h" 40 #include "cfgloop.h"
29 #include "tree-chrec.h"
30 #include "tree-data-ref.h" 41 #include "tree-data-ref.h"
31 #include "tree-scalar-evolution.h" 42 #include "tree-scalar-evolution.h"
32 #include "tree-pass.h" 43 #include "tree-ssa-propagate.h"
33 #include "value-prof.h" 44 #include "cfganal.h"
34 #include "sese.h" 45 #include "sese.h"
35 46
36 /* Print to stderr the element ELT. */ 47 /* For a USE in BB, if BB is outside REGION, mark the USE in the
48 LIVEOUTS set. */
37 49
38 static void 50 static void
39 debug_rename_elt (rename_map_elt elt) 51 sese_build_liveouts_use (sese_info_p region, bitmap liveouts, basic_block bb,
40 { 52 tree use)
41 fprintf (stderr, "("); 53 {
42 print_generic_expr (stderr, elt->old_name, 0); 54 gcc_assert (!bb_in_sese_p (bb, region->region));
43 fprintf (stderr, ", "); 55 if (TREE_CODE (use) != SSA_NAME)
44 print_generic_expr (stderr, elt->expr, 0); 56 return;
45 fprintf (stderr, ")\n"); 57
46 } 58 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
47 59
48 /* Helper function for debug_rename_map. */ 60 if (!def_bb || !bb_in_sese_p (def_bb, region->region))
49 61 return;
50 static int 62
51 debug_rename_map_1 (void **slot, void *s ATTRIBUTE_UNUSED) 63 unsigned ver = SSA_NAME_VERSION (use);
52 { 64 bitmap_set_bit (liveouts, ver);
53 struct rename_map_elt_s *entry = (struct rename_map_elt_s *) *slot; 65 }
54 debug_rename_elt (entry); 66
55 return 1; 67 /* Marks for rewrite all the SSA_NAMES defined in REGION and that are
56 } 68 used in BB that is outside of the REGION. */
57
58 /* Print to stderr all the elements of RENAME_MAP. */
59
60 DEBUG_FUNCTION void
61 debug_rename_map (htab_t rename_map)
62 {
63 htab_traverse (rename_map, debug_rename_map_1, NULL);
64 }
65
66 /* Computes a hash function for database element ELT. */
67
68 hashval_t
69 rename_map_elt_info (const void *elt)
70 {
71 return SSA_NAME_VERSION (((const struct rename_map_elt_s *) elt)->old_name);
72 }
73
74 /* Compares database elements E1 and E2. */
75
76 int
77 eq_rename_map_elts (const void *e1, const void *e2)
78 {
79 const struct rename_map_elt_s *elt1 = (const struct rename_map_elt_s *) e1;
80 const struct rename_map_elt_s *elt2 = (const struct rename_map_elt_s *) e2;
81
82 return (elt1->old_name == elt2->old_name);
83 }
84
85
86
87 /* Print to stderr the element ELT. */
88 69
89 static void 70 static void
90 debug_ivtype_elt (ivtype_map_elt elt) 71 sese_build_liveouts_bb (sese_info_p region, basic_block bb)
91 { 72 {
92 fprintf (stderr, "(%s, ", elt->cloog_iv); 73 ssa_op_iter iter;
93 print_generic_expr (stderr, elt->type, 0); 74 use_operand_p use_p;
94 fprintf (stderr, ")\n"); 75
95 } 76 for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);
96 77 gsi_next (&bsi))
97 /* Helper function for debug_ivtype_map. */ 78 FOR_EACH_PHI_ARG (use_p, bsi.phi (), iter, SSA_OP_USE)
98 79 sese_build_liveouts_use (region, region->liveout,
99 static int 80 bb, USE_FROM_PTR (use_p));
100 debug_ivtype_map_1 (void **slot, void *s ATTRIBUTE_UNUSED) 81
101 { 82 for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);
102 struct ivtype_map_elt_s *entry = (struct ivtype_map_elt_s *) *slot; 83 gsi_next (&bsi))
103 debug_ivtype_elt (entry); 84 {
104 return 1; 85 gimple *stmt = gsi_stmt (bsi);
105 } 86
106 87 bitmap liveouts = region->liveout;
107 /* Print to stderr all the elements of MAP. */ 88 if (is_gimple_debug (stmt))
108 89 liveouts = region->debug_liveout;
109 DEBUG_FUNCTION void 90
110 debug_ivtype_map (htab_t map) 91 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
111 { 92 sese_build_liveouts_use (region, liveouts, bb, USE_FROM_PTR (use_p));
112 htab_traverse (map, debug_ivtype_map_1, NULL); 93 }
113 } 94 }
114 95
115 /* Computes a hash function for database element ELT. */ 96 /* Reset debug stmts that reference SSA_NAMES defined in REGION that
116 97 are not marked as liveouts. */
117 hashval_t
118 ivtype_map_elt_info (const void *elt)
119 {
120 return htab_hash_pointer (((const struct ivtype_map_elt_s *) elt)->cloog_iv);
121 }
122
123 /* Compares database elements E1 and E2. */
124
125 int
126 eq_ivtype_map_elts (const void *e1, const void *e2)
127 {
128 const struct ivtype_map_elt_s *elt1 = (const struct ivtype_map_elt_s *) e1;
129 const struct ivtype_map_elt_s *elt2 = (const struct ivtype_map_elt_s *) e2;
130
131 return (elt1->cloog_iv == elt2->cloog_iv);
132 }
133
134
135
136 /* Record LOOP as occuring in REGION. */
137 98
138 static void 99 static void
139 sese_record_loop (sese region, loop_p loop) 100 sese_reset_debug_liveouts (sese_info_p region)
140 { 101 {
141 if (sese_contains_loop (region, loop)) 102 bitmap_iterator bi;
142 return;
143
144 bitmap_set_bit (SESE_LOOPS (region), loop->num);
145 VEC_safe_push (loop_p, heap, SESE_LOOP_NEST (region), loop);
146 }
147
148 /* Build the loop nests contained in REGION. Returns true when the
149 operation was successful. */
150
151 void
152 build_sese_loop_nests (sese region)
153 {
154 unsigned i; 103 unsigned i;
155 basic_block bb; 104 EXECUTE_IF_AND_COMPL_IN_BITMAP (region->debug_liveout, region->liveout,
156 struct loop *loop0, *loop1; 105 0, i, bi)
157
158 FOR_EACH_BB (bb)
159 if (bb_in_sese_p (bb, region))
160 {
161 struct loop *loop = bb->loop_father;
162
163 /* Only add loops if they are completely contained in the SCoP. */
164 if (loop->header == bb
165 && bb_in_sese_p (loop->latch, region))
166 sese_record_loop (region, loop);
167 }
168
169 /* Make sure that the loops in the SESE_LOOP_NEST are ordered. It
170 can be the case that an inner loop is inserted before an outer
171 loop. To avoid this, semi-sort once. */
172 FOR_EACH_VEC_ELT (loop_p, SESE_LOOP_NEST (region), i, loop0)
173 { 106 {
174 if (VEC_length (loop_p, SESE_LOOP_NEST (region)) == i + 1) 107 tree name = ssa_name (i);
175 break; 108 auto_vec<gimple *, 4> stmts;
176 109 gimple *use_stmt;
177 loop1 = VEC_index (loop_p, SESE_LOOP_NEST (region), i + 1); 110 imm_use_iterator use_iter;
178 if (loop0->num > loop1->num) 111 FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, name)
179 { 112 {
180 VEC_replace (loop_p, SESE_LOOP_NEST (region), i, loop1); 113 if (! is_gimple_debug (use_stmt)
181 VEC_replace (loop_p, SESE_LOOP_NEST (region), i + 1, loop0); 114 || bb_in_sese_p (gimple_bb (use_stmt), region->region))
115 continue;
116 stmts.safe_push (use_stmt);
117 }
118 while (!stmts.is_empty ())
119 {
120 gimple *stmt = stmts.pop ();
121 gimple_debug_bind_reset_value (stmt);
122 update_stmt (stmt);
182 } 123 }
183 } 124 }
184 } 125 }
185 126
186 /* For a USE in BB, if BB is outside REGION, mark the USE in the
187 LIVEOUTS set. */
188
189 static void
190 sese_build_liveouts_use (sese region, bitmap liveouts, basic_block bb,
191 tree use)
192 {
193 unsigned ver;
194 basic_block def_bb;
195
196 if (TREE_CODE (use) != SSA_NAME)
197 return;
198
199 ver = SSA_NAME_VERSION (use);
200 def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
201
202 if (!def_bb
203 || !bb_in_sese_p (def_bb, region)
204 || bb_in_sese_p (bb, region))
205 return;
206
207 bitmap_set_bit (liveouts, ver);
208 }
209
210 /* Marks for rewrite all the SSA_NAMES defined in REGION and that are
211 used in BB that is outside of the REGION. */
212
213 static void
214 sese_build_liveouts_bb (sese region, bitmap liveouts, basic_block bb)
215 {
216 gimple_stmt_iterator bsi;
217 edge e;
218 edge_iterator ei;
219 ssa_op_iter iter;
220 use_operand_p use_p;
221
222 FOR_EACH_EDGE (e, ei, bb->succs)
223 for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi))
224 sese_build_liveouts_use (region, liveouts, bb,
225 PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi), e));
226
227 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
228 {
229 gimple stmt = gsi_stmt (bsi);
230
231 if (is_gimple_debug (stmt))
232 continue;
233
234 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
235 sese_build_liveouts_use (region, liveouts, bb, USE_FROM_PTR (use_p));
236 }
237 }
238
239 /* For a USE in BB, return true if BB is outside REGION and it's not
240 in the LIVEOUTS set. */
241
242 static bool
243 sese_bad_liveouts_use (sese region, bitmap liveouts, basic_block bb,
244 tree use)
245 {
246 unsigned ver;
247 basic_block def_bb;
248
249 if (TREE_CODE (use) != SSA_NAME)
250 return false;
251
252 ver = SSA_NAME_VERSION (use);
253
254 /* If it's in liveouts, the variable will get a new PHI node, and
255 the debug use will be properly adjusted. */
256 if (bitmap_bit_p (liveouts, ver))
257 return false;
258
259 def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
260
261 if (!def_bb
262 || !bb_in_sese_p (def_bb, region)
263 || bb_in_sese_p (bb, region))
264 return false;
265
266 return true;
267 }
268
269 /* Reset debug stmts that reference SSA_NAMES defined in REGION that
270 are not marked as liveouts. */
271
272 static void
273 sese_reset_debug_liveouts_bb (sese region, bitmap liveouts, basic_block bb)
274 {
275 gimple_stmt_iterator bsi;
276 ssa_op_iter iter;
277 use_operand_p use_p;
278
279 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
280 {
281 gimple stmt = gsi_stmt (bsi);
282
283 if (!is_gimple_debug (stmt))
284 continue;
285
286 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
287 if (sese_bad_liveouts_use (region, liveouts, bb,
288 USE_FROM_PTR (use_p)))
289 {
290 gimple_debug_bind_reset_value (stmt);
291 update_stmt (stmt);
292 break;
293 }
294 }
295 }
296
297 /* Build the LIVEOUTS of REGION: the set of variables defined inside 127 /* Build the LIVEOUTS of REGION: the set of variables defined inside
298 and used outside the REGION. */ 128 and used outside the REGION. */
299 129
300 static void 130 void
301 sese_build_liveouts (sese region, bitmap liveouts) 131 sese_build_liveouts (sese_info_p region)
302 { 132 {
303 basic_block bb; 133 basic_block bb;
304 134
305 FOR_EACH_BB (bb) 135 gcc_assert (region->liveout == NULL
306 sese_build_liveouts_bb (region, liveouts, bb); 136 && region->debug_liveout == NULL);
307 if (MAY_HAVE_DEBUG_INSNS) 137
308 FOR_EACH_BB (bb) 138 region->liveout = BITMAP_ALLOC (NULL);
309 sese_reset_debug_liveouts_bb (region, liveouts, bb); 139 region->debug_liveout = BITMAP_ALLOC (NULL);
140
141 /* FIXME: We could start iterating form the successor of sese. */
142 FOR_EACH_BB_FN (bb, cfun)
143 if (!bb_in_sese_p (bb, region->region))
144 sese_build_liveouts_bb (region, bb);
310 } 145 }
311 146
312 /* Builds a new SESE region from edges ENTRY and EXIT. */ 147 /* Builds a new SESE region from edges ENTRY and EXIT. */
313 148
314 sese 149 sese_info_p
315 new_sese (edge entry, edge exit) 150 new_sese_info (edge entry, edge exit)
316 { 151 {
317 sese region = XNEW (struct sese_s); 152 sese_info_p region = XNEW (struct sese_info_t);
318 153
319 SESE_ENTRY (region) = entry; 154 region->region.entry = entry;
320 SESE_EXIT (region) = exit; 155 region->region.exit = exit;
321 SESE_LOOPS (region) = BITMAP_ALLOC (NULL); 156 region->liveout = NULL;
322 SESE_LOOP_NEST (region) = VEC_alloc (loop_p, heap, 3); 157 region->debug_liveout = NULL;
323 SESE_ADD_PARAMS (region) = true; 158 region->params.create (3);
324 SESE_PARAMS (region) = VEC_alloc (tree, heap, 3); 159 region->rename_map = new hash_map <tree, tree>;
160 region->bbs.create (3);
325 161
326 return region; 162 return region;
327 } 163 }
328 164
329 /* Deletes REGION. */ 165 /* Deletes REGION. */
330 166
331 void 167 void
332 free_sese (sese region) 168 free_sese_info (sese_info_p region)
333 { 169 {
334 if (SESE_LOOPS (region)) 170 region->params.release ();
335 SESE_LOOPS (region) = BITMAP_ALLOC (NULL); 171 BITMAP_FREE (region->liveout);
336 172 BITMAP_FREE (region->debug_liveout);
337 VEC_free (tree, heap, SESE_PARAMS (region)); 173
338 VEC_free (loop_p, heap, SESE_LOOP_NEST (region)); 174 delete region->rename_map;
175 region->rename_map = NULL;
176 region->bbs.release ();
339 177
340 XDELETE (region); 178 XDELETE (region);
341 } 179 }
342 180
343 /* Add exit phis for USE on EXIT. */ 181 /* Add exit phis for USE on EXIT. */
344 182
345 static void 183 static void
346 sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e) 184 sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e)
347 { 185 {
348 gimple phi = create_phi_node (use, exit); 186 gphi *phi = create_phi_node (NULL_TREE, exit);
349 187 create_new_def_for (use, phi, gimple_phi_result_ptr (phi));
350 create_new_def_for (gimple_phi_result (phi), phi,
351 gimple_phi_result_ptr (phi));
352 add_phi_arg (phi, use, false_e, UNKNOWN_LOCATION); 188 add_phi_arg (phi, use, false_e, UNKNOWN_LOCATION);
353 add_phi_arg (phi, use, true_e, UNKNOWN_LOCATION); 189 add_phi_arg (phi, use, true_e, UNKNOWN_LOCATION);
190 update_stmt (phi);
354 } 191 }
355 192
356 /* Insert in the block BB phi nodes for variables defined in REGION 193 /* Insert in the block BB phi nodes for variables defined in REGION
357 and used outside the REGION. The code generation moves REGION in 194 and used outside the REGION. The code generation moves REGION in
358 the else clause of an "if (1)" and generates code in the then 195 the else clause of an "if (1)" and generates code in the then
363 | else 200 | else
364 | REGION; 201 | REGION;
365 */ 202 */
366 203
367 void 204 void
368 sese_insert_phis_for_liveouts (sese region, basic_block bb, 205 sese_insert_phis_for_liveouts (sese_info_p region, basic_block bb,
369 edge false_e, edge true_e) 206 edge false_e, edge true_e)
370 { 207 {
208 if (MAY_HAVE_DEBUG_STMTS)
209 sese_reset_debug_liveouts (region);
210
371 unsigned i; 211 unsigned i;
372 bitmap_iterator bi; 212 bitmap_iterator bi;
373 bitmap liveouts = BITMAP_ALLOC (NULL); 213 EXECUTE_IF_SET_IN_BITMAP (region->liveout, 0, i, bi)
374 214 if (!virtual_operand_p (ssa_name (i)))
375 update_ssa (TODO_update_ssa); 215 sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e);
376
377 sese_build_liveouts (region, liveouts);
378 EXECUTE_IF_SET_IN_BITMAP (liveouts, 0, i, bi)
379 sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e);
380 BITMAP_FREE (liveouts);
381
382 update_ssa (TODO_update_ssa);
383 }
384
385 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */
386
387 edge
388 get_true_edge_from_guard_bb (basic_block bb)
389 {
390 edge e;
391 edge_iterator ei;
392
393 FOR_EACH_EDGE (e, ei, bb->succs)
394 if (e->flags & EDGE_TRUE_VALUE)
395 return e;
396
397 gcc_unreachable ();
398 return NULL;
399 }
400
401 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */
402
403 edge
404 get_false_edge_from_guard_bb (basic_block bb)
405 {
406 edge e;
407 edge_iterator ei;
408
409 FOR_EACH_EDGE (e, ei, bb->succs)
410 if (!(e->flags & EDGE_TRUE_VALUE))
411 return e;
412
413 gcc_unreachable ();
414 return NULL;
415 }
416
417 /* Returns the expression associated to OLD_NAME in RENAME_MAP. */
418
419 static tree
420 get_rename (htab_t rename_map, tree old_name)
421 {
422 struct rename_map_elt_s tmp;
423 PTR *slot;
424
425 gcc_assert (TREE_CODE (old_name) == SSA_NAME);
426 tmp.old_name = old_name;
427 slot = htab_find_slot (rename_map, &tmp, NO_INSERT);
428
429 if (slot && *slot)
430 return ((rename_map_elt) *slot)->expr;
431
432 return NULL_TREE;
433 }
434
435 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR). */
436
437 static void
438 set_rename (htab_t rename_map, tree old_name, tree expr)
439 {
440 struct rename_map_elt_s tmp;
441 PTR *slot;
442
443 if (old_name == expr)
444 return;
445
446 tmp.old_name = old_name;
447 slot = htab_find_slot (rename_map, &tmp, INSERT);
448
449 if (!slot)
450 return;
451
452 if (*slot)
453 free (*slot);
454
455 *slot = new_rename_map_elt (old_name, expr);
456 }
457
458 /* Renames the scalar uses of the statement COPY, using the
459 substitution map RENAME_MAP, inserting the gimplification code at
460 GSI_TGT, for the translation REGION, with the original copied
461 statement in LOOP, and using the induction variable renaming map
462 IV_MAP. Returns true when something has been renamed. */
463
464 static bool
465 rename_uses (gimple copy, htab_t rename_map, gimple_stmt_iterator *gsi_tgt,
466 sese region, loop_p loop, VEC (tree, heap) *iv_map)
467 {
468 use_operand_p use_p;
469 ssa_op_iter op_iter;
470 bool changed = false;
471
472 if (is_gimple_debug (copy))
473 {
474 if (gimple_debug_bind_p (copy))
475 gimple_debug_bind_reset_value (copy);
476 else
477 gcc_unreachable ();
478
479 return false;
480 }
481
482 FOR_EACH_SSA_USE_OPERAND (use_p, copy, op_iter, SSA_OP_ALL_USES)
483 {
484 tree old_name = USE_FROM_PTR (use_p);
485 tree new_expr, scev;
486 gimple_seq stmts;
487
488 if (TREE_CODE (old_name) != SSA_NAME
489 || !is_gimple_reg (old_name)
490 || SSA_NAME_IS_DEFAULT_DEF (old_name))
491 continue;
492
493 changed = true;
494 new_expr = get_rename (rename_map, old_name);
495 if (new_expr)
496 {
497 tree type_old_name = TREE_TYPE (old_name);
498 tree type_new_expr = TREE_TYPE (new_expr);
499
500 if (type_old_name != type_new_expr
501 || (TREE_CODE (new_expr) != SSA_NAME
502 && is_gimple_reg (old_name)))
503 {
504 tree var = create_tmp_var (type_old_name, "var");
505
506 if (type_old_name != type_new_expr)
507 new_expr = fold_convert (type_old_name, new_expr);
508
509 new_expr = build2 (MODIFY_EXPR, type_old_name, var, new_expr);
510 new_expr = force_gimple_operand (new_expr, &stmts, true, NULL);
511 gsi_insert_seq_before (gsi_tgt, stmts, GSI_SAME_STMT);
512 }
513
514 replace_exp (use_p, new_expr);
515 continue;
516 }
517
518 scev = scalar_evolution_in_region (region, loop, old_name);
519
520 /* At this point we should know the exact scev for each
521 scalar SSA_NAME used in the scop: all the other scalar
522 SSA_NAMEs should have been translated out of SSA using
523 arrays with one element. */
524 gcc_assert (!chrec_contains_undetermined (scev));
525
526 new_expr = chrec_apply_map (scev, iv_map);
527
528 /* The apply should produce an expression tree containing
529 the uses of the new induction variables. We should be
530 able to use new_expr instead of the old_name in the newly
531 generated loop nest. */
532 gcc_assert (!chrec_contains_undetermined (new_expr)
533 && !tree_contains_chrecs (new_expr, NULL));
534
535 /* Replace the old_name with the new_expr. */
536 new_expr = force_gimple_operand (unshare_expr (new_expr), &stmts,
537 true, NULL_TREE);
538 gsi_insert_seq_before (gsi_tgt, stmts, GSI_SAME_STMT);
539 replace_exp (use_p, new_expr);
540
541 if (TREE_CODE (new_expr) == INTEGER_CST
542 && is_gimple_assign (copy))
543 {
544 tree rhs = gimple_assign_rhs1 (copy);
545
546 if (TREE_CODE (rhs) == ADDR_EXPR)
547 recompute_tree_invariant_for_addr_expr (rhs);
548 }
549
550 set_rename (rename_map, old_name, new_expr);
551 }
552
553 return changed;
554 }
555
556 /* Duplicates the statements of basic block BB into basic block NEW_BB
557 and compute the new induction variables according to the IV_MAP. */
558
559 static void
560 graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb,
561 htab_t rename_map,
562 VEC (tree, heap) *iv_map, sese region)
563 {
564 gimple_stmt_iterator gsi, gsi_tgt;
565 loop_p loop = bb->loop_father;
566
567 gsi_tgt = gsi_start_bb (new_bb);
568 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
569 {
570 def_operand_p def_p;
571 ssa_op_iter op_iter;
572 gimple stmt = gsi_stmt (gsi);
573 gimple copy;
574 tree lhs;
575
576 /* Do not copy labels or conditions. */
577 if (gimple_code (stmt) == GIMPLE_LABEL
578 || gimple_code (stmt) == GIMPLE_COND)
579 continue;
580
581 /* Do not copy induction variables. */
582 if (is_gimple_assign (stmt)
583 && (lhs = gimple_assign_lhs (stmt))
584 && TREE_CODE (lhs) == SSA_NAME
585 && is_gimple_reg (lhs)
586 && scev_analyzable_p (lhs, region))
587 continue;
588
589 /* Create a new copy of STMT and duplicate STMT's virtual
590 operands. */
591 copy = gimple_copy (stmt);
592 gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
593 mark_sym_for_renaming (gimple_vop (cfun));
594
595 maybe_duplicate_eh_stmt (copy, stmt);
596 gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
597
598 /* Create new names for all the definitions created by COPY and
599 add replacement mappings for each new name. */
600 FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
601 {
602 tree old_name = DEF_FROM_PTR (def_p);
603 tree new_name = create_new_def_for (old_name, copy, def_p);
604 set_rename (rename_map, old_name, new_name);
605 }
606
607 if (rename_uses (copy, rename_map, &gsi_tgt, region, loop, iv_map))
608 fold_stmt_inplace (copy);
609
610 update_stmt (copy);
611 }
612 }
613
614 /* Copies BB and includes in the copied BB all the statements that can
615 be reached following the use-def chains from the memory accesses,
616 and returns the next edge following this new block. */
617
618 edge
619 copy_bb_and_scalar_dependences (basic_block bb, sese region,
620 edge next_e, VEC (tree, heap) *iv_map)
621 {
622 basic_block new_bb = split_edge (next_e);
623 htab_t rename_map = htab_create (10, rename_map_elt_info,
624 eq_rename_map_elts, free);
625
626 next_e = single_succ_edge (new_bb);
627 graphite_copy_stmts_from_block (bb, new_bb, rename_map, iv_map, region);
628 remove_phi_nodes (new_bb);
629 htab_delete (rename_map);
630
631 return next_e;
632 } 216 }
633 217
634 /* Returns the outermost loop in SCOP that contains BB. */ 218 /* Returns the outermost loop in SCOP that contains BB. */
635 219
636 struct loop * 220 struct loop *
637 outermost_loop_in_sese (sese region, basic_block bb) 221 outermost_loop_in_sese_1 (sese_l &region, basic_block bb)
638 { 222 {
639 struct loop *nest; 223 struct loop *nest;
640 224
641 nest = bb->loop_father; 225 nest = bb->loop_father;
642 while (loop_outer (nest) 226 while (loop_outer (nest)
644 nest = loop_outer (nest); 228 nest = loop_outer (nest);
645 229
646 return nest; 230 return nest;
647 } 231 }
648 232
649 /* Sets the false region of an IF_REGION to REGION. */ 233 /* Same as outermost_loop_in_sese_1, returns the outermost loop
650 234 containing BB in REGION, but makes sure that the returned loop
651 void 235 belongs to the REGION, and so this returns the first loop in the
652 if_region_set_false_region (ifsese if_region, sese region) 236 REGION when the loop containing BB does not belong to REGION. */
653 { 237
654 basic_block condition = if_region_get_condition_block (if_region); 238 loop_p
655 edge false_edge = get_false_edge_from_guard_bb (condition); 239 outermost_loop_in_sese (sese_l &region, basic_block bb)
656 basic_block dummy = false_edge->dest; 240 {
657 edge entry_region = SESE_ENTRY (region); 241 loop_p nest = outermost_loop_in_sese_1 (region, bb);
658 edge exit_region = SESE_EXIT (region); 242
659 basic_block before_region = entry_region->src; 243 if (loop_in_sese_p (nest, region))
660 basic_block last_in_region = exit_region->src; 244 return nest;
661 void **slot = htab_find_slot_with_hash (current_loops->exits, exit_region, 245
662 htab_hash_pointer (exit_region), 246 /* When the basic block BB does not belong to a loop in the region,
663 NO_INSERT); 247 return the first loop in the region. */
664 248 nest = nest->inner;
665 entry_region->flags = false_edge->flags; 249 while (nest)
666 false_edge->flags = exit_region->flags; 250 if (loop_in_sese_p (nest, region))
667 251 break;
668 redirect_edge_pred (entry_region, condition); 252 else
669 redirect_edge_pred (exit_region, before_region); 253 nest = nest->next;
670 redirect_edge_pred (false_edge, last_in_region); 254
671 redirect_edge_succ (false_edge, single_succ (dummy)); 255 gcc_assert (nest);
672 delete_basic_block (dummy); 256 return nest;
673 257 }
674 exit_region->flags = EDGE_FALLTHRU; 258
675 recompute_all_dominators (); 259 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */
676 260
677 SESE_EXIT (region) = false_edge; 261 edge
678 262 get_true_edge_from_guard_bb (basic_block bb)
679 if (if_region->false_region)
680 free (if_region->false_region);
681 if_region->false_region = region;
682
683 if (slot)
684 {
685 struct loop_exit *loop_exit = ggc_alloc_cleared_loop_exit ();
686
687 memcpy (loop_exit, *((struct loop_exit **) slot), sizeof (struct loop_exit));
688 htab_clear_slot (current_loops->exits, slot);
689
690 slot = htab_find_slot_with_hash (current_loops->exits, false_edge,
691 htab_hash_pointer (false_edge),
692 INSERT);
693 loop_exit->e = false_edge;
694 *slot = loop_exit;
695 false_edge->src->loop_father->exits->next = loop_exit;
696 }
697 }
698
699 /* Creates an IFSESE with CONDITION on edge ENTRY. */
700
701 static ifsese
702 create_if_region_on_edge (edge entry, tree condition)
703 { 263 {
704 edge e; 264 edge e;
705 edge_iterator ei; 265 edge_iterator ei;
706 sese sese_region = XNEW (struct sese_s); 266
707 sese true_region = XNEW (struct sese_s); 267 FOR_EACH_EDGE (e, ei, bb->succs)
708 sese false_region = XNEW (struct sese_s); 268 if (e->flags & EDGE_TRUE_VALUE)
709 ifsese if_region = XNEW (struct ifsese_s); 269 return e;
710 edge exit = create_empty_if_region_on_edge (entry, condition); 270
711 271 gcc_unreachable ();
712 if_region->region = sese_region; 272 return NULL;
713 if_region->region->entry = entry; 273 }
714 if_region->region->exit = exit; 274
715 275 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */
716 FOR_EACH_EDGE (e, ei, entry->dest->succs) 276
717 { 277 edge
718 if (e->flags & EDGE_TRUE_VALUE) 278 get_false_edge_from_guard_bb (basic_block bb)
719 { 279 {
720 true_region->entry = e; 280 edge e;
721 true_region->exit = single_succ_edge (e->dest); 281 edge_iterator ei;
722 if_region->true_region = true_region; 282
723 } 283 FOR_EACH_EDGE (e, ei, bb->succs)
724 else if (e->flags & EDGE_FALSE_VALUE) 284 if (!(e->flags & EDGE_TRUE_VALUE))
725 { 285 return e;
726 false_region->entry = e; 286
727 false_region->exit = single_succ_edge (e->dest); 287 gcc_unreachable ();
728 if_region->false_region = false_region; 288 return NULL;
729 }
730 }
731
732 return if_region;
733 } 289 }
734 290
735 /* Moves REGION in a condition expression: 291 /* Moves REGION in a condition expression:
736 | if (1) 292 | if (1)
737 | ; 293 | ;
738 | else 294 | else
739 | REGION; 295 | REGION;
740 */ 296 */
741 297
742 ifsese 298 ifsese
743 move_sese_in_condition (sese region) 299 move_sese_in_condition (sese_info_p region)
744 { 300 {
745 basic_block pred_block = split_edge (SESE_ENTRY (region)); 301 basic_block region_entry_dest = region->region.entry->dest;
746 ifsese if_region; 302 basic_block pred_block = split_edge (region->region.entry);
747 303 basic_block merge_block = split_edge (region->region.exit);
748 SESE_ENTRY (region) = single_succ_edge (pred_block); 304
749 if_region = create_if_region_on_edge (single_pred_edge (pred_block), integer_one_node); 305 edge true_edge = make_edge (pred_block, merge_block, EDGE_TRUE_VALUE);
750 if_region_set_false_region (if_region, region); 306 edge false_edge = find_edge (pred_block, region_entry_dest);
307 false_edge->flags &= ~EDGE_FALLTHRU;
308 false_edge->flags |= EDGE_FALSE_VALUE;
309 gimple_stmt_iterator gsi = gsi_last_bb (pred_block);
310 gcond *cond = gimple_build_cond (NE_EXPR, integer_one_node, integer_zero_node,
311 NULL_TREE, NULL_TREE);
312 gsi_insert_after (&gsi, cond, GSI_CONTINUE_LINKING);
313 if (dom_info_available_p (CDI_DOMINATORS))
314 set_immediate_dominator (CDI_DOMINATORS, merge_block, pred_block);
315
316 ifsese if_region = XNEW (ifsese_s);
317 if_region->region = XCNEW (sese_info_t);
318 if_region->true_region = XCNEW (sese_info_t);
319 if_region->false_region = XCNEW (sese_info_t);
320 if_region->region->region.entry = single_pred_edge (pred_block);
321 if_region->region->region.exit = single_succ_edge (merge_block);
322 if_region->false_region->region.entry = false_edge;
323 if_region->false_region->region.exit = region->region.exit;
324 if_region->true_region->region.entry = true_edge;
325 if_region->true_region->region.exit
326 = single_succ_edge (split_edge (true_edge));
327
328 region->region = if_region->false_region->region;
751 329
752 return if_region; 330 return if_region;
753 } 331 }
754 332
755 /* Replaces the condition of the IF_REGION with CONDITION: 333 /* Replaces the condition of the IF_REGION with CONDITION:
760 */ 338 */
761 339
762 void 340 void
763 set_ifsese_condition (ifsese if_region, tree condition) 341 set_ifsese_condition (ifsese if_region, tree condition)
764 { 342 {
765 sese region = if_region->region; 343 sese_info_p region = if_region->region;
766 edge entry = region->entry; 344 edge entry = region->region.entry;
767 basic_block bb = entry->dest; 345 basic_block bb = entry->dest;
768 gimple last = last_stmt (bb); 346 gimple *last = last_stmt (bb);
769 gimple_stmt_iterator gsi = gsi_last_bb (bb); 347 gimple_stmt_iterator gsi = gsi_last_bb (bb);
770 gimple cond_stmt; 348 gcond *cond_stmt;
771 349
772 gcc_assert (gimple_code (last) == GIMPLE_COND); 350 gcc_assert (gimple_code (last) == GIMPLE_COND);
773 351
774 gsi_remove (&gsi, true); 352 gsi_remove (&gsi, true);
775 gsi = gsi_last_bb (bb); 353 gsi = gsi_last_bb (bb);
778 cond_stmt = gimple_build_cond_from_tree (condition, NULL_TREE, NULL_TREE); 356 cond_stmt = gimple_build_cond_from_tree (condition, NULL_TREE, NULL_TREE);
779 gsi = gsi_last_bb (bb); 357 gsi = gsi_last_bb (bb);
780 gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT); 358 gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
781 } 359 }
782 360
361 /* Return true when T is defined outside REGION or when no definitions are
362 variant in REGION. When HAS_VDEFS is a valid pointer, sets HAS_VDEFS to true
363 when T depends on memory that may change in REGION. */
364
365 bool
366 invariant_in_sese_p_rec (tree t, const sese_l &region, bool *has_vdefs)
367 {
368 if (!defined_in_sese_p (t, region))
369 return true;
370
371 gimple *stmt = SSA_NAME_DEF_STMT (t);
372
373 if (gimple_code (stmt) == GIMPLE_PHI
374 || gimple_code (stmt) == GIMPLE_CALL)
375 return false;
376
377 /* VDEF is variant when it is in the region. */
378 if (gimple_vdef (stmt))
379 {
380 if (has_vdefs)
381 *has_vdefs = true;
382 return false;
383 }
384
385 /* A VUSE may or may not be variant following the VDEFs. */
386 if (tree vuse = gimple_vuse (stmt))
387 return invariant_in_sese_p_rec (vuse, region, has_vdefs);
388
389 ssa_op_iter iter;
390 use_operand_p use_p;
391 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
392 {
393 tree use = USE_FROM_PTR (use_p);
394
395 if (!defined_in_sese_p (use, region))
396 continue;
397
398 if (!invariant_in_sese_p_rec (use, region, has_vdefs))
399 return false;
400 }
401
402 return true;
403 }
404
405 /* Return true when DEF can be analyzed in REGION by the scalar
406 evolution analyzer. */
407
408 bool
409 scev_analyzable_p (tree def, sese_l &region)
410 {
411 loop_p loop;
412 tree scev;
413 tree type = TREE_TYPE (def);
414
415 /* When Graphite generates code for a scev, the code generator
416 expresses the scev in function of a single induction variable.
417 This is unsafe for floating point computations, as it may replace
418 a floating point sum reduction with a multiplication. The
419 following test returns false for non integer types to avoid such
420 problems. */
421 if (!INTEGRAL_TYPE_P (type)
422 && !POINTER_TYPE_P (type))
423 return false;
424
425 loop = loop_containing_stmt (SSA_NAME_DEF_STMT (def));
426 scev = scalar_evolution_in_region (region, loop, def);
427
428 return (!chrec_contains_undetermined (scev)
429 && (TREE_CODE (scev) != SSA_NAME
430 || !defined_in_sese_p (scev, region))
431 && scev_is_linear_expression (scev)
432 && (! loop
433 || ! loop_in_sese_p (loop, region)
434 || ! chrec_contains_symbols_defined_in_loop (scev, loop->num)));
435 }
436
783 /* Returns the scalar evolution of T in REGION. Every variable that 437 /* Returns the scalar evolution of T in REGION. Every variable that
784 is not defined in the REGION is considered a parameter. */ 438 is not defined in the REGION is considered a parameter. */
785 439
786 tree 440 tree
787 scalar_evolution_in_region (sese region, loop_p loop, tree t) 441 scalar_evolution_in_region (const sese_l &region, loop_p loop, tree t)
788 { 442 {
789 gimple def;
790 struct loop *def_loop;
791 basic_block before = block_before_sese (region);
792
793 /* SCOP parameters. */ 443 /* SCOP parameters. */
794 if (TREE_CODE (t) == SSA_NAME 444 if (TREE_CODE (t) == SSA_NAME
795 && !defined_in_sese_p (t, region)) 445 && !defined_in_sese_p (t, region))
796 return t; 446 return t;
797 447
798 if (TREE_CODE (t) != SSA_NAME 448 if (!loop_in_sese_p (loop, region))
799 || loop_in_sese_p (loop, region)) 449 loop = NULL;
800 return instantiate_scev (before, loop, 450
801 analyze_scalar_evolution (loop, t)); 451 return instantiate_scev (region.entry, loop,
802 452 analyze_scalar_evolution (loop, t));
803 def = SSA_NAME_DEF_STMT (t); 453 }
804 def_loop = loop_containing_stmt (def); 454
805 455 /* Return true if BB is empty, contains only DEBUG_INSNs. */
806 if (loop_in_sese_p (def_loop, region)) 456
807 { 457 bool
808 t = analyze_scalar_evolution (def_loop, t); 458 sese_trivially_empty_bb_p (basic_block bb)
809 def_loop = superloop_at_depth (def_loop, loop_depth (loop) + 1); 459 {
810 t = compute_overall_effect_of_inner_loop (def_loop, t); 460 gimple_stmt_iterator gsi;
811 return t; 461
812 } 462 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
813 else 463 if (gimple_code (gsi_stmt (gsi)) != GIMPLE_DEBUG
814 return instantiate_scev (before, loop, t); 464 && gimple_code (gsi_stmt (gsi)) != GIMPLE_LABEL)
815 } 465 return false;
466
467 return true;
468 }
469
470 /* Pretty print edge E to FILE. */
471
472 void
473 print_edge (FILE *file, const_edge e)
474 {
475 fprintf (file, "edge (bb_%d, bb_%d)", e->src->index, e->dest->index);
476 }
477
478 /* Pretty print sese S to FILE. */
479
480 void
481 print_sese (FILE *file, const sese_l &s)
482 {
483 fprintf (file, "(entry_"); print_edge (file, s.entry);
484 fprintf (file, ", exit_"); print_edge (file, s.exit);
485 fprintf (file, ")\n");
486 }
487
488 /* Pretty print edge E to STDERR. */
489
490 DEBUG_FUNCTION void
491 debug_edge (const_edge e)
492 {
493 print_edge (stderr, e);
494 }
495
496 /* Pretty print sese S to STDERR. */
497
498 DEBUG_FUNCTION void
499 debug_sese (const sese_l &s)
500 {
501 print_sese (stderr, s);
502 }