gcc/
[official-gcc.git] / gcc / sese.c
blob2ba2f980ca0ee0a6b62fff8fe5ba55c5b8c6d211
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 "symtab.h"
27 #include "options.h"
28 #include "tree.h"
29 #include "fold-const.h"
30 #include "tree-pretty-print.h"
31 #include "predict.h"
32 #include "tm.h"
33 #include "hard-reg-set.h"
34 #include "function.h"
35 #include "dominance.h"
36 #include "cfg.h"
37 #include "basic-block.h"
38 #include "tree-ssa-alias.h"
39 #include "internal-fn.h"
40 #include "gimple-fold.h"
41 #include "tree-eh.h"
42 #include "gimple-expr.h"
43 #include "gimple.h"
44 #include "gimplify.h"
45 #include "gimple-iterator.h"
46 #include "gimplify-me.h"
47 #include "gimple-ssa.h"
48 #include "tree-cfg.h"
49 #include "tree-phinodes.h"
50 #include "ssa-iterators.h"
51 #include "stringpool.h"
52 #include "tree-ssanames.h"
53 #include "tree-ssa-loop.h"
54 #include "tree-into-ssa.h"
55 #include "cfgloop.h"
56 #include "tree-chrec.h"
57 #include "tree-data-ref.h"
58 #include "tree-scalar-evolution.h"
59 #include "tree-pass.h"
60 #include "value-prof.h"
61 #include "sese.h"
62 #include "tree-ssa-propagate.h"
63 #include "tree-hash-traits.h"
65 /* Helper function for debug_rename_map. */
67 bool
68 debug_rename_map_1 (tree_node *const &old_name, tree_node *const &expr,
69 void *)
71 fprintf (stderr, "(");
72 print_generic_expr (stderr, old_name, 0);
73 fprintf (stderr, ", ");
74 print_generic_expr (stderr, expr, 0);
75 fprintf (stderr, ")\n");
76 return true;
79 typedef hash_map<tree_ssa_name_hash, tree> rename_map_type;
82 /* Print to stderr all the elements of RENAME_MAP. */
84 DEBUG_FUNCTION void
85 debug_rename_map (rename_map_type *rename_map)
87 rename_map->traverse <void *, debug_rename_map_1> (NULL);
91 /* Record LOOP as occurring in REGION. */
93 static void
94 sese_record_loop (sese region, loop_p loop)
96 if (sese_contains_loop (region, loop))
97 return;
99 bitmap_set_bit (SESE_LOOPS (region), loop->num);
100 SESE_LOOP_NEST (region).safe_push (loop);
103 /* Build the loop nests contained in REGION. Returns true when the
104 operation was successful. */
106 void
107 build_sese_loop_nests (sese region)
109 unsigned i;
110 basic_block bb;
111 struct loop *loop0, *loop1;
113 FOR_EACH_BB_FN (bb, cfun)
114 if (bb_in_sese_p (bb, region))
116 struct loop *loop = bb->loop_father;
118 /* Only add loops if they are completely contained in the SCoP. */
119 if (loop->header == bb
120 && bb_in_sese_p (loop->latch, region))
121 sese_record_loop (region, loop);
124 /* Make sure that the loops in the SESE_LOOP_NEST are ordered. It
125 can be the case that an inner loop is inserted before an outer
126 loop. To avoid this, semi-sort once. */
127 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region), i, loop0)
129 if (SESE_LOOP_NEST (region).length () == i + 1)
130 break;
132 loop1 = SESE_LOOP_NEST (region)[i + 1];
133 if (loop0->num > loop1->num)
135 SESE_LOOP_NEST (region)[i] = loop1;
136 SESE_LOOP_NEST (region)[i + 1] = loop0;
141 /* For a USE in BB, if BB is outside REGION, mark the USE in the
142 LIVEOUTS set. */
144 static void
145 sese_build_liveouts_use (sese region, bitmap liveouts, basic_block bb,
146 tree use)
148 unsigned ver;
149 basic_block def_bb;
151 if (TREE_CODE (use) != SSA_NAME)
152 return;
154 ver = SSA_NAME_VERSION (use);
155 def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
157 if (!def_bb
158 || !bb_in_sese_p (def_bb, region)
159 || bb_in_sese_p (bb, region))
160 return;
162 bitmap_set_bit (liveouts, ver);
165 /* Marks for rewrite all the SSA_NAMES defined in REGION and that are
166 used in BB that is outside of the REGION. */
168 static void
169 sese_build_liveouts_bb (sese region, bitmap liveouts, basic_block bb)
171 edge e;
172 edge_iterator ei;
173 ssa_op_iter iter;
174 use_operand_p use_p;
176 FOR_EACH_EDGE (e, ei, bb->succs)
177 for (gphi_iterator bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi);
178 gsi_next (&bsi))
179 sese_build_liveouts_use (region, liveouts, bb,
180 PHI_ARG_DEF_FROM_EDGE (bsi.phi (), e));
182 for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);
183 gsi_next (&bsi))
185 gimple stmt = gsi_stmt (bsi);
187 if (is_gimple_debug (stmt))
188 continue;
190 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
191 sese_build_liveouts_use (region, liveouts, bb, USE_FROM_PTR (use_p));
195 /* For a USE in BB, return true if BB is outside REGION and it's not
196 in the LIVEOUTS set. */
198 static bool
199 sese_bad_liveouts_use (sese region, bitmap liveouts, basic_block bb,
200 tree use)
202 unsigned ver;
203 basic_block def_bb;
205 if (TREE_CODE (use) != SSA_NAME)
206 return false;
208 ver = SSA_NAME_VERSION (use);
210 /* If it's in liveouts, the variable will get a new PHI node, and
211 the debug use will be properly adjusted. */
212 if (bitmap_bit_p (liveouts, ver))
213 return false;
215 def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
217 if (!def_bb
218 || !bb_in_sese_p (def_bb, region)
219 || bb_in_sese_p (bb, region))
220 return false;
222 return true;
225 /* Reset debug stmts that reference SSA_NAMES defined in REGION that
226 are not marked as liveouts. */
228 static void
229 sese_reset_debug_liveouts_bb (sese region, bitmap liveouts, basic_block bb)
231 gimple_stmt_iterator bsi;
232 ssa_op_iter iter;
233 use_operand_p use_p;
235 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
237 gimple stmt = gsi_stmt (bsi);
239 if (!is_gimple_debug (stmt))
240 continue;
242 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
243 if (sese_bad_liveouts_use (region, liveouts, bb,
244 USE_FROM_PTR (use_p)))
246 gimple_debug_bind_reset_value (stmt);
247 update_stmt (stmt);
248 break;
253 /* Build the LIVEOUTS of REGION: the set of variables defined inside
254 and used outside the REGION. */
256 static void
257 sese_build_liveouts (sese region, bitmap liveouts)
259 basic_block bb;
261 FOR_EACH_BB_FN (bb, cfun)
262 sese_build_liveouts_bb (region, liveouts, bb);
263 if (MAY_HAVE_DEBUG_STMTS)
264 FOR_EACH_BB_FN (bb, cfun)
265 sese_reset_debug_liveouts_bb (region, liveouts, bb);
268 /* Builds a new SESE region from edges ENTRY and EXIT. */
270 sese
271 new_sese (edge entry, edge exit)
273 sese region = XNEW (struct sese_s);
275 SESE_ENTRY (region) = entry;
276 SESE_EXIT (region) = exit;
277 SESE_LOOPS (region) = BITMAP_ALLOC (NULL);
278 SESE_LOOP_NEST (region).create (3);
279 SESE_ADD_PARAMS (region) = true;
280 SESE_PARAMS (region).create (3);
282 return region;
285 /* Deletes REGION. */
287 void
288 free_sese (sese region)
290 if (SESE_LOOPS (region))
291 SESE_LOOPS (region) = BITMAP_ALLOC (NULL);
293 SESE_PARAMS (region).release ();
294 SESE_LOOP_NEST (region).release ();
296 XDELETE (region);
299 /* Add exit phis for USE on EXIT. */
301 static void
302 sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e)
304 gphi *phi = create_phi_node (NULL_TREE, exit);
305 create_new_def_for (use, phi, gimple_phi_result_ptr (phi));
306 add_phi_arg (phi, use, false_e, UNKNOWN_LOCATION);
307 add_phi_arg (phi, use, true_e, UNKNOWN_LOCATION);
310 /* Insert in the block BB phi nodes for variables defined in REGION
311 and used outside the REGION. The code generation moves REGION in
312 the else clause of an "if (1)" and generates code in the then
313 clause that is at this point empty:
315 | if (1)
316 | empty;
317 | else
318 | REGION;
321 void
322 sese_insert_phis_for_liveouts (sese region, basic_block bb,
323 edge false_e, edge true_e)
325 unsigned i;
326 bitmap_iterator bi;
327 bitmap liveouts = BITMAP_ALLOC (NULL);
329 update_ssa (TODO_update_ssa);
331 sese_build_liveouts (region, liveouts);
332 EXECUTE_IF_SET_IN_BITMAP (liveouts, 0, i, bi)
333 sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e);
334 BITMAP_FREE (liveouts);
336 update_ssa (TODO_update_ssa);
339 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */
341 edge
342 get_true_edge_from_guard_bb (basic_block bb)
344 edge e;
345 edge_iterator ei;
347 FOR_EACH_EDGE (e, ei, bb->succs)
348 if (e->flags & EDGE_TRUE_VALUE)
349 return e;
351 gcc_unreachable ();
352 return NULL;
355 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */
357 edge
358 get_false_edge_from_guard_bb (basic_block bb)
360 edge e;
361 edge_iterator ei;
363 FOR_EACH_EDGE (e, ei, bb->succs)
364 if (!(e->flags & EDGE_TRUE_VALUE))
365 return e;
367 gcc_unreachable ();
368 return NULL;
371 /* Returns the expression associated to OLD_NAME in RENAME_MAP. */
373 static tree
374 get_rename (rename_map_type *rename_map, tree old_name)
376 gcc_assert (TREE_CODE (old_name) == SSA_NAME);
377 tree *expr = rename_map->get (old_name);
378 if (expr)
379 return *expr;
381 return NULL_TREE;
384 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR). */
386 static void
387 set_rename (rename_map_type *rename_map, tree old_name, tree expr)
389 if (old_name == expr)
390 return;
392 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);
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 /* Create a new copy of STMT and duplicate STMT's virtual
540 operands. */
541 copy = gimple_copy (stmt);
542 gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
544 maybe_duplicate_eh_stmt (copy, stmt);
545 gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
547 /* Create new names for all the definitions created by COPY and
548 add replacement mappings for each new name. */
549 FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
551 tree old_name = DEF_FROM_PTR (def_p);
552 tree new_name = create_new_def_for (old_name, copy, def_p);
553 set_rename (rename_map, old_name, new_name);
556 if (rename_uses (copy, rename_map, &gsi_tgt, region, loop, iv_map,
557 gloog_error))
559 gcc_assert (gsi_stmt (gsi_tgt) == copy);
560 fold_stmt_inplace (&gsi_tgt);
563 update_stmt (copy);
567 /* Copies BB and includes in the copied BB all the statements that can
568 be reached following the use-def chains from the memory accesses,
569 and returns the next edge following this new block. GLOOG_ERROR is
570 set when the code generation cannot continue. */
572 edge
573 copy_bb_and_scalar_dependences (basic_block bb, sese region,
574 edge next_e, vec<tree> iv_map,
575 bool *gloog_error)
577 basic_block new_bb = split_edge (next_e);
578 rename_map_type rename_map (10);
580 next_e = single_succ_edge (new_bb);
581 graphite_copy_stmts_from_block (bb, new_bb, &rename_map, iv_map, region,
582 gloog_error);
583 remove_phi_nodes (new_bb);
585 return next_e;
588 /* Returns the outermost loop in SCOP that contains BB. */
590 struct loop *
591 outermost_loop_in_sese (sese region, basic_block bb)
593 struct loop *nest;
595 nest = bb->loop_father;
596 while (loop_outer (nest)
597 && loop_in_sese_p (loop_outer (nest), region))
598 nest = loop_outer (nest);
600 return nest;
603 /* Sets the false region of an IF_REGION to REGION. */
605 void
606 if_region_set_false_region (ifsese if_region, sese region)
608 basic_block condition = if_region_get_condition_block (if_region);
609 edge false_edge = get_false_edge_from_guard_bb (condition);
610 basic_block dummy = false_edge->dest;
611 edge entry_region = SESE_ENTRY (region);
612 edge exit_region = SESE_EXIT (region);
613 basic_block before_region = entry_region->src;
614 basic_block last_in_region = exit_region->src;
615 hashval_t hash = htab_hash_pointer (exit_region);
616 loop_exit **slot
617 = current_loops->exits->find_slot_with_hash (exit_region, hash, NO_INSERT);
619 entry_region->flags = false_edge->flags;
620 false_edge->flags = exit_region->flags;
622 redirect_edge_pred (entry_region, condition);
623 redirect_edge_pred (exit_region, before_region);
624 redirect_edge_pred (false_edge, last_in_region);
625 redirect_edge_succ (false_edge, single_succ (dummy));
626 delete_basic_block (dummy);
628 exit_region->flags = EDGE_FALLTHRU;
629 recompute_all_dominators ();
631 SESE_EXIT (region) = false_edge;
633 free (if_region->false_region);
634 if_region->false_region = region;
636 if (slot)
638 struct loop_exit *loop_exit = ggc_cleared_alloc<struct loop_exit> ();
640 memcpy (loop_exit, *((struct loop_exit **) slot), sizeof (struct loop_exit));
641 current_loops->exits->clear_slot (slot);
643 hashval_t hash = htab_hash_pointer (false_edge);
644 slot = current_loops->exits->find_slot_with_hash (false_edge, hash,
645 INSERT);
646 loop_exit->e = false_edge;
647 *slot = loop_exit;
648 false_edge->src->loop_father->exits->next = loop_exit;
652 /* Creates an IFSESE with CONDITION on edge ENTRY. */
654 static ifsese
655 create_if_region_on_edge (edge entry, tree condition)
657 edge e;
658 edge_iterator ei;
659 sese sese_region = XNEW (struct sese_s);
660 sese true_region = XNEW (struct sese_s);
661 sese false_region = XNEW (struct sese_s);
662 ifsese if_region = XNEW (struct ifsese_s);
663 edge exit = create_empty_if_region_on_edge (entry, condition);
665 if_region->region = sese_region;
666 if_region->region->entry = entry;
667 if_region->region->exit = exit;
669 FOR_EACH_EDGE (e, ei, entry->dest->succs)
671 if (e->flags & EDGE_TRUE_VALUE)
673 true_region->entry = e;
674 true_region->exit = single_succ_edge (e->dest);
675 if_region->true_region = true_region;
677 else if (e->flags & EDGE_FALSE_VALUE)
679 false_region->entry = e;
680 false_region->exit = single_succ_edge (e->dest);
681 if_region->false_region = false_region;
685 return if_region;
688 /* Moves REGION in a condition expression:
689 | if (1)
691 | else
692 | REGION;
695 ifsese
696 move_sese_in_condition (sese region)
698 basic_block pred_block = split_edge (SESE_ENTRY (region));
699 ifsese if_region;
701 SESE_ENTRY (region) = single_succ_edge (pred_block);
702 if_region = create_if_region_on_edge (single_pred_edge (pred_block), integer_one_node);
703 if_region_set_false_region (if_region, region);
705 return if_region;
708 /* Replaces the condition of the IF_REGION with CONDITION:
709 | if (CONDITION)
710 | true_region;
711 | else
712 | false_region;
715 void
716 set_ifsese_condition (ifsese if_region, tree condition)
718 sese region = if_region->region;
719 edge entry = region->entry;
720 basic_block bb = entry->dest;
721 gimple last = last_stmt (bb);
722 gimple_stmt_iterator gsi = gsi_last_bb (bb);
723 gcond *cond_stmt;
725 gcc_assert (gimple_code (last) == GIMPLE_COND);
727 gsi_remove (&gsi, true);
728 gsi = gsi_last_bb (bb);
729 condition = force_gimple_operand_gsi (&gsi, condition, true, NULL,
730 false, GSI_NEW_STMT);
731 cond_stmt = gimple_build_cond_from_tree (condition, NULL_TREE, NULL_TREE);
732 gsi = gsi_last_bb (bb);
733 gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
736 /* Returns the scalar evolution of T in REGION. Every variable that
737 is not defined in the REGION is considered a parameter. */
739 tree
740 scalar_evolution_in_region (sese region, loop_p loop, tree t)
742 gimple def;
743 struct loop *def_loop;
744 basic_block before = block_before_sese (region);
746 /* SCOP parameters. */
747 if (TREE_CODE (t) == SSA_NAME
748 && !defined_in_sese_p (t, region))
749 return t;
751 if (TREE_CODE (t) != SSA_NAME
752 || loop_in_sese_p (loop, region))
753 return instantiate_scev (before, loop,
754 analyze_scalar_evolution (loop, t));
756 def = SSA_NAME_DEF_STMT (t);
757 def_loop = loop_containing_stmt (def);
759 if (loop_in_sese_p (def_loop, region))
761 t = analyze_scalar_evolution (def_loop, t);
762 def_loop = superloop_at_depth (def_loop, loop_depth (loop) + 1);
763 t = compute_overall_effect_of_inner_loop (def_loop, t);
764 return t;
766 else
767 return instantiate_scev (before, loop, t);