1 /* Single entry single exit control flow regions.
2 Copyright (C) 2008, 2009, 2010, 2011
3 Free Software Foundation, Inc.
4 Contributed by Jan Sjodin <jan.sjodin@amd.com> and
5 Sebastian Pop <sebastian.pop@amd.com>.
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation; either version 3, or (at your option)
14 GCC is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
25 #include "coretypes.h"
26 #include "tree-pretty-print.h"
27 #include "tree-flow.h"
29 #include "tree-chrec.h"
30 #include "tree-data-ref.h"
31 #include "tree-scalar-evolution.h"
32 #include "tree-pass.h"
33 #include "value-prof.h"
36 /* Print to stderr the element ELT. */
39 debug_rename_elt (rename_map_elt elt)
41 fprintf (stderr, "(");
42 print_generic_expr (stderr, elt->old_name, 0);
43 fprintf (stderr, ", ");
44 print_generic_expr (stderr, elt->expr, 0);
45 fprintf (stderr, ")\n");
48 /* Helper function for debug_rename_map. */
51 debug_rename_map_1 (void **slot, void *s ATTRIBUTE_UNUSED)
53 struct rename_map_elt_s *entry = (struct rename_map_elt_s *) *slot;
54 debug_rename_elt (entry);
58 /* Print to stderr all the elements of RENAME_MAP. */
61 debug_rename_map (htab_t rename_map)
63 htab_traverse (rename_map, debug_rename_map_1, NULL);
66 /* Computes a hash function for database element ELT. */
69 rename_map_elt_info (const void *elt)
71 return SSA_NAME_VERSION (((const struct rename_map_elt_s *) elt)->old_name);
74 /* Compares database elements E1 and E2. */
77 eq_rename_map_elts (const void *e1, const void *e2)
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;
82 return (elt1->old_name == elt2->old_name);
87 /* Print to stderr the element ELT. */
90 debug_ivtype_elt (ivtype_map_elt elt)
92 fprintf (stderr, "(%s, ", elt->cloog_iv);
93 print_generic_expr (stderr, elt->type, 0);
94 fprintf (stderr, ")\n");
97 /* Helper function for debug_ivtype_map. */
100 debug_ivtype_map_1 (void **slot, void *s ATTRIBUTE_UNUSED)
102 struct ivtype_map_elt_s *entry = (struct ivtype_map_elt_s *) *slot;
103 debug_ivtype_elt (entry);
107 /* Print to stderr all the elements of MAP. */
110 debug_ivtype_map (htab_t map)
112 htab_traverse (map, debug_ivtype_map_1, NULL);
115 /* Computes a hash function for database element ELT. */
118 ivtype_map_elt_info (const void *elt)
120 return htab_hash_pointer (((const struct ivtype_map_elt_s *) elt)->cloog_iv);
123 /* Compares database elements E1 and E2. */
126 eq_ivtype_map_elts (const void *e1, const void *e2)
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;
131 return (elt1->cloog_iv == elt2->cloog_iv);
136 /* Record LOOP as occuring in REGION. */
139 sese_record_loop (sese region, loop_p loop)
141 if (sese_contains_loop (region, loop))
144 bitmap_set_bit (SESE_LOOPS (region), loop->num);
145 VEC_safe_push (loop_p, heap, SESE_LOOP_NEST (region), loop);
148 /* Build the loop nests contained in REGION. Returns true when the
149 operation was successful. */
152 build_sese_loop_nests (sese region)
156 struct loop *loop0, *loop1;
159 if (bb_in_sese_p (bb, region))
161 struct loop *loop = bb->loop_father;
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);
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)
174 if (VEC_length (loop_p, SESE_LOOP_NEST (region)) == i + 1)
177 loop1 = VEC_index (loop_p, SESE_LOOP_NEST (region), i + 1);
178 if (loop0->num > loop1->num)
180 VEC_replace (loop_p, SESE_LOOP_NEST (region), i, loop1);
181 VEC_replace (loop_p, SESE_LOOP_NEST (region), i + 1, loop0);
186 /* For a USE in BB, if BB is outside REGION, mark the USE in the
190 sese_build_liveouts_use (sese region, bitmap liveouts, basic_block bb,
196 if (TREE_CODE (use) != SSA_NAME)
199 ver = SSA_NAME_VERSION (use);
200 def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
203 || !bb_in_sese_p (def_bb, region)
204 || bb_in_sese_p (bb, region))
207 bitmap_set_bit (liveouts, ver);
210 /* Marks for rewrite all the SSA_NAMES defined in REGION and that are
211 used in BB that is outside of the REGION. */
214 sese_build_liveouts_bb (sese region, bitmap liveouts, basic_block bb)
216 gimple_stmt_iterator bsi;
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));
227 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
229 gimple stmt = gsi_stmt (bsi);
231 if (is_gimple_debug (stmt))
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));
239 /* For a USE in BB, return true if BB is outside REGION and it's not
240 in the LIVEOUTS set. */
243 sese_bad_liveouts_use (sese region, bitmap liveouts, basic_block bb,
249 if (TREE_CODE (use) != SSA_NAME)
252 ver = SSA_NAME_VERSION (use);
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))
259 def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
262 || !bb_in_sese_p (def_bb, region)
263 || bb_in_sese_p (bb, region))
269 /* Reset debug stmts that reference SSA_NAMES defined in REGION that
270 are not marked as liveouts. */
273 sese_reset_debug_liveouts_bb (sese region, bitmap liveouts, basic_block bb)
275 gimple_stmt_iterator bsi;
279 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
281 gimple stmt = gsi_stmt (bsi);
283 if (!is_gimple_debug (stmt))
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)))
290 gimple_debug_bind_reset_value (stmt);
297 /* Build the LIVEOUTS of REGION: the set of variables defined inside
298 and used outside the REGION. */
301 sese_build_liveouts (sese region, bitmap liveouts)
306 sese_build_liveouts_bb (region, liveouts, bb);
307 if (MAY_HAVE_DEBUG_INSNS)
309 sese_reset_debug_liveouts_bb (region, liveouts, bb);
312 /* Builds a new SESE region from edges ENTRY and EXIT. */
315 new_sese (edge entry, edge exit)
317 sese region = XNEW (struct sese_s);
319 SESE_ENTRY (region) = entry;
320 SESE_EXIT (region) = exit;
321 SESE_LOOPS (region) = BITMAP_ALLOC (NULL);
322 SESE_LOOP_NEST (region) = VEC_alloc (loop_p, heap, 3);
323 SESE_ADD_PARAMS (region) = true;
324 SESE_PARAMS (region) = VEC_alloc (tree, heap, 3);
329 /* Deletes REGION. */
332 free_sese (sese region)
334 if (SESE_LOOPS (region))
335 SESE_LOOPS (region) = BITMAP_ALLOC (NULL);
337 VEC_free (tree, heap, SESE_PARAMS (region));
338 VEC_free (loop_p, heap, SESE_LOOP_NEST (region));
343 /* Add exit phis for USE on EXIT. */
346 sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e)
348 gimple phi = create_phi_node (use, exit);
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);
353 add_phi_arg (phi, use, true_e, UNKNOWN_LOCATION);
356 /* Insert in the block BB phi nodes for variables defined in REGION
357 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
359 clause that is at this point empty:
368 sese_insert_phis_for_liveouts (sese region, basic_block bb,
369 edge false_e, edge true_e)
373 bitmap liveouts = BITMAP_ALLOC (NULL);
375 update_ssa (TODO_update_ssa);
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);
382 update_ssa (TODO_update_ssa);
385 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */
388 get_true_edge_from_guard_bb (basic_block bb)
393 FOR_EACH_EDGE (e, ei, bb->succs)
394 if (e->flags & EDGE_TRUE_VALUE)
401 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */
404 get_false_edge_from_guard_bb (basic_block bb)
409 FOR_EACH_EDGE (e, ei, bb->succs)
410 if (!(e->flags & EDGE_TRUE_VALUE))
417 /* Returns the expression associated to OLD_NAME in RENAME_MAP. */
420 get_rename (htab_t rename_map, tree old_name)
422 struct rename_map_elt_s tmp;
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);
430 return ((rename_map_elt) *slot)->expr;
435 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR). */
438 set_rename (htab_t rename_map, tree old_name, tree expr)
440 struct rename_map_elt_s tmp;
443 if (old_name == expr)
446 tmp.old_name = old_name;
447 slot = htab_find_slot (rename_map, &tmp, INSERT);
454 *slot = new_rename_map_elt (old_name, expr);
457 /* Renames the scalar uses of the statement COPY, using the
458 substitution map RENAME_MAP, inserting the gimplification code at
459 GSI_TGT, for the translation REGION, with the original copied
460 statement in LOOP, and using the induction variable renaming map
461 IV_MAP. Returns true when something has been renamed. GLOOG_ERROR
462 is set when the code generation cannot continue. */
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,
471 bool changed = false;
473 if (is_gimple_debug (copy))
475 if (gimple_debug_bind_p (copy))
476 gimple_debug_bind_reset_value (copy);
477 else if (gimple_debug_source_bind_p (copy))
485 FOR_EACH_SSA_USE_OPERAND (use_p, copy, op_iter, SSA_OP_ALL_USES)
487 tree old_name = USE_FROM_PTR (use_p);
491 if (TREE_CODE (old_name) != SSA_NAME
492 || !is_gimple_reg (old_name)
493 || SSA_NAME_IS_DEFAULT_DEF (old_name))
497 new_expr = get_rename (rename_map, old_name);
500 tree type_old_name = TREE_TYPE (old_name);
501 tree type_new_expr = TREE_TYPE (new_expr);
503 if (type_old_name != type_new_expr
504 || (TREE_CODE (new_expr) != SSA_NAME
505 && is_gimple_reg (old_name)))
507 tree var = create_tmp_var (type_old_name, "var");
509 if (type_old_name != type_new_expr)
510 new_expr = fold_convert (type_old_name, new_expr);
512 new_expr = build2 (MODIFY_EXPR, type_old_name, var, new_expr);
513 new_expr = force_gimple_operand (new_expr, &stmts, true, NULL);
514 gsi_insert_seq_before (gsi_tgt, stmts, GSI_SAME_STMT);
517 replace_exp (use_p, new_expr);
521 scev = scalar_evolution_in_region (region, loop, old_name);
523 /* At this point we should know the exact scev for each
524 scalar SSA_NAME used in the scop: all the other scalar
525 SSA_NAMEs should have been translated out of SSA using
526 arrays with one element. */
527 if (chrec_contains_undetermined (scev))
533 new_expr = chrec_apply_map (scev, iv_map);
535 /* The apply should produce an expression tree containing
536 the uses of the new induction variables. We should be
537 able to use new_expr instead of the old_name in the newly
538 generated loop nest. */
539 if (chrec_contains_undetermined (new_expr)
540 || tree_contains_chrecs (new_expr, NULL))
546 /* Replace the old_name with the new_expr. */
547 new_expr = force_gimple_operand (unshare_expr (new_expr), &stmts,
549 gsi_insert_seq_before (gsi_tgt, stmts, GSI_SAME_STMT);
550 replace_exp (use_p, new_expr);
552 if (TREE_CODE (new_expr) == INTEGER_CST
553 && is_gimple_assign (copy))
555 tree rhs = gimple_assign_rhs1 (copy);
557 if (TREE_CODE (rhs) == ADDR_EXPR)
558 recompute_tree_invariant_for_addr_expr (rhs);
561 set_rename (rename_map, old_name, new_expr);
567 /* Duplicates the statements of basic block BB into basic block NEW_BB
568 and compute the new induction variables according to the IV_MAP.
569 GLOOG_ERROR is set when the code generation cannot continue. */
572 graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb,
574 VEC (tree, heap) *iv_map, sese region,
577 gimple_stmt_iterator gsi, gsi_tgt;
578 loop_p loop = bb->loop_father;
580 gsi_tgt = gsi_start_bb (new_bb);
581 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
585 gimple stmt = gsi_stmt (gsi);
589 /* Do not copy labels or conditions. */
590 if (gimple_code (stmt) == GIMPLE_LABEL
591 || gimple_code (stmt) == GIMPLE_COND)
594 /* Do not copy induction variables. */
595 if (is_gimple_assign (stmt)
596 && (lhs = gimple_assign_lhs (stmt))
597 && TREE_CODE (lhs) == SSA_NAME
598 && is_gimple_reg (lhs)
599 && scev_analyzable_p (lhs, region))
602 /* Create a new copy of STMT and duplicate STMT's virtual
604 copy = gimple_copy (stmt);
605 gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
606 mark_sym_for_renaming (gimple_vop (cfun));
608 maybe_duplicate_eh_stmt (copy, stmt);
609 gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
611 /* Create new names for all the definitions created by COPY and
612 add replacement mappings for each new name. */
613 FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
615 tree old_name = DEF_FROM_PTR (def_p);
616 tree new_name = create_new_def_for (old_name, copy, def_p);
617 set_rename (rename_map, old_name, new_name);
620 if (rename_uses (copy, rename_map, &gsi_tgt, region, loop, iv_map,
622 fold_stmt_inplace (copy);
631 /* Copies BB and includes in the copied BB all the statements that can
632 be reached following the use-def chains from the memory accesses,
633 and returns the next edge following this new block. GLOOG_ERROR is
634 set when the code generation cannot continue. */
637 copy_bb_and_scalar_dependences (basic_block bb, sese region,
638 edge next_e, VEC (tree, heap) *iv_map,
641 basic_block new_bb = split_edge (next_e);
642 htab_t rename_map = htab_create (10, rename_map_elt_info,
643 eq_rename_map_elts, free);
645 next_e = single_succ_edge (new_bb);
646 graphite_copy_stmts_from_block (bb, new_bb, rename_map, iv_map, region,
648 remove_phi_nodes (new_bb);
649 htab_delete (rename_map);
654 /* Returns the outermost loop in SCOP that contains BB. */
657 outermost_loop_in_sese (sese region, basic_block bb)
661 nest = bb->loop_father;
662 while (loop_outer (nest)
663 && loop_in_sese_p (loop_outer (nest), region))
664 nest = loop_outer (nest);
669 /* Sets the false region of an IF_REGION to REGION. */
672 if_region_set_false_region (ifsese if_region, sese region)
674 basic_block condition = if_region_get_condition_block (if_region);
675 edge false_edge = get_false_edge_from_guard_bb (condition);
676 basic_block dummy = false_edge->dest;
677 edge entry_region = SESE_ENTRY (region);
678 edge exit_region = SESE_EXIT (region);
679 basic_block before_region = entry_region->src;
680 basic_block last_in_region = exit_region->src;
681 void **slot = htab_find_slot_with_hash (current_loops->exits, exit_region,
682 htab_hash_pointer (exit_region),
685 entry_region->flags = false_edge->flags;
686 false_edge->flags = exit_region->flags;
688 redirect_edge_pred (entry_region, condition);
689 redirect_edge_pred (exit_region, before_region);
690 redirect_edge_pred (false_edge, last_in_region);
691 redirect_edge_succ (false_edge, single_succ (dummy));
692 delete_basic_block (dummy);
694 exit_region->flags = EDGE_FALLTHRU;
695 recompute_all_dominators ();
697 SESE_EXIT (region) = false_edge;
699 free (if_region->false_region);
700 if_region->false_region = region;
704 struct loop_exit *loop_exit = ggc_alloc_cleared_loop_exit ();
706 memcpy (loop_exit, *((struct loop_exit **) slot), sizeof (struct loop_exit));
707 htab_clear_slot (current_loops->exits, slot);
709 slot = htab_find_slot_with_hash (current_loops->exits, false_edge,
710 htab_hash_pointer (false_edge),
712 loop_exit->e = false_edge;
714 false_edge->src->loop_father->exits->next = loop_exit;
718 /* Creates an IFSESE with CONDITION on edge ENTRY. */
721 create_if_region_on_edge (edge entry, tree condition)
725 sese sese_region = XNEW (struct sese_s);
726 sese true_region = XNEW (struct sese_s);
727 sese false_region = XNEW (struct sese_s);
728 ifsese if_region = XNEW (struct ifsese_s);
729 edge exit = create_empty_if_region_on_edge (entry, condition);
731 if_region->region = sese_region;
732 if_region->region->entry = entry;
733 if_region->region->exit = exit;
735 FOR_EACH_EDGE (e, ei, entry->dest->succs)
737 if (e->flags & EDGE_TRUE_VALUE)
739 true_region->entry = e;
740 true_region->exit = single_succ_edge (e->dest);
741 if_region->true_region = true_region;
743 else if (e->flags & EDGE_FALSE_VALUE)
745 false_region->entry = e;
746 false_region->exit = single_succ_edge (e->dest);
747 if_region->false_region = false_region;
754 /* Moves REGION in a condition expression:
762 move_sese_in_condition (sese region)
764 basic_block pred_block = split_edge (SESE_ENTRY (region));
767 SESE_ENTRY (region) = single_succ_edge (pred_block);
768 if_region = create_if_region_on_edge (single_pred_edge (pred_block), integer_one_node);
769 if_region_set_false_region (if_region, region);
774 /* Replaces the condition of the IF_REGION with CONDITION:
782 set_ifsese_condition (ifsese if_region, tree condition)
784 sese region = if_region->region;
785 edge entry = region->entry;
786 basic_block bb = entry->dest;
787 gimple last = last_stmt (bb);
788 gimple_stmt_iterator gsi = gsi_last_bb (bb);
791 gcc_assert (gimple_code (last) == GIMPLE_COND);
793 gsi_remove (&gsi, true);
794 gsi = gsi_last_bb (bb);
795 condition = force_gimple_operand_gsi (&gsi, condition, true, NULL,
796 false, GSI_NEW_STMT);
797 cond_stmt = gimple_build_cond_from_tree (condition, NULL_TREE, NULL_TREE);
798 gsi = gsi_last_bb (bb);
799 gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
802 /* Returns the scalar evolution of T in REGION. Every variable that
803 is not defined in the REGION is considered a parameter. */
806 scalar_evolution_in_region (sese region, loop_p loop, tree t)
809 struct loop *def_loop;
810 basic_block before = block_before_sese (region);
812 /* SCOP parameters. */
813 if (TREE_CODE (t) == SSA_NAME
814 && !defined_in_sese_p (t, region))
817 if (TREE_CODE (t) != SSA_NAME
818 || loop_in_sese_p (loop, region))
819 return instantiate_scev (before, loop,
820 analyze_scalar_evolution (loop, t));
822 def = SSA_NAME_DEF_STMT (t);
823 def_loop = loop_containing_stmt (def);
825 if (loop_in_sese_p (def_loop, region))
827 t = analyze_scalar_evolution (def_loop, t);
828 def_loop = superloop_at_depth (def_loop, loop_depth (loop) + 1);
829 t = compute_overall_effect_of_inner_loop (def_loop, t);
833 return instantiate_scev (before, loop, t);