Mercurial > hg > CbC > CbC_gcc

comparison gcc/sese.c @ 55:77e2b8dfacca gcc-4.4.5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update it from 4.4.3 to 4.5.0
author ryoma <e075725@ie.u-ryukyu.ac.jp>
date Fri, 12 Feb 2010 23:39:51 +0900
parents
children b7f97abdc517
comparison
equal deleted inserted replaced
52:c156f1bd5cd9 55:77e2b8dfacca
1 /* Single entry single exit control flow regions.
2 Copyright (C) 2008, 2009 Free Software Foundation, Inc.
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"
25 #include "tm.h"
26 #include "ggc.h"
27 #include "tree.h"
28 #include "rtl.h"
29 #include "basic-block.h"
30 #include "diagnostic.h"
31 #include "tree-flow.h"
32 #include "toplev.h"
33 #include "tree-dump.h"
34 #include "timevar.h"
35 #include "cfgloop.h"
36 #include "tree-chrec.h"
37 #include "tree-data-ref.h"
38 #include "tree-scalar-evolution.h"
39 #include "tree-pass.h"
40 #include "domwalk.h"
41 #include "value-prof.h"
42 #include "pointer-set.h"
43 #include "gimple.h"
44 #include "sese.h"
45
46 /* Print to stderr the element ELT. */
47
48 static void
49 debug_rename_elt (rename_map_elt elt)
50 {
51 fprintf (stderr, "(");
52 print_generic_expr (stderr, elt->old_name, 0);
53 fprintf (stderr, ", ");
54 print_generic_expr (stderr, elt->expr, 0);
55 fprintf (stderr, ")\n");
56 }
57
58 /* Helper function for debug_rename_map. */
59
60 static int
61 debug_rename_map_1 (void **slot, void *s ATTRIBUTE_UNUSED)
62 {
63 struct rename_map_elt_s *entry = (struct rename_map_elt_s *) *slot;
64 debug_rename_elt (entry);
65 return 1;
66 }
67
68 /* Print to stderr all the elements of MAP. */
69
70 void
71 debug_rename_map (htab_t map)
72 {
73 htab_traverse (map, debug_rename_map_1, NULL);
74 }
75
76 /* Computes a hash function for database element ELT. */
77
78 hashval_t
79 rename_map_elt_info (const void *elt)
80 {
81 return htab_hash_pointer (((const struct rename_map_elt_s *) elt)->old_name);
82 }
83
84 /* Compares database elements E1 and E2. */
85
86 int
87 eq_rename_map_elts (const void *e1, const void *e2)
88 {
89 const struct rename_map_elt_s *elt1 = (const struct rename_map_elt_s *) e1;
90 const struct rename_map_elt_s *elt2 = (const struct rename_map_elt_s *) e2;
91
92 return (elt1->old_name == elt2->old_name);
93 }
94
95
96
97 /* Print to stderr the element ELT. */
98
99 static void
100 debug_ivtype_elt (ivtype_map_elt elt)
101 {
102 fprintf (stderr, "(%s, ", elt->cloog_iv);
103 print_generic_expr (stderr, elt->type, 0);
104 fprintf (stderr, ")\n");
105 }
106
107 /* Helper function for debug_ivtype_map. */
108
109 static int
110 debug_ivtype_map_1 (void **slot, void *s ATTRIBUTE_UNUSED)
111 {
112 struct ivtype_map_elt_s *entry = (struct ivtype_map_elt_s *) *slot;
113 debug_ivtype_elt (entry);
114 return 1;
115 }
116
117 /* Print to stderr all the elements of MAP. */
118
119 void
120 debug_ivtype_map (htab_t map)
121 {
122 htab_traverse (map, debug_ivtype_map_1, NULL);
123 }
124
125 /* Computes a hash function for database element ELT. */
126
127 hashval_t
128 ivtype_map_elt_info (const void *elt)
129 {
130 return htab_hash_pointer (((const struct ivtype_map_elt_s *) elt)->cloog_iv);
131 }
132
133 /* Compares database elements E1 and E2. */
134
135 int
136 eq_ivtype_map_elts (const void *e1, const void *e2)
137 {
138 const struct ivtype_map_elt_s *elt1 = (const struct ivtype_map_elt_s *) e1;
139 const struct ivtype_map_elt_s *elt2 = (const struct ivtype_map_elt_s *) e2;
140
141 return (elt1->cloog_iv == elt2->cloog_iv);
142 }
143
144
145
146 /* Record LOOP as occuring in REGION. */
147
148 static void
149 sese_record_loop (sese region, loop_p loop)
150 {
151 if (sese_contains_loop (region, loop))
152 return;
153
154 bitmap_set_bit (SESE_LOOPS (region), loop->num);
155 VEC_safe_push (loop_p, heap, SESE_LOOP_NEST (region), loop);
156 }
157
158 /* Build the loop nests contained in REGION. Returns true when the
159 operation was successful. */
160
161 void
162 build_sese_loop_nests (sese region)
163 {
164 unsigned i;
165 basic_block bb;
166 struct loop *loop0, *loop1;
167
168 FOR_EACH_BB (bb)
169 if (bb_in_sese_p (bb, region))
170 {
171 struct loop *loop = bb->loop_father;
172
173 /* Only add loops if they are completely contained in the SCoP. */
174 if (loop->header == bb
175 && bb_in_sese_p (loop->latch, region))
176 sese_record_loop (region, loop);
177 }
178
179 /* Make sure that the loops in the SESE_LOOP_NEST are ordered. It
180 can be the case that an inner loop is inserted before an outer
181 loop. To avoid this, semi-sort once. */
182 for (i = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), i, loop0); i++)
183 {
184 if (VEC_length (loop_p, SESE_LOOP_NEST (region)) == i + 1)
185 break;
186
187 loop1 = VEC_index (loop_p, SESE_LOOP_NEST (region), i + 1);
188 if (loop0->num > loop1->num)
189 {
190 VEC_replace (loop_p, SESE_LOOP_NEST (region), i, loop1);
191 VEC_replace (loop_p, SESE_LOOP_NEST (region), i + 1, loop0);
192 }
193 }
194 }
195
196 /* For a USE in BB, if BB is outside REGION, mark the USE in the
197 LIVEOUTS set. */
198
199 static void
200 sese_build_liveouts_use (sese region, bitmap liveouts, basic_block bb,
201 tree use)
202 {
203 unsigned ver;
204 basic_block def_bb;
205
206 if (TREE_CODE (use) != SSA_NAME)
207 return;
208
209 ver = SSA_NAME_VERSION (use);
210 def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
211
212 if (!def_bb
213 || !bb_in_sese_p (def_bb, region)
214 || bb_in_sese_p (bb, region))
215 return;
216
217 bitmap_set_bit (liveouts, ver);
218 }
219
220 /* Marks for rewrite all the SSA_NAMES defined in REGION and that are
221 used in BB that is outside of the REGION. */
222
223 static void
224 sese_build_liveouts_bb (sese region, bitmap liveouts, basic_block bb)
225 {
226 gimple_stmt_iterator bsi;
227 edge e;
228 edge_iterator ei;
229 ssa_op_iter iter;
230 use_operand_p use_p;
231
232 FOR_EACH_EDGE (e, ei, bb->succs)
233 for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi))
234 sese_build_liveouts_use (region, liveouts, bb,
235 PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi), e));
236
237 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
238 {
239 gimple stmt = gsi_stmt (bsi);
240
241 if (is_gimple_debug (stmt))
242 continue;
243
244 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
245 sese_build_liveouts_use (region, liveouts, bb, USE_FROM_PTR (use_p));
246 }
247 }
248
249 /* For a USE in BB, return true if BB is outside REGION and it's not
250 in the LIVEOUTS set. */
251
252 static bool
253 sese_bad_liveouts_use (sese region, bitmap liveouts, basic_block bb,
254 tree use)
255 {
256 unsigned ver;
257 basic_block def_bb;
258
259 if (TREE_CODE (use) != SSA_NAME)
260 return false;
261
262 ver = SSA_NAME_VERSION (use);
263
264 /* If it's in liveouts, the variable will get a new PHI node, and
265 the debug use will be properly adjusted. */
266 if (bitmap_bit_p (liveouts, ver))
267 return false;
268
269 def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
270
271 if (!def_bb
272 || !bb_in_sese_p (def_bb, region)
273 || bb_in_sese_p (bb, region))
274 return false;
275
276 return true;
277 }
278
279 /* Reset debug stmts that reference SSA_NAMES defined in REGION that
280 are not marked as liveouts. */
281
282 static void
283 sese_reset_debug_liveouts_bb (sese region, bitmap liveouts, basic_block bb)
284 {
285 gimple_stmt_iterator bsi;
286 ssa_op_iter iter;
287 use_operand_p use_p;
288
289 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
290 {
291 gimple stmt = gsi_stmt (bsi);
292
293 if (!is_gimple_debug (stmt))
294 continue;
295
296 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
297 if (sese_bad_liveouts_use (region, liveouts, bb,
298 USE_FROM_PTR (use_p)))
299 {
300 gimple_debug_bind_reset_value (stmt);
301 update_stmt (stmt);
302 break;
303 }
304 }
305 }
306
307 /* Build the LIVEOUTS of REGION: the set of variables defined inside
308 and used outside the REGION. */
309
310 static void
311 sese_build_liveouts (sese region, bitmap liveouts)
312 {
313 basic_block bb;
314
315 FOR_EACH_BB (bb)
316 sese_build_liveouts_bb (region, liveouts, bb);
317 if (MAY_HAVE_DEBUG_INSNS)
318 FOR_EACH_BB (bb)
319 sese_reset_debug_liveouts_bb (region, liveouts, bb);
320 }
321
322 /* Builds a new SESE region from edges ENTRY and EXIT. */
323
324 sese
325 new_sese (edge entry, edge exit)
326 {
327 sese region = XNEW (struct sese_s);
328
329 SESE_ENTRY (region) = entry;
330 SESE_EXIT (region) = exit;
331 SESE_LOOPS (region) = BITMAP_ALLOC (NULL);
332 SESE_LOOP_NEST (region) = VEC_alloc (loop_p, heap, 3);
333 SESE_ADD_PARAMS (region) = true;
334 SESE_PARAMS (region) = VEC_alloc (tree, heap, 3);
335
336 return region;
337 }
338
339 /* Deletes REGION. */
340
341 void
342 free_sese (sese region)
343 {
344 if (SESE_LOOPS (region))
345 SESE_LOOPS (region) = BITMAP_ALLOC (NULL);
346
347 VEC_free (tree, heap, SESE_PARAMS (region));
348 VEC_free (loop_p, heap, SESE_LOOP_NEST (region));
349
350 XDELETE (region);
351 }
352
353 /* Add exit phis for USE on EXIT. */
354
355 static void
356 sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e)
357 {
358 gimple phi = create_phi_node (use, exit);
359
360 create_new_def_for (gimple_phi_result (phi), phi,
361 gimple_phi_result_ptr (phi));
362 add_phi_arg (phi, use, false_e, UNKNOWN_LOCATION);
363 add_phi_arg (phi, use, true_e, UNKNOWN_LOCATION);
364 }
365
366 /* Insert in the block BB phi nodes for variables defined in REGION
367 and used outside the REGION. The code generation moves REGION in
368 the else clause of an "if (1)" and generates code in the then
369 clause that is at this point empty:
370
371 | if (1)
372 | empty;
373 | else
374 | REGION;
375 */
376
377 void
378 sese_insert_phis_for_liveouts (sese region, basic_block bb,
379 edge false_e, edge true_e)
380 {
381 unsigned i;
382 bitmap_iterator bi;
383 bitmap liveouts = BITMAP_ALLOC (NULL);
384
385 update_ssa (TODO_update_ssa);
386
387 sese_build_liveouts (region, liveouts);
388 EXECUTE_IF_SET_IN_BITMAP (liveouts, 0, i, bi)
389 sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e);
390 BITMAP_FREE (liveouts);
391
392 update_ssa (TODO_update_ssa);
393 }
394
395 /* Get the definition of NAME before the SESE. Keep track of the
396 basic blocks that have been VISITED in a bitmap. */
397
398 static tree
399 get_vdef_before_sese (sese region, tree name, sbitmap visited)
400 {
401 unsigned i;
402 gimple stmt = SSA_NAME_DEF_STMT (name);
403 basic_block def_bb = gimple_bb (stmt);
404
405 if (!def_bb || !bb_in_sese_p (def_bb, region))
406 return name;
407
408 if (TEST_BIT (visited, def_bb->index))
409 return NULL_TREE;
410
411 SET_BIT (visited, def_bb->index);
412
413 switch (gimple_code (stmt))
414 {
415 case GIMPLE_PHI:
416 for (i = 0; i < gimple_phi_num_args (stmt); i++)
417 {
418 tree arg = gimple_phi_arg_def (stmt, i);
419 tree res;
420
421 if (gimple_bb (SSA_NAME_DEF_STMT (arg))
422 && def_bb->index == gimple_bb (SSA_NAME_DEF_STMT (arg))->index)
423 continue;
424
425 res = get_vdef_before_sese (region, arg, visited);
426 if (res)
427 return res;
428 }
429 return NULL_TREE;
430
431 case GIMPLE_ASSIGN:
432 case GIMPLE_CALL:
433 {
434 use_operand_p use_p = gimple_vuse_op (stmt);
435 tree use = USE_FROM_PTR (use_p);
436
437 if (def_bb->index == gimple_bb (SSA_NAME_DEF_STMT (use))->index)
438 RESET_BIT (visited, def_bb->index);
439
440 return get_vdef_before_sese (region, use, visited);
441 }
442
443 default:
444 return NULL_TREE;
445 }
446 }
447
448 /* Adjust a virtual phi node PHI that is placed at the end of the
449 generated code for SCOP:
450
451 | if (1)
452 | generated code from REGION;
453 | else
454 | REGION;
455
456 The FALSE_E edge comes from the original code, TRUE_E edge comes
457 from the code generated for the SCOP. */
458
459 static void
460 sese_adjust_vphi (sese region, gimple phi, edge true_e)
461 {
462 unsigned i;
463
464 gcc_assert (gimple_phi_num_args (phi) == 2);
465
466 for (i = 0; i < gimple_phi_num_args (phi); i++)
467 if (gimple_phi_arg_edge (phi, i) == true_e)
468 {
469 tree true_arg, false_arg, before_scop_arg;
470 sbitmap visited;
471
472 true_arg = gimple_phi_arg_def (phi, i);
473 if (!SSA_NAME_IS_DEFAULT_DEF (true_arg))
474 return;
475
476 false_arg = gimple_phi_arg_def (phi, i == 0 ? 1 : 0);
477 if (SSA_NAME_IS_DEFAULT_DEF (false_arg))
478 return;
479
480 visited = sbitmap_alloc (last_basic_block);
481 sbitmap_zero (visited);
482 before_scop_arg = get_vdef_before_sese (region, false_arg, visited);
483 gcc_assert (before_scop_arg != NULL_TREE);
484 SET_PHI_ARG_DEF (phi, i, before_scop_arg);
485 sbitmap_free (visited);
486 }
487 }
488
489 /* Returns the name associated to OLD_NAME in MAP. */
490
491 static tree
492 get_rename (htab_t map, tree old_name)
493 {
494 struct rename_map_elt_s tmp;
495 PTR *slot;
496
497 tmp.old_name = old_name;
498 slot = htab_find_slot (map, &tmp, NO_INSERT);
499
500 if (slot && *slot)
501 return ((rename_map_elt) *slot)->expr;
502
503 return old_name;
504 }
505
506 /* Register in MAP the rename tuple (old_name, expr). */
507
508 void
509 set_rename (htab_t map, tree old_name, tree expr)
510 {
511 struct rename_map_elt_s tmp;
512 PTR *slot;
513
514 if (old_name == expr)
515 return;
516
517 tmp.old_name = old_name;
518 slot = htab_find_slot (map, &tmp, INSERT);
519
520 if (!slot)
521 return;
522
523 if (*slot)
524 free (*slot);
525
526 *slot = new_rename_map_elt (old_name, expr);
527 }
528
529 /* Adjusts the phi nodes in the block BB for variables defined in
530 SCOP_REGION and used outside the SCOP_REGION. The code generation
531 moves SCOP_REGION in the else clause of an "if (1)" and generates
532 code in the then clause:
533
534 | if (1)
535 | generated code from REGION;
536 | else
537 | REGION;
538
539 To adjust the phi nodes after the condition, the RENAME_MAP is
540 used. */
541
542 void
543 sese_adjust_liveout_phis (sese region, htab_t rename_map, basic_block bb,
544 edge false_e, edge true_e)
545 {
546 gimple_stmt_iterator si;
547
548 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
549 {
550 unsigned i;
551 unsigned false_i = 0;
552 gimple phi = gsi_stmt (si);
553
554 if (!is_gimple_reg (PHI_RESULT (phi)))
555 {
556 sese_adjust_vphi (region, phi, true_e);
557 continue;
558 }
559
560 for (i = 0; i < gimple_phi_num_args (phi); i++)
561 if (gimple_phi_arg_edge (phi, i) == false_e)
562 {
563 false_i = i;
564 break;
565 }
566
567 for (i = 0; i < gimple_phi_num_args (phi); i++)
568 if (gimple_phi_arg_edge (phi, i) == true_e)
569 {
570 tree old_name = gimple_phi_arg_def (phi, false_i);
571 tree expr = get_rename (rename_map, old_name);
572 gimple_seq stmts;
573
574 gcc_assert (old_name != expr);
575
576 if (TREE_CODE (expr) != SSA_NAME
577 && is_gimple_reg (old_name))
578 {
579 tree type = TREE_TYPE (old_name);
580 tree var = create_tmp_var (type, "var");
581
582 expr = build2 (MODIFY_EXPR, type, var, expr);
583 expr = force_gimple_operand (expr, &stmts, true, NULL);
584 gsi_insert_seq_on_edge_immediate (true_e, stmts);
585 }
586
587 SET_PHI_ARG_DEF (phi, i, expr);
588 }
589 }
590 }
591
592 /* Rename the SSA_NAMEs used in STMT and that appear in MAP. */
593
594 static void
595 rename_variables_in_stmt (gimple stmt, htab_t map, gimple_stmt_iterator *insert_gsi)
596 {
597 ssa_op_iter iter;
598 use_operand_p use_p;
599
600 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
601 {
602 tree use = USE_FROM_PTR (use_p);
603 tree expr = get_rename (map, use);
604 tree type_use = TREE_TYPE (use);
605 tree type_expr = TREE_TYPE (expr);
606 gimple_seq stmts;
607
608 if (use == expr)
609 continue;
610
611 if (type_use != type_expr
612 || (TREE_CODE (expr) != SSA_NAME
613 && is_gimple_reg (use)))
614 {
615 tree var;
616
617 if (is_gimple_debug (stmt))
618 {
619 if (gimple_debug_bind_p (stmt))
620 gimple_debug_bind_reset_value (stmt);
621 else
622 gcc_unreachable ();
623
624 break;
625 }
626
627 var = create_tmp_var (type_use, "var");
628
629 if (type_use != type_expr)
630 expr = fold_convert (type_use, expr);
631
632 expr = build2 (MODIFY_EXPR, type_use, var, expr);
633 expr = force_gimple_operand (expr, &stmts, true, NULL);
634 gsi_insert_seq_before (insert_gsi, stmts, GSI_SAME_STMT);
635 }
636
637 replace_exp (use_p, expr);
638 }
639
640 update_stmt (stmt);
641 }
642
643 /* Returns true if NAME is a parameter of SESE. */
644
645 static bool
646 is_parameter (sese region, tree name)
647 {
648 int i;
649 tree p;
650
651 for (i = 0; VEC_iterate (tree, SESE_PARAMS (region), i, p); i++)
652 if (p == name)
653 return true;
654
655 return false;
656 }
657
658 /* Returns true if NAME is an induction variable. */
659
660 static bool
661 is_iv (tree name)
662 {
663 return gimple_code (SSA_NAME_DEF_STMT (name)) == GIMPLE_PHI;
664 }
665
666 static void expand_scalar_variables_stmt (gimple, basic_block, sese,
667 htab_t, gimple_stmt_iterator *);
668 static tree
669 expand_scalar_variables_expr (tree, tree, enum tree_code, tree, basic_block,
670 sese, htab_t, gimple_stmt_iterator *);
671
672 static tree
673 expand_scalar_variables_call (gimple stmt, basic_block bb, sese region,
674 htab_t map, gimple_stmt_iterator *gsi)
675 {
676 int i, nargs = gimple_call_num_args (stmt);
677 VEC (tree, gc) *args = VEC_alloc (tree, gc, nargs);
678 tree fn_type = TREE_TYPE (gimple_call_fn (stmt));
679 tree fn = gimple_call_fndecl (stmt);
680 tree call_expr, var, lhs;
681 gimple call;
682
683 for (i = 0; i < nargs; i++)
684 {
685 tree arg = gimple_call_arg (stmt, i);
686 tree t = TREE_TYPE (arg);
687
688 var = create_tmp_var (t, "var");
689 arg = expand_scalar_variables_expr (t, arg, TREE_CODE (arg), NULL,
690 bb, region, map, gsi);
691 arg = build2 (MODIFY_EXPR, t, var, arg);
692 arg = force_gimple_operand_gsi (gsi, arg, true, NULL,
693 true, GSI_SAME_STMT);
694 VEC_quick_push (tree, args, arg);
695 }
696
697 lhs = gimple_call_lhs (stmt);
698 var = create_tmp_var (TREE_TYPE (lhs), "var");
699 call_expr = build_call_vec (fn_type, fn, args);
700 call = gimple_build_call_from_tree (call_expr);
701 var = make_ssa_name (var, call);
702 gimple_call_set_lhs (call, var);
703 gsi_insert_before (gsi, call, GSI_SAME_STMT);
704
705 return var;
706 }
707
708 /* Copies at GSI all the scalar computations on which the ssa_name OP0
709 depends on in the SESE: these are all the scalar variables used in
710 the definition of OP0, that are defined outside BB and still in the
711 SESE, i.e. not a parameter of the SESE. The expression that is
712 returned contains only induction variables from the generated code:
713 MAP contains the induction variables renaming mapping, and is used
714 to translate the names of induction variables. */
715
716 static tree
717 expand_scalar_variables_ssa_name (tree op0, basic_block bb,
718 sese region, htab_t map,
719 gimple_stmt_iterator *gsi)
720 {
721 gimple def_stmt;
722 tree new_op;
723
724 if (is_parameter (region, op0)
725 || is_iv (op0))
726 return get_rename (map, op0);
727
728 def_stmt = SSA_NAME_DEF_STMT (op0);
729
730 /* Check whether we already have a rename for OP0. */
731 new_op = get_rename (map, op0);
732
733 if (new_op != op0
734 && gimple_bb (SSA_NAME_DEF_STMT (new_op)) == bb)
735 return new_op;
736
737 if (gimple_bb (def_stmt) == bb)
738 {
739 /* If the defining statement is in the basic block already
740 we do not need to create a new expression for it, we
741 only need to ensure its operands are expanded. */
742 expand_scalar_variables_stmt (def_stmt, bb, region, map, gsi);
743 return new_op;
744 }
745 else
746 {
747 if (!gimple_bb (def_stmt)
748 || !bb_in_sese_p (gimple_bb (def_stmt), region))
749 return new_op;
750
751 switch (gimple_code (def_stmt))
752 {
753 case GIMPLE_ASSIGN:
754 {
755 tree var0 = gimple_assign_rhs1 (def_stmt);
756 enum tree_code subcode = gimple_assign_rhs_code (def_stmt);
757 tree var1 = gimple_assign_rhs2 (def_stmt);
758 tree type = gimple_expr_type (def_stmt);
759
760 return expand_scalar_variables_expr (type, var0, subcode, var1, bb,
761 region, map, gsi);
762 }
763
764 case GIMPLE_CALL:
765 return expand_scalar_variables_call (def_stmt, bb, region, map, gsi);
766
767 default:
768 gcc_unreachable ();
769 return new_op;
770 }
771 }
772 }
773
774 /* Copies at GSI all the scalar computations on which the expression
775 OP0 CODE OP1 depends on in the SESE: these are all the scalar
776 variables used in OP0 and OP1, defined outside BB and still defined
777 in the SESE, i.e. not a parameter of the SESE. The expression that
778 is returned contains only induction variables from the generated
779 code: MAP contains the induction variables renaming mapping, and is
780 used to translate the names of induction variables. */
781
782 static tree
783 expand_scalar_variables_expr (tree type, tree op0, enum tree_code code,
784 tree op1, basic_block bb, sese region,
785 htab_t map, gimple_stmt_iterator *gsi)
786 {
787 if (TREE_CODE_CLASS (code) == tcc_constant
788 || TREE_CODE_CLASS (code) == tcc_declaration)
789 return op0;
790
791 /* For data references we have to duplicate also its memory
792 indexing. */
793 if (TREE_CODE_CLASS (code) == tcc_reference)
794 {
795 switch (code)
796 {
797 case REALPART_EXPR:
798 case IMAGPART_EXPR:
799 {
800 tree op = TREE_OPERAND (op0, 0);
801 tree res = expand_scalar_variables_expr
802 (type, op, TREE_CODE (op), NULL, bb, region, map, gsi);
803 return build1 (code, type, res);
804 }
805
806 case INDIRECT_REF:
807 {
808 tree old_name = TREE_OPERAND (op0, 0);
809 tree expr = expand_scalar_variables_ssa_name
810 (old_name, bb, region, map, gsi);
811
812 if (TREE_CODE (expr) != SSA_NAME
813 && is_gimple_reg (old_name))
814 {
815 tree type = TREE_TYPE (old_name);
816 tree var = create_tmp_var (type, "var");
817
818 expr = build2 (MODIFY_EXPR, type, var, expr);
819 expr = force_gimple_operand_gsi (gsi, expr, true, NULL,
820 true, GSI_SAME_STMT);
821 }
822
823 return fold_build1 (code, type, expr);
824 }
825
826 case ARRAY_REF:
827 {
828 tree op00 = TREE_OPERAND (op0, 0);
829 tree op01 = TREE_OPERAND (op0, 1);
830 tree op02 = TREE_OPERAND (op0, 2);
831 tree op03 = TREE_OPERAND (op0, 3);
832 tree base = expand_scalar_variables_expr
833 (TREE_TYPE (op00), op00, TREE_CODE (op00), NULL, bb, region,
834 map, gsi);
835 tree subscript = expand_scalar_variables_expr
836 (TREE_TYPE (op01), op01, TREE_CODE (op01), NULL, bb, region,
837 map, gsi);
838
839 return build4 (ARRAY_REF, type, base, subscript, op02, op03);
840 }
841
842 default:
843 /* The above cases should catch everything. */
844 gcc_unreachable ();
845 }
846 }
847
848 if (TREE_CODE_CLASS (code) == tcc_unary)
849 {
850 tree op0_type = TREE_TYPE (op0);
851 enum tree_code op0_code = TREE_CODE (op0);
852 tree op0_expr = expand_scalar_variables_expr (op0_type, op0, op0_code,
853 NULL, bb, region, map, gsi);
854
855 return fold_build1 (code, type, op0_expr);
856 }
857
858 if (TREE_CODE_CLASS (code) == tcc_binary
859 || TREE_CODE_CLASS (code) == tcc_comparison)
860 {
861 tree op0_type = TREE_TYPE (op0);
862 enum tree_code op0_code = TREE_CODE (op0);
863 tree op0_expr = expand_scalar_variables_expr (op0_type, op0, op0_code,
864 NULL, bb, region, map, gsi);
865 tree op1_type = TREE_TYPE (op1);
866 enum tree_code op1_code = TREE_CODE (op1);
867 tree op1_expr = expand_scalar_variables_expr (op1_type, op1, op1_code,
868 NULL, bb, region, map, gsi);
869
870 return fold_build2 (code, type, op0_expr, op1_expr);
871 }
872
873 if (code == SSA_NAME)
874 return expand_scalar_variables_ssa_name (op0, bb, region, map, gsi);
875
876 if (code == ADDR_EXPR)
877 return op0;
878
879 gcc_unreachable ();
880 return NULL;
881 }
882
883 /* Copies at the beginning of BB all the scalar computations on which
884 STMT depends on in the SESE: these are all the scalar variables used
885 in STMT, defined outside BB and still defined in the SESE, i.e. not a
886 parameter of the SESE. The expression that is returned contains
887 only induction variables from the generated code: MAP contains the
888 induction variables renaming mapping, and is used to translate the
889 names of induction variables. */
890
891 static void
892 expand_scalar_variables_stmt (gimple stmt, basic_block bb, sese region,
893 htab_t map, gimple_stmt_iterator *gsi)
894 {
895 ssa_op_iter iter;
896 use_operand_p use_p;
897
898 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
899 {
900 tree use = USE_FROM_PTR (use_p);
901 tree type = TREE_TYPE (use);
902 enum tree_code code = TREE_CODE (use);
903 tree use_expr;
904
905 if (!is_gimple_reg (use))
906 continue;
907
908 /* Don't expand USE if we already have a rename for it. */
909 use_expr = get_rename (map, use);
910 if (use_expr != use)
911 continue;
912
913 use_expr = expand_scalar_variables_expr (type, use, code, NULL, bb,
914 region, map, gsi);
915 use_expr = fold_convert (type, use_expr);
916
917 if (use_expr == use)
918 continue;
919
920 if (is_gimple_debug (stmt))
921 {
922 if (gimple_debug_bind_p (stmt))
923 gimple_debug_bind_reset_value (stmt);
924 else
925 gcc_unreachable ();
926
927 break;
928 }
929
930 if (TREE_CODE (use_expr) != SSA_NAME)
931 {
932 tree var = create_tmp_var (type, "var");
933
934 use_expr = build2 (MODIFY_EXPR, type, var, use_expr);
935 use_expr = force_gimple_operand_gsi (gsi, use_expr, true, NULL,
936 true, GSI_SAME_STMT);
937 }
938
939 replace_exp (use_p, use_expr);
940 }
941
942 update_stmt (stmt);
943 }
944
945 /* Copies at the beginning of BB all the scalar computations on which
946 BB depends on in the SESE: these are all the scalar variables used
947 in BB, defined outside BB and still defined in the SESE, i.e. not a
948 parameter of the SESE. The expression that is returned contains
949 only induction variables from the generated code: MAP contains the
950 induction variables renaming mapping, and is used to translate the
951 names of induction variables. */
952
953 static void
954 expand_scalar_variables (basic_block bb, sese region, htab_t map)
955 {
956 gimple_stmt_iterator gsi;
957
958 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi);)
959 {
960 gimple stmt = gsi_stmt (gsi);
961 expand_scalar_variables_stmt (stmt, bb, region, map, &gsi);
962 gsi_next (&gsi);
963 }
964 }
965
966 /* Rename all the SSA_NAMEs from block BB according to the MAP. */
967
968 static void
969 rename_variables (basic_block bb, htab_t map)
970 {
971 gimple_stmt_iterator gsi;
972 gimple_stmt_iterator insert_gsi = gsi_start_bb (bb);
973
974 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
975 rename_variables_in_stmt (gsi_stmt (gsi), map, &insert_gsi);
976 }
977
978 /* Remove condition from BB. */
979
980 static void
981 remove_condition (basic_block bb)
982 {
983 gimple last = last_stmt (bb);
984
985 if (last && gimple_code (last) == GIMPLE_COND)
986 {
987 gimple_stmt_iterator gsi = gsi_last_bb (bb);
988 gsi_remove (&gsi, true);
989 }
990 }
991
992 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */
993
994 edge
995 get_true_edge_from_guard_bb (basic_block bb)
996 {
997 edge e;
998 edge_iterator ei;
999
1000 FOR_EACH_EDGE (e, ei, bb->succs)
1001 if (e->flags & EDGE_TRUE_VALUE)
1002 return e;
1003
1004 gcc_unreachable ();
1005 return NULL;
1006 }
1007
1008 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */
1009
1010 edge
1011 get_false_edge_from_guard_bb (basic_block bb)
1012 {
1013 edge e;
1014 edge_iterator ei;
1015
1016 FOR_EACH_EDGE (e, ei, bb->succs)
1017 if (!(e->flags & EDGE_TRUE_VALUE))
1018 return e;
1019
1020 gcc_unreachable ();
1021 return NULL;
1022 }
1023
1024 /* Returns true when NAME is defined in LOOP. */
1025
1026 static bool
1027 defined_in_loop_p (tree name, loop_p loop)
1028 {
1029 gimple stmt = SSA_NAME_DEF_STMT (name);
1030
1031 return (gimple_bb (stmt)->loop_father == loop);
1032 }
1033
1034 /* Returns the gimple statement that uses NAME outside the loop it is
1035 defined in, returns NULL if there is no such loop close phi node.
1036 An invariant of the loop closed SSA form is that the only use of a
1037 variable, outside the loop it is defined in, is in the loop close
1038 phi node that just follows the loop. */
1039
1040 static gimple
1041 alive_after_loop (tree name)
1042 {
1043 use_operand_p use_p;
1044 imm_use_iterator imm_iter;
1045 loop_p loop = gimple_bb (SSA_NAME_DEF_STMT (name))->loop_father;
1046
1047 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, name)
1048 {
1049 gimple stmt = USE_STMT (use_p);
1050
1051 if (gimple_code (stmt) == GIMPLE_PHI
1052 && gimple_bb (stmt)->loop_father != loop)
1053 return stmt;
1054 }
1055
1056 return NULL;
1057 }
1058
1059 /* Return true if a close phi has not yet been inserted for the use of
1060 variable NAME on the single exit of LOOP. */
1061
1062 static bool
1063 close_phi_not_yet_inserted_p (loop_p loop, tree name)
1064 {
1065 gimple_stmt_iterator psi;
1066 basic_block bb = single_exit (loop)->dest;
1067
1068 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
1069 if (gimple_phi_arg_def (gsi_stmt (psi), 0) == name)
1070 return false;
1071
1072 return true;
1073 }
1074
1075 /* A structure for passing parameters to add_loop_exit_phis. */
1076
1077 typedef struct alep {
1078 loop_p loop;
1079 VEC (rename_map_elt, heap) *new_renames;
1080 } *alep_p;
1081
1082 /* Helper function for htab_traverse in insert_loop_close_phis. */
1083
1084 static int
1085 add_loop_exit_phis (void **slot, void *data)
1086 {
1087 struct rename_map_elt_s *entry;
1088 alep_p a;
1089 loop_p loop;
1090 tree expr, new_name;
1091 bool def_in_loop_p, used_outside_p, need_close_phi_p;
1092 gimple old_close_phi;
1093
1094 if (!slot || !data)
1095 return 1;
1096
1097 entry = (struct rename_map_elt_s *) *slot;
1098 a = (alep_p) data;
1099 loop = a->loop;
1100 expr = entry->expr;
1101
1102 if (TREE_CODE (expr) != SSA_NAME)
1103 return 1;
1104
1105 new_name = expr;
1106 def_in_loop_p = defined_in_loop_p (new_name, loop);
1107 old_close_phi = alive_after_loop (entry->old_name);
1108 used_outside_p = (old_close_phi != NULL);
1109 need_close_phi_p = (def_in_loop_p && used_outside_p
1110 && close_phi_not_yet_inserted_p (loop, new_name));
1111
1112 /* Insert a loop close phi node. */
1113 if (need_close_phi_p)
1114 {
1115 basic_block bb = single_exit (loop)->dest;
1116 gimple phi = create_phi_node (new_name, bb);
1117 tree new_res = create_new_def_for (gimple_phi_result (phi), phi,
1118 gimple_phi_result_ptr (phi));
1119
1120 add_phi_arg (phi, new_name, single_pred_edge (bb), UNKNOWN_LOCATION);
1121 VEC_safe_push (rename_map_elt, heap, a->new_renames,
1122 new_rename_map_elt (gimple_phi_result (old_close_phi),
1123 new_res));
1124 }
1125
1126 /* Remove the old rename from the map. */
1127 if (def_in_loop_p && *slot)
1128 {
1129 free (*slot);
1130 *slot = NULL;
1131 }
1132
1133 return 1;
1134 }
1135
1136 /* Traverses MAP and removes from it all the tuples (OLD, NEW) where
1137 NEW is defined in LOOP. Inserts on the exit of LOOP the close phi
1138 node "RES = phi (NEW)" corresponding to "OLD_RES = phi (OLD)" in
1139 the original code. Inserts in MAP the tuple (OLD_RES, RES). */
1140
1141 void
1142 insert_loop_close_phis (htab_t map, loop_p loop)
1143 {
1144 int i;
1145 struct alep a;
1146 rename_map_elt elt;
1147
1148 a.loop = loop;
1149 a.new_renames = VEC_alloc (rename_map_elt, heap, 3);
1150 update_ssa (TODO_update_ssa);
1151 htab_traverse (map, add_loop_exit_phis, &a);
1152 update_ssa (TODO_update_ssa);
1153
1154 for (i = 0; VEC_iterate (rename_map_elt, a.new_renames, i, elt); i++)
1155 {
1156 set_rename (map, elt->old_name, elt->expr);
1157 free (elt);
1158 }
1159
1160 VEC_free (rename_map_elt, heap, a.new_renames);
1161 }
1162
1163 /* Helper structure for htab_traverse in insert_guard_phis. */
1164
1165 struct igp {
1166 basic_block bb;
1167 edge true_edge, false_edge;
1168 htab_t before_guard;
1169 };
1170
1171 /* Return the default name that is before the guard. */
1172
1173 static tree
1174 default_before_guard (htab_t before_guard, tree old_name)
1175 {
1176 tree res = get_rename (before_guard, old_name);
1177
1178 if (res == old_name)
1179 {
1180 if (is_gimple_reg (res))
1181 return fold_convert (TREE_TYPE (res), integer_zero_node);
1182 return gimple_default_def (cfun, SSA_NAME_VAR (res));
1183 }
1184
1185 return res;
1186 }
1187
1188 /* Prepares EXPR to be a good phi argument when the phi result is
1189 RES. Insert needed statements on edge E. */
1190
1191 static tree
1192 convert_for_phi_arg (tree expr, tree res, edge e)
1193 {
1194 tree type = TREE_TYPE (res);
1195
1196 if (TREE_TYPE (expr) != type)
1197 expr = fold_convert (type, expr);
1198
1199 if (TREE_CODE (expr) != SSA_NAME
1200 && !is_gimple_min_invariant (expr))
1201 {
1202 tree var = create_tmp_var (type, "var");
1203 gimple_seq stmts;
1204
1205 expr = build2 (MODIFY_EXPR, type, var, expr);
1206 expr = force_gimple_operand (expr, &stmts, true, NULL);
1207 gsi_insert_seq_on_edge_immediate (e, stmts);
1208 }
1209
1210 return expr;
1211 }
1212
1213 /* Helper function for htab_traverse in insert_guard_phis. */
1214
1215 static int
1216 add_guard_exit_phis (void **slot, void *s)
1217 {
1218 struct rename_map_elt_s *entry = (struct rename_map_elt_s *) *slot;
1219 struct igp *i = (struct igp *) s;
1220 basic_block bb = i->bb;
1221 edge true_edge = i->true_edge;
1222 edge false_edge = i->false_edge;
1223 tree res = entry->old_name;
1224 tree name1 = entry->expr;
1225 tree name2 = default_before_guard (i->before_guard, res);
1226 gimple phi;
1227
1228 /* Nothing to be merged if the name before the guard is the same as
1229 the one after. */
1230 if (name1 == name2)
1231 return 1;
1232
1233 name1 = convert_for_phi_arg (name1, res, true_edge);
1234 name2 = convert_for_phi_arg (name2, res, false_edge);
1235
1236 phi = create_phi_node (res, bb);
1237 res = create_new_def_for (gimple_phi_result (phi), phi,
1238 gimple_phi_result_ptr (phi));
1239
1240 add_phi_arg (phi, name1, true_edge, UNKNOWN_LOCATION);
1241 add_phi_arg (phi, name2, false_edge, UNKNOWN_LOCATION);
1242
1243 entry->expr = res;
1244 *slot = entry;
1245 return 1;
1246 }
1247
1248 /* Iterate over RENAME_MAP and get tuples of the form (OLD, NAME1).
1249 If there is a correspondent tuple (OLD, NAME2) in BEFORE_GUARD,
1250 with NAME1 different than NAME2, then insert in BB the phi node:
1251
1252 | RES = phi (NAME1 (on TRUE_EDGE), NAME2 (on FALSE_EDGE))"
1253
1254 if there is no tuple for OLD in BEFORE_GUARD, insert
1255
1256 | RES = phi (NAME1 (on TRUE_EDGE),
1257 | DEFAULT_DEFINITION of NAME1 (on FALSE_EDGE))".
1258
1259 Finally register in RENAME_MAP the tuple (OLD, RES). */
1260
1261 void
1262 insert_guard_phis (basic_block bb, edge true_edge, edge false_edge,
1263 htab_t before_guard, htab_t rename_map)
1264 {
1265 struct igp i;
1266 i.bb = bb;
1267 i.true_edge = true_edge;
1268 i.false_edge = false_edge;
1269 i.before_guard = before_guard;
1270
1271 update_ssa (TODO_update_ssa);
1272 htab_traverse (rename_map, add_guard_exit_phis, &i);
1273 update_ssa (TODO_update_ssa);
1274 }
1275
1276 /* Create a duplicate of the basic block BB. NOTE: This does not
1277 preserve SSA form. */
1278
1279 static void
1280 graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, htab_t map)
1281 {
1282 gimple_stmt_iterator gsi, gsi_tgt;
1283
1284 gsi_tgt = gsi_start_bb (new_bb);
1285 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1286 {
1287 def_operand_p def_p;
1288 ssa_op_iter op_iter;
1289 gimple stmt = gsi_stmt (gsi);
1290 gimple copy;
1291
1292 if (gimple_code (stmt) == GIMPLE_LABEL)
1293 continue;
1294
1295 /* Create a new copy of STMT and duplicate STMT's virtual
1296 operands. */
1297 copy = gimple_copy (stmt);
1298 gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
1299 mark_sym_for_renaming (gimple_vop (cfun));
1300
1301 maybe_duplicate_eh_stmt (copy, stmt);
1302 gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
1303
1304 /* Create new names for all the definitions created by COPY and
1305 add replacement mappings for each new name. */
1306 FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
1307 {
1308 tree old_name = DEF_FROM_PTR (def_p);
1309 tree new_name = create_new_def_for (old_name, copy, def_p);
1310 set_rename (map, old_name, new_name);
1311 }
1312 }
1313 }
1314
1315 /* Copies BB and includes in the copied BB all the statements that can
1316 be reached following the use-def chains from the memory accesses,
1317 and returns the next edge following this new block. */
1318
1319 edge
1320 copy_bb_and_scalar_dependences (basic_block bb, sese region,
1321 edge next_e, htab_t map)
1322 {
1323 basic_block new_bb = split_edge (next_e);
1324
1325 next_e = single_succ_edge (new_bb);
1326 graphite_copy_stmts_from_block (bb, new_bb, map);
1327 remove_condition (new_bb);
1328 remove_phi_nodes (new_bb);
1329 expand_scalar_variables (new_bb, region, map);
1330 rename_variables (new_bb, map);
1331
1332 return next_e;
1333 }
1334
1335 /* Returns the outermost loop in SCOP that contains BB. */
1336
1337 struct loop *
1338 outermost_loop_in_sese (sese region, basic_block bb)
1339 {
1340 struct loop *nest;
1341
1342 nest = bb->loop_father;
1343 while (loop_outer (nest)
1344 && loop_in_sese_p (loop_outer (nest), region))
1345 nest = loop_outer (nest);
1346
1347 return nest;
1348 }
1349
1350 /* Sets the false region of an IF_REGION to REGION. */
1351
1352 void
1353 if_region_set_false_region (ifsese if_region, sese region)
1354 {
1355 basic_block condition = if_region_get_condition_block (if_region);
1356 edge false_edge = get_false_edge_from_guard_bb (condition);
1357 basic_block dummy = false_edge->dest;
1358 edge entry_region = SESE_ENTRY (region);
1359 edge exit_region = SESE_EXIT (region);
1360 basic_block before_region = entry_region->src;
1361 basic_block last_in_region = exit_region->src;
1362 void **slot = htab_find_slot_with_hash (current_loops->exits, exit_region,
1363 htab_hash_pointer (exit_region),
1364 NO_INSERT);
1365
1366 entry_region->flags = false_edge->flags;
1367 false_edge->flags = exit_region->flags;
1368
1369 redirect_edge_pred (entry_region, condition);
1370 redirect_edge_pred (exit_region, before_region);
1371 redirect_edge_pred (false_edge, last_in_region);
1372 redirect_edge_succ (false_edge, single_succ (dummy));
1373 delete_basic_block (dummy);
1374
1375 exit_region->flags = EDGE_FALLTHRU;
1376 recompute_all_dominators ();
1377
1378 SESE_EXIT (region) = false_edge;
1379
1380 if (if_region->false_region)
1381 free (if_region->false_region);
1382 if_region->false_region = region;
1383
1384 if (slot)
1385 {
1386 struct loop_exit *loop_exit = GGC_CNEW (struct loop_exit);
1387
1388 memcpy (loop_exit, *((struct loop_exit **) slot), sizeof (struct loop_exit));
1389 htab_clear_slot (current_loops->exits, slot);
1390
1391 slot = htab_find_slot_with_hash (current_loops->exits, false_edge,
1392 htab_hash_pointer (false_edge),
1393 INSERT);
1394 loop_exit->e = false_edge;
1395 *slot = loop_exit;
1396 false_edge->src->loop_father->exits->next = loop_exit;
1397 }
1398 }
1399
1400 /* Creates an IFSESE with CONDITION on edge ENTRY. */
1401
1402 ifsese
1403 create_if_region_on_edge (edge entry, tree condition)
1404 {
1405 edge e;
1406 edge_iterator ei;
1407 sese sese_region = XNEW (struct sese_s);
1408 sese true_region = XNEW (struct sese_s);
1409 sese false_region = XNEW (struct sese_s);
1410 ifsese if_region = XNEW (struct ifsese_s);
1411 edge exit = create_empty_if_region_on_edge (entry, condition);
1412
1413 if_region->region = sese_region;
1414 if_region->region->entry = entry;
1415 if_region->region->exit = exit;
1416
1417 FOR_EACH_EDGE (e, ei, entry->dest->succs)
1418 {
1419 if (e->flags & EDGE_TRUE_VALUE)
1420 {
1421 true_region->entry = e;
1422 true_region->exit = single_succ_edge (e->dest);
1423 if_region->true_region = true_region;
1424 }
1425 else if (e->flags & EDGE_FALSE_VALUE)
1426 {
1427 false_region->entry = e;
1428 false_region->exit = single_succ_edge (e->dest);
1429 if_region->false_region = false_region;
1430 }
1431 }
1432
1433 return if_region;
1434 }
1435
1436 /* Moves REGION in a condition expression:
1437 | if (1)
1438 | ;
1439 | else
1440 | REGION;
1441 */
1442
1443 ifsese
1444 move_sese_in_condition (sese region)
1445 {
1446 basic_block pred_block = split_edge (SESE_ENTRY (region));
1447 ifsese if_region;
1448
1449 SESE_ENTRY (region) = single_succ_edge (pred_block);
1450 if_region = create_if_region_on_edge (single_pred_edge (pred_block), integer_one_node);
1451 if_region_set_false_region (if_region, region);
1452
1453 return if_region;
1454 }
1455
1456 /* Returns the scalar evolution of T in REGION. Every variable that
1457 is not defined in the REGION is considered a parameter. */
1458
1459 tree
1460 scalar_evolution_in_region (sese region, loop_p loop, tree t)
1461 {
1462 gimple def;
1463 struct loop *def_loop;
1464 basic_block before = block_before_sese (region);
1465
1466 if (TREE_CODE (t) != SSA_NAME
1467 || loop_in_sese_p (loop, region))
1468 return instantiate_scev (before, loop,
1469 analyze_scalar_evolution (loop, t));
1470
1471 if (!defined_in_sese_p (t, region))
1472 return t;
1473
1474 def = SSA_NAME_DEF_STMT (t);
1475 def_loop = loop_containing_stmt (def);
1476
1477 if (loop_in_sese_p (def_loop, region))
1478 {
1479 t = analyze_scalar_evolution (def_loop, t);
1480 def_loop = superloop_at_depth (def_loop, loop_depth (loop) + 1);
1481 t = compute_overall_effect_of_inner_loop (def_loop, t);
1482 return t;
1483 }
1484 else
1485 return instantiate_scev (before, loop, t);
1486 }