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-iterator.h"
30 #include "gimple-ssa.h"
32 #include "tree-phinodes.h"
33 #include "ssa-iterators.h"
34 #include "tree-ssanames.h"
35 #include "tree-ssa-loop.h"
36 #include "tree-into-ssa.h"
38 #include "tree-chrec.h"
39 #include "tree-data-ref.h"
40 #include "tree-scalar-evolution.h"
41 #include "tree-pass.h"
42 #include "value-prof.h"
44 #include "tree-ssa-propagate.h"
46 /* Print to stderr the element ELT. */
49 debug_rename_elt (rename_map_elt elt
)
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");
58 /* Helper function for debug_rename_map. */
61 debug_rename_map_1 (rename_map_elt_s
**slot
, void *s ATTRIBUTE_UNUSED
)
63 struct rename_map_elt_s
*entry
= *slot
;
64 debug_rename_elt (entry
);
69 /* Hashtable helpers. */
71 struct rename_map_hasher
: typed_free_remove
<rename_map_elt_s
>
73 typedef rename_map_elt_s value_type
;
74 typedef rename_map_elt_s compare_type
;
75 static inline hashval_t
hash (const value_type
*);
76 static inline bool equal (const value_type
*, const compare_type
*);
79 /* Computes a hash function for database element ELT. */
82 rename_map_hasher::hash (const value_type
*elt
)
84 return SSA_NAME_VERSION (elt
->old_name
);
87 /* Compares database elements E1 and E2. */
90 rename_map_hasher::equal (const value_type
*elt1
, const compare_type
*elt2
)
92 return (elt1
->old_name
== elt2
->old_name
);
95 typedef hash_table
<rename_map_hasher
> rename_map_type
;
98 /* Print to stderr all the elements of RENAME_MAP. */
101 debug_rename_map (rename_map_type rename_map
)
103 rename_map
.traverse
<void *, debug_rename_map_1
> (NULL
);
106 /* Computes a hash function for database element ELT. */
109 rename_map_elt_info (const void *elt
)
111 return SSA_NAME_VERSION (((const struct rename_map_elt_s
*) elt
)->old_name
);
114 /* Compares database elements E1 and E2. */
117 eq_rename_map_elts (const void *e1
, const void *e2
)
119 const struct rename_map_elt_s
*elt1
= (const struct rename_map_elt_s
*) e1
;
120 const struct rename_map_elt_s
*elt2
= (const struct rename_map_elt_s
*) e2
;
122 return (elt1
->old_name
== elt2
->old_name
);
127 /* Record LOOP as occurring in REGION. */
130 sese_record_loop (sese region
, loop_p loop
)
132 if (sese_contains_loop (region
, loop
))
135 bitmap_set_bit (SESE_LOOPS (region
), loop
->num
);
136 SESE_LOOP_NEST (region
).safe_push (loop
);
139 /* Build the loop nests contained in REGION. Returns true when the
140 operation was successful. */
143 build_sese_loop_nests (sese region
)
147 struct loop
*loop0
, *loop1
;
150 if (bb_in_sese_p (bb
, region
))
152 struct loop
*loop
= bb
->loop_father
;
154 /* Only add loops if they are completely contained in the SCoP. */
155 if (loop
->header
== bb
156 && bb_in_sese_p (loop
->latch
, region
))
157 sese_record_loop (region
, loop
);
160 /* Make sure that the loops in the SESE_LOOP_NEST are ordered. It
161 can be the case that an inner loop is inserted before an outer
162 loop. To avoid this, semi-sort once. */
163 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop0
)
165 if (SESE_LOOP_NEST (region
).length () == i
+ 1)
168 loop1
= SESE_LOOP_NEST (region
)[i
+ 1];
169 if (loop0
->num
> loop1
->num
)
171 SESE_LOOP_NEST (region
)[i
] = loop1
;
172 SESE_LOOP_NEST (region
)[i
+ 1] = loop0
;
177 /* For a USE in BB, if BB is outside REGION, mark the USE in the
181 sese_build_liveouts_use (sese region
, bitmap liveouts
, basic_block bb
,
187 if (TREE_CODE (use
) != SSA_NAME
)
190 ver
= SSA_NAME_VERSION (use
);
191 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (use
));
194 || !bb_in_sese_p (def_bb
, region
)
195 || bb_in_sese_p (bb
, region
))
198 bitmap_set_bit (liveouts
, ver
);
201 /* Marks for rewrite all the SSA_NAMES defined in REGION and that are
202 used in BB that is outside of the REGION. */
205 sese_build_liveouts_bb (sese region
, bitmap liveouts
, basic_block bb
)
207 gimple_stmt_iterator bsi
;
213 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
214 for (bsi
= gsi_start_phis (e
->dest
); !gsi_end_p (bsi
); gsi_next (&bsi
))
215 sese_build_liveouts_use (region
, liveouts
, bb
,
216 PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi
), e
));
218 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
220 gimple stmt
= gsi_stmt (bsi
);
222 if (is_gimple_debug (stmt
))
225 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
226 sese_build_liveouts_use (region
, liveouts
, bb
, USE_FROM_PTR (use_p
));
230 /* For a USE in BB, return true if BB is outside REGION and it's not
231 in the LIVEOUTS set. */
234 sese_bad_liveouts_use (sese region
, bitmap liveouts
, basic_block bb
,
240 if (TREE_CODE (use
) != SSA_NAME
)
243 ver
= SSA_NAME_VERSION (use
);
245 /* If it's in liveouts, the variable will get a new PHI node, and
246 the debug use will be properly adjusted. */
247 if (bitmap_bit_p (liveouts
, ver
))
250 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (use
));
253 || !bb_in_sese_p (def_bb
, region
)
254 || bb_in_sese_p (bb
, region
))
260 /* Reset debug stmts that reference SSA_NAMES defined in REGION that
261 are not marked as liveouts. */
264 sese_reset_debug_liveouts_bb (sese region
, bitmap liveouts
, basic_block bb
)
266 gimple_stmt_iterator bsi
;
270 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
272 gimple stmt
= gsi_stmt (bsi
);
274 if (!is_gimple_debug (stmt
))
277 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
278 if (sese_bad_liveouts_use (region
, liveouts
, bb
,
279 USE_FROM_PTR (use_p
)))
281 gimple_debug_bind_reset_value (stmt
);
288 /* Build the LIVEOUTS of REGION: the set of variables defined inside
289 and used outside the REGION. */
292 sese_build_liveouts (sese region
, bitmap liveouts
)
297 sese_build_liveouts_bb (region
, liveouts
, bb
);
298 if (MAY_HAVE_DEBUG_STMTS
)
300 sese_reset_debug_liveouts_bb (region
, liveouts
, bb
);
303 /* Builds a new SESE region from edges ENTRY and EXIT. */
306 new_sese (edge entry
, edge exit
)
308 sese region
= XNEW (struct sese_s
);
310 SESE_ENTRY (region
) = entry
;
311 SESE_EXIT (region
) = exit
;
312 SESE_LOOPS (region
) = BITMAP_ALLOC (NULL
);
313 SESE_LOOP_NEST (region
).create (3);
314 SESE_ADD_PARAMS (region
) = true;
315 SESE_PARAMS (region
).create (3);
320 /* Deletes REGION. */
323 free_sese (sese region
)
325 if (SESE_LOOPS (region
))
326 SESE_LOOPS (region
) = BITMAP_ALLOC (NULL
);
328 SESE_PARAMS (region
).release ();
329 SESE_LOOP_NEST (region
).release ();
334 /* Add exit phis for USE on EXIT. */
337 sese_add_exit_phis_edge (basic_block exit
, tree use
, edge false_e
, edge true_e
)
339 gimple phi
= create_phi_node (NULL_TREE
, exit
);
340 create_new_def_for (use
, phi
, gimple_phi_result_ptr (phi
));
341 add_phi_arg (phi
, use
, false_e
, UNKNOWN_LOCATION
);
342 add_phi_arg (phi
, use
, true_e
, UNKNOWN_LOCATION
);
345 /* Insert in the block BB phi nodes for variables defined in REGION
346 and used outside the REGION. The code generation moves REGION in
347 the else clause of an "if (1)" and generates code in the then
348 clause that is at this point empty:
357 sese_insert_phis_for_liveouts (sese region
, basic_block bb
,
358 edge false_e
, edge true_e
)
362 bitmap liveouts
= BITMAP_ALLOC (NULL
);
364 update_ssa (TODO_update_ssa
);
366 sese_build_liveouts (region
, liveouts
);
367 EXECUTE_IF_SET_IN_BITMAP (liveouts
, 0, i
, bi
)
368 sese_add_exit_phis_edge (bb
, ssa_name (i
), false_e
, true_e
);
369 BITMAP_FREE (liveouts
);
371 update_ssa (TODO_update_ssa
);
374 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */
377 get_true_edge_from_guard_bb (basic_block bb
)
382 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
383 if (e
->flags
& EDGE_TRUE_VALUE
)
390 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */
393 get_false_edge_from_guard_bb (basic_block bb
)
398 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
399 if (!(e
->flags
& EDGE_TRUE_VALUE
))
406 /* Returns the expression associated to OLD_NAME in RENAME_MAP. */
409 get_rename (rename_map_type rename_map
, tree old_name
)
411 struct rename_map_elt_s tmp
;
412 rename_map_elt_s
**slot
;
414 gcc_assert (TREE_CODE (old_name
) == SSA_NAME
);
415 tmp
.old_name
= old_name
;
416 slot
= rename_map
.find_slot (&tmp
, NO_INSERT
);
419 return (*slot
)->expr
;
424 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR). */
427 set_rename (rename_map_type rename_map
, tree old_name
, tree expr
)
429 struct rename_map_elt_s tmp
;
430 rename_map_elt_s
**slot
;
432 if (old_name
== expr
)
435 tmp
.old_name
= old_name
;
436 slot
= rename_map
.find_slot (&tmp
, INSERT
);
443 *slot
= new_rename_map_elt (old_name
, expr
);
446 /* Renames the scalar uses of the statement COPY, using the
447 substitution map RENAME_MAP, inserting the gimplification code at
448 GSI_TGT, for the translation REGION, with the original copied
449 statement in LOOP, and using the induction variable renaming map
450 IV_MAP. Returns true when something has been renamed. GLOOG_ERROR
451 is set when the code generation cannot continue. */
454 rename_uses (gimple copy
, rename_map_type rename_map
,
455 gimple_stmt_iterator
*gsi_tgt
,
456 sese region
, loop_p loop
, vec
<tree
> iv_map
,
461 bool changed
= false;
463 if (is_gimple_debug (copy
))
465 if (gimple_debug_bind_p (copy
))
466 gimple_debug_bind_reset_value (copy
);
467 else if (gimple_debug_source_bind_p (copy
))
475 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, op_iter
, SSA_OP_USE
)
477 tree old_name
= USE_FROM_PTR (use_p
);
481 if (TREE_CODE (old_name
) != SSA_NAME
482 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
486 new_expr
= get_rename (rename_map
, old_name
);
489 tree type_old_name
= TREE_TYPE (old_name
);
490 tree type_new_expr
= TREE_TYPE (new_expr
);
492 if (type_old_name
!= type_new_expr
493 || TREE_CODE (new_expr
) != SSA_NAME
)
495 tree var
= create_tmp_var (type_old_name
, "var");
497 if (!useless_type_conversion_p (type_old_name
, type_new_expr
))
498 new_expr
= fold_convert (type_old_name
, new_expr
);
500 new_expr
= force_gimple_operand (new_expr
, &stmts
, true, var
);
501 gsi_insert_seq_before (gsi_tgt
, stmts
, GSI_SAME_STMT
);
504 replace_exp (use_p
, new_expr
);
508 scev
= scalar_evolution_in_region (region
, loop
, old_name
);
510 /* At this point we should know the exact scev for each
511 scalar SSA_NAME used in the scop: all the other scalar
512 SSA_NAMEs should have been translated out of SSA using
513 arrays with one element. */
514 if (chrec_contains_undetermined (scev
))
517 new_expr
= build_zero_cst (TREE_TYPE (old_name
));
520 new_expr
= chrec_apply_map (scev
, iv_map
);
522 /* The apply should produce an expression tree containing
523 the uses of the new induction variables. We should be
524 able to use new_expr instead of the old_name in the newly
525 generated loop nest. */
526 if (chrec_contains_undetermined (new_expr
)
527 || tree_contains_chrecs (new_expr
, NULL
))
530 new_expr
= build_zero_cst (TREE_TYPE (old_name
));
533 /* Replace the old_name with the new_expr. */
534 new_expr
= force_gimple_operand (unshare_expr (new_expr
), &stmts
,
537 gsi_insert_seq_before (gsi_tgt
, stmts
, GSI_SAME_STMT
);
538 replace_exp (use_p
, new_expr
);
540 if (TREE_CODE (new_expr
) == INTEGER_CST
541 && is_gimple_assign (copy
))
543 tree rhs
= gimple_assign_rhs1 (copy
);
545 if (TREE_CODE (rhs
) == ADDR_EXPR
)
546 recompute_tree_invariant_for_addr_expr (rhs
);
549 set_rename (rename_map
, old_name
, new_expr
);
555 /* Duplicates the statements of basic block BB into basic block NEW_BB
556 and compute the new induction variables according to the IV_MAP.
557 GLOOG_ERROR is set when the code generation cannot continue. */
560 graphite_copy_stmts_from_block (basic_block bb
, basic_block new_bb
,
561 rename_map_type rename_map
,
562 vec
<tree
> iv_map
, sese region
,
565 gimple_stmt_iterator gsi
, gsi_tgt
;
566 loop_p loop
= bb
->loop_father
;
568 gsi_tgt
= gsi_start_bb (new_bb
);
569 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
573 gimple stmt
= gsi_stmt (gsi
);
577 /* Do not copy labels or conditions. */
578 if (gimple_code (stmt
) == GIMPLE_LABEL
579 || gimple_code (stmt
) == GIMPLE_COND
)
582 /* Do not copy induction variables. */
583 if (is_gimple_assign (stmt
)
584 && (lhs
= gimple_assign_lhs (stmt
))
585 && TREE_CODE (lhs
) == SSA_NAME
586 && is_gimple_reg (lhs
)
587 && scev_analyzable_p (lhs
, region
))
590 /* Create a new copy of STMT and duplicate STMT's virtual
592 copy
= gimple_copy (stmt
);
593 gsi_insert_after (&gsi_tgt
, copy
, GSI_NEW_STMT
);
595 maybe_duplicate_eh_stmt (copy
, stmt
);
596 gimple_duplicate_stmt_histograms (cfun
, copy
, cfun
, stmt
);
598 /* Create new names for all the definitions created by COPY and
599 add replacement mappings for each new name. */
600 FOR_EACH_SSA_DEF_OPERAND (def_p
, copy
, op_iter
, SSA_OP_ALL_DEFS
)
602 tree old_name
= DEF_FROM_PTR (def_p
);
603 tree new_name
= create_new_def_for (old_name
, copy
, def_p
);
604 set_rename (rename_map
, old_name
, new_name
);
607 if (rename_uses (copy
, rename_map
, &gsi_tgt
, region
, loop
, iv_map
,
610 gcc_assert (gsi_stmt (gsi_tgt
) == copy
);
611 fold_stmt_inplace (&gsi_tgt
);
618 /* Copies BB and includes in the copied BB all the statements that can
619 be reached following the use-def chains from the memory accesses,
620 and returns the next edge following this new block. GLOOG_ERROR is
621 set when the code generation cannot continue. */
624 copy_bb_and_scalar_dependences (basic_block bb
, sese region
,
625 edge next_e
, vec
<tree
> iv_map
,
628 basic_block new_bb
= split_edge (next_e
);
629 rename_map_type rename_map
;
630 rename_map
.create (10);
632 next_e
= single_succ_edge (new_bb
);
633 graphite_copy_stmts_from_block (bb
, new_bb
, rename_map
, iv_map
, region
,
635 remove_phi_nodes (new_bb
);
636 rename_map
.dispose ();
641 /* Returns the outermost loop in SCOP that contains BB. */
644 outermost_loop_in_sese (sese region
, basic_block bb
)
648 nest
= bb
->loop_father
;
649 while (loop_outer (nest
)
650 && loop_in_sese_p (loop_outer (nest
), region
))
651 nest
= loop_outer (nest
);
656 /* Sets the false region of an IF_REGION to REGION. */
659 if_region_set_false_region (ifsese if_region
, sese region
)
661 basic_block condition
= if_region_get_condition_block (if_region
);
662 edge false_edge
= get_false_edge_from_guard_bb (condition
);
663 basic_block dummy
= false_edge
->dest
;
664 edge entry_region
= SESE_ENTRY (region
);
665 edge exit_region
= SESE_EXIT (region
);
666 basic_block before_region
= entry_region
->src
;
667 basic_block last_in_region
= exit_region
->src
;
668 void **slot
= htab_find_slot_with_hash (current_loops
->exits
, exit_region
,
669 htab_hash_pointer (exit_region
),
672 entry_region
->flags
= false_edge
->flags
;
673 false_edge
->flags
= exit_region
->flags
;
675 redirect_edge_pred (entry_region
, condition
);
676 redirect_edge_pred (exit_region
, before_region
);
677 redirect_edge_pred (false_edge
, last_in_region
);
678 redirect_edge_succ (false_edge
, single_succ (dummy
));
679 delete_basic_block (dummy
);
681 exit_region
->flags
= EDGE_FALLTHRU
;
682 recompute_all_dominators ();
684 SESE_EXIT (region
) = false_edge
;
686 free (if_region
->false_region
);
687 if_region
->false_region
= region
;
691 struct loop_exit
*loop_exit
= ggc_alloc_cleared_loop_exit ();
693 memcpy (loop_exit
, *((struct loop_exit
**) slot
), sizeof (struct loop_exit
));
694 htab_clear_slot (current_loops
->exits
, slot
);
696 slot
= htab_find_slot_with_hash (current_loops
->exits
, false_edge
,
697 htab_hash_pointer (false_edge
),
699 loop_exit
->e
= false_edge
;
701 false_edge
->src
->loop_father
->exits
->next
= loop_exit
;
705 /* Creates an IFSESE with CONDITION on edge ENTRY. */
708 create_if_region_on_edge (edge entry
, tree condition
)
712 sese sese_region
= XNEW (struct sese_s
);
713 sese true_region
= XNEW (struct sese_s
);
714 sese false_region
= XNEW (struct sese_s
);
715 ifsese if_region
= XNEW (struct ifsese_s
);
716 edge exit
= create_empty_if_region_on_edge (entry
, condition
);
718 if_region
->region
= sese_region
;
719 if_region
->region
->entry
= entry
;
720 if_region
->region
->exit
= exit
;
722 FOR_EACH_EDGE (e
, ei
, entry
->dest
->succs
)
724 if (e
->flags
& EDGE_TRUE_VALUE
)
726 true_region
->entry
= e
;
727 true_region
->exit
= single_succ_edge (e
->dest
);
728 if_region
->true_region
= true_region
;
730 else if (e
->flags
& EDGE_FALSE_VALUE
)
732 false_region
->entry
= e
;
733 false_region
->exit
= single_succ_edge (e
->dest
);
734 if_region
->false_region
= false_region
;
741 /* Moves REGION in a condition expression:
749 move_sese_in_condition (sese region
)
751 basic_block pred_block
= split_edge (SESE_ENTRY (region
));
754 SESE_ENTRY (region
) = single_succ_edge (pred_block
);
755 if_region
= create_if_region_on_edge (single_pred_edge (pred_block
), integer_one_node
);
756 if_region_set_false_region (if_region
, region
);
761 /* Replaces the condition of the IF_REGION with CONDITION:
769 set_ifsese_condition (ifsese if_region
, tree condition
)
771 sese region
= if_region
->region
;
772 edge entry
= region
->entry
;
773 basic_block bb
= entry
->dest
;
774 gimple last
= last_stmt (bb
);
775 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
778 gcc_assert (gimple_code (last
) == GIMPLE_COND
);
780 gsi_remove (&gsi
, true);
781 gsi
= gsi_last_bb (bb
);
782 condition
= force_gimple_operand_gsi (&gsi
, condition
, true, NULL
,
783 false, GSI_NEW_STMT
);
784 cond_stmt
= gimple_build_cond_from_tree (condition
, NULL_TREE
, NULL_TREE
);
785 gsi
= gsi_last_bb (bb
);
786 gsi_insert_after (&gsi
, cond_stmt
, GSI_NEW_STMT
);
789 /* Returns the scalar evolution of T in REGION. Every variable that
790 is not defined in the REGION is considered a parameter. */
793 scalar_evolution_in_region (sese region
, loop_p loop
, tree t
)
796 struct loop
*def_loop
;
797 basic_block before
= block_before_sese (region
);
799 /* SCOP parameters. */
800 if (TREE_CODE (t
) == SSA_NAME
801 && !defined_in_sese_p (t
, region
))
804 if (TREE_CODE (t
) != SSA_NAME
805 || loop_in_sese_p (loop
, region
))
806 return instantiate_scev (before
, loop
,
807 analyze_scalar_evolution (loop
, t
));
809 def
= SSA_NAME_DEF_STMT (t
);
810 def_loop
= loop_containing_stmt (def
);
812 if (loop_in_sese_p (def_loop
, region
))
814 t
= analyze_scalar_evolution (def_loop
, t
);
815 def_loop
= superloop_at_depth (def_loop
, loop_depth (loop
) + 1);
816 t
= compute_overall_effect_of_inner_loop (def_loop
, t
);
820 return instantiate_scev (before
, loop
, t
);