Fix type in the changelog entry,
[official-gcc.git] / gcc / sese.c
blobdb8c629199163c2b097c9d0b23fe8d10c45e3297
1 /* Single entry single exit control flow regions.
2 Copyright (C) 2008-2015 Free Software Foundation, Inc.
3 Contributed by Jan Sjodin <jan.sjodin@amd.com> and
4 Sebastian Pop <sebastian.pop@amd.com>.
6 This file is part of GCC.
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.
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.
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/>. */
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "alias.h"
26 #include "backend.h"
27 #include "cfghooks.h"
28 #include "tree.h"
29 #include "gimple.h"
30 #include "hard-reg-set.h"
31 #include "ssa.h"
32 #include "options.h"
33 #include "fold-const.h"
34 #include "tree-pretty-print.h"
35 #include "internal-fn.h"
36 #include "gimple-fold.h"
37 #include "tree-eh.h"
38 #include "gimplify.h"
39 #include "gimple-iterator.h"
40 #include "gimplify-me.h"
41 #include "tree-cfg.h"
42 #include "tree-ssa-loop.h"
43 #include "tree-into-ssa.h"
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"
49 #include "value-prof.h"
50 #include "sese.h"
51 #include "tree-ssa-propagate.h"
52 #include "tree-hash-traits.h"
54 /* Helper function for debug_rename_map. */
56 bool
57 debug_rename_map_1 (tree_node *const &old_name, tree_node *const &expr,
58 void *)
60 fprintf (stderr, "(");
61 print_generic_expr (stderr, old_name, 0);
62 fprintf (stderr, ", ");
63 print_generic_expr (stderr, expr, 0);
64 fprintf (stderr, ")\n");
65 return true;
68 typedef hash_map<tree_ssa_name_hash, tree> rename_map_type;
71 /* Print to stderr all the elements of RENAME_MAP. */
73 DEBUG_FUNCTION void
74 debug_rename_map (rename_map_type *rename_map)
76 rename_map->traverse <void *, debug_rename_map_1> (NULL);
80 /* Record LOOP as occurring in REGION. */
82 static void
83 sese_record_loop (sese region, loop_p loop)
85 if (sese_contains_loop (region, loop))
86 return;
88 bitmap_set_bit (SESE_LOOPS (region), loop->num);
89 SESE_LOOP_NEST (region).safe_push (loop);
92 /* Build the loop nests contained in REGION. Returns true when the
93 operation was successful. */
95 void
96 build_sese_loop_nests (sese region)
98 unsigned i;
99 basic_block bb;
100 struct loop *loop0, *loop1;
102 FOR_EACH_BB_FN (bb, cfun)
103 if (bb_in_sese_p (bb, region))
105 struct loop *loop = bb->loop_father;
107 /* Only add loops if they are completely contained in the SCoP. */
108 if (loop->header == bb
109 && bb_in_sese_p (loop->latch, region))
110 sese_record_loop (region, loop);
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. */
116 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region), i, loop0)
118 if (SESE_LOOP_NEST (region).length () == i + 1)
119 break;
121 loop1 = SESE_LOOP_NEST (region)[i + 1];
122 if (loop0->num > loop1->num)
124 SESE_LOOP_NEST (region)[i] = loop1;
125 SESE_LOOP_NEST (region)[i + 1] = loop0;
130 /* For a USE in BB, if BB is outside REGION, mark the USE in the
131 LIVEOUTS set. */
133 static void
134 sese_build_liveouts_use (sese region, bitmap liveouts, basic_block bb,
135 tree use)
137 unsigned ver;
138 basic_block def_bb;
140 if (TREE_CODE (use) != SSA_NAME)
141 return;
143 ver = SSA_NAME_VERSION (use);
144 def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
146 if (!def_bb
147 || !bb_in_sese_p (def_bb, region)
148 || bb_in_sese_p (bb, region))
149 return;
151 bitmap_set_bit (liveouts, ver);
154 /* Marks for rewrite all the SSA_NAMES defined in REGION and that are
155 used in BB that is outside of the REGION. */
157 static void
158 sese_build_liveouts_bb (sese region, bitmap liveouts, basic_block bb)
160 edge e;
161 edge_iterator ei;
162 ssa_op_iter iter;
163 use_operand_p use_p;
165 FOR_EACH_EDGE (e, ei, bb->succs)
166 for (gphi_iterator bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi);
167 gsi_next (&bsi))
168 sese_build_liveouts_use (region, liveouts, bb,
169 PHI_ARG_DEF_FROM_EDGE (bsi.phi (), e));
171 for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);
172 gsi_next (&bsi))
174 gimple *stmt = gsi_stmt (bsi);
176 if (is_gimple_debug (stmt))
177 continue;
179 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
180 sese_build_liveouts_use (region, liveouts, bb, USE_FROM_PTR (use_p));
184 /* For a USE in BB, return true if BB is outside REGION and it's not
185 in the LIVEOUTS set. */
187 static bool
188 sese_bad_liveouts_use (sese region, bitmap liveouts, basic_block bb,
189 tree use)
191 unsigned ver;
192 basic_block def_bb;
194 if (TREE_CODE (use) != SSA_NAME)
195 return false;
197 ver = SSA_NAME_VERSION (use);
199 /* If it's in liveouts, the variable will get a new PHI node, and
200 the debug use will be properly adjusted. */
201 if (bitmap_bit_p (liveouts, ver))
202 return false;
204 def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
206 if (!def_bb
207 || !bb_in_sese_p (def_bb, region)
208 || bb_in_sese_p (bb, region))
209 return false;
211 return true;
214 /* Reset debug stmts that reference SSA_NAMES defined in REGION that
215 are not marked as liveouts. */
217 static void
218 sese_reset_debug_liveouts_bb (sese region, bitmap liveouts, basic_block bb)
220 gimple_stmt_iterator bsi;
221 ssa_op_iter iter;
222 use_operand_p use_p;
224 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
226 gimple *stmt = gsi_stmt (bsi);
228 if (!is_gimple_debug (stmt))
229 continue;
231 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
232 if (sese_bad_liveouts_use (region, liveouts, bb,
233 USE_FROM_PTR (use_p)))
235 gimple_debug_bind_reset_value (stmt);
236 update_stmt (stmt);
237 break;
242 /* Build the LIVEOUTS of REGION: the set of variables defined inside
243 and used outside the REGION. */
245 static void
246 sese_build_liveouts (sese region, bitmap liveouts)
248 basic_block bb;
250 FOR_EACH_BB_FN (bb, cfun)
251 sese_build_liveouts_bb (region, liveouts, bb);
252 if (MAY_HAVE_DEBUG_STMTS)
253 FOR_EACH_BB_FN (bb, cfun)
254 sese_reset_debug_liveouts_bb (region, liveouts, bb);
257 /* Builds a new SESE region from edges ENTRY and EXIT. */
259 sese
260 new_sese (edge entry, edge exit)
262 sese region = XNEW (struct sese_s);
264 SESE_ENTRY (region) = entry;
265 SESE_EXIT (region) = exit;
266 SESE_LOOPS (region) = BITMAP_ALLOC (NULL);
267 SESE_LOOP_NEST (region).create (3);
268 SESE_ADD_PARAMS (region) = true;
269 SESE_PARAMS (region).create (3);
270 region->parameter_rename_map = new parameter_rename_map_t;
272 return region;
275 /* Deletes REGION. */
277 void
278 free_sese (sese region)
280 if (SESE_LOOPS (region))
281 SESE_LOOPS (region) = BITMAP_ALLOC (NULL);
283 SESE_PARAMS (region).release ();
284 SESE_LOOP_NEST (region).release ();
285 delete region->parameter_rename_map;
286 region->parameter_rename_map = NULL;
288 XDELETE (region);
291 /* Add exit phis for USE on EXIT. */
293 static void
294 sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e)
296 gphi *phi = create_phi_node (NULL_TREE, exit);
297 create_new_def_for (use, phi, gimple_phi_result_ptr (phi));
298 add_phi_arg (phi, use, false_e, UNKNOWN_LOCATION);
299 add_phi_arg (phi, use, true_e, UNKNOWN_LOCATION);
300 update_stmt (phi);
303 /* Insert in the block BB phi nodes for variables defined in REGION
304 and used outside the REGION. The code generation moves REGION in
305 the else clause of an "if (1)" and generates code in the then
306 clause that is at this point empty:
308 | if (1)
309 | empty;
310 | else
311 | REGION;
314 void
315 sese_insert_phis_for_liveouts (sese region, basic_block bb,
316 edge false_e, edge true_e)
318 unsigned i;
319 bitmap_iterator bi;
320 bitmap liveouts = BITMAP_ALLOC (NULL);
322 update_ssa (TODO_update_ssa);
324 sese_build_liveouts (region, liveouts);
325 EXECUTE_IF_SET_IN_BITMAP (liveouts, 0, i, bi)
326 sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e);
327 BITMAP_FREE (liveouts);
329 update_ssa (TODO_update_ssa);
332 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */
334 edge
335 get_true_edge_from_guard_bb (basic_block bb)
337 edge e;
338 edge_iterator ei;
340 FOR_EACH_EDGE (e, ei, bb->succs)
341 if (e->flags & EDGE_TRUE_VALUE)
342 return e;
344 gcc_unreachable ();
345 return NULL;
348 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */
350 edge
351 get_false_edge_from_guard_bb (basic_block bb)
353 edge e;
354 edge_iterator ei;
356 FOR_EACH_EDGE (e, ei, bb->succs)
357 if (!(e->flags & EDGE_TRUE_VALUE))
358 return e;
360 gcc_unreachable ();
361 return NULL;
364 /* Returns the expression associated to OLD_NAME in RENAME_MAP. */
366 static tree
367 get_rename (rename_map_type *rename_map, tree old_name)
369 gcc_assert (TREE_CODE (old_name) == SSA_NAME);
370 tree *expr = rename_map->get (old_name);
371 if (expr)
372 return *expr;
374 return NULL_TREE;
377 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR). */
379 static void
380 set_rename (rename_map_type *rename_map, tree old_name, tree expr, sese region)
382 if (old_name == expr)
383 return;
385 rename_map->put (old_name, expr);
387 tree t;
388 int i;
389 /* For a parameter of a scop we dont want to rename it. */
390 FOR_EACH_VEC_ELT (SESE_PARAMS (region), i, t)
391 if (old_name == t)
392 region->parameter_rename_map->put(old_name, expr);
395 /* Renames the scalar uses of the statement COPY, using the
396 substitution map RENAME_MAP, inserting the gimplification code at
397 GSI_TGT, for the translation REGION, with the original copied
398 statement in LOOP, and using the induction variable renaming map
399 IV_MAP. Returns true when something has been renamed. GLOOG_ERROR
400 is set when the code generation cannot continue. */
402 static bool
403 rename_uses (gimple *copy, rename_map_type *rename_map,
404 gimple_stmt_iterator *gsi_tgt,
405 sese region, loop_p loop, vec<tree> iv_map,
406 bool *gloog_error)
408 use_operand_p use_p;
409 ssa_op_iter op_iter;
410 bool changed = false;
412 if (is_gimple_debug (copy))
414 if (gimple_debug_bind_p (copy))
415 gimple_debug_bind_reset_value (copy);
416 else if (gimple_debug_source_bind_p (copy))
417 return false;
418 else
419 gcc_unreachable ();
421 return false;
424 FOR_EACH_SSA_USE_OPERAND (use_p, copy, op_iter, SSA_OP_USE)
426 tree old_name = USE_FROM_PTR (use_p);
427 tree new_expr, scev;
428 gimple_seq stmts;
430 if (TREE_CODE (old_name) != SSA_NAME
431 || SSA_NAME_IS_DEFAULT_DEF (old_name))
432 continue;
434 changed = true;
435 new_expr = get_rename (rename_map, old_name);
436 if (new_expr)
438 tree type_old_name = TREE_TYPE (old_name);
439 tree type_new_expr = TREE_TYPE (new_expr);
441 if (type_old_name != type_new_expr
442 || TREE_CODE (new_expr) != SSA_NAME)
444 tree var = create_tmp_var (type_old_name, "var");
446 if (!useless_type_conversion_p (type_old_name, type_new_expr))
447 new_expr = fold_convert (type_old_name, new_expr);
449 new_expr = force_gimple_operand (new_expr, &stmts, true, var);
450 gsi_insert_seq_before (gsi_tgt, stmts, GSI_SAME_STMT);
453 replace_exp (use_p, new_expr);
454 continue;
457 scev = scalar_evolution_in_region (region, loop, old_name);
459 /* At this point we should know the exact scev for each
460 scalar SSA_NAME used in the scop: all the other scalar
461 SSA_NAMEs should have been translated out of SSA using
462 arrays with one element. */
463 if (chrec_contains_undetermined (scev))
465 *gloog_error = true;
466 new_expr = build_zero_cst (TREE_TYPE (old_name));
468 else
469 new_expr = chrec_apply_map (scev, iv_map);
471 /* The apply should produce an expression tree containing
472 the uses of the new induction variables. We should be
473 able to use new_expr instead of the old_name in the newly
474 generated loop nest. */
475 if (chrec_contains_undetermined (new_expr)
476 || tree_contains_chrecs (new_expr, NULL))
478 *gloog_error = true;
479 new_expr = build_zero_cst (TREE_TYPE (old_name));
481 else
482 /* Replace the old_name with the new_expr. */
483 new_expr = force_gimple_operand (unshare_expr (new_expr), &stmts,
484 true, NULL_TREE);
486 gsi_insert_seq_before (gsi_tgt, stmts, GSI_SAME_STMT);
487 replace_exp (use_p, new_expr);
489 if (TREE_CODE (new_expr) == INTEGER_CST
490 && is_gimple_assign (copy))
492 tree rhs = gimple_assign_rhs1 (copy);
494 if (TREE_CODE (rhs) == ADDR_EXPR)
495 recompute_tree_invariant_for_addr_expr (rhs);
498 set_rename (rename_map, old_name, new_expr, region);
501 return changed;
504 /* Duplicates the statements of basic block BB into basic block NEW_BB
505 and compute the new induction variables according to the IV_MAP.
506 GLOOG_ERROR is set when the code generation cannot continue. */
508 static void
509 graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb,
510 rename_map_type *rename_map,
511 vec<tree> iv_map, sese region,
512 bool *gloog_error)
514 gimple_stmt_iterator gsi, gsi_tgt;
515 loop_p loop = bb->loop_father;
517 gsi_tgt = gsi_start_bb (new_bb);
518 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
520 def_operand_p def_p;
521 ssa_op_iter op_iter;
522 gimple *stmt = gsi_stmt (gsi);
523 gimple *copy;
524 tree lhs;
526 /* Do not copy labels or conditions. */
527 if (gimple_code (stmt) == GIMPLE_LABEL
528 || gimple_code (stmt) == GIMPLE_COND)
529 continue;
531 /* Do not copy induction variables. */
532 if (is_gimple_assign (stmt)
533 && (lhs = gimple_assign_lhs (stmt))
534 && TREE_CODE (lhs) == SSA_NAME
535 && is_gimple_reg (lhs)
536 && scev_analyzable_p (lhs, region))
537 continue;
539 /* Do not copy parameters that have been generated in the header of the
540 scop. */
541 if (is_gimple_assign (stmt)
542 && (lhs = gimple_assign_lhs (stmt))
543 && TREE_CODE (lhs) == SSA_NAME
544 && region->parameter_rename_map->get(lhs))
545 continue;
547 /* Create a new copy of STMT and duplicate STMT's virtual
548 operands. */
549 copy = gimple_copy (stmt);
550 gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
552 maybe_duplicate_eh_stmt (copy, stmt);
553 gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
555 /* Create new names for all the definitions created by COPY and
556 add replacement mappings for each new name. */
557 FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
559 tree old_name = DEF_FROM_PTR (def_p);
560 tree new_name = create_new_def_for (old_name, copy, def_p);
561 set_rename (rename_map, old_name, new_name, region);
564 if (rename_uses (copy, rename_map, &gsi_tgt, region, loop, iv_map,
565 gloog_error))
567 gcc_assert (gsi_stmt (gsi_tgt) == copy);
568 fold_stmt_inplace (&gsi_tgt);
571 /* For each SSA_NAME in the parameter_rename_map rename their usage. */
572 ssa_op_iter iter;
573 use_operand_p use_p;
574 if (!is_gimple_debug (copy))
575 FOR_EACH_SSA_USE_OPERAND (use_p, copy, iter, SSA_OP_USE)
577 tree old_name = USE_FROM_PTR (use_p);
579 if (TREE_CODE (old_name) != SSA_NAME
580 || SSA_NAME_IS_DEFAULT_DEF (old_name))
581 continue;
583 tree *new_expr = region->parameter_rename_map->get (old_name);
584 if (!new_expr)
585 continue;
587 replace_exp (use_p, *new_expr);
590 update_stmt (copy);
594 /* Copies BB and includes in the copied BB all the statements that can
595 be reached following the use-def chains from the memory accesses,
596 and returns the next edge following this new block. GLOOG_ERROR is
597 set when the code generation cannot continue. */
599 edge
600 copy_bb_and_scalar_dependences (basic_block bb, sese region,
601 edge next_e, vec<tree> iv_map,
602 bool *gloog_error)
604 basic_block new_bb = split_edge (next_e);
605 rename_map_type rename_map (10);
607 next_e = single_succ_edge (new_bb);
608 graphite_copy_stmts_from_block (bb, new_bb, &rename_map, iv_map, region,
609 gloog_error);
610 remove_phi_nodes (new_bb);
612 return next_e;
615 /* Returns the outermost loop in SCOP that contains BB. */
617 struct loop *
618 outermost_loop_in_sese (sese region, basic_block bb)
620 struct loop *nest;
622 nest = bb->loop_father;
623 while (loop_outer (nest)
624 && loop_in_sese_p (loop_outer (nest), region))
625 nest = loop_outer (nest);
627 return nest;
630 /* Sets the false region of an IF_REGION to REGION. */
632 void
633 if_region_set_false_region (ifsese if_region, sese region)
635 basic_block condition = if_region_get_condition_block (if_region);
636 edge false_edge = get_false_edge_from_guard_bb (condition);
637 basic_block dummy = false_edge->dest;
638 edge entry_region = SESE_ENTRY (region);
639 edge exit_region = SESE_EXIT (region);
640 basic_block before_region = entry_region->src;
641 basic_block last_in_region = exit_region->src;
642 hashval_t hash = htab_hash_pointer (exit_region);
643 loop_exit **slot
644 = current_loops->exits->find_slot_with_hash (exit_region, hash, NO_INSERT);
646 entry_region->flags = false_edge->flags;
647 false_edge->flags = exit_region->flags;
649 redirect_edge_pred (entry_region, condition);
650 redirect_edge_pred (exit_region, before_region);
651 redirect_edge_pred (false_edge, last_in_region);
652 redirect_edge_succ (false_edge, single_succ (dummy));
653 delete_basic_block (dummy);
655 exit_region->flags = EDGE_FALLTHRU;
656 recompute_all_dominators ();
658 SESE_EXIT (region) = false_edge;
660 free (if_region->false_region);
661 if_region->false_region = region;
663 if (slot)
665 struct loop_exit *loop_exit = ggc_cleared_alloc<struct loop_exit> ();
667 memcpy (loop_exit, *((struct loop_exit **) slot), sizeof (struct loop_exit));
668 current_loops->exits->clear_slot (slot);
670 hashval_t hash = htab_hash_pointer (false_edge);
671 slot = current_loops->exits->find_slot_with_hash (false_edge, hash,
672 INSERT);
673 loop_exit->e = false_edge;
674 *slot = loop_exit;
675 false_edge->src->loop_father->exits->next = loop_exit;
679 /* Creates an IFSESE with CONDITION on edge ENTRY. */
681 static ifsese
682 create_if_region_on_edge (edge entry, tree condition)
684 edge e;
685 edge_iterator ei;
686 sese sese_region = XNEW (struct sese_s);
687 sese true_region = XNEW (struct sese_s);
688 sese false_region = XNEW (struct sese_s);
689 ifsese if_region = XNEW (struct ifsese_s);
690 edge exit = create_empty_if_region_on_edge (entry, condition);
692 if_region->region = sese_region;
693 if_region->region->entry = entry;
694 if_region->region->exit = exit;
696 FOR_EACH_EDGE (e, ei, entry->dest->succs)
698 if (e->flags & EDGE_TRUE_VALUE)
700 true_region->entry = e;
701 true_region->exit = single_succ_edge (e->dest);
702 if_region->true_region = true_region;
704 else if (e->flags & EDGE_FALSE_VALUE)
706 false_region->entry = e;
707 false_region->exit = single_succ_edge (e->dest);
708 if_region->false_region = false_region;
712 return if_region;
715 /* Moves REGION in a condition expression:
716 | if (1)
718 | else
719 | REGION;
722 ifsese
723 move_sese_in_condition (sese region)
725 basic_block pred_block = split_edge (SESE_ENTRY (region));
726 ifsese if_region;
728 SESE_ENTRY (region) = single_succ_edge (pred_block);
729 if_region = create_if_region_on_edge (single_pred_edge (pred_block), integer_one_node);
730 if_region_set_false_region (if_region, region);
732 return if_region;
735 /* Replaces the condition of the IF_REGION with CONDITION:
736 | if (CONDITION)
737 | true_region;
738 | else
739 | false_region;
742 void
743 set_ifsese_condition (ifsese if_region, tree condition)
745 sese region = if_region->region;
746 edge entry = region->entry;
747 basic_block bb = entry->dest;
748 gimple *last = last_stmt (bb);
749 gimple_stmt_iterator gsi = gsi_last_bb (bb);
750 gcond *cond_stmt;
752 gcc_assert (gimple_code (last) == GIMPLE_COND);
754 gsi_remove (&gsi, true);
755 gsi = gsi_last_bb (bb);
756 condition = force_gimple_operand_gsi (&gsi, condition, true, NULL,
757 false, GSI_NEW_STMT);
758 cond_stmt = gimple_build_cond_from_tree (condition, NULL_TREE, NULL_TREE);
759 gsi = gsi_last_bb (bb);
760 gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
763 /* Return false if T is completely defined outside REGION. */
765 static bool
766 invariant_in_sese_p_rec (tree t, sese region)
768 ssa_op_iter iter;
769 use_operand_p use_p;
770 if (!defined_in_sese_p (t, region))
771 return true;
773 gimple *stmt = SSA_NAME_DEF_STMT (t);
775 if (gimple_code (stmt) == GIMPLE_PHI
776 || gimple_code (stmt) == GIMPLE_CALL)
777 return false;
779 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
781 tree use = USE_FROM_PTR (use_p);
782 if (!defined_in_sese_p (use, region))
783 continue;
785 if (!invariant_in_sese_p_rec (use, region))
786 return false;
789 return true;
792 /* Returns the scalar evolution of T in REGION. Every variable that
793 is not defined in the REGION is considered a parameter. */
795 tree
796 scalar_evolution_in_region (sese region, loop_p loop, tree t)
798 gimple *def;
799 struct loop *def_loop;
800 basic_block before = block_before_sese (region);
802 /* SCOP parameters. */
803 if (TREE_CODE (t) == SSA_NAME
804 && !defined_in_sese_p (t, region))
805 return t;
807 if (TREE_CODE (t) != SSA_NAME
808 || loop_in_sese_p (loop, region))
809 return instantiate_scev (before, loop,
810 analyze_scalar_evolution (loop, t));
812 def = SSA_NAME_DEF_STMT (t);
813 def_loop = loop_containing_stmt (def);
815 if (loop_in_sese_p (def_loop, region))
817 t = analyze_scalar_evolution (def_loop, t);
818 def_loop = superloop_at_depth (def_loop, loop_depth (loop) + 1);
819 t = compute_overall_effect_of_inner_loop (def_loop, t);
820 return t;
823 if (invariant_in_sese_p_rec (t, region))
824 return t;
826 return instantiate_scev (before, loop, t);