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"
30 #include "tree-chrec.h"
31 #include "tree-data-ref.h"
32 #include "tree-scalar-evolution.h"
33 #include "tree-pass.h"
34 #include "value-prof.h"
37 /* Print to stderr the element ELT. */
40 debug_rename_elt (rename_map_elt elt
)
42 fprintf (stderr
, "(");
43 print_generic_expr (stderr
, elt
->old_name
, 0);
44 fprintf (stderr
, ", ");
45 print_generic_expr (stderr
, elt
->expr
, 0);
46 fprintf (stderr
, ")\n");
49 /* Helper function for debug_rename_map. */
52 debug_rename_map_1 (rename_map_elt_s
**slot
, void *s ATTRIBUTE_UNUSED
)
54 struct rename_map_elt_s
*entry
= *slot
;
55 debug_rename_elt (entry
);
60 /* Hashtable helpers. */
62 struct rename_map_hasher
: typed_free_remove
<rename_map_elt_s
>
64 typedef rename_map_elt_s value_type
;
65 typedef rename_map_elt_s compare_type
;
66 static inline hashval_t
hash (const value_type
*);
67 static inline bool equal (const value_type
*, const compare_type
*);
70 /* Computes a hash function for database element ELT. */
73 rename_map_hasher::hash (const value_type
*elt
)
75 return SSA_NAME_VERSION (elt
->old_name
);
78 /* Compares database elements E1 and E2. */
81 rename_map_hasher::equal (const value_type
*elt1
, const compare_type
*elt2
)
83 return (elt1
->old_name
== elt2
->old_name
);
86 typedef hash_table
<rename_map_hasher
> rename_map_type
;
89 /* Print to stderr all the elements of RENAME_MAP. */
92 debug_rename_map (rename_map_type rename_map
)
94 rename_map
.traverse
<void *, debug_rename_map_1
> (NULL
);
97 /* Computes a hash function for database element ELT. */
100 rename_map_elt_info (const void *elt
)
102 return SSA_NAME_VERSION (((const struct rename_map_elt_s
*) elt
)->old_name
);
105 /* Compares database elements E1 and E2. */
108 eq_rename_map_elts (const void *e1
, const void *e2
)
110 const struct rename_map_elt_s
*elt1
= (const struct rename_map_elt_s
*) e1
;
111 const struct rename_map_elt_s
*elt2
= (const struct rename_map_elt_s
*) e2
;
113 return (elt1
->old_name
== elt2
->old_name
);
118 /* Record LOOP as occurring in REGION. */
121 sese_record_loop (sese region
, loop_p loop
)
123 if (sese_contains_loop (region
, loop
))
126 bitmap_set_bit (SESE_LOOPS (region
), loop
->num
);
127 SESE_LOOP_NEST (region
).safe_push (loop
);
130 /* Build the loop nests contained in REGION. Returns true when the
131 operation was successful. */
134 build_sese_loop_nests (sese region
)
138 struct loop
*loop0
, *loop1
;
141 if (bb_in_sese_p (bb
, region
))
143 struct loop
*loop
= bb
->loop_father
;
145 /* Only add loops if they are completely contained in the SCoP. */
146 if (loop
->header
== bb
147 && bb_in_sese_p (loop
->latch
, region
))
148 sese_record_loop (region
, loop
);
151 /* Make sure that the loops in the SESE_LOOP_NEST are ordered. It
152 can be the case that an inner loop is inserted before an outer
153 loop. To avoid this, semi-sort once. */
154 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop0
)
156 if (SESE_LOOP_NEST (region
).length () == i
+ 1)
159 loop1
= SESE_LOOP_NEST (region
)[i
+ 1];
160 if (loop0
->num
> loop1
->num
)
162 SESE_LOOP_NEST (region
)[i
] = loop1
;
163 SESE_LOOP_NEST (region
)[i
+ 1] = loop0
;
168 /* For a USE in BB, if BB is outside REGION, mark the USE in the
172 sese_build_liveouts_use (sese region
, bitmap liveouts
, basic_block bb
,
178 if (TREE_CODE (use
) != SSA_NAME
)
181 ver
= SSA_NAME_VERSION (use
);
182 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (use
));
185 || !bb_in_sese_p (def_bb
, region
)
186 || bb_in_sese_p (bb
, region
))
189 bitmap_set_bit (liveouts
, ver
);
192 /* Marks for rewrite all the SSA_NAMES defined in REGION and that are
193 used in BB that is outside of the REGION. */
196 sese_build_liveouts_bb (sese region
, bitmap liveouts
, basic_block bb
)
198 gimple_stmt_iterator bsi
;
204 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
205 for (bsi
= gsi_start_phis (e
->dest
); !gsi_end_p (bsi
); gsi_next (&bsi
))
206 sese_build_liveouts_use (region
, liveouts
, bb
,
207 PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi
), e
));
209 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
211 gimple stmt
= gsi_stmt (bsi
);
213 if (is_gimple_debug (stmt
))
216 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
217 sese_build_liveouts_use (region
, liveouts
, bb
, USE_FROM_PTR (use_p
));
221 /* For a USE in BB, return true if BB is outside REGION and it's not
222 in the LIVEOUTS set. */
225 sese_bad_liveouts_use (sese region
, bitmap liveouts
, basic_block bb
,
231 if (TREE_CODE (use
) != SSA_NAME
)
234 ver
= SSA_NAME_VERSION (use
);
236 /* If it's in liveouts, the variable will get a new PHI node, and
237 the debug use will be properly adjusted. */
238 if (bitmap_bit_p (liveouts
, ver
))
241 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (use
));
244 || !bb_in_sese_p (def_bb
, region
)
245 || bb_in_sese_p (bb
, region
))
251 /* Reset debug stmts that reference SSA_NAMES defined in REGION that
252 are not marked as liveouts. */
255 sese_reset_debug_liveouts_bb (sese region
, bitmap liveouts
, basic_block bb
)
257 gimple_stmt_iterator bsi
;
261 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
263 gimple stmt
= gsi_stmt (bsi
);
265 if (!is_gimple_debug (stmt
))
268 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
269 if (sese_bad_liveouts_use (region
, liveouts
, bb
,
270 USE_FROM_PTR (use_p
)))
272 gimple_debug_bind_reset_value (stmt
);
279 /* Build the LIVEOUTS of REGION: the set of variables defined inside
280 and used outside the REGION. */
283 sese_build_liveouts (sese region
, bitmap liveouts
)
288 sese_build_liveouts_bb (region
, liveouts
, bb
);
289 if (MAY_HAVE_DEBUG_STMTS
)
291 sese_reset_debug_liveouts_bb (region
, liveouts
, bb
);
294 /* Builds a new SESE region from edges ENTRY and EXIT. */
297 new_sese (edge entry
, edge exit
)
299 sese region
= XNEW (struct sese_s
);
301 SESE_ENTRY (region
) = entry
;
302 SESE_EXIT (region
) = exit
;
303 SESE_LOOPS (region
) = BITMAP_ALLOC (NULL
);
304 SESE_LOOP_NEST (region
).create (3);
305 SESE_ADD_PARAMS (region
) = true;
306 SESE_PARAMS (region
).create (3);
311 /* Deletes REGION. */
314 free_sese (sese region
)
316 if (SESE_LOOPS (region
))
317 SESE_LOOPS (region
) = BITMAP_ALLOC (NULL
);
319 SESE_PARAMS (region
).release ();
320 SESE_LOOP_NEST (region
).release ();
325 /* Add exit phis for USE on EXIT. */
328 sese_add_exit_phis_edge (basic_block exit
, tree use
, edge false_e
, edge true_e
)
330 gimple phi
= create_phi_node (NULL_TREE
, exit
);
331 create_new_def_for (use
, phi
, gimple_phi_result_ptr (phi
));
332 add_phi_arg (phi
, use
, false_e
, UNKNOWN_LOCATION
);
333 add_phi_arg (phi
, use
, true_e
, UNKNOWN_LOCATION
);
336 /* Insert in the block BB phi nodes for variables defined in REGION
337 and used outside the REGION. The code generation moves REGION in
338 the else clause of an "if (1)" and generates code in the then
339 clause that is at this point empty:
348 sese_insert_phis_for_liveouts (sese region
, basic_block bb
,
349 edge false_e
, edge true_e
)
353 bitmap liveouts
= BITMAP_ALLOC (NULL
);
355 update_ssa (TODO_update_ssa
);
357 sese_build_liveouts (region
, liveouts
);
358 EXECUTE_IF_SET_IN_BITMAP (liveouts
, 0, i
, bi
)
359 sese_add_exit_phis_edge (bb
, ssa_name (i
), false_e
, true_e
);
360 BITMAP_FREE (liveouts
);
362 update_ssa (TODO_update_ssa
);
365 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */
368 get_true_edge_from_guard_bb (basic_block bb
)
373 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
374 if (e
->flags
& EDGE_TRUE_VALUE
)
381 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */
384 get_false_edge_from_guard_bb (basic_block bb
)
389 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
390 if (!(e
->flags
& EDGE_TRUE_VALUE
))
397 /* Returns the expression associated to OLD_NAME in RENAME_MAP. */
400 get_rename (rename_map_type rename_map
, tree old_name
)
402 struct rename_map_elt_s tmp
;
403 rename_map_elt_s
**slot
;
405 gcc_assert (TREE_CODE (old_name
) == SSA_NAME
);
406 tmp
.old_name
= old_name
;
407 slot
= rename_map
.find_slot (&tmp
, NO_INSERT
);
410 return (*slot
)->expr
;
415 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR). */
418 set_rename (rename_map_type rename_map
, tree old_name
, tree expr
)
420 struct rename_map_elt_s tmp
;
421 rename_map_elt_s
**slot
;
423 if (old_name
== expr
)
426 tmp
.old_name
= old_name
;
427 slot
= rename_map
.find_slot (&tmp
, INSERT
);
434 *slot
= new_rename_map_elt (old_name
, expr
);
437 /* Renames the scalar uses of the statement COPY, using the
438 substitution map RENAME_MAP, inserting the gimplification code at
439 GSI_TGT, for the translation REGION, with the original copied
440 statement in LOOP, and using the induction variable renaming map
441 IV_MAP. Returns true when something has been renamed. GLOOG_ERROR
442 is set when the code generation cannot continue. */
445 rename_uses (gimple copy
, rename_map_type rename_map
,
446 gimple_stmt_iterator
*gsi_tgt
,
447 sese region
, loop_p loop
, vec
<tree
> iv_map
,
452 bool changed
= false;
454 if (is_gimple_debug (copy
))
456 if (gimple_debug_bind_p (copy
))
457 gimple_debug_bind_reset_value (copy
);
458 else if (gimple_debug_source_bind_p (copy
))
466 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, op_iter
, SSA_OP_USE
)
468 tree old_name
= USE_FROM_PTR (use_p
);
472 if (TREE_CODE (old_name
) != SSA_NAME
473 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
477 new_expr
= get_rename (rename_map
, old_name
);
480 tree type_old_name
= TREE_TYPE (old_name
);
481 tree type_new_expr
= TREE_TYPE (new_expr
);
483 if (type_old_name
!= type_new_expr
484 || TREE_CODE (new_expr
) != SSA_NAME
)
486 tree var
= create_tmp_var (type_old_name
, "var");
488 if (!useless_type_conversion_p (type_old_name
, type_new_expr
))
489 new_expr
= fold_convert (type_old_name
, new_expr
);
491 new_expr
= force_gimple_operand (new_expr
, &stmts
, true, var
);
492 gsi_insert_seq_before (gsi_tgt
, stmts
, GSI_SAME_STMT
);
495 replace_exp (use_p
, new_expr
);
499 scev
= scalar_evolution_in_region (region
, loop
, old_name
);
501 /* At this point we should know the exact scev for each
502 scalar SSA_NAME used in the scop: all the other scalar
503 SSA_NAMEs should have been translated out of SSA using
504 arrays with one element. */
505 if (chrec_contains_undetermined (scev
))
508 new_expr
= build_zero_cst (TREE_TYPE (old_name
));
511 new_expr
= chrec_apply_map (scev
, iv_map
);
513 /* The apply should produce an expression tree containing
514 the uses of the new induction variables. We should be
515 able to use new_expr instead of the old_name in the newly
516 generated loop nest. */
517 if (chrec_contains_undetermined (new_expr
)
518 || tree_contains_chrecs (new_expr
, NULL
))
521 new_expr
= build_zero_cst (TREE_TYPE (old_name
));
524 /* Replace the old_name with the new_expr. */
525 new_expr
= force_gimple_operand (unshare_expr (new_expr
), &stmts
,
528 gsi_insert_seq_before (gsi_tgt
, stmts
, GSI_SAME_STMT
);
529 replace_exp (use_p
, new_expr
);
531 if (TREE_CODE (new_expr
) == INTEGER_CST
532 && is_gimple_assign (copy
))
534 tree rhs
= gimple_assign_rhs1 (copy
);
536 if (TREE_CODE (rhs
) == ADDR_EXPR
)
537 recompute_tree_invariant_for_addr_expr (rhs
);
540 set_rename (rename_map
, old_name
, new_expr
);
546 /* Duplicates the statements of basic block BB into basic block NEW_BB
547 and compute the new induction variables according to the IV_MAP.
548 GLOOG_ERROR is set when the code generation cannot continue. */
551 graphite_copy_stmts_from_block (basic_block bb
, basic_block new_bb
,
552 rename_map_type rename_map
,
553 vec
<tree
> iv_map
, sese region
,
556 gimple_stmt_iterator gsi
, gsi_tgt
;
557 loop_p loop
= bb
->loop_father
;
559 gsi_tgt
= gsi_start_bb (new_bb
);
560 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
564 gimple stmt
= gsi_stmt (gsi
);
568 /* Do not copy labels or conditions. */
569 if (gimple_code (stmt
) == GIMPLE_LABEL
570 || gimple_code (stmt
) == GIMPLE_COND
)
573 /* Do not copy induction variables. */
574 if (is_gimple_assign (stmt
)
575 && (lhs
= gimple_assign_lhs (stmt
))
576 && TREE_CODE (lhs
) == SSA_NAME
577 && is_gimple_reg (lhs
)
578 && scev_analyzable_p (lhs
, region
))
581 /* Create a new copy of STMT and duplicate STMT's virtual
583 copy
= gimple_copy (stmt
);
584 gsi_insert_after (&gsi_tgt
, copy
, GSI_NEW_STMT
);
586 maybe_duplicate_eh_stmt (copy
, stmt
);
587 gimple_duplicate_stmt_histograms (cfun
, copy
, cfun
, stmt
);
589 /* Create new names for all the definitions created by COPY and
590 add replacement mappings for each new name. */
591 FOR_EACH_SSA_DEF_OPERAND (def_p
, copy
, op_iter
, SSA_OP_ALL_DEFS
)
593 tree old_name
= DEF_FROM_PTR (def_p
);
594 tree new_name
= create_new_def_for (old_name
, copy
, def_p
);
595 set_rename (rename_map
, old_name
, new_name
);
598 if (rename_uses (copy
, rename_map
, &gsi_tgt
, region
, loop
, iv_map
,
601 gcc_assert (gsi_stmt (gsi_tgt
) == copy
);
602 fold_stmt_inplace (&gsi_tgt
);
609 /* Copies BB and includes in the copied BB all the statements that can
610 be reached following the use-def chains from the memory accesses,
611 and returns the next edge following this new block. GLOOG_ERROR is
612 set when the code generation cannot continue. */
615 copy_bb_and_scalar_dependences (basic_block bb
, sese region
,
616 edge next_e
, vec
<tree
> iv_map
,
619 basic_block new_bb
= split_edge (next_e
);
620 rename_map_type rename_map
;
621 rename_map
.create (10);
623 next_e
= single_succ_edge (new_bb
);
624 graphite_copy_stmts_from_block (bb
, new_bb
, rename_map
, iv_map
, region
,
626 remove_phi_nodes (new_bb
);
627 rename_map
.dispose ();
632 /* Returns the outermost loop in SCOP that contains BB. */
635 outermost_loop_in_sese (sese region
, basic_block bb
)
639 nest
= bb
->loop_father
;
640 while (loop_outer (nest
)
641 && loop_in_sese_p (loop_outer (nest
), region
))
642 nest
= loop_outer (nest
);
647 /* Sets the false region of an IF_REGION to REGION. */
650 if_region_set_false_region (ifsese if_region
, sese region
)
652 basic_block condition
= if_region_get_condition_block (if_region
);
653 edge false_edge
= get_false_edge_from_guard_bb (condition
);
654 basic_block dummy
= false_edge
->dest
;
655 edge entry_region
= SESE_ENTRY (region
);
656 edge exit_region
= SESE_EXIT (region
);
657 basic_block before_region
= entry_region
->src
;
658 basic_block last_in_region
= exit_region
->src
;
659 void **slot
= htab_find_slot_with_hash (current_loops
->exits
, exit_region
,
660 htab_hash_pointer (exit_region
),
663 entry_region
->flags
= false_edge
->flags
;
664 false_edge
->flags
= exit_region
->flags
;
666 redirect_edge_pred (entry_region
, condition
);
667 redirect_edge_pred (exit_region
, before_region
);
668 redirect_edge_pred (false_edge
, last_in_region
);
669 redirect_edge_succ (false_edge
, single_succ (dummy
));
670 delete_basic_block (dummy
);
672 exit_region
->flags
= EDGE_FALLTHRU
;
673 recompute_all_dominators ();
675 SESE_EXIT (region
) = false_edge
;
677 free (if_region
->false_region
);
678 if_region
->false_region
= region
;
682 struct loop_exit
*loop_exit
= ggc_alloc_cleared_loop_exit ();
684 memcpy (loop_exit
, *((struct loop_exit
**) slot
), sizeof (struct loop_exit
));
685 htab_clear_slot (current_loops
->exits
, slot
);
687 slot
= htab_find_slot_with_hash (current_loops
->exits
, false_edge
,
688 htab_hash_pointer (false_edge
),
690 loop_exit
->e
= false_edge
;
692 false_edge
->src
->loop_father
->exits
->next
= loop_exit
;
696 /* Creates an IFSESE with CONDITION on edge ENTRY. */
699 create_if_region_on_edge (edge entry
, tree condition
)
703 sese sese_region
= XNEW (struct sese_s
);
704 sese true_region
= XNEW (struct sese_s
);
705 sese false_region
= XNEW (struct sese_s
);
706 ifsese if_region
= XNEW (struct ifsese_s
);
707 edge exit
= create_empty_if_region_on_edge (entry
, condition
);
709 if_region
->region
= sese_region
;
710 if_region
->region
->entry
= entry
;
711 if_region
->region
->exit
= exit
;
713 FOR_EACH_EDGE (e
, ei
, entry
->dest
->succs
)
715 if (e
->flags
& EDGE_TRUE_VALUE
)
717 true_region
->entry
= e
;
718 true_region
->exit
= single_succ_edge (e
->dest
);
719 if_region
->true_region
= true_region
;
721 else if (e
->flags
& EDGE_FALSE_VALUE
)
723 false_region
->entry
= e
;
724 false_region
->exit
= single_succ_edge (e
->dest
);
725 if_region
->false_region
= false_region
;
732 /* Moves REGION in a condition expression:
740 move_sese_in_condition (sese region
)
742 basic_block pred_block
= split_edge (SESE_ENTRY (region
));
745 SESE_ENTRY (region
) = single_succ_edge (pred_block
);
746 if_region
= create_if_region_on_edge (single_pred_edge (pred_block
), integer_one_node
);
747 if_region_set_false_region (if_region
, region
);
752 /* Replaces the condition of the IF_REGION with CONDITION:
760 set_ifsese_condition (ifsese if_region
, tree condition
)
762 sese region
= if_region
->region
;
763 edge entry
= region
->entry
;
764 basic_block bb
= entry
->dest
;
765 gimple last
= last_stmt (bb
);
766 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
769 gcc_assert (gimple_code (last
) == GIMPLE_COND
);
771 gsi_remove (&gsi
, true);
772 gsi
= gsi_last_bb (bb
);
773 condition
= force_gimple_operand_gsi (&gsi
, condition
, true, NULL
,
774 false, GSI_NEW_STMT
);
775 cond_stmt
= gimple_build_cond_from_tree (condition
, NULL_TREE
, NULL_TREE
);
776 gsi
= gsi_last_bb (bb
);
777 gsi_insert_after (&gsi
, cond_stmt
, GSI_NEW_STMT
);
780 /* Returns the scalar evolution of T in REGION. Every variable that
781 is not defined in the REGION is considered a parameter. */
784 scalar_evolution_in_region (sese region
, loop_p loop
, tree t
)
787 struct loop
*def_loop
;
788 basic_block before
= block_before_sese (region
);
790 /* SCOP parameters. */
791 if (TREE_CODE (t
) == SSA_NAME
792 && !defined_in_sese_p (t
, region
))
795 if (TREE_CODE (t
) != SSA_NAME
796 || loop_in_sese_p (loop
, region
))
797 return instantiate_scev (before
, loop
,
798 analyze_scalar_evolution (loop
, t
));
800 def
= SSA_NAME_DEF_STMT (t
);
801 def_loop
= loop_containing_stmt (def
);
803 if (loop_in_sese_p (def_loop
, region
))
805 t
= analyze_scalar_evolution (def_loop
, t
);
806 def_loop
= superloop_at_depth (def_loop
, loop_depth (loop
) + 1);
807 t
= compute_overall_effect_of_inner_loop (def_loop
, t
);
811 return instantiate_scev (before
, loop
, t
);