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"
36 #include "tree-ssa-propagate.h"
38 /* Print to stderr the element ELT. */
41 debug_rename_elt (rename_map_elt elt
)
43 fprintf (stderr
, "(");
44 print_generic_expr (stderr
, elt
->old_name
, 0);
45 fprintf (stderr
, ", ");
46 print_generic_expr (stderr
, elt
->expr
, 0);
47 fprintf (stderr
, ")\n");
50 /* Helper function for debug_rename_map. */
53 debug_rename_map_1 (rename_map_elt_s
**slot
, void *s ATTRIBUTE_UNUSED
)
55 struct rename_map_elt_s
*entry
= *slot
;
56 debug_rename_elt (entry
);
61 /* Hashtable helpers. */
63 struct rename_map_hasher
: typed_free_remove
<rename_map_elt_s
>
65 typedef rename_map_elt_s value_type
;
66 typedef rename_map_elt_s compare_type
;
67 static inline hashval_t
hash (const value_type
*);
68 static inline bool equal (const value_type
*, const compare_type
*);
71 /* Computes a hash function for database element ELT. */
74 rename_map_hasher::hash (const value_type
*elt
)
76 return SSA_NAME_VERSION (elt
->old_name
);
79 /* Compares database elements E1 and E2. */
82 rename_map_hasher::equal (const value_type
*elt1
, const compare_type
*elt2
)
84 return (elt1
->old_name
== elt2
->old_name
);
87 typedef hash_table
<rename_map_hasher
> rename_map_type
;
90 /* Print to stderr all the elements of RENAME_MAP. */
93 debug_rename_map (rename_map_type rename_map
)
95 rename_map
.traverse
<void *, debug_rename_map_1
> (NULL
);
98 /* Computes a hash function for database element ELT. */
101 rename_map_elt_info (const void *elt
)
103 return SSA_NAME_VERSION (((const struct rename_map_elt_s
*) elt
)->old_name
);
106 /* Compares database elements E1 and E2. */
109 eq_rename_map_elts (const void *e1
, const void *e2
)
111 const struct rename_map_elt_s
*elt1
= (const struct rename_map_elt_s
*) e1
;
112 const struct rename_map_elt_s
*elt2
= (const struct rename_map_elt_s
*) e2
;
114 return (elt1
->old_name
== elt2
->old_name
);
119 /* Record LOOP as occurring in REGION. */
122 sese_record_loop (sese region
, loop_p loop
)
124 if (sese_contains_loop (region
, loop
))
127 bitmap_set_bit (SESE_LOOPS (region
), loop
->num
);
128 SESE_LOOP_NEST (region
).safe_push (loop
);
131 /* Build the loop nests contained in REGION. Returns true when the
132 operation was successful. */
135 build_sese_loop_nests (sese region
)
139 struct loop
*loop0
, *loop1
;
142 if (bb_in_sese_p (bb
, region
))
144 struct loop
*loop
= bb
->loop_father
;
146 /* Only add loops if they are completely contained in the SCoP. */
147 if (loop
->header
== bb
148 && bb_in_sese_p (loop
->latch
, region
))
149 sese_record_loop (region
, loop
);
152 /* Make sure that the loops in the SESE_LOOP_NEST are ordered. It
153 can be the case that an inner loop is inserted before an outer
154 loop. To avoid this, semi-sort once. */
155 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop0
)
157 if (SESE_LOOP_NEST (region
).length () == i
+ 1)
160 loop1
= SESE_LOOP_NEST (region
)[i
+ 1];
161 if (loop0
->num
> loop1
->num
)
163 SESE_LOOP_NEST (region
)[i
] = loop1
;
164 SESE_LOOP_NEST (region
)[i
+ 1] = loop0
;
169 /* For a USE in BB, if BB is outside REGION, mark the USE in the
173 sese_build_liveouts_use (sese region
, bitmap liveouts
, basic_block bb
,
179 if (TREE_CODE (use
) != SSA_NAME
)
182 ver
= SSA_NAME_VERSION (use
);
183 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (use
));
186 || !bb_in_sese_p (def_bb
, region
)
187 || bb_in_sese_p (bb
, region
))
190 bitmap_set_bit (liveouts
, ver
);
193 /* Marks for rewrite all the SSA_NAMES defined in REGION and that are
194 used in BB that is outside of the REGION. */
197 sese_build_liveouts_bb (sese region
, bitmap liveouts
, basic_block bb
)
199 gimple_stmt_iterator bsi
;
205 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
206 for (bsi
= gsi_start_phis (e
->dest
); !gsi_end_p (bsi
); gsi_next (&bsi
))
207 sese_build_liveouts_use (region
, liveouts
, bb
,
208 PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi
), e
));
210 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
212 gimple stmt
= gsi_stmt (bsi
);
214 if (is_gimple_debug (stmt
))
217 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
218 sese_build_liveouts_use (region
, liveouts
, bb
, USE_FROM_PTR (use_p
));
222 /* For a USE in BB, return true if BB is outside REGION and it's not
223 in the LIVEOUTS set. */
226 sese_bad_liveouts_use (sese region
, bitmap liveouts
, basic_block bb
,
232 if (TREE_CODE (use
) != SSA_NAME
)
235 ver
= SSA_NAME_VERSION (use
);
237 /* If it's in liveouts, the variable will get a new PHI node, and
238 the debug use will be properly adjusted. */
239 if (bitmap_bit_p (liveouts
, ver
))
242 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (use
));
245 || !bb_in_sese_p (def_bb
, region
)
246 || bb_in_sese_p (bb
, region
))
252 /* Reset debug stmts that reference SSA_NAMES defined in REGION that
253 are not marked as liveouts. */
256 sese_reset_debug_liveouts_bb (sese region
, bitmap liveouts
, basic_block bb
)
258 gimple_stmt_iterator bsi
;
262 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
264 gimple stmt
= gsi_stmt (bsi
);
266 if (!is_gimple_debug (stmt
))
269 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
270 if (sese_bad_liveouts_use (region
, liveouts
, bb
,
271 USE_FROM_PTR (use_p
)))
273 gimple_debug_bind_reset_value (stmt
);
280 /* Build the LIVEOUTS of REGION: the set of variables defined inside
281 and used outside the REGION. */
284 sese_build_liveouts (sese region
, bitmap liveouts
)
289 sese_build_liveouts_bb (region
, liveouts
, bb
);
290 if (MAY_HAVE_DEBUG_STMTS
)
292 sese_reset_debug_liveouts_bb (region
, liveouts
, bb
);
295 /* Builds a new SESE region from edges ENTRY and EXIT. */
298 new_sese (edge entry
, edge exit
)
300 sese region
= XNEW (struct sese_s
);
302 SESE_ENTRY (region
) = entry
;
303 SESE_EXIT (region
) = exit
;
304 SESE_LOOPS (region
) = BITMAP_ALLOC (NULL
);
305 SESE_LOOP_NEST (region
).create (3);
306 SESE_ADD_PARAMS (region
) = true;
307 SESE_PARAMS (region
).create (3);
312 /* Deletes REGION. */
315 free_sese (sese region
)
317 if (SESE_LOOPS (region
))
318 SESE_LOOPS (region
) = BITMAP_ALLOC (NULL
);
320 SESE_PARAMS (region
).release ();
321 SESE_LOOP_NEST (region
).release ();
326 /* Add exit phis for USE on EXIT. */
329 sese_add_exit_phis_edge (basic_block exit
, tree use
, edge false_e
, edge true_e
)
331 gimple phi
= create_phi_node (NULL_TREE
, exit
);
332 create_new_def_for (use
, phi
, gimple_phi_result_ptr (phi
));
333 add_phi_arg (phi
, use
, false_e
, UNKNOWN_LOCATION
);
334 add_phi_arg (phi
, use
, true_e
, UNKNOWN_LOCATION
);
337 /* Insert in the block BB phi nodes for variables defined in REGION
338 and used outside the REGION. The code generation moves REGION in
339 the else clause of an "if (1)" and generates code in the then
340 clause that is at this point empty:
349 sese_insert_phis_for_liveouts (sese region
, basic_block bb
,
350 edge false_e
, edge true_e
)
354 bitmap liveouts
= BITMAP_ALLOC (NULL
);
356 update_ssa (TODO_update_ssa
);
358 sese_build_liveouts (region
, liveouts
);
359 EXECUTE_IF_SET_IN_BITMAP (liveouts
, 0, i
, bi
)
360 sese_add_exit_phis_edge (bb
, ssa_name (i
), false_e
, true_e
);
361 BITMAP_FREE (liveouts
);
363 update_ssa (TODO_update_ssa
);
366 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */
369 get_true_edge_from_guard_bb (basic_block bb
)
374 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
375 if (e
->flags
& EDGE_TRUE_VALUE
)
382 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */
385 get_false_edge_from_guard_bb (basic_block bb
)
390 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
391 if (!(e
->flags
& EDGE_TRUE_VALUE
))
398 /* Returns the expression associated to OLD_NAME in RENAME_MAP. */
401 get_rename (rename_map_type rename_map
, tree old_name
)
403 struct rename_map_elt_s tmp
;
404 rename_map_elt_s
**slot
;
406 gcc_assert (TREE_CODE (old_name
) == SSA_NAME
);
407 tmp
.old_name
= old_name
;
408 slot
= rename_map
.find_slot (&tmp
, NO_INSERT
);
411 return (*slot
)->expr
;
416 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR). */
419 set_rename (rename_map_type rename_map
, tree old_name
, tree expr
)
421 struct rename_map_elt_s tmp
;
422 rename_map_elt_s
**slot
;
424 if (old_name
== expr
)
427 tmp
.old_name
= old_name
;
428 slot
= rename_map
.find_slot (&tmp
, INSERT
);
435 *slot
= new_rename_map_elt (old_name
, expr
);
438 /* Renames the scalar uses of the statement COPY, using the
439 substitution map RENAME_MAP, inserting the gimplification code at
440 GSI_TGT, for the translation REGION, with the original copied
441 statement in LOOP, and using the induction variable renaming map
442 IV_MAP. Returns true when something has been renamed. GLOOG_ERROR
443 is set when the code generation cannot continue. */
446 rename_uses (gimple copy
, rename_map_type rename_map
,
447 gimple_stmt_iterator
*gsi_tgt
,
448 sese region
, loop_p loop
, vec
<tree
> iv_map
,
453 bool changed
= false;
455 if (is_gimple_debug (copy
))
457 if (gimple_debug_bind_p (copy
))
458 gimple_debug_bind_reset_value (copy
);
459 else if (gimple_debug_source_bind_p (copy
))
467 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, op_iter
, SSA_OP_USE
)
469 tree old_name
= USE_FROM_PTR (use_p
);
473 if (TREE_CODE (old_name
) != SSA_NAME
474 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
478 new_expr
= get_rename (rename_map
, old_name
);
481 tree type_old_name
= TREE_TYPE (old_name
);
482 tree type_new_expr
= TREE_TYPE (new_expr
);
484 if (type_old_name
!= type_new_expr
485 || TREE_CODE (new_expr
) != SSA_NAME
)
487 tree var
= create_tmp_var (type_old_name
, "var");
489 if (!useless_type_conversion_p (type_old_name
, type_new_expr
))
490 new_expr
= fold_convert (type_old_name
, new_expr
);
492 new_expr
= force_gimple_operand (new_expr
, &stmts
, true, var
);
493 gsi_insert_seq_before (gsi_tgt
, stmts
, GSI_SAME_STMT
);
496 replace_exp (use_p
, new_expr
);
500 scev
= scalar_evolution_in_region (region
, loop
, old_name
);
502 /* At this point we should know the exact scev for each
503 scalar SSA_NAME used in the scop: all the other scalar
504 SSA_NAMEs should have been translated out of SSA using
505 arrays with one element. */
506 if (chrec_contains_undetermined (scev
))
509 new_expr
= build_zero_cst (TREE_TYPE (old_name
));
512 new_expr
= chrec_apply_map (scev
, iv_map
);
514 /* The apply should produce an expression tree containing
515 the uses of the new induction variables. We should be
516 able to use new_expr instead of the old_name in the newly
517 generated loop nest. */
518 if (chrec_contains_undetermined (new_expr
)
519 || tree_contains_chrecs (new_expr
, NULL
))
522 new_expr
= build_zero_cst (TREE_TYPE (old_name
));
525 /* Replace the old_name with the new_expr. */
526 new_expr
= force_gimple_operand (unshare_expr (new_expr
), &stmts
,
529 gsi_insert_seq_before (gsi_tgt
, stmts
, GSI_SAME_STMT
);
530 replace_exp (use_p
, new_expr
);
532 if (TREE_CODE (new_expr
) == INTEGER_CST
533 && is_gimple_assign (copy
))
535 tree rhs
= gimple_assign_rhs1 (copy
);
537 if (TREE_CODE (rhs
) == ADDR_EXPR
)
538 recompute_tree_invariant_for_addr_expr (rhs
);
541 set_rename (rename_map
, old_name
, new_expr
);
547 /* Duplicates the statements of basic block BB into basic block NEW_BB
548 and compute the new induction variables according to the IV_MAP.
549 GLOOG_ERROR is set when the code generation cannot continue. */
552 graphite_copy_stmts_from_block (basic_block bb
, basic_block new_bb
,
553 rename_map_type rename_map
,
554 vec
<tree
> iv_map
, sese region
,
557 gimple_stmt_iterator gsi
, gsi_tgt
;
558 loop_p loop
= bb
->loop_father
;
560 gsi_tgt
= gsi_start_bb (new_bb
);
561 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
565 gimple stmt
= gsi_stmt (gsi
);
569 /* Do not copy labels or conditions. */
570 if (gimple_code (stmt
) == GIMPLE_LABEL
571 || gimple_code (stmt
) == GIMPLE_COND
)
574 /* Do not copy induction variables. */
575 if (is_gimple_assign (stmt
)
576 && (lhs
= gimple_assign_lhs (stmt
))
577 && TREE_CODE (lhs
) == SSA_NAME
578 && is_gimple_reg (lhs
)
579 && scev_analyzable_p (lhs
, region
))
582 /* Create a new copy of STMT and duplicate STMT's virtual
584 copy
= gimple_copy (stmt
);
585 gsi_insert_after (&gsi_tgt
, copy
, GSI_NEW_STMT
);
587 maybe_duplicate_eh_stmt (copy
, stmt
);
588 gimple_duplicate_stmt_histograms (cfun
, copy
, cfun
, stmt
);
590 /* Create new names for all the definitions created by COPY and
591 add replacement mappings for each new name. */
592 FOR_EACH_SSA_DEF_OPERAND (def_p
, copy
, op_iter
, SSA_OP_ALL_DEFS
)
594 tree old_name
= DEF_FROM_PTR (def_p
);
595 tree new_name
= create_new_def_for (old_name
, copy
, def_p
);
596 set_rename (rename_map
, old_name
, new_name
);
599 if (rename_uses (copy
, rename_map
, &gsi_tgt
, region
, loop
, iv_map
,
602 gcc_assert (gsi_stmt (gsi_tgt
) == copy
);
603 fold_stmt_inplace (&gsi_tgt
);
610 /* Copies BB and includes in the copied BB all the statements that can
611 be reached following the use-def chains from the memory accesses,
612 and returns the next edge following this new block. GLOOG_ERROR is
613 set when the code generation cannot continue. */
616 copy_bb_and_scalar_dependences (basic_block bb
, sese region
,
617 edge next_e
, vec
<tree
> iv_map
,
620 basic_block new_bb
= split_edge (next_e
);
621 rename_map_type rename_map
;
622 rename_map
.create (10);
624 next_e
= single_succ_edge (new_bb
);
625 graphite_copy_stmts_from_block (bb
, new_bb
, rename_map
, iv_map
, region
,
627 remove_phi_nodes (new_bb
);
628 rename_map
.dispose ();
633 /* Returns the outermost loop in SCOP that contains BB. */
636 outermost_loop_in_sese (sese region
, basic_block bb
)
640 nest
= bb
->loop_father
;
641 while (loop_outer (nest
)
642 && loop_in_sese_p (loop_outer (nest
), region
))
643 nest
= loop_outer (nest
);
648 /* Sets the false region of an IF_REGION to REGION. */
651 if_region_set_false_region (ifsese if_region
, sese region
)
653 basic_block condition
= if_region_get_condition_block (if_region
);
654 edge false_edge
= get_false_edge_from_guard_bb (condition
);
655 basic_block dummy
= false_edge
->dest
;
656 edge entry_region
= SESE_ENTRY (region
);
657 edge exit_region
= SESE_EXIT (region
);
658 basic_block before_region
= entry_region
->src
;
659 basic_block last_in_region
= exit_region
->src
;
660 void **slot
= htab_find_slot_with_hash (current_loops
->exits
, exit_region
,
661 htab_hash_pointer (exit_region
),
664 entry_region
->flags
= false_edge
->flags
;
665 false_edge
->flags
= exit_region
->flags
;
667 redirect_edge_pred (entry_region
, condition
);
668 redirect_edge_pred (exit_region
, before_region
);
669 redirect_edge_pred (false_edge
, last_in_region
);
670 redirect_edge_succ (false_edge
, single_succ (dummy
));
671 delete_basic_block (dummy
);
673 exit_region
->flags
= EDGE_FALLTHRU
;
674 recompute_all_dominators ();
676 SESE_EXIT (region
) = false_edge
;
678 free (if_region
->false_region
);
679 if_region
->false_region
= region
;
683 struct loop_exit
*loop_exit
= ggc_alloc_cleared_loop_exit ();
685 memcpy (loop_exit
, *((struct loop_exit
**) slot
), sizeof (struct loop_exit
));
686 htab_clear_slot (current_loops
->exits
, slot
);
688 slot
= htab_find_slot_with_hash (current_loops
->exits
, false_edge
,
689 htab_hash_pointer (false_edge
),
691 loop_exit
->e
= false_edge
;
693 false_edge
->src
->loop_father
->exits
->next
= loop_exit
;
697 /* Creates an IFSESE with CONDITION on edge ENTRY. */
700 create_if_region_on_edge (edge entry
, tree condition
)
704 sese sese_region
= XNEW (struct sese_s
);
705 sese true_region
= XNEW (struct sese_s
);
706 sese false_region
= XNEW (struct sese_s
);
707 ifsese if_region
= XNEW (struct ifsese_s
);
708 edge exit
= create_empty_if_region_on_edge (entry
, condition
);
710 if_region
->region
= sese_region
;
711 if_region
->region
->entry
= entry
;
712 if_region
->region
->exit
= exit
;
714 FOR_EACH_EDGE (e
, ei
, entry
->dest
->succs
)
716 if (e
->flags
& EDGE_TRUE_VALUE
)
718 true_region
->entry
= e
;
719 true_region
->exit
= single_succ_edge (e
->dest
);
720 if_region
->true_region
= true_region
;
722 else if (e
->flags
& EDGE_FALSE_VALUE
)
724 false_region
->entry
= e
;
725 false_region
->exit
= single_succ_edge (e
->dest
);
726 if_region
->false_region
= false_region
;
733 /* Moves REGION in a condition expression:
741 move_sese_in_condition (sese region
)
743 basic_block pred_block
= split_edge (SESE_ENTRY (region
));
746 SESE_ENTRY (region
) = single_succ_edge (pred_block
);
747 if_region
= create_if_region_on_edge (single_pred_edge (pred_block
), integer_one_node
);
748 if_region_set_false_region (if_region
, region
);
753 /* Replaces the condition of the IF_REGION with CONDITION:
761 set_ifsese_condition (ifsese if_region
, tree condition
)
763 sese region
= if_region
->region
;
764 edge entry
= region
->entry
;
765 basic_block bb
= entry
->dest
;
766 gimple last
= last_stmt (bb
);
767 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
770 gcc_assert (gimple_code (last
) == GIMPLE_COND
);
772 gsi_remove (&gsi
, true);
773 gsi
= gsi_last_bb (bb
);
774 condition
= force_gimple_operand_gsi (&gsi
, condition
, true, NULL
,
775 false, GSI_NEW_STMT
);
776 cond_stmt
= gimple_build_cond_from_tree (condition
, NULL_TREE
, NULL_TREE
);
777 gsi
= gsi_last_bb (bb
);
778 gsi_insert_after (&gsi
, cond_stmt
, GSI_NEW_STMT
);
781 /* Returns the scalar evolution of T in REGION. Every variable that
782 is not defined in the REGION is considered a parameter. */
785 scalar_evolution_in_region (sese region
, loop_p loop
, tree t
)
788 struct loop
*def_loop
;
789 basic_block before
= block_before_sese (region
);
791 /* SCOP parameters. */
792 if (TREE_CODE (t
) == SSA_NAME
793 && !defined_in_sese_p (t
, region
))
796 if (TREE_CODE (t
) != SSA_NAME
797 || loop_in_sese_p (loop
, region
))
798 return instantiate_scev (before
, loop
,
799 analyze_scalar_evolution (loop
, t
));
801 def
= SSA_NAME_DEF_STMT (t
);
802 def_loop
= loop_containing_stmt (def
);
804 if (loop_in_sese_p (def_loop
, region
))
806 t
= analyze_scalar_evolution (def_loop
, t
);
807 def_loop
= superloop_at_depth (def_loop
, loop_depth (loop
) + 1);
808 t
= compute_overall_effect_of_inner_loop (def_loop
, t
);
812 return instantiate_scev (before
, loop
, t
);