1 /* Single entry single exit control flow regions.
2 Copyright (C) 2008-2013 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)
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/>. */
24 #include "coretypes.h"
25 #include "hash-table.h"
27 #include "tree-pretty-print.h"
29 #include "gimple-ssa.h"
31 #include "tree-phinodes.h"
32 #include "ssa-iterators.h"
33 #include "tree-ssanames.h"
34 #include "tree-ssa-loop.h"
35 #include "tree-into-ssa.h"
37 #include "tree-chrec.h"
38 #include "tree-data-ref.h"
39 #include "tree-scalar-evolution.h"
40 #include "tree-pass.h"
41 #include "value-prof.h"
43 #include "tree-ssa-propagate.h"
45 /* Print to stderr the element ELT. */
48 debug_rename_elt (rename_map_elt elt
)
50 fprintf (stderr
, "(");
51 print_generic_expr (stderr
, elt
->old_name
, 0);
52 fprintf (stderr
, ", ");
53 print_generic_expr (stderr
, elt
->expr
, 0);
54 fprintf (stderr
, ")\n");
57 /* Helper function for debug_rename_map. */
60 debug_rename_map_1 (rename_map_elt_s
**slot
, void *s ATTRIBUTE_UNUSED
)
62 struct rename_map_elt_s
*entry
= *slot
;
63 debug_rename_elt (entry
);
68 /* Hashtable helpers. */
70 struct rename_map_hasher
: typed_free_remove
<rename_map_elt_s
>
72 typedef rename_map_elt_s value_type
;
73 typedef rename_map_elt_s compare_type
;
74 static inline hashval_t
hash (const value_type
*);
75 static inline bool equal (const value_type
*, const compare_type
*);
78 /* Computes a hash function for database element ELT. */
81 rename_map_hasher::hash (const value_type
*elt
)
83 return SSA_NAME_VERSION (elt
->old_name
);
86 /* Compares database elements E1 and E2. */
89 rename_map_hasher::equal (const value_type
*elt1
, const compare_type
*elt2
)
91 return (elt1
->old_name
== elt2
->old_name
);
94 typedef hash_table
<rename_map_hasher
> rename_map_type
;
97 /* Print to stderr all the elements of RENAME_MAP. */
100 debug_rename_map (rename_map_type rename_map
)
102 rename_map
.traverse
<void *, debug_rename_map_1
> (NULL
);
105 /* Computes a hash function for database element ELT. */
108 rename_map_elt_info (const void *elt
)
110 return SSA_NAME_VERSION (((const struct rename_map_elt_s
*) elt
)->old_name
);
113 /* Compares database elements E1 and E2. */
116 eq_rename_map_elts (const void *e1
, const void *e2
)
118 const struct rename_map_elt_s
*elt1
= (const struct rename_map_elt_s
*) e1
;
119 const struct rename_map_elt_s
*elt2
= (const struct rename_map_elt_s
*) e2
;
121 return (elt1
->old_name
== elt2
->old_name
);
126 /* Record LOOP as occurring in REGION. */
129 sese_record_loop (sese region
, loop_p loop
)
131 if (sese_contains_loop (region
, loop
))
134 bitmap_set_bit (SESE_LOOPS (region
), loop
->num
);
135 SESE_LOOP_NEST (region
).safe_push (loop
);
138 /* Build the loop nests contained in REGION. Returns true when the
139 operation was successful. */
142 build_sese_loop_nests (sese region
)
146 struct loop
*loop0
, *loop1
;
149 if (bb_in_sese_p (bb
, region
))
151 struct loop
*loop
= bb
->loop_father
;
153 /* Only add loops if they are completely contained in the SCoP. */
154 if (loop
->header
== bb
155 && bb_in_sese_p (loop
->latch
, region
))
156 sese_record_loop (region
, loop
);
159 /* Make sure that the loops in the SESE_LOOP_NEST are ordered. It
160 can be the case that an inner loop is inserted before an outer
161 loop. To avoid this, semi-sort once. */
162 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop0
)
164 if (SESE_LOOP_NEST (region
).length () == i
+ 1)
167 loop1
= SESE_LOOP_NEST (region
)[i
+ 1];
168 if (loop0
->num
> loop1
->num
)
170 SESE_LOOP_NEST (region
)[i
] = loop1
;
171 SESE_LOOP_NEST (region
)[i
+ 1] = loop0
;
176 /* For a USE in BB, if BB is outside REGION, mark the USE in the
180 sese_build_liveouts_use (sese region
, bitmap liveouts
, basic_block bb
,
186 if (TREE_CODE (use
) != SSA_NAME
)
189 ver
= SSA_NAME_VERSION (use
);
190 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (use
));
193 || !bb_in_sese_p (def_bb
, region
)
194 || bb_in_sese_p (bb
, region
))
197 bitmap_set_bit (liveouts
, ver
);
200 /* Marks for rewrite all the SSA_NAMES defined in REGION and that are
201 used in BB that is outside of the REGION. */
204 sese_build_liveouts_bb (sese region
, bitmap liveouts
, basic_block bb
)
206 gimple_stmt_iterator bsi
;
212 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
213 for (bsi
= gsi_start_phis (e
->dest
); !gsi_end_p (bsi
); gsi_next (&bsi
))
214 sese_build_liveouts_use (region
, liveouts
, bb
,
215 PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi
), e
));
217 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
219 gimple stmt
= gsi_stmt (bsi
);
221 if (is_gimple_debug (stmt
))
224 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
225 sese_build_liveouts_use (region
, liveouts
, bb
, USE_FROM_PTR (use_p
));
229 /* For a USE in BB, return true if BB is outside REGION and it's not
230 in the LIVEOUTS set. */
233 sese_bad_liveouts_use (sese region
, bitmap liveouts
, basic_block bb
,
239 if (TREE_CODE (use
) != SSA_NAME
)
242 ver
= SSA_NAME_VERSION (use
);
244 /* If it's in liveouts, the variable will get a new PHI node, and
245 the debug use will be properly adjusted. */
246 if (bitmap_bit_p (liveouts
, ver
))
249 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (use
));
252 || !bb_in_sese_p (def_bb
, region
)
253 || bb_in_sese_p (bb
, region
))
259 /* Reset debug stmts that reference SSA_NAMES defined in REGION that
260 are not marked as liveouts. */
263 sese_reset_debug_liveouts_bb (sese region
, bitmap liveouts
, basic_block bb
)
265 gimple_stmt_iterator bsi
;
269 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
271 gimple stmt
= gsi_stmt (bsi
);
273 if (!is_gimple_debug (stmt
))
276 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
277 if (sese_bad_liveouts_use (region
, liveouts
, bb
,
278 USE_FROM_PTR (use_p
)))
280 gimple_debug_bind_reset_value (stmt
);
287 /* Build the LIVEOUTS of REGION: the set of variables defined inside
288 and used outside the REGION. */
291 sese_build_liveouts (sese region
, bitmap liveouts
)
296 sese_build_liveouts_bb (region
, liveouts
, bb
);
297 if (MAY_HAVE_DEBUG_STMTS
)
299 sese_reset_debug_liveouts_bb (region
, liveouts
, bb
);
302 /* Builds a new SESE region from edges ENTRY and EXIT. */
305 new_sese (edge entry
, edge exit
)
307 sese region
= XNEW (struct sese_s
);
309 SESE_ENTRY (region
) = entry
;
310 SESE_EXIT (region
) = exit
;
311 SESE_LOOPS (region
) = BITMAP_ALLOC (NULL
);
312 SESE_LOOP_NEST (region
).create (3);
313 SESE_ADD_PARAMS (region
) = true;
314 SESE_PARAMS (region
).create (3);
319 /* Deletes REGION. */
322 free_sese (sese region
)
324 if (SESE_LOOPS (region
))
325 SESE_LOOPS (region
) = BITMAP_ALLOC (NULL
);
327 SESE_PARAMS (region
).release ();
328 SESE_LOOP_NEST (region
).release ();
333 /* Add exit phis for USE on EXIT. */
336 sese_add_exit_phis_edge (basic_block exit
, tree use
, edge false_e
, edge true_e
)
338 gimple phi
= create_phi_node (NULL_TREE
, exit
);
339 create_new_def_for (use
, phi
, gimple_phi_result_ptr (phi
));
340 add_phi_arg (phi
, use
, false_e
, UNKNOWN_LOCATION
);
341 add_phi_arg (phi
, use
, true_e
, UNKNOWN_LOCATION
);
344 /* Insert in the block BB phi nodes for variables defined in REGION
345 and used outside the REGION. The code generation moves REGION in
346 the else clause of an "if (1)" and generates code in the then
347 clause that is at this point empty:
356 sese_insert_phis_for_liveouts (sese region
, basic_block bb
,
357 edge false_e
, edge true_e
)
361 bitmap liveouts
= BITMAP_ALLOC (NULL
);
363 update_ssa (TODO_update_ssa
);
365 sese_build_liveouts (region
, liveouts
);
366 EXECUTE_IF_SET_IN_BITMAP (liveouts
, 0, i
, bi
)
367 sese_add_exit_phis_edge (bb
, ssa_name (i
), false_e
, true_e
);
368 BITMAP_FREE (liveouts
);
370 update_ssa (TODO_update_ssa
);
373 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */
376 get_true_edge_from_guard_bb (basic_block bb
)
381 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
382 if (e
->flags
& EDGE_TRUE_VALUE
)
389 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */
392 get_false_edge_from_guard_bb (basic_block bb
)
397 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
398 if (!(e
->flags
& EDGE_TRUE_VALUE
))
405 /* Returns the expression associated to OLD_NAME in RENAME_MAP. */
408 get_rename (rename_map_type rename_map
, tree old_name
)
410 struct rename_map_elt_s tmp
;
411 rename_map_elt_s
**slot
;
413 gcc_assert (TREE_CODE (old_name
) == SSA_NAME
);
414 tmp
.old_name
= old_name
;
415 slot
= rename_map
.find_slot (&tmp
, NO_INSERT
);
418 return (*slot
)->expr
;
423 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR). */
426 set_rename (rename_map_type rename_map
, tree old_name
, tree expr
)
428 struct rename_map_elt_s tmp
;
429 rename_map_elt_s
**slot
;
431 if (old_name
== expr
)
434 tmp
.old_name
= old_name
;
435 slot
= rename_map
.find_slot (&tmp
, INSERT
);
442 *slot
= new_rename_map_elt (old_name
, expr
);
445 /* Renames the scalar uses of the statement COPY, using the
446 substitution map RENAME_MAP, inserting the gimplification code at
447 GSI_TGT, for the translation REGION, with the original copied
448 statement in LOOP, and using the induction variable renaming map
449 IV_MAP. Returns true when something has been renamed. GLOOG_ERROR
450 is set when the code generation cannot continue. */
453 rename_uses (gimple copy
, rename_map_type rename_map
,
454 gimple_stmt_iterator
*gsi_tgt
,
455 sese region
, loop_p loop
, vec
<tree
> iv_map
,
460 bool changed
= false;
462 if (is_gimple_debug (copy
))
464 if (gimple_debug_bind_p (copy
))
465 gimple_debug_bind_reset_value (copy
);
466 else if (gimple_debug_source_bind_p (copy
))
474 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, op_iter
, SSA_OP_USE
)
476 tree old_name
= USE_FROM_PTR (use_p
);
480 if (TREE_CODE (old_name
) != SSA_NAME
481 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
485 new_expr
= get_rename (rename_map
, old_name
);
488 tree type_old_name
= TREE_TYPE (old_name
);
489 tree type_new_expr
= TREE_TYPE (new_expr
);
491 if (type_old_name
!= type_new_expr
492 || TREE_CODE (new_expr
) != SSA_NAME
)
494 tree var
= create_tmp_var (type_old_name
, "var");
496 if (!useless_type_conversion_p (type_old_name
, type_new_expr
))
497 new_expr
= fold_convert (type_old_name
, new_expr
);
499 new_expr
= force_gimple_operand (new_expr
, &stmts
, true, var
);
500 gsi_insert_seq_before (gsi_tgt
, stmts
, GSI_SAME_STMT
);
503 replace_exp (use_p
, new_expr
);
507 scev
= scalar_evolution_in_region (region
, loop
, old_name
);
509 /* At this point we should know the exact scev for each
510 scalar SSA_NAME used in the scop: all the other scalar
511 SSA_NAMEs should have been translated out of SSA using
512 arrays with one element. */
513 if (chrec_contains_undetermined (scev
))
516 new_expr
= build_zero_cst (TREE_TYPE (old_name
));
519 new_expr
= chrec_apply_map (scev
, iv_map
);
521 /* The apply should produce an expression tree containing
522 the uses of the new induction variables. We should be
523 able to use new_expr instead of the old_name in the newly
524 generated loop nest. */
525 if (chrec_contains_undetermined (new_expr
)
526 || tree_contains_chrecs (new_expr
, NULL
))
529 new_expr
= build_zero_cst (TREE_TYPE (old_name
));
532 /* Replace the old_name with the new_expr. */
533 new_expr
= force_gimple_operand (unshare_expr (new_expr
), &stmts
,
536 gsi_insert_seq_before (gsi_tgt
, stmts
, GSI_SAME_STMT
);
537 replace_exp (use_p
, new_expr
);
539 if (TREE_CODE (new_expr
) == INTEGER_CST
540 && is_gimple_assign (copy
))
542 tree rhs
= gimple_assign_rhs1 (copy
);
544 if (TREE_CODE (rhs
) == ADDR_EXPR
)
545 recompute_tree_invariant_for_addr_expr (rhs
);
548 set_rename (rename_map
, old_name
, new_expr
);
554 /* Duplicates the statements of basic block BB into basic block NEW_BB
555 and compute the new induction variables according to the IV_MAP.
556 GLOOG_ERROR is set when the code generation cannot continue. */
559 graphite_copy_stmts_from_block (basic_block bb
, basic_block new_bb
,
560 rename_map_type rename_map
,
561 vec
<tree
> iv_map
, sese region
,
564 gimple_stmt_iterator gsi
, gsi_tgt
;
565 loop_p loop
= bb
->loop_father
;
567 gsi_tgt
= gsi_start_bb (new_bb
);
568 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
572 gimple stmt
= gsi_stmt (gsi
);
576 /* Do not copy labels or conditions. */
577 if (gimple_code (stmt
) == GIMPLE_LABEL
578 || gimple_code (stmt
) == GIMPLE_COND
)
581 /* Do not copy induction variables. */
582 if (is_gimple_assign (stmt
)
583 && (lhs
= gimple_assign_lhs (stmt
))
584 && TREE_CODE (lhs
) == SSA_NAME
585 && is_gimple_reg (lhs
)
586 && scev_analyzable_p (lhs
, region
))
589 /* Create a new copy of STMT and duplicate STMT's virtual
591 copy
= gimple_copy (stmt
);
592 gsi_insert_after (&gsi_tgt
, copy
, GSI_NEW_STMT
);
594 maybe_duplicate_eh_stmt (copy
, stmt
);
595 gimple_duplicate_stmt_histograms (cfun
, copy
, cfun
, stmt
);
597 /* Create new names for all the definitions created by COPY and
598 add replacement mappings for each new name. */
599 FOR_EACH_SSA_DEF_OPERAND (def_p
, copy
, op_iter
, SSA_OP_ALL_DEFS
)
601 tree old_name
= DEF_FROM_PTR (def_p
);
602 tree new_name
= create_new_def_for (old_name
, copy
, def_p
);
603 set_rename (rename_map
, old_name
, new_name
);
606 if (rename_uses (copy
, rename_map
, &gsi_tgt
, region
, loop
, iv_map
,
609 gcc_assert (gsi_stmt (gsi_tgt
) == copy
);
610 fold_stmt_inplace (&gsi_tgt
);
617 /* Copies BB and includes in the copied BB all the statements that can
618 be reached following the use-def chains from the memory accesses,
619 and returns the next edge following this new block. GLOOG_ERROR is
620 set when the code generation cannot continue. */
623 copy_bb_and_scalar_dependences (basic_block bb
, sese region
,
624 edge next_e
, vec
<tree
> iv_map
,
627 basic_block new_bb
= split_edge (next_e
);
628 rename_map_type rename_map
;
629 rename_map
.create (10);
631 next_e
= single_succ_edge (new_bb
);
632 graphite_copy_stmts_from_block (bb
, new_bb
, rename_map
, iv_map
, region
,
634 remove_phi_nodes (new_bb
);
635 rename_map
.dispose ();
640 /* Returns the outermost loop in SCOP that contains BB. */
643 outermost_loop_in_sese (sese region
, basic_block bb
)
647 nest
= bb
->loop_father
;
648 while (loop_outer (nest
)
649 && loop_in_sese_p (loop_outer (nest
), region
))
650 nest
= loop_outer (nest
);
655 /* Sets the false region of an IF_REGION to REGION. */
658 if_region_set_false_region (ifsese if_region
, sese region
)
660 basic_block condition
= if_region_get_condition_block (if_region
);
661 edge false_edge
= get_false_edge_from_guard_bb (condition
);
662 basic_block dummy
= false_edge
->dest
;
663 edge entry_region
= SESE_ENTRY (region
);
664 edge exit_region
= SESE_EXIT (region
);
665 basic_block before_region
= entry_region
->src
;
666 basic_block last_in_region
= exit_region
->src
;
667 void **slot
= htab_find_slot_with_hash (current_loops
->exits
, exit_region
,
668 htab_hash_pointer (exit_region
),
671 entry_region
->flags
= false_edge
->flags
;
672 false_edge
->flags
= exit_region
->flags
;
674 redirect_edge_pred (entry_region
, condition
);
675 redirect_edge_pred (exit_region
, before_region
);
676 redirect_edge_pred (false_edge
, last_in_region
);
677 redirect_edge_succ (false_edge
, single_succ (dummy
));
678 delete_basic_block (dummy
);
680 exit_region
->flags
= EDGE_FALLTHRU
;
681 recompute_all_dominators ();
683 SESE_EXIT (region
) = false_edge
;
685 free (if_region
->false_region
);
686 if_region
->false_region
= region
;
690 struct loop_exit
*loop_exit
= ggc_alloc_cleared_loop_exit ();
692 memcpy (loop_exit
, *((struct loop_exit
**) slot
), sizeof (struct loop_exit
));
693 htab_clear_slot (current_loops
->exits
, slot
);
695 slot
= htab_find_slot_with_hash (current_loops
->exits
, false_edge
,
696 htab_hash_pointer (false_edge
),
698 loop_exit
->e
= false_edge
;
700 false_edge
->src
->loop_father
->exits
->next
= loop_exit
;
704 /* Creates an IFSESE with CONDITION on edge ENTRY. */
707 create_if_region_on_edge (edge entry
, tree condition
)
711 sese sese_region
= XNEW (struct sese_s
);
712 sese true_region
= XNEW (struct sese_s
);
713 sese false_region
= XNEW (struct sese_s
);
714 ifsese if_region
= XNEW (struct ifsese_s
);
715 edge exit
= create_empty_if_region_on_edge (entry
, condition
);
717 if_region
->region
= sese_region
;
718 if_region
->region
->entry
= entry
;
719 if_region
->region
->exit
= exit
;
721 FOR_EACH_EDGE (e
, ei
, entry
->dest
->succs
)
723 if (e
->flags
& EDGE_TRUE_VALUE
)
725 true_region
->entry
= e
;
726 true_region
->exit
= single_succ_edge (e
->dest
);
727 if_region
->true_region
= true_region
;
729 else if (e
->flags
& EDGE_FALSE_VALUE
)
731 false_region
->entry
= e
;
732 false_region
->exit
= single_succ_edge (e
->dest
);
733 if_region
->false_region
= false_region
;
740 /* Moves REGION in a condition expression:
748 move_sese_in_condition (sese region
)
750 basic_block pred_block
= split_edge (SESE_ENTRY (region
));
753 SESE_ENTRY (region
) = single_succ_edge (pred_block
);
754 if_region
= create_if_region_on_edge (single_pred_edge (pred_block
), integer_one_node
);
755 if_region_set_false_region (if_region
, region
);
760 /* Replaces the condition of the IF_REGION with CONDITION:
768 set_ifsese_condition (ifsese if_region
, tree condition
)
770 sese region
= if_region
->region
;
771 edge entry
= region
->entry
;
772 basic_block bb
= entry
->dest
;
773 gimple last
= last_stmt (bb
);
774 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
777 gcc_assert (gimple_code (last
) == GIMPLE_COND
);
779 gsi_remove (&gsi
, true);
780 gsi
= gsi_last_bb (bb
);
781 condition
= force_gimple_operand_gsi (&gsi
, condition
, true, NULL
,
782 false, GSI_NEW_STMT
);
783 cond_stmt
= gimple_build_cond_from_tree (condition
, NULL_TREE
, NULL_TREE
);
784 gsi
= gsi_last_bb (bb
);
785 gsi_insert_after (&gsi
, cond_stmt
, GSI_NEW_STMT
);
788 /* Returns the scalar evolution of T in REGION. Every variable that
789 is not defined in the REGION is considered a parameter. */
792 scalar_evolution_in_region (sese region
, loop_p loop
, tree t
)
795 struct loop
*def_loop
;
796 basic_block before
= block_before_sese (region
);
798 /* SCOP parameters. */
799 if (TREE_CODE (t
) == SSA_NAME
800 && !defined_in_sese_p (t
, region
))
803 if (TREE_CODE (t
) != SSA_NAME
804 || loop_in_sese_p (loop
, region
))
805 return instantiate_scev (before
, loop
,
806 analyze_scalar_evolution (loop
, t
));
808 def
= SSA_NAME_DEF_STMT (t
);
809 def_loop
= loop_containing_stmt (def
);
811 if (loop_in_sese_p (def_loop
, region
))
813 t
= analyze_scalar_evolution (def_loop
, t
);
814 def_loop
= superloop_at_depth (def_loop
, loop_depth (loop
) + 1);
815 t
= compute_overall_effect_of_inner_loop (def_loop
, t
);
819 return instantiate_scev (before
, loop
, t
);